---
# System prepended metadata

title: Занятие 4. Асимметричное шифрование.
tags: [Cryptography and Steganography]

---

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

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

![](https://i.imgur.com/opWSLla.png)

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

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

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

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

![](https://i.imgur.com/eYidO5O.png)

## ALG38RA1C!

![](https://i.imgur.com/vEkEdx2.jpg)

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

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 и держится в секрете.

![](https://i.imgur.com/j1d2nyr.png)

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

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

`Cd   = me  (mod n)`

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

`Ce   = md  (mod n)`

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

![](https://i.imgur.com/mAMCyg8.png)

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

![](https://i.imgur.com/nv6i0kw.png)

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

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

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

![](https://i.imgur.com/h7xZD5U.png)

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

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

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


![](https://i.imgur.com/O6OuWY2.png)

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

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


![](https://i.imgur.com/UF7jApr.png)

