Alice decides to use RSA with the public key N = 1889570071. In order to guard a

Question

Alice decides to use RSA with the public key N = 1889570071. In order to guard against transmission errors, Alice has Bob encrypt his message twice, once using the encryption exponent e1 = 1021763679 and once using the encryption exponent e2 = 519424709. Eve intercepts the two encrypted messages

c1 = 1244183534 and c2 = 732959706.

Assuming that Eve also knows N and the two encryption exponents e1 and e2, use the method described in Example 3.14 to help Eve recover Bob’s plaintext without finding a factorization of N.

Erample 3.14. Suppose that Alice publishes two different exponents el and eo for use with her public modulus N and that Bob encrypts a single plaintext m using both of Alice's exponents. If Eve intercepts the ciphertexts

Explanation / Answer

Answer:

C1=me1(modN)

C2=me2(modN)

Eve intercepts c1 and c2 . as we know e1 and e2 are relatively prime . therefore GCD(e1,e2)=1.

Now we can find x and y belongs to z so that

e1x+e2y=1

For claciulating x and y values we can use extended euclidens algorithm we can find x and y values.

1021763679 x + 519424709 y = 1

Using extended euclidens algorithm we got the values as

x = 25246389

Y= -496549570

Therefore eve clacilates

C1x.c2y=mxe1.mye2(modN)

=mxe1+ye2(modN)

=m1 modN

Therefore c1x.c2y=m(modN)

1021763679 25246389 + 519424709 -496549570 = m (mod 1889570071).

Finally we got the m value without finding a factorization of N.

We can find Bob’s plaintext without finding a factorization of N.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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