RSA multi factor

labba · 2016-01-30, 23:07

hi,
i have used the YaFu and entered a N of an RSA and it solved it by giving me back 15 primes... how can i continue from this point on to break the small RSA key that i have ?

Mini-Geek · 2016-01-30, 23:19

Are you sure you've got the right N? Any good key choice (if not any valid key, if this article's offhand comment is right) will be a semiprime, not consist of 15 primes.

Anyway, once you've got the right number factored, this post from StackOverflow goes into (the mathematical side, not a script or anything) how to calculate the private key. The most important part is this: (d is the private exponent, e is the public exponent, n is the public key, n is semiprime with factors p and q)

Code:

d = e^-1 mod phi(n)
  = e^-1 mod (p-1)*(q-1)

(note that if you don't have a semiprime, the phi calculation gets more complicated)

Then you just need to compute that modular multiplicative inverse, convert the number into a usable format (hex?) and use it.

wombatman · 2016-01-30, 23:25

Sounds like a Teslacrypt infection. You may wish to head over here if that's the case: http://www.mersenneforum.org/showthread.php?t=20767

2016-01-30, 23:07	#1
labba Jan 2016 1 Posts	RSA multi factor hi, i have used the YaFu and entered a N of an RSA and it solved it by giving me back 15 primes... how can i continue from this point on to break the small RSA key that i have ?

2016-01-30, 23:19	#2
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 17·251 Posts	Are you sure you've got the right N? Any good key choice (if not any valid key, if this article's offhand comment is right) will be a semiprime, not consist of 15 primes. Anyway, once you've got the right number factored, this post from StackOverflow goes into (the mathematical side, not a script or anything) how to calculate the private key. The most important part is this: (d is the private exponent, e is the public exponent, n is the public key, n is semiprime with factors p and q) Code: d = e^-1 mod phi(n) = e^-1 mod (p-1)(q-1) (note that if you don't have a semiprime, the phi calculation gets more complicated) Then you just need to compute that modular multiplicative inverse, convert the number into a usable format (hex?) and use it. Last fiddled with by Mini-Geek on 2016-01-30 at 23:28*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
multi-core TF	dbaugh	Information & Answers	3	2011-09-06 01:32
Multi-threaded factoring	bchaffin	Aliquot Sequences	8	2010-10-24 13:38
Multi-Core / Multi-CPU Assignments (missing)	worknplay	Software	3	2008-11-05 17:26
Dual (or multi) motherboards?	uigrad	Hardware	16	2008-10-18 08:36
Multi CPU installation using GUI client ?	willy1	NFSNET Discussion	5	2004-03-18 13:19

2016-01-30, 23:25	#3
wombatman I moo ablest echo power! May 2013 11011101001₂ Posts	Sounds like a Teslacrypt infection. You may wish to head over here if that's the case: http://www.mersenneforum.org/showthread.php?t=20767