Crypto趣题-Oracle

这篇文章主要记录一下有趣的交互题

rsa

题目来源：NCTF 2021

题目：

import socketserver
from Crypto.Util.number import *
import os
import signal
import string
import random
from hashlib import sha256
from secret import flag

class Task(socketserver.BaseRequestHandler):
    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 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'Give me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def handle(self):
        p = getPrime(512)
        q = getPrime(512)
        n = p*q
        e = 65537

        signal.alarm(120)
        self.send(b'Try to factor n within 120 seconds')
        self.send("n = {}\ne = {}".format(n, e).encode())
        self.send(b'And solve the proof-of-work below to begin the challenge.')

        if not self.proof_of_work():
            return

        signal.alarm(12)
        secret = os.urandom(16)
        for i in range(4):
            self.send("c{} = {}".format(i, pow(bytes_to_long(secret[4*i:4*i+4]), e, n)).encode())

        self.send(b"Give me the secret:")
        s = self.recv()
        if secret.hex().encode() == s:
            self.send(b"Congratulations! Your flag is: "+flag.encode())
        else:
            self.send(b"Wrong secret")
        self.request.close()


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


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


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

代码比较长，但是大多数是交互相关的代码，所以不用管，先把交互剥离掉来分析这个题。

脱离交互，单独分析

那么就不管靶机的其他交互流程，我们只看要解决的核心任务代码，在这里我把与靶机交互的部分简化成普通input、print等形式，然后展示出来：

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537

print(n)
print(e)

secret = os.urandom(16)
for i in range(4):
    print("c{} = {}".format(i, pow(bytes_to_long(secret[4*i:4*i+4]), e, n)).encode())

s = input("Give me the secret:")
if secret.hex().encode() == s:
    print(b"Congratulations! Your flag is: "+flag.encode())
else:
    print(b"Wrong secret")

代码的意思就是：

• 生成一组RSA的密钥p，q，n，e，并给出公钥(n，e)
• 随机生成 16 个字节，并切为4块，每组4个字节，作为待加密的明文
• 对每一组明文分别进行RSA加密，并给出密文
• 要求从4组密文还原出完整明文

首先很快就能明白，这里的n是没有办法分解的，因为没有任何关于p、q、d的泄漏信息。那么怎么还原出明文呢，就要注意到以下两点：

• 明文分成了4组，每组4个字节，也就是32bit，是个很小的明文
• 这题是个交互题

这两点分别有什么作用就是接下来要详细说明的地方。

首先要明白，这里的明文如果不分组，直接进行加密，那么其本质上就是一个纯粹的RSA加密，就当前的密码技术来说，我们如果没有私钥的话，自然没有任何机会还原出明文。

而分组最直观的效果，就是每一组被加密的明文变小了，那么也就说明可能有机会爆破！打个比方，如果你已知明文就是一个字节，那么他可能的范围也就在(0,256)之间，要还原明文，你只需要将(0,256)之间的所有数逐个进行加密。如果加密后的密文与给定的密文相等，那么对应的明文即为所求。

但是这个题目中明文即使分了组，每一组的明文仍然是个32bit的随机数，直接爆破还是不太现实的，因此需要采取一定方法。

那么我们需要注意到，这个32bit的随机数有很大概率是个合数，这是因为，在n个正整数中，质数出现的概率大约为：

$$\frac{1}{\ln n}$$

因此，对于n取2^32，其概率经计算大约是 0.045084220027780106，概率相当小。所以明文m大概率能写成两个整数的乘积形式：

$$m = i*j$$

而由于m是(0,2^32)之间的数，所以我们可以概率性的界定 i、j 两数的范围。

什么叫概率性的界定范围呢？比如说，i、j 都在(0,2^16)这个范围里，概率有多大？其实这个问题等价于m的因子全部小于2^16的概率，因此可以用如下的程序简单验证：

import os
from Crypto.Util.number import *
from tqdm import tqdm

count = 0    
for i in tqdm(range(1000)):        
    m = bytes_to_long(os.urandom(4))
    for j in range(2,2**16):
        while(m % j == 0):
            m //= j
    if(m == 1):
        count += 1
print(count/1000)

经计算概率大概在0.32左右，这说明什么，这说明m有0.32的概率写为两个(0,2^16)之间的数的乘积，这对我们的爆破有什么帮助呢？首先，加密过程就可以改写成：

$$m^e\equiv (i*j)^e \equiv i^e*j^e \equiv c\quad(mod\;n)$$

那么就有：

$$c^{-1}*j^e\equiv i^{-e}\quad (mod\;n)$$

此时你会发现，如果m能够写为(0,2^16)内的 i，j 两数的乘积的形式，那么类似于中间相遇攻击，我们就可以用如下方式爆破：

• 把所有(0,2^16)中的 $ i^{-e}\quad (mod\;n)$ 提前存储在一个字典内
• 接下来，只需要爆破(0,2^16)中的 j，验证 $ c^{-1}*j^e\quad (mod\;n)$ 在刚才的字典中，则对应的 i，j 乘积即为需求的明文

容易明白，这种攻击方式成功的概率，就等同于m能写为这样的 i，j 乘积的概率，也就是0.32左右。那么连续4次均成功，概率大约为:

$$(0.32)^4 = 0.01048576$$

因此，不考虑题目其他限制的话，每一次攻击大约有1%的概率成功，而可以用以下程序计算出，交互66次，就有大于50%的概率至少成功一次：

fre = 0.01048576
success = 1
count = 1
while(1):
    success *= (1-fre)
    if(success < 0.5):
        print(count)
        break
    count += 1

回到交互

但是实际上，这题对交互时间是有一定限制的：

• 从连接上靶机开始，计时120s，超时会退出
• 从完成proof_of_work开始，计时12s，超时会退出

而注意到我们连接上靶机后，靶机端就会发送给我们公钥(n，e)，而获得了(n，e)之后，我们就可以开始建立字典。一直到proof_of_work完成后，我们才需要进行字典的查询来搜索出4组明文。

也就是说，我们有更充足的时间建立字典，而查询字典的时间更有限。因此，我们要适当增大 i 的范围，但是对应的，搜索j的范围不能变小，仍然要考虑搜索2^16内的所有数。所以我们测试以下几种新的乘积划分：

$$i \in (0,2^{17}),j \in (0,2^{15})$$ $$i \in (0,2^{18}),j \in (0,2^{14})$$ $$i \in (0,2^{19}),j \in (0,2^{13})$$ $$i \in (0,2^{20}),j \in (0,2^{12})$$ $$i \in (0,2^{21}),j \in (0,2^{11})$$

经计算，几种划分对应的攻击成功概率依次是：0.36、0.45、0.52、0.55、0.62，理论上来说当然是越后面的划分越好，但是同时，建立字典的耗时也需要考虑进去。你可以用以下程序简单测试出，字典大小最大也就只能取到2^20，否则就会直接超出120s的限制：

import os
from Crypto.Util.number import *
from tqdm import tqdm

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
S = {pow(i,-e,n):i for i in tqdm(range(1,2**20))}

因此，思路就是：接收到公钥(n，e)后，建立一个大小为2^20的字典，然后再进行proof_of_work，进行完毕后开始查表。如此与靶机交互多次后，就有大概率得到flag。理论上来说八次就有大于50%的概率得到flag了，不过运气不好确实可能需要很久很久。

但同时你也可以注意到，m并不一定就是32bit的数，他的前几个bit完全可能是0，因此相信自己运气的话，可以适当缩小划分范围来节省耗时，比如划分为：

$$i \in (0,2^{19}),j \in (0,2^{12})$$ $$i \in (0,2^{18}),j \in (0,2^{12})$$

等等缩小后的范围，都是有可能成功的。

exp.py：

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
	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

while(1):
	r = remote("node5.anna.nssctf.cn",28803)

	#part1
	r.recvline()
	n = int(r.recvline().strip()[3:])
	e = 65537
	S = {pow(i,-e,n):i for i in tqdm(range(1,2**19))}
	proof_of_work()

	#part2
	secret = ""
	for i in range(4):
		c = int(r.recvline().split(b'=')[1].strip())
		inv_c = inverse(c,n)
		for j in range(1,2**16):
			s = inv_c*(pow(j,e,n))%n
			if(s in S):
				print(i)
				secret += hex(S[s]*j)[2:].zfill(8)
				break
	temp = r.recvline()
	r.sendline(secret.encode())
	temp = r.recvline()
	print(temp)
	r.close()
    
#flag暂时还没有，靶机有一点小问题

Lost Modulus

题目来源：SEETF 2022

题目：

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long

with open("flag.txt", "rb") as f:
    FLAG = f.read()

n = bytes_to_long(FLAG)

#make sure i have a big modulus
while n.bit_length() < 2048:
    n *= n

def encrypt(m1, m2):
    e = getPrime(256)
    assert m1.bit_length() >= 1600 and long_to_bytes(m1).startswith(b"SEE{"), 'first message must be at least 1600 bits and begin with "SEE{"'
    assert 500 <= m2.bit_length() <= 600, 'second message must be within 500 to 600 bits'

    return pow(m1, e, n), pow(m2, e, n)


def main():
    try:
        m1 = int(input("Message 1 (as integer) : ").strip())
        m2 = int(input("Message 2 (as integer) : ").strip())
        c1, c2 = encrypt(m1, m2)
        print(f"\nCiphers: \n{[c1,c2]}")
    except Exception as e:
        print(e)

if __name__ == '__main__':
    main()

梳理一下加密流程：

• 将flag转为大整数n，反复乘方直至n大于2048bit
• 允许我们输入两个整数m1、m2，要求满足：
• • m1转为字节串后要求以”SEE{“开头，并且大于1600bit
  • m2大小要在500-600bit之间
• 随机生成一个256bit的素数e，并使用公钥(n,e)对m1、m2分别进行RSA加密，并给出密文

题目要求我们恢复模数n，而有关模数的恢复一般都会用到gcd。因此本题的关键就在于如何利用被限制了的明文m1、m2，构造出模数n的倍数。

首先观察到，m1的二进制长度可以为m2的三倍以上，也就是说，我们可以利用立方关系进行构造。而如何构造出m1恰为一个数的3次方，并且开头还是”SEE{“呢？很容易，只需要先构造出一个符合条件的m1，然后开立方根，取整作为m2，再取m2的立方作为新的m1即可。这是因为，开立方根、取整后再立方回来，对m1的影响均在低位，不会影响到其高位的”SEE{“

所以此时我们就有明文关系如下：

$$m_1^e \equiv (m_2^3)^e \equiv c_1\quad (mod\;n)$$ $$m_2^e \equiv c_2\quad (mod\;n)$$

所以有：

$$c_2^3-c_1 = kn$$

因此多连接几次靶机，取多组kn后求解gcd，就能去除小因子得到n，再爆破具体是m的几次方即可。

exp.py：

from Crypto.Util.number import *
from pwn import *
import os
from gmpy2 import iroot

def gen():
    m1 = bytes_to_long(b"SEE{" + os.urandom(200))
    m2 = iroot(m1,3)[0]
    m1 = m2**3
    return (m1,m2)

kn = []
for i in range(4):
    r = remote("node4.anna.nssctf.cn",28625)
    m1,m2 = gen()
    temp = r.recvuntil(b"Message 1 (as integer) : ")
    r.sendline(str(m1).encode())
    temp = r.recvuntil(b"Message 2 (as integer) : ")
    r.sendline(str(m2).encode())
    temp = r.recvuntil(b"Ciphers:")
    c = eval(r.recvuntil("]").decode())
    c1 = c[0]
    c2 = c[1]
    kn.append(c2**3-c1)
    r.close()
n = kn[0]
for i in kn[1:]:
    n = GCD(n,i)
for i in range(2,10):
    if(iroot(n,i)[1] == True):
        print(long_to_bytes(iroot(n,i)[0]))

#NSSCTF{1affebef-9c23-45f1-b88e-406f9611c614}

welcomesigner2

题目来源：WMCTF 2023

题目：

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

flag = b"***********************************"
def pad(message):
    return message + b"\x00"*((16-len(message)%16)%16)


def myfastexp(m,d,N,j,N_):
    A = 1
    B = m
    d = bin(d)[2:][::-1]
    n = len(d)
    N = N
    for i in range(n):
        if d[i] == '1':
            A = A * B % N
        #  a fault occurs j steps before the end of the exponentiation
        if i >= n-1-j:
            N = N_
        B = B**2 % N
    return A


def encrypt(message,key):
    key = bytes.fromhex(md5(str(key).encode()).hexdigest())
    enc = AES.new(key,mode=AES.MODE_ECB)
    c   = enc.encrypt(pad(message))
    return c


border = "|"
print(border*75)
print(border, "Hi all, I have another algorithm that can quickly calculate powers. ", border)
print(border, "But still there's something wrong with it. Your task is to get      ", border)
print(border, "its private key,and decrypt the cipher to cat the flag ^-^          ", border)
print(border*75)


while True:
# generate
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    e = 17
    if GCD(e,(p-1)*(q-1)) == 1:
        d = inverse(e,(p-1)*(q-1))
        n_ = n 
        break
n_ = n
msg = bytes_to_long(b"Welcome_come_to_WMCTF")
sig = pow(msg,d,n)
assert sig == myfastexp(msg,d,n,0,n_)
CHANGE = True
while True:
    try:
        ans = input("| Options: \n|\t[G]et data \n|\t[S]ignatrue \n|\t[F]ault injection \n|\t[Q]uit\n").lower().strip()
        
        if ans == 'f':
            if CHANGE:
                print(border,"You have one chance to change one byte of N. ")
                temp,index = input("bytes, and index:").strip().split(",")
                assert 0<= int(temp) <=255
                assert 0<= int(index) <= 1023 
                n_ = n ^ (int(temp)<<int(index))
                print(border,f"[+] update: n_ -> \"{n_}\"")
                CHANGE = False
            else:
                print(border,"Greedy...")
        elif ans == 'g':
            print(border,f"n = {n}")
            print(border,f"flag_ciphertext = {encrypt(flag,d).hex()}")
        elif ans == 's':
            index = input("Where your want to interfere:").strip()
            sig_ = myfastexp(msg,d,n,int(index),n_)
            print(border,f"signature of \"Welcome_come_to_WMCTF\" is {sig_}")
        elif ans == 'q':
            quit()
    except Exception as e:
        print(border,"Err...")
        quit()

我觉得很有意思的一个错误注入题目，在这里记录一下思路。

首先梳理题目任务，在连接上靶机后，题目随机生成长度为512比特的素数p、q，并以p、q、e=17生成RSA加解密的剩余参数n、d。同时生成一个n_，在开始时其值与n相等。

然后，题目以一个已知的msg计算了其正确解密值pow(msg,d,n)作为sig，然后进入交互环节。

靶机提供的操作有:

• 输入”f”，可以更改模数n的任意8比特为自定义值，并且该操作在全程仅能进行一次
• 输入”g”，可以获得正确的初始模数n，并获得AES加密后的flag值，其中AES的密钥为私钥d
• 输入”s”，可以指定位置进行一次错误注入，错误注入具体是怎样的稍后讲
• 输入”q”，退出交互

所以我们要完成的任务是：改变n的某8个比特，使其更容易被我们利用；并使用题目提供的错误注入操作还原私钥d，之后AES解密密文。

那么主要问题就有两个：

• 如何改变n？
• 如何利用错误注入还原d？

接下来就开始题目分析。首先会介绍一点前置知识。

快速幂

题目提供的错误注入就是基于快速幂的，因此要完成题目先要知道快速幂的基本原理。

首先，如果按正常思路进行模幂运算，那么如果要计算pow(c,d,n)，就需要先令m = c，然后进行d次下列运算：

$$m = m*c \quad (mod\; n)$$

而如果d的数量级较大，这种运算的效率是不可接受的，因此需要应用快速幂。

快速幂的基本思想是：先把幂次转为二进制表示，在这里我们举个简单例子，假设d = 23，那么就有其二进制为：

$$bin(d) = 10111$$

而c的d次方模n其实就可以利用二进制转化为如下运算：

$$m = (1*c) * (1*c^2) * (1*c^{2^2}) * (0*c^{2^3}) * (1*c^{2^4}) \quad(mod\;n)$$

其中，每一项的系数是d的二进制逆过来后对应位置的值，乘数是c的对应次平方。这样做为什么减少了次数呢？这是因为c的对应次平方，只需要在前一个c的对应次平方的基础上再做一次平方就好。因此，用快速幂可以把模幂运算的复杂度减少到logn的数量级。其代码形式用直观一点的方式实现如下：

def myfastexp(c,d,n):
    d = bin(d)[2:][::-1]
    m = [c]
    temp = c
    for i in range(len(d)-1):
        temp = temp ** 2 % n
        m.append(temp)
    final = 1
    for i in range(len(d)):
        if(d[i] == "1"):
            final = final * m[i] % n
    return final

这个函数中m数组存放c的各次平方的数值，然后与b的二进制逆序对应相乘，最终返回pow(c,d,n)的计算值，与我们刚才说的过程完全相同。而更一般的，会写成如下形式：

def normal_fastexp(c,d,n):
    d = bin(d)[2:][::-1]
    final = 1
    for i in range(len(d)):
        if(d[i] == "1"):
            final = final * c % n
        c = c**2 % n
    return final

只是精简了代码，实际进行的操作依然是完全相同的。

错误注入

了解了快速幂后，再来看题目提供的错误注入代码：

def myfastexp(m,d,N,j,N_):
    A = 1
    B = m
    d = bin(d)[2:][::-1]
    n = len(d)
    N = N
    for i in range(n):
        if d[i] == '1':
            A = A * B % N
        #  a fault occurs j steps before the end of the exponentiation
        if i >= n-1-j:
            N = N_
        B = B**2 % N
    return A

可以发现，我们可以提供一个错误注入位置，在快速幂运算到错误注入位置之前，其模数是正确的n；而快速幂运算到错误注入位置的时候，模数会改变为我们改变了一个字节的n_，并且在之后都按照这个被改变的模数进行快速幂。

我们假设d为1023比特，其二进制序列为1xxx…xxxx，我们当前提供的注入位置是0，我们画一下题目的错误注入如何得到结果：

注意到到错误注入位置时，题目的快速幂仍然是先计算乘，再改变模数，也就是说，注入位置为0时，最后的结果其实是正确结果。而图中的红色部分就是由于错误注入、模数改变导致的m的对应次方幂计算错误，在这里，红色部分等于：

$$(m^{2^{1021}})^2 \quad (mod\;n')$$

n’就是n_，因为我的hexo转义有问题，公式块里一直打不出下划线，所以用n’代替。

那么当注入位置是1时，得到的结果如下：

此时可以发现，在计算最后一次快速幂的结果时，我们错误的使用了n_而非n下的m对应次方，因此结果产生了错误。而这个错误结果可以写成如下形式：

$$sig' = fault * right$$

right指快速幂在注入位置及之前的正确结果，fault指在注入位置之后的错误结果，他们是可以以乘积形式体现在最终结果里的。我们以此为依据把d的二进制串分为高位dhigh和低位dlow，则right等于：

pow(m,int(dlow,2),n)

fault等于：

pow(Bad,int(dhigh,2),n_)

其中，Bad就是由于错误注入产生的错误m的对应次方幂，也就是倒数第二个红色块的模n’下的平方。而这个值是可以计算出来的，因为我们拥有d的高位1、n’以及m；而我们又拥有靶机返回的sig’，因此我们可以用之前的等式计算出right在模n下的值。

用处在哪里呢？我们继续往后推进一位：

那么假设d的第二高位为0，那么就有：

int(dhigh,2) = 2*int(dhigh,2)
int(dlow,2) = int(dlow,2)

那么由于dlow不变，所以这一次我们计算出的right应该与前一次相等，而如果不等，就说明d的第二高位为1.

以此类推，我们就能还原出d的所有二进制位。

需要注意的是，d不一定是1023位，因此可能需要多次连接靶机，直到随机到某次d是1023位时才能正确解密。而之所以选择1023，是因为测试下来d是1023比特概率最大，能达到40%左右，因此成功率最大。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from Crypto.Cipher import AES
from hashlib import md5

def decrypt(message,key):
    key = bytes.fromhex(md5(str(key).encode()).hexdigest())
    enc = AES.new(key,mode=AES.MODE_ECB)
    c   = enc.decrypt(message)
    return c

#context.log_level = 'debug'
while(1):
    r = remote("node5.anna.nssctf.cn",28015)


    #part1 get c,n
    r.recvuntil(b"[Q]uit")
    r.sendline(b"g")
    r.recvuntil(b"n =")
    n = int(r.recvline().strip().decode())
    r.recvuntil(b"flag_ciphertext =")
    c = long_to_bytes(int(r.recvline().strip().decode(),16))


    #part2 get n_
    change_byte = 0
    ind = 0
    find = 0
    for temp in range(256):
        if(find):
            break
        for index in range(1024):
            n_ = n ^ (temp<<index)
            if isPrime(n_):
                change_byte = temp
                ind = index
                find = 1
                break

    sendnum = str(change_byte) + "," + str(ind)
    r.recvuntil(b"[Q]uit")
    r.sendline(b"f")
    r.recvuntil(b"and index:")
    r.sendline(sendnum.encode())
    r.recvuntil(b"n_ -> ")
    n_ = int(r.recvline().strip().decode()[1:-1])


    #part3 get d
    len_d = 1023
    def getm(m,n,n_):
        final = []
        c = m
        for i in range(len_d):
            final.append(c)
            c = c**2 % n
        return final
    msg = bytes_to_long(b"Welcome_come_to_WMCTF")
    m = getm(msg,n,n_)

    def getd(d,siglist,n_,m):
        for i in trange(1,len_d-1):
            current = siglist[i]
            inv_Bad = inverse(pow(m[len_d-1-i]**2%n_,int(d,2),n_),n_)
            cur = current * inv_Bad % n_
            
            nextsig = siglist[i+1]
            next_inv_Bad = inverse(pow(m[len_d-2-i]**2%n_,2*int(d,2),n_),n_)
            inv_next = nextsig * next_inv_Bad % n_

            if(inv_next == cur):
                d += "0"
            else:
                d += "1"
        return d

    siglist = []
    for i in trange(len_d):
        r.recvuntil(b"[Q]uit")
        r.sendline(b"s")
        r.recvuntil(b"interfere:")
        index = i
        r.sendline(str(index).encode())
        r.recvuntil(b" is ")
        sig_ = int(r.recvline().strip().decode())
        siglist.append(sig_)

    init_d = "1"
    d = getd(init_d,siglist,n_,m) + "1"
    d = int(d,2)


    #part4 getflag
    if(b"NSSCTF" in decrypt(c,d)):
        print(decrypt(c,d))
        break
    r.close()

#NSSCTF{f89d3e5c-138b-4d6d-8da9-cbe1a9dad5cd}

其中，选择一个素数n_是为了保证计算出逆元。

而另一道WMCTF的welcomesigner1，其实也是异曲同工，变化非常小，可以尝试练习。

signature

题目来源：EIS 2019

题目：

#!/usr/bin/env python3
# coding=utf-8

import binascii
import os
import random
import signal

def b2n(b):
    res = 0
    for i in b:
        res *= 2
        res += i
    return res

def n2b(n, length):
    tmp = bin(n)[2:]
    tmp = '0'*(length-len(tmp)) + tmp
    return [int(i) for i in tmp]

def s2n(s):
    return int(binascii.hexlify(s), 16)

def sign(msg):
    msg = n2b(s2n(msg), len(msg)*8)
    msg += b1
    for shift in range(len(msg)-64):
        if msg[shift]:
            for i in range(65):
                msg[shift+i] ^= b2[i]
    res = msg[-64:]
    return b2n(res)

b1 = n2b(0xdeadbeeffeedcafe, 64)
b2  = n2b(0x10000000247f43cb7, 65)

if __name__ == '__main__':
    signal.alarm(60)
    with open('/home/ctf/flag', 'r') as f:
        flag = f.read()

    try:
        print("Welcome to the Signature Challenge!")
        raw = os.urandom(256)
        pos = random.randint(0, 248)
        raw_hex = bytearray(binascii.hexlify(raw))
        for i in range(8):
            raw_hex[(pos+i)*2] = ord('_')
            raw_hex[(pos+i)*2+1] = ord('_')
        raw_hex = bytes(raw_hex)
        print(f"Here is the message: {raw_hex.decode('ascii')}")
        ans = input("Please fill the blank: ")
        ans = bytes.fromhex(ans)
        assert len(ans) == 8

        raw = bytearray(raw)
        for i in range(8):
            raw[pos+i] = ans[i]
        raw = bytes(raw)
        if sign(raw) == 0x1337733173311337:
            print(f"Great! Here is your flag: {flag}")
        else:
            print(f"Wrong! Bye~")
    except Exception:
        print("Error!")

题目的前几个函数无非就是字节流与数字、数字与二进制、二进制与列表的转化，稍微看看传递参数以及返回值就好。接下来主要分析题目任务：

• 连接上靶机后，开始限时60s
• 靶机随机生成256字节raw，并将其转为16进制字符串，然后随机生成一个0-248的位置pos
• 将16进制串中以pos开头的连续十六个字符以”_”代替，相当于抹掉了十六个十六进制字符
• 靶机发送抹掉后的十六进制串给我们，我们可以在抹掉的位置填充上16个十六进制字符
• 靶机会将经我们填充后的十六进制串转化为字节，并进行sign操作，如果sign操作得到的结果为0x1337733173311337，则得到flag

那么主要要关注的就是这个sign函数到底对msg进行了什么操作：

• 将传入的字节流msg转化为二进制列表，并在后面连接上b1的二进制列表
• 对上述二进制列表的msg对应部分进行遍历。如果当前位置为1，则将以该位置开头的65位二进制与b2进行异或
• 遍历完成后，b1对应位置的二进制串转为数字，作为sign的返回值

而可以发现，这个sign的过程完全是可以逆推回去的。比如，连接上b1后的二进制列表的最后一位，最多只异或了一次，倒数第二位最多只异或了两次，依此类推。而最后一次异或是否进行，可以由b1的最后一个二进制位是否与目标0x1337733173311337的最后一个二进制位相等来判断。如果不相等说明进行了异或，就把最后六十五个二进制位与b2对应异或回去；相等则不用管。

那么我们就完成了对最后一位二进制的处理，然后将处理过后得到的倒数第二个二进制位看作需要处理的最后一个二进制位，问题就转化为了刚才的问题，依次类推就可以得到填充部分的值。

然而，解出来的填充部分仍然会受到填充部分之前字节异或的影响，因此还需要处理一下。但是有一个比较简单的办法：由于pos是0-248的随机数，因此我们可以反复连接靶机，随机到pos为0时就不需要再进行额外处理了。并且由生日攻击的思想可以知道，连接248次就有大于50的概率随机到至少一次pos为0，也并不费什么时间。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *

def b2n(b):
    res = 0
    for i in b:
        res *= 2
        res += i
    return res

def n2b(n, length):
    tmp = bin(n)[2:]
    tmp = '0'*(length-len(tmp)) + tmp
    return [int(i) for i in tmp]

def s2n(s):
    return int(binascii.hexlify(s), 16)

def sign(msg):
    msg = n2b(s2n(msg), len(msg)*8)
    msg += b1
    for shift in range(len(msg)-64):
        if msg[shift]:
            for i in range(65):
                msg[shift+i] ^= b2[i]
    res = msg[-64:]
    return b2n(res)

def calc(msg):
    final = "0000000000000000" + msg[16:] + "deadbeeffeedcafe"
    aim = "1337733173311337"
    length = len(final)*4
    temp = n2b(int(final,16),length)
    aim = n2b(int(aim,16),length)

    for i in trange(length-1,64-1,-1):
        if(temp[i] != aim[i]):
            for j in range(65):
                aim[i-j] ^= b2[-j-1]

    for i in range(len(aim)):
        aim[i] = str(aim[i])

    tt = hex(int("".join(aim),2))[2:]
    return tt[:16]

b1 = n2b(0xdeadbeeffeedcafe, 64)
b2 = n2b(0x10000000247f43cb7, 65)
b3 = n2b(0x1337733173311337, 64)

for i in trange(1000):
    r = remote("node4.anna.nssctf.cn",28634)
    r.recvuntil(b"message: ")
    msg = r.recvline().strip().decode()
    if(msg[0] != "_"):
        r.close()
        continue
    r.recvuntil(b"blank: ")
    print(msg)
    r.sendline(calc(msg))
    print(r.recvline())
    break

#NSSCTF{9e8b2a1a-ad77-4ef3-a161-2f8693c7a0ac}

give you hand!

题目来源：暂不明确

题目：

import gmpy2
from Crypto.Util.number import *
import random

from secret import flag

p = getPrime(1024)
q = getPrime(1024)
phi = (p-1)*(q-1)
n = p*q

g = random.randint(2, n-1)

round = 10
E = 1
print(f'n = {n}')
print('give you hand!')
for i in range(round):
    while True:
        e = random.randint(3, 2**128)
        if gmpy2.gcd(e, phi) == 1:
            break
    d = gmpy2.invert(e, phi)
    print(e, pow(g,d,n))
    E *= e
print('give me fight!')
C = int(input('> ').strip())
if pow(C, E, n) == g:
    print('Pa!!!!')
    print(flag)
else:
    print('Wrong!')

较早之前别的师傅问我的一个题目，觉得还是有记录一下的价值。

连接上靶机后，靶机生成随机大素数p、q，并计算其乘积n。之后取一个2到n-1的随机数g。

然后题目正式开始，进行一个共计十轮的操作，每一轮给出的操作以及数据分别是：

• 生成一个随机加密指数e，保证e和phi互素后，生成对应的解密指数d
• 给出每一轮的e，以及g^d模n的值

十轮数据发放完毕后，题目要求我们输入一个C，如果C满足以下条件就能得到flag：

$$C^{e_1e_2...e_{10}} \equiv g \quad(mod\;n)$$

首先可以发现g是可以求的，我们只需要任取一轮ei和g^di，计算下式就可以得到g：

$$(g^{d_i})^{e_i} \equiv g \quad(mod\;n)$$

有了g过后，如果我们能有每一轮的d，那么我们我们就可以取如下的式子作为C，这个C显然满足题目要求。：

$$C = g^{d_1d_2...d_{10}}$$

但是每一轮的d真的能够求解吗？整理一下我们的已知条件，其实我们只有十轮如下值：

$$e_i,g^{d_i}$$

可以看出，虽然指数位置有不同，但是要用这两个条件求出d的话，其实这和已知密文和公钥，求RSA私钥没什么区别，都依赖于n的分解。而由于是靶机题，可以反复交互，因此我冒出的第一个想法是：有没有机会反复与靶机交互，刷出一个p-1光滑的p使得n易分解？但是显然这里的p、q作为1024比特的素数，对于这种方法来说太不现实了。所以要另作考虑。

然后我的思路就是，其实并不需要知道每个d，我们只需要知道 $ g^{d_1d_2…d_{10}} $ 的值。那么也就是说，我们现在要考虑的是：已知g^d1、g^d2，能否求出g^d1d2。毕竟只要能这样求出一组，那么就能这样反复构造出g^d1d2…d10。

乍一看，这个问题好像就是个CDH问题，不太明白这个问题的可以参考：

密码学常见困难问题DLP,CDH,DDH,GDH,BDH,CBDH,DBDH,GBDH，更新中_密码学ddh_song_qing_8的博客-CSDN博客

而CDH是计算困难的，目前没有有效的办法解决这个问题。然而，这一题相比于CDH问题而言，多了一些额外的条件，也就是每一轮的加密指数ei的值。这能否帮助我们解决这个问题？

其实共模攻击就可以，这里就以已知g^d1、g^d2，求出g^d1d2为例。我们有以下两组式子：

$$(g^{d_1})^{e_1} \equiv g \quad(mod\;n)$$ $$(g^{d_2})^{e_2} \equiv g \quad(mod\;n)$$

时刻记住我们的目的是求出g^d1d2，而我们要利用共模攻击，就要把g^d1d2当作m，所以把上面两式按如下方式变形一下：

$$(g^{d_1d_2})^{e_1} \equiv g^{d_2} \quad (mod\;n)$$ $$(g^{d_1d_2})^{e_2} \equiv g^{d_1} \quad (mod\;n)$$

这样就跟共模攻击完全对应上了。把g^d1d2看作待求的m，c1=g^d1,c2=g^d2，以及两个加密指数e1、e2均是给定了的，因此就可以共模求出g^d1d2。

求出g^d1d2后，剩下的同理进行迭代即可。比如继续求g^d1d2d3的步骤如下：

$$(g^{d_1d_2d_3})^{e_1e_2} \equiv g^{d_3} \quad(mod\;n)$$ $$(g^{d_1d_2d_3})^{e_3} \equiv g^{d_1d_2} \quad(mod\;n)$$

同理进行共模即可。如此反复就能求出g^d1d2…d10的值，也就是我们需要传给靶机的C了。

而这里需要注意一些小细节。我们刚才的分析是基于10轮ei全部互素，才能共模攻击成功的。如果交互发现不成功，多和靶机连接几次，刷出一组满足要求的ei就行。

而有没有一种对于任意ei都能求出来的办法？我思考了一下这个问题，如果仍然是基于共模攻击的思路的话，倘若存在ei、ej不互素的情况，那么对这一次共模攻击，有：

$$se_i + te_j = k$$

其中k是ei、ej的最大公约数。那么我们求出来的应该是：

$$g^{kd_1d_2...d_{10}} = (g^{d_1d_2...d_{10}})^k$$

那么要得到C，就需要求这个值模n下的k次剩余。而这就又依赖于n的分解，所以我认为ei存在不互素的情况下这题是无法求解的，所以才设计为靶机题以方便多次交互刷数据。

这题就没有exp了，因为我只有问我的师傅给我的附件，而没有靶机交互环境。

Calm Down

题目来源：HKCERT CTF 2020

题目描述：

I am so excited having a chance talking to Alice. She told me to calm down - and sent me an encrypted secret.

题目：

import base64
import binascii
import hashlib
import os
import random
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes

from secret import message

class RSAKey:
    def __init__(self, e, d, n):
        self.e = e
        self.d = d
        self.n = n

    def encrypt(self, message):
        message = bytes_to_long(message)
        ciphertext = pow(message, self.e, self.n)
        return long_to_bytes(ciphertext)

    def decrypt(self, ciphertext):
        ciphertext = bytes_to_long(ciphertext)
        message = pow(ciphertext, self.d, self.n)
        return long_to_bytes(message)


class Challenge:
    def __init__(self, message):
        self.generate_key()
        self.message = message

    def generate_key(self):
        key = RSA.generate(2048)
        self.key = RSAKey(key.e, key.d, key.n)

    def get_public_key(self):
        n = base64.b64encode(long_to_bytes(self.key.n)).decode()
        print(f'[pkey] {n}')

    def get_secret_message(self):
        ciphertext = self.key.encrypt(self.message)
        ciphertext = base64.b64encode(ciphertext).decode()
        print(f'[shhh] {ciphertext}')

    def send(self, ciphertext):
        ciphertext = base64.b64decode(ciphertext)
        message = self.key.decrypt(ciphertext)
        if message[-1:] != b'.':
            raise Exception('Be polite. Your message should terminate with a full-stop.')
        print('nice')

def main():
    c = Challenge(message)

    while True:
        command = input('[cmd] ').split(' ')

        try:
            if command[0] == 'send':
                c.send(command[1])
            elif command[0] == 'pkey':
                c.get_public_key()
            elif command[0] == 'read':
                c.get_secret_message()
        except:
            print('nope')

if __name__ == '__main__':
    main()

题目提供了几个交互功能：

• 输入”pkey”，可以获得RSA的公钥n(e是默认的65537)
• 输入”read”，可以获得flag的RSA加密密文
• 输入”send”，可以在后面继续输入一个密文，并且获得一个关于解密结果的信息：该解密值是否以”.”结尾

而我们拥有无限次交互次数，所以我们需要合理利用这几个交互功能，去想办法得到flag的明文。

而稍加思考就知道，pkey和read命令我们用一次就够了，不会有更多额外信息。真正有用的是send——他可以泄露出关于解密密文的最后一字节的相关消息，因此我们要反复利用send。这个时候就可以联想到关于RSA oracle的LSB攻击，在那里，我们可以构造如下形式的密文让oracle解密：

$$a^ec \quad(mod\;n)$$

这个密文解密的结果为：

$$am \quad(mod\;n)$$

而这个解密值就给我们提供了不少信息，比如我们可以取a=2^k，这样可以返回密文的奇偶性对明文m的范围进行二分搜索之类。

而在这一题目中，首先可以直接发送c给靶机，会发现返回的信息是”nice”，这说明明文本身是以”.”结尾的。这就给我们提供了很大的操作空间。我们通过刚才构造密文相似的思路，通过移位的方式保解密结果的最后一字节恒为”.”，从而构造出如下的密文序列发送给靶机：

$$(256(2^k) + 1)^ec \quad(mod\;n)$$

而之所以解密结果最后一字节恒为”.”，是因为解密结果是：

$$256(2^k)m + m \quad(mod\;n)$$

这相当于：

$$(m << (8+k)) + m \quad(mod\;n)$$

所以最后一字节不受影响，依然等于flag的最后一字节也就是”.”，因此靶机会一直返回nice。但是显然返回nice需要一个条件：解密结果小于n！

这给我们提供了一个信息：当解密结果首次大于n时，靶机端大概率不会返回nice(之所以不说死，是因为确实可能模了n后最后一字节还刚好为”.”)，此时我们就可以得到：

$$(256(2^{k})+1)m > n$$ $$(256(2^{k-1})+1)m < n$$

而如果我们能找到一个si，使得解密结果恰好大于n，此时有：

$$(256s_i+1)m = n + res$$ $$(256(s_i-1)+1)m < n$$

注意这里sk-1中的-1是确确实实的减去一这个数值，而不是在下标上，此时res是一个较小值，所以我们可以直接整除得到m，也就是flag值：

$$m = flag = \frac{n}{256s_i+1}$$

所以现在的问题就在于如何精确的找到这个si，而由刚才的结果我们知道si落在了如下范围中：

$$(2^{k-1},2^{k})$$

因此我们在这个小范围内二分查找即可得到si。

exp：

from Crypto.Util.number import *
from gmpy2 import powmod
from pwn import *
from base64 import *

r = remote("archive.cryptohack.org",53580)

#part1 get n,e,c
r.sendline(b"pkey")
r.recvuntil(b"[pkey]")
n = bytes_to_long(b64decode(r.recvline().strip().decode()))

r.sendline(b"read")
r.recvuntil(b"[shhh]")
c = bytes_to_long(b64decode(r.recvline().strip().decode()))
e = 65537

#part2 get first_range of m
x = 1
while(1):
    msg = powmod((256*x + 1),e,n)*c % n
    msg = long_to_bytes(msg)
    r.sendline(b"send " + b64encode(msg))
    if(b"nice" in r.recvline()):
        x *= 2
    else:
        break
print("Part1 Done!")

#part3 get final_range of m
L = x // 2
R = x
while(1):
    if(x == (L+R) // 2):
        break
    x = (L + R) // 2
    msg = powmod((256*x + 1),e,n)*c % n
    msg = long_to_bytes(msg)
    r.sendline(b"send " + b64encode(msg))
    if(b"nice" in r.recvline()):
        L = x
    else:
        R = x 

flag = n // (256*x + 1)
print(long_to_bytes(flag))

#hkcert20{c4lm_d0wn_4nd_s0lv3_th3_ch4llen9e}.

爆破时间比较长。做出题目后又想了一下，其实直接在(0,2^2048)的范围内直接二分应该也可以，就用不着第一步了，第一步更大的意义在于明确构造形式。

babyDLP

题目来源：祥云杯 2022

题目：

import socketserver
from time import sleep
from secret import flag
import signal
import random 

from Crypto.Util.number import *
import random

def pow_d(g, e, n):
	t, r = 0, 1
	for _ in bin(e)[2:]:
		if r == 4: t += 1
		r = pow(r, 2, n)
		if _ == '1': r = r * g % n
	return t, r

def ts(m, p):
	m = m % p
	return pow(m, (p - 1) // 2, p) == 1
class Task(socketserver.BaseRequestHandler):
    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):
        return self._recvall()
        



    def handle(self):
        border = b"|"
        self.send(border*72)
        self.send(border+b"Solve a DLP challenge in some special way to get the flag", border)

        p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
        s = random.randint(2, (p - 1) // 2)

        while True:
            self.send(b"| Options: \n|\t[T]ry the magic machine \n|\t[Q]uit")
            ans = self.recv().lower()

            if ans == b't':
                self.send(border+b"please send your desired integer: ")
                g = self.recv()
                try:
                    g = int(g)
                except:
                    self.send(border+b"The given input is not integer!")
                    break 
                sleep(0.3)
                if ts(g, p):
                    t, r = pow_d(g, s, p)
                    if r == 4:
                        self.send(border+b'Great! you got the flag:'+flag)
                    else:
                        self.send(border+b"t, r = "+f"{t, r}".encode())
                else:
                    self.send(border+"The given base is NOT valid!!!")
            elif ans == b'q':
                self.send(border+"Quitting ...")
                break 
            else:
                self.send(border+"Bye bye ...") 
                break 
                
                






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


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


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

题目名字是DLP，但是其实做完觉得和交互关系更大，就把题目放在oracle这篇了。还是先简单介绍下题目流程。

连接上靶机后，题目生成一个素数p以及一个随机数s：

p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
s = random.randint(2, (p - 1) // 2)

在生成这两个数后，靶机提供给我们一个如下形式的交互：

• 可以输给靶机一个整数g，靶机会用快速幂计算出 $g^s \;(mod\;p)$的值，记这个值为r
• 如果r=4，则得到flag
• 否则靶机返回t、r，其中t的值表示快速幂的计算过程中有没有得到过4这个数字

可以想见，如果DLP易求的话过程就很简单，就只需要随便送一组数据然后求出s，并计算$g = 4^{s^{-1}}$然后发送给靶机就行。然而可以发现，题目给的p是一个2q+1型的素数，虽然可以变成有限域下的DLP，但是数量级实在太大了，也没办法利用cado-nfs来解决。总而言之，DLP是没有办法求出来的。

所以要解决这个题的关键就是找出额外信息t的利用方式，这里不妨再重复一次t的作用：表示本次快速幂的计算过程中有没有得到过4这个数字。

而对快速幂过程熟悉一点的话，会发现快速幂的一个相当有用的性质：所有中间计算结果都可以看作是对前缀二进制串的幂运算。这里可以举个例子帮助理解，比如现在要用快速幂计算$2^{11}$，那么用快速幂的方法写成二进制串就有：

$$2^{1011}$$

而快速幂是按位计算的，那么把四次按位计算的中间结果都写出来就有(最开始r=1)：

$$1 \rightarrow 2 \rightarrow 4 \rightarrow 32 \rightarrow 2048$$

这就可以看出前面提到过的中间计算结果与前缀的关系了：

$$2^0 \rightarrow 2^{1} \rightarrow 2^{10} \rightarrow 2^{101} \rightarrow 2^{1011}$$

而他对于这个题目的意义就在于，我们可以用已知的前缀加上对下一个二进制位的猜测，去构造出下一次发送给靶机的数字，然后检查t是不是1(也就是下一次运算结果是不是4)来判断我们当前猜测的是否正确。

具体一点，我们现在已知s的MSB肯定是1，这也就是说，如果我们发送4，中间结果序列中的第一个值就一定是4，靶机也就一定会返回t=1。

那么如何猜测s的下一bit呢？我们不妨猜测下一bit是0，那么我们取$g=\sqrt[10]{4}$(虽然结果就是2没错，但要注意这里指的是模p下的2次剩余的意思，与开根区分开)，那么由于快速幂的前缀运算的性质，如果下一bit的确是0的话，在快速幂运算完前两bit10后，得到的就是4这个结果，靶机会返回1；而如果下一bit是1，那么靶机就会返回0了。如此一来就可以判断我们是否猜对了s的下一bit。

后面就是重复这个过程不断地去猜测s的下一bit，一直到求出s后，就可以计算$g = 4^{s^{-1}}$并发送给靶机得到flag。不过有一个小问题，就是s具体是多少bit我们并不能确定，所以实用一点的做法就是当求出前1000bit后，就开始把当前前缀当成s去试，看看能不能获得flag。

exp：

from Pwn4Sage.pwn import *
from Crypto.Util.number import *
from tqdm import *

p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
phi = (p-1)//2

sh = remote("node4.anna.nssctf.cn",28561)

g = 4
Zp = Zmod(p)
s_prefix = "1"
for i in trange(1024):
    temp = int(Zp(g).nth_root(int(s_prefix+"0",2)))
    sh.recvuntil(b"[Q]uit")
    sh.sendline(b"T")
    sh.recvuntil(b"integer: ")
    sh.sendline(str(temp).encode())
    sh.recvline()

    tt = sh.recvline()
    
    if(b"Great" in tt):
        print(tt)
        break
    else:
        check = tt.strip().decode()[9]
        if(check == "1"):
            s_prefix += "0"
        else:
            s_prefix += "1"
    
    #cause bitlen of s is unknown
    if(len(s_prefix) > 1000):
        s = int(s_prefix,2)
        d = inverse(s,phi)
        temp = int(pow(4,d,p))

        sh.recvuntil(b"[Q]uit")
        sh.sendline(b"T")
        sh.recvuntil(b"integer: ")
        sh.sendline(str(temp).encode())
        sh.recvline()

        tt = sh.recvline()
        
        if(b"Great" in tt):
            print(tt)
            break

#NSSCTF{2c6d1708-9bd5-4259-b44f-39f21aa7dee5}

pilfer techies

题目来源：amateursCTF 2024

题目：

#!/usr/local/bin/python3

import hmac
from os import urandom

def strxor(a: bytes, b: bytes):
    return bytes([x ^ y for x, y in zip(a, b)])

class Cipher:
    def __init__(self, key: bytes):
        self.key = key
        self.block_size = 16
        self.rounds = 256

    def F(self, x: bytes):
        return hmac.new(self.key, x, 'md5').digest()[:15]

    def encrypt(self, plaintext: bytes):
        plaintext = plaintext.ljust(((len(plaintext)-1)//self.block_size)*16+16, b'\x00')
        ciphertext = b''

        for i in range(0, len(plaintext), self.block_size):
            block = plaintext[i:i+self.block_size]
            idx = 0
            for _ in range(self.rounds):
                L, R = block[:idx]+block[idx+1:], block[idx:idx+1]
                L, R = strxor(L, self.F(R)), R
                block = L + R
                idx = R[0] % self.block_size
            ciphertext += block

        return ciphertext.hex()


key = urandom(16)
cipher = Cipher(key)
flag = open('flag.txt', 'rb').read().strip()

print("pilfer techies")
while True:
    choice = input("1. Encrypt a message\n2. Get encrypted flag\n3. Exit\n> ").strip()
    if choice == '1':
        pt = input("Enter your message in hex: ").strip()
        pt = bytes.fromhex(pt)
        print(cipher.encrypt(pt))
    elif choice == '2':
        print(cipher.encrypt(flag))
    else:
        break

print("Goodbye!")

题目基于一个分组密码，以及可以交互无限次的oracle。连接上靶机后，靶机生成一个16字节的随机key，并用其初始化分组密码cipher类，在这之后交互开始，每次交互我们可以选择：

• 输入1，可以输入一段明文，得到这段明文的加密值
• 输入2，可以得到flag的加密值

那么关键的问题就是分析清楚这个分组密码加密的流程，他的分块长度为16，每个块之间彼此独立，所以就单独研究其中一个块的加密流程就行。

对于每个块，他会加密256轮，每一轮的具体操作为：

• 1、按照上一轮的索引值idx，将块变化为L和R两部分，其中L是15字节而R是1字节

  这里的idx是上一轮的R模16的值，对于第一轮则是0

• 2、进行如下异或操作，并将L与R拼接在一起得到新的分块，其中F函数是带密钥的md5加密并取前15字节，可以近似看作是返回一个完全随机的串：

  L, R = strxor(L, self.F(R)), R

• 3、然后由本轮的R模16的值，确定下一轮的idx

理清这个过程过后，可以发现很有趣的一点，就是如果在某一轮开始时，由其idx确定的R模16的值恰好等于15，那么在这一轮及之后，R的值将永远不会改变，因为idx将恒为15，R将永远置于新block的最后一字节。

同时，由于R不会改变，所以F(R)也不再会改变，那么对于L来说，在这之后他将会反复与相同的F(R)做异或，因此每两次会相互抵消掉。

这时候产生了一个问题，那就是在什么时候，idx确定的那个字节模16会恰好余15？这是一个很重要的时机，因为在这个时机之后，整个串的结构就稳定了。稳定指的是，整个串将会在两个状态间反复跳动，并且最后一个值永远保持不变。

而正如前面所说，由于F函数是带密钥的md5加密并取前15字节，可以近似看作是返回一个完全随机的串，那么可以想成，idx选中的那个字节模16余15的概率，就是0-255的所有数字中，模16余15的概率，也就是1/16。

有了这一点，我们就可以想办法来逐块确定flag的字符了。这里我以flag的第一个分块为例。既然已知flag头是”amateursCTF{“，那么我们不妨假设他是：

amateursCTF{XXXX

然后想想，这个分块进入加密后，流程是什么样的。这里为了描述清楚，我们按上面的三个步骤，一步一步来。比如步骤一，由于第一次加密idx一定是0，所以其分块为：

L = mateursCTF{XXXX
R = a

然后进入第二步：

L = mateursCTF{XXXX ^ F(a)
R = a

然后是第三步，由于a的ASCII码是97，模16余1，所以此时选中的是L的第二个字节(注意下标是从0开始的)，也就是说，下一轮第一步选中的R是：

a ^ F(a)[1]

这个时候注意一点，F(R)既然是随机的，那么其中每个字节也可以看作随机的，所以a ^ F(a)[1]也可以看作随机的。因此，可以想为：flag的该分块有1/16的概率在第二轮就跳转到稳定状态，也就是说，如果我们反复重连，那么每次其实都是有1/16的概率是满足”第二轮就跳转”这个情况的。

但是，恰好满足上面这个情况，用处又在哪里？由于第二轮就达到稳定，那么之后的255轮加密，都会满足我们刚才说的：

• R再也不会变动，并且他的具体值是a ^ F(a)[1]，把这个值记作是T
• L会反复异或255次F(T)，最后等价于只异或了一次F(T)

所以我们最后得到的密文其实是：

L = m!teursCTF{XXXX ^ F(a) ^ F(T)
R = T

这里有几个小细节，比如上面L里的感叹号是什么意思，这里可以动手画一画具体加密流程，把前两轮根据idx拆分为L、R的过程写出来，很容易明白意思的。

现在要想一想，当靶机恰好满足这个情况时，我们该怎么利用这个第二轮就跳转的特点，去构造让靶机加密的明文。由于已知flag的第一个字符是a，那么所以第一轮的跳转是确定的，并且同时可以确定第二轮开始时刻的idx，因为其实就是a模16的值。

而由于a模16是1，所以第二轮选中的是第二个字符，由于整体左移了一位，所以其实第二轮选中的是开始时的第三个字符，我们已知这个字符也是a，因此我们构造payload：

a + b"\x00" + a + b"\x00"*13

那么我们反复重连靶机，当随机出来的密钥恰好满足a ^ F(a)[1]模16余15时，我们最后得到的密文是：

L = (b"\x00" + ! + b"\x00"*13) ^ F(a) ^ F(T)
R = T

所以和flag的第一块密文异或就可以得到flag的剩余14个字符的值了，整理出来第一个分块就是：

amateursCTF{i_lo

那么接下来要考虑剩下的各分组怎么办。对于第一组，由于flag头的缘故，我们恰好知道第一个字符a，以及由其确定的idx确定的第三个字符a。但是对于后续的分组我们似乎并不知道这些消息。然而可以看出flag是有语意的，比如第二个分组的第一个字符很显然大概率是v，那么我们就仅需要爆破由其确定的idx对应的一个字符，然后与明文异或得到完整第二个分组，再由语意得到第三个分组的第一个字符，……如此重复就可以得到所有flag分块了。

而似乎还有一个问题就是如何确定我们爆破的那个字符是正确的，如果我们爆破的字符正确，并且恰好满足第二轮跳转至稳定，那么可以得到一个结论是flag对应块的密文的最后两字节，与我们构造的payload的密文的最后两字节是一样的(这个同样推荐手动画一画图来推)。而在字符爆破正确时，有1/16的概率满足此要求，所以进行40次就大概率至少出现一次满足要求的跳转。

具体每个分块的payload可以见下。

exp：

from pwn import *
from time import time
from Crypto.Util.number import *
from tqdm import *
#context(log_level = 'debug')


def get_flag_enc(io):
    io.recvuntil(b'>')
    io.sendline(b'2')
    flag_enc = io.recvline()
    return flag_enc.strip().decode()

def get_choice(io,payload):
    io.recvuntil(b'>')
    io.sendline(b'1')
    io.recvuntil(b'Enter your message in hex: ')
    io.sendline(payload)
    enc = io.recvline()
    return enc.strip().decode()

def attack():
    start = time()
    
    for iii in tqdm("_0123456789abcdefghijklmnopqrstuvwxyz"):
        for jjj in range(40):
            io = remote('chal.amt.rs',1415)
            head = get_flag_enc(io)[128:160]

            #pay = b"a" + b"\x00" + b"a" + b"\x00"*13   #payload1
            #pay = b"v" + b"\x00"*6 + iii.encode() + b"\x00"*8   #payload2
            #pay = b"c" + b"\x00"*3 + iii.encode() + b"\x00"*11  #payload3
            #pay = b"A" + b"\x00" + iii.encode() + b"\x00"*13   #payload4
            pay = b"y" + b"\x00"*9 + iii.encode() + b"\x00"*5   #payload5
            assert len(pay) == 16
            payload = (pay).hex().encode()
            head_= get_choice(io,payload)

            if(head[-4:] == head_[-4:]):
                print(long_to_bytes(int(head,16)^int(head_,16)))
                exit()
            
            io.close()
        
    end = time()

attack()
#print(ord("y") % 16)
#amateursCTF{i_love_cycles_4nd_cycl3s_anD_cYcl3s_AND_cyCLEs_aNd_cyc135_4319d671}

count_the_counter

题目来源：b01lersCTF 2024

题目：

#!/bin/python3
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from secret import flag
import os


def Encrypt(key, message, nonce):
    cipher = AES.new(key, AES.MODE_CTR, nonce=long_to_bytes(nonce))
    return cipher.encrypt(message).hex()


def chal():
    key = os.urandom(16)
    print("Treat or Trick, count my thing. ")
    nonce_counter = 1
    print(Encrypt(key, flag, nonce_counter))
    while True:
        nonce_counter += 1
        to_enc = input("Give me something to encrypt: ")
        print(Encrypt(key, bytes.fromhex(to_enc), nonce_counter))


if __name__ == "__main__":
    chal()

题目基于AES的CTR模式，在最开始时，题目会使用如下nonce对flag进行加密：

b"\x01"

然后题目会使nonce逐次增加，并且每次均允许我们加密任意值并返回明文，要求还原flag。

首先要弄清楚以下两个概念：

• AES的CTR模式，其加密方法是对每个分块的counter进行加密，并与明文异或得到密文；加密完每个分块后counter自增，然后重复上述过程直至所有明文分块均被加密。
• pycryptodome里CTR模式的nonce参数是按如下方式拼接成最终counter：

nonce || counter

• 其中如果nonce是x字节，那么counter就是拼接在后面的从全0开始自增的16-x字节

有了这两点后可以发现下面这个事实(比赛中我并没有发现，是队友想到的，非常巧妙)：

对于nonce=1，和nonce=256的情况，其counter起始值分别为：

b"\x01" + b"\x00"*15
b"\x01\x00" + b"\x00"*14

所以此时用于与明文异或的counter加密块是完全一样的，因此我们输入全0去加密，将得到的串与flag的密文异或就得到了flag的明文。

exp：

from Crypto.Util.number import *
from pwn import *

sh = remote("gold.b01le.rs", 5002)
sh.recvuntil(b"Treat or Trick, count my thing. \n")
flag_enc = long_to_bytes(int(sh.recvline().strip().decode(),16))
length = len(flag_enc)

msg = (b"\x00"*length).hex().encode()
sh.sendline(b"00\n"*254 + msg)
for i in range(1,256):
    sh.recvuntil(b"Give me something to encrypt: ")

counter_enc = long_to_bytes(int(sh.recvline().strip().decode(),16))
print(xor(flag_enc,counter_enc))

#bctf{there_is_a_reason_for_random_nonce_and_with_fixed_length_8c6bf5a1398d1f1d95f1}