关于RSA迭代10次加密等价于原明文的证明及相关问题咨询

嘿，我来帮你一步步拆解这个问题，把每个疑惑都理清楚～

首先，先纠正一个可能的表述误解：你说“迭代x^{e十次”，正确的数学表达应该是**每次把前一次的加密结果再做x→x}e的运算**，也就是最终得到的是x^(49^10)，而不是(x^49)^10 = x^(49*10)——后者只是一次加密后取10次方，不是迭代。这也是你的提示能用上的关键！

一、为什么常规的de ≡1 mod φ(n)在这里不适用，但结果仍然成立？ #

常规RSA中，我们要求加密指数e和φ(n)互质，然后找解密指数d使得ed ≡1 mod φ(n)，这样x^(ed) ≡x modn。但这里的情况不是ed≡1 modφ(n)，而是我们的“总加密指数”是49^10，它满足的是49^10 ≡1 mod φ(p)和49^10≡1 mod φ(q)（其中p=383，q=563），而不是mod φ(n)。

这是因为：

• 对于质数p，根据费马小定理的扩展，x^t ≡x modp对所有整数x成立的充要条件是t≡1 mod(p-1)（当x≠0时，x^(t-1)≡1 modp，而乘法群阶为p-1，所以t-1必须是p-1的倍数；x=0时显然成立）。
• 我们不需要t≡1 modφ(n)，只要分别满足t≡1 modφ(p)和t≡1 modφ(q)，再通过中国剩余定理就能推出t≡x modn。

二、如何证明E(x)=x（即x^(49^10)≡x mod215629）？ #

我们用中国剩余定理，分别对p=383和q=563验证，再合并结果：

1. 验证x^(49^10)≡x mod383

• 383是质数，φ(383)=382=2*191
• 已知7^20≡1 mod191，而49=7²，所以49^10=(7²)^10=7^20≡1 mod191
• 同时，49是奇数，49^10也是奇数，即49^10≡1 mod2
• 因为2和191互质，根据中国剩余定理，49^10≡1 mod(2*191)=mod382
• 所以49^10=1 + k*382（k是整数）
  • 若x≡0 mod383，则x^(49^10)=0≡x mod383，成立
  • 若x≠0 mod383，根据费马小定理x^382≡1 mod383，则x^(49^10)=x^(1+k*382)=x*(x^382)^k≡x*1^k=x mod383，成立

2. 验证x^(49^10)≡x mod563

• 563是质数，φ(563)=562=2*281
• 同理，根据提示7^20≡1 mod281，可得49^10=7^20≡1 mod281
• 49^10是奇数，故49^10≡1 mod2，因此49^10≡1 mod(2*281)=mod562
• 同样，49^10=1 + m*562（m是整数）
  • 若x≡0 mod563，x^(49^10)=0≡x mod563，成立
  • 若x≠0 mod563，费马小定理得x^562≡1 mod563，则x^(49^10)=x*(x^562)^m≡x*1^m=x mod563，成立

3. 合并结果

根据中国剩余定理，因为x^(49^10)≡x mod383且x^(49^10)≡x mod563，所以x^(49^10)≡x mod(383*563)=215629，即E(x)=x。

三、这对不知道n质因数的窃听者意味着什么？ #

这意味着这个加密方案完全没有保密作用：

1. 窃听者不需要破解RSA（不需要分解n或找解密指数），只要拿到加密后的结果，就直接得到了原明文——因为迭代十次加密等于没加密。
2. 即使窃听者一开始不知道这个缺陷，只要尝试加密任意测试明文，就会发现加密十次后回到原明文，从而立刻意识到方案的漏洞。
3. 进一步，窃听者可以利用49^10≡1 modφ(p)和49^10≡1 modφ(q)这个信息，缩小φ(n)的范围，甚至辅助分解n（比如49^10-1是φ(p)和φ(q)的倍数，而φ(n)=φ(p)φ(q)，可以通过这个关系寻找n的因数）。

备注：内容来源于stack exchange，提问作者Cotton Headed Ninnymuggins