MaximIluin Aug 15 at 13:16

Криптография для котиков или почему открытый ключ не может расшифровать сообщение

Easy

4 min

5.7K

Привет, Хабр!

Недавно на работе возникла задача, связанная с асимметричным шифрованием — методом криптографии, где для шифрования и расшифровки используются два разных ключа:
Открытый ключ (public key) — можно свободно передавать, им шифруют данные.
Закрытый ключ (private key) — хранится в тайне, только им можно расшифровать.

И в процессе изучения у меня сложилась путаница в голове.
«Почему расшифровать сообщение можно только закрытым ключом?»
«Как открытый ключ не может расшифровать то, что сам же зашифровал?!»
Я перерыл кучу статей и обучающих видео, но понимания так и не появилось. Пока вдруг — бац — не сложилось. И теперь хочу поделиться этим озарением в максимально простой (и слегка котиковой) форме.

Возможно, кому‑то сэкономит пару часов жизни.

Короткий ответ:
Всё дело в математике. Но если бы меня устраивали такие ответы, я бы не полез в дебри.

Давайте разберём одну из самых первых криптосистем с асимметричным шифрованием — ранцевую схему Меркла‑Хеллмана. Чтобы было понятнее, будем шифровать кличку дефолтного кота — БАРСИК.

Прежде чем мы приступим, важно усвоить два термина:

1. Супервозрастающая последовательность — это такая цепочка чисел, где каждое новое число больше суммы всех предыдущих. Например: [1, 3, 6, 12]. Проверим:

3 > 1,
6 > 1+3,
12 > 1+3+6.

2. Обратное по модулю число — это число, которое при умножении на исходное даёт 1 по модулю N. Например, для числа 3 и модуля 11 обратное — это 4, потому что

Пример 1. Ранцевая система Меркла‑Хеллмана.
Приступим к созданию ключей:

Создание закрытого ключа	Нужно придумать супервозрастающую последовательность
	[11, 13, 27, 55, 111, 223, 447, 895]
	Выбираем простое число больше суммы последовательности
	Выбираем 1801
	Выбираем любое число из интервала от 1 до 1801
	Например, 915
	Отлично, мы создали закрытый ключ: 1. [11, 13, 27, 55, 111, 223, 447, 895] 2. 1801 3. 915
Создание открытого ключа	Умножим каждый элемент нашей супервозрастающей последовательности на 915 и найдем остаток от деления на 1801
	11	13	27	55	111	223	447	895
	11 × 915 mod1801	13 × 915 mod1801	27 × 915 mod1801	55 × 915 mod1801	111 × 915 mod1801	223 × 915 mod1801	447 × 915 mod1801	895× 915 mod1801
	1060	1089	1292	1698	709	532	178	1271
	Последовательность [1060, 1089, 1292, 1698, 709, 532, 178, 1271] - это наш открытый ключ

Берем слово, БАРСИК и переводим каждую букву в 8-битную кодировку
Б	А	Р	С	И	К
11000001	11000000	11010000	11010001	11001000	11001010
Умножаем биты на элементы открытого ключа. Если бит = 1 — берём число из ключа. Если бит = 0 — пропускаем.
1 × 1060 + 1 × 1089 + 0 × 1292 + 0 × 1698 + 0 × 709 + 0 × 532 + 0 × 178 + 1 × 1271 = 3420	1 × 1060 + 1 × 1089 + 0 × 1292 + 0 × 1698 + 0 × 709 + 0 × 532 + 0 × 178 + 0 × 1271 = 2149	1 × 1060 + 1 × 1089 + 0 × 1292 + 1 × 1698 + 0 × 709 + 0 × 532 + 0 × 178 + 0 × 1271 = 3847	1 × 1060 + 1 × 1089 + 0 × 1292 + 1 × 1698 + 0 × 709 + 0 × 532 + 0 × 178 + 1 × 1271 = 5118	1 × 1060 + 1 × 1089 + 0 × 1292 + 0 × 1698 + 1 × 709 + 0 × 532 + 0 × 178 + 0 × 1271 = 2858	1 × 1060 + 1 × 1089 + 0 × 1292 + 0 × 1698 + 1 × 709 + 0 × 532 + 1 × 178 + 0 × 1271 = 3036
Таким образом БАРСИК превратился в [3420, 2149, 3847, 5118, 2858, 3036]

Мы зашифровали наше сообщение — и знаем последовательность [1060, 1089, 1292, 1698, 709, 532, 178, 1271] и шаги шифрования, но расшифровать наше сообщение не представляется возможным. Зная только открытый ключ, подобрать исходные биты сложно. Попробуйте подобрать для числа 3420 комбинацию, какие биты были единицами, а какие нулями.

Давайте теперь, вернем барсика на место с помощью закрытого ключа.
Напомню, что наш закрытый ключ это [11, 13, 27, 55, 111, 223, 447, 895], 1801, 915.

Находим обратное по модулю число. Нужно решить

Берем полученный шифротекст [3420, 2149, 3847, 5118, 2858, 3036] Каждый элемент умножаем на 559 и находим остаток от деления на 1801
3420 × 559mod1801 = 919	2149 × 559mod1801 = 24	3847 × 559mod1801 = 79	5118 × 559mod1801 = 974	2858 × 559mod1801 = 135	3036 × 559mod1801 = 582
Используем "жадный алгоритм": 1. Берём полученное число (например, 919) и вычитаем из него самый большой элемент закрытого ключа, который меньше или равен ему (в нашем случае — 895). 2. Запоминаем этот элемент и повторяем шаг 1 для разности (919 - 895 = 24). 3. Продолжаем, пока не получим 0.
919-895=24 24-13=11 11-11=0	24-13 =11 11-11 =0	79-55=24 24-13= 11 11-11=0	974-895=79 79-55=24 24-13= 11 11-11 = 0	135-111=24 24-13=11 11-11= 0	582-447=135 135-111=24 24-13=11 11-11=0
Запишем элементы последовательности закрытого ключа [11, 13, 27, 55, 111, 223, 447, 895], которые мы брали для вычитания
895,13,11	13,11	55,13,11	895,55,13,11	111,13,11	447,111,13,11
Используемые элементы обозначим 1, а остальные 0
11000001	11000000	11010000	11010001	11001000	11001010

Переводим биты в буквы и получаем исходного барсика ^•ﻌ•^

Надеюсь, мне удалось показать пример того, как математика превращает простые операции в «невозвратимые» шифры.

Пример 2. RSA

Создание открытого ключа	Находим два больших (чтобы было посложнее) простых числа
	Например, 524309 и 912349
	Находим их произведение

	Выбираем любое простое число
	Пусть будет 32831
	Мы создали открытый ключ: 1. 32831 2. 478352791841
Создание закрытого ключа	Вычисляем функцию Эйлера

	Находим обратное по модулю число. Нужно решить

	Мы создали закрытый ключ: 1. 138634618031 2. 478352791841

Берем слово, БАРСИК и присваиваем каждой букве значение ее порядкового номера в русском алфавите
Б	А	Р	С	И	К
2	1	18	19	10	12
Прибавим 13, чтобы все числа были двузначными
15	14	31	32	23	15
Конкатенируем (склеим) полученные значения
151431322315
Полученное значение возводим в степень 32831. Затем находим остаток от деления результата на 478352791841
$\left(151431322325^{32831}\right) \bmod 478352791841 = 445187033916$

Мы зашифровали сообщение. Теперь без закрытого ключа расшифровка становится сложной задачей. Для этого потребуется решить уравнение: $x^{32831} \equiv 445187033916 \pmod{478352791841}$
Wolfram|Alpha с этим не справился. Хотя для нахождения ключей я использовал числа по 20 бит, в то время как Национальный институт стандартов и технологий говорит о минимальном значении в 1024 бита.

Вернем барсику его привычный вид с помощью закрытого ключа

Берём шифротекст 445187033916. Возводим его в степень 138634618031. Затем находим остаток от деления результата на 478352791841
$\left(445187033916^{138634618031}\right) \bmod 478352791841 = 151431322325$
Разбиваем полученное значение 151431322325 на блоки по 2 цифры
15	14	31	32	23	25
Отнимаем 13
2	1	18	19	10	12

Присваиваем каждому числу соответствующую букву алфавита

Я очень надеюсь, что мне удалось наглядно ответить на вопрос: «почему зная открытый ключ невозможно пройти по алгоритму шифрования задом на перед и получить исходное сообщение».

Криптография — это не магия, а тщательно продуманные математические задачи. И если ваш Барсик должен остаться в тайне, никому не давайте закрытый ключ. Закрытый ключ — как лазерная указка: должна быть только у хозяина.

P.S. Ранцевая криптосистема Меркла-Хеллмана была взломана, а RSA остаётся стойкой.

Hubs:

Cryptography