费马小定理

若P为质数，存在整数 a， 且gcd(a,p)=1,即二者互为质数，则有a^(p-1)≡ 1(mod p)（指a的p-1次幂取模与1取模恒等）

欧拉函数

对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。

1、当n是素数时，φ(n)=n-1。

2、欧拉函数是积性函数,但不是完全积性函数。

当且只当n可以分解成两个互质的整数之积，n = p × q，则φ(n) = φ(pq) = φ(p)φ(q)

特别的，对于两个素数p,q，n=pq, φ(n)=φ(pq)=(p-1)(q-1)。(RSA算法应用）

3、素数幂p^r,欧拉函数为：φ(p^r)=p^(r-1)*(p-1)

剩余类

模的同余类指的是模 m余数相同的整数构成的集合（其实就是同余）

Carmichael 函数

 

Paillier 算法介绍

python代码实现：（使用 phe 演示 paillier 的同态加和标量乘的性质：）

代码原文链接：https://blog.csdn.net/qq_40589204/article/details/116310125

from phe import paillier # 开源库
import time # 做性能测试

# 测试paillier参数
print("默认私钥大小：",paillier.DEFAULT_KEYSIZE) #2048
# 生成公私钥
public_key,private_key = paillier.generate_paillier_keypair()
# 测试需要加密的数据
message_list = [3.1415,100,-4.6e-19]
# 加密操作
time_start_enc = time.time()
encrypted_message_list = [public_key.encrypt(m) for m in message_list]
time_end_enc = time.time()
print("加密耗时s：",time_end_enc-time_start_enc)
# 解密操作
time_start_dec = time.time()
decrypted_message_list = [private_key.decrypt(c) for c in encrypted_message_list]
time_end_dec = time.time()
print("解密耗时s：",time_end_dec-time_start_dec)
# print(encrypted_message_list[0])
print("原始数据:",decrypted_message_list)

# 测试加法和乘法同态
a,b,c = encrypted_message_list # a,b,c分别为对应密文
a_sum = a + 5 # 密文加明文
a_sub = a - 3 # 密文加明文的相反数
b_mul = b * 1 # 密文乘明文,数乘
c_div = c / -10.0 # 密文乘明文的倒数

# print("a:",a.ciphertext()) # 可以输出密文a的纯文本形式
# print("b:",b.ciphertext()) # 密文b的纯文本形式
# print("c:",c.ciphertext()) # 密文c的纯文本形式
# print("a_sum：",a_sum.ciphertext()) # 密文a_sum的纯文本形式

print("a+5=",private_key.decrypt(a_sum))
print("a-3",private_key.decrypt(a_sub))
print("b*1=",private_key.decrypt(b_mul))
print("c/-10.0=",private_key.decrypt(c_div))

##密文加密文
print((private_key.decrypt(a)+private_key.decrypt(b))==private_key.decrypt(a+b))
#报错，不支持a*b，因为通过密文加实现了明文加的目的，这和原理设计是不一致的，只支持密文加！
print((private_key.decrypt(a)+private_key.decrypt(b))==private_key.decrypt(a*b))

'''
默认私钥大小： 3072
加密耗时s： 0.967409610748291
解密耗时s： 0.2832789421081543
原始数据: [3.1415, 100, -4.6e-19]
a+5= 8.1415
a-3 0.14150000000000018
b*1= 100
c/-10.0= 4.6e-20
True
'''

验证Paillier算法满足加法同态特性及简单加解密 (👍)：

from phe import paillier # 开源库
import time

# 生成公私钥
public_key,private_key = paillier.generate_paillier_keypair()
# 测试需要加密的数据
a= 3.432
b= 300

# 加密操作
time_start_enc = time.time()
encrypted_a = public_key.encrypt(a)
encrypted_b = public_key.encrypt(b) *2      #加密
encrypted_c = encrypted_a+encrypted_b
time_end_enc = time.time()
print("加密耗时s：",time_end_enc-time_start_enc)

# 解密操作
time_start_dec = time.time()
decrypted_a = private_key.decrypt(encrypted_a)
decrypted_b = private_key.decrypt(encrypted_b)    #解密
decrypted_c = private_key.decrypt(encrypted_c)
time_end_dec = time.time()
print("解密耗时s：",time_end_dec-time_start_dec)

print("密文如下:")
print("a:",encrypted_a.ciphertext()) # 可以输出密文a的纯文本形式
print("b:",encrypted_a.ciphertext()) # 密文b的纯文本形式
print("c:",encrypted_a.ciphertext()) # 密文c的纯文本形式

print(f'原始数据: {decrypted_a},{decrypted_b},{decrypted_c}')     #解密原文

'''
加密耗时s： 0.6382911205291748
解密耗时s： 0.28326940536499023
密文如下:
a: 1353618012540547................
b: 1353618012540547...............
c: 1353618012540547......................
原始数据: 3.432,600,603.432
'''

联动：验证RSA算法满足乘法同态特性 (👍)：

#使用gmpy2库
import gmpy2
import time   #同样可以使用time库计算加解密时间
from Crypto.PublicKey import RSA
RSA_BITS = 2048
RSA_EXPONENT = 65537
#生成公私密钥
private_key = RSA.generate(bits=RSA_BITS, e=RSA_EXPONENT)
public_key = private_key.publickey()
#测试的数据
a = 15
b = 5

#加密
time_start_enc = time.time()
encrypted_a = gmpy2.powmod(a, public_key.e, public_key.n)
encrypted_b = gmpy2.powmod(b, public_key.e, public_key.n)
encrypted_c = encrypted_a*encrypted_b    #验证乘法同态性
time_end_enc = time.time()
print("加密耗时s：",time_end_enc-time_start_enc)

#解密
time_start_dec = time.time()
decrypted_a = gmpy2.powmod(encrypted_a, private_key.d, private_key.n)
decrypted_b = gmpy2.powmod(encrypted_b, private_key.d, private_key.n)
decrypted_c = gmpy2.powmod(encrypted_c, private_key.d, private_key.n)
time_end_dec = time.time()
print("解密耗时s：",time_end_dec-time_start_dec)

print("密文如下:")
print("a:",encrypted_a)         # 可以输出密文a的纯文本形式
print("b:",encrypted_b)         # 密文b的纯文本形式
print("c:",encrypted_c)         # 密文c的纯文本形式

#c = a*b结果符合乘法同态加密算法的预期
print(f'解密原始数据: a={decrypted_a},b={decrypted_b},c={decrypted_c}')     #解密原文
'''
加密耗时s： 0.0
解密耗时s： 0.007978439331054688
密文如下:
a: 207633827911....
b: 6558661184640.....
c: 13617975806......
解密原始数据: a=15,b=5,c=75
'''

加解密推论听的这节课讲的很详细！：密码学番外篇1(下) https://www.bilibili.com/video/BV1XT411z7CP/?share_source=copy_web&vd_source=413cd3fe377b37dc603bf413260e9921