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