# Занятие 4. Асимметричное шифрование.

###### tags: `Cryptography and Steganography`


#### Дополнительные материалы

- [Хабр: Асимметричное шифрование](https://habr.com/ru/post/449552/)
- [Касперский: Асимметричное шифрование](https://encyclopedia.kaspersky.ru/glossary/asymmetric-encryption/)

## Асимметричное шифрование

Асимметричное шифрование — это метод шифрования данных, предполагающий использование двух ключей — открытого и закрытого. Открытый (публичный) ключ применяется для шифрования информации и может передаваться по незащищенным каналам. Закрытый (приватный) ключ применяется для расшифровки данных, зашифрованных открытым ключом. Открытый и закрытый ключи — это очень большие числа, связанные друг с другом определенной функцией, но так, что, зная одно, крайне сложно вычислить второе. При этом два ключа связанны математически.


## ALG38RA1C!


## Алгоритм формирования ключей

1. выбираются два различных случайных простых числа `p` и `q` заданного размера (например, 1024 бита каждое);
1. вычисляется их произведение `n = p * q`, которое называется модулем;
1. вычисляется значение функции Эйлера от числа  `n: f(n)=(p-1) * (q-1);
1. выбирается целое число `e: 1< e < f(n)`, взаимно простое со значением функции `f(n)`; число  `e` называется открытой экспонентой; обычно в качестве `e` берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые из чисел Ферма: 17, 257 или 65537, так как в этом случае время, необходимое для шифрования с использованием быстрого возведения в степень, будет меньше; слишком малые значения `e`, например 3, потенциально могут ослабить безопасность схемы RSA;
1. вычисляется числo `d`, мультипликативно обратное к числу `e` по модулю `f(n)`, называется секретной экспонентой; обычно оно вычисляется при помощи расширенного алгоритма Евклида; пара `(e,n)` публикуется в качестве открытого ключа RSA; пара `(d,n)` играет роль закрытого ключа RSA и держится в секрете.


## Алгоритм шифрования и дешифрования

Зная публичный ключ, или же открытый человек может зашифровать сообщение по формуле:

`Cd = me (mod n)`

Расшифровка же происходит по формуле

`Ce = md (mod n)`

При этом сообщение можно обрабатывать отдельными байтами, такого рода вопросы обговариваются на этапе реализации канала связи.


## Это же можно как то ломануть?


## Распространённый метод взлома RSA

В основе методов взлома RSA лежит вопрос факторизации чисел (разложение его на канонический вид). Идея в том, что для успешного декодирования нам надо знать число `d`, мультиплекативно числу `e` по модулю функции Эйлера от числа `n`. Казалось в чём проблема то? Берём расширенный алгоритм Евклида, ищем обратный и дело в шляпе, но… нам не известно значение этой функции и сложность в его подсчёте зная лишь число `n`.

Но вот если оно маленькое…


## Настало время практики

Пример задачи с реальной CTF площадки формата T/B категории Crypto

> Decrypt my super sick RSA:
>
> c:8533139361076999596208540806559574687666062896040360148742851107661304651861689
>
> n:769457290801263793712740792519696786147248001937382943813345728685422050738403253
>
> e:65537


## Итог лекции:

Сегодня мы рассмотрели концепцию ассиметричного шифрования на примере популярного алгоритма шифрования RSA, рассмотрели практические применения данного шифра, рассмотрели алгебру данного алгоритма. Так же рассмотрели возможности взлома данного шифра.