Question

(i) Find Bezout’s Identity for 53 and 61.
Using RSA, you send Alice the modulus m = 3233 (= 53 · 61) and

the encrypting exponent e = 7. Alice has a two-letter message that she turns into a number ≤ 2626 and encrypts and sends you. You receive c = 1067. You have already determined that the decrypting exponent is d = 1783.

(ii) Find c^d (mod 53) and c^d (mod 61).

(iii) Then use Bezout’s identity from (i) to find Alice’s plaintext message.

Answer 1

(i)

Bezout’s Identity is the gcd of two co-prime integers. Bezout’s Identity for 53 and 61 can be calculated as follows:

Bezout’s Identity = gcd(a, b)           [a=53, b=61]

                           = gcd(53, 61)

                           =1

Gcd(a, b) = ax + by

               = 53x + 61y

= 1

According to Bezout’s Identity the multiplicative inverse of e modulo (n) can be calculated as follows:

d= e modulo (n)                [(n) = (p-1)*(q-1) = (a-1)*(b-1) = (53-1)*(61-1) = 3120]

= 7 modulo 3120.

= 1783

Thus, d = 1783.

(ii)

C^d(mod 53)

= 1067¹⁷⁸³mod 53

= 4

C^d(mod 61)

= 1067¹⁷⁸³mod 61

= 17

(iii)

The Bezout’s identity in part(i) shows that the multiplicative inverse of 7 modulo 3120 is 1783. It can be verified by calculating 7 × 1783 mod 3120 = 1. Thus, d = 1783, c = 1067 and N = 3233.

Alice plaintext message can be calculated as follows:

P = C^dmod N

P = C^dmod m                                                [N=p*q=m]

P = 1067¹⁷⁸³ mod 3233=322

P = 322