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