edited by
11,945 views
2 votes
2 votes

In an RSA system, the public key of given user is e = 31 and n = 3599. The private key of user will be ________

edited by

2 Answers

Best answer
3 votes
3 votes
Given $n$=3599 and $e$=31

$n$ = $p*q$ where $p$ and $q$ are prime numbers

 

$3599 = 59 * 61$

We have, $ed$=$1mod\phi(n) $

Where , $ \phi(n) $ is Euler's tortient function .

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

$ \phi(n) = 58 * 60  = 3480 $

Now 31 * $d$ = $1mod( 3480) $

 

 

$3480 * X + 31 * Y  = 1$

Step1:  Eucledian Algorithm

----------------------------------------------

3480 = 112 * (31) + 8

31 = 3 * (8) + 7

8 = 1 * (7) + 1

Step 2 : Back Substitution

-----------------------------------------

1 = 8 - 1(7)

1 = 8 - 1( 31 - 3(8) )

1 = 4(8) - 1(31)

1 = 4( 3480 - 112(31)  ) - 1(31)

1 = 4(3480) - 449(31)

Since 449 is a negative number substract from tortient function

So that $d = 3480 - 449 = 3031 $
selected by
1 votes
1 votes

n=3599=3600-1 = 60*60 - 1 = 60^2 - 1^2 = (60+1)(60-1) = 61*59 = p*q
p=61
q=59

phi(n) = (p-1)(q-1) = (61-1)(59-1) = 60*58 = 3480

 

(e*d) % phi(n) = 1

31d % 3480 = 1

Divident = 31d

Quotient = k

Divisor = 3480

Remainder = 1

Divident = remainder + quotient*divisor

=> 31d = 1 + k*3480

=> d=(1+k*3480)/31

k,d are positive integers

By Brute Force, If I apply k=27, then I get (1+27*3480)/31 = (1+93960)/31 = 93961/31 = 3031

 

In Exam, depending on Time, u can apply either this or AMALJITH 's procedure

Related questions