密码学:后量子密码学中的模数是多少?

公钥加密的旧篇章即将结束,新篇章即将开启。在20世纪70年代末完成的工作对我们很有帮助,但现在我们面临着量子计算机会打破这些方法的威胁。

只要是从事网络安全或安全软件开发的人,就都可能已经了解过公钥加密以及在20世纪70年代末和80年代前后创建的方法。现在我们可能需要学习更多的理论,因为我们所学的方法可能会受到量子计算机的威胁。

如果想开始学习这些新方法,那就有必要往下读了。

(mod p) 运算

在传统的公钥加密中,我们使用一个模数来创建有限域。虽然这听起来很复杂,但实际上这是一个非常简单的概念。对于有限域,我们引入一个模数,它通常是一个素数。对于素数,我们从整数除法中确定余数,然后取余数作为结果。例如,如果素数为17,我们将得到 0 到 16 范围内的输出值:

5 (mod 17) = 6 19 (mod 17) = 2 100 (mod 17) = 15

(mod p)运算的伟大之处在于,我们仍然可以进行加减乘除,并最终得到相同的结果,例如:

15 (mod 17) +100 (mod 17) = (15+100) (mod 17) = 13 15 (mod 17) 100 (mod 17) = (15100) (mod 17) = 4

在离散对数中,我们经常使用Diffie Hellman方法,我们选择一个共享素数 (p) 和一个共享生成器值 (g),并计算:

A = g^x (mod p) B = g^y (mod p)

交换A和B,共享密钥为:

K = A^y (mod p)

之所以有效,是因为:

K = A^y (mod p) = (g^x)^y (mod p) = g^{xy} (mod p)

在RSA方法中,我们使用模数(N)。对于加密,我们有:

C = M^e (mod N)

要破译:

M = C^d (mod N)

在这种情况下,N是两个素数的乘积,RSA 的优势在于分解模数 (N) 的难度。椭圆曲线方法也使用一个素数(p)的模数,其中我们有:

y² =x³ + ax + b (mod p)

这将我们在椭圆曲线上使用的点的值限制在 0 和 (p-1) 之间。

多项式

但是,量子计算机将破解RSA、椭圆曲线和离散对数,那么后量子密码学中的模数相当于什么?我们可以使用格加密,这涉及到我们使用多项式值来表示我们的位串。

如果我们有一个值19,它可以表示为10011和一个多项式值:

x⁴+x+1

67可以用1000011表示,并且是一个多项式:

x ⁶+ x +1

如果我们把这两个多项式相加,我们得到:

( x⁴ + x +1)+( x ⁶+ x +1)= x ⁶+ x ⁴+1+1

因为我们使用的是 Base 2,所以 1+1 等于 0,因此我们得到:

( x⁴ + x +1)+( x ⁶+ x +1)= x ⁶+ x

同样的道理也适用于添加相同的幂,例如:

x⁴ + x⁴ = 0 x⁴ + x⁴ + x⁴ = x⁴

以此类推。

在格密码中,我们用多项式进行加,减,乘,除。一个运算可能有一个x³+x+1的多项式,和一个x²+1的秘密多项式,然后将它们相乘得到一个结果。为了恢复原来的值,我们可以除以秘密多项式。

但是,我们如何将多项式的最大幂限制在有限域内呢?就像我们用传统的公钥方法那样,我们用一个模数,然后除以模数,保留余数。

有限域的模数

有限域或Galois域(GF)具有有限数量的元素,并且阶数等于素数 (GF(p)) 或素数的幂 (GF(2^ p ))。例如,GF(2^n)有2^n个元素,它的元素被称为二元多项式(其中多项式因子的系数要么为零,要么为一个值)。为了将多项式减少到给定的大小,我们使用一个模数多项式,它除以输出值。对于GF(128),我们可以使用x ⁷+ x +1 的模数。

让我们举个例子:

a = + x ²+1

b = x ⁶+ x ⁴+ x ³+1

当我们相加时,得到:

a + b = x ³+ x ²+1+ x ⁶+ x ⁴+ x ³+1= x ⁶+ x ⁴+ x ²

现在,我们把它们相乘:

a × b =( x ³+ x ²+1)×( x ⁶+ x ⁴+ x ³+1)= x⁹ + x ⁷ + x ⁶+ x ³+ x ⁸+ x ⁶+ x ⁵+ x ²+ x ⁶+ x ⁴+ x ³+1= x ⁹+ x ⁸+ x ⁷ + x ⁵+ x ⁴+ x²+1

我们现在用这个值除以模数。在此例中,对于 GF(128),模数是x⁷ + x +1:

1.jpg

对于GF(128), a×b的结果如下:

a × b = x ⁶+ x ⁵+ x ⁴+ x ³+ x ²

在Sage中:

2.jpg

示例运行:

3.jpg

如果我们现在使用 GF(256) :

4.jpg

示例运行:

5.jpg

我们可以看到,在Sage中GF(256)的默认模数为:

x ⁸+ x ⁴+ x ³+ x ²+1

我们可以在 Sage 中使用列出默认模值:

6.jpg

给出了:

7.jpg

不可约多项式

就像公钥加密中的素数一样,我们需要一个不能被任何数整除的多项式。为此,我们使用一个不可约多项式。不可约多项式的例子有:

8.jpg 我们的不可约多项式是x、x²、x²+x+1 和 x³+x²+1。它们等价于我们在传统公钥加密方法中使用的素数,并类似于(mod p)运算。一种常用的方法是 x⁸+x⁴+x³+x+1,用于AES加密。在Sage中,我们可以定义自己的模数,例如:

k.<x>= GF(2^8, modulus=x^8+x^4+x^3+x+1)<x>= GF(2^8, modulus=x^8+x^4+x^3+x+1)

如果我们有y = x ⁵+ x ³+ x ²+1 的输入值 101101,我们乘以h = x ⁴+ x +1,我们得到:

r = yh = (x⁵+x³+x²+1) × (x⁴+x+1)

然后我们可以创建以下Sage代码:


\# Rijndael finite field
k.<x>= GF(2^8, modulus=x^8+x^4+x^3+x+1)
y = (x^5+x^3+x^2+1)
h= (x^4+x+1)
r=y*h

print(f"(x^5+x^3+x^2+1) * (x^4+x+1)= {r} ({r.integer_representation()})")

当运行时,我们会得到的结果:


$ sage 1.sage

(x^5+x^3+x^2+1) * (x^4+x+1)= x^7 + x^4 + 1 (145)

现在可以除以我们的不可约多项式,得到原来的值:


\# Rijndael finite field
k.<x>= GF(2^8, modulus=x^8+x^4+x^3+x+1)
y = (x^5+x^3+x^2+1)
h= (x^4+x+1)
r=y*h
r2=r/h

print(f"{r}/ (x^4+x+1)= {r2} ({r2.integer_representation()})")

得到的结果:


$ sage 1.sage

x^7 + x^4 + 1/ (x^4+x+1)= x^5 + x^3 + x^2 + 1 (45)

我们可以看到乘法,除法,加减法,这些运算都是可逆的。

结论

公钥加密的旧篇章即将结束,新篇章即将开启。在20世纪70年代末完成的工作对我们很有帮助,但现在我们面临着量子计算机会打破这些方法的威胁。事实上,我们开发的方法从来都不是真正可证明的难题——它们只是在传统计算机中难以破解。所以,让我们来看看多项式,模和格的奇妙世界。

Source:https://medium.com/asecuritysite-when-bob-met-alice/so-whats-a-modulus-in-post-quantum-cryptography-b75292111d65

关于

ChinaDeFi - ChinaDeFi.com 是一个研究驱动的DeFi创新组织,同时我们也是区块链开发团队。每天从全球超过500个优质信息源的近900篇内容中,寻找思考更具深度、梳理更为系统的内容,以最快的速度同步到中国市场提供决策辅助材料。

本文首发于:https://mp.weixin.qq.com/s/KkFDJQVpT_Srb6mri7lj1A

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
ChinaDeFi 去中心化金融社区
ChinaDeFi 去中心化金融社区
ChinaDeFi.com 是一个研究驱动的DeFi创新组织,同时我们也是区块链开发团队。每天从全球超过500个优质信息源的近900篇内容中,寻找思考更具深度、梳理更为系统的内容,以最快的速度同步到中国市场提供决策辅助材料。