Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
(96,51,30,2) (96,53,17,2) (96, 53, 19, 2) (96, 53, 32, 2) (96, 53, 48, 2) (96, 54, 15, 2) (96, 55, 44, 2) (96, 55, 53, 2) (96, 56, 9, 2) (96,56,51,2) (96, 57, 3, 2) (96, 57, 17, 2) (96, 57, 47, 2) (96, 58, 35, 2) (96, 59, 46, 2) (96, 60, 29, 2) (96, 60, 41, 2) (96, 60, 45, 2) (96, 61, 17, 2) (96, 63, 20, 2) (96, 65, 12, 2) (96, 65, 39, 2) (96, 65, 51, 2) (96, 67, 5, 2) (96, 67, 25, 2) (96,67,34,2) (96, 68, 5, 2) (96, 68, 19, 2) (96, 69, 17, 2) (96,69,36,2) (96, 70, 23, 2) (96, 71, 6, 2) (96, 71, 40, 2) (96, 72, 53, 2) (96, 73, 32, 2) (96, 77, 27, 2) (96, 77, 31, 2) (96, 77, 32, 2) (96, 77, 33, 2) (96,77,71,2) (96,78,39,2) (96, 79, 4, 2) (96, 81, 80, 2) (96, 83, 14, 2) (96, 83, 26, 2) (96, 83, 54, 2) (96, 83, 60, 2) (96, 83, 65, 2) (96, 83, 78, 2) (96, 84, 65, 2) (96, 85, 17, 2) (96, 85, 31, 2) (96, 85, 76, 2) (96,85,79,2) (96,86,39,2) (96,86,71,2) (96, 87, 9, 2) (96, 87, 44, 2) (96, 87, 45, 2) (96, 88, 19, 2) (96, 88, 35, 2) (96, 88, 43, 2) (96,88,79,2) (96, 89, 35, 2) (96, 89, 51, 2) (96, 89, 69, 2) (96, 89, 87, 2) (96, 92, 51, 2) (96,92,71,2) (96, 93, 32, 2) (96, 93, 39, 2) (96, 94, 35, 2) (96, 95, 4, 2) (96, 95, 16, 2) (96, 95, 32, 2) (96, 95, 44, 2) (96, 95, 45, 2) (128, 5, 4, 2) (128, 15, 4, 2) (128, 21, 19, 2) (128, 25, 5, 2) (128, 26, 11, 2) (128,27,25,2) (128, 31, 25, 2) (128, 33, 21, 2) (128, 35, 22, 2) (128, 37, 8, 2) (128, 41, 12, 2) (128, 42, 35, 2) (128, 43, 25, 2) (128,43,42,2) (128,45,17,2) (128,45,27,2) (128, 49, 9, 2) (128, 51, 9, 2) (128, 54, 51, 2) (128, 55, 45, 2) (128, 56, 15, 2) (128, 56, 19, 2) (128,56,55,2) (128, 57, 21, 2) (128, 57, 37, 2) (128, 59, 29, 2) (128, 59, 49, 2) (128, 60, 57, 2) (128,61,9,2) (128, 61, 23, 2) (128, 61, 52, 2) (128, 63, 40, 2) (128, 63, 62, 2) (128, 67, 41, 2) (128, 69, 33, 2) (128, 71, 53, 2) (128, 72, 15, 2) (128,72,41,2) (128, 73, 5, 2) (128, 73, 65, 2) (128, 73, 67, 2) (128, 75, 13, 2) (128, 80, 39, 2) (128,80,53,2) (128, 81, 55, 2) (128, 82, 67, 2) (128, 83, 60, 2) (128, 83, 61, 2) (128, 83, 77, 2) (128, 84, 15, 2) (128, 84, 43, 2) (128,85,63,2) (128,87,57,2) (128,87,81,2) (128, 89, 81, 2) (128, 90, 43, 2) (128, 91, 9, 2) (128, 91, 13, 2) (128, 91, 44, 2) (128, 92, 35, 2) (128,95,94,2) (128, 96, 23, 2) (128, 96, 61, 2) (128, 97, 25, 2) (128, 97, 68, 2) (128, 97, 72, 2) (128,97,75,2) (128, 99, 13, 2) (128, 99, 14, 2) (128, 99, 26, 2) (128, 99, 54, 2) (128, 99, 56, 2) (128, 99, 78, 2) (128, 100, 13, 2) (128, 100, 39, 2) (128,101,44,2) (128, 101, 97, 2) (128, 103, 46, 2) (128, 104, 13, 2) (128, 104, 19, 2) (128, 104, 35, 2) (128,105,7,2) (128, 105, 11, 2) (128, 105, 31, 2) (128, 105, 48, 2) (128, 107, 40, 2) (128, 107, 62, 2) (128, 107, 102, 2) (128, 108, 35, 2) (128,108,73,2) (128,108,75,2) (128,108,89,2) (128, 109, 1 1, 2) (128, 109, 108, 2) (128, 1 10, 23, 2) (128, Ill, 61, 2) (128, 113, 59, 2) (128, 114, 83, 2) (128,115,73,2) (128, 117, 105, 2) (128, 119, 30, 2) (128, 119, 101, 2) (128, 120, 9, 2) (128, 120, 27, 2) (128,120,37,2) (128, 120, 41, 2) (128, 120, 79, 2) (128, 120, 81, 2) (128, 121, 5, 2) (128, 121, 67, 2) (128, 121, 95, 2) (128, 121, 96, 2) (128, 123, 40, 2) (128,123,78,2) (128, 124, 41, 2) (128, 124, 69, 2) (128, 124, 81, 2) (128, 125, 33, 2) (128, 125, 43, 2) (128,127,121,2) Объединяющая функция Регистр-1 Регистр-2 Регистр-n Регистр-3 Рис. 17-5. Комбинированные генераторы. Каскад LFSR/FCSR с суммированием/четностью По теории сложение с переносом разрушает алгебраические свойства LFSR, а XOR разрушает алгебраиче- ские свойства FCSR. Данный генератор объединяет эти идеи, используемые в перечисленных суммирующем генераторе LFSR/FCSR и генераторе четности LFSR/FCSR, с каскадом Голлманна. Генератор представляет собой последовательность массивов регистров , тактирование каждого массива опре- деляется выходом предыдущего массива. На 11-й показан один этап такого генератора. Тактируется первый массив LFSR, и результаты объединяются сложением с переносом . Если выход функции объединения равен 1, то тактируется следующий массив (из FCSR), и выход этих FCSR объединяется с выходом предыдущей фун к- ции объединения с помощью XOR. Если выход первой функции объединения равен 0, то массив FCSR не так- тируется, и выход просто складывается с переносом, полученным на предыдущем этапе Если выход этой второй функции объединения равен 1, то тактируется третий массив (из LFSR), и т.д. LFSR Сумматор с переносом LFSR LFSR LFSR FCSR XOR FCSR FCSR FCSR Рис. 17-6. Придуманный генератор. Генератор использует много регистров: n*m, где n - количество этапов, а m - количество регистров на этапе. Я рекомендую n = 10 и m = 5. Чередующиеся генераторы "стоп-пошел" Эти генераторы использую FCSR вместо некоторых LFSR. Кроме того, операция XOR может быть заменена сложением с переносом (см. 10-й). — Генератор "стоп-пошел" FCSR. Регистр-1, Регистр-2 и Регистр-3 - это FCSR. Объединяющая функция - XOR. — Генератор "стоп-пошел" FCSR/LFSR. Регистр-1 - FCSR, а Регистр-2 и Регистр-3 - LFSR. Объединяющая функция - сложение с переносом. — Генератор "стоп-пошел" LFSR/FCSR. Регистр-1 - LFSR, а Регистр-2 и Регистр-3 - FCSR. Объединяющая функция - XOR. Регистр-1 Регистр-3 Регистр-2 Объединяющая функция Рис. 17-7. Чередующийся генератор "стоп-пошел" Прореживаемые генераторы Существует четыре основных типа генераторов, использующих FCSR: — Прореживаемый генератор FCSR. Прореживаемый генератор с FCSR вместо LFSR. — Прореживаемый генератор FCSR/LFSR. Прореживаемый генератор с LFSR, прореживающим FCSR. — Прореживаемый генератор LFSR/FCSR. Прореживаемый генератор с FCSR, прореживающим LFSR. — Самопрореживаемый генератор FCSR. Самопрореживаемый генератор с FCSR вместо LFSR. 17.6 Сдвиговые регистры с нелинейной обратной связью Нетрудно представить более сложную, чем используемая в LFSR или FCSR, последовательность обратной связи. Проблема в том, что не существует математического аппарата, позволяющего провести анализ таких п о- следовательностей. Что-то получится, но кто знает что? Вот некоторые из проблем, связанных со сдвиговыми регистрами с нелинейной обратной связью . — В выходной последовательности могут быть смещения, например, единиц может быть больше, чем нулей. — Максимальный период последовательности может быть меньше, чем ожидалось . — Период последовательности для различных начальных значений может быть различным . — Последовательность какое-то время может выглядеть как случайная, а потом "скатываться" к единстве н- ному значению. (Это можно легко устранить, выполняя XOR крайнего правого бита с нелинейной фун к- цией.) Плюсом является то, что из-за отсутствия теории анализа сдвиговых регистров с нелинейной обратной св я- зью существует немного способов криптоанализировать потоковые шифры, основанные на таких регистрах . Использовать сдвиговые регистры с нелинейной обратной связью можно, но очень осторожно . В сдвиговом регистре с нелинейной обратной связью функция обратной связи может быть произвольной (например, как на ). + ? • ? • + Рис. 17-8. Сдвиговый регистр с нелинейной обратной связью (возможно небезопасный). b 3 b 2 b 1 • Рис. 17-9. 3-битовый сдвиговый регистр с нелинейной обратной связью. На 8-й показан 3-битовый генератор со следующей обратной связью: новым битом является произведение первого и второго битов. Если его проинициализировать значением 110, то последовательность внутренних со- стояний будет следующей: 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 И так до бесконечности. Выходом является последовательность младших значащих битов : 0 1 1 0 1 0 0 0 0 0 0 0. . . . Это не слишком полезно. Может быть и хуже. Если начальное значение 100, то следующими состояниями являются 010, 001, а затем всегда 000. Если начальным значением является 111 , то оно будет повторяться всегда и с самого начала . Была проделана определенная работа по вычислению линейной сложности произведения двух LFSR [1650, 726, 1364, 630, 658, 659]. Конструкция, включающая вычисление LFSR над полем нечетных характеристик [310] не является безопасной [842.]. 17.7 Другие потоковые шифры В литературе описывались и другие потоковые шифры . Вот некоторые из них. Генератор Плесса (Pless) Этот генератор использует свойства J-K триггеров [1250]. Восемь LFSR управляют четырьмя J-K триггерами; каждый триггер нелинейно объединяет два LFSR. Чтобы избежать проблемы, что выход триггера определяет и источник, и значение следующего выходного бита, после тактирования четырех триггеров их в ы- ходы перемешиваются для получения окончательного потока ключей . Этот алгоритм был криптоаналитически взломан с помощью вскрытия каждого триггера в отдельности [1356]. К тому же, объединение J-K триггеров слабо криптографически; генераторы такого типа не устоят перед корреляционным вскрытием [1451]. Генератор на базе клеточного автомата В [1608, 1609], Стив Вольфрам (Steve Wolfram) предложил использовать в качестве генератора псевдосл у- чайных чисел одномерный клеточный автомат . Рассмотрение клеточного автомата не является предметом этой книги, но генератор Вольврама состоит из одномерного массива битов a 1 , a 2 , a 3 , ... , a k , ..., an и функции обнов- ления: a k '= a k-1 ? (a k ? a k+1 ) Бит извлекается из одного из значений a k , реально все равно какого. Генератор ведет себя как вполне случайный . Однако для этих генераторов существует успешное вскрытие с известным открытым текстом [1052]. Это вскрытие выполнимо на PC со значениями n вплоть до 500 битов. Кроме того, Пол Барделл (Paul Bardell) доказал, что выход клеточного автомата может быть также сгенерир о- ван с помощью сдвигового регистра с линейной обратной связью той же длины и, следовательно, не дает бол ь- шей безопасности [83]. Генератор 1/p Этот генератор был предложен и подвергнут криптоанализу в [193]. Если внутреннее состояние генератора в момент времени t равно x t , то x t+1 = bx t mod p Выходом генератора является младший значащий бит x t div p, где div - это целочисленное деление с усече- нием. Для максимального периода константы b и p должны быть выбраны так, что p - простое число, а b - при- митивный корень mod p. К сожалению, этот генератор не безопасен. (Заметим, что для b = 2 FCSR целыми чис- лами связи выдает последовательность, обратную данной .) crypt(1) Оригинальный алгоритм шифрования UNIX, crypt(1), представляет собой потоковый шифр, использующий те же идеи, что и Энигма. Это 256-элементный, однороторный подстановочный шифр с отражателем . И ротор, и отражатель получаются из ключа. Этот алгоритм намного проще, чем немецкая Энигма времен второй мировой войны, и квалифицированному криптоаналитику несложно его взломать [1576, 1299]. Для вскрытия файлов, зашифрованных crypt(1), можно использовать свободно доступную программу UNIX, называемую Crypt Break- ers Workbench (CBW, инструмент взломщика шифров). Другие схемы Еще один генератор основан на проблеме рюкзака (см. раздел 19.2) [1363]. CRYPTO-LEGGO небезопасен [301]. Джоан Дэймен (Joan Daemen) разработала SubStream, Jam и StepRightUp [402], но они слишком новы, чтобы их комментировать. Множество других алгоритмов описано в литературе, но еще больше хранится в се к- рете и встроено в аппаратуру. 17.8 Системно-теоретический подход к проектированию потоковых шифров На практике, проектирование потокового шифра во многом похоже проектирование блочного шифра . В этом случае используется больше математической теории, но в конце концов криптограф предлагает какую-то схему и затем пытается выполнить ее анализ. Согласно Райнеру Рюппелу существует четыре различных подхода к проектированию потоковых шифров [1360, 1362]: — Системно-теоретический подход. Используя ряд фундаментальных критериев и законов проектирования, пытается удостовериться, что каждая схема создает сложную и неизвестную проблему для криптоанал и- тика,. — Информационно-теоретический подход. Пытается сохранить открытый текст в тайне от криптоаналитика. Независимо от того, как много действий выполнит криптоаналитик, он никогда не получит однозначного решения. — Сложностно-теоретический подход. Пытается использовать в качестве основания для криптосистемы н е- которую известную и сложную проблему, такую как разложение на множители или взятие дискретных логарифмов, или сделать криптосистему эквивалентной этой проблеме . — Рандомизированный подход. Пытается создать чрезвычайно большую проблему, заставляя криптоанал и- тика проверить множество бессмысленных данных в ходе попыток криптоанализа . Эти подходы отличаются предположениями о возможностях и способностях криптоаналитика, определением успеха криптоанализа и пониманием безопасности . Большинство исследований в этой области - теоретические, но среди бесполезных потоковых шифров есть и вполне приличные . Системно-теоретический подход использовался во всех ранее приведенных потоковых шифрах, результатом его применения являются большинство используемых в реальном мире потоковых шифров . Криптограф разра- батывает генераторы потока ключей, обладающие проверяемыми характеристиками безопасности - периодом, распределением битов, линейной сложностью и т.д. - а не шифры, основанные на математической теории . Криптограф также изучает различные методы криптоанализа этих генераторов и проверяет, устойчивы ли ген е- раторы по отношению к этим способам вскрытия . Со временем этот подход привел к появлению набора критериев проектирования потоковых шифров [1432, 99, 1357, 1249]. Они рассматривались Рюппелом в [1362], где он подробно приводит теоретические основы этих критериев. — Длинный период без повторений. — Критерий линейной сложности - большая линейная сложность , линейный профиль сложности, локальная линейная сложность и т.д. — Статистические критерии, например, идеальные k-мерные распределения. — Путаница - каждый бит потока ключей должен быть сложным преобразованием всех или большинства битов ключа. — Диффузия - избыточность в подструктурах должна рассеиваться, приводя к более "размазанной" стат и- стике. — Критерии нелинейности для логических функций, такие как отсутствие корреляции m-го порядка, рас- стояние до линейных функций, лавинный критерий, и т.д. Этот перечень критериев проектирования не уникален для потоковых шифров, разработанных с помощью системно-теоретического подхода, он справедлив для всех потоковых шифров . Это справедливо и для всех блочных шифров. Особенностью системно-теоретического подхода является то, что потоковые шифры неп о- средственно разрабатываются, чтобы удовлетворить этим критериям . Главной проблемой таких криптосистем является невозможность доказать их безопасность, никогда не было доказано, что эти критерии проектирования необходимы или достаточны для безопасности . Генератор потока ключей может удовлетворять всем правилам разработки, но тем не менее оказаться небезопасным . Другой мо- жет оказаться безопасным. Этом процессе все еще остается что-то магическое . С другой стороны вскрытие любого из этих генераторов потока ключей представляет собой отличную пр о- блему для криптоаналитика. Если будет разработано достаточно различных генераторов , может оказаться, что криптоаналитик не станет тратить время, взламывая каждый из них . Может, его больше заинтересует возмож- ность прославиться, достигнув успеха, разлагая на множители большие числа или вычисляя дискретные лог а- рифмы. 17.9 Сложностно-теоретический подход к проектированию потоковых шифров Рюппел также очертил сложностно-теоретический подход к проектированию потоковых шифров . В соответ- ствии с ним криптограф пытается использовать теорию сложности, чтобы доказать его генераторы безопасны . Следовательно, генераторы должны быть как можно больше сложнее, основываясь на тех же трудных пробл е- мах, что и криптография с открытыми ключами . И, также как алгоритмы с открытыми ключами, они оказыв а- ются медленными и громоздкими. Генератор псевдослучайных чисел Шамира Эди Шамир использовал в качестве генератора псевдослучайных чисел алгоритм RSA [1417]. Хотя Шамир показал, что предсказание выхода генератора псевдослучайных чисел равносильно взлому RSA, потенциальное смещение выхода была продемонстрирована в [1401, 200]. Генератор Blum-Micali Безопасность этого генератора определяется трудностью вычисления дискретных логарифмов [200]. Пусть g - простое число, а p - еще одно простое число. Ключ x 0 начинает процесс: x i+1 = g x i mod p Выходом генератора является 1, если x i < (p - 1)/2, и 0 в противном случае. Если p достаточно велико, чтобы вычисление дискретных логарифмов mod p стало физически невозможным, то этот генератор безопасен. Дополнительные теоретические результаты можно найти в [1627, 986, 985, 1237, 896, 799]. RSA Этот генератор RSA [35, 36] является модификацией [200]. Начальные параметры - модуль N, произведение двух больших простых чисел p и q, и целое число e, относительно простое с (p-1)(q-1), а также стартовое слу- чайное число x 0 , меньшее N. x i+1 = x e i mod N Выход генератора представляет собой младший значащий бит x i . Безопасность этого генератора опирается на сложность вскрытия RSA. Если N достаточно велико, то генератор безопасен. Дополнительная теория приве- дена в [1569, 1570, 1571, 30, 354]. Blum, Blum, and Shub Простейший и наиболее эффективный генератор, использующий сложностно-теоретический подход, в честь своих авторов называется Blum, Blum, and Shub. Мы сократим его название до BBS, хотя иногда его называют генератором с квадратичным остатком [193]. Теория генератора BBS использует квадратичные остатки по модулю n (см. раздел 11.3). Вот как он работает. |