公钥加密的旧篇章即将结束,新篇章即将开启。在20世纪70年代末完成的工作对我们很有帮助,但现在我们面临着量子计算机会打破这些方法的威胁。
只要是从事网络安全或安全软件开发的人,就都可能已经了解过公钥加密以及在20世纪70年代末和80年代前后创建的方法。现在我们可能需要学习更多的理论,因为我们所学的方法可能会受到量子计算机的威胁。
如果想开始学习这些新方法,那就有必要往下读了。
在传统的公钥加密中,我们使用一个模数来创建有限域。虽然这听起来很复杂,但实际上这是一个非常简单的概念。对于有限域,我们引入一个模数,它通常是一个素数。对于素数,我们从整数除法中确定余数,然后取余数作为结果。例如,如果素数为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³ + 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:
对于GF(128), a×b的结果如下:
a × b = x ⁶+ x ⁵+ x ⁴+ x ³+ x ²
在Sage中:
示例运行:
如果我们现在使用 GF(256) :
示例运行:
我们可以看到,在Sage中GF(256)的默认模数为:
x ⁸+ x ⁴+ x ³+ x ²+1
我们可以在 Sage 中使用列出默认模值:
给出了:
就像公钥加密中的素数一样,我们需要一个不能被任何数整除的多项式。为此,我们使用一个不可约多项式。不可约多项式的例子有:
我们的不可约多项式是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年代末完成的工作对我们很有帮助,但现在我们面临着量子计算机会打破这些方法的威胁。事实上,我们开发的方法从来都不是真正可证明的难题——它们只是在传统计算机中难以破解。所以,让我们来看看多项式,模和格的奇妙世界。
关于
ChinaDeFi - ChinaDeFi.com 是一个研究驱动的DeFi创新组织,同时我们也是区块链开发团队。每天从全球超过500个优质信息源的近900篇内容中,寻找思考更具深度、梳理更为系统的内容,以最快的速度同步到中国市场提供决策辅助材料。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!