Question

For solving the problems, you are required to use the following formalization of the RSA public-key cryptosystem.

In the RSA public-key cryptosystem, each participants creates his public key and secret key according to the following steps:

·       Select two very large prime number p and q. The number of bits needed to represent p and q might be 1024.

·       Compute

               n = pq

                          (n) = (p – 1) (q – 1).

The formula for (n) is owing to Theorem: The number of elements in is given by Euler’s totient function, which is     

                          

where the product is over all primes that divide n, including n if n is prime.

·       Choose a small prime number as an encryption component g, that is relatively prime to (n).   That means,

                        gcd(g, (n) ) = 1, i.e.,

                        gcd(g, (p-1)(q-1)) = 1.

·        Compute the multiplicative inverse   That is,

                       

The inverse exists and is unique.

            That is, the decryption component h = g^-1 mod (n).

·       Let pkey = (n, g) by the public key, and skey = (n, h) be the secret key.

·       For any message M mod n, the encryption of M is C = M^g mod n.

·       The decryption of C is M = C^h mod n.

End of the formalization of the RSA public-key cryptosystem.

Let g = 59, p = 991 and q = 997.

Problem B: [20 pts.]

Given a plaintext M = 5065747269, what is the encryption of M, using C = M^g mod n. Show in details how you derive C, which is the ciphertext of the plaintext M.

Answer 1

Ans:

here p=991 and q=997

And the Encryption key g=59

so,now

n=p*q=991*997 = 988027

(n)= (p-1)*(q-1) =990*996 = 986040

And now we selected public key(encryption key) g =59

Now, private key (decryption key) h was given by,

g=h^-1 mod(n)  

or this can be wrriten as g*h =1 mod (n)

59*h =1 mod 986040

59 * 584939 = 1 mod 986040 (true)

so, decryption key (h) =584939

Now,

given that plaintext M = 5065747269,

Now Ciphertext was given by,

C=M^g mod n = 5065747269 ⁵⁹ mod 988027 = 433940

so, the Ciphertext C= 433940