This is a longer problem to read, but otherwise, it shouldn’t require much work.

Question

This is a longer problem to read, but otherwise, it shouldn’t require much

work.

The RSA encryption algorithm was described by Rivest, Shamir and Adleman; the letters RSA stand for their initials. We will describe briefly how this works.

The RSA algorithm involves three steps:

(i) key generation: – chosep,q twoprimenumbers and let n=pq, so that (n)=(p1)(q1);

– Let 1 < e < (n) be a number coprime with (n) and let d be chosen such that

de 1   mod (n).

The number d is computed via the Euclidean algorithm. Its existence follows since

(e, (n)) = 1. Then:

– the pair (n, e) is the public key;

– the pair (n, d) is the private key (or rather, d is the private key exponent).

(ii) encryption:

– Alice transmits her public key (n, e) to Bob, and keeps the private exponent d secret. – Bob then wishes to send a message M to Alice. The message M is encoded as an integer 0 < m < n with (m,n) = 1 which is obtained via an agreed-upon reversible protocol.

– Bob computes the integer c such that 0 < c < n and

c me   mod n.

Since Bob knows the public key (n, e) as well as the message m, then he can certainly

calculate the integer c. Bob then transmits c to Alice.

(iii) decryption: When Alice receives c, the original message m is recovered by computing

cdm modn. While the key d is secret, d is however known to Alice, who then also can compute m.

Answer the following questions (no work is required for (b)):

(a) Explain why the decryption step (iii) works, so that Alice does recover the message m.

(b) In order to crack the code, an eavesdropper may overhear c, but to find m he must must know d. Since de 1 mod (n) and e is public, finding d would be guaranteed once (n) is known. However,

(n) = (p 1)(q 1)

and this last step requires the prime factorization of n. If the primes p, q are chosen to be

large, then cipher may be hard to break.

(c) Explicitly work out a “baby” example. You should not use a calculator for this part.

Pick p = 11, q = 13, e = 113.

– What is the public key? What is the private key? – How would Bob transmit the message m = 15? Here you can use Fermat’s theorem

for the primes p and q and assemble the answer using the Chinese remainder theorem.

Explanation / Answer

a) Decryption :

Decryption is the process of converting cipher text message into original message format understandable by the received end user.Yes Alice can recover the original by computing the required calculations.

b) An eavesdropper may hear the c but he cannot get the compute the primes for p,q values so that the message cannot be decrypted.if he tries hardly he may get decrypted.

c)given p=11,q=13,e=113

n=p*q=11*13=143

pie(n)=(p-1)*(q-1)=10*12=120

to compute d

d=(e mod pie(n))=1

but there are noco-primes113,120

only 1

public key(e,n)={113,120)

private key(d,n)={1,120}

message M=15

C=15^e %120=7.912474e+132 %120=6.593728e+130

M=C^d%120=6.593728e+130%120=15

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.