McEliece 被选为抗量子密钥封装标准

asecuritysite 发布于 2026-07-10 阅读 30

McEliece 加密方法（Classic McEliece）已被 ISO 选为抗量子密钥封装标准。

我们生活在一个由大型（且面目模糊）企业主导的世界，但往往是个体构建了我们的信息世界。其中一位就是罗伯特·J·麦克利斯（Robert J. McEliece），他于2019年5月去世，享年76岁。在从事一系列与太空相关的项目时，他在信息传输和存储等多个领域做出了贡献。罗伯特最终因其工作获得了克劳德·E·香农奖，并发表了多次令人难忘的演讲。他最著名的成就是围绕纠错码，包括Rollup码，而现在他的工作引起了极大关注，旨在创建一种能够抵御量子计算机的加密系统。

如今，他的方法——经典麦克利斯（Classic McEliece）算法——已被国际标准化组织（ISO）选为量子鲁棒密钥封装方法（KEM）的国际标准。该标准有五种主要模式：McEliece348864、McEliece460896 524、McEliece6688128、McEliece6960119 和 McEliece8192128。总体而言，安全性很强，公钥较大，私钥也相对较大，但密文尺寸较小：

类型            公钥大小（字节）  私钥大小（字节）  密文大小（字节）
McEliece348864      261,120        6,492              196  基于码
McEliece460896      524,160       13,608              156  基于码
McEliece6688128   1,044,992       13,932              208  基于码
McEliece6960119   1,047,319       13,948              194  基于码
McEliece8192128   1,357,824       14,120              208  基于码

因此，当我们需要强安全性但密文尺寸小时，经典麦克利斯非常有用。不幸的是，它在密钥生成方面较慢，但封装和解封装性能尚可接受：

以下是 WASM 实现 链接：

更多示例：

麦克利斯公钥加密方法（后量子鲁棒）

罗伯特·J·麦克利斯

对任何现代研究者来说，这是一个教训：1978年，罗伯特·麦克利斯仅用两页纸就概述了一种基于代数编码的公钥加密方法——现在被称为麦克利斯密码学方法 论文。这是一种非对称加密方法（具有公钥和私钥），在当时看来是陷门方法的有力竞争者。不幸的是，RSA 成为了王者，而麦克利斯方法被设计师们排到了队列末尾。

它基本沉寂了近40年。但随着量子计算机时代的来临，它正在被重新考虑，因为它被认为能够免疫使用肖尔算法的攻击 此处。

量子鲁棒方法的主要竞争者包括：

  • 基于格的密码学——此类方法显示出巨大潜力，并催生了新的密码学，例如全同态加密 此处 和代码混淆。下节给出示例。
  • 基于码的密码学——该方法于1978年与麦克利斯密码系统一同创建，但几乎未在真实应用中使用。麦克利斯方法使用纠错码中使用的线性码，涉及矩阵向量乘法。线性码的一个示例是汉明码 此处。
  • 多元多项式密码学——这类方法关注于求解有限域上多元多项式系统的困难性。不幸的是，许多已提出的方法已被攻破。
  • 基于哈希的签名——这涉及使用哈希方法创建数字签名。缺点是需要签名者跟踪所有已签名的消息，并且可生成的签名数量有限。

麦克利斯方法

麦克利斯方法使用基于码的密码学。其基础在于解码一般线性码的困难性，并且在加密和解密方面通常比 RSA 更快。其中，我们有一个概率密钥生成方法，用于生成公钥和私钥。密钥通过参数 $n$、$k$ 和 $T$ 生成。

密钥通过参数 $n$、$k$ 和 $t$ 生成。由此，我们创建一个 $[n,k]$ 的码矩阵，能够纠正 $t$ 个错误。在他的论文中，麦克利斯定义了 $n=1024$，$k=524$，$t=50$，这给出了 $524 \times (1024-524) = 262,000$ 位的公钥大小。在上面的例子中，我们使用 $k=1608$，$N=2048$ 和 $T=40$，这给出了 $1608 \times (2048-40) = 3,228,864$ 位的公钥大小。为了实现量子鲁棒性，推荐 $N=6960$，$k=5412$，$t=119$（给出 $8,373,911$ 位的大密钥大小）。

这里是加密演示 此处。

示例

本页面简单解释了如何为麦克利斯加密创建密钥。它使用一个 (7,4) 汉明码，具有一位纠错能力。以下是概要 此处：

import numpy
import sysg =numpy.array([[1,0,0,0,1,1,0],[0,1,0,0,1,0,1],[0,0,1,0,0,1,1 ],[0,0,0,1,1,1,1]])
s =numpy.array([[1,1,0,1],[1,0,0,1],[0,1,1,1],[1,1,0,0]])
p=numpy.array([[0,1,0,0,0,0,0],[0,0,0,1,0,0,0],[0,0,0,0,0,0,1],[1,0,0,0,0,0,0],[0,0,1,0,0,0,0],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0]])print 'G:\n',g
print 'S:\n',s
print 'P:\n',pmatrix = numpy.dot(s,g)%2
G_1 = numpy.dot(matrix,p)%2print 'Result:\n',G_1message = ([1,1,0,1])
e = ([0,0,0,0,1,0,0])res=numpy.dot(message,G_1)%2cipher = numpy.add(res,e)%2print '\nCipher:',cipherp_1=numpy.linalg.inv(p)%2print '\nP^{-1}:\n',p_1y_1 = numpy.dot(cipher,p_1)%2print "\ny\':",y_1

