一点点学习别人的WP，这回看到一个大姥(r3kapig)的帖子，DiceCTF第二名，不过有好多东西一时还理解不了，得慢慢来。

题目

这个题有3个功能：

rsa加密功能，p,q,N未知，e=17低加密指数

解密，不过解密方法比较特别，分别对p,q求nth_root不过未给出nth_root函数，所以不能直接使用。

对flag加密，用PKCS1_OAEP填充。多数情况下低加密指数如果明文比较小会导致加密后比N小或者仅比N大一点，可以通过开根号爆破。但填充后长度基本与N长度一致，爆破无效。

import asyncio
import traceback
from Crypto.Util.number import getPrime, bytes_to_long
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSAfrom nth_root import nth_root, chinese_remainder # not providedclass Server:def __init__(self):e = 17nbits = 512p = getPrime(nbits)q = getPrime(nbits)N = p * qself.p = pself.q = qself.N = Nself.e = edef encrypt(self, m):assert 0 <= m < self.Nc = pow(m, self.e, self.N)return int(c)def decrypt(self, c):assert 0 <= c < self.Nmp = int(nth_root(c, self.p, self.e))mq = int(nth_root(c, self.q, self.e))m = chinese_remainder([mp, mq], [self.p, self.q])return int(m)def encrypt_flag(self):with open("flag.txt", "rb") as f:flag = f.read()key = RSA.construct((self.N, self.e))cipher = PKCS1_OAEP.new(key)c = cipher.encrypt(flag)c = bytes_to_long(c)return casync def handle(a):S = Server()while True:cmd = (await a.input("Enter your option (EDF) > ")).strip()if cmd == "E":m = int(await a.input("Enter your integer to encrypt > "))c = S.encrypt(m)await a.print(str(c) + '\n')elif cmd == "D":c = int(await a.input("Enter your integer to decrypt > "))m = S.decrypt(c)await a.print(str(m) + '\n')elif cmd == "F":c = S.encrypt_flag()await a.print(str(c) + '\n')returnclass Handler:def __init__(self, reader, writer):self.reader = readerself.writer = writerasync def print(self, data):self.writer.write(str(data).encode())await self.writer.drain()async def input(self, prompt):await self.print(prompt)return (await self.reader.readline()).decode()async def __aenter__(self):return selfasync def __aexit__(self, exc_t, exc_v, exc_tb):self.writer.close()await self.writer.wait_closed()if exc_v is not None and not isinstance(exc_v, asyncio.TimeoutError):traceback.print_exception(exc_v)return Trueasync def main():async def callback(*args):async with Handler(*args) as a:await asyncio.wait_for(handle(a), 20)server = await asyncio.start_server(callback, '0.0.0.0', 5000)print('listening')async with server:await server.serve_forever()if __name__ == "__main__":asyncio.run(main())

思路：

求N

首先要求N，我本来是想弄几个17次幂后比N略大的值求gcd，看到大姥的解法眼前一亮。

先随机取m,然后求enc(m),enc(m^2),enc(m^4)然后分别用没有模过N的原值求差m^e,(m^2)^e,(m^4)^e减，再求gcd这个更方便。

函数头部

from pwn import *
import random 
from Crypto.Util.number import GCD,long_to_bytes,bytes_to_long 
from gmpy2 import iroot context.log_level = 'debug'def enc(m):io.sendlineafter(b"Enter your option (EDF) > ", b'E')io.sendlineafter(b"Enter your integer to encrypt > ", str(m).encode())return int(io.recvline())def dec(c):io.sendlineafter(b"Enter your option (EDF) > ", b'D')io.sendlineafter(b"Enter your integer to encrypt > ", str(c).encode())return int(io.recvline())def get_flag():io.sendlineafter(b"Enter your option (EDF) > ", b'F')return int(io.recvline())def decrypt(c, N, p, q):assert 0 <= c < Nmp = int(c.nth_root(e))mq = int(c.nth_root(e))m = chinese_remainder([mp, mq], [p, q])return int(m)

求N

m = random.randrange(0,2**155)
m2 = m**2
m4 = m**4
c1 = enc(m)
c2 = enc(m2)
c4 = enc(m4)
N = GCD(GCD(c1**2 - c2, c2**2 - c4), c1**4 - c4)

分解N

这个方法头一回见。

先取一个略小于 $\text{[math]}$ 的值，使p<m<q(大概率)，求c = m^e %N

由于e=17所以gcd(e,(p-1)*(q-1))有1/17的概率不为1，p,q两个出现1个的概率略大于1/9,对于爆破来说这个概率并不小。

当不互素时 decrypt(c)-m = kp 与N求gcd就能得到p

这时候获取enc(flag)，（远端会在获取后结束，对flag无法交互）

    tmpn = iroot(N,2)[0] - 1000c = enc(tmpn)ret = dec(c)if ret == tmpn:io.close()continue else:iflag = get_flag()print('N = ',N)print('tmpn = ', tmpn)print('c = ',c)print('ret = ', ret)print('iflag = ',iflag)#e=17 gcd(e,p-1) != 1 的概率是1/17 io.interactive()

经过x 次交互得到如下数据

e = 17
N = 145929886027830605678430202427323053628064442310464018856395565973995064472578943595719088909803787366850912624656960966772751178490892976055180188367608145038609558294202567019869852120311834412433602187079592510589435977725095316257649141862850904221294264419961365596274045500230679371213475300930406042261
tmpn = 12080144288369680134663865822252253203358727058793479854567933546272937742973360100460050936204099841676294371963062308235668122560773478644865802421986920
ret = 38626509565846846198929657581252980560445889902524802003755764516997686363556486348466834915881637092111849253058180514729213545303952798006800009337375370781676698957130798722071959097949405886433880476180556708960839753606831748033044468904639617141322699562124769255797179947555095545345666523628726328021
iflag = 94785540286244324280900673502395494485593520218609389745579915172323211491609524359277466592150462516952301308455222973538441633205212054875400879171885042191555256518152907528122607881031719899722188867464126986611318409258138548887258038636675128271840693263847776054879375943419688129202875859618405032469

这时候就能得到p,q

p = GCD(ret-tmpn, N)
q = N//p 
'''
p = 12489852031586615822311701100326231241806260275896449364532516898411555577529972957144893166576911381503372838312839610202975336506868820457393001178785531
q = 11683876290830066998757443847623160481197019426815171259465107520260429703525441378146027740470276103931704547758704704292062887913193269825188377531686831
'''

修改PKCS1_OAEP.py增加unpad函数

pycryptodome库在PKCS1_OAEP.py提供了OAEP的解密功能，在RSA解密后进行了unpad但是没有独立的unpad函数。而由于gcd(e,phi)!=1所以也就不能直接用decrypt函数。

修改的方法是将decrypt函数复制一下，改为unpad然后将第2a,2b步的解密删掉改为从参数直接获取明文

unpad后

    def unpad(self, ct_int):"""Decrypt a message with PKCS#1 OAEP.:param ciphertext: The encrypted message.:type ciphertext: bytes/bytearray/memoryview:returns: The original message (plaintext).:rtype: bytes:raises ValueError:if the ciphertext has the wrong length, or if decryptionfails the integrity check (in which case, the decryptionkey is probably wrong).:raises TypeError:if the RSA key has no private half (i.e. you are tryingto decrypt using a public key)."""# See 7.1.2 in RFC3447modBits = Crypto.Util.number.size(self._key.n)k = ceil_div(modBits,8) # Convert from bits to byteshLen = self._hashObj.digest_size#patch--------------------------------------------# Step 1b and 1c#if len(ciphertext) != k or k<hLen+2:#    raise ValueError("Ciphertext with incorrect length.")# Step 2a (O2SIP)#ct_int = bytes_to_long(ciphertext)# Step 2b (RSADP)#m_int = self._key._decrypt(ct_int)m_int = ct_int    #与decrypt基本相同，只是用ct_int跳过解密#------------------------------------------------------# Complete step 2c (I2OSP)em = long_to_bytes(m_int, k)# Step 3alHash = self._hashObj.new(self._label).digest()# Step 3by = em[0]# y must be 0, but we MUST NOT check it here in order not to# allow attacks like Manger's (http://dl.acm.org/citation.cfm?id=704143)maskedSeed = em[1:hLen+1]maskedDB = em[hLen+1:]# Step 3cseedMask = self._mgf(maskedDB, hLen)# Step 3dseed = strxor(maskedSeed, seedMask)# Step 3edbMask = self._mgf(seed, k-hLen-1)# Step 3fdb = strxor(maskedDB, dbMask)# Step 3gone_pos = hLen + db[hLen:].find(b'\x01')lHash1 = db[:hLen]invalid = bord(y) | int(one_pos < hLen)hash_compare = strxor(lHash1, lHash)for x in hash_compare:invalid |= bord(x)for x in db[hLen:one_pos]:invalid |= bord(x)if invalid != 0:raise ValueError("Incorrect decryption.")# Step 4return db[one_pos + 1:]

文件位置一般在这

"C:\Users\AAAA\AppData\Local\Programs\Python\Python310\Lib\site-packages\Crypto\Cipher\PKCS1_OAEP.py"

求明文

由于e与phi不互素，所以这里要对p,q分别求根

from Crypto.Util.number import isPrime,long_to_bytes,bytes_to_long 
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
import time def rthroot(c, r, q):c %= qassert(isPrime(r) and (q - 1) % r == 0 and (q - 1) % (r**2) != 0)l = ((q - 1) % (r**2)) // ralpha = (-inverse(l, r)) % rroot = pow(c, ((1 + alpha * (q - 1) // r) // r), q)return rootdef allroot(r, q, root):all_root = set()all_root.add(root)while len(all_root) < r:new_root = rootunity = pow(getRandomRange(2, q), (q - 1) // r, q)for i in range(r - 1):new_root = (new_root * unity) % qall_root.add(new_root)return all_rootdef decrypt(proot, qroot, p, q):count = 0total = len(proot) * len(qroot)t1 = inverse(q, p)t2 = inverse(p, q)for i in proot:for j in qroot:count += 1m = (i * t1 * q + j * t2 * p) % (p * q)assert (pow(m,e,N) == c)try:print( cipher.unpad((m)))print(m)except:continuekey = RSA.construct((N, e))
cipher = PKCS1_OAEP.new(key)  #rthroot要求 (q-1)%e == 0 所以必要时是p,q交换，使(q-1)%e == 0
p,q = q,p proot = rthroot(c, e, p)
qroot = pow(c,inverse(e,q-1),q)
print('[+] Calculating all e-th roots...')all_proot = allroot(e, p, proot)
all_qroot = [qroot]# 3 allroot(e, q, qroot)
print('[+] CRT cracking...')decrypt(all_proot, all_qroot, p, q)