Объединение блочных шифров

Глава 15

Объединение блочных шифров

Одним из способов объединения является многократное шифрование- для шифрования одного и того же блока открытого текста алгоритм шифрования… Повторное шифрование блока открытого текста одним и тем же ключом с помощью… 15.1 Двойное шифрование

15.2

Тройное шифрование с двумя ключами

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

C = E_Ki(D_K2(E_Ki(P))) P = D_Ki(E_Ki(D_Ki(C)))

Иногда такой режим называют шифрование-дешифрирование-шифрование(encrypt-decrypt-encrypt, EDE) [55]. Если блочный алгоритм использует и-битовый ключ, то длина ключа описанной схемы составляет 2л бит. Любопытный вариант схемы шифрование-дешифрирование-шифрование был разработан в IBM для совмести­мости с существующими реализациями алгоритма: задание двух одинаковых ключей эквивалентно одинарному шифрованию, этим ключом. Схема шифрование-дешифрирование-шифрование сама по себе не обладает ник а-кой безопасностью, но этот режим был использован для улучшения алгоритма DES в стандартах Х9.17 и ISO 8732 [55, 761].

К и К₂ чередуются для предотвращения описанного выше вскрытия "встреча посередине" . Если С = Е_к (Е_к (Е_к (Р))), то криптоаналитик для любого возможного К_х может заранее вычислить Е_к (Е_к (Р))

и затем выполнить вскрытие. Для этого потребуется только 2"⁺² шифрований.

Тройное шифрование с двумя ключами устойчиво к такому вскрытию . Но Меркл и Хеллман разработали другой способ размена памяти на время, который позволяет взломать этот метод шифрования за 2^й-1 действий, используя 2" блоков памяти [1075].

Для каждого возможного К₂ расшифруйте 0 и сохраните результат. Затем расшифруйте 0 для каждого воз­можного К_и чтобы получить Р. Выполните тройное шифрование Р, чтобы получить С, и затем расшифруйте С ключом К_х. Если полученное значение совпадает с значением (хранящемся в памяти), полученным при деши ф-рировании 0 ключом К₂, то пара К_х К₂ является возможным результатом поиска. Проверьте, так ли это. Если нет, продолжайте поиск.

Выполнение этого вскрытия с выбранным открытым текстом требует огромного объема памяти . Понадобит­ся 2" времени и памяти, а также 2^т выбранных открытых текстов. Вскрытие не очень практично, но все же чув­ствительность к нему является слабостью алгоритма.

Пауль ван Оорсчот (Paul van Oorschot) и Майкл Винер (Michael Wiener) преобразовали это вскрытие ко вскрытию с известным открытым текстом, для которого нужно р известных открытых текстов. В примере пред­полагается, что используется режим EDE.

(1) Предположить первое промежуточное значения а.

(2) Используя известный открытый текст, свести в таблицу для каждого возможного К_г второе промежуточ­ное значение Ъ, при первом промежуточном значении, равном а:

Ъ = D_Ki (С)

где С - это шифротекст, полученный по известному открытому тексту.

(3) Для каждого возможного К₂ найти в таблице элементы с совпадающим вторым промежуточным значение

b:

b = E_Ki (a)

(4) Вероятность успеха равно plm, где/; - число известных открытых текстов, а т - размер блока. Если совпа­дения не обнаружены, выберите другое а и начните сначала.

Вскрытие требует 2^й+> времени и р - памяти. Для DES это равно 2^по/р [1558]. Для р, больших 256, это вскрытие быстрее, чем исчерпывающий поиск.

Тройное шифрование с тремя ключами

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

C = E_Ki{D_Ki{E_Ki{P))) P = D_Ki(E_K2(D_Kj(Q))

Для наилучшего вскрытия с разменом памяти на время, которым является "встреча посередине", потребуется 2²" действий и 2" блоков памяти [1075]. Тройное шифрование с тремя независимыми ключами безопасно н а-столько, насколько на первый взгляд кажется безопасным двойное шифрование .

Тройное шифрование с минимальным ключом (ТЕМЕ)

Существует безопасный способ использовать тройное шифрование с двумя ключами, противостоящий описанному вскрытию и называемый Тройным шифрованием с минимальным ключом (Triple Encryption with Minimum Key, TEMK) [858]. Фокус в той, чтобы получить три ключа из: Х_г иХ₂.

K₂=E_Xi(D_X2(E_Xi(T₂))) K₃ = E_Xi(D_X2(E_Xi(T₃)))

Т_иТ₂и Т₃ представляют собой константы, которые необязательно хранить в секрете. Эта схема гарантирует, что для любой конкретной пары ключей наилучшим будет вскрытие с известным открытым текстом .

Режимы тройного шифрования

Недостаточно просто определить тройное шифрование, нужно выбрать один из способов его использования . Решение зависит от требуемых безопасности и эффективности . Вот два возможных режима тройного шифрова­ния:

Внутренний СВС:Файл три раза шифруется в режиме СВС (см. 14tha). Для этого нужно три различных IV.

C=E^S^C^-S=D^T^S^-T=E^P,®^) P=T^D^Tyj=S^E^-S=C^D^q)

Со, S₀ и Т₀ являются 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):

с;=М^(ЗД©с;._з)))

В этом случае С₀, С_л и С_₂ являются IV. Это не поможет при программной реализации, разве только при и с-пользовании параллельного компьютера.

К сожалению менее сложный режим является также и менее безопасным . Бихам проанализировал различ­ные режимы по отношению к дифференциальному криптоанализу и обнаружил, что безопасность внутреннего СВС по сравнению с однократным шифрованием увеличивается незначительно . Если рассматривать тройное шифрование как единый большой алгоритм, то внутренние обратные связи позволяют вводить внешнюю и из­вестную информацию внутрь алгоритма, что облегчает криптоанализ . Для дифференциальных вскрытий нужно огромное количество выбранных шифротекстов, что делает эти вскрытия не слишком практичными, но этих результатов должно хватить, чтобы насторожить параноидальных пользователей . Анализ устойчивости алго­ритмов к вскрытиям грубой силой и "встречей посередине" показал, что оба варианта одинаково безопасны [806].

Кроме этих существуют и другие режимы. Можно зашифровать файл один раз в режиме ЕСВ, затем дважды в СВС, или один раз в СВС, один в ЕСВ и еще раз в СВС, или дважды в СВС и один раз в ЕСВ. Бихам показал, что эти варианты не безопаснее, чем однократный DES, против вскрытия дифференциальным криптоанализом с выбранным открытым текстом [162]. Он не оставил больших надежд и для других вариантов . Если вы собирае­тесь применять тройное шифрование, используйте внешнюю обратную связь .

Варианты тройного шифрования

Прежде, чем появились доказательства того, что DES не образует группу, для многократного шифрования предлагались различные схемы. Одним из способов обеспечить то, что тройное шифрование не выродится в однократное, было изменение эффективной дины блока. Простым методом является добавление бита-заполнителя. Между первым и вторым, а также между вторым и третьим шифрованиями текст дополняется

строкой случайных битов (см. Рис. 15.2). Если РР - это функция дополнения, то: C = E_Ki(PP(E_K2(PP(E_Ki(P)))))

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

Открытый текст

■ ■

 

Шифрование

_^_^_:*^

ппппп

 

Запо

лнит ель

~~v------- ------- v-------- ------- v-------- ------- v-------- ------- ■-

■ ■

V .. А А

Шифрование

Запо

лнит ель

ддддд

<------- ~Y------- -------- Y-------- -------- Y------- -------- Y-------- -------- S

■ ■

 

Шифрование

Дшдп

Г------- ----- Y-------- ------- V-------- ------- -V-------- ------- -V-------- ------- -S

 

Шифротекст

■ ■

Рис. 15-2. Тройное шифрование с заполнением.

Другой метод, предложенный Карлом Эллисоном (Carl Ellison), использует некоторую функцию независи­мой от ключа перестановки между тремя шифрованиями . Перестановка должна работать с большими блоками -8 Кбайт или около этого, что делает эффективный размер бока для этого варианта равным 8 Кбайтам . При ус­ловии, что перестановка выполняется быстро, этот вариант ненамного медленнее, чем базовое тройное шифр о-вание.

С = Е_Къ (T(E_Ki (T(E_Ki (Р)))))

Г собирает входные блоки (до 8 Кбайт в длину) и использует генератор псевдослучайных чисел для их пер е-мешивания. Изменение одного бита входа приводит к изменению 8 байтов результата первого шифрования, к изменению до 64 байтов результата второго шифрования и к изменению до 512 байтов результата третьего шифрования. Если каждый блочный алгоритм работает в режиме СВС, как было первоначально предложено, то изменение единичного бита входа скорее всего приведет к изменению всего 8-килобайтового блока, даже если этот блок не является первым.

Самый последний вариант этой схемы отвечает на вскрытие внутреннего СВС, выполненное Бихамом, до­бавлением процедуры отбеливания, чтобы замаскировать структуру открытых текстов . Эта процедура представ­ляет собой потоковую операцию XOR с криптографически безопасным генератором псевдослучайных чисел и ниже обозначена как R. Г мешает криптоаналитику определить a priori, какой ключ используется для шифрова­ния любого заданного байта входа последнего шифрования . Второе шифрование обозначено пЕ (шифрование с циклическим использованием п различных ключей):

С = Е_Къ (R(T(nE_Ki (T(E_Ki (Р))))))

Все шифрования выполняются в режиме ЕСВ, используется не меньше и+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 = P_t®S_t ®T_t

