Binary basics#
Подготовлено: rasti
Автор задания: rasti
Уровень сложности: Легко
Описание#
- В глубинах старого склепа загадочная головоломка охраняла могущественную реликвию. Многие пытались взломать её код, но никому это не удалось. На этот раз отважный криптограф обнаружил бледную надпись на стене, казавшуюся бессмысленной, о парах и тенях двоих. Погружаясь в шифр, он понял смысл намёка, который вел его через лабиринт чисел. Но когда раскрылась последняя тайна, криптой прокатился низкий шепот: «Некоторые вещи лучше оставить во тьме» Реликвия была обнажена, но проклятие только начинало действовать.
В таске дано два файла:
source.py: шифрует секретное сообщениеoutput.txt: содержит RSA параметры, зашифрованный флаг и подсказку
Анализ исходного кода#
from Crypto.Util.number import getPrime, bytes_to_long
from math import prod
FLAG = open('flag.txt', 'rb').read()
primes = [getPrime(128) for _ in range(16)]
n = prod(primes)
e = 0x10001
m = bytes_to_long(FLAG)
c = pow(m, e, n)
treat = sum([primes[i]*2**(0x1337-158*(2*i+1)) for i in range(16)])
with open('output.txt', 'w') as f:
f.write(f'{n = }\n')
f.write(f'{e = }\n')
f.write(f'{c = }\n')
f.write(f'{treat = }\n')Как обычно флаг прочтен из flag.txt и зашифрован через RSA. Публичная экспонента равна стандартному значению 0x10001 = 65537 и публичный ключ RSA вместе с зашифрованным флагом записаны в файл. Более того, вычисляется странная подсказка на основе 16 простых чисел и записывается в файл.
Решение#
Начнём с анализа модуля. Этот модуль нестандартен: он состоит из 16 простых чисел по 128 бит, поэтому имеет длину 2048 бит и практически не поддаётся факторизации. Единственная оставшаяся для обработки информация это значение подсказки treat.
Для краткости обозначим простые RSA как $p_0, p_1, …, p_{15}$. Подсказка может быть выражена как:
$$ \text{hint} = 2^{4761} p_0 + 2^{4445}p_1 + 2^{4129}p_2 + ... + 2^{21}p_{15} $$Нам дано линейное сочетание тех самых простых с коэффициентами убывающими степенями двойки. Это намекает, что стоит мыслить в двоичной системе, а не в десятичной. Можно попытаться представить hint в двоичном виде и заметить закономерности, но мы разберём процесс пошагово. Возьмём произвольное число, умножим его на большую степень двойки и посмотрим на двоичный вид результата.
>>> a = 0xdead
>>> bin(a)
'0b1101111010101101'
>>> bin(2**60 * a)
'0b1101111010101101000000000000000000000000000000000000000000000000000000000000'Можно заметить, что число $a$ осталось по сути таким же, но добавлены нули, следовательно создается некоторое пустое пространство. Тоже самое бы произошло при левом сдвиге на 60 бит.
>>> bin(a << 60)
'0b1101111010101101000000000000000000000000000000000000000000000000000000000000'Теперь добавим еще одно случайное число через $2^{32} \cdot a$.
>>> b = 0xbeef
>>> bin(b)
'0b1011111011101111'
>>> bin(2**60 * a + b)
'0b1101111010101101000000000000000000000000000000000000000000001011111011101111'И также $b$ осталось как есть, но было добавлено в конец большого числа. Теперь повторим путь расчета подсказки, через умножение $b$ на большую степень от 2, но меньше чем 60.
>>> bin(2**60*a+2**27*b)
'0b1101111010101101000000000000000001011111011101111000000000000000000000000000'В бинарном виде это работает так $$ 2^{60} \cdot a = 1101111010101101000000000000000000000000000000000000000000000000000000000000\ 2^{27} \cdot b = 0000000000000000000000000000000001011111011101111000000000000000000000000000\
\text{hint} = 1101111010101101000000000000000001011111011101111000000000000000000000000000 $$
Верхняя часть $60-27 = 33$ бит от $b$ это $0$ , следовательно значение $a$ остается таким же после сложения. В этом таске мы знаем только значение $\text{hint}$ , выражая его в бинарном виде будет просто различить $a,b$ по нулям между ними.
0b1100010011000010000101100101001011100001110110100000111100100000001101110010101110000010100001111100001000011001101110110001010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101101111011111011010010010101111111110110101111101100101011111111000000100100000110101010000110010000110100111000110010000110010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ... <REDACTED> ... 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110000010110100001100010000011100000001011011110011001110101011100101000101100110000001101101111011011101001110011011000010110010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001111111000001111001001001100010010010010010101011011000111010000100000101111101000111011111111000101011100111100010110000101000000000000000000000Тогда простые из 128 бит и можно различить по множеству нулей их отдельно, например первые два:
p_0 = 11000100110000100001011001010010111000011101101000001111001000000011011100101011100000101000011111000010000110011011101100010101
p_1 = 10110111101111101101001001010111111111011010111110110010101111111100000010010000011010101000011001000011010011100011001000011001Так как они простые, они должны оканчиваться всегда на бит $1$. Чтобы извлечь все простые, мы можем начинать либо с самого старшего бита (MSB), либо с самого младшего (LSB). Чтобы не усложнять процесс большими правыми сдвигами и операциями AND, начнём с LSB. Суть идеи:
- Начать с младшего бита и выполнять правый сдвиг на 1 бит, пока младший бит не станет равен 1.
- В этом случае найдено простое число, извлечь последние 128 бит и добавить в список простых. Последние 128 бит hint можно получить либо как $\text{hint}\ &\ (2^{128}-1)$, либо $\text{hint} \pmod {2^{128}}$.
- Удалить последние 128 бит из hint, сдвинув вправо на 128 бит, и обратно к шагу 1 до тех пор, пока hint не станет равен 0.
Выполним первую итерацию вручную. Последние биты hint таковы:
111111000001111001001001100010010010010010101011011000111010000100000101111101000111011111111000101011100111100010110000101000000000000000000000
Remove LSB :
11111100000111100100100110001001001001001010101101100011101000010000010111110100011101111111100010101110011110001011000010100000000000000000000
Remove LSB : 1111110000011110010010011000100100100100101010110110001110100001000001011111010001110111111110001010111001111000101100001010000000000000000000
Remove LSB :
111111000001111001001001100010010010010010101011011000111010000100000101111101000111011111111000101011100111100010110000101000000000000000000
Remove LSB :
11111100000111100100100110001001001001001010101101100011101000010000010111110100011101111111100010101110011110001011000010100000000000000000
.
.
.
Remove LSB :
11111100000111100100100110001001001001001010101101100011101000010000010111110100011101111111100010101110011110001011000010100
Remove LSB :
1111110000011110010010011000100100100100101010110110001110100001000001011111010001110111111110001010111001111000101100001010
Remove LSB :
111111000001111001001001100010010010010010101011011000111010000100000101111101000111011111111000101011100111100010110000101
[+] Prime found :
111111000001111001001001100010010010010010101011011000111010000100000101111101000111011111111000101011100111100010110000101
// ... и так далее извлекать 128 bits ...Автоматизируем через скрипт
def extract_primes(hint):
primes = []
while hint:
hint >>= 1
if hint % 2 == 1:
primes.append(hint & (2**128-1))
hint >>= 128
return primesИмея все простые можно расшифровать RSA, например через эту функцию
from math import prod
def decrypt(n, e, c, primes):
assert n == prod(primes) # n = p1 * q1 * ...
phi = prod([p-1 for p in primes])
d = pow(e, -1, phi)
m = pow(c, d, n)
return long_to_bytes(m)Получение флага:
def pwn():
primes = extract_primes(treat)
flag = decrypt(n, e, c, primes)
print(flag.decode())
if __name__ == '__main__':
pwn()