The Wonderful Mind of Michael O. Rabin

The Wonderful Mind of Michael O. Rabin

We live in a digitally flaw world. Very little of what we see can be truly trusted. But there are some people who have strived to make our world more trusted, and Michael O. Rabin is one of the most predominant. He was born in 1931 in Germany. In the 1960s he worked in the University of California and MIT, and then moved onto a Professorship at Harvard University. Finally, in 1981, he became a professor at the Hebrew University, and has worked there ever since.

Miller-Rabin test

While at MIT he met Gary Miller, and together they created the Miller-Rabin primality test and which is a fast way of determining if a number is prime or not:

Miller-Rabin Test for Primes is one of the most popular methods for testing for prime numbers used in RSA. Given an odd number (n), we will have an odd number of (n−1), of which we can calculate the power of 2 with a value of s so that n−1=2^s.d. For example, if n is 25, (n−1) will be 24, and which is 2×2×2×3 and which is 2³×3. We then select a random value of a and which is between 1 and (n−1). We have a prime if:

and where r is a value between 0 and s−1. The code is [here]:

A sample run with an unsafe value is:

n=31

(n-1)=30 = 2^1 x 15
s=1, d=15
a=3, r=0

Test 2. It may be prime (a^{2^r d} (mod n) == n-1)

It is still extensively used within public key encryption. Here are some tests using the M-R primality test:

• Is 5 prime?. Try
• Is 7919 prime?. Try
• Is 858,599,509 prime?. Try
• Is 982,451,653 prime?. Try
• Is 982,451,652 prime?. Try
• Is 643808006…,6,769,180,017,646,161,851,573,147,596,390,153 prime (210 digits)?. Try
• Is 643808006…,6,769,180,017,646,161,851,573,147,596,390,152 prime (210 digits)?. Try
• Is 4494179990..9,144,354,948,751,003,607,115,263,071,543,163 prime (210 digits)?. Try
• Is 4494179990..9,144,354,948,751,003,607,115,263,071,543,162 prime (210 digits)?. Try

Public key encryption method

Then, in 1979, Rabin created the Rabin public key encryption method, and was one of the first to show that integer factorization was a hard problem to solve. It created one of the foundation elements for public key encryption, and has since been used in many other research projects [here]:

With Rabin public key we select two prime numbers (p and q). If possible p≡q≡3(mod 4) simplifies the decryption process. Initially we determine:

n=pq

n is the public key and p and q is the private key. We encrypt with n and decrypt with factors of p and q of n. To encrypt, let the plaintext be P={0,…,n−1} and the message m∈P. The ciphertext (c) is then:

c=m² (mod n)

The decryption is then:

m_p=√c (modp)

and:

m_q=√c (mod q)

Let’s take two prime numbers of p=7 and q=11. n will then equal 77, and give a plaintext space (P) of {1, 2 … 76}. If we have a message of (m=5), then the cipher will be c=52 (mod 77) and which is 25. We can now run a small Python program to see how many of the same ciphers we get for each possible message (c=m² (mod n)):

p=7
q=11

n=p*q

m = 5
find=m**2 % n,

for i in range(1,n-1):
    c=i**2 % n,

    if (find==c): print "(%d->%s*)" % (i,c[0]),
    else: print "(%d-> %s)" % (i,c[0]),

The output of this shows the matches for a cipher message of m=5:

(1-> 1) (2-> 4) (3-> 9) (4-> 16) (5->25*) (6-> 36) (7-> 49) (8-> 64) (9-> 4) (10-> 23) (11-> 44) (12-> 67) (13-> 15) (14-> 42) (15-> 71) (16->25*) (17-> 58) (18-> 16) (19-> 53) (20-> 15) (21-> 56) (22-> 22) (23-> 67) (24-> 37) (25-> 9) (26-> 60) (27-> 36) (28-> 14) (29-> 71) (30-> 53) (31-> 37) (32-> 23) (33-> 11) (34-> 1) (35-> 70) (36-> 64) (37-> 60) (38-> 58) (39-> 58) (40-> 60) (41-> 64) (42-> 70) (43-> 1) (44-> 11) (45-> 23) (46-> 37) (47-> 53) (48-> 71) (49-> 14) (50-> 36) (51-> 60) (52-> 9) (53-> 37) (54-> 67) (55-> 22) (56-> 56) (57-> 15) (58-> 53) (59-> 16) (60-> 58) (61->25*) (62-> 71) (63-> 42) (64-> 15) (65-> 67) (66-> 44) (67-> 23) (68-> 4) (69-> 64) (70-> 49) (71-> 36) (72->25*) (73-> 16) (74-> 9) (75-> 4)

We can see we get four possible cipher results which are the same as m=5. These are (m=5,c=25), (m=16,c=25), (m=61,c=25) and (m=72,c=25). This will always be the case, so the challenge is to find the one that is the correct mapping back to the message. The Rabin cryptosystem is thus referred to as a four-to-one method.

To decrypt we use Chinese Remainder Theory on using the √c(mod p) and a √c(mod q) operations. If we select primes of p≡q≡3(mod4), the decryption is simply:

The code for this given here:

https://asecuritysite.com/principles_pub/rabin2

Rabin-Karp

As if these contributions were not enough, in 1981, he created the first instance of oblivious transfer, and where a receiver has a defined probability of receiving a message correctly or not. Then, in 1987, he was back in creating the Rabin-Karp string search method, and which integrated a novel rolling hash technique:

Conclusions

Sometimes academia can be wonderful, and it is made wonderful by the likes of Michael O Rabin. He wasn’t driven by research grants and publication metrics, he was driven by the discovery of new things. Many of things he discovered are now a core foundation of our information age. We must also thank people like Ralph Merkle [here], and who laid down the core foundation around blockchain, and to Adi Shamir [here] for laying down the core principles around public key encryption, Zero Knowledge Proof, and cryptoanalysis.