2025-N1CTF junior-crypto

参考鸡块神的博客，复现一下

CheckIn

题目：

import os
from Crypto.Util.number import *
from secret import FLAG

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

r = bytes_to_long(b'n1junior2025')
gift = ((2025 * p + r * r) * p % phi) >> 750

msg = bytes_to_long(FLAG)
ct = pow(msg, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
print(f"gift = {gift}")

'''
n = 127060392619341060272126983366487069092712215979664340339428955285201267724168574813227106020122399594060458777939446978632526348867806863618885370221957087197582864380885199290793062293120324984868138488667017882272415668310242448870352699380394381756621677031459335310964085476227148301120850021800822495119
e = 65537
ct = 18305235107479382231970252522433686185039231184629854177334609960907102735540326234277108553640185845164498239822263821349544015918443334769445559622730315115384134147808359107914969010678607157349844717217781801237935737980608575612421610972048739840839726108493286994232100086338529591086935374295281642738
gift = 8312456126096895497368692810699639462746223116345115761188530231045483000989605820
'''

注意到：

$gift = ((2025p + r^2)p\;\%\;\phi) >> 750$

右移750位后，低750位都没了，可以想到$\;\%\;\phi$和$\;\%\;n$效果应该差不多，就用数据测试了一下，得出来的数是一样的，因为要算p的高位所以不用很精确
那么可以得到下式：

$gift = ((2025p + r^2)p\;\%\;n) >> 750$

然后就有：

$(gift << 750) \approx (2025p + r^2)p + kn$

爆破k，再通过上式求出p的高位，最后copper就行了
小改了一下鸡块的代码
exp：

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

n = 127060392619341060272126983366487069092712215979664340339428955285201267724168574813227106020122399594060458777939446978632526348867806863618885370221957087197582864380885199290793062293120324984868138488667017882272415668310242448870352699380394381756621677031459335310964085476227148301120850021800822495119
e = 65537
c = 18305235107479382231970252522433686185039231184629854177334609960907102735540326234277108553640185845164498239822263821349544015918443334769445559622730315115384134147808359107914969010678607157349844717217781801237935737980608575612421610972048739840839726108493286994232100086338529591086935374295281642738
gift = 8312456126096895497368692810699639462746223116345115761188530231045483000989605820

r = bytes_to_long(b'n1junior2025')
G = gift << 750
PR.<x> = PolynomialRing(RealField(1000))
for i in trange(2200, 5000):
    f = (2025*x + r*r)*x - i*n - G
    res = f.roots()
    res = int(res[-1][0]) >> 230 << 230
    P.<y> = PolynomialRing(Zmod(n))
    g = res + y
    ress = g.small_roots(X=2^230, beta=0.499, epsilon=0.04)
    if(ress != []):
        print(i)
        # print(res)
        p = int(int(ress[0]) + res)
        # print(p)
        break

q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(int(pow(c, d, n))))
# flag{ec6f23afd0b7453bb8224146b6aad196}

BabyAES

题目：

from Crypto.Cipher import AES
from random import randbytes
import os

FLAG = "flag{REDACTED}"
pad = lambda x: x+randbytes(16-len(x)%16)
cipher = AES.new(os.urandom(16), AES.MODE_CBC, iv=randbytes(16))

for ROUND in range(128):
    msg = pad(bytes.fromhex(input("msg: ")))
    cts = [cipher.encrypt(msg), randbytes(len(msg))]
    decision = os.urandom(1)[0]&1
    print("ct:", cts[decision].hex())
    assert input("[+] ") == str(decision)
print(f"Congrats! 🚩 {FLAG}")

题目意思是输入明文后，返回密文，来判断是通过AES加密后得到的，还是直接返回的与填充后的明文等长的随机数
漏洞点就是可以输入19968bits的明文，那么就会返回19968bits的随机数，那就可以进行随机数预测了，从而进行decision
注意两个地方：

1. pad也调用了randbytes，预测的时候要算上
2. randbytes和predictor.predict_getrandbits两个函数输出是反着的，举个例子：

import random
from Crypto.Util.number import *
from extend_mt19937_predictor import ExtendMT19937Predictor
from random import randbytes
predictor = ExtendMT19937Predictor()

for _ in range(624):
    predictor.setrandbits(random.getrandbits(32), 32)

for _ in range(1):
    k = (randbytes(2))
    temp = predictor.predict_getrandbits(16)
    print(long_to_bytes(temp))
    print(k)
    # b'\xbf\xca'
    # b'\xca\xbf'

exp：

from Crypto.Util.number import *
from extend_mt19937_predictor import ExtendMT19937Predictor
from pwn import *
from tqdm import trange
from os import urandom

context.log_level = "critical"
sh = remote("39.106.16.204", 46046)

sh.recvuntil(b"msg: ")
sh.sendline(urandom(19968//8-16).hex().encode())
sh.recvuntil(b"ct:")
res = bytes_to_long(bytes.fromhex(sh.recvline().strip().decode())[::-1])
sh.recvuntil(b"[+] ")
sh.sendline(b"1")


predictor = ExtendMT19937Predictor()
# 传入624*32=19968bits的数进行随机数预测
for _ in range(624):    
    x = res & 0xffffffff
    res >>= 32
    predictor.setrandbits(x, 32)

for i in trange(127):
    sh.recvuntil(b"msg: ")
    predictor.predict_getrandbits(16*8) # pad调用了randbytes，填充了16*8bits也需要算上
    temp = predictor.predict_getrandbits(19968)
    sh.sendline(urandom(19968//8-16).hex().encode())
    sh.recvuntil(b"ct:")
    res = bytes_to_long(bytes.fromhex(sh.recvline().strip().decode())[::-1])
    sh.recvuntil(b"[+] ")

    if(res == temp):
        sh.sendline(b"1")
    else:
        sh.sendline(b"0")
print(sh.recvline())