Random Prime Generator/Modular Arithmetic

[Tuvas]

I have made and recently posted a libary I made to do Modular
Arithmetic and Prime numbers on my website at
http://www.geocities.com/brp13/Python/index.html . I am currently in a
crypotology class, and am working on building a RSA public key
cryptology system for a class project. I am building the librarys just
to get the experience to do so. However, I would ask if any of you know
of any gaping security holes that can easily be seen from my selection
of random prime numbers, ei, are they somehow predictable? Just wanting
to make sure. For simpler than going to the website, I used the ranint
function to pick a random prime number, then ran it through the miller
rabin primality test. It's a probabalistic test, which means it isn't
full proof, but there's still less than 1 in a million of giving a
false reading. Thanks! And if you should so want for some reason, feel
free to use it!

 

[Tuvas]

I have discoved that the mod function isn't quite right in dealing with
powers, but, I'll have it fixed shortly.

 

[Alex Martelli]

to make sure. For simpler than going to the website, I used the ranint

I assume you mean random.randint here.

function to pick a random prime number, then ran it through the miller
rabin primality test. It's a probabalistic test, which means it isn't
full proof, but there's still less than 1 in a million of giving a

Miller-Rabin is not the problem -- rather, random.randint might be... it
makes no claims to be cryptographically strong, in either the current
Mersenne implementation or the previous Wichman-Hill one. Could you
maybe use /dev/random or the like? Cfr
<http://world.std.com/~cme/P1363/ranno.html> for an introduction to the
subject. (For speed, you may want to look into gmpy.sf.net, but that's
quite a separate issue from the strength of your random numbers).


Alex

 

[Tuvas]

Well, the RSA element's never going to encrypt more than a small, 1
block system except under rare occasions, the primary encryption will
be AES128. Thanks for the help though!

 

[Tuvas]

Okay, the bug in my code has been fixed, it should work alot better
now... I thought I had tested the power function, but I appearently
wasn't even close... But now it works just fine.

I guess you are right, I will have to work on a better system to be
cryptologically secure. But, at least I have a start. Thanks for the
help!

 

[Paul Rubin]

I have made and recently posted a libary I made to do Modular
Arithmetic and Prime numbers on my website at
http://www.geocities.com/brp13/Python/index.html . I am currently in a
crypotology class, and am working on building a RSA public key
cryptology system for a class project. I am building the librarys just
to get the experience to do so.

I'm looking at
http://www.geocities.com/brp13/Python/prime3.html

You do something for x in range(10) but you don't use x in the loop.

I'll guess you actually intended to pick some random number n and find
the closest prime p >= n. That's not a good strategy: imagine you pick
a random number n in the range 1..50. Let's say n is 14. 14 isn't
prime, so you check 15, 16, and 17. 17 is prime so you return p = 17.
You also return 17 if n is 15, 16, or 17. So the chance of your
returning p = 17 is 4/50.

What is your chance of returning p = 19? It means n has to be 18 or
19, so the chance is only 2/50. That's not good--you want all primes
to be equally likely.

Anyway, the simplest approach is:

1) get random numbers by reading characters from os.urandom() and
converting them to integers. Don't use randint which makes no attempt
at cryptographic security.

2) For each random integer (you can set the low bit to make sure it is
odd), test against some small prime divisors p (say the primes up to
1000) as a fast way to throw away some composites. If n%p == 0 for
any p, throw away n and go back to step 1.

3) If you get an n with no small divisors, do the (slow) Miller-Rabin
test. If it passes, you're done; if it fails, go back to step 1.

 

[Tuvas]

Okay, I don't know if your farmiliar with the miller-rabin primality
test, but it's what's called a probabalistic test. Meaning that trying
it out once can give fake results. For instance, if you use the number
31 to test if 561 is prime, you will see the results say that it isn't.
Mathematically, the most possible wrong answers is 1/4th of the
numbers. Thus, one should try at least 10 times (A very standard value)
in order to ensure that the number is not a psuedoprime, but indeed a
real prime number. That was the intent of the loop of 10 without using
the number.

If this test fails, it will chose another random number to test.

I could easily test with several small numbers, at least primes up to
20 would greatly reduce the number of miller-rabin tests to perform,
and would speed up the process considerably. Might as well toss it in.

Thanks for the tip on the urandom. I knew there had to be a better
random number generator somewhere. I saw lots of stuff for os specific,
but I'm trying to develop this as os independent.

 

[Astan Chee]

thanks for the webpage info,
however theres a small error I found when trying to generate a prime
number with more than 300 decimal digits. It comes up with

File "prime.py", line 84, in mod_square_pow
return x*mod_square_pow(((a**2)%n),t,n,p*2)
File "prime.py", line 84, in mod_square_pow
return x*mod_square_pow(((a**2)%n),t,n,p*2)
File "prime.py", line 73, in mod_square_pow
if(p*2>t):
RuntimeError: maximum recursion depth exceeded in cmp

Have you considered this? otherwise the algorithm is rather quick for
generating large random prime numbers.
Thanks for your help

 

[Tuvas]

Hmmmm. Well, I don't know what else I could do, except for to write a
function that doesn't require recursion. Still, 300 digits isn't too
bad... I have also realized that if you try is_prime(3) it will return
false. I'll have to work on it... Thanks for the help!

 

[Astan Chee]

Also you last code which looked like:

def cran_rand(min,max):
if(min>max):
x=max
max=min
min=x
range=round(log(max-min)/log(256))
if range==0:
range=1
num=max+1
while(num>max):
num=min+s2num(urandom(range))
return num


what does s2num do? im assuming it changes string chars to ascii
decimal? Is that correct?
and i thought is_prime would work better if you listed all small primes
(<20000) and check if they are divisible by those.
Aside from that Im really interested in your cran_rand function as I
havent fully tested it out yet.
Cheers

 

[Tuvas]

Yep, you guessed correctly about the s2num function, I knew I should
have put a bit more.. It just converts an ascii string to a number,
however many numbers that are nessicary. I could indeed check for all
primes below a certain number, however, it still seems to run quite
fast, at least to a 400 digit number. It's not something I'm going to
use a ton, so optimizing it might not be worth it much more than it is.
Perhaps I'll try all primes at least up to 100, that wouldn't be too
bad... Maybe I'll have to modify my old prime string to output the
python command to check all of them, it's a bit of a pain the whole if
0 in (n%2, n%3) stuff, and I can't think of a better way to do it
without writing a new function to do so.
I'm going to post the new code in just a minute, it's running quite
nicely. I'm also posting my RSA function, which I believe should be
secure enough. I'm uploading the code to them now, the HTML page'll be
a few minutes...

 

[Astan Chee]

Also I think the snippet code [p for p in range(2,N) if 0 not in
[pow(w,p-1,p)==1 for w in [2, 3, 5, 7, 11] if p>w]] is probably nicer to
generate a list of primes for up to N (instead of hard coded)
Aside from that looks nice.
Thanks

 

[Tuvas]

Actually, it wasn't very nice, it returned composites instead of
primes... There was alot of little bugs, I'm glad I checked it again.
The new code once again is uploaded, the previews are on their way... I
did set up a system to check for primality up to 1000, I think any more
than that and it will become conter-productive.

 

[Tuvas]

Although, I have to brag quickly, adding in this simple prime check
speed up the algorithm to the point that it's actually faster to find a
prime number with my program than to verify a number prime with
GP/PARI, so, I feel good.

 

[Bryan Olson]

Okay, I don't know if your farmiliar with the miller-rabin primality
test,

Paul is familiar with it. When he referred to your Miller-Rabin
test, he meant all the rounds.

> but it's what's called a probabalistic test. Meaning that trying
it out once can give fake results.

In the sense that some composites will pass as prime for some
bases.

> For instance, if you use the number
31 to test if 561 is prime, you will see the results say that it isn't.

That's not an instance of a fake result; Miller-Rabin has that
one right. When Miller-Rabin says a number is composite, it is
always correct.


Your current Miller-Rabin test, in

http://www.geocities.com/brp13/Python/modular.html

in method Mod.is_strong_pseudo_prime(), looks buggy. Obviously
you want "cut()" not "cut", and "if 1:" cannot fail. In my opinion,
the Mod class is not such a good idea; just use functions.


