RSA算法举例

Question

请详细举例解释RSA加密和基于RSA数字签名的算法步骤.

Answer 1

首先看下rsa算法：
找两素数p和q
计算n=p*q和
t=(p-1)*(q-1)
取小于n的一个数e,并且e与t互质，就是最大公约数是1
找一个数d，d满足（ed-1）
mod
t
＝0
公钥取（n，e），私钥取（n，d）
现在开始分析，
已知公钥是（n＝35,e＝5）,那么
n＝p*q，p与q只能是7和5
那么t就是24
而（ed-1）%t＝0
也就是（5d-1）%24＝0,那么可以取d为5
所以私钥是
（d＝5,n＝35）
解密公式：m＝c^d
mod
n
=10^5
mod
35
=5
所以明文m是5