Provable Secure Public Key Encryption with the Rabin Method
Well, the RSA public key encryption method is nearly 50 years old, and it still does not have a formal proof of its security. It has done well over the years and generally has managed to scale up its computational difficulty to keep pace with computing improvements. While it is thought that the difficulty of RSA is based on factorising a modulus (n) into its prime number factors, it is not a provable secure method, and tomorrow, someone could find a way around the basic method. The first method public key encryption method, though, to prove its security was the Rabin public key encryption method [1]. This was created by the mighty Michael O Rabin [here].
Note: Obviously, the hard problems is integer factorisation, and discrete logarithms will not be safe in terms of quantum cracking, but, at the current time, they are computationally difficult.
Rabin public key
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:
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:
The decryption is then:
and
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² (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 the Chinese Remainder Theory using the √c(mod p) and a √c(mod) operations. If we select primes of p≡q≡3(mod4), the decryption is simply:
Coding
The coding is (based on [code]) is here:
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 here:
=== Message ===
Message=hello
=== Private key (128 bit prime numbers) ===
p=270576397968349702240268570806789986947, q=219242991039694982252977037582947245671
=== Public key ===
n=59321978795327837368543975705006433832257716767865371948246597234695692256437
Cipher: 863473166557328969468694791968801
helloYou can try some provably secure public key encryption here:
References
[1] Rabin, M. O. (1979). Digitalized signatures and public-key functions as intractable as factorization.
