Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[85]

14.6 CRAB

Этот алгоритм был разработан Бертом Калиски [Burt Kaliski] и Мэттом Робшоу [Matt Robshaw] из RSA Laboratories [810]. В основе Crab лежит идея использовать методы однонаправленных хэш-функций для созд а-ния быстрого алгоритма шифрования. Следовательно, Crab очень похож на MD5, и в этом разделе предполаг а-ется, что вы знакомы с материалом раздела 18.5.

У Crab очень большой блок: 1024 байта. Так как Crab был представлен скорее как материал для исследов а-ния, а не реальный алгоритм, конкретной процедуры генерации ключей не было предложено. Авторы рассмо трели метод, который позволяет превратить 80-битовый ключ в три вспомогательных подключа, хотя алгоритм позволяет легко использовать ключи переменной длины. В Crab используется два набора больших подключей:

Перестановка чисел с 0 до 255: P0, P1, P2, P255.

Массив из 2048 32-битовых чисел: S0, S1, S2,..., S2047.

Все эти подключи должны быть вычислены до шифрования или дешифрирования. Для шифрования 1024-байтового блока X:

(1)Разделите X на 256 32-битовых подблоков: X0, X1, X2, X255.

(2)Переставьте подблоки X в соответствии с P.

(3)For r=0 to 3 For g = 0 to 63

A = X(4g) <<< 2r B = X(4g+1) <<< 2r С = X(4g+2) <<< 2r D = X(4g+3) <<< 2r

For step s = 0 to 7

A = A © (B + fr(B, C, D) + S512r+8g+s)

TEMP = D D = С С = В

В = A <<< 5 A = TEMP

X(4g) <<< 2r = A X(4g+1) <<< 2r = B X(4g+2) <<< 2r = C X(4g+3) <<< 2r = D

(4)Снова объединить X0, X1, X2, X255, получая шифротекст. Функции fr(B, С, D) аналогичны используемым в MD5:

f,(B, С, D) = (B л C) v ((- B) л D) f1(B, С, D) = (B л D) v (C л (- D))

f2(B, С, D) = B © C © D

f,(B, С, D) = C © (B v (- D))

Дешифрирование представляет собой обратный процесс. Генерирование подключей является непростой з а-дачей. Вот как по 80-битовому ключу K может быть сгенерирован массив перестановок P.

(1)Проинициализируйте K0, K1, K2, K9 10 байтами K.

(2)For ,=10 to 255

K, = K,--2 © K,--6 © K,--7 © Ki-10

(3)For ,=10 to 255, P, = ,


(5)For 7=0 to 1

For i = 256 to 1 step -1

m = (К256-; + К257-;) mod i

K257-i = K257-i <<< 3

Переставить Pi и

S-массив из 2048 32-битовых слов может быть сгенерирован аналогичным образом либо по тому же 80-битовому ключу, либо по другому ключу Авторы предупреждают, что эти детали должны "рассматриваться только в качестве мотивации, могут быть и другие эффективные схемы, обеспечивающие лучшую безопасность" [810]

Crab был предложен как испытательный стенд для новых идей, а не как рабочий алгоршж Во многом он использует те же приемы, что и MD5 Бихам заметил, что очень большой блок упрощает криптоанализ алг о-ритма [160] С другой стороны Crab может позволять эффективно использовать очень большой ключ В этом случае "упрощение криптоанализа" может ничего не значите

14.7 SXAL8/MBAL

Это 64-битовый блочный алгоритм из Японии [769] SXAL8 - это основной алгоритм, а MBAL представляет собой расширенную версию с переменной длиной блока Так как внутри MBAL выполняется ряд умных дейс т-вий, авторы утверждают, что они могут обеспечить достаточную безопасность за малое число этапов При длине блока 1024 байта MBAL примерно в 70 раз быстрее, чем DESz К несчастью в [1174] показано, что MBAL чу в-ствителен к дифференциальному криптоанализу, а в [865] - что он чувствителен и к линейному криптоанал изу

14.8 RC5

RC5 представляет собой блочный фильтр с большим числом параметров: размером блока, размером ключа и количеством этапов Он был изобретен Роном Ривестом и проанализирован в RSA Laboratories [1324, 1325]

Используется три действия: XOR, сложение и циклические сдвиги На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные циклические сдвиги являются нелинейной функцией Эти циклические сдвиги, зависящие и от ключа, и от данных, представляют собой интересную оп е-рацикх

