Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 34 из 78

. Но какой?
16.7 Nanoteq
Nanoteq - это южноафриканская электронная компания . Именно этот алгоритм используется южноафрика н- ской полицией при шифровании передачи факсов, а возможно и для прочих нужд .
Более или менее этот алгоритм описан в [902, 903]. Он использует 127-битовый LFSR с фиксированным многочленом обратной связи, ключ представляет собой начальное состояние регистра . При помощи 25 элемен- тарных ячеек 127 битов регистра превращаются в один бит потока ключей . У каждой ячейки 5 входов и один выход:
f(x l
, x
2
, x
3
, x
4
, x
5
) = x l
+ x
2
+ (x l
+ x
3
) (x
2
+ x
4
+ x
5
) + (x l
+ x
4
) (x
2
+ x
3
) + x
5

Каждый выход функции подвергается операции XOR с некоторым битом ключа. Кроме того, существует секретная перестановка, зависящая от конкретной реализации и не описанная в статьях подробно . Этот алго- ритм доступен только в аппаратном виде .
Безопасен ли он? Я не уверен. Ряд интересных факсов, передаваемых между полицейскими участками, ин о- гда появлялся в либеральных газетах. Это вполне могло быть результатом американской, английской или сове т- ской разведывательной деятельности. Росс Андерсон (Ross Anderson) предпринял ряд первых шагов, криптоа- нализируя этот алгоритм в [46], я думаю, что скоро появятся новые результаты.
16.8 Rambutan
Rambutan - это английский алгоритм, разработанный Communications Electronics Security Croup ( Группа по безопасности электронных коммуникаций, одно из объединений, использованное CCHQ). Он продается только в виде аппаратного модуля и одобрен для защиты документов вплоть до грифа "Конфиденциально" . Сам алго- ритм засекречен, и микросхема не предназначена для широкой коммерческой продажи .
Rambutan использует 112-битовый ключ (плюс биты четности) и может работать трех режимах: ECB, CBC,
и 8-битовый CFB. Это сильный аргумент в пользу того, что этот алгоритм - блочный, но слухи утверждают иное. Предположительно это потоковый шифр с LFSR. У него пять приблизительно 80-битовых сдвиговых р е- гистров различной длины. Полиномы обратной связи значительно прорежены, в каждом из них всего лишь 10
отводов. Каждый сдвиговый регистр обеспечивает четыре входа для очень большой и сложной нелинейной функции, которая и выдает единственный бит .
Почему Rambutan? Возможно из-за фрукта, который колючий и неприступный снаружи, но мягкий и не ж- ный внутри. Но с другой стороны никакой причины может и не быть .
16.9 Аддитивные генераторы
Аддитивные генераторы (иногда называемые запаздывающими генераторами Фиббоначи ) очень эффек- тивны, так как их результатом являются случайные слова, а не случайные биты [863]. Сами по себе они не безопасны, но их можно использовать в качестве составных блоков для безопасных генераторов .
Начальное состояние генератора представляет собой массив n-битовых слов: 8-битовых слов, 16-битовых слов, 32-битовых слов, и т.д.: X
1
, X
2
, X
3
, ..., X
m
. Это первоначальное состояние и является ключом . i-ое слово генератора получается как
X
i
= (X
i-a
+ X
i-b
+ X
i-c
+ + X
i-m
) mod 2
n
При правильном выборе коэффициентов a, b, c, . . . , m период этого генератора не меньше 2
n
-1. Одним из требований к коэффициентам является то, что младший значащий бит образует LFSR максимальной длины.
Например, (55,24,0) - это примитивный многочлен mod 2 из 14-й. Это означает, что длина следующего адди- тивного генератора максимальна.
X
i
= (X
i-55
+X
i-24
) mod 2
n
Это работает, так как у примитивного многочлена три коэффициента . Если бы их было больше, для получе- ния максимальной длины потребовались бы дополнительные условия . Подробности можно найти в [249].
Fish
Fish - это аддитивный генератор, основанный на методах, используемых в прореживаемом генераторе [190].
Он выдает поток 32-битовых слов, которые могут быть использованы (с помощью XOR) с потоком открытого текста для получения шифротекста или с потоком шифротекста для получения открытого текста . Название алго- ритма представляет собой сокращение от Fibonacci shrinking generator - прореживаемый генератор Фиббоначи .
Во первых используйте два следующих аддитивных генератора . Ключом является начальные состояния этих генераторов.
A
i
= (A
i-55
+A
i-24
) mod 2 32
B
i
= (B
i-52
+B
i-19
) mod 2 32
Эти последовательности прореживаются попарно в зависимости от младшего значащего бита B
i
: если его значение равно 1, то пара используется, если 0 - игнорируется . C
j
- это последовательность используемых слов
Ai, а D
j
- это последовательность используемых слов B
i
. Для генерации двух 32-битовых слов-результатов K
2j и
K
2j+1
эти слова используются парами - C
2j
, C
2j+1
, D
2j
, D
2j+1
E
2j
= C
2j
? (D
2j
, ? D
2j+1
)

