SCTF

Barter（赛后）

两个文件：

sage：

from Crypto.Util.number import *
from random import *
from secrets import flag


def gen_random(seed, P, Q, r_list, times):
    s = seed
    for i in range(times):
        s = int((s * P)[0])
        r = int((s * Q)[0])
        r_list.append(r)
    return r_list

def gen_seed():
    seed = getRandomNBitInteger(32)
    return seed

def getP_Q():
    Q = Curve.random_point()
    P = 114514*Q
    return P, Q

def enc(flag, rlist):
    seq = list(randint(0, 1) for _ in range(4))
    add = rlist[55]*(seq[0]*rlist[66] + seq[1]*rlist[77] + seq[2]*rlist[88] + seq[3]*rlist[99])
    xor = pow(rlist[114], rlist[514], rlist[233]*rlist[223])
    enc = (bytes_to_long(flag)^^xor)+add
    return enc

nums = 600

seed = gen_seed()

p = 58836547289031152641641668761108233140346455328711205590162376160181002854061
F = GF(p)
a = F(114)
b = F(514)
Curve = EllipticCurve(F, [a, b])
P, Q = getP_Q()
r_list = []
r_list = gen_random(seed, P, Q, r_list, nums)
ENCFLAG = enc(flag, r_list)
print(ENCFLAG)
print(P, Q)
print(r_list[0])

'''
4911741083112145038719536311222612998219730565328651097326896414315857050336523018712625917027324116103593300559128797807261543857571883314990480072241188
#####################################
#####################################
Oh no, P, Q and r_list[0] are accidentally lost, but John seems to know, you can ask him about these missing values ::>_<::
'''

homework.py：

from Crypto.Util.number import *
from params import N, E, D
from leak_data import P, Q, r_1
import re

def challenge():
    meum = '''option:
    1: get pubkey
    2: get sign
    3: verify
    4: exit'''
    print("Hi, I am John. If you help me with my homework, I'll give you the data that I know (￣o￣) . z Z")
    print(meum)
    sign = None

    while True:
        print('[+]input your option: ', end='')
        your_input = input()

        if your_input == '1':
            print(f'[+]N = {N}')
            print(f'[+]e = {E}')
            continue

        elif your_input == '2':
            sign = pow(bytes_to_long(MSG.encode()), D, N)
            print(f'[+]sign = {sign}')
            continue

        elif your_input == '3':
            if sign is None:
                print('[+]Please input option 2 to generate sign first.')
                continue
            msg_user = input("[+]Please input your message: ")
            n = int(input("[+]Please input n: "))
            e = int(input("[+]Please input e: "))
            if e <= 3:
                print('[+]e is invalid')
                break
            else:
                if re.match(r'I can not agree more!!!$', msg_user):
                    if pow(bytes_to_long(msg_user.encode()), e, n) == sign:
                        print("Goooooooood! You are my hero! I can give you the data that I know ╰(*°▽°*)╯")
                        print(f'Leak_data: \n P={P}\n Q={Q}\n first num in r_list={r_1}')
                        break
                    else:
                        print('[+]Error signature!')
                        break
                else:
                    print('[+]Error message!')
                    break

        elif your_input == '4':
            break

if __name__ == '__main__':
    MSG = 'This is an easy challenge'
    challenge()

这个题需要先破解homework得到PQ和r才能去解椭圆曲线。

homework破解非常简单，对方随机生成RSA参数进行加密，需要我们用I can not agree more!!!这串作为m并发送我们的e和n再进行一次加密，如果两次加密值相同就返回椭圆曲线参数。

直接生成一个小e即可，有$sign=m^e\bmod n$可直接假设：

$n=m^e-sign$

传值，得到返回参数：

1
2
3

P=(24181776889473219401017476947331354458592459788552219617833554538756564211844, 33783050059316681746742286692492975385672807657476634456871855157562656976035)
Q=(16104852983623236554878602983757606922134442855643833150623643268638509292839, 3562830444362909774600777083869972812060967068803593091854731534842281574275)
first num in r_list=50920555924101118476219158701093345090627150442059647242030060086626996278598

在这题的椭圆曲线里生成了一个随机数序列：

def gen_random(seed, P, Q, r_list, times):
    s = seed
    for i in range(times):
        s = int((s * P)[0])
        r = int((s * Q)[0])
        r_list.append(r)
    return r_list

而且PQ的关系也是已知的：

def getP_Q():
    Q = Curve.random_point()
    P = 114514*Q
    return P, Q

我们已知了$PQ$和$r_0$，不知道seed，用公式观察一下试试：

$P=114514\cdot Q$ $s_0=(s\cdot P)_x=(114514\cdot s\cdot Q)_x$ $r_0=(s_0\cdot Q)_x=((114514\cdot s\cdot Q)_x\cdot Q)_x$ $s_1=(s_0\cdot P)_x=((114514\cdot s\cdot Q)_x\cdot 114514\cdot Q)_x$

可以发现$s_1$和$r_0$在椭圆曲线上差了$114514$倍，我们知道$r_0$了，代入曲线可以求$s_1$，紧接着可以反复把$r$数组全部还原，剩下的直接照搬异或就出了：

from tqdm import tqdm
from Crypto.Util.number import *
p = 58836547289031152641641668761108233140346455328711205590162376160181002854061
F = GF(p)
a = F(114)
b = F(514)
E = EllipticCurve(F, [a, b])


P=E(24181776889473219401017476947331354458592459788552219617833554538756564211844, 33783050059316681746742286692492975385672807657476634456871855157562656976035)
Q=E(16104852983623236554878602983757606922134442855643833150623643268638509292839, 3562830444362909774600777083869972812060967068803593091854731534842281574275)

r0=50920555924101118476219158701093345090627150442059647242030060086626996278598
enc=4911741083112145038719536311222612998219730565328651097326896414315857050336523018712625917027324116103593300559128797807261543857571883314990480072241188

rlist = [r0]
for _ in range(600):
    s = (E.lift_x(rlist[-1])*114514)[0]
    rlist.append((s * Q)[0])
    
rlist = [int(i) for i in rlist]

for i in range(2^4):
    seq = []
    for j in range(4):
        seq.append(i&1)
        i >>=1

    add = rlist[55]*(seq[0]*rlist[66] + seq[1]*rlist[77] + seq[2]*rlist[88] + seq[3]*rlist[99])
    xor = pow(rlist[114], rlist[514], rlist[233]*rlist[223])
    flag = long_to_bytes(int((enc-add)^^xor))
    if b'SCTF' in flag:
        print(flag)

GoogleCTF

LCG（赛后）

from secret import config
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime

class LCG:
    lcg_m = config.m
    lcg_c = config.c
    lcg_n = config.n

    def __init__(self, lcg_s):
        self.state = lcg_s

    def next(self):
        self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
        return self.state

if __name__ == '__main__':

    # Find prime value of specified bits a specified amount of times
    seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
    lcg = LCG(seed)
    primes_arr = []
    
    dump = True
    items = 0
    dump_file = open("dump.txt", "w")

    primes_n = 1
    while True:
        for i in range(config.it):
            while True:
                prime_candidate = lcg.next()
                if dump:
                    dump_file.write(str(prime_candidate) + '\n')
                    items += 1
                    if items == 6:
                        dump = False
                        dump_file.close()
                if not isPrime(prime_candidate):
                    continue
                elif prime_candidate.bit_length() != config.bits:
                    continue
                else:
                    primes_n *= prime_candidate
                    primes_arr.append(prime_candidate)
                    break
        
        # Check bit length
        if primes_n.bit_length() > 4096:
            print("bit length", primes_n.bit_length())
            primes_arr.clear()
            primes_n = 1
            continue
        else:
            break

    # Create public key 'n'
    n = 1
    for j in primes_arr:
        n *= j
    print("[+] Public Key: ", n)
    print("[+] size: ", n.bit_length(), "bits")

    # Calculate totient 'Phi(n)'
    phi = 1
    for k in primes_arr:
        phi *= (k - 1)

    # Calculate private key 'd'
    d = pow(config.e, -1, phi)

    # Generate Flag
    assert config.flag.startswith(b"CTF{")
    assert config.flag.endswith(b"}")
    enc_flag = bytes_to_long(config.flag)
    assert enc_flag < n

    # Encrypt Flag
    _enc = pow(enc_flag, config.e, n)

    with open ("flag.txt", "wb") as flag_file:
        flag_file.write(_enc.to_bytes(n.bit_length(), "little"))

    # Export RSA Key
    rsa = RSA.construct((n, config.e))
    with open ("public.pem", "w") as pub_file:
        pub_file.write(rsa.exportKey().decode())

看完代码，题目给了LCG的前六组，可以根据这六组逐个还原LCG的参数，根据题目RSA生成代码直接解就行，生成质数部分直接复制粘贴即可：

from Crypto.Util.number import *
import gmpy2

s = [
    2166771675595184069339107365908377157701164485820981409993925279512199123418374034275465590004848135946671454084220731645099286746251308323653144363063385,
    6729272950467625456298454678219613090467254824679318993052294587570153424935267364971827277137521929202783621553421958533761123653824135472378133765236115,
    2230396903302352921484704122705539403201050490164649102182798059926343096511158288867301614648471516723052092761312105117735046752506523136197227936190287,
    4578847787736143756850823407168519112175260092601476810539830792656568747136604250146858111418705054138266193348169239751046779010474924367072989895377792,
    7578332979479086546637469036948482551151240099803812235949997147892871097982293017256475189504447955147399405791875395450814297264039908361472603256921612,
    2550420443270381003007873520763042837493244197616666667768397146110589301602119884836605418664463550865399026934848289084292975494312467018767881691302197,
]
seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635

x0, x1, x2, x3, x4, x5 = s[0], s[1], s[2], s[3], s[4], s[5]
t0, t1, t2, t3, t4 = x1 - x0, x2 - x1, x3 - x2, x4 - x3, x5 - x4
p = gmpy2.gcd(
    gmpy2.gcd(t3 * t1 - t2 * t2, t2 * t0 - t1 * t1),
    gmpy2.gcd(t4 * t2 - t3 * t3, t3 * t1 - t2 * t2),
)
a = (x2 - x1) * gmpy2.invert((x1 - x0), p) % p
b = (x1 - a * x0) % p
seed = gmpy2.invert(a, p) * (s[0] - b) % p


class LCG:
    lcg_m = a
    lcg_c = b
    lcg_n = p

    def __init__(self, lcg_s):
        self.state = lcg_s

    def next(self):
        self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
        return self.state


lcg = LCG(seed)
primes_arr = []
dump = True
items = 0


primes_n = 1
while True:
    for i in range(8):
        while True:
            prime_candidate = lcg.next()
            if dump:
                print(prime_candidate)
                items += 1
                if items == 6:
                    dump = False
            if not isPrime(prime_candidate):
                continue
            elif prime_candidate.bit_length() != 512:
                continue
            else:
                primes_n *= prime_candidate
                primes_arr.append(prime_candidate)
                break

    if primes_n.bit_length() > 4096:
        print("bit length", primes_n.bit_length())
        primes_arr.clear()
        primes_n = 1
        continue
    else:
        break

phi = 1
n = 1
for k in primes_arr:
    phi *= k - 1
    n *= k

e = 65537
d = gmpy2.invert(e, phi)
with open("flag.txt", "rb") as f:
    f = f.read()[::-1]
print(long_to_bytes(pow(bytes_to_long(f), d, n)))

第一次做没做出来，发现flag文件的二进制字节被反转了，再[::-1]反转回来才能解出来。

巅峰极客2023

数学但高中

x=4{0<y<6}
y=4{2<x<6,17<x<18,28<x<30,41<x<42}
y=6{4<x<6,15<x<16,17<x<19,41<x<43,50<x<51}
x=7{0<y<6}
(x-9)^2+(y-3)^2=1
x=10{2<y<3}
(x-12)^2+(y-3)^2=1
x=13{0<y<3}
y=0{11<x<13,15<x<16,50<x<51}
y=-x+17{14<x<15}
y=x-11{14<x<15}
x=15{0<y<2,4<y<6}
x=17{1<y<6}
x=19{3<y<4}
x=21{3<y<4}
(x-20)^2+(y-3)^2=1{2<y<3}
(x-23)^2+(y-3)^2=1{3<y<4}
x=22{2<y<3}
x=24{2<y<3}
(x-26)^2+(y-3)^2=1{25<x<26}
y=0.5x-11{26<x<27}
y=-0.5x+17{26<x<27}
y=2{29<x<30,31<x<33,39<x<40}
x=29{2<y<5}
x=32{2<y<5}
y=x-27{31<x<32}
(x-34)^2+((y-3.5)^2)/(1.5^2)=1
x=36{2<y<3}
(x-37)^2+(y-3)^2=1{3<y<4}
x=38{2<y<3}
x=41{2<y<6}
x=44{3<y<4}
(x-45)^2+(y-3)^2=1{2<y<3}
x=46{3<y<4}
x=47{2<y<3}
(x-48)^2+(y-3)^2=1{3<y<4}
x=49{2<y<3}
x=51{0<y<2,4<y<6}
y=x-49{51<x<52}
y=-x+55{51<x<52}

给了一堆函数曲线之类的东西，猜测是画图的flag，用几何画板geogebra应该就可以，不过暂时没研究明白几何画板怎么玩，就直接手操了：

Simple_encryption

from Crypto.Util.number import *
import gmpy2
import random
import binascii
from secret import flag

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
g, r1, r2 = [getRandomRange(1, N) for _ in range(3)]
g1 = pow(g, r1 * (p - 1), N)
g2 = pow(g, r2 * (q - 1), N)

def encrypt(m):
    s1, s2 = [getRandomRange(1, N) for _ in range(2)]
    c1 = (m * pow(g1, s1, N)) % N
    c2 = (m * pow(g2, s2, N)) % N
    print("c1=", c1)
    print("c2=", c2)
    return (c1, c2)

c = encrypt(bytes_to_long(flag[:len(flag) // 2]))
print('N=', N)
print('g1=', g1)

def pad(msg, length):
    l = len(msg)
    return msg + (length - l) * chr(length - l).encode('utf-8')

p = getStrongPrime(1024)
q = getStrongPrime(1024)
assert (p != q)
n = p * q
e = 5
d = inverse(e, (p - 1) * (q - 1))
assert (e * d % (p - 1) * (q - 1))

flag = pad(flag[len(flag) // 2:], 48)
m = [int(binascii.b2a_hex(flag[i * 16:i * 16 + 16]).decode('utf-8'), 16) for i in range(3)]
print('S=', sum(m) % n)
cnt = len(m)
A = [(i + 128) ** 2 for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
C = [(i + 512) for i in range(cnt)]
Cs = [int(pow((A[i] * m[i] ** 2 + B[i] * m[i] + C[i]), e, n)) for i in range(cnt)]
print('N=', n)
print('e=', e)
print('Cs=', Cs)

'''
c1= 19024563955839349902897822692180949371550067644378624199902067434708278125346234824900117853598997270022872667319428613147809325929092749312310446754419305096891122211944442338664613779595641268298482084259741784281927857614814220279055840825157115551456554287395502655358453270843601870807174309121367449335110327991187235786798374254470758957844690258594070043388827157981964323699747450405814713722613265012947852856714100237325256114904705539465145676960232769502207049858752573601516773952294218843901330100257234517481221811887136295727396712894842769582824157206825592614684804626241036297918244781918275524254
c2= 11387447548457075057390997630590504043679006922775566653728699416828036980076318372839900947303061300878930517069527835771992393657157069014534366482903388936689298175411163666849237525549902527846826224853407226289495201341719277080550962118551001246017511651688883675152554449310329664415179464488725227120033786305900106544217117526923607211746947511746335071162308591288281572603417532523345271340113176743703809868369623401559713179927002634217140206608963086656140258643119596968929437114459557916757824682496866029297120246221557017875892921591955181714167913310050483382235498906247018171409256534124073270350
N= 21831630625212912450058787218272832615084640356500740162478776482071876178684642739065105728423872548532056206845637492058465613779973193354996353323494373418215019445325632104575415991984764454753263189235376127871742444636236132111097548997063091478794422370043984009615893441148901566420508196170556189546911391716595983110030778046242014896752388438535131806524968952947016059907135882390507706966746973544598457963945671064540465259211834751973065197550500334726779434679470160463944292619173904064826217284899341554269864669620477774678605962276256707036721407638013951236957603286867871199275024050690034901963
g1= 20303501619435729000675510820217420636246553663472832286487504757515586157679361170332171306491820918722752848685645096611030558245362578422584797889428493611704976472409942840368080016946977234874471779189922713887914075985648876516896823599078349725871578446532134614410886658001724864915073768678394238725788245439086601955497248593286832679485832319756671985505398841701463782272300202981842733576006152153012355980197830911700112001441621619417349747262257225469106511527467526286661082010163334100555372381681421874165851063816598907314117035131618062582953512203870615406642787786668571083042463072230605649134
S= 234626762558445335519229319778735528295
N= 28053749721930780797243137464055357921262616541619976645795810707701031602793034889886420385567169222962145128498131170577184276590698976531070900776293344109534005057067680663813430093397821366071365221453788763262381958185404224319153945950416725302184077952893435265051402645871699132910860011753502307815457636525137171681463817731190311682277171396235160056504317959832747279317829283601814707551094074778796108136141845755357784361312469124392408642823375413433759572121658646203123677327551421440655322226192031542368496829102050186550793124020718643243789525477209493783347317576783265671566724068427349961101
e= 5
Cs= [1693447496400753735762426750097282582203894511485112615865753001679557182840033040705025720548835476996498244081423052953952745813186793687790496086492136043098444304128963237489862776988389256298142843070384268907160020751319313970887199939345096232529143204442168808703063568295924663998456534264361495136412078324133263733409362366768460625508816378362979251599475109499727808021609000751360638976, 2240772849203381534975484679127982642973364801722576637731411892969654368457130801503103210570803728830063876118483596474389109772469014349453490395147031665061733965097301661933389406031214242680246638201663845183194937353509302694926811282026475913703306789097162693368337210584494881249909346643289510493724709324540062077619696056842225526183938442535866325407085768724148771697260859350213678910949, 5082341111246153817896279104775187112534431783418388292800705085458704665057344175657566751627976149342406406594179073777431676597641200321859622633948317181914562670909686170531929552301852027606377778515019377168677204310642500744387041601260593120417053741977533047412729373182842984761689443959266049421034949822673159561609487404082536872314636928727833394518122974630386280495027169465342976]
'''

flag分了两部分加密。

前部分先利用费马小定理计算得到$g_2$和$p$：

$\begin{cases}g_1=g^{r_1(p-1)}\bmod N\\g_2=g^{r_2(q-1)}\bmod N\end{cases}$ $g_1g_2=g^{k\phi(n)}\bmod N=1$ $g^{r_1(p-1)}\bmod p=1\Rightarrow g^{r_1(p-1)}-1=tp$

然后变换一下同余方程组还是利用费马小定理使其能使用中国剩余定理求解$m_1$：

$\begin{cases}c_1 = mg_1^{s_1} \bmod N=mg^{r_1s_1(p-1)}\bmod N\\c_2 = mg_2^{s_2}\bmod N=mg^{r_2s_2(q-1)}\bmod N\end{cases}$ $\begin{cases}c_1 \bmod p=m\bmod p\\c_2\bmod q = m\bmod q\end{cases}$

后部分$e$过小直接开根后分别求解三个一元二次方程，ABC参数都给了所以直接解就行：

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

N= 21831630625212912450058787218272832615084640356500740162478776482071876178684642739065105728423872548532056206845637492058465613779973193354996353323494373418215019445325632104575415991984764454753263189235376127871742444636236132111097548997063091478794422370043984009615893441148901566420508196170556189546911391716595983110030778046242014896752388438535131806524968952947016059907135882390507706966746973544598457963945671064540465259211834751973065197550500334726779434679470160463944292619173904064826217284899341554269864669620477774678605962276256707036721407638013951236957603286867871199275024050690034901963
g1= 20303501619435729000675510820217420636246553663472832286487504757515586157679361170332171306491820918722752848685645096611030558245362578422584797889428493611704976472409942840368080016946977234874471779189922713887914075985648876516896823599078349725871578446532134614410886658001724864915073768678394238725788245439086601955497248593286832679485832319756671985505398841701463782272300202981842733576006152153012355980197830911700112001441621619417349747262257225469106511527467526286661082010163334100555372381681421874165851063816598907314117035131618062582953512203870615406642787786668571083042463072230605649134
c1= 19024563955839349902897822692180949371550067644378624199902067434708278125346234824900117853598997270022872667319428613147809325929092749312310446754419305096891122211944442338664613779595641268298482084259741784281927857614814220279055840825157115551456554287395502655358453270843601870807174309121367449335110327991187235786798374254470758957844690258594070043388827157981964323699747450405814713722613265012947852856714100237325256114904705539465145676960232769502207049858752573601516773952294218843901330100257234517481221811887136295727396712894842769582824157206825592614684804626241036297918244781918275524254
c2= 11387447548457075057390997630590504043679006922775566653728699416828036980076318372839900947303061300878930517069527835771992393657157069014534366482903388936689298175411163666849237525549902527846826224853407226289495201341719277080550962118551001246017511651688883675152554449310329664415179464488725227120033786305900106544217117526923607211746947511746335071162308591288281572603417532523345271340113176743703809868369623401559713179927002634217140206608963086656140258643119596968929437114459557916757824682496866029297120246221557017875892921591955181714167913310050483382235498906247018171409256534124073270350

g2=gmpy2.invert(g1,N)
p=gmpy2.gcd(g1-1,N)
q=N//p
phi=(p-1)*(q-1)
cp = c1 % p
cq = c2 % q
m = solve_crt([cp,cq],[p,q])
print(long_to_bytes(m).decode(),end='')

res=[]
Cs= [1693447496400753735762426750097282582203894511485112615865753001679557182840033040705025720548835476996498244081423052953952745813186793687790496086492136043098444304128963237489862776988389256298142843070384268907160020751319313970887199939345096232529143204442168808703063568295924663998456534264361495136412078324133263733409362366768460625508816378362979251599475109499727808021609000751360638976, 
     2240772849203381534975484679127982642973364801722576637731411892969654368457130801503103210570803728830063876118483596474389109772469014349453490395147031665061733965097301661933389406031214242680246638201663845183194937353509302694926811282026475913703306789097162693368337210584494881249909346643289510493724709324540062077619696056842225526183938442535866325407085768724148771697260859350213678910949, 
     5082341111246153817896279104775187112534431783418388292800705085458704665057344175657566751627976149342406406594179073777431676597641200321859622633948317181914562670909686170531929552301852027606377778515019377168677204310642500744387041601260593120417053741977533047412729373182842984761689443959266049421034949822673159561609487404082536872314636928727833394518122974630386280495027169465342976]
res.append(int(gmpy2.iroot(Cs[0],5)[0]))
res.append(int(gmpy2.iroot(Cs[1],5)[0]))
res.append(int(gmpy2.iroot(Cs[2],5)[0]))

def solve(list):
    A = [(i + 128) ** 2 for i in range(3)]
    B = [(i + 1024) for i in range(3)]
    C = [(i + 512) for i in range(3)]
    get = []
    for i in range(3):
        get.append((-B[i]+gmpy2.iroot(int(B[i]**2-4*A[i]*(C[i]-list[i])),2)[0])//(2*A[i]))
    return get

print("".join(long_to_bytes(int(i)).decode() for i in solve(res)))

DASCTF 2023七月

ezDHKE

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import randbytes, getrandbits
from flag import flag

def diffie_hellman(g, p, flag):
    alice = getrandbits(1024)
    bob = getrandbits(1024)
    alice_c = pow(g, alice, p)
    bob_c = pow(g, bob, p)
    print(alice_c , bob_c)
    key = sha256(long_to_bytes(pow(bob_c, alice, p))).digest()
    iv = b"dasctfdasctfdasc"
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc = aes.encrypt(flag)
    print(enc)

def getp():
    p = int(input("P = "))
    assert isPrime(p)
    assert p.bit_length() >= 1024 and p.bit_length() <= 2048
    g = 2
    diffie_hellman(g, p, flag)

getp()

一道DH，传一个符合要求的$p$，首先想到了用$p-1$光滑数：

from Crypto.Util.number import *

while True:
    p = 2
    while p.bit_length() < 1024:
        p *= getPrime(16)
    if p.bit_length() < 2048:
        p = p + 1
    if isPrime(p):
        print(p)
        break
    else:
        print('Failed')
        
#1667833661893190850614229728242541473293090915587516195377451154299565854036707919099882497009094106528670113622582165967857335570266503881754097306871220357984103872808513913944395982281681516153048594439559300291842285061839022871314628039891098410917621542562195094231722413980078436853725372342624712803167

发送，得到了$AB$和$enc$，sage的discrete_log的算法包含了Pohlig–Hellman的光滑数算法，分解得到$a$，即可求出key，解密得到flag：

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

p=1667833661893190850614229728242541473293090915587516195377451154299565854036707919099882497009094106528670113622582165967857335570266503881754097306871220357984103872808513913944395982281681516153048594439559300291842285061839022871314628039891098410917621542562195094231722413980078436853725372342624712803167
A=674338210175916971040145932562399337979803757873940643305779230227023770048277289379616197311090576212146354324600042151827768489913436479730502970022683944021451855725712384135519384435844299034886947385743994245307535983614074769003902403120531577386321567969843754563629583882687720501366639876370403334063 
B=1496405443110435697016942653655407798903378252274283459115580396855258014491004374918548812118652923231512011132623305747438339133524052501013037935697029275845589904549107374889754485778123275792581689009825019096968528611330186767295673567032691651711760660150612951284828461266305440640100176699756442139271
enc=b'\tQZ`\xf4\x85e\xc0\x04\x08\xde\xa6\xcb\x08A\x95\x8b\x12\x80\xab\xd0\xe0\xbb\xf9\xce\x05\xab\xffh\x1cl\xb6\xe4VX\x06\xf8\xd2\xed\x81\xf2\x8c{\x9em\x06\x91\xc8'

'''F = IntegerModRing(p)
a = discrete_log(F(A), F(2))
print(a)'''

a=134637600312404672552619474452519856417289889351153359861331867871723205226426976036720937904922831097464189207651306439726793719056104318275311370416324895329262529016160530522778176631604479645395601484474144732115675519021324643356649512302139842899207009059468554963266614619707715509022572109298910737558

key = sha256(long_to_bytes(pow(B, a, p))).digest()
iv = b"dasctfdasctfdasc"
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(enc)
print(flag)

ezRSA（赛后）

from Crypto.Util.number import *
from secret import secret, flag
def encrypt(m):
    return pow(m, e, n)
assert flag == b"dasctf{" + secret + b"}"
e = 11
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)
print(N, gift, pow(n, e, N))
print(encrypt(bytes_to_long(secret)),
    encrypt(bytes_to_long(flag)))

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
c1 = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
c2 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
c3 = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

注意到这里的$gift=P\oplus (Q<<16)$，提供了$gift$，相当于知道了$P$的前16位，可以根据二进制的乘法还原出$Q$的最开始的几位（由于需要考虑进位，所以可以少取几位），知道$Q$的前$x$位之后根据异或可以得到$P$的$16+x$位，然后按照这种方法不断循环就可以大致求出$P$，由于$Q$的最后16位不知道，所以$P$求到最后会差几位，直接爆破即可：

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
e=11

p_high = gift >>(512-16)

while True:
    try:
        q_high = (N>>(1024 - p_high.bit_length()*2))//p_high >> 6
        print('q_solve =',q_high,q_high.bit_length())
        gifts = gift^(q_high<<(512-16-q_high.bit_length()))
        p_high = gifts >> (512-16-q_high.bit_length())
        print('p_solve =',p_high,p_high.bit_length())
    except:
        break
        
for i in range(64):
    P = (p_high << 6) + i
    if N % P == 0:
        print(P)
        break

Q = N//P
print(P,Q)

在这里恢复n的时候有一个坑的地方：print(N, gift, pow(n, e, N))

这里的n如果本来比N还大的话，我们求逆得到的n就不对了，需要再加上一个N。

这题还考了一种相关信息攻击：

1
2
3

assert flag == b"dasctf{" + secret + b"}"
print(encrypt(bytes_to_long(secret)),
    encrypt(bytes_to_long(flag)))

我们得到的两个密文的明文不同，而且这两个明文有些联系（bytes是256一位）：

1	flag = bytes_to_long(b'dasctf{' + b'\x00' * i + b'}') + 256 * secret

这里就可以使用Franklin-Reiter相关消息攻击：如果两个信息之间存在已知的固定差异（$f(x)=ax+b$），并且在相同的模数$n$下进行RSA加密，那么就有可能恢复出这两个消息。

有：

$C_1\equiv M_1^e(\bmod N)$ $C_2\equiv M_2^e(\bmod N)$ $M_1\equiv f(M_2)(\bmod N)$

可以知道$M_2$是$f(x)^e-C_1\equiv 0(\bmod N)$的一个解，也是$x^e-C_2\equiv 0(\bmod N)$的解，对两个多项式分别进行辗转相除法求得多项式的最大公因子，如果最大公因子是线性的（次数为1），即最大公因子可以表示为一个一次多项式（$x-M_2$），那么在模数下仍满足$x-M_2=0$，就求得了$M_2$：

这个题中没告诉flag的长度，所以需要进行爆破，找到符合长度的secret。

from Crypto.Util.number import *
import gmpy2

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
c1 = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
c2 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
c3 = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
P=8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
Q=9366986529377069783394625848920106951220134111548343265311677163992169555436421569730703291128771472885865288798344038000984911921843088200997725324682297

phi=(P-1)*(Q-1)
d=gmpy2.invert(11,phi)
n=int(pow(c1,d,N))+N

def GCD(a,b):
    if b == 0:
        return a.monic()
    else:
        return GCD(b,a % b)
    
PR.<x> = PolynomialRing(Zmod(n))

for i in range(50):
    f1 = x ^ 11 - c2
    f2 = (bytes_to_long(b'dasctf{' + b'\x00' * i + b'}') + 256 * x) ^ 11 - c3
    if GCD(f1,f2)[0] != 1:
        print(b'DASCTF{'+long_to_bytes(int(n - GCD(f1,f2)[0]))+b'}')

NepCTF 2023

打比赛两天比较忙，就做了几个misc，过了一遍密码的几个题，感觉比较复杂也没做出来，赛后复现一下吧。

random_RSA（赛后）

这题学长仿着校赛的那道题出的：

from gmpy2 import next_prime, invert as inverse_mod
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from random import getrandbits
from math import lcm
from sys import exit
flag = "1234"
global_bits = 1024

BANNER = rb"""
.--------.--------.--------.--------.--------.--------.--------.--------.--------.--------.--------.
| N.--.  | E.--.  | P.--.  | C.--.  | T.--.  | F.--.  | H.--.  | A.--.  | P.--.  | P.--.  | Y.--.  |
|  :/\:  |  (\/)  |  :():  |  :/\:  |  :/\:  |  :/\:  |  (\/)  |  :():  |  :/\:  |  :/\:  |  (\/)  |
|  :\/:  |  :\/:  |  ()()  |  (__)  |  :\/:  |  (__)  |  :\/:  |  ()()  |  :\/:  |  :\/:  |  :\/:  |
|  '--'n |  '--'e |  '--'p |  '--'c | '--'t  |  '--'f |  '--'h |  '--'a |  '--'p |  '--'p |  '--'y |
`--------`--------`--------`--------'--------`--------`--------`--------`--------`--------`--------`
"""

def generate_prime(bits: int):
    p = (getrandbits(bits - 32) << 32)
    return next_prime(p)


def generate_private_key(bits: int):
    p, q = generate_prime(bits), generate_prime(bits)
    n, phi = p * q, lcm(p-1, q - 1)

    d = inverse_mod(0x10001, phi)
    privateKey = RSA.construct((int(n), int(0x10001), int(d), int(p), int(q)))
    return privateKey, p > q


if __name__ == "__main__":
    print(BANNER.decode())
    print("Welcome to the world of random RSA.")
    print("Please make your choice.")
    for _ in range(8):
        choice = input()

        if choice == '1':
            p, q = generate_prime(global_bits), generate_prime(global_bits)
            N = p*q
            d = generate_prime(global_bits-32)
            e = inverse_mod(d, (p * p - 1) * (q * q - 1))
            print(f"{int(N)}")
            print(f"{int(e)}")

        elif choice == '2':
            privateKey, signal = generate_private_key(global_bits)
            Cipher = PKCS1_v1_5.new(privateKey)
            c = (Cipher.encrypt(flag.encode()))
            print(c)
            exit()

        else:
            exit()

还记得之前那个是解一个二元的同余方程，这里最大的变化就是e = inverse_mod(d, (p * p - 1) * (q * q - 1))，问题就是如何分解模数，当时想到了用连分数攻击，但是具体怎么个攻击法不是很清楚。

依照论文《Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits》，如果出现上述这种情况，可以寻找$\frac e{N^2-\frac 94N+1}$的连分数来恢复，但是不确定谁才是真正的$p,q$，所以后续还需要排列组合一下，用到itertools：

import gmpy2, itertools
from extend_mt19937_predictor import ExtendMT19937Predictor
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5


def attack(N, e):
    convergents = continued_fraction(
        ZZ(e) / ZZ(int(N ^ 2 - 9 / 4 * N + 1))
    ).convergents()
    for c in convergents:
        k = c.numerator()
        d = c.denominator()
        if pow(pow(3, e, N), d, N) == 3:
            phi = -(((e * d - 1) // k) - N ^ 2 - 1)
            paddq = gmpy2.iroot(phi + 2 * N, 2)[0]
            psubq = gmpy2.iroot(phi - 2 * N, 2)[0]
            p = (paddq + psubq) // 2
            q = N // p
            return p, q, d


def generate_prime(bits: int):
    p = predictor.predict_getrandbits(bits - 32) << 32
    return gmpy2.next_prime(p)


N = [
    3765304535291018339688670915896633223049145240557925608076814531580764601506094555625235870930145344445034517999252187810691525051945406571449198399619338466719394096327909343739405114412183218693874257550201904795355429473491452123232766685889958978508746764937033934388116453314906550166251190689334987889491070284034342757231103113370747651109695929056916132220291521767583483907419454636178829846508861417282419720051506489452559583486366763002184149965303026016285269557063844163561975102092475685056717839708800504657083102707802580204551750511621130061415762082460977670712101611396626771712322664347191591323,
    334632136453190551723081253576634900585632232582351643743083954002337465509647787170466132811539860248177158778004387142610580971591037048596232650016811454798468939369216327233665888745787309521420145465526350988305057386068795286538656425850578290878785540725823927498178793582332746795954290315983108734928238954557771729784933864761834378886910250682621647463849692985037254423294379442111428114361697295170408409335579777444340902948267852779645089648331867542798646589899493486600774662691287670728444012563200203019555388567168417631932353770160592775673303986571920660111230813531455512751129063668773513109,
    153715361735531965272821019242034854365280672797974694129828808729014207544226656645669155433599719460128954317891729222286388189452981947447380976396847669367257109336893730334936811298996103788918912412912043950379358514115443236390609791034492613165873862174762235838535786107756803285722732838308106005141864996466534888774468262171576492016835324319614101186714978118794877295234334199529077228105563893755774687121271124614388739875586056852744030880217275042784137847103955364431665506050736429068076969468715027611207720808285712884312343701689446175985259810861442589445293961929665727922966218183322643991,
    7649717688029700473239198357034068317967619332212148096452918919648108665367993684191395637339881295124789979477813114571304026387696234426797430312923723594276296427130133329160615089210594195951349573695228331695856018211030704956236879259959060767496927003079483843839671238825390589720292050579154663187413209114288105669626034344187663390952882022858881130145243345550538078765358856064008966837923926711059067447250716386545271352390379483873001929689366607348000025669596978953090522217641996833642841588178606558699901723390995785457730729333619815170514232673742237928630790953027996105498037232590249039053,
    7457883801163318826405526150112579893417970974020504629242561157019113562804326849056156724208041137150533505739990407109077810321379027208498635880118205061287061395091326582299965612518833703906054294223411569962057620128373567861629262515342618228686329309087490239995091051782509922379844038225275527471556782395090408119191145356046868082594514442233628660461363025205838524451347467219223874599977669916216761453909322037149880021461652885858294699892505782091039442283103866451823909748022667639157470807593475928084573431819134127451933080773075137409421894801075502546925802480677875398545074012657587083983,
    1813559865513707653055230789285394341068979896078084508620368892013433949432881330199380116711706246678749889981127822085668163618236713915766210705689701980478991012628265976347772668333610539935853260290619179387341574042594172518938365835338645385754536560978089330755372236415605247266194763503664269455613236672427228340880941257837044509918038846090085398979381440302492083140216039768579678674528911253979612107665221688844691527767527990967852442304087733243427802719885743703095217136758377532888713160271848900361056757404771363206535372378132469622112276980219190857006925965234174026305359802656998075507,
    7018714901781695384238187379808766296980529575242596207509988571386042720510190906033962914089587542321597146267822149170716062102747855091099966952060196851723837834296127483395022712980320508963622409883161512764519326190222180028853293641307178142216866231601275942050561361155279891771536614243714775716528212034586465344158653077046696967782965191150213340212327271906507086443578451292626475752484105108868575454796993931340872669661915188373097848902310691046138927368076970570810771118232622158738069820111765539883905999343012765450489465671547836075707793564844796888036950048848507258710529880264456978619,
]
e = [
    7366635133308336189637831170384977836694264065634288360782746681326026297216918144435268356839986329412631551102171723870848568250180640846873268887544893980743655417665429613006480641821611959115150610131631997610859583816756488548344610003758128917472080126202962327383161648551011064990697767956767472049832671456988295454144759407234813474643273809970367987827847266778100704999783911394747787301777842452473022977096245346638355373000494166315823619498502378907047100855589473263443951302510454613614983242245800645329663435353005808792350476867223672426590467266835459205773816473065872621629673198924341827557728013243915088499026124523782987667142132477895764920539939507207353238795917175516314439317092385480353961218037528632048486067720233854136080717362331246003376272401028793301533330671567657462006801304529117039359033778564055875922710253333294537580848418065626762714333393039578727146089661205775274959881174012565531583329784901510977285670219486315816574707789882703969465007261361489834017650782755027941718045416163757882301850400042695516981001126394034504199507705256624781636475771083820163864860374904204911524107828720122664050988746498116525887186921001186002841984524856520198482943690729004126660921,
    94128072103270544951761402955477278111051543608438514758901351962833421943552478491923160953899926984993441526458840100770089599190409413056841943442762751453182808592549095710666764100401297184026498293763116408957038287034783169276109375171325443967585089408588889123392861474515089975351355715014873957785709823059505216584491364723523777962800736875685886145967042501770771010353645526815781190868685491413708468500044583816520413444859597957679234728895746683882329109516255194251627086368635222785163613602067942222275954398741292510652497216260759315102799270730570057482299559163775882617217232865604831277534942547520261997183276811422360490310900065272033105183443079240913227758075087805190322107074510398773100826247013649620116662383596359811675364585322445916610384787640339868669269740427124031395984902562057215023860139550320616690249547247265226575487771330255741909554198423847144232099418778379936760002750988381603672141060338805465754103845139990394724807262930354399826150465799234313903415692707692976069815806280427872412127793196019406170839184674500319860928479357681340068484714538705389893385426065178209049195830495435297499510761574613780019492063731579226927073605056117291419683409392049330971823,
    29938063184059722715836999348619662986820135033368134003129093184173608756932914388044521740170608273027242136864259821779104436118568148403788177717328830595583737498486887906888560528834325661017012794171293970925583418678260928809108732689876846497038817246787118385305171360347425199280597715576469636790661054178989848430107476444714096401838226928214846051627286476574909009273483730730012288546052530276330894267716266745627741009284487213534718087971712602071958046826812382205771458576996864103588271971596790249677095953627593334412463850833489619552252343282747368818498069106583587605936110466543236641337733986372616490128771270037318029295526720464846272707640922638627490023654806921863041129160366134147012441282747942112730928156294563806100579406040860206834742347455124192175765073693535133433726826087284560529586906379233113040876231121306168504426137650360219839202066444812239528700595764259739637679999346648586419813783208237545399496930176977510947867694568696631805236201456363731190760715702203618533010370718095402914775029801127359591465235479277045419287968366021347122345151133939671594722532621651937782632644262303086385203676978486055708096210363092859204384197567441018742862151535970325337,
    22242172854585820599771662231592135629751522579639384363017295649354179258540837582192678551261478534817526103751356207632266517773788143978894768283914893074296403964361516953031986661282387169902902535358664567926936825360973679103096277022192787735748224582088404373210870415913820650112391908457926220868627735802109994277210310855252396517414737341249433266949112137432454061526723592625800128275224241458730876411426745366095007972516091808988655185242608456785522411174191402418788882796392602094168822213397414257594609535315883650826937231541186302618473269968221787628515707656683197829845204584651244564409925017557748404665245114204388073154508062825060580937679948691946470970869780179376161489990421844330828497260883720644434965422904462494280431467574058723863274857471578587737940376570627084337626796997657894669390826331922603006644476839037111712478349475688502469769526441362990812411526026624169858951937609629375908999078962140488526530740367562675194715226591821981283130422727934114396560118408257639910141264943252774851742665125020744570778742697643990313512839806290767261082249187798760344853462439103270401917156234795879795105282539611541934241424322659622229924460215744836224481608055159779743891987,
    7935615333069344782550539080941744675593939286007591806958487750116455093837758943332661795018117645405322945287360502547714067960330003996294422504519564856822194551811994978801231251098003986519255919363241998506462063103796728895961090408270022455411603822641748971036706146621484486295585515477441489806261439608644649762562513119493095475170095127417410517420787742785388934924579731549107151524103783767890440593038050282713737692611258633613657821822467920242288790623615344622917861947040259939856758241913324151661414068729477840408936676268167083119822980915296470563794025717830932052269161506002100339702645483713444167574328181603708212563968150962069592753517717694739742703771558250327523154239821714610178994360221447477312770517347344847983552480167418359788823492240370769817576172497026241084878337132715849711575903280189585243898482522149325072004522335879516642946384395900345695909934720374459649295906802294897306955307332924772477005157532973972805811022695414167456651071085278818794683137465359363826659476597616083578688497724940359644989023798286621568142435839062768662707551346343320329475307624112737666579693619188245048304660114861603079309309906389607022001946114684324398813253984267000150449967,
    164724742790494775261806711902276018852469305976720859409992192118979621017192706934453787196309379727807740686567971193919929247419416656051955584733517291983922220811147189636365583006175675685867895166384041231418660233425269784822683023982868367336461160261357885815057437191381325707013115691868167182889623537400280169466347243568341980940531165363947802792350736208622531893909030212981202061889029667561981343223354931082143735651763422536056585282624582109691889044446565401146791777356484506977971115457721083173263530811413473382253083088839270825223648329240595182922955231624401667918881846728505950552932462386207919655853390200335159403012521370804355985901891290495715180317670061786323129472077797590492412938087856426015959862474998241506854722331607708219119363019823810742043846432997686478760894912937632501674926117888376911841803296269856441628429583230676724046015818594654307075665650706617870752947616176198560533861603328528466934953028273077415032887804128677899096254680630160929802757955287574180750511398727169378406799693874163420293859206378391315266233060040950102157257909070415812338079166735695989281160785311568513529536573169484406961016221730267933252984924458858639187568330955438813921231,
    17631067554479313247175539183573165403651771719391212375552951497482733701531879295053654972862370420307478530333423283283339230687444658611058338898747209254721511878220884711382776185948963570286590254046127244582703841617586703300834269582420905510071198658574511645218534243787971248573898538325170359581014724146045446555423520128022960649353505292887267766015269849277635652613379264899709526743934171351524702625023029545450707299611235121884301408414240419067636254667709006178036318547812268693365895023967775094797356574685901479155795893507350398597837862943649394206733123791896702643404795188321640355451822009099798580695247380884654850072379378488636749779394790480431646139855704812950274333857881195457921766323086829756991115536472758486891359850784642602550336091379314327213881503972612955893916970540759324873445367953100990902180867720579319469979496854377815266948828355784276218615788119887319338297250290703777062452841834910860553945587516526316450911753847957857781076883365550303848768938610995133633322599352370461958641183301525550866404920866795789962368579912955476640915658361379954039470514512106817656941903974607746786227905914277329203896740138916825540218493120873046564279638394784252295619323,
]

c = b".\xbfm\x80k*\x0f{\x05aZ\xa2_\x86\xbf\x8e\xd9\xce'\xcc\xf5\xaa5\xff[i\xf9Li\x11:\xd8Mz\x85\xa7GL\xeb\xc3\x83\xd2*\xf4\xf5\xc4\x08iu\x8b\xc4\x11v\xcb\xc8\xa3\xfbVB\xe5\x07:\x18\xa6\xfd[\x92\xeb\xd2\xe6B\xc7j\xb7\x88\xb8\xf9\xe7\xf3\xe0E\xa6\x03\x1e\xfa\x84\xd7\xf0\xfe\xf3\xb8\xe2\xf4`h\xc3\x1a\xbf\x83\xb3|\xb6_\xe0\x87\x11a\xedl\x868\xe0\x8cl\x93\x8a`F/O\xb5}%\x93\xb7z\xb6\xb2\x96\xdd\xc7\xe4\xd1(D\x9b\x7f\xa0\xea\xce\x11\xb2\x96\xec\xbd\x94\x96`Y=V\x08@X\x91\x8e\x84?\xeb\xba\xed\x95\x00\x14\xe5\xbc\x87\xc7r\xb1`_77\x8e\x82\x96Z\x07GFhkm\"nO\x0c\xbb\xf3.\xb3\x0b\xd4\xef\xb0YYy`9\x95\xb4\xdc\xdd\x06\r\xb8\xeel\x066@?\xbcx\x101 ^n\x05\xb6\x98\x81ek\x1b!\r,;\x98\x96\xeaR\x1d\xe5U\x9e\x89\xca\xa7\xbe\xca\x12\xcb\xaf\x05\xd5\x05YM\x97\x8a\xa5"

P = []
Q = []
D = []
for i in range(7):
    p, q, d = attack(N[i], e[i])
    P.append(int(p >> 32))
    Q.append(int(q >> 32))
    D.append(d >> 32)


for i in itertools.product([0, 1], repeat=7):
    try:
        fac = []
        for j in range(len(i)):
            if i[j] == 1:
                fac.append(P[j])
                fac.append(Q[j])
                fac.append(D[j])
            else:
                fac.append(Q[j])
                fac.append(P[j])
                fac.append(D[j])

        predictor = ExtendMT19937Predictor()
        for i in range(len(fac)):
            if int(fac[i]).bit_length() < 965:
                predictor.setrandbits(fac[i], 960)
            else:
                predictor.setrandbits(fac[i], 992)

        p, q = generate_prime(1024), generate_prime(1024)
        n, phi = p * q, lcm(p - 1, q - 1)
        d = inverse_mod(0x10001, phi)
        privateKey = RSA.construct((int(n), int(0x10001), int(d), int(p), int(q)))
        Cipher = PKCS1_v1_5.new(privateKey)
        flag = Cipher.decrypt(c, "\x00")
        print(flag)
        break
    except:
        pass

WMCTF

from Crypto.Util.number import *
from random import randrange
from secret import flag

def gen_prime(bit):
    while 1:
        P = getPrime(bit)
        if len(bin(P)) - 2 == bit:
            return P

pq_bit = 512
offset = 16

P,Q = [gen_prime(pq_bit) for i in range(2)]
N = P * Q
gift = int(bin(P ^ (Q >> offset))[2+offset:],2)
pr(N)
pr(gift)

inpP = int(input())
if inpP != P:
    pr(b"you lose!")
    exit()

secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]

results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1)  for ri in results]

pr(bs)
pr(rs)
inpsecret = int(input())
if inpsecret == secret:
    pr(flag)

这题分为两个部分，上半是一个类似于上面ezRSA的求解因子的操作，不过这里没有提供高位，可以直接爆破一下：

N = 56926121230070860522021858222376835199152768535695893312307107271470069724930276796319823573131233195237160028777740480344562965515093909280322054086785487388103390618832318336984744202378593597183981582538471590847113343740046218768605691018126706982690057576771999872413555389254225943044818790534983211867
gift = 179855635362202401189637654527305278267838051491985548013479645843896448045963084621418188187077860016324803214638232902394544150770345050212854238842

for h in range(32768, 65535):
    gg = gift + (h << (512 - 16))
    p_high = gg >> (512 - 16)
    while True:
        try:
            q_high = (N >> (1024 - p_high.bit_length() * 2)) // p_high >> 6
            gifts = gg ^ (q_high << (512 - 16 - q_high.bit_length()))
            p_high = gifts >> (512 - 16 - q_high.bit_length())
        except:
            break
    try:
        for i in range(2**6):
            P = (p_high << 6) + i
            if N % P == 0:
                print(P, N // P)
    except:
        pass

得到$pq$之后发送，会得到发来的两个数组：

secret = randrange(0,P)
bs = [randrange(0,P) for _ in range(38)]

results = [(bi * secret) % P for bi in bs]
rs = [ri & (2 ** offset - 1)  for ri in results]

pr(bs)
pr(rs)

这里需要求解一个secret，搜索发现属于格密码的HNP问题：

$2^{16}k_i\equiv b_is-r_i(\bmod p)$ $2^{-16}b_is-2^{-16}r_i\equiv k_i(\bmod p)$

题目比较常规，找了道差不多的题目改了改：

p = 11097356886714303582042893881171986567091401868447229878503047789761897485022302260317124893493702691228364525570373590910056115747877840029999866380610223

bs = [5387698015877849837882921423342017708155444190335961820405722215335852977335390820857481585434449016636335952770723311768916733799089117289205218502419606, 650471216782011759645022062640509711926996735020251275978971345507642644564075094156062031600261942496607624723929246244735618107358089176591848004348391, 6892903057178860129386688215569774798856400351014017060703886147768553739624962487481469668471625433585233788376496342110607517705509446954467327981630608, 10558146217032686084780873566925952381406930468404116116883569742913909418317825029965832918484884762403282735413753206846274765419932064337450818984248054, 5895415442088304335075372438017932133885868509444667400284843896831303957528388054288887813996402038199111852177790699136545463857579658675903340447062163, 5429024410614963379865219259975147383629950413248077865390569915021231258663758271426436460389815769323236013664720331435963974964648287965544449065269796, 9026061660318029970583789958687022405333849900223149905948914743741240152082556310642216826239157255360498393220970025247084970629707295326151787097739470, 9987787428206816995850349762789606634812404454347812646058676687395659473474197306399216159790010449792477748167622035909410465377793292190006286746423274, 2219882147954108708840577265969694482093318909707767606354094905609717560942016128151728113851186281314135963004282045018374113530058586118814069243919529, 448757898952195794732591529111692253250164310530502726405668619180155713699029254781106387718875294003380948759606096353377052975496257750540980902200778, 5758653512060580754844348908481795573915995758307454610577312717012029063801642812799241752795878752846316566511482026158363885685586463754255822907693695, 451407923140660945242455996808809564152178783574163893129896751571955655419694047302205795680988585534903177540569006476372988386974713491023439929159026, 633230505240984785152032107199697607142942221176494363282719218090842541716845224386067665579315266043773982412795676744597305708356598867728704864589776, 1873190106392837354104400680537195411114254251102350148513372284223841924186325948790777253558186704552585713605684421787221410972907036097255365624473450, 2378344617083543424448032167509636924990155019932249453905019078602008117706158987527488527042698261839476468330013047487417876731137315873798888588470222, 2041490918666445400155338029718590811728321100435361255475667686435257229236970377627380175478356582980165642805265465423479765728673033124872546566385586, 5562161572200618028354345987299340111930078299847265710086174356409817095136403822321442138703607136459753226468060755767359990809912165191525799668695194, 5747234564119121785321011246727969704422611840072385774157664049108853751368346706805693382579294969825994862268640942182569121253716853132907345764307939, 8711521062723349590043059489855073535946052234990913757437890347386107248179336560218502066046421074197588333654807876448053668867474787637034338684918646, 3315012579877772110918215314158524960614627244604284637905444215220273580285487157686581740829048820736622528444258472998857688206632723701316565735733441, 5546154726961135678231117496318693445209508601072296509072183409019567463552371689350178057966104310171589572056336776559176855351086359177629932234196550, 3210029904188905528418762865762860869303323377258665972527427212116198548111352207058446069365253354674921968880673880399786725395578776350248179308628748, 10843936556611444261236981575784285818543127684649594185908397301964934586327913247825082747331673594235701670093030132266375809586461029560547000376976259, 6109998016677649914877201823404560484970816089875676710769267944367498990120567697221448844101964580968840400803344669148726692092294926446783659619214576, 5845789000584380610984539779605991403432667349729999673859641615898065218110678683119040475240751804243020389180781027199152636556329114964903206159902529, 2978206364062142507924182683147186917280271225942784082942105053728393144909546285722973282439828908940095850686786079027997116957290187820185190955763478, 6172828045950561259361364955607904722730989822468578500079867327320412590167223290116851092240394293157176976858784303537724018502930568835611443150651565, 7276734264264156394849232946266365251451947245412208586150565621876731163850573337504381487556687197688905647923429178659520220297621303831067919313410263, 3174250935189051073896846162393872594492003965678114695568417093691366243434525958022465816335752281251528544505448643745253787429411926831986289204883674, 6093691251666218937687383630438296270086788146989761585751750001923551024830181398231345750563441889348377747370613585331834029372443912918336983092300186, 10096646446971081026853706495186301279465296233138748560834746144164615654055150736814340732777289692486966572132768416035838287881181678294741435773964909, 8910382579772641305873435379231059340173429305417698402532090276346045435768234779190862149435094577890323386387056525014327144178759659119217204400714683, 3933072529238941268900040999537821261948444537912919914446421661923109677382310237583616922988592740560036795345194304129614194476572206993895859654990035, 5297616631647713320273614376028978020531793358568039411666823922639911828340747099895808672237065841708616332085783027624376509371773096431136618023286834, 5257516673290708095813773480275744141704872613428524210965419462561140237627111403201960099316667611246891201897039938627093157883750555046439973809189882, 10258024129168788280748704276949204673517069302816996431976512552153603914212946110648682507216486336629396614508777344247540495198173116870062239473007726, 109420448594931913569612908119015744722217665784121695843519143728750932074310599152460322892779794568077023248786450716381443084154979030492351498361925, 4748868717171457081934731961849037503853518293108190435095345896237075826383529119745072366847766895101020323142681923650076340134187570278669989702218781]

rs = [3315, 30170, 9642, 18143, 17691, 48991, 58031, 41460, 5285, 39039, 62495, 22239, 1453, 59877, 22876, 60799, 26800, 16142, 63558, 27836, 26849, 57671, 1866, 45222, 55869, 40139, 18220, 21401, 27625, 36526, 31195, 45689, 43974, 45140, 45960, 31932, 18782, 25973]

A = []
B = []
for i in range(len(bs)):
    A.append(int(bs[i] * gmpy2.invert(2**16, p)))
    B.append(int(-rs[i] * gmpy2.invert(2**16, p)))

M = Matrix(QQ, 40, 40)
for i in range(38):
    M[i, i] = p
    M[38, i] = A[i]
    M[39, i] = B[i]
M[38, 38] = (2 ^ 496)/p
M[39, 39] = 2 ^ 496
res = M.LLL()
print(res[0])

SICTF Round2

大部分都是随手出的题就不往上放了。

签到题来咯！（赛后）

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

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
e = getPrime(10)
n = p*q
c1 = pow(114*m+2333,e,n)
c2 = pow(514*m+4555,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

'''
n = 18993579800590288733556762316465854395650778003397512624355925069287661487515652428099677335464809283955351330659278915073219733930542167360381688856732762552737791137784222098296804826261681852699742456526979985201331982720936091963830799430264680941164508709453794113576607749669278887105809727027129736803614327631979056934906547015919204770702496676692691248702461766117271815398943842909579917102217310779431999448597899109808086655029624478062317317442297276087073653945439820988375066353157221370129064423613949039895822016206336117081475698987326594199181180346821431242733826487765566154350269651592993856883
c1 = 3089900890429368903963127778258893993015616003863275300568951378177309984878857933740319974151823410060583527905656182419531008417050246901514691111335764182779077027419410717272164998075313101695833565450587029584857433998627248705518025411896438130004108810308599666206694770859843696952378804678690327442746359836105117371144846629293505396610982407985241783168161504309420302314102538231774470927864959064261347913286659384383565379900391857812482728653358741387072374314243068833590379370244368317200796927931678203916569721211768082289529948017340699194622234734381555103898784827642197721866114583358940604520
c2 = 6062491672599671503583327431533992487890060173533816222838721749216161789662841049274959778509684968479022417053571624473283543736981267659104310293237792925201009775193492423025040929132360886500863823523629213703533794348606076463773478200331006341206053010168741302440409050344170767489936681627020501853981450212305108039373119567034948781143698613084550376070802084805644270376620484786155554275798939105737707005991882264123315436368611647275530607811665999620394422672764116158492214128572456571553281799359243174598812137554860109807481900330449364878168308833006964726761878461761560543284533578701661413931
'''

没看出来是Franklin Reiter攻击，这次做题又把这个攻击方式回顾了一遍：

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

n = 18993579800590288733556762316465854395650778003397512624355925069287661487515652428099677335464809283955351330659278915073219733930542167360381688856732762552737791137784222098296804826261681852699742456526979985201331982720936091963830799430264680941164508709453794113576607749669278887105809727027129736803614327631979056934906547015919204770702496676692691248702461766117271815398943842909579917102217310779431999448597899109808086655029624478062317317442297276087073653945439820988375066353157221370129064423613949039895822016206336117081475698987326594199181180346821431242733826487765566154350269651592993856883
c1 = 3089900890429368903963127778258893993015616003863275300568951378177309984878857933740319974151823410060583527905656182419531008417050246901514691111335764182779077027419410717272164998075313101695833565450587029584857433998627248705518025411896438130004108810308599666206694770859843696952378804678690327442746359836105117371144846629293505396610982407985241783168161504309420302314102538231774470927864959064261347913286659384383565379900391857812482728653358741387072374314243068833590379370244368317200796927931678203916569721211768082289529948017340699194622234734381555103898784827642197721866114583358940604520
c2 = 6062491672599671503583327431533992487890060173533816222838721749216161789662841049274959778509684968479022417053571624473283543736981267659104310293237792925201009775193492423025040929132360886500863823523629213703533794348606076463773478200331006341206053010168741302440409050344170767489936681627020501853981450212305108039373119567034948781143698613084550376070802084805644270376620484786155554275798939105737707005991882264123315436368611647275530607811665999620394422672764116158492214128572456571553281799359243174598812137554860109807481900330449364878168308833006964726761878461761560543284533578701661413931


def GCD(a,b):
    if b == 0:
        return a.monic()
    else:
        return GCD(b,a % b)
    
P.<x> = PolynomialRing(Zmod(n))

for e in trange(2**10):
    if isPrime(e):
        i=e
        f1 = (114*x+2333) ^ i - c1
        f2 = (514*x+4555) ^ i - c2
        if GCD(f1,f2)[0] != 1:
            print(long_to_bytes(int(n - GCD(f1,f2)[0])))

SHCTF

题目整体比较简单，该省的省了。

XOR

n = 20810298530643139779725379335557687960281905096107101411585220918672653323875234344540342801651123667553812866458790076971583539529404583369246005781146655852295475940942005806084842620601383912513102861245275690036363402134681262533947475193408594967684453091957401932685922178406769578067946779033282889429596341714417295489842047781388337010440309434639274398589029236213499110100040841426995862849012466514170374143655264739023758914247116354182164550612494432327931655944868705959874670536031052370968354394583880324756639698871918124498442308334232127034553164826483441746719644515097123067550594588348951855987
c = 15294238831055894095745317706739204020319929545635634316996804750424242996533741450795483290384329104330090410419090776738963732127756947425265305276394058773237118310164375814515488333015347737716139073947021972607133348357843542310589577847859875065651579863803460777883480006078771792286205582765870786584904810922437581419555823588531402681156158991972023042592179567351862630979979989132957073962160946903567157184627177910380657091234027709595863061642453096671316307805667922247180282486325569430449985678954185611299166777141304330040782500340791721548519463552822293017606441987565074653579432972931432057376
e = 65537
p⊕q = 66138689143868607947630785415331461127626263390302506173955100963855136134289233949354345883327245336547595357625259526618623795152771487180400409991587378085305813144661971099363267511657121911410275002816755637490837422852032755234403225128695875574749525003296342076268760708900752562579555935703659615570

给了$p\oplus q$，网上随便找了个分解脚本梭哈了：

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

def check_cong(k, p, q, n, xored=None):
    kmask = (1 << k) - 1
    p &= kmask
    q &= kmask
    n &= kmask
    pqm = (p*q) & kmask
    return pqm == n and (xored is None or (p^q) == (xored & kmask))

def extend(k, a):
    kbit = 1 << (k-1)
    assert a < kbit
    yield a
    yield a | kbit

def factor(n, p_xor_q):
    tracked = set([(p, q) for p in [0, 1] for q in [0, 1]
                   if check_cong(1, p, q, n, p_xor_q)])

    PRIME_BITS = int(math.ceil(math.log(n, 2)/2))

    maxtracked = len(tracked)
    for k in range(2, PRIME_BITS+1):
        newset = set()
        for tp, tq in tracked:
            for newp_ in extend(k, tp):
                for newq_ in extend(k, tq):
                    # Remove symmetry
                    newp, newq = sorted([newp_, newq_])
                    if check_cong(k, newp, newq, n, p_xor_q):
                        newset.add((newp, newq))

        tracked = newset
        if len(tracked) > maxtracked:
            maxtracked = len(tracked)
    print('Tracked set size: {} (max={})'.format(len(tracked), maxtracked))

    # go through the tracked set and pick the correct (p, q)
    for p, q in tracked:
        if p != 1 and p*q == n:
            return p, q

    assert False, 'factors were not in tracked set. Is your p^q correct?'


n = 20810298530643139779725379335557687960281905096107101411585220918672653323875234344540342801651123667553812866458790076971583539529404583369246005781146655852295475940942005806084842620601383912513102861245275690036363402134681262533947475193408594967684453091957401932685922178406769578067946779033282889429596341714417295489842047781388337010440309434639274398589029236213499110100040841426995862849012466514170374143655264739023758914247116354182164550612494432327931655944868705959874670536031052370968354394583880324756639698871918124498442308334232127034553164826483441746719644515097123067550594588348951855987
p_xor_q = 66138689143868607947630785415331461127626263390302506173955100963855136134289233949354345883327245336547595357625259526618623795152771487180400409991587378085305813144661971099363267511657121911410275002816755637490837422852032755234403225128695875574749525003296342076268760708900752562579555935703659615570
c = 15294238831055894095745317706739204020319929545635634316996804750424242996533741450795483290384329104330090410419090776738963732127756947425265305276394058773237118310164375814515488333015347737716139073947021972607133348357843542310589577847859875065651579863803460777883480006078771792286205582765870786584904810922437581419555823588531402681156158991972023042592179567351862630979979989132957073962160946903567157184627177910380657091234027709595863061642453096671316307805667922247180282486325569430449985678954185611299166777141304330040782500340791721548519463552822293017606441987565074653579432972931432057376
e = 65537

p, q = factor(n, p_xor_q)
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

近期比赛复现Vol.1

SCTF

Barter（赛后）

GoogleCTF

LCG（赛后）

巅峰极客2023

数学但高中

Simple_encryption

DASCTF 2023七月

ezDHKE

ezRSA（赛后）

NepCTF 2023

random_RSA（赛后）

WMCTF

SICTF Round2

签到题来咯！（赛后）

SHCTF

XOR

easymath

ez_rsa

e？

factorizing_n

N1CTF

e2W@rmup

近期比赛复现Vol.1

SCTF

Barter（赛后）

GoogleCTF

LCG（赛后）

巅峰极客2023

数学但高中

Simple_encryption

DASCTF 2023七月

ezDHKE

ezRSA（赛后）

NepCTF 2023

random_RSA（赛后）

WMCTF

signin

SICTF Round2

签到题来咯！（赛后）

SHCTF

XOR

easymath

ez_rsa

e？

factorizing_n

N1CTF

e2W@rmup