Разное

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

Содержание

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

Анализ алгоритма шифрования строки
В данной статье будут приведены алгоритмы шифрования строк для их анализа и дальнейшего декодирования.

Hex

Пример строки

3132333a3b666c6167

Особенности
В hex могут присутствовать только цифры 1234567890 и буквы abcdef. Длина строки должна быть четной.

Base64

Пример строки

MTIzOjtmbGFnMQ==

Особенности
На конце строки могут присутствовать от 0 до 2 знаков ==. Так же в строке могут быть прописные (заглавные) буквы и символы / и +.

Ceasar cipher

Пример строки

pbhagrefvgr.bet

Особенности
Кодируются только буквы (одного алфавита). По-умолчанию поворот на 13 (ROT13), но может быть и другим.

Base32

Пример строки

GEYTCMJRGE======

Особенности
Все буквы одного типа (например строчные). На конце от 0 до 6 знаков =

Atom128

Пример строки

SfQ50x97+IctQfT2QfPm0x99+/CC

Особенности
В середине строки могут присутствовать следующие символы: + / =

URI encode

Пример строки

1234%27%22%D0%BF%D1%80%D0%B8%D0%B2%D0%B5%D1%82

Особенности
Преобразуются все символы, кроме 1234567890 и abcdefghjklmnopqrstuvwxyz В некоторых случаях не используются =, а / и + заменены соответственно на * и —

Demical

Пример строки

flag

Особенности
Преобразуются абсолютно все символы.

Morse

Пример строки

.—- ..— …— ….-

Особенности
Вместо . и — могут использоваться другие символы.

Hackerize XS

Пример строки

1234Λß↻Ð☰∲ç╫¿├↑ღ∏☐þ¶┏§⊥üƴ₪✕¥ᶾпривет

Особенности
Заменяются только буквы английского алфавита.

Reverse=

Пример строки

54321dlrowolleh

Особенности
Чтение строки с конца.

Binary

Пример строки

01101000 01100101 01101100 01101100 01101111

Особенности
Пробелы могут быть не расставлены. Тогда длина строки будет делиться на 8, на 7 или на 6 (зависит от случая).

Encool 2

Пример строки

1234❡øø∂נøß❣привет

Особенности
Кодируются только символы английского алфавита.

MEGAN-35

Пример строки

RdNtSLX1lLranwDslLbrRZRuSdixTI/q

Особенности
Аналогично Atom128.

TRIPO-5

Пример строки

mYGKnj=znKAMmgTT

Особенности
Аналогично Atom128

GILA7

Пример строки

Bg=dCTzrCd/hB7GG

Особенности
Аналогично Atom128.

HAZZ-15

Пример

+gidJ4zoJdQL+H55

Особенности
Аналогично Atom128.

ESAB-46

Пример

vz5jND0mNjQpvA//

Особенности
В строке могут присутствовать символы / и =

TIGO-3FX

Пример

w1V3Dx+ID35TwFXX

Особенности
Аналогично Atom128.

FERON-74

Пример

WrSZdY6mdZwoW744

Особенности
Аналогично Atom128.

ZONG22

Пример

Xd0F19xc1FHMXZ22

Особенности
Аналогично Atom128.


взято с сайта http://itsecwiki.org/

Заметка пятая. Разбор задания Crypto Backdoor с Google CTF 2017

Это заметка о том, как мы с Костей Плотниковым решали задание на ассиметричную криптографию с Google CTF, который прошёл неделю назад. Она кишит кодом на питоне, несложными терминами из теории групп и математическими выкладками. Смело пропускайте, если боитесь чего-нибудь из этого.

Формулировка как всегда бесконечно расплывчата:

This public-key cryptosystem has a flaw. Can you exploit it? crypto_backdoor.py

Костя попробовал меня ввести в курс дела, когда я присоединился к нему. Он рассказал, что в скрипте реализовано что-то вроде эллиптической криптографии. Работает она так: сначала на плоскости рисуется специальная кривая, а затем для каждой пары точек на ней определяется операция сложения. Сумма двух точек с кривой тоже лежит на кривой за исключением случая, когда получается особое значение — ноль. После этого естественным образом определяется умножение точки на натуральное число.

В эллиптической криптографии Боб, желающий получать зашифрованные сообщения от Алисы, выбирает секретное число $N$ и точку на эллиптической кривой $g$. Последняя называется генератором и сообщается всем желающим, а вот секретное число становится закрытым ключом Боба. Открытым ключом в этом случае называется произведение генератора и закрытого ключа; $B = Ng$.

Собственно, на мысли об эллиптических кривых Костю натолкнули наличие в скрипте точки-генератора и двух открытых ключей:

# Modulus
p = 606341371901192354470259703076328716992246317693812238045286463
# g is the generator point.
g = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824)
# Alice's public key A:
A = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727)
# Bob's public key B:
B = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485)

Модуль $p$ здесь тоже неслучаен — в эллиптической криптографии как раз рассматриваются кривые над полем $\mathbb{Z}_p$. Позже, правда, мы пришли к выводу, что эллиптическая криптография тут совсем ни при чём. .. Но сначала мы внимательно изучили операцию сложения двух точек:

def add(a, b, p):
  if a == -1:
    return b
  if b == -1:
    return a
  x1, y1 = a
  x2, y2 = b
  x3 = ((x1*x2 - x1*y2 - x2*y1 + 2*y1*y2) * modinv(x1 + x2 - y1 - y2 - 1, p)) % p
  y3 = ((y1*y2) * modinv(x1 + x2 - y1 - y2 - 1, p)) % p
  return (x3, y3)

Нейтральный элемент (он же ноль) обозначен как $-1$, поэтому первые четыре строки функции очевидны. Функция $modinv(x, p)$ находит обратный элемент к $x$ в кольце $\mathbb{Z}_p$ с помощью расширенного алгоритма Евклида. Значит, сумма точек $(x_1, y_1)$ и $(x_2, y_2)$ это точка
$$\left(\frac{x_1x_2 — x_1y_2 — x_2y_1 + 2y_1y_2}{x_1+x_2-y_1-y_2-1}, \frac{y_1y_2}{x_1+x_2-y_1-y_2-1}\right)$$

Дробь означает целочисленное деление в кольце $\mathbb{Z}_p$.

Упрощаем сложение

Математик во мне захотел разобраться с этой операцией. Больше всего смущали одинаковые знаменатели и сложный числитель первой координаты. Стало проще, когда я переписал числитель как $(x_1-y_1)(x_2-y_2)+y_1y_2$, а знаменатель как $(x_1-y_1) + (x_2-y_2)$. Давайте перейдём из системы координат $(x, y)$ в систему $(t, y)$, где $t = x-y$. Обратный переход тоже очень простой: $x = t + y$. Если переписать операцию сложения в новой системе координат, то получится

$$(t_1, y_1) + (t_2, y_2) = \left(\frac{t_1t_2+y_1y_2}{t_1+t_2-1} — \frac{y_1y_2}{t_1+t_2-1}, \frac{y_1y_2}{t_1+t_2-1}\right) = \left(\frac{t_1t_2}{t_1+t_2-1}, \frac{y_1y_2}{t_1+t_2-1}\right)$$

Получившаяся формула в некотором смысле даже симметрична. Это дало нам оптимизм на несколько следующих часов.

Мастер-секрет

Однако в скрипте само по себе сложение нигде не используются. Зато используется умножение точки на число:

from secret_data import aliceSecret, bobSecret, flag

assert A == mul(aliceSecret, g, p)
assert B == mul(bobSecret, g, p)

aliceMS = mul(aliceSecret, B, p)
bobMS = mul(bobSecret, A, p)
assert aliceMS == bobMS
masterSecret = aliceMS[0]*aliceMS[1]

Настало время разобраться, что вообще происходит в скрипте и что нужно найти. k = \frac{B_t}{1 + B_t}$$

Чтобы найти искомое $k$, достаточно вычислить логарифм в кольце $\mathbb{Z}_p$, то есть решить задачу дискретного локарифмирования. Здесь мы с Костей приуныли, потому что поняли, что зашли в тупик. Дискретное логарифмирование — задача, которую нельзя решить за нормальное время.

Только через час Костя догадался проверить данный нам модуль $p$ на простоту. Совершенно неожиданно он оказался составным:

$$p = 961236149 \times 951236179 \times 941236273 \times 911236121 \times 931235651 \times 921236161 \times 901236131$$

Наверняка все знают, как посчитать дискретный логарифм по непростому основанию. А мы не знаем. Так что мы взяли бумажку и стали придумывать алгоритм.

Когда-то Асанов рассказывал байку, что студенты УПИ обычно знают способ решить задачу, а студенты матмеха не знают. Зато студенты матмеха могут придумать решение. Кажется, теперь я понял эту байку.

Дискретный логарифм по составному основанию

Пусть мы нашли дискретный логарифм от $b$ по основанию $a$ в кольцах $\mathbb{Z}_p$ и $\mathbb{Z}_q$. {m+3v} \equiv \dots \pmod{q}$. Если мы найдём число, которое можно выразить и как $n + ?u$, и как $m + ?v$, то оно станет ответом задачи дискретного логарифмирования по модулю $pq$.

Ну а найти такое число — дело техники и расширенного алгоритма Евклида. Если $n + ?u = m + ?v$, то $?u — ?v = m — n$. Если $m-n$ не делится на $НОД(u, v)$, то решения нет, иначе расширенный алгоритм Евклида решит это линейное диофантово уравнение, и всё станет хорошо.

Так как данный в задании модуль $p$ мы разложили на простые множители $p_1 \times p_2 \times \dots \times p_7$, которые к тому же получились не очень большими, то мы можем решить задачу дискретного логарифмирования в каждом из $\mathbb{Z}_{p_i}$. Соединить семь чисел в один большой ответ поможет описанный только что алгоритм.

Как решить дискретный логарифм для  $p_i$

Простые делители модуля $p$ были не очень большими, но и не настолько маленькими, чтобы дискретный логарифм можно было найти простым перебором. К счастью, есть алгоритм Baby Steps Giant Steps, который позволяет сделать это намного быстрее — за $O(\sqrt{n})$. {\phi(p)} \equiv 1 \pmod{p}$, но $\phi(p)$ могло оказаться не минимальным числом с таким свойством. Значит, искомый порядок — это делитель $\phi(p)$. Но делителей слишком много, чтобы перебирать их все. Так что пришла пора узнать более быстрый способ находить порядок элемента. На помощь пришла пдфка из интернета, в которой есть чудесный алгоритм 4.79, я реализовал его и научился быстро находить порядок элемента в кольце, зная разложение на простые множители у $\phi(p)$.

Заключение

Применив всю магию сверху, мы нашли закрытый ключ Боба $bobSecret$. Умножив его на открытый ключ Алисы, мы нашли мастер-секрет, который и выдал нам флаг:

Master secret found: (254828745614253797280016043417264027645246572307317271091197847, 540509273347153402828726537667691800163306365090607497812000946)
Flag: CTF{Anyone-can-make-bad-crypto}

Если вкратце повторить всё наше решение, то оно перестаёт казаться страшным и длинным:

  1. переходим в систему координат $(t, y)$,
  2. вычисляем $a = \frac{g_t}{g_t+1}$ и $b = \frac{B_t}{1 + B_t}$,
  3. решаем задачу дискретного логарифма $a^{?} = b$ в кольце $\mathbb{Z}_p$, зная разложение $p$ на простые множители,
  4. умножаем полученный ответ на открытый ключ Алисы $A$, это и есть мастер-секрет,
  5. переходим обратно в координаты $(x, y)$, перемножаем координаты мастер-секрета, расшифровываем флаг.

Материалы для подготовки к Олимпиаде

В данном разделе опубликованы рекомендованные материалы для самостоятельной подготовки к Олимпиаде

Формат проведения

CTF (Capture The Flag) task-based — это формат соревнований по информационной безопасности, целью которого  является захват так называемого «флага» за выполнение задания. Это могут быть скомпрометированные данные, пароли, почты и всё то, что можно найти во время анализа приложений и файлов. Все флаги имеют одинаковый формат: InnoCTF{[a-zA-Z0-9]+}. Пример: InnoCTF{h5110_w0r1d}. За отправленный «флаг» участники получают баллы. Все задания можно отнести к следующим категориям:

  • admin — безопасное администрирование операционных систем Windows и Linux
  • crypto — криптографическая защита информации
  • forensic — компьютерная криминалистика в IT-сфере
  • math — хэши, алгоритмы, сортировки, структуры данных
  • network — анализ сетевого трафика и отслеживание вредоносной сетевой активности
  • ppc — профессиональное программирование подсистем в сфере ИБ
  • reverse — обратная разработка и исследование бинарных программ и алгоритмов
  • stegano — поиск и обнаружение скрытых каналов передачи, а также их организация
  • web — поиск и эксплуатация веб-уязвимостей

Литература

Если вы не знаете, что такое информационная безопасность, то для начала вам стоит посетить CTF News — самый крупный новостной портал в России на данную тематику. Специально для новичков есть отдельный раздел со всей необходимой литературой.
Также будут полезны данные ресурсы:
https://dlib.rsl.ru/02000023874
http://kmb.ufoctf.ru/

Полезные инструменты

Как уже было описано выше, все задания входят в одну или несколько категорий. Для каждой категории мы собрали список инструментов, которые могут оказаться полезными при решении:

  • admin: Docker, Bash, SSH, Linux commands
  • crypto: Cryptool, Sage, xortool, John the Ripper
  • forensic: binwalk, ExifTool, Volatility, CAINE
  • math: AlgoList, E-maxx, Hydra
  • network: Wireshark, Netcat, Socat, OpenVPN, OpenSSL, nmap
  • ppc: Python, Sublime Text, Notepad++, Vim
  • reverse: GDB, IDA Pro, OllyDbg, Hopper, dex2jar, uncompyle6
  • stegano: OpenStego, Steghide, GIMP, Audacity, StegSolve
  • web: Burp Suite, Beef XSS, Nikto, Sqlmap

Практика

Для проверки своих знаний вы можете воспользоваться следующими ресурсами:
https://ctftime. org/
https://training.hackerdom.ru/
http://freehackquest.com/
https://hack.me

CRYPTO CTF

  • Объявления

  • Команды

  • испытаний

  • Табло

  • правил

  • FAQ

  • Войти

  • Зарегистрироваться

2nd Crypto CTF 2020 состоится между

Пт, 14 авг 2020, 15:00 UTC — сб, 15 авг 2020, 15:00 UTC

Давай повеселимся!

CTFtime.

org / Крипто CTF

CTFtime.org / Крипто CTF

Официальный URL: https://cr.yp.toc.tf/

Crypto CTF — это онлайн-соревнование для хакеров, призванное проверить, оценить и расширить свои навыки использования криптографии. В этом CTF мы представим различные криптографические задачи, касающиеся современных методов криптографии.
Добро пожаловать всем любителям криптовалюты!
CryptoCTF — это месть за постоянные жалобы участников CTF на крипто-вызовы в соревнованиях CTF.В этом новом турнире мы пытаемся предоставить любителям криптографии увлекательные и сложные задачи, связанные с чистой криптографией, чтобы сжать их сердце и проверить их страсть к криптографии.
Каждая задача будет основана на конкретном криптографическом примитиве или будет включать прямое применение криптографии в других областях.
Организаторы этих турниров щедро предлагают свои навыки для разработки оригинальных задач и задач Crypto для подобных конкурсов.

Да здравствует крипто 🙂

CTF событий

Связанные теги:

сеть

pwn

php

крипто

стего

прыгать

взлом

криминалистика

gpg

base64

андроид

питон

xor

des

RSA

основной

грубая сила

c ++

разобрать механизм с целью понять, как это работает

метасплоит

программирование

c

инженерное дело

безопасность

разное

разгромленный

sql

эксплуатировать

стегано

математика

сеть

Рубин

prng

http

проникновение

вредоносное ПО

окна

сеть

пентестинг

угадывать

html

существование

linux

анализ

факторинг

спать

rev

nmap

встроенный

базы данных

bof

шеллкод

переполнение

Ферма

GDB

PNG

реверсирование

криптография-rsa

тор

электроника

подмена

спать

aws

нападения

буфер

ret2libc

статический

ecc

склеп

c

рюкзак

esper

обеспечить регресс

criativas

Gambiarras

куча

pgp

повернутый

гаусс

rsa-подобный

матрица

обмен секретами

движущийся

виртуальный бокс

number_theory

gcd

модульно-арифметический

многочлен

линейная алгебра

случайность

бессерверный

35c3

криптоапи

windowsbinary

gc

холм

арифметика

оаэп

misc200

бух

fini_array

Boneh-Durfee

ret2win

многочлены

Goldwasser-Micali

сложный

биномиальный

частота

напиши что где

defcon2021

квантовый крипто

FIRST SecLounge CTF 2020 — Крипто-вызовы

Трек

, состоящий из 7 вопросов, связанных с различными задачами криптографии. [защита электронной почты] <[защита электронной почты] @ V $ [защита электронной почты] / RiF9 + ELt'AKWC0DIal6Bln $ & DBO% [защита электронной почты] << W # G & M) * + Ceu '[защита электронной почты] / pn8P (% 7Df0Z; DepP + De * F #.4cTMDIal, @ + DkP $ DKK <$ DBO.: Blmp-E + * 6f / g + ,, F`T) VDf0B: + EV:. +? ;;% E, oZ1FCAWpAKX9; [защита электронной почты]]: [защита электронной почты]: [ электронная почта защищена] @; F (& Zl + s: uG + E_a: [электронная почта защищена], D / @ <> p1 + B3 # c + D, FuB-: o0 +> @ 54Ai; PXAR [MU2.SO «ARf =` 1h &

Это текст в кодировке ASCII85. Мы можем догадаться об этом, проанализировав частоту символов, посмотрев на распределение и т. Д.

Расшифрованный текст:

Основная потребность в кодировании двоичного кода в текст возникает из необходимости передавать произвольные двоичные данные по уже существующим протоколам связи , которые были разработаны для передачи только англоязычного текста, читаемого человеком. Эти протоколы связи могут быть только 7-битными (и в рамках этого избегать определенных управляющих кодов ASCII) и могут требовать разрыва строки через определенные максимальные интервалы и не могут содержать пробелы. Таким образом, только 95 печатаемых символов ASCII «безопасны» для передачи данных.Флаг — 0aaf66deb575d43ecfe4b5205157d538f54e77f0547a3b7e5125fea2a3995f0b.

Флаг : 0aaf66deb575d43ecfe4b5205157d538f54e77f0547a3b7e5125fea2a3995f0b

Нарушение кода

Можете найти флаг?

Мы обнаружили секретный текст, скрытый в строке исходного кода HTML 1004:
segsa ptvey xmjve kerkt xqjtx gmvtt urksy bzuzo

И следующее в заголовке HTTP: x-options: M3 — B — I, IV, V — J, T, V — 1,1,1

Это настройки шифрования Enigma:

  • M3 — модель 3
  • B — отражатель типа
  • I, IV, V — типы ротора и заказ
  • Дж, Т, В — ротор начальное значение
  • 1,1,1 — установочные кольца роторов

Мы использовали CyberChef для декодирования флага.

Флаг : JFKJR UIAWX MVDZW YGKNC MLTGK JDXSE

Нарушение кода — бонус

Можете найти флаг?

Зашифрованная строка: jjlpe oniqy lkwht griha bhesq zyiqz btikt idj

Мы нашли изображение в кодировке base64 в источнике HTML.

Это также настройки Enigma. С помощью поиска Google мы нашли исходное изображение, которое помогло идентифицировать столбцы.a l cfX> 2 <6D: E [защита электронной почты]: 3 = 6 [защита электронной почты] @ 3E2 :? 2 DJ >> 6EC: 42 = 4: A96C [D:>: = 2C [защита электронной почты] # ~% b [защита электронной почты] E96 ae = 6EE6CD @ 7 E96 2 = A9236EX]% 96 7 = 28: D baf5decdg7eeg37fcbh343g_67c55c_cg6`ea642haa637ad _3f

Текст закодирован с помощью ROT47. Либо мы угадываем это, либо пытаемся взломать его как шифр подстановки, один за другим.

Некоторые из самых основных шифров — это шифры подстановки. Если мы посмотрим на зашифрованный текст и пробелы между символами выглядят естественно, обычно можно предположить, что это шифр подстановки, в котором пробелы не заменяются.

Также проверка индекса совпадения текста может помочь нам идентифицировать. (Это текст на английском языке — https://en.wikipedia.org/wiki/Index_of_coincidence.) К сожалению, в этот раз этого не происходит, поскольку индекс совпадения обычно рассчитывается только по строчным буквам и без каких-либо специальных символов или цифр.

Как только мы узнаем, что это английский текст с подстановочным шифром, мы можем попытаться угадать символы. Поскольку мы видим как строчные, так и прописные буквы, это хорошее предположение, что символы в начале зашифрованного текста «% 96» переводятся в «The».Мы можем работать оттуда и легко угадывать почти всех персонажей.

Как только мы закончили и остались с неизвестными символами, верный путь вперед — это вычислить расстояние между зашифрованными и незашифрованными текстовыми символами. Как только мы понимаем, что это константа 47, мы знаем, что это всегда был ROT47.

Подсказка1: При вычислении индекса совпадения или использовании автоматического взломщика шифра подстановки для текста рекомендуется удалять последнюю часть зашифрованного текста, которая обычно содержит случайные символы (файл.k.a флаг).

Hint2: Название задачи было большой подсказкой, которую мы поняли только позже. Салат относится к Цезарю, а «x / 2» относится к половине. Половина Цезаря — это именно ROT47.

Hint3: Мы не знаем, почему некоторые символы были красными. Наверное, это был ложный флаг.

Flag : 327d56458f668bf7439acb80ef4dd4048e62eca64db253a922eebfa7a3e10b7 (Исходный флаг был той же строкой с пробелом в конце, но позже организаторы изменили его.)

Challenge of the Challenge — Bonus

В качестве награды за чтение инструкций обратите внимание, что если вы когда-нибудь найдете флаг со значением, вы должны отправить строку, закодированную с помощью ROT13, чтобы заработать кредит.

На странице инструкций были скрыты шестнадцатеричные значения.

Собирая их, мы получили следующее: ФЛАГ: Все должны прочитать инструкцию перед запуском!

Версия в кодировке ROT13 «Все должны прочитать инструкции перед запуском!» был флаг.

Flag : Rirelobql fubhyq ernq gur vafgehpgvbaf orsber fgneg!

Музей

Этот музей скрывает для вас очень важный секрет.

Поскольку это криптовалюта с изображением, мы заподозрили, что стеганография использовалась, чтобы скрыть флаг. Нам просто нужно было найти правильный алгоритм и ключ.

В качестве первого шага мы искали здание на Google Maps.Сравнив оригинальное здание с изображением, мы нашли первую подсказку.

Первое изображение взято из изображения в задании; второй — оригинал.

Мы подозревали, что значение 1903 как-то связано с ключом, который мы искали.

Следующим шагом был поиск правильного алгоритма.

Мы потратили довольно много времени и попробовали несколько инструментов, чтобы найти правильное направление.

Stegdetect был одним из самых полезных инструментов, он подсказал, что алгоритм, который мы ищем, — это F5.

Мы использовали декодер стеганографии F5, найденный на GitHub. Большую часть времени мы угадывали правильный пароль. Поскольку 1903 год не помогал, мы пробовали несколько других паролей, пока наконец не нашли правильный. Пароль был 219036, так как орнамент около 1903 года интерпретировался как числа.

Флаг : 322b

fca3b9bb72eb410c7da1d1d

Решения CTF-задач для криптографии net-force

Криптоанализ относится к изучению шифров с целью взлома кода и получения незашифрованной (разумной) информации.В то время как более старые криптосистемы, такие как шифр Цезаря, зависели от секретности самого алгоритма шифрования, современные криптосистемы предполагают состязательное знание алгоритма и криптосистемы. Обещание секретности обеспечивается защищенным ключом, который имеет решающее значение для дешифрования зашифрованного текста в практические временные рамки. Во время криптоанализа у нас нет ключа, и мы обязаны получить соответствующий открытый текст.

В приведенных ниже задачах мы сосредотачиваемся на обнаружении закономерностей в зашифрованном тексте, чтобы понять, как происходило шифрование.В отличие от хеширования, шифрование — это , а не односторонний процесс, поэтому мы можем отменить его, чтобы получить открытый текст. Грубая сила — это последний выбор при криптоанализе, поскольку современные шифры могут иметь чрезвычайно большие размеры ключей. Решая эти задачи, вам следует по возможности воздерживаться от бездумного грубого форсирования или использования автоматизированных инструментов. Вместо этого лучше изучить криптосистему как можно более тщательно и попутно развивать навыки взлома кода.

О задачах криптографии net-force

Эти задачи требуют, чтобы вы нашли пароли, скрытые в предоставленных зашифрованных текстах.Задачи расположены в порядке возрастания сложности, и вы можете выполнять их в любом порядке. Каждая задача зависит от множества криптографических методов и требует логического мышления, чтобы прийти к решению.

Спойлер!

Обратите внимание, что следующий контент предоставляет решения интригующих криптографических проблем в Net-Force. Было бы бесполезно читать дальше, не попробовав сначала свой абсолютно лучший в сложных условиях.

Решения криптографических проблем с 1 по 8

Задача криптографии 1, уровень 301: «Основы криптографии»

Эта первая задача — это стартовая задача, знакомящая нас с концепцией криптографии и криптоанализа, и поэтому она очень проста. Нам предоставляется строка символов, которую нам нужно расшифровать, чтобы получить текстовое сообщение [рисунок 1].

Рисунок 1

Если вы знакомы с текстом в кодировке base64, знаки «=» в конце несут полную уверенность в том, что строка требует декодирования base64.Чтобы base64 декодировал эту строку в Linux, мы используем утилиту base64 [Рисунок 2]:

Рисунок 2

После декодирования base64 у нас все еще есть зашифрованный текст, который, по-видимому, является результатом простого шифрования поворота. Мы написали небольшой скрипт на Python, который перебирал нас, пока мы не смогли прочитать открытый текст. В качестве альтернативы вы можете использовать один из инструментов дешифрования шифра ротации в режиме онлайн, чтобы получить открытый текст [рисунок 3].

Рисунок 3

Примечание : Часто задаваемый вопрос студентов о тексте в кодировке base64: всегда ли он заканчивается знаком «=»? Ответ — «Нет».Знак «=» используется в качестве заполнения, чтобы гарантировать, что результирующая строка в кодировке base64 имеет оптимальную длину. Однако, если он уже имеет нужную длину, заполнение не требуется, и вы не увидите знак «=» в конце. Таким образом, не зависите от идентификации строк в кодировке base64 на основе завершающих знаков «=».

Пароль : crypto

Задача криптографии 2, уровень 302: «Замена…»

Эта следующая задача немного сбивает с толку людей, не говорящих по-голландски, поскольку в результате получается «открытый текст» на голландском языке.Название предполагает, что это простой шифр подстановки, который легко решить с помощью атаки известного открытого текста.

Рисунок 4

Вначале, при отображении зашифрованного текста на данный открытый текст, мы знаем 5 замен: «o»: «l», «g»: «e», «r»: «u», «t»: «z» и «Z»: «t». Мы пишем небольшой словарь Python, который выполняет эти замены в зашифрованном тексте, и теперь у нас есть частичный открытый текст [рисунок 5].

Рисунок 5

С этого момента мы зависим от поиска шаблонов и добавления новых сопоставлений по мере их изучения.Например, последним словом может быть «netforce», что означает, что нам нужно сопоставить: «d»: «f», «l»: «o», «u»: «r» и «a»: «С».

Теперь вырисовывается закономерность. Мы замечаем, что если «r» отображается в «u», то «u» будет отображаться в «r». Используя это знание, мы можем производить дальнейшие замены, пока не получим голландское сообщение с открытым текстом [рисунок 6].

Рисунок 6

Этот скрипт Python доступен на GitHub.

Google Translate затем показывает нам приблизительный перевод этого голландского сообщения:

«Хорошая замена, зашифруй мне пароль для страницы вызова netforce»

Пароль : netforce

Задача криптографии 3, уровень 307: «Морской кодекс»

Этот код должен быть знаком большинству, если не всем.Точки и тире — явное свидетельство того, что это азбука Морзе. Если есть сомнения, название «морской кодекс» подтверждает это. Вы можете декодировать этот код Морзе вручную или использовать один из онлайн-декодеров кода Морзе.

После декодирования получается открытый текст: THEPASSWORDFORTHISLEVELISWELLDONE

Пароль : welldone

Задача криптографии 4, уровень 305: «крипта XOR»

Эта задача представляет нам 2 длинные двоичные последовательности и просит нас объединить их, в то время как в заголовке задачи написано «XOR» [Рисунок 7].

Рисунок 7

Становится ясно, что мы должны выполнить побитовое исключающее ИЛИ для этих двух двоичных последовательностей. Мы объединяем их с помощью побитового XOR и преобразуем полученную двоичную последовательность в ASCII для получения открытого текста с помощью скрипта Python [рисунок 8].

Рисунок 8

Этот скрипт Python доступен на Github.

Пароль : bin

Задача криптографии 5, уровень 304: «Проверьте таблицы….”

Эта задача представляет собой частично понятный зашифрованный текст. Если вы знакомы с криптографией, ссылка в заголовке на «таблицы» должна указывать на то, что это некая форма транспозиционного шифра.

Рисунок 9

В шифре транспонирования вы переставляете символы вместо того, чтобы делать замены, как в случае шифра замены. Мы начинаем с определения того, что, возможно, является отправной точкой предложения открытого текста, «thisisatra», и переходим оттуда.Вскоре порядок транспонирования становится очевидным, и мы получаем расшифрованный открытый текст [рисунок 10].

Фиг.10

Пароль : столбцы

Задача криптографии 6, уровень 308: «Да здравствует Франция»

Эта задача требует от нас провести атаку с использованием известного открытого текста, поскольку нам предоставляется фрагмент зашифрованного текста и соответствующий открытый текст. После внимательного изучения обоих, мы замечаем, что, хотя сначала «t» отображалось в «v», позже в строке «t» было отображено «r» [рисунок 11].Это говорит о том, что мы имеем дело с полиалфавитным шифром — скорее всего, с шифром Виженера.

Рисунок 11

Можно получить ключ на основе известной атаки с использованием открытого текста с использованием программирования. Здесь мы используем онлайн-анализатор шифров Виженера, который мгновенно обнаружил ключ с известным открытым текстом [Рисунок 12].

Рисунок 12

Используемый ключ был «криптогай». Глядя на эту табличку Виженера, мы можем увидеть, как символы открытого текста были сопоставлены с зашифрованным текстом с помощью символов в ключе.Например, на рисунке 13 показано, как первый символ открытого текста «t» был сопоставлен с «v» с использованием первой буквы в ключе, то есть «c». Обратите внимание, что ключ Виженера повторяется в процессе шифрования.

Рисунок 13

Примечание : Шифр ​​Виженера — популярный и простой пример полиалфавитного шифра. Следовательно, заметив полиалфавитный шифр, Виженер должен сделать первое предположение относительно алгоритма шифрования.Также обратите внимание, что в названии упоминается Франция. На самом деле это намек, поскольку шифр Виженера был дан французом Блезом де Виженером.

Пароль : cryptoguy

Задача криптографии 7, уровень 303: «СУПЕР-шифр»

Следующая задача представляет собой строку для дешифрования, и эта строка зашифрованного текста также содержит некоторые числа. На первый взгляд, все сохраненные пробелы и длины слов позволяют предположить, что это еще один шифр подстановки.

Рисунок 14

Нашим первым ключом к решению проблемы было наблюдение за образцом в зашифрованном тексте, который был подобен образцам, встречавшимся ранее в открытых текстах других задач. Расшифрованная строка открытого текста в запросах обычно говорит что-то вроде: «Пароль для страницы запроса — ******». Наблюдая за зашифрованным текстом, весьма вероятно, что первое слово — это «the» (что будет означать, что 4 -е слово также является «the»), 2 -е слово — «пароль», а 5 -е слово — это «пароль». слово — «вызов».Тот факт, что зашифрованный текст повторяет символы так же, как возможный открытый текст, предполагает, что это моноалфавитный шифр подстановки . Например, вероятное текстовое слово «пароль» содержит 2 «s», а соответствующее слово зашифрованного текста «q5tt /> /> lse» содержит 2 «t» и находится в нужном месте. Это означает, что мы можем сопоставить «t» с «s» во время дешифрования. Точно так же мы можем формировать ассоциации для других символов в открытом тексте и зашифрованном тексте. Из этих ассоциаций мы смогли получить частичный открытый текст [Рисунок 15].

Рисунок 15

После наблюдения становится очевидным, что «i» отображается в «2». Следовательно, открытый текст, который мы знаем до сих пор, выглядит следующим образом: «пароль для сайта вызова: el ** e».

Возможным паролем может быть «элитный», что имеет смысл. Однако сайт вызова отклонил этот пароль. Это потребовало дальнейшей оценки зашифрованного текста, которая выявила другую закономерность. Этот шаблон имеет какое-то отношение к «leetspeak». Буквенное обозначение «t» — «7», 7, увеличенное на 1, равно 8, что является символом зашифрованного текста.Аналогично, leetspeak для «i» — это «1», 1, увеличенная на 1, составляет 2, что является символом зашифрованного текста. Зная, что leetspeak участвует в шифровании, мы приходим к «3lit3», что является правильным паролем.

Пароль : 3lit3

Задача криптографии 8, уровень 306: «Задача дешифрования»

Эта задача представляет собой длинную строку чисел, которую мы должны расшифровать. Подсказка в названии (DEC) предполагает, что это как-то связано с десятичными знаками.При внимательном рассмотрении зашифрованного текста выявляется шаблон «909», повторяющийся в строке [рисунок 16].

Рисунок 16

После многочисленных попыток нам не удалось связать значение с «909» в контексте зашифрованного текста. Следовательно, мы решили убрать его из зашифрованного текста. Мы использовали функцию замены Python, чтобы удалить все вхождения «909» из зашифрованного текста. Нас осталось:

841041011129711511511

14100105115100101999

10118101114116

Используя подсказку, приведенную в заголовке, decimal, мы обработали эту последовательность как строку десятичных знаков.Для этого мы использовали функцию полосы Python, чтобы удалить все «909» и сохранить полученные десятичные дроби в списке. Теперь у нас:

[’84’, ‘104’, ‘101’, ‘112’, ’97’, ‘115’, ‘115’, ‘119’, ‘111’, ‘114’, ‘100’, ‘105’, «115», «100», «101», «99», «99», «111», «110», «118», «101», «114», «116»]

Затем, после преобразования этих десятичных знаков в соответствующие символы ASCII с помощью функции chr в Python, мы получили текстовое сообщение [рисунок 17].

Рисунок 17

Этот скрипт Python доступен на Github.

Пароль : decconvert

Заключение

После некоторого бездействия сообщество Net-Force снова принимает новых членов и находится под новым руководством. Эти криптографические задачи в Net-Force были хорошо продуманными и интригующими. Если вы новичок в криптоанализе, эти упражнения позволят вам быстро освоиться с проблемами, которые усложняются по мере вашего продвижения.

Криптоанализ — это метод проб и ошибок, и обычно требуется несколько попыток, прежде чем вы поймете закономерности в сложных задачах.В приведенных выше решениях для краткости обсуждаются только успешные попытки. Если вам это понравилось, подумайте о том, чтобы попробовать более увлекательные задачи в Net-Force, чтобы проверить или развить свои навыки в области безопасности.

Источники

Сообщество Net-Force

Вызовы

Стол Виженера

Анализатор шифров Виженера онлайн

Гугл переводчик

CryptoCTF 2020 | Блог CryptoHack

Вот наши рецензии на конкурс CryptoCTF 2020.Члены сообщества CryptoHack играли под командой «CryptoHackers» и заняли второе место в общем зачете, решив 18 из 20 задач в течение 24-часового соревнования. Это был первый раз, когда мы все вместе играли в CTF, и мы обязательно будем делать это снова в будущем. Было действительно приятно собрать так много криптографических умов в одном чате и вместе решать некоторые загадочные головоломки.

Спасибо всем, кто играл за CryptoHackers, и ASIS CTF за организацию этого приятного мероприятия.Поздравляем Хеллмана за то, что он стал удивительно быстрой армией из одного человека!

Мы опубликуем здесь больше рецензий, как только они будут закончены. Если вы заметили ошибку или улучшение, которое можно было бы сделать, пинг-джек или гиперреальность на CryptoHack Discord.

Вызовы

Название задачи Категория решено Очки
Завершающие биты Битшифтинг willwam845 30
Амстердам Кодировка randomdude999, rkm0959 55
Игрок PRNG Cryptanalyse, willwam845 87
Три вороны RSA TheBlueFlame121 90
Модель RSA TheBlueFlame121, rkm0959, Иоахим 112
Однострочная криптография Простые числа UnblvR 146
Аббат Математика ркм0959 194
Эффект бабочки PRNG rkm0959, Робин_Джадул 209
Безумная шляпа Матрицы ркм0959 217
Классический Классический Смокинг, гиперреальность 226
Небеса ЛФСР Q7, Робин Джадул 226
Полоса Простые числа задняя панель, rkm0959 285
Комплекс в ад Hill Cipher задняя крышка, joseph, UnblvR 300
Фатима Реверс задняя панель 316
Намура Рюкзак Q7 375
Достойный RSA RSA домкрат 423
Генгол Goldwasser, RSA pcback, гиперреальность, UnblvR 450

Конечные биты

Вызов

  Текст, содержащий флаг, передается, пока
к сожалению, его головная и хвостовая части потеряны :(
  

Нам дан файл, содержащий двоичный файл.

Решение

Из описания задачи мы можем догадаться, что у предоставленных двоичных данных есть пара битов, удаленных с обоих концов. Однако не беспокойтесь, поскольку удаленные биты никак не повлияют на остальные данные.

Мы знаем, что некоторые биты были удалены, поэтому мы можем просто заменить их некоторыми ложными битами, а затем попытаться декодировать из двоичного кода, пока не получим читаемый текст.

  из импорта Crypto.Util.number *

flag = open ('output.txt', 'r').читать (). полоса ()

я = 0
в то время как True:
данные = long_to_bytes (int (флаг, 2) * 2 ** я)
если в данных b'CCTF:
печать (данные)
выход()
я + = 1
  

Вывод:

базовая единица информации в вычислительной технике и цифровой связи. Имя представляет собой набор двоичных цифр. [1] Бит представляет логическое состояние с одним из двух возможных значений. Эти значения обычно представлены как 0 или 1, но другие представления, такие как истина / ложь, да / нет, +/- или вкл / выкл, являются общими.Флаг — CCTF {it5_3n0u9h_jU5T_tO_sh2ft_M3}.
Соответствие между этими значениями и физическими состояниями нижележащего хранилища или устройства является условием, и разные назначения могут использоваться даже в одном и том же устройстве или программе. Это может быть физически реализовано с помощью двухканального

Флаг

CCTF {it5_3n0u9h_jU5T_tO_sh2ft_M3}


Амстердам

Вызов

Нормально ли иметь такую ​​кодировку?

  от Crypto.Импорт Util.number *
из functools import уменьшить
оператор импорта
из секретного флага импорта, n, k

def расческа (n, k):
если k> n:
возврат 0
к = мин (к, п - к)
u = уменьшить (operator.mul, диапазон (n, n - k, -1), 1)
d = уменьшить (operator.mul, диапазон (1, k + 1), 1)
вернуть u // d

def encrypt (msg, n, k):
msg = bytes_to_long (msg.encode ('utf-8'))
если msg> = comb (n, k):
возврат -1
m = ['1'] + ['0' для i в диапазоне (n - 1)]
для i в диапазоне (1, n + 1):
если msg> = comb (n - i, k):
m [i-1] = '1'
msg - = расческа (n - i, k)
к - = 1
м = int (''.присоединиться (м), 2)
i, z = 0, [0 для i в диапазоне (n - 1)]
с = 0
в то время как (m> 0):
если m% 4 == 1:
с + = 3 ** я
м - = 1
элиф м% 4 == 3:
с + = 2 * 3 ** я
т + = 1
m // = 2
я + = 1
вернуть c

enc = encrypt (флаг, n, k)
печать ('enc =', enc)

Enc = 55503328178762801622749998559973784796092358171334382935716776996508868023934797249230127125126798747281667412388943419480163599313755087009897203801700187625824503409897203801700187625624507309
  

Решение

Мы видим, что есть два шага к решению этой проблемы.Во-первых, мы должны получить значение $ m $ из результата шифрования. Затем мы вычисляем открытый текст из $ m $.

Первую часть можно сделать с помощью рекурсии. Разделив случаи на $ c \ pmod 3 $, мы можем найти, какой оператор if мы ввели на первой итерации while. Это также дает наше значение $ m \ pmod {4} $. Мы продолжаем это, пока не получим исходное значение $ c $.

  def recv (res):
    если res == 1:
        возврат 1
    если res% 3 == 0:
        return 2 * recv (res // 3)
    если res% 3 == 1:
        возврат 1 + 2 * recv (res // 3)
    если res% 3 == 2:
        возврат -1 + 2 * recv (res // 3)

## результат вычисления
m = 1303793107008238642

29808978789360

721418928977023070833

98578551447560972351036453899271623

9387482345515668380476074788749548946464

Теперь вычисляем открытый текст.Обратите внимание, что $ m $ изначально была битовой строкой, которая затем была преобразована в целое число. Поэтому мы начинаем с преобразования $ m $ в битовую строку.

  с = []
пока m> 0:
    s.append (м% 2)
    m // = 2
s = s [:: - 1]
n = len (s)
  

С помощью индукции можно доказать, что после успешного (не возвращающего $ -1 $) вызова encrypt () значение «msg» должно быть $ 0 $. Ключевая идея — треугольник Паскаля.
Если мы знаем значение $ k $ в конце encrypt (), мы можем реконструировать открытый текст, поскольку нам известен результат $ m $.Перебор всех возможностей для $ k $, и все готово.

Реализация

  def comb (n, k):
    если k> n:
        возврат 0
    к = мин (к, п - к)
    u = уменьшить (operator.mul, диапазон (n, n - k, -1), 1)
    d = уменьшить (operator.mul, диапазон (1, k + 1), 1)
    вернуть u // d

def recv (res):
    если res == 1:
        возврат 1
    если res% 3 == 0:
        return 2 * recv (res // 3)
    если res% 3 == 1:
        возврат 1 + 2 * recv (res // 3)
    если res% 3 == 2:
        возврат -1 + 2 * recv (res // 3)

## m = recv (прил.)
m = 1303793107008238642

29808978789360

721418928977023070833

98578551447560972351036453899271623

9387482345515668380476074788749548946464
s = []
пока m> 0:
с.добавить (m% 2)
m // = 2
s = s [:: - 1]
n = len (s)

ans = 0
для k в диапазоне (0, 400):
ans = 0
для i в диапазоне (0, n-1):
если s [n-1-i] == 1:
ans + = расческа (i, k)
к = к + 1
печать (long_to_bytes (ans))

Флаг

CCTF {With_Re3p3ct_for_Sch5lkwijk_dec3nt_Encoding!}


Игрок

Вызов

В этой задаче у нас есть доступ к серверу со следующими параметрами

  ++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++
+ Привет, между философией и азартными играми существует сильная связь! +
+ Играй как древний философ и найди флаг :) +
++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++
| Параметры:
| [C] ipher flag!
| [E] ncryption функция!
| [T] ry шифрование
| [Покидать
  

Где функция шифрования задается:

  def encrypt (m, p, a, b):
    утверждать m 

Решение

Цель состоит в том, чтобы расшифровать флаг, восстановив скрытые параметры $ a, b, p $ и затем решив полином, используемый в encrypt .3 + ax + b = c \ mod p \)

Реализация

  импорт ОС
os.environ ["PWNLIB_NOTERM"] = "Верно"
из импорта pwn *
из Crypto.Util.number import long_to_bytes

debug = False

r.recvuntil (b '| \ t [Q] uit \ n')

r.sendline ('C')
data = r.recvuntil (b '| \ t [Q] uit \ n')
enc = int (data.split () [3] .decode (). strip ())

def encrypt_int (n):
    r.sendline ('Т')
    r.recvuntil ('ваше сообщение для шифрования: \ n')
    r.sendline (str (n))
    data = r.recvuntil (b '| \ t [Q] uit \ n')
    b = int (data.split () [3].3 + a * x + b - прил.
rts = f.roots ()
печать (rts)

для root в rts:
    flag = корень [0]
    печать (long_to_bytes (флаг))

r.interactive ()
  

Флаг

CCTF {__ Gerolamo__Cardano_4N_itaLi4N_p0lYma7H}


Три вороны

Вызов

На дереве сидели три ворона, Даун, даун, сено, даун, Они были такими черными, какими могли быть.

  #! / Usr / bin / python

из импорта Crypto.Util.number *
из флага флаг импорта

def keygen (nbit):
    в то время как True:
        p, q, r = [getPrime (nbit) для _ в диапазоне (3)]
        если isPrime (p + q + r):
            pubkey = (p * q * r, p + q + r)
            Privkey = (p, q, r)
            вернуть pubkey, privkey

def encrypt (msg, pubkey):
    enc = pow (bytes_to_long (msg.encode ('utf-8')), 0x10001, pubkey [0] * pubkey [1])
    return enc

nbit = 512
pubkey, _ = генерация ключей (nbit)
печать ('pubkey =', pubkey)

enc = encrypt (флаг, ключ публикации)
печать ('enc =', enc)
  

Решение

Вызов шифрует флаг с модулем

\ [N = (p * q * r) * (p + q + r) \]

и дает результат $ n = pqr $, $ k = p + q + r $. Чтобы полностью взломать криптосистему, нам нужно найти значение модуля

\ [\ phi (N) = (p-1) (q-1) (r-1) (p + q + r - 1) \]

, но мы можем упростить это, когда зашифрованное сообщение $ m $ достаточно мало.{-1} \ mod \ phi (k) $, и решайте!

Заметим, что для любых $ n, l $, пока $ l | n $, любая эквивалентность $ a \ Equiv b \ pmod n $ также имеет место mod $ l $: $ a \ Equiv b \ pmod l $ (но обратите внимание, что обратное не обязательно). {1+ \ phi (k)} \ pmod k $, как если бы это была задача RSA с одним простым числом.И поскольку $ m

Реализация

  из импорта Crypto.Util.number *

k = 316784281198543784750399740721651367080372576240453326011585563628448080936367751923739925108415081379960494254845564354209680

9308777477807442821 с = 8218052282226011897229703

352121405425478527551188647686132806711749218377825052975130981587124725887204897098824178254447045826556754154241671286925464578318013

81010678126463222862469474571716187283412550120358711584979848384608553737740744439923176622174157561006450

8424995132578

308133333280111055

946336261022409777264026

7460721156592758697375592513776080542554621244272964238970513862354075367

0198753593504020114641665993551735683720877849740176380740521204428603298109322

79609273614197028789207955484171795079102810011784480605674925404666755777824
е = 0x10001

фи = k-1
d = pow (e, -1, phi)

флаг = pow (c, d, k)
печать (long_to_bytes (флаг))

Флаг

CCTF {th4_thr3E_r4V3n5_ThRe3_cR0w5}


Модель

Вызов

  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)
  

Решение

Ключом к решению этой задачи является то, что

\ [е \ эквив 2 Q ^ {- 1} Q - 1 \ эквив 2 - 1 \ эквив 1 \ pmod P \]

Итак, зашифровав сообщение m , мы имеем для некоторого целого числа $ k $

\ [m ^ e \ Equiv m ^ {1 + \ frac {k (q-1)} {2}} \ Equiv m \ cdot m ^ \ frac {k (q-1)} {2} \ pmod q \ ]

Рассматривая второй член, его можно уменьшить с помощью малой теоремы Ферма следующим образом:

\ [m ^ {\ frac {k * (q-1)} {2}} \ Equiv (m ^ {(q-1)}) ^ {\ frac {k} {2}} \ Equiv 1 ^ {\ гидроразрыв {к} {2}} \ эквив 1 ^ {\ гидроразрыв {1} {2}} \ pmod q \]

$ 1 $ может иметь здесь только два корня, а именно $ \ pm 1 $.e \ mp m \ Equiv 0 \ pmod q $ делится на $ q $.

Последний шаг, требующий внимания, заключается в том, что мы восстанавливаем $ q $, а не $ p $, что имеет значение для восстановления $ e $, поскольку простые числа здесь не взаимозаменяемы.

Реализация

  из импорта 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

2087747296822771164021634333019318423516471032884550719936264648930313876549202628497682839721770005885469950131270106
9850748706050896660281521826421577811533118718010597292033378006728085404811309462279999611838337634021778212294558626288745086362085621437525865936230074347122941073540018999235922055196144158063074002285730451489574517481352975876675873350653869693395028213098495559488151733

3877

06466633380921338845195921235252323721 flag_enc = 821634474333140
  • 05831776342200252705923796193752552649425282859227400617284746437075756157249953578189229459392338128783031841882560801175367779263048253787547952450480816724222285583987363793884961526545550108715847375346137865114137

    27506957702375732452598640804768960184186521954448243004125

    58942654500736501019422246293893

    8217359988866888133937177183763

    83679812248535071935556786120146664176700930317926014136576602368078825068852452899295285724380832277291

    73810885478353692596774819973451373878214205560

    507708169428542522843559753653510138036019639
    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 (м))

    Флаг

    CCTF {7He_mA1n_iD34_0f_pUb1iC_key_cryPto9raphy_iZ_tHa7_It_l3ts_y0u_puBli5h_4N_pUbL! C_k3y_wi7hOuT_c0_Ger0mi 907hOuT_c0_GeR0mi9


    Однострочное шифрование

    Вызов

    Профиль, взгляд, голос могут захватить сердце ♥ в кратчайшие сроки ».

    Нам дали этот очень короткий фрагмент:

      #! / 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  

    и вывод функции печати, состоящий из одного гигантского числа. Это типичное шифрование RSA, с небольшим отклонением: n не указывается!

    Решение

    Основной выбор для p и q идентичен. m составляет не более 2048 бит.

  • Когда мы получили небольшой пул значений-кандидатов, объединим два и два случайных значения из пула
  • Проверьте, составляет ли их продукт 2048 бит, и попробуйте расшифровать зашифрованный текст.
  • Реализация

      #! / 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 = 132071684 6529569994065968467674726141275170450106550

    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), (1453387
    8401025088546508817953211392597

    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, 84661620325416
    48714620324777288157484807522832537271896727, 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, 225134760840647758387627669216228088
    72229705782250944073182, 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

    662270

    6483668950238588764594692681480769707324016554574698948603027409300338968573544143950532532532634474498533821603163396485 г: 120671750615350567408663286141792380110847038079359421702223325943240746

    8452931825405156276243520869293655223677329

    40374796315241454965 р: 68051654200085157207332136111040326067798514

    40942748721163833107639364882355808718200151519497304188154695981671131677635619224129781969654824622

    7674305201415050592661606881387625228654411615892410789722236619387260438451167443951095682870377511504228417125095204183240940265601 д: 9374271128197012368737527412500899400608329381824894

    93069509248449466340860308831673133

    398872454947439751830651967183020585597436856749771552385894803
    672

    745178525979884494517698946787612883007
    276087925574561383623033220640342314238570313761147

    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

    745178525979884494517698946787612883007
    276087925574561383623033220640342314238570313761147

    8776114

    4468505970527
    у = 62555029861163892280349841392428573747807

    304260235834031195878428382500216962419282794089213188350667672807684260421645876440307096244625059736661128077243622373777

    664558475346725148637679179

    21827556754971529567337828995831821656338281687895303874971235130850309582018888576967

    04573014978038017951327113259714077403045870976500229355564735315227227

    78

    22720079488985396486582320273126185467503019480961873778316616850146500551181

    205003734702444247745395809759638757742466287334983047217540475
    1943863479573235864782496267138830878462336954417976083797888 утверждать 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 лет.
    • Тай Дуонг и Джулиано Риццо - крестные отцы практического криптографического программного обеспечения.
      безопасность.Некоторые вещи в этом испытании не имели для нас смысла до тех пор, пока
      Джулиано использовал их в распространенном программном обеспечении.
    Юридический

    Отдельные материалы упражнений принадлежат их автору и могут распространяться или не распространяться по лицензии с открытым исходным кодом.

    .

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    2021 © Все права защищены. Карта сайта