Я здесь только собрал чужие цветы,

А от меня самого – только нитка, которой они связаны.

Мишель де Монтень из эссе «О тщеславии» (в переводе Н.Я.Рыковой)

Известно, что антология – собрание литературных текстов сравнительно небольшого объёма, созданных как одним, так и несколькими авторами. А если дословно, то это «собрание цветов» или «букет», от греческого anthos, означающего «цветок», и logia, производного от legein, означающего «собрание». В Древней Греции так образно именовали собрания стихотворений разных авторов. Действительно, тут «цветы» — это лишь метафора подборки образцов чего-либо, не всегда связанного с поэзией, составленного чаще всего одним человеком и неизбежно отражающего его вкусы. Поэтому CTF-задачи в нижеследующем тексте всего лишь выбор составителя и не более.

Задачка с Offzone 2025 натолкнула на мысль составить свой маленький букет «этюдов» на тему «partial PEM private key» (закрытый ключ с неполной информацией в формате PEM-файла). Будем рассматривать закрытые ключи популярной криптосистемы RSA, про которую и не грех вспомнить.

Обратите внимание, на вычисление закрытой экспоненты D. В природе встречается несколько методов:

• Через функцию Эйлера Phi = (P-1)*(Q-1), её любят давать учителя на уроках по крипте.

• Через НОК (наименьшее общее кратное) lcm(P-1, Q-1), любимицу математиков, поскольку она дает наименьший рабочий положительный результат D (всё-таки D – это показатель степени в процедурах шифрования/расшифрования и чем меньше размер D в битах, тем меньше вычислительная нагрузка при возведении в степень). Применение НОК ещё встретится в тексте:

• Через НОК на «минималках» (P-1) * (Q-1) / 2. Просто позволяет избежать вычисления операций gcd (НОД — наибольший общий делитель) — небольшое повышение производительности.

Сам PEM (Privacy-Enhanced Mail) — это де факто формат файла для хранения криптографических данных, таких как сертификаты или ключи. Слово «почта» в названии означает, что содержимое файла текстовое в кодировке Base64 с читаемыми верхними и нижними колонтитулами: например, «-----BEGIN RSA PRIVATE KEY-----» и «-----END RSA PRIVATE KEY-----». Формату PEM посвящено несколько документов RFC под общим заголовком «Privacy Enhancement for Internet Electronic Mail»:

• rfc1421 = «Part I: Message Encryption and Authentication Procedures»

• rfc1422 = «Part II: Certificate-Based Key Management»

• rfc1423 = «Part III: Algorithms, Modes, and Identifiers»

• rfc1424 = «Part IV: Key Certification and Related Services»

Нас интересуют задачи, когда в файле PEM передается частично «порезанный» закрытый ключ RSA. Рассмотрим конкретный пример с прошедшего Offzone 2025  из вселенной CUB_3. Файлы к заданию — тут.

Входными данными являются картинка PEM-файла с закрытым ключом private_key_pem.png, скрипт для шифрования файлов file_protector.py и зашифрованный Page1.png.enc. PEM-файл не полный, часть данных отсутствует, состоит их трех блоков читабельных символов. Задача — восстановить PEM-файл, а затем расшифровать Page1.png.enc. На рисунке видно, что между колонтитулами «-----BEGIN» и «-----END» лежит «encapsulated text portion» в терминах PEM в кодировке Base64, где часть данных просто вырезана. К восстановлению утраченной части данных и относится категория CTF-задач «partial PEM private key».

Понятно, что PEM-файл всего лишь обертка из кодировки Base64 и захардкоженных колонтитулов. А что скрывает Base64? А там сериализованные по правилам DER (Distinguished Encoding Rules) двоичные данные, представляющие собой структуру, написанную на языке ASN.1 (Abstract Syntax Notation One). Рассмотрим первый блок данных PEM-файла из задания.

Структуру RSAPrivateKey, описывающую параметры закрытого ключа алгоритма RSA, можно найти в rfc3447 (Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1, пункт A.1.2). Она включает в себя как открытые параметры алгоритма: modulus — N, publicExponent — E, так и закрытые: privateExponent — D, prime1 — P, prime2 — Q. К ним же добавляется пара exponent1 и exponent2 — это просто запись закрытого ключа D в другой форме: Dp = D mod (P-1) и Dq = D mod (Q-1), а также coefficient – инверсия множителя InvQ = Q^(-1) mod P. Перечисленные Dp, Dq, InvQ применяют в варианте алгоритма RSA, основанного на китайской теореме об остатках (Chinese Reminder Theorem) – CRT-RSA. Его задача состоит просто в ускорении выполнения операций возведения в степень (замена вычислений с «длинным» ключом D на более короткие Dp и Dq, актуально для смарткарт). Есть еще в структуре RSAPrivateKey опциональное поле otherPrimeInfos, но оно не добавляется, когда значение поля Version = 0 (наш случай). В сериализованном виде поля RSAPrivateKey следуют друг за другом в соответствии с описанием структуры. Как устроена сериализация сущностей языка ASN.1 с помощью правил кодирования DER можно посмотреть тут. Возьмем первый блок данных из предоставленного PEM-файла. На рисунке видно, что, сняв Base64, нам доступны параметры N, E, а вот от параметра D остались только старшие биты (0x20A81E95…). Печально, именно он применяется при расшифровании. Тогда рассмотрим следующий блок данных.

Второй блок дал еще одно число. По структуре RSAPrivateKey это один из простых множителей: либо P, либо Q размером 0x80 байт (1024 бита). Пусть будет P. Тогда найдем Q = N / P и убеждаемся, что остаток от деления нулевой N mod Q = 0. Получаем:

N = 23515222943674849297874515495212530647591613085719842750956688127019499352474954307021949294776248031462809389319802881279937186213376124727170040098877115173080057635197844521044847499476721622967596327170669454744422266651568195943345486158729039622143993725361492281152411334582253366186456678668591820397155333314921268660807067682384577555880417419436396209624795437778767080908009586460890727838203635496016893432496560372587498817018644055422924445370440215205159485349856558069583011361038882865269517125858449022008443492759653487410585623230180235205803038963567089733351713824596599397514264514846706591761
P = 132607607504562545878121909151776274742674812857779419856390121428487910930920933559130088463469442395856661884417274322147214524802543356072389776356928828870509420537533379672271172130282090852796765788752916173175899842938433426819959197934812737300492337215487614359932570347099764904892741375434423140527
Q = 177329365834956157630053495817220347650116105227209826948309091478273630236853230316150966092193594369808433803625254147002082542759984796524142488078507163048895356083703822239082101746651433792960002583403652760028411604228600803156935471584150085956738722242671349775098976506628679892542542752532516033343

Осталось найти privateExponent – D. Делаем по канону.

• Считаем значение функции Эйлера Phi = (P-1) * (Q-1)

• Вычисляем закрытый ключ D = E^(-1) mod Phi (в питоне D = pow(E, -1, Phi) или через расширенный алгоритм Евклида)

D = 15880140028398637109195268425272993597526734698686067419501062043206570370048011470164600636101853691448815447037792940166432091603698682090652480807728510052797308250584955106465093926054606490826554133511138574058602631757100648733701337052550922922880950826205791009341950666736978645355756285525955365474824657083566917765691660808609774340514447925550613689373816603146088792252061268181239802251227273427345009148634306483091504539839003580073705924040182140076307000608987830765078226369402550377331816139605685474927037796570458566847739356841952793353676528815025906323610387259054927541545928467316550137801

Осталось собрать найденные параметры в одну структуру RSAPrivateKey, пройтись Base64, добавить колонтитулы и получить готовый PEM-файл.

import struct, base64
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.number import inverse

N = 23515222943674849297874515495212530647591613085719842750956688127019499352474954307021949294776248031462809389319802881279937186213376124727170040098877115173080057635197844521044847499476721622967596327170669454744422266651568195943345486158729039622143993725361492281152411334582253366186456678668591820397155333314921268660807067682384577555880417419436396209624795437778767080908009586460890727838203635496016893432496560372587498817018644055422924445370440215205159485349856558069583011361038882865269517125858449022008443492759653487410585623230180235205803038963567089733351713824596599397514264514846706591761
p = 132607607504562545878121909151776274742674812857779419856390121428487910930920933559130088463469442395856661884417274322147214524802543356072389776356928828870509420537533379672271172130282090852796765788752916173175899842938433426819959197934812737300492337215487614359932570347099764904892741375434423140527
q = N // p
e = 65537
d = inverse(e, (p-1) * (q-1))
res = bytes.fromhex("0201000282010100") # add Version (int) = 0
res += long_to_bytes(N)                 # add Modulus         N=23515222943...
res += bytes.fromhex("0203010001")      # add publicExponent  E=65537
res += bytes.fromhex("02820100")        # add privateExponent D=15880140028...
res += long_to_bytes(d)
res += bytes.fromhex("02818100")        # add prime1          P=13260760750...
res += long_to_bytes(p)
res += bytes.fromhex("02818100")        # add prime2          Q=17732936583...
res += long_to_bytes(q)
res += bytes.fromhex("02818100")        # exponent1           D % (P-1)
res += long_to_bytes(d % (p-1))
res += bytes.fromhex("02818100")        # exponent2           D % (Q-1)
res += long_to_bytes(d % (q-1))
res += bytes.fromhex("02818100")        # coefficient         Q^(-1) % P
res += long_to_bytes(pow(q, -1, p))
res = b'\x30\x82' + struct.pack(">H", len(res)) + res # add SEQUENCE + length
res_b64 = base64.b64encode(res)         # to base64
res_b64 = b'-----BEGIN RSA PRIVATE KEY-----\n' + res_b64 + b'\n-----END RSA PRIVATE KEY-----'
open("public_temp.pem", "wb").write(res_b64)

С помощью скрипта собираем все параметры в PEM-файл. Теперь полученный файл можно загрузить в любой онлайновый парсер. Например, в ASN.1 java script decoder.

Последний шаг — расшифровать картинку Page1.png.enc.

Представленная задача оказалась несложной: доступны все биты модуля N и все биты одного из простых множителей. А, нет, была одна сложность ?. Надо было набрать base64 символы с картинки в текстовой файл руками. И желательно без ошибок.

Хотя слишком поздно вспомнил. С задачей вытащить символы из картинки неплохо справляется ChatGPT. Плюс ему в карму.

Имея представление о том, как выглядит категория задач «partial PEM private key», я собрал небольшую антологию, посвященной этой теме. Временной отрезок — последняя пятилетка, начало ревущих 20-х. Сразу скажу, что задачи я условно разбиваю на два типа (далее по тексту I и II). Когда известны некоторые компоненты структуры RSAPrivateKey в полном объеме бит — I‑тип. И когда компоненты «испорчены» — известны только старшие биты, младшие или посередке — II‑тип.

I.A Случай из жизни «Recovering a full PEM Private Key when half of it is redacted»

Оригинал решения смотрим тут.

Во времена, когда твиттер еще был твиттером, пользователь SAXX сообщил о найденном закрытом ключе в ходе пентеста, приложив скриншот PEM-файла, с отредактированными 31 из 51 строками. Какая часть информации была доступна: примерно 2000 бит модуля N (из 4096 бит), последние биты простого множителя P (RSAPrivateKey.prime1), все биты простого множителя Q (RSAPrivateKey.prime2) и экспоненты Dp (RSAPrivateKey.exponent1). Хотя открытая экспонента E отсутствует, это не беда. Три наиболее частых варианта значения E: 3 (0x3), 17 (0x11), 65537 (0x10001). К слову, во всех задач, представленных в этой статье Е = 65537 (0x10001). Итак, сделав предположение об открытой экспоненте E (RSAPrivateKey.publicExponent), энтузиасты довольно быстро восстановили ключ. Само решение подобных проблем, когда известны Q и Dp, или P и Dq, или Dp и Dq рассмотрим в следующих паре примеров.

I.B RSA Encryption Key Recovery

Оригинал решения смотрим тут.

В задаче предоставлялся отредактированный PEM-файл. Тут уже ключевой информации вырезано больше. Неизвестен ни открытый ключ (N, E), ни закрытый (D), ни множители (P, Q), а только известны поля exponent1 Dp и exponent2 Dq, необходимые для алгоритма CRT. Думаете, это тупик. Оказывается, такой вариант уже рассматривался в работе Matthew Campagna, Amit Sethi «Key Recovery Method for CRT Implementation of RSA». Перед вычислениями тоже необходимо сделать предположение о значении E = 65537. Тогда схема нахождения простого множителя P, следующая:

Левую часть уравнения считаем, Dp и E нам известны (помним, что E предположили равным 65537). Тогда в правой части уравнения достаточно перебрать коэффициент Kp в диапазоне 3 <= Kp < E, чтобы найти простой множитель P.

Аналогично выглядит схема нахождения простого множителя Q:

И снова перебираем коэффициент Kq в диапазоне 3 <= Kq < E, чтобы найти простой множитель Q. Далее считаем N = P * Q, а затем D через расширенный алгоритм дядюшки Евклида.

Сразу приведу похожую задачу: Information Paradox - Space Heroes CTF 2022.

Здесь известны все биты Q и Dp. Снова делаем предположение, что E = 65537, затем восстанавливаем множитель P через уже знакомую формулу Dp * E – 1 = Kp * (P-1), находим N = P * Q и D.

Задач I-типа достаточно встречается в CTF-среде, давайте посмотрим на то, что посложнее.

II.A Key-Recovery – UMD CTF 2024

Оригинал решения смотрим тут.

Вот такой экзотический вариант PEM-файла предоставлен в задании. В наличии все элементы структуры RSAPrivateKey, но разной степени «испорченности». На рисунке красным цветом — показаны «отсутствующие» части, голубым — целые биты модуля N, жёлтым — E, оранжевым — множителя P, фиолетовым — множителя Q.

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

Функция Эйлера Phi = (P-1) * (Q-1) — это стандартное вычисление в системе RSA

Но также работает и следующее Phi = lcm(P-1, Q-1), где lcm = НОК, наименьшее общее кратное. Выражение lcm(P-1, Q-1) еще называют функцией Кармайкла. Про это выражение упоминают сами авторы RSA в своей работе «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems», пункт IX.C.

А как можно выразить НОК? С помощью другого известного факта про произведение двух чисел:

Т.к. P и Q — простые нечетные числа, то (P-1) и (Q-1) — четные числа. Следовательно, gcd(P-1, Q-1) = 2*z (общий делитель точно будет состоять из множителя 2 и некоего множителя z). Получим:

Теперь рассмотрим основное уравнение RSA.

Автор использует это уравнение снова и снова для нахождения недостающих бит N, D, P или Q, двигаясь от младших бит к старшим. Значения коэффициентов k и z ищем перебором. Коэффициент k лежит в диапазоне k < E, а для коэффициента z выбираем малый диапазон 1 <= z < 100. Ниже представлен один из найденных фрагментов, младшие биты модуля N.

Само финальное уравнение автор предлагает решить либо с помощью функции solve_mod (медленно), либо через 2-адический полином (быстрее) фреймворка Sage. На рисунке показан уже найденный один из фрагментов для модуля N при k = 33411 и z = 5. Т.е. «утерянные» биты N = …e693fffffffffffffff1adeaf833a09 стали …e6932b4f5ddbbd6d5e41adeaf833a09 (ссылка на скрипт Sage Cell).

Для любознательных читателей — доступен другой вариант решения от самих организаторов UMDCTF 2024 «key-recovery» с восстановлением от старших бит к младшим, с использованием решётки и LLL-базиса (приведенного по алгоритму Ленстре—Ленстре—Ловасу). Как раз с этой решёткой встретимся в следующей задаче.

II.B Bro-Key-n — UIUCTF 2022

Оригинал решения смотрим тут.

Полные биты в наличии только у модуля N и экспоненты E, остальные компоненты либо отсутствуют, либо «подпорчены». Больше всего известных бит у экспоненты Dp, примерно 75% от общего числа бит. Автор восстанавливает недостающие компоненты с помощью N, E и неполного Dp.

Тут же автор упоминает работу, часто цитируемую в подобных задачах. В 2020 году  Gabrielle De Micheli и Nadia Heninger собрали известные техники по восстановлению закрытого ключа на основе частичной информации в работе «Recovering cryptographic keys from partial information, by example».

На рисунке выделил красным данный случай: известны старшие биты Dp = D mod (P-1). Повторим последовательность действий из пункта 4.2.7 статьи. Пусть a — это число Dp, где вместо неизвестных бит стоят нули:

a = 0x0C55ACB5A46475E4FCB3FC012A26F3B896BC34F7F047035C610D3739B98CE50A146EC49127E5E8667352E06DAC2BFA37224A47C29CD904B9E418BF4F8484F60594906CCEDAC2257DE1CDC54453BA892D1E1A00FE8FC7E1B415DFE4C5055BCAB0AF08A335A6D9A934FA98644D884794621738F8783EEB975A8468134811D36CD9544C9AC47086BA8865C81155BCDC39FE5C1376A07A59934FF25E18554517E462927C6F85571249C3CA82C7DD8691707186DE2EA6CB69CED941C6F5F90CFB5D0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Пусть r — это число из неизвестных бит. Тогда Dp = a + r. Количество неизвестных бит равно 2044 — 1528 = 516 бит. Максимально возможное значение из неизвестных бит обозначим R = 2⁵¹⁶.

Также добавим новую переменную InvE = E^(-1) mod N – мультипликативное обратное значение экспоненты E по модулю N. Отсюда, InvE * E = 1 mod N, следовательно InvE * E = 1 mod P и InvE * E = 1 mod Q. Это простое свойство модульной арифметики. Если число делится на N, то оно делится и на все делители N, включая P и Q.

А теперь начинаем преобразовывать:

Это простое линейное уравнение с одной переменной r (по модулю P). Нам известно a, InvE, и факт того, что Kp < E . Значение P — неизвестно. Однако, известно, что N ≡ 0 mod P (N сравнимо c 0 по модулю P). Оказывается, этого факта достаточно, чтобы преобразовать задачу в задачу о кратчайшем векторе (SVP) в решётке 3x3, а затем решить квадратное уравнение.

В пунктах 4.2.1 / 4.2.2 статьи описана конструкция решётки для решения этой задачи, а также объясняется, почему она работает. Конструкцию решётки 3x3 и уравнение вытащил отдельно на картинку выше.

Код алгоритма автора я перенёс на платформу CoCalc для уже найденного коэффициента Kp = 21128. Код находит множители P и Q, что позволяет затем найти значение закрытой экспоненты D.

Итого, задачи по восстановлению ключа с частично известными битами являются интересными и сложными. Универсального ответа на вопрос «могу ли я, зная частичную информацию о ключе, восстановить его» не существует. Всё зависит от конкретного алгоритма и характера восстанавливаемой информации.

Эпилог

«Я надеюсь, что потомки благосклонно отнесутся ко мне не только за то, что я объяснял, но и за то, что я намеренно пропустил, дабы удовольствие открытия досталось другим».

Рене Декарт (1596 — 1650), Геометрия

Цитата взята из последнего предложения книги Рене Декарта La Géométrie («Геометрия»), впервые опубликованной в 1637 году. Дружище Рене признаёт, что его знания не всеобъемлющи и он не может знать всего, оставляя место для других точек зрения и интерпретаций. Я полностью с ним согласен. Я беру на себя ответственность за все прокравшиеся в текст ошибки, и заранее приношу свои извинения. На этом сию антологию завершаю.

И памятуя Джонни Донна, английского поэта и проповедника — «Человек — не остров в море, Он — лишь часть материка» хочу поблагодарить моих внезапных читателей Мишгана, Антоныча, Шефа за правки и советы.

И напутствие. Играйте в CTF– игры разума на околокомпьютерные темы. Играйте и обрящете.