DAOrayaki ｜一种后量子认证的密钥协议方案

Quantum Computing

8 months ago • 23 min read

DAOrayaki ｜一种后量子认证的密钥协议方案

Quantum Computing

8 months ago • 23 min read • Loading Views

DAOrayaki DAO研究奖金池：

资助地址: DAOrayaki.eth

投票进展：DAO Reviewer 1/0 通过

赏金总量：50 USD

研究种类：Quantum Computing, ECDH, Protocol

原文作者: Melanee Group

创作者：Wonder@DAOrayaki.org

审核者：Hahaho@DAOrayaki.org

原文: A Post-Quantum Authenticated Key Agreement Scheme

摘要

众所周知，光子是量子计算机的基础。这些计算机与基于光纤的电信基础设施将构成一个合适的网络。有了强大的计算机和网络，现有的密码系统很快就会丧失其安全性。因此，我们必须设计一些新的加密算法来对抗量子计算机的攻击。在本文中，我们提出了一个全新的、适配后量子密码学的密钥交换方案。我们的协议是基于超奇异同源迪菲赫尔曼密钥交换（SIDH）的抗量子公钥密码系统。

关键词：量子计算机，光子，加密算法，超奇异同源迪菲赫尔曼密钥交换（SIDH）。

1、简介

我们目前常用的计算机使用的是普通的硅芯片，我们称之为经典计算机。科学家们正在研究建立高性能计算机。他们已经成功地发明了量子光子芯片，通过操纵芯片的硅光子来创造量子计算机。

光子是基本粒子的一种类型。新的光子思想起源于 20 世纪前 20 年，源自阿尔伯特·爱因斯坦的工作成果[1]。“光子计算”是利用激光器或光子处理器制造的光子来帮助进行计算。如上所述，为了建立量子计算机，科学家们利用光子的特性来创造强大的计算机。再进行测量之前，量子计算机根据物体状态的概率先行计算。

尽管有强大的处理能力，但 ECC 和 RSA 这样常规的公钥加密算法，已经不再有效；对量子计算机而言，这些加密算法也不够安全。因此，我们必须寻找能抵御量子计算机攻击、能够成功替代目前加密算法的方法。这和美国标准与技术研究所（NIST）提出的观点不谋而合[2]。

到目前为止，已经提出了许多方案，主要可以分为五类：基于点阵的算法，基于代码的算法，基于多变量方程的算法，基于散列的算法和超奇异同源密钥交换算法（SIKE）。

一种良好的后量子密码算法必须能够抵御经典计算机和量子计算机的攻击。根据我们已经掌握的信息，为了建立这种高效的算法，我们可以使用对称密码系统和公钥加密，例如密钥交换，迪菲赫尔曼密钥交换（DH）或椭圆曲线迪菲赫尔曼密钥交换（ECDH）等等。我们选择基于DH 的方案作为主要解决方案，其中一个原因是 DH 在生成短暂密钥方面比其他方案有优势：生成一个新的 DH 密钥对是非常快的。

在 NIST 提出的方案中，有一个和迪菲赫尔曼密钥交换相似的方案：即超奇异同源密钥交换算法（SIKE）。它是基于超奇异同源迪菲赫尔曼密钥交换（SIDH）建立的，使用基于超奇异同源（SI）的密码系统比其他后量子算法更容易。在所有后量子公钥密码系统中，SIKE 的密钥大小是最小的。如果想提供 124 位的安全密钥，SIKE 的公钥大小只有 564 字节[3]。

本文的结构如下。在第 2 章中，我们对普通 ECC 和 ECDH 算法进行了概述，并阐述了其在遭受量子计算机攻击时存在的弱点。在这一章的下半部分，我们将陈述超奇异同源密钥交换加密算法，这也是我们最初设计的基础概念。在第 3 章中，我们将阐述为什么我们的设计是一个后量子认证的密钥协议系统。在第 4 章中，我们将对所提出的方案进行软件分析，并将检查该方案是否具有良好的安全特性，以抵御量子和经典计算机的攻击，最后部分为结论。

2、初步准备

在这一章中，我们想介绍一下普通 ECC 和 SIDH 算法的概要，以便我们在设计中使用它们。

2.1 椭圆曲线密码学

这是基于椭圆曲线的协议，其基本假设是找到随机椭圆曲线元素相对于公知基点的离散对数是不可行的，这就是“椭圆曲线离散对数问题（ECDLP）”。椭圆曲线加密法（ECC）是作为RSA 加密法的替代品而开发的。1985 年，Neal Koblitz 和 Victor Miller 首次提出使用椭圆曲线建立新型密码系统的想法。在公钥方案之间，椭圆曲线密码系统具有高水平的安全性。另一方面，在同等安全水平下，椭圆曲线加密的密钥大小比其他公钥加密方法更小。实际上，在一段关系中，椭圆曲线加密算法需要更小的数值来生成参与的两方之间的共同密钥。椭圆曲线的计算构建在有限的字段上，可以选择素数字段或二进制字段。点加法是 ECC 的基本算术，也是纯量乘法的基本运算，Q=kP，其中 k∈Z，点 Q,P∈E(Fq)，Fq 是一个素数有限域。

椭圆曲线是一个以下形式的三次方程：E:y2 + a1xy + a2y = x3 + a3x2 + a4x + a5。其中，a1、a2、a3、a4 和 a5 是实数。奇异椭圆曲线的形式可以是 Ep(m, n): y2 = x3 + ax + b (mod p)，在一个素数有限域 Fp 上，其中 a, b∈Fp, p > 3, 且 4a3+ 27b2≠0 (mod p)。我们可以看到图1 中的奇异椭圆曲线。

椭圆曲线密码学的安全性取决于攻击者无法根据他所掌握的乘法器计算出所需的点。椭圆曲线的大小决定了该问题的难度。

一些基于离散对数的协议已经被改编为椭圆曲线，但我们在这里展示了两个重要问题。

问题 1：假设 E 是在一个有限域 Fq 上定义的椭圆曲线。P 和 Q 是 E(Fq) 上的有理点，假设 P 的素数 n 阶， Q=dP，其中 d 是区间 [1，n-1] 中的一个整数。在已知有限域和 Q 的情况下求出 d 的问题就是椭圆曲线离散对数问题（ECDLP）。

问题 2：椭圆曲线离散对数问题（ECDHP）是：给定一个在某一有限域定义的椭圆曲线 E，点 P∈E(Fq) 的 n 阶，以及点 A=aP，B=bP∈

，找出点 C=abP[4]。

2.2 DH 和 ECDH

在这一节中，我们简要介绍迪菲赫尔曼密钥交换算法（DH）和椭圆曲线迪菲赫尔曼密钥交换算法（ECDH）。

2.2.1. 迪菲赫尔曼

密钥交换算法（DH）问题

迪菲赫尔曼密钥交换算法问题（DHP）是由 Whitfield Diffie 和 Martin Hellman 在密码学领域首次提出的数学问题。

已知 x∈(Z/pZ)× 的情况下，函数 x→rx 容易计算，但难以反推。这里的指数 x 是加密的；基数 r（(ra,rb) →rab）和模数 p 是公开的。函数 x →rx 的逆函数是离散对数 y →logry [5]。

2.2.2 椭圆曲线迪菲赫尔曼

密钥交换算法（ECDH）

椭圆曲线迪菲赫尔曼密钥交换算法（ECDH）是一个密钥交换协议，它允许两个部分通过一个不确定的通道建立一个共享的密钥。这个在两方之间共享的值可以用两种方式使用：直接和间接。从这个密钥开始，可以在下一步使用对称加密（如 AES）来加密所需的信息。它是使用椭圆曲线加密法的迪菲赫尔曼密钥交换协议的一个变体[6]。

其中一方（A）选择一个随机的 ra∈[1,p] 并将 raP=P +---+P 发送给另一方（B）。B 选择一个随机的 rb∈[1,p] 并发送 rbP 给 A。A 认证 rbP 并计算出 ra.rb.P，然后 B 计算 rb.ra.P。

E/Fp 和点 P∈E（Fp）是公开的。ECDH 被用于互联网的重要部分。它最重要的用途之一是在传输层安全性协议（TLS）中。

2.3 基于 ECC 的协议的优缺点

下面我们将展示在实际中使用基于 ECC 的协议的优点和缺点，并说明了为什么我们必须设计一个新的框架。

2.3.1 优点

一提到 ECC 和 ECDH 的最主要优势，便是如果想实现同等的安全水平，ECC 和 ECDH 的密钥位数会更短。普通 ECC 密钥位数为 256 比特，而 RSA 密钥的大小为 3072 比特。我们在表 1 中说明了 ECC 与 RSA 相比的优势。相较于 RSA，ECC 的第二个优势仍然是密钥大小。可以说，由于 ECC 的密钥较小，相比其他公钥加密方法，它存储密钥需要的内存更少。另一方面，它的处理速度也比 RSA 要快。

2.3.2 缺点

前几节我们提到了高处理能力，量子计算机可以轻松解决经典计算机无法解决的数学问题。但是，这个概念面临着许多数学上的难题，这些难题也是目前现有的几种公钥加密算法的基础。换句话说，普通的 ECC 和 ECDH 将很容易被量子计算机破解，这将对目前的通信和网络安全产生重要影响。

由于量子计算机的存在，旁路攻击很容易破解 ECC 普通协议。因此，我们必须把我们的设计改为现代设计[7]。

超奇异同源迪菲赫尔曼 (SIDH) 密钥交换提供了一种后量子密码学的安全算法，是基于椭圆曲线密码学形成的，通过使用同源物来实现迪菲赫尔曼密钥交换的算法。SIKE 吸取了 ECC 的优势和新功能来改进公钥密码学方案。在下一章，我们将展示设计后量子验证的密钥协议所需的基本概念。

2.4 超奇异同源迪菲赫尔曼 (SIDH)

如上所述，鉴于量子计算机的处理能力，它可以轻易地破坏现有公钥加密算法的安全性，并曝光其基本信息，而这些信息必须保密。由于这些原因，我们描述了用于密钥协议的超奇异同源迪菲赫尔曼。

超奇异同源迪菲赫尔曼（SIDH）是由 De Feo、Jao 和 Plut [8]于 2011 年提出，它采用了传统的椭圆曲线密码学。SIDH 提供了完美的前向保密性，前向保密性提高了加密通信的长期安全性。

我们感兴趣的是在一个特定域上的超奇异曲线集（直至同构）和以下列形式定义的公钥。PK = (E,P,Q), SIDH 的公钥由一个秘密同源的密码域和该同源下某些公共点的图像点组成，E/Fp2 : y2 = x3 + ax + b 是一条超奇异椭圆曲线，p = 2eA，3eB±1 是一个大素数，E 的心数是 #E(Fp2)=(p∓1)2，j(E)=1728 *(4a3/ ( 4a3 +27b2) ∈k，且超奇异J-不变量：#SP2=|P/12| 。

具有相同 J-不变量的椭圆曲线在 k 的扩展有限元上是同构的，并且具有同构的自同态环 End(E)。因此，区分正常或超奇异的 J-不变量是有意义的。

态射 ϕ：E1→E2 是一个由特定函数定义的轨迹，它将 E1 的区分点发送到 E2 的区分点。对于对手方来说，在基于同源的协议中找到 ϕ 是一个难点。非零映射的形态被称为同源性。同源关系的内核是 R=ker(j)=，其中 Pi 和 Qi 是公钥，Si 是各方的密钥[9]。

我们想在图上显示同源性的轨迹。因此，我们必须首先得到同源核[le-i-1]Ri，需要执行以下步骤。

a. 计算同源性 ji =Ei / 。

b. 计算 Ei+1=ϕi（Ei）。

c. 将点推到新的曲线 Ri+1 = ϕi (Ri)。我们在图3中展示了同源性的走势。

下面，我们根据所述内容来演示 SIDH 协议。Alice 首先选择一个随机数 nA∈Z/lA eA Z，并根据下式获得映射函数。同时 Alice 获得 jA 下的 P 点和 Q 点的图像（j（PB），j（QB））。

ϕA: E0 →EA = E/，其中 PA 和 QA 是公共 A 的参数。

Bob 选择一个随机数 nB∈Z/lB eB Z，得到映射函数 Ψ=jB: E0 →EB = E/，Bob 得到 jB 下 P点和 Q点的图像（Ψ（PA），Ψ（QA））。

Alice 将 {A, Ψ (PB), Ψ (QB ), EA }发送给Bob，Bob 也将信息 {B, Ψ (PA), Ψ (QA), EB} 发送出去。

在收到上述信息后，各方计算 j(EAB) 以找到共同的密钥。图 4 是 SIDH 的总结(10)。

Alice：j(EBA)= EB / Ψ (PA) +[ nA] Ψ (QA)以及

Bob: j(EAB)= EA / Ψ (PB) +[ nB] Ψ (QB)

K :=j-inv(EAB)=j-inv(EBA)

在下面的表格中，我们描述了私有价值并显示了 DH、ECDH 和 SIDH 的计算难点。

在最初的 SIDH 中，我们面临着现有 API 应用的挑战，用现有的信息技术来实现成本比较昂贵（11）。由于网络实施的延迟，使用 MAC 是最合适的方式之一，可以用较低的成本更好地实现效果。因此，我们将提出一个具有合适功能的新方案。

3、提出拟定协议

前面几章介绍了一些概念，并基于次设计出了一个抗量子计算机攻击的密钥协议。此外，我们的方案不存在现有基础设施实施成本高的问题。我们还认为，我们的方案具有密钥协议协议应该具有的重要安全特征。在表 3 中，我们描述了在我们的认证协议中使用的符号。

Alice 和 Bob 已经共享了一个安全数——PW，其中包含他们的一些秘密信息。Alice 选择一个随机数 nA∈Z/lA eA Z 并计算 jA，参数内核（ker(jA)=(PA+[nA]QA)）和 EA=E0 / ker(jA)。Alice 也得到了 Bob 这个点的图像（（jA（PB），jA（QB））。然后，Alice 将计算密钥，K0= H (PW + A + B)，并准备将消息 {EA, ϕA (PB), ϕA (QB), A, B, MACK0 (EA, ϕA (PB), ϕA (QB), A, B) }发送给 Bob。

同时，Bob 选择一个随机数 nB∈Z/lB eB Z，并计算参数 jB、参数内核（ker(jB)=(PB+[nB]QB)）和 EB=E0 / ker(jB)。Bob 也得到了 Alice 这个点的图像（jB（PA），jB（QA））。收到信息后，Bob 首先形成 K0，然后通过检查 MACK0 来检查信息的完整性。如果条件正确，Alice 将被认证给 Bob，Bob 准备 PKB={EB, ϕB (PA), ϕB (QA)}。

接下来，Bob 准备 EAB= EA / ϕA (PB) + [nB] ϕA (QB)，并计算出密钥，K1= H (j (EAB) + PW + A+ B) 。最后 Bob 准备好消息{EB, ϕB (PA), ϕB (QA), B, MACK1 (EB, ϕB (PA), ϕB (QA), B)}，发送给 Alice。

收到信息后，Alice 准备 EBA= EB / ϕB (PA) + [nA]jB (QA)，并计算 K1'= H(j(EBA) + PW + A + B) 和 MACK1'。然后 Bob检查MACK1'=MACK1。如果条件如何，Bob 将被认证给 Alice。

最后 Alice 和 Bob 可以形成如下的共享密钥：

SK= H（H（j（EAB）+PKA+PKB+A+B））。你可以在图5中看到协议方案的摘要。需要注意的是，PW 的值在每次运行时都会更新。

4、分析

在本章中，我们首先展示了提出方案的安全特性，然后介绍了软件分析的结果。

4.1 安全特性

a. 相互认证

在这个协议中发生相互认证，所有双方都将被认证。Alice 通过检查 K1 和 MACK1 来认证 Bob。因为 PW 中包含他们的秘密参数。另一方面，Bob 可以通过检查 K0 和 MACK0 来认证Alice。

b. 匿名性

在拟定的协议中，我们有完全的匿名性。由于使用单向散列函数，所有各方都是不可识别的。

c. 前向/后向保密性

该方案具有前向/后向保密性。整个过程将包含会话密钥的前向和后向安全性，如果得到一个会话密钥，并不影响前一个和后一个密钥的安全性。拟定协议的认证方案具有前向保密性，因为我们的协议使用随机数和 PW，它们将在每一轮中被更新，我们在会话密钥中使用单向散列函数，我们没有直接发送会话密钥。

d. 已知会话密钥攻击

在我们的认证方案中，会话是基于 SIDH 的，并且这个会话的密钥是一个短密钥，所以已知会话密钥攻击不会对这个协议起作用。

e. 抵御中间人攻击

这种攻击无法实现，因为所提出的方案是所有参与成员之间的相互认证。

f. 旁路攻击

攻击者可以通过窃听和监测各方之间的信息交流和监测实施的功耗来获取重要信息，所获得的信息可以用来恢复秘钥，这种类型的攻击被称为旁路攻击。旁路攻击可以通过不同的方式进行。例如，通过将天线放在网络的传感器附近，可以实现上述攻击。

旁路攻击可以以各种方式发生在 ECC 上，其中之一便是重要信息的无意泄露。但是对于基于同源性的方案，也就是我们提出的方案，秘密的同源性不容易被计算出来。因为我们知道，根据对方的基础点只能计算出一个秘密的同源性。因此，基于 SIDH 的协议是可以抵抗旁路攻击的。

g. 不可否认性

各方的不可否认性是安全协议中应该考虑的问题之一。这意味着任何一方都不应该忽略信息的接收和发送。在拟定协议的方案中，由于使用了 MAC，所以各方可以确保对方是真实的。

4.2 软件分析

