创建: 2016-04-08 13:24
更新: 2023-12-05 09:01
链接: https://scz.617.cn/misc/201604081324.txt
从初等数论角度看，为使模幂运算加解密成立，需要满足何种条件？数学专业的肯定不会在此问题上犯低级错误，计算机专业的，在此问题上或许会犯低级错误。
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算法只是欧拉定理很小的一次应用，拿这次应用中的条件来对模幂运算加解密成立扯淡只会越扯越淡，一定要回到数学本身的理解上。
[复制链接]
发表于 2023-12-5 09:32
