Hi,
How or what should i use to break > 512 rsa key, RSATool cant do it, just like factor from miracl(RSATool == miracl factor?), so what, should i ask santa claus for some cray?

bart

This forum intend to discuss insight of cryptography not how to break them....

Hello Unregistered !

Why don't you buy yourself a computer for $5 000 000 ? I'm sure it will be able to break RSA-512 in less than a week

Um.. The reason they use RSA is because it's hard to break. For instance, if you can factor any of the challenge numbers at RSA.com then you can get from $10K to $200K. The smallest is 576-bits, not too much bigger than what you want to factor.

In other words, it ain't gonna happen.

distributed.net maybe??

Interesting site. Even with the power they claim, it will still take, maybe 3 years. I think the financial incentive, however small, makes it obvious that there has to be a better way to try and break this besides overwhelming computer strength.

Then again, maybe I am talking out my ass :P
Feel free to tell me so I can take it.

Peace, Woodmann

(I should have read the stats page. So 4 years maybe)

With paralel computing it would take less.For example in university we have a project called ASMA which connects more than 30 computer together to solve complex problems

In August 1999, RSA-155 (a number with 512 bits)
was successfully factored after seven months by
smaller groups.
This was done by using the NFS and about 300
workstations and PC:s, this result could today be
achieved alot faster by a well-organized group of
users, perhaps Distributed.Net is such an organization?
However, the cost for breaking it is still to high for
most attackers!

regards
McCodEMaN

If this RSA implementation you are talking about in some application you are trying to break? if so I suggest finding a weakness in the implementation of RSA in the application.

goatass

Thats true, insecure implementation is likely the most easy
way to obtain a successful attack.
However, this would not be an attack at the RSA system, so
everything depends on your purpose!

regards
McCodEMaN

RSA-518 - factored in less than a second...

E:
10001
N:
1FCA57ACAC6156F69315EAF1A9D6314EDB8CBCF0746F888BF290557FEC4689C71
D:
77F50EE08396CA8FA4751016D6C76748292CE7C66F966DA9A7A2FAFDBA94715
P:
3
Q:
A98C7E43975C7A7865CA3A5E34765C4F3D9945026CFD82EA6301C7FF96CD897B

Someone smells what I want to say ?

Hehe... nice one tE

Always a good reminder that we have to be careful what we say when talking about crypto stuff!

Cheers!

Kythen

Woah, I feel like mom just smacked me with the wooden spoon on my ass. :O

Have you factor 512 rsa in seconds!
How did you do that? what did you know from start?

P i much smaller than Q?

tE tell me, how you(i mean DAMN) have cracked key from ASProtect?

bart

Hi there.

As you might have noticed one of the prime factors of N
is 3 and as you know the size of P and Q should normally not differ too much. All I wanted to say with posting that example
is that it depends also a lot on carefully chosen parameters for
the RSA system (goatass already said it might be useful to
search for weak points in the implementation). The N I posted will be factored in no noticable amount of time by every lame
factoring program which starts with trial division by small primes.

---

Recca/DAMN could break the RSA-1024 system in older versions
of Asprotect, because he discovered a weakness in Asprotect's
primenumber generator. Alexey used a .dll (which has been
stored inside the asprotect.exe as compressed resource) to
generate both primenumbers P and Q. To manage this he used
some shitty pseudo random number generator (PRNG) routine to generate
512 bits of 'random' data for each number, P and Q. Then he tested if those numbers are prime. If not -> increase number
and test again. <- Loop. The prng he used was similar to the C rand() function. But it comes even worse. As SEED value for this
crap generator he used a 32(!) Bit value which was some mixture
of ThreadID XOR some Timestamp if I remember right

Well, everyone can see now how it was possible to break this
lame crap. There was no need to factor the public modulus N.
All efforts could be reduced to a complexity of max. 2^32
bruteforce attempts using the ripped prime number generator
from Alexey and perform one trial modulus operation for each
seed value, thus each generated primenumber. Basically:

1) seed=-1;
2) seed++;
2) Prime=GeneratePrimeUsingAlexeysShit(seed);
3) remainder=N%Prime
4) If (remainder==0) -> P=Prime, Q=N
5) Else goto 2

Infact the complexity wasn't even 2^32 (means you would
not start with seed=0) because of the timestamp he used in the
seed. TMG released keygens for asprotected programs, too and
we measured on my Athlon 800 that it was possible to factor
*every* asprotect key in max. 12h. We could find parameters
P&Q for some programs in less than 20 minutes even. Not bad
for such super-secure program like asprotect

Sidenote: As many other routines in Asprotect (compression, polyengine...) the .dll Alexey used hasn't been coded by himself, as usual...Well, at least he's good in 'borrowing' other peoples
code.

Another leeto who fucked up his RSA-512 'protection' in his
ugly Asprotect clone was/is Bruno Branciforti in his
License Control v1.01 application. I'm not gonna post here
what he did wrong, because we released a keygen for this
program and good old Bruno already tried to bother us on
IRC for info how we made that (the moron came into our
chan using a fake nick and introduced himself as cracker - lol).

Oke, hope someone finds this posting useful.

Regards,

tE![TMG]

Greetings!

True, the factorization example you described above is done in seconds, and I guess you used your own tool (rsa tool 2) to solve it?! Also, it's an excellent example on how one not should select primes.

regards
McCodEMaN