Extract numbers from a key

Peter Lebbing peter at digitalbrains.com
Mon Aug 15 11:06:53 CEST 2011


On 14/08/11 16:39, Hubert Kario wrote:
> looking through full 512bit space will take 8192 less time than checking all 
> numbers between 2^525 and 2^526.

Or, equivalently, looking through full 512 bit space takes the same amount of
time as checking all numbers between 2^513 and 2^514. It's exactly the same
thing, with a 1 tacked on at the end. I don't understand what significance 2^525
has?

> 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.

I'm not sure I follow.

You propose to check for the public modulus not being a semiprime when trying to
solve the RSA problem, because this will only take a fraction of the time needed
for subsequently solving it when p and q are prime?

I wonder if that will pay off. I just don't know. It's one of the possible
answers to my original question. If it pays off, it means that, yes, the
adversary has a better chance to solve the RSA problem if p or q is composite,
because the adversary could first check for this possibility "just in case", as
you put it.

Peter.

-- 
I use the GNU Privacy Guard (GnuPG) in combination with Enigmail.
You can send me encrypted mail if you want some privacy.
My key is available at http://wwwhome.cs.utwente.nl/~lebbing/pubkey.txt



More information about the Gnupg-users mailing list