rsa.sage

# Attacks on RSA, 2018
# Мануал по Sage на примере textbook RSA.
# Материалы: https://khashaev.ru/secsem/rsa/

# Открываем интерактивную оболочку командой sage в терминале.

# Sage основан на синтаксисе Python.
2 * 3

# Но он немного отличается и в нем есть множество других полезных вещей.

# Кстати, в интерактивной оболочке можно использовать специальную переменную _.
# _ — это результат вычисления предыдущего выражения.
1 + _

# Правда, числовые литералы в нем не типа int, как в Python.
# 1 — это целое число, элемент кольца целых чисел.
type(1)

# Чтобы сконвертировать в привычный int, нужно написать int(...)
int(1)
type(_)

# Еще особенности.
# Если ^ в Python это XOR, то в Sage это возведение в степень.
2^3

# А чтобы сделать обычный XOR, надо писать ^^
2 ^^ 3

# Как и в Python, можно брать целые числа по модулю:
6 % 5

# Но вместо этого удобнее создавать алгебраические объекты, например, кольцо вычетов по модулю n
ZMod(5)

# Сохраним это кольцо в переменную
K = _

# Наберем K. и нажмем tab, чтобы увидеть, какие методы доступны.
# Попробуем некоторые из них.

# Порядок (количество элементов)
K.order()

# Случайный элемент кольца.
K.random_element()

# Является ли кольцо полем? Чуть позже узнаем, что это значит.
K.is_field()

# Можем сконвертировать целое число в элемент кольца вычетов:
K(4)

# Так как у нас ZMod(5), то 5 и 6 в нем "переполнятся" и получится 0 и 1.
K(5)
K(6)

# То есть выполнено равенство.
K(0) == K(5)

# Можем сохранять элементы кольца в переменные, как обычно:
a = K(2)
b = K(3)

# Можем складывать и умножать:
a + b
a * b

# В кольце обратным по сложению к числу a называется число b такое, что a + b == 0.
# По сложению у любого числа в кольце вычетов Zmod(n) есть обратное.
-a
-b

# Если через модуль это записать, то -a % n == (n - a) % n.

# А вот по умножению... Кстати, что такое обратное число по умножению?
# В кольце обратным по умножению к числу a называется число b такое, что a * b == 1.
# Можно легко доказать, что не бывает больше одного обратного числа.

# Попробуем взять обратное к 0:
K(0)^-1

# Упс! Получился ZeroDivisionError: Inverse does not exist.
# Если подумать, легко понять, что к 0 никогда не может существовать обратного,
# потому что не существует b такого, что 0 * b == 1.

# Попробуем все остальные элементы:
K(1)^-1, K(2)^-1, K(3)^-1, K(4)^-1

# Для всех остальных в Zmod(5) получилось найти обратное.
# Но всегда ли это так? Давайте попробуем другое кольцо, например, Zmod(6)
R = ZMod(6)

# Для этих обратные есть:
R(1)^-1, R(5)^-1

# А для этих нет:
R(2)^-1
R(3)^-1
R(4)^-1

# Для этих всегда получается ZeroDivisionError: Inverse does not exist.

# Вспомним вот что:
K.is_field()
R.is_field()

# Ага, вот оно что!

# Поле — это особый вид кольца, в котором все элементы обратимы по умножению.
# Если что, это не совсем строгое и точное определение, но для наших целей его хватит.
# Известный факт: Zmod(n) — поле <=> n — простое число.

# Давайте вернемся в Zmod(5).
K = Zmod(5)
a = K(2)
b = K(3)

# Деление.
a / b

# По определению, это то же самое, что и:
a * b^-1

# Получается, что в поле мы можем делить вседа, кроме как на 0.
# В кольцах — не всегда, это как повезет.
# Иными словами, для деления делитель b должен быть обратимым по умножению.

# Немного забудем про кольца и посмотрим, что мы еще можем делать.

# Можем раскладывать числа на простые множители.
factor(15)
factor(30)
factor(28)

# Можно даже раскладывать на простые множители не только числа, но и многочлены.
factor(x^2 - 1)

# Кстати, x — это заботливо для нас определенная т.н. символическая переменная.
x

# Можем и другие сделать.
y = var('y')
factor(y^4 + y^2 + 1)

# В Sage уже реализовано множество полезных функций.

# Например, для вычисления НОД.
gcd(18, 27)

# НОК.
lcm(18, 27)

# Вспомним несколько первых простых чисел.
list(primes(30))

# Можем проверять числа на простоту.
is_prime(3)
is_print(4)

# Простейший алгоритм проверки на простоту (проверять все делители числа до корня) работает за O(sqrt(n)).
# В Sage реализованы более эффективные алгоритмы.

# Поэтому можем проверять на простоту даже достаточно большие числа.
is_prime(10^9 + 7)
is_prime(10^100)

# Sage даже умеет генерировать достаточно большие простые числа.
# Что, кстати, пригодится нам для генерации ключей RSA.
random_prime(2^512)
p = _
p < 2^512

random_prime(2^512)
q = _
q < 2^512

