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

创建: 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，欧拉定理成立，进而模幂运算加解密成立:

ed=hφ(n)+1 m^φ(n)≡1(mod n) m^(hφ(n))≡1(mod n) m^(ed)=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算法只是欧拉定理很小的一次应用，拿这次应用中的条件来对模幂运 算加解密成立扯淡只会越扯越淡，一定要回到数学本身的理解上。