标题: 初等数论中模幂运算加解密成立的条件

创建: 2016-04-08 13:24
更新: 2023-12-05 09:38
链接: https://scz.617.cn/misc/201604081324.txt
      https://www.52pojie.cn/thread-1865358-1-1.html

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

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

再进一步，满足gcd(e,φ(n))=1的e很多，未要求e是素数，检验如下运算:

n=29
φ(n)=n-1=28
e=9
d=pow(e,-1,28)=25
m=16
c=pow(m,e,n)=24
pow(c,d,n)=16=m

此时公钥(n,e)是(29,9)，私钥(n,d)是(29,25)，n是单素数，没有p、q的事，e是与
φ(n)互素的合数。

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

再说一遍，RSA算法只是欧拉定理很小的一次应用，拿这次应用中的条件来对模幂运
算加解密成立扯淡只会越扯越淡，一定要回到数学本身的理解上。