Blum, Blum, and Shub - раздел Компьютеры, Объединение блочных шифров Простейший И Наиболее Эффективный Генератор, Использующий Сложностно-Теоретич...
Простейший и наиболее эффективный генератор, использующий сложностно-теоретический подход, в честь своих авторов называется Blum, Blum, and Shub. Мы сократим его название до BBS, хотя иногда его называют генератором с квадратичным остатком [193].
Теория генератора BBS использует квадратичные остатки по модулю п (см. раздел 11.3). Вот как он работает.
Сначала найдем два простых числа, р и q, которые конгруэнтны 3 modulo 4. Произведение этих чисел, п, является целым числом Блюма (Blum). Выберем другое случайное целое число х, взаимно простое с п. Вычислим
x0 = x2 modH
Это стартовое число генератора.
Теперь можно начать вычислять биты. i'-ым псевдослучайным битом является младший значащий бит х„ где
x^xjmo&n
Самым интригующим свойством этого генератора является то, что для получения г'-го бита не нужно вычислять предыдущие i- биты. Если вам известны р и q, вы можете вычислить г'-ый бит непосредственно.
Ь, - это младший значащий бит х„ где х, = дЛг'^СМХ»-!))
Это свойство означает, что вы можете использовать этот криптографически сильный генератор псевдосл у-чайных чисел в качестве потоковой криптосистемы для файла с произвольным доступом .
Безопасность этой схемы основана на сложности разложения п на множители. Можно опубликовать и, так что кто угодно может генерировать биты с помощью генератора. Однако пока криптоаналитик не сможет разложить п на множители, он никогда не сможет предсказать выход генератора - ни даже утверждать что-нибудь вроде: "Следующий бит с вероятностью 51 процент будет единицей".
Более того, генератор BBS непредсказуем в левом направлениии непредсказуем в правом направлении. Это означает, что получив последовательность, выданную генератором, криптоаналитик не сможет предсказать ни следующий, ни предыдущий бит последовательности . Это вызвано не безопасностью, основанной на каком-то никому не понятном сложном генераторе битов, а математикой разложения п на множители.
Этот алгоритм медленен, но есть способы его ускорить. Оказывается, что в качестве псевдослучайных битов можно использовать несколько каждого х,. В соответствии с [1569, 1570, 1571, 35, 36] если п - длинах,, можно использовать log2H младших значащих битов х,. Генератор BBS сравнительно медленный и не подходит для потоковых шифров. Однако для высоконадежных приложений, таких как генерация ключей, этот генератор лучше многих других.
17.10 Другие подходы к проектированию потоковых шифров
При информационно-теоретическом подходе к потоковым шифрам предполагается, что криптоаналитик о б-ладает неограничеными временем и вычислительной мощностью. Единственным практически реализованным потоковым шифром, защищенным от такого противника, является одноразовый блокнот (см. раздел 1.5). Так как писать биты в блокноте не очень удобно, его иногда называют одноразовой лентой.На двух магнитных лентах, на одной для шифрования, а на другой для дешифрирования, должен быть записан идентичный поток ключей. Для шифрования просто выполняется XOR открытого текста с битами ленты. Для дешифрирования
выполняется XOR шифротекста с битами другой, идентичной ленты. Один и тот же поток ключей нельзя использовать дважды. Так как биты потока ключей действительно случайны, предсказать поток ключей нево з-можно. Если сжигать ленты после использования, то безопасность будет абсолютной (при условии, что у кого-то другого нет копии ленты).
Другой информационно-теоретический потоковый шифр, разработанных Клаусом Шнорром ( Claus Schnorr) предполагает, что криптоаналитик имеет доступ только к ограниченному числу битов шифротекста [1395]. Результаты являются слишком теоретическими results и не имеют практического значения. Подробности можно найти [1361, 1643,1193].
С помощью рандомизированного потокового шифра криптограф пытается сделать решение проблемы, сто я-щей перед криптоаналитиком, физически невозможным. Для этого, сохраняя небольшой размер секретного ключа, криптограф значительно увеличивает количество битов, с которыми придется иметь дело криптоанал и-тику. Это может быть сделано за счет использования при шифровании и дешифрировании большой опублик о-ванной случайной строки. Ключ же указывает, какие части строки будут использованы при шифровании и д е-шифрировании. Криптоаналитику, не знающему ключа, придется перебирать случайные комбинации частей строки. Безопасность такого шифра можно выразить с помощью среднего числа битов, которые должен пров е-рить криптоаналитик прежде, чем вероятностьопределить ключ значительно улучшится по сравнению с вероя т-ностью простого угадывания.
Шифр "Pun ван Винкль "
Джеймс Массей (James Massey) и Ингемар Ингемарсон (Ingemar Ingemarsson) предложили шифр Тип ван Винкль" [1011], названный так, потому что получатель, чтобы начать дешифрирование, должен получить 2П битов шифротекста. Алгоритм, показанный на 7-й, прост в реализации, гарантировано безопасен и совершенно непрактичен. Просто выполните XOR открытого текста с потоком ключей и задержите поток ключей на время от 0 до 20 лет - точная задержка является частью ключа. По словам Массея: "Можно легко доказать, что вражескому криптоаналитику для вскрытия шифра понадобятся тысячи лет, если кто-то согласится подождать с чт е-нием открытого текста миллионы лет." Развитие этой идеи можно найти в [1577, 755].
На сайте allrefs.net читайте: Объединение блочных шифров...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Blum, Blum, and Shub
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Объединение блочных шифров
Существует множество способов объединять блочные алгоритмы для получения новых алгоритмов. Стимулом создавать подобные схемы является желание повысить безопасность, не пробираясь через тернии созд
ЕСВ + OFB
Этот метод был разработан для шифрования нескольких сообщений фиксированной длины, например, бл о-ков диска [186, 188]. Используются два ключа: Ki и К2. Сначала для генерац
Пятикратное шифрование
Если тройное шифрование недостаточно безопасно - может быть, вам нужно шифровать ключи тройного шифрования, используя еще более сильный алгоритм - то кратность шифрования можно увеличить . Очень ус
И потоковые
16.1 Линейные конгруэнтные генераторы
Линейными конгруэнтными генераторамиявляютсягенераторы следующей формы
Хп = (аХпЛ + Ъ) mod
Объединение линейных конгруэнтных генераторов
Был предпринят ряд попыток объединения линейных конгруэнтных генераторов [1595, 941]. Криптографическая безопасность полученных результатов не повышается, но они обладают более длинными периодами
Программная реализация LFSR
Программные реализации LFSR медленны и быстрее работают, если они написаны на ассемблере, а не на С. Одним из решений является использование параллельно 16 LFSR (или 32, в зависимости от длины слов
Линейная сложность
Анализировать потоковые шифры часто проще, чем блочные. Например, важным параметром, используемым для анализа генераторов на базе LFSR, является линейная сложность(linear complexi
Генератор Геффа
В этом генераторе потока ключей используются три 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 начинает
Рандомизированный потоковый шифр Диффи
Эта схема впервые была предложена Уитфилдом Диффи [1362]. Используется 2" случайных последовательностей. Ключ представляет собой случайную и-битовую строку. Для шифрования сообщения Ал
Рандомизированный потоковый шифр Маурера
Уели Маурер (Ueli Maurer) описал схему, основанную на выполнении XOR открытого текста с несколькими большими открытыми последовательностями случайных битов [1034, 1029, 1030]. Ключ является набором
Таблицы RAND
Давным давно, в 1955 году, когда компьютеры все еще были в новинку, Rand Corporation издала книгу, содержавшую миллион случайных цифр [1289]. Их метод описывался так:
Случайные цифры
Использование случайного шума
Лучшим способом получить большое количество случайных битов является извлечение их из естественной случайности реального мира. Часто такой метод требует специальной аппаратуры, но этот трюк можно п
Использование таймера компьютера
Если вам нужен один случайный бит (или даже несколько), воспользуйтесь младшим значащим битом любого регистра таймера. В системе UNIX он может быть не слишком случайным из-за различной возможной с
Измерение скрытого состояния клавиатуры
Процесс печатания и случаен, и неслучаен. Он достаточно неслучаен, чтобы его можно было использовать для идентификации печатающего человека, но он достаточно случаен, чтобы его можно было использов
Смещения и корреляции
Главной проблемой подобных систем являются возможные закономерности в генерируемой последовател ь-ности. Используемые физические процессы могут быть случайны, но между физическим процессом и компь
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов