Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:16:02 ADT
Hal Finney (hal@rain.org)
Tue, 17 Mar 1998 11:24:56 -0800
As most people know, primes can't be factored. So I assume that what
you really want is to generate a product of two large primes where it
superficially looks like it will be hard to factor, but in fact it turns
out to be easy.
The first thing to realize is that it is very hard to do this without
getting caught. Although you can choose weak primes so that an attacker
could factor the product with some algorithm, you can't credibly claim
that you didn't know your primes were weak. The chances of accidentally
choosing a weak prime are so small that almost the only way it could
happen in practice would be if you had done it intentionally, as you in
fact want to do.
With this in mind, one approach is to have one of the two primes p
be such that p-1 is composed only of small factors. "Small" depends
on the resources that your attacker is going to apply to the problem,
but probably you would want to choose somewhere around 30 bits as the
upper limit.
There is a well known factoring algorithm which cracks numbers where
one of the factors is of this form. It would be somewhat unusual for
an attacker to try this algorithm on product of large primes because
the chances of it working would be practically zero, but he might try
it just in case he got really lucky. That's why you can't make the
p-1 factor size too high, because as implausible as it might be for an
attacker to try the p-1 algorithm, it is even less likely that he would
spend a lot of time on it.
The chances that a randomly chosen 256 bit prime will have p-1 with the
highest factor around 30 bits is about one in 2^24. The chances for a
512 bit prime are about one in 2^64. This is why I say that you would
probably get caught, because the chances that this happened to you by
accident are so low. Maybe with the smaller primes you could claim to
have been unlucky, but it is pretty far fetched.
Hal
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:16:02 ADT