人类很难对安全协议进行分析，因为人类的思维无法考虑所有的攻击情况。为了做到这一点，我们通常会寻找一些软件，使我们的工作变得简单。SKYTHER 就是这些软件中的一个。与其他软件相比，SKYTHE 的优势在于它不需要为应用程序定义一个场景，而 SKYTHER 考虑了对协议的所有不同的攻击模式（12）。模拟结果显示在表 4 中，该软件的一些安全特性如下。

Alive：一种认证类型，其方式是创建一个通信伙伴，它将证明另一方是处于激活状态的。这就证明了双向认证的存在。

Niagree：一种认证类型，用于证明信息的发送方和接收方对交换的数值达成一致，并且没有信息被攻击者收到。

WeakAgree：这个特征意味着有一个强认证，即接收方确认从发送方收到的所有信息都是有效的。

Nisynch: 这个特征表示各方确信这个信息只由被认证的人发送。

Secret x：这个特征意味着这个协议的参数没有被攻击者操纵过。

我们还在表 5 中总结了 SIDH 和 ECC 密码学的特征。

5. 总结

在这篇文章中，我们首先总结了量子计算机和光子的构造。然后，我们证明了在量子计算机的攻击下，现有的公钥密码算法是如何轻易地丧失其安全性的。

接下来，我们介绍了基于同源的密钥协议，并提出了一个具有良好安全特性的基于同源的密钥协议。

如果你觉得这篇文章有帮助，请关注我们的 Medium 账户，并与你的朋友分享这个页面，以提高我们文章的 SEO。

参考文献：

[1] Joos, George. “Theoretical Physics”. London and Glasgow: Blackie and Son Limited. p. 679, 1951.

[2] The National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization, 2017–2018. “https://csrc.nist.gov/projects/post-quantum-cryptography/ post-quantum-cryptography-standardization”.

[3] D. Jao, R. Azarderakhsh, M. Campagna, C. Costello, L. De Feo, B. Hess, A. Jalali, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, J. Renes, V. Soukharev, and D. Urbanik. “Supersingular Isogeny Key Encapsulation”. Submission to Post-Quantum Cryptography Standardization Process, 2017.

[4] R. A. Goutham, G.-J. Lee , K.-Y. Yoo “An anonymous id-based remote mutual authentication with key agreement protocol on ecc using smart cards,” in Proceedings of the 30th Annual ACM Symposium on Applied Computing. ACM, P.169–174, 2015.

[5] B. den Boer, “Diffie–Hellman is as strong as discrete log for certain primes in Advances in Cryptology” — CRYPTO 88, Lecture Notes in Computer Science 403, Springer, p. 530, 1988.

[6] NIST, Special Publication 800–56A, “Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography”, March, 2006.

[7] Yan Bo Ti. “Fault Attack on Super-singular Isogeny Cryptosystems”. In Tanja Lange and Tsuyoshi Takagi, editors, Post-Quantum Cryptography, pages 107–122, Cham, 2017. Springer International Publishing.

[8] De Feo, Luca; Jao, Plut. “Towards quantum-resistant cryptosystems from super-singular elliptic curve isogenies” (PDF). PQCrypto 2011. Springer. Retrieved 4 May 2014.

[9] Doliskani ,Javad, Geovandro C. C. F. Pereira, and Paulo S. L. M. Barreto. “Faster Cryptographic Hash Function From Supersingular Isogeny Graphs”. Cryptology e Print Archive , Report 2017/1202. https://eprint.iacr.org/2017/1202.

[10] Costello, Craig, P. Longa, and M. Naehrig. “Efficient Algorithms for Supersingular Isogeny Diffie-Hellman.” In: Advances in Cryptology– CRYPTO2016:36th Annual International Cryptology Conference, 2016.

[11] V. Soukharev, B. Hess “ PQDH: A Quantum-Safe Replacement for Diﬃe-Hellman based on SIDH “, ia.cr/2019/730.

[12] J.C.M. Baeten, “Scyther — Semantics and Veriﬁcation of Security Protocols”, ISBN 90–386–0804–7. — ISBN 978–90–386–0804–4 NUR 993, 2006.

通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容，瓜分10000USDC赏金池！欢迎加入DAOrayaki社区，了解去中心化自治组织（DAO），探讨最新话题！

官方网站：https://daorayaki.org

Media：https://media.daorayaki.org

Discord server: https://discord.gg/wNUPmsGsa4

Medium: https://medium.com/@daorayaki

Email: daorayaki@dorafactory.org

Twitter: @daorayaki_

微信助手：DAOrayaki-Media

小宇宙：DAOrayaki