So the way I read it.

Given two numbers p and q. Which for RSA are supposed to be large primes.

Then n = p*q

The public key is the two fields (n, e).  e is called the public exponent and appears to be chosen from a set of common values.
The private key is also two fields (n, d). d is called the private exponent it it is derived by knowing  e, p-1, and q-1.

The trick is, it is really hard to factor n into p & q. Therefore it is equally as hard to find p-1 and q-1

My postulation is that if n is arbitrary, and e is one of the common values, then there are lots of different p, q pairs that would work. The less prime the numbers the easier to find p and q, and therefore p-1 and q-1. And if you have a big block of arbitrary data that give you lots of flexibility in trying to collide a hash.

(That is the point where I could be totally off base though. Really interested, if a crypto geek knows better than me.)

I did read that the key generation algorithms create p and q such that they are “very likely prime” but it is too much work to know for sure. This leads me to believe non-primes don’t cause any obvious FAILs. I could be wrong though.

Sorry, actually it’s ECDSA (Elliptic Curve Digital Signature Algorithm) not RSA.  I shouldn’t have said “prime numbers”.  ECDSA doesn’t take much time to generate a keypair.

24,645 total views, 22 views today

https://bitcointalk.org/index.php?topic=571.msg5778#msg5778