With Rabin public key [1] we select two prime numbers (\(p\) and \(q\)). If possible \( p \equiv q \equiv 3 \pmod 4 \) simplifies the decryption process. Initially we determine \(n=p\cdot q\) and where \(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\).
Rabin public key |
Theory
With Rabin public key we select two prime numbers (p and q). If possible \( p \equiv q \equiv 3 \pmod 4 \) simplifies the decryption process. Initially we determine:
\(n=p q\)
\(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,\dots ,n-1\}\) and the message \(m\in P\). The ciphertext (\(c\)) is then:
\( c=m^{2} \pmod {n} \)
The decryption is then:
\(m_{p}={\sqrt {c} } \pmod p \)
and
\(m_{q}={\sqrt {c} } \pmod q \)
More details on the decryption process [here].
Example
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=5^2 \pmod {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^2 \pmod 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 \(\sqrt{c}\pmod p\) and a \(\sqrt{c}\pmod q\) operations. If we select primes of \( p \equiv q \equiv 3 \pmod 4 \), the decryption is simply:
\(m = c^{(p-1)/4} \pmod p\)
Coding
The coding is (based on [code]):
import random from Crypto.Util.number import * import codecs import Crypto from Crypto import Random def encryption(plaintext, n): # c = m^2 mod n plaintext = padding(plaintext) return plaintext ** 2 % n def padding(plaintext): binary_str = bin(plaintext) # convert to a bit string output = binary_str + binary_str[-16:] # pad the last 16 bits to the end return int(output, 2) # convert back to integer def decryption(a, p, q): n = p * q r, s = 0, 0 # find sqrt # for p if p % 4 == 3: r = sqrt_p_3_mod_4(a, p) elif p % 8 == 5: r = sqrt_p_5_mod_8(a, p) # for q if q % 4 == 3: s = sqrt_p_3_mod_4(a, q) elif q % 8 == 5: s = sqrt_p_5_mod_8(a, q) gcd, c, d = egcd(p, q) x = (r * d * q + s * c * p) % n y = (r * d * q - s * c * p) % n lst = [x, n - x, y, n - y] print (lst) plaintext = choose(lst) string = bin(plaintext) string = string[:-16] plaintext = int(string, 2) return plaintext # decide which answer to choose def choose(lst): for i in lst: binary = bin(i) append = binary[-16:] # take the last 16 bits binary = binary[:-16] # remove the last 16 bits if append == binary[-16:]: return i return # Find SQROOT in Zp where p = 3 mod 4 def sqrt_p_3_mod_4(a, p): r = pow(a, (p + 1) // 4, p) return r # Find SQROOT in Zp where p = 5 mod 8 def sqrt_p_5_mod_8(a, p): d = pow(a, (p - 1) // 4, p) r =0 if d == 1: r = pow(a, (p + 3) // 8, p) elif d == p - 1: r = 2 * a * pow(4 * a, (p - 5) // 8, p) % p return r def egcd(a, b): if a == 0: return b, 0, 1 else: gcd, y, x = egcd(b % a, a) return gcd, x - (b // a) * y, y bits=60 msg="hello" if (len(sys.argv)>1): msg=str(sys.argv[1]) if (len(sys.argv)>2): bits=int(sys.argv[2]) while True: p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) if ((p % 4)==3): break while True: q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) if ((p % 4)==3): break n = p*q print ("=== Message ===") print(("Message=%s") % msg) print(("\n=== Private key (%d bit prime numbers) ===") % bits) print(("p=%d, q=%d") % (p,q)) print("\n=== Public key ===") print("n=%d" % n) plaintext = bytes_to_long(msg.encode('utf-8')) ciphertext = encryption(plaintext, n) print("\nCipher:",ciphertext) plaintext = decryption(ciphertext, p, q) st=format(plaintext, 'x') print(bytes.fromhex(st).decode())
A sample run for 128-bit prime numbers is:
=== Message === Message=hello === Private key (128 bit prime numbers) === p=270576397968349702240268570806789986947, q=219242991039694982252977037582947245671 === Public key === n=59321978795327837368543975705006433832257716767865371948246597234695692256437 Cipher: 863473166557328969468694791968801 hello
Reference
[1] Rabin, M. O. (1979). Digitalized signatures and public-key functions as intractable as factorization (No. MIT/LCS/TR-212). Massachusetts Inst of Tech Cambridge Lab for Computer Science [paper].