原文链接：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))