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