рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Линейная сложность

Линейная сложность - раздел Компьютеры, Объединение блочных шифров Анализировать Потоковые Шифры Часто Проще, Чем Блочные. Например, Важным Пара...

Анализировать потоковые шифры часто проще, чем блочные. Например, важным параметром, используе­мым для анализа генераторов на базе 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 читайте: Объединение блочных шифров...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Линейная сложность

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Объединение блочных шифров
Существует множество способов объединять блочные алгоритмы для получения новых алгоритмов. Стиму­лом создавать подобные схемы является желание повысить безопасность, не пробираясь через тернии созд

ЕСВ + OFB
Этот метод был разработан для шифрования нескольких сообщений фиксированной длины, например, бл о-ков диска [186, 188]. Используются два ключа: Ki и К2. Сначала для генерац

Пятикратное шифрование
Если тройное шифрование недостаточно безопасно - может быть, вам нужно шифровать ключи тройного шифрования, используя еще более сильный алгоритм - то кратность шифрования можно увеличить . Очень ус

И потоковые
16.1 Линейные конгруэнтные генераторы Линейными конгруэнтными генераторамиявляютсягенераторы следующей формы Хп = (аХпЛ + Ъ) mod

Объединение линейных конгруэнтных генераторов
Был предпринят ряд попыток объединения линейных конгруэнтных генераторов [1595, 941]. Криптографи­ческая безопасность полученных результатов не повышается, но они обладают более длинными периодами

Сдвиговый регистр с обратной связьюсостоит из двух частей: сдвигового регистра и функции обратной
связи(см. 15th). Сдвиговый регистр представляет собой последовательность битов . (Количество битов опреде­ляется длинойсдвигового регистра. Если длина равна п

Программная реализация LFSR
Программные реализации LFSR медленны и быстрее работают, если они написаны на ассемблере, а не на С. Одним из решений является использование параллельно 16 LFSR (или 32, в зависимости от длины слов

Генератор Геффа
В этом генераторе потока ключей используются три LFSR, объединенные нелинейным образом (см. 10th) [606]. Два LFSR являются входами мультиплексора, а третий LFSR управляет выходом мультиплексора. Ес

Обобщенный генератор Геффа
Вместо выбора между двумя LFSR в этой схеме выбирается один из к LFSR, где к является степенью 2. Все­го используется к + 1 LFSR (см. 9th). Тактовая частота LFSR-1 должна быть

Генератор "стоп-пошел" (Stop-and-Go) Both-Piper
Этот генератор, показанный на 7th, использует выход одного LFSR для управления тактовой частотой друго­го LFSR [151]. Тактовый вход LFSR-2 управляется выходом LFSR-1, так что LFSR-2 может изменять

Пороговый генератор
Этот генератор пытается обойти проблемы безопасности, характерные для предыдущих генераторов, с п о-мощью переменного числа LFSR [277]. По теории при использовании большего количества LFSR вскрыть

Самопрореживающие (Self-Decimated) генераторы
Самопрореживающими называются генераторы, которые управляют собственной тактовой частотой . Было предложено два типа таких генераторов, один Рэйнером Рюппелом (Ranier Rueppel) (см. 3-й) [1359] друг

Каскад Голлманна
Каскад Голлманна (см. 0-й), описанный в [636, 309], представляет собой усиленную версию генератора "стоп-пошел". Он состоит из последовательности LFSR, тактирование каждого из которых упр

Прореживаемый генератор
Прореживаемый (shrinking) генератор [378] использует другую форму управления тактированием. Возьмем два LFSR: LFSR-1 и LFSR -2. Подадим тактовый импульс на оба регистра. Если выходом LFSR-1 являетс

Самопрореживаемый генератор
Самопрореживаемый (self-shrinking) генератор [1050] является вариантом прореживаемого генератора. Вме­сто двух LFSR используется пара битов одного LFSR. Протактируйте LFSR дважды. Если первым битом

Алгоритм М
Это название дано Кнутом [863]. Алгоритм представляет собой способ объединить несколько псевдослучай­ных потоков, увеличивая их безопасность. Выход одного генератора используется для выбора отстающ

Патенты и лицензии
SEAL запатентован [380]. По поводу лицензирования нужно обращаться к Управляющему по лицензиям IBM ( Director of Licenses, IBM Corporation, 500 Columbus Ave., Thurnwood, NY, 10594 ).

Комбинированные генераторы FCSR
Эти генераторы используют переменное количество LFSR и/или FCSR и множество функций, объединяю­щих регистры. Операция XOR разрушает алгебраические свойства FCSR, поэтому имеет смысл использовать эт

Каскад LFSR/FCSR с суммированием/четностью
По теории сложение с переносом разрушает алгебраические свойства LFSR, a XOR разрушает алгебраиче­ские свойства FCSR. Данный генератор объединяет эти идеи, используемые в перечисленных суммирующем

Генератор 1/р
Этот генератор был предложен и подвергнут криптоанализу в [193]. Если внутреннее состояние генератора в момент времени t равно х,, то хм=Ъх,то&р

Другие схемы
Еще один генератор основан на проблеме рюкзака (см. раздел 19.2) [1363]. CRYPTO-LEGGO небезопасен [301]. Джоан Дэймен (Joan Daemen) разработала SubStream, Jam и StepRightUp [402], но они слишком но

Генератор Blum-Micali
Безопасность этого генератора определяется трудностью вычисления дискретных логарифмов [200]. Пусть g - простое число, ар - еще одно простое число. Ключ х0 начинает

Blum, Blum, and Shub
Простейший и наиболее эффективный генератор, использующий сложностно-теоретический подход, в честь своих авторов называется Blum, Blum, and Shub. Мы сократим его название до BBS, хотя иногда его на

Рандомизированный потоковый шифр Диффи
Эта схема впервые была предложена Уитфилдом Диффи [1362]. Используется 2" случайных последователь­ностей. Ключ представляет собой случайную и-битовую строку. Для шифрования сообщения Ал

Рандомизированный потоковый шифр Маурера
Уели Маурер (Ueli Maurer) описал схему, основанную на выполнении XOR открытого текста с несколькими большими открытыми последовательностями случайных битов [1034, 1029, 1030]. Ключ является набором

Таблицы RAND
Давным давно, в 1955 году, когда компьютеры все еще были в новинку, Rand Corporation издала книгу, со­державшую миллион случайных цифр [1289]. Их метод описывался так: Случайные цифры

Использование случайного шума
Лучшим способом получить большое количество случайных битов является извлечение их из естественной случайности реального мира. Часто такой метод требует специальной аппаратуры, но этот трюк можно п

Использование таймера компьютера
Если вам нужен один случайный бит (или даже несколько), воспользуйтесь младшим значащим битом лю­бого регистра таймера. В системе UNIX он может быть не слишком случайным из-за различной возможной с

Измерение скрытого состояния клавиатуры
Процесс печатания и случаен, и неслучаен. Он достаточно неслучаен, чтобы его можно было использовать для идентификации печатающего человека, но он достаточно случаен, чтобы его можно было использов

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги