Что такое rsa ключи
RSA, а так ли все просто?
Прелюдия
Немного теории
Для того чтобы понять почему крайне не рекомендуется использовать RSA в его наиболее простой форме сперва отметим следующее требование, выдвигаемое к асимметричным криптосистемам.
Требование 1:
Современная асимметричная криптосистема может(но это еще не факт) считаться стойкой, если злоумышленник, имея два открытых текста M1 и M2, а также один шифротекст Cb не может с вероятностью большей, чем 0.5 определить какому из двух открытых текстов соответствует шифротекст Cb.
Посмотрим, удовлетворяет ли RSA данному требованию. Итак, представим, злоумышленник Мэлори прослушивает переписку Алисы и Боба. В один чудесный для себя день он видит, что Боб в открытом виде задал Алисе очень важный вопрос, знание ответа на который обогатит, ну или, по крайней мере, безмерно потешит любопытство Мэлори. Алиса односложно отвечает Бобу на этот вопрос личного характера. Она шифрует свой ответ открытым ключом Боба и отправляет шифротекст. Далее Мэлори перехватывает шифротекст и подозревает, что в нем зашифровано либо «Да», либо «Нет». Всё, что ему теперь нужно сделать для того чтобы узнать ответ Алисы это зашифровать открытым ключом Боба слово «Да» и если полученный криптотекст совпадет с перехваченным, то это означает, что Алиса ответила «Да», в противном же случает злоумышленник поймет, что ответом было «Нет».
Как видно из этого, пускай несколько надуманного, но все же не столь и утопичного примера, RSA не столь надежна как это принято считать. Да конечно, можно сказать, что Алиса сама дура и никто ее не просил отвечать на такой серьезный для нее вопрос односложно. Так что же теперь запретить использование односложных ответов в криптографии? Конечно, нет. Все не так плохо, достаточно чтобы алгоритм добавлял к тексту некоторую случайную информацию, которую бы невозможно было предугадать и коварный Мэлори будет бессилен. Ведь, в самом деле, не сможет же он предсказать, что ответ «Да» после обработки алгоритмом превратится, например, в «Да4FE6DA54», а следовательно и зашифровать это сообщение он не сможет и нечего ему будет сравнивать с перехваченным криптотекстом.
Таким образом, уже сейчас можно сказать, что RSA во всех своих проявлениях будь то PGP или SSL не шифрует только отправленные на вход шифрующей функции данные. Алгоритм сперва добавляет к этим данным блоки содержащие случайный набор бит. И только после этого полученный результат шифруется. Т.е. вместо привычной всем
C=M E (mod N)
получаем более близкую к действительности
C=(M||Rand) E (mod N),
где Rand случайное число.
Такую методику называют схемами дополнения. В настоящее время использование RSA без схем дополнения является не столько плохим тоном, сколько непосредственно нарушением стандартов.
Но это далеко не все. Считается, что даже если криптоситема удовлетворяет сформулированному выше требованию, это еще не доказывает ее пригодность в практических целях. Сформулируем еще одно требование к стойкости асимметричного алгоритма.
Требование 2:
Пусть злоумышленник имеет доступ к расшифровывающему «черному ящику». Т.е. любой криптотекст по просьбе злоумышленника может быть расшифрован. Далее злоумышленник создает два открытых текста M1 и M2. Один из этих текстов шифруется и полученный в результате криптотекст Cb возвращается злоумышленнику. Задача злоумышленника угадать с вероятностью большей чем 0.5 какому из сообщений M1 и M2 соответсвует криптотекст Cb. При этом он может попросить расшифровать любое сообщение, кроме Cb(в противном случае игра не имеет смысла). Говорят что криптосистема стойкая, если злоумышленник, даже в таких прекрасных для себя условиях, не сможет указать какому исходному тексту соответствует Cb с вероятностью большей 0.5.
В свете вышесказанного посмотрим как с этим обстоят дела в RSA.
Итак, злоумышленник имеет два сообщения M1 и M2. А также криптотекст
Cb=M1 E (mod N).
Ему необходимо указать какому конкретно из двух текстов соответствует Cb. Для этого он может предпринять следующее. Зная открытый ключ E, он может создать сообщение
C’=2 E *Cb(mod N).
Далее он просит расшифровывающий «черный ящик» расшифровать сообщение C’. А затем несложная арифметика ему в помощь. Имеем:
M’=C’ D (mod N)=2 ED *M1 ED (mod N)=2*M1(mod N).
Т.е. вычислив M’/2 злоумышленник увидит M1. А это означает, что он поймет что в нашем примере было зашифровано сообщение M1, а следовательно мы еще раз убедились в неприемлемости использования RSA в его наивном виде на практике.
Устранить и эту неприятность помогают схемы дополнения. Только теперь к ним выдвигается требование не только о том, чтобы дополнительная информация была абсолютно случайной и непрогнозируемой. Но так же и том, чтобы дополнительные блоки помогали определить был ли шифротекст получен в результате работы шифрующей функции или он смоделирован злоумышленником. Причем в случае, если будет обнаружено, что шифротекст смоделирован вместо расшифрованных данных атакующему будет выдано сообщение о несоответствие данных реальному криптотексту.
Казалось бы, реализация такой схемы дополнения является труднорешаемой задачей, но ведь в криптографии уже есть готовый инструмент контроля целостности данных. Конечно же, это хеш-функции. Все современные схемы дополнений реализованы на идее применения хеш-функции в качестве проверки расшифрованных данных на подлинность.
В RSA при подписи и при шифровании данных используют две различные схемы дополнений. Схема, реализуемая для подписания документов, называется RSA-PSS(probabilistic signature scheme) или вероятностная схема подписи. Схема, используемая при шифровании – RSA-OAEP(Optimal asymmetric encryption padding) или оптимизированное асимметричное дополнение шифрования, на примере OAEP и рассмотрим как на самом деле происходит шифрование сообщений в RSA.
RSA-OAEP
Заключение
Т.е. RSA это не только возведение в степень по модулю большого числа. Это еще и добавление избыточных данных позволяющих реализовать дополнительную защиту вашей информации. Вы, возможно, спросите: а зачем это все нужно? Неужели в действительности может произойти такая ситуация, когда атакующий получит доступ к расшифровывающему алгоритму? Совсем по другому поводу как-то было сказано: если какая-либо неприятность может произойти, она обязательно произойдет. Только вот с использованием схем дополнений это уже не будет считаться неприятностью.
upd: перенес в блог криптография.
upd2:
Литература и ссылки:
1. Н. Фергюссон, Б. Шнайер «Практическая криптография»
2. Н. Смарт «Криптография»
3. Спецификация RSA-OAEP(pdf)
Что такое RSA-ключ ЕГАИС?
Регулятор закона в целях контроля передвижения каждой бутылки алкоголя от производства до покупателя внедрил всероссийскую базу данных. Это обеспечивает прозрачность движения каждой единицы товара, а также помогает бороться с недоимками по фискальным платежам. Для работы в системе ЕГАИС требуется иметь крипто-ключ и сформированный ключ RSA, а также транспортный модуль. Все это необходимо для защищенной работы в системе, чтобы третьи лица не смогли воспользоваться информацией в своих интересах.
Ключ RSA ЕГАИС – что это?
Представляет собой сертификат для защищенного соединения с единой платформой. Система необходима для передачи данных в безопасном режиме. Криптосистема позволяет пользоваться ключом шифрования только соответствующим зарегистрированным субъектам. Все данные зашифрованы от посторонних третьих лиц. РСА-ключ для ЕГАИС записывается на крипто-ключ на веб-ресурсе официального портала. Операция по записи зашифрованных данных предоставляется бесплатно.
В процессе осуществления профессиональной деятельности для каждого юридического подразделения необходимо получить собственный RSA-ключ для работы с использованием Рутокен в ЕГАИС. Перед тем как зарегистрировать соответствующие данные требуется удостовериться, что запущен аппаратный крипто-ключ той компании, для которой формируется сертификат РСА.
Что нужно для формирования ключа RSA ЕГАИС Рутокен
На начальной стадии пользователю потребуется зарегистрироваться на официальном ресурсе. После этого понадобится зайти в Личный кабинет с помощью уже имеющейся электронной подписи. В панели управления необходимо будет выбрать графу «Показать сертификат». После чего вы сможете увидеть все сертификационные материалы со сведениями о ваших точках с указанием всех идентификационных данных. Представленная информация необходима для записи специального RSA-ключа.
На следующем этапе нужно будет перейти в раздел «Получить ключ». На табло вы сможете увидеть перечень пунктов сбыта АП, которые были указаны вами при прохождении процедуры регистрации. Затем вы можете выбрать соответствующий пункт, для которого предназначен специализированный крипто-ключ и выбрать поле «Сформировать ключ». Электронная платформа запросит ввести пароль. В случае какого-либо затруднения вы можете обратиться в службу поддержки на официальном веб-ресурсе.
После того как вы установили или перезаписали РСА сертификат ЕГАИС на Рутокен можно приступать к установке УТМ. Запустив универсальный транспортный модуль, вы сможете приступить к производству и продаже алкоголя в рамках новых положений законодателя. Дополнительно нужно будет позаботиться о приобретении сканеров с целью считывания данных и стабильного осуществления всех процессов на электронной платформе.
Как обновить сертификат РСА ЕГАИС Рутокен
В связи с обновлением сертификата все субъекты алкорынка обязаны произвести обновление ключа RSA. В самом начале необходимо будет удалить старый сертификат и уже затем установить новый.
После удаления необходимо произвести обновление ключа RSA ЕГАИС Рутокен. Все манипуляции нужно будет выполнить на официальном веб-портале. При формировании ключа вам нужно будет ввести пин-код. Если все идентификационные данные будут введены правильно, сертификат будет зарегистрирован. В случае возникновения каких-либо сложностей при продлении ключа РСА ЕГАИС обратитесь в техподдержку. Специалисты могут подключиться удаленно к вашему компьютерному устройству в целях наиболее оперативного решения вопроса.
Ошибки с RSA-ключом ЕГАИС
В процессе генерации РСА сертификата могут возникать определенные сложности. В большинстве случаев существуют две причины. Первая – это неполадки на веб-ресурсе. Вторая – некорректные настройки компьютерного оборудования. Для устранения проблем с RSA-ключом ЕГАИС потребуется выполнить следующие действия:
Если же при обновлении ключа RSA ЕГАИС возникнут какие-либо сложности и не будет появляться графа «Запрос пин-кода», то необходимо в компьютерном оборудовании произвести соответствующие корректировки в настройках. В большинстве случаев неправильные настройки являются следствием невыполнения операций по формированию ключа.
При работе с использованием системы RuToken вам потребуется зайти в Панель управления, где потребуется выбрать Настройки, напротив строки Рутокен вам необходимо выбрать значение Microsoft Base Smart Card Crypto Provider. После этого нужно попробовать еще раз сформировать ключ. Если возникнут сложности, необходимо произвести обновление драйверов.
Помимо этого, проблема возникает при неправильном введении пин-кода. Если вы несколько раз неправильно ввели данные, то носитель может заблокироваться. Тогда вам придется обратиться в удостоверяющий центр. Дополнительно причиной ошибки может стать несоответствие адреса РСА ключа, указанного в лицензии. Если же будет выявление несоответствие данных, нужно будет обратиться в техподдержку Росалкогольрегулирования. С соответствующим запросом можно обратиться как лично, так и через Личный кабинет. Стоит отметить, что в некоторых случаях после внесения корректировок может потребоваться повторное формирование РСА-ключа.
Итак, для успешной работы во всероссийской системе вам помимо крипто-ключа и установки УТМ необходимо позаботиться о формировании RSA-ключа.
Иллюстрация работы RSA на примере
Вокруг алгоритмов шифрования с отрытым и закрытым ключом существует множество недопониманий и мистификаций. Здесь я хотел бы предельно коротко и наглядно, с конкретными числами и минимумом формул, показать, как это работает.
Я не вдаюсь в теорию (не очень понятно, на какой уровень подготовки читателя следует рассчитывать), но я уверен, что прочитав эту короткую иллюстрацию, любому человеку будет проще разобраться в формулах и строгих доказательствах.
Итак. Допустим, я хочу получить от вас некие данные. Мы с вам не хотим, чтобы эти данные узнал кто-то, кроме нас. И у нас нет никакой уверенности в надёжности канала передачи данных. Приступим.
Шаг первый. Подготовка ключей
Я должен проделать предварительные действия: сгенерировать публичный и приватный ключ.
Теперь пара чисел
Шаг второй. Шифрование
Строго говоря, вам вовсе незачем вычислять огромное число «19 в степени 5». При каждом умножении достаточно вычислять не полное произведение, а только остаток от деления на 21. Но это уже детали реализации вычислений, давайте не будем в них углубляться.
Шаг третий. Расшифровка
Я получил ваши данные ( E=10 ), и у меня имеется закрытый ключ
Обратите внимание на то, что открытый ключ не может расшифровать сообщение. А закрытый ключ я никому не говорил. В этом вся прелесть асимметричного шифрования.
Заметьте, никто, кроме меня (даже вы!) не может расшифровать ваше сообщение ( E=10 ), так как ни у кого нет закрытого ключа.
В чём гарантия надёжности шифрования
Постараюсь это показать на примере. Давайте разложим на множители число 360:
Мы на каждом шагу, практически без перебора, получали всё новые и новые множители, легко получив полное разложение 360=2×2×2×3×3×5
Давайте теперь возьмём число 361. Тут нам придётся помучиться.
При использовании больших чисел, задача становится очень сложной. Это позволяет надеяться, что у взломщика просто не хватит вычислительных ресурсов, чтобы сломать ваши шифр за обозримое время.
А как это всё работает на практике?
Многие читатели спрашивают, как всё это применяется на практике. Давайте рассмотрим чуть более приближенный к жизни пример. Зашифруем и расшифруем слово «КРОТ», предложенное одним из читателей. А заодно, бегло рассмотрим, какие проблемы при этом встречаются и как они решаются.
Сперва сгенерируем ключи с чуть бо́льшими числами. Они не так наглядны, но позволят нам шифровать не только числа от нуля до 20.
Оттолкнёмся от пары простых чисел
Мы готовы к шифрованию. Переведём наше слово в цифровое представление. Мы можем взять просто номера букв в алфавите. У нас получится последовательность чисел: 11, 17, 15, 19.
Мы можем зашифровать каждое из этих чисел открытым ключом
Немного о сложностях
На самом деле, изложенный способ шифрования очень слаб и никогда не используется. Причина проста — шифрование по буквам. Одна и та же буква будет шифроваться одним и тем же числом. Если злоумышленник перехватит достаточно большое сообщение, он сможет догадаться о его содержимом. Сперва он обратит внимание на частые коды пробелов и разделит шифровку на слова. Потом он заметит однобуквенные слова и догадается, как кодируются буквы «a», «и», «o», «в», «к»… Путём недолгого перебора, он вычислит дополнительные буквы по коротким словам, типа «но», «не», «по». И по более длинным словам без труда восстановит все оставшиеся буквы.
Таким образом, злоумышленнику не придётся отгадывать ваши секретные ключи. Он взломает ваше сообщение, не зная их.
Чтобы этого не происходило, используются специальные дополнительные алгоритмы, суть которых в том, что каждая предыдущая часть сообщения начинает влиять на следующую.
Последовательность (11, 28, 43, 62) получается «запутанной». Все буквы в ней как бы перемешаны, в том смысле, что на каждый код влияет не одна буква, а все предыдущие.
На практике, в исходное сообщение специально добавляются случайные и бессмысленные буквы в начало. Чтобы даже по первому коду было невозможно ничего понять. Получатель просто отбрасывает начало сообщения.
То есть мы можем добавить случайное число в начало и получить (299, 11, 17, 15, 19). После перемешивания получится: 299, 310, 4, 19, 38. После шифрования уже невозможно будет догадаться где была какая буква.
В реальной жизни всё ещё немного сложнее. Блоки, на которые бьётся сообщение длиннее одной буквы. Поэтому, сперва применяются алгоритмы выравнивания, потом алгоритмы разбиения на блоки с перепутыванием, и только потом применяется само RSA-шифрование.
Получатель делает всё в обратном порядке: расшифровывает, «распутывает» блоки и отбрасывает ненужную информацию, добавленную просто для выравнивания (чтобы сообщение можно было разбить на целое число блоков).
Детали и принципы формирования блоков можно почитать тут. Я же в этой заметке хотел рассказать только про RSA. Надесь, удалось.
Реализация алгоритма RSA в архитектуре «клиент-сервер»
Возникновение потребности
Данная статья посвящена одной из проблем, с которой я столкнулся при разработке собственного проекта. Проект имеет клиент-серверную архитектуру, и представляет собой бизнес-приложение. Практически первым вопросом после реализации передачи данных по сети и построения каркаса, возникла необходимость шифрования передаваемых данных. Первым возможным алгоритмом (планирует поддержка нескольких) был выбран алгоритм шифрования RSA.
В статье будут рассмотрены варианты реализации алгоритма RSA на клиент-серверной архитектуре, и пример такой реализации в реальном проекте.
Концепция алгоритма RSA
Данная концепция представлена на рисунке №1, изображенном выше.
Как Вы видите, ключ после генерации синим персонажем передается зеленому персонажу по незащищенному каналу в открытом виде. Его может перехватить кто угодно, но с его помощью можно только зашифровать сообщение.
Поэтому зеленый персонаж легко получает открытый ключ и производит шифрование своего сообщения с помощью данного ключа.
В пределах двух человек схема довольно-таки простая. Однако, если необходимо организовать такую систему на архитектуре клиент-сервер, возникает ряд дополнительных вопросов, которые мы рассмотрим ниже.
Клиент — сервер
Итак, для начала определимся с ключами. Как вы помните, для зашифровки сообщений необходим открытый ключ получателя. Соответственно, серверу необходим открытый ключ клиента, а клиенту – открытый ключ сервера. Следовательно, перед началом передачи данных, необходимо произвести обмен ключами. Как это происходит, рассмотрим на рисунке №2, в котором представлен процесс обмена ключами.
Обмен завершен в три этапа. Теперь как у сервера, так и у клиента имеется открытый ключ собеседника «на том конце линии». Однако тут сразу необходимо выбрать одно из двух решений поводу того, как сервер будет генерировать ключи для своих клиентов:
1. Сервер генерирует один ключ для всех клиентов ;
2. Сервер генерирует новый ключ для каждого отдельного клиента ;
Я думаю, каждый из Вас знает, что чем больше ключ, тем больше его практическая полезность. Однако, в случае алгоритма RSA, генерация ключа – не такая уж и простая задача, поскольку она представляет основную вычислительную сложность. К тому же, алгоритм устроен таким образом, что чем больше ключ, тем больший объем данных необходимо будет передавать.
К примеру, при передаче сообщения длиной 5 байт, и используя ключ длиной 512 бит, зашифрованное сообщение будет «весить» 64кбайт. Это связано с тем, что максимальный объем данных, который можно зашифровать таким ключом, равен 64-11=53 кбайт (11кбайт используется для битовых сдвигов). Если необходимо зашифровать больше – разбиваем на блоки по 53 кбайт. А если взять ключ = 4096 бит, то минимальный блок будет равен 512кбайт, несмотря на то, что мы зашифровываем всего-то 5 байтов.
Следовательно, необходимо решить:
У каждого могут быть свои взгляды на тот счет, какой вариант предпочесть, да и многое тут зависит от разрабатываемого продукта. Однако в данном проекте было решено использовать второй вариант.
Генерация и отправка ключа серверу
В нашем проекте используется трехуровневая архитектура: клиент-сервер-база данных. Сервер написан на Java, клиент — на C#. Ниже я буду описывать реализацию шифрования как на серверной части, так и на клиентской. Начнем именно с пользователя — клиента.
Далее необходимо сохранить открытый ключ в байтовом формате и отправить серверу. Для этого необходимо немного разобраться в том, из чего состоят ключи RSA. Если кратко – то они состоят из так называемых открытых и секретных экспонент и единого для обоих ключей модуля. Соответственно, открытый ключ – это открытая экспонента и модуль, закрытый ключ — закрытая экспонента и модуль. Подробнее можно прочитать здесь в главе «Алгоритм создания открытого и секретного ключей».
Записываем открытую экспоненту в буфер вывода (C#):
В данном случае длина экспоненты нужна нам для того, чтобы знать, где именно заканчивается экспонента и начинается модуль (при считывании данных на сервере). После записи отправляем данные серверу.
После того, как сервер принял пакет с ключом, необходимо забрать ключ из пакета и сохранить его. Смотрим (Java):
Думаю, здесь не нужно особо еще комментировать код, разве что странную строку, названную мною «магией вуду» :), где мы выставляем первый байт модуля равным нулю. А дело вот в чем – по неизвестным мне причинам реализация RSA в Java требует, чтобы модуль ключа всегда начинался с нуля. Возможно, это связано с тем, чтобы иметь модуль > 0, т.к. когда я пытался сам реализовать RSA на Java с использованием больших чисел (BigInteger), при неравенстве первого байта нулю получалось отрицательное число. Данный вопрос оставляю Вам, господа Хабравчане, буду очень рад, если кто-нибудь объяснит эту особенность.
Далее идет генерация ключа сервером. Рассмотрим следующий кусок кода (Java):
Думаю, тут все понятно. Хотя, конечно, если углубляться, то обязательно надо погуглить на тему таких существ, как X509 и PKCS8 (X509EncodedKeySpec и PKCS8EncodedKeySpec).
Следующим этапом является отправка ключей серверу. Производится это практически так же, как и в случае клиента (Java):
И наконец, получаем ключ на стороне клиента, считываем и сохраняем его (C#):
В случае сервера немного посложнее (Java):
Зашифрованное сообщение готово к отправке и расшифровке у получателя с помощью закрытого ключа. Единственное, о чем не стоит забывать — это то, что максимальный размер сообщения, которое может быть зашифровано, равно размерю ключа минус 11 байт. Поэтому при шифровке необходимо делить данные на блоки и шифровать их поочереди. Вот пример на C#:
На Java реализуете сами, там изменений — пара строк 🙂
Конечно, в рамках данной статьи я не смогу охватить весь объем реализации данного функционала, но, я думаю, теперь Вы точно имеете представление о том, как реализовать защищенный канал для своих клиентов с помощью алгоритма RSA.
Хватит использовать RSA
RSA — первый широко используемый алгоритм асимметричной криптографии, который до сих пор популярен в индустрии. Он относительно прост, на первый взгляд. Шифрование и подпись RSA можно посчитать на листке бумаги, чем часто занимаются студенты на лабораторных работах.
Но существует просто огромное количество нюансов, без учёта которых вашу реализацию RSA сможет взломать даже ребёнок.
По какой-то причине люди до сих пор считают RSA хорошим алгоритмом. Но на самом деле, простор для выстрела в ногу при реализации RSA чрезвычайно огромен. Слабые параметры проверить трудно, если не невозможно. А слабая производительность алгоритма побуждает разработчиков использовать рискованные способы её повысить.
Хуже того, атаки типа padding oracle, которые изобрели более 20 лет назад, актуальны и сегодня.
Даже если в теории и возможно имплементировать RSA корректно, на практике такой «подвиг» совершить почти невозможно. И уязвимости, постоянно возникающие уже на протяжении десятилетий, это только подтверждают.
Пару слов об алгоритме RSA
Если знаете, как работает RSA, эту часть можно пропустить.
RSA — криптосистема с открытым ключом, у которой есть два применения.
Первый — шифрование, когда Алиса публикует свой открытый ключ и Боб, зная его, может зашифровать сообщение, которое сможет прочитать только Алиса, расшифровав его своим закрытым ключом.
Второй — цифровая подпись, которая позволяет Алисе подписать сообщение своим закрытым ключом так, чтобы все могли проверить эту подпись с помощью её открытого ключа.
Оба алгоритма отличаются незначительными деталями, поэтому будем их называть просто RSA.
Чтобы начать работать с RSA, Алисе нужно выбрать два простых числа p и q, которые вместе образуют группу чисел по модулю N = pq. Потом Алисе нужно выбрать открытую экспоненту e и секретную d такие, что 
. По сути, e и d должны быть взаимно просты.
Как только эти параметры будут выбраны, Боб может послать Алисе сообщение M, вычислив 
. Алиса может затем расшифровать сообщение, вычислив 
.
Цифровая подпись происходит ровно наоборот. Если Алиса хочет подписать сообщение, она вычисляет подпись 
, которую Боб может проверить, убедившись, что сообщение 
Вот как бы и всё, это основная идея. К Padding oracles мы вернёмся попозже, а пока давайте посмотрим что можно сделать если параметры RSA выбраны неверно.
Начало конца
Для работы RSA требуется выбрать довольно много параметров. К сожалению, невинные на первый взгляд методы их выбора могут навредить безопасности. Давайте пройдемся по каждому из них и посмотрим, какие неприятные сюрпризы вас ждут.
Генерация простых чисел
Безопасность RSA основана на том факте, что имея большое число N, являющееся произведением двух простых чисел p и q, разложение N на простые множители, не зная p и q сделать трудно. Разработчики несут ответственность за выбор простых чисел, составляющих модуль RSA. Этот процесс чрезвычайно медленный по сравнению с генерацией ключей для других криптографических протоколов, где достаточно просто выбрать несколько случайных байтов. Поэтому, вместо того чтобы генерировать действительно случайное простое число, разработчики часто пытаются создавать числа определенной формы. Это почти всегда плохо кончается. Существует много способов выбора простых чисел таким образом, чтобы факторинг N был простым. Например, p и q должны быть глобально уникальными. Если p или q когда-либо повторно используются в других модулях RSA, то оба множителя можно легко вычислить с помощью алгоритма GCD. Плохие генераторы случайных чисел делают этот сценарий довольно вероятным, и исследования показали, что примерно 1% трафика TLS в 2012 году было подвержено такой атаке.
Более того, p и q должны быть выбраны независимо друг от друга. Если p и q совместно используют приблизительно половину своих старших битов, то N может быть вычислено с использованием метода Ферма. На самом деле, даже выбор алгоритма тестирования простоты может иметь последствия для безопасности. Пожалуй, самая широко разрекламированная атака — это уязвимость ROCA в RSALib, которая затронула многие смарт-карты, модули доверенных платформ и даже ключи Yubikey. Здесь при генерации ключей используются только простые числа определенной формы для ускорения вычислений. Простые числа, сгенерированные таким образом, тривиально обнаружить, используя хитрые приемы теории чисел. Как только слабая система была распознана, специальные алгебраические свойства простых чисел позволяют злоумышленнику использовать метод Копперсмита для разложения N.
Стоит учитывать, что ни в одном из этих случаев генерация простых чисел таким образом не является очевидным фактом, приводящем к полному отказу системы. Всё потому, что малозначимые теоретико-числовые свойства простых чисел оказывают существенное влияние на безопасность RSA. Ожидание того, что обыкновенный разработчик будет ориентироваться в этом математическом минном поле, серьезно подрывает безопасность.
Секретная экспонента d
Поскольку использование закрытого ключа большого размера отрицательно влияет на время расшифровки и подписи, у разработчиков есть стимул выбирать небольшую d, особенно в случаях устройств с низким потреблением энергии, таком как смарт-карты. Тем не менее, злоумышленник может восстановить закрытый ключ, когда d меньше корня 4-й степени из N. Вместо этого разработчикам стоит выбирать большое значение d, так, чтобы для ускорения дешифрования могла бы использоваться Китайская теорема об остатках. Однако сложность этого подхода увеличивает вероятность незначительных ошибок реализации, которые могут привести к восстановлению ключа.
Вы скажете, что обычно при инициализации RSA вы сначала генерируете модуль, используете фиксированную открытую экспоненту, а затем выбираете секретную?
Да, это предотвращает атаки с маленькой секретной экспонентой, если вы всегда используете одну из рекомендуемых открытых экспонент e.
К сожалению, это так же предполагает, что разработчики действительно будут этим заниматься. В реальном мире разработчики часто делают странные вещи, например, сначала выбирают d, а потом считают e.
Открытая экспонента e
Как и в случае c секретной экспонентой, разработчики хотят использовать небольшие открытые экспоненты, чтобы сэкономить на шифровании и проверке подписей. Обычно в этом контексте используются простые числа Ферма, в частности e = 3, 17 и 65537.
Несмотря на то, что криптографы рекомендуют использовать 65537, разработчики часто выбирают e = 3, что приводит к множеству уязвимостей в криптосистеме RSA.
(Тут разработчики использовали e = 1, который на самом деле не шифрует открытый текст вообще.)
Когда e = 3 или схожего размера, многое может пойти не так. Маленькие открытые экспоненты часто сочетаются с другими распространенными ошибками, позволяющими злоумышленнику расшифровать определенные шифротексты или факторизовать N.
Например, атака Франклина-Рейтера позволяет злоумышленнику дешифровать два сообщения, которые связаны известным, фиксированным расстоянием. Другими словами, предположим, что Алиса посылает Бобу только «купить» или «продать». Эти сообщения будут связаны известным значением и позволят злоумышленнику определить, какие из них означают «купить», а какие «продать», не расшифровывая сообщения. Некоторые атаки с маленькой e могут даже привести к восстановлению ключа.
Если открытая экспонента маленькая (не только 3), злоумышленник, который знает несколько бит секретного ключа, может восстановить оставшиеся биты и сломать криптосистему. Хотя многие из этих e = 3-атак на RSA можно пофиксить выравниванием (padding), разработчики, которые сами реализуют RSA, чрезвычайно часто забывают его использовать.
Подписи RSA также уязвимы для маленьких публичных экспонент. В 2006 году Блейхенбахер обнаружил атаку, которая позволяет злоумышленникам подделывать произвольные подписи во многих реализациях RSA, в том числе используемых в Firefox и Chrome. Это означает, что любой сертификат TLS из уязвимой реализации может быть подделан. Эта атака использует тот факт, что многие библиотеки используют небольшую публичную экспоненту и не делают простую проверку выравнивания при обработке подписей RSA. Атака Блейхенбахера на подпись настолько проста, что включена во многие упражнения на курсах криптографии.
Выбор параметров — трудная задача
Общим для всех этих атак на параметры является то, что общее количество возможных вариантов параметров намного больше, чем количество безопасных вариантов.
Предполагается, что разработчики сами будут управлять этим сложным процессом отбора, поскольку всё, кроме открытой экспоненты, должно генерироваться при инициализации.
Нет простых способов проверить надежность параметров. Вместо этого разработчикам нужна серьёзная математическая база, наличие которой не следует ожидать от рядовых сотрудников. Хоть использование RSA с выравниванием и может спасти вас при наличии неверных параметров, многие по-прежнему предпочитают этого не делать.
Padding Oracle атаки
Как мы уже выяснили выше, простое использование RSA «из коробки» не совсем работает. Например, схема RSA, изложенная во введении, будет создавать идентичные шифротексты, если один и тот же открытый текст когда-либо шифровался более одного раза. Это проблема, потому что это позволит злоумышленнику узнать содержание сообщения из контекста, не имея возможности расшифровать его. Вот почему нам нужно выравнивать сообщения несколькими случайными байтами. К сожалению, наиболее широко используемая схема выравнивания, PKCS # 1 v1.5, часто уязвима к так называемой атаке padding oracle.
Первоначальная атака на PKCS # 1 v1.5 была обнаружена еще в 1998 году Даниэлем Блейханбахером. Несмотря на то, что ей более 20 лет, сегодня она продолжает быть актуальной для многих систем. Современные версии этой атаки часто включают в себя дополнительный оракул, немного более сложный, чем тот, который первоначально описал Блейханбахер, например, время отклика сервера или выполнение какого-либо понижения версии протокола в TLS. Одним особенно шокирующим примером была атака ROBOT, которая была настолько ужасной, что команда исследователей смогла подписать сообщения секретными ключами Facebook и PayPal. Некоторые могут возразить, что это на самом деле не вина RSA — основная математика в порядке, люди просто испортили важный стандарт несколько десятилетий назад. Дело в том, что у нас уже тогда, с 1998 года была стандартная схема выравнивания с строгим доказательством безопасности, OAEP. Но почти никто не использует ее. Даже когда это происходит, общеизвестно, что OAEP сложно реализовать, и он часто уязвим к атаке Мангера, которая является еще одной атакой оракула, которую можно использовать для восстановления открытого текста.
Фундаментальная проблема здесь заключается в том, что выравнивание необходимо при использовании RSA, и эта дополнительная сложность открывает большой простор для атак на криптосистему. Тот факт, что один бит информации, «правильно ли было выровнено сообщение», может оказать настолько большое влияние на безопасность, что делает разработку защищенных библиотек практически невозможной. TLS 1.3 больше не поддерживает RSA, поэтому мы можем ожидать, что в будущем будет меньше таких атак.
Но пока разработчики будут продолжать использовать RSA в своих собственных приложениях, Padding Oracle атаки будут продолжать происходить.
Что делать?
Люди часто предпочитают использовать RSA, потому что они считают, что это концептуально проще, чем запутанный протокол DSA или криптография с эллиптической кривой (ECC). Но хотя RSA интуитивно понятнее, ему очень не хватает защиты от дурака.
Прежде всего, распространенным заблуждением является то, что эллиптика очень опасна, потому что выбор плохой кривой может всё свести на нет. Верно то, что выбор кривой имеет большое влияние на безопасность, но одним из преимуществ использования ECC является то, что выбор параметров может быть сделан публично. Криптографы делают выбор параметров за вас, так что разработчикам просто нужно генерировать случайные байты данных для использования в качестве ключей. Разработчики теоретически могут построить реализацию ECC с ужасными параметрами и не смогут проверить наличие таких вещей, как некорректные точки кривой, но они, как правило, этого не делают. Вероятное объяснение состоит в том, что математика, стоящая за ECC, настолько сложна, что очень немногие люди чувствуют себя достаточно уверенно, чтобы ее реализовать. Другими словами, этот страх заставляет людей использовать библиотеки, созданные криптографами, которые знают своё дело. RSA, с другой стороны, настолько прост, что его можно (плохо) реализовать за час.
Во-вторых, любое согласование ключей на основе алгоритма Диффи-Хеллмана или схема подписи (включая варианты эллиптической кривой) не требуют выравнивания и, следовательно, полностью устойчивы к атакам Padding Oracle. Это серьезная победа, учитывая, что у RSA очень длинный послужной список попыток избежать этого класса уязвимостей.
Мы рекомендуем использовать Curve25519 для обмена ключами и ed25519 для цифровых подписей. Шифрование должно выполняться с использованием протокола ECIES, который сочетает в себе обмен ключами ECC с алгоритмом симметричного шифрования. Curve25519 была разработана чтобы полностью предотвратить классы атак, которые могут случиться с другими кривыми, а еще она очень быстрая. Более того, она реализована во множестве библиотек, например libsodium, который снабжен легкой для чтения документацией и доступен для большинства языков.
Хватит использовать RSA. Серьезно.
(Twilio до сих пор использует RSA ключи)
(Travis CI до сих пор использует 1024 битные ключи и не даёт их заменить)
RSA был важной вехой в развитии безопасных коммуникаций, но последние два десятилетия криптографических исследований сделали его устаревшим. Алгоритмы на эллиптических кривых как для обмена ключами, так и для цифровых подписей были стандартизированы еще в 2005 году и с тех пор были интегрированы в интуитивно понятные и устойчивые к неправильному использованию библиотеки, такие как libsodium. Тот факт, что RSA все еще широко используется в наши дни, указывает как на ошибку со стороны криптографов из-за неадекватного описания рисков, присущих RSA, так и со стороны разработчиков, переоценивающих свои способности успешно развертывать его. Security сообщество должно начать думать об этом как о стадной проблеме — хоть некоторые из нас и могут быть в состоянии ориентироваться в чрезвычайно опасном процессе настройки или реализации RSA, исключения дают понять разработчикам, что в некотором роде RSA еще актуален. Несмотря на множество предостережений и предупреждений на StackExchange и GitHub README, очень немногие люди верят, что именно они испортят RSA, и поэтому они продолжают поступать безрассудно. В конечном счете ваши пользователи будут платить за это. Вот почему мы все должны согласиться с тем, что использование RSA в 2019 году совершенно неприемлемо. Без исключений.
Оригинал статьи на английском.
VirgilSecurity, Inc. разрабатывает open source developer friendly SDK и сервисы для защиты данных. Мы позволяем разработчикам использовать существующие алгоритмы с минимальным риском для безопасности.