关于#网络安全#的问题：非对称加密验证

Question

######第一张图是验证 非对称加密的流程，注意小标题5
要求: 验证第二张图的内容，利用中国剩余定理和费马小定理，麻烦解释的清楚一点，谢谢！抱拳了

Answer 1

回答不易，有用请采纳：
看第一张图，第一张图描述了一种非对称加密方案，其中A选择两个大质数P和Q，并将N = PQ作为公钥发布。A还计算出P'和Q'，使得PP'=1(mod Q-1)和QQ'=1(mod P-1)。B使用这个公钥对信息M进行加密，得到C = M^N mod N。A使用私钥来解密该信息，即通过求解M=C(mod Q)和M = C^Q'(mod P)来求得M。

看第二张图，第二张图要求证明这种方案是正确的，也就是证明使用公钥加密信息再使用私钥解密能得到原始信息。为了证明这一点，可以使用费马小定理和中国剩余定理。

费马小定理：对于一个大质数p和任意整数a，a^(p-1) = 1 (mod p)。

中国剩余定理：给定两个不互质的自然数a和b，以及它们的余数x和y，那么一组方程ax ≡ x(mod b)和by ≡ y(mod a)有唯一解x和y。

首先，因为P和Q是大质数，所以可以使用费马小定理证明M^N = M^(PQ) = (M^P)^Q = M^Q(mod P)。这意味着可以使用Q'来解密M = C^Q'(mod P)。

其次，因为P和Q是不互质的，所以可以使用中国剩余定理证明M = C(mod Q)。这意味着我们可以使用P'来解密M = C^P'(mod Q)。

由于M^N = M^Q(mod P)和M = C^Q'(mod P)，所以可以得到M^N = C^Q'(mod P)

由于M = C(mod Q)和M = C^P'(mod Q)，所以可以得到M = C^P'(mod Q)

因此，通过使用Q'来解密M = C^Q'(mod P)和使用P'来解密M = C^P'(mod Q)，我们可以得到原始信息M。这证明了使用公钥加密信息再使用私钥解密能得到原始信息的正确性。

Answer 2

大佬，费马(M^P)^Q = M^Q(mod P)；中国剩余M = C(mod Q)，这个怎么得出来的?有点懵，可以麻烦您给更多解释不谢谢

Answer 3

费马小定理告诉我们，对于任意正整数M和质数P，M^P = M(mod P)。所以M^P^Q = M^Q (mod P)

Answer 4

M = C(mod Q) 是在解密过程中使用的公式，这是由于在加密过程中，原始信息M被转化为密文C = M^N mod N, 所以 在解密过程中，我们可以用 C mod Q来得出M，即M = C(mod Q)。