RC5 использует блок переменной длины, но в приводимом примере мы остановимся на 64-битовом блоке данных Шифрование использует 2r+2 зависящих от ключа 32-битовых слов - 50, S1, 52, ••• 52r+1 - где r - число этапов Эти слова мы сгенерируем позднее Для шифрования сначала разделим блок открытого текста на два 32-битовых слова: A и (RC5 предполагает следующее соглашение по упаковке байтов в слова: первый байт занимает младшие биты регистра A, и т) Затем:

A = A + 50

B = B + 51

For i = 1 to r:

A = ((A © B) <<< B) +

B = ((B © A) <<< A) + 52i+1 Результат находится в регистрах A и

Дешифрирование также прост Разбейте блок открытого текста на два слова, A и B, а затем: For i = r down to 1:

B = ((B - 52i+1) >>> A) © A

A = ((A - 52i) >>> B) © B B = B - 51 A = A - 50

Символ ">>>" обозначает циклический сдвиг направо Конечно же, все сложения и вычитания выполняются по модулю 232z


Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в ма с-сив L из c 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S инициализируется при помощи линейного конгруэнтного генератора по модулю 2 32:

for , = 1 to 2(r + 1) - 1:

S, = (S,-1 + Q) mod 232

P = 0xb7e15163 и Q = 0x9e3779b9, эти константы основываются на двоичном представлении e и phi. Наконец, подставляем L в S:

, = = 0

A = B = 0

выполнить n раз (где n - максимум 2(r + 1) и с):

A = S = (S + A + B) <<< 3

B = L, = (L, + A + B) <<< (A + B) , = (, + 1) mod 2(r + 1) j = (j + 1 ) mod с

По сути, RC5 представляет собой семейство алгоритмов. Только что мы определили RC5 с 32-битовым сл о-вом и 64-битовым блоком, не существуе причин, запрещающих использовать тот же алгоритм с 64-битовым словом и 128-битовым. Для w = 64, P и Q равны 0xb7e151628aed2a6b и 0x9e3779b97f4a7c15, соответственно. Ривест обозначил различные реализации RC5 как RC5- w/r/b, где w - это размер слова, r - число этапов, а b -длина ключа в байтах.

RC5 является новым алгоритмом, но RSA Laboratories потрптила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 этапов статистика выглядит очень хорошо. После 8 этапов каждый бит открытого текста влияет по крайней мере на один циклический сдвиг. Дифференциальное вскрытие требует 2 24 выбранных открытых текстов для 5 этапов, 2 45 для 10 этапов, 2 53 для 12 этапов и 268 для 15 этапов. Конечно же, существует только 264 возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с 15 и более этапами. Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 этапов. Ривест рекомендует использовать не меньше 12 этапов, а лучше 16 [1325]. Это число может меняться.

RSADSI в настоящее время патентует RC5, а это названия заявлено, как торговая марка. Компания утве р-ждает, что плата за лицензирование будет очень мала, но это лучше проверить.

14.9 Другие блочные алгоритмы

Существует алгоритм, называемый в литературе CRYPTO-MECCANO [301], но он не является безопасным. Четыре японских криптографа на Eurocrypt 91 представили алгоритм, основанный на хаотичных отображениях [687, 688], Бихам выполнил криптоанализ этого алгоритма на той же конференции [157]. Другой алгоритм оп и-рается на подмножества некоторого множества случайных кодов [693]. Существует множество алгоритмов, о снованных на теории кодов, исправляющих ошибки: вариант алгоритма МакЭлайса (McEliece) (см. раздел 19.7) [786, 1290], алгоритм Rao-Nam [1292, 733, 1504, 1291, 1056, 1057, 1058, 1293], варианты алгоритма Rao-Nam [464, 749, 1503] и алгоритм Li-Wang [964, 1561] - все они небезопасны. CALC также небезопасен [1109]. Алг о-ритм TEA (Tiny Encryption Algorithm, Крошечный алгоритм шифрования) слишком нов, чтобы его коммент и-ровать [1592]. Другим алгоритмом является Vino [503]. MacGuffin, блочный алгоритм, предложенный Мэттом Блэйзом и мной, также небезопасен [189], он был взломан на той же конференции, на которой он был предл о-жен. BaseKing, похожий по философии на 3-way, но использующий 192-битовый блок [385], слишком нов, чт о-бы его комментировать.

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

14.10 Теория проектирования блочного шифра

В раздел 11.1 я описывал принципы Шеннона для смешения и рассеяния. Спустя пятьдесят лет после того, как эти принципы были впервые сформулированы, они остаются краеугольным камнем проектирования хор о-



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203]