Dark Mode

40 votes

$\phi$(n) = (p-1)*(q-1)=192

encryption key (e) =35

we have to choose decryption key(d) such a way that (d*e)%$\phi$(n) =1

(35*11)%192=1

ANS:11

encryption key (e) =35

we have to choose decryption key(d) such a way that (d*e)%$\phi$(n) =1

(35*11)%192=1

ANS:11

We can use extended euclidean algorithm to find the inverse.

$e * d = 1 mod 192$

here, we initialize $t1=0 , t2= 1, r1=192, r2= 35$ where $t=t1-q*t2$

And, proceed as follows:

Shift the values at each step as shown:

q | r1 | r2 | r | t1 | t2 | t |
---|---|---|---|---|---|---|

5 | 192 | 35 | 17 | 0 | 1 | -5 |

2 | 35 | 17 | 1 | 1 | -5 | 11 |

17 | 17 | 1 | 0 | -5 | 11 | -192 |

1 | 0 | 11 | -192 |

Stop the procedure when you get $r2=0$. The value of t1 will give you inverse i.e value of $d=11$

Finally you get **Private key of A =11.**

0

19 votes

2

2

10 votes

RSA ALGO

1. Calculate value of N = P x Q, where P and Q are large prime nos.(given)2. Calculate Z = (P - 1) x (Q - 1)

3. Choose a value for E (Public key) such that E & Z has no common factors other than 1 between them.

4. Calculate value of D (Private key) such that (E*D - 1 ) MOD Z = 0 , OR (E*D MOD Z = 1)

5. A's Public key becomes a tuple pair of <N,E>

6. A's Private key becomes a tuple-pair of <N,D>

7. Encryption formula (Cipher text): C = message

^{E}MOD N8. Decryption formula (Message): message = C

^{D}MOD N

So in the prob. we have P,Q. So we can calc. N & Z

Now,

E*D MOD N = 1

35*D MOD 192 = 1 ....(eqn)

The above eqn can be written as:

35*D = 1 + 192 * K ( K = some positive int.)

If we analyse the above eqn. it can be seen that D > 5 since we get a remainder of 1 on MODULUS.

Find a int. value for K such that , 192 * K + 1= 35*D.

Take K = 2, 1 + 192*2=385;

**35*11 which implies D = 11 (ANS)**