2022祥云杯&DASCTF X GFCTF 2022十月挑战赛

DASCTF X GFCTF 2022十月挑战赛

RSA

from Crypto.Util.number import *
from gmpy2 import iroot,invert
from binascii import hexlify,unhexlify

n_2 = 675835056744450121024004008337170937331109883435712066354955474563267257037603081555653829598886559337325172694278764741403348512872239277008719548968016702852609803016353158454788807563316656327979897318887566108985783153878668451688372252234938716250621575338314779485058267785731636967957494369458211599823364746908763588582489400785865427060804408606617016267936273888743392372620816053927031794575978032607311497491069242347165424963308662091557862342478844612402720375931726316909635118113432836702120449010
n_3 = 91294511667572917673898699346231897684542006136956966126836916292947639514392684487940336406038086150289315439796780158189004157494824987037667065310517044311794725172075653186677331434123198117797575528982908532086038107428540586044471407073066169603930082133459486076777574046803264038780927350142555712567
e_1 = 65537
e_2 = 3
c_1 = 47029848959680138397125259006172340325269302342762903311733700258745280761154948381409328053449580957972265859283407071931484707002138926840483316880087281153554181290481533
c_2 = 332431
c_3 = 11951299411967534922967467740790967733301092706094553308467975774492025797106594440070380723007894861454249455013202734019215071856834943490096156048504952328784989777263664832098681831398770963056616417301705739505187754236801407014715780468333977293887519001724078504320344074325196167699818117367329779609
m = 9530454742891231590945778054072843874837824815724564463369259282490619049557772650832818763768769359762168560563265763313176741847581931364
k = 8139616873420730499092246564709331937498029453340099806219977060224838957080870950877930756958455278369862703151353509623205172658012437573652818022676431

# for i in range(0,1000000):
#     if(iroot(c_2+i*(n_2),3)[1]):
#         print("n_1 =",iroot(c_2+i*(n_2),3)[0])
#         break
n_1 = 70406706457855863712635967741447303613971473150228480705119773604469794649140239446237334040048504811343327173817296308781190911727763110615393368497803655390445303946160971
p = 2224243981
q = 2732337821
r = 11585031296201346891716939633970482508158508580350404805965250133832632323150440185890235814142601827544669601048550999405490149435265122374459158586377571
phi = (p-1)*(q-1)*(r-1)
d = invert(e_1,phi)
m1 = pow(c_1,d,n_1)
m1 = long_to_bytes(m1)
print(m1)
print(long_to_bytes(int(str(m1)[4:-1],16)))
m2 = long_to_bytes(m)
print(unhexlify(m2))
# b'0x666c61677b3230366538353964'
# b'flag{206e859d'
# b'859d8e854c4f600cb12757bbf9f5}'

十月刷题记录

[GUET-CTF2019]BabyRSA

import sympy
import gmpy2
from Crypto.Util.number import long_to_bytes
p_q = 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
p_1q_1 = 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e  = 0xe6b1bee47bd63f615c7d0a43c529d219
d  = 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag = 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

p = sympy.Symbol('p')
q = sympy.Symbol('q')
f1 = p + q
f2 = (p+1)*(q+1)
x = sympy.solve([f1-p_q,f2-p_1q_1],[p,q])[0]
p = 7021910101974335245794950722131367118195509913680915814438898999848788125908122655583911434165700354149914056221915541094395668546921268189522005629523759
q = 8228801334907462855397256098699556584084854642543205682719705217859576250443629616812386484797164506834582095674143447181804355696220642775619711451990971
# print(gmpy2.is_prime(q)&gmpy2.is_prime(p)) True
n = p*q
phi = (p-1)*(q-1)
m = pow(enc_flag,d,n)
mm = long_to_bytes(m)
print(mm)

祥云杯

common_rsa

import gmpy2
from Crypto.Util.number import long_to_bytes,getPrime,inverse
import binascii

n = 253784908428481171520644795825628119823506176672683456544539675613895749357067944465796492899363087465652749951069021248729871498716450122759675266109104893465718371075137027806815473672093804600537277140261127375373193053173163711234309619016940818893190549811778822641165586070952778825226669497115448984409
e = 31406775715899560162787869974700016947595840438708247549520794775013609818293759112173738791912355029131497095419469938722402909767606953171285102663874040755958087885460234337741136082351825063419747360169129165
c = 97724073843199563126299138557100062208119309614175354104566795999878855851589393774478499956448658027850289531621583268783154684298592331328032682316868391120285515076911892737051842116394165423670275422243894220422196193336551382986699759756232962573336291032572968060586136317901595414796229127047082707519
p = 	12080882567944886195662683183857831401912219793942363508618874146487305963367052958581455858853815047725621294573192117155851621711189262024616044496656907
q = n//p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# b'flag{9aecf8d8-6966-4ffa-96b0-2e744d28baf2}'

tracing

from Crypto.Util.number import *
c = 64885875317556090558238994066256805052213864161514435285748891561779867972960805879348109302233463726130814478875296026610171472811894585459078460333131491392347346367422276701128380739598873156279173639691126814411752657279838804780550186863637510445720206103962994087507407296814662270605713097055799853102

n = 113793513490894881175568252406666081108916791207947545198428641792768110581083359318482355485724476407204679171578376741972958506284872470096498674038813765700336353715590069074081309886710425934960057225969468061891326946398492194812594219890553185043390915509200930203655022420444027841986189782168065174301

e=65537
f=open(r'tracing/trace.out','rb')
arr = f.readlines()
#以'\n'作为分隔 读取成为 <class 'bytes'>
b = 0
a = 1

def isOdd(a):
    return a & 1 == 1
def rshift1(a):
    return a << 1
def lshift(a, s):
    return a >> s

for i in arr[::-1]:
    if (b"a, b = b, a" in i):
        a, b = b, a
    if (b'a = rshift1(a)' in i):
        a=rshift1(a)
    if (b'b = rshift1(b)' in i):
        b=rshift1(b)
    if (b'a = a - b' in i):
        a = a + b
d=inverse(65537,a)
m=pow(c,d,n)
print(long_to_bytes(m))
b'flag{a526344-a8c7-411d-bf53-ef6a2479de1a}'

little little fermat

解法一

from Crypto.Util.number import * 
from random import * 
from libnum import * 
import gmpy2 
from itertools import combinations, chain 

e = 65537 
n = 14132106732571642637548350691522493009724686596047415506904017635686070743554027091108158975147178351963999658958949587721449719649897845300515427278504841871501371441992629
9248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393 
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828
498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883 
tp = [gmpy2.mpz(1 << i) for i in range(512)] 
it = chain(*[combinations(range(3, 417 - 3), i) for i in range(4)]) 
for cf in it: 
   A = -sum([tp[i] for i in cf]) 
   D = A**2 + 4 * n 
   if gmpy2.is_square(D): 
       d = gmpy2.isqrt(D) 
       p = (-A + d) // 2 
       q = n // p 
       break 
x=p-1 
d = pow(e, -1, (p - 1) * (q - 1)) 
m=pow(c, d, n) 
print(long_to_bytes(m^(x**2)))
# b'flag{I~ju5t_w@nt_30_te11_y0u_how_I_@m_f3ll1ng~}45108#@7++3@79?3328?!!@08#712/+963-60#9-/83#+/1@@=59!/84@?3#4!4=-9542/##'

#https://blog.maple3142.net/2022/07/18/cryptoctf-2022-writeups/#sparse
#3. medium-hard 
#3.3. Sparse

解法二

import gmpy2
from Crypto.Util.number import long_to_bytes,inverse,isPrime,bytes_to_long

n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
p = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734646483980612727952939084061619889139517526028673988305393
q = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734648016476153593841839977704512156756634066593725142934001
e = 65537
x = q - 1
phi = ( p - 1 ) * ( q - 1 )
d = inverse(e,phi)
m = pow(c,d,n)
x = x ** 2
flag = m ^ x
print(long_to_bytes(flag))
# print(pow(114514,p-1,p))
# b'flag{I~ju5t_w@nt_30_te11_y0u_how_I_@m_f3ll1ng~}45108#@7++3@79?3328?!!@08#712/+963-60#9-/83#+/1@@=59!/84@?3#4!4=-9542/##'

babyDLP

# Arr3stY0u 脚本
# TeamGipsy 脚本
EDI EDI安全

from Crypto.Util.number import *
from pwn import *
import gmpy2
context.log_level = 'debug'
p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
def get_root(x,p):
    # g^x==4 mod p
    gg,a,b=gmpy2.gcdext(x,p-1)
    if gg==2:
        t=pow(4,a,p)
        g=pow(t,(p+1)//4,p)
        return g
    elif gg==1:
        return pow(4,a,p)
s='1'
r=remote('47.95.3.91', 42259)
while True:
    r.sendline('t')
    g=get_root(int(s,2),p)
    r.sendline(str(g))
    r.recvuntil(' desired integer: \n')
    tr=r.recvline()
    if b'flag' in tr:
        print(tr)
        break
    tt,rr=eval(tr[8:])
    if tt==1:
        s=s+'1'
    else:
        if s[-1]=='1':
            s=s[:-1]+'0'
    print(s)
r.interactive()

leak

# TeamGipsy 脚本
->https://mp.weixin.qq.com/s/4JVUFZ-pAMqoF8ZxSiolWA

fill

#sagemath
from gmpy2 import *
import hashlib
nbits = 32
n = 991125622
S = 492226042629702
s = [562734112, 859151551 ,741682801]
M = [19621141192340, 39617541681643, 3004946591889, 6231471734951, 3703341368174, 48859912097514, 4386411556216, 11028070476391, 18637548953150, 29985057892414, 20689980879644, 20060557946852, 46908191806199, 8849137870273, 28637782510640, 35930273563752, 20695924342882, 36660291028583, 10923264012354, 29810154308143, 4444597606142, 31802472725414, 23368528779283, 15179021971456, 34642073901253, 44824809996134, 31243873675161, 27159321498211, 2220647072602, 20255746235462, 24667528459211, 46916059974372]
m = (s[2] - s[1])*invert(s[1]-s[0],n)%n
mm = 55365664
c = (s[1] - s[0]*m) % n
cc = 8712091
print(m,m.bit_length())
print(c,c.bit_length())
seed = s[0]
s = [0] * nbits
s[0] = seed
for i in range(1,nbits):
    s[i] = (s[i-1] * m + c) % n
for i in range(nbits):
    M[i] = M[i] - s[i]
def solve(suq_a, c, n):
    A = Matrix(ZZ, n + 1, n + 1) # 构造一个(n+1)x(n+1)维的矩阵
    for i in range(n):
        A[i, i] = 1
    for i in range(n):
        A[i, n] = suq_a[i]
    A[n, n] = -c
    res = A.LLL()[-1] # 取结果矩阵的第一行数据
    return res
res = solve(M,S,nbits)
print(res)
mm = res
x = ''
for i in range(len(mm)):
    x += str(mm[i])
x = int(x,2)
x = f'flag{{{hashlib.sha256(str(x).encode()).hexdigest()}}}'
print(x)
# 55365664 26
# 8712091 24
# (1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0)
# flag{fdb9a9c25f1da1edb0f88669b10265b5c229b2c86ee3539a7184b9ff3bf2cfd7}