当我们给定公钥e与n时,对于很大的n,其欧拉函数的值是很难求解的(只有采取质因数分解的方法,而大数的质因数分解几乎是计算上不可行的)。
因此便很难求出私钥。
如何使用RSA加密
那么接收方Bob,通过选取合适的p和q,那么通过RSA算法,可以获得公钥和私钥,那么将公钥公布出去,私钥自己保存,那么别人就可以向接收方Bob发送密文,而只有拥有密钥的Bob才可以解密。
面临的问题有:
1.如何创建两个不相等且足够大的素数:使用米勒-拉宾素性检验(Miller_rabin算法进行素数判定)
2.如何求得e对于模数为n欧拉函数的乘法逆元:扩展欧几里得算法exgcd(a,b)求得模逆元d
3.对于加密解密,可以使用蒙哥马利算法 montgomery(n, p, m):快速计算(n^p)%m的值,即逐次平方法
值得注意的是:RSA加解密算法本身是操作于整数的模幂运算,而要加密的消息明文通常以字节序列表示,所以需要两个转换函数。
过几天把代码附上
部分内容参考:https://www.packetmania.net/2021/03/01/Python-Textbook-RSA/#%E5%B7%A5%E5%85%B7%E5%87%BD%E6%95%B0



