Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Семейство псевдослучайных функций также упрощает проблему синхронизации, встречающуюся в ста н- дартных потоковых шифрах. Предположим, что вы посылаете шифрованные сообщения по каналу, в котором данные иногда теряются. С помощью семейства псевдослучайных функций можно зашифровать ключом k n-ое передаваемое сообщение, x n , выполнив XOR x n and k(n). Получателю не нужно хранить состояние шифра для восстановления x n , ему не приходится беспокоиться и о потерянных сообщениях, влияющих на процесс деши ф- рирования. Описание SEAL Внутренний цикл SEAL показан на 16th. Алгоритм управляется тремя полученными из ключа таблицами: R, S и T. Предварительная обработка отображает ключ k на эти таблицы с помощью процедуры, основанной на SHA (см. раздел 18.7). 2-килобайтная таблица T представляет собой S-блок 9*32 битов. 160 a T S R M 1 Инициа- лизация Создание таблиц (SHA) 6 l 32 n M 2 … … M 3 M 64 … B 1 B 2 B 3 B 63 B 64 … … Рис. 17-1. Внутренний цикл SEAL. SEAL также использует четыре 32-битовых регистра , A, B, C и D, начальные значения которых определяют- ся n и полученными по k таблицами R и T. Эти регистры изменяются в ходе итераций, каждая из которых с о- стоит из восьми этапов. На каждом этапе 9 битов первого регистра (все равно A, B, C или D) используются в качестве индекса таблицы T. Затем выбранное из T значение складывается со вторым регистром (снова одному из A, B, C или D) или объединяется с его содержимым с помощью XOR. Потом первый регистр циклически сдвигается на 9 позиций. На некоторых этапах второй регистр далее модифицируется с помощью сложения или XOR с содержимым первого регистра (уже сдвинутым) . После 8 таких этапов A, B, C и D добавляются к потоку ключей, при этом каждый из них маскируется сложением или XOR с определенным словом из S. Итерация за- вершается прибавлением к A и C дополнительных значений, зависящих от n, n 1 , n 2 , n 3 , n 4 , выбор конкретного значения определяется четностью номера итерации . По видимому, при разработке этой схемы главными были следующие идеи: 1. Использование большого, секретного, получаемого из ключа S-блока (Т). 2. Чередующиеся некоммутируемые арифметические операции (сложение и XOR). 3. Использование внутреннего состояния, поддерживаемого шифром, которое не проявляется явно в п о- токе данных (значения ni, которые модифицируют A и C в конце каждой итерации). 4. Изменение функции этапа в соответствии с номером этапа и изменение функции итерации в соотве т- ствии с номером итерации. Для шифрования каждого байта текста SEAL требует около пяти элементарных операций . На 50- мегагерцовом процессоре i486 он работает со скоростью 58 Мбит/с. SEAL возможно является самым быстрым из описанных в этой книге. С другой стороны SEAL должен выполнить предварительную обработку, заполняя внутренние таблицы . Размер этих таблиц составляет примерно 3 Кбайт , а для их расчета нужно примерно 200 вычислений SHA. Та- ким образом, SEAL не подходит для тех случаев, когда не хватает времени для обработки ключа или памяти для хранения таблиц. Безопасность SEAL SEAL достаточно новый алгоритм, ему еще предстоит пройти через горнило открытого криптоанализа . Это вызывает определенную настороженность . Однако SEAL кажется хорошо продуманным алгоритмом . Его осо- бенности, в конечном счете, наполнены смыслом . К тому же Дон Копперсмит считается лучшим криптоанал и- тиком в мире. Патенты и лицензии SEAL запатентован [380]. По поводу лицензирования нужно обращаться к Управляющему по лицензиям IBM ( Director of Licenses, IBM Corporation, 500 Columbus Ave., Thurnwood, NY, 10594 ). 17.3 WAKE WAKE - сокращение от Word Auto Key Encryption (Автоматическое шифрование слов ключом)- это алг о- ритм, придуманный Дэвидом Уилером (David Wheeler) [1589]. Он выдает поток 32-битовых слов, которые с помощью XOR могут быть использованы для получения шифротекста из открытого текста или открытого текста из шифротекста. Это быстрый алгоритм. WAKE работает в режиме CFB, для генерации следующего слова ключа используется предыдущее слово шифротекста. Алгоритм также использует S-блок из 256 32-битовых значений. Этот S-блок обладает одним особым свойством: Старший байт всех элементов представляет собой перестановку всех возможных байтов, а 3 младших байта случайны. Сначала по ключу сгенерируем элементы S-блока, S i . Затем проинициализируем четыре регистра с испол ь- зованием того же или иного ключа: a 0 , b 0 , c 0 и d 0 . Для генерации 32-битового слова потока ключей K i K i = d i Слово шифротекста C i представляет собой XOR слова открытого текста P i с K i . Затем обновим четыре реги- стра: a i+1 = M(a i ,d i ) b i+1 = M(b i ,a i+1 ) c i+1 = M(c i ,b i+1 ) d i+1 = M(d i ,c i+1 ) Функция M представляет собой M(x,y) = (x + y) >> 8 ? S (x + y)^255 Схема алгоритма показана на 15-й. Знак >> обозначает обычный, не циклический сдвиг вправо . Младшие 8 битов x+y являются входом S-блока. Уилер приводит процедуру генерации S-блока, но на самом деле она не- полна. Будет работать любой алгоритм генерации случайных байтов и случайной перестановки . K C P A M B M C M D M Рис. 17-2. WAKE. Самым ценным качеством WAKE является его скорость. Однако он чувствителен к вскрытию с выбранным открытым текстом или выбранным шифротекстом . Этот алгоритм использовался в предыдущей версии антив и- русной программы д-ра Соломона. 17.4 Сдвиговые регистры с обратной связью по переносу Сдвиговый регистр с обратной связью по переносу , или FCSR (feedback with carry shift register), похож на LFSR. В обоих есть сдвиговый регистр и функция обратной связи, разница в том, что в FCSR есть также регистр переноса (см. 14-й). Вместо выполнения XOR над всеми битами отводной последовательности эти биты скл а- дываются друг с другом и с содержимым регистра переноса . Результат mod 2 и становится новым битом. Ре- зультат, деленный на 2, становится новым содержимым регистра переноса . bn bn -1 b 4 b 3 b 2 b 1 Сумма div 2 Сдвиговый регистр Сумма mod 2 Выходной бит Сумма Рис. 17-3. Сдвиговый регистр с обратной связью по переносу. На 13-й приведен пример 3-битового FCSR с ответвлениями в первой и второй позициях . Пусть его началь- ное значение 001, а начальное содержимое регистра переноса равно 0. Выходом будет является крайний правый бит сдвигового регистра. Сдвиговый регистр Регистр переноса 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0 1 1 0 0 0 b 3 b 2 b 1 Сумма div 2 Сумма mod 2 Выходной бит Сумма Рис. 17-4. 3-битовый FCSR. Заметим, что конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом, равным 10 . Стоит упомянуть и еще о нескольких моментах . Во первых, регистр переноса является не битом, а числом . Размер регистра переноса должен быть не меньше log 2 t, где t - это число ответвлений. В предыдущем примере только три ответвления, поэтому регистр переноса однобитовый . Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения 0, 1, 2 или 3. Во вторых, существует начальная задержка прежде, чем FCSR перейдет в циклический режим. В предыду- щем примере никогда не повторяется только одно состояние . Для больших и более сложных FCSR задержка может быть больше. В третьих, максимальный период FCSR не 2 n-1 , где n - длина сдвигового регистра. Максимальный период равен q-1, где q - это целое число связи. Это число задает ответвления и определяется как : q = 2q l + 2 2 q 2 + 2 3 q 3 + . . . + 2 n q n -1 (Да, q i отсчитываются слева направо.) И даже хуже, q должно быть простым числом, для которого 2 являе т- ся примитивным корнем. В дальнейшем предполагается, что q удовлетворяет этому условию. В приведенном примере q = 2*0 + 4*1 + 8*1 - 1 == 11. 11 - это простое число, примитивным корнем котор о- го является 2. Роэтому максимальный период равен 10. Не все начальные состояния дают максимальный период . Например, рассмотрим FCSR с начальным значе- нием 101 и регистром переноса, установленным в 4. Сдвиговый регистр Регистр переноса 1 0 1 4 1 1 0 2 1 1 1 1 1 1 1 1 С этого момента регистр выплевывает бесконечную последовательность единиц . Любое начальное состояние приводит к одной из четырех ситуаций . Во первых, оно может быть частью мак- симального периода. Во вторых, оно может перейти в последовательность максимального периода после н а- чальной задержки. В третьих, после начальной задержки оно может породить бесконечную последовательность нулей. В четвертых, после начальной задержки оно может породить бесконечную последовательность единиц . Для определения, чем закончится конкретное начальное состояние, существует математическая формула, но намного проще проверить это опытным путем. Запустите на некоторое время FCSR. (Если m - это начальный объем памяти, а t - количество ответвлений, то достаточно log 2 (t) + log 2 (m) +1 тактов.) Если выходной поток вырождается в бесконечную последовательность нулей или единиц за n битов, где n - это длина FCSR, не ис- пользуйте это начальное состояние. В противном случае его можно использовать . Так как начальное состояние FCSR соответствует ключу потокового шифра, это означает, что ряд ключей генератора на базе FCSR будут слабыми. В 16-й перечислены все целые числа связи, меньшие 10000, для которых 2 является примитивным корнем . Для всех этих чисел максимальный период равен q-1. Чтобы получить по одному из этих чисел последовател ь- ность ответвлений, рассчитаем бинарный состав q+1. Например, 9949 дает последовательность ответвлений в позициях 1, 2, 3, 4, 6, 7, 9, 10 и 13, так как 9950 = 2 13 + 2 10 + 2 9 + 2 7 + 2 6 + 2 4 + 2 3 + 2 2 + 2 1 В 15-й перечислены все отводные последовательности из четырех ответвлений, которые дают FCSR макси- мальной длины для сдвиговых регистров с длиной 32 бита, 64 бита и 128 битов . q, простое число, примитивным корнем которого является 2, получается объединением всех четырех значений , a, b, c и d. q = 2 a + 2 b + 2 c + 2 d - 1 Для создания 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 Эти генераторы используют переменное количество LFSR и/или FCSR и множество функций, объединяю- щих регистры. Операция XOR разрушает алгебраические свойства FCSR, поэтому имеет смысл использовать эту операцию для их объединения. Генератор, показанный на 12th, использует переменное число FCSR. Его выходом является XOR выходов отдельных FCSR. Другими генераторами, являющимися развитием аналогичных линий, являются : — Генератор четности FCSR. Все регистры - FCSR, а объединяющая функция - XOR. — Генератор четности LFSR/FCSR. Используется смесь LFSR и FCSR, объединяемых с помощью XOR. — Пороговый генератор FCSR. Все регистры - FCSR, а объединяющей функцией является мажорирование . — Пороговый генератор LFSR/FCSR. Используется смесь LFSR и FCSR, объединяемых с помощью мажо- рирования. — Суммирующий генератор FCSR. Все регистры - FCSR, а объединяющая функция - сложение с переносом. — Суммирующий генератор LFSR/FCSR. Используется смесь LFSR и FCSR, объединяемых с помощью сложения с переносом. Табл. 17-1. Целые значения связи для FCSR с максимальным периодом 2 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 149 163 173 179 181 197 211 227 269 293 317 347 349 373 379 389 419 421 443 461 467 491 509 523 541 547 557 563 587 613 619 653 659 661 677 701 709 757 773 787 797 821 827 829 853 859 877 883 907 941 947 1019 1061 1091 1109 1117 1123 1171 1187 1213 1229 1237 1259 1277 1283 1291 1301 1307 1373 1381 1427 1451 1453 1483 1493 1499 1523 1531 1549 1571 1619 1621 1637 1667 1669 1693 1733 1741 1747 1787 1861 1867 1877 1901 1907 1931 1949 1973 1979 1987 1997 2027 2029 2053 2069 2083 2099 2131 2141 2213 2221 2237 2243 2267 2269 2293 2309 2333 2339 2357 2371 2389 2437 2459 2467 2477 2531 2539 2549 2557 2579 2621 2659 2677 2683 2693 2699 2707 2741 2789 2797 2803 2819 2837 2843 2851 2861 2909 2939 2957 2963 3011 3019 3037 3067 3083 3187 3203 3253 3299 3307 3323 3347 3371 3413 3461 3467 3469 3491 3499 3517 3533 3539 3547 3557 3571 3581 3613 3637 3643 3659 3677 3691 3701 3709 3733 3779 3797 3803 3851 3853 3877 3907 3917 3923 3931 3947 3989 4003 4013 4019 4021 4091 4093 4099 4133 4139 4157 4219 4229 4243 4253 4259 4261 4283 4349 4357 4363 4373 4397 4451 4483 4493 4507 4517 4547 4603 4621 4637 4691 4723 4787 4789 4813 4877 4933 4957 4973 4987 5003 5011 5051 5059 5077 5099 5107 5147 5171 5179 5189 5227 5261 5309 5333 5387 5443 5477 5483 5501 5507 5557 5563 5573 5651 5659 5683 5693 5701 5717 5741 5749 5779 5813 5827 5843 5851 5869 5923 5939 5987 6011 6029 6053 6067 6101 6131 6173 6197 6203 6211 6229 6269 6277 6299 6317 6323 6373 6379 6389 6397 6469 6491 6547 6619 6637 6653 6659 6691 6701 6709 6733 6763 6779 6781 6803 6827 6829 6869 6883 6899 6907 6917 6947 6949 6971 7013 7019 7027 7043 7069 7109 7187 7211 7219 7229 7237 7243 7253 7283 7307 7331 7349 7411 7451 7459 7477 7499 7507 7517 7523 7541 7547 7549 7573 7589 7603 7621 7643 7669 7691 7717 7757 7789 7829 7853 7877 7883 7901 7907 7933 7949 8053 8069 8093 8117 8123 8147 8171 8179 8219 8221 8237 8243 8269 8291 8293 8363 8387 8429 8443 8467 8539 8563 8573 8597 8627 8669 8677 8693 8699 8731 8741 8747 8803 8819 8821 8837 8861 8867 8923 8933 8963 8971 9011 9029 9059 9173 9181 9203 9221 9227 9283 9293 9323 9341 9349 9371 9397 9419 9421 9437 9467 9491 9533 9539 9547 9587 9613 9619 9629 9643 9661 9677 9733 9749 9803 9851 9859 9883 9901 9907 9923 9941 9949 Табл. 17-2. Отводные последовательности для FCSR максимальной длины (32, 6, 3, 2) (32, 7, 5, 2) (32, 8, 3, 2) (32, 13, 8, 2) (32, 13, 12, 2) (32, 15, 6, 2) (32, 16, 2, 1) (32, 16, 3, 2) (32, 16, 5, 2) (32, 17, 5, 2) (32, 19, 2, 1) (32, 19, 5, 2) (32, 19, 9, 2) (32, 19, 12, 2) (32, 19, 17, 2) (32, 20, 17, 2) (32, 21, 9, 2) (32, 21, 15, 2) (32,23,8,2) (32, 23, 21, 2) (32, 25, 5, 2) (32, 25, 12, 2) (32,27,25,2) (32, 29, 19, 2) (32, 29, 20, 2) (32, 30, 3, 2) (32, 30, 7, 2) (32, 31, 5, 2) (32, 31, 9, 2) (32, 31, 30, 2) (64, 3, 2, 1) (64,14,3,2) (64,15,8,2) (64, 17, 2, 1) (64, 17, 9, 2) (64, 17, 16, 2) (64, 19, 2, 1) (64, 19, 18, 2) (64, 24, 19, 2) (64, 25, 3, 2) (64,25,4,2) (64, 25, 1 1, 2) (64, 25, 19, 2) (64, 27, 5, 2) (64, 27, 16, 2) (64, 27, 22, 2) (64, 28, 19, 2) (64, 28, 25, 2) (64, 29, 16, 2) (64, 29, 28, 2) (64, 31, 12, 2) (64, 32, 21, 2) (64, 35, 29, 2) (64, 36, 7, 2) (64, 37, 2, 1) (64, 37, 1 1, 2) (64,39,4,2) (64, 39, 25, 2) (64, 41, 5, 2) (64, 41, 1 1, 2) (64,41,27,2) (64, 43, 21, 2) (64, 43, 28, 2) (64, 45, 28, 2) (64, 45, 41, 2) (64, 47, 5, 2) (64, 47, 21, 2) (64, 47, 30, 2) (64, 49, 19, 2) (64, 49, 20, 2) (64,52,29,2) (64,53,8,2) (64, 53, 43, 2) (64, 56, 39, 2) (64, 56, 45, 2) (64, 59, 5, 2) (64, 59, 8, 2) (64, 59, 28, 2) (64, 59, 38, 2) (64,59,44,2) (64, 60, 49, 2) (64, 61, 51, 2) (64, 63, 8, 2) (64, 63, 13, 2) (64, 63, 61, 2) (96, 15, 5. 2) (96, 21, 17, 2) (96, 25, 19, 2) (96, 25, 20, 2) (96, 29, 15, 2) |