998 views

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

edited | 998 views
+1

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
0
how you got that p and q values exactly???
0
$3600 = 60 * 60$

$3599 = (60 - 1) * (60 +1 )$

Luckily Got This Primes Easily By Intuition Only
0
The whole purpose of RSA is to choose primes so that intruder cannot get the intuition of prime numbers. :p
0
0
The solution given by him is correct. Question is not wrong and checks the concept.
0
What  i mean, is this really a valid question??

The complexity of this question is behind the illogical guessing
0
yeah the guessing part is illogical.
0

this will clear all steps

+1 vote

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

0
how u found k??
0
BRUTE FORCE
0
I kept on trying from 1 to 27 :(
0
so there is no approach except guessing it?
0
Unfortunately, Yes

+1 vote