Paillier半同态加密rust实现笔记

同态加密（HE）

　　HE是一种特殊的加密方法，它允许直接对加密数据执行计算，如加法和乘法，而计算过程不会泄露原文的任何信息。计算的结果仍然是加密的，拥有密钥的用户对处理过的密文数据进行解密后，得到的正好是处理后原文的结果。

根据支持的计算类型和支持程度，同态加密可以分为以下三种类型：

半同态加密（Partially Homomorphic Encryption, PHE）：只支持加法或乘法中的一种运算。其中，只支持加法运算的又叫加法同态加密（Additive Homomorphic Encryption, AHE）；
部分同态加密（Somewhat Homomorphic Encryption, SWHE）：可同时支持加法和乘法运算，但支持的计算次数有限；
全同态加密（Fully Homomorphic Encryption, FHE）：支持任意次的加法和乘法运算。

Paillier半同态加密方案

　　Paillier是一个支持加法同态的公钥密码系统 [1]，由Paillier在1999年的欧密会（EUROCRYPT）上首次提出。此后，在PKC'01中提出了Paillier方案的简化版本，是当前Paillier方案的最优方案。在众多PHE方案中，Paillier方案由于效率较高、安全性证明完备的特点，在各大顶会和实际应用中被广泛使用，是隐私计算场景中最常用的PHE实例化方案之一。

Paillier的rust实现

　　算法原理我阅读的是这位大佬的文章：Paillier半同态加密：原理、高效实现方法和应用，说的非常详细。

KeyGen()：密钥生成算法。用于产生加密数据的公钥PK（Public Key）和私钥SK（Secret Key），以及一些公开常数PP（Public Parameter）：

　　　　a、随机选择两个大素数 $p, q$ 满足 $g c d ( p q , ( p ? 1 ) ( q ? 1 ) ) = 1$ ，且满足 $p,q$ 长度相等

　　　　b、计算 $n = pq$ 以及 $\lambda = lcm(p-1,q-1)$ ，这里 $lcm$ 表示最小公倍数， $|n|$ 为 $n$ 的比特长度

　　　　c、随机选择整数 $g \leftarrow Z_{n^2} ^ *$ ，下面代码中用的是优化后的算法，取g = n + 1

　　　　d、定义 $L$ 函数： $L(x) = \dfrac{x-1}{n}$ ，计算 $\mu=(L(g^\lambda\mod n^2))^{-1}\mod n$ ,这地方的μ我在测试中发现就是λ^-1，代码中直接计算的lcm^-1mod n

　　公钥： $(n，g)$ ，私钥： $(\lambda, \mu)$

 1 pub struct PaillierKeypair{
 2     // public key
 3     pub n: BigUint,
 4     pub n_exp2: BigUint,
 5     pub g: BigUint,
 6     // private key
 7     pub lcm: BigUint,
 8     // u = (L(g^lcm mod n^2)) mod n = lcm
 9 }
10 impl fmt::Display for PaillierKeypair{
11         fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
12             write!(f, "(\nn = {}\nn^2 = {}\ng = {}\nlcm = {}\n)",
13                    self.n,self.n_exp2, self.g,self.lcm)
14         }
15 }
16 
17 pub fn key_gen(bits_n:usize)-> PaillierKeypair{
18     loop {
19         let p = Generator::new_prime(bits_n / 2); // 这里实际应用中可以多任务加速的，我跑起来比较耗时，可以优化
20         let q = Generator::new_prime(bits_n / 2); // 当bits_n = 1536时，用时甚至达到1分钟
21         let n = p.checked_mul(&q).unwrap(); // n = p*q
22 
23         if n.bits() != bits_n {
24             continue
25         }
26         // check: gcd(pq,(p-1)(q-1)) == 1
27         let mut temp = p.checked_sub(&ONE).unwrap(); // p-1
28         temp = temp.checked_mul(&q.checked_sub(&ONE).unwrap()).unwrap(); // (p-1)(q-1)
29 
30         if n.gcd(&temp) != *ONE {
31             continue
32         }
33 
34         let n_exp2 = n.checked_mul(&n).unwrap(); // n^2
35         let g = n.checked_add(&ONE).unwrap(); // g = n + 1
36         let lcm = (p.checked_sub(&ONE).unwrap()).lcm(&(q.checked_sub(&ONE).unwrap()));
37 
38         return PaillierKeypair {
39             n,　　　　　　// p*q
40             n_exp2,    // n^2 这里计算主要是为了后面加解密方便，提速
41             g,
42             lcm,　　　　// 最小公倍数lcm((p-1）(q-1)) = λ
43         };
44     }
45 }

　　2. Encrypt()：加密算法。使用PK对用户数据Data进行加密，得到密文CT（Ciphertext）；

　　　　a、输入明文消息 $m$ ，满足 $0\leq m<n$

　　　　b、选择随机数 $r$ 满足 $0\leq r<n$ 且 $r\in Z_n^*$

　　　　c、计算密文 $c=g^m r^n \mod n^2$

 1 pub fn encrypt(message: &BigUint,key: &PaillierKeypair)->BigUint{   // 这个地方message的范围是[0,n)半开区间，当message大于n时会错误，开始没注意查了很久
 2     let r = Generator::new_uint(key.n.bits()).mod_floor(&key.n);  // 随机r的取值同样是[0,n)
 3     // g^m = (n+1)^m = (mn + 1) mod n^2
 4     let g_exp_m = message.checked_mul(&key.n).unwrap()
 5         .checked_add(&ONE).unwrap()
 6         .mod_floor(&key.n_exp2);
 7 
 8     let r_exp_n = r.modpow(&key.n,&key.n_exp2);
 9     let c = g_exp_m.checked_mul(&r_exp_n).unwrap();
10     c.mod_floor(&key.n_exp2)
11 }

　　3. Decrypt()：解密算法。用于解密得到数据原文PT（Plaintext）;

　　　　a、输入密文 $c$ ，满足 $c\in Z_{n^2}^*$

　　　　b、计算明文消息 $m=L(c^\lambda \mod n^2)\cdot\mu \mod n$

 1 pub fn mod_inverse(a: &BigUint, n: &BigUint)->Option{   //这个主要求解模逆运算：a^-1 mod n ，没找到现成的运算接口，自己撸了一个，用的是扩展欧几里得算法
 2     let signed_a = BigInt::from_biguint(Sign::Plus,a.clone());　// 扩展欧几里得算法可能会出现负数，所以我转一下，不确定专业库是否有更好的办法
 3     let signed_n = BigInt::from_biguint(Sign::Plus,n.clone());
 4     let extend_gcd = signed_a.extended_gcd(&signed_n);
 5     if extend_gcd.gcd.ne(&BigInt::one()){
 6         return None
 7     }
 8     if extend_gcd.x.gt(&&BigInt::zero()) {
 9         Some(extend_gcd.x.to_biguint().unwrap())
10     }else {
11         Some((extend_gcd.x + unsigned_n).to_biguint().unwrap())
12     }
13 }

1 pub fn decrypt(cypher: &BigUint,key: &PaillierKeypair)->BigUint{ 
2     let u = mod_inverse(&key.lcm,&key.n).unwrap();  // 计算μ，为了速度可以放到秘钥生成的时候，毕竟秘钥对只要一次就可以，加解密才是运行最多的代码
3     cypher.modpow(&key.lcm,&key.n_exp2)      
4         .checked_sub(&ONE).unwrap()
5         .checked_div(&key.n).unwrap()
6         .checked_mul(&u).unwrap()
7         .mod_floor(&key.n)
8 }

　　4. 加解密的验证代码

    #[test]
    fn encrypt_decrypt_test(){
        let keys = key_gen(256); //生成256bits的秘钥对
        // g^m * r^n mod n^2
        let message = Generator::new_prime(256).mod_floor(&keys.n_exp2); // 随机数生成后一定要取n的模，否者解密对不上，因为解密的结果就是有限域[0,n)内
        println!("message: {}",message);
        let cypher = encrypt(&message,&keys);
        println!("cypher: {}",cypher);
        let message = decrypt(&cypher,&keys);
        println!("message: {}",message);

    }

　　随机的一个结果，验证是正确的，可以看到明文空间message在n个比特位，而密文空间则是2n的比特位：

1 message: 66974503675301339632978118530573227132140576565216955902029048867114353816463
2 cypher: 1580877749905632525039727741115670439885127886872359880625218265544553014636237278105806831783772438286839148487172139171820994824898226125064321022362594
3 message: 66974503675301339632978118530573227132140576565216955902029048867114353816463

　　将bits_n参数改为规范的1536后，秘钥的生成比较费时，加解密速度我比较满意，一个结果：

1 message: 1252684931009798105744886157798912173919623779017951705401972293985120531626650393138647048991249424015358398974415833034240029525367790100454746009445616906108452612800233545937932132033401054195527373989843081853540308637524031020576866862133481586260487701455003009450625730007049098610496206308660661144686380509082731332049148456268629649541550807600476702833752962698861650432874278762915550474003254147043302816313167343001675822871227906876870952697912363
2 cypher: 91458756898925932591572235226490802504721979964759783902619875482271203393604895228531274503840751337641010436621213721263209500520214054452098964782515565617546433200781417032127193574747779244640713495808227786561857236592307932151460176482010583605181022284631545630619923886447574646746128408527052746772364343005705077708559384361740186441515196060956650060939898536900563554727453497752356839724393471346793037607582993245437284075542939121810424690643012231922690506028686567313483583186821778187848768507153177975808084372417406434211778158991629395012236176981582219916652227890387391621931089482849258855512513949600191201756208634324187989201812785248311075030812797456023879791353169268254968201351924548497547736664449534915899847846124453851263632198495757622154634736904295603655826927286374264360586445195358143053862853930711025411764808509563477304903234951133207018886127992385530687897040204369060819878
3 message: 1252684931009798105744886157798912173919623779017951705401972293985120531626650393138647048991249424015358398974415833034240029525367790100454746009445616906108452612800233545937932132033401054195527373989843081853540308637524031020576866862133481586260487701455003009450625730007049098610496206308660661144686380509082731332049148456268629649541550807600476702833752962698861650432874278762915550474003254147043302816313167343001675822871227906876870952697912363

　　5. 同态加实现于验证代码

　　　　a、对于明文 m₁和 m₂, 计算 m = m₁+ m₂ mod n

　　　　b、对于密文 $c_1$ 和 $c_2$ ，计算 $c=c_1\cdot c_2 \mod n^2$

 1 #[test]
 2     fn paillier_add_test(){
 3         let keypair = key_gen(256);
 4 
 5         let message0 = Generator::new_prime(256).mod_floor(&keypair.n);
 6         let message1 = Generator::new_prime(256).mod_floor(&keypair.n);
 7         println!("message0:{}",message0);
 8         println!("message1:{}",message1);
 9 
10         let cypher0 = encrypt(&message0,&keypair);
11         let cypher1 = encrypt(&message1,&keypair);
12 
13         let sum_raw = (message0+message1).mod_floor(&keypair.n);
14         println!("plaintext sum:{}",sum_raw);
15 
16         let sum_cypher = cypher0.checked_mul(&cypher1).unwrap()
17                                     .mod_floor(&keypair.n_exp2);
18         let decrypted = decrypt(&sum_cypher,&keypair);
19         println!("ciphertext decrypted sum :{}",decrypted);
20         assert_eq!(sum_raw,decrypted);
21 
22     }

随机的一次结果显示（加密中有随机数r导致每次结果不同），达到预期效果：

message0:80572675196213302274781046440925488076062768477540430842285233194904118761087
message1:75330398095297333423599060505544509578495617068994807014615413620411449663583
plaintext sum:70628361780147599051583823081065583758277794528232401024661717273681824114561
ciphertext decrypted sum :70628361780147599051583823081065583758277794528232401024661717273681824114561

修改到1536比特位key的随机一次结果（比较耗时），：

message0:981241317054349089148524566105637038505190329391459972594035858135788691817167238665303375476049525265414506655443779767820351043735520937984152385641997998052982292618924926746413884437004669543875165490772310691519057966522411218878188795396637999548368673325051576190634533828541034781803593282427223238986324567695549078345676930567058349372987225302857037548233632447843010243211309725885654100552608434728655678616607255114327566078247430873988316740716047
message1:133823190640697178740024093649235391846831968400682841540758432284623592178685358256341638757715856326961765431735399473172755097164936764955756659077870992547532591005153559403262882062362470608675258805393433089503986924642349272395787714376661407094480094172405918774310887974205993891187590280020348306100413116807635993787344590051608701903096860617799013220309140201458310410635562433282923781858204053114833339784605723320949415632842049847705945741150718
plaintext sum:1115064507695046267888548659754872430352022297792142814134794290420412283995852596921645014233765381592376272087179179240993106140900457702939909044719868990600514883624078486149676766499367140152550424296165743781023044891164760491273976509773299406642848767497457494964945421802747028672991183562447571545086737684503185072133021520618667051276084085920656050768542772649301320653846872159168577882410812487843489018401212978435276981711089480721694262481866765
ciphertext decrypted sum :1115064507695046267888548659754872430352022297792142814134794290420412283995852596921645014233765381592376272087179179240993106140900457702939909044719868990600514883624078486149676766499367140152550424296165743781023044891164760491273976509773299406642848767497457494964945421802747028672991183562447571545086737684503185072133021520618667051276084085920656050768542772649301320653846872159168577882410812487843489018401212978435276981711089480721694262481866765

　　6. 同态标量乘法实现于验证代码

　　　　a、对于明文空间 m₁和 a, 计算 m = a * m₁ mod n

　　　　b、对于密文 $c_1$ 和标量 $a$ ，计算 $c = c_1^a \mod n^2$ 　　

 1 fn paillier_scala_mul_test(){
 2         let keypair = key_gen(256);
 3 
 4         let a = Generator::new_uint(32);  // 生成一个随机32bits的整数
 5         let message = Generator::new_prime(256).mod_floor(&keypair.n);
 6         println!("message:{}",message);
 7         println!("a:{}",a);
 8         let message_mul_a  = message.clone().mul(&a).mod_floor(&keypair.n);
 9         println!("plaintext ScalaMul: {}",message_mul_a);
10 
11         let cypher = encrypt(&message,&keypair);
12         let cypher_exp_a = cypher.modpow(&a,&keypair.n_exp2);
13         let decrypted = decrypt(&cypher_exp_a,&keypair);
14 
15         println!("decrypted ScalaMul: {}",decrypted);
16         assert_eq!(message_mul_a,decrypted);
17 
18     }

随机一次测试结果：

message:33881166959344009350892522926807888414391558053525841173372553541039646592819
a:1028573599
plaintext ScalaMul: 84987263896517518588122173040042618261677792733688091835755914749117111689180
decrypted ScalaMul: 84987263896517518588122173040042618261677792733688091835755914749117111689180

bits_n扩展到1536后，随机一次结果，测试通过：

message:336904875687065699756037862153680043531666842141845237320562288460274184952266107168259942436780215909209542844162788565290287909810097658153237331523473656144170107795859582642314735693068770358936974958539171474606565716685655227151044490268529273541593084865520480721259091847423361873435749512068048242843552222111364971284497424434983509503745200682525086343817260021790648672304225694887295901445746490359354557019188908268713676738986349343948646740413047
a:3928419561
plaintext ScalaMul: 110690937513873058124794849927088700013403464344629003586096074170264668081500005560518618969348961941431184636502187644166497295354595125590832141689212672211267763451829619875245497886055758386362503609652988193111042024926860417019096337831573028629066426476229998805176236209617055473949814930635131358022285842277763974133312077153399755755402668938483187368666734151323133378676575001681723139986999559916624447700566129373278884470388279312362334209964073
decrypted ScalaMul: 110690937513873058124794849927088700013403464344629003586096074170264668081500005560518618969348961941431184636502187644166497295354595125590832141689212672211267763451829619875245497886055758386362503609652988193111042024926860417019096337831573028629066426476229998805176236209617055473949814930635131358022285842277763974133312077153399755755402668938483187368666734151323133378676575001681723139986999559916624447700566129373278884470388279312362334209964073

总结：这次paillier的实现除了秘钥对生成比较耗时外，其他都还令人满意！秘钥对的生成一方面可以多线程并行实现优化，另外大素数的算法实现，实际应用中甚至可以用查表实现，没必要实时的计算。

Paillier半同态加密rust实现笔记

相关

标签