利用RSA算法运算,如果p=11,q=13,公钥pk=13,对明文15进行加密。求私钥sk及密文
时间: 2023-06-18 15:07:18 浏览: 451
已知p和q,生成私钥的rsa破解
首先计算n=p*q=11*13=143,然后计算欧拉函数φ(n)=(p-1)*(q-1)=10*12=120。
公钥pk=13,因为要加密明文15,所以加密时要计算15^pk mod n,即15^13 mod 143。为了高效计算,可以使用快速幂算法,步骤如下:
1. 将pk转换为二进制,得到1101;
2. 从右往左扫描二进制数,遇到1就乘上当前的底数,即15,否则不乘。底数初始为15^1 mod 143=15;
3. 每乘一次底数,就将底数平方取模,即底数变为底数的平方再模n;
4. 最终得到的结果即为密文,即15^13 mod 143=11。
因为加密使用了公钥pk,所以私钥sk必须满足sk*pk≡1(mod φ(n)),即sk*13≡1(mod 120)。可以使用扩展欧几里得算法求解,得到sk=37。
因此,私钥sk=37,密文为11。
阅读全文