已知(dp,dq,p,q,c),其中dp=d mod (p-1),dq=d mod (q-1),则计算明文m的算法如下:
1.计算q模p的逆元记为I
2.计算m1=(c^dp) mod p
3.计算m2=(c^dq) mod q
可得m=(((m1 - m2) * I) mod p) * q + m2
我想不明白最后一步m究竟怎么推到出来的,需要用到中国剩余定理(CRT)么???
我自己的解法是这样:
再计算一步p模q的逆元记为J
则根据中国剩余定理(CRT)得m=(m1 * I * q + m2 * J * p) mod (p * q)
自己实际验证了一下两个方法得到的结果一样,但就是不能证明它们等价。。。求高手!
|