Random Prime Generator/Modular Arithmetic

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!

re: Random Prime Generator/Modular Arithmetic

Tuvas <tuvas21@gmail.com> wrote:
...[color=blue]
> to make sure. For simpler than going to the website, I used the ranint[/color]

I assume you mean random.randint here.
[color=blue]
> 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[/color]

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

re: Random Prime Generator/Modular Arithmetic

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

re: Random Prime Generator/Modular Arithmetic

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!

re: Random Prime Generator/Modular Arithmetic

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!

re: Random Prime Generator/Modular Arithmetic

"Tuvas" <tuvas21@gmail.com> writes:[color=blue]
> 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.[/color]

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.

re: Random Prime Generator/Modular Arithmetic

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.

re: Random Prime Generator/Modular Arithmetic

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 wrote:
[color=blue]
>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.
>
>
>[/color]

re: Random Prime Generator/Modular Arithmetic

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!

re: Random Prime Generator/Modular Arithmetic

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 wrote:
[color=blue]
>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!
>
>
>[/color]

re: Random Prime Generator/Modular Arithmetic

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...

re: Random Prime Generator/Modular Arithmetic

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 wrote:
[color=blue]
>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...
>
>
>[/color]

re: Random Prime Generator/Modular Arithmetic

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.

re: Random Prime Generator/Modular Arithmetic

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.

re: Random Prime Generator/Modular Arithmetic

Tuvas wrote:[color=blue]
> Okay, I don't know if your farmiliar with the miller-rabin primality
> test,[/color]

Paul is familiar with it. When he referred to your Miller-Rabin
test, he meant all the rounds.
[color=blue]
> but it's what's called a probabalistic test. Meaning that trying
> it out once can give fake results.[/color]

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

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

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.


--
--Bryan

re: Random Prime Generator/Modular Arithmetic

Bryan Olson wrote:[color=blue]
> Tuvas wrote:[color=green]
> > Okay, I don't know if your farmiliar with the miller-rabin primality
> > test,[/color]
>
> Paul is familiar with it. When he referred to your Miller-Rabin
> test, he meant all the rounds.
>[color=green]
> > but it's what's called a probabalistic test. Meaning that trying
> > it out once can give fake results.[/color]
>
> In the sense that some composites will pass as prime for some
> bases.
>
>[color=green]
> > For instance, if you use the number
> > 31 to test if 561 is prime, you will see the results say that it isn't.[/color]
>
> 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.[/color]

I mis-stated. If you try 31 in the Miller-Rabin test.
[color=blue][color=green][color=darkred]
>>>Mod(31,561).is_strong_pseudo_prime()[/color][/color][/color]
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:[color=blue][color=green][color=darkred]
>>>Mod(16,561).is_strong_pseudo_prime()[/color][/color][/color]
True
[color=blue]
>
>
> 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.
>[/color]

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.
[color=blue]
>
> Note that Python has modular exponentiation built in.
>
> pow(base, power, modulus)[/color]


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.
[color=blue]
>
> 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.
>
>
> --
> --Bryan[/color]

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

re: Random Prime Generator/Modular Arithmetic

Tuvas wrote:
[...][color=blue]
> 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:
>[color=green][color=darkred]
>>>>Mod(16,561).is_strong_pseudo_prime()[/color][/color]
>
> True[/color]

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.


--
--Bryan

re: Random Prime Generator/Modular Arithmetic

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...

re: Random Prime Generator/Modular Arithmetic

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.

re: Random Prime Generator/Modular Arithmetic

Tuvas wrote:[color=blue]
> Okay, now I get the correct number of 561 pseudoprimes, 5, so I can
> assume that it is indeed working right.[/color]

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


--
--Bryan

re: Random Prime Generator/Modular Arithmetic

Actually, there was a small bug fix that I found, and I had a teacher
who told me once that there was only 5 pseudoprimes. I realized that
large numbers of prime numbers were returning false, and discovered the
root of the problem, which was that my M-R test ended too late... But,
it works now, thankfully.

I may switch soon to an upgraded version of the code, to be more
efficient. But for now, I'm just glad to have it work!