ГДЕ КЛЮЧ ШИФРОВАНИЯ

Время на прочтение

Ассиметричный алгоритм криптографии RSA, датой возникновения концепции которого считается 1976 год сейчас очень активно используется для обмена данными, верификацией источника программного обеспечения и в других сферах, где необходимо обмениваться данными или верифицировать отправителя. Кроме того, он является базовой частью HTTPS протокола, использование которого в России достигло 98% по данным Яндекс. Радара.

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

Но что же это за алгоритм такой и как он работает? В этой статье я постараюсь разложить по полочкам основные принципы его работы и ассиметричной криптографии в целом.

RSA ключи и шифрование данных

В отличии от симметричных алгоритмов шифрования, имеющих всего один ключ для шифрования и расшифровки информации, в алгоритме RSA используется 2 ключа – открытый (публичный) и закрытый (приватный).

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

В ассиметричной криптографии и алгоритме RSA, в частности, публичный и приватный ключи являются двумя частями одного целого и неразрывны друг с другом. Для шифрования информации используется открытый ключ, а для её расшифровки приватный.

Предположим, Боб хочет передать Алисе какое-то сообщение, но лично он это сделать не может, поэтому ему необходимо использовать посредника, например Стива. Однако Боб передаёт Алисе информацию про сюрприз для Стива на его день рождения, так что не может допустить, чтобы Стив это сообщение увидел. И тут ему пригодится протокол RSA.

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

RSA шифрование сообщений

Вы можете задаться вопросом, а почему Стив не может подменить ключ Алисы на свой, расшифровать сообщение, а потом, подглядев его, зашифровать обратно на ключ Алисы? Ещё как может, это называется атака «человек посередине» (Man in the middle (MITM)), и выглядит она следующим образом:

Но есть ли решение этой проблемы? Да! Chain of Trust, или «Цепочка доверия»

Подпись данных и цепочка доверия

Перед тем как разбирать что такое «Цепочка доверия», нужно знать про ещё одну возможность закрытого ключа – подпись информации. Она осуществляется с помощью закрытого ключа и проверяется открытым.

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

RSA подпись данных

С функцией подписи закрытого ключа разобрались, действительно полезная штука! Но как это решает проблему человека по середине, ведь если Боб и Алиса не могут без посредников обменяться открытыми ключами, Стив может подменить их при передаче и постоянно перехватывать сообщения?

А всё просто! Поскольку, с помощью закрытого ключа можно подписать какие-то данные, с его помощью можно подписать и сам открытый ключ.

Если есть кто-то, предположим Грант, которому Боб и Алиса могут доверять и чей открытый ключ у них уже есть, то Грант может подписать их открытые ключи. Таким образом, если Стив попытается подменить открытый ключ Алисы, которая посылает его Бобу, то Боб сразу обнаружит подмену, ведь на ключе не будет подписи Гранта.

Также Грант может подписать открытый ключ Марку, который подпишет открытые ключи Боба и Алисы, создав таким образом ту самую «цепочку доверия».

В реальном мире существуют доверенные корневые центры сертификации (Грант), промежуточные центры (Марк) и конечные получатели (Боб и Алиса).

Компрометация ключей и списки отзыва

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

На такой случай, умные люди придумали «список отзыва» (Certificate Revocation List (CRL)), в котором будут публиковаться скомпрометированные ключи, к которым больше нет доверия.

Адрес, где находится такой список отзыва встроен во все сертификаты корневых и промежуточных центров сертификации. То есть, если Алиса заподозрит, что Стив увидел её закрытый ключ, она должна будет немедленно сказать от этом Марку, который опубликует номер её сертификата в своём списке отзыва. Боб со своей стороны, при получении старого сертификата, которым попытается воспользоваться Стив, найдёт запись о его отзыве в списке Марка и будет понимать, что Алиса была скомпрометирована и доверять её старому сертификату уже нельзя.

CRL в сертификате

Под капотом

С базовыми аспектами RSA алгоритма разобрались, теперь давайте заглянем «под капот» и посмотрим, как работает эта магия.

Вся ассиметричная криптография держится на принципе «в одну сторону быстро, в другую неразумно долго».

