[Back] This page uses the method on homomorphic encrytion from DGHV (Dijk, Gentry, Halevi and Vaikuntanathan). It converts the bits of a string to a single bit and then ciphers each bit:
Simple Homomorphic Cipher for password checking |
Theory
The code uses the DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) scheme [paper] and which is a fully homomorphic encryption scheme [1].
First we get a random number (p) and two random numbers (q and r), and then encrypt a single bit (m) with:
\(c = p \times q + 2 \times r +m \)
In this case p will be our secret key.
If 2r is smaller than p/2, we cipher with mod p we get:
\(d = (c \mod p) \mod 2\)
We have basically added noise to the value with the q and r values.
With this function we can add (XOR) and multiply (AND).
The logic for checking the first two bits of the password for a match is:
\(cipherbit_7 = (\overline{c_1[7]} \cdot \overline{c_2[7]}) + ({c_1[7]} {c_2[7]}) \)
\(cipherbit_6 = (\overline{c_1[6]} \cdot \overline{c_2[6]}) + ({c_1[6]} {c_2[6]}) \)
etc
Code
The following is an outline:
import sys
from random import randint
import bitarray
def to_bin(string):
res = ''
for char in string:
tmp = bin(ord(char))[2:]
tmp = '%08d' %int(tmp)
res += tmp
return res
def inv(val):
return(val ^ 1)
password1='A'
password2='B'
print "Password A: ",password1, "Password B: ",password2
bits1 = to_bin(password1)
bits2 = to_bin(password2)
print "Bits:\t",bits1
print "Bits:\t",bits2
c_bits1 = [0 for i in xrange(8)]
c_bits2 = [0 for i in xrange(8)]
p =randint(300000, 600000)*2+1
print "Cipher bits 1:"
print "Bit\tCipher\t\tq\t\tr"
for i in range(0,8):
q=randint(50000000, 90000000)
r=randint(1,200)
c_bits1[i] = q * p + 2*r +int(bits1[i])
print bits1[i], "\t",c_bits1[i],"\t",q,"\t",r
if (2*r > p/2):
print 'Error'
print
print "Cipher bits 2:"
print "Bit\tCipher\t\tq\t\tr"
for i in range(0,8):
q=randint(50000000, 90000000)
r=randint(1,200)
c_bits2[i] = q * p + 2*r +int(bits2[i])
print bits2[i], "\t",c_bits2[i],"\t",q,"\t",r
if (2*r > p/2):
print 'Error'
cipher_bit7 = ( (inv(c_bits1[7]) * inv(c_bits2[7]) ) + ( c_bits1[7] * c_bits2[7] ) )
cipher_bit6 = ( (inv(c_bits1[6]) * inv(c_bits2[6]) ) + ( c_bits1[6] * c_bits2[6] ) )
cipher_bit5 = ( (inv(c_bits1[5]) * inv(c_bits2[5]) ) + ( c_bits1[5] * c_bits2[5] ) )
print
print "p value:\t",p
print "\nCipher result:"
print cipher_bit5, cipher_bit6, cipher_bit7
#decrypt
result7 = (cipher_bit7 % p) % 2
result6 = (cipher_bit6 % p) % 2
result5 = (cipher_bit5 % p) % 2
print "\nResults"
print result5,result6,result7
if ((result7==1) and (result6==1) and (result5==1)):
print "Passwords are the same"
else:
print "Passwords are not the same"
Example
In the following we create 16 cipher value bits and then make a calculation, and then decipher with the p value:
Password A: A Password B: A Bits: 01000001 Bits: 01000001 Cipher bits 1: Bit Cipher q r 0 87287788205444 78622560 82 1 88750786929049 79940324 18 0 61043423130676 54983524 32 0 80491991247193 72501395 29 0 86945995810958 78314698 142 0 84631751261457 76230193 174 0 84101674513206 75752738 6 1 83851357008809 75527270 149 Cipher bits 2: Bit Cipher q r 0 94222140856380 84868526 171 1 95098406442408 85657803 184 0 71366212470212 64281550 31 0 58005073238079 52246797 159 0 56107886863272 50537948 174 0 94347189697499 84981161 103 0 59943468498828 53992764 48 1 82178328189517 74020326 39 p value: 1110213 Cipher result: 15969535781392288756035033131 10082692153762243110106057171 13781528670812359005495712181 Results 1 1 1 Passwords are the same
Presentation
Here is a presentation on the method used:
Reference
[1] M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan, "Fully Homomorphic Encryption over the Integers". Proceedings of Eurocrypt 2010.