原文链接：https://tover.xyz/p/OU98/
参考
[OU98] Okamoto T, Uchiyama S. A new public-key cryptosystem as secure as factoring[C]//Advances in Cryptology—EUROCRYPT'98: International Conference on the Theory and Application of Cryptographic Techniques Espoo, Finland, May 31–June 4, 1998 Proceedings 17. Springer Berlin Heidelberg, 1998: 308-318.
前言
之所以选择写这个加密方案，主要原因是它有一种很好用的同态性质，即摘要的第6点，次要原因是它用了一些挺“漂亮”的构造，次次要原因是我自己有可能会用到，所以做个笔记。
设\rm{E}(m, r)是在该方案中使用随机数r对明文m进行加密，密文落在\mathbb{Z}_n^*中，如果有两个明文m_0和m_1达到条件m_0 + m_1 < p（p是一个模数，可以参考下面的理论部分），上图摘要第6点的同态性质说的是（虽然论文里没说，但其实随机数部分也有同态）：
\rm{E}(m_0, r_0) \rm{E}(m_1, r_1) \equiv \rm{E}(m_0 + m_1, r_0 + r_1) \pmod n
从这个关系可以轻松推出摘要第7点的密文转换：
\rm{E}(m, r) \rm{E}(0, r') \equiv \rm{E}(m + 0, r + r') \equiv \rm{E}(m, r'') \pmod n
另外文章没说的是，这个方案还有一个“乘法同态”的属性（可以姑且称上面的同态是“加法同态”），设存在一个x \in \mathbb{Z}_p使得xm < p（如果不用正确解密甚至不需要这个条件），则：
\rm{E}(m, r)^x \equiv \rm{E}(xm, xr) \pmod n
知识清单
如果看到这里还没把你劝退的话，接下来的阅读可能需要：
- 群论知识，最好也知道环
- 看过RSA/ElGamal等加密方案，虽然只是方便作类比而已
- 英语论文阅读能力
- Sagemath/Python代码阅读、编写能力
理论部分
前置知识
这里需要先说明方案加解密时用到一些东西。首先是解密需要用到的一个p-西罗子群（[OU98]定义1），令p是奇素数，下面的\Gamma是\mathbb{Z}_{p^2}^*的p-西罗子群：
\Gamma = \{x \in \mathbb{Z}_{p^2}^* \ |\ x \equiv 1 \pmod p \}
实际上也可以看成下面的写法（虽然我没严格证明过但两个东西应该等同，而且文章中实际计算时也会用下面比较具象的表述）：
\Gamma = \{x^{p-1} \pmod {p^2} \ |\ x \in \mathbb{Z}_{p^2}^* \}
文章中直接由\mathbb{Z}_{p^2}^*的阶是p(p-1)（和x \equiv 1 \pmod p，根据拉格朗日定理？）就推出\Gamma的阶是p。
用上面的“具象表述”也可以给出比较严格的推理：设g是\mathbb{Z}_{p^2}^*的一个生成元（根据广义原根定理，\mathbb{Z}_{p^2}^*是循环群，所以一定有生成元）
\Gamma表述中的x表示的其实是\mathbb{Z}_{p^2}^*中的所有元素，那么借助生成元使用g^i也可以达到同样的效果，所以\Gamma可以被写作（其中\varphi(·)是欧拉函数，\varphi(p^2) = p(p-1)）：
\Gamma = \{(g^i)^{p-1} \pmod {p^2} \ |\ i \in \mathbb{Z}_{\varphi(p^2)} \}
根据欧拉定理，有
g^{(i + p) (p-1)} \equiv g^{i(p-1) + p(p-1)} \equiv g^{i(p-1)} g^{\varphi(p^2)} \equiv g^{i(p-1)} \pmod {p^2}
说明i和i+p生成的值是一样的，即只要i \ge p，生成的值就是多余的，只有落在\mathbb{Z}_p中的i有用，所以\Gamma可以被写作：
\Gamma = \{(g^i)^{p-1} \pmod {p^2} \ |\ i \in \mathbb{Z}_{p} \}
所以|\Gamma| = |\mathbb{Z}_p| = p，即\Gamma阶为p。
观察\Gamma的结构，只要x \in \Gamma，就有x - 1 \equiv 0 \pmod p，即x-1 = kp（k \in \mathbb{Z}_{p-1}），也就是x-1可以被p整除，于是就可以定义一个文章中称作\mathbb{F}_p \text{-valued}的函数L：
L(x) := \frac{x-1}{p}
之所以定义这个L是因为解密需要用到其同态属性（其中L(·)括号里是\mathbb{Z}_{p^2}上的运算，括号外是\mathbb{Z}_p上的运算）：
L(ab) \equiv L(a) + L(b) \pmod p
简要证明：首先
\begin{aligned}
L(ab) = &\frac{ab-1}{p} \\
= &\frac{(a-1)(b-1)+(a-1)+(b-1)}{p} \\
= &\frac{a-1}{p}(b-1) + \frac{a-1}{p} + \frac{b-1}{p} \\
= &L(a)(b-1) + L(a) + L(b)
\end{aligned}
最后，因为b \in \Gamma，所以b-1 \equiv 0 \pmod p，故
\begin{aligned}
L(ab) \equiv & L(a)(b-1) + L(a) + L(b) \\
\equiv & L(a) + L(b) \pmod p
\end{aligned}
得证。
最后说明一下怎么用L的同态属性解密：设x \in \Gamma，L(x) \not\equiv 0 \pmod p，设y \equiv x^m \pmod {p^2}模拟一个密文，m \in \mathbb{Z}_p，那么可以通过计算
m \equiv \frac{\sum_{i=1}^{m}L(x)}{L(x)} \equiv \frac{L(y)}{L(x)} \equiv \frac{y-1}{x-1} \pmod p
实现解密。
另外，文章中介绍了取样“x \in \Gamma”的方法，只要g是\mathbb{Z}_{p^2}^*的一个生成元（或者原文叫原根），就会有g^{p-1} \in \Gamma。
讲证明前先讲一个换模公式：若y \equiv x \pmod {ab}，则y \equiv x \pmod a且y \equiv x \pmod b。
简要证明：由y \equiv x \pmod {ab}可得，存在k \in \mathbb{Z}使得y = x + kab，所以
y \equiv x + kab \equiv x \pmod a
同理y \equiv x + kab \equiv x \pmod b。
而在上述取样中，由于g^{p-1} \in \mathbb{Z}_{p^2}（注意因为\Gamma是\mathbb{Z}_{p^2}的子群），所以需要证的是
(g^{p-1} \pmod {p^2}) \equiv 1 \pmod p
使用上面的换模公式后，即证
g^{p-1} \equiv 1 \pmod p
根据欧拉定理，显然成立。
加密方案
密钥生成：
- 取俩大素数p和q，其中p和q都是\kappa位的素数，即|p| = |q| = \kappa，另外还需要满足\rm{gcd}(p, q-1) = \rm{gcd}(q, p-1) = 1；
- 设n = p^2q；
- 采样\mathbb{Z}_{p^2}^*的一个生成元g，文章的做法是，先任意取g \in \mathbb{Z}_n^*，若g_p \equiv g^{p-1} \pmod {p^2}的阶为p则保留，否则重选g（大概意思是让g的阶是\varphi(p^2)）；
- 设h \equiv g^n \pmod n；
- 公钥设置为：(n, g, h, \kappa)，其实h不公开也行，文章说公开是为了效率；
- 私钥设置为： (p, q)。
加密：
- 明文空间为0 < m < 2^{\kappa - 1}，实际上m的取值是\mathbb{Z}_p，但是由于p不公开，而\{0, 1\}^{\kappa-1} \sube \mathbb{Z}_p，所以取\{0, 1\}^{\kappa-1}作明文空间，另外个人觉得m可以等于0；
- 取随机数r \in \mathbb{Z}_n，实际上r的取值是\mathbb{Z}_{\varphi(n)}，同样因为p、q不公开，而h^{r+\varphi(n)} \equiv h^r \pmod n，所以问题不大；
- 计算密文：C \equiv g^m h^r \pmod n。
解密：
收到密文C后，计算C_p \equiv C^{p-1} \pmod {p^2}；
计算明文：
C_p
\equiv g^{m(p-1)}h^{r(p-1)}
\equiv g^{m(p-1) + rn(p-1)}
\equiv g^{m(p-1) + rpq \varphi(p^2)}
\equiv g^{m(p-1)}
\equiv g_p^m
所以：
\frac{L(C_p)}{L(g_p)}
\equiv \frac{C_p - 1}{g_p - 1}
\equiv \frac{g_p^m - 1}{g_p - 1}
\equiv \frac{L(g_p^m)}{L(g_p)}
\equiv m \pmod p
最后回来看一下同态性质，设两个密文C_0 \equiv g^{m_0} h^{r_0} \pmod n和C_1 \equiv g^{m_1} h^{r_1} \pmod n，则有
C_0 C_1 \equiv g^{m_0} h^{r_0} g^{m_1} h^{r_1} \equiv g^{m_0 + m_1} h^{r_0 + r_1} \pmod n
即C_0 C_1就是使用随机数r_0 + r_1对m_0 + m_1加密的密文。
设C \equiv g^m h^r \pmod n，0 \le xm < p，则有
C^x \equiv (g^m h^r)^x \equiv g^{xm} h^{xr} \pmod n
即C^x就是使用随机数xr对xm加密的密文。
安全性证明
应该没人会看的，会看的还不如看论文（逃
实现代码
代码基本上是根据上面理论部分写的，只是为了一些微不足道的实用性加了一堆if和assert，如果懂Python/Sagemath应该不难看懂。
keyGen(self, kappa=1024)基本上按上面理论部分写，只是我只判断g_p \ne 1，因为g_p的阶只能是p或1，而阶为1时只可能是g_p = 1；L(self, x)只是简单地返回(x-1) // self.p，为了统一类型，所有函数的返回值我都设置成整数（Integer）类型，所以就没判断x是否属于\mathbb{Z}_{p^2}，最后返回也要包一层Integer(·)；encrypt(self, m)也是按理论部分写，中间加了个m的范围判断，实际上这步感觉应该由用户判定，因为限死m落在\mathbb{Z}_p会少了很多“骚操作”（decrypt(self, c)那里，在理论部分（和文章中）只是写了m \equiv \frac{L(C_p)}{L(g_p)} \pmod p，这个除法就很迷惑，实际上应该是一个\mathbb{Z}_p中的求逆（因为L(C_p)和L(g_p)都会小于p）；- 最后测试了一下，在密钥生成中最耗时的是密钥生成部分，加密解密几乎瞬间完成，估计是素数采样需要时间，应该可以换作使用伪素数解决
参考代码：
# Sage
class OU98:
def __init__(self, kappa=1024, g=None, n=None, p=None, q=None):
self.debug = False
self.kappa = kappa
if g==None and n==None and p==None and q==None:
self.p, self.q, self.n, self.g, self.h, self.gp = self.keyGen(self.kappa)
elif g!=None and n!=None:
self.p, self.q, self.n, self.g = p, q, n, g
self.h = pow(g, n, n)
else:
raise RuntimeError('give me at least g and n')
def test(self):
assert self.debug == True
print('p = %s' % self.p)
print('q = %s' % self.q)
print('g = %s' % self.g)
def keyGen(self, kappa=1024):
while True:
# gen p with kappa size
while True:
p = random_prime(2^kappa)
if len(p.bits()) == kappa:
break
# gen q with kappa size
while True:
q = random_prime(2^kappa)
if len(q.bits()) == kappa:
break
if gcd(p, q-1)==1 and gcd(q, p-1)==1:
break
# gen n, g, h
n = p*p*q
while True:
g = randrange(2, n)
gp = pow(g, p-1, p^2)
if gp != 1:
break
h = pow(g, n, n)
return Integer(p), Integer(q), Integer(n), Integer(g), Integer(h), Integer(gp)
def L(self, x):
if self.p==None:
raise RuntimeError('give me private keys!')
assert x % self.p == 1
assert x > 0 and x < self.p^2
return Integer((x-1) // self.p)
def encrypt(self, m):
if self.g==None or self.n==None:
raise RuntimeError('give me public keys!')
if type(m) != type(123):
raise TypeError
assert m >= 0
assert m < 2^(self.kappa-1)
r = randrange(1, self.n)
c = pow(self.g, m, self.n) * pow(self.h, r, self.n) % self.n
return Integer(c)
def decrypt(self, c):
if self.p==None:
raise RuntimeError('give me private keys!')
try:
self.gp
except:
self.gp = Integer(pow(self.g, self.p-1, self.p^2))
cp = Integer(pow(c, self.p-1, self.p^2))
m = self.L(cp) * self.L(self.gp).inverse_mod(self.p) % self.p
return m
if __name__ == '__main__':
# test correctness
# test time
import time
kappa = 512
for i in range(5):
t = time.time()
ou = OU98(kappa)
print('gen used: %s' % (time.time() - t))
#ou.test()
m = Integer(randrange(2, 2^(kappa-1)))
t = time.time()
c = ou.encrypt(m)
print('enc used: %s' % (time.time() - t))
t = time.time()
m2 = ou.decrypt(c)
print('dec used: %s' % (time.time() - t))
if m != m2:
break
print('--------------\n')
else:
print('passed!')
# test function
kappa = 256
ou1 = OU98(kappa,
231647749704830516191856775735058951582973748052376493876005550179680339768002386735844553860651472418830670763203401111501099820999265532225823653146633600539271633141439807033626938099143244499458112180922003084575670170749439549,
449965027732786705204448970702653854316346349301045875495834129686323103419549315275112897318530198300450662598129396177920876892924334677401170876443274521113887362004858500246223292731098144098170050605521176321065811898811575921
)
m = Integer(randrange(2, 2^(kappa-1)))
c = ou1.encrypt(m)
ou2 = OU98(kappa,
231647749704830516191856775735058951582973748052376493876005550179680339768002386735844553860651472418830670763203401111501099820999265532225823653146633600539271633141439807033626938099143244499458112180922003084575670170749439549,
449965027732786705204448970702653854316346349301045875495834129686323103419549315275112897318530198300450662598129396177920876892924334677401170876443274521113887362004858500246223292731098144098170050605521176321065811898811575921,
64870160335526547317489515685800845826224255169675627357037302268782157579143,
106927353523516648126355464793570089637028921500478312009962497218537911288129
)
print(m == ou2.decrypt(c))