P5
Name: rlT66838 Date: 08/17/99
java.math.BigInteger.isProbablePrime theoretically may not reject some
large composite integers with the specified certainty.
Reliable fast primality testing is essential for some protocols
involved in information security and cryptography. The primality
testing method may need to test composite integers which have been
nonrandomly chosen in a deliberate "attack" on the method; see for
example Orman (1998: pages 25-26). Human lives or substantial amounts
of resources may be at stake.
I am unaware of any documentation which gives the range which the
current java.math.BigInteger.isProbablePrime method (isProbablePrime)
can reliably test. If the current isProbablePrime method can reliably
test any actual number which is an instance of the current BigInteger
class, then this is not a security weakness.
However, the best proof of correctness known to me of the algorithm
used in the current isProbablePrime method is the proof of the
Miller-Rabin algorithm (Menezes et al. 1997: chapter 4, page 139,
algorithm 4.24) which is based on the assumption that true random
numbers are used for "bases". For an introduction to the reasoning in
this "best available" proof of correctness, see the discussion of
algorithm P in Knuth (1997: section 4.5.4, page 395), or see Coutinho
(1999: chapter 6, section 4, page 103, second paragraph). [I list
citations in the below section on "Work Arounds."]
In fact true random numbers are NOT used in the current
isProbablePrime method. This is significant because the "best
available" proof of correctness assumes that the "true" random numbers
are available to use as bases which are evenly distributed on all
integers in the range 2 to n-2, inclusive, where n is the number being
tested for primality. The number n being tested may often be much
larger than 2^255, that is, much larger than 2 raised to the 255th
power. By examining the publicly available reference source code
for the classes java.math.BigInteger and java.util.Random, it can be
seen that a base, b, used in the current isProbablePrime method is
essentially calculated by joining together 32 bit integers returned by
consecutive calls to java.util.Random, which uses a pseudorandom
linear congruential method with an underlying period of 2^48.
Consecutive numbers returned by a linear congruential method are known
to have a highly NONRANDOM "lattice" distribution relative to one
another (Knuth 1997: section 3.3.4). Consequently the bases which
actually result in the current isProbablePrime method may have a
significantly uneven distribution on all integers in the range 2 to
n-2, and the assumption used in the "best available" proof may not be
"adequately" met.
At this point this is only a theoretical failing, since I don't know a
composite integer which the isProbablePrime method fails to reject
with at least the specified probability. If one or more exist, maybe
it would take several days, weeks, months, or years using a
microcomputer or a supercomputer to find one. However, it may be best
to spend some thought on the subject now, and reduce or eliminate the
risk that someone hostile and in a position to cause some serious
damage may someday discover that the failing is not merely
theoretical.
(Review ID: 93939)
======================================================================
java.math.BigInteger.isProbablePrime theoretically may not reject some
large composite integers with the specified certainty.
Reliable fast primality testing is essential for some protocols
involved in information security and cryptography. The primality
testing method may need to test composite integers which have been
nonrandomly chosen in a deliberate "attack" on the method; see for
example Orman (1998: pages 25-26). Human lives or substantial amounts
of resources may be at stake.
I am unaware of any documentation which gives the range which the
current java.math.BigInteger.isProbablePrime method (isProbablePrime)
can reliably test. If the current isProbablePrime method can reliably
test any actual number which is an instance of the current BigInteger
class, then this is not a security weakness.
However, the best proof of correctness known to me of the algorithm
used in the current isProbablePrime method is the proof of the
Miller-Rabin algorithm (Menezes et al. 1997: chapter 4, page 139,
algorithm 4.24) which is based on the assumption that true random
numbers are used for "bases". For an introduction to the reasoning in
this "best available" proof of correctness, see the discussion of
algorithm P in Knuth (1997: section 4.5.4, page 395), or see Coutinho
(1999: chapter 6, section 4, page 103, second paragraph). [I list
citations in the below section on "Work Arounds."]
In fact true random numbers are NOT used in the current
isProbablePrime method. This is significant because the "best
available" proof of correctness assumes that the "true" random numbers
are available to use as bases which are evenly distributed on all
integers in the range 2 to n-2, inclusive, where n is the number being
tested for primality. The number n being tested may often be much
larger than 2^255, that is, much larger than 2 raised to the 255th
power. By examining the publicly available reference source code
for the classes java.math.BigInteger and java.util.Random, it can be
seen that a base, b, used in the current isProbablePrime method is
essentially calculated by joining together 32 bit integers returned by
consecutive calls to java.util.Random, which uses a pseudorandom
linear congruential method with an underlying period of 2^48.
Consecutive numbers returned by a linear congruential method are known
to have a highly NONRANDOM "lattice" distribution relative to one
another (Knuth 1997: section 3.3.4). Consequently the bases which
actually result in the current isProbablePrime method may have a
significantly uneven distribution on all integers in the range 2 to
n-2, and the assumption used in the "best available" proof may not be
"adequately" met.
At this point this is only a theoretical failing, since I don't know a
composite integer which the isProbablePrime method fails to reject
with at least the specified probability. If one or more exist, maybe
it would take several days, weeks, months, or years using a
microcomputer or a supercomputer to find one. However, it may be best
to spend some thought on the subject now, and reduce or eliminate the
risk that someone hostile and in a position to cause some serious
damage may someday discover that the failing is not merely
theoretical.
(Review ID: 93939)
======================================================================