Okamoto-Uchiyama加密方案学习笔记

参考·

[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))
    cp = Integer(pow(c, self.p-1, self.p^2) % 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))

同态性质应用·

（2023.04.04更新）

理论上同态只要跟着文章开始时的几条式子操作就好了，即明文的加法是密文的乘法、明文的数乘是密文取对应常数的幂，不过在应用上需要注意的是，进行若干次同态操作后需要保证明文依然落在$\mathbb{Z}_p$中（或$\{0, 1\}^\kappa$中），否则不能解密，下面给一个应用上的例子。

假设在服务器端有一个度（Degree）为$d$的多项式

$$f(x) = a_0 x^0 + a_1 x^1 + ... + a_d x^d$$

服务端想要在保证自己的多项式系数（$a_0, a_1, ..., a_d$）不被暴露给用户端计算$f(x)$；而用户也不想服务端知道自己的输入$x$是什么。那么可以设计以下协议：

$$\begin{array}{|l|} \hline \begin{array}{lcl} \\ \mathrm{User}(x) & \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{Server}(a_0, a_1, ..., a_d) \\ \begin{array}{l} \\ \text{pk} = (g, n), \text{sk} = (p, q) \leftarrow \text{KeyGen}(1^\kappa) \\ c_x = (\text{Enc}_\text{pk}(x^0), \text{Enc}_\text{pk}(x^1), ..., \text{Enc}_\text{pk}(x^d)) \\ \end{array} & & \\ & \overset{_\text{pk}, c_x}{\longrightarrow} & \\ & &\begin{array}{l} c_{f(x)} \equiv \prod_{i=0}^{d} c_{x, i} ^ {a_i} \pmod n \\ \end{array} \\ & \overset{c_{f(x)}}{\longleftarrow} & \\ \begin{array}{l} f(x) = \text{Dec}_\text{sk}(c_{f(x)}) \\ \end{array} & & \\ \end{array} \\ \hline \end{array}$$

即用户先对自己的每一项$x^i$进行加密，然后发送给服务端，服务端通过同态操作实现线性运算，得出$f(x)$的密文$c_{f(x)}$（服务端没有私钥不能解密），然后把$c_{f(x)}$发送回用户，用户解密后便可得到$f(x)$（直观上用户不能通过$c_{f(x)}$获取客户端的系数）。

上面说过，需要保证明文依然落在$\mathbb{Z}_p$中，所以需要稍微计算一下参数的取值，为了简化，假设参数和未知数都是$\lambda$比特的数（$x, a_0, a_1, ..., a_d \in \{0, 1\}^\lambda$），那么只要设置

$$\lambda (d + 1) + 1 \le \kappa$$

即可，推导过程有点像二进制编码，$a_d x^d$项最大$\lambda (d + 1)$，前面的项加起来不会大于$a_d x^d$，所以$f(x)$不会大于$a_d x^d$的两倍。（大概意思，逃

当然以上只是一个小玩具，实际应用时还要考虑很多东西，比如这个多项式只能进行有限次（没记错是最多$d$次）的运算，否则用户可以通过解线性方程的方法恢复系数；又比如在参数设计方面，要考虑攻击者能否进行类似对背包密码的格攻击，等。

另外，OU98的加密算法只能进行加法和数乘（Scalar）同态，而不能进行乘法同态，即对$\text{E}(a)$和$\text{E}(b)$操作后获得$\text{E}(ab)$，如果选用能够乘法同态的算法的话，上面协议估计能有更多骚操作，比如用户只用对$x$进行加密，又或者可以对多元多项式进行运算，等。

下面给一下上面玩具协议的参考代码，在运行前还要进行一些操作：

假设上面代码文件叫OU98.sage，理论上运行一次后会生成一个OU98.sage.py的文件，为了能在别的代码中通过import引用上面代码，需要稍微先改一下文件的名字：

cp ./OU98.sage.py ./OU98.py

还有上面代码中，需要把decrypt函数中对应行修改为（后来才找到的Bug，我也不知道这里Sagemath抽了什么风x）：

cp = Integer(pow(c, self.p-1, self.p^2) % self.p^2)

最后参考代码（有空再考虑把同态写个函数，逃）：

# Sage
# An example of computing a*x^2 + b*x + c
from OU98 import OU98
bits = 15
degree = 16
kappa, g, n, p, q = (256,
    231647749704830516191856775735058951582973748052376493876005550179680339768002386735844553860651472418830670763203401111501099820999265532225823653146633600539271633141439807033626938099143244499458112180922003084575670170749439549,
    449965027732786705204448970702653854316346349301045875495834129686323103419549315275112897318530198300450662598129396177920876892924334677401170876443274521113887362004858500246223292731098144098170050605521176321065811898811575921,
    64870160335526547317489515685800845826224255169675627357037302268782157579143,
    106927353523516648126355464793570089637028921500478312009962497218537911288129
  )
assert bits * (degree + 1) + 1 <= kappa   # ensure fx < 2^kappa


def User():
  global kappa, g, n, p, q  # Omit KeyGen and GetKey...
  ou = OU98(kappa, g, n, p, q)
  x = Integer(randint(0, 2^bits-1))

  cx = [ou.encrypt(x^i) for i in range(degree + 1)] # degree+1 terms (0 ~ ...), maybe cx0 can be omitted.
  return (kappa, g, n), cx, x


def Server(pk, cx):
  kappa, g, n = pk
  ou = OU98(kappa, g, n)
  coeff = [Integer(randint(0, 2^bits-1)) for i in range(degree + 1)] # Term degree: 0-2

  # By homomorphic:
  cfx = product([pow(cx[i], coeff[i], n) for i in range(degree + 1)]) % n
  return cfx, coeff


def Checker(cfx, coeff, x):
  global kappa, g, n, p, q
  ou = OU98(kappa, g, n, p, q)

  fx = ou.decrypt(cfx)
  print('[Debug] fx1 = %d' % fx)
  realFx = sum([coeff[i] * x^i for i in range(degree + 1)])
  print('[Debug] fx2 = %d' % realFx)
  return fx == realFx


def Transcriber():
  pk, cx, x = User()
  cfx, coeff = Server(pk, cx)
  result = Checker(cfx, coeff, x)
  return result
  

if __name__ == '__main__':
  for i in range(5):
    print('--------------\n')
    print(Transcriber())