Note that Python has modular exponentiation built in.

pow(base, power, modulus)

with positive integer arguments will return base**power % modulus.


Finally, though most introductory crypto courses don't cover it,
RSA requires "padding" of the plaintext data. Google RSA + Padding
for more. Or ask on sci.crypt.

 

[Tuvas]

Paul is familiar with it. When he referred to your Miller-Rabin
test, he meant all the rounds.


In the sense that some composites will pass as prime for some
bases.



That's not an instance of a fake result; Miller-Rabin has that
one right. When Miller-Rabin says a number is composite, it is
always correct.

I mis-stated. If you try 31 in the Miller-Rabin test.
True

However, 561 is not prime, it is divisible by 3, 11, and 17.

Actually, I did another test, and realized that it was indeed a bug in
the code. Yikes. Oh well, thanks for the help in identifying it!

An example that would be alot easier is this:

True



Your current Miller-Rabin test, in

http://www.geocities.com/brp13/Python/modular.html

in method Mod.is_strong_pseudo_prime(), looks buggy. Obviously
you want "cut()" not "cut", and "if 1:" cannot fail. In my opinion,
the Mod class is not such a good idea; just use functions.

The reason for the modulos class, well, was more of a practice than
anything else.

I could indeed just use functions, but I needed the Mod class for a few
other things, and figured it was just easier to program it once and use
it for anything rather than anything else.

Note that Python has modular exponentiation built in.

pow(base, power, modulus)

Nice to see that Python supports modular exponentiation. I'll have to
remember that one. Probably the next time I do an update to the code,
I'll just use it instead, it's probably faster than mine.

with positive integer arguments will return base**power % modulus.


Finally, though most introductory crypto courses don't cover it,
RSA requires "padding" of the plaintext data. Google RSA + Padding
for more. Or ask on sci.crypt.

Overall, I guess another update is coming soon. Thanks for the help in
debuging again!

 

[Bryan Olson]

Tuvas wrote:
[...]

Actually, I did another test, and realized that it was indeed a bug in
the code. Yikes. Oh well, thanks for the help in identifying it!

An example that would be alot easier is this:


True

Hmmm...my M-R tester disagrees...

Ah, there's another bug in is_strong_pseudo_prime().
While your exponent 'x' is even, you do the test with x,
not necessarily x/2.

Incidentally, the lowest base for which 561 is strongly
pseudo-prime is 50.

 

[Tuvas]

Ahh, I see, I missed doing the last step in my M-R test. Hmmm. Well,
got that one fixed now, time for a new release I guess. Sigh. I do seem
to be going through them rather quickly...

 

[Tuvas]

Okay, now I get the correct number of 561 pseudoprimes, 5, so I can
assume that it is indeed working right. Whew. Thanks for the help on
that one. Now, I only wish I could change the answer to my last
homework assignment... Oh well.

 

[Bryan Olson]

Okay, now I get the correct number of 561 pseudoprimes, 5, so I can
assume that it is indeed working right.

Your code now looks right, so I'm guessing "5" was a typo,
perhaps because "5" is just below "8" on the numeric keypad.


You can simplify your loop like:

def is_strong_pseudo_prime(a, n):
# check for n == 2 and/or other input validation omitted
if pow(a, n - 1, n) != 1:
return False
x = n - 1
while x % 2 == 0:
x = x / 2
y = pow(a, x, n)
if y == n - 1:
return True
elif y != 1:
return False
return True


For time efficiency, I prefer a slightly longer version that does
all the square-root-checking in the course of the one modular
exponentiation.

def is_mr_pseudoprime(n, w):
""" Pass positive integers n and w, with w < n.
Return true iff n is prime or a strong base-w pseudo-prime.
"""
assert n == long(n) and w == long(w) and 1 < w < n
power = n - 1
pow2 = 0
while power % 2 == 0:
power /= 2
pow2 += 1
r = pow(w, power, n)
for _ in xrange(pow2):
prev = r
r = r * r % n
if r == 1:
return prev in (1, n - 1)
return r == 1