當前位置：首頁 > 编程语言 > python >内容正文

python

[超详细保姆教程]Python3.8 实现 Paillier算法

發布時間：2023/12/10 python 28 豆豆

生活随笔收集整理的這篇文章主要介紹了 [超详细保姆教程]Python3.8 实现 Paillier算法小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

準備工作

安裝gmpy2, libnum2

pip install gmpy2

如果報錯

Microsoft Visual C++ 14.0 or later not found

且安裝 Microsoft Build Tools
下載地址:https://visualstudio.microsoft.com/downloads/#build-tools-for-visual-studio-2019
仍未成功解決bug的情況下,請移步：
https://www.lfd.uci.edu/~gohlke/pythonlibs/
由于gmpy2官方不支持py3.4+，所以建議到這里找當前python和cpu版本對應的gmpy2輪子，再通過pip安裝。

pip install /your/path/to/gmpy-xxx.whl

如果pip又報錯，記得升級一下pip

pip install --upgrade pip

如果升級pip的過程中又又又報錯, 可以去官網下最新版的pip手動安裝
_{安裝教程點我，不要問我怎么知道的:)}
至此，準備工作結束

Paillier算法原理

b3ale已經講的比較詳盡了，本篇不再贅述，而在具體實現過程中（b2ale大佬用py2.+而本魚用py3.8）為了簡化運算，本魚做了一些調整：
公/私鑰生成過程中有幾個參數:

$n=p×qn=p\times q$ , where $gcd?(pq,(p?1)(q?1))=1\gcd(pq, (p-1)(q-1))=1$ and p,q are large primes.

$λ=lcm(p?1,q?1)\lambda=lcm(p-1,q-1)$ , lcm(*):=least common multiplier

$g$ 是 $1, n^2]$ 的一個隨機整數

$μ=(L(gλmod?n2))?1mod?n\mu=\left(L(g^\lambda\text{ mod }n^2)\right)^{-1}\text{mod }n$ ， $L(x)=x?1nL(x)=\frac{x-1}{n}$

而當保證 $p, q$ 等長時，上述參數可以被簡化¹：
$n=p×qn=p\times q$
$λ=(p?1)(q?1)\lambda=(p-1)(q-1)$
$g = n + 1$
$μ≡?(n)?1mod?n\mu\equiv\phi(n)^{-1}\text{mod }n$ , $?(n)=(p?1)(q?1)\phi(n)=(p-1)(q-1)$
注意， $?(n)?1\phi(n)^{-1}$ 不是 $1?(n)\frac{1}{\phi(n)}$
Def:
$y≡x?1mod?ny\equiv x^{-1}\text{mod }n$
means $?y?s.t.\exist\text{ y }s.t.$
$xymod?n=1xy\text{ mod }n=1$
所以不要傻傻取倒數哦:）

代碼部分

雖然源代碼的結果暫時沒bug，但感謝評論里網友的指正，這版修改了r 的范圍

import gmpy2 as gy import random import time import libnumclass Paillier(object):def __init__(self, pubKey=None, priKey=None):self.pubKey = pubKeyself.priKey = priKeydef __gen_prime__(self, rs):p = gy.mpz_urandomb(rs, 1024)while not gy.is_prime(p):p += 1return pdef __L__(self, x, n):res = gy.div((x - 1), n)# this step is essential, directly using "/" causes bugs# due to the floating representation in pythonreturn resdef __key_gen__(self):# generate random statewhile True:rs = gy.random_state(int(time.time()))p = self.__gen_prime__(rs)q = self.__gen_prime__(rs)n = p * qlmd =(p - 1) * (q - 1)# originally, lmd(lambda) is the least common multiple. # However, if using p,q of equivalent length, then lmd = (p-1)*(q-1)if gy.gcd(n, lmd) == 1:# This property is assured if both primes are of equal lengthbreakg = n + 1mu = gy.invert(lmd, n)#Originally,# g would be a random number smaller than n^2, # and mu = (L(g^lambda mod n^2))^(-1) mod n# Since q, p are of equivalent length, step can be simplified.self.pubKey = [n, g]self.priKey = [lmd, mu]returndef decipher(self, ciphertext):n, g = self.pubKeylmd, mu = self.priKeym = self.__L__(gy.powmod(ciphertext, lmd, n ** 2), n) * mu % nprint("raw message:", m)plaintext = libnum.n2s(int(m))return plaintextdef encipher(self, plaintext):m = libnum.s2n(plaintext)n, g = self.pubKeyr = gy.mpz_random(gy.random_state(int(time.time())), n)while gy.gcd(n, r) != 1:r += 1ciphertext = gy.powmod(g, m, n ** 2) * gy.powmod(r, n, n ** 2) % (n ** 2)return ciphertextif __name__ == "__main__":pai = Paillier()pai.__key_gen__()pubKey = pai.pubKeyprint("Public/Private key generated.")plaintext = input("Enter your text: ")# plaintext = 'Cat is the cutest.'print("Original text:", plaintext)ciphertext = pai.encipher(plaintext)print("Ciphertext:", ciphertext)deciphertext = pai.decipher(ciphertext)print("Deciphertext: ", deciphertext)

貼一下結果：

Public/Private key generated. Enter your text: cats are the cutest animals. Original text: cats are the cutest animals. Ciphertext: 25346052223872432090673668028369814604750247872904970940453944637708132647693204447778058880188038796678960862480881662269316378038493339862722209450411253159179315579752120520624939517063365042233931559896342057537389383952241515791347881852148363861753156179549392802765201449719683069952653295569855548410125487531238484452325942272812376312498451106331901808817957276225047415960843273067205538684823776768908998399236488360103379351910791237039327283684001428489122374617383511502046482482322402453392173775730236663434913095163636044966266000407676177741906128789357850903643218802668960510046971262440944983838269784997738833643580522170487543961478352995278467192822109770945694108204938082666374252365883280480814043509923339387330401838438181236029473156208445767317218958368213866511398303936396097673820649243814674271673628904029408916818782112251959117003752482612733840628053816567744244093683167511961067264147976506483016458989196540999107745662123949636470485110891091051121417812448337008313106758577418968748296123218548519646893437905650525955277905273590575596836384879925456617663449399435190489493249446852270503540985471716706354406219962362581099291271017280794875678261298782319015278610120121085038719101 raw message: 10466007488176005613356960919452814639381574466217680235130285486894 Deciphertext: b'cats are the cutest animals.'

注意，當傳遞信息越長，生成的素數需要更大

def __gen_prime__(self, rs):p = gy.mpz_urandomb(rs, 1024)...

以上

ref

https://en.wikipedia.org/wiki/Paillier_cryptosystem#cite_note-katzLindell-1
http://blog.b3ale.cn/2019/10/24/Python%E5%AE%9E%E7%8E%B0Paillier%E5%8A%A0%E5%AF%86%E8%A7%A3%E5%AF%86%E7%AE%97%E6%B3%95/
https://www.zhihu.com/question/27645858

https://en.wikipedia.org/wiki/Paillier_cryptosystem#cite_note-katzLindell-1 ??

總結

以上是生活随笔為你收集整理的[超详细保姆教程]Python3.8 实现 Paillier算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。