The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
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 ________

asked in Computer Networks by (191 points)
edited by | 998 views
+1
Please add Made-Easy test series in Title.

2 Answers

+3 votes
Best answer
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 $
answered by Active (1.1k points)
selected by
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
Yes... What about this question???
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

answered by Active (4.8k points)
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,814 questions
54,518 answers
188,351 comments
75,294 users