---
# System prepended metadata

title: RSA

---

# 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