In an RSA system the public key (e,n) of user A is defined as (7,119). Calculate Φn and private key d. what is the cipher text when you encrypt message m=10, using the public key? -

Given Data:

• Public Key (e,n) = (7,119)
• Message m=10

Solution:

• From given data we find that e=7 and n=119.

• The formula for n is: n= p *q.

  That means, p and q should be a factor of 119. Two such numbers are 7 and 17.

  Therefore, p=17 and q=7

• Now, Φ (n) = (p-1) * (q-1) .

  Therefore, $Φ (n) = (p-1)*(q-1) \\ Φ (n) = (17-1)*(7-1) \\ Φ (n) = 96$

• Now, the condition on e and Φ (n) is that GCD(e, Φ(n))=1 .

  We can see that this condition is satisfied by the current values of e and φ(n) i.e. GCD(7,96)=1.

• Next we determine d.

  It is given as d*e=1 mod Φ (n) where d < Φ (n).

  Therefore: d*7 =1 mod 96

• To obtain d we apply Euclid’s inverse algorithm (extended Euclid’s algorithm is used to find out the multiplicative inverse of a number. Follow the steps mentioned below to obtain the answer)

• Construct a table as below and fill with the given values: As seen r1 and r2 will have the values of Φ (n) and e respectively. Also, t1 and t2 will have default values as 0 and 1.

• Next, we solve just for the first half of the table by following basic arithmetic i.e. dividing r1/r2 ; placing the quotient in q and remainder in r.

• Now, shift down the values of r2 and r to the next row’s r1 and r2 column. And carry out the arithmetic operation on it.

• Proceed forward until you get 0 in the r2 column.

• Now, we move to the second half. Here there is only one formula:

  t=t1 – (q * t2)

• We need to end the process when the number of rows gets exhausted i.e. till that row where first half ended.
• Now
  • If t1 is negative: add t2 to t1. That’s your value of d (d=t1+t2)
  • Else if t1 is positive, d=t1
• Here , d= -41+96=55
• To send message m = 10 :
  • To send a message, we need to encrypt it. For encryption we use the public key (e,n).
  • While receiving a message, we decrypt the message using the private key (d,n)
• Encryption:
  • E = $m^e$ mod n = $10^7$ mod 119
  • 107 mod 119= [(101 mod 119) x (102 mod 119) x (104 mod 119)]mod 119
  • ($10^1$ mod 119)=10
  • ($10^2$ mod 119)=100
  • ($10^4$ mod 119)=4
  • $10^7$ mod 119= [10 * 100 * 4]mod 119 =4000 mod 119=73
  • Therefore E=73, which is the encrypted message.