This one ...

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+18 votes

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

+14 votes

+1

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.

+22 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

+11

attempting such questions with an on-screen calculator could be a tough task, (in this case) you check for d=5,6,7,8,.... and hope you get answer before 19 otherwise your 1.5 minutes are wasted. Speaking for myself in examination I felt, relying on repetitive calculations increases the panic level. A better approach would be

We know

*ϕ*(n)=192 and e=35, so

(35*d)%192=1 OR 35*d=192k+1 for some k

now look at RHS, last digit of 192k (be it any k) will be {2,4,6,8,0}, add 1 to them and you'll see last digit of RHS will always be {3,5,7,9,1}

as you can see on LHS the last digit is 5, there is no way you can get {3,7,9,1} on the last digit of 35*d, be it any d you pick. Now you can conclude that last digit of 35*d is definitely 5. Therefore you need to check for odd values only. Check for d=5,7,9,11,... time halved

@happy singh: in RSA crypto, they settle for smallest d found. Chalo by chance you got 203, what you should have done is check for any smaller than 203 (which is relatively easy)

subtract a number (say A) from 35*203 such that it is a multiple of both 35 and 192, not necessarily LCM.

As 35*203 > product of (35,192), go for 35*192

35*203 - 35*192 = 35*11

you could have got 11

+6 votes

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.

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

+6 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)**

+4 votes

Approach

Find first number bigger than 192 which is divided by 35 = 210

210%192 = 18

taking twice of 210*2 = 420

420%192 = **36**

Clearly, visible 36 is 1 more than 35

That means Subtract 35 from 420 = 385 so that remainder can be reduced to 1(Required condition of RSA ** (d*e) mod ϕ(n) =1**)

So, e*d = 385 => 35*d = 385

**d = 11**

+3 votes

(what i did), first i calculated n i.e. 13*17,

then z = (p-1)*(q-1) = 12*16= 192.

to find private key from given public key i.e. e=35 we need to find d which satisfy the equation

e*d = 1(mod z) or e*d mod z =1

i focused on z = 192, and try to find which multiple of 192 can give remainder 1 when divided by 35 , luckily i got 192*2= 385

which satisfy 35*11 mod 192 =1.

mp point here is instead of doing a lengthy work, try the simple one GATE will not try to test your calculation skill

then z = (p-1)*(q-1) = 12*16= 192.

to find private key from given public key i.e. e=35 we need to find d which satisfy the equation

e*d = 1(mod z) or e*d mod z =1

i focused on z = 192, and try to find which multiple of 192 can give remainder 1 when divided by 35 , luckily i got 192*2= 385

which satisfy 35*11 mod 192 =1.

mp point here is instead of doing a lengthy work, try the simple one GATE will not try to test your calculation skill

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 495
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,104 questions

44,682 answers

127,203 comments

43,742 users