Реферат Курсовая Конспект
Объединение блочных шифров - раздел Компьютеры, Глава 15 ...
|
Глава 15
15.2
Тройное шифрование с двумя ключами
В более интересном методе, предложенном Тачменом в [1551], блок обрабатывается три раза с помощью двух ключей: первым ключом, вторым ключом и снова первым ключом . Он предлагает, чтобы отправитель сначала шифровал первым ключом, затем дешифрировал вторым, и окончательно шифровал первым ключом . Получатель расшифровывает первым ключом, затем шифрует вторым и, наконец, дешифрирует первым .
C = EKi(DK2(EKi(P))) P = DKi(EKi(DKi(C)))
Иногда такой режим называют шифрование-дешифрирование-шифрование(encrypt-decrypt-encrypt, EDE) [55]. Если блочный алгоритм использует и-битовый ключ, то длина ключа описанной схемы составляет 2л бит. Любопытный вариант схемы шифрование-дешифрирование-шифрование был разработан в IBM для совместимости с существующими реализациями алгоритма: задание двух одинаковых ключей эквивалентно одинарному шифрованию, этим ключом. Схема шифрование-дешифрирование-шифрование сама по себе не обладает ник а-кой безопасностью, но этот режим был использован для улучшения алгоритма DES в стандартах Х9.17 и ISO 8732 [55, 761].
К и К2 чередуются для предотвращения описанного выше вскрытия "встреча посередине" . Если С = Ек (Ек (Ек (Р))), то криптоаналитик для любого возможного Кх может заранее вычислить Ек (Ек (Р))
и затем выполнить вскрытие. Для этого потребуется только 2"+2 шифрований.
Тройное шифрование с двумя ключами устойчиво к такому вскрытию . Но Меркл и Хеллман разработали другой способ размена памяти на время, который позволяет взломать этот метод шифрования за 2й-1 действий, используя 2" блоков памяти [1075].
Для каждого возможного К2 расшифруйте 0 и сохраните результат. Затем расшифруйте 0 для каждого возможного Ки чтобы получить Р. Выполните тройное шифрование Р, чтобы получить С, и затем расшифруйте С ключом Кх. Если полученное значение совпадает с значением (хранящемся в памяти), полученным при деши ф-рировании 0 ключом К2, то пара Кх К2 является возможным результатом поиска. Проверьте, так ли это. Если нет, продолжайте поиск.
Выполнение этого вскрытия с выбранным открытым текстом требует огромного объема памяти . Понадобится 2" времени и памяти, а также 2т выбранных открытых текстов. Вскрытие не очень практично, но все же чувствительность к нему является слабостью алгоритма.
Пауль ван Оорсчот (Paul van Oorschot) и Майкл Винер (Michael Wiener) преобразовали это вскрытие ко вскрытию с известным открытым текстом, для которого нужно р известных открытых текстов. В примере предполагается, что используется режим EDE.
(1) Предположить первое промежуточное значения а.
(2) Используя известный открытый текст, свести в таблицу для каждого возможного Кг второе промежуточное значение Ъ, при первом промежуточном значении, равном а:
Ъ = DKi (С)
где С - это шифротекст, полученный по известному открытому тексту.
(3) Для каждого возможного К2 найти в таблице элементы с совпадающим вторым промежуточным значение
b:
b = EKi (a)
(4) Вероятность успеха равно plm, где/; - число известных открытых текстов, а т - размер блока. Если совпадения не обнаружены, выберите другое а и начните сначала.
Вскрытие требует 2й+> времени и р - памяти. Для DES это равно 2по/р [1558]. Для р, больших 256, это вскрытие быстрее, чем исчерпывающий поиск.
Тройное шифрование с тремя ключами
Если вы собираетесь использовать тройное шифрование, я рекомендую три различных ключа. Общая длина ключа больше, но хранение ключа обычно не является проблемой . Биты дешевы.
C = EKi{DKi{EKi{P))) P = DKi(EK2(DKj(Q))
Для наилучшего вскрытия с разменом памяти на время, которым является "встреча посередине", потребуется 22" действий и 2" блоков памяти [1075]. Тройное шифрование с тремя независимыми ключами безопасно н а-столько, насколько на первый взгляд кажется безопасным двойное шифрование .
Тройное шифрование с минимальным ключом (ТЕМЕ)
Существует безопасный способ использовать тройное шифрование с двумя ключами, противостоящий описанному вскрытию и называемый Тройным шифрованием с минимальным ключом (Triple Encryption with Minimum Key, TEMK) [858]. Фокус в той, чтобы получить три ключа из: Хг иХ2.
K2=EXi(DX2(EXi(T2))) K3 = EXi(DX2(EXi(T3)))
ТиТ2и Т3 представляют собой константы, которые необязательно хранить в секрете. Эта схема гарантирует, что для любой конкретной пары ключей наилучшим будет вскрытие с известным открытым текстом .
Режимы тройного шифрования
Недостаточно просто определить тройное шифрование, нужно выбрать один из способов его использования . Решение зависит от требуемых безопасности и эффективности . Вот два возможных режима тройного шифрования:
Внутренний СВС:Файл три раза шифруется в режиме СВС (см. 14tha). Для этого нужно три различных IV.
C=E^S^C^-S=D^T^S^-T=E^P,®^) P=T^D^Tyj=S^E^-S=C^D^q)
Со, S0 и Т0 являются IV.
Внешний СВС:Файл троекратно шифруется в режиме СВС (см. 14thb). Для этого нужен один IV.
C=E^D^E^P,®^))) P=C^D^E^D^q)))
Ф
Ф
Ф
Е
кх
Е
кх
Е
кх
Е
Ki
Е
Ki
Е
Ki
Ф
Ф
Ф
К2 |
D
К2 |
D
К2 |
D,
К2 |
D
К2 |
D
К2 |
D
Ф
Ф
Е
к,
Е
к,
Е
к,
Е
къ
Е
къ
Е
къ
(а) Внутренний СВС
(Ь) Внешний СВС
Рис. 15-1. Тройное шифрование в режиме СВС.
Для обоих режимов нужно больше ресурсов, чем для однократного шифрования: больше аппаратуры или больше времени. Однако при трех шифрующих микросхемах производительность внутреннего СВС не меньше, чем при однократном шифровании. Так как три шифрования СВС независимы, три микросхемы могут быть загружены постоянно, подавая свой выход себе на вход.
Напротив во внешнем СВС обратная связь находится снаружи по отношению к трем шифрованиям . Это означает, что даже с тремя микросхемами производительность будет равна только одной трети производительн о-сти при однократном шифровании. Чтобы получить ту же производительность для внешнего СВС, потребуется чередование IV (см. раздел 9.12):
с;=М^(ЗД©с;._з)))
В этом случае С0, Сл и С_2 являются IV. Это не поможет при программной реализации, разве только при и с-пользовании параллельного компьютера.
К сожалению менее сложный режим является также и менее безопасным . Бихам проанализировал различные режимы по отношению к дифференциальному криптоанализу и обнаружил, что безопасность внутреннего СВС по сравнению с однократным шифрованием увеличивается незначительно . Если рассматривать тройное шифрование как единый большой алгоритм, то внутренние обратные связи позволяют вводить внешнюю и известную информацию внутрь алгоритма, что облегчает криптоанализ . Для дифференциальных вскрытий нужно огромное количество выбранных шифротекстов, что делает эти вскрытия не слишком практичными, но этих результатов должно хватить, чтобы насторожить параноидальных пользователей . Анализ устойчивости алгоритмов к вскрытиям грубой силой и "встречей посередине" показал, что оба варианта одинаково безопасны [806].
Кроме этих существуют и другие режимы. Можно зашифровать файл один раз в режиме ЕСВ, затем дважды в СВС, или один раз в СВС, один в ЕСВ и еще раз в СВС, или дважды в СВС и один раз в ЕСВ. Бихам показал, что эти варианты не безопаснее, чем однократный DES, против вскрытия дифференциальным криптоанализом с выбранным открытым текстом [162]. Он не оставил больших надежд и для других вариантов . Если вы собираетесь применять тройное шифрование, используйте внешнюю обратную связь .
Варианты тройного шифрования
Прежде, чем появились доказательства того, что DES не образует группу, для многократного шифрования предлагались различные схемы. Одним из способов обеспечить то, что тройное шифрование не выродится в однократное, было изменение эффективной дины блока. Простым методом является добавление бита-заполнителя. Между первым и вторым, а также между вторым и третьим шифрованиями текст дополняется
строкой случайных битов (см. Рис. 15.2). Если РР - это функция дополнения, то: C = EKi(PP(EK2(PP(EKi(P)))))
Это дополнение не только разрушает шаблоны, но также обеспечивает перекрытие блоков шифрования, как кирпичей в стене. К длине сообщения добавляется только один блок.
Открытый текст
■ ■
Шифрование
_^_^_:*^
ппппп
Запо
лнит ель
~~v------- ------- v-------- ------- v-------- ------- v-------- ------- ■-
■ ■
V .. А А
Шифрование
Запо
лнит ель
ддддд
<------- ~Y------- -------- Y-------- -------- Y------- -------- Y-------- -------- S
■ ■
Шифрование
Дшдп
Г------- ----- Y-------- ------- V-------- ------- -V-------- ------- -V-------- ------- -S
Шифротекст
■ ■
Рис. 15-2. Тройное шифрование с заполнением.
Другой метод, предложенный Карлом Эллисоном (Carl Ellison), использует некоторую функцию независимой от ключа перестановки между тремя шифрованиями . Перестановка должна работать с большими блоками -8 Кбайт или около этого, что делает эффективный размер бока для этого варианта равным 8 Кбайтам . При условии, что перестановка выполняется быстро, этот вариант ненамного медленнее, чем базовое тройное шифр о-вание.
С = ЕКъ (T(EKi (T(EKi (Р)))))
Г собирает входные блоки (до 8 Кбайт в длину) и использует генератор псевдослучайных чисел для их пер е-мешивания. Изменение одного бита входа приводит к изменению 8 байтов результата первого шифрования, к изменению до 64 байтов результата второго шифрования и к изменению до 512 байтов результата третьего шифрования. Если каждый блочный алгоритм работает в режиме СВС, как было первоначально предложено, то изменение единичного бита входа скорее всего приведет к изменению всего 8-килобайтового блока, даже если этот блок не является первым.
Самый последний вариант этой схемы отвечает на вскрытие внутреннего СВС, выполненное Бихамом, добавлением процедуры отбеливания, чтобы замаскировать структуру открытых текстов . Эта процедура представляет собой потоковую операцию XOR с криптографически безопасным генератором псевдослучайных чисел и ниже обозначена как R. Г мешает криптоаналитику определить a priori, какой ключ используется для шифрования любого заданного байта входа последнего шифрования . Второе шифрование обозначено пЕ (шифрование с циклическим использованием п различных ключей):
С = ЕКъ (R(T(nEKi (T(EKi (Р))))))
Все шифрования выполняются в режиме ЕСВ, используется не меньше и+2 ключей шифрования и криптографически безопасный генератор псевдослучайных чисел.
Эта схема была предложена для использования вместе с DES, но она работает с любым блочным алгоритмом. Результаты криптоанализа такой схемы мне неизвестны.
15.3 Удвоение длины блока
В академическом сообществе давно спорят на тему, достаточна ли 64-битовая длина блока . С одной стороны 64-битовый блок обеспечивает диффузию открытого текста только в 8 байтах шифротекста . С другой стороны более длинный блок затрудняет безопасную маскировку структуры, кроме того, больше возможностей ошибит ь-
ся.
Существуют предложения удваивать длину блока алгоритма с помощью многократного шифрования [299]. Прежде, чем реализовывать одно из них, оцените возможность вскрытия "встреча посередине" . Схема Ричарда Аутбриджа (Richard Outerbridge) [300], показанная на 12-й, не более безопасна, чем тройное шифрование с одинарным блоком и двумя ключами [859].
Левая половина Левая половина |
Е* | ||
-J Левая | Правая | |
поло- | поло- | |
вина | вина | |
Екг | ||
J Левая | Правая | |
поло- | поло- | |
вина | вина | |
▼ 1Г | ||
Е* | ||
Рис. 15-3. Удвоение длины блока.
Однако я не рекомендую использовать подобный прием. Он не быстрее обычного тройного шифрования: для шифрования двух блоков данных все также нужно шесть шифрований . Характеристики обычного тройного шифрования известны, а за новыми конструкциями часто прячутся новые проблемы .
15.4 Другие схемы многократного шифрования
Проблемой тройного шифрования с двумя ключами является то, что для увеличения вдвое пространства ключей нужно выполнять три шифрования каждого блока открытого текста. Разве не здорово было бы найти какой-нибудь хитрый способ объединить два шифрования, которые удвоили бы пространство ключей ?
Двойной OFB/счетчик
Этот метод использует блочный алгоритм для генерации двух потоков ключей, которые используются для шифрования открытого текста.
Т;= ^2(т;_1е/2);/2= /2+ 1
Q = Pt®St ®Tt
St и Ti - внутренние переменные, а/,и/2 - счетчики. Две копии блочного алгоритма работают в некотором гибридном режиме OFB/счетчик, а открытый текст, 5*, и Tt объединяются с помощью XOR. Ключи Кг и К2 независимы. Результаты криптоанализа этого варианта мне неизвестны.
XDES?
В [1644, 1645] DES используется как компонент ряда блочных алгоритмов с увеличенными размерами кл ю-чей и блоков. Эти схемы никак не зависят от DES, и в них может использоваться любой блочный алгоритм .
Первый, xDES1, представляет собой просто схему Luby-Rackoff с блочным шифром в качестве базовой функции (см. раздел 14.11). Размер блока в два раза больше размера блока используемого блочного фильтра, а размер ключа в три раза больше, чем у используемого блочного фильтра . В каждом из 3 этапов правая половина шифруется блочным алгоритмом и одним из ключей, затем выполняется XOR результата и левой половины, и половины переставляются.
Это быстрее, чем обычное тройное шифрование, так как тремя шифрованиями шифруется блок, длина которого в два раза больше длины блока используемого блочного алгоритма. Но при этом существует простое вскрытие "встреча посередине", которое позволяет найти ключ с помощью таблицы размером 2 *, где к - это размер ключа блочного алгоритма. Правая половина блока открытого текста шифруется с помощью всех возможных значений Ки выполняется XOR с левой половиной открытого текста и полученные значения сохраняются в таблице. Затем правая половина шифротекста шифруется с помощью всех возможных значений К3, и выполняется поиск совпадений в таблице. При совпадении пара ключей КгиКъ- возможный вариант правого ключа. После нескольких повторений вскрытия останется только один кандидат. Таким образом, xDES1 не является идеальным решением. Даже хуже, существует вскрытие с выбранным открытым текстом, доказывающее, что xDES1 не намного сильнее используемого в нем блочного алгоритма [858].
по размеру равен блоку используемого блочного шифра, а все 10 ключей |
В xDES2 эта идея расширяется до 5-этапного алгоритма, размер блока которого в 4 раза, а размер ключа в 10 раз превышают размеры блока и ключа используемого блочного шифра . На 11th показан один этап xDES2, каждый из четырех подблоков независимы.
С | |||||||||||
1 | ' | Ек, | - | Екг | - | ||||||
t | J* | ||||||||||
Рис. 15-4. Один этап xDES2.
К тому же, эта схема быстрее, чем тройное шифрование: для шифрования блока, который в четыре раза больше блока используемого блочного шифра, нужно 10 шифрований . Однако этот метод чувствителен к дифференциальному криптоанализу [858] и использовать его не стоит. Такая схема остается чувствительной к дифференциальному криптоанализу, даже если используется DES с независимыми ключами этапов.
Для i > 3 xDES' вероятно слишком велик, чтобы использовать его в качестве блочного алгоритма . Например, размер блока для xDES3 в 6 раз больше, чем у лежащего в основе блочного шифра, ключ в 21 раз длиннее, а для шифрования блока, который в 6 раз длиннее блока лежащего в основе блочного шифра, нужно 21 шифрование .
Это медленнее, чем тройное шифрование.
Глава 16
Генераторы псевдослучайных последовательностей
Шифры
Табл. 16-1. Константы для линейных конгруэнтных генераторов
Переполняется при | а 106 | Ъ | т |
^20 | |||
?24 | |||
~25 | |||
~26 | |||
2 27 | |||
^28 | |||
2 29 | |||
2 30 | |||
2 31 | |||
2 32 | |||
2 33 | |||
2 34 | |||
2 35 |
Однако, линейные конгруэнтные генераторы сохраняют свою полезность для некриптографических прил о-жений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестах демонстрируют хорошие статистические характеристики. Важную информацию о линейных конгруэнтных г е-нераторах и их теории можно найти в [942].
Рис. 16-1. Сдвиговый регистр с обратной связью
Криптографам нравились потоковые шифры на базе сдвиговых регистров : они легко реализовывались с помощью цифровой аппаратуры. Я лишь слегка затрону математическую теорию. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности сдвиговых регистров [1411]. Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие ене-которые свои резальтаты и результаты Селмера [643]. См. также [970, 971, 1647].
Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью(linear feedback shift register, или LFSR) (см. 14th). Обратная связь представляет собой просто XOR некоторых битов регистра, перечень этих битов называется отводной последовательностью(tap sequence). Иногда такой регистр называется конфигурацией ФиббоначиИз-за простоты последовательности обратной связи для анализа LFSR можно использовать довольно развитую математическую теорию. Криптографы любят анализировать последовательности, убеждая себя, что эти последовательности достаточно случа й-ны, чтобы быть безопасными. LFSR чаще других сдвиговых регистров используются в криптографии.
ь„ | Vi | ■ ■ ■ ■ | ь4 | Ь3 | ь2 | ||||
^^^ ■ ■ ■ ■ | Выходной бит | ||||||||
Рис. 16-2. Сдвиговый регистр с линейной обратной связью.
На 13-й показан 4-битовый LFSR с отводом от первого и четвертого битов. Если его проинициализировать значением 1111, то до повторения регистр будет принимать следующие внутренние состояния :
1 1 1 1
0 1 1 1
1 0 1 1
0 1 0 1
1 0 1 0 1 1 0 1 0 1 1 0
0 0 1 1
1 0 0 1 0 1 0 0 0 0 1 0
0 0 0 1
1 0 0 0 1 1 0 0 1 1 1 0
ь4 | Ь3 | ь2 | bi | ь. | |
Выходной бит |
Рис. 16-3. 4-битовый LFSR.
Выходной последовательностью будет строка младших значащих битов :
1 1 1 1 0 1 0 1 1 0 0 1 0 0 0. . . .
й-битовый LFSR может находиться в одном из 2"-1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2й-1 битов. (Число внутренних состояний и период равны 2"-1, потому что заполнение LFSR нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно .) Только при определенных отводных последовательностях LFSR циклически пройдет через все 2"-1 внутренних состояний, такие
LFSR являются LFSR последовательностью.
С
максимальным периодом. Получившийся результат называется
М-
Для того, чтобы конкретный LFSR имел максимальный период, многочлен, образованный из отводной п о-следовательности и константы 1, должен быть примитивным по модулю 2. Степеньмногочлена является длиной сдвигового регистра. Примитивный многочлен степени п - это неприводимый многочлен, который является делителем х^ +1, но не является делителем xd+ для всех d, являющихся делителями 2й-1 (см. раздел 11.3). Соответствующую математическую теорию можно найти в [643, 1649, 1648].
В общем случае не существует простого способа генерировать примитивные многочлены данной степени по модулю 2. Проще всего выбирать многочлен случайным образом и проверять, не является ли он примитивным . Это нелегко - и чем-то похоже на проверку, не является ли простым случайно выбранное число - но многие м а-тематические пакеты программ умеют решать такую задачу. Ряд методов приведен в [970, 971].
Некоторые, но, конечно же, не все, многочлены различных степеней, примитивные по модулю 2, приведены в 14-й [1583, 643, 1649, 1648, 1272, 691]. Например, запись (32, 7, 5, 3, 2, 1, 0) означает, что следующий многочлен примитивен по модулю 2:
х32 +х7 +х5 +х3 +х2 +х+ 1
Это можно легко обобщить для LFSR с максимальным периодом. Первым числом является длина LFSR. Последнее число всегда равно 0, и его можно опустить. Все числа, за исключением 0, задают отводную последов а-тельность, отсчитываемую от левого края сдвигового регистра. То есть, члены многочлена с меньшей степенью соответствуют позициям ближе к правому краю регистра.
Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра новый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и первого битов (см. 12th), получающийся LFSR будет иметь максимальную длину, циклически проходя до повтор е-ния через 232-1 значений.
Код для этого LFSR на языке С выглядит следующим образом:
int LFSR ( ) {
static unsigned long ShiftRegister = 1;
/* Все, кроме О. */
ShiftRegister = ((((ShiftRegister » 31)
л(ShiftRegister » 6)
л(ShiftRegister » 4)
л(ShiftRegister » 2)
л(ShiftRegister » 1)
AShiftRegister))
& 0x00000001)
«31)
I (ShiftRegister » 1) ; return ShiftRegister & 0x00000001; }
Если сдвиговый регистр длиннее компьютерного слова, код усложняется, но не намного .
Ь32 | ■ ■ ■ ■ | ь7 | ь6 | ь5 | ь4 | Ь3 | ь2 | bi | ||
* | ||||||||||
^~****щ^^ | ■ ■ ■ ■ , | Выходной бит | ||||||||
Рис. 16-4. 32-битовый LFSR с максимальной длиной.
Табл. 16-2. Некоторые примитивные многочлены по модулю 2
(1, 0) (2, 1, 0) (3, 1, 0) (4,1, 0) (5, 2, 0) (6, 1, 0) (7, 1, 0)
(7, 3, 0) | (14, 5, 3, 1, 0) | (18, 5, 2, 1, 0) |
(8, 4,3, 2, 0) | (15, 1, 0) | (19, 5, 2, 1, 0) |
(9, 4,0) | (16, 5, 3.2, 0) | (20, 3, 0) |
(10, 3, 0) | (17, 3, 0) | (21, 2, 0) |
(11, 2, 0) | (17, 5, 0) | (22, 1, 0) |
(12, 6, 4,1, 0) | (17, 6, 0) | (23, 5, 0) |
(13, 4,3, 1, 0) | (18, 7, 0) | (24, 4,3, 1, 0) |
(25, 3, 0) (26, 6, 2, 1, 0) (27, 5, 2, 1, 0) (28, 3, 0) (29, 2, 0) (30, 6, 4, 1.0) (31, 3, 0) (31, 6, 0) (31, 7, 0) (31, 13, 0) (32, 7, 6, 2, 0) (32, 7, 5, 3, 2, 1, 0) (33, 13, 0) (33, 16, 4, 1, 0) (34, 8, 4, 3, 0) (34, 7, 6, 5, 2, 1, 0) (35, 2, 0) (135, 11, 0) (135, 16, 0) (135, 22, 0) (136, 8, 3, 2, 0) (137, 21, 0) (138, 8, 7, 1, 0) (139, 8, 5, 3, 0) (140, 29, 0) (141, 13, 6, 1, 0) (142, 21, 0) (143, 5, 3, 2, 0) (144, 7, 4, 2, 0) (145, 52, 0) (145, 69, 0) (146, 5, 3, 2, 0) (147, 11, 4, 2, 0) (148, 27, 0) (149, 10, 9, 7, 0) (150, 53, 0) (151, 3, 0) (151, 9, 0) (151, 15, 0) (151, 31, 0) (151, 39, 0) (151, 43, 0) (151, 46, 0) (151, 51, 0) (151, 63, 0) (151, 66, 0) (151, 67, 0) (151, 70, 0) (36, 11, 0) (36, 6, 5, 4, 2, 1, 0) (37, 6, 4, 1, 0) (37, 5, 4, 3, 2, 1, 0) (38, 6, 5, 1, 0) (39, 4, 0) (40, 5, 4, 3, 0) (41, 3, 0) (42, 7, 4, 3, 0) (42, 5, 4, 3, 2, 1, 0) (43, 6, 4, 3, 0) (44, 6, 5, 2, 0) (45, 4, 3, 1, 0) (46, 8, 7, 6, 0)
(46, 8, 5, 3, 2, 1, 0) (47, 5, 0) (48, 9, 7, 4, 0) (48, 7, 5, 4, 2, 1, 0) (49, 9, 0) (49, 6, 5, 4, 0) (50, 4, 3, 2, 0) (51, 6, 3, 1, 0) (52, 3, 0) (53, 6, 2, 1, 0) (54, 8, 6, 3, 0) (54, 6, 5, 4, 3, 2, 0) (55, 24, 0) (55, 6, 2, 1, 0) (56, 7, 4, 2, 0) (57, 7, 0) (57, 5, 3, 2, 0) (58, 19.0) (58, 6, 5, 1, 0) (59, 7, 4, 2, 0) (59, 6, 5, 4, 3, 1, 0) (60, 1, 0) (61, 5, 2, 1, 0) (62, 6, 5, 3, 0) (63, 1, 0) (64, 4, 3, 1, 0) (65, 18, 0) (65, 4, 3, 1, 0) (66, 9, 8, 6, 0) (66, 8, 6, 5, 3, 2, 0) (67, 5, 2, 1, 0) (152, 6, 3, 2, 0) (153, 1, 0) (153, 8, 0) (154, 9, 5, 1, 0) (155, 7, 5, 4, 0) (156, 9, 5, 3, 0) (157, 6, 5, 2, 0) (158, 8, 6, 5, 0) (159, 31, 0) (159, 34, 0) (159, 40, 0) (160, 5, 3, 2, 0) (161, 18, 0) (161, 39, 0) (161, 60, 0) (162, 8, 7, 4, 0) (163, 7, 6, 3, 0) (164, 12, 6, 5, 0) (165, 9, 8, 3, 0) (166, 10, 3, 2, 0) (167, 6, 0) (170, 23, 0) (172, 2, 0) (174, 13, 0) (175, 6, 0) (175, 16, 0) (175, 18, 0) (175, 57, 0) (177, 8, 0) (177, 22, 0) (1 77, 88, 0)
(68, 9, 0) (68, 7, 5, 1, 0) (69, 6, 5, 2, 0) (70, 5, 3, 1, 0) (71, 6, 0) (71, 5, 3, 1, 0) (72, 10, 9, 3, 0) (72, 6, 4, 3, 2, 1, 0) (73, 25, 0) (73, 4, 3, 2, 0) (74, 7, 4, 3, 0) (75, 6, 3, 1, 0) (76, 5, 4, 2, 0) (77, 6, 5, 2, 0) (78, 7, 2, 1, 0) (79, 9, 0) (79, 4, 3, 2, 0) (80, 9, 4, 2, 0) (80, 7, 5, 3, 2, 1, 0) (81, 4, 0) (82, 9, 6, 4, 0) (82, 8, 7, 6, 1, 0) (83, 7, 4, 2, 0) (84, 13, 0) (84, 8, 7, 5, 3, 1, 0) (85, 8, 2, 1, 0) (86, 6, 5, 2, 0) (87, 13, 0) (87, 7, 5, 1, 0) (88, 11, 9, 8, 0) (88, 8, 5, 4, 3, 1, 0) (89, 38, 0) (89, 51, 0) (89, 6, 5, 3, 0) (90, 5, 3, 2, 0) (91, 8, 5, 1, 0) (91, 7, 6, 5, 3, 2, 0) (92, 6, 5, 2, 0) (93, 2, 0) (94, 21, 0) (94, 6, 5, 1, 0) (95, 11, 0) (95, 6, 5, 4, 2, 1, 0) (96, 10, 9, 6, 0) (96, 7, 6, 4, 3, 2, 0) (178, 87, 0) (183, 56, 0) (194, 87, 0) (198, 65, 0) (201, 14, 0) (201, 17, 0) (201, 59, 0) (201, 79, 0) (202, 55, 0) (207, 43, 0) (212, 105, 0) (218, 11, 0) (218, 15, 0) (218, 71, 0) (218.83, 0) (225, 32, 0) (225, 74, 0)
(225, 88, 0) (225, 97, 0) (225, 109, 0) (231, 26, 0) (231, 34, 0) (234, 31, 0) (234, 103, 0) (236, 5, 0) (250, 103, 0) (255, 52, 0) (255, 56, 0) (255, 82, 0) (258, 83, 0) (266, 47, 0) (97, 6, 0) (98, 11, 0) (98, 7, 4, 3, 1, 0) (99, 7, 5, 4, 0) (100, 37, 0) (100, 8, 7, 2, 0) (101, 7, 6, 1, 0) (102, 6, 5, 3, 0) (103, 9, 9) (104, 11, 10, 1, 0) (105, 16, 0) (106, 15, 0) (107, 9, 7, 4, 0) (108, 31, 0) (109, 5, 4, 2.0) (110, 6, 4, 1, 0) (111, 10, 0) (111, 49, 0) (113, 9, 0) (113, 15, 0) (113, 30, 0) (114, 11, 2, 1, 0) (115, 8, 7, 5, 0) (116, 6, 5, 2, 0) (117, 5, 2, 1, 0) (118, 33, 0) (119, 8, 0) (119, 45, 0) (120, 9, 6, 2, 0) (121, 18, 0) (122, 6, 2, 1, 0) (123, 2, 0) (124, 37, 0) (125, 7, 6, 5, 0) (126, 7, 4, 2, 0) (127, 1, 0) (127, 7, 0) (127, 63, 0) (128, 7, 2, 1, 0) (129, 5, 0) (130, 3, 0) (131, 8, 3, 2, 0) (132, 29, 0) (133, 9, 8, 2, 0) (134, 57, 0) (270, 133, 0) (282, 35, 0) (282, 43, 0)
(286, 69, 0) | (378, 43, 0) | (521, 168, 0) | (2281, 915, 0) |
(286, 73, 0) | (378, 107, 0) | (607, 105, 0) | (2281, 1029, 0) |
(294, 61, 0) | (390, 89, 0) | (607, 147, 0) | (3217, 67, 0) |
(322, 67, 0) | (462, 73, 0) | (607, 273, 0) | (3217, 576, 0) |
(333, 2, 0) | (521, 32, 0) | (1279, 216, 0) | (4423, 271, 0) |
(350, 53, 0) | (521, 48, 0) | (1279, 418, 0) | (9689, 84, 0) |
(366, 29, 0) | (521, 158, 0) | (2281, 715, 0) |
Обратите внимание, что у всех элементов таблицы нечетное число коэффициентов . Я привел такую длинную таблицу, так как LFSR часто используются для криптографии с потоковыми шифрами, и я хотел, чтобы разные люди могли подобрать различные примитивные многочлены. Еслир(х) примитивен, то примитивен и х"р(1/х), поэтому каждый элемент таблицы на самом деле определяет два примитивных многочлена .
Например, если (а, Ь, 0) примитивен, то примитивен и (а, а - Ь, 0). Если примитивен (а, Ь, с, d, 0), то примитивен n(a, a - d, a - c, a - b, 0). Математически:
если примитивен ха + хъ + 1, то примитивен и ха + ха"ъ + 1
если примитивен ха + х» + хс + xd + 1, то примитивен и ха + xa'd + ха'с + ха'ъ + 1
Быстрее всего программно реализуются примитивные трехчлены, так как для генерации нового бита тужно выполнять XOR только двух битов сдвигового регистра. Действительно, все многочлены обратной связи, приведенные в 14-й, являются разреженными,то есть, у них немного коэффициентов. Разреженность всегда представляет собой источник слабости, которой иногда достаточно для вскрытия алгоритма . Для криптографических алгоритмов гораздо лучше использовать плотныепримитивные многочлены, те, у которых много коэффициентов. Применяя плотные многочлены, особенно в качестве части ключа, можно использовать значительно более короткие LFSR.
Генерировать плотные примитивные многочлены по модулю 2 нелегко . В общем случае для генерации примитивных многочленов степени к нужно знать разложение на множители числа 2*-1. Примитивные многочлены можно найти в следующих трех хороших работах: [652, 1285, 1287].
Сами по себе LFSR являются хорошими генераторами псевдослучайных последовательностей, но они обл а-дают некоторыми нежелательными неслучайными свойствами . Последовательные биты линейны, что делает их бесполезными для шифрования. Для LFSR длины п внутреннее состояние представляет собой предыдущие п выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2й выходным битам генератора с помощью высоко эффективного алгоритма Berlekamp-Massey [1082,1083]: см. раздел 16.3.
Кроме того, большие случайные числа, генерируемые с использованием идущих подряд битов этой послед о-вательности, сильно коррелированны и для некоторых типов приложений вовсе не являются случайными . Несмотря на это LFSR часто используются для создания алгоритмов шифрования .
И
■ ■ ■ ■
Be
Ь4
Ьз |
bi |
Ь2
1Л1Л1Л
Выходной бит
Рис. 16-5. LFSR Галуа.
Выигрыш состоит в том, что все XOR можно сделать за одну операцию. Эта схема также может быт распараллелена, а полиномы различных обратных связей могут быть различны . Такая конфигурация Галуа может дать выигрыш и при аппаратной реализации, особенно в виде СБИС . Вообще, при использовании аппаратуры, которая хорошо выполняет сдвиги применяйте конфигурацию Фиббоначи, если есть возможность использовать параллелизм, применяйте конфигурацию Галуа.
16.3 Проектирование и анализ потоковых шифров
Большинство реальных потоковых шифров основаны на LFSR. Даже в первые дни электроники построить их было несложно. Сдвиговый регистр не представляет из себя ничего большего, чем массив битов, а последов а-тельность обратной связи - набор вентилей XOR. Даже при использовании СБИС потоковый шифр на базе LFSR обеспечивает немалую безопасность с помощью нескольких логических вентилей .
Проблема LFSR состоит в том, что их программная реализация очень неэффективна. Вам приходится избегать разреженных многочленов обратной связи - они облегчают корреляционные вскрытия [1051, 1090, 350] - а плотные многочлены обратной связи неэффективны. Выход любого потокового шифра является побитовым, для шифрования того, что можно выполнить за одну итерацию DES, необходимо выполнить 64 итерации потокового алгоритма. Действительно, программная реализация простого алгоритма LFSR, подобного описываемому ниже сжимающему генератору, не быстрее, чем DES.
Эта отрасль криптографии быстро развивается и very politically charged. Большинство разработок засекречены - множество используемых сегодня военных систем шифрования основаны на LFSR. Действительно, у большинства компьютеров Cray (Cray 1, Cray X-MP, Cray Y-MP) есть весьма любопытная инструкция, обычно называемая как "счетчик совокупности" (population count). Она подсчитывает количество единиц в регистре и может быть использована как для эффективного вычисления расстояния Хэмминга между двумя двоичными словами и для реализации векторизированной версии LFSR. Я слышал, что эта инструкция считается канонич е-ской инструкцией NSA, обязательно фигурирующей почти во всех контрактах, касающихся компьютеров.
С другой сторон было взломано удивительно большое число казавшихся сложными генераторов на базе сдвиговых регистров. И, конечно же, число таких генераторов, взломанных военными криптоаналитическими учреждениями, такими как NSA, еще больше. Иногда удивляешься тому, что самые простые из них предлагаются снова и снова.
Рис. 16-6. Генератор Геффа.
Если длины LFSR равны пи п2 и п3, соответственно, то линейная сложность генератора равна
(щ+ 1)п2 + щщ,
Период генератора равен наименьшему общему делителю периодов трех генераторов . При условии, что степени трех примитивных многочленов обратной связи взаимно просты, период этого генератора будет равен произведению периодов трех LFSR.
Хотя этот генератор неплохо выглядит на бумаге, он криптографически слаб и не может устоять против корреляционного вскрытия [829, 1638]. В 75 процентах времени выход генератора равен выходу LFSR-2. Поэтому, если известны отводные последовательности обратной связи, можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра. Тогда можно подсчитать, сколько раз выход LFSR совпадает с выходом генератора. Если начальное значение определено неверно, две последовательности будут согласовываться в 50 процентах времени, а если правильно, то в 75 процентах времени .
Аналогично, выход генератора равен выходу LFSR в 75 процентах времени. С такими корреляциями генератор потока ключей может быть легко взломан. Например, если примитивные многочлены состоят только из трех членов, и длина самого большого LFSR равна и, для восстановления внутренних состояний всех трех LFSR нужен фрагмент выходной последовательности длиной 37и битов [1639].
Рис. 16-7. Обобщенный генератор Геффа.
Несмотря на то, что эта схема сложнее генератора Геффа, для взлома можно использовать то же корреляционное вскрытие. Не рекомендую этот генератор.
Генератор Дженнингса В этой схеме мультиплексо управдр<»|Ы]| LFSR31, BijffapaeT |
a |
С |
LFSR-1 |
Тактирован |
К, |
тся дл: |
истюльзуЕ! |
функция, которая отобр 1ждет выход LFSR-2 на вход^щ^мтш.^' |
объединения двух LFSR [778, 779, 780]. Мультиплексор, 1 бит LFSK-2 в качествеч©ыбГоттного выходного бита. Кроме того, используется
К2 |
> b(t)
К3
LFSR-2
Рис. 16-8. Генератор Дженнингса.
Ключом является начальное состояние двух LFSR и функции отображения. Хотя у этого генератора замечательные статистические свойства, он пал перед выполненным Россом Андерсоном (Ross Anderson) вскрытием корректности встречей посередине [39] и вскрытием линейной корректности [1638,442]. Не используйте этот генератор.
Рис. 16-9. Генератор "стоп-пошел" Beth-Piper.
Никому не удалось привести для общего случая достоверные данные о линейной сложности этого генератора. Однако он не устоял перед корреляционным вскрытием [1639].
Чередующийся генератор "стоп-пошел"
В этом генераторе используются три LFSR различной длины. LFSR-2 тактируется, когда выход LFSR-1 равен 1, LFSR-3 тактируется, когда выход LFSR-1 равен 0. Выходом генератора является XOR LFSR-2 и LFSR-3 (см. Рис. 16.10) [673].
Q------- *-b(t) |
Рис. 16-10. Чередующийся генератор "стоп-пошел"
У этого генератора большой период и большая линейная сложность . Авторы показали способ корреляционного вскрытия LFSR-1, но это не сильно ослабляет генератор. Были предложены и другие генераторы такого типа [1534, 1574, 1477].
Двусторонний генератор "стоп-пошел "
В этом генераторе используется два LFSR с одинаковой длиной п (см. Рис. 16.11) [1638]. Выходом генератора является XOR выходов каждого LFSR. Если выход LFSR-1 в момент времени М равен 0, а в момент времени t-2 -l, то LFSR-2 не тактируется в момент времени t. Наоборот, если выход LFSR-2 в момент времени М равен 0, а в момент времени t-2 - 1, и если LFSR-2 тактируется в момент времени t, то LFSR-1 не тактируется в момент времени t.
Ф(0
фл(0
a(t+n-)
Т
a(t+n-2)
a(t)
„.этапный LFSR- 2
11
ziLy—*" °®
Т
„.этапный LFSR-1
b(t+n-)
b(t+n-2)
bit)
ф(0
фв(0
Рис. 16-11. Двусторонний генератор "стоп-пошел".
Линейная сложность такой системы примерно равна ее периоду. Согласно [1638], "в такой системе не очевидная избыточность ключа не наблюдается".
Рис. 16-12. Пороговый генератор.
Для трех LFSR выход генератора можно представить как:
Ъ = (ах л а2) © (й!л аъ) © (а2 л аъ)
Это очень похоже на генератор Геффа за исключением того, что пороговый генератор обладает большей л и-нейной сложностью
щпг + й1йз + п2п3
где пи п2ип3 - длины первого, второго и третьего LFSR.
Этот генератор не слишком хорош. Каждый выходной бит дает некоторую информацию о состоянии LFSR -точнее 0.189 бита - и генератор в целом не может устоять перед корреляционным вскрытием . Я не советую использовать такой генератор.
Ф
Рис. 16-13. Самопрореживающий генератор Рюппела.
>b(t) |
Ф
Рис. 16-14. Самопрореживающий генератор Чамберса и Голлмана.
Многоскоростной генератор с внутренним произведением(inner-product)
Этот генератор, предложенный Массеем (Massey) и Рюппелом [1014], использует два LFSR с разными тактовыми частотами (см. 1st). Тактовая частота LFSR-2 в а? раз больше, чем у LFSR-1. Отдельные биты этих LFSR объединяются операцией AND, а затем для получения выходного бита генератора они объединяются посредс т-вом XOR.
>b(t) |
Ф
D * ф
Рис. 16-15. Многоскоростной генератор с внутренним произведением.
Хотя этот генератор обладает высокой линейной сложностью и великолепными статистическими характер и-стиками, он все же не может устоять перед вскрытием линейной согласованности [1639]. Если щ - длина LFSR-1, пг - длина LFSR-2, a d - отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной
п2+ п2 + log2d
Суммирующий генератор
Еще одно предложение Рэйнер Рюппела, этот генератор суммирует выходы двух LFSR (с переносом) [1358, 1357]. Это в высокой степени нелинейная операция. В конце 80-х этот генератор был лидером в отношении безопасности, но он пал перед корреляционным вскрытием [1053, 1054, 1091]. Кроме того, было показано, что этот генератор является частным случаем обратной связи, использующей сдвиговый регистр с переносом (см.
раздел 17.4), и может быть взломан [844].
DNRSG
Это означает "динамический генератор случайной последовательности" ("dynamic random-sequence generator") [1117]. Идея состоит в том, чтобы взять два различных фильтруемых генератора - пороговых, суммиру тощих, и т.п. - использующих один набор LFSR, а управляемых другим LFSR.
Сначала тактируются все LFSR. Если выходом LFSR-0 является 1, то вычисляется выход первого фильтрующего генератора. Если выходом LFSR-0 является 0, то вычисляется выход второго фильтрующего генератора. Окончательным результатом является XOR выходов первого и второго генераторов.
Ф
Рис. 16-16. Каскад Голлманна.
Это дерзкая идея: концептуально они очень просты и могут быть использованы для генерации последов а-тельностей с огромными периодами, огромными линейными сложностями и хорошими статистическими сво й-ствами. Они чувствительны к вскрытию, называемому запиранием(lock-in) [640] и представляющему метод, с помощью которого сначала криптоаналитик восстанавливает вход последнего сдвигового регистра в каскаде , а затем взламывает весь каскад, регистр за регистром. В некоторых случаях это представляет собой серьезную проблему и уменьшает эффективную длину ключа алгоритма, но для минимизации возможности такого вскрытия можно предпринять ряд определенных мер.
[637, 638, 642, к не |
использовать |
Дальнейший анализ показал, что с ростом к последовательность приближается к случайной 639]. На основании недавних вскрытий коротких каскадов Голлманна [1063], я советую меньше 15. Лучше использовать больше коротких LFSR, чем меньше длинных LFSR.
Pike
Pike - это обедненная и урезанная версия Fish, предложенная Россом Андерсоном, тем, кто взломал Fish [45]. Он использует три аддитивных генератора. Например:
A^iAt.ss+At.rimodl32
Bt = {Bt.si+BU1) той?1
C, = (C,,58 +C,-19jmod 232
Для генерации слова потока ключей взгляните на биты переноса при сложении . Если все три одинаковы (все нули или все единицы), то тактируются все три генератора. Если нет, то тактируются только два совпадающих генератора. Сохраните биты переноса для следующего раза. Окончательным выходом является XOR выходов трех генераторов.
Pike быстрее Fish, так как в среднем для получения результата нужно 2.75 действия, а не 3. Он также слишком нов, чтобы ему доверять, но выглядит очень неплохо.
Mush
Mush представляет собой взаимно прореживающий генератор . Его работу объяснить легко [1590]. Возьмем два аддитивных генератора: А и В. Если бит переноса А установлен, тактируется В. Если бит переноса В установлен, тактируется А. Тактируем А и при переполнении устанавливаем бит переноса. Тактируем В и при переполнении устанавливаем бит переноса. Окончательным выходом является XOR выходов А и В. Проще всего использовать те же генераторы, что и в Fish:
А^Ц^+А^той!32
S, = (S,_52 +iWmod 232
В среднем для генерации одного выходного слова нужно три итерации генератора . И если коэффициенты аддитивного генератора выбраны правильно и являются взаимно простыми, длина выходной последовательн о-сти будет максимальна. Мне неизвестно об успешных вскрытиях, но не забывайте, что этот алгоритм очень нов .
16.10 Gifford
Дэвид Джиффорд (David Gifford) изобрел потоковый шифр и использовал его для шифрования сводок нов о-стей в районе Бостона с 1984 по 1988 год [608, 607, 609]. Алгоритм использует единственный 8-байтовый р е-гистр: Ь0, Ъъ . . . , Ъъ Ключом является начальное состояние регистра. Алгоритм работает в режиме OFB, открытый текст абсолютно не влияет на работу алгоритма. (См. -1-й).
*Сброс |
Рис. 16-17. Gifford.
Для генерации байта ключа к, объединим Ь0 и Ьи а также объединим Ь4 и Ьъ Перемножим полученные числа, получая 32-битовое число. Третьим слева байтом и будет *,-.
Для обновления регистра возьмем Ъх и сдвинем вправо "с приклеиванием" на 1 бит следующим образом: крайний левый бит одновременно и сдвигается, и остается на месте . Возьмем Ь, и сдвинем его на один бит влево, в крайней правой позиции должен появиться 0. Выполним XOR измененного Ъъ измененного Ъ, и Ь0. Сдвинем первоначальный байт регистра на 1 бит вправо и поместим этот байт в крайнюю левую позицию .
В течение всего времени использования этот алгоритм оставался безопасным, но он был взломан в 1994 году [287]. Оказалось, что многочлен обратной связи не был примитивным и, таким образом, мог быть вскрыт .
PKZIP
Алгоритм шифрования, встроенный в программу сжатия данных PKZIP, был разработан Роджером Щлафлы (Roger Schlafly). Это потоковый шифр, шифрующий данные побайтно. По крайней мере этот алгоритм используется в версии 2.04g. Я не могу ничего сказать о более поздних версиях, но если не было сделано никаких з а-явлений об обратном, можно считать с большой вероятностью, что алгоритм не изменился . Алгоритм использует три 32-битовых переменных, инициализированных следующим образом :
К0 = 305419896
#!= 591751049
Кг = 878082192
Используется 8-битовый ключ К3, полученный из К2. Вот этот алгоритм (в стандартной нотации С):
G=PiAK3
К0= сгс32 (К0, Р,)
Ку= Кх+ (К0 & OxOOOOOOff)
K1 =i:1*134775813 + l
К2 = сгс32 (К2, Кх » 24)
К3 = ((К2 | 2)* ((К2 | 2)л1)) » 8
Функция сгс32 берет свое предыдущее значение и байт, выполняет их XOR и вычисляет следующее значение с помощью многочлена CRC, определенного 0xedb88320. На практике 256-элементная таблица может быть рассчитана заранее, и вычисление сгс32 превращается в:
сгс32 (а, Ь) = (а » 8) л table [(а & Oxff) © Ъ ]
Таблица рассчитывается в соответствии с первоначальным определением сгс32:
table [г] = crc32 (i, 0)
Для шифрования потока открытого текста сначала для обновления ключей зациклим байты ключа в алг о-ритме шифрования. Полученный шифротекст на этом этапе игнорируется. Затем побайтно зашифруем открытый текст. Открытому тексту предшествуют двенадцать случайных байтов, но это на самом деле неважно . Дешифрирование похоже на шифрование за исключением того, что во втором действии алгоритма вместо Р, используется С,.
Безопасность PKZIP
К сожалению она не слишком велика. Для вскрытия нужно от 40 до 2000 байтов известного открытого те к-ста, временная сложность вскрытия составит около 227 [166]. На вашем персональном компьютере это можно сделать за несколько часов. Если в сжатом файле используются какие-нибудь стандартные заголовки, получ е-ние известного открытого текста не представляет собой проблемы . Не используйте встроенное в PKZIP шифрование.
Глава 17
Другие потоковые шифры и генераторы настоящих случайных последовательностей
RC4
RC4 - это потоковый шифр с переменным размером ключа, разработанный в 1987 году Роном Ривестом для RSA Data Security, Inc. В течение семи лет он находился в частной собственности, и подробное описание алгоритма предоставлялось только после подписания соглашения о неразглашении .
В сентябре 1994 кто-то анонимно опубликовал исходный код в списке рассылки "Киберпанки" (Cypherpunks). Он быстро распространился в телеконференнции Usenet sci.crypt и через Internet по различным ftp-серверам во всем мире. Обладатели легальных копий RC4 достоверность этого кода. RSA Data Security, Inc. попыталась загнать джинна обратно в бутылку, утверждая, что несмотря на опубликование алгоритм остается торговым секретом, было слишком поздно. С тех пор алгоритм обсуждался и изучался в Usenet, распространялся на конференциях и служил в качестве учебного пособия на курсах по криптографии .
Описывать RC4 просто. Алгоритм работает в режиме OFB: поток ключей не зависит от открытого текста. Используется S-блок размером 8*8: So, Si, . . . , S255- Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины . В алгоритме применяются два счетчика, i nj, с нулевыми начальными значениями.
Для генерации случайного байта выполняется следующее :
i = (i +l) mod 256
j =G + &) mod 256
поменять местами St и Sj
t = (St + Sj) mod 256
K = St
Байт К используется в операции XOR с открытым текстом для получения шифротекста или в операции XOR с шифротекстом для получения открытого текста. Шифрование выполняется примерно в 10 раз быстрее, чем DES.
Также несложна и инициализация S-блока. Сначала заполним его линейно: S0 = 0, Si = 1, . . . , 6*255 = 255. Затем заполним ключом другой 256-байтовый массив, при необходимости для заполнения всего массива повторяя ключ: Ко, Къ. . . , К255. Установим значение индекса; равным 0. Затем:
for г = 0 to 255:
j =G + Si + К,) mod 256
поменять местами St и Sj
И это все. RSADSI утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу , что, по-видимому, в нем нет никаких коротких циклов, и что он в высокой степени нелинеен . (Опубликованных криптоаналических результатов нет. RC4 может находиться в примерно 21700 (256! * 2562) возможных состояний: невероятное число.) S-блок медленно изменяется при использовании: i обеспечивает изменение каждого элемента, а у - что элементы изменяются случайным образом. Алгоритм настолько несложен, что большинство программистов могут закодировать его просто по памяти.
Эту идею можно обобщить на S-блоки и слова больших размеров. Выше была описана 8-битовая версия RC4. Нет причин, по которым нельзя бы было определить 16-битовый RC4 с 16*16 S-блоком (100 К памяти) и 16-битовым словом. Начальная итерация займет намного больше времени - для сохранения приведенной схемы нужно заполнить 65536-элементный массив - но получившийся алгоритм должен быть быстрее.
RC4 с ключом длиной не более 40 битов обладает специальным экспортным статусом (см. раздел 13.8). Этот специальный статус никак не влияет на безопасность алгоритма, хотя в течение многих лет RSA Data Security, Inc. намекало на обратное. Название алгоритма является торговой маркой, поэтому каждый, кто напишет собс т-венный код, должен назвать его как-то иначе. Различные внутренние документы RSA Data Security, Inc. до сих пор не были опубликованы [1320, 1337].
Итак, какова же ситуация вокруг алгоритма RC4? Он больше не является торговым секретом, поэтому кто угодно имеет возможность воспользоваться им. Однако RSA Data Security, Inc. почти наверняка возбудит дело против каждого, кто применит нелицензированный RC4 в коммерческом продукте. Возможно им и не удастся
выиграть процесс, но почти наверняка для другой компании дешевле купить лицензию, чем судиться .
RC4 входит в десятки коммерческих продуктов, включая Lotus Notes, AOCE компании Apple Computer и and Oracle Secure SQL. Этот алгоритм также является частью спецификации Сотовой цифровой пакетной передачи данных (Cellular Digital Packet Data) [37].
17.2 SEAL
SEAL - это программно эффективный потоковый шифр, разработанный в IBM Филом Рогэвэем (Phil Roga-way) и Доном Копперсмитом (Don Coppersmith) [1340]. Алгоритм оптимизирован для 32-битовых процессоров : Для нормальной работы ему нужно восемь 32-битовых регистров и кэш-память на несколько килобайт . Чтобы избежать влияния использования медленных операций SEAL выполняет ряд предварительных действий с ключом, сохраняя результаты в нескольких таблицах. Эти таблицы используются для ускорения шифрования и д е-шифрирования.
Семейство псевдо случайных функций
Особенностью SEAL является то, что он в действительности является не традиционным потоковым шифром, а представляет собой семейство псевдослучайных функцийПри 160-битовом ключе к и 32-битовом п SEAL растягивает п в L-битовую строку к(п). L может принимать любое значение, меньшее 64 Кбайт. SEAL, по видимому, использует следующее свойство: если к выбирается случайным образом, то к(п) должно быть вычислительно неотличимо от случайной L-битовой функции п.
Практический эффект того, что SEAL является семейством псевдослучайных функций, состоит в том, что он удобен в ряде приложений, где неприменимы традиционные потоковые шифры . Используя большинство потоковых шифров, вы создаете однонаправленную последовательность битов : единственным способом определить г'-ый бит, зная ключ и позицию i, является генерирование всех битов вплоть до г'-ого. Отличие семейства псевдослучайных функций состоит в том, что вы можете легко получить доступ к любой позиции потока ключей . Это очень полезно.
Представим себе, что вам нужно "закрыть" жесткий диск. Вы хотите зашифровать каждый 512-байтовый сектор. Используя семейство псевдослучайных функций, подобное SEAL, содержимое сектора п можно зашифровать, выполнив его XOR с к(п). Это то же самое, как если бы была выполнена операция XOR всего диска с длинной псевдослучайной функцией, и любая часть этой длинной строки может быть независимо вычислена без всяких проблем.
Семейство псевдослучайных функций также упрощает проблему синхронизации, встречающуюся в стандартных потоковых шифрах. Предположим, что вы посылаете шифрованные сообщения по каналу, в котором данные иногда теряются. С помощью семейства псевдослучайных функций можно зашифровать ключом к и-ое передаваемое сообщение, х„, выполнив XOR x„ and k(n). Получателю не нужно хранить состояние шифра для восстановления х„, ему не приходится беспокоиться и о потерянных сообщениях, влияющих на процесс деши ф-рирования.
Описание SEAL
Внутренний цикл SEAL показан на 16th. Алгоритм управляется тремя полученными из ключа таблицами: R, ShT. Предварительная обработка отображает ключ к на эти таблицы с помощью процедуры, основанной на SHA (см. раздел 18.7). 2-килобайтная таблица Г представляет собой S-блок 9*32 битов.
a
N
Рис. 17-1. Внутренний цикл SEAL.
SEAL также использует четыре 32-битовых регистра, А, В, С и D, начальные значения которых определяются п и полученными по к таблицами R и Т. Эти регистры изменяются в ходе итераций, каждая из которых с о-стоит из восьми этапов. На каждом этапе 9 битов первого регистра (все равно А, В, С или D) используются в качестве индекса таблицы Т. Затем выбранное из Г значение складывается со вторым регистром (снова одному из А, В, С или D) или объединяется с его содержимым с помощью XOR. Потом первый регистр циклически сдвигается на 9 позиций. На некоторых этапах второй регистр далее модифицируется с помощью сложения или XOR с содержимым первого регистра (уже сдвинутым). После 8 таких этапов А,В,СиИ добавляются к потоку ключей, при этом каждый из них маскируется сложением или XOR с определенным словом из S. Итерация завершается прибавлением к А и С дополнительных значений, зависящих от п, щ, п2, щ, щ, выбор конкретного значения определяется четностью номера итерации. По видимому, при разработке этой схемы главными были следующие идеи:
1. Использование большого, секретного, получаемого из ключа S-блока (7).
2. Чередующиеся некоммутируемые арифметические операции (сложение и XOR).
3. Использование внутреннего состояния, поддерживаемого шифром, которое не проявляется явно в п о-токе данных (значения ni, которые модифицируют А и С в конце каждой итерации).
4. Изменение функции этапа в соответствии с номером этапа и изменение функции итерации в соотве т-ствии с номером итерации.
Для шифрования каждого байта текста SEAL требует около пяти элементарных операций. На 50-мегагерцовом процессоре i486 он работает со скоростью 58 Мбит/с. SEAL возможно является самым быстрым из описанных в этой книге.
С другой стороны SEAL должен выполнить предварительную обработку, заполняя внутренние таблицы . Размер этих таблиц составляет примерно 3 Кбайт, а для их расчета нужно примерно 200 вычислений SHA. Таким образом, SEAL не подходит для тех случаев, когда не хватает времени для обработки ключа или памяти для хранения таблиц.
Безопасность SEAL
SEAL достаточно новый алгоритм, ему еще предстоит пройти через горнило открытого криптоанализа . Это вызывает определенную настороженность. Однако SEAL кажется хорошо продуманным алгоритмом. Его особенности, в конечном счете, наполнены смыслом. К тому же Дон Копперсмит считается лучшим криптоанали-тиком в мире.
C
-+ M |
B
-+ M |
A
P
K
ф-
C
Рис. 17-2. WAKE.
Самым ценным качеством WAKE является его скорость. Однако он чувствителен к вскрытию с выбранным открытым текстом или выбранным шифротекстом. Этот алгоритм использовался в предыдущей версии антивирусной программы д-ра Соломона.
17.4 Сдвиговые регистры с обратной связью по переносу
Сдвиговый регистр с обратной связью по переносу, или FCSR (feedback with carry shift register), похож на LFSR. В обоих есть сдвиговый регистр и функция обратной связи, разница в том, что в FCSR есть также регистр переноса (см. 14-й). Вместо выполнения XOR над всеми битами отводной последовательности эти биты скла-
дываются друг с другом и с содержимым регистра переноса. Результат mod 2 и становится новым битом. Результат, деленный на 2, становится новым содержимым регистра переноса .
Сдвиговый регистр
Сумма | mod | . . . | Выходной бит | |||||||||||||
оп | ьп- | £>4 | t>3 | t>2 | D | |||||||||||
Сумма | ||||||||||||||||
i----------- * | ||||||||||||||||
CyMMadiv 2
Рис. 17-3. Сдвиговый регистр с обратной связью по переносу.
На 13-й приведен пример 3-битового FCSR с ответвлениями в первой и второй позициях. Пусть его начальное значение 001, а начальное содержимое регистра переноса равно 0. Выходом будет является крайний правый бит сдвигового регистра.
Сдвиговый регистр | Регистр переноса |
0 0 1 | |
1 0 0 | |
0 1 0 | |
1 0 1 | |
1 1 0 | |
1 1 1 | |
0 1 1 | |
1 0 1 | |
0 1 0 | |
0 0 1 | |
0 0 0 | |
1 0 0 |
л ма | mod | Ь3 | |||||
t>2 | и | ||||||
Сумма | |||||||
Выходной бит
---- V
Сумма div 2
Рис. 17-4. 3-битовый FCSR.
Заметим, что конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом, равным 10 .
Стоит упомянуть и еще о нескольких моментах. Во первых, регистр переноса является не битом, а числом. Размер регистра переноса должен быть не меньше log2?, где t - это число ответвлений. В предыдущем примере
только три ответвления, поэтому регистр переноса однобитовый . Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения 0, 1, 2 или 3.
Во вторых, существует начальная задержка прежде, чем FCSR перейдет в циклический режим. В предыдущем примере никогда не повторяется только одно состояние. Для больших и более сложных FCSR задержка может быть больше.
В третьих, максимальный период FCSR не 2"' где п - длина сдвигового регистра. Максимальный период равен q-l, где q - это целое число связи.Это число задает ответвления и определяется как:
q = 2qi + 22q2 + 23q3 + . . . + 2nqn-l
(Да, q, отсчитываются слева направо.) И даже хуже, q должно быть простым числом, для которого 2 является примитивным корнем. В дальнейшем предполагается, что q удовлетворяет этому условию.
В приведенном примере q = 2*0 + 4*1 + 8*1 - 1 — И. И - это простое число, примитивным корнем которого является 2. Роэтому максимальный период равен 10.
Не все начальные состояния дают максимальный период. Например, рассмотрим FCSR с начальным значением 101 и регистром переноса, установленным в 4.
Сдвиговый регистр Регистр переноса
1 0 1 4
1 1 0 2
1 1 1 1
1 1 1 1
С этого момента регистр выплевывает бесконечную последовательность единиц .
Любое начальное состояние приводит к одной из четырех ситуаций . Во первых, оно может быть частью максимального периода. Во вторых, оно может перейти в последовательность максимального периода после н а-чальной задержки. В третьих, после начальной задержки оно может породить бесконечную последовательность нулей. В четвертых, после начальной задержки оно может породить бесконечную последовательность единиц .
Для определения, чем закончится конкретное начальное состояние, существует математическая формула, но намного проще проверить это опытным путем. Запустите на некоторое время FCSR. (Если т - это начальный объем памяти, a t - количество ответвлений, то достаточно log2(0 + log2(m) +1 тактов.) Если выходной поток вырождается в бесконечную последовательность нулей или единиц за п битов, где п - это длина FCSR, не используйте это начальное состояние. В противном случае его можно использовать . Так как начальное состояние FCSR соответствует ключу потокового шифра, это означает, что ряд ключей генератора на базе FCSR будут слабыми.
В 16-й перечислены все целые числа связи, меньшие 10000, для которых 2 является примитивным корнем . Для всех этих чисел максимальный период равен q-l. Чтобы получить по одному из этих чисел последовательность ответвлений, рассчитаем бинарный состав q+l. Например, 9949 дает последовательность ответвлений в позициях 1, 2, 3, 4, 6, 7, 9, 10 и 13, так как
9950 = 213 + 210 + 29 + 27 + 26 + 24 + 23 + 22 + 21
В 15-й перечислены все отводные последовательности из четырех ответвлений, которые дают FCSR максимальной длины для сдвиговых регистров с длиной 32 бита, 64 бита и 128 битов . q, простое число, примитивным корнем которого является 2, получается объединением всех четырех значений , a, b, cnd.
q = 2a + 2» + T + 2d -l
Для создания FCSR с периодом q - 1 можно использовать любую из этих последовательностей .
Идея использовать в криптографии FCSR все еще является очень новой, впервые она была выдвинута Энди Клаппером (Andy Klapper) и Марком Горески (Mark Goresky) [844, 845, 654, 843, 846]. Также, как анализ LFSR основан на сложении примитивных многочленов mod 2, анализ FCSR основан на сложении неких чисел, называемых 2-adic.Соответствующая теория выходит далеко за пределы этой книги, но в мире 2-adic чисел существуют аналоги для всего. Точно также, как определяется линейная сложность, можно определить и 2-adic сложность. Существует 2-adic аналог и для алгоритма Berlekamp-Massey. Это означает, что перечень возможных потоковых шифров по крайней мере удвоился. Все, что можно делать с LFSR, можно делать и с FCSR.
Существуют работы, развивающие эту идею и рассматривающие несколько регистров переноса . Анализ этих генераторов последовательностей основан на сложении разветвленных расширений 2-adic чисел [845, 846].
17.5 Потоковые шифры, использующие FCSR
Потоковые шифры на базе FCSR не описаны в литературе, теория все еще слишком нова. Чтобы как-то "погнать зайца дальше" я предложу здесь несколько вариантов . Я охватываю два направления: предлагаю потоковые шифры на базе FCSR, которые совпадают с ранее предложенными генераторами LFSR, а также предлагаю потоковые шифры, использующие FCSR и LFSR одновременно. Безопасность первого варианта возможно может быть проанализирована с помощью 2-adic чисел, генераторы второго варианта не могут быть проанализированы с использованием алгебраических методов - возможно их анализ может быть выполнен только косвенным образом. В любом случае, важно выбирать LFSR и FCSR с взаимно простыми периодами.
Все придет потом. Сейчас мне неизвестно ни о реализации, ни об анализе ни одной из этих идей . Подождите несколько лет и просматривайте литературу, прежде чем вы поверите в одну из этих идей .
Каскадные генераторы
Существует два способа использовать FCSR в каскадных генераторах:
— Каскад FCSR. Каскад Голлманна с FCSR вместо LFSR.
— Каскад LFSR/FCSR. Каскад Голлманна с генераторами, меняющими LFSR на FCSR и наоборот.
Табл. 17-2. Отводные последовательности для FCSR максимальной длины
(32, 6, 3, 2) | (32, 29, 19, 2) | (64, 27, 22, 2) | (64, 49, 19, 2) |
(32, 7, 5, 2) | (32, 29, 20, 2) | (64, 28, 19, 2) | (64, 49, 20, 2) |
(32, 8, 3, 2) | (32, 30, 3, 2) | (64, 28, 25, 2) | (64,52,29,2) |
(32, 13, 8, 2) | (32, 30, 7, 2) | (64, 29, 16, 2) | (64,53,8,2) |
(32, 13, 12, 2) | (32, 31, 5, 2) | (64, 29, 28, 2) | (64, 53, 43, 2) |
(32, 15, 6, 2) | (32, 31, 9, 2) | (64, 31, 12, 2) | (64, 56, 39, 2) |
(32, 16, 2, 1) | (32, 31, 30, 2) | (64, 32, 21, 2) | (64, 56, 45, 2) |
(32, 16, 3, 2) | (64, 35, 29, 2) | (64, 59, 5, 2) | |
(32, 16, 5, 2) | (64, 3, 2, 1) | (64, 36, 7, 2) | (64, 59, 8, 2) |
(32, 17, 5, 2) | (64,14,3,2) | (64, 37, 2, 1) | (64, 59, 28, 2) |
(32, 19, 2, 1) | (64,15,8,2) | (64, 37, 1 1, 2) | (64, 59, 38, 2) |
(32, 19, 5, 2) | (64, 17, 2, 1) | (64,39,4,2) | (64,59,44,2) |
(32, 19, 9, 2) | (64, 17, 9, 2) | (64, 39, 25, 2) | (64, 60, 49, 2) |
(32, 19, 12, 2) | (64, 17, 16, 2) | (64, 41, 5, 2) | (64, 61, 51, 2) |
(32, 19, 17, 2) | (64, 19, 2, 1) | (64, 41, 1 1, 2) | (64, 63, 8, 2) |
(32, 20, 17, 2) | (64, 19, 18, 2) | (64,41,27,2) | (64, 63, 13, 2) |
(32, 21, 9, 2) | (64, 24, 19, 2) | (64, 43, 21, 2) | (64, 63, 61, 2) |
(32, 21, 15, 2) | (64, 25, 3, 2) | (64, 43, 28, 2) | |
(32,23,8,2) | (64,25,4,2) | (64, 45, 28, 2) | (96, 15, 5. 2) |
(32, 23, 21, 2) | (64, 25, 1 1, 2) | (64, 45, 41, 2) | (96, 21, 17, 2) |
(32, 25, 5, 2) | (64, 25, 19, 2) | (64, 47, 5, 2) | (96, 25, 19, 2) |
(32, 25, 12, 2) | (64, 27, 5, 2) | (64, 47, 21, 2) | (96, 25, 20, 2) |
(32,27,25,2) | (64, 27, 16, 2) | (64, 47, 30, 2) | (96, 29, 15, 2) |
(96, 29, 17, 2) (96, 30, 3, 2) (96, 32, 21, 2) (96, 32, 27, 2) (96,33,5,2) (96, 35, 17, 2) (96, 35, 33, 2) (96, 39, 21, 2) (96,40,25,2) (96, 41, 12, 2) (96, 41, 27, 2) (96, 41, 35, 2) (96, 42, 35, 2) (96, 43, 14, 2) (96, 44, 23, 2) (96, 45, 41, 2) (96, 47, 36, 2) (96, 49, 31, 2) (96,51,30,2) (96,53,17,2) (96, 53, 19, 2) (96, 53, 32, 2) (96, 53, 48, 2) (96, 54, 15, 2) (96, 55, 44, 2) (96, 55, 53, 2) (96, 56, 9, 2) (96,56,51,2) (96, 57, 3, 2) (96, 57, 17, 2) (96, 57, 47, 2) (96, 58, 35, 2) (96, 59, 46, 2) (96, 60, 29, 2) (96, 60, 41, 2) (96, 60, 45, 2) (96, 61, 17, 2) (96, 63, 20, 2) (96, 65, 12, 2) (96, 65, 39, 2) (96, 65, 51, 2) (96, 67, 5, 2) (96, 67, 25, 2) (96,67,34,2) (96, 68, 5, 2) (96, 68, 19, 2) (96, 69, 17, 2) (96,69,36,2) (96, 70, 23, 2) (96, 71, 6, 2) (96, 71, 40, 2) (96, 72, 53, 2) (96, 73, 32, 2) (96, 77, 27, 2)
(96, 77, 31, 2) (96, 77, 32, 2) (96, 77, 33, 2) (96,77,71,2) (96,78,39,2) (96, 79, 4, 2) (96, 81, 80, 2) (96, 83, 14, 2) (96, 83, 26, 2) (96, 83, 54, 2) (96, 83, 60, 2) (96, 83, 65, 2) (96, 83, 78, 2) (96, 84, 65, 2) (96, 85, 17, 2) (96, 85, 31, 2) (96, 85, 76, 2) (96,85,79,2) (96,86,39,2) (96,86,71,2) (96, 87, 9, 2) (96, 87, 44, 2) (96, 87, 45, 2) (96, 88, 19, 2) (96, 88, 35, 2) (96, 88, 43, 2) (96,88,79,2) (96, 89, 35, 2) (96, 89, 51, 2) (96, 89, 69, 2) (96, 89, 87, 2) (96, 92, 51, 2) (96,92,71,2) (96, 93, 32, 2) (96, 93, 39, 2) (96, 94, 35, 2) (96, 95, 4, 2) (96, 95, 16, 2) (96, 95, 32, 2) (96, 95, 44, 2) (96, 95, 45, 2)
(128, 5, 4, 2) (128, 15, 4, 2) (128, 21, 19, 2) (128, 25, 5, 2) (128, 26, 11, 2) (128,27,25,2) (128, 31, 25, 2) (128, 33, 21, 2) (128, 35, 22, 2) (128, 37, 8, 2) (128, 41, 12, 2) (128, 42, 35, 2)
(128, 43, 25, 2) (128,43,42,2) (128,45,17,2) (128,45,27,2) (128, 49, 9, 2) (128, 51, 9, 2) (128, 54, 51, 2) (128, 55, 45, 2) (128, 56, 15, 2) (128, 56, 19, 2) (128,56,55,2) (128, 57, 21, 2) (128, 57, 37, 2) (128, 59, 29, 2) (128, 59, 49, 2) (128, 60, 57, 2) (128,61,9,2) (128, 61, 23, 2) (128, 61, 52, 2) (128, 63, 40, 2) (128, 63, 62, 2) (128, 67, 41, 2) (128, 69, 33, 2) (128, 71, 53, 2) (128, 72, 15, 2) (128,72,41,2) (128, 73, 5, 2) (128, 73, 65, 2) (128, 73, 67, 2) (128, 75, 13, 2) (128, 80, 39, 2) (128,80,53,2) (128, 81, 55, 2) (128, 82, 67, 2) (128, 83, 60, 2) (128, 83, 61, 2) (128, 83, 77, 2) (128, 84, 15, 2) (128, 84, 43, 2) (128,85,63,2) (128,87,57,2) (128,87,81,2) (128, 89, 81, 2) (128, 90, 43, 2) (128, 91, 9, 2) (128, 91, 13, 2) (128, 91, 44, 2) (128, 92, 35, 2) (128,95,94,2) (128, 96, 23, 2) (128, 96, 61, 2) (128, 97, 25, 2) (128, 97, 68, 2) (128, 97, 72, 2)
(128,97,75,2) (128, 99, 13, 2) (128, 99, 14, 2) (128, 99, 26, 2) (128, 99, 54, 2) (128, 99, 56, 2) (128, 99, 78, 2) (128, 100, 13, 2) (128, 100, 39, 2) (128,101,44,2) (128, 101, 97, 2) (128, 103, 46, 2) (128, 104, 13, 2) (128, 104, 19, 2) (128, 104, 35, 2) (128,105,7,2) (128, 105, 11, 2) (128, 105, 31, 2) (128, 105, 48, 2) (128, 107, 40, 2) (128, 107, 62, 2) (128, 107, 102, 2) (128, 108, 35, 2) (128,108,73,2) (128,108,75,2) (128,108,89,2) (128, 109, 1 1, 2) (128, 109, 108, 2) (128, 1 10, 23, 2) (128, Ill, 61, 2) (128, 113, 59, 2) (128, 114, 83, 2) (128,115,73,2) (128, 117, 105, 2) (128, 119, 30, 2) (128, 119, 101, 2) (128, 120, 9, 2) (128, 120, 27, 2) (128,120,37,2) (128, 120, 41, 2) (128, 120, 79, 2) (128, 120, 81, 2) (128, 121, 5, 2) (128, 121, 67, 2) (128, 121, 95, 2) (128, 121, 96, 2) (128, 123, 40, 2) (128,123,78,2) (128, 124, 41, 2) (128, 124, 69, 2) (128, 124, 81, 2) (128, 125, 33, 2) (128, 125, 43, 2) (128,127,121,2)
Регистр-1 | |
Регистр-2 | |
Регистр-3 | |
Регистр-л | |
Объединяющая функция | |
Рис. 17-5. Комбинированные генераторы.
Рис. 17-6. Придуманный генератор.
Генератор использует много регистров: п*т, где п - количество этапов, а т - количество регистров на этапе. Я рекомендую и = 10 и m = 5.
Чередующиеся генераторы "стоп-пошел"
Эти генераторы использую FCSR вместо некоторых LFSR. Кроме того, операция XOR может быть заменена сложением с переносом (см. 10-й).
— Генератор "стоп-пошел" FCSR. Регистр-1, Регистр-2 и Регистр-3 - это FCSR. Объединяющая функция -XOR.
— Генератор "стоп-пошел" FCSR/LFSR. Регистр-1 - FCSR, а Регистр-2 и Регистр-3 - LFSR. Объединяющая функция - сложение с переносом.
— Генератор "стоп-пошел" LFSR/FCSR. Регистр-1 - LFSR, а Регистр-2 и Регистр-3 - FCSR. Объединяющая функция - XOR.
Регистр-2
Регистр-1
->-
Объединяющая функция
Регистр-3
Рис. 17-7. Чередующийся генератор "стоп-пошел"
Прореживаемые генераторы
Существует четыре основных типа генераторов, использующих FCSR:
— Прореживаемый генератор FCSR. Прореживаемый генератор с FCSR вместо LFSR.
— Прореживаемый генератор FCSR/LFSR. Прореживаемый генератор с LFSR, прореживающим FCSR.
— Прореживаемый генератор LFSR/FCSR. Прореживаемый генератор с FCSR, прореживающим LFSR.
— Самопрореживаемый генератор FCSR. Самопрореживаемый генератор с FCSR вместо LFSR.
17.6 Сдвиговые регистры с нелинейной обратной связью
Нетрудно представить более сложную, чем используемая в LFSR или FCSR, последовательность обратной связи. Проблема в том, что не существует математического аппарата, позволяющего провести анализ таких п о-следовательностей. Что-то получится, но кто знает что? Вот некоторые из проблем, связанных со сдвиговыми регистрами с нелинейной обратной связью.
— В выходной последовательности могут быть смещения, например, единиц может быть больше, чем нулей.
— Максимальный период последовательности может быть меньше, чем ожидалось .
— Период последовательности для различных начальных значений может быть различным .
— Последовательность какое-то время может выглядеть как случайная, а потом "скатываться" к единстве н-ному значению. (Это можно легко устранить, выполняя XOR крайнего правого бита с нелинейной функцией.)
Плюсом является то, что из-за отсутствия теории анализа сдвиговых регистров с нелинейной обратной ев я-зью существует немного способов криптоанализировать потоковые шифры, основанные на таких регистрах . Использовать сдвиговые регистры с нелинейной обратной связью можно, но очень осторожно .
В сдвиговом регистре с нелинейной обратной связью функция обратной связи может быть произвольной (например, как на ).
У
--------- *(у~)4
—к * )4--------- —
н А )*-
->( * )■*-
(+-
Рис. 17-8. Сдвиговый регистр с нелинейной обратной связью (возможно небезопасный).
Ъъ
Ъг
I
—©"
Рис. 17-9. 3-битовый сдвиговый регистр с нелинейной обратной связью.
На 8-й показан 3-битовый генератор со следующей обратной связью: новым битом является произведение первого и второго битов. Если его проинициализировать значением 110, то последовательность внутренних состояний будет следующей:
1 1 0
0 1 1
1 0 1 0 1 0 0 0 1 0 0 0 0 0 0
И так до бесконечности. Выходом является последовательность младших значащих битов :
0 1 1 0 1 0 0 0 0 0 0 0___
Это не слишком полезно.
Может быть и хуже. Если начальное значение 100, то следующими состояниями являются 010, 001, а затем всегда 000. Если начальным значением является 111, то оно будет повторяться всегда и с самого начала.
Была проделана определенная работа по вычислению линейной сложности произведения двух LFSR [1650, 726, 1364, 630, 658, 659]. Конструкция, включающая вычисление LFSR над полем нечетных характеристик [310] не является безопасной [842.].
17.7 Другие потоковые шифры
В литературе описывались и другие потоковые шифры. Вот некоторые из них.
Генератор Плесса (Pless)
Этот генератор использует свойства J-K триггеров [1250]. Восемь LFSR управляют четырьмя J-K триггерами; каждый триггер нелинейно объединяет два LFSR. Чтобы избежать проблемы, что выход триггера определяет и источник, и значение следующего выходного бита, после тактирования четырех триггеров их в ы-ходы перемешиваются для получения окончательного потока ключей .
Этот алгоритм был криптоаналитически взломан с помощью вскрытия каждого триггера в отдельности
[1356]. К тому же, объединение J-K триггеров слабо криптографически; генераторы такого типа не устоят перед корреляционным вскрытием [1451].
Генератор на базе клеточного автомата
В [1608, 1609], Стив Вольфрам (Steve Wolfram) предложил использовать в качестве генератора псевдослучайных чисел одномерный клеточный автомат. Рассмотрение клеточного автомата не является предметом этой книги, но генератор Вольврама состоит из одномерного массива битов аъ а2, а3, ... , аь ..., an и функции обновления:
а£= акЛ © (ак v ak+l)
Бит извлекается из одного из значений ак, реально все равно какого.
Генератор ведет себя как вполне случайный. Однако для этих генераторов существует успешное вскрытие с известным открытым текстом [1052]. Это вскрытие выполнимо на PC со значениями п вплоть до 500 битов. Кроме того, Пол Барделл (Paul Bardell) доказал, что выход клеточного автомата может быть также сгенерир о-ван с помощью сдвигового регистра с линейной обратной связью той же длины и, следовательно, не дает бол ь-шей безопасности [83].
Генератор псевдослучайных чисел Шамира
Эди Шамир использовал в качестве генератора псевдослучайных чисел алгоритм RSA [1417]. Хотя Шамир показал, что предсказание выхода генератора псевдослучайных чисел равносильно взлому RSA, потенциальное смещение выхода была продемонстрирована в [1401, 200].
RSA
Этот генератор RSA [35, 36] является модификацией [200]. Начальные параметры - модуль N, произведение двух больших простых чисел р и q, и целое число е, относительно простое с (p-l)(q-l), а также стартовое случайное число х0, меньшее N.
x,+1 = xe,modiV
Выход генератора представляет собой младший значащий бит х,. Безопасность этого генератора опирается на сложность вскрытия RSA. Если N достаточно велико, то генератор безопасен. Дополнительная теория приведена в [1569, 1570, 1571, 30, 354].
Рис. 17-10. Шифр "Рип ван Винкль".
Табл. 17-3. Скорости шифрования нескольких потоковых шифров на i486SX/33 МГц
Алгоритм Скорость шифрования (Мбайт/с)
А5 5
PIKE62
RC4 164
SEAL 381
17.13 Генерация нескольких потоков из одного генератора псевдослучайной последовательности
Если нужно зашифровать несколько каналов связи при помощи одного блока - например, мультиплексора -простым решением является использование для каждого потока своего генератора псевдослучайной последов а-тельности. При этом возникают две следующих проблемы : нужна дополнительная аппаратура, и все генераторы должны быть синхронизированы. Проще было бы использовать один генератор.
Одно из решений - тактировать генератор несколько раз. Если нужно три независимых потока, тактируйте генератор три раза и отправьте по одному биту в каждый поток . Этот метод работает, но могут быть сложности при получении большой частоты. Например, если вы можете тактировать генератор только в три раза быстрее тактирования потока данных, вы сможете создать только три потока . Другим способом является использование одной и той же последовательности для каждого канала, возможно с переменной временной задержкой . Это небезопасно.
Действительно удачная идея [1489], запатентованная NSA, показана на 6-й. Записывайте выход вашего любимого генератора в простой от-битовый сдвиговый регистр. По каждому тактовому импульсу сдвигайте регистр на один бит вправо. Затем для каждого выходного потока выполните AND регистра с другим от-битовым вектором, рассматриваемым как уникальный идентификатор для выбранного выходного потока, затем объедините с помощью XOR все биты, получая выходной бит для этого потока. Если требуется получить параллельно несколько выходных потоков, для каждого выходного потока нужно использовать отдельный вектор и логический массив XOR/AND.
Гене | эатор | |||||||||||||
1--------------------------------------------------- ► | т-битовый выход | |||||||||||||
Вектор 1 Вектор 2 | Вектор п | |||||||||||||
I 1 | I I | I I | ||||||||||||
Побитовое | Побитовое | • • • | Побитовое | |||||||||||
AND | AND | AND | ||||||||||||
i | I | |||||||||||||
Побитовое | Побитовое | • • • | Побитовое | |||||||||||
XOR | XOR | XOR | ||||||||||||
Пот | эк1 | Поток 2 | Поток п |
Рис. 17-11. Генератор нескольких битов.
Существует ряд вещей, которые нужно отслеживать. Если любой из этих потоков является линейной комбинацией других потоков, то система может быть взломана. Но если вы достаточно аккуратны, описанный способ является простым и безопасным способом решения проблемы.
17.14 Генераторы реальных случайных последовательностей
Иногда криптографически безопасные псевдослучайные последовательности недостаточно хороши . В криптографии вам могут понадобиться действительно случайные числа. Первое, что приходит в голову - это генерация ключей. Прекрасно можно генерировать случайные криптографические ключи, используя генератор псевд о-случайных последовательностей, но если враг добудет копию этого генератора и главный ключ, он сможет со з-дать те же ключи и взломать вашу криптосистему, независимо от надежности ваших алгоритмов. Последовательность, выдаваемую генератором случайных последовательностей, воспроизвести невозможно . Никто, даже вы сами, не сможет воспроизвести последовательность битов, выдаваемую этими генераторами .
Крупной философской проблемой является вопрос о том, дают ли эти методы действительно случайные биты. Я не собираюсь ввязываться в этот спор. Здесь я рассматриваю выдачу битов, которые невозможно во с-произвести, и у которых статистические свойства как у случайных битов .
Для любого генератора действительно случайных последовательностей важным вопросом является его пр о-верка. На эту тему существует множество литературы. Тесты на случайность можно найти в [863, 99]. Маурер показал, что все эти тесты можно получить из попытки сжать последовательность [1031, 1032]. Если случайная последовательность сжимается, то она не является по настоящему случайной .
В любом случае, все, что мы имеем в этой области, во многом относится к черной магии . Главным моментом является генерация последовательности битов, которую не сможет угадать ваш противник . Это гораздо более трудная задача, чем кажется. Я не могу доказать, что любой из описанных методов генерирует случайные биты. Результатом их работы являются последовательности битов, которые невозможно легко воспроизвести . Подробности можно найти в [1375, 1376, 511].
– Конец работы –
Используемые теги: Объединение, блочных, шифров0.059
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Объединение блочных шифров
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов