Hike News
Hike News

Python实现Paillier加密解密算法

Paillier 加密系统,是 1999 年 Paillier 发明的概率公钥加密系统。基于复合剩余类的困难问题。该加密算法是一种同态加密,满足加法和数乘同态。

Introduction

Keygen

首先选择两个大素数 $p$ 和 $q$,计算出 $n$ 为 $p$ 和 $q$ 的乘积。并取一个随机数 $g$(通常取 $n+1$)。$n$ 和 $g$ 作为公钥。

然后根据卡迈克尔函数计算私钥 $\lambda$ 为 $p-1$ 和 $q-1$ 的乘积。

Encipher

加密时取一个随机数 $r$,计算出 $c \equiv g^m r^n(mod\ n^2)$。

Decipher

解密有一点复杂。首先我们可以得到:

$$
c^\lambda \equiv (g^m r^n)^\lambda \equiv g^{m \lambda} r^{n \lambda}(mod\ n^2)
$$

根据卡迈克尔函数,即对于任何 $\omega \in Z^*_{n^2}$,必定存在以下结论:

$$
\omega^{n \lambda} \equiv 1(mod\ n^2)
$$

那么可以得到 $c^\lambda \equiv g^{m \lambda}(mod\ n^2)$。

然后看看生成元 $g$,实际上是通过 $g=(1+\alpha n)\beta^n$ 得到的,并且 $\alpha,\beta \in Z^*_n$。由此可得:

$$
c^\lambda \equiv (1+\alpha n)^{m \lambda}\beta^{n m \lambda} \equiv (1+\alpha n)^{m \lambda}(mod\ n^2)
$$

再根据公式 $(1+n)^x \equiv 1+xn(mod\ n^2)$,可以得到:

$$
c^\lambda \equiv (1+n)^{\alpha m \lambda} \equiv 1+n \alpha m \lambda(mod\ n^2)
$$

然后我们在此处定义一个函数 $L(x)=\frac{x-1}{n}$,则 $L(c^\lambda)=\alpha m \lambda$。

那么我们可以得到明文的计算公式为 $m \equiv \frac{L(c^\lambda)}{L(g^\lambda)} \equiv \frac{\alpha m \lambda}{\alpha \lambda} \equiv m(mod\ n)$。

Getting started

通过 gmpy2 和 libnum 库实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#!/usr/bin/env python
import gmpy2
import random
import time
import libnum

def get_prime(rs):
p = gmpy2.mpz_urandomb(rs, 1024)
while not gmpy2.is_prime(p):
p = p + 1
return p

def L(x, n):
return (x - 1) / n

def keygen():
rs = gmpy2.random_state(int(time.time()))
p = get_prime(rs)
q = get_prime(rs)
n = p * q
lmd = (p - 1) * (q - 1)
#g = random.randint(1, n ** 2)
g = n + 1
if gmpy2.gcd(L(gmpy2.powmod(g, lmd, n ** 2), n), n) != 1:
print '[!] g is not good enough'
exit()
pk = [n, g]
sk = lmd
return pk, sk

def encipher(plaintext, pk):
m = libnum.s2n(plaintext)
n, g = pk
r = random.randint(1, n ** 2)
c = gmpy2.powmod(g, m, n ** 2) * gmpy2.powmod(r, n, n ** 2) % (n ** 2)
return c

def decipher(c, pk, sk):
[n, g] = pk
lmd = sk
u = gmpy2.invert(L(gmpy2.powmod(g, lmd, n ** 2), n), n) % n
m = L(gmpy2.powmod(c, lmd, n ** 2), n) * u % n
plaintext = libnum.n2s(m)
return plaintext

if __name__ == '__main__':
pk, sk = keygen()
#print 'pk:', pk
#print 'sk:', sk
plaintext = raw_input('Please input your message: ')
ciphertext = encipher(plaintext, pk)
print 'Ciphertext:', ciphertext
plaintext = decipher(ciphertext, pk, sk)
print 'Plaintext:', plaintext

References

The Paillier Cryptosystem
卡迈克尔函数