Весёлый RSA Writeup

Ссылка на таск Codeby:

https://codeby.games/categories/cryptography/bc2d6cee-6f45-4ef8-aa14-f6df8c9ffc0a

Описание задания §

Боб шифрует для трех сторон одно и то же сообщение с помощью RSA. Узнайте сообщение, отправленное Бобом. В флаге укажите SHA256 от сообщения.

Решение §

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

Описание работы кода §

1. Импортирование необходимых библиотек:

   • mod_inverse из библиотеки sympy для нахождения обратного по модулю числа.
   • factorint из библиотеки sympy.ntheory для разложения числа на простые множители.

2. Инициализация данных:

   • Заданы три набора данных, каждый из которых содержит модуль ( n ), экспоненту ( e ) и шифртекст ( C ).

3. Функция factorize:

   • Принимает модуль ( n ) и возвращает список его простых множителей.
   • Например, для ( n = 59911 ) множители будут ( p ) и ( q ) (два простых числа, произведение которых дает 59911).

4. Функция compute_phi:

   • Вычисляет phi на основе разложения на простые множители.
   • Использует формулу простые множители

5. Функция find_private_exponent:

   • Вычисляет (\phi(n)) для заданного ( n ).
   • Пытается найти закрытую экспоненту ( d ) как обратную по модулю (\phi(n)) к открытому ключу ( e ).
   • Если обратное число не существует, возвращает None.

6. Функция decrypt_message:

   • Принимает шифртекст ( C ), закрытую экспоненту ( d ) и модуль ( n ).
   • Возвращает расшифрованное сообщение, вычисленное как ( C^d \mod n ).

7. Основной цикл:

   • Перебирает все три набора данных.
   • Для каждого набора пытается найти закрытую экспоненту ( d ).
   • Если закрытая экспонента найдена, расшифровывает сообщение и выводит его.

from sympy import mod_inverse
from hashlib import sha256
from sympy.ntheory import factorint
 
# Даны модули n1, n2, n3 и соответствующие им экспоненты e1, e2, e3 и шифртексты C1, C2, C3
e1, n1, C1 = 5, 59911, 7721
e2, n2, C2 = 7, 363241, 244800
e3, n3, C3 = 13, 470369, 76794
 
# Функция для разложения модуля на множители
def factorize(n):
    return list(factorint(n).keys())
 
# Расчет phi(n)
def compute_phi(n):
    factors = factorize(n)
    phi = 1
    for f in factors:
        phi *= (f - 1)
    return phi
 
# Попробуем найти d для каждого набора (e, n)
def find_private_exponent(e, n):
    phi = compute_phi(n)
    try:
        d = mod_inverse(e, phi)
        return d
    except ValueError:
        return None
 
# Расшифровка шифртекста
def decrypt_message(c, d, n):
    return pow(c, d, n)
 
# Данные для расшифровки
moduli = [n1, n2, n3]
exponents = [e1, e2, e3]
ciphertexts = [C1, C2, C3]
 
for i in range(3):
    d = find_private_exponent(exponents[i], moduli[i])
    if d is not None:
        message = decrypt_message(ciphertexts[i], d, moduli[i])
        # Хеширование сообщения
        hash_result = sha256(str(message).encode()).hexdigest()
        # Форматирование вывода как флага CODEBY
        flag_format = f"CODEBY{{{hash_result}}}"
        print(flag_format)
        break

Tags:

#codeby#writeup#crypto#medium