Например, если мы перемножим числа 592939 и 592967 мы получим число 351593260013. Но как имея только число 351593260013 узнать числа 592939 и 592967? А если каждое из этих двух чисел будут длиной более 1000 знаков? Это называется «сложность задачи факторизации произведения двух больших простых чисел», т.е. в одну сторону просто, а в обратную невероятно сложно.

Теперь рассмотрим процедуру создания публичного и приватного ключей:

Расширенный алгоритм ЕвклидаРасширенный алгоритм ЕвклидаГде a =(N), b = eПосле вычисления x2 и y2 вычисляем d по простой формуле, где x — меньшее из этих двух чисел

После произведённый вычислений, у нас будут:

e и n – открытый ключ

d и n – закрытый ключ

А теперь создадим эти ключи на примере малых простых чисел:

Пусть p = 19, q = 41

Ключи мы с вами вычислили, теперь перейдём к шифрованию сообщений.

Предположим, что Боб спрашивает у Алисы во сколько сегодня вечеринка. Алиса знает, что вечеринка в 21, но что ей нужно сделать чтобы передать это Бобу так, чтобы Стив об этом не узнал?

Заключение

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

Также рекомендую почитать пару интересных статей на тему криптографии от коллег с Хабра:

Первые несколько миллисекунд HTTPS соединения – про то, как работает криптография работает на сайтах

Доступно о криптографии на эллиптических кривых — альтернатива RSA

Полное руководство по переходу с HTTP на HTTPS – о том как настроить HTTPS у себя на сайте

Let’s Encrypt выдал миллиард сертификатов – о том как Let’s Encrypt помогает обезопасить интернет

Идея криптосистемы с открытым ключом

Асимметричное шифрование с открытым ключом базируется на следующих принципах:

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

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

Этот принцип можно объяснить через бытовую аналогию «замо́к — ключ от замка́» для отправки посылки. У участника A есть личный замок и ключ от него. Если участник А хочет получить секретную посылку от участника Б, то он публично передаёт ему свой замок. Участник Б защёлкивает замок на секретной посылке и отправляет её участнику А. Получив посылку, участник А открывает ключом замок и получает посылку.

Знание о передаче замка и перехват посылки ничего не дадут потенциальному злоумышленнику: ключ от замка есть только у участника А, поэтому посылка не может быть вскрыта.

Реализация через одностороннюю функцию

Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, то есть таких функций  , что по известному   довольно просто найти значение  , тогда как определение   из   невозможно за разумный срок.

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

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

Понять идеи и методы криптографии с открытым ключом помогает следующий пример — хранение паролей в удалённом компьютере, к которому должны подключаться пользователи. Каждый пользователь в сети имеет свой пароль. При входе он указывает имя и вводит секретный пароль. Но если хранить пароль на диске удалённого компьютера, то кто-нибудь его может считать (особенно легко это сделать администратору этого компьютера) и получить доступ к секретной информации. Для решения задачи используется односторонняя функция. При создании секретного пароля в компьютере сохраняется не сам пароль, а результат вычисления функции от этого пароля и имени пользователя. Например, пользователь Алиса придумала пароль «Гладиолус». При сохранении этих данных вычисляется результат функции  (АЛИСА_ГЛАДИОЛУС), пусть результатом будет строка РОМАШКА, которая и будет сохранена в системе. В результате файл паролей примет следующий вид:

Вход в систему теперь выглядит так:

Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет функция, применяемая к АЛИСА_ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. « Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.

В предыдущем примере используется односторонняя функция без лазейки, поскольку не требуется по зашифрованному сообщению получить исходное. В следующем примере рассматривается схема с возможностью восстановить исходное сообщение с помощью «лазейки», то есть труднодоступной информации. Для шифрования текста можно взять большой абонентский справочник, состоящий из нескольких толстых томов (по нему очень легко найти номер любого жителя города, но почти невозможно по известному номеру найти абонента). Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву. Таким образом букве ставится в соответствие номер телефона абонента. Отправляемое сообщение, например «КОРОБКА», будет зашифровано следующим образом:

Криптотекстом будет являться цепочка номеров, записанных в порядке их выбора в справочнике. Чтобы затруднить расшифровку, следует выбирать случайные имена, начинающиеся на нужную букву. Таким образом исходное сообщение может быть зашифровано множеством различных списков номеров (криптотекстов).

Примеры таких криптотекстов:

Схема шифрования с открытым ключом

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

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

Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркла о распространении открытого ключа, они предложили метод получения секретных ключей, используя открытый канал. Этот метод экспоненциального обмена ключей, который стал известен как обмен ключами Диффи — Хеллмана, был первым опубликованным практичным методом для установления разделения секретного ключа между заверенными пользователями канала. В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом. Эта же схема была разработана (англ. Malcolm J. Williamson) в 1970-х, но держалась в секрете до 1997 года. Метод Меркле по распространению открытого ключа был изобретён в 1974 и опубликован в 1978 году, его также называют загадкой Меркле.

В 1977 году учёными Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом из Массачусетского технологического института был разработан алгоритм шифрования, основанный на проблеме разложения на множители. Система была названа по первым буквам их фамилий (RSA — Rivest, Shamir, Adleman). Эта же система была изобретена в 1973 году (англ. ), работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года. R SA стал первым алгоритмом, пригодным и для шифрования, и для цифровой подписи.

Вообще, в основу известных асимметричных криптосистем кладётся одна из сложных математических проблем, которая позволяет строить односторонние функции и функции-лазейки. Например, криптосистемы Меркля — Хеллмана и Хора — Ривеста опираются на так называемую задачу об укладке рюкзака.

Основные принципы построения криптосистем с открытым ключом

Пусть есть 3 ключа  ,  ,  , распределенные так, как показано в таблице.

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

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

Преимущество этой схемы заключается в том, что для её реализации нужно только одно сообщение и n ключей (в схеме с n агентами). Если передаются индивидуальные сообщения, то есть используются отдельные ключи для каждого агента (всего n ключей) и каждого сообщения, то для передачи сообщений всем различным подмножествам требуется   ключей.

Криптоанализ алгоритмов с открытым ключом

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

Ещё одна форма атаки — вычисление закрытого ключа, зная открытый (рисунок ниже). Криптоаналитик знает алгоритм шифрования  , анализируя его, пытается найти  . Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B.

Большинство криптосистем с открытым ключом основано на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших простых чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на простые множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее. Ниже приведены данные разложения на множители с помощью алгоритма «Квадратичное решето».

Также задачу разложения потенциально можно решить с помощью алгоритма Шора при использовании достаточно мощного квантового компьютера.

Преимущества асимметричных шифров перед симметричными:

Недостатки алгоритма несимметричного шифрования в сравнении с симметричным:

Виды асимметричных шифров

У этого термина существуют и другие значения, см. Ключ.

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

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

Количество информации в ключе, как правило, измеряется в битах.

Для современных симметричных алгоритмов (AES, CAST5, IDEA, Blowfish, Twofish) основной характеристикой криптостойкости является длина ключа. Шифрование с ключами длиной 128 бит и выше считается сильным, так как для расшифровки информации без ключа требуются годы работы мощных суперкомпьютеров. Для асимметричных алгоритмов, основанных на проблемах теории чисел (проблема факторизации — RSA, проблема дискретного логарифма — Elgamal) в силу их особенностей минимальная надёжная длина ключа в настоящее время — 1024 бит.

Для асимметричных алгоритмов, основанных на использовании теории эллиптических кривых (ECDSA, ГОСТ Р 34.10-2001, ДСТУ 4145-2002), минимальной надёжной длиной ключа считается 163 бит, но рекомендуются длины от 191 бит и выше.

Криптографические ключи различаются согласно алгоритмам, в которых они используются.

Главное свойство ключевой пары: по секретному ключу легко вычисляется открытый ключ, но по известному открытому ключу практически невозможно вычислить секретный.

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

Использование асимметричных алгоритмов снимает проблему распространения ключей пользователей в системе, но ставит новые проблемы: достоверность полученных ключей. Эти проблемы более-менее успешно решаются в рамках инфраструктуры открытых ключей (PKI).