Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
C E R T nE T E P K K K = 3 2 1 ( ( ( ( ( ( )))))) Все шифрования выполняются в режиме ECB, используется не меньше n+2 ключей шифрования и крипто- графически безопасный генератор псевдослучайных чисел . Эта схема была предложена для использования вместе с DES, но она работает с любым блочным алгори т- мом. Результаты криптоанализа такой схемы мне неизвестны . 15.3 Удвоение длины блока В академическом сообществе давно спорят на тему, достаточна ли 64-битовая длина блока . С одной стороны 64-битовый блок обеспечивает диффузию открытого текста только в 8 байтах шифротекста . С другой стороны более длинный блок затрудняет безопасную маскировку структуры, кроме того, больше возможностей ошибит ь- ся. Существуют предложения удваивать длину блока алгоритма с помощью многократного шифрования [299]. Прежде, чем реализовывать одно из них, оцените возможность вскрытия "встреча посередине" . Схема Ричарда Аутбриджа (Richard Outerbridge) [300], показанная на 12-й, не более безопасна, чем тройное шифрование с од и- нарным блоком и двумя ключами [859]. Правая поло- вина Левая поло- вина Шифротекст Открытый текст E K 1 E K 2 E K 1 Правая поло- вина Левая поло- вина Правая поло- вина Левая поло- вина E K 1 E K 2 E K 1 Правая поло- вина Левая поло- вина Рис. 15-3. Удвоение длины блока. Однако я не рекомендую использовать подобный прием . Он не быстрее обычного тройного шифрования : для шифрования двух блоков данных все также нужно шесть шифрований . Характеристики обычного тройного шифрования известны, а за новыми конструкциями часто прячутся новые проблемы . 15.4 Другие схемы многократного шифрования Проблемой тройного шифрования с двумя ключами является то, что для увеличения вдвое пространства ключей нужно выполнять три шифрования каждого блока открытого текста . Разве не здорово было бы найти какой-нибудь хитрый способ объединить два шифрования, которые удвоили бы пространство ключей ? Двойной OFB/счетчик Этот метод использует блочный алгоритм для генерации двух потоков ключей, которые используются для шифрования открытого текста. S E S I I I T E T I I I C P S T i K i i K i i i i i = ? = + = ? = + = ? ? ? ? 1 2 1 1 1 1 1 2 2 2 1 1 ( ); ( ); S i и T i - внутренние переменные, а I 1 и I 2 - счетчики. Две копии блочного алгоритма работают в некотором гибридном режиме OFB/счетчик, а открытый текст, S i и T i объединяются с помощью XOR. Ключи K 1 и K 2 независимы. Результаты криптоанализа этого варианта мне неизвестны . ECB + OFB Этот метод был разработан для шифрования нескольких сообщений фиксированной длины, например, бл о- ков диска [186, 188]. Используются два ключа: K 1 и K 2 . Сначала для генерации маски для блока нужной длины используется выбранный алгоритм и ключ . Эта маска будет использована повторно для шифрования сообщений теми же ключами. Затем выполняется XOR открытого текста сообщения и маски. Наконец результат XOR шиф- руется с помощью выбранного алгоритма и ключа K 2 в режиме ECB. Анализ этого метода проводился только в той работе, в которой он и был опубликован . Понятно, что он не слабее одинарного шифрования ECB и возможно также силен, как и двойное применение алгоритма . Вероятно, криптоаналитик может выполнять поиск ключей независимо, если он получит несколько открытых текстов фа й- лов, зашифрованных одним ключом. Чтобы затруднить анализ идентичных блоков в одних и тех же местах различных сообщений, можно испол ь- зовать IV. В отличии от использования IV в других режимах в данном случае перед шифрованием ECB выпол- няется XOR каждого блока сообщения с IV. Мэтт Блэйз (Matt Blaze) разработал этот режим для своей UNIX Cryptographic File System (CFS, криптогра- фическая файловая система). Это хороший режим, поскольку скрытым состоянием является только одно ши ф- рование в режиме ECB, маска может быть сгенерирована только один раз и сохранена . В CFS в качестве блоч- ного алгоритма используется DES. xDES i В [1644, 1645] DES используется как компонент ряда блочных алгоритмов с увеличенными размерами кл ю- чей и блоков. Эти схемы никак не зависят от DES, и в них может использоваться любой блочный алгоритм . Первый, xDES 1 , представляет собой просто схему Luby-Rackoff с блочным шифром в качестве базовой функции (см. раздел 14.11). Размер блока в два раза больше размера блока используемого блочного фильтра, а размер ключа в три раза больше, чем у используемого блочного фильтра . В каждом из 3 этапов правая полови- на шифруется блочным алгоритмом и одним из ключей, затем выполняется XOR результата и левой половины, и половины переставляются. Это быстрее, чем обычное тройное шифрование , так как тремя шифрованиями шифруется блок, длина кот о- рого в два раза больше длины блока используемого блочного алгоритма . Но при этом существует простое вскрытие "встреча посередине", которое позволяет найти ключ с помощью таблицы размером 2 k , где k - это размер ключа блочного алгоритма. Правая половина блока открытого текста шифруется с помощью всех во з- можных значений K 1 , выполняется XOR с левой половиной открытого текста и полученные значения сохран я- ются в таблице. Затем правая половина шифротекста шифруется с помощью всех возможных значений K 3 , и выполняется поиск совпадений в таблице . При совпадении пара ключей K 1 и K 3 - возможный вариант правого ключа. После нескольких повторений вскрытия останется только один кандидат. Таким образом, xDES 1 не яв- ляется идеальным решением. Даже хуже, существует вскрытие с выбранным открытым текстом, доказывающее, что xDES 1 не намного сильнее используемого в нем блочного алгоритма [858]. В xDES 2 эта идея расширяется до 5-этапного алгоритма, размер блока которого в 4 раза, а размер ключа в 10 раз превышают размеры блока и ключа используемого блочного шифра . На 11th показан один этап xDES 2 , каж- дый из четырех подблоков по размеру равен блоку используемого блочного шифра, а все 10 ключей независимы. E K 1 E K 2 Рис. 15-4. Один этап xDES 2 К тому же, эта схема быстрее, чем тройное шифрование : для шифрования блока, который в четыре раза больше блока используемого блочного шифра, нужно 10 шифрований . Однако этот метод чувствителен к диф- ференциальному криптоанализу [858] и использовать его не стоит. Такая схема остается чувствительной к ди ф- ференциальному криптоанализу, даже если используется DES с независимыми ключами этапов. Для i ? 3 xDES i вероятно слишком велик, чтобы использовать его в качестве блочного алгоритма . Например, размер блока для xDES 3 в 6 раз больше, чем у лежащего в основе блочного шифра, ключ в 21 раз длиннее, а для шифрования блока, который в 6 раз длиннее блока лежащего в основе блочного шифра, нужно 21 шифрование . Это медленнее, чем тройное шифрование . Пятикратное шифрование Если тройное шифрование недостаточно безопасно - может быть, вам нужно шифровать ключи тройного шифрования, используя еще более сильный алгоритм - то кратность шифрования можно увеличить . Очень ус- тойчиво к вскрытию "встреча посередине" пятикратное шифрование . (Аргументы, аналогичные рассмотренным для двойного шифрования, показывают, что четырехкратное шифрование по сравнению с тройным лишь незн а- чительно повышает надежность.) C E D E D E P P D E D E D C K K K K K K K K K K = = 1 2 3 2 1 1 2 3 2 1 ( ( ( ( ( ))))) ( ( ( ( ( ))))) Эта схема обратно совместима с тройным шифрованием, если K 1 = K 2 , и с однократным шифрованием, если K 1 = K 2 = K 3 . Конечно, она будет еще надежней, если использовать пять независимых ключей . 15.5 Уменьшение длины ключа в CDMF Этот метод был разработан IBM для продукта CDMF (Commercial Data Masking Facility, Коммерческое средство маскирования данных) (см. раздел 24.8), чтобы превратить 56-битовый ключ DES в 40-битовый, раз- решенный для экспорта [785]. Предполагается, что первоначальный ключ DES содержит биты четности. (1) Обнуляются биты четности: биты 8, 16, 24, 32, 40, 48, 56, 64. (2) Результат этапа (1) шифруется с помощью DES ключом 0xc408b0540ba1e0ae, результат шифрования об ъ- единяется посредством XOR с результатом этапа (1). (3) В результате этапа (2) обнуляются следующие биты: 1, 2, 3, 4, 8, 16, 17, 18, 19, 2.0, 2.4, 32, 33, 34, 35, 36, 40, 48, 49, 50, 51, 52, 56, 64. (4) Результат этапа (3) шифруется с помощью DES ключом 0xef2c041ce6382fe6. Полученный ключ использ у- ется для шифрования сообщения. Не забывайте, что этот метод укорачивает ключ и, следовательно, ослабляет алгоритм . 15.6 Отбеливание Отбеливанием (whitening) называется способ, при котором выполняется XOR части ключа с входом блоч- ного алгоритма и XOR другой части ключа с выходом блочного алгоритма . Впервые этот метод был применен для варианта DESX, разработанного RSA Data Security, Inc., а затем (по-видимому, независимо) в Khufu и Khafre. (Ривест и дал имя этому методу, это необычное использование слова .) Смысл этих действий в том, чтобы помешать криптоаналитику получить пару "открытый текст/шифротекст" для лежащего в основе блочного алгоритма . Метод заставляет криптоаналитика угадывать не только ключ алг о- ритма, но и одно из значений отбеливания . Так как XOR выполняется и перед, и после блочного алгоритма, считается, что этот метод устойчив против вскрытия "встреча посередине" . C K E P K P K D C K K K = ? ? = ? ? 3 1 1 3 2 2 ( ) ( ) Если K 1 = K 2 , то для вскрытия грубой силой потребуется 2 n+m/p действий, где n - размер ключа, m - размер блока, и p - количество известных открытых текстов . Если K 1 и K 2 различны, то для вскрытия грубой силой с тремя известными открытыми текстами потребуется 2 n+m+1 действий. Против дифференциального и линейного криптоанализа, такие меры обеспечивают защиту только для нескольких битов ключа. Но с вычислительной точки зрения это очень дешевый способ повысить безопасность блочного алгоритма . 15.7 Многократное последовательное использование блочных алгоритмов А как насчет шифрования сначала алгоритмом А и ключом К А , а затем еще раз алгоритмом В и ключом К В ? Может быть у Алисы и Боба различные представления о том, какой алгоритм безопаснее : Алиса хочет пользо- ваться алгоритмом А, а Боб - алгоритмом В . Этот прием, иногда называемый последовательным использова- нием (cascading), можно распространить и на большее количество алгоритмов и ключей . Пессимисты утверждали, что совместное использование двух алгоритмов не гарантирует повышения без о- пасности. Алгоритмы могут взаимодействовать каким-то хитрым способом, что на самом деле даже уменьшит. Даже тройное шифрование тремя различными алгоритмами может не быть настолько безопасным, насколько вам это кажется. Криптография - достаточно темное искусство, если вы не совсем понимаете, что делаете, то можете легко попасть в беду. Действительность намного светлее. Упомянутые предостережения верны, только если различные ключи з а- висят друг от друга. Если все используемые ключи независимы, то сложность взлома последовательности алг о- ритмов по крайней мере не меньше, чем сложность взлома первого из применяемых алгоритмов [1033]. Если второй алгоритм чувствителен к вскрытию с выбранным открытым текстом, то первый алгоритм может обле г- чить это вскрытие и при последовательном использовании сделать второй алгоритм чувствительным к вскр ы- тию с известным открытым текстом. Такое возможное облегчение вскрытия не ограничивается только алгори т- мами шифрования: если вы позволите кому-то другому определить любой из алгоритмов, делающих что-то с вашим сообщением до шифрования, стоит удостовериться, что ваше шифрование устойчиво по отношению к вскрытию с выбранным открытым текстом . (Обратите внимание, что наиболее часто используемым алгоритмом для сжатия и оцифровки речи до модемных скоростей, применяемым перед любым алгоритмом шифрования, является CELP, разработанный NSA.) Это можно сформулировать и иначе: При использовании вскрытия с выбранным открытым текстом посл е- довательность шифров взломать не легче, чем любой из шифров последовательности [858]. Ряд результатов показал, что последовательное шифрование взломать по крайней мере не легче, чем самый сильный из шифров последовательности, но в основе этих результатов лежат некоторые несформулированные предположения [528]. Только если алгоритмы коммутативны, как в случае каскадных потоковых шифров (или блочных шифров в р е- жиме OFB), надежность их последовательности не меньше, чем у сильнейшего из используемых алгоритмов . Если Алиса и Боб не доверяют алгоритмам друг друга , они могут использовать их последовательно . Для по- токовых алгоритмов их порядок не имеет значения . При использовании блочных алгоритмов Алиса может сн а- чала использовать алгоритм A, а затем алгоритм B. Боб, который больше доверяет алгоритму B, может исполь- зовать алгоритм B перед алгоритмом A. Между алгоритмами они могут вставить хороший потоковый шифр. Это не причинит вреда и может значительно повысить безопасность . Не забудьте, что ключи для каждого алгоритма последовательности должны быть независимыми . Если алго- ритм A использует 64-битовый ключ, а алгоритм B - 128-битовый ключ, то получившаяся последовательность должна использовать 192-битовый ключ . При использовании зависимых ключей у пессимистов гораздо больше шансов оказаться правыми. 15.8 Объединение нескольких блочных алгоритмов Вот другой способ объединить несколько блочных алгоритмов , безопасность которого гарантировано будет по крайней мере не меньше, чем безопасность обоих алгоритмов . Для двух алгоритмов (и двух независимых ключей): (1) Генерируется строка случайных битов R того же размера, что и сообщение М. (2) R шифруется первым алгоритмом. (3) М ? R шифруется вторым алгоритмом. (4) Шифротекст сообщения является объединением результатов этапов (2) и (3). При условии, что строка случайных битов действительно случайна , этот метод шифрует M с помощью одно- разового блокнота, а затем содержимое блокнота и получившееся сообщение шифруются каждым из двух алго- ритмов. Так как и то, и другое необходимо для восстановления M, криптоаналитику придется взламывать оба алгоритма. Недостатком является удвоение размера шифротекста по сравнению с открытым текстом . Этот метод можно расширить для нескольких алгоритмов, но добавление каждого алгоритма увеличивает шифротекст. Сама по себе идей хороша, но, как мне кажется, не очень практична . Глава 16 Генераторы псевдослучайных последовательностей и потоковые шифры 16.1 Линейные конгруэнтные генераторы Линейными конгруэнтными генераторами являются генераторы следующей формы X n = ( aX n-1 + b ) mod m в которых X n - это n-ый член последовательности, а X n-1 - предыдущий член последовательности. Перемен- ные a, b и m - постоянные: a - множитель, b - инкремент, и m - модуль. Ключом, или затравкой, служит значе- ние X 0 Период такого генератора не больше, чем m. Если a, b и m выбраны правильно, то генератор будет генера- тором с максимальным периодом (иногда называемым максимальной длиной ), и его период будет равен m. (Например, b должно быть взаимно простым с m.) Подробное описание выбора констант для получения макс и- мального периода можно найти в [863, 942]. Еще одной хорошей статьей по линейным конгруэнтным генерат о- рам и их теории является [1446]. В 15-й, взятой из [1272,], перечисляются хорошие константы линейных конгруэнтных генераторов . Все они обеспечивают генераторы с максимальным периодом и, что даже более важно, удовлетворяют спектральному тесту на случайность для размерностей 2, 3, 4, 5 и 6 [385, 863]. Таблица организована по максимальному прои з- ведению, которое не вызывает переполнения в слове указанной длины . Преимуществом линейных конгруэнтных генераторов является их быстрота за счет малого количества оп е- раций на бит. К несчастью линейные конгруэнтные генераторы нельзя использовать в криптографии, так как они предск а- зуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом (Jim Reeds) [1294, 1295, 1296], а затем Джоан Бояр (Joan Boyar) [1251]. Ей удалось также вскрыть квадратичные генераторы : Xn = (aX n-1 2 + bX n-1 + c) mod m и кубические генераторы: Xn = (aX n-1 3 + bX n-1 2 + c X n-1 + d) mod m Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального ген е- ратора [923, 899, 900]. Были взломаны и усеченные линейные конгруэнтные генераторы [581, 705, 580], и усе- ченные линейные конгруэнтные генераторы с неизвестными параметрами [1500, 212]. Таким образом была до- казана бесполезность конгруэнтных генераторов для криптографии. Табл. 16-1. Константы для линейных конгруэнтных генераторов Переполняется при a b m 2 20 106 1283 6075 2 21 211 1663 7875 2 22 421 1663 7875 2 23 430 2531 11979 936 1399 6655 1366 1283 6075 2 24 171 11213 53125 859 2531 11979 419 6173 29282 967 3041 14406 2 25 141 28411 134456 625 6571 31104 1541 2957 14000 1741 2731 12960 1291 4621 21870 205 29573 139968 2 26 421 17117 81000 1255 6173 29282 281 28411 134456 2 27 1093 18257 86436 421 54773 259200 1021 24631 116640 1021 25673 121500 2 28 1277 24749 117128 741 66037 312500 2041 25673 121500 2 29 2311 25367 120050 1807 45289 214326 1597 51749 244944 1861 49297 233280 2661 36979 175000 4081 25673 121500 3661 30809 145800 2 30 3877 29573 139968 3613 45289 214326 1366 150889 714025 2 31 8121 28411 134456 4561 51349 243000 7141 54773 259200 2 32 9301 49297 233280 4096 150889 714025 2 33 2416 374441 1771875 2 34 17221 107839 510300 36261 66037 312500 2 35 84589 45989 217728 Однако, линейные конгруэнтные генераторы сохраняют свою полезность для некриптографических прил о- жений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестах демонстрируют хорошие статистические характеристики. Важную информацию о линейных конгруэнтных г е- нераторах и их теории можно найти в [942]. Объединение линейных конгруэнтных генераторов Был предпринят ряд попыток объединения линейных конгруэнтных генераторов [1595, 941]. Криптографи- ческая безопасность полученных результатов не повышается, но они обладают более длинными периодами и лучшими характеристиками в некоторых статистических тестах . Для 32-битовых компьютеров можно испол ь- зовать следующий генератор [941]: static long sl = 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 <= c < m. */ /* combinedLCG возвращает действительное псевдослучайное значение в диапазоне * (0,1). Она объединяет линейные конгруэнтные генераторы с периодами * 2 31 -85 и 2 31 -249, и ее период равен произведению этих двух простых чисел. */ double combinedLCG ( void ) { long q ; long z ; MODMULT ( 53668, 40014, 12211, 2147483563L, s1 ) MODMULT ( 52774, 40692, 3791, 2147483399L, s2 ) z = s1 - s2 ; if ( z < 1 ) z += 2147483562 ; return z * 4.656613e-10 ; } /* В общем случае перед использованием combinedLCG вызывается initLCG. */ void initLCG( long InitS1, long InitS2 ) { sl = InitS1; s2 = InitS2; } Этот генератор работает при условии, что компьютер может представить все целые числа между -2 31 +85 и 2 31 -249. Переменные s 1 и s 2 глобальны и содержат текущее состояние генератора . Перед первым вызовом их необходимо проинициализировать. Для переменной s 1 начальное значение должно лежать в диапазоне между 1 и 2147483562, для переменной s 2 - между 1 и 2147483398. Период генератора близок к 10 18 На 16-битовом компьютере используйте другой генератор : static int sl = 1 ; /* "int" должно быть 16-битовым целым. */ static int s2 = 1 ; static int s3 = 1 ; #define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if (s<0) s+=m ; /* combinedLCG возвращает действительное псевдослучайное значение в диапазоне * (0,1). Она объединяет линейные конгруэнтные генераторы с периодами 2 15 -405, * 2 15 -1041 и 2 15 -1111, и ее период равен произведению этих трех простых чисел. */ double combinedLCG ( void ) { long q ; long z ; MODMULT ( 206, 157, 21, 32363, sl ) MODMULT ( 217, 146, 45, 31727, s2 ) MODMULT ( 222, 142, 133, 31657, s3 ) z = s1 - s2 ; if ( z < 1 ) z -= 32362 ; z += s3 ; if ( z < 1 ) z += 32362 ; return z * 3.0899e-5 ; } /* В общем случае перед использованием combinedLCG вызывается initLCG. */ void initLCG( long InitS1, long InitS2, long InitS3) { sl = InitS1; s2 = InitS2; s3 = InitS3; } Этот генератор работает при условии, что компьютер может представить все целые числа между -32363 и 32363. Переменные s 1 , s 2 и s 3 глобальны и содержат текущее состояние генератора . Перед первым вызовом их необходимо проинициализировать. Для переменной s 1 начальное значение должно лежать в диапазоне между 1 и 32362, для переменной s 2 - между 1 и 31726, для переменной s 3 - между 1 и 31656. Период генератора равен 1.6*10 13 . Для обоих генераторов константа b равна 0. 16.2 Сдвиговые регистры с линейной обратной связью Последовательности сдвиговых регистров используются как в криптографии, так и в теории кодирования . Их теория прекрасно проработана, потоковые шифры на базе сдвиговых регистров являлись рабочей лошадкой военной криптографии задолго до появления электроники . Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи (см. 15th). Сдвиговый регистр представляет собой последовательность битов . (Количество битов опреде- ляется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n-битовым сдвиговым регистром.) Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 поз и- цию. Новый крайний левый бит является функцией всех остальных битов регистра . На выходе сдвигового реги- стра оказывается один, обычно младший значащий, бит . Периодом сдвигового регистра называется длина п о- лучаемой последовательности до начала ее повторения . Функция обратной связи b n b n -1 b 4 b 3 b 2 b 1 Рис. 16-1. Сдвиговый регистр с обратной связью Криптографам нравились потоковые шифры на базе сдвиговых регистров : они легко реализовывались с по- мощью цифровой аппаратуры. Я лишь слегка затрону математическую теорию . В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства , разработал теорию последовательности сдв и- говых регистров [1411]. Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие ене- которые свои резальтаты и результаты Селмера [643]. См. также [970, 971, 1647]. Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с об- ратной связью (linear feedback shift register, или LFSR) (см. 14th). Обратная связь представляет собой просто XOR некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа LFSR можно использовать довольно развитую математическую теорию . Крипто- графы любят анализировать последовательности, убеждая себя, что эти последовательности достаточно случа й- ны, чтобы быть безопасными. LFSR чаще других сдвиговых регистров используются в криптографии. b n b n -1 b 4 b 3 b 2 b 1 Выходной бит Рис. 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 b 4 b 3 b 2 b 1 Выходной бит Рис. 16-3. 4-битовый LFSR. Выходной последовательностью будет строка младших значащих битов : 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0. . . . n-битовый LFSR может находиться в одном из 2 n -1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2 n -1 битов. (Число внут- ренних состояний и период равны 2 n -1, потому что заполнение LFSR нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно .) Только при опре- деленных отводных последовательностях LFSR циклически пройдет через все 2 n -1 внутренних состояний, такие LFSR являются LFSR с максимальным периодом. Получившийся результат называется М- последовательностью. Для того, чтобы конкретный LFSR имел максимальный период, многочлен, образованный из отводной п о- следовательности и константы 1, должен быть примитивным по модулю 2. Степень многочлена является дли- ной сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем x n 2 1 1 ? + , но не является делителем x d +1 для всех d, являющихся делителями 2 n -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: x 32 + x 7 +x 5 + x 3 + x 2 + x + 1 Это можно легко обобщить для LFSR с максимальным периодом. Первым числом является длина LFSR. По- следнее число всегда равно 0, и его можно опустить . Все числа, за исключением 0, задают отводную последов а- тельность, отсчитываемую от левого края сдвигового регистра . То есть, члены многочлена с меньшей степенью соответствуют позициям ближе к правому краю регистра . Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра н о- вый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и пе р- вого битов (см. 12th), получающийся LFSR будет иметь максимальную длину, циклически проходя до повтор е- ния через 2 32 -1 значений. Код для этого LFSR на языке C выглядит следующим образом: int LFSR ( ) { static unsigned long ShiftRegister = 1; /* Все, кроме 0. */ ShiftRegister = ((((ShiftRegister >> 31) ^(ShiftRegister >> 6) ^(ShiftRegister >> 4) ^(ShiftRegister >> 2) ^(ShiftRegister >> 1) ^ShiftRegister)) & 0x00000001) <<31) | (ShiftRegister >> 1) ; return ShiftRegister & 0x00000001; } Если сдвиговый регистр длиннее компьютерного слова, код усложняется, но не намного . b 32 b 7 b 6 b 5 b 4 b 3 b 2 b 1 Выходной бит Рис. 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) (8, 4, 3, 2, 0) (9, 4, 0) (10, 3, 0) (11, 2, 0) (12, 6, 4, 1, 0) (13, 4, 3, 1, 0) (14, 5, 3, 1, 0) (15, 1, 0) (16, 5, 3.2, 0) (17, 3, 0) (17, 5, 0) (17, 6, 0) (18, 7, 0) (18, 5, 2, 1, 0) (19, 5, 2, 1, 0) (20, 3, 0) (21, 2, 0) (22, 1, 0) (23, 5, 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) (286, 73, 0) (294, 61, 0) (322, 67, 0) (333, 2, 0) (350, 53, 0) (366, 29, 0) (378, 43, 0) (378, 107, 0) (390, 89, 0) (462, 73, 0) (521, 32, 0) (521, 48, 0) (521, 158, 0) (521, 168, 0) (607, 105, 0) (607, 147, 0) (607, 273, 0) (1279, 216, 0) (1279, 418, 0) (2281, 715, 0) (2281, 915, 0) (2281, 1029, 0) (3217, 67, 0) (3217, 576, 0) (4423, 271, 0) (9689, 84, 0) Обратите внимание, что у всех элементов таблицы нечетное число коэффициентов . Я привел такую длинную таблицу, так как LFSR часто используются для криптографии с потоковыми шифрами, и я хотел, чтобы разные люди могли подобрать различные примитивные многочлены . Если p(x) примитивен, то примитивен и x n p(1/x), поэтому каждый элемент таблицы на самом деле определяет два примитивных многочлена . Например, если (a, b, 0) примитивен, то примитивен и (a, a - b, 0). Если примитивен (a, b, c, d, 0), то прими- тивен и (a, a - d, a - c, a - b, 0). Математически: если примитивен x a + x b + 1, то примитивен и x a + x a - b + 1 если примитивен x a + x b + x c + x d + 1, то примитивен и x a + x a-d + x a-c + x a-b + 1 Быстрее всего программно реализуются примитивные трехчлены, так как для генерации нового бита тужно выполнять XOR только двух битов сдвигового регистра. Действительно, все многочлены обратной связи, при- веденные в 14-й, являются разреженными, то есть, у них немного коэффициентов. Разреженность всегда пред- ставляет собой источник слабости, которой иногда достаточно для вскрытия алгоритма . Для криптографических алгоритмов гораздо лучше использовать плотные примитивные многочлены, те, у которых много коэффицие н- тов. Применяя плотные многочлены, особенно в качестве части ключа, можно использовать значительно более короткие LFSR. Генерировать плотные примитивные многочлены по модулю 2 нелегко . В общем случае для генерации при- митивных многочленов степени k нужно знать разложение на множители числа 2 k -1. Примитивные многочлены можно найти в следующих трех хороших работах: [652, 1285, 1287]. Сами по себе LFSR являются хорошими генераторами псевдослучайных последовательностей, но они обл а- дают некоторыми нежелательными неслучайными свойствами . Последовательные биты линейны, что делает их бесполезными для шифрования. Для LFSR длины n внутреннее состояние представляет собой предыдущие n выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2n выходным битам генератора с помощью высоко эффективного алгоритма Berlekamp-Massey [1082,1083]: см. раздел 16.3. Кроме того, большие случайные числа, генерируемые с использованием идущих подряд битов этой послед о- вательности, сильно коррелированны и для некоторых типов приложений вовсе не являются случайными . Не- смотря на это LFSR часто используются для создания алгоритмов шифрования . Программная реализация LFSR Программные реализации LFSR медленны и быстрее работают, если они написаны на ассемблере, а не на C. Одним из решений является использование параллельно 16 LFSR (или 32, в зависимости от длины слова вашего компьютера). В этой схеме используется массив слов, размер которого равен длине LFSR, а каждый бит слова массива относится к своему LFSR. При условии, что используются одинаковые многочлены обратной связи , это может дать заметный выигрыш производительности . Вообще, лучшим способом обновлять сдвиговые регистры является умножение текущего состояния на подходящие двоичные матрицы [901]. Схему обратной связи LFSRможно модифицировать. Получающийся генератор не будет криптографически более надежным, но он все еще будет обладать максимальным периодом, и его легче реализовать программно [1272]. Вместо использования для генерации нового крайнего левого бита битов отводной последовательности выполняется XOR каждого бита отводной последовательности с выходом генератора и замена его результатом этого действия, затем результат генератора становится новым крайним левым битом (см. 11th). Иногда эту мо- дификацию называют конфигурацией Галуа. На языке C это выглядит следующим образом: #define mask 0x80000057 static unsigned long ShiftRegister=1; void seed_LFSR (unsigned long seed) { if (seed == 0) /* во избежание беды */ seed = 1 ; ShiftRegister = seed; } int modified_LFSR (void) { if (ShiftRegister & 0x00000001) { ShiftRegister = (ShiftRegister ^ mask >> 1) | 0x8000000 ; return 1; } else { ShiftRegister >>= 1; return 0; } } b 32 b 7 b 6 b 5 b 4 b 3 b 2 b 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, еще больше. Иногда удивляешься тому, что самые простые из них предлаг а- ются снова и снова. Линейная сложность Анализировать потоковые шифры часто проще, чем блочные . Например, важным параметром, используе- мым для анализа генераторов на базе LFSR, является линейная сложность (linear complexity), или линейный интервал. Она определяется как длина n самого короткого LFSR, который может имитировать выход генерато- ра. Любая последовательность, генерированная конечным автоматом над конечным полем, имеет конечную линейную сложность [1006]. Линейная сложность важна, потому что с помощью простого алгоритма, называ е- мого алгоритмом Berlekamp-Massey, можно определить этот LFSR, проверив только 2n битов потока ключей [1005]. Воссоздавая нужный LFSR, вы взламываете потоковый шифр. Эта идея можно расширить с полей на кольца [1298] и на случаи, когда выходная последовательность ра с- сматривается как числа в поле нечетной характеристики [842]. Дальнейшее расширение приводит к вводу пон я- тия профиля линейной сложности, который определяет линейную сложность последовательности по мере ее удлинения [1357, 1168, 411, 1582]. Другой алгоритм вычисления линейной сложности прост только в очень сп е- цифических условиях [597, 595, 596, 1333]. Обобщение понятия линейной сложности выполнено в [776]. Суще- ствую также понятия сферической и квадратичной сложности [844]. В любом случае помните, что высокая линейная сложность не обязательно гарантирует безопасность генер а- тора, но низкая линейная сложность указывает на недостаточную безопасность генератора [1357, 12.49]. Корреляционная независимость Криптографы пытаются получить высокую линейную сложность, нелинейно объединяя результаты некот о- рых выходных последовательностей. При этом опасность состоит в том, что одна или несколько внутренних выходных последовательностей - часто просто выходы отдельных LFSR - могут быть связаны общим ключевым потоком и вскрыты при помощи линейной алгебры . Часто такое вскрытие называют корреляционным вскры- тием или вскрытием разделяй-и-властвуй. Томас Сигенталер (Thomas Siegenthaler) показал, что можно точно определить корреляционную независимость, и что существует компромисс между корреляционной независ и- мостью и линейной сложностью [1450]. Основной идеей корреляционного вскрытия является обнаружение некоторой корреляции между выходом генератора и выходом одной из его составных частей . Тогда, наблюдая выходную последовательность, можно получить информацию об этом промежуточном выходе . Используя эту информацию и другие корреляции, мо ж- но собирать данные о других промежуточных выходах до тех пор, пока генератор не будет взломан . Против многих генераторов потоков ключей на базе LFSR успешно использовались корреляционные вскр ы- тия и их вариации, такие как быстрые корреляционные вскрытия, предлагающие компромисс между вычисл и- тельной сложностью и эффективностью [1451, 278, 1452, 572, 1636, 1051, 1090, 350, 633, 1054, 1089, 995]. Ряд интересных новых идей в этой области можно найти в [46, 1641]. Другие вскрытия Существуют и другие способы вскрытия генераторов потоков ключей . Тест на линейную корректность (linear consistency) пытается найти некоторое подмножество ключа шифрования с помощью матричной техники [1638]. Существует и вскрытие корректности "встречей посередине" (meet-in-the-middle consistency attack) [39, 41]. Алгоритм линейного синдрома (linear syndrome algorithm) основан на возможности записать фраг- мент выходной последовательности в виде линейного уравнения [1636, 1637]. Существует вскрытие лучшим аффинным приближением (best afflne approximation attack) [502] и вскрытие выведенным предложением (derived sequence attack) [42]. К потоковым шифрам можно применить также методы дифференциального [501] и линейного [631] криптоанализа. 16.4 Потоковые шифры на базе LFSR Основной подход при проектировании генератора потока ключей на базе LFSR прост. Сначала берется один или несколько LFSR, обычно с различными длинами и различными многочленами обратной связи . (Если длины взаимно просты, а все многочлены обратной связи примитивны, то у образованного генератора будет макс и- мальная длина.) Ключ является начальным состоянием регистров LFSR. Каждый раз, когда необходим новый бит, сдвиньте на бит регистры LFSR (это иногда называют тактированием (clocking)). Бит выхода представля- ет собой функцию, желательно нелинейную, некоторых битов регистров LFSR. Эта функция называется комби- нирующей функцией, а генератор в целом - комбинационным генератором. (Если бит выхода является функцией единственного LFSR, то генератор называется фильтрующим генератором.) Большая часть теории подобного рода устройств разработана Селмером ( Selmer) и Нилом Цирлером (Neal Zierler) [1647]. Можно ввести ряд усложнений. В некоторых генераторах для различных LFSR используется различная так- товая частота, иногда частота одного генератора зависит от выхода другого . Все это электронные версии идей шифровальных машин, появившихся до Второй мировой войны, которые называются генераторами с управле- нием тактовой частотой (clock-controlled genelators) [641]. Управление тактовой частотой может быть с пр я- мой связью, когда выход одного LFSR управляет тактовой частотой другого LFSR, или с обратной связью, когда выход одного LFSR управляет его собственной тактовой частотой . Хотя все эти генераторы чувствительны, по крайней мере теоретически, к вскрытиям вложением и вероятной корреляцией [634, 632], многие из них безопасны до сих пор. Дополнительную теорию сдвиговых регистров с управляемой тактовой частотой можно найти в [89]. Ян Касселлс (Ian Cassells), ранее возглавлявший кафедру чистой математики в Кембридже и работавший криптоаналитиком в Bletchly Park, сказал, что "криптография - это смесь математики и путаницы , и без путани- цы математика может быть использована против вас ." Он имел в виду, что в потоковых шифрах для обеспеч е- ния максимальной длины и других свойств необходимы определенные математические структуры, такие как LFSR, но, чтобы помешать кому-то получить содержание регистра и вскрыть алгоритм, необходимо внести н е- который сложный нелинейный беспорядок . Этот совет справедлив и для блочных алгоритмов . Поэтому не стоит серьезно увлекаться генераторами потока ключей на базе LFSR, описания которых появи- лись в литературе. Я не знаю, используется ли хоть один из них в реальных криптографических продуктах . Большей частью они представляют лишь теоретический интерес . Некоторые были взломаны, некоторые могли остаться безопасными. Так как шифры на базе LFSR обычно реализуются аппаратно, на рисунках используются символы электро н- ной логики. В тексте, ? означает XOR, ? - AND, ? - OR, и ¬ - NOT. Генератор Геффа В этом генераторе потока ключей используются три LFSR, объединенные нелинейным образом (см. 10th) [606]. Два LFSR являются входами мультиплексора, а третий LFSR управляет выходом мультиплексора. Если a 1 , a 2 и a 3 - выходы трех LFSR, выход генератора Геффа (Geffe) можно описать как: b = (a 1 ? a 2 ) ?((¬a 1 ) ? a 3 ) b(t) Мультиплексор 2 в 1 Выбор LFSR-1 LFSR-3 LFSR-2 Рис. 16-6. Генератор Геффа. Если длины LFSR равны n 1 , n 2 и n 3 , соответственно, то линейная сложность генератора равна (n 1 + 1) n 2 + n 1 n 3 , Период генератора равен наименьшему общему делителю периодов трех генераторов . При условии, что сте- пени трех примитивных многочленов обратной связи взаимно просты, период этого генератора будет равен произведению периодов трех LFSR. Хотя этот генератор неплохо выглядит на бумаге , он криптографически слаб и не может устоять против ко р- реляционного вскрытия [829, 1638]. В 75 процентах времени выход генератора равен выходу LFSR-2. Поэтому, если известны отводные последовательности обратной связи , можно догадаться о начальном значении LFSR-2 и сгенерировать выходную последовательность этого регистра . Тогда можно подсчитать, сколько раз выход LFSR совпадает с выходом генератора. Если начальное значение определено неверно, две последовательности будут согласовываться в 50 процентах времени, а если правильно, то в 75 процентах времени . Аналогично, выход генератора равен выходу LFSR в 75 процентах времени. С такими корреляциями генера- тор потока ключей может быть легко взломан . Например, если примитивные многочлены состоят только из трех членов, и длина самого большого LFSR равна n, для восстановления внутренних состояний всех трех LFSR нужен фрагмент выходной последовательности длиной 37n битов [1639]. Обобщенный генератор Геффа Вместо выбора между двумя LFSR в этой схеме выбирается один из k LFSR, где k является степенью 2. Все- го используется k + 1 LFSR (см. 9th). Тактовая частота LFSR-l должна быть в log 2 k раз выше, чем у остальных k LFSR. Мультиплексор n в 1 b(t) Выбор LFSR-1 LFSR-2 LFSR-n+1 LFSR-3 Рис. 16-7. Обобщенный генератор Геффа. Несмотря на то, что эта схема сложнее генератора Геффа , для взлома можно использовать то же корреляц и- онное вскрытие. Не рекомендую этот генератор. Генератор Дженнингса В этой схеме мультиплексор используется для объединения двух LFSR [778, 779, 780]. Мультиплексор, управляемый LFSR-l, выбирает 1 бит LFSR-2 в качестве очередного выходного бита. Кроме того, используется функция, которая отображает выход LFSR-2 на вход мультиплексора (см. 8th). 0 1 ... n-1 Мультиплексор K 3 K 2 K 1 b(t) В ы б о р LFSR-1 LFSR-2 ? Рис. 16-8. Генератор Дженнингса. Ключом является начальное состояние двух LFSR и функции отображения. Хотя у этого генератора замеча- тельные статистические свойства, он пал перед выполненным Россом Андерсоном (Ross Anderson) вскрытием корректности встречей посередине [39] и вскрытием линейной корректности [1638,442]. Не используйте этот генератор. Генератор "стоп-пошел" (Stop-and-Go) Both-Piper Этот генератор, показанный на 7th, использует выход одного LFSR для управления тактовой частотой друго- го LFSR [151]. Тактовый вход LFSR-2 управляется выходом LFSR-l, так что LFSR-2 может изменять свое со- стояние в момент времени t только, если выход LFSR-l в момент времени t - 1 был равен 1. Тактирован ? b a a a LFSR-1 LFSR-3 LFSR-2 Тактирование ? b(t) a 3 (t) a 2 (t) a 1 (t) LFSR-1 LFSR-3 LFSR-2 Рис. 16-9. Генератор "стоп-пошел" Beth-Piper. Никому не удалось привести для общего случая достоверные данные о линейной сложности этого генератора. Однако он не устоял перед корреляционным вскрытием [1639]. Чередующийся генератор "стоп-пошел" В этом генераторе используются три LFSR различной длины. LFSR-2 тактируется, когда выход LFSR-l равен 1, LFSR-3 тактируется, когда выход LFSR-l равен 0. Выходом генератора является XOR LFSR-2 и LFSR-3 (см. Рис. 16.10) [673]. ? (t) b(t) a 1 (t) LFSR-1 LFSR-3 LFSR-2 Рис. 16-10. Чередующийся генератор "стоп-пошел" У этого генератора большой период и большая линейная сложность . Авторы показали способ корреляцион- ного вскрытия LFSR-1, но это не сильно ослабляет генератор. Были предложены и другие генераторы такого типа [1534, 1574, 1477]. Двусторонний генератор "стоп-пошел" В этом генераторе используется два LFSR с одинаковой длиной n (см. Рис. 16.11) [1638]. Выходом генерато- ра является XOR выходов каждого LFSR. Если выход LFSR-l в момент времени t-1 равен 0, а в момент времени t-2 - 1, то LFSR-2 не тактируется в момент времени t. Наоборот, если выход LFSR-2 в момент времени t-1 равен 0, а в момент времени t-2 - 1, и если LFSR-2 тактируется в момент времени t, то LFSR-l не тактируется в момент времени t. n-этапный LFSR-2 ? A (t) ? (t) a(t+n-1) a(t+n-2) a(t) n-этапный LFSR-1 ? B (t) ? (t) b(t+n-1) b(t+n-2) b(t) с(t) Рис. 16-11. Двусторонний генератор "стоп-пошел". Линейная сложность такой системы примерно равна ее периоду. Согласно [1638], "в такой системе не оче- видная избыточность ключа не наблюдается ". Пороговый генератор Этот генератор пытается обойти проблемы безопасности, характерные для предыдущих генераторов, с п о- мощью переменного числа LFSR [277]. По теории при использовании большего количества LFSR вскрыть шифр сложнее. Этот генератор показан на 4-й. Возьмите выход большого числа LFSR (используя нечетное число регистров). Для получения максимального периода убедитесь, что длины всех LFSR взаимно просты, а многочлены обрат- ной связи - примитивны.. Если более половины выходных битов LFSR - 1, то выходом генератора является 1. Если более половины выходных битов LFSR - 0, то выходом генератора является 0. b(t) LFSR-1 Функция мажорирования LFSR-3 LFSR-n LFSR-2 Рис. 16-12. Пороговый генератор. Для трех LFSR выход генератора можно представить как : b = (a 1 ? a 2 ) ? (a 1 ? a 3 ) ? (a 2 ? a 3 ) Это очень похоже на генератор Геффа за исключением того, что пороговый генератор обладает большей л и- нейной сложностью n 1 n 2 + n 1 n 3 + n 2 n 3 где n 1 , n 2 и n 3 - длины первого, второго и третьего LFSR. Этот генератор не слишком хорош. Каждый выходной бит дает некоторую информацию о состоянии LFSR - точнее 0.189 бита - и генератор в целом не может устоять перед корреляционным вскрытием . Я не советую ис- пользовать такой генератор. Самопрореживающие (Self-Decimated) генераторы Самопрореживающими называются генераторы, которые управляют собственной тактовой частотой . Было предложено два типа таких генераторов, один Рэйнером Рюппелом ( Ranier Rueppel) (см. 3-й) [1359] другой Биллом Чамберсом (Bill Chambers) и Дитером Коллманом (Dieter Collmann) [308] (см. 2nd). В генераторе Рюп- пела если выход LFSR равен 0, LFSR тактируется d раз. Если выход LFSR равен 0, LFSR тактируется k раз. Ге- нератор Чамберса и Коллмана сложнее, но идея остается той же . К сожалению оба генератора не безопасны [1639], хотя был предложен ряд модификаций, которые могут исправить встречающиеся проблемы [1362.]. ? LFSR 0: Тактирование d раз 1: Тактирование k раз b(t) Рис. 16-13. Самопрореживающий генератор Рюппела. ? LFSR 0: Тактирование d раз 1: Тактирование k раз z ... 2 1 b(t) Рис. 16-14. Самопрореживающий генератор Чамберса и Голлмана. Многоскоростной генератор с внутренним произведением (inner-product) Этот генератор, предложенный Массеем ( Massey) и Рюппелом [1014], использует два LFSR с разными так- товыми частотами (см. 1st). Тактовая частота LFSR-2 в d раз больше, чем у LFSR-l. Отдельные биты этих LFSR объединяются операцией AND, а затем для получения выходного бита генератора они объединяются посредс т- вом XOR. d * ? n-этапный LFSR-2 ? l-этапный LFSR-1 b(t) Рис. 16-15. Многоскоростной генератор с внутренним произведением. Хотя этот генератор обладает высокой линейной сложностью и великолепными статистическими характер и- стиками, он все же не может устоять перед вскрытием линейной согласованности [1639]. Если n 1 - длина LFSR- l, n 2 - длина LFSR-2, а d - отношение тактовых частот, то внутреннее состояние генератора может быть получено по выходной последовательности длиной n 2 + n 2 + log 2 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 выходов первого и второго генераторов. Каскад Голлманна Каскад Голлманна (см. 0-й), описанный в [636, 309], представляет собой усиленную версию генератора "стоп-пошел". Он состоит из последовательности LFSR, тактирование каждого из которых управляется пред ы- дущим LFSR. Если выходом LFSR-l в момент времени t является 1, то тактируется LFSR-2. Если выходом LFSR-2 в момент времени t является 1, то тактируется LFSR-3, и так далее. Выход последнего LFSR и является выходом генератора. Если длина всех LFSR одинакова и равна n, линейная сложность системы из k LFSR равна n(2 n - 1) k-1 ? LFSR-1 1 LFSR-2 LFSR-3 Рис. 16-16. Каскад Голлманна. Это дерзкая идея: концептуально они очень просты и могут быть использованы для генерации последов а- тельностей с огромными периодами, огромными линейными сложностями и хорошими статистическими сво й- ствами. Они чувствительны к вскрытию, называемому запиранием (lock-in) [640] и представляющему метод, с помощью которого сначала криптоаналитик восстанавливает вход последнего сдвигового регистра в каскаде , а затем взламывает весь каскад, регистр за регистром . В некоторых случаях это представляет собой серьезную проблему и уменьшает эффективную длину ключа алгоритма , но для минимизации возможности такого вскр ы- тия можно предпринять ряд определенных мер. Дальнейший анализ показал, что с ростом k последовательность приближается к случайной [637, 638, 642, 639]. На основании недавних вскрытий коротких каскадов Голлманна [1063], я советую использовать k не меньше 15. Лучше использовать больше коротких LFSR, чем меньше длинных LFSR. Прореживаемый генератор Прореживаемый (shrinking) генератор [378] использует другую форму управления тактированием . Возьмем два LFSR: LFSR-l и LFSR -2. Подадим тактовый импульс на оба регистра . Если выходом LFSR-l является 1, то выходом генератора является выход LFSR-2. Если выход LFSR-l равен 0, оба бита сбрасываются, LFSR такти- руются заново и все повторяется. Идея проста, достаточно эффективна и кажется безопасной . Если многочлены обратной связи прорежены, генератор чувствителен к вскрытию, но других проблем обнаружено не было . Хотя этот тип генератора доста- точно нов. Одна из проблем реализации состоит в том, что скорость выдачи результата не постоянна, если LFSR-l генерирует длинную последовательность нулей, то на выходе генератора ничего нет . Для решения этой проблемы авторы предлагают использовать буферизацию [378]. Практическая реализация прореживаемого г е- нератора рассматривается в [901]. Самопрореживаемый генератор Самопрореживаемый (self-shrinking) генератор [1050] является вариантом прореживаемого генератора . Вме- сто двух LFSR используется пара битов одного LFSR. Протактируйте LFSR дважды. Если первым битом пары будет 1, то второй бит будет выходом генератора . Если первый бит - 0, сбросьте оба бита и попробуйте снова. Хотя для самопрореживаемого генератора нужно примерно в два раза меньше памяти, чем для прореживаем о- го, он работает в два раза медленнее. Хотя самопрореживаемый генератор также кажется безопасным, он может вести себя непредсказуемым о б- разом и обладать неизвестными свойствами . Это очень новый генератор, дайте ему немного времени . 16.5 A5 A5 - это потоковый шифр, используемый для шифрования GSM (Group Special Mobile). Это европейский стандарт для цифровых сотовых мобильных телефонов . Он используется для шифрования канала "телефон- базовая станция". Оставшаяся часть канала не шифруется, телефонная компания может легко сделать что- нибудь с вашими разговорами. Вокруг этого протокола ведутся странные политические игры . Первоначально предполагалось, что крипт о- графия GSM позволит запретить экспорт телефонов в некоторые страны . Теперь ряд чиновников обсуждает, не повредит ли A5 экспортным продажам несмотря на то, что он так слаб, что вряд ли сможет служить препятс т- вием. По слухам в середине 80-х различные секретные службы НАТО сцепились по вопросу, должно ли шифр о- вание GSM быть сильным или слабым. Немцам была нужна сильная криптография, так как рядом с ними нах о- дился Советский Союз. Взяла верх другая точка зрения, и A5 представляет собой французскую разработку. Большинство деталей нам известно. Британская телефонная компания передала всю документацию Брэ д- фордскому университету (Bradford University), не заставив подписать соглашение о неразглашении . Информа- ция где-то просочилась и наконец была опубликована в Internet. A5 описывается в [1622], также в конце этой книги приведен код этого протокола. A5 состоит из трех LFSR длиной 19, 22 и 23, все многочлены обратной связи - прорежены . Выходом являет- ся XOR трех LFSR. В A5 используется изменяемое управление тактированием . Каждый регистр тактируется в зависимости от своего среднего бита, затем выполняется XOR с обратной пороговой функцией средних битов всех трех регистров. Обычно на каждом этапе тактируется два LFSR. Существует тривиальное вскрытие, требующее 2 40 шифрований: предположите содержание первых двух LFSR и попытайтесь определить третий LFSR по потоку ключей. (Действительно ли такой способ вскрытия возможен, остается под вопросом, который скоро будет разрешен разрабатываемой машиной для аппаратного поиска ключей [45].) Тем не менее, становится ясно, что идеи, лежащие в основе A5, неплохи. Алгоритм очень эффективен. Он удовлетворяет всем известным статистическим тестам, единственной его слабостью является то, что его регис т- ры слишком коротки, чтобы предотвратить поиск ключа перебором . Варианты A5 с более длинными сдвиговы- ми регистрами и более плотными многочленами обратной связи должны быть безопасны . 16.6 Hughes XPD/KPD Этот алгоритм был предложен Hughes Aircraft Corp. Эта фирма встроила его в армейские тактические рации и оборудование поиска направления для продажи за границу. Алгоритм был разработан в 1986 году и получил название XPD, сокращение от Exportable Protection Device - Экспортируемое устройство защиты. Позднее он был переименован в KPD - Устройство кинетической защиты - и рассекречен [1037, 1036]. Алгоритм использует 61-битовый LFSR. Существует 2 10 различных примитивных многочлена обратной св я- зи, одобренных NSA. Ключ выбирает один из этих многочленов (хранящихся где-то в ПЗУ), а также начальное состояние LFSR. В алгоритме восемь различных нелинейных фильтров , каждый из которых использует шесть отводов LFSR, выдавая один бит. Объединяясь, эти биты образуют байт, который и применяется для шифрования или деши ф- рирования потока данных. Этот алгоритм выглядит очень привлекательно, но у меня есть определенные сомнения . NSA разрешило его экспорт, следовательно должен быть способ вскрытия порядка, не большего чем 2 40 |