Ctf crypto: String crypto · Курс молодого CTF бойца v 1.5

  def genkey (nbit):
    в то время как True:
        p, q = getPrime (nbit), getPrime (nbit)
        if gcd ((p-1) // 2, (q-1) // 2) == 1:
            P, Q = (q-1) // 2, (p-1) // 2
            r = обратный (Q, P)
            е = 2 * г * Q - 1
            возврат (p, q, e)

def encrypt (msg, pubkey):
    e, n = pubkey
    вернуть pow (bytes_to_long (msg), e, n)
  

  из импорта Crypto.Util.number *
импортная математика

def derive_e (p, q):
P, Q = (q-1) // 2, (p-1) // 2
г = pow (Q; -1; P)
е = 2 * г * Q - 1
вернуть е

N = 177564531812671757618131662484345167792122794138983211109389551387549629559478410214883571512678939653547041686848567423183950948698379284488194109758
20877472968227711640216343330193184235164710328845507199362646489303138765492026284976828397217700058854699501312701069850748706050896660281521826421577811533118718010597292033378006728085404811309462279999611838337634021778212294558626288745086362085621437525865936230074347122941073540018999235922055196144158063074002285730451489574517481352975876675873350653869693395028213098495559488151733
3877
06466633380921338845195921235252323721
flag_enc = 821634474333140
05831776342200252705923796193752552649425282859227400617284746437075756157249953578189229459392338128783031841882560801175367779263048253787547952450480816724222285583987363793884961526545550108715847375346137865114137
27506957702375732452598640804768960184186521954448243004125
58942654500736501019422246293893
8217359988866888133937177183763
83679812248535071935556786120146664176700930317926014136576602368078825068852452899295285724380832277291
73810885478353692596774819973451373878214205560507708169428542522843559753653510138036019639
403849614198536

m = bytes_to_long (b'0 ')
кт = 81318810802150
48746640667437604424712020981611880694236897307355197954729272187834734645252608142276060679
57457604813200474240351777562057279323259869333476564175883027146040576242710605228346830427359670501468710670658892889236
372036025492345850000988528165447814459294233776775431513084429476275523786450668955298777656088135728572762982716831509944611274681961181265871598110468456603820675085450111755868116701855834309297184745623927049652098555126342100576188575279707161689744307542342529954295940519235056325177719366827352338997812935
366884885020756981

q = математика.gcd (ct - m, N)
утверждать isPrime (q)
p = N // q
е = derive_e (p, q)
d = pow (e, -1, (p-1) * (q-1))
m = pow (flag_enc, d, N)
печать (long_to_bytes (м))
  

  #! / Usr / bin / python

от Crypto.Импорт Util.number *
из секретного импорта m, n, x, y, flag

p, q = x ** (m + 1) - (x + 1) ** m, y ** (n + 1) - (y + 1) ** n
assert isPrime (p) и isPrime (q) и p  

  #! / Usr / bin / python3
из Crypto.Util.number import long_to_bytes
из gmpy2 import invert, is_prime
из tqdm импорт tqdm

простые числа = []

для xy в tqdm (диапазон (500)):
    для mn в диапазоне (500):
        простое число = ху ** (тп + 1) - (ху + 1) ** тп
        если премьер.bit_length ()> 2048: перерыв
        если is_prime (простое число):
            primes.append (простое число)

с = 1460847413295235232889708071732546430843832262331984742844793394320242127083779399847708301424667310196530234834
062655934244065705032549531016125948268383108879698723118735440224501070612559381488973867339949208410120554358243554988672501793432431342039566921839273633319559556862946851036282506651270800836026811372480074872738966382668652678105183848502430499525634166088288835145414705795688786135114799585596506505555357140161761871724188274546128208872045878153092716215744
660389647711254669394
7245216262
272010814738087
3244711311698792435222513388474103420001421

для i в диапазоне (len (простые числа)):
    для j в диапазоне (i, len (простые числа)):
        pq = простые числа [i] * простые числа [j]
        если len (bin (pq) [2:]) == 2048:
            пытаться:
                d = инвертировать (0x10001, (простые числа [i] -1) * (простые числа [j] -1))
                dec = long_to_bytes (pow (c, d, pq))
                если b "CCTF" в dec:
                    печать (dec)
            кроме ValueError:
                проходить
  
 Флаг 
  CCTF {0N3_1! NE_CrYp7O_iN_202O} 
 Эффект бабочки 
 Вызов 
 Вы слышали об эффекте бабочки в теории хаоса?
 У нас очень наглядный образец!
  def hq_prng (x, p, g):
    rng = 0
    для _ в диапазоне (getRandomNBitInteger (14)):
        х = pow (g, x, p)
    для i в диапазоне (nbit):
        х = pow (g, x, p)
        если x <(p-1) // 2:
            rng + = 2 ** я - 1
        elif x> (p-1) // 2:
            rng - = 2 ** я + 1
        еще:
            rng ^ = 2 ** (я + 1)
    если rng <= 0:
        return -rng
    возвратный звонок

def keygen (p, g):
    r, s = hq_prng (getRandomNBitInteger (nbit), p, g), hq_prng (getRandomNBitInteger (nbit), p, g)
    и, v = gmpy2.next_prime (r ** 2 + s ** 2), gmpy2.next_prime (2 * r * s)
    е, п = 0x10001, и * v
    вернуть e, n

def encrypt (msg, e, n):
    вернуть pow (bytes_to_long (msg.encode ('utf-8')), e, n)

| шифруют (флаг, е, п) = 11766758294702630748270985031821482016596498049541442371160861468107503654695
8808368292873415023810025855494234856062831966
211512140886278545717992674137541201362047155400299634
043663153514223748501458524468683473984628847846
312507115087057705
103989678439960043788163169606969942
| (Р, г, п) = (6839693299972
4628292736055
231980
4894620521363257317833167L, 1114840866365636893
10456704759
88378384611325239859308138541650L, 1744210031238100333817
221837856515717326
620972514408538503841677183124321812193934320473
42573392
995456170219203738445267182920854405200580
112727672179973733495396216086101041988492895531950766664805075406312493730029215085806581713874721280621739864343621647737777392
1017939L)
 
 Решение 
 Начнем с осознания того, что данное значение $ g $ на самом деле не является генератором $ \ mathbb {F} _p $.2 + 1000) \ cdot (2x_ix_j + 1000) \) верно. Это сокращает количество пар для вычисления. Кроме того, если мы зафиксируем $ x_i $, значения $ x_j $, которые удовлетворяют этому неравенству, образуют интервал. Следовательно, можно использовать двоичный поиск для эффективного вычисления этого интервала. Это достаточно эффективно для поставленной задачи.
 Реализация 
  из импорта Crypto.Util.number *

р = 6839693299972
4628292736055231980
4894620521363257317833167
г = 1114840866365636893
10456704759
88378384611325239859308138541650
N = 1744210031238100333817221837856515717326
620972514408538503841677183124321812193934320473
42573392
995456170219203738445267182920854405200580
112727672179973733495396216086101041988492895531950766664805075406312493730029215085806581713874721280621739864343621647737777392
1017939
с = 11766758294702630748270985031821482016596498049541442371160861468107503654695
8808368292873415023810025855494234856062831966
211512140886278545717992674137541201362047155400299634
043663153514223748501458524468683473984628847846
312507115087057705
103989678439960043788163169606969942
 е = 0x10001
def hq_prng (x, p, g):
 глобальный rsf;
 rng = 0
 для i в диапазоне (256):
 x = rsf [x]
 если x <(p-1) // 2:
 rng + = 2 ** я - 1
 elif x> (p-1) // 2:
 rng - = 2 ** я + 1
 еще:
 rng ^ = 2 ** (я + 1)
 х = х% 31337
 если rng <= 0:
 return -rng
 возвратный звонок  rsf [0] = 1
для i в диапазоне (1, 31337):
 rsf [i] = (g * rsf [i-1])% p
WOW = [0] * 31337
для i в диапазоне (0, 31337):
 WOW [i] = hq_prng (i, p, g)
УХ ТЫ.Сортировать()
для i в диапазоне (0, 31337):
 lef = я + 1
 rig = 31336
 средний, лучший = 0, 0
 в то время как lef <= rig:
 mid = (lef + rig) // 2
 if (WOW [i] * WOW [i] + WOW [mid] * WOW [mid]) * 2 * WOW [i] * WOW [mid]> = n:
 лучший = средний
 rig = mid -1
 еще:
 lef = mid + 1
 если лучше == 0:
 Продолжать
 для j в диапазоне (лучше-1, мин (лучше + 30, 31337)):
 u = ВАУ [i] * ВАУ [i] + ВАУ [j] * ВАУ [j]
 v = 2 * ВАУ [i] * ВАУ [j]
 если u * v <= n и n <= (u + 1000) * (v + 1000):
 u = nextprime (u)
 v = nextprime (v)
 если u * v == n:
 перерыв  u = 1320716846529569994065968467674726141275170450106550
723
6606220559473477009696618646553552
5315941229263316963221556883007951846286507319
 v = 13206540315287197799978983146788408283040839212
83447128092673850363700135834489414841071624197602378226210911
97770109472702331423302981
фи = (u-1) * (v-1)
 d = inverse_mod (е, фи)
 флаг = pow (c, d, N)
 печать (long_to_bytes (флаг))
 
 Флаг 
  CCTF {r341Ly_v3ryYyyyYY_s3cUrE ___ PRNG___} 
 Аббат 
 Вызов 
 Не большие жизненные проблемы требуют характера.Каждый может подняться до кризиса и смело встретить сокрушительную трагедию, но встретить мелкие опасности дня со смехом.
  импортная строка
случайный импорт
из фракций импорт фракций как фракций
из секретного флага импорта


Def me (msg):
если len (msg) == 1:
return ord (сообщение)
msg = msg [:: - 1]
reducer = len (сообщение) - 1
resultNum, resultDen = frac (ord (msg [0]), reducer) .denominator, frac (ord (msg [0]), reducer) .numerator
редуктор - = 1
для i в диапазоне (1, len (msg) -1):
результат = ord (msg [i]) + frac (resultNum, resultDen)
resultDen, resultNum = результат.знаменатель, результат. числитель
resultDen, resultNum = resultNum, reducer * resultDen
редуктор - = 1
result = ord (msg [-1]) + frac (resultNum, resultDen)
resultDen, resultNum = result.denominator, result.numerator
return (resultNum, resultDen)

def you (msg):
если len (msg) == 1:
return ord (сообщение)
msg = msg [:: - 1]
редуктор = (-1) ** len (сообщение)
результат = гидроразрыв (ord (сообщение [0]), редуктор)
resultNum, resultDen = result.denominator, result.numerator
редуктор * = -1
для i в диапазоне (1, len (msg) -1):
результат = ord (msg [i]) + frac (resultNum, resultDen)
resultDen, resultNum = результат.знаменатель, результат. числитель
resultDen, resultNum = resultNum, reducer * resultDen
редуктор * = -1

result = ord (msg [-1]) + frac (resultNum, resultDen)
resultDen, resultNum = result.denominator, result.numerator
return (resultNum, resultDen)

def us (msg):
если len (msg) == 1:
return ord (сообщение)
msg = msg [:: - 1]
reducer = (-1) ** int (frac (len (msg), len (msg) ** 2))
результат = гидроразрыв (ord (сообщение [0]), редуктор)
resultNum, resultDen = result.denominator, result.numerator
редуктор ** = -1
reducer = int (редуктор)
для i в диапазоне (1, len (msg) -1):
результат = ord (msg [i]) + frac (resultNum, resultDen)
resultDen, resultNum = результат.знаменатель, результат. числитель
resultDen, resultNum = resultNum, reducer * resultDen
редуктор ** = -1
reducer = int (редуктор)
result = ord (msg [-1]) + frac (resultNum, resultDen)
resultDen, resultNum = result.denominator, result.numerator
return (resultNum, resultDen)

dict_encrypt = {
1: я,
2: ты,
3: нас,
4: ты,
5: я
}
cipher = [[] для _ в диапазоне (5)]
S = список (диапазон (1,6))
random.shuffle (S)
print ("enc = [")
для i в диапазоне (4):
cipher [i] = dict_encrypt [S [i]] (flag [int (i * len (flag) // 5): int (i * len (flag) // 5 + len (flag) // 5)])
печать (шифр [i])
Распечатать(", ")
я + = 1
cipher [i] = dict_encrypt [S [i]] (flag [int (i * len (flag) // 5): int (i * len (flag) // 5 + len (flag) // 5)])
печать (шифр [i])
Распечатать( " ]")

ENC = [(4874974328610108385835995981839358584964018454799387862L, 7274460867213040421640464026815060
02538654479393L), (39640220997840521464725453281273
0171987264976009809L, 366968282179507143583456804992018400453304099650742276L), (14533878401025088546508817953211392597
977L, 1529712573230983998328149700664285268430
1078L), (847044030654776638396368866548461568880468
627L, 717773708720775877427974283328022404459326394028L), (2876058883055973853077251382758860614976633976011L, 87125503955817046806751398045655398265004367939L)]
  
 Решение 
 Код разбивает флаг на пять частей, применяет к ним три типа функции шифрования, а затем объединяет их в массив.Следовательно, достаточно написать коды, отменяющие эти шифрования. Затем мы можем попытаться перевернуть каждый зашифрованный текст с помощью всех типов функций шифрования и посмотреть, какие строки он нам дает.
 Начнем с функции шифрования  me  и продолжим работу.
 Основная интуиция заключается в том, что значение  resultNum / resultDen  сохраняется между 0 и 1 в конце каждой итерации. Если это так, это означает, что мы можем вычислить каждый символ открытого текста, просто взяв целую часть дроби и используя функцию  chr () .Почему это могло быть правдой? Что ж, мы можем предположить, что длина каждого поврежденного сообщения меньше, чем, скажем, 30. Поскольку каждый символ строки читается, их значение ASCII будет не менее 33. Имея эту идею в руках, можно доказать утверждение по индукции. Реверс также прост. Возьмите целую часть, измените ее на символ, возьмите оставшуюся дробную часть и измените ее соответствующим образом.
  you  шифрование немного сложнее, так как появляются отрицательные значения.При осмотре мы видим, что  resultNum / resultDen  меняет свой знак на каждой итерации. Абсолютное значение находится в диапазоне от 0 до 1. Ключевая идея остается той же, но нам нужно быть осторожными.
  us  шифрование просто, так как значение редуктора   равно  1  все время. При этом код остается очень похожим на код шифрования  me .
 Реализация 
  def me (resultNum, resultDen, dg):
st = ""
если resultNum == 0 или resultDen == 0:
возвращаться ""
если dg == 0:
TT = resultNum // resultDen
если TT <0 или TT> 256:
возвращаться ""
st = chr (TT)
resultNum = resultNum - TT * resultDen
st + = me (resultNum, resultDen, dg + 1)
вернуться ул
acnum = resultDen * dg
acden = resultNum
если acden == 0:
возвращаться ""
TT = acnum // acden
если TT <0 или TT> 256:
возвращаться ""
st = chr (TT)
acnum = acnum - TT * acden
st + = я (acnum, acden, dg + 1)
вернуться ул

def you (resultNum, resultDen, dg, cv):
st = ""
если resultNum == 0 или resultDen == 0:
возвращаться ""
если cv == 0:
TT = resultNum // resultDen
если TT <0 или TT> 256:
возвращаться ""
st = chr (TT)
resultNum% = resultDen
st + = вы (resultNum, resultDen, dg, cv + 1)
вернуться ул
acnum = resultDen
acden = resultNum * dg
если acden <0:
acden = -acden
acnum = acnum
если acden == 0:
возвращаться ""
если cv% 2 == 0:
TT = acnum // acden
если TT <0 или TT> 256:
возвращаться ""
st = chr (TT)
acnum% = acden
st + = вы (acnum, acden, dg * -1, cv + 1)
вернуться ул
еще:
TT = (acnum + acden - 1) // acden
если TT <0 или TT> 256:
возвращаться ""
st = chr (TT)
acnum = acnum - TT * acden
st + = вы (acnum, acden, dg * -1, cv + 1)
вернуться ул

def us (resultNum, resultDen, dg):
st = ""
если resultNum == 0 или resultDen == 0:
возвращаться ""
если dg == 0:
TT = resultNum // resultDen
если TT <0 или TT> 256:
возвращаться ""
st = chr (TT)
resultNum% = resultDen
st + = us (resultNum, resultDen, dg + 1)
вернуться ул
acnum = resultDen
acden = resultNum // dg
если acden == 0:
возвращаться ""
TT = acnum // acden
если TT <0 или TT> 256:
возвращаться ""
st = chr (TT)
acnum% = acden
st + = us (acnum, acden, dg)
вернуться ул

для i в диапазоне (0, 5):
print (me (enc [i] [0], enc [i] [1], 0))
print (вы (enc [i] [0], enc [i] [1], -1, 0))
print (us (enc [i] [0], enc [i] [1], 0))

  
 Флаг 
 `CCTF {This_13  n0t_Arthur_Who_l0ves_Short_st0ries_This_IS   ASIS   Crypto_CTF  ___ with_very_m0d3rn_arthur_Enc0d1ng3000 _ D0_you_Enc0d1ng !! _ D0_you_39
 Безумная шляпа 
 Вызов 
 Мечта - это не реальность, но кто скажет, что есть что?
  импорт случайный
из секретного импорта p, флаг

def транспонировать (x):
result = [[x [j] [i] для j в диапазоне (len (x))] для i в диапазоне (len (x [0]))]
вернуть результат

def multiply (A, B):
если len (A [0])! = len (B):
return None
результат = []
для i в диапазоне (len (A)):
r = []
для j в диапазоне (len (B [0])):
р.добавить (0)
result.append (r)
для i в диапазоне (len (A)):
для j в диапазоне (len (B [0])):
для k в диапазоне (len (B)):
результат [i] [j] + = A [i] [k] * B [k] [j]
вернуть результат

def sum_matrix (A, B):
результат = []
для i в диапазоне (len (A)):
r = []
для j в диапазоне (len (A [0])):
r.append (A [i] [j] + B [i] [j])
result.append (r)
вернуть результат

def keygen (p):
d = random.randint (1, 2 ** 64)
если p% 4 == 1:
Q = []
для i в диапазоне (p):
q = []
для j в диапазоне (p):
если я == j:
q.append (0)
elif pow ((i-j), int ((p-1) // 2), p) == 1:
q.добавить (1)
еще:
q.append (-1)
Q.append (q)
Q_t = транспонировать (Q)
H = []
r = []
r.append (0)
r.extend ([1 для i в диапазоне (p)])
H.append (r)
для i в диапазоне (1, p + 1):
r = []
для j в диапазоне (p + 1):
если j == 0:
r.append (1)
еще:
r.append (Q [i-1] [j-1])
H.append (r)

h3 = [[0 для j в диапазоне (2 * (p + 1))] для i в диапазоне (2 * (p + 1))]
для i в диапазоне (0, p + 1):
для j в диапазоне (0, p + 1):
если H [i] [j] == 0:
h3 [i * 2] [j * 2] = 1
h3 [i * 2] [j * 2 + 1] = -1
h3 [i * 2 + 1] [j * 2] = -1
h3 [i * 2 + 1] [j * 2 + 1] = -1
elif H [i] [j] == 1:
h3 [i * 2] [j * 2] = 1
h3 [i * 2] [j * 2 + 1] = 1
h3 [i * 2 + 1] [j * 2] = 1
h3 [i * 2 + 1] [j * 2 + 1] = -1
еще:
h3 [i * 2] [j * 2] = -1
h3 [i * 2] [j * 2 + 1] = -1
h3 [i * 2 + 1] [j * 2] = -1
h3 [i * 2 + 1] [j * 2 + 1] = +1
ID = [[(-1) ** d, если i == j, иначе 0 для i в диапазоне (len (h3))] для j в диапазоне (len (h3))]
h3 = умножить (ID, h3)
возврат (h3, d)
еще:
Q = []
для i в диапазоне (p):
q = []
для j в диапазоне (p):
если я == j:
q.добавить (0)
elif pow ((i-j), int ((p-1) // 2), p) == 1:
q.append (1)
еще:
q.append (-1)
Q.append (q)
Q_t = транспонировать (Q)
Q_Q_t = умножить (Q, Q_t)
h2 = []
h2.append ([1 для i в диапазоне (p + 1)])
для i в диапазоне (1, p +1):
r = []
для j в диапазоне (p +1):
если j == 0:
r.append (-1)
elif i == j:
r.append (1 + Q [i-1] [j-1])
еще:
r.append (Q [i-1] [j-1])
h2.append (r)
ID = [[(-1) ** d, если i == j, иначе 0 для i в диапазоне (len (h2))] для j в диапазоне (len (h2))]
h2 = умножить (ID, h2)
возврат (h2, d)

def encrypt (сообщение, ключ):
матрица = ключ [0]
d = ключ [1]
m = [[ord (char) для символа в сообщении]]
de = [[-d для i в диапазоне (len (msg))]]
C = умножить (m, матрица)
шифр = матрица_сумма (C, de)
вернуть шифр

ключ = keygen (p)
flag = flag + (len (key [0] [0]) - len (flag)) * flag [-1]
cipher = encrypt (флаг, ключ)
print ('cipher =', шифр)
  
 Решение 
 Анализируя размеры зашифрованного текста, легко найти $ p = 37 $.Поскольку матричная часть секретного ключа определяется только $ p $ и четностью $ d $, у нас есть две возможные матрицы для рассмотрения. Кроме того, если мы зафиксируем $ d $, мы сможем вычислить открытый текст, решив систему линейных уравнений. Действуем так.
 Если мы перебираем $ d $ просто как целые числа, решение уравнения может содержать рациональные нецелые числа. Это медленно и подвержено ошибкам с плавающей запятой (если мы не позаботимся должным образом), поэтому мы воспользуемся другим трюком.
 Поскольку все порядковые значения в открытом тексте находятся в диапазоне от $ 0 $ до $ 256 $, мы перенесем всю эту задачу в $ \ mathbb {F} _ {257} $.Таким образом, мы можем попробовать $ 257 $ различных значений $ d $, решить систему, не беспокоясь о плавающей ошибке, и получить наш ответ.
 Реализация 
  ## keygen (d): просто keygen с p = 37, четность d

MAT0 = кейген (0)
MAT1 = кейген (1)
MM0 = Матрица (GF (257), MAT0)
MM1 = Матрица (GF (257), MAT1)
adv = [1] * 76
adv = вектор (GF (257), adv)
AD0 = MM0.solve_right (нареч.)
AD1 = MM1.solve_right (нареч.)
Шифр = [-34597494130611, -34597494138177, -34597494137803, -34597494138385, -34597494138025, -34597494138097, -34597494138073, -34597494138245, -34597494138183, -34597494138445, -34597494137991, -34597494138597, -34597494138309, -34597494138309, -34597494138279, -34597494138771 , -34597494138327, -34597494138485, -34597494138233, -34597494138389, -34597494138207, -34597494138555, -34597494138141, -34597494138501, -34597494138677, -34597494138297, -34597494138563, -34597494138439, -34597494138429, -34597494138041, -34597494138611, -34597494138469, - 34597494138217, -34597494138585, -34597494138403, -34597494138177, -34597494137777, -34597494138587, -34597494138231, -34597494138677, -34597494138127, -34597494138679, -34597494137789, -34597494138305, -34597494138025, -34597494138301, -34597494137941, -34597494138489, -34597494137583, -34597494138297, -34597494137949, -34597494138475, -34597494137879, -34597494138813, -34597494137981, -34597494138395, -34597494138201, -34597494138459, -34597494138195, -34597494138617, -34597494138003, -34597494138557 , -34597494138429, -34597494138499, -34597494137951, -34597494138673, -34597494137975, -34597494138341, -34597494138121, -34597494138375, -34597494137869, -34597494138459, -34597494137739, -34597494138405, -34597494137921, -34597494138775]
res = вектор (GF (257), шифр)
ХХ = ММ0.решить_right (разрешение)
YY = MM1.solve_right (res)
для i в диапазоне (0, 257):
    stX = ""
    stY = ""
    для j в диапазоне (0, 76):
        XX [j] + = AD0 [j]
        ГГ [j] + = AD1 [j]
    для j в диапазоне (0, len (XX)):
        if (int) (XX [j]) <= 255:
            stX = stX + chr ((int) (XX [j]))
    для j в диапазоне (0, len (YY)):
        if (int) (YY [j]) <= 255:
            stY = stY + chr ((int) (YY [j]))
    если "CCTF" в stX:
        печать (stX)
    если "CCTF" в stY:
        печать (stY)
  
 Флаг 
  CCTF {Th23_i3_Hadamard_rip_y0ung _ & _ bri11iant_Paley!} 
 Классический 
 Вызов 
 Classic - это просто, но важно!
  b7UkM iK2L0 PUVnZ Ho79I tDAf0 PUvfQ G5jHo 7GwLG wL9It vfQHo 7G5j0 PUvfQ 9Ithd JkMiK 2LU2b 0PUkM B8Nih dJK2L GwL0P 2 UHo
...
  
 Решение 
 Взяв триграммы из зашифрованного текста (т. Е. Разделив его на группы по три символа), это становится классическим моноалфавитным шифром подстановки. См. В сценарии встроенные комментарии о методологии решения, которую мы использовали для этой более открытой задачи.
 Реализация 
  импортная строка
из коллекций счетчик импорта
из cipher_solver.simple import SimpleSolver

с open ('enc.txt') как f:
    ctext = f.read ().полоса (). заменить ('', '')

def chunks (l, n):
    п = макс (1, п)
    return [l [i: i + n] для i в диапазоне (0, len (l), n)]

№1. Мы подозреваем, что группы по 5 человек вводят нас в заблуждение.
# Давайте разберем символы на группы разного размера и посмотрим на
# размер набора
для i в диапазоне (1,10):
    unique = len (set (chunks (ctext, i)))
    print (f "{unique} уникальные группы при разделении на группы длиной {i}")

# 2. Разделение на группы по 3 (триграммы) дает гораздо меньше уникальных символов.
chunked = фрагменты (ctext, 3)
freq = Счетчик (по частям).наиболее общий()
печать (частота)

# 3. Создайте таблицу замены для каждой триграммы на другую букву.
# важно только то, что наиболее частая триграмма соответствует пробелу
subs = {}
алфавит = "" + строка. = ord (исенгард [книга])
    lizzy_grant = oh + isengard [: - 1] if luke == 0 else no + isengard [: - 1]
    вернуть lizzy_grant

david = len (седьмая_печать)
эльф = седьмая_печать
лорд = BitArray (байты = байты (open ('flag.jpg ',' rb '). read ())). bin
bilbo = len (господин)
matthew = 0
princess_leia = ''
судьба = бильбо // давид
апокалипсис = Бильбо% Дэвид
для i в диапазоне (32):
    эльф = рожденный_то_ди (эльф)
пока Мэтью <судьба:
    princess_leia + = matthew_effect (эльф, господин [Мэтью * Дэвид: (Мэтью + 1) * Дэвид])
    эльф = рожденный_то_ди (эльф)
    Мэтью + = 1
princess_leia + = matthew_effect (эльф [: апокалипсис], господин [Мэтью * Дэвид:])
res = open ('flag.enc', 'wb')
res.write (bytes (int (princess_leia [i: i + 8], 2) для i в диапазоне (0, bilbo, 8)))
  
 Решение 
 После некоторого переименования и небольшого реверс-инжиниринга логики задачи мы видим, что изображение JPEG было скомпилировано с помощью ключевого потока, сгенерированного из LFSR.int (j))
 печать (ключ)
 
 Тогда мы можем получить
  1100011100101011000
0110001110010101100
0011000111001010110
0001100011100101011
1000110001110010101
0
  
 Поскольку мы знаем из исходного кода, что шифрование с последовательными ключами разделяет почти весь ключ ( x ... xa  и  bx ... x ), мы можем восстановить длину ключа из этого. Мы можем наблюдать это вращение уже в приведенном выше списке битов благодаря нашей вставке новых строк в правильные позиции.d [l] == 1:
 печать (я, j, k, l)
 седьмая_печать = '1100011100101011000'
 new_testament = [я, j, k, l]
 david = len (седьмая_печать)
 эльф = седьмая_печать
 лорд = BitArray (байты = байты (open ('flag.enc', 'rb'). read ())). bin
 bilbo = len (господин)
 matthew = 0
 princess_leia = ''
 судьба = бильбо // давид
 апокалипсис = Бильбо% Дэвид
 # для i в диапазоне (32):
 # эльф =born_to_die (эльфийка)
 пока Мэтью <судьба:
 princess_leia + = matthew_effect (эльф, господин [Мэтью * Дэвид: (Мэтью + 1) * Дэвид])
 эльф = рожденный_то_ди (эльф)
 Мэтью + = 1
 princess_leia + = matthew_effect (эльф [: апокалипсис], господин [Мэтью * Дэвид:])
 res = open (f'flag_ {i} - {j} - {k} - {l}.jpg ',' wb ')
 res.write (bytes (int (princess_leia [i: i + 8], 2) для i в диапазоне (0, bilbo, 8)))
 res.close ()  
 Флаг 
  CCTF {0Ne_k3y_t0_rU1e_7hem_A11_4Nd_7o_d3crYp7_th4_fl4g!} 
 Полоса 
 Вызов 
 Иногда люди, о которых никто ничего не представляет, делают то, чего никто не может представить.
  #! / Usr / bin / python

от Crypto.Импорт Util.number *
из секретного флага импорта, r

def a (n): # ВНИМАНИЕ: очень медленная реализация ...
если n <= 2:
вернуть n
elif n == 3:
возврат 24
еще:
return (6 * a (n-1) ** 2 * a (n-3) - 8 * a (n-1) * a (n-2) ** 2) // (a (n-2) * а (п-3))

def strip (n):
return int (bin (n) [2:]. rstrip ('0'), 2)

def encrypt (msg, r):
n = полоса (a (r))
вернуть pow (bytes_to_long (msg.encode ('utf-8')), 0x10001 + 0x02, n)

печать (зашифровать (флаг, г))
  
 Решение 
 Задача  a (n)  - это последовательность A028365 в OEIS, которая имеет более простую форму (записанную в PARI):  a (n) = prod (k = 1, n, 2 ^ k-1) * 2 ^ ((n ^ 2 + n) / 2) , а после удаления  a (n)  составляет всего  прод (k = 1, n, 2 ^ k-1) .
 Мы оценили  r  и получили  r> = 605 , факторизовали  a (r)  с помощью  FactorDB API , но для расчета огромного модуля потребовалась вечность. Итак, мы взяли 2 простых множителя из множителей  a (r)  и позволили их произведению быть новым модулем, и, наконец, мы получили флаг.
 В альтернативном решении используется оценка  r> = 60 . Мы можем взять все простые множители  a (60) , которые меньше  500000 , и решить  x ** e = enc (mod p)  для каждого из них методом грубой силы.я - 1)
 f.connect ()
 fac + = f.get_factor_list ()
fac2 = отсортировано (список (набор (fac)), обратный = True)
n_ = 1
 phi_ = 1
 для i, j в комбинациях (fac2, 2):
 п_ = я * j
 phi_ = (i - 1) * (j - 1)
 d_ = inverse_mod (e, phi_)
 m = long_to_bytes (pow (c, d_, n_))
 если b'CCTF 'в м:
 печать (м)
 перерыв
 
 Решение 2 
  из factordb.factordb import FactorDB
из tqdm импорт tqdm
из Crypto.Util.number import long_to_bytes

## модульная инверсия мода b, может быть заменена на Crypto.Обратное значение Util.number
def minv (a, b):
    если a == 1:
        возврат 1
    return b - minv (b% a, a) * b // a


## Китайская теорема об остатках
def CRT (a, b, c, d):
    na = d * minv (d, b) * a + b * minv (b, d) * c
    nb = b * d
    na% = nb
    утверждать на% b == a
    утверждать на% d == c
    return na, nb


enc = int (open ("./ flag.enc", 'r'). read ())

п = 1
е = 0x10001 + 0x02
totph = 1
вау = []
res = 1
для i в tqdm (диапазон (2, 68)):
    res = res * (2 ** я - 1)
    f = FactorDB (2 ** я - 1)
    f.connect ()
    А = е.get_factor_list ()
    для числа в A:
        если число в вау:
            totph = totph * число
        еще:
            totph = totph * (число - 1)
            wow.append (число)

AA = 0
BB = 1

wow.sort ()
для i в tqdm (диапазон (0, len (wow))):
    печать (вау [я])
    если wow [i]> 50000:
        Продолжать
    cnt = 0
    whi = 0
    для j в диапазоне (0, вау [i]):
        if pow (j, e, wow [i]) == enc% wow [i]:
            cnt = cnt + 1
            whi = j
    если cnt == 1:
        AA, BB = CRT (AA, BB, whi, wow [i])
        печать (long_to_bytes (AA))
  
 Флаг 
  CCTF {R3arR4n9inG_7He_9Iv3n_eQu4t10n_T0_7h4_mUcH_MOrE_traCt4bLe_0n3} 
 Комплекс в ад 
 Вызов 
 Я уже знаю, что отправляюсь в ад
 На данный момент он действительно становится большим или идет домой!
  импорт математики
строка импорта
случайный импорт
из секретного флага импорта, ключ

mapstr = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ! {} _"

def multiply (A, B):
ac, ar, bc, br = len (A [0]), len (A), len (B [0]), len (B)
если ac! = br:
return None
результат = []
для я в диапазоне (ар):
r = []
для j в диапазоне (bc):
р.добавить (0)
result.append (r)
для я в диапазоне (ар):
для j в диапазоне (bc):
для k в диапазоне (br):
результат [i] [j] + = A [i] [k] * B [k] [j]
вернуть результат


def Comple_congruent (z):
a = z.real% len (mapstr)
b = z.imag% len (mapstr)
вернуть a + b * 1j

def plain_to_matrix (сообщение, n):
p = int (math.ceil (len (msg) // (2 * n))) + 1

matrix_row_size = n
matrix_col_size = p
индекс = 0
matrix_plain = []
для i в диапазоне (matrix_row_size):
col = []
для j в диапазоне (matrix_col_size):
если индекс> = len (msg):
col.добавить (0 + 0.j)
индекс elif == len (сообщение) -1:
col.append (mapstr.index (msg [индекс]) + 0.j)
индекс + = 1
еще:
col.append (mapstr.index (msg [index]) + mapstr.index (msg [index + 1]) * 1.j)
индекс + = 2
matrix_plain.append (столбец)
вернуть matrix_plain


def encrypt (флаг, ключ):
n = len (ключ)
p = int (math.ceil (len (флаг) // (2 * n))) + 1
matrix_plain = plain_to_matrix (флаг, n)
key_congruent = []
для i в диапазоне (n):
r = []
для j в диапазоне (n):
r.append (comple_congruent (ключ [i] [j]))
key_congruent.добавить (г)
cipher = умножить (совпадение_ключа, матрица_плейн)
результат = []
для i в диапазоне (n):
r = []
для j в диапазоне (p):
r.append (comple_congruent (шифр [i] [j]))
result.append (r)
вернуть результат

cipher = encrypt (флаг, ключ)
print ("cipher =", шифр)
  
 Решение 
 tldr;
 Используйте формат флага для настройки системы уравнений.
 Брутфорс первых двух записей во 2-й строке.
 Многие ключи позволяют дешифровать первую строку.
 Используйте последние записи в первой строке, зная, что такое заполнение, чтобы подобрать полный правильный ключ.
  plain_to_matrix (msg, n)  принимает строку сообщения в качестве входных данных и количество строк  n  и возвращает матрицу с  n строками , в которой символы  msg  являются комплексными числами в качестве записей (одно комплексное число представляет два символа). Если сообщение не заполняет матрицу полностью, оно дополняется  0  с.
  encrypt (msg, key)  шифрует данное сообщение, умножая его слева (как матрицу) на ключ $ 2 \ times 2 $.8 $, что невозможно брутфорсом.
 Мы можем использовать формат флага, чтобы уменьшить количество требуемого перебора. Пусть ключ будет
\ [K = \ begin {bmatrix}
 а + би & с + ди \\
 e + fi & g + привет
 \ end {bmatrix} \]
 где $ a, b, c, d, e, f, g \ in \ mathbb {Z} / 66 \ mathbb {Z} $
 Запишите матрицу флагов открытого текста как
\ [M = \ begin {bmatrix}
 m_0 + m_1i & m_2 + m_3 i & \ cdots & m_ {32} + m_ {33} i \\
 m_ {34} + m_ {35} i & m_ {36} + m_ {37} i & \ cdots & m_ {66} + m_ {67} i
 \ end {bmatrix} \]
 и матрица зашифрованного текста как
\ [C = \ begin {bmatrix}
 c_0 + c_1i & c_2 + c_3 i & \ cdots & c_ {32} + c_ {33} i \\
 c_ {34} + c_ {35} i & c_ {36} + c_ {37} i & \ cdots & c_ {66} + c_ {67} i
 \ end {bmatrix} \]
 (все коэффициенты в $ \ mathbb {Z} / 66 \ mathbb {Z} $).
 Итак, $ C = KM $. 4 $ для $ m_ {34}, m_ {35}, m_ {36} $ и $ m_ {37} $ и решаем 8 ключевых значений с помощью 8 уравнений.3 $. К счастью для нас, оказалось, что последние 4 символа открытого текста - это } 000 , поэтому у нас достаточно информации, чтобы перечислить возможные ключи с минимальным перебором. Мы можем использовать ту же настройку, что и выше, за исключением того, что вместо перебора $ m_ {34}, m_ {35}, m_ {36} $ и $ m_ {37} $ мы принимаем их равными } 000 . Решение системы даст нам вектор $ \ mathbf {k} = (a, b, c, d, e, f, g, h) $, но это может быть неправильный ключ.
 Любой вектор вида $ \ mathbf {k} + \ mathbf {t} $, где $ \ mathbf {t} $ находится в ядре матрицы коэффициентов, $ A $, удовлетворяет системе.{-1} = \ begin {bmatrix}
 а '+ b'i & c' + d'i \\
 e '+ f'i & g' + h'i
 \ end {bmatrix} \]
 Тогда по определению
\ [\ begin {bmatrix}
 а + би & с + ди \\
 e + fi & g + привет
 \ end {bmatrix}
 \ begin {bmatrix}
 а '+ b'i & c' + d'i \\
 e '+ f'i & g' + h'i
 \ end {bmatrix} =
 \ begin {bmatrix}
 1 & 0 \\
 0 и 1
 \ end {bmatrix} \]
 так
\ [\ begin {выровнено}
 aa '- bb' + ce '- df' & = 1 \\
 ab '+ ba' + cf '+ de' & = 0 \\
 ac '- bd' + cg '- dh' & = 0 \\
 ad '+ bc' + ch '+ dg' & = 0 \\
 ea '- fb' + ge '- hf' & = 0 \\
 eb '+ fa' + gf '+ he' & = 0 \\
 ec '- fd' + gg '- hh' & = 1 \\
 ed '+ fc' + gh '+ hg' & = 0
 \ конец {выровнено} \]
, которая представляет собой систему из 8 уравнений с 8 неизвестными, которые можно легко решить.
 Реализация 
  от itertools import product

mapstr = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ! {} _"
шифр = [[(24 + 36j), (41 + 47j), (3 + 27j), (36 + 41j), (57 + 58j), (11 + 24j), (33 + 7j), (52 + 64j ), (26 + 23j), (30 + 35j), (64 + 39j), (52 + 19j), (39 + 45j), (33 + 31j), (3 + 17j), (21 + 32j), (15 + 55j)], [(33 + 44j), (15 + 39j), (64 + 50j), (44 + 41j), (39 + 20j), 42j, (16 + 12j), (63 + 27j) ), (9 + 52j), (39 + 64j), (5 + 18j), (53 + 25j), (47 + 31j), (5 + 49j), (24 + 8j), (57 + 9j), (38 + 16j)]]

F = IntegerModRing (66)

def multiply (A, B):
    ac, ar, bc, br = len (A [0]), len (A), len (B [0]), len (B)
    если ac! = br:
        return None
    результат = []
    для я в диапазоне (ар):
        r = []
        для j в диапазоне (bc):
            р.добавить (0)
        result.append (r)
    для я в диапазоне (ар):
        для j в диапазоне (bc):
            для k в диапазоне (br):
                результат [i] [j] + = A [i] [k] * B [k] [j]
    вернуть результат

def inv (ключ):
    a, b, c, d, e, f, g, h = ключ
    M = [[a, -b, 0,0, c, -d, 0,0],
         [b, a, 0,0, d, c, 0,0],
         [0,0, a, -b, 0,0, c, -d],
         [0,0, b, a, 0,0, d, c],
         [e, -f, 0,0, g, -h, 0,0],
         [f, e, 0,0, h, g, 0,0,],
         [0,0, e, -f, 0,0, g, -h],
         [0,0, f, e, 0,0, h, g]]
    M = Матрица (F, M)
    t = вектор (F, [1,0,0,0,0,0,1,0])
    я = М.решить_right (t)
    a, b, c, d, e, f, g, h = карта (ZZ, i)
    I = [[a + b * 1j, c + d * 1j], [e + f * 1j, g + h * 1j]]
    вернуться я

def cong (z):
    а = z.real ()% 66
    b = z.imag ()% 66
    вернуть a + b * 1j

def decrypt (ключ):
    Kinv = inv (ключ)
    key = [[cong (Kinv [i] [j]) для j в диапазоне (2)] для i в диапазоне (2)]
    M = умножить (ключ, шифр)
    res = []
    flag = ''
    для i в диапазоне (2):
        для j в диапазоне (17):
            a = cong (M [i] [j]). real ()
            b = cong (M [i] [j]). imag ()
            флаг + = mapstr [int (a)] + mapstr [int (b)]
    флаг возврата

# первый раунд, брутфорс m34, m35, m36, m37
# c0, c1, c2, c3 = 24, 36, 41, 17
# c34, c35, c36, c37 = 33, 44, 15, 19
# m0, m1, m2, m3 = 38, 38, 55, 41
# RECOVERS первая строка: CCTF {This_0n3_Is_State_0f_th4_4rt_

c0, c1, c2, c3 = 21, 32, 15, 55
c34, c35, c36, c37 = 57, 9, 38, 16
m0, m1, m2, m3 = 4, 27, 29, 65
m34, m35, m36, m37 = 64, 0, 0, 0

A = [[m0, -m1, m34, -m35,0,0,0,0],
     [m1, m0, m35, m34,0,0,0,0],
     [m2, -m3, m36, -m37,0,0,0,0],
     [м3, м2, м37, м36,0,0,0,0],
     [0,0,0,0, m0, -m1, m34, -m35],
     [0,0,0,0, m1, m0, m35, m34],
     [0,0,0,0, m2, -m3, m36, -m37],
     [0,0,0,0, м3, м2, м37, м36]]
v = [c0, c1, c2, c3, c34, c35, c36, c37]
A = Матрица (F, A)
v = вектор (F, v)
х = А.решить_right (v)
A2 = Матрица (GF (2), A)
A2K = Матрица (F, A2.right_kernel_matrix ())
# A3 и A11 имеют нулевое значение

для lc в продукте (диапазон (2), repeat = A2.right_nullity ()):
    пытаться:
        t2 = A2K.linear_combination_of_rows (lc)
        t = вектор ([crt ([int (a2), 0, 0], [2, 3, 11]) для a2 в t2])
        ключ = x + t
        flag = расшифровать (ключ)
        печать (флаг)
    кроме ValueError:
        проходить
    кроме KeyboardInterrupt:
        выход()
  
 Флаг 
  CCTF {This_0n3_Is_State_0f_th4_4rt_and_C0mplex_is_Truly_compl3x !!} 
 Фатима 
 Вызов 
 Я думаю, мы все должны изучить эллиптические кривые, и фатима - хорошее начало, наслаждайтесь!
  #! / Usr / bin / env python3
# - * - кодировка: utf-8 - * -

от fastecdsa.кривая импорт кривой
из Точки импорта fastecdsa.point
импортная математика, случайная
из флага флаг импорта
время импорта

def multiply (A, B):
ac, ar, bc, br = len (A [0]), len (A), len (B [0]), len (B)
если ac! = br:
return None
результат = []
для я в диапазоне (ар):
r = []
для j в диапазоне (bc):
r.append (0)
result.append (r)
для я в диапазоне (ар):
для j в диапазоне (bc):
для k в диапазоне (br):
результат [i] [j] + = A [i] [k] * B [k] [j]
вернуть результат

def pow_matrix (A, n):
R = циркулянт ([1] + [0 для i в диапазоне (len (A) -1)])
для _ в диапазоне (n):
R = умножить (R, A)
вернуть R

def циркулянт (v):
C, n = [], len (v)
для i в диапазоне (n):
С.добавить (v)
tmp = []
tmp.append (v [-1])
tmp.extend (v [: - 1])
v = tmp
вернуть C

def спираль (A):
строка = len (A)
col = len (A [0])
top = 0
left = 0
tmp = []

в то время как (верхняя строка <строка и левая строка <столбец):
для i в диапазоне (слева, столбец):
tmp.append (A [вверху] [i])
верх + = 1
для i в диапазоне (верх, строка):
tmp.append (A [i] [col - 1])
столбец - = 1
если (верхняя строка <строка):
для i в диапазоне (col - 1, (left - 1), - 1):
tmp.append (A [строка - 1] [i])
ряд - = 1

если (left  Решение 
 Обратите внимание, что  pow_matrix (C, i) == циркулянт ([0] * (100 - i) + [1] + [0] * (i - 1))  с  C = циркулянт ([0 для i в range (len (B) -1)] + [1]) , зная, что мы можем восстанавливать открытый текст шаг за шагом.k  имеет вид  циркулирующий ([0] * (100 - i) + [1] + [0] * (i - 1)) , поэтому мы можем просто подобрать  i  и проверить каждый случай, который дает правильный простой текст. Операторы обхода и часть EC могут быть отменены с помощью справочных таблиц.
 Реализация 
  из импорта Crypto.Util.number *
импортировать itertools
импорт tqdm
из fastecdsa.curve import Curve
из Точки импорта fastecdsa.point
импортная математика, случайная

############ Повторное использование кода задачи ############
def multiply (A, B):
ac, ar, bc, br = len (A [0]), len (A), len (B [0]), len (B)
если ac! = br:
return None
результат = []
для я в диапазоне (ар):
r = []
для j в диапазоне (bc):
р.добавить (0)
result.append (r)
для я в диапазоне (ар):
для j в диапазоне (bc):
для k в диапазоне (br):
результат [i] [j] + = A [i] [k] * B [k] [j]
вернуть результат

def pow_matrix (A, n):
R = циркулянт ([1] + [0 для i в диапазоне (len (A) -1)])
для _ в диапазоне (n):
R = умножить (R, A)
вернуть R

def циркулянт (v):
C, n = [], len (v)
для i в диапазоне (n):
C.append (v)
tmp = []
tmp.append (v [-1])
tmp.extend (v [: - 1])
v = tmp
вернуть C

def спираль (A):
строка = len (A)
col = len (A [0])
top = 0
left = 0
tmp = []

в то время как (верхняя строка <строка и левая строка <столбец):
для i в диапазоне (слева, столбец):
tmp.добавить (A [вверху] [i])
верх + = 1
для i в диапазоне (верх, строка):
tmp.append (A [i] [col - 1])
столбец - = 1
если (верхняя строка <строка):
для i в диапазоне (col - 1, (left - 1), - 1):
tmp.append (A [строка - 1] [i])
ряд - = 1

если (left  
 И это результат, абзац из  Фатимской Богоматери .
 Начиная с весны 1917 года дети сообщали о явлениях Ангела, а начиная с мая 1917 года - о явлениях Девы Марии, которую дети описали как Леди, более сияющую, чем Солнце.Дети передали пророчество о том, что молитва положит конец Великой войне и что 13 октября того же года Леди раскроет свою личность и проведет CCTF {Elliptic_Curv3  1s_fun  & _simpLE_Circulaitng_it_make_it_funnier !!}, чтобы все могли поверить в это. Газеты сообщили о пророчествах, и многие паломники начали посещать этот район. Рассказы детей вызвали глубокие споры и вызвали резкую критику как со стороны местных светских, так и религиозных властей. Провинциальный администратор на короткое время взял детей под стражу, полагая, что пророчества были политически мотивированы в противовес официально светской Первой Португальской республике, установленной в 1910 году.[6] События 13 октября стали известны как «Солнечное чудо»…
 Флаг 
  CCTF {Elliptic_Curv3_1s_fun _ & _ simpLE_Circulaitng_it_make_it_funnier !!} 
 Намура 
 Вызов 
  def encrypt (pubkey, msg):
C = 0
для i в диапазоне (n):
C + = pubkey [i] * int (msg [i])
вернуть C

flag = flag.lstrip ('CCTF {'). rstrip ('}')
bflag = bin (bytes_to_long (flag.encode ('utf-8'))) [2:]
n = len (bflag)
и = п - 30

pubkey = keygen ((n + 1) // 3, n, u)

печать ('pubkey =', pubkey)
enc = encrypt (pubkey, bflag)
печать ('enc =', enc)
  
 Решение 
 Это похоже на ранцевую криптосистему, которая обычно решается алгоритмами сокращения решетки, моделирующими задачу кратчайшего вектора (SVP).Мы заметили, что название задачи «Намура» намекает на статью, описывающую этот алгоритм, - ранцевую криптосистему с открытым ключом Наскао и Мураками, использующую китайскую теорему об остатках. В разделе 4.2 описывается решетка, которая может решать задачи суммы подмножеств с низкой плотностью, а открытый ключ в этой задаче имеет очень низкую плотность:
  d = len (pubkey) / log (max (pubkey), 2)
печать (CDF (d))
0,5625
  
 Поскольку можно предположить, что флаг представляет собой печатаемые символы ASCII, мы можем уменьшить размер ключа публикации, удалив соответствующее число до MSB каждого символа в открытом тексте.
  новый = []
pubkey = [0] + pubkey
для i в диапазоне (len (pubkey)):
    если я% 8 == 0:
        Продолжать
    new.append (pubkey [i])
print ('pubkey =', новый)
  
 Тогда мы можем решить эту задачу, как и другие задачи о ранце, путем перебора перестановки и использования алгоритма сокращения решетки BKZ для поиска SVP.
 Реализация 
  импорт ре
случайный импорт
импортировать многопроцессорность как mp
from functools import partial

def check (sol, A, s):
    "" "Проверьте, является ли * sol * решением проблемы подмножества суммы."" "
    return sum (x * a for x, a in zip (sol, A)) == s

def решить (a, s, ID = None):
    rand = random.Random (x = ID)

    mat = []
    для idx, val в перечислении (a):
        mat.append ([0] * idx + [1] + [0] * (len (a) -idx-1) + [val])
    mat.append ([0] * len (a) + [- s])

    # основной цикл
    itr = 0
    start_time = cputime ()
    в то время как True:
        itr + = 1

        # 2. Случайно перемешать
        l = мат [::]
        перемешать (l, random = rand.random)

        №3. БКЗ !!!
        m = матрица (l)
        t_BKZ = cputime ()
        l_sol = м.BKZ (block_size = 25)
        print (f "{itr} выполняется. Время работы BKZ: {cputime (t_BKZ) :. 3f} s")

        для строки в l_sol:
            если все ([x> = 0 для x в строке [: - 1]]):
                печать (строка)
                print (проверьте (строка, a, s))
                print (f "После выполнения {itr}. НАЙТИ SVP !!! {line} \ n"
                      f "Используемое одноядерное время: {cputime (start_time) :. 3f} s")
                вернуть True


enc = 1546575376465967753276253676484467260782425419406781078357515
Публичных = [636730424634282684150787505024636846878192530834301373045417941, 44344373605670185482155004540
56747702320750978
93, 40448946793472218661471393250783970070284064844489844729640, 2438178506188801348411667154785222321653401060527584288473058029, 17069477409243358471897897077706622577630696771143373974126, 4396893130381899655054557551793492148977658211100513328122993482, 260168253141894278193287056129997597680628407096685851, 8495786964304801066711846105434868737506048858961510584478, 867634152731852110202428052792503837522496305953184128350
0, 2141949195467351870752341331086896393444
855567
943, 13177247818928294767272764296136493697391
7197350586077, 8466162032541648714620324777288157484807522832537271896727, 18898
622399357217368964385384275068207071755568870885142697, 4345106754542111105556800435292359436746763182165461814839878219, 184475194340864943997078423481
88878268101086942786334241578, 46351 518677852486535849253198200323421083535832783650
351369, 18
0231153447767958167471428147295737587261835048395769, 32736726991794278838098554938393037792687468962414002119644, 47596833
6863354069372064775438697384972606618058259428, 22774797151125684742
8784040287857475672572685264806983, 7122812704089486011482407537474741428127403029959878626851, 4663860235979475414650446442104011820603148660069426522253772670, 35707575813861484926197213797544708993160952561231099128391, 460971324484885315187249816087737573433532
656414838786, 14312489946883
0176295567118297228062
7671705412012, 22256187365763998527181971614167
023368081178287753385225648, 478276888543203960544853923069531810979233577647404486
, 1025808412433473089433862844337525335386046496037581875356716631, 285070315283361225103516
71614
2662336925683266673455769, 468648404266467373733026713724725
48980
3457550045106744, 3316117133062845 0453275217382647934051828005331038083037906, 14114962974456553148479837245709826364485773351142419546
680, 2542720351620819402979547749565244924618621495731029455602801063, 4197157173419472170084161
8987699514176876278506629655813541, 77517822179349508504357672960938122058
40944436598437451103, 1341597796943613200200560889564801116846969301604051962802959921, 472427558738458680932684266380781
33750
174396, 2254966368661541088781
0011063323766242664855534020654216185, 15572805843337464695743725374999443380244436636784823457268, 263060461355351726244024949311923372968467484234342136010504498, 421848
953587876527116792449437414059225489587311420630, 22513476084064775838762766921622808872229705782250944073182, 1048197300230894759772482326800601949486880189444304544
1349, 4594309375612539584017
696572687973736843473298
61461158, 12335266486813032047564
7695007575423669369548188681389, 3016611933554222534504704995 395833948561521013355966057174149640, 68543164296038745883336548376966127265339412
70162343687962, 12523505784321952733140441764993245772656606639708501799071, 2004856
36709503981
612521156885201358615487450361722687, 1725528220657822102510144312466698156124143365979935333948441423, 3301536380780212554033742823735941195638359575128262344444357806, 33611767810811769
9867695
284375994647164396417238879397, 2555688594
8218735938381172552745926292876995621798813594216, 214919
59861721027875250011594210747138266017264150889296633, 4654853318545885657451422703700711659405223637471250014707272999, 178382775525000288381922347857748068756186881503759861899
99, 3876452588731221361888242546888347728419654382142841199604124779, 2283317070521561115970687892255141823986922119608171153201553969, 30153436384545630411225203386258523748035633382700837350107, 130896379
21611684027617168973833892399982687941479751647735, 336329815659231886717160
7310462448 1755649616128282937579774, 3543718722328215
4832245155182570535205536855659505934745836, 29555550069226662844543615864283232856958998231643765012061, 4193238
1395832431998242809775488323071053203281739810565939, 48637154505423241426945038974
069694288484386266524822426647, 3583711168144466683
4650704848504341023445180872465082660398, 1433492863048866856968843544774985957106873111077658213115876127, 3622680772935480479302879234497984985614630209532096422962674742, 3887543
86937418224225531858370221228308704662592143667
, 3010960827639423613523800853443011766752449479334524527050675334, 16759555420743839489708702301358149367999511098660341747344
, 2568984843336400124353481960719548494069287783874504372170058935, 680042408260630675242336818143271325154353883745350135887078713, 18967683692167859873865813768792359296006947445277687988097, 537513148597668578568712785471862479586342936485511258184103046, 433831815757299605537847417225118672403414865783850 5626251846209, 4509359887372553408550688030273180923282246069532844476087185588, 1961425576962957081785371096529881351777256192797473186708183898, 4562726127192998241808421239521775685020063730950933119470565151, 31974164760370635447572
5965582808251383336065711778098, 4509743379431751154130020063323115
06422197393584253150, 1737231313740527925458531852974418083735884963087687882655818328, 47237714348441736361870130027922780708005170476297565209636, 402106881592459668247234277095767
19658388809493963529859273, 47865933679354
77424957497728176259220
92374805751998882, 170684794784134
870515868713796043
960780007506398289654, 2092
61301369305263620771320336826052044341129920779847, 238654275340926204926244410947989833
42017285966198413932291, 2575514997936878781309794857665223684996125674280321049577858392, 2526059212864002845504783002187945419965243527858703947395965701, 20770553769636
993188737229202782309424513798741527458096 967, 194772166679344880661950688674566557436875331512
73531178573, 2321982120042809240576670
3025887795295409352093643395133004, 413486009385051766121433611328881570
500134549846473180, 12798738522001443231160327443797286486924653552312015287694, 3934811009597203954835516432740855968621865146569217009553064951, 804570958275502176779582603101955727481164663345322968855176622, 4755601230261360181533138175300662604366870408130
6343576381, 2016264
351496152147334292
404440695604760546558347, 385712193119880898103340213183599
60880661479936388701406991, 4787
17724796254412923926380805933072651244745134226910, 403228266126326263488043524077179619385866145325037513940941892, 4080757802977772396554968304371742747141072297333640725823656444, 2480862883842493536769334310714884272887049336400711180125, 1607777042247987295060365154963999272145526955355524894746933487]
 решить_n = частичное (решить, pubkey, enc)
 CPU_CORE_NUM = 8
 с т.пл.Пул (CPU_CORE_NUM) как пул:
 reslist = pool.imap_unordered (решить_n, диапазон (CPU_CORE_NUM))
 # завершить все процессы, как только один процесс вернется
 для res в reslist:
 если res:
 pool.terminate ()
 перерыв
 
 Вывод:
 После 19 прогонов. НАЙТИ СВП !!! (1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0 , 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0 , 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0 , 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1 , 1, 0, 0, 0, 0, 0)
 Используемое одноядерное время: 643.215с
  флаг = ''
svp = (1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1 , 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1 , 0, 1, 1,
       0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0)
для i в диапазоне (0, len (svp), 7):
    flag + = '0' + '' .join (map (str, svp [i: i + 7]))
print (b'CCTF {'+ long_to_bytes (int (флаг, 2)) + b'} ')
  
 Флаг 
  CCTF {MuR4kam1_nA54K0} 
 Достойный RSA 
 Вызов 
 RSA тоже может быть достойным!
  Примечание  Хотя эта задача очень приличная и решаемая, если сосредоточить внимание на номере модуля, вы можете использовать любые инструменты, угадывание или что-то еще, что вы знаете, для ее решения!
 Решение 
 TD; DR
 Видите, что когда записано с основанием 11, модуль в основном нули
 Запишите модуль в виде многочлена по основанию 11 и разложите на множители многочлен
.
 Решить RSA
 Все, что нам дают, это открытый ключ RSA
  ----- НАЧАТЬ ОТКРЫТЫЙ КЛЮЧ -----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA / Ug8rlEPci1UXMsT + UDo
y8DfxbTHX / 3BK2oU + FPWiJf + EiUBM2x4ep04qZ1SO9Pmqj / WH9skMrF1J / LXuY3l
fjvJCh0DXa9VUyX2dAJidja9Ior7GpFwwjYdKh + OETNV + 2 / CcX4RiPvj + 8ApmedW
gn4Fxaeivki + f / UwDa + ws1fTUzmI325v8yvcryHhbgeUWiF85EP6HFAavTsVPlxb
LikVMAB1fuzDbqqJvW2u138w6b2Fh4WrezYF6tbAyZej2HX46phwDm9C7MXYJ / sU
oS + E8P7S1jMTCWjfwMCOKU3SFGrkWtXuTaoMZ2nZ + HVfJV8xJOjWez1OxQ5P3F1w
GQIDAQAB
----- КОНЕЦ ОБЩЕСТВЕННОГО КЛЮЧА -----
  
 и некоторые зашифрованные данные.
 Из  .pem  получаем
  Algo RSA
Формат X.509
Дамп ASN1
Открытый ключ RSA [21: 5d: 61: 5d: 7e: ef: d0: 58: 12: d0: dc: 14: bd: 7c: e1: 69: eb: 77: 01: f0]
Модуль: fd483cae510f722d545ccb13f940e8cbc0dfc5b4c75ffdc12b6a14f853d68897fe122501336c787a9d38a99d523bd3e6aa3fd61fdb2432b17527f2d7b98de57e3bc90a1d035daf555325f67402627636bd228afb1a9170c2361d2a1f8e113355fb6fc2717e1188fbe3fbc02999e756827e05c5a7a2be48be7ff5300dafb0b357d3533988df6e6ff32bdcaf21e16e07945a217ce443fa1c501abd3b153e5c5b2e2
00757eecc36eaa89bd6daed77f30e9bd851f75ab7b3605ead6c0c997a3d875f8ea98700e6f42ecc5d827fb14a12f84f0fed2d633130968dfc0c08e294dd2146ae45ad5ee4daa0c6769d9f8755f255f3124e8d67b3d4ec50e4fdc5d7019
общественная экспонента: 10001
  
, где модуль равен некоторому целому числу  2048  бит.Поскольку нам дан ключ  X.509 , esrever предложил посмотреть базу данных предсказуемых ключей RSA, которая содержит 30k открытых ключей, которые были небезопасными. Мы загрузили их и искали общий фактор между нашим общим модулем и одним из этих известных слабых ключей. Однако нам не повезло.
 Другая идея заключалась в том, что, возможно, эту проблему можно решить с помощью факторизации Ферма, при этом «Decent RSA» является каламбуром для метода бесконечного спуска. Я позволил алгоритму поработать некоторое время, но в конце концов убил его.
 Решение пришло из изучения модуля в различных базах. Изначально я надеялся, что простые числа могут быть простыми числами Мерсенна, которые можно выявить, глядя на модуль в базе 2, но оказалось, что правильной базой для решения является база 11.
  sage: N.str (база = 11)
'10010000000000000000000000000000020000000000010000000000000000000000000000000000000000000002002000002000000000000000020020004000000000002000000000004040000000000020000000002000000000000000000400000000000000000000000004000000000000000000000800000000000000000000000408000000000000000200000004000000600200000000000000000000000000000400000000000200000000000000000000000000000040000000000000080000000040400000000000000800000000000000000000000000000080000000000000000000000040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004000000000000008'
  
 Тогда мы можем записать  N  в виде полинома следующим образом:
  sage: poly = sum (e * x ^ i for i, e in enumerate (N.i для i, e в перечислении (Integer (key.n) .digits (11)))
(p, _), (q, _) = poly.factor_list ()
р, д = р (х = 11), д (х = 11)
утверждать p * q == n

d = inverse_mod (key.e, (p-1) * (q-1))
print (long_to_bytes (pow (флаг, d, n)))
  
 Флаг 
  CCTF {___ RSA ___ 1n_D3cEn7_W0rLd_cRyPtO5 !!!} 
 GenGol 
 Вызов 
 Мы обновили криптосистему для шифрования больших сообщений. Попробуй его сломать!
 Мы можем подключиться к серверу и прочитать фрагмент исходного кода:
  def genkey (k, nbit):
    утверждать 2 * k <= nbit
    в то время как True:
        p = случайный.randint (1, 2 ** (nbit - k)) * 2 ** k + 1
        если isPrime (p):
            q = getPrime (нбит)
            п = р * д
            в то время как True:
                y = random.randint (1, n)
                jp, jq = pow (y, (p-1) / 2, p), pow (y, (q-1) / 2, q)
                если (jp + jq == p + q - 2):
                    d = random.randint (int (exp (0,272 * log (n))), int (exp (0,292 * log (n)))) | 1
                    е = обратное (d, (p - 1) * (n / p - 1))
                    если e * d% ((p - 1) * (n / p - 1)) == 1:
                        return (n, y, k, e), (p, d)

def encrypt (msg, pkey):
    n, y, k, _ = pkey
    m = bytes_to_long (сообщение)
    утверждать m <= 2 ** k - 1
    x = случайный.рандинт (1, п)
    c = pow (y, m, n) * pow (x, 4 ** k, n)% n
    вернуть c
  
 Мы также можем запрашивать открытые ключи и зашифрованные зашифрованные тексты.
 Решение 
 Это странная криптосистема с элементами RSA и заведомо ошибочной генерацией ключей. Частный показатель степени  d  не используется напрямую при дешифровании, но  d  даст нам факторизацию модуля, которая выглядит релевантной при расшифровке. Кроме того, строки около  jp  и  jq  гарантируют, что  y  является квадратичным без остатка (т.е.е. не квадратный корень) по модулю  p  и  q . Использование квадратичной остаточности напоминает нам вероятностную криптосистему Голдвассера-Микали.
 Сразу же мы отметили, что верхняя граница на  d  (N  0,292 ) является верхней границей атаки Боне-Дерфи (B-D). B-D, расширение метода Копперсмита, может восстановить d из модуля, если  d  достаточно мало.
 Мы пробовали использовать «готовую» реализацию B-D, предоставленную здесь Дэвидом Вонгом, однако она не сработала даже после настройки параметров  дельта  и  м .
 А пока нам нужно было выяснить, как расшифровать зашифрованные тексты после восстановления факторизации модуля. Мы нашли статью «Эффективные криптосистемы на основе 2k-х символов остатка энергии», в которой описывается криптосистема, которую мы видим здесь, своего рода «Обобщенный Голдвассер-Микали», отсюда и название задачи «GenGol». Раздел 3.2 содержит алгоритм дешифрования.
 Факторизация модуля 
 Мы смогли решить эту задачу, когда у pcback возникла умная идея изменить атаку B-D, используя тот факт, что простое число $ p $ имело необычную форму.{512}} = 0 \ pmod e $ с $ s = p_0 + q_0 $
 Это приводит к модифицированному уравнению, аналогичному исходному уравнению BD: $ k (A + s) + 1 = 0 \ pmod e $ с $ A = \ frac {N + 1} {2} $ и $ s = - \ frac {p + q} {2} $. Есть одно принципиальное отличие: $ A $ и $ s $ на ~ 512 бит меньше, чем в исходном уравнении. Это приводит к более быстрым вычислениям с меньшим размером решетки.
 Теперь сценарий Дэвида Вонга можно обновить, изменив полином:
  P.  = полиномиальное кольцо (ZZ)
# [-] A = int ((N + 1) / 2)
# [-] pol = 1 + x * (A + y)
A = (N - int (N% (2 ** 512))) // 2 ** 512
pol = inverse_mod (2 ** 512, e) + x * (A - y)
  
 Затем мы можем восстановить $ p $ и $ q $ из $ k $.Запустив модифицированный скрипт pcback, мы получаем следующий результат:
  === решение найдено ===
х: 2683124143283316080652072
6622706483668950238588764594692681480769707324016554574698948603027409300338968573544143950532532532634474498533821603163396485
г: 120671750615350567408663286141792380110847038079359421702223325943240746
8452931825405156276243520869293655223677329
40374796315241454965
р: 68051654200085157207332136111040326067798514
40942748721163833107639364882355808718200151519497304188154695981671131677635619224129781969654824622
7674305201415050592661606881387625228654411615892410789722236619387260438451167443951095682870377511504228417125095204183240940265601
д: 9374271128197012368737527412500899400608329381824894
93069509248449466340860308831673133
398872454947439751830651967183020585597436856749771552385894803
672
745178525979884494517698946787612883007276087925574561383623033220640342314238570313761147
8776114
4468505970527
=== 3.14493989944458 секунд ===
  
 Расшифровка флага 
 Пока pcback учился решать модифицированный сценарий B-D, UnblvR работал над реализацией обобщенного протокола Голдвассера-Микали, который он реализовал с помощью python
  из журнала импорта математики, exp
случайный импорт
из Crypto.Util.number import getPrime, isPrime, inverse, bytes_to_long, long_to_bytes

def legendre_symbol (a, p):
    ls = pow (a, (p - 1) // 2, p)
    вернуть -1, если ls == p - 1 else ls

def genkey (k, nbit):
    утверждать 2 * k <= nbit
    в то время как True:
        p = случайный.randint (1, 2 ** (nbit - k)) * 2 ** k + 1
        если isPrime (p):
            q = getPrime (нбит)
            п = р * д
            в то время как True:
                y = random.randint (1, n)
                jp, jq = pow (y, (p-1) / 2, p), pow (y, (q-1) / 2, q)
                если (jp + jq == p + q - 2):
                    d = random.randint (int (exp (0,272 * log (n))), int (exp (0,292 * log (n)))) | 1
                    е = обратное (d, (p - 1) * (n / p - 1))
                    если e * d% ((p - 1) * (n / p - 1)) == 1:
                        return (n, y, k, e), (p, d)

def encrypt (msg, pub):
    n, y, k, _ = pub
    m = bytes_to_long (сообщение)
    утверждать m <= 2 ** k - 1
    x = случайный.рандинт (1, п)
    c = pow (y, m, n) * pow (x, 4 ** k, n)% n
    вернуть c

def decrypt (c, pub, priv):
    n, y, k, e = pub
    p, _ = priv
    m = 0
    B = 1
    D = pow (y, inverse ((p-1), p) // (2 ** k), p)
    C = pow (c, (p-1) // (2 ** k), p)
    для j в диапазоне (1, k):
        z = pow (C, 2 ** (k-j), p)
        если z! = 1:
            т + = В
            C = (C * D)% p
        В * = 2
        D = pow (D, 2, p)
    если C! = 1:
        т + = В

    м - = (1 << 512)
    возврат абс (м)% (2 ** k)

pub, priv = genkey (512, 1024)
msg = "CCTF {this_is_a_test_message}"
c = зашифровать (сообщение, публикация)
m = расшифровать (c, pub, priv)
assert long_to_bytes (m) == сообщение
  
 Все, что оставалось, - это объединить свои усилия и схватить флаг.512 == 0:
 print ("p:", pf)
 print ("q:", н / пф)
 еще:
 print ("p:", N / pf)
 print ("q:", pf)
 
 Реализация 
  из журнала импорта математики, exp
случайный импорт
из Crypto.Util.number import getPrime, isPrime, inverse, bytes_to_long, long_to_bytes

# Данные о вызове
п = 637934657193
19405006365144325711659387692572782168385080014627719507797647248687148520722936701
665163297786566841633505558063871407960795788255964350193702239693210208145457308480545438217518577295330054116121151347373114755560782040672547926409677195577711382494040585668954215416073608312804727557354730865350850825167829775866577106224100777451079597106302723382941457303546322719775733137646230106938435554843142307807867150
55387034876199982416794024112992052740183312425799530813
6580055307267728332744004833470059699636327292472801239570572097698759537227941727
к = 512
е = 40007058326413048317198208730711
5477856628944800595532469774487124283398595587403418104883
89263237304755152830338075665208
273783575583701947459640516701652368081252494214779
492641287767135
426323
84
1930125022062723737394797498877035678377592141493833793644143952748534446069346
437052
85407270966361128643893842460414222172467789760020896274159442141211350700629427551527427087273383418485054401108735836888266240006621307346844261245374994250245464034080003195611068
30604631216896059360054567160
961463
42186132301488748492678008324441165927
 с = 2076236531012576199455804061453889820064642138786354892007120685667610037384949798864855497275350216543927355263467568
255998266562469789924426960311682067158842635014294314391
94292292
9297783442122092319467511971155786587154474978936572036643051684240363366549216293871321423431247376852947896978619831823340762180349373804433451343033774524112251413433455559241330303444833181863027869585085821237469719514080311264406018170228464955451439678
31504588176012105166481555153278186747662435177630254069
22659896346077715220272241432820818351024774037561959798372661243865688558304519893
# Из модифицированного скрипта B-D
 р = 68051654200085157207332136111040326067798514
40942748721163833107639364882355808718200151519497304188154695981671131677635619224129781969654824622
7674305201415050592661606881387625228654411615892410789
722236619387260438451167443951095682870377511504228417125
09520418324094
0265601
 д = 9374271128197012368737527412500899400608329381824894
93069509248449466340860308831673133
398872454947439751830651967183020585597436856749771552385
894803
672
745178525979884494517698946787612883007276087925574561383623033220640342314238570313761147
8776114
4468505970527
у = 62555029861163892280349841392428573747807
304260235834031195878428382500216962419282794089213188350667672807684260421645876440307096244625059736661128077243622373777
664558475346725148637679179
21827556754971529567337828995831821656338281687895303874971235130850309582018888576967
04573014978038017951327113259714077403045870976500229355564735315227227
78
22720079488985396486582320273126185467503019480961873778316616850146500551181
2050037347024442477453958097596387577424662873349830472175404751943863479573235864782496267138830878462336954417976083797888
утверждать n == p * q

pub = (n, y, k, e)
утверждать n == p * q

def decrypt (c, pub, p):
    _, y, k, _ = pub

    m = 0
    B = 1
    D = pow (y, inverse ((p-1), p) // (2 ** k), p)
    C = pow (c, (p-1) // (2 ** k), p)
    для j в диапазоне (1, k):
        z = pow (C, 2 ** (k-j), p)
        если z! = 1:
            т + = В
            C = (C * D)% p
        В * = 2
        D = pow (D, 2, p)
    если C! = 1:
        т + = В

    м - = (1 << 512)
    возврат абс (м)% (2 ** k)

m = расшифровать (c, pub, p)
печать (long_to_bytes (м))
  
 Флаг 
  CCTF {9en3r4liZed_adDi7iv3lY_h0mOmorphiC_Goldwa5ser_Mic4Li} 
 Блог CryptoHack | Обновления о платформе CryptoHack, новости криптографии и записи о CTF.
 21 мая 2021 г.
 Крипто-спамеры атакуют наше сообщество Discord
 
 DiscordCryptoHack
 Недавно наше сообщество Discord подверглось атаке со стороны спамеров, рекламирующих «раздачу криптовалюты». Мы предприняли несколько шагов, чтобы попытаться предотвратить спам, но они не дали результата. В этом посте исследуется, как, по нашему мнению, спамеры автоматически получают список участников и обходят средства проверки и защиты от злоупотреблений в Discord.В конце мы рассмотрим несколько возможных решений.
 23 апреля 2021 г.
 Кибер-апокалипсис CTF 2021 | Часть 1
 
 WriteupEasyMediumHard
 На этой неделе, возможно, крупнейшее в истории кибербезопасности Capture The Flag (CTF) было проведено как совместное мероприятие между HackTheBox и CryptoHack. С  9900  игроками, участвующими в  4740  командах; обильные призы, включая наличные и подарки; и пожертвования на благотворительность для каждой решенной задачи, это было фантастическое событие для участия.
 23 апреля 2021 г.
 Кибер-апокалипсис CTF 2021 | Часть 2
 
 WriteupInsane
 Во второй части нашего подведения итогов после успеха Cyber ​​Apocalypse CTF 2021 мы разбиваем четыре самые сложные задачи, которые мы включили. RuneScape был вызовом, основанным на криптосистеме Имаи-Мацумото. Тетрис 3D построен на классическом шифре, представленном в Тетрисе. Hyper Metroid требовал вычисления порядка якобиана особого класса гиперэллиптических кривых, а Губка Боб Квадратные Штаны представлял собой заднее столкновение губчатого хэша.Мы любили решать эти задачи и надеемся, что вам понравится эта статья.
 24 марта 2021 г.
 Восстановление полного закрытого ключа PEM, когда половина его отредактирована
 
 TwitterRSAPEM
 ENOENT проверил сегодня учетную запись @CryptoHack__ с помощью CTF-подобного вызова: исходный твит. Вот статья о том, как с помощью частично отредактированного PEM можно восстановить весь закрытый ключ.
 26 янв.2021 г.
 Новые испытания 01/2021 и футболки
 
 ОбъявлениеCryptoHack
 С Новым годом, КриптоХакеры! Пришло время опубликовать следующий набор задач, в котором снова преобладают предложения от сообщества.
 22 янв.2021 г.
 Фактор логарифмического времени: математический трюк
 
 RSABroken-Cryptography
 Если вы интересуетесь криптографией и время от времени просматриваете Reddit, вы, вероятно, уже видели что-то подобное раньше.Кто-то создает новый пост на r / crypto или r / cryptography, утверждая, что может эффективно разложить на множители целые числа или модули RSA. Затем это обычно сопровождается серьезным недостатком контекста и объяснения, обозначениями, которые в лучшем случае сомнительны, часто просто нечитаемыми, и отвращением к предоставлению даже минимального доказательства путем факторизации фактического, криптографически большого модуля. Тем не менее, поскольку это трудно понять, и иногда здесь используется математика, которая, на первый взгляд, может иметь более глубокий смысл, вы задаетесь вопросом, можно ли здесь найти какое-то понимание.
  Спойлер : нет…
 11 янв.2021 г.
 Взлом китайского прокси-туннеля: запись личного прокси CTF в реальном мире
 
 WriteupBlock-CiphersAESNetworking
 Real World CTF - это китайский CTF, ориентированный на реалистичные уязвимости. Это одно из самых сложных, если не , , самое сложное ежегодное соревнование CTF. LiveOverflow предлагает отличное видео с финала 2018 года, демонстрирующее впечатляющие призы, среду киберпанка и физическую безопасность на мероприятии.На этот раз очного финала провести явно не удалось; Вместо этого организаторы пожертвовали деньги на благотворительность.
 6 янв.2021 г.
 Конечные группы, гауссовские целые числа и TetCTF 2021
 
 WriteupFinite-FieldsGaussian-Integer
 На прошлых выходных TetCTF провела новогоднее соревнование CTF. Я испытал особую ностальгию, играя в это, потому что это был CTF TetCTF 2020, где мы с Hyper играли в крипто-вызовы и вскоре после этого решили сделать CryptoHack вместе.Что-то в криптовалютных проблемах Ndh действительно заставляет меня продолжать учиться.
 24 нояб.2020 г.
 Атака по побочному каналу ECDSA: Реестр проективных сигнатур Донжон Запись CTF
 
 WriteupECDSASide-ChannelsSignatures
 Эта задача заключалась в атаке по специальному побочному каналу на криптографию с эллиптическими кривыми. Это была одна из самых сложных задач в Ledger Donjon CTF. Запись от esrever и joachim.
 24 нояб.2020 г.
 Брутфорс Биткойн BIP39 Seeds: Ножницы Секретная книга общего доступа Донжон Запись CTF
 
 WriteupCryptocurrencyBlockchain
 Эта задача была одной из самых простых для понимания в Ledger Donjon CTF. Он включал перебор парольной фразы биткойнов из 12 слов, начиная с частичной информации о ней. Запись от Иоахима.
 23 ноя.2020
 Боковые каналы: удаленная лаборатория и ошибочная запись в AES Ledger Donjon CTF
 
 WriteupSide-Channels AES
 Эти две задачи были частью категории побочных каналов Ledger Donjon CTF и включали использование атак по сбоям.Записи Иоахима и Эсревера соответственно.
 23 ноя.2020
 Подписи BLS и секретная запись RNG Donjon CTF
 
 WriteupECCRNGSignatures
 После наших описаний Fast Multisignatures и One Time-Based Signatures для Ledger Donjon CTF, вот еще две схемы уязвимых подписей из категории чистой криптографии. Записи от Robin_Jadoul.
 19 ноя.2020
 Аппаратный кошелек Судоку: книга эллиптических отношений Donjon CTF Writeup
 
 ЗаписиECCReversingCryptocurrency
 Эта задача была единственной в категории обратного инжиниринга Ledger Donjon CTF.Запись по rbtree.
 19 ноя.2020
 Atmega Pwn: PicoHSM бросает вызов Donjon CTF Writeup
 
 WriteupHardwarePwn
 Это была серия из трех задач эксплуатации оборудования в Ledger Donjon CTF. Все три задачи основывались друг на друге и выполнялись на одном и том же физическом оборудовании, размещенном организаторами. Запись от Robin_Jadoul.
 18 ноя.2020
 Взлом EOS: современный криптокомпьютер Ledger Donjon CTF Writeup
 
 WriteupBlockchainCryptocurrencySmart-Contracts
 Эти две проблемы в категории Hardware / Pwn в Ledger Donjon CTF привели к тому, что мы использовали узел EOS с помощью смарт-контрактов.
 18 ноя.2020
 Быстрые множественные подписи и одноразовая книга подписей Donjon CTF Writeup
 
 WriteupMultisignatures
 Эти две проблемы в категории криптографии Ledger Donjon CTF связаны с использованием уязвимых схем подписей. Запись от josephsurin.
 14 нояб.2020 г.
 Не удается открыть приложения на macOS: ожидает катастрофа OCSP
 
 NewsMacOSOCSPPKI
 Два дня назад пользователи macOS испытывали тревожные зависания при открытии приложений, загруженных не из Mac App Store.Многие пользователи подозревали проблемы с оборудованием их устройств, но, обратившись к социальным сетям, они обнаружили, что это широко распространенная проблема. И это не случайно, что это произошло так скоро после запуска macOS Big Sur.
 11 ноя.2020
 Новые вызовы 11/2020
 
 AnnouncementCryptoHack
 Мы очень рады поделиться со всеми вами новым набором задач с головоломками, созданными CryptoHack и сообществом.Одной из наших мотиваций для CryptoHack было создание предлога, чтобы узнать как можно больше, и нам нравится иметь возможность разгадывать головоломки и изучать новые области математики и криптографии.
 7 сен.2020
 Новые вызовы 09/2020
 
 AnnouncementCryptoHack
 По мере роста CryptoHack мы выпускаем все больше и больше задач, представленных сообществом. Нам нравится получать новые вызовы, особенно в тех областях, которые в настоящее время недостаточно освещены на сайте.
 21 августа 2020 г.
 Открытая полоса, открытая проблема
 
 WriteupMobius-Transformations
 На прошлой неделе CryptoHack играл в CryptoCTF большой командой и сумел занять второе место. Мы поделились описанием задач, которые решили решить вскоре после окончания конкурса. Из всех проблем, с которыми мы столкнулись, двум удалось поставить нас в тупик за 24 часа, на которые боролся CTF.
 15 августа 2020 г.
 CryptoCTF 2020
 
 WriteupCryptoCTF
 Вот наши рецензии на конкурс CryptoCTF 2020.Члены сообщества CryptoHack играли под командой «CryptoHackers» и заняли второе место в общем зачете, решив 18 из 20 задач в течение 24-часового соревнования. Это был первый раз, когда мы все вместе играли в CTF, и мы обязательно будем делать это снова в будущем. Было действительно приятно собрать так много криптографических умов в одном чате и вместе решать некоторые загадочные головоломки.
 Cryptopals Crypto Challenges 
 Добро пожаловать на вызов 
 Незавершенные работы.
 На этом сайте будут размещены все восемь наборов наших криптовалютных задач, с
 решения на большинстве основных языков.
 Но: пока нет. Если бы мы ждали нажатия кнопки «Опубликовать», пока все
 был здесь, возможно, мы будем писать это в 2015 году. Итак, мы публикуем
 как мы идем. В частности: дайте нам немного времени на задачу
 решения.
 Мы не можем представить их лучше, чем
 Мацей Цегловски
 сделал, так что сначала прочтите этот пост в блоге.
 Мы собрали сборник из 48 упражнений, демонстрирующих атаки на реальные криптовалюты.
 Это другой способ узнать о криптографии, чем занятия или чтение книги. Мы даем вам проблемы, которые нужно решить. Они проистекают из недостатков реальных систем и современных криптографических конструкций. Мы даем вам достаточно информации, чтобы самостоятельно изучить основные концепции криптографии. Когда вы закончите, вы не только узнаете много нового о том, как построены криптосистемы, но также поймете, как они атакуются.
 Каковы правила? 
 Нет! В течение нескольких лет мы решали эти задачи по электронной почте и просили участников не сообщать
 их результаты.  Система чести сработала прекрасно!  Но теперь мы готовы отложить церемонию и
 просто опубликуйте задачи, чтобы каждый мог поработать над ними.
 Сколько мне нужно знать математики?
 
 Если у вас возникнут проблемы с математикой в ​​этих задачах, вы сможете найти местного девятиклассника, который поможет вам.Оказывается, многие современные крипто-атаки не требуют сложной математики.
 Сколько криптовалюты мне нужно знать?
 
 Никто. В этом-то и дело.
 Итак, что мне нужно знать?
 
 Вы захотите уметь грамотно писать код на любом языке. Мы получили заявки на C, C ++, Python, Ruby, Perl, Visual Basic, X86 Assembly, Haskell и Lisp. Удивите нас другим языком. Наш друг Мачей говорит, что эти задачи - хороший способ выучить новый язык, так что, возможно, сейчас самое время заняться Clojure или Rust.
 Чего мне ожидать?
 
 Сейчас у нас восемь наборов. Они становятся все труднее. Опять же: они основаны на реальных уязвимостях. Ни одна из них не является «головоломкой». Они не созданы, чтобы сбивать вас с толку. Однако некоторые из атак являются умными, и если вы не знакомы с крипто-хитростью ... что ж, вам должно понравиться разгадывать головоломки. Признание хип-хопа MTV начала 90-х тоже не повредит.
 Можете ли вы дать нам длинное снисходительное описание того, почему вы выбрали именно это?
 
  Оказывается, можем.
 Если вы еще не так хорошо знакомы с криптографией или если вы знакомы в основном с такими вещами, как прикладная криптография, этот факт может вас удивить: большая часть криптографии фатально взломана. Системы, на которые мы полагаемся сегодня, которые, как известно, не могут быть смертельно сломаны, просто ждут, чтобы их сломали. Никто не уверен, что TLS 1.2, SSH 2 или OTR останутся безопасными, как было задумано.
 Текущее состояние криптографической безопасности программного обеспечения аналогично состоянию безопасности программного обеспечения в 1990-х годах.В частности: примерно до 1995 года не было общепризнанным фактом, что программное обеспечение, созданное людьми, может иметь проблемы со счетом. В результате никто не мог правильно определить размер буфера, и человечество потратило миллиарды долларов на очистку после полутора десятилетий аварийных исправлений уязвимостей, связанных с повреждением памяти.
 Подсчет - не сложная задача. Но криптография есть. Есть всего несколько вещей, которые вы можете испортить, чтобы получить неверный размер буфера. Есть десятки, а может быть, и сотни непонятных мелочей, которые вы можете сделать, чтобы взять криптосистему, которая должна быть защищена даже от противника с большим количеством ядер ЦП, чем атомов в солнечной системе, и сделать ее решаемой с помощью сценария Perl и 15 секунд. .Не верьте нам на слово: решайте задачи, и вы увидите.
 Люди уже «знают» это, но на самом деле они этого не знают, и мы думаем, что причина этого в том, что очень немногие люди на самом деле знают, как реализовать самые известные атаки. Так что напишите нам, и мы проведем для вас экскурсию по ним.
 Как мне начать?
 
 Начните здесь!
 Кто это сделал? 
 Томас Птачек (@tqbf)
 Шон Девлин (@spdevlin)
 Алекс Бальдуччи (@iamalexalright)
 Марцин Вельгошевски (@marcinw)
 Криптопалы обслуживаются и расширяются (начиная с Сета 8) Шоном Девлином совместно с командой службы криптографии в NCC Group.
 Мы не смогли бы сделать это без помощи еще нескольких человек. Примерно в порядке
 влияние:
 Нейт Лоусон
 научил нас практически всему, что мы знаем о криптографии.
 Тревор Перрин
 научил Нейта кое-чему. Я могу рассказать вам довольно интересную историю о том, как Тревор
 интеллектуальное происхождение каждой успешной атаки на TLS за последние 5 лет.
 Тай Дуонг и Джулиано Риццо - крестные отцы практического криптографического программного обеспечения.
 безопасность.Некоторые вещи в этом испытании не имели для нас смысла до тех пор, пока
 Джулиано использовал их в распространенном программном обеспечении.
 Юридический
 
 Отдельные материалы упражнений принадлежат их автору и могут распространяться или не распространяться по лицензии с открытым исходным кодом.
 .
No related posts.