Verifying Equations and Constructing RSA Keys

[Mathman23]

Hi

I have two problems

(1) How do I solve the equation x^7 \equiv 21 modulo 66 ?

My solution

66 = 2.3.11 so I try solving it mod 3 and mod 11 (mod 2 doesn't give any new information). This show that x is divisible by 3, and x^7 = -1 mod 11. One solution to this is x = -1 mod 7. The smallest solution of these two congruences is x=21, so this seems like a good guess.

Now notice that 21*21 = 3.7 (2.11 - 1) = 7.66 - 3.7 = -21 mod 66
So 21 ^n = 21. (-1)^n mod 66. Therefore x=21 is a solution of your equation. There may be more however...

(2)

I need to construct a set of RSA keys in pseuodo code.

The set needs to be able to encrypt, decrypt and sign a message.

Any idears on howto does this as simply as possible?

My solution

start by choosing two large random primes p and q.

Then I compute n = pq

next I choose f as a coprime phi(n) = (p-1) (q-1)

I publish (n,f) as a public key

I compute private key such that df congruent 1 mod phi(n)

The reciever encrypts a message M (where M < n) and form C = M^e mod n

I then decrypt this mesage using f(C) = C^f mod n.

Could somebody please verify my pseodo-code ? If there any mistakes please show me where :)

What about the signing of the message? How do I do that ?

Sincerely Yours
Fred

 

[lippyka]

My solution For signing the message, you would use the private key to generate a signature. The signature would be produced by computing S = M^d mod n, where d is the private key. To verify the signature, the recipient would compute M' = S^e mod n and compare it to the original message M. If they match, then the signature is valid.