St и Ti - внутренние переменные, а/,и/₂ - счетчики. Две копии блочного алгоритма работают в некотором гибридном режиме OFB/счетчик, а открытый текст, 5*, и T_t объединяются с помощью XOR. Ключи Кг и К₂ независимы. Результаты криптоанализа этого варианта мне неизвестны.

ЕСВ + OFB

Анализ этого метода проводился только в той работе, в которой он и был опубликован . Понятно, что он не слабее одинарного шифрования ЕСВ и возможно… Чтобы затруднить анализ идентичных блоков в одних и тех же местах различных… Мэтт Блэйз (Matt Blaze) разработал этот режим для своей UNIX Cryptographic File System (CFS, криптогра­фическая…

XDES?

В [1644, 1645] DES используется как компонент ряда блочных алгоритмов с увеличенными размерами кл ю-чей и блоков. Эти схемы никак не зависят от DES, и в них может использоваться любой блочный алгоритм .

Первый, xDES¹, представляет собой просто схему Luby-Rackoff с блочным шифром в качестве базовой функции (см. раздел 14.11). Размер блока в два раза больше размера блока используемого блочного фильтра, а размер ключа в три раза больше, чем у используемого блочного фильтра . В каждом из 3 этапов правая полови­на шифруется блочным алгоритмом и одним из ключей, затем выполняется XOR результата и левой половины, и половины переставляются.

Это быстрее, чем обычное тройное шифрование, так как тремя шифрованиями шифруется блок, длина кото­рого в два раза больше длины блока используемого блочного алгоритма. Но при этом существует простое вскрытие "встреча посередине", которое позволяет найти ключ с помощью таблицы размером 2 *, где к - это размер ключа блочного алгоритма. Правая половина блока открытого текста шифруется с помощью всех воз­можных значений К_и выполняется XOR с левой половиной открытого текста и полученные значения сохраня­ются в таблице. Затем правая половина шифротекста шифруется с помощью всех возможных значений К₃, и выполняется поиск совпадений в таблице. При совпадении пара ключей К_гиК_ъ- возможный вариант правого ключа. После нескольких повторений вскрытия останется только один кандидат. Таким образом, xDES¹ не яв­ляется идеальным решением. Даже хуже, существует вскрытие с выбранным открытым текстом, доказывающее, что xDES¹ не намного сильнее используемого в нем блочного алгоритма [858].

по размеру равен блоку используемого блочного шифра, а все 10 ключей

В xDES² эта идея расширяется до 5-этапного алгоритма, размер блока которого в 4 раза, а размер ключа в 10 раз превышают размеры блока и ключа используемого блочного шифра . На 11th показан один этап xDES², каж­дый из четырех подблоков независимы.

 

 

 

 

 

 

				С
1	'	Ек,	-		Екг	-
	t	J*

Рис. 15-4. Один этап xDES2.

К тому же, эта схема быстрее, чем тройное шифрование: для шифрования блока, который в четыре раза больше блока используемого блочного шифра, нужно 10 шифрований . Однако этот метод чувствителен к диф­ференциальному криптоанализу [858] и использовать его не стоит. Такая схема остается чувствительной к диф­ференциальному криптоанализу, даже если используется DES с независимыми ключами этапов.

Для i > 3 xDES' вероятно слишком велик, чтобы использовать его в качестве блочного алгоритма . Например, размер блока для xDES³ в 6 раз больше, чем у лежащего в основе блочного шифра, ключ в 21 раз длиннее, а для шифрования блока, который в 6 раз длиннее блока лежащего в основе блочного шифра, нужно 21 шифрование .

Это медленнее, чем тройное шифрование.

Пятикратное шифрование

C = EKi(DK2(EKi(DK2(EKi(P))))) P = DKi(EK2(DKi(EK2(DKi(Q)))) Эта схема обратно совместима с тройным шифрованием, если Кг =К2,ис однократным шифрованием, если КХ=К2 = Къ. Конечно,…

Глава 16

Генераторы псевдослучайных последовательностей

Шифры

И потоковые

Линейными конгруэнтными генераторамиявляютсягенераторы следующей формы Хп = (аХпЛ + Ъ) mod m в которых Х„ - это й-ый член последовательности, аХ„л - предыдущий член последовательности. Перемен­ные a, bum -…

Табл. 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].

Объединение линейных конгруэнтных генераторов

static long si = 1 ; /* "long" должно быть 32-битовым целым. */ static long s2 = 1 ; #define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if (s<0) s+=m ; … /* MODMIJLT(a,b,c,nl,s) рассчитывает s*b mod m при условии, что m=a*b+c и 0 <= с < m. */

Сдвиговый регистр с обратной связьюсостоит из двух частей: сдвигового регистра и функции обратной

            ----         …             …

Рис. 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, но не является делителем x^d+ для всех 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:

х³² +х⁷ +х⁵ +х³ +х² +х+ 1

Это можно легко обобщить для LFSR с максимальным периодом. Первым числом является длина LFSR. По­следнее число всегда равно 0, и его можно опустить. Все числа, за исключением 0, задают отводную последов а-тельность, отсчитываемую от левого края сдвигового регистра. То есть, члены многочлена с меньшей степенью соответствуют позициям ближе к правому краю регистра.

Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра но­вый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и пер­вого битов (см. 12th), получающийся LFSR будет иметь максимальную длину, циклически проходя до повтор е-ния через 2³²-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

если примитивен х^а + х» + х^с + x^d + 1, то примитивен и х^а + x^a'^d + х^а'^с + х^а'^ъ + 1

Быстрее всего программно реализуются примитивные трехчлены, так как для генерации нового бита тужно выполнять XOR только двух битов сдвигового регистра. Действительно, все многочлены обратной связи, при­веденные в 14-й, являются разреженными,то есть, у них немного коэффициентов. Разреженность всегда пред­ставляет собой источник слабости, которой иногда достаточно для вскрытия алгоритма . Для криптографических алгоритмов гораздо лучше использовать плотныепримитивные многочлены, те, у которых много коэффициен­тов. Применяя плотные многочлены, особенно в качестве части ключа, можно использовать значительно более короткие LFSR.

Генерировать плотные примитивные многочлены по модулю 2 нелегко . В общем случае для генерации при­митивных многочленов степени к нужно знать разложение на множители числа 2*-1. Примитивные многочлены можно найти в следующих трех хороших работах: [652, 1285, 1287].

Сами по себе LFSR являются хорошими генераторами псевдослучайных последовательностей, но они обл а-дают некоторыми нежелательными неслучайными свойствами . Последовательные биты линейны, что делает их бесполезными для шифрования. Для LFSR длины п внутреннее состояние представляет собой предыдущие п выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2й выходным битам генератора с помощью высоко эффективного алгоритма Berlekamp-Massey [1082,1083]: см. раздел 16.3.

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

Программная реализация LFSR

Схему обратной связи LFSRмoжнo модифицировать. Получающийся генератор не будет криптографически более надежным, но он все еще будет обладать… #define mask 0x80000057 static unsigned long ShiftRegister=l; void seedJLFSR (unsigned long seed) {

И

■ ■ ■ ■

Be

Ь₄

 

Ьз

bi

Ь₂

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, еще больше. Иногда удивляешься тому, что самые простые из них предлага­ются снова и снова.

Линейная сложность

Эта идея можно расширить с полей на кольца [1298] и на случаи, когда выходная последовательность рас­сматривается как числа в поле нечетной… цифических условиях [597, 595, 596, 1333]. Обобщение понятия линейной… В любом случае помните, что высокая линейная сложность не обязательно гарантирует безопасность генер а-тора, но низкая…

Генератор Геффа

Ъ = (ах л а2) ©((­«0л аъ) Мультиплексор 2в1   LFSR-2  

Рис. 16-6. Генератор Геффа.

Если длины LFSR равны п_и п₂ и п₃, соответственно, то линейная сложность генератора равна

(щ+ 1)п₂ + щщ,

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

Хотя этот генератор неплохо выглядит на бумаге, он криптографически слаб и не может устоять против кор­реляционного вскрытия [829, 1638]. В 75 процентах времени выход генератора равен выходу LFSR-2. Поэтому, если известны отводные последовательности обратной связи, можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра. Тогда можно подсчитать, сколько раз выход LFSR совпадает с выходом генератора. Если начальное значение определено неверно, две последовательности будут согласовываться в 50 процентах времени, а если правильно, то в 75 процентах времени .

Аналогично, выход генератора равен выходу LFSR в 75 процентах времени. С такими корреляциями генера­тор потока ключей может быть легко взломан. Например, если примитивные многочлены состоят только из трех членов, и длина самого большого LFSR равна и, для восстановления внутренних состояний всех трех LFSR нужен фрагмент выходной последовательности длиной 37и битов [1639].

Обобщенный генератор Геффа

  Мультиплексор ПВ1 Выбор           • • •

Рис. 16-7. Обобщенный генератор Геффа.

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

Генератор Дженнингса В этой схеме мультиплексо управдр<»|Ы]| LFSR31, BijffapaeT

a

С

LFSR-1

Тактирован

К,

тся дл:

истюльзуЕ!

функция, которая отобр 1ждет выход LFSR-2 на вход^щ^мтш.^'ссора (см. 8th)

объединения двух LFSR [778, 779, 780]. Мультиплексор, 1 бит LFSK-2 в качествеч©ыбГ^оттного выходного бита. Кроме того, используется

К2

> b(t)

 

К₃

LFSR-2

Рис. 16-8. Генератор Дженнингса.

Ключом является начальное состояние двух LFSR и функции отображения. Хотя у этого генератора замеча­тельные статистические свойства, он пал перед выполненным Россом Андерсоном (Ross Anderson) вскрытием корректности встречей посередине [39] и вскрытием линейной корректности [1638,442]. Не используйте этот генератор.

Генератор "стоп-пошел" (Stop-and-Go) Both-Piper

  Lror-£ ai(t)   LFSR-1 a,(t) Д          

Рис. 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], "в такой системе не оче­видная избыточность ключа не наблюдается".

