# RSA

1) Введение ~ 15 мин
- ~~Шифрование с закрытым ключом~~
~~XOR, Виженер, AES~~
- Шифрование с открытым ключом
RSA, но есть много вещей кроме RSA, просто она самая хайповая

- Модульная арифметика

2) Матеша - ~~по желанию~~ ~
- Группа
- У нас есть модуль и множество вычетов по нему. Как мы сделаем мультипликативную группу?
- Взять конкретный модуль (9)
- https://ru.wikipedia.org/wiki/Мультипликативная_группа_кольца_вычетов
- $\phi(n)$
- https://ru.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел)

3) RSA
- Не забыть про сигнатуры

`pow(e, -1, phi(n))`

`from gmpy2 import invert`

http://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf

http://factordb.com/

https://shadowservants.ru/contests/15
keker:kek

## Атаки

1) Факторизация чисел -- долго
- https://en.wikipedia.org/wiki/Fermat%27s_factorization_method
$N = a^2 - b^2$
Возьмем за А ceil(sqrt(N))
$a^2 - N -$ Квадрат. Получив квадрат, получим b
2) Blinding

RSA ctf tool: https://github.com/Ganapati/RsaCtfTool