key length/size RSA discussion/recommendations in the wiki

[Ingo Klöcker]

On Wednesday 29 October 2014 22:18:13 Peter Lebbing wrote:
> On 2014-10-29 21:49, vedaal at nym.hush.com wrote:
> > Surely Peter knows this too ;-)
> > 
> > More likely 128 was a typo for the more common older RSA key of 1028
> > ...
> 
> No, I'm using a strict definition of brute force.
> 
> For p = 2^63 to 2^64-1
>    For q = 2^63 to 2^64-1
>      If p * q == n:
>        Break
>    Next
> Next

If anything then I'd do

For p = 2^63 to 2^64-1
   If n modulo p == 0:
      Break
Next
q = n / p

which is O(n^(1/2)), but IMO still brute force (even in your strict 
definition), while yours is O((n^(1/2)^2) = O(n). "brute force" doesn't 
mean that you have to use the most naïve algorithm.


> I don't feel the method outlined by Rob is still brute force. That
> brute actually is using his brain. Possibly his brain resembles a
> sieve, but still :). Am I too strict?

Actually, that brute doesn't seem to be using his brain. If he'd use his 
brain then he'd use he fists to brute force the secret out of you. ;-p


Regards,
Ingo
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: </pipermail/attachments/20141030/7359334a/attachment.sig>