close

Вход

Забыли?

вход по аккаунту

?

РСЛОС

код для вставкиСкачать
Шифрование и дешифрование
Поточные шифры преобразуют открытый текст в шифротекст по одному биту за операцию. Генератор потока ключей (иногда называемый генератором с бегущим ключом) выдает поток битов: k1, k2, ..., ki. Этот поток битов (иногда называемый бегущим ключом) и поток битов открытого текста, p1, p2, ..., pi, подвергаются операции XOR, и в результате получается поток битов шифротекста: ci = pi⊕ki. При дешифровании, для восстановления битов открытого текста, операция XOR выполняется над битами шифротекста и тем же самым потоком ключей: pi = ci⊕ki. Отметим, что ki = pi⊕ci. Безопасность системы полностью зависит от свойств генератора потока ключей. Если генератор потока ключей выдает бесконечную строку нулей, шифротекст будет совпадать с открытым текстом и преобразование будет бессмысленным. Если генератор потока ключей выдает повторяющийся 16-битовый шаблон, криптостойкость будет пренебрежимо мала. В случае бесконечного потока случайных битов криптостойкость поточного шифра будет эквивалентна криптостойкости одноразового блокнота. Генератор потока ключей создает битовый поток, который похож на случайный, но в действительности детерминирован и может быть безошибочно воспроизведен при дешифровании. Чем ближе выход генератора потока ключей к случайному, тем выше трудоемкость криптоаналитической атаки. Блочные и поточные шифры реализуются по-разному. Поточные шифры, шифрующие и дешифрующие данные по одному биту, не очень подходят для программных реализаций. Блочные шифры легче реализовывать программно, так как они позволяют избежать трудоемких манипуляций с битами и оперируют удобными для компьютера блоками данных. С другой стороны, поточные шифры больше подходят для аппаратной реализации. Регистры сдвига с обратной связью
Большинство реальных поточных шифров основано на регистрах сдвига с обратной связью. Регистр сдвига применяют для генерации ключевой последовательности. Регистр сдвига с обратной связью состоит из двух частей: регистра сдвига и функции обратной связи. Регистр сдвига представляет собой последовательность битов. (Количество битов определяется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n-битовым регистром сдвига.) Всякий раз, когда нужно извлечь бит, все биты регистра сдвига сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе регистра оказывается один, обычно младший значащий бит. Периодом регистра называется длина получаемой последовательности до начала ее повторения. Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью (РСЛОС). Обратная связь представляет собой XOR некоторых битов регистра; эти биты называются отводной последовательностью. РСЛОС (n-битовый) может находиться в одном из 2n−1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2n−1 битов. (Число внутренних состояний и период равны 2n−1, потому что заполнение РСЛОС нулями приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.) Только при определенных отводных последовательностях РСЛОС циклически пройдет через все 2n−1 внутренних состояний. Такие РСЛОС имеют максимальный период. Получившийся pезультат называется М-последовательностью. Для того чтобы конкретный РСЛОС имел максимальный период, многочлен, ассоциированный с отводной последовательностью, должен быть примитивным по модулю 2 - то есть не раскладываться на произведение двоичных многочленов меньшей степени. Например, многочлен x32 + x7 + x5 + x3 + x2 + x + 1 примитивен по модулю 2. Рассмотрим этот многочлен в терминах РСЛОС с максимальным периодом. Степень многочлена задает длину РСЛОС. Свободный член многочлена всегда равен 1, и его можно опустить. Степени формальной переменной многочлена, за исключением 0-й, задают отводную последовательность, отсчитываемую от левого края сдвигового регистра. То есть члены многочлена с меньшей степенью соответствуют позициям, расположенным ближе к правому краю регистра. Тогда для взятого 32-битового сдвигового регистра новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и первого битов; получающийся РСЛОС будет иметь максимальную длину, циклически проходя до повторения через 232−1 различных значений. Сами по себе РСЛОС являются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными свойствами. Для РСЛОС длины n внутреннее состояние представляет собой предыдущие n выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2n выходным битам генератора с помощью алгоритма Берлекэмпа-Мэсси. Кроме того, большие случайные числа, генерируемые с использованием идущих подряд бит этой последовательности, сильно коррелированы и для некоторых типов приложений вовсе не являются случайными. Несмотря на это, РСЛОС часто используются при разработке алгоритмов шифрования. A5
А5 - это поточный шифр, используемый для шифрования GSM (Group Special Mobile), - европейского стандарта для цифровых сотовых мобильных телефонов. А5 состоит из трех PCЛОС длиной 19, 22 и 23. Выходом является XOR трех PCЛОС. В А5 используется изменяемое управление тактированием. Каждый регистр тактируется в зависимости от своего среднего бита, затем выполняется XOR с обратной пороговой функцией средних битов всех трех регистров. Обычно на каждом этапе тактируется два РСЛОС. Существует тривиальная атака на открытом тексте, основанная на предположении о содержании первых двух РСЛОС и попытке определения третьего РСЛОС по ключевой последовательности. Тем не менее идеи, лежащие в основе А5, позволяют проектировать надежные поточные шифры. Алгоритм эффективен и удовлетворяет всем известным статистическим тестам, единственная его слабость - короткие регистры. Варианты А5 с более длинными сдвиговыми регистрами и более плотными многочленами обратной связи позволяют противостоять силовой атаке. RC4
RC4 - это поточный шифр с переменным размером ключа, разработанный в 1987 г. Ривестом (R. Rivest) для RSA Data Security, Inc. Алгоритм работает в режиме OFB: поток ключей не зависит от открытого текста. Используется S-блок размером 8×8: S0, S1, S2, ..., S255. Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины. В алгоритме применяются два счетчика, i и j, с нулевыми начальными значениями. Для генерации случайного байта выполняются следующие вычисления: * i = (i + 1) mod 256; * j = (j + Si) mod 256. * Поменять местами Si и Sj. * t = (Si + Sj) mod 256; * K = St. К используется в операции XOR с открытым текстом для получения шифротекста или в операции XOR с шифротекстом для получения открытого текста. Шифрование выполняется примерно в 10 раз быстрее, чем в DES. Также несложна и инициализация S-блока. Сначала S-блок заполняется по правилу: S0 = 0, S1 = 1, ..., S255 = 255. После этого ключ записывается в массив: K0, K1, ..., K255. Затем при начальном значении j = 0 в цикле выполняются следующие вычисления: * for i = 0 to 255 do j = (j + Si + Ki) mod 256 * Поменять местами Si и Sj. Компания RSA Data Security, Inc. утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу и что он в высокой степени нелинеен. S-блок медленно изменяется при использовании: i и j обеспечивают случайное изменение каждого элемента. RC4 входит в десятки коммерческих продуктов, включая Lotus Notes, AOCE компании Apple Computer и Oracle Secure SQL. Этот алгоритм также является частью спецификации стандарта Сотовой цифровой пакетной передачи данных CDPD (Cellular Digital Packet Data). SEAL
SEAL - это эффективный поточный шифр, разработанный в IBM Рогэвэем (P. Rogaway) и Копперсмитом (D. Coppersmith). Алгоритм оптимизирован для 32-битовых процессоров. Для нормальной работы ему нужно восемь 32-битовых регистров и память на несколько килобайтов. В SEAL предусмотрен ряд предварительных действий с ключом с сохранением результатов в нескольких таблицах. Таблицы используются для ускорения процедур шифрования и дешифрования. Особенностью SEAL является то, что он в действительности является не традиционным поточным шифром, а представляет собой семейство псевдослучайных функций. При 160-битовом ключе k и 32-битовом регистре n, SEAL растягивает n в L-битовую строку k(n). L может принимать любое значение, меньшее 64 Кбайт. SEAL использует следующее правило: если k выбирается случайным образом, то k(n) должно быть неотличимо от случайной L-битовой функции n. Практический эффект того, что SEAL является семейством псевдослучайных функций, состоит в том, что он удобен в ряде приложений, где не применимы традиционные поточные шифры. При использовании большинства поточных шифров создается однонаправленная последовательность бит: единственным способом определить i-й бит (зная ключ и позицию i) является генерирование всех битов вплоть до i-го. Отличие семейства псевдослучайных функций состоит в том, что можно легко получить доступ к любой позиции ключевой последовательности. Например, для шифрования жесткого диска, состоящего из множества 512-байтовых секторов, можно воспользоваться семейством псевдослучайных функций, подобных SEAL, и выполнить XOR каждого сектора с k(n). Это то же самое, как если бы была выполнена операция XOR всего диска с длинной псевдослучайной функцией, причем любая часть этой длинной последовательности бит может быть вычислена независимо. Семейство псевдослучайных функций также упрощает проблему синхронизации, встречающуюся в стандартных поточных шифрах, - можно зашифровать на ключе k n-е передаваемое сообщение хn, выполнив XOR хn и k(n). Получателю не нужно хранить состояние шифра для восстановления хn, ему не приходится беспокоиться и о потерянных сообщениях, влияющих на процесс дешифрования. 
Документ
Категория
Рефераты
Просмотров
239
Размер файла
68 Кб
Теги
рслос
1/--страниц
Пожаловаться на содержимое документа