rsa 相关记录

算法概述

明文 m：就是待加密的文本啦，一般也就是我们的flag。

密文 C：加密完成后的密文，一般题目会给你，我们要做的就是根据密文解密出明文。

公钥 e（加密钥）：用来加密的密钥，是一个整数，是公开的。

两个大素数 p,q：RSA加密的关键部分，一般不会告诉你。我们选取两个大素数并计算它们的乘积，得到n=p*q。后面会用p,q,n来加密解密。由于p,q非常大，想要对n进行因式分解得到p，q非常困难，这也确保了RSA的安全性。

私钥 d（解密钥）：用来解密，一般不会告诉你，d满足e*d mod (p-1)(q-1)=1，所以我们只要知道e和p,q就可以把d算出来。

加密过程：$c = E(m)=m^{e}\bmod n$

解密过程：$m = D(c)=c^{d}\bmod n$

解题思路

思路一： 分解n得到pq

适用情况：n已知且可因式分解

既然n = p*q，那么最常规的想法就是把n因式分解得到p,q，上面说n很难分解，但对于一些不太大的n，我们可以借助工具去分解它。下面介绍两种常规因式分解方法：

第一种：在线因式分解网站，例如factordb.com，我们可以利用在线网站快速分解出p,q

第二种：yafu大数分解工具

yafu-x64 factor(n)                               //常规分解n

yafu-x64 "factor(@)" -batchfile 1.txt   //把n复制到txt文件中再分解，用于n过长的情况

import gmpy2
from Crypto.Util.number import long_to_bytes
 
 
q = 189239861511125143212536989589123569301
p = 386123125371923651191219869811293586459
 
e = 65537
c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
# n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
n = q*p
# print(n)
d = gmpy2.invert(e, (p - 1) * (q - 1))
print("d=",d)
m = pow(c, d, n)
print(m)
print(long_to_bytes(m))