19,781 views
In a RSA cryptosystem, a participant $A$ uses two prime numbers $p = 13$ and $q = 17$ to generate her public and private keys. If the public key of $A$ is $35$, then the private key of $A$ is __________ .

That's a blessing in disguise for this question.
$d\times 35 = 1 \text{ mod } 192$

we can write it as:

$d = \frac{1+k\phi}{e} = \frac{1+k\times192}{35}$ , now just put $k's$ value

$d = \frac{1+2\times192}{35} = \frac{385}{35} = 11$
how would you solve this question during exam time ?

$\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

Stackoverflow solution is not proper . Mathematical rules are broken

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.

Efficient for bigger values

by

Not sure if its right methodology or not but usually the co-prime number is a prime number. So I checked only for prime numbers - 3, 5, 7, 11. And got ans in less than 2 minutes.
@ yashgupta1992
what is the procedure?
can u tell me in detail
@Srestha I dont recall the procedure, but due to rigrous practice intutively I knew the other number will be only a prime and hence did not waste time for looking at every other number. Though I will research out if there is a mathematical logic behind it.
Apart from given condition or rules; is there any other rules for applying this formulae . Or we can apply this step any time at any set of input(s).

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 = messageE MOD N

8. Decryption formula (Message):  message = CD 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)

From given data, we find-

$\Rightarrow$ $35*d \equiv 1 (mod 192)$

Where $d$ is description key.

Also, we have.

From euclidean theorem,

$11*35-192*2=1$

Comparing with $35x + 192y=1$

We get $x = 11.$ as the value of d.
by

Best solution