lost key
赛后学习了一下这道密码题的攻击姿势。
题目脚本如下:
1 | #!/usr/bin/env python |
服务器随机生成 RSA 中的 n 和 e,并将 flag 的密文发给我们。服务器提供了两个服务:对于我们给出的明文服务器返回密文;对于我们给出的密文返回解密后的明文最后一个字节。
这个题考点有两个:获取公钥和 LSB Oracle Attrack。
获取公钥
首先我们需要获得公钥,这里可以通过选择明文攻击的典型手法获取 n,原理大致如下:
我们首先发送 2 让服务器进行加密,返回 c1=2e mod n
继续发送 2**2,也就是 4,让服务器进行加密,返回 c2=4e mod n
我们有:c12-c2=kn
为什么呢?不妨设 2e=a+bn,我们有 c1=(a+bn)mod n=a,同时 c2=(a2+2abn+b2n2)mod n =a2 mod n,所以 c12 和 c2 模 n 同余。
一般来说 a2 会比 n 大,所以 k 不为 0。
同理我们分别发送 3 和 9,用同样的方法得到了 n 的又一个倍数,计算他们的公因数,这样大概率得到的就是 n。
为了准确我们也可以多发送几组,取他们的公因数。
获取 flag
得到了 n,我们就可以获取 flag 了。这个题提供的解密返回解密结果的最后一个字节,很像之前 Xman 选拔赛出国的经典的 LSB Oracle Attrack(不了解的可以看一下 这篇 以及 ctf-wiki 的相关推导 )
之前的是给我们最后一个 bit 的值,也就是对应明文的奇偶,现在给我们的不仅仅是 1 bit 而是 8 bit。
如果我们考虑用同样的方法,即浪费他给的那 7 个 bit,我们会发现由于 n 是 1024 位,采用二分逼近需要 1024 次,题目连接一次只提供 150 次交互,显然条件不能浪费。
给了我们最后一字节,我们也可以采用利用最后 1bit 攻击类似的手法,详细的推导过程 iromise 师傅已经在 ctf-wiki 相关部分中写的很详细了。
下面是 exp:(我用的是 socket,pwn 师傅们可能习惯用 pwntools,可以参考 wiki 里的脚本)
1 | # _*_ coding:utf-8 _*_ |
hitcon{1east_4ign1f1cant_BYTE_0racle_is_m0re_pow3rfu1!}
参考: