Cuda and a cluster

[Dubslow]

Originally Posted by efiGeek

I can't even get 1 private key, no less than getting many. All I have to date is public keys.

I of course misspoke horribly. I meant public key. If you have several public keys from the same source, and the source is known to not be very judicious with its key generation, then it's possible that given a pubkey n=pq, a different pubkey n' was composed with one prime in common, say n' = pq'. Then by taking the greatest common divisor (very very efficient) of the two pubkeys n and n', we see that they share p as a divisor, and thus both keys are broken. This is of course an insanely stupid error to make, but there is substantial evidence of this happening in the wild (mostly due to poor random number generation). It is of course not easy to verify that both primes in a generated key have never ever been used in the history of cryptography by anyone else, though the probabilities for an *actually random* generation process are extremely low. On the other hand, humans are extremely fallible, and randomness is hard.

VBCurtis is right on the money regarding P-1. For n=pq, if any of p-1, p+1, q-1, or q+1 are very smooth numbers (where smooth depends on how much effort you're willing to put into the computation), then it's possible to find p or q respectively as a factor of n. (The P-1 algorithm deterministically finds p if p-1 is smooth, the P+1 algorithm probablisitically finds p if p+1 is smooth.) On the other hand, if you have the private key, it's easy to check that p and q are not vulnerable in such a way, but again, humans have been known to screw up.

[jasonp]

The attacks on RSA are pretty much always against the implementation or how it is used (i.e. OAEP or PKCS padding for messages to be signed).

None of the public software packages that implement GNFS can scale to a kilobit-size general number; even the linear algebra for RSA768 was carried out by tools that are not public.

That being said, NFS@Home proved that with national-level computing resources the linear algebra of MPI Msieve can scale very nicely, i.e. hundreds of fast nodes with infiniband interconnect using expensive switches.

[efiGeek]

Lets look at this example, and at anytime someone can provide a N that is generated using an e=3 and I will duplicate using their N (N==publicKey)

N= 101806658414183540288589161730408727740120618190893755130135230358383847117603160559626014451009399132403781263037663818440290191996583564759868946951567739745439868625355766356270064519905180064861089230479316487135935491374372341644480297851088741417099178959180285316531509052468674647010290263190995108441
D= 67871105609455693525726107820272485160080412127262503420090153572255898078402107039750676300672932754935854175358442545626860127997722376506579297967711812955551350642276495509722301421327278983891827379609087831181502226121364423219132052857059432020064346448685883130890070539102000640979819121874736553923

N * 0.6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666665
== 67871105609455693525726107820272485160080412127262503420090153572255898078402107039750676300672932754935854175358442545626860127997722376506579297967711811565316678336651268577769655886656718158883391489235458571590171097952004312632771453418606346232860033418201611353660968125750956932417362061348443842358.837335485934947820934413723870413906923820373579529700248553396127931758723225476222981840317925492120419320224820242045338971261051771824094731987384095320
which results in revealing the upper 512 bits of the private key or this
6787110560945569352572610782027248516008041212726250342009015357225589807840210703975067630067293275493585417535844254562686012799772237650657929796771181

If the multiplier is extended a decimal place at a time, by hand and a lot of time, you can revel more if not all of the private key.

I understand that this is far from being a crack/break on RSA, but it is a start. RSA key pairs using 3, 7 or 11 suffer from this.

-Tim

[Dubslow]

Whoa buddy, learn to use [code] tags please

[efiGeek]

Originally Posted by Dubslow

Whoa buddy, learn to use [code] tags please

I guess you can now see that I VERY RARELY post on message boards therefor I do not know the unwritten rules or even what a [code] tag is. I will try to edit it now.

-Tim

[jasonp]

See here for a recent paper on reconstructing d given some fraction of the bits of the key are known. The paper also references the more conventional attacks that reconstruct the key using lattice reduction if some fraction of it is known.

[efiGeek]

Originally Posted by jasonp

See here for a recent paper on reconstructing d given some fraction of the bits of the key are known. The paper also references the more conventional attacks that reconstruct the key using lattice reduction if some fraction of it is known.

Thanks JasonP! I had read parts of that paper a long time ago and had forgot about it. I will try to code it today and I will let you know the outcome. I knew of Coppersmith's attack, but I have no clue as to the lower bits but it looks like this one will work by just knowing any of the bits.

-Tim