Homomorphic encryption technology learning

1、 Concept ： Homomorphic encryption is a cryptography technology based on the computational complexity theory of mathematical problems . The homomorphic encrypted data is processed to obtain an output , Decrypt this output , The result is the same as that obtained by processing unencrypted original data in the same method .
2、 Homomorphic encryption process ：
Take the cloud computing application scenario as an example ,Alice adopt Cloud, The whole process of processing data with homomorphic encryption is roughly like this ：

Alice Encrypt data . And send the encrypted data to Cloud;
Alice towards Cloud Processing method of submitted data , Here we use the function f To express ;
Cloud In function f Process the data under , And send the processed results to Alice;
Alice Decrypt data , Get the results .

According to the homomorphic encryption algorithm , Can be divided into RSA（ Multiplication ）、Paillier（ Add ） etc. .
3、Paillier Homomorphic encryption algorithm ：
Key generation
There are several steps in total ：
1、 Randomly choose two prime numbers p and q Satisfy |p|=|q|=τ|p|=|q|=τ, This condition guarantees p and q Of equal length .
2、 Calculation N=pqN=pq and λ=lcm(p−1,q−1)λ=lcm(p−1,q−1), notes ：lcm Is the least common multiple .
3、 Random selection g∈Z∗N2g∈ZN2∗, Satisfy gcd(L(gλmodN2),N)=1gcd(L(gλmodN2),N)=1, notes ：gcd Represents the greatest common divisor ;Z Represents an integer , The subscript indicates how many elements there are in the integer set ;L(x)=x−1NL(x)=x−1N
4、 The public key is (N,g)(N,g)
5、 The private key is λλ
encryption
For any integer m∈ZNm∈ZN, Choose any random number r∈Z∗Nr∈ZN∗, Ciphertext C=E(m)=gmrNmodN2C=E(m)=gmrNmodN2
Decrypt
The cipher C∈Z∗N2C∈ZN2∗, Decrypt to get clear text m The calculation of is as follows ：
m=L(CλmodN2)L(gλmodN2)modNm=L(CλmodN2)L(gλmodN2)modN
Additive homomorphism
For any plaintext m1,m2∈ZNm1,m2∈ZN, hypothesis E(m1)=gm1rN1modN2E(m1)=gm1r1NmodN2 and E(m2)=gm2rN2modN2E(m2)=gm2r2NmodN2, Yes
E(m1)E(m2)=gm1+m2(r1r2)NmodN2=E(m1+m2modN)E(m1)E(m2)=gm1+m2(r1r2)NmodN2=E(m1+m2modN)
This property shows that Paillier The encryption scheme has additive homomorphism .
4、Paillier Homomorphic encryption algorithm python Realization

from phe import paillier  #  Open source library 
import time  #  Do a performance test 
#  test paillier Parameters 
print(" Default private key size ：", paillier.DEFAULT_KEYSIZE)  # 2048
#  Generating public and private keys 
public_key, private_key = paillier.generate_paillier_keypair()
#  Test the data that needs to be encrypted 
message_list = [12, 100]
#  Encryption operation 
time_start_enc = time.time()
encrypted_message_list = [public_key.encrypt(m) for m in message_list]
time_end_enc = time.time()
print(" Encryption takes time ms：", time_end_enc - time_start_enc)
#  Decryption operation 
time_start_dec = time.time()
decrypted_message_list = [private_key.decrypt(c) for c in encrypted_message_list]
time_end_dec = time.time()
print(" Decryption time ms：", time_end_dec - time_start_dec)
print(" Raw data :", decrypted_message_list)

a1, b1 = message_list  # a1,b1 They are the corresponding original data 
#  Test the homomorphism of addition and multiplication 
a2, b2 = encrypted_message_list  # a2,b2 Corresponding ciphertext 

print("a1 a2 = ", a1, a2)
print("b1 b2 = ", b1, b2)
#  Ciphertext plus plaintext 
print("a1+5=", a1 + 5, ",dec(a2+5)=", private_key.decrypt(a2 + 5))
#  Ciphertext ciphertext 
print("a1+b1=", a1 + b1, ",dec(a2+b2)=", private_key.decrypt(a2 + b2))
#  Ciphertext multiplied by plaintext 
print("a1*2 = ", a1 * 2, ",dec(a2*2) = ", private_key.decrypt(a2 * 2))
#  Ciphertext by ciphertext （ I won't support it ）
print("a1*b1 = ", a1 * b1, ",dec(a2*b2) = ", private_key.decrypt(a2 * b2))

Output results ：
4、RSA Homomorphic encryption algorithm ：
Key generation
1、 Find two prime numbers at random P and Q, The bigger, the safer , And calculate the product n=P∗Qn=P∗Q.P and Q The binary digits of the product of represent RSA Encrypted bits , Generally speaking, there should be 1024 or 2048 position .

2、 Calculation n The Euler function of ϕ(n)ϕ(n), Means less than or equal to n In the positive integer of , And n The number of numbers constituting the coprime relationship . such as 1~8 in , and 8 Mutual quality is 1,3,5,7, therefore ϕ(8)=4ϕ(8)=4, If p and q Prime number , So the Euler function of their product has a special property , Formula for ϕ(n)=ϕ(P∗Q)=ϕ(P−1)ϕ(Q−1)=(P−1)(Q−1)ϕ(n)=ϕ(P∗Q)=ϕ(P−1)ϕ(Q−1)=(P−1)(Q−1).

3、 selection e, Be greater than 1 Less than ϕ(n)ϕ(n), also e And ϕ(n)ϕ(n) To be mutual .

4、 Work out an integer d, bring (ed−1) % ϕ(n)=0(ed−1) % ϕ(n)=0, namely e∗de∗d Divide ϕ(n)ϕ(n) The remainder is 1, In fact, it's transformed into finding the binary first-order equation ed+kϕ(n)=1ed+kϕ(n)=1 A set of solutions （ seek d and k）, The specific use is the extended Euclidean algorithm .

So we can get ：

 Public key  (n, e)
 Private key  (n, d)

Under such conditions , If you want to base it on n and e Work out d, It can only be brutally cracked , The longer the number is , The longer the glass breaks .
encryption
We now have several key values ：n, e, d. To use a public key (n, e) encryption , First, the encrypted number must be an integer and less than n（ If it's a string , You can take... One by one ascii Code or unicode value , And the middle can be divided by non numbers and letters ）. Suppose the number we need to encrypt is A, After encryption B by （ To distinguish, use uppercase ）：

Ae % n=BAe % n=B

without d, Then it's hard to get from B To recover A Of .
Decrypt

If we have a private key (n, d), So for B, It can be calculated by the following formula A：

Bd % n=ABd % n=A

Multiplicative homomorphism relative Paillier It's a little simpler , We just need to multiply the two encrypted numbers , The code snippet is as follows ：

print(' Next, encrypt the calculation  2 x 20')
print(' encryption  2')
enc1 = rsa.core.encrypt_int(2, public_key.e, public_key.n)
print(enc1)
print(' encryption  20') # 40471062776583530669631608186743860028386032505372124150562694293213549812024
enc2 = rsa.core.encrypt_int(20, public_key.e, public_key.n)
print(enc2) # 16915103439566807805446086181091224947678993169521653470724152014464992293178
print(' Multiply ')
result = enc1 * enc2
print(result) # 684572213175112282577113686759405066981454950839007710126450052851088805616753069318980764721622690261112227625923822693220128510206043466290770597572272
print(' Decryption result ')
decrypt_result = rsa.core.decrypt_int(result, private_key.d, public_key.n)
print(decrypt_result) # 40

This blog reference ：https://blog.csdn.net/watson2017/article/details/121630306