Пороговый генератор

Этот генератор показан на 4-й. Возьмите выход большого числа LFSR (используя нечетное число регистров). Для получения максимального периода…         LFSR-2 …         LFSR-3  

Рис. 16-12. Пороговый генератор.

Для трех LFSR выход генератора можно представить как:

Ъ = (а_х л а₂) © (й!л а_ъ) © (а₂ л а_ъ)

Это очень похоже на генератор Геффа за исключением того, что пороговый генератор обладает большей л и-нейной сложностью

щпг + й1йз + п₂п₃

где п_и п₂ип₃ - длины первого, второго и третьего LFSR.

Этот генератор не слишком хорош. Каждый выходной бит дает некоторую информацию о состоянии LFSR -точнее 0.189 бита - и генератор в целом не может устоять перед корреляционным вскрытием . Я не советую ис­пользовать такой генератор.

Самопрореживающие (Self-Decimated) генераторы

Ф

Рис. 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 - отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной

п₂+ п₂ + log₂d

Суммирующий генератор

Еще одно предложение Рэйнер Рюппела, этот генератор суммирует выходы двух LFSR (с переносом) [1358, 1357]. Это в высокой степени нелинейная операция. В конце 80-х этот генератор был лидером в отношении безопасности, но он пал перед корреляционным вскрытием [1053, 1054, 1091]. Кроме того, было показано, что этот генератор является частным случаем обратной связи, использующей сдвиговый регистр с переносом (см.

раздел 17.4), и может быть взломан [844].

DNRSG

Это означает "динамический генератор случайной последовательности" ("dynamic random-sequence genera­tor") [1117]. Идея состоит в том, чтобы взять два различных фильтруемых генератора - пороговых, суммиру то­щих, и т.п. - использующих один набор LFSR, а управляемых другим LFSR.

Сначала тактируются все LFSR. Если выходом LFSR-0 является 1, то вычисляется выход первого фильт­рующего генератора. Если выходом LFSR-0 является 0, то вычисляется выход второго фильтрующего генерато­ра. Окончательным результатом является XOR выходов первого и второго генераторов.

Каскад Голлманна

п(2" - If1 f f • • LFSR-1   __ I

Ф

Рис. 16-16. Каскад Голлманна.

Это дерзкая идея: концептуально они очень просты и могут быть использованы для генерации последов а-тельностей с огромными периодами, огромными линейными сложностями и хорошими статистическими сво й-ствами. Они чувствительны к вскрытию, называемому запиранием(lock-in) [640] и представляющему метод, с помощью которого сначала криптоаналитик восстанавливает вход последнего сдвигового регистра в каскаде , а затем взламывает весь каскад, регистр за регистром. В некоторых случаях это представляет собой серьезную проблему и уменьшает эффективную длину ключа алгоритма, но для минимизации возможности такого вскры­тия можно предпринять ряд определенных мер.

[637, 638, 642, к не

использовать

Дальнейший анализ показал, что с ростом к последовательность приближается к случайной 639]. На основании недавних вскрытий коротких каскадов Голлманна [1063], я советую меньше 15. Лучше использовать больше коротких LFSR, чем меньше длинных LFSR.

Прореживаемый генератор

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

Самопрореживаемый генератор

го, он работает в два раза медленнее. Хотя самопрореживаемый генератор также кажется безопасным, он может вести себя… 16.5 А5

Pike

Pike - это обедненная и урезанная версия Fish, предложенная Россом Андерсоном, тем, кто взломал Fish [45]. Он использует три аддитивных генератора. Например:

A^iAt.ss+At.rimodl³²

B_t = {B_t.si+B_U1) той?¹

C, = (C,,₅₈ +C,-₁₉jmod 2³²

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

Pike быстрее Fish, так как в среднем для получения результата нужно 2.75 действия, а не 3. Он также слиш­ком нов, чтобы ему доверять, но выглядит очень неплохо.

Mush

Mush представляет собой взаимно прореживающий генератор . Его работу объяснить легко [1590]. Возьмем два аддитивных генератора: А и В. Если бит переноса А установлен, тактируется В. Если бит переноса В уста­новлен, тактируется А. Тактируем А и при переполнении устанавливаем бит переноса. Тактируем В и при пере­полнении устанавливаем бит переноса. Окончательным выходом является XOR выходов А и В. Проще всего использовать те же генераторы, что и в Fish:

А^Ц^+А^той!³²

S, = (S,_₅₂ +iWmod 2³²

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

16.10 Gifford

Дэвид Джиффорд (David Gifford) изобрел потоковый шифр и использовал его для шифрования сводок нов о-стей в районе Бостона с 1984 по 1988 год [608, 607, 609]. Алгоритм использует единственный 8-байтовый р е-гистр: Ь₀, Ъ_ъ . . . , Ъ_ъ Ключом является начальное состояние регистра. Алгоритм работает в режиме OFB, от­крытый текст абсолютно не влияет на работу алгоритма. (См. -1-й).

*Сброс

 

Рис. 16-17. Gifford.

Для генерации байта ключа к, объединим Ь₀ и Ь_и а также объединим Ь₄ и Ь_ъ Перемножим полученные чис­ла, получая 32-битовое число. Третьим слева байтом и будет *,-.

Для обновления регистра возьмем Ъ_х и сдвинем вправо "с приклеиванием" на 1 бит следующим образом: крайний левый бит одновременно и сдвигается, и остается на месте . Возьмем Ь, и сдвинем его на один бит вле­во, в крайней правой позиции должен появиться 0. Выполним XOR измененного Ъ_ъ измененного Ъ, и Ь₀. Сдви­нем первоначальный байт регистра на 1 бит вправо и поместим этот байт в крайнюю левую позицию .

В течение всего времени использования этот алгоритм оставался безопасным, но он был взломан в 1994 году [287]. Оказалось, что многочлен обратной связи не был примитивным и, таким образом, мог быть вскрыт .

Алгоритм М

#define ARR_SIZE (8192) /* например - чем больше, тем лучше */ static unsigned char delay! ARRSIZE ] ; unsigned char prngA( void ) long prngB( void… long i ; for ( i = 0 ; i < ARR_SIZE ; i++ ) delay[i] = prngAO ; } /* lnlt_algM */ unsigned char alglM( void ) {

PKZIP

Алгоритм шифрования, встроенный в программу сжатия данных PKZIP, был разработан Роджером Щлафлы (Roger Schlafly). Это потоковый шифр, шифрующий данные побайтно. По крайней мере этот алгоритм исполь­зуется в версии 2.04g. Я не могу ничего сказать о более поздних версиях, но если не было сделано никаких з а-явлений об обратном, можно считать с большой вероятностью, что алгоритм не изменился . Алгоритм использу­ет три 32-битовых переменных, инициализированных следующим образом :

К₀ = 305419896

#!= 591751049

К_г = 878082192

Используется 8-битовый ключ К₃, полученный из К₂. Вот этот алгоритм (в стандартной нотации С):

G=Pi^AK₃

К₀= сгс32 (К₀, Р,)

Ку= К_х+ (К₀ & OxOOOOOOff)

K₁ =i:₁*134775813 + l

К₂ = сгс32 (К₂, К_х » 24)

К₃ = ((К₂ | 2)* ((К₂ | 2)^л1)) » 8

Функция сгс32 берет свое предыдущее значение и байт, выполняет их XOR и вычисляет следующее значение с помощью многочлена CRC, определенного 0xedb88320. На практике 256-элементная таблица может быть рас­считана заранее, и вычисление сгс32 превращается в:

сгс32 (а, Ь) = (а » 8) ^л table [(а & Oxff) © Ъ ]

Таблица рассчитывается в соответствии с первоначальным определением сгс32:

table [г] = crc32 (i, 0)

Для шифрования потока открытого текста сначала для обновления ключей зациклим байты ключа в алг о-ритме шифрования. Полученный шифротекст на этом этапе игнорируется. Затем побайтно зашифруем откры­тый текст. Открытому тексту предшествуют двенадцать случайных байтов, но это на самом деле неважно . Де­шифрирование похоже на шифрование за исключением того, что во втором действии алгоритма вместо Р, ис­пользуется С,.

Безопасность PKZIP

К сожалению она не слишком велика. Для вскрытия нужно от 40 до 2000 байтов известного открытого те к-ста, временная сложность вскрытия составит около 2²⁷ [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, . . . , S₂₅5- Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины . В алгоритме применяются два счетчика, i nj, с нулевыми начальными значениями.

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

i = (i +l) mod 256

j =G + &) mod 256

поменять местами S_t и Sj

t = (St + Sj) mod 256

K = S_t

Байт К используется в операции XOR с открытым текстом для получения шифротекста или в операции XOR с шифротекстом для получения открытого текста. Шифрование выполняется примерно в 10 раз быстрее, чем DES.

Также несложна и инициализация S-блока. Сначала заполним его линейно: S₀ = 0, Si = 1, . . . , 6*255 = 255. За­тем заполним ключом другой 256-байтовый массив, при необходимости для заполнения всего массива повторяя ключ: Ко, К_ъ. . . , К₂₅₅. Установим значение индекса; равным 0. Затем:

for г = 0 to 255:

j =G + Si + К,) mod 256

поменять местами S_t и Sj

И это все. RSADSI утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу , что, по-видимому, в нем нет никаких коротких циклов, и что он в высокой степени нелинеен . (Опубликованных криптоаналических результатов нет. RC4 может находиться в примерно 2¹⁷⁰⁰ (256! * 256²) возможных состоя­ний: невероятное число.) 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. Итерация за­вершается прибавлением к А и С дополнительных значений, зависящих от п, щ, п₂, щ, щ, выбор конкретного значения определяется четностью номера итерации. По видимому, при разработке этой схемы главными были следующие идеи:

1. Использование большого, секретного, получаемого из ключа S-блока (7).

2. Чередующиеся некоммутируемые арифметические операции (сложение и XOR).

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

4. Изменение функции этапа в соответствии с номером этапа и изменение функции итерации в соотве т-ствии с номером итерации.

Для шифрования каждого байта текста SEAL требует около пяти элементарных операций. На 50-мегагерцовом процессоре i486 он работает со скоростью 58 Мбит/с. SEAL возможно является самым быстрым из описанных в этой книге.

С другой стороны SEAL должен выполнить предварительную обработку, заполняя внутренние таблицы . Размер этих таблиц составляет примерно 3 Кбайт, а для их расчета нужно примерно 200 вычислений SHA. Та­ким образом, SEAL не подходит для тех случаев, когда не хватает времени для обработки ключа или памяти для хранения таблиц.

Безопасность SEAL

SEAL достаточно новый алгоритм, ему еще предстоит пройти через горнило открытого криптоанализа . Это вызывает определенную настороженность. Однако SEAL кажется хорошо продуманным алгоритмом. Его осо­бенности, в конечном счете, наполнены смыслом. К тому же Дон Копперсмит считается лучшим криптоанали-тиком в мире.

Патенты и лицензии

17.3 WAKE WAKE - сокращение от Word Auto Key Encryption (Автоматическое шифрование слов… WAKE работает в режиме CFB, для генерации следующего слова ключа используется предыдущее слово шифротекста. Алгоритм…

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 .

Стоит упомянуть и еще о нескольких моментах. Во первых, регистр переноса является не битом, а числом. Размер регистра переноса должен быть не меньше log₂?, где t - это число ответвлений. В предыдущем примере

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

Во вторых, существует начальная задержка прежде, чем FCSR перейдет в циклический режим. В предыду­щем примере никогда не повторяется только одно состояние. Для больших и более сложных FCSR задержка может быть больше.

В третьих, максимальный период FCSR не 2"' где п - длина сдвигового регистра. Максимальный период равен q-l, где q - это целое число связи.Это число задает ответвления и определяется как:

q = 2q_i + 2²q₂ + 2³q₃ + . . . + 2ⁿq_n-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 - количество ответвлений, то достаточно log₂(0 + log₂(m) +1 тактов.) Если выходной поток вырождается в бесконечную последовательность нулей или единиц за п битов, где п - это длина FCSR, не ис­пользуйте это начальное состояние. В противном случае его можно использовать . Так как начальное состояние FCSR соответствует ключу потокового шифра, это означает, что ряд ключей генератора на базе FCSR будут слабыми.

В 16-й перечислены все целые числа связи, меньшие 10000, для которых 2 является примитивным корнем . Для всех этих чисел максимальный период равен q-l. Чтобы получить по одному из этих чисел последователь­ность ответвлений, рассчитаем бинарный состав q+l. Например, 9949 дает последовательность ответвлений в позициях 1, 2, 3, 4, 6, 7, 9, 10 и 13, так как

9950 = 2¹³ + 2¹⁰ + 2⁹ + 2⁷ + 2⁶ + 2⁴ + 2³ + 2² + 2¹

В 15-й перечислены все отводные последовательности из четырех ответвлений, которые дают FCSR макси­мальной длины для сдвиговых регистров с длиной 32 бита, 64 бита и 128 битов . q, простое число, примитивным корнем которого является 2, получается объединением всех четырех значений , a, b, cnd.

q = 2^a + 2» + T + 2^d -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 и наоборот.

Комбинированные генераторы FCSR

Другими генераторами, являющимися развитием аналогичных линий, являются : — Генератор четности FCSR. Все регистры - FCSR, а объединяющая функция -… — Генератор четности LFSR/FCSR. Используется смесь LFSR и FCSR, объединяемых с помощью XOR.

Табл. 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. Комбинированные генераторы.

Каскад LFSR/FCSR с суммированием/четностью

Генератор представляет собой последовательность массивов регистров , тактирование каждого массива опре­деляется выходом предыдущего массива. На 11-й…   LFSR А   Сумматор с переносом …   --------------- ►

Рис. 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--------- —

н ^А )*-

->( * )■*-

(+-

Рис. 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) предложил использовать в качестве генератора псевдослу­чайных чисел одномерный клеточный автомат. Рассмотрение клеточного автомата не является предметом этой книги, но генератор Вольврама состоит из одномерного массива битов а_ъ а₂, а₃, ... , а_ь ..., an и функции обнов­ления:

а£= а_кЛ © (а_к v a_k+l)

Бит извлекается из одного из значений а_к, реально все равно какого.

Генератор ведет себя как вполне случайный. Однако для этих генераторов существует успешное вскрытие с известным открытым текстом [1052]. Это вскрытие выполнимо на PC со значениями п вплоть до 500 битов. Кроме того, Пол Барделл (Paul Bardell) доказал, что выход клеточного автомата может быть также сгенерир о-ван с помощью сдвигового регистра с линейной обратной связью той же длины и, следовательно, не дает бол ь-шей безопасности [83].

Генератор 1/р

хм=Ъх,то&р Выходом генератора является младший значащий бит xt div р, где div - это… crypt(l)

Другие схемы

17.8 Системно-теоретический подход к проектированию потоковых шифров На практике, проектирование потокового шифра во многом похоже проектирование… Согласно Райнеру Рюппелу существует четыре различных подхода к проектированию потоковых шифров [1360, 1362]:

Генератор псевдослучайных чисел Шамира

Эди Шамир использовал в качестве генератора псевдослучайных чисел алгоритм RSA [1417]. Хотя Шамир показал, что предсказание выхода генератора псевдослучайных чисел равносильно взлому RSA, потенциальное смещение выхода была продемонстрирована в [1401, 200].

Генератор Blum-Micali

Выходом генератора является 1, если х,< (р- 1)/2, и 0 в противном случае. Если/; достаточно велико, чтобы вычисление дискретных логарифмов то Ар стало…

RSA

Этот генератор RSA [35, 36] является модификацией [200]. Начальные параметры - модуль N, произведение двух больших простых чисел р и q, и целое число е, относительно простое с (p-l)(q-l), а также стартовое слу­чайное число х₀, меньшее N.

x,₊₁ = x^e,modiV

Выход генератора представляет собой младший значащий бит х,. Безопасность этого генератора опирается на сложность вскрытия RSA. Если N достаточно велико, то генератор безопасен. Дополнительная теория приве­дена в [1569, 1570, 1571, 30, 354].

Blum, Blum, and Shub

Теория генератора BBS использует квадратичные остатки по модулю п (см. раздел 11.3). Вот как он работает. Сначала найдем два простых числа, р и q, которые конгруэнтны 3 modulo 4.… x0 = x2 modH

Рис. 17-10. Шифр "Рип ван Винкль".

Рандомизированный потоковый шифр Диффи

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

Рандомизированный потоковый шифр Маурера

ется оцифровка поверхности Луны. 17.11 Шифры с каскадом нескольких потоков Если производительность не важна, то нет причин выбирать несколько потоковых шифров и объединять их в каскад. Для…

Табл. 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].

Таблицы RAND

Случайные цифры этой книги были получены при помощи рандомизации основной таблицы, сгенерированной эле к-тронной рулеткой. Вкратце, источник… Вкниге рассматривались и результаты различных проверок данных на случайность .… Строки таблицы цифр нумеруются от 00000 до 19999. При использовании таблицы нужно сначала выбрать случайную стартовую…

Использование случайного шума

Найдите событие, которое случается регулярно, но случайно: атмосферный шум, преодолевающий какой-то порог, ребенок, падающий, учась ходить. Измерьте… Бросьте стрелу дартс в перечень котировок Нью-Йоркской фондовой бирже в… Подключите к компьютеру счетчик Гейгера, подсчитайте количество импульсов за фиксированный интервал времени и возьмите…

Использование таймера компьютера

Не стоит извлекать таким образом слишком много битов . Выполнение много раз одной и той же процедуры последовательно может легко сместить биты,… Наш генератор действительно случайных чисел . . . работает, устанавливая… Этот метод очень чувствителен к случайности системных прерываний и квантованности таймера . При тести­ровании на…

Измерение скрытого состояния клавиатуры

В идеале вы должны по каждому нажатию клавиши генерировать только один бит . Использование большего количества битов может сместить результаты в…

Смещения и корреляции

Способом устранить смещение,или отклонение, является XOR нескольких битов друг с другом. Если слу­чайный бит смещен к 0 на величину е, то… Р(0) = 0.5 + е XOR двух из таких битов дает:

Развернуть

Открыть в широком формате