阅读： 11

从初等数论角度看，为使模幂运算加解密成立，需要满足何种条件？数学专业的肯定不会在此问题上犯低级错误，计算机专业的，在此问题上或许会犯低级错误。

m^e≡c(mod n)
c^d≡m(mod n)
m^(e*d)≡m(mod n)

此处只考虑正整数，其成立条件是:

gcd(e,φ(n))=1
e*d≡1(mod φ(n))
m<n

成立条件并未要求n是半素数(有且只有两个不同的素因子)，亦未限制e是素数。

对于正整数n，在[1,n]中，有多少个整数与n互素？计算该值的方法叫做欧拉函数，以φ(n)或phi(n)表示。

欧拉定理:

若a、n都是正整数，且gcd(a,n)=1，则:

a^φ(n)≡1(mod n)
a^(φ(n)+1)≡a(mod n)

上述运算成立条件并未要求n为合数。

欧拉定理可进一步推广成Carmichael定理。设正整数n的素因子分解为:

n=(p1^k1)*(p2^k2)*…(pr^kr)

对于所有a属于Zn*(即[1,n-1])，有:

λ(n)=lcm(φ(p1^k1),φ(p2^k2),…,φ(pr^kr))
a^λ(n)≡1(mod n)
λ(n)|φ(n)

设n的素因子分解为:

n=p*q

有:

λ(n)=lcm(p-1,q-1)

RSA算法只是欧拉定理(也可以说是Carmichael定理)很小的一次应用。在RSA算法场景中，出于安全考虑，确实要求n是两个大素数的积，但这个要求不是欧拉定理本身的要求，不是模幂运算加解密成立的约束条件。

当n是单素数时，存在符合欧拉定理的情形。考虑任意m<n的正整数，m均与n互素，满足gcd(m,n)=1，欧拉定理成立，进而模幂运算加解密成立:

e*d=h*φ(n)+1
m^φ(n)≡1(mod n)
m^(h*φ(n))≡1(mod n)
m^(e*d)=m^(h*φ(n)+1)=m^(h*φ(n))*m≡m(mod n)

设n为单素数，检验如下运算:

n=29
φ(n)=n-1=28
e=3
d=pow(e,-1,28)=19
m=16
c=pow(m,e,n)=7
pow(c,d,n)=16

上例完全符合欧拉定理，有n、e、d，能完成m、c之间的转换，与p、q是否存在无关。这种看上去很安全，其实跟没加密一样，因为φ(n)=n-1，进而轻松求d。不过单素数很容易被素性检测发现，不够隐蔽。

版权声明
本站“技术博客”所有内容的版权持有者为绿盟科技集团股份有限公司（“绿盟科技”）。作为分享技术资讯的平台，绿盟科技期待与广大用户互动交流，并欢迎在标明出处（绿盟科技-技术博客）及网址的情形下，全文转发。
上述情形之外的任何使用形式，均需提前向绿盟科技（010-68438880-5462）申请版权授权。如擅自使用，绿盟科技保留追责权利。同时，如因擅自使用博客内容引发法律纠纷，由使用者自行承担全部法律责任，与绿盟科技无关。