Day 51: Rabin-Miller

A friend of mine asked me to implement RSA. Let’s implement RSA from scratch, then. And since RSA encryption requires more than one algorithm, I will spread it into several days.

In this article I will dig deep but still not deep enough. I’m sorry if the explanation is not crystal clear or sufficient. I need to assume you are comfortable with basics of algebra. If you are not, just say loudly, “bad, bad math”, and read only the first and the last paragraphs.

disclaimer: do not consider my code to be secure; do not consider any cryptography coming from non-experts to be secure; you should never implement any kind of cryptography on your own nor should you interfere with your security in any way; this series is just for fun and as such should be taken

First of all, I will need large prime numbers. To find some, I will implement Rabin-Miller which is what is called a strong pseudoprime test.

That’s a probabilistic test that always identifies a prime number, but sometimes incorrectly denotes a composite as prime. Fortunately, the chance to make a mistake can be decreased by repeating the test.


How does is work? Remember the famous Fermat’s little theorem.

For a prime p the congruence forms a finite field and holds for any a < p. This has a consequence for a square roots of unity.

If is congruent to 1, then x+1 or x-1 has to be divisible by p which implies that x must either be 1 or -1. Hence for prime p there exists no non-trivial (other than 1 or -1) square root of unity.

Rabin-Miller searches for such roots. It starts by a^(p-1) and repetitively takes the square roots. If any non-trivial root is found, p is composite.

The recipe as described would be difficult to implement. But it can be implemented in a probabilistic way. First, we decompose p.

Next we choose a random a and check the following conditions.

For any prime p either the first condition holds or there exists s to comply the second condition. If the conditions can’t be satisfied, p is composite.

But if p is in fact a composite, there is 1/4 chance it will pass the test. Therefore we select another a and repeat the test. After testing k independent values for a, the chance for a mistake gets down to 4^-k.


Notice the idea behind Rabin-Miller. The test initially assumes p to be a prime. Then it searches for evidence it is not. If the evidence is not found, p is a prime with high probability, also called pseudoprime.

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

algorithm

def rabin_miller(prime, tests):
if prime < 5:
return prime in [2, 3]

# set: prime = q * 2**r + 1
q, r = prime - 1, 0
while not q & 1:
q >>= 1
r += 1
    # test repeatedly
for _ in range(tests):
a = randrange(2, prime - 1)
        # pass if: a**q == 1
x = pow(a, q, prime)
if x in [1, prime - 1]:
continue
        # pass if: a**(q * 2**s) == -1, s < r
for _ in range(r - 1):
x = pow(x, 2, prime)
if x == prime - 1:
break
else:
return False
    return True

def prime(bits, tests):
while True:
# random number in [2**bits .. 2**(bits+1)-1]
prime = (1 << bits) | randrange(1 << bits) | 1
        # primality test
if rabin_miller(prime, tests):
return prime

primes

> prime(8, 32)
439
> prime(256, 32)
201154668793766474288430442536590367131439790324764568915020140210857975836059
> prime(1024, 32)
269125048232206117401345895250201449591504183307549168266495829328465264365652266044888014380098012601071901893115536491229951294978896859902559840313809450810889882042706192927923664269003122102302053634736033255126634817570070117329196841505966627142819487286647283902994873557290230700280152589497493642329
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.