Rabin_Cryptosystem

3690 days ago by alex

############################################### # # Example based on Alisdair McAndrew # Introduction to Cryptography With # Open-Source Software # (CRC Press, 2011) pp 103ff # # Updated 27 Mar 2014 to demonstrate padding # to enable automatic decrypting. # ############################################### 
       
# Utility functions (thanks to A. McAndrew). def str2num(s): return ZZ(map(ord,s),256) def num2str(n): nl = n.digits(256) return join(map(chr,nl),'') 
       
##################################################### # # Demonstrate functions ord, chr, map, join, digits # ##################################################### 
       
##################################################### # # Python built-in function "ord" assigns to each # character its 8-bit ASCII code. # # Printable characters c have 0 < ord(c) < 128 # ord("a"), ord("A"), ord("9"), ord("!"), ord("#") 
       
##################################################### # # Function "chr" is the inverse function to "ord". # Given an ASCII code it delivers the character # represented by that code. # # Printable characters chr(c) have 0 < c < 128 # # chr(98), chr(66), chr(50), chr(126), chr(184) 
       
##################################################### # # Function "map" is a Python built-in. # You can use map to pass all the elements of # a sequence through a given function. def isq(i): return i^2 map(isq, [i for i in range(10)]) 
       
############################################ # # Function "join" is a Python built-in; # its opposite is 'split'. # ############################################ 
       
seq = ['Four','score','and','seven','years', 'ago'] jq = join(seq); jq 
       
 
       
# Plaintext: opening words of an old song pl = "Sumer is icumen in" pn = str2num(pl); pn 
       
# Length of plaintext in bits log(pn,2).n(digits=4) 
       
# Set up a 160-bit key as the product of two 80-bit primes p = next_prime(2^80); p; f = mod(p,4); f 
       
while mod(p,4) == 1: p = next_prime(p+1) p 
       
mod(p,4) 
       
####################### # Is p a smooth prime? ####################### factor(p-1) 
       
# Choose second prime q to have 80 bits too, # but not close to p. q = next_prime(p+2^60+1) while mod(q,4) == 1: q = next_prime(q+1) q 
       
mod(q,4) 
       
# # Is q a smooth prime? # factor(q-1) 
       
N = p*q; N 
       
pn < N 
       
# Ciphertext ct = power_mod(pn,2,N); ct 
       
######################################### # # Use extended Euclidean Algorithm. # Find coefficients to write 1=gcd(p,q) # as linear combination of p and q. # ######################################## x, s, t = xgcd(p,q) s; t 
       
# Use the easy method to get square roots of # ciphertext mod p and q. cp = power_mod(ct, (p+1)//4, p) cp 
       
cq = power_mod(ct, (q+1)//4, q) cp 
       
 
       
num2str((s*p*cq + t*q*cp)%N) 
       
num2str((-s*p*cq - t*q*cp)%N) 
       
num2str((s*p*cq - t*q*cp)%N) 
       
num2str((-s*p*cq + t*q*cp)%N) 
       
######################################################### # # Decryption -- "by hand" # # Really, did we HAVE do this? Shouldn't a powerful system # like Sage have its own function to solve congruences # by the Chinese Remainder Theorem (CRT)? # # If it did, what do you think its name would be? # ######################################################## 
       
################################################################# # # Demonstrate padding for redundancy for automatic decrypting. # ################################################################# 
       
print pl 
       
# Pad plaintext with 16 1-bits plpad = join([pl, '\xff\xff'], '') plpad; print plpad 
       
ppn = str2num(plpad); ppn 
       
ppn<N 
       
# Ciphertext for padded message ctp = power_mod(ppn,2,N); ctp 
       
# Square roots of ciphertext mod p and q. cp = power_mod(ctp, (p+1)//4, p) cq = power_mod(ctp, (q+1)//4, q) cp; cq 
       
########################################################### # # Calculate the four square roots of ctp mod N via CRT. # If any ends with '\xff\xff', delete the padding and print. # sgns = [[1,1],[-1,-1],[1,-1],[-1,1]] for i in range(4): rawdecode = num2str((sgns[i][0]*s*p*cq + sgns[i][1]*t*q*cp)%N) if rawdecode.endswith('\xff\xff'): print rawdecode[0:len(rawdecode)-2]