Microsoft предупреждает об аннулировании RSA-ключей короче 1024 бит — «Хакер»

: новый уровень безопасности в мобильных приложениях – шифрование rsa-2048

2. Длинное умножение

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

Умножение в столбик не является самым эффективным методом. Его сложность составляет O(k2), где k — разрядность операндов в выбранной системе счисления. Существуют более эффективные алгоритмы: умножение Карацубы, умножение посредством преобразования Фурье [2, 7] и др.

Итак, умножение «в столбик» сводит длинное умножение к серии коротких умножений и сложений. Разумно использовать разрядность имеющегося аппаратного умножителя полностью. Например, в микроконтроллерах PIC24 и dsPIC имеется умножитель 16*16 => 32, то есть умножающий 16-битные числа и дающий 32-битный результат. Таким образом, максимально возможное основание системы счисления для этих микроконтроллеров — 216=65536.

Причем важно то, что результат 32-битный, потому что все эти 32 бита понадобятся в ходе дальнейших вычислений. Скажем, в процессорах x86 разрядность результата равна разрядности операндов, т.е. 32 бита. Чтобы не допустить переполнения, приходится ограничивать разрядность операндов 16 битами.

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

Но для микроконтроллеров dsPIC более эффективен другой подход [6]. А именно, вычисление матрицы не по строкам, а по столбцам. Сначала первый столбец, потом второй и т.д. Когда столбец вычислен — его значения можно сразу сложить между собой, получится цифра итогового результата и перенос.

Разумеется, нет смысла хранить все числа из столбца — можно вместо этого сразу добавлять их к сумме. При таком подходе операции умножения чередуются с операциями добавления результата к аккумулятору. А следовательно, становится возможным использование мощных DSP-средств этого микроконтроллера, инструкций REPEAT и MAC, которые за один такт процессора извлекают два операнда из памяти, перемножают их, добавляют результат к аккумулятору и увеличивают значения указателей.

Длинным беззнаковым умножением 2048*2048 => 4096 занимается в моей библиотеке подпрограмма mpi_muluu.

4. Длинное деление

Эффективные методы длинного деления сводят его к умножению на обратное делителю число [7]. В свою очередь, это обратное число вычисляется тоже с помощью умножения, например, итеративным методом, основанным на методе Ньютона решения уравнений [3,7]. Теоретически это могло бы быть очень выгодно для RSA, ведь делить приходится много раз на одно и то же число, так что обратное ему число нужно вычислить только один раз.

Если вспомнить изучаемый в школе метод деления «в столбик» и попытаться реализовать его «в лоб» на компьютере — то сталкиваешься с тем, что этот метод, за исключением работы в двоичной системе счисления, не сводит длинное деление к короткому или другим простым операциям.

В самом деле, снеся некоторое количество цифр делимого, необходимо разделить их на весь длинный делитель, чтобы получить очередную цифру частного. Как же здесь быть? В [4] приводится теорема, которая дает возможность «угадать» цифру частного с малой погрешностью. Она действует для случаев, когда:

1. разрядность делителя на одну цифру меньше разрядности частичного остатка;
2. первая цифра делителя больше или равна половине основания системы счисления.

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

Чтобы «угадать» цифру частного, нужно разделить две первые цифры частичного остатка на первую цифру делителя. Полученное значение либо равно истинной цифре частного, либо превышает ее не более, чем на 2. В самом деле, если мы делим 499 на 50 — то разделив 49 на 5, получаем 9, что совпадает с истинной первой цифрой частного.

Деление двух цифр частичного остатка на одну цифру делителя — это «короткое» деление, аппаратная поддержка которого очень желательна. В dsPIC33 есть аппаратная поддержка деления 32-битных чисел на 16-битные, с 16-битными частными и остатком. Этого вполне достаточно для реализации длинного деления в системе счисления по основанию 216=65536. Для x86 максимальная разрядность делимого составляет 32 бита, что также дает основание системы счисления 65536.

После «угадывания» цифры частного, необходимо умножить эту цифру на делитель и вычесть произведение из частичного остатка. Если результат меньше 0 — добавить делитель обратно и уменьшить оценку цифры частного на 1. Если все равно остаток меньше 0 — добавить делитель еще раз и еще раз уменьшить оценку частного.

Для RSA не требуется знать частное, а нужен только остаток от деления. В связи с этим я написал функцию mpi_moduu, вычисляющую только остаток. Для 2048-битного RSA необходимо делить 4096-битные числа на 2048-битные, с 2048-битным остатком.

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

Для работы вышеописанного алгоритма деления необходимы следующие компоненты длинной арифметики:

1. умножение длинного числа на короткое (на одну цифру);
2. вычитание длинных чисел;
3. сложение длинных чисел;
4. сравнение длинных чисел,

которые описываются ниже.

Сложность процедуры длинного деления — O(k2) по коротким умножениям и O(k) — по коротким делениям, где k — количество разрядов делителя в системе счисления по основанию 65536.

Decim

Decim — потоковый шифр на основе РСЛОС, разработанный Комом Бербаином, Оливером Биллетом, Анн Канту, Николя Куртуа, Бландином Дебре, Генри Гильбертом, Луи Губином, Алином Гуже, Луи Гранбуланом, Седериком Ларду, Марин Минье, Томасом Порнином и Эрвом Сибе.

Самое главное требование к шифрам — устойчивость к различным видам атак. Алгебраические атаки — одна из самых серьёзных угроз безопасности потоковым шифрам. Если соотношение между комбинацией битов секретного ключа и порождённым её битом гамма является простым или легко предсказуемым, то и нахождение алгебраических зависимостей между комбинацией битов секретного ключа и битом ключевого потока (гамма) так же является простой задачей. Для усложнения соотношений между комбинацией битов секретного ключа (или комбинацией битов начального состояния РСЛОС, порождённого секретным ключом) и битов ключевого потока (гамма) используют нелинейную фильтрующую функцию от комбинации битов секретного ключа и механизмы десинхронизации между комбинацией битов секретного ключа и битами ключевого потока (гамма). Оба этих механизма (нелинейная фильтрующая функция и механизм десинхронизации между комбинацией битов РСЛОС и битами ключевого потока) являются основой работы и основным средством предотвращения криптоаналитических атак шифра Decim.
Начало работы потокового шифра Decim начинается с ввода 80-битного секретного ключа и 64-битного открытого ключа (Initialization Vector). Затем, с помощью определённых линейных комбинаций битов К и битов IV, использования нелинейной фильтрующей функции F и применения механизма выборки ABSG вычисляется начальное состояние 192 битного РСЛОС. После выполнения всех этих операций начинается генерация ключевого потока

Microsoft предупреждает об аннулировании rsa-ключей короче 1024 бит

Misty1

Блочный алгоритм шифрования, созданный на основе «вложенных» сетей Фейстеля 1995 году криптологом Мицуру Мацуи (Mitsuru Matsui) совместно с группой специалистов для компании Mitsubishi Electric. MISTY — это аббревиатура Mitsubishi Improved Security Technology, а также инициалы создателей алгоритма: в разработке алгоритма также приняли участие Тэцуя Итикава (Tetsuya Ichikawa)

MISTY1 — это сеть Фейстеля с изменчивым числом раундов (рекомендовано 8, но оно может быть любым, кратным 4). Алгоритм работает с 64-битными блоками и использует 128-битный ключ. Шифр стал победителем среди алгоритмов, шифрующих 64-битные блоки, на Европейском конкурсе NESSIE.

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

Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Эксперты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.

MISTY1 запатентованный алгоритм. Однако исконный владелец патента, Mitsubishi Electric, объявил, что будет выдавать лицензию на использование бесплатно.MISTY1 был разработан на основе теории «подтверждённой безопасности» против дифференциального и линейного криптоанализа. Этот алгоритм был спроектирован, чтобы противостоять различным криптоатакам, известным на момент создания.

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

Дифференциальный криптоанализ высокого порядка эффективно применяется к блочным шифрам с малой степенью. Мисти содержит 2 look-up таблицы S7 и S9, обе с малой ad, 3 и 2 соответственно. Поэтому достаточно много статей посвящены дифференциальному криптоанализу мисти.

Невозможный дифференциальный анализ также применим к блочному шрифту с одинаковым значением подключа в каждом раунде (или в каждом n-ом раунде). И так как MISTY1 имеет достаточно простую систему расширения ключа, вполне естественно рассмотреть применимость данной атаки к данному алгоритму. Лучший результата для подобной атаки был также получен при рассмотрении алгоритма без FL функций.

Шифр стал победителем среди алгоритмов, шифрующих 64-битные блоки, на Европейском конкурсе NESSIE (2000—2003 года). В результате анализа алгоритма, проведённого в рамках этого конкурса и до него, эксперты сделали вывод, что никаких серьёзных уязвимостей данный алгоритм не имеет (они особо отметили, что именно структура алгоритма с вложенными сетями Фейстеля существенно затрудняет криптоанализ).

Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Эксперты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации.

Существует модификация данного алгоритма — MISTY2. Однако она не получила широкой известности вследствие низкого уровня криптостойкости.

Так же получила распространение модификация MISTY1 — алгоритм KASUMI — в 2000 году стал стандартом шифрования мобильной связи W-CDMA.

KASUMI (от японск.霞 (hiragana かすみ, romaji kasumi) — туман, mist) — блочный шифр, использующийся в сетях сотовой связи 3GPP. Также обозначается A5/3 при использовании в GSM и GEA3 в GPRS.

KASUMI разработан группой SAGE (Security Algorithms Group of Experts), которая является частью Европейского Института по Стандартизации в области Телекоммуникаций (ETSI). За основу был взят существующий алгоритм MISTY1 и оптимизирован для использования в сотовой связи.

KASUMI использует 64-битный размер блока и 128-битный ключ в 8-раундовой схеме Фейстеля. В каждом раунде используется 128-битный раундовый ключ, состоящий из восьми 16-битных подключей, полученных из исходного ключа по фиксированной процедуре генерации подключей.

Rabin

Этот алгоритм был опубликован в январе 1979 года Майклом О. Рабином. Криптосистема Рабина была первой асимметричной криптосистемой, в которой восстановление всего открытого текста из зашифрованного текста можно было доказать так же сильно, как факторинг.

Генерация ключа:

Выберем два больших разных числа p и q. Можно выбрать

Генерация ключа

1. выбираются два случайных числа p и q с учётом следующих требований:
2. числа должны быть большими (см. разрядность);
3. числа должны быть простыми;
4. должно выполняться условие:.

Выполнение этих требований сильно ускоряет процедуру извлечения корней по модулю р и q;

вычисляется число

1. число n — открытый ключ;
2. числа p и q — закрытый.

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

Расшифровка Для расшифровки сообщения необходим закрытый ключ — числа p и q. Процесс расшифровки выглядит следующим образом:

1. Сначала, используя алгоритм Евклида, из уравнения находят числа и ;
2. далее, используя китайскую теорему об остатках, вычисляют четыре числа:

   

Одно из этих чисел является истинным открытым текстом m.

P.S. Если кому интересно, то почти по всем алгоритмам, представленным в данной статье, имеются архивы, с реализацией на С, С или Ассемблере(на каком-то из языков), соответственно реализации не мои, скажу больше использовать их навряд ли получится, хотя кто знает.

P.P.S. Была идея также сделать Сравнительную таблицу, но для начала хотелось бы узнать, по каким именно параметрам Вы хотели бы увидеть сравнение.

P.P.P.S Для статейного конкурса «Нетологии», Ссылка на сайт, Ссылка на блог.

Redoc

Симметричный блочный криптоалгоритм, разработанный Майклом Вудом в 1990 году для компании Cryptech и получивший наименование REDOC II. Все операции — подстановки, перестановки, XOR выполняются с байтами что позволяет его эффективно реализовать программно.

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

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

Существует также значительно упрощенная версия алгоритма — REDOC III, созданный Майклом Вудом. Используется 80-битный блок, длина ключа переменна, может достигать 20480 битов. Перестановки и подстановки исключены, все операции над блоком и ключом основаны лишь на применении XOR, за счет чего значительно увеличена скорость шифрования в ущерб стойкости к дифференциальному криптоанализу.

Основой алгоритма являются генерированные на основе секретного ключа 256 10-байтовых ключей, и полученные на основе XOR 128 10-байтовых ключей два 10-байтовых блока маски. Для успешного восстановления обеих масок алгоритма REDOC III требуется 223 открытых текстов.

Алгоритм REDOC II и его упрощенная версия запатентованы в США.

Safer

Семейство симметричных блочных криптоалгоритмов на основе подстановочно-перестановочной сети. Основной вклад в разработку алгоритмов внёс Джеймс Мэсси. Первый вариант шифра был создан и опубликован в 1993 году.

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

Первая разновидность алгоритма — SAFER K-64 была разработана Джэймсом Мэсси для калифорнийской корпорации «Cylinc» в 1993 году. Опубликованный в том же году, алгоритм имел блок и ключ шифрования длиной в 64 бита. Для него рекомендовалось использовать 6 раундов шифрования.

Однако, из-за необходимости увеличить длину ключа до 128 бит (так как была обнаружена слабость в первоначальном варианте алгоритма), Мэсси разработал новый вариант шифра SAFER K-128, который был опубликован на следующий год после SAFER K-64. Новый алгоритм включал в себя расписание ключей, разработанное министерством внутренних дел Сингапура, и в дальнейшем использовался им для различных целей. Также для этого алгоритма рекомендовалось использовать 10 (максимум 12) раундов шифрования.

Спустя некоторое время в первых вариантах алгоритма выявились некоторые слабости, обнаруженные Ларсом Кнудсеном и Шоном Мёрфи. Это повлекло за собой создание новых версий алгоритма, названных SAFER SK-64 и SAFER SK-128, в которых расписание ключей было изменено в соответствии со схемой, предложенной Кнудсеном.

Также был разработан вариант с длиной ключа, уменьшенной до 40 бит — SAFER SK-40. Сокращение «SK» в названии алгоритмов расшифровывается как «Strengthened Key schedule» (Усиленное расписание ключей). Для новых вариантов шифра предлагалось использовать не 6, а по крайней мере 8 (максимум 10) раундов шифрования.

Алгоритм SAFER был разработан в 1998 году калифорнийской корпорацией Cylinc совместно с Армянской академией наук для участия в конкурсе AES, на котором прошёл лишь первый отборочный тур. Данный шифр имеет входной блок длиной 128 бит и размер ключа 128, 192 или 256 бит.

Последней из созданных разновидностей алгоритма SAFER является SAFER , разработанный Мэсси в 2000 году и ставший дальнейшим развитием алгоритма SAFER . Алгоритм принял участие в европейском конкурсе алгоритмов NESSIE, где был представлен в двух вариантах:

шифр с 64-битным блоком и 128-битным блоком. Он прошёл во вторую фазу конкурса, но не был выбран в набор рекомендуемых NESSIE криптографических примитивов. Эксперты сочли, что шифр слишком медленный на всех машинах, кроме 8-битных (таких как смарт-карты), а запас безопасности шифра слишком мал.

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

Sc2000

Симметричный блочный криптоалгоритм, разработанный фирмой Fujitsu и университетом г. Токио в 2000 году. В алгоритме используется 128-битный блок и ключ длиной от 128 до 256 бит (совместим со стандартом AES и поддерживает типовые длины ключа — 128/192/256).

Был рекомендован комитетом CRYPTREC в 2003 году для использования государственными учреждениями Японии, однако в 2021 году был перемещён в список «кандидатов» в рекомендованные шифры. Участвовал в конкурсе Nessie, но не попал во второй раунд, хотя и показал достаточную устойчивость к атакам — причиной стала его слишком сложная структура и опасение в вероятности скрытых уязвимостей.

SC2000 — шифр со смешанной структурой: здесь используются элементы сети Фейстеля и подстановочно-перестановочной сети. Алгоритм выполняет 6.5 (для 128-битного ключа) и ли 7.5 (для ключа длиной 192—256 бит) раундов шифрования. Каждый из раундов состоит из запросов к таблице подстановки, добавления ключа и бесключевой двухраундовой сети Фейстеля.

Расширение ключа в алгоритме SC2000 выполняется в два этапа: основе секретного симметричного ключа генерируется промежуточный ключ, затем из промежуточного ключа вычисляется нужное количество фрагментов расширенного ключа.

Один раунд шифра довольно сложен и состоит из следующих операций: Входное 128-битное значение делится на 4 подблока по 32 бита, на каждый из них операцией XOR накладывается 32-битный фрагмент расширенного ключа. Выполняется операция T, которая разбивает блок данных на 32 подблока по 4 бита каждый.

Каждый 4-битный подблок проходит через таблицу подстановки S4, которая выглядит так: (2,5,10,12,7,15,1,11,13,6,0,9,4,8,3,14)

Далее блок данных разбивается на 32-битные подблоки с помощью операции T’, обратной к операции T. Выполняется наложение операцией XOR других четырёх фрагментов расширенного ключа. Значения первой пары подблоков передаются на вход функции F. В результате выполнения данной функции получаются два 32-битных значения, которые накладываются операцией XOR на два первых подблока. Первая пара подблоков меняется местами с второй парой подблоков, затем выполняется повторно прошлый шаг трансформации.

Skipjack

Блочный шифр, разработанный Агентством национальной безопасности США в рамках проекта Capstone[en]. После разработки сведения о шифре были засекречены. Изначально он предназначался для использования в чипе Clipper для защиты аудио информации, передаваемой по сетям правительственной телефонной связи, а также по сетям мобильной и беспроводной связи. Позже алгоритм был рассекречен.

Skipjack являлся одной из инициатив, предложенных в рамках проекта Capstone. Руководили проектом Агентство национальной безопасности (АНБ) и Национальный институт стандартов и технологий (НИСТ), финансируемые правительством США. Официальная дата начала инициативы — 1993 год.

Алгоритм шифрования был разработан в 1980 году, а первая его реализация была получена в 1987 году. Шифр был предназначен для использования в чипе Clipper, встраиваемом в защищаемое оборудование. При этом Skipjack использовался только для шифрования сообщений, а депонирование ключа для возможности последующего использования уполномоченными органами — наиболее обсуждаемый аспект использования шифра — достигалось за счёт отдельного механизма, называемого Law Enforcement Access Field.

Изначально проект был засекречен и по этой причине подвергся огромной критике. Для повышения общественного доверия и оценки алгоритма были призваны несколько академических исследователей. По причине отсутствия времени для самостоятельного тщательного исследования, эксперты сконцентрировались на изучении представленного АНБ описания процесса разработки и оценки алгоритма.

1. Принимая во внимание, что стоимость вычислительных мощностей уменьшается вдвое каждые 18 месяцев, лишь через 36 лет стоимость взлома Skipjack полным перебором сравняется со стоимостью взлома DES сегодня.
2. Риск взлома шифра с помощью более быстрых способов, включая дифференциальный криптоанализ, незначителен. Алгоритм не имеет слабых ключей и свойства комплементарности.
3. Устойчивость Skipjack к криптоанализу не зависит от секретности самого алгоритма.

Шифр был опубликован в открытый доступ 24 июня 1998 года. В августе 2021 года НИСТ принял новые принципы использования криптографических стандартов, в которых отозвал сертификацию алгоритма Skipjack для правительственных целей.

Skipjack использует 80-битный ключ для шифрования/дешифрования 64-битных блоков данных. Это несбалансированная сеть Фейстеля с 32 раундами.

Symantec: сертификаты с ключами менее 2048 бит не предоставляют надлежащий уровень безопасности

Типизация ка

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

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

1. Бесключевые КА — не используют в вычислениях никаких ключей;
2. Одноключевые КА — работают с одним ключевым параметром (секретным ключом);
3. Двухключевые КА — на различных стадиях работы в них применяются два ключевых параметра: секретный и открытый ключи.