Реферат Курсовая Конспект
Линейная сложность - раздел Компьютеры, Объединение блочных шифров Анализировать Потоковые Шифры Часто Проще, Чем Блочные. Например, Важным Пара...
|
Анализировать потоковые шифры часто проще, чем блочные. Например, важным параметром, используемым для анализа генераторов на базе LFSR, является линейная сложность(linear complexity), или линейный интервал. Она определяется как длина п самого короткого LFSR, который может имитировать выход генератора. Любая последовательность, генерированная конечным автоматом над конечным полем, имеет конечную линейную сложность [1006]. Линейная сложность важна, потому что с помощью простого алгоритма, называ е-мого алгоритмом Berlekamp-Massey,можно определить этот LFSR, проверив только 2и битов потока ключей [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, v - OR, и - NOT.
– Конец работы –
Эта тема принадлежит разделу:
На сайте allrefs.net читайте: Объединение блочных шифров...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Линейная сложность
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов