[Crypto] rsa_padding - CirQ

xp0int Posted on Mar 12 2018

? Crypto ? ? rsa ? ? high precision ?

一道与普通rsa不太相同的题，基本没见过这个思路，但实际上并不难，需要一点数学的直觉。

直接看代码可以知道，所使用的消息$m$、大整数$N$和加密指数$e$都是固定的，但需要用户自行输入一个padding，加密过程是：

$$cipher=(m+sha256(padding))^e\ mod\ N$$

其中$e$的值固定为3，但因为消息$m$过长，三次方后超过$N$，导致直接开立方不奏效。由于密钥参数都是确定的，因此可以用两次加密作差来解决求模的问题，记$sha256(padding)$为$p$，密文为$c$，那么两次加密的结果记做：

$$c_1=(m+p_1)^3\ mod\ N$$ $$c_2=(m+p_2)^3\ mod\ N$$

直接相减可以消去$m$的立方项，由于$p\ll m$，因此相减之后的结果也不会超过$N$，即

$$c_1-c_2=(p_1^3-p_2^3)+3(p_1^2-p_2^2)m+3(p_1-p_2)m^2\ mod\ N$$ $$ =(p_1^3-p_2^3)+3(p_1^2-p_2^2)m+3(p_1-p_2)m^2$$

这里用到一个假设是 $3(p_1-p_2)m^2\ll N$，因此不会被求模，可能这一步比较凭直觉，但是事实也确实如此。

移项可以得到关于m的一元二次方程，解方程即可。回忆一下二次方程的求根公式需要用到开方操作，但python自带的`math.sqrt`有溢出限制，因此要用到高精度求解，这里用的是gmpy2这个第三方库，很好用，但需要设定一下全局的求解精度：

```python
from pwn import *
from hashlib import sha256
from string import *
import gmpy2

context.log_level = 'error'
gmpy2.get_context().precision = 2048

def enter(sh): # 做工作量证明，没什么好说的
    condition = sh.recvuntil('str\n\n').split()[0]
    def POW(x):
        r = condition.replace('str', '"'+x+'"')
        return eval(r) == True
    postfix = util.iters.mbruteforce(POW, ascii_letters+digits, 5)
    sh.sendline(postfix)

def send(): # 这个函数需要运行两次，分别发送w和u得到两个密文
    p = remote('116.62.141.130', 23333)
    enter(p)
    p.recvuntil('want?')
    p.sendline('2')
    p.recvuntil('padding:')
    #p.sendline('wb9J')
    p.sendline('uDaz')
    p.interactive()

w = 'wb9J'
with_w = 14550589053226237723784378782911157204367764723818273183278778830494499416487873545893468743965983173908692352307319099326274169973375387668121132274358740661675603176127544158825636168393286090271569545184140084312236815407826741955987000669827007469234846354503532996056122210255766499476239027667611324521618888621820406801104915946390327546557922932113558227334995966247861847888945395534045504779859336497392974026440646007960324182593728022274875079834294292984914444067657462568765178062510153359081152844786274988649121306002973793985267278962849801079026067292405846997505048651241950266591305187987978198713

u = 'uDaz'
with_u = 14550589053226237723784378782911157204367764723818273183284827534950929220274713515064300779911945999522249447863069056869160023759098123628992518025220042646777935256722814170110172638540769969084842200453311039632252490837318646169003162023702642852718440630591416809904683876663469546356315683294431475239920694455074311877002823898681237543987974274506853637843279001570564784833459744680575998282585070374220160449360842395676848902576493970505502732901690479235290299617418190954815264726336509268370010258209644209457542001522111942631207467644725735877465107438095706971926190124898391660765233275103556904673

s256 = lambda x: int(sha256(x).hexdigest(), 16)
p1, p2 = s256(w), s256(u)
c1, c2 = with_w, with_u

sqrt = lambda n: int(gmpy2.sqrt(gmpy2.mpz(n)))

# 一元二次方程求根
a = 3 * (p2 - p1)
b = 3 * (p2**2 - p1**2)
c = p2**3 - p1**3 - c2 + c1
lmbd = b**2 - 4*a*c
root = (-b + sqrt(lmbd)) / (2 * a) # 两个根要取正数的那一个

print hex(root)[2:].decode('hex')
```

解密出来的密文是：Welcom to Nu1L CTF, Congratulations, You get flag, and flag is **N1CTF{f7efbf4e5f5ef78ca1fb9c8f5eb02635}**

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