Re: Special factorization method sought
From: Robert Maas, see http://tinyurl.com/uh3t (rem642b_at_Yahoo.Com)
Date: 07/01/05
- Next message: Taliesin: "Re: own cypher-algorithm - TaShiKai"
- Previous message: D. J. Bernstein: "Re: Quantum Computer vs. crypto"
- Maybe in reply to: daniel bleichenbacher: "Re: Special factorization method sought"
- Next in thread: Risto Lankinen: "Re: Special factorization method sought"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Thu, 30 Jun 2005 23:04:55 -0700
> From: "Pubkeybreaker" <Robert_silverman@raytheon.com>
> Unless of course, the numbers are *so* extremely close that
> difference of squares can be used. However, for even moderately
> large N, if N = A*B and the size of A and B differs by only 1 bit,
> then this method is useless.
Ah, that's good (for me) to know. So the algorithm I developed in late
1977 (after reading Martin Gardner's info about the RSA code) is quite
sufficient. The user specifies the number of decimal digits desired,
and a string which is the high-order decimal digits, such as the user's
telephone number or social security number etc. that will be easy to
remember. This template will be used as a restriction on p*q so that
when it's published it'll be obvious whose code is being published, and
so two different users would ever come up the same exact product by
accident. After that number-of-digits and high-order prefix is
specified, the program synthesizes a random prime that has about half
the number of digits. Then it performs interval-arithmetic division, in
contracting mode instead of the usual expanding mode, to find what
range the other prime number must be such that the product is
guaranteed to have the correct number of digits and correct high-order
prefix. Then it synthesizes that second prime in that range. The range
is so wide that it's extremely unlikely that the two primes would be so
close as to make factorization by square root method practical.
And if you are really worried about the two primes accidently being too
close, for the range of the first prime, instead of taking the full
range near the square root of the desired product, you can take only
the lower half of it, minus the part that is too near the square root.
The other prime then will be guaranteed in the upper half also far
enough from the square root. For example, if your phone number is
1-414-213-5624 (if you can't guess where I came up with that particular
fake phone number, you shouldn't be reading this newsgroup), and you
want a 100-digit product, then the template for the product is
14142135624xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
so you want two primes, each appx. 50-digits, with the first bounded
sufficiently below the square root of the lower bound of the above
template, i.e. significantly less than the square root of
14142135624000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
which is
37606030931221656910158100994704773561630651512262
so to be totally safe you set the high bound for
the first prime at
30000000000000000000000000000000000000000000000000
and the low bound at
10000000000000000000000000000000000000000000000000
Depending on which first prime in that range is actually picked, the
second prime will then be somewhere in the range
47140452080000000000000000000000000000000000000000
to
141421356250000000000000000000000000000000000000000
and as you can see worst case (for the two being close together) is a
factor wider than 30:47 i.e. wider than 1 : 1.5.
Note that you can generate hundreds of p*q, each with the same public
phone-number prefix, so if somebody factors one of your p*q it only
cracks that one of your codes, so all your other messages encrypted
with other p*q are still secret. And the whole time the public can
readily identify which p*q beong to you regardless of what the rest of
the digits are, because of that prefix. You might be able to get a
copyright or other protection on your particular prefix, so nobody else
would be allowed to usurp your prefix for their p*q product thereby
masquerading as you with another code. Or if there's no legal
protection, you can post public messages signed with all your previous
p*q each time you announce a new p*q. Somebody who factors one or two
of your old p*q would be able to forge those few signatures but
wouldn't be able to factor *all* your previous p*q and thereby truly
forge an announcement of your next key, so if you make new p*q faster
than anyone catches up with factoring all the old ones you're safe.
One extra idea: Your phone number might change, so it might be best to
include your birth date in the public p*q prefix, to make sure nobody
who takes over your old phone number can claim the right to re-use your
public p*q prefix (unless they have the same exact birthdate, which is
unlikely, but if that happens, you can use the chain of public
announcements of your new p*q to distinguish yourself from the other
person using the same prefix but using different p*q).
- Next message: Taliesin: "Re: own cypher-algorithm - TaShiKai"
- Previous message: D. J. Bernstein: "Re: Quantum Computer vs. crypto"
- Maybe in reply to: daniel bleichenbacher: "Re: Special factorization method sought"
- Next in thread: Risto Lankinen: "Re: Special factorization method sought"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
