发布于 

xman-crypto

xman罚坐了，看来自己和学好密码还有很远的距离~

Ez_RSA

赛后好久才看见WP来复现，所以只能本地起环境了。

  1. 先搞点本地起py脚本的骚操作：

    封装一个pyprocess.sh执行python process.py指令，然后用pwn的库起。

  2. 读题：放魔改后的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from Crypto.Util.number import bytes_to_long,getPrime,inverse,GCD
from hashlib import sha256

import random
import string
import os
from uuid import uuid4

flag="flag{"+str(uuid4())+"}"
flag=bytes(flag,"utf-8")

def proof_of_work():
    random.seed(os.urandom(8))
    proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
    _hexdigest = sha256(proof.encode()).hexdigest()
    print(b"[+] sha256(XXXX+%s) == %s".decode() % (proof[4:],_hexdigest))
    print("[+] Plz tell me XXXX: ")
    x = input("[-] ").encode('latin1')
    if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
        return False
    return True

def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = getPrime(32)
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
        e = getPrime(32)
    d = inverse(e,(p-1)*(q-1))
    return (e,n),(d,p,q)

def main():
    m = bytes_to_long(flag)
    publickey,secretkey = init_key()
    print("[+]",publickey)
    print("[+]",pow(m,publickey[0],publickey[1]))

    for _ in range(10000):
        try:
            c = int(input("[-] "))
            m = pow(c,secretkey[0],publickey[1])
            msg = int.to_bytes(m,1024//8,'big')
            print("[+]",msg.startswith(b"\x00"))
        except:
            print("[!] ERROR!")

if __name__ == '__main__':
    if proof_of_work():
        main()
    else:
        print("[!] Wrong!")

可以发现这个题过了工作证明之后提供了一个解密接口，可以进行选择密文攻击，那么我们就需要构造合适的密文来泄露信息。这里能泄露的信息只有最高8位是否为0。

根据同态加密，我们可以知道，rsa密文进行乘法运算是同态的，所以这里可以用密文乘来对原明文进行操作。

前八位是否为0等价于解密的文段m是否满足\(m>=2^{1024-8}=2^{1016}\)​，通过这个点和乘法操作可以进行单调性分析,构造m=2**1016//x，然后应用二分查找查出x即可。

上exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
from pwn import *

from gmpy2 import *
p=process('/home/zuni-w/Desktop/pyprocess.sh' )

q=process('/home/zuni-w/Desktop/pysha.sh' )

s=p.recvuntil("XXX+")
s=p.recvuntil(")")
la=s[:-1]
s=p.recvuntil("==")

s=p.recvuntil("\n")
sha=s[1:-1]
q.recvuntil("?:")
q.sendline(str(la)[2:-1])
q.recvuntil("ans:")
q.sendline(str(sha)[2:-1])

s=q.recvuntil("\n")
ans=s[:-1]
print(ans[:-1])
q.close()
p.recv()
p.sendline(ans)



s=p.recvuntil("\n")
e,n =eval(s[4:])


s=p.recvuntil("\n")
c=eval(s[4:])

f=True
i=-1
while f:
    i+=1
    c1=powmod(2**i,e,n)
    c2=c*c1%n
    p.recvuntil("[-]")
    p.sendline(str(c2))
    s=p.recvuntil("\n")
    f=eval(s[4:])
    

print(i)

r=2**i
l=2**(i-1)
while r>l:
    mid=(r+l+1)//2
    c1=powmod(mid,e,n)
    c2=c*c1%n
    p.recvuntil("[-]")
    p.sendline(str(c2))
    s=p.recvuntil("\n")
    f=eval(s[4:])
    if f :
        l=mid

    else :
        r=mid-1

print(mid,r==l)
t=2**1016//r
from binascii import *
print(unhexlify(hex(t)[2:]))

中间使用了已经写好的pow脚本，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from hashlib import sha256
from base64 import *
s='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
m0=input('XXX+?:')
print(m0)
a=input("ans:")
for i in range(64):
    for j in range(64):
        for k in range(64):
            for l in range(64):
                t=s[i]+s[j]+s[k]+s[l]
                m=t+m0
                p=sha256()
                p.update(m.encode("UTF-8"))
                d=p.hexdigest()
                if a in d:
                    print(t)

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站由 [@Zuni](http://example.com/) 创建，使用 Stellar 作为主题。