锐单电子商城 , 一站式电子元器件采购平台!
  • 电话:400-990-0325

RSA算法加解密过程全解析

时间:2023-12-20 00:37:02 电位器rsa0k11v901s

与传统的对称加密算法系统不同,非对称公私钥密码系统中的加密钥和解密钥是分开的。加密钥用于公开加密他人,只有持有解密钥的人才能解密信息。许多非对称密码算法诞生于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)=m1

基本的模算术

如果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) AB(modn)。同余关系是一种等价关系。

模的含义可以换算为普通乘式:
A m o d    B = C → A = k B + C A\mod B=C \rightarrow A=kB+C AmodB=CA=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(AB)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 aa<m。**那么,要是 e d = φ ( m ) + 1 ed=\varphi(m)+1 ed=φ(m)+1的话,不就有 a e d m o d    m = a φ ( m ) + 1 m o d    m = a a^{ed} \mod m=a^{\varphi(m)+1}\mod m=a aedmodm=aφ(m)+1modm=a了吗?!那么,我们现在这样来描述我们的加解密函数 f 1 f_1 f1 f 2 f_2 f2,令 f 1 = f 2 = a x m o d    m f_1=f_2=a^x\mod m f1=f2=axmodm,其中a为明文,选择一个 m m m,计算 φ ( m ) \varphi(m) φ(m),公钥和私钥的策略是,然后选择一个 e e e并根据 e d = φ ( m ) + 1 ed=\varphi(m)+1 ed=φ(m)+1计算 d d d

经过上面的简单思考,我们来解决一些随之而来的问题。

首先,我们为了得到 a φ ( m ) + 1 m o d    m = a a^{\varphi(m)+1}\mod m=a aφ(m)+1modm=a,实际上弱化了欧拉定理,要求底数 a < m aa<m。不过这并不是什么大问题,底数a代表的明文如果实在太长,我们把它分割一下,让它小于m就行了。

其次,欧拉定理还要求底数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

相关文章