后量子密码

crypto 评论

​

后量子密码学（Post-Quantum Cryptography，PQC），又称抗量子计算密码学，是密码学的一个研究领域，专门研究能够抵抗量子计算机的加密算法，特别是公钥加密（非对称加密）算法。不同于量子密码学，后量子密码学使用现有的电子计算机，不依靠量子力学，它依靠的是密码学家认为无法被量子计算机有效解决的计算难题。

在公钥加密方面，后量子密码学的研究方向包括了格密码学（Lattice-based Cryptography）、容错学习问题（LWE）、多变量密码学（英语：Multivariate Cryptography）、散列密码学（英语：Hash-based Cryptography）、编码密码学（Code-based Cryptography）与超奇异椭圆曲线同源密码学（Supersingular Isogeny Key Exchange）。密码学家认为，基于这些计算难题有望构建出不受量子计算机的威胁的公钥加密系统，替代现有的方案。

​

环LWE（RLWE）

环LWE问题是LWE问题在环上的版本，不同的是 $A$ 和 $s$ 的选取是在多项式环。

多项式环 $R_q = \mathbb{Z_q}[x]/f(x)$，表示每次计算后都要对多项式系数模 $q$，对多项式模 $f(x)$。它其中的每个元素都是一个多项式，每一次操作都相当于对多个元素进行操作，也就是能够一次加密多个比特的明文，对比LWE每次仅能对一个比特操作来说能够大大提高效率满足实际需要。

​

超奇异同源密钥交换（SIDH）

超奇异椭圆曲线同源密码学（Supersingular Elliptic Curve Isogeny Cryptography）是利用超奇异椭圆曲线（Supersingular Elliptic Curves）与超奇异同源图（Supersingular Isogeny Graphs）的数学性质的密码学，可以实现超奇异同源密钥交换（Supersingular Isogeny Key Exchange，SIKE）（协议为超奇异同源Diffie-Hellman密钥交换协议，SIDH），具有前向安全性。其使用方法和现有的Diffie-Hellman密钥交换相似，有望直接替代当前的常规椭圆曲线密钥交换（ECDH）。

Diffie-Hellman基本协议：

img

抽象Diffie-Hellman：

Alice的秘密是 $a$，她的计算先做→，得到 $g^a$，再做↓，得到 $g^{ab}$。而Bob的秘密是 $b$，他先做↓，再做→。殊途同归得到 $g^{ab}$。

img

SIDH构造的简化版本

SIDH的基本代数结构是超奇异椭圆曲线群 $E$ 和超奇异同源（Isogeny）$\phi$。基本思路如下图所示：

img

首先，超奇异椭圆曲线群 $E$ 理解为一个群。其次，构造用到的超奇异同源 $\phi : E \mapsto E’$ 是从群 $E$ 到群 $E’$ 的一种群同态。算法类似DH算法分为以下两个步骤：

  • 首先，Alice选取一个点 $R_A \in E$，$\langle R_A \rangle$ 确定了群 $E$ 的一个子群，然后可以计算得到一个从 $E$ 映射到其子群 $E_A$ 的同源 $\phi_A: E \mapsto E_A$，这是Alice的秘密信息。Alice发送公开信息 $E_A$ 给Bob。
  • 同样，Bob选择点 $R_B\in E$，然后计算得到 $\phi_B: E \mapsto E_B$，把公开信息 $E_B$ 发送给Alice。

最终Alice算出 $E/\langle R_B, R_A \rangle$，Bob算出 $E/\langle R_A, R_B \rangle$。上图中的 $E/\langle R_A \rangle$ 和 $E/\langle R_B \rangle$ 分别是 $E_A$ 和 $E_B$，这样表达是为了与之前的表达一致，其实这里并不是做商群，而是表达说 $\phi_A$ 的Kernel是 $\langle R_A \rangle$。目前的科技文献大多使用这种表达。

上面说到，$E_A$ 是曲线群 $E$ 的子群，它由同源 $\phi_A$ 决定，可理解为群同态 $\phi_A$ 映射到 $E$ 上的像 (Image)形成的子群。同理，$E_{BA}$ 是同源 $\phi_{BA}$ 映射到 $E$ 上的子群，而同源 $\phi_{BA}$ 是由 $\langle R_B, R_A \rangle$ 决定的，即同源 $\phi_{BA}$ 的Kernel是 $\langle R_B, R_A \rangle$。

SIDH构造的细化版本

img

为了满足Alice在没有Bob的秘密信息的情况下能计算出 $E_{BA}$ 的要求，SIDH需要使用更多的参数设计和相关计算。算法增加描述如下：

SIDH参数设计

首先，选择超奇异椭圆曲线 $E$ 作为公开参数。然后Alice随机选择两个元素 $P_A, Q_A \in E$，并公开作为自己的公共参数。同样，Bob也随机选择两个元素 $P_B, Q_B \in E$ 并公开。

Alice的操作
  • 随机选择两个整数 $s_A$ 和 $t_A$ 作为秘密信息，计算 $R_A = s_A P_A + t_A Q_A\in E$，并由 $R_A$ 计算得到一个从 $E$ 映射到其子群 $E_A$ 的同源 $\phi_A: E \mapsto E_A$，这也是Alice的秘密信息；
  • 获取Bob的公开信息，并计算 $\phi_A(P_B)$ 和 $\phi_A(Q_B)$，这些是公开信息；
  • Alice发送公开信息 $E_A$、$\phi_A(P_B)$ 和 $\phi_A(Q_B)$ 给Bob。
Bob的操作
  • 随机选择两个整数 $s_B$ 和 $t_B$ 作为秘密信息，计算 $R_B = s_B P_B + t_B Q_B\in E$，并由 $R_B$ 计算得到一个从 $E$ 映射到其子群 $E_B$ 的同源 $\phi_B: E \mapsto E_B$，这也是Bob的秘密信息；
  • 获取Alice的公开信息，并计算 $\phi_B(P_A)$ 和 $\phi_B(Q_A)$，这些是公开信息；
  • Bob发送公开信息 $E_B$、$\phi_B(P_A)$ 和 $\phi_B(Q_A)$ 给Alice。
秘密值的计算

Alice计算子群 $E_{BA}$ ，方法如下：

  • 注意，此时Alice掌握的信息是 $s_A$、$t_A$、$R_A$、$\phi_B(P_A)$ 和 $\phi_B(Q_A)$，她想计算得到 $\phi_B(R_A)$。并且要强调，$\phi_B$ 是一种群同态。
  • 利用群同态的属性可计算得到：$\phi_B(R_A) = \phi_B(s_A P_A + t_A Q_A) = s_A \phi_B(P_A) + t_A \phi_B(Q_A)$ 。
  • 根据 $\phi_B(R_A)$ 计算 $E_{BA}$。$E_{BA}$是曲线群 $E$ 的子群，是以 $\phi_B (R_A)$ 为Kernel的群同态映射到 $E$ 上的子群。这个群同态也就是Isogeny，这个Isogeny记为 $\phi_{BA}$ 。

类似的，Bob可以计算子群 $E_{AB}$：

  • $\phi_A(R_B) = s_B \phi_A(P_B) + t_B \phi_A(Q_B)$；
  • 由此可计算得 $E_{AB}$ ；

最后冲顶的一步，计算秘密值。首先要明确，很可能 $E_{BA} \ne E_{AB}$，但是，$E_{BA}$ 同构于 $E_{AB}$。利用同构曲线的一个属性：所有同构曲线的J-Invariant值相同。于是Alice和Bob分别计算这两条曲线的J-Invariant值 $J(E_{BA})$ 和 $J(E_{AB})$，这就是他们共同拥有的秘密。J-Invariant的计算定义可在标准教科书中找到，本文把它视为黑盒子使用。

Sage代码

参数设置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#选取一条在素域k上的超奇异椭圆曲线
lA, lB = 2, 3
eA, eB = 6, 7
p = lA ^ eA * lB ^ eB - 1
assert p.is_prime()
assert p % 4 == 3
k = GF(p) # 注意，这里并不是标准做法，只是因为Sage的局限不得已
E = EllipticCurve(k, [1, 0]) #选取曲线
E
E.is_supersingular() # 看看所生成的曲线是否超奇异.
print(E.j_invariant())

#选取四个随机点作为公共参数
points = []
while len(points) != 4:
    p = E.random_point()
    if p not in points:
        points.append(p)
PA, PB, QA, QB = points
PA, PB, QA, QB

Alice 的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#Alice选择两个随机数并计算自己的秘密值RA
#RA定义了phi_A的kernel
sA, tA = 123, 525
RA = sA * PA + tA * QA
print(RA)

#phiA就是同源也是群同态
phiA = E.isogeny(RA)

#Alice的公共信息EA
EA = phiA.codomain()
print(E.is_isogenous(EA)) # 确认EA与E同源

#Alice发送以下信息给Bob
EA, phiA_PB, phiA_QB = EA, phiA(PB), phiA(QB)
EA, phiA_PB, phiA_QB

Bob 的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#Bob的工作类似
sB, tB = 812, 580
RB = sB * PB + tB * QB
print(RB)

#phiB就是从E到EB同态映射,Kernel是RB
phiB = E.isogeny(RB)

#Bob的公共信息EB
EB = phiB.codomain()
print(E.is_isogenous(EB)) # 确认EB与E同源

# Bob发送以下信息给Alice
EB, phiB_PA, phiB_QA = EB, phiB(PA), phiB(QA)
EB, phiB_PA, phiB_QA

秘密值计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Alice计算秘密值
R_BA = sA * phiB_PA + tA * phiB_QA
print(R_BA)
phiBA = EB.isogeny(R_BA)
print(phiBA)
KA = phiBA.codomain().j_invariant()

# Bob计算秘密值
R_AB = sB * phiA_PB + tB * phiA_QB
print(R_AB)
phiAB = EA.isogeny(R_AB)
print(phiAB)
KB = phiAB.codomain().j_invariant()

#测试秘密值是否相等
if KA == KB:
    print("Success!")

Castryck-Decru攻击

（待补充）

参考：

Castryck-Decru-SageMath

An efficient key recovery attack on SIDH

Castryck-Decru Key Recovery Attack on SIDH