这基于示例 此处。我们用一个 (7,4) 汉明码（纠正一个错误）来说明该过程。生成矩阵为：

             1  0  0  0  1  1  0
         G = 0  1  0  0  1  0  1
             0  0  1  0  0  1  1
             0  0  0  1  1  1  1

Bob 选择一个扰码矩阵（S）：

              1  1  0  1
          S = 1  0  0  1
              0  1  1  1
              1  1  0  0

还有一个置换矩阵：

              0  1  0  0  0  0  0
              0  0  0  1  0  0  0
              0  0  0  0  0  0  1
         P =  1  0  0  0  0  0  0
              0  0  1  0  0  0  0
              0  0  0  0  0  1  0
              0  0  0  0  1  0  0

Bob 的公钥就变成了这些矩阵的点积：

                  1  1  1  1  0  0  0
     G' = SGP   = 1  1  0  0  1  0  0
                  1  0  0  1  1  0  1
                  0  1  0  1  1  1  0

Bob 将使用 $G'$ 作为公钥，但 $S$、$G$ 和 $P$ 是保密的。接下来，为了让 Alice 向 Bob 发送加密消息，她将消息转换为长度为 $k$ 的二进制向量。

对于长度为 $m$ 的消息，Alice 将随机创建一个重量为 $t$ 的二进制 $n$ 向量，并随机将 $t$ 个 1 放置在一个长度为 $n$ 的零向量中。

然后这被发送给 Bob：

$y = mG' + e$

Bob 随后用以下方式解密：$yP^{-1} = (mG' + e)P^{-1} = mSG + eP^{-1} = mSG + e'$

示例运行结果为：

Message:
 [1. 1. 0. 1.]
G:
 [[1 0 0 0 1 1 1]
 [0 1 0 0 0 1 1]
 [0 0 1 0 1 0 1]
 [0 0 0 1 1 1 0]]
S:
 [[1 1 0 1]
 [1 0 0 1]
 [0 1 1 1]
 [1 1 0 0]]
P:
 [[0 1 0 0 0 0 0]
 [0 0 0 1 0 0 0]
 [0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0]
 [0 0 1 0 0 0 0]
 [0 0 0 0 0 1 0]
 [0 0 0 0 1 0 0]]
Result (GSP):
 [[1 1 0 1 0 1 0]
 [1 1 0 0 1 0 0]
 [1 0 0 1 0 0 1]
 [0 1 1 1 0 0 0]]Cipher: [0. 1. 1. 0. 0. 1. 0.]P^{-1}:
 [[0. 0. 0. 1. 0. 0. 0.]
 [1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 1. 0. 0.]
 [0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1.]
 [0. 0. 0. 0. 0. 1. 0.]
 [0. 0. 1. 0. 0. 0. 0.]]syndrome': [1. 0. 1.] 5.0
Error position:  7
y':  [1. 0. 0. 0. 1. 1. 0.]
y' (corrected):  [1. 0. 0. 0. 1. 1. 1.]S^{-1}:
 [[1. 1. 0. 1.]
 [1. 1. 0. 0.]
 [0. 1. 1. 1.]
 [1. 0. 0. 1.]]Decipher: [1. 1. 0. 1.]

结论

我们需要在量子计算机时代思考定义困难问题的新方法。使用代数编码来创建量子鲁棒密码学，现在已成为替代某些公钥方法的严肃候选者。

罗伯特·麦克利斯无疑是一位天才，我们需要更多天才出现，重建我们充满缺陷的互联网。请观看这个视频，看看一位伟大的导师如何让事物变得生动：

因此，以下是密钥和密文大小：

类型            公钥大小（字节）  私钥大小（字节）  密文大小（字节）
------------------------------------------------------------------------
Kyber512              800              1,632                  768  学习误差（格）
Kyber738            1,184              2,400                1,088  学习误差（格）
Kyber1024           1,568              3,168                1,568  学习误差（格）
Bike128             1,541              3,114                1,573  基于码
Bike192             3,083              6,198                3,115  基于码
Bike256             5,122             10,276                5,154  基于码
HQC128              2,249              2,289                4,497  基于码
HQC192              4,522              4,562                9,042  基于码
HQC256              7,245              7,285               14,485  基于码
McEliece348864    261,120              6,492                  196  基于码
McEliece460896    524,160             13,608                  156  基于码
McEliece6688128 1,044,992             13,932                  208  基于码
McEliece6960119 1,047,319             13,948                  194  基于码
McEliece8192128 1,357,824             14,120                  208  基于码
  • 原文链接： medium.com/asecuritysite...
  • 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
微信扫码分享

相关文章

0 条评论

登录后发表评论