§ 80. Современные алгоритмы шифрования

Определения и обозначения

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

Симметричное шифрование — способ защиты, в котором один и тот же секретный ключ применяют и для шифрования, и для расшифрования. Отправитель и получатель должны иметь одинаковый ключ и не раскрывать его посторонним. Это определение сразу показывает главное условие: до обмена данными участникам нужно безопасно договориться о секрете.

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

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

Как это устроено

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

В симметричной схеме отправитель шифрует сообщение общим ключом, а получатель тем же ключом расшифровывает его. Это удобно и обычно быстро, в том числе для больших файлов. Однако если отправитель просто пришлёт ключ вместе с сообщением по незащищённому каналу, посторонний сможет перехватить оба. Значит, участникам требуется заранее безопасно передать ключ или получить его другим защищённым способом.

В асимметричной схеме отправитель может узнать открытый ключ получателя и зашифровать сообщение им. Расшифровать результат должен обладатель соответствующего закрытого ключа, который не покидает его устройство. Связь между ключами позволяет выполнять такую операцию, но вычислить закрытый ключ по открытому при надёжных параметрах должно быть практически невозможно. Именно поэтому открытый ключ не требуется держать в тайне.

RSA показывает, как можно построить такую пару. Сначала выбирают два больших простых числа p и q, вычисляют n = pq и φ(n) = (p − 1)(q − 1), затем выбирают число e, взаимно простое с φ(n), и находят d так, чтобы ed ≡ 1 mod φ(n). Открытый ключ составляют n и e, а d входит в закрытый ключ; формулы шифрования и расшифрования используют эти числа. Если известны p и q, найти d можно, но по одному большому n разложить его на множители должно быть чрезвычайно трудно.

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

Сравнение симметричного и асимметричного шифрования

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

Разбор задач

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

1. Вспомним признак симметричной схемы: один ключ служит для шифрования и расшифрования.
2. Сопоставим этот признак с условием: ключ общий для Алисы и Бориса, значит, схема симметричная.
3. Проверим, смогут ли они общаться безопасно: сначала ключ нужно передать так, чтобы посторонний не перехватил его.

Ответ: используется симметричное шифрование. До обмена сообщениями Алиса и Борис должны безопасно договориться об общем ключе и передать его друг другу.

Задача 2. Борис хочет отправить Алисе сообщение так, чтобы прочитать его могла только она. Нужно указать ключ для шифрования и ключ для расшифрования. Важно отсчитывать роли ключей от получателя, а не от отправителя.

1. Определим, кому предназначено сообщение: получатель — Алиса.
2. Найдём открытый ключ Алисы и зашифруем сообщение им; этот ключ можно получить заранее, не раскрывая секрет.
3. Для обратного преобразования используем соответствующий закрытый ключ Алисы, который находится только у неё.

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

Задача 3. Для учебного примера RSA заданы простые числа p = 5 и q = 11. Найдём n и φ(n), выберем допустимое e и подберём d из условия ed ≡ 1 mod φ(n). Малые числа удобны для вычислений, но не подходят для реальной защиты.

1. Вычислим n = pq = 5 · 11 = 55, а φ(n) = (5 − 1)(11 − 1) = 4 · 10 = 40.
2. Выберем e = 3: оно меньше 40 и взаимно просто с 40, то есть не имеет с ним общего делителя, кроме 1.
3. Найдём d: при d = 27 произведение ed = 3 · 27 = 81, а 81 при делении на 40 даёт остаток 1. Значит, ed ≡ 1 mod 40.

Ответ: n = 55, φ(n) = 40, допустимая пара — e = 3 и d = 27. В учебном примере открытый ключ — (55, 3), закрытый включает d = 27; в реальном RSA используют намного более крупные параметры.

Типичные ошибки

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

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

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

Нельзя считать RSA надёжным при любых числах. Малые или неудачно выбранные параметры упрощают подбор ключей и разложение n на множители, хотя школьные примеры именно такими и должны быть для удобства счёта. Проверьте назначение чисел: если их можно перебрать вручную, это иллюстрация принципа, а не защита.

Связь с другими темами

Для понимания темы нужны двоичное представление данных, остаток от деления и операции с целыми числами: компьютеры хранят сообщения в битах, а криптографические алгоритмы выполняют над числами точные преобразования. Идею RSA помогают понять простые числа, разложение на множители и арифметика по модулю, то есть вычисления с остатками. Эти знания пригодятся при изучении защищённых сетевых соединений и электронной подписи. Они также объясняют, как передавать данные безопасно, даже если канал связи доступен посторонним.

Что запомнить

• Надёжность шифрования зависит прежде всего от ключа, а не от секретности алгоритма.
• В симметричной схеме для шифрования и расшифрования используют общий секретный ключ.
• В асимметричной схеме открытый ключ можно сообщать другим, а закрытый хранят в тайне.
• Чтобы зашифровать сообщение для получателя, используют его открытый ключ.
• Сообщение, зашифрованное открытым ключом, расшифровывают соответствующим закрытым ключом.
• Симметричные алгоритмы обычно быстрее, а асимметричные помогают решать проблему обмена ключами.