buu(前三页第三弹) RSA习题与相关知识总结
首先先描述一下题目：题目一共有四行数据，前两行数据中每行数据包含两个元素，两行数据中第一个元素都相同，第二个元素不同由元素相同可以想到共模攻击由此可以得出： 各字母都分析出来了，那么直接上解题脚本即可： gmpy2.gcdext(a,b) : 【扩展欧几里得算法的内置函数】
Return a 3-element tuple (g,s,t) such that
g == gcd(a,b) and g == as + bt
【返回一个 3 元素元组 （g，s，t），使得 g == gcd（a，b） 和 g == as + bt】
最后得到flag{r3a_C0mmoN_moD@_4ttack} 天知道这题我看了多久，我一直没看到题目给的 e，我说怎么大家就用 n,c1,c2 就能求出来了，所以说信息一定要看全，一定要划到最后面 和上一题好像啊！那话不多说直接套用以上解题脚本运行后还是发现有一些不一样的，因为直接套用得不到flag，哪里出问题了？打印libnum.n2s(int(m))和m的结果： 大佬们的见解：
显然第一位所说 “ m的开头为1，而这样是不可能转换为可见字节 ”，这一说法有点问题。上面一题m开头就为1，得到了flag,m开头为1，所以一串数字开头为1是可以转字节的，所以大家别被误导了既然不能转字节，那么就试试转ascii码吧，转化代码如下：
最终得到flag{whenwethinkitispossible}
至今为止数字串转flag有2种方法（一种不行就试另一种）:
1.转字节
2.转ascii码（在m长度不大的情况下，就如本题，既然能转ascii码，那么大胆猜测还有一种可能是能按照26个英文字母进行转换，前提也是m长度不大）这里简单说一下上面提到的16进制转字符串，十六进制数的一个基本特点：它由十六个数码：数字0～9加上字母A-F组成，所以说纯数字转字符串一般不考虑16进制转化 （注：此题有两种解法，一种是直接用在线网站分解n ,得到p,q,特别简单且快速，比较暴力。但，我喜欢！、
另一种便是一步步分析下来，求p,q ，以下讲解如何分析得到flag）
首先这里遇到了两个没见过的函数 ----> Fraction() 和 Derivative() Fraction(a,b) 相当于 a / b (a 除 b)
Derivative(a,b),前一个参数表示求导的内容，后一个参数表示求导的主体
Derivative(arctan § ,p)的意思是以p为主体对 arctan§ 求导，得到1/（1 + p^2），同理Derivative(arth(q),q) 得到 1/（1 - q^2）
最后
Fraction(1,Derivative(arctanc ( p ) ,p)) = 1 + p^2，Fraction(1,Derivative(arth(q),q) = 1 - q^2
得到关系式： z = p^2 +q^2，又 n = p * q，进一步得到关系式 ： (p + q) ^ 2 = z + 2n
(p - q) ^ 2 = z - 2n
用代码解出p,q
得到flag{Advanced_mathematics_is_too_hard!!!} 又了解了两个新函数： Fraction(a,b) 相当于 a / b (a 除 b)
Derivative(a,b),前一个参数表示求导的内容，后一个参数表示求导的主体
对于有n的，多尝试能否暴力分解得p,q （先告知：此题有简便方法，即 直接将 P_n 和 Q_n 进行分解，得到两组 p,q（即用线上网站将n 分解得到p,q）将p,q带入生成factor2的代码中，即可得到 P,Q，之后就是常规的rsa解密了。以下是更详细深入的解析）
这题与 buu [GWCTF 2019]BabyRSA 1 比较像，分四个模块，第一个模块告诉我们生成素数的方法（对后面的分析没什么实质性关系）第二个模块即生成 P 的过程（gen_p）: 告诉了我们 n = p * q , phi = (p-1) * (q-1) = p * q - (p+q) + 1 = n - (p+q) + 1
==>n = p * q , phi = n - (p+q) + 1
==>p + q = n - phi + 1
==>(p - q)^2 = (p+q)^2 - 4 * n
==>p - q = [(p-q)^2] ^0.5
==>p = [(p + q) + (p - q)] // 2
==>q = (p + q) - p
由上过程便可得出p,q,从而求出factor2,注意 p<q,若求出来的不符合则调换下位置求P代码： 第三个模块即生成 Q 的过程（gen_q）,和上面生成 P 的过程很像， 不过此时已知的是 n = p * q , e * d = 1 mod phi
==>e * d - 1 = k * phi = k * (p - 1) * (q-1)
==>(e * d - 1) // p * q < (e * d - 1) // [p * q - (p + q) + 1] = k
求 Q 代码如下： 第四个模块则是告诉我们关于rsa的基础运算过程，想必这个大家都清楚，也不过多赘述了以下是完整代码： 最后flag{Ju3t_@_31mp13_que3t10n} 总之通过这题对rsa又有了更深的理解，对某些的模块的运用也更加熟练看大佬的wp,原来 k 还能这么求，真的想不到k的详细解析： 这里是引不等式两边的分母一个pq，一个pq-(p+q)+1相差并不大，并且还是整除，所以估计(ed-1)//pq和(ed-1)//(pq-(p+q)+1)差值不到1用
然后这里两次整除后，后面小数部分应该都省略掉了
打开的 rsa_16m 文件 ：
（在此我只想说神人才找得到 c 的位置） ，这位置是真的难找啊
首先打开 description.md 文件，得到：
翻译下来： 当您需要真正安全的通信时，您可以使用带有 4096 位密钥的 RSA。
我想要真正非常安全的通信来传输核发射代码（是的，物联网无处不在），所以我使用带有16777216位密钥的RSA。俄罗斯人肯定无法考虑这一点！
文件md5 ： 1049a0c83a2e34760363b4ad9778753f
从所有以上的题目描述可以得知的已知条件有：n,c,e已知，且 n,c 特别大，e = 0x10001 = 65537又 c = m^e mod n
所以当 m^e 严重小于 n 的时候，c 很可能就是 m^e，所以对 c 开 e 次方即可得到 m
以下是解题代码（将 rsa_16m 文件 和 代码文件 放在同一个文件夹中）：
得到flag{(I)NSA_W0uld_bE_pr0uD}
（在此我只想说神人才找得到 C 的位置） 这位置是真的难找啊,找不到也许就放弃了若 n ,c 特别特别大，考虑以上方法（又了解了一种rsa题型）
题目四个文件，分别如下：
rsa.py
HUB1
HUB2
README.txt
素数生成算法太麻烦了，有没有取巧的方法呢？
诶，这里好像有个不错的想法哟。
看起来节约了不少时间呢，嘿嘿嘿……
顺便问问，应该大家都知道base64吧，用来编码还是很方便的呢！
从代码中可以知道，HUB文件中的数值分别对应：N,e,和6个密文c，其中两组文件中N相同，e，c不同，由此可以想到共模攻击 共模攻击知识回顾
共模攻击，也称同模攻击
共模攻击利用的大前提是，RSA体系在生成密钥的过程中使用了相同的模数n
在CTF题目中，就是 同一明文，同一n，不同e，进行加密
m,n相同；e,c不同，且e1和e2互质
常规题： (c1 ^ s1 * c2 ^ s2)%n == m , gcd(e1,e2) == 1
变形题：gcd(e1,e2) != 1
假设 gcd(e1,e2) == x
(c1 ^ s1 * c2 ^ s2)%n == m1^x%n = m
m = m1^x%n
m = m1^x + kn
由此我们可以想到 buu RSAROLL（滚动拼接）这一题，都是多组c,每组求出后拼接到一起由此直接上脚本： 得到一大串
MKhDOQ==
Zm9y
dGhl
Zmlyc3Q=
NjI=
dmFsdWVzLg==
…（此处省略）
看起来很像 base64,但又不是寻常的 base64,看了大佬的wp，知道是用 base64隐写术 解密
base64隐写术：
脚本：
得到flag{7c86d8f7d6de33a87f7f9d6b005ce640}
在写代码过程中，发现 long_to_bytes(m) 与 binascii.unhexlify(hex(m)[2:]).decode() 有些不同
long_to_bytes(m)：
2.binascii.unhexlify(hex(m)[2:]).decode() ：
二者所得结果排版不同，对这题来说用 binascii.unhexlify(hex(m)[2:]).decode() 更合适，因为更适合进行分隔以后遇到解出来得到类似以上的结果的题目，考虑隐写术 给了4个文件
首先这种出现pubkey的题都很熟悉，那么可以用惯用的套路来求解其中的n,e第一步：在kali中分别使用命令(也可用在线解公钥网站得到n,e)： openssl rsa -pubin -text -modulus -in warmup -in pubkey1.pem
openssl rsa -pubin -text -modulus -in warmup -in pubkey2.pem
分别得到：
由此可以得出：e不同，n相同，想到了共模攻击
e1 = 2333
e2 = 23333
n = 0x75A8B8AA2AD2950E9AED4BE34618DFBEABB8CBA832685CC94F45173330100624846CCF90F3C2DB75BA5AF4B39CAEF1175AB9F898794EAC6082A4F766F7CB280B16F6980B38DDA811761324D619513B3CBE65877ACF51FC70405A8347C121207E71F8E6FCAE39647ED2231D306DD53849257BC306E997A502867012249D1691F5DC11D6AF06539F3F808939343DDE09301A761AE12C1C969076C502BC5A971E10ABCB366547BC94373F37A57DDC43858DB29BAAAAAD0E6867885EA3757403008C164E9C7AFA39B3C65089A151DDD8C06C64271086F9255ADB8ACF82182F8FA252930A187961635BC2A85C761330F85C896314B3FDAE4EFEF7E0A8C93B8854BFC3
然而共模攻击还要知道密文c的值，文件中myflag便是对应的密文（这种应该可以说是约定俗成了：公钥对应n和e ，私钥对应n和d ，flag对应密文c或明文m）在rsa中对于类似base64编码的密文，我们可以用以下方式进行解码： 由此可写出完整代码： 得到 flag{23re_SDxF_y78hu_5rFgS} 在kali中打开公钥或私钥文件用以下命令： openssl rsa -pubin -text -modulus -in warmup -in pubkey1.pem
RSA中遇到类似base46的字符串用以下代码进行转码： c1 = bytes_to_long(base64.b64decode(f1))
给了两个文件：
public.key:
flag0.enc（用记事本打开）:
首先利用 public.key 解出 n, e
也可利用在线解公钥网站得出n,e
此处密文c的求解有些特殊（并不是base64相关解码），此种情况记住即可以下为解题代码：
两个文件，都用记事本打开，记住用记事本打开
pub.key:
flag.enc:
显然第一个文件即时普通的公钥(n,e)解密文件，第二个文件是密文c解密文件,与
buu [AFCTF2018]可怜的RSA 1 和 buu [HDCTF2019]together 1 很像公钥解密按套路来，可以用线上工具，也可以用脚本
1.线上公钥解析网站：
2.代码解密（将代码文件和 pub.key文件 放同一个文件夹）：
得到： n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
e = 65537
n 分解得 p,q: p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
最终便是求密文了，遇到此种一段乱码的直接用python脚本（记住就好，不必深究，挺简单的,记住将代码文件和 flag.enc文件 放同一个文件夹）： 最终得到密文c: c = 29666689760194689065394649908301285751747553295673979512822807815563732622178
自此，所有未知数都已求出，完整代码如下： 得到 flag{decrypt_256} 至今为止已知m数值转flag有2种方法（一种不行就试另一种）:
1.转字节
2.转ascii码（在m长度不大的情况下，就如本题，既然能转ascii码，那么大胆猜测还有一种可能是能按照26个英文字母进行转换，前提也是m长度不大）
这里简单说一下16进制转字符串，十六进制数的一个基本特点：它由十六个数码：数字0～9加上字母A-F组成，所以说纯数字转字符串一般不考虑16进制转化
新收获的两个函数：
Fraction(a,b) 相当于 a / b (a 除 b)
Derivative(a,b),前一个参数表示求导的内容，后一个参数表示求导的主体
< a >
已知 n , phi 如何求p，q（注：n = p * q , phi = (p-1) * (q-1)）：
两个方程，两个未知数，很容易解：
告诉了我们 n = p * q , phi = (p-1) * (q-1) = p * q - (p+q) + 1 = n - (p+q) + 1
==>n = p * q , phi = n - (p+q) + 1
==>p + q = n - phi + 1
==>(p - q)^2 = (p+q)^2 - 4 * n
==>p - q = [(p-q)^2] ^0.5
==>p = [(p + q) + (p - q)] // 2
==>q = (p + q) - p
< b >
已知 n，e * d ，如何求 p，q（注：n = p * q，e * d = 1 mod phi）:
此时已知的是 n = p * q , e * d = 1 mod phi,那么我们便将已知转化为 n，phi
==>e * d - 1 = k * phi = k * (p - 1) * (q-1)
==> k = (e * d - 1) // [p * q - (p + q) + 1] > (e * d - 1) // p * q
k = ((e * d-1) // n)+1
phi = (e * d- 1) // k
k的详细解析:
这里不等式两边的分母一个pq，一个pq-(p+q)+1相差并不大，并且还是整除，所以估计(ed-1)//pq和(ed-1)//(pq-(p+q)+1)差值不到1用:
k = ((e * d-1) // n)+1
phi = (e * d- 1) // k
然后这里两次整除后，后面小数部分应该都省略掉了
对于求公钥私钥的套路我们已了解，那么接下来我们来总结此种题型下求密文的方法（至今知道的有三种）： 1.密文出现一段乱码的用以下代码打开：
2.密文出现一串类似base64的字符串的有一下两种：
(1)第一种：
(2)第二种（此种情况可在使用第一种方式下得不到答案的情况下使用，很特殊的一种方式）：