This page uses the method on homomorphic encryption 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 range(8)] c_bits2 = [0 for i in range(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.