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

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

我觉得哈可以利用中国剩余定理和费马小定理来证明。

第一个：中国剩余定理：对于不同的模数m1,m2,…,mk，如果对于所有的i(1<=i<=k)都有ax≡b(mod mi)有解，那么对于模M=m1m2…*mk的方程ax≡b(mod M)也有解，且唯一解x=b(mod M)。

第二个：费马小定理：对于任意质数p和整数a，有a^(p-1)≡1(mod p)。

因此，我们可以将C'=MN(mod N)代入M=CP'(mod Q)和M=CQ'(mod P)两个式子中，利用费马小定理和中国剩余定理证明M为原始消息。

Answer 3

题目要求我们证明在B使用A的公钥对信息进行加密后，A使用对应的私钥进行解密能够得到原始信息。

给出的加密方案是一种RSA加密，使用两个大质数P和Q来生成公钥和私钥。公钥由P和Q相乘得到N=PQ,私钥由计算得到P'和Q'满足PP'=1(mod Q-1),QQ'=1(mod P-1)。

为了证明方案是正确的，我们可以使用费马小定理和中国剩余定理。

费马小定理告诉我们，对于任意质数P和整数a，a^(P-1) = 1 (mod P)。

中国剩余定理告诉我们，对于两个整数a和b，以及两个模数m和n，当m和n互质时，方程组a = x (mod m)和a = x (mod n)有且仅有一个解x (mod mn)。

利用这两个定理，我们可以证明方案是正确的:

1.假设P和Q是大质数，且P和Q-1互质，Q和P-1互质。
2.A公布N=PQ作为公钥。
3.A计算P'和Q'，使得PP'=1(mod Q-1)，QQ'=1(mod P-1)。
4.B使用公钥将信息M加密为C=M~mod N。
5.A通过解方程M=C(modQ)和M=C(mod P)来求得M。

由于P和Q互质，所以我们可以使用中国剩余定理来解决问题。通过解方程M=C(modQ)和M=C(mod P)可以得到M在模Q和模P下的值，这两个值是相同的，因此我们可以使用中国剩余定理来计算M在模N下的值。

使用费马小定理可以证明这种加密方式是安全的。由于P和Q是大质数，所以P-1和Q-1都是大质数。使用P'和Q'来解密信息时，M被还原成M^(P-1)(mod P)和M^(Q-1)(mod Q)，而由于P-1和Q-1都是大质数，所以M^(P-1)(mod P) =1和M^(Q-1)(mod Q) =1，因此M被还原成原始信息。

综上所述，这种加密方式是正确和安全的。