RSA 加密及解密
对于解题来说 一般会给你以下信息：模数N、公钥E和密文C. 如果只是做题的话
0x01 分解模数N
对于大数可以在 http://factordb.com上寻找在数据库中是否已经有对应的数字, 如果比较小的话直接在RSAtool2v17上就可以分解.
0x02 对模数N进行因式分解得到两个质数P和Q, 计算欧拉函数φ(n), 从而得到私钥D
φ(n) = (P-1)(Q-1) E*D ≡ 1 (mod φ(n)) 也就是说E*D (mod φ(n)) 结果为1 这一步可以直接用RSAtool2v17来解决
0x03 通过私钥D, 模数N和密文C来得到原文M
CD ≡ M (mod N) 注意M必然小于N 所以M=CD(mod N) 最后将M化为16进制对应ASCII就行了
0x04 如果是多质数加密
差别在N的生成为N= p1 * p2 * p3…*pn 和欧拉函数φ(n) = (p1-1)(p2-1)(p3-1)…(pn-1) 上. 其余算法均与双质数相同
0x04 RSA的数学原理以及证明
可以在这里查看, 讲解的很清楚~
PS:私钥同样可以加密信息, 但是在这里信息不是重点, 而是可以证明这个信息是拥有此私钥的人发出的, 相当于发出人对这个信息签了名.