Extract numbers from a key

[Hubert Kario]

On Sunday 14 August 2011 14:05:02 Peter Lebbing wrote:
> On 14/08/11 13:41, Hubert Kario wrote:
> > From what I learned, RSA cracking is basically an exaustive search.
> > If your "prime" is composite, it is at most half as long as a real prime
> > would be.
> > 
> > So, instead of a ~1024 bit prime you have a ~512 bit prime, which are
> > tryvial to crack.
> 
> Yes [1], but it depends on your search space (and the route through it). You
> are trying to find two 1024 bits long primes, not shorter ones.

looking through full 512bit space will take 8192 less time than checking all 
numbers between 2^525 and 2^526.

as we're talking about 512 and 1024, it will be "few" orders of magnitude 
longer.

Checking "just in case" for such situation in the grand scheme of things will 
make your cracking algorihm only marginally slower.

> 
> The most naïve method would be:
> 
> pick a 1024-bit random number a
> pick a 1024-bit random number b

Ah, the EMACS Ctrl+Alt+Meta+Top+P 1024 command! ;)

>From what I tried myself, checking all numbers as they go produced faster 
algorithms than finding primes and then checking them.

Prime numbers are quite common, testing for primality is expensive, prime 
number distribution is non deterministic.

> [1] Actually, a 1024-bit RSA key is considered secure, and that consists of
> two 512-bit primes. Now, a 512-bit RSA key, yes, those are crackable, but
> not 512-bit primes. But it's the thought that counts, not the actual
> numbers, so this is just a footnote.

I keep forgeting that people still use 1024bit RSA keys ;)
but, yes, I meant 1024 bit and 512 bit keys, which consist of two ~512 bit and 
~256 bit primes

Regards,
-- 
Hubert Kario
QBS - Quality Business Software
02-656 Warszawa, ul. Ksawerów 30/85
tel. +48 (22) 646-61-51, 646-74-24
www.qbs.com.pl