扩大节-合并节-数据目录

题目：

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from hashlib import sha256
import random, os, signal, string

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(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}")
    print('Give me XXXX: ')
    x = input()
    if len(x) != 4 or sha256(x.encode()+proof[4:].encode()).hexdigest() != _hexdigest:
        print('Wrong PoW')
        return False
    return True

if not proof_of_work():
    exit(1)
    
signal.alarm(10)
print("Give me a bad RSA keypair.")

try:
    p = int(input('p = '))
    q = int(input('q = '))
    assert p > 0
    assert q > 0
    assert p != q
    assert p.bit_length() == 512
    assert q.bit_length() == 512
    assert isPrime(p)
    assert isPrime(q)
    n = p * q
    e = 65537
    assert p % e != 1
    assert q % e != 1
    d = inverse(e, (p-1)*(q-1))
except:
    print("Invalid params")
    exit(2)

try:
    key = RSA.construct([n,e,d,p,q])
    print("This is not a bad RSA keypair.")
    exit(3)
except KeyboardInterrupt:
    print("Hacker detected.")
    exit(4)
except ValueError:
    print("How could this happen?")
    from secret import flag
    print(flag)

关键在想办法报ValueError，查看construct函数的源码，可以分析出是n、d不互素：

if Integer(n).gcd(d) != 1:
    raise ValueError("RSA private exponent is not coprime to modulus")

构造出合适的d：

令$d = m \cdot p = m + m \cdot (p-1)$

两边同乘上e：

$e \cdot d = e \cdot m + e \cdot m \cdot(p-1)$

结合$e \cdot d \equiv 1 \space mod \space \phi(n)$，可得：

$e \cdot m \equiv 1 \space mod \space \phi(n) \equiv 1 \space mod \space (p-1)$

$p$随机生成，则可以求出m来。

$e \cdot d = e \cdot m \cdot p = 1 + k \cdot (p-1) \cdot (q-1)$

$(q-1) = \frac{e \cdot m \cdot p - 1}{k \cdot (p-1)}$，$k在(1,e)$，可以爆破。

代码如下：

from pwn import *
import string
import hashlib

def hashstring(partstr, hashstr):
    str = string.ascii_letters + string.digits
    for i1 in str:
        for i2 in str:
            for i3 in str:
                for i4 in str:
                    plain = i1 + i2 + i3 + i4 + partstr
                    maystr = hashlib.sha256(plain.encode()).hexdigest()
                    if maystr == hashstr:
                        print(i1 + i2 + i3 + i4)
                        return i1 + i2 + i3 + i4

def getPQ():
    e = 65537
    p = getPrime(512)
    m = inverse(e,p-1)
    res = (e*m*p-1) // (p-1)
    for k in range(0,e):
        if res % k == 0:
            q = res // k + 1
            return p,q

s = remote("...", ...)
s.recvuntil(b"XXXX+")
partstr = s.recvuntil(b')')[:-1].decode()
print(partstr)
s.recvuntil(b"== ")
hashstr = s.recvline()[:-1].decode()
print(hashstr)
knownpart = hashstring(partstr, hashstr)
s.recvuntil(b"Give me XXXX: ")
s.sendline(knownpart.encode())

print(s.recvuntil(b"Give me a bad RSA keypair."))
p,q = getPQ()

解出p、q就不多bb了。

参考：

2023CISCN-badkey1 - L00kback - 博客园 (cnblogs.com)

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com