Одноразовый блокнот
Одна из целей криптографии — идеальная секретность. Исследования Шеннона показали, что идеальная секретность может быть достигнута, если символы исходного текста зашифрованы с помощью ключа, выбранного случайно из некоторой области ключей. Например, аддитивный шифр может быть легко взломан, потому что используется один и тот же ключ. Но даже и этот шифр может быть идеальным, если ключ, который применяется для шифрования каждого символа, выбран случайно из множества ключей (00, 01, 02.... 25): если первый символ зашифрован с помощью ключа 04, второй символ — с помощью ключа 02, третий — с помощью ключа 21, и так далее. Атака "только для зашифрованного текста" становится невозможна. Если передатчик изменяет ключ, используя каждый раз иную случайную последовательность целых чисел, другие типы атак также будут невозможны.
Эта идея используется в шифре, который называется одноразовым блокнотом. Его изобрел американский инженер Вернам. В этом шифре ключ имеет ту же самую длину, что и исходный текст, и выбран совершенно случайно.
Одноразовый блокнот — идеальный шифр, но его почти невозможно реализовать коммерчески. Если ключ каждый раз генерируется заново, как Алиса может каждый раз сообщать Бобу новый ключ? Для этого каждый раз нужно передавать сообщение. Однако есть некоторые случаи, когда возможно использование одноразового блокнота. Например, если президент страны должен передать полностью секретное сообщение президенту другой страны, он может перед посылкой сообщения передать с помощью доверенного посланника случайный ключ. Некоторые вопросы изменения шифра одноразового блокнота обсуждаются в дальнейших лекциях, когда будет рассматриваться введение в современную криптографию.
\
№26
RC4 — это потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколе SSL и для шифрования паролей в Windows NT). Алгоритм RC4 строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов с равномерным распределением. Основные преимущества шифра — высокая скорость работы и переменный размер ключа. Типичная реализация выполняет 19 машинных команд на каждый байт текста. Ядро алгоритма состоит из функции генерации ключевого потока. Эта функция генерирует последовательность битов, которая затем объединяется с открытым текстом посредством суммирования по модулю два. Дешифрация состоит из регенерации этого ключевого потока и суммирования его с шифрограммой по модулю два, восстанавливая исходный текст. Другая главная часть алгоритма — функция инициализации, которая использует ключ переменной длины для создания начального состояния генератора ключевого потока.
RC4 — фактически класс алгоритмов, определяемых размером его блока. Этот параметр n является размером слова для алгоритма. Обычно, n = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. Внутреннее состояние RC4 состоит из массива размером 2n слов и двух счетчиков, каждый размером в одно слово. Массив известен как S-бокс, и далее будет обозначаться как S. Он всегда содержит перестановку 2n возможных значений слова. Два счетчика обозначены через i и j.
Алгоритм инициализации RC4 приведен ниже. Этот алгоритм использует ключ, сохраненный в Key, и имеющий длину l байт. Инициализация начинается с заполнения массива S, далее этот массив перемешивается путем перестановок определяемых ключом. Так как только одно действие выполняется над S, то должно выполняться утверждение, что S всегда содержит все значения кодового слова.
№27
Шифр A5/1.
В GSM во время разговора посылается последовательность кадров каждые 4.6 мс. Каждый кадр состоит из 114-ти бит информации от Абонента к Базовой станции и 114-ти бит от Базовой станции к Абоненту. Каждый новый разговор может быть зашифрован новым сессионным ключом K. Для шифрования каждого кадра используется сессионный ключ K и номер кадра Fn (известное число), эти два числа служат для начальной инициализации генератора псевдослучайной последовательности. Биты с выхода генератора используют для операции XOR с передаваемым сообщением.
В
A5/1 используется три регистра сдвига с
линейной обратной связью с длинами 19,
22 и 23 бита, которые обозначаются как R1,
R2 и R3 соответственно. Самый младший бит
регистра называется нулевым битом.
Обратная связь в регистре R1 осуществляют
биты 13, 16, 17, 18; в R2 – 20, 21; в R3 – 7, 20, 21, 22.
При сдвиге регистра значения битов
обратной связи подвергается операции
XOR и результат записывается в нулевой
бит сдвинутого регистра. Все три регистра
являются регистрами сдвига максимального
периода с периодами 219-1,
222-1,
223-1
соответственно. Управление сдвигом
регистров происходит с помощью следующего
мажоритарного правила: каждый регистр
имеет один бит «синхронизации» (бит 8
для R1, бит 10 для R2 и бит 10 для R3). Каждый
такт вычисляется мажоритарная функция
от трёх битов синхронизации
F(x,y,z)=x*y+x*z+y*z (* - логический AND, + - логический
OR) и на данном такте сдвигаются только
те регистры, в которых биты синхронизации
совпадают с F.
рис. 2 структура шифра A5/1.
Процесс генерации псевдослучайной последовательности из сессионного ключа K и счетчика кадров Fn состоит из четырёх шагов:
• В начале каждый из регистров равен нулю, затем производится 64 такта (причём без управления сдвигом). Во время этого шага на каждом такте каждый бит K (от младшего к старшему) XOR-ится с младшим битом каждого регистра.
• Производится ещё 22 такта (опять без управления сдвигом), причем младшие биты регистров XOR-ятся с битами Fn (от младшего к старшему). Состояние регистров в конце этого шага называется начальным состоянием кадра.
• Производится 100 тактов с управлением сдвигом, но без генерирования выходной псевдослучайной последовательности.
• Производится 228 тактов с управлением сдвигом и генерируются 228 бит выходной последовательности. На каждом такте генерируется один выходной бит как XOR старших битов трёх регистров.
.