# Перемножив два простых числа, получим 1024-битный модуль RSA.
n = p * q

# Кстати, насколько сложно факторизовывать числа?
# Давайте посмотрим.

# Если много маленьких множителей, то очень быстро раскладываются даже очень
# большие числа.
time factor(2^1000 * 3^500)

# Однако, если есть большие множители, то уже сложнее.
# Примерно 2—3 секунды занимает разложение примера ниже на среднем компьютере.
# Такая задача называется RSA-180.
time factor(random_prime(2^90) * random_prime(2^90))

# RSA-200. Уже примерно 16 секунд:
time factor(random_prime(2^100) * random_prime(2^100))

# Есть такой конкурс: https://ru.wikipedia.org/wiki/RSA-числа
# Организаторы берут два простых числа и перемножают, получившийся модуль публикуется.
# Задача: факторизовать получившийся модуль.

# За факторизацию больших RSA-модулей платят деньги, например:
# RSA-768: уже факторизовали.
# RSA-896: не факторизовали, приз — $75,000.
# RSA-1024: не факторизовали, приз — $100,000.

# А насколько быстро работает алгоритм Евклида?
p = random_prime(2^512)
q1 = random_prime(2^512)
q2 = random_prime(2^512)
time g = gcd(p * q1, p * q2)
g == p

# Быстро! Кстати, алгоритм Евклида вычисляющий gcd(a, b) работает
# за O(log(max(a, b))).
# Короче говоря, сколько примерно бит в числах, столько примерно и вычисляется.

# Число в степень тоже быстро возводить.
2^10000

# a^n возводится за O(log n) алгоритмом быстрого возведения в степень.
# Идея такая:
#     a^4 = (a^2)^2
#     a^8 = (a^4)^2
#     a^9 = a^8 * a
# Ну и так далее, немного подумав, можно из этого свойства получить
# рекурсивный алгоритм.

# Вернемся к нашей модельной реализации RSA.

# Простые множители p и q у нас уже есть. Из них сделали n.
# Давайте также возьмем открытую экспоненту для RSA.
# Можно брать, например: 3, 35, 65537... Возьмем просто 3.
e = 3

# Попробуем сгенерировать закрытый ключ d из p и q.
# Согласно алгоритму генерации ключей RSA, его можно сделать так.

# Начнем с phi — это значение функции Эйлера для модуля n.
phi = (p - 1) * (q - 1)

# Заметьте, что мы здесь используем p и q, которые знает только тот, кто
# генерирует RSA-ключи.

# Теперь осталось сделать d:
d = inverse_mod(e, phi) # это то же самое, что e^-1 по модулю phi

# Упс! Тут скорее всего нам должно было не повезти и мы получили
# ZeroDivisionError: Inverse does not exist.

# Действительно, phi = (p - 1) * (q - 1) — составное число, поэтому такой модуль не образует поле. 

# Оказывается, чтобы все работало,
# e надо выбирать так, чтобы оно было взаимно простым с phi.

# Ну или генерировать числа p, q до тех пор, пока phi не будет взаимно простым
# с выбранным e.

# Давайте так и сделаем!
e = 3
while True:
    p, q = random_prime(2^512), random_prime(2^512)
    n = p * q
    phi = (p - 1) * (q - 1)
    if gcd(e, phi) == 1:
        break

# Пришлось немного подождать, но все же получилось.

# Кстати, такой метод генерации не очень безопасный, есть очень много нюансов.
#
# Например, если p и q получатся достаточно близкими друг к другу, то тогда
# их можно будет взломать атакой Ферма. Есть и другие атаки.
#
# Но пока что будем использовать этот упрощенный метод для демонстрации.

# Осталось сделать закрытый ключ:
d = inverse_mod(e, phi)

# Теперь будем жить в большом кольце вычетов Zmod(n).
K = Zmod(n)

# Возьмем какое-нибудь секретное сообщение m < n.
K.random_element()
m = _

# Обязательно m < n.
# Скажем, если у нас RSA-1024, то зашифровать мы сможем не более
# 1024 бит = (1024 / 8) байт = 128 байт.
# В этом недостаток RSA по сравнению с алгоритмами симметричного шифрования.
# Но мы можем, например, делать следующий трюк:
#  1. Сгенерировать случайный ключ для симметричного шифрования.
#  2. Зашифровать этот ключ с помощью RSA.
#  3. Передаваемые данные зашифровать симметричным шифрованием.

# Зашифруем его открытым ключом (n, e).
m^e
c = _

# Расшифруем его закрытым ключом (n, d).
c^d

# Сравним:
m == (m^e)^d

# Вот так вот примерно RSA и работает.

# Теперь про то, как из мира чисел перейти в реальный.
#
# Вот тут можно посмотреть документацию и примеры использования библиотеки PyCrypto:
# https://www.dlitz.net/software/pycrypto/api/2.6/Crypto.PublicKey.RSA-module.html
#
# С ее помощью мы можем генерировать ключи, импортировать и экспортировать их в формат PEM и много еще чего.
# 
# Для Python библиотека ставится так:
# pip install PyCrypto
#
# Для Sage она должна быть уже установлена.