15.08.2025 13:16
MaximIluin 2 1300 Источник

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

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

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

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

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

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

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

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

  • 3 > 1,

  • 6 > 1+3,

  • 12 > 1+3+6.

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

Пример 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.

Находим обратное по модулю число. Нужно решить915× x (mod 1801) = 1

x=559

Берем полученный шифротекст [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=1
11-11=0

24-13 =11
11-11 =0

79-55=24
24-13= 1
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

Находим их произведение

524309 × 912349 = 478352791841

Выбираем любое простое число

Пусть будет 32831

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

Создание закрытого ключа

Вычисляем функцию Эйлера
(p-1)(q-1)=φ(n)

(524309-1) × (912349-1) = 478351355184

Находим обратное по модулю число. Нужно решить
32831 × x (mod 478351355184) = 1

x = 138634618031

Мы создали закрытый ключ:
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 остаётся стойкой.

Комментарии (2)


  1. abutorin
    15.08.2025 13:19
    #28712116

    а теперь давайте усложним:

    В цифровой подписи, публичный ключ предназначен для шифрования или расшифрования?


    1. suns
      15.08.2025 13:19
      #28712148

      Для проверки подписи, не всегда проверка+создание подписей эквивалентно шифрованию+расшифровыванию

      Пример - подпись через дерево Меркла, где никакого шифрования не происходит вовсе, а лишь доказывается, что «этот хеш - истина»