[Courses] [security] Crypto Scientists Crack Prime Problem

[Jacinta Richardson]

Great article Raven, but I've got a few things to add:

> 	So, back to our original point.  Being able to quickly determine
> whether a number is prime -- what effect does that have on all this?
> Well, one of the weakest points about RSA and other public key
> algorithms is that their large prime numbers are only probably prime.
> It's really hard to tell whether a number with eight zillion digits is
> actually prime or not -- you have to try dividing it by every prime
> number up to half of its value or so.  That's very time consuming.

Goodness no.  That'd mean encryption was next to impossible.

Perfect Primality tests (also does factorisation)
-------------------------------------------------

There are a few perfect tests for primality:
	Naive: check every number between 1 and N as factors 
			(N steps)
	Naive II: check each prime up to the square root of N
			=~ (sqrt(N) / 2) steps
	Sieve of Eratosthenes: 
		a) list all natural numbers from 2 until N
		b) 2 is prime, mark out all multiples of 2
		c) the first remaining unmarked number is prime
		   mark all multiples of this number less than N
		d) repeat c) (unless you cross out N)

None of these methods are fast enough to be practical for use in
generating or testing large primes for use in RSA.  If our prime is in the
order of 10^200 (a reasonable size) then the first method will take about
10^200 operations, the second will take about 10^100 and Erathosthenes'
Sieve would take up all of your memory and hundres of years.  ;)

Fermat's theroem
----------------

Fortunately our good friend Fermat had a great thorem which allows us to
test a number for primality without attempting to factorise it.  It
states:

	Let p be a prime and let a be an integer which is not a multiple
of p.  Then:
		a^(p-1) =~ 1 mod p.      =~ standing for equivalent.

That is, if a number 'p' is prime then for all integers 'a' (where 'a' and
'p' are relatively prime (the greatest common divisor of 'a' and 'b' being
1)) a^(p-1) must be 1 in modulo 'p'.  this is provably true for all primes
and gives us a great way of answering whether a number is not prime.


Pseudoprimes
------------
Fermat's theorem says that for all 'a', a^(p-1) =~ 1 mod 'p'.  A composite
number 'n' is said to be a pseudoprime to base 'a' if 
	a^(p-1) =~ 1 mod n

So we need to test for many values of a.  Obviously picking all values
from 1 to N will be more expensive than our naive approach above.
If we pick random values for 'a' and test a given number of these to
determine if 'n' is "prime enough", we still cannot guarantee that the
number is prime.  In fact we can be sure some composite numbers will get
through.

Carmichael numbers
------------------
There are some composite numbers which, for almost any 'a', 
	a^(n-1) =~ 1 mod n
These numbers are called Carmichael numbers.  Formally:

        A composite number n is a Carmichael number if 
		a^(n-1) =~ 1 mod n, 
	for all a with the greater common divisor of a and n
        being 1 (a relatively prime to n). 

The existence of pseudoprimes and Carmichael numbers make the use of
Fermat's theorem useless, in guaranteeing a number is prime, in this
simple form.  Almost any choice of 'a' will have the property that it's
greatest common divisor with 'n' will be 1.  If not, we've just found a
factor of 'n', so 'n' is not prime. 

We need to look at another useful property of primes to replace Fermat's
theorem.

Rabin Miller algorithm (one of many primality testing algorithms)
-----------------------------------------------------------------
The Rabin Miller algorithm uses the property of strong pseudoprimes in
checking for primality.  We can determine whether a number is a strong
pseudoprime to a given base using the following theorem:

	Let 'n' be a positive integer and 'a' be a number randomly chosen
	between 1 and 'n'.  Let n - 1 = 2^(st) where 't' is an odd
	integer.
	If either:
		a^m  =~ 1 mod n  or
		(a^t)^(2^i)  =~ -` mod n
	Then 'n' is either a prime number or a stron pseudo prime to base
	'a'.

We thus now have a method for testing primality.  The algorithm determines
with certainty whether a number is composite but can only establish with
high-probability if a number is prime.  The probability of error is no
worse than (1/4)^k where 'k' is the number of bases we test.  If 
k > 50 then the probability of error is less than 10^(-30) which is much
smaller than chances of hardware error on your computer.

This algorithm is also very fast.  It requires no more than 2k*log_2(n-1)
operations.  Since 'k' need not be higher than 50, this is fast even for
large 'n'.

How to generate primes
----------------------

Due to the number of very clever and effective ways of factorising a
composite number 'n' we have to ensure that primes used in RSA are 'strong
primes'.  A strong prime is one that, if it occurs as a factor of a larger
number 'n' makes the factorisation of 'n' difficult.  The qualities of
this prime depend on the current state of the art of factorisation
techniques, and on the size of the relevant numbers.  Currently, a strong
prime is a prime 'p' such that: 
        p - 1 has a `large' prime factor r.
        p + 1 has a `large' prime factor.
        r - 1 has a `large' prime factor.

The first condition is design to resist the Pollard p - 1 factorisation
method.  The second condition is designed to resist an analogous attack
using p + 1.  The third condition is of a similar nature.

The easiest method of generating prime numbers is to pick a random seed
and check all numbers greater than that until we have located a prime. 
Since the Prime number Theorem states that the number of primes less than
some value 'n' is approximately n/log_10(n+1) and there are infinitely
many primes, we are guaranteed to discover a prime number fairly quickly. 

These primes will not necessarily be good for use with RSA as we have no
evidence that they are necessarily strong primes.  However these numbers
can be used in our determination of stronger primes.  Also, if our prime
numbers are to be used in RSA it is important that the random seed be as
random as possible.  Otherwise anyone who uses the same random function
can generate our primes and the purpose of strong primes is destroyed. 

Further Considerations
----------------------

As well as ensuring that our primes are strong primes we have to ensure
that we select 'p' and 'q' such that they are about the same bit length
and sufficiently large.  This is to avoid the elliptic curve factoring. 

Another restriction is that p - q should not be too small.  If p - q is
small then p is approximately sqrt(pq).  Thus 'n' can be factorised by
trial division by odd integers near sqrt(n).  If we're choosing 'p and 'q'
at random, then the probability that p-q will be appropriately large will
be large. 

> Since those of us that use PGP, etc., don't want to wait too long for
> our keys to be generated, the RSA algorithm picks values for P and Q
> that are very likely to be prime, but that's not known for certain. 

It can be certain enough.  If we set 'k' big enough we can be more
certain that the machine has accidently bit-flipped a bit in the integer
representation than the number isn't prime.  I guess what the above link
(which I really should take a look at soon) provides is another (perhaps
faster) way to test primailty.  That's not so scarey.

> 	If those numbers aren't actually prime, then there may be
> different solutions for the equations other than the ones that are
> supposed to work.  So, someone might be able to decrypt a message
> without having *the* matching key -- they'd just need *a* matching key,
> if there were more than one.  (That's what could happen if P and Q
> aren't prime.)  If the new algorithm can determine whether P and Q are
> really prime and they're not for a given key pair, that could lead to a
> weakness in RSA.  But if that's the case, RSA and other algorithm
> authors could modify their software to use the new algorithm to ensure
> that P and Q really are prime, and that would defeat that sort of
> attack.

This has always been a problem.  That doesn't change because we've got a
new primality test.  It would change lots if we could efficiently factor
the damn things.  ;)

> 	There's a lot of sound and fury at the moment about this
> article, and many people are freaking out about it, but I don't think
> it's anything to worry about.  Mathematicians haven't fully satisfied
> themselves yet that it's a good tester for primes -- I don't think we'll
> be seeing exploit code in the near future.

People are freaking because they've forgotten how RSA works.  The author
of the article has no clue either:

" RSA, a popular encryption algorithm used in securing Internet commerce,
is built on the assumption that when prime numbers--those evenly divisible
only by themselves and the number one--are large enough, they're nearly
impossible to generate and determine. "

No, it is built on the assumption that factoring large numbers is next to
impossible.

We should be overjoyed about having a new method to test for primality.  
It might give us some interesting insights into new factorisation methods.  

	Jacinta

PS: Lots of the text of this email was pulled out of a computer science
essay I had to write last year.  I can provide code or algorithms for all
theories and am happy to provide such for generating RSA strong primes if
anyone wants them.

--
   ("`-''-/").___..--''"`-._          |  Jacinta Richardson	    |
    `6_ 6  )   `-.  (     ).`-.__.`)  |  Perl Training Australia    |
    (_Y_.)'  ._   )  `._ `. ``-..-'   |      +613 9354 6001 	    |  
  _..`--'_..-_/  /--'_.' ,'           | contact at perltraining.com.au |
(il),-''  (li),'  ((!.-'              |   www.perltraining.com.au   |