@BFG29 Sep 21 at 20:55

Истории о «partial PEM»

Medium

12 min

8.3K

CTF * Reverse engineering *

Review

Comments 12

@Melirius Sep 22 at 08:39

Хабр торт!

@BFG29 Sep 22 at 11:05

В данном конкретном случае к заданию прилагался file_protector.py (в статье есть ссылка, где можно его скачать). Там была вся логика для шифрования файлов (AES CBC) и создания enc-файлов (там хранили шифрованный aes ключ, для шифрования которого использовали RSA с заданным ключом в PEM-файле).

@thereisnocolor Sep 23 at 04:50

Очень полезная и позновательная статья, однако не могли бы вы объяснить логику расшифровки изображения? У нас есть приватный ключ, который зашифрованно изображение, но как понять по какому алгоритму? Ведь там может быть все что угодно, от RAW шифрования блоков до XOR и другой матепатики с перестановками и сдвигами. Хотелось бы понять как вы рассуждали, решая данное задание и почему именно так, а не иначе.

@kulik_alex Oct 20 at 05:53

Спасибо за статью. Начитался, пощёл beginner's quest решать.

Как ты Crypto установил? а то у меня не здоровая ситуация, что я вручную файл перегоняю в число при рабочем решении.

@BFG29 Oct 22 at 14:33

Типа так. "pip install pycryptodome"

@kulik_alex Oct 22 at 17:32

На винде? В debian pip пошлёт в apt там непишет python3-pycryptodome is already the newest version в python3 ModuleNotFoundError: No module named 'Crypto'. С учётом того что на сайте написанно что поддержка закончилась и советуют использовать cryptography тут уже смысла нет.

@BFG29 Oct 22 at 19:29

Да, на винде. Проект pycryptodome жив. Последняя версия, кажется, в мае выходила. pycryptodome был форком pycrypto. Так и продолжают называть основной модуль Crypto.

@kulik_alex Oct 22 at 19:39

Я про оригинальный https://www.pycrypto.org/

@kulik_alex Oct 20 at 07:42

Откуда взялась матрица

$B=\begin{bmatrix}R^2&Ra&0\\0&R&a\\0&0&N\end{bmatrix}$

@BFG29 Oct 22 at 20:59

Матрица описана в статье «Recovering cryptographic keys from partial information, by example» (ссылка в тексте есть), в пункте 4.2.1 на стр.11-12 объясняется, почему она работает. Каждая строка в матрице - это вектор с заданными коэффициентами. Одна из задач - построить решетку (матрицу) с правильными коэффициентами (в модульной математике ими будут большие числа). Глядишь, при упрощении (редукции) этих векторов найдется базовый вектор, у которого размер коэффициентов значительно меньше.

@kulik_alex Oct 23 at 12:13

Метод Копперсмита я приблизительно понял. Howgrave-Graham пока непонял. Откуда взялись многочлены ?

И у sage внутри матрица 7х7 высчитывается.

тут матрица 4х4

@BFG29 Oct 25 at 14:15

Решетка строится на базе многочлена. Минимальный размер решетки в методе Копперсмита обычно равен степени многочлена плюс один (d+1), чтобы успешно найти корни многочлена по заданному модулю. Слишком маленькая решетка не даст результата, а слишком большая может быть вычислительно неэффективной. В примере по ссылке F(x) = x^3 + 10x +5000x - 222. Выполняется условие ≡ 0 mod 10001. Степень многочлена = 3, значит, размер решетки будет 4х4, в которой каждый вектор (каждая строка матрицы) удовлетворяет условию ≡ 0 mod 10001.
В задаче, что в статье тоже есть многочлен F(r) = ar^2+br+c, где 0 < r < R. Степень многочлена = 2, размер решетки будет 3х3. У нас есть уравнение A+r ≡ 0 mod P (само r не знаем, поэтому вместо него берем максимально возможное R) и N ≡ 0 mod P. Строим вектора, у них должно выполняться условие ≡ (сравнимо с 0) по модулю P. Вектора: (0 0 N) для нулевой степени, (0 R A) для 1-й степени, (R^2 A*R 0) для 2-й степени. Последний вектор получается из R * (A+R). В учебниках звучит так, ячейки в решетке выбираются таким образом, чтобы сбалансировать вклады разных выражений, и обеспечить уменьшение чисел.