做系统去哪网站下载镜像,wordpress 里程密,东莞建设网东莞市住房和城乡,网页制作对联随着对crypten与密码学的了解#xff0c;我们将逐渐深入学习相关知识。今天#xff0c;我们将跟随同态加密的发展历程对相关算法进行简单的收集整理 。
目录
同态加密概念
RSA算法
ElGamal算法
ELGamal签名算法
Paillier算法
BGN方案
Gentry 方案
BGV 方案
BFV 方案…随着对crypten与密码学的了解我们将逐渐深入学习相关知识。今天我们将跟随同态加密的发展历程对相关算法进行简单的收集整理 。
目录
同态加密概念
RSA算法
ElGamal算法
ELGamal签名算法
Paillier算法
BGN方案
Gentry 方案
BGV 方案
BFV 方案
GSW 方案
CKKS方案 同态加密概念
同态加密是基于数学难题与计算复杂性理论的密码学技术。
它是指密文状态下对加密信息进行计算得到一个输出将这一输出进行解密其结果与用同一方法处理未加密的明文信息计算得到的输出结果是一致的。 同态加密分为半同态加密和全同态加密。其中
半同态加密允许在加密数据上执行特定的算术运算加法或乘法。
全同态加密支持对密文进行任意形式的加法和乘法运算。 半同态加密 全同态加密 乘法同态 加法同态 有限次数全同态 第一代 第二代 第二代 第三代 可实现浮点数近似计算适合机器学习建模场景 RSA算法 ElGamal算法 Paillier算法 Boneh-Goh-Nissim方案 Gentry方案 BGV方案 BFV方案 GSW方案 CKKS方案 RSA算法
RSA算法是一种公钥算法体制即每一位用户都有一对密钥一个是可以公开的另一个则是秘密的分为加密密钥Ka和解密密钥Kd。加密密钥控制加密解密密钥控制解密由计算复杂性原理保证加密钥Ka不能通过计算推出解密钥。这样就实现了即使将Ka公开也不会暴露Kd。
RSA算法描述
任意选取两个不同的大素数p和q经典值为1024位计算乘积npqzp-1q-1任意选取一个大整数e满足gcdez1即e和z互质。整数e用作加密钥。注意e的选取是很容易例如所有大于p和q的素数都可用确定解密钥d。满足demodz1即dekz1因此若知道e和z则很容易计算出d公开整数n和e秘密保存d。
加密算法(明文mm为小于n的整数加密为密文c)
cm^emodn
解密算法(将密文c解密为明文m)
mc^dmodn
代码示例
import randomdef fastExpMod(b, n, m):return : b^n mod mresult 1while n ! 0:if (n 1) 1: # 按位与操作result (result * b) % mb (b * b) % mn n 1 # 位数右移操作return resultdef Euclid(a, b):欧几里得算法 ax by gcd(a,b)Return : [x , y , gcd(a,b)]X [1, 0, a]Y [0, 1, b]while Y[2] ! 0:Q X[2] // Y[2]NEW_Y [i * Q for i in Y]T list(map(lambda x: x[0] - x[1], zip(X, NEW_Y)))X Y.copy()Y T.copy()return Xdef fermatPrimeTest(m, k):费马素性检验算法m : 给定整数k : 安全参数重复K次if m % 2 0:return Falsefor i in range(k):a random.randint(2, m - 2)g Euclid(a, m)if g[2] 1:r fastExpMod(a, m - 1, m)if r 1:continueelse:return Falseelse:return Falsereturn Truedef findPrime(lower, upper):return : 一个位于upper和lower之间的素数while True:n random.randint(lower, upper)if fermatPrimeTest(n, 6) True:return ndef selectE(fn):fn : euler functionReturn : ewhile True:e random.randint(1, fn)temp Euclid(e, fn)if temp[2] 1:return edef keyGenerate(lower, upper):给定两个素数p和q生成的区间return : e,n,dp findPrime(lower, upper)q findPrime(lower, upper)print(p: str(p) q: str(q))# print(q:str(q))n p * qfn (p - 1) * (q - 1)e selectE(fn)temp Euclid(e, fn) # 欧几里得算法求逆元d temp[0]if d 0: # 由于e和fn互素故一定存在逆元d d fn # 保证d为正数return e, n, ddef Encryption_Decryption():e, n, d keyGenerate(1000, 10000) # 密钥生成# 更改keyGenerate函数的两个参数可以改变生成素数的位数大小。print(public key (e,n):, end)print(( str(e) , str(n) )\n)print(private key d: str(d) \n)m random.randint(1, n) # m n m为明文print(Plaintext: str(m))c fastExpMod(m, e, n) # 加密 c为密文 m^e mod nprint(\nEncryption of PlainText: str(c))x fastExpMod(c, d, n) # 解密 c^d mod nprint(\nDecryption of CipherText: str(x))if x m:print(\nThe plaintext and ciphertext are the same.)if __name__ __main__:Encryption_Decryption() 运行结果 这段代码通过生成RSA密钥对加密一个随机生成的明文然后解密密文验证了加密和解密的正确性。具体步骤包括生成素数、计算 n 和 ϕ(n)、选择公钥 e、计算私钥 d、加密明文、解密密文并最终验证解密后的明文与原始明文是否相同。 ElGamal算法
EIGamal密码是除了RSA密码之外最有代表性的公开密钥密码。
与RSA算法不同RSA是基于因数分解的公钥体制密码而EIGamal是建立在离散对数的困难问题上的一种公钥体制密码。
EIGamal算法描述
选取一个素数p以及小于p的两个随机数g和x计算yg^xmodp公钥为ygp私钥为x
加密算法 M为明文
选取一个与p-1互质的整数kC1g^kmodpC2y^kMmodp(C1,C2)即为密文
解密算法
C2/C1^x modpMmodp
举例
取p11, g5, x2
则 y g^xmodp 3
取 k 为 7 m为10
则C1 g^kmodp 3
C2 y^k*m mod p 2
则C1^xmodp 9
9在模11下的逆元为5
所以 C 2 /C 1^ x2∗5mod10 10mod10所以解密成功 示例代码
import random# 判断一个数是否为素数def is_prime(n):if n 1:return Falseif n 3:return Trueif n % 2 0 or n % 3 0:return Falsei 5while i * i n:if n % i 0 or n % (i 2) 0:return Falsei 6return True# 生成一个随机的素数def generate_prime():while True:p random.randint(100, 1000)if is_prime(p):return p# 生成一个原根def generate_generator(p):phi p - 1factors []for i in range(2, int(phi ** 0.5) 1):if phi % i 0:factors.append(i)while phi % i 0:phi // iif phi 1:factors.append(phi)for g in range(2, p):is_generator Truefor factor in factors:if pow(g, phi // factor, p) 1:is_generator Falsebreakif is_generator:return g# 生成ElGamal公私钥对def generate_keys():p generate_prime()g generate_generator(p)a random.randint(2, p - 1)h pow(g, a, p)return (p, g, h, a)keys generate_keys()print(公钥(p, g, h) , keys[0], ,, keys[1], ,, keys[2])print(私钥a , keys[3]) 运行结果 这段代码实现了 ElGamal 密码体制的公私钥对生成包括生成随机素数、原根和计算公私钥。生成的公钥 (p, g, h) 和私钥 a 可以用于后续的加密和解密操作。 ELGamal签名算法
密钥产生
确定一个大素数p
取p的一个本原根g
在Zp域上选择一个随机数x
y gxmodp
(y, g, p)为公钥x为私钥
签名算法
设待签名的消息为m
取一个与p-1互质的k
C1gkmodp
C2(H(m)-x*C1) * k-1mod(p-1)
输出签名(C1,C2)和消息m 代码示例
import randomfrom sympy import isprime, mod_inverse# 选择一个素数p和生成元gdef generate_prime_and_generator():while True:p random.randint(2 ** 10, 2 ** 11) # p的范围if isprime(p):breakwhile True:g random.randint(2, p - 2)if pow(g, (p - 1), p) 1:breakreturn p, g# 生成密钥对def generate_key_pair(p, g):x random.randint(2, p - 2)y pow(g, x, p)return x, y# 签署消息def sign_message(p, g, x, m):k random.randint(1, p - 2)r pow(g, k, p)s (m - x * r) * mod_inverse(k, p - 1) % (p - 1)return (r, s)# 验证签名def verify_signature(p, g, y, m, r, s):if not (0 r p and 0 s p - 1):return Falseleft pow(y, r, p) * pow(r, s, p) % pright pow(g, m, p)return left right# 输出签名详细过程def print_signature_process(p, g, x, m, r, s):print(--------------------签名过程--------------------)print(f签名消息为: {m})print(f私钥x为: {x})print(f随机数k为: {k})print(f签名结果r为: {r})print(f签名结果s为: {s})# 主程序if __name__ __main__:# 生成素数和生成元p, g generate_prime_and_generator()# Alice生成密钥对x_alice, y_alice generate_key_pair(p, g)# 输出参数print(--------------------参数生成过程--------------------)print(f素数p为: {p})print(f生成元g为: {g})print(fAlice的公钥y为: {y_alice})# Alice签署消息message 20240301k random.randint(1, p - 2)r, s sign_message(p, g, x_alice, message)# 输出签名详细过程print_signature_process(p, g, x_alice, message, r, s)# 用户输入签名print(--------------------验证签名过程--------------------)user_r int(input(请输入r的值: ))user_s int(input(请输入s的值: ))# 验证签名if verify_signature(p, g, y_alice, message, user_r, user_s):print(签名有效)else:print(签名无效) 运行结果 这段代码实现了 ElGamal 签名方案的生成、签署和验证过程。通过生成素数 p 和生成元 g生成密钥对签署消息并验证签名确保了数字签名的安全性和有效性。 Paillier算法
Paillier 同态加密算法是一种非对称加密算法该算法利用了数论中的复合剩余类的数学性质。
Paillier算法描述
1.随机选择两个大质数p和q满足gcdpq,(p-1)(q-1)1。 这个属性是保证两个质数长度相等。
2.计算 n pq和λ lcm (p - 1,q-1)。
3.选择随机整数gg属于Z*n^2使得满足n整除g的阶。
4.公钥为ng
5.私钥为λ。
加密算法
m属于Znr为[1,n-1]的随机数转换成密文
Cg^m·r^n modn^2;
解密算法 代码示例
from phe import paillierimport gmpy2 as gy# 生成 Paillier 密钥对public_key, private_key paillier.generate_paillier_keypair(n_length128)print(n: , public_key.n)print(g: , public_key.g)print(p: ,private_key.p)print(q: ,private_key.q)a 15b 20print(a: ,a)print(b: ,b)# 加密 a 和 ba_enc public_key.encrypt(a)print(a_enc: ,a_enc.ciphertext())b_enc public_key.encrypt(b)print(b_enc: ,b_enc.ciphertext())print(同态加)print(a b ,ab)c_enc a_enc b_encprint(c_enc a_enc b_enc: ,c_enc.ciphertext())c_dec private_key.decrypt(c_enc)print(c_dec a b: ,c_dec)print(同态数乘)print(a * b ,a*b)c1_enc a * b_encprint(c1_enc a * b_enc: ,c1_enc.ciphertext())c2_enc b * a_encprint(c2_enc b * a_enc: ,c2_enc.ciphertext())c1_dec private_key.decrypt(c1_enc)c2_dec private_key.decrypt(c2_enc)print(c1_dec a * b: ,c1_dec)print(c2_dec b * a: ,c2_dec)
运行结果 这段代码展示了如何使用 Paillier 同态加密算法进行基本的同态加法和数乘操作。Paillier 同态加密算法是一种加法同态加密算法支持对密文的加法和数乘操作。 BGN方案
BGN是一种同态加密方案是Bonel h等人在2005提出的一种具有全同态性质的加密方案。和传统的仅能支持单同态的elgamal和paillier加密方案不一样BGN能够同时支持加同态和一次乘同态运算。 1.选择椭圆曲线和生成元
2.选择一个椭圆曲线 E 和一个生成元 P使得 E 的阶为 q且 q 是一个大素数。
3.选择一个随机的私钥 s范围在 1 到 q−1 之间。
4.计算公钥 PpubsP。
生成密钥对
公钥(E,P,Ppub)
私钥s
加密算法
选择随机数
选择一个随机数 r范围在 1 到 q−1 之间。
加密消息
对于消息 m计算密文 C
C(rP,rPpubmP)
其中C 是一个二元组第一个元素是 rP第二个元素是 rPpubmP。解密算法
解密密文
对于密文 C(C1,C2)计算mPC2−sC1
由于 C1rP 和 C2rPpubmP可以推导出
mP(rPpubmP)−s(rP)r(sP)mP−s(rP)mP
通过椭圆曲线上的点 mP 恢复消息 m。 同态加法
同态加法
对于两个密文 C1(C11,C12) 和 C2(C21,C22)计算
C1C2(C11C21,C12C22)
解密结果为
m1m2(C12C22)−s(C11C21)(m1Pm2P)(m1m2)P
同态数乘
同态数乘
对于一个密文 C(C1,C2) 和一个标量 k计算
kC(kC1,kC2)
解密结果为
kmk(C2−sC1)k(mP)(km)P 代码示例
from ecdsa import NIST384p, SigningKey, VerifyingKeyfrom ecdsa.util import randrange_from_seed__trytryagainimport os# 生成密钥对def generate_keys():sk SigningKey.generate(curveNIST384p)vk sk.verifying_keyreturn sk, vk# 加密消息def encrypt(vk, m):# 生成一个在有效范围内的随机数 rr randrange_from_seed__trytryagain(os.urandom(32), NIST384p.order)C1 r * NIST384p.generatorC2 (r * vk.pubkey.point) (m * NIST384p.generator)return C1, C2# 解密消息def decrypt(sk, C1, C2):# 计算 -sC1neg_sC1 -(sk.privkey.secret_multiplier * C1)# 计算 C2 (-sC1)mP C2 neg_sC1# 通过椭圆曲线上的点 mP 恢复消息 mm mP.x() % NIST384p.orderreturn m# 同态加法def homomorphic_add(C1, C2, D1, D2):return C1 D1, C2 D2# 同态数乘def homomorphic_mul(C1, C2, k):return k * C1, k * C2# 主程序if __name__ __main__:# 生成密钥对sk, vk generate_keys()print(公钥:, vk.to_string().hex())print(私钥:, sk.to_string().hex())# 加密消息m1 15m2 20C1, C2 encrypt(vk, m1)D1, D2 encrypt(vk, m2)print(C1:, C1.x(), C1.y())print(C2:, C2.x(), C2.y())print(D1:, D1.x(), D1.y())print(D2:, D2.x(), D2.y())# 同态加法E1, E2 homomorphic_add(C1, C2, D1, D2)m3 decrypt(sk, E1, E2)print(同态加法结果:, m3)# 同态数乘k 3F1, F2 homomorphic_mul(C1, C2, k)m4 decrypt(sk, F1, F2)print(同态数乘结果:, m4)
运行结果 BGN 同态加密方案通过椭圆曲线上的点运算实现了对密文的加法和数乘操作。通过生成密钥对、加密消息、解密消息、同态加法和同态数乘可以实现对密文的高效计算。 Gentry 方案
提出者及背景2009 年由 Craig Gentry提出这是全同态加密领域的重要突破解决了自公钥加密发明以来一直困扰科学家们的难题。
在传统加密中数据一旦加密就很难在密文状态下进行各种类型的计算。例如对于常规的 RSA 或 AES 加密加密后的数据只能进行有限的操作如存储、传输等。而全同态加密允许在密文上直接进行任意次数的加法和乘法等计算并且解密后的结果与在明文上进行相同计算再解密的结果相同。
Gentry 方案之前全同态加密的概念虽然被提出但一直没有有效的实现方式。Gentry 利用基于理想格的复杂数学结构设计出了首个可行的全同态加密方案。
核心原理基于理想格的数学对象利用 “双盲” 设计可以检测加密漏洞并进行修复而不会造成信息泄露。
方案特点最初的方案依赖矩阵和矢量进行加密计算复杂实用性不强。但它为后续全同态加密方案的研究奠定了基础具有开创性意义。
局限性随着计算步骤的增加连续加密的计算结果质量下降需要系统实现一定量的计算来进行数据清理实现全同态且计算复杂。
BGV 方案
提出者及背景由 Brakerski、Gentry 和 Vaikuntanathan 提出是第二代全同态加密方案中的重要代表。
核心原理基于更弱的假设来提高性能和安全性使用 LWE 或 RLWE 问题构建一个基本的 GLWE 加密方案再利用 “重线性化” 和 “维度缩减” 技术进行改进还使用了 “模数切换” 技术来实现同态加法和同态乘法操作并有效减少计算复杂度和存储需求。
方案特点不需要 Gentry 的自举过程提供了基于 LWE 或 RLWE 问题的 FHE 方案选择在选择适当的方案时具有更大灵活性其安全性和效率都有一定的提升。
局限性虽然避免了自举过程但在实际应用中对于大规模数据和复杂计算其性能仍有待进一步提高。
BFV 方案
提出者及背景最初的 LWE 形式由 Brakerski 给出后在此基础上给出了更实用的 RLWE 形式是第二代同态加密中的核心方案之一微软的全同态加密软件 SEAL 最初就是实现的 BFV 方案。
核心原理在明文空间的高 bit 位编码信息使用的编码结构通过密钥生成、加密、解密和同态运算等算法来实现同态加密。
方案特点同态加法相对简单就是向量加法。同态乘法较为复杂需要引入 “重线性化” 技术将乘法破坏的解密结构恢复成线性结构。
局限性乘法运算的复杂性导致其在处理复杂计算时效率可能较低且重线性化过程可能会引入一定的误差和计算开销。
GSW 方案
提出者及背景由 Gentry、Sahai 和 Waters 提出是一种基于近似特征向量的全同态加密方案。
核心原理利用近似特征向量的相关性质将加密、解密和同态运算等操作与矩阵的运算相结合通过对密文进行特定的矩阵变换来实现同态计算。
方案特点同态运算更加高效为矩阵的加、乘运算且不会引起密文维度的膨胀无需借助其他技术来控制密文维度的增长密文噪声的控制更加简洁、有效。
局限性不支持 SIMD 同态操作自举实现依赖的安全假设强度较第二代有所弱化且困难问题的近似因子仅为维度 n 的多项式。 这些方案在同态加密领域的发展中逐代递进从Gentry的首次证明FHE的存在性到BGV、BFV和GSW方案的不断优化和简化逐步提高了同态加密的效率和实用性。每个方案都在前一个方案的基础上进行了改进引入了新的技术和方法。 CKKS方案
CKKS方案是由Jung Hee Cheon、Kyoohyung Han、Duhyeong Kim、Moon Sung Lee和Yongsoo Song在2019年提出的一种同态加密方案。
它是第一个支持复数运算的同态加密方案。这使得它在处理复数和多项式运算时非常高效特别适用于需要进行复数运算的应用场景如信号处理、图像处理和机器学习。CKKS方案基于环上学习带误差问题Ring-LWE这是一种高效的构造方法减少了密文的大小和计算复杂度。同时CKKS方案引入了多模数技术支持在不同模数下进行同态操作提高了灵活性和效率。
算法步骤
1.选择参数
选择一个合适的环 R 和一个模数 q。
选择一个生成元 g 和一个随机的私钥 s。
2.生成公钥
计算公钥 hgsmodq。
生成密钥对 (h,s)。
加密算法
选择一个随机数 r。
加密消息
对于消息 m计算密文 C
C(r·g,r·hm)modq
解密算法
解密密文
对于密文 C(C1,C2)计算
mC2−s·C1modq
同态加法
同态加法
对于两个密文 C1(C11,C12) 和 C2(C21,C22)计算
C1C2(C11C21,C12C22)modq
同态数乘
同态数乘
对于一个密文 C(C1,C2) 和一个标量 k计算
kC(k·C1,k·C2)modq 代码示例
import tenseal as ts# 生成密钥对def generate_keys():# 创建 CKKS 上下文context ts.context(ts.SCHEME_TYPE.CKKS, poly_modulus_degree8192, coeff_mod_bit_sizes[60, 40, 40, 60])# 生成密钥context.generate_galois_keys()context.global_scale 2 ** 40return context# 加密消息def encrypt(context, message):# 创建张量tensor ts.plain_tensor(message)# 加密张量encrypted_tensor ts.ckks_tensor(context, tensor)return encrypted_tensor# 解密消息def decrypt(context, encrypted_tensor):# 解密张量decrypted_tensor encrypted_tensor.decrypt()return decrypted_tensor# 同态加法def homomorphic_add(encrypted_tensor1, encrypted_tensor2):return encrypted_tensor1 encrypted_tensor2# 同态数乘def homomorphic_mul(encrypted_tensor, scalar):return encrypted_tensor * scalar# 主程序if __name__ __main__:# 生成密钥对context generate_keys()print(密钥生成完成)# 加密消息message1 [1, 2, 3, 4]message2 [5, 6, 7, 8]encrypted_tensor1 encrypt(context, message1)encrypted_tensor2 encrypt(context, message2)print(消息加密完成)# 同态加法encrypted_sum homomorphic_add(encrypted_tensor1, encrypted_tensor2)decrypted_sum decrypt(context, encrypted_sum)print(同态加法结果:, decrypted_sum.tolist())# 同态数乘scalar 3encrypted_mul homomorphic_mul(encrypted_tensor1, scalar)decrypted_mul decrypt(context, encrypted_mul)print(同态数乘结果:, decrypted_mul.tolist()) 运行结果 这段代码实现了一个基于 CKKS 同态加密方案的示例支持对密文的加法和数乘操作。通过生成密钥对、加密消息、解密消息、同态加法和同态数乘可以实现对密文的高效计算。 本篇简单介绍了随着同态加密的发展而产生的几种同态加密算法同态加密的发展是向着高效化、功能化的方向前进的其应用前景十分广阔。通过对同态加密的了解我们一定能够实现更高效的技术。
本篇借鉴来源于Kimi 是一个有着超大“内存”的智能助手可以一口气读完二十万字的小说还会上网冲浪快来跟他聊聊吧
同态加密技术概览-CSDN博客