F
2j
= D
2j+1
? (E
j
, ? C
2j+1
)
K
2j
= E
2j
? F
2j
K
2j+1
= C
2j+1
? F
2j
Этот алгоритм быстр. на процессоре i486/33 реализация Fish на языке C шифрует данные со скоростью
15-Мбит/с. К сожалению он также не безопасен, порядок вскрытия составляет около 2 40
[45].
Pike
Pike - это обедненная и урезанная версия Fish, предложенная Россом Андерсоном, тем, кто взломал Fish
[45]. Он использует три аддитивных генератора . Например:
A
i
= (A
i-55
+A
i-24
) mod 2 32
B
i
= (B
i-57
+B
i-7
) mod 2 32
C
i
= (C
i-58
+C
i-19
) mod 2 32
Для генерации слова потока ключей взгляните на биты переноса при сложении . Если все три одинаковы (все нули или все единицы), то тактируются все три генератора. Если нет, то тактируются только два совпадающих генератора. Сохраните биты переноса для следующего раза. Окончательным выходом является XOR выходов трех генераторов.
Pike быстрее Fish, так как в среднем для получения результата нужно 2.75 действия, а не 3. Он также слиш- ком нов, чтобы ему доверять, но выглядит очень неплохо.
Mush
Mush представляет собой взаимно прореживающий генератор . Его работу объяснить легко [1590]. Возьмем два аддитивных генератора: A и B. Если бит переноса A установлен, тактируется B. Если бит переноса B уста- новлен, тактируется A. Тактируем A и при переполнении устанавливаем бит переноса. Тактируем B и при пере- полнении устанавливаем бит переноса. Окончательным выходом является XOR выходов A и B. Проще всего использовать те же генераторы, что и в Fish:
A
i
= (A
i-55
+A
i-24
) mod 2 32
B
i
= (B
i-52
+B
i-19
) mod 2 32
В среднем для генерации одного выходного слова нужно три итерации генератора . И если коэффициенты аддитивного генератора выбраны правильно и являются взаимно простыми, длина выходной последовательн о- сти будет максимальна. Мне неизвестно об успешных вскрытиях, но не забывайте, что этот алгоритм очень нов .
16.10 Gifford
Дэвид Джиффорд (David Gifford) изобрел потоковый шифр и использовал его для шифрования сводок нов о- стей в районе Бостона с 1984 по 1988 год [608, 607, 609]. Алгоритм использует единственный 8-байтовый р е- гистр: b
0
, b
1
, . . . , b
7
. Ключом является начальное состояние регистра . Алгоритм работает в режиме OFB, от- крытый текст абсолютно не влияет на работу алгоритма . (См. -1-й).

P
K
C
Сброс
Функция выхода
Сдвиг вправо на
1 бит "с приклеива нием"
Сдвиг влево на 1 бит
Рис. 16-17. Gifford.
Для генерации байта ключа k i
объединим b
0
и b
1
, а также объединим b
4
и b
7
. Перемножим полученные чис- ла, получая 32-битовое число. Третьим слева байтом и будет k i
Для обновления регистра возьмем b
1
и сдвинем вправо "с приклеиванием" на 1 бит следующим образом:
крайний левый бит одновременно и сдвигается, и остается на месте . Возьмем b
7
и сдвинем его на один бит вле- во, в крайней правой позиции должен появиться 0 . Выполним XOR измененного b
1
, измененного b
7
и b
0
. Сдви- нем первоначальный байт регистра на 1 бит вправо и поместим этот байт в крайнюю левую позицию .
В течение всего времени использования этот алгоритм оставался безопасным, но он был взломан в 1994 году
[287]. Оказалось, что многочлен обратной связи не был примитивным и, таким образом, мог быть вскрыт .
16.11 Алгоритм M
Это название дано Кнутом [863]. Алгоритм представляет собой способ объединить несколько псевдослуча й- ных потоков, увеличивая их безопасность . Выход одного генератора используется для выбора отстающего в ы- хода другого генератора [996, 1003]. На языке C:
#define ARR_SIZE (8192) /* например - чем больше, тем лучше */
static unsigned char delay[ ARRSIZE ] ;
unsigned char prngA( void )
long prngB( void ) ;
void init_algM( void ) {
long i ;
for ( i = 0 ; i < ARR_SIZE ; i++ )
delay[i] = prngA() ;
} /* lnlt_algM */
unsigned char alglM( void ) {
long j,v ;
j = prngB() % ARR_SIZE ; /* получить индекс delay[]*/
v = delay[j] ; /* получить возвращаемое значение */
delay[j] = prngA() ; /* заменить его */
return ( v ) ;
} /* algM */
Смысл состоит в том, что если prngA - действительно случайно, невозможно ничего узнать о prngB (и, сле- довательно, невозможно выполнить криптоанализ ). Если prngA имеет такой вид, что его криптоанализ может быть выполнен только, если его выход доступен в свою очередь (т.е., только если сначала был выполнен крип-

тоанализ prngB), а в противном случае оно по сути действительно случайно, то эта комбинация должна быть безопасной.
16.12 PKZIP
Алгоритм шифрования, встроенный в программу сжатия данных PKZIP, был разработан Роджером Щлафлы
(Roger Schlafly). Это потоковый шифр, шифрующий данные побайтно . По крайней мере этот алгоритм исполь- зуется в версии 2.04g. Я не могу ничего сказать о более поздних версиях, но если не было сделано никаких з а- явлений об обратном, можно считать с большой вероятностью, что алгоритм не изменился . Алгоритм использу- ет три 32-битовых переменных, инициализированных следующим образом :
K
0
= 305419896
K
1
= 591751049
K
2
= 878082192
Используется 8-битовый ключ K
3
, полученный из K
2
. Вот этот алгоритм (в стандартной нотации C):
C
i
=P
i
^ K
3
K
0
= crc32 (K
0
, P
i
)
K
1
= K
1
+ (K
0
& 0x000000ff)
K
1
= K
1
*134775813 + 1
K
2
= crc32 (K
2
, K
1
>> 24)
K
3
= ((K
2
| 2)* ((K
2
| 2)^1)) >> 8
Функция crc32 берет свое предыдущее значение и байт, выполняет их XOR и вычисляет следующее значение с помощью многочлена CRC, определенного 0xedb88320. На практике 256-элементная таблица может быть рас- считана заранее, и вычисление crc32 превращается в:
crc32 (a, b) = (a >> 8) ^ table [(a & 0xff) ? b ]
Таблица рассчитывается в соответствии с первоначальным определением crc32:
table [i] = crc32 (i, 0)
Для шифрования потока открытого текста сначала для обновления ключей зациклим байты ключа в алг о- ритме шифрования. Полученный шифротекст на этом этапе игнорируется . Затем побайтно зашифруем откры- тый текст. Открытому тексту предшествуют двенадцать случайных байтов, но это на самом деле неважно . Де- шифрирование похоже на шифрование за исключением того, что во втором действии алгоритма вместо P
i ис- пользуется C
i
Безопасность PKZIP
К сожалению она не слишком велика. Для вскрытия нужно от 40 до 2000 байтов известного открытого те к- ста, временная сложность вскрытия составит около 2 27
[166]. На вашем персональном компьютере это можно сделать за несколько часов. Если в сжатом файле используются какие-нибудь стандартные заголовки, получ е- ние известного открытого текста не представляет собой проблемы . Не используйте встроенное в PKZIP шифро- вание.

Глава 17
Другие потоковые шифры и генераторы настоящих случайных по- следовательностей
17.1 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: S
0
, S
1
, . . . , S
255
. Элементы представляют собой перестановку чисел от 0 до
255, а перестановка является функцией ключа переменной длины . В алгоритме применяются два счетчика, i и j,
с нулевыми начальными значениями.
Для генерации случайного байта выполняется следующее :
i = (i + 1) mod 256
j = (j + S
i
) mod 256
поменять местами S
i и Sj t = (S
i
+ S
j
) mod 256
K = S
t
Байт K используется в операции XOR с открытым текстом для получения шифротекста или в операции XOR
с шифротекстом для получения открытого текста . Шифрование выполняется примерно в 10 раз быстрее, чем
DES.
Также несложна и инициализация S-блока. Сначала заполним его линейно: S
0
= 0, S
1
= 1, . . . , S
255
= 255. За- тем заполним ключом другой 256-байтовый массив, при необходимости для заполнения всего массива повторяя ключ: K
0
, K
1
, . . . , K
255
. Установим значение индекса j равным 0. Затем:
for i = 0 to 255:
j = (j + S
i
+ K
i
) mod 256
поменять местами S
i и S
j
И это все. RSADSI утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу ,
что, по-видимому, в нем нет никаких коротких циклов, и что он в высокой степени нелинеен . (Опубликованных криптоаналических результатов нет. RC4 может находиться в примерно 2 1700
(256! * 256 2
) возможных состоя- ний: невероятное число.) S-блок медленно изменяется при использовании : i обеспечивает изменение каждого элемента, а j - что элементы изменяются случайным образом . Алгоритм настолько несложен, что большинство программистов могут закодировать его просто по памяти .
Эту идею можно обобщить на S-блоки и слова больших размеров. Выше была описана 8-битовая версия
RC4. Нет причин, по которым нельзя бы было определить 16-битовый RC4 с 16*16 S-блоком (100 K памяти) и
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-битовом ключе k и 32-битовом n SEAL
растягивает n в L-битовую строку k(n). L может принимать любое значение, меньшее 64 Кбайт . SEAL, по види- мому, использует следующее свойство: если k выбирается случайным образом, то k(n) должно быть вычисли- тельно неотличимо от случайной L-битовой функции n.
Практический эффект того, что SEAL является семейством псевдослучайных функций, состоит в том, что он удобен в ряде приложений, где неприменимы традиционные потоковые шифры . Используя большинство пото- ковых шифров, вы создаете однонаправленную последовательность битов : единственным способом определить i-ый бит, зная ключ и позицию i, является генерирование всех битов вплоть до i-ого. Отличие семейства псевдо- случайных функций состоит в том, что вы можете легко получить доступ к любой позиции потока ключей . Это очень полезно.
Представим себе, что вам нужно "закрыть" жесткий диск . Вы хотите зашифровать каждый 512-байтовый сектор. Используя семейство псевдослучайных функций, подобное SEAL, содержимое сектора n можно зашиф- ровать, выполнив его XOR с k(n). Это то же самое, как если бы была выполнена операция XOR всего диска с длинной псевдослучайной функцией, и любая часть этой длинной строки может быть независимо вычислена без всяких проблем.