2023-0xGame-week2-wp-crypto

比赛记录

[Week 2] Fault!Fault!

题目描述：

机缘巧合之下，小Z意外获得了一张用于身份认证的加密芯片，这块芯片可以输入一定的信息，并输出签名后的结果。经过一段时间的逆向工作之后，小Z得到了其中的签名逻辑。

小Z转念一想，如果私钥是存储在芯片中的，那么我是否能够通过某种办法读取到其中的私钥？是否意味着我可以任意伪造签名？

于是小Z重金买下工具，，，那么在拥有干涉加解密的能力前提下，这个攻击要如何实施呢……

题目：

from Crypto.Util.number import *
import socketserver
import signal
from secret import flag
import random
import os
import string
from hashlib import sha256
from string import ascii_uppercase
from random import shuffle,choice,randint
import os


def decrypt(c,d,n,index):
    """something go wrong"""
    d_ = d^(1<<(index))
    m_ = pow(c,d_,n)
    return str(m_)

MEMU = """
    Welc0me_2_0xGame2023!
/----------------------------\\
|          options           |
| [S]ign                     |
| [F]ault injection          |
| [C]heck answer             |
\\---------------------------/
"""


class Task(socketserver.BaseRequestHandler):
    def proof_of_work(self):
        '''验证函数'''
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def timeout_handler(self, signum, frame):
        raise TimeoutError

        '''以上是交互部分'''
    def handle(self):
        '''题干'''
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(300)
        self.send(MEMU)
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return

        q = getPrime(512)
        p = getPrime(512)
        e = 65537
        n = q*p
        phi = (q-1)*(p-1)
        d = inverse(e,phi)

        self.send(MEMU.encode())
        while True:
            code = self.recv()
            if code == b'S':
                self.send(b'What you want to sign?:')
                m = bytes_to_long(self.recv())
                c = pow(m,e,n)
                self.send(f'{n}\n{e}\n{c}'.encode())
                
            elif code == b'F':
                self.send(b'Give me the Signatrue:')
                Signatrue = int(self.recv())
                self.send(b'Where you want to interfere?')
                index = int(self.recv())
                self.send(b'The decrypt text:')
                self.send(decrypt(Signatrue,d,n,index).encode())

            elif code == b'C':
                self.send(b'Give me the private key:')
                ans = int(self.recv())
                if ans == d:
                    self.send(b'Here is your flag:')
                    self.send(flag)
                    
            else:
                self.send(b'invaild input')

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10005
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

梳理一下题目加密流程：

连接上靶机后，计时开始，限时300s(这么长的限时就暗示可能需要不断交互)
先通过一个proof_of_work，具体为通过哈希值，爆破四位十六进制串
通过proof后，生成RSA加密所需的p，q，e，n，phi，d等参数，然后可以有如下选项：
- 输入”S”，可以对任意明文m进行加密，并返回密文c及公钥对(n，e)
- 输入”F”，可以对任意密文进行故障解密，故障解密具体是什么意思一会儿讲
- 输入”C”，可以输入一个值，如果该值与d相等，则获得flag

其中，故障解密的代码如下：

def decrypt(c,d,n,index):
    """something go wrong"""
    d_ = d^(1<<(index))
    m_ = pow(c,d_,n)
    return str(m_)

可以看到，相比于常规的RSA解密指数，用在故障解密中的指数d的index这一比特位发生了翻转，也就是第index比特位的0变成1，或1变成0。而这种翻转其实可以写成如下简单形式：

0变成1：

$d' = d + 2^{index}$

1变成0：

$d' = d - 2^{index}$

我们用这个指数对RSA解密，就得到：

$c^{d'} \equiv c^{d \pm 2^{index}} \equiv c^d *c^{\pm 2^{index}} \quad (mod\;n)$

而具体是加号还是减号，就取决于d的那一bit原本是0还是1，因此，我们就有了判别d的某一比特位的方法：

如果d的第index比特位是0，则：

$d' = d + 2^{index}$ $c^{d'} \equiv c^{d + 2^{index}} \equiv c^d *c^{ 2^{index}}\equiv m*c^{2^{index}} \quad (mod\;n)$

也就是：

$c^{d'} \equiv m*c^{2^{index}} \quad (mod\;n)$

而如果d的第index比特位为1，则正好相反，以下式子成立：

$c^{d'} \equiv m*c^{-2^{index}} \quad (mod\;n)$

因此，通过反复更改index并令其解密，我们就能得到d的所有比特位，然后就可以还原出d并上交得到flag。但是对于我的电脑来说，300s限制有点紧张，所以要不断掐掉proof过的慢的交互，不然很难完整复原d的所有比特位。不过之后发现，其实该容器的p，q，n，e都不会变，因此d也不会变，所以完全可以分两次攻击得到不同比特位，然后组合一下就好。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
import string
from hashlib import sha256
from gmpy2 import powmod

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("43.139.107.237",10005)

#part1
proof_of_work()
temp = r.recvuntil(b"-----/")

m = 2
r.sendline(b"S")
temp = r.recvuntil(b"What you want to sign?:")
r.sendline(long_to_bytes(m))
r.recvline()
n = int(r.recvline().strip().decode()[2:])
e = int(r.recvline().strip().decode())
c = int(r.recvline().strip().decode())

d = ""	
for index in tqdm(range(1024)):
    try:
        r.sendline(b"F")	
        r.recvuntil(b"Give me the Signatrue:")
        r.sendline(str(c).encode())
        r.recvuntil(b"Where you want to interfere?")
        r.sendline(str(index).encode())
        r.recvuntil(b"The decrypt text:")
        temp = r.recvline()
        m_ = int(r.recvline().strip().decode())
        t1 = (powmod(c,2**index,n) * m) % n
        t2 = (powmod(c,-2**index,n) * m) % n
        if(t1 == m_):
            d += "0"
        elif(t2 == m_):
            d += "1"	
    except:
        break

d = int(d[::-1],2)
r.sendline(b"C")
temp = r.recvuntil(b"Give me the private key:")
r.sendline(str(d).encode())
temp = r.recvall()
print(temp)

#0xGame{F@ult_Milest0ne!!}

[Week 2] EzLFSR

题目描述：

暂无

题目：

from Crypto.Util.number import *
from secret import flag,secret

assert flag == b'0xGame{'+secret+b'}'

def make_mask(m):
    tmp = str(bin(bytes_to_long(m)))[2:].zfill(128)
    return tmp

def string2bits(s):
    return [int(b) for b in s]

def bits2string(bs):
    s = [str(b) for b in bs]
    return ''.join(s)

def lfsr(state, mask):
    assert(len(state) == 128)
    assert(len(mask)  == 128)

    output = 0
    for i in range(128):
        output = output ^ (state[i] & mask[i])

    return output

if __name__ == '__main__':
    initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
    secret = make_mask(secret)
    mask = string2bits(secret)

    for b in secret: assert(b == '0' or b == '1')
    assert(len(secret) == 128)

    for i in range(256):
        state = initState[i:]
        output = lfsr(state, mask)
        initState += [output]

    outputState = bits2string(initState[128:])
    print('outputState =', outputState)

'''
outputState = 1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110
'''

老样子，先梳理题目加密流程：

题目把secret变为二进制列表后，作为掩码mask，flag由固定flag头尾及secret组成
给定LFSR的初始序列initState，与mask一样是一个长度为128的二进制列表
用LFSR生成256比特的流密码，并给出。要求我们反推出mask列表，从而求出secret

其中，LFSR的生成逻辑如下：

def lfsr(state, mask):
    assert(len(state) == 128)
    assert(len(mask)  == 128)

    output = 0
    for i in range(128):
        output = output ^ (state[i] & mask[i])

    return output

乍一看可能觉得不太好想，但是再一看，这不就是个GF(2)下的线性方程吗！这是因为：

state[i] & mask[i]，可以写成 state[i] * mask[i]
output = output ^ (state[i] & mask[i]) ，其实就是把128个乘积在GF(2)下求和

那么这样一来就好做了，把mask当作128个变量组成的列向量，取128个output，就能求解一个满秩的矩阵方程如下：

$\left( \begin{matrix} m_{1,1} & m_{1,2} &... &m_{1,128}\\ m_{2,1} & m_{2,2} &... &m_{2,128} \\ & &...\\ m_{127,1} & m_{127,2} &... &m_{127,128} \\ m_{128,1} & m_{128,2} &... &m_{128,128} \\ \end{matrix} \right)* \left( \begin{matrix} mask_1\\ mask_2 \\ ...\\ mask_{127} \\ mask_{128} \\ \end{matrix} \right) = \left( \begin{matrix} output_1\\ output_2 \\ ...\\ output_{127} \\ output_{128} \\ \end{matrix} \right) \quad(mod\;2)$

求完后转回字符串，再套上flag头尾即可。

exp：

from Crypto.Util.number import *

def bits2string(bs):
    s = [str(b) for b in bs]
    return ''.join(s)

def string2bits(s):
    return [int(b) for b in s]

outputState = "1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110"
initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]

c = string2bits(outputState[:128])
M = [initState[i:] + c[:i] for i in range(128)]
c = vector(GF(2),c)
m = matrix(GF(2),128,128,M)
secret = m.solve_left(c)
print(long_to_bytes(int(bits2string(secret),2)))

#0xGame{Rec0ver_the_M@sk}

[Week 2] What’s CRT?

题目描述：

1	先穿袜子后穿鞋，先当**后当爷

题目：

from Crypto.Util.number import *
from secert import flag

m = bytes_to_long(flag)
e = 260792700
q,p,q_,p_ = [getPrime(512) for _ in range(4)]
gift = [q+p,q_+p_]
n,n_ = q*p,q_*p_
mq_ = pow(m,4,q_)
mp_ = pow(m,4,p_)
c = pow(m,e,n)

print(f'mygift={gift}\nmq_={mq_}\nmp_={mp_}\nn={n}\nn_={n_}\nc={c}')
'''
mygift=[15925416640901708561793293991573474917595642805739825596593339102414328214313430010166125066639132916608736569443045051644173933089503934675628814467277922, 18342424676996843423829480445042578097182127446865571536445030052846412665700132683433441858073625594933132038175200824257774638419166516796318527302903098]
mq_=6229615098788722664392369146712291169948485951371133086154028832805750551655072946170332335458186479565263371985534601035559229403357396564568667218817197
mp_=7514598449361191486799480225087938913945061715845128006069296876457814528347371315493644046029376830166983645570092100320566196227210502897068206073043718
n=63329068473206068067147844002844348796575899624395867391964805451897110448983910133293450006821779608031734813916287079551030950968978400757306879502402868643716591624454744334316879241573399993026873598478532467624301968439714860262264449471888606538913071413634346381428901358109273203087030763779091664797
n_=84078907800136966150486965612788894868587998005459927216462899940718213455112139441858657865215211843183780436155474431592540465189966648565764225210091190218976417210291521208716206733270743675534820816685370480170120230334766919110311980614082807421812749491464201740954627794429460268010183163151688591417
c=12623780002384219022772693100787925315981488689172490837413686188416255911213044332780064192900824150269364486747430892667624289724721692959334462348218416297309304391635919115701692314532111050955120844126517392040880404049818026059951326039894605004852370344012563287210613795011783419126458214779488303552
'''

不管是题目标题CRT，还是题目描述暗示孙子定理，都是告诉我们这题要用中国剩余定理。

首先，根据题目给的条件，能够很轻松的求出p、q、p‘、q’几个参数。那么由于：

1 2	mq_ = pow(m,4,q_) mp_ = pow(m,4,p_)

可以先用中国剩余定理试一试。但是不行，那应该flag超长了，所以必须把p、q也用上。

而这个e是个偶数，是肯定和p-1,q-1都不互素的，又因为e比较小，所以扔上facrotdb上分解一下：

正好，他与phi的公因数也是4，因此把e拆开：

$(m^4)^{\frac{e}{4}} \equiv c \quad(mod\;n)$

然后求e/4对phi的逆元d，正常RSA解密就能得到：

$m^4 \equiv c^d \quad (mod\;n)$

此时，我们就拥有了关于m^4的三个等式：

$m^4 \equiv c^d \quad (mod\;n)$ $m^4 \equiv mp' \quad (mod\;p')$ $m^4 \equiv mq' \quad (mod\;q')$

中国剩余定理组合，开四次根就能得到flag。

exp：

from Crypto.Util.number import *
from gmpy2 import iroot
from sympy.ntheory.modular import crt

e = 260792700
gift=[15925416640901708561793293991573474917595642805739825596593339102414328214313430010166125066639132916608736569443045051644173933089503934675628814467277922, 18342424676996843423829480445042578097182127446865571536445030052846412665700132683433441858073625594933132038175200824257774638419166516796318527302903098]
mq_=6229615098788722664392369146712291169948485951371133086154028832805750551655072946170332335458186479565263371985534601035559229403357396564568667218817197
mp_=7514598449361191486799480225087938913945061715845128006069296876457814528347371315493644046029376830166983645570092100320566196227210502897068206073043718
n=63329068473206068067147844002844348796575899624395867391964805451897110448983910133293450006821779608031734813916287079551030950968978400757306879502402868643716591624454744334316879241573399993026873598478532467624301968439714860262264449471888606538913071413634346381428901358109273203087030763779091664797
n_=84078907800136966150486965612788894868587998005459927216462899940718213455112139441858657865215211843183780436155474431592540465189966648565764225210091190218976417210291521208716206733270743675534820816685370480170120230334766919110311980614082807421812749491464201740954627794429460268010183163151688591417
c=12623780002384219022772693100787925315981488689172490837413686188416255911213044332780064192900824150269364486747430892667624289724721692959334462348218416297309304391635919115701692314532111050955120844126517392040880404049818026059951326039894605004852370344012563287210613795011783419126458214779488303552

p = (iroot((gift[0]**2 - 4*n),2)[0] + gift[0])//2
q = n // p

q_ = (iroot((gift[1]**2 - 4*n_),2)[0] + gift[1])//2
p_ = n_ // q_

d = inverse(e//4,(p-1)*(q-1))
m = pow(c,d,n)

N = [n,p_,q_]
C = [m,mp_,mq_]
M = crt(N,C)[0]

print(long_to_bytes(iroot(M,4)[0]))

#0xGame{7881ed67088e9f72b860f8c376599785}

有一个小细节需要注意，如果你按这个方式一直出不来，那么可以检查一下p’、q’是否求反了，是有这个可能性的。

[Week 2] 中间的那个人

题目描述：

小爱(Alice)和小爆(Bob)现在在神秘的幻想乡中需要进行远程通话，但是他们又不希望中间传递的信息被心怀不轨的人窃取——很显然，他们的通话需要加密。但是在双方并未事先沟通好的情况下，他们要如何协商好密钥呢？

题目：

from secret import flag
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *

p = getPrime(128)
g = 2
A = getrandbits(32)
B = getrandbits(32)

Alice = pow(g,A,p)
Bob = pow(g,B,p)
key = pow(Alice,B,p)
key = sha256(long_to_bytes(key)).digest()

iv = b"0xGame0xGameGAME"
aes = AES.new(key, AES.MODE_CBC, iv)
enc = aes.encrypt(flag)
print(f'g={g}\np={p}')  #we tell
print(f'Bob={Bob}')     #Bob tell
print(f'Alice={Alice}') #Alice tell

print(f'enc={enc}')#Here is they secret

'''
g=2
p=250858685680234165065801734515633434653
Bob=33067794433420687511728239091450927373
Alice=235866450680721760403251513646370485539
enc=b's\x04\xbc\x8bT6\x846\xd9\xd6\x83 y\xaah\xde@\xc9\x17\xdc\x04v\x18\xef\xcf\xef\xc5\xfd|\x0e\xca\n\xbd#\x94{\x8e[.\xe8\xe1GU\xfa?\xda\x11w'
'''

一个典型的Diffie-Hellman密钥交换协议，其困难性依赖于离散对数在某些有限域下难以求解。但是观察题目生成有限域用的p较小而且较光滑，因此可以直接求解出离散对数，进而得到公用密钥key，然后AES解密即可。

exp：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *

g=2
p=250858685680234165065801734515633434653
Bob=33067794433420687511728239091450927373
Alice=235866450680721760403251513646370485539
enc=b's\x04\xbc\x8bT6\x846\xd9\xd6\x83 y\xaah\xde@\xc9\x17\xdc\x04v\x18\xef\xcf\xef\xc5\xfd|\x0e\xca\n\xbd#\x94{\x8e[.\xe8\xe1GU\xfa?\xda\x11w'

'''
A=discrete_log(mod(Alice,p),mod(g,p))
print(A)
'''
A = 3992780394

iv = b"0xGame0xGameGAME"
key = int(pow(Bob,A,p))
key = sha256(long_to_bytes(key)).digest()
aes = AES.new(key, AES.MODE_CBC, iv)
m = aes.decrypt(enc)

print(m)

#0xGame{51393fe1fd5fc2df1bf018d06f0fa11d}

[Week 2] EzRSA

题目描述：

1	三个小问题。一个定理、一个常见的分解方式、一个不太常见的连分数分解（啥事连分数？）

题目：

from challenges.challenge1 import RSAServe as challenge1
from challenges.challenge2 import RSAServe as challenge2
from challenges.challenge3 import RSAServe as challenge3
from secret import flag
import random
import os
import string
from hashlib import sha256
from string import ascii_uppercase
from random import shuffle,choice,randint
import os
import socketserver
import signal


SCORE = [0, 0, 0]
BANNER = """
 ____  ____    _    
|  _ \/ ___|  / \   
| |_) \___ \ / _ \  
|  _ < ___) / ___ \ 
|_| \_\____/_/   \_\

Here are four challenges(1, 2, 3), solve them all then you can get flag.
"""
MEMU = """
/----------------------------\\
|          options           |
| 1. get public key          |
| 2. get cipher text         |
| 3. check                   |
\\---------------------------/
"""

class Task(socketserver.BaseRequestHandler):
    def proof_of_work(self):
        '''验证函数'''
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def Serve(self, S):
        self.send(MEMU.encode())
        while True:
            option = self.recv()
            if option == b'1':
                pubkey = S.pubkey()
                for s in pubkey:
                    self.send(str(s).encode())
            elif option == b'2':
                c = S.encrypt()
                self.send(c.encode())
            elif option == b'3':
                usr_answer = self.recv(b"input your answer: ")
                return S.check(usr_answer)
            else:
                self.send(b"invaild option")

    def handle(self):
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(300)
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return
        self.send(BANNER.encode())
        while True:
            self.send(f'your score {sum(SCORE)}'.encode())
            if sum(SCORE) == 3:
                self.send(f"here are flag:{flag}".encode())
                break
            self.send(b'select challange{1,2,3}')#
            code = self.recv()
            if code == b'1':
                S = challenge1()
                res = self.Serve(S)
                if res == True:
                    SCORE[0] = 1
                    self.send(b'Conguration!You are right!')
            elif code == b'2':
                S = challenge2()
                res = self.Serve(S)
                if res == True:
                    SCORE[1] = 1
                    self.send(b'Conguration!You are right!')
            elif code == b'3':
                S = challenge3()
                res = self.Serve(S)
                if res == True:
                    SCORE[2] = 1
                    self.send(b'Conguration!You are right!')
            else:
                self.send(b'invaild input')


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10006
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

一个交互题，要实现的目标就是分别通过他的三个challenge，就可以拿到flag。

那么接下来就一个一个challenge分析。

challenge1

题目：

from Crypto.Util.number import *
from secret import flag1
import random

class RSAServe:
    def __init__(self) -> None:
        self.e = 65537
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.n = self.q*self.p
        self.g, self.r1 = [random.randint(1, self.q*self.p) for _ in range(2)]
        self.gift = pow(self.g, self.r1 * (self.p - 1), self.n)
        self.m = flag1

    def encrypt(self):
        m_ = bytes_to_long(self.m)
        c = pow(m_, self.e, self.p*self.q)
        return hex(c)

    def check(self, msg):
        return msg == self.m

    def pubkey(self):
        return self.p*self.q, self.e

题目会给出一个gift，如下：

$gift \equiv g^{r_1*(p-1)} \quad(mod\;n)$

那么先同余性质转到模p下，然后费马小定理即可：

$gift \equiv g^{r_1*(p-1)} \equiv 1 \quad(mod\;p)$

所以求gcd(gift-1,n)就能得到p，分解n后解密即可。

challenge2

题目：

from Crypto.Util.number import *
from secret import flag2
from random import choice

class RSAServe:
    def __init__(self) -> None:
        self.e = 65537
        self.m = flag2
        self.p = self.GetMyPrime(1024)
        self.q = self.GetMyPrime(1024)

    def GetMyPrime(self,bits):
        while True:
            n = 2
            while n.bit_length() < bits:
                a = choice(sieve_base)
                n *= a
            if isPrime(n + 1):
                return n + 1

    def encrypt(self):
        m_ = bytes_to_long(self.m)
        c = pow(m_, self.e, self.p*self.q)
        return hex(c)

    def check(self, msg):
        return msg == self.m

    def pubkey(self):
        return self.p*self.q, self.e

可以看出是p-1光滑，不多说了。

challenge3

from Crypto.Util.number import *
from secret import flag3
from random import choice
from sympy import *
class RSAServe:
    def __init__(self) -> None:
        self.e = 65537
        self.m = flag3
        self.p = getPrime(896)
        self.n1 = self.getN()
        self.n2 = self.getN()

    def getN(self):
        q = getPrime(128)
        self.p = nextprime(self.p)
        return q*self.p

    def encrypt(self):
        m_ = bytes_to_long(self.m)
        c = pow(m_, self.e, self.n2)
        return hex(c)

    def check(self, msg):
        return msg == self.m

    def pubkey(self):
        return self.n1, self.n2 , self.e

可以发现，题目的两个公钥n1、n2是按如下方式生成的：

$n1 = q1 * p1$ $n2 = q2 * nextprime(p1)$

可以看到，n1、n2有一个因数非常相近，几乎相等。那么我们把上面两式写成分式形式：

$\frac{n1}{n2} = \frac{q1}{q2} * \frac{p1}{nextprime(p1)}$

所以有：

$\frac{n1}{n2} \approx \frac{q1}{q2}$

因此将n1/n2进行连分数展开，就很有可能找到q1/q2这个收敛子。

完整交互

最后还需要把以上求解步骤全部写作交互下的(当然手动也行)，exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
import string
from hashlib import sha256

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("43.139.107.237",10006)

proof_of_work()

#chall1
if(1):
    temp = r.recvuntil(b"select challange{1,2,3}")
    r.sendline(b"1")
    r.recvuntil(b"-----------/")
    r.sendline(b"1")
    r.recvline()
    r.recvline()
    n = int(r.recvline().strip().decode()[2:])
    e = int(r.recvline().strip().decode())
    r.sendline(b"2")
    gift = int(r.recvline().strip().decode())
    c = int(r.recvline().strip().decode()[2:],16)
    p = GCD((gift - 1),n)
    q = n // p
    d = inverse(e,(p-1)*(q-1))
    m = pow(c,d,n)
    r.sendline(b"3")
    r.recvuntil(b"input your answer: ")
    r.sendline(long_to_bytes(m))
    print("Chall1 done!")


#chall2
if(1):
    temp = r.recvuntil(b"select challange{1,2,3}")
    r.sendline(b"2")
    r.recvuntil(b"-----------/")
    r.sendline(b"1")
    r.recvline()
    r.recvline()
    n = int(r.recvline().strip().decode()[2:])
    e = int(r.recvline().strip().decode())
    r.sendline(b"2")
    c = int(r.recvline().strip().decode()[2:],16)
    a = 2
    m = 2
    while True:
        a = pow(a, m, n)
        p = GCD(a-1, n)
        if p != 1 and p != n:
            break
        m += 1
    q = n // p
    phi = (p-1)*(q-1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    r.sendline(b"3")
    r.recvuntil(b"input your answer: ")
    r.sendline(long_to_bytes(m))
    print("Chall2 done!")


#chall3
if(1):
    #展开为连分数列表
    def continuedFra(x, y):
        cF = []
        while y:
            cF += [x // y]
            x, y = y, x % y
        return cF
    #将当前连分数列表计算成有理分数
    def Simplify(ctnf):
        numerator = 0
        denominator = 1
        for x in ctnf[::-1]:
            numerator, denominator = denominator, x * denominator + numerator
        return (numerator, denominator)
    #将连分数列表变成不同的有理数逼近列表
    def getit(c):
        cf=[]
        for i in range(1,len(c)):
            cf.append(Simplify(c[:i]))
        return cf

    temp = r.recvuntil(b"select challange{1,2,3}")
    r.sendline(b"3")
    r.recvuntil(b"-----------/")
    r.sendline(b"1")
    r.recvline()
    r.recvline()
    n1 = int(r.recvline().strip().decode()[2:])
    n2 = int(r.recvline().strip().decode())
    e = int(r.recvline().strip().decode())
    r.sendline(b"2")
    c = int(r.recvline().strip().decode()[2:],16)
    q1 = continuedFra(n1,n2)
    q1 = getit(q1)
    for a,b in q1[4:]:
        if(n2 % a == 0 and isPrime(a) and len(bin(a)) > 126):
            q2 = a
            p__ = n2 // q2
            break
    d = inverse(e,(p__-1)*(q2-1))
    m = pow(c,d,n2)
    r.sendline(b"3")
    r.recvuntil(b"input your answer: ")
    r.sendline(long_to_bytes(m))
    print("Chall3 done!")


#getflag
r.recvline()
r.recvline()
print(r.recvline())

#0xGame{a1425c9ce44989ffd64968130ee2f9fd}