From: Nathan Zook <nzook@bga.com>
Date: Wed, 1 Feb 95 16:58:23 PST
To: cypherpunks@toad.com
Subject: Lucky primes & omlets on my face...
Message-ID: <Pine.3.89.9502011814.A8923-0100000@jake.bga.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----
 
Considering the general temperature of this list, I'm amazed that I didn't
get torched over my algorithm.  sigh.  The c-punks are all too busy
debating operating systems to worry about effiency in their remailers.
 
Unless, of course, Hal's "I don't understand" was from the Moore school?
 
Let's try this again.
 
Let 2*x be the target number of bits in the modulous.
 
Let n be a large random number with x+2 digits.
Let n1 be the next multiple of 0x10001.
Let t2 be n1 mod 8, t3 be n1 mod 9, t5 be n1 mod 25, t7 be n1 mod 49.
 
Loop:
For i = 2 to 7
 If n1 = 1 mod i and (n1-1)/i + 1 is not a multiple of {2,3,5,7}
    If (n1-1)/i + 1  is prime.
      {
        Let k = 0's in n1/0x10001.
        If k is in range, save and exit.
      }
    EndIf
 EndIf
Next
n1 += 0x10001;
EndLoop
 
Recall:  x^p = x mod p therefore, x^(p-1) = 1 mod p. So what we need is:
(x^e)^d = x^ed = x^(p-1)*i+1 = x mod p.  
 
ie: ed = (p-1)*i+1
or: (ed - 1) / i + 1 = p
 
Now 0x10001 inverts easily, it is just n1/0x10001.  By keeping track of
various quantities, we can eliminate all multiprecision divisions except
for the original one needed to get n1 and the t's, and doing increments
instead.
 
>Yes, I see that you are right about this.  It would be easy to generate
>e,d pairs and get a d which is significantly short on 1's by 10% or more.
>I did not quite follow your algorithm to do this (was n the modulus or
>was it phi, the sum of the modulus' divisors?).  The one caveat is that
>if "high-zero" decryption exponents are widely used, it could conceivably
>reduce the search space somehow, although I don't see offhand how to
>exploit this.
>
>Hal
 
>>     (you may wish to ensure that k is _above_ a certain threshhold...)
 
I don't either, but if >80% of the digits were 0, I'ld probably start to
get nervous.  But I don't need a fast-key for my home system, I'm barely
handing 10 signatures a day.  I only advocate using high 0's when you are
in a high usage environment.
 
Nathan
 
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
 
iQEVAwUBLzA2NnmgMs8UcStNAQEyjQf/aOPBXcN6/M9cmh3aQHXeIr5uY3DEwvRw
WHBtWv0dVE1jfSS/4i71apWi2+Gm7iRyLGc/G4Y03RkcqMhePGSHgN6NHEHC3QaR
qoKMsa/h6z5nSMd/t8umTiSUJxFX2/1z8k29j7bM5gduUTqHPdFwcVnQnE8Rhy72
hwF+r3g9lFIhavsLFnT7KPeQ1ozVFJ+ItoTDWOOjjA8/MSGFi5JFkViw+saP2F/j
2JEbMhmMcjtTchu+s/yNVGJeL0C0DMjh2Ysh/wS/GwbcoXK1RFb602lXtCp2AUz5
Mzn9Xsdv4bUyyoumN5wT6YDdwu6QwvvU5Fh9sTZUwFHsY9RrMy53jQ==
=lK0s
-----END PGP SIGNATURE-----