RSA算法加解密过程全解析
时间:2023-12-20 00:37:02
与传统的对称加密算法系统不同,非对称公私钥密码系统中的加密钥和解密钥是分开的。加密钥用于公开加密他人,只有持有解密钥的人才能解密信息。许多非对称密码算法诞生于1976年,但RSA这是最容易理解的。下面将尝试正确的RSA分析实现的具体流程。
寻找合适的加密、解密函数
我并不知道RSA最初的诞生经历了什么样的启发和灵光闪烁,但仍有办法切入RSA设计理念,现在,我们从它的实际效果:公钥加密,私钥解密,尝试一步一步地分析它,理解它。
我们面临的第一个问题是,如果我们想达到加解密钥匙分离的效果,我们该怎么办?
先尝试使用数学语言抽象化描述一下这个问题:
加密函数为 f 1 ( m , e ) f_1(m,e) f1(m,e),m为明文,e解密函数是加密密钥 f 2 ( x , d ) f_2(x,d) f2(x,d),x为密文,d为了解密钥,我们需要找到函数 f 1 f_1 f1和 f 2 f_2 f2,使得: m = f 2 ( f 1 ( m , e ) , d ) m=f_2(f_1(m, e),d) m=f2(f1(m,e),d)成立,经过函数 f 1 f_1 f1和 f 2 f_2 f2两次变换之后,我们需要能够把明文给还原回来。
为了解决上面的问题,我们需要对两个数学知识有一定的了解,第一个是欧拉定理,第二个则是模算术。
欧拉定理
若 a , m 均 为 正 整 数 , 且 g c d ( a , m ) = 1 , 则 a φ ( m ) ≡ 1 ( m o d m ) 若a,m均为正整数,且gcd(a,m)=1,则a^{\varphi(m)}\equiv 1 (\mod m) 若a,m均为正整数,且gcd(a,m)=1,则aφ(m)≡1(modm)
g c d ( a , m ) gcd(a,m) gcd(a,m)表示求数a和m的最大公因数,如果最大公因数为1,这两个数互质。
其中 φ ( m ) \varphi(m) φ(m)是一个重要的数论函数:欧拉函数。 φ ( m ) \varphi(m) φ(m)表示小于等于m的正整数中与m互质的数的数目。显然,若m为素数,则 φ ( m ) = m − 1 \varphi(m)=m-1 φ(m)=m−1。
基本的模算术
如果A和B满足 A m o d n = B m o d n A \mod n=B\mod n Amodn=Bmodn,我们称之为A与B有同余关系,同余关系常常又表示成: A ≡ B ( m o d n ) A\equiv B (\mod n) A≡B(modn)。同余关系是一种等价关系。
模的含义可以换算为普通乘式:
A m o d B = C → A = k B + C A\mod B=C \rightarrow A=kB+C AmodB=C→A=kB+C
基本的模加法和模乘法、模幂运算规则如下:
( A + B ) m o d C = ( A m o d C + B m o d C ) m o d C ( A ∗ B ) m o d C = ( ( A m o d C ) ∗ ( B m o d C ) ) m o d C ( A B ) m o d C = ( A m o d C ) B m o d C (A + B) \mod C = (A \mod C + B \mod C) \mod C \\ (A * B) \mod C = ((A \mod C) * (B \mod C)) \mod C \\ (A^B)\mod C = (A\mod C)^B \mod C \\ (A+B)modC=(AmodC+BmodC)modC(A∗B)modC=((AmodC)∗(BmodC))modC(AB)modC=(AmodC)BmodC
了解了模幂的规则,其实我们很快就能发现函数 f ( a , x ) = a x m o d m f(a,x)=a^x\mod m f(a,x)=axmodm很有趣,因为存在 f ( f ( a , e ) , d ) = f ( a , e d ) f(f(a,e),d)=f(a,ed) f(f(a,e),d)=f(a,ed),即 ( a e m o d m ) d m o d m = a e d m o d m (a^e \mod m)^d \mod m = a^{ed} \mod m (aemodm)dmodm=aedmodm成立,而 a e d m o d m a^{ed} \mod m aedmodm与 a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi(m)}\equiv 1 (\mod m) aφ(m)≡1(modm)之间的相似度又不禁令我们遐想联翩。实际上,欧拉定理再变通一下,我们就能得
到 a φ ( m ) + 1 m o d m = a a^{\varphi(m)+1}\mod m=a aφ(m)+1modm=a,**其中 a < m a
经过上面的简单思考,我们来解决一些随之而来的问题。
首先,我们为了得到 a φ ( m ) + 1 m o d m = a a^{\varphi(m)+1}\mod m=a aφ(m)+1modm=a,实际上弱化了欧拉定理,要求底数 a < m a
其次,欧拉定理还要求底数a和模m互质( g c d ( a , m ) = 1 gcd(a,m)=1 gcd(a,m)=1),这是一个比较严苛的要求。幸运的是,即使明文a与m不互质,我们也可以证明我们的加密、解密函数仍然有效,稍后将给出证明。
另外,在实现上仍有诸多疑问:一个数的幂的结果增长得特别快,计算 a e d a^{ed} aed是否很容易超出编程语言中整型变量的范围呢?如何根据 n n n确定 φ ( n ) \varphi(n) φ(n)?
快速模幂
我们先来解决计算 a e d m o d n a^{ed}\mod n aedmodn的问题。
例如,要求计算 2 256 m o d 7 2^{256}\mod 7 2256mod7。显然,先计算出 2 256 2^{256} 2256不是什么明智的选择。根据模算术的基本规则,我们可以得到:
2 256 m o d 7 = ( 2 128 m o d 7 ∗ 2 128 m o d 7 ) m o d 7 2^{256}\mod 7=(2^{128}\mod 7*2^{128}\mod7)\mod7 2256mod7=(2