[Crypto] rsa system - CirQ

xp0int Posted on May 2 2018

? rsa ?

这次比赛中比较遗憾没有做出来的一道题，赛后看了其他大佬的[writeup](https://www.anquanke.com/post/id/107007)才明白了怎么做这道题，也记录下来，个人觉得还是比较有质量的一道题了，虽然大佬说是简单题。关于这一点，想到了一个算是很恰当的比喻，就像是做高考题，总有学霸说“这道题一看就知道怎么做了啊”，但是自己在做的时候就是百思不得其解，到最后看了答案又恍然大悟：好像这种解法以前做题就遇到过，虽然当时不会，现在还是不会。这么来看，我好像把这个博客当成错题集来用了。

这道题很简单，就两个操作，1)自定义填充flag，2)获取rsa加密后的flag。后一步操作的N和e都是固定的，没什么好说，主要是填充的操作有漏洞。

首先，flag长度固定为38字节，而用于加密的flag字符串是256字节。填充分为两部分，用户填充的user_pad和代码填充的code_pad，code_pad的过程如下（其中的参数s已经经过user_pad了）：
```python
def pad(s):
    s += (256 - len(s)) * chr(256 - len(s))
    ret = ['\x00' for _ in range(256)]
    for index, pos in enumerate(s_box):
        ret[pos] = s[index]
    return ''.join(ret)
```
其中的`s_box`是AES的S盒，完全照搬，但实际上的作用是重排。过程就是，在s后面填充字符`chr(256-len(s))`以保证长度为256，再经过重排输出。填充的字符之所以那么奇怪，是为了之后恢复时能够去掉这些填充位：
```python
def unpad(s):
    ret = ['\x00' for _ in range(256)]
    for index, pos in enumerate(invs_box):
        ret[pos] = s[index]
    return ''.join(ret[0:-ord(ret[-1])])
```
最后一行，通过`ret[-1]`就能够知道原来的长度到哪里，就能够截断并输出不带code_pad的字符串，本来是个很聪明的做法，但问题也恰恰出现在这里。根据`pad`函数，如果输入的`s`有256位，那么code_pad就不会填充而只是单纯的重排，而在unpad时，字符串仍然会被截断在最后一个字节的ascii码上，只要控制截断的位置，就能够得到只有部分高位的flag加密后的字符串，然后对flag**逐位爆破**。方法很简单，如果我们通过user_pad把第256位设为`chr(0xff)`，那么第二次unpad之后，flag的有效位就只有256-255=1位了，这样加密过后的明文是很容易爆破的，搜索空间也就只有一遍ascii而已（甚至可以只在printable中找）。

贴出关键部分代码：
```python
flag = ''
num = 256

while len(flag) != 38:
    num = num - 1
    s = '\x00' * num

p = remote('123.59.138.211', 23333)
    sign(p, chr(num) * 218)
    sign(p, s)
    enc_high_bytes = get(p)
    p.close()

for c in range(20, 128):
        if enc_high_bytes == pow(pad(flag + chr(c) + s), e, n):
            flag += chr(c)
            break
    print flag
```

![enter image description here](https://leanote.com/api/file/getImage?fileId=5ae9988cab6441251c0017dd)

打赏还是打残，这是个问题