准备工作

安装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\times q$, where $\gcd (pq,(p-1)(q-1))=1$ and p,q are large primes.

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

$g$ 是$[1,n^2]$的一个随机整数

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

而当保证$p,q$等长时，上述参数可以被简化¹：
$n=p\times q$
$\lambda =(p-1)(q-1)$
$g=n+1$
$\mu \equiv \varphi (n{)}^{-1}\text{mod }n$, $\varphi (n)=(p-1)(q-1)$
注意，$\varphi (n{)}^{-1}$不是$\frac{1}{\varphi (n)}$
Def:
$$y\equiv x^{-1}\text{mod }n$$
means $\exists \text{ y }s.t.$
$$xy\text{ mod }n=1$$
所以不要傻傻取倒数哦:）

代码部分

虽然源代码的结果暂时没bug，但感谢评论里网友的指正，这版修改了r 的范围

import gmpy2 as gy
import random
import time
import libnum

class Paillier(object):
    def __init__(self, pubKey=None, priKey=None):
        self.pubKey = pubKey
        self.priKey = priKey

    def __gen_prime__(self, rs):
        p = gy.mpz_urandomb(rs, 1024)
        while not gy.is_prime(p):
            p += 1
        return p
    
    def __L__(self, x, n):
        res = gy.div((x - 1), n)
        # this step is essential, directly using "/" causes bugs
        # due to the floating representation in python
        return res
    
    def __key_gen__(self):
        # generate random state
        while True:
            rs = gy.random_state(int(time.time()))
            p = self.__gen_prime__(rs)
            q = self.__gen_prime__(rs)
            n = p * q
            lmd =(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 length
                break
        g = n + 1
        mu = 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]
        return
        
    def decipher(self, ciphertext):
        n, g = self.pubKey
        lmd, mu = self.priKey
        m =  self.__L__(gy.powmod(ciphertext, lmd, n ** 2), n) * mu % n
        print("raw message:", m)
        plaintext = libnum.n2s(int(m))
        return plaintext

    def encipher(self, plaintext):
        m = libnum.s2n(plaintext)
        n, g = self.pubKey
        r = gy.mpz_random(gy.random_state(int(time.time())), n)
        while gy.gcd(n, r)  != 1:
            r += 1
        ciphertext = gy.powmod(g, m, n ** 2) * gy.powmod(r, n, n ** 2) % (n ** 2)
        return ciphertext

if __name__ == "__main__":
    pai = Paillier()
    pai.__key_gen__()
    pubKey = pai.pubKey
    print("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

---

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