Question

Part 3: Lets say you intercept the ciphertext C = 10 sent to a user whose public key is e = 5, n Place answers to all parts in a pdf document attached to the assignment submission. 35, what is the plaintext M? Show all of your steps.

Answer 1

using RSA algorithm

Let two primes be p = 7 and q = 5

modulus n = pq = 7 x 5 = 35

Given e = 5, n= 35

The pair of numbers (n, e) = (35, 5) forms the public key and can be made available to anyone whom we wish to be able to send us encrypted messages.

Input be p = 7 , q = 5, and e = 5 to the Extended Euclidean Algorithm.

∅ =(p-1)(q-1)

∅ =(7-1)(5-1)

= 6*4

∅=24

For d = d*e mod ∅

d*5mod 24=1

ax+by=gcd(a,b)……equ 1

a=∅ , b=e

a=24, b=5

put the value of a , b in equ 1

∅x+ey=gcd(∅, e)

24x+5y=gcd(24, 5).......equ 2

row	a	b	d	k
1	1	0	24	-
2	0	1	5	4
3	1	-4	4	1
4	-1	5	1

in table a1,a2 ,b1, b2 is assume value and ,d1 and d2 is respectively ∅ and e

now k2=d1 divide by d2

a3= a1-(a2*k2)

b3= b1-(b2*k2)

d3=d1-(d2*k2)

now a4= x , b4= y,

put these value in equ 2

24x+5y=gcd(24, 5)

24*(-1)+5*(5)=gcd(24, 5)

-24+25=gcd(24, 5)

1=gcd(24, 5)

condition of d

if d>∅

d=d mod ∅

here d=b4=5

then

5+24= 29

the output will be d = 29

now plaintext=?

p= c to the power d mod n

p= 10 to the power 29 mod 35

p= 82

answer is 82.