$证明：[M^{e}mod (p\times q)]^{d}mod(p\times q)=M，其中M为明文，(e,n)为公钥，(d,n)为私钥$

$[M^{e}mod (p\times q)]^{d}mod(p\times q)$
$=(M^{e})^{d}mod (p\times q)      //模算术的性质$
$=M^{ed}mod(p\times q)$

$又\because (ed)mod(p-1)(q-1)=1，即存在整数k满足ed=k(p-1)(q-1)+1，因此，我们必须证明：$
$M^{k(p-1)(q-1)+1}mod(p\times q)=M$
$即[M^{k(p-1)(q-1)+1}-M]mod(p\times q)=0$
$即证：[M^{k(p-1)(q-1)+1}-M]mod(p)=0和[M^{k(p-1)(q-1)+1}-M]mod(q)=0$
$先证：[M^{k(p-1)(q-1)+1}-M]mod(p)=0，同理可得[M^{k(p-1)(q-1)+1}-M]mod(q)=0$
$[M^{k(p-1)(q-1)+1}-M]mod(p)=[M^{k(p-1)(q-1)+1}]mod(p)-(M)mod(p)     //模算术的性质$
$\because [M^{k(p-1)(q-1)+1}]mod(p)$
$=[(M)M^{k(p-1)(q-1)}]mod(p)$
$=[(M)(M^{(p-1)k(q-1)})]mod(p)$
$=((M)mod(p))\times [(M^{(p-1)})mod(p)]^{k(q-1)}              //模算术的性质$   
$=((M)mod(p))\times (1)^{k(q-1)}                     //费马定理+欧拉定理$
$=(M)mod(p)$
$\therefore [M^{k(p-1)(q-1)+1}]mod(p)-(M)mod(p)=0$
$\therefore [M^{k(p-1)(q-1)+1}-M]mod(p)=0，结果得证$

参考文献：
1、《密码编码学与网络安全-原理与实践(第四版)》，William Stallings著，孟庆树、王丽娜、傅建明等译


转载本文请联系原作者获取授权，同时请注明本文来自代冕科学网博客。
链接地址：https://blog.sciencenet.cn/blog-791354-636381.html

上一篇：《可用性工程》阅读笔记4
下一篇：《集体智慧编程》源代码调整