2023 羊城杯

CRYPTO

Danger_RSA

from Crypto.Util.number import *

#m = bytes_to_long(flag)


def get_key(a, nbit):
    assert a >= 2
    while True:
        X = getRandomInteger(nbit // a)
        s = getRandomRange(pow(2, a ** 2 - a + 4), pow(2, a ** 2 - a + 5))
        p = X ** a + s
        if isPrime(p):
            return (p, s)

a=5
p, s = get_key(a, 1024)
q, t = get_key(a, 1024)

print(p,q,s,t)
N = p * q
e = s * t
#c = pow(m, e, N)
print("N =", N)
print("e =", e)
#print("c =", c)
# N = 20289788565671012003324307131062103060859990244423187333725116068731043744218295859587498278382150779775620675092152011336913225797849717782573829179765649320271927359983554162082141908877255319715400550981462988869084618816967398571437725114356308935833701495015311197958172878812521403732038749414005661189594761246154666465178024563227666440066723650451362032162000998737626370987794816660694178305939474922064726534186386488052827919792122844587807300048430756990391177266977583227470089929347969731703368720788359127837289988944365786283419724178187242169399457608505627145016468888402441344333481249304670223
# e = 11079917583
# c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766

CryptoCTF 2023 原题 2023 CryptoCTF（二） (qq.com)

from gmpy2 import *
from sympy import isprime
n=20289788565671012003324307131062103060859990244423187333725116068731043744218295859587498278382150779775620675092152011336913225797849717782573829179765649320271927359983554162082141908877255319715400550981462988869084618816967398571437725114356308935833701495015311197958172878812521403732038749414005661189594761246154666465178024563227666440066723650451362032162000998737626370987794816660694178305939474922064726534186386488052827919792122844587807300048430756990391177266977583227470089929347969731703368720788359127837289988944365786283419724178187242169399457608505627145016468888402441344333481249304670223


ab = int(iroot(n,4)[0])
ab4 = ab^4

rs = 11079917583
for r in rs.divisors():
    s = rs//r
    c = n-ab4-rs
    delta = c^2-4*rs*ab4
    sdelta = int(iroot(delta,2)[0])
    a4 = (c+sdelta)//(2*s)
    if iroot(a4,4)[1]:
        a = int(iroot(a4,4)[0])
        b = int(iroot(ab4,4)[0]//a)
        if isprime(a^4+r):
            print("[+] p=",a^4+r)
            print("[+] q=",n//(a^4+r))
        elif isprime(a^4+s):
            print("[+] p=",a^4+s)
            print("[+] q=",n//(a^4+s))
            
[+] p= 5213351003420231819415242686664610206224730148063270274863722096379841592931572096469136339538500817713355302889731144789372844731378975059329731297860686270736540109105854515590165681366189003405833252270606896051264517339339578167231093908235856718285980689179840159807651185918046198419707669304960745217
[+] q= 3891889986375336330559716098591764128742918441309724777337583126578227827768865619689858547513951476952436981068109005313431255086775128227872912287517417948310766208005723508039484956447166240210962374423348694952997002274647622939970550008327647559433222317977926773242269276334110863262269534189811138319 

import random
import time
from tqdm import tqdm
from Crypto.Util.number import *
# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(d, a)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def onemod(p,r): 
    t=random.randint(2,p)
    while pow(t,(p-1)//r,p)==1: 
         t=random.randint(2,p)
    return pow(t,(p-1)//r,p) 
 
def solution(p,root,e):  
    while True:
        g=onemod(p,e) 
        may=[] 
        for i in tqdm(range(e)): 
            may.append(root*pow(g,i,p)%p)
        if len(may) == len(set(may)):
            return may


def solve_in_subset(ep,p):
    cp = int(pow(c,inverse(int(e//ep),p-1),p))
    com_factors = []
    while GCD(ep,p-1) !=1:
        com_factors.append(GCD(ep,p-1))
        ep //= GCD(ep,p-1)
    com_factors.sort()

    cps = [cp]
    for factor in com_factors:
        mps = []
        for cp in cps:
            mp = AMM(cp, factor, p)
            mps += solution(p,mp,factor)
        cps = mps
    for each in cps:
        assert pow(each,e,p)==c%p
    return cps




p= 5213351003420231819415242686664610206224730148063270274863722096379841592931572096469136339538500817713355302889731144789372844731378975059329731297860686270736540109105854515590165681366189003405833252270606896051264517339339578167231093908235856718285980689179840159807651185918046198419707669304960745217
q = 3891889986375336330559716098591764128742918441309724777337583126578227827768865619689858547513951476952436981068109005313431255086775128227872912287517417948310766208005723508039484956447166240210962374423348694952997002274647622939970550008327647559433222317977926773242269276334110863262269534189811138319
e = 11079917583
c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766

ep = 3
eq = 49
m_p = solve_in_subset(ep,p)
m_q = solve_in_subset(eq,q)

start = time.time()
print('Start CRT...')
for mpp in m_p:
    for mqq in m_q:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if solution < 2^800 :   # Always the bit_length of flag is less than 800
            print(long_to_bytes(solution))


end = time.time()
print("Finished in {} seconds.".format(end - start))

DASCTF{C0nsTruct!n9_Techn1qUe2_f0r_RSA_Pr1me_EnC2ypt10N}

SigninCrypto

from random import *
from Crypto.Util.number import *
from Crypto.Cipher import DES3
from flag import flag
from key import key
from iv import iv
import os
import hashlib
import secrets

K1= key
hint1 = os.urandom(2) * 8
xor =bytes_to_long(hint1)^bytes_to_long(K1)
print(xor)

def Rand():
    rseed = secrets.randbits(1024)
    List1 = []
    List2 = []
    seed(rseed)
    for i in range(624):
        rand16 = getrandbits(16)
        List1.append(rand16)
    seed(rseed)
    for i in range(312):
        rand64 = getrandbits(64)
        List2.append(rand64)
    with open("task.txt", "w") as file:
        for rand16 in List1:
            file.write(hex(rand16)+ "n")
        for rand64 in List2:
            file.write(hex((rand64 & 0xffff) | ((rand64 >> 32) & 0xffff) << 16) + "n")
Rand()

K2 = long_to_bytes(getrandbits(64))
K3 = flag[:8]

KEY = K1 + K2 + K3

IV=iv

IV1=IV[:len(IV)//2]
IV2=IV[len(IV)//2:]

digest1 = hashlib.sha512(IV1).digest().hex()
digest2 = hashlib.sha512(IV2).digest().hex()

digest=digest1+digest2
hint2=(bytes_to_long(IV)<<32)^bytes_to_long(os.urandom(8))
print(hex(bytes_to_long((digest.encode()))))
print(hint2)


mode = DES3.MODE_CBC
des3 = DES3.new(KEY, mode, IV)

pad_len = 8 - len(flag) % 8
padding = bytes([pad_len]) * pad_len
flag += padding

cipher = des3.encrypt(flag)

ciphertext=cipher.hex()
print(ciphertext)

# 334648638865560142973669981316964458403
# 0x62343937373634656339396239663236643437363738396663393438316230353665353733303939613830616662663633326463626431643139323130616333363363326631363235313661656632636265396134336361623833636165373964343533666537663934646239396462323666316236396232303539336438336234393737363465633939623966323664343736373839666339343831623035366535373330393961383061666266363332646362643164313932313061633336336332663136323531366165663263626539613433636162383363616537396434353366653766393464623939646232366631623639623230353933643833
# 22078953819177294945130027344
# a6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1

K1 ：hint1是2字节随机数 * 8，但是 K1不是16字节，根据 xor 可以获取道 hint1 是 'xfbxc2'，然后异或回来就能获取 K1 了

K2：MT19937，老套路了，list1和list2 是互补的，相互拼接就能得到 624 个完整的 32 字节随机数，然后往后生成一个 64 bit 随机数就好了，我这里用现成的工具生成了两个 32 比特随机数然后拼接，long_to_bytes((2007704621<<32)+1688604302)，

with open("task.txt") as f:
 data = f.read().split("n")

data = [int(i[2:],16) for i in data]
#print(data)

rand = data[:624]


index = 0
for each in data[624:]:
 rand[index] = (rand[index]<<16)+ (each & 0xffff)
 each2 = each >> 16
 rand[index+1] = (rand[index+1]<<16)+ (each2 & 0xffff)
 index+=2

print(rand)

K3：一个字节爆破，K3 = b'DASCTF{'+chr(j).encode()

IV：IV是8字节的。所以 hint2 泄露了 IV 的高四字节，通过看哈希，高四字节和低四字节是一样的，IV 是 ‘GWHTGWHT’

然后拿着 K1,K2,K3 和  IV 解密密文就好了

from random import *
from Crypto.Util.number import *
from Crypto.Cipher import DES3
# from flag import flag
# from key import key
# from iv import iv
import os
import hashlib
import secrets


hint1 = b'xfbxc2'
for j in range(128):
    xor = 334648638865560142973669981316964458403
    K1 = long_to_bytes(bytes_to_long(hint1*8)^xor)
    #print(K1)


    K2 = long_to_bytes((2007704621<<32)+1688604302)
    #K3 = flag[:8]
    K3 = b'DASCTF{'+chr(j).encode()

    KEY = K1 + K2 + K3
    #print(KEY)

    IV=b'GWHTGWHT'


    flag= 0xa6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1
    flag = long_to_bytes(flag)
    mode = DES3.MODE_CBC
    des3 = DES3.new(KEY, mode, IV)

    cipher = des3.decrypt(flag)
    if b"DASCTF" in cipher:
        print(cipher)

DASCTF{8e5ee461-f4e1-4af2-8632-c9d62f4dc073}

MCeorpkpleer

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


def pubkey(list, m, w):
    pubkey_list = []
    for i in range(len(e_bin)):
        pubkey_list.append(w * list[i] % m)
    return pubkey_list


def e_cry(e, pubkey):
    pubkey_list = pubkey
    encode = 0
    for i in range(len(e)):
        encode += pubkey_list[i] * int(e[i]) % m
    return encode


p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = getPrime(64)
m = bytes_to_long(flag)
c = pow(m, e, n)

e_bin = (bin(e))[2:]
list = [pow(3, i) for i in range(len(e_bin))]
m = getPrime(len(bin(sum(list))) - 1)
w = getPrime(64)
pubkey = pubkey(list, m, w)
en_e = e_cry(e_bin, pubkey)

print('p = {}n'
      'n = {}n'
      'c = {}n'
      'pubkey = {}n'
      'en_e = {}'.format((p >> 435) << 435, n, c, pubkey, en_e))

'''
p = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464
pubkey = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
en_e = 31087054322877663244023458448558
'''

代码写得真绕，其实就是一个背包恢复公钥指数 e + 已知 p 高位分解 n

#matrix
m=[] 
a = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]

#Pub
# a = 31087054322877663244023458448558

#enc
s = 31087054322877663244023458448558

#init lattice

for i in range(len(a)):
    b=[]
    for j in range(len(a)):
        if i == j:
            b.append(2)
        else:
            b.append(0)
    m.append(b)
 
b=[]
for i in range(len(m)):
    m[i].append(a[i])
    b.append(1)

b.append(s)
m.append(b)
#print(len(m[0])) 
M = matrix(ZZ, m)
print("Start LLL")
ML = M.LLL()
for each in ML:
    for i in each:
        if i == 1 or i == -1 or i==0:
            pass
        else:
            break
    else:
        v = each
print(v)
flag=''
for i in v[:-1]:
    if i < 0:
        flag+='1'
    else:
        flag+='0'

sage: flag
'1101110101111111101010101111101101001110100000010000100001010011'
sage: int(flag,2)
15960663600754919507

p = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464
R.<x> = Zmod(n)[]
f = p+x
x = f.small_roots(X=2^235,beta=0.49,epsilon=0.02)[0]
p = int(f(x))
q = int(n//p)
phi=(p-1)*(q-1)
e=15960663600754919507
d=inverse(e,phi)
long_to_bytes(pow(c,d,n))

DASCTF{T81I_tPPS_6r7g_xlPi_OO3M_6vyV_Rkba}

Easy_3L

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

m = bytes_to_long(flag)


def get_key():
    p = getPrime(1400)
    f = getRandomNBitInteger(1024)
    while True:
        q = getPrime(512)
        if gcd(f, q) != 1:
            continue
        else:
            break
    h = (invert(f, p) * q) % p
    return p, h


def encrypt1(m):
    a = getPrime(250)
    b = getRandomNBitInteger(240)
    n = getPrime(512)
    seed = m
    s = [0] * 6
    s[0] = seed
    for i in range(1, 6):
        s[i] = (s[i - 1] * a + b) % n
    return s


def encrypt2(msg, p, h):
    s = getRandomNBitInteger(512)
    c = (s * h + msg) % p
    return c


s = encrypt1(m)
print("S1 =", s[1])
print("S2 =", s[2])
print("S4 =", s[4])
print("S5 =", s[5])

p, h = get_key()
c = encrypt2(s[3], p, h)
print("p =", p)
print("h =", h)
print("c =", c)

# S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
# S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
# S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
# S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
# p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
# h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
# c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287

又是套娃，LCG 套 NTRU

NTRU部分

from Crypto.Util.number import *

def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return (m)


q,h = (25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351, 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711)
e = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287
M = matrix(ZZ,[[1,h],[0,q]])
ML = M.LLL()
f,g = ML[0]
f = abs(f)
g = abs(g)


print(decrypt(q, h, f, g, e))


m = 10700695166096094995375972320865971168959897437299342068124161538902514000691034236758289037664275323635047529647532200693311709347984126070052011571264606

LCG部分

from Crypto.Util.number import *
from functools import reduce


def gcd(a, b):
    while b:
        a, b = b, a%b
    return a


def crack_unknown_increment(states, modulus, multiplier):

    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment


def crack_unknown_multiplier(states, modulus):

    multiplier = (states[2] - states[1]) * inverse(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)


def crack_unknown_modulus(states):

    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    #print(modulus)
    return crack_unknown_multiplier(states, modulus)


def lcg(seed,params):

    (m,c,n)=params
    x = seed % n
    yield int(x)
    while True:
        x = (m * x + c) % n
        yield int(x)



mm = [28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141,
1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888,
10700695166096094995375972320865971168959897437299342068124161538902514000691034236758289037664275323635047529647532200693311709347984126070052011571264606,
9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997,
9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736]



(n,m,c)=crack_unknown_modulus(mm)

print(n,m,c)

#x = (m * x + c) % n

ff = (mm[0]-c) * inverse(m,n) % n
from Crypto.Util.number import *
print(long_to_bytes(ff))

DASCTF{NTRU_L0G_a6e_S1mpLe}

XOR贯穿始终

自由和谐和谐富强公正友善爱国公正法治法治文明和谐自由法治自由法治平等公正友善公正公正民主法治自由公正敬业和谐富强公正友善爱国和谐平等平等友善敬业法治敬业和谐富强法治平等平等友善敬业公正公正公正友善敬业法治平等平等诚信自由公正自由平等友善敬业公正友善法治和谐和谐

怎么还混入编码了，社会主义核心价值观加密/解密 http://www.atoolbox.net/Tool.php?Id=850

C0ngr4tulati0n5_y0u_fou^d_m3

from gmpy2 import gcd
from Crypto.Util.number import getPrime
from secret import enflag

p = getPrime(512)
q = getPrime(512)
n = q * p
phi = (p - 1) * (q - 1)
e = getPrime(17)
assert gcd(e, phi) == 1
# 以上信息生成了私钥文件,但文件被损坏了你能提取有用信息吗

c = pow(enflag, e, n)
print('c = ' + str(c))

'''
c = 91817924748361493215143897386603397612753451291462468066632608541316135642691873237492166541761504834463859351830616117238028454453831120079998631107520871612398404926417683282285787231775479511469825932022611941912754602165499500350038397852503264709127650106856760043956604644700201911063515109074933378818
'''

-----BEGIN PRIVATE KEY-----
MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBALmtMy+2uH1ZtbIL
SuiAukFthyQRH5mp7UmLyzZQkdg9zEP9/5tgffikQ7ytx5kHySHnazgAO1sOzmYE
N4Axlev6uafiP8B1Eij97v5VkYJ1I9e3mtBNheTbXKoT8op+ASQ1fQaF4A8UzLuW
eZeZI8JTH/SH+bolAK3kiZXDFdkTAgMBAAECgYEAl067LaC7Cvs2A5cMPhfYsESv
IgcKN1CwW4Sd3u8dSphhgu7TgyzIuvwxbuo2g1BC6WwKhaI6vGN+csfw6nh98GEn
/p3D0huNroAYvf/DRRB9UnHdttX7wB+Mv3P0RBDWHgBiCDVvHFuFUV78cIs0tnbn
jxjU07aPV2XRC3AfA2ECQQDqWUNPVg3i6vTyHCL7EGkbeUheYpAAfcKCQrxjc5+5
X6A+XtgHAA1JHwykPlCpHUOmlA85DJF1ejuoImzlgRLJAkEAytTCnQF+MN2r1gaA
UETZyj5qMYT7Th8zKEVVVJjDawLnuX4usJ2FyRnjCkk86U75QSJhw5mMc0QnG25u
Gz3++w==
-----END PRIVATE KEY-----

base64解码转 hex，然后根据 pem 文件格式进行私钥解析

30820277020100300d06092a864886f70d0101010500048202613082025d020100028181
# n
0x0b9ad332fb6b87d59b5b20b4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece660437803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb9679979923c2531ff487f9ba2500ade48995c315d913
02030
# e
10001  
028181# d 
00974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361024100# pea59434f560de2eaf4f21c22fb10691b79485e6290007dc28242bc63739fb95fa03e5ed807000d491f0ca43e50a91d43a6940f390c91757a3ba8226ce58112c9024100# qcad4c29d017e30ddabd606805044d9ca3e6a3184fb4e1f332845555498c36b02e7b97e2eb09d85c919e30a493ce94ef9412261c3998c7344271b6e6e1b3dfefb

得到 d 0x974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361

然后RSA解密

>>> pow(c,d,n)
569500674440382717905452096996762310441626465967827040670978692492730930260454816484735928634446L
>>> long_to_bytes(_)
'DASCTF{0e287wQx08Rx17x00FGXYFZx07Vx03kIUCnx02VDgx01fx0cN'

明文的低位被异或了，

压缩包里有提示：钥匙先别扔掉，万一后面还有用呢

所以把这个 和  C0ngr4tulati0n5_y0u_fou^d_m3 异或一下

>>> bytes_to_long('C0ngr4tulati0n5_y0u_fou^d_m3')
7075847009007829264439049254909489230451066419147221546551444729139L
>>> long_to_bytes(pow(c,d,n)^_)
'DASCTF{0e2874af5e422482378640e61d919e9a}'

DASCTF{0e2874af5e422482378640e61d919e9a}

esyRSA

from gmpy2 import invert
from hashlib import md5
from secret import p, q

e = ?????
n = p*q
phi = (p-1)*(q-1)
d = invert(e, phi)
ans = gcd(e,phi)

print n, e, d
print "Flag: DASCTF{%s}" %md5(str(p + q)).hexdigest()

"""
n = 8064259277274639864655809758868795854117113170423331934498023294296505063511386001711751916634810056911517464467899780578338013011453082479880809823762824723657495915284790349150975180933698827382368698861967973964030509129133021116919437755292590841218316278732797712538885232908975173746394816520256585937380642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
"""

这题更是无力吐槽，代码写的稀巴烂，n还给错了

这里的n复制了两次，原来的 n 是 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373

然后 e  给了五个问号，所以不大，直接维纳攻击或者 boneh_durfee 就可以解得 13521

然后已知 e,d 分解 n 就可以了

e = 13521
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913

from gmpy2 import gcd
from random import *
  
def factor_n_with_ed(n,e,d):  
    p = 1  
    q = 1  
    while p==1 and q==1:  
        k = d * e - 1  
        g = -randint(0,n)
        while p==1 and q==1 and k % 2 == 0:  
            k //= 2  
            y = pow(g,k,n)  
            if y!=1 and gcd(y-1,n)>1:  
                p = gcd(y-1,n)  
                q = n//p  
    return p,q
print(factor_n_with_ed(n,e,d))
p  = 10181341212828413853336916619161138854377885230386496425058202154486415709366161346816273366144505351043947477469664133317598479763451392984403646602585037
q = 7920625690369490250766357750388349704260128405941822835255851274284409978206593795103040446837018619894098452542488850045009467407103749792461438242280929

print(md5(str(p + q).encode()).hexdigest())

4ae33bea90f030bfddb7ac4d9222ef8f