Описание криптосхемы

Описание алгоритма дается по работе Йована Голича, представленной на конференции Eurocrypt '97.

Пусть обозначает известный примитивный полином обратной связи РСЛОС_i (регистра сдвига с линейной обратной связью) длины r _i(i = 1,2,3). Известно, что r₁ = 19, r₂ = 22, r₃ = 23. Известно также, что полиномы обратной связи прорежены (но в описанных криптоаналитических методах вскрытия этот факт не используется).

Пусть обозначает начальное заполнение РСЛОС_i и пусть обозначает соответствующую последовательность максимальной длины и с периодом , порождаемую в РСЛОС_i рекуррентой .

Пусть обозначает состояние РСЛОС_i в момент t >= 0 в схеме с движением "стоп/вперед", описываемым ниже, и пусть обозначает средний отвод в регистре РСЛОС_i , используемый для управления движением. Полагается, что . Тогда управляющая движением регистров последовательность задается как

где g - это 4-значная мажоритарная функция от трех двоичных переменных, такая что если и g(s₁,s₂,s₃) = {1,2,3}, если s₁ = s₂ = s₃ . Другими словами, значение управления движением C(t) определяет, какие РСЛОС сдвигаются для генерации выходного бита y(t) как суммы

(в каждом такте сдвигается по меньшей мере два регистра). Пусть обозначает двоичную управляющую последовательность для РСЛОС_i (сдвигающийся, если c_i(t) = 1 и стоящий на месте, если c_i(t) = 0), которая очевидным образом получается из последовательности управления движением C. Так как последнее уравнение для y(t) формально можно использовать для генерации начального бита y(0) из S(0), то называют выходной последовательностью. Первые 100 бит выхода отбрасываются, следующие 114 бит используются в качестве гаммы для шифрования одного направления полной дуплексной связи, затем еще 100 бит отбрасываются, а следующие 114 бит используются в качестве гаммы для шифрования сигнала связи обратного направления. Таким образом, зашифрованные сообщения имеют очень короткую длину и часто происходит ресинхронизация.

Начальные заполнения РСЛОС определяются в терминах секретного и открытого ключей. Открытый ключ - это известный 22-битовый номер фрейма, генерируемый счетчиком и, следовательно, отличающийся для каждого нового сообщения. Секретный сеансовый ключ длиной 64 бита первым загружается в регистры (начальное заполнение из всех нулей избегается принудительной установкой 1 в выходе последней ячейки), а затем 22-битовый открытый ключ побитно добавляется в последовательности обратной связи каждого регистра в то время, когда они сдвигаются по описанному выше мажоритарному закону. Более строго, если обозначает открытый ключ, то для каждого t, -21 <= t <= 0, регистры сначала сдвигаются по заданному закону "стоп/вперед", а затем бит p(t) прибавляется в последнюю ячейку каждого РСЛОС. После 22 таких шагов заполнения РСЛОС образуют секретный ключ сообщения или начальные заполнения регистров при генерации шифрующей гаммы.

Как уже отмечалось, в системах GSM поточный шифр A5 используется для закрытия связи между абонентом и базовой станцией, так что фактически при связи двух абонентов шифрование происходит дважды. Это дает возможность строить криптоаналитическую атаку с известным открытым текстом (если заручиться небольшой поддержкой "помощника" на базовой станции). Кроме того, следует отметить, что 64-битовый секретный сеансовый ключ генерируется с помощью другого алгоритма, исходя из "основного" (master) ключа, специфического для каждого пользователя, и открытого случайного 128-битового ключа, передаваемого в незащищенной форме с базовой станции на аппарат абонента. Таким образом, успешное вскрытие одного или нескольких сеансовых ключей открывает дверь для криптоаналитических атак на основной ключ пользователя.

RC4

RC4 — это поточный шифр с переменным размером ключа, разработанный в 1987 г. Ривестом (R. Rivest) для RSA Data Security, Inc. Алгоритм работает в режиме OFB: поток ключей не зависит от открытого текста. Используется S-блок размером 8×8: S₀, S₁, S₂, …, S₂₅₅. Элементы представляют собой перестановку чисел от 0 до 255, а перестановка является функцией ключа переменной длины. В алгоритме применяются два счетчика, i и j, с нулевыми начальными значениями. Для генерации случайного байта выполняются следующие вычисления:

· i = (i + 1) mod 256;

· j = (j + S_i) mod 256.

· Поменять местами S_i и S_j.

· t = (S_i + S_j) mod 256;

· K = S_t.

К используется в операции XOR с открытым текстом для получения шифротекста или в операции XOR с шифротекстом для получения открытого текста. Шифрование выполняется примерно в 10 раз быстрее, чем в DES. Также несложна и инициализация S-блока. Сначала S-блок заполняется по правилу: S₀ = 0, S₁ = 1, …, S₂₅₅ = 255. После этого ключ записывается в массив: K₀, K₁, …, K₂₅₅. Затем при начальном значении j = 0 в цикле выполняются следующие вычисления:

· for i = 0 to 255 do j = (j + S_i + K_i) mod 256

· Поменять местами S_i и S_j.

Компания RSA Data Security, Inc. утверждает, что алгоритм устойчив к дифференциальному и линейному криптоанализу и что он в высокой степени нелинеен. S-блок медленно изменяется при использовании: i и j обеспечивают случайное изменение каждого элемента. RC4 входит в десятки коммерческих продуктов, включая Lotus Notes, AOCE компании Apple Computer и Oracle Secure SQL. Этот алгоритм также является частью спецификации стандарта Сотовой цифровой пакетной передачи данных CDPD (Cellular Digital Packet Data).

Алгоритм инициализации RC4 приведен ниже. Этот алгоритм использует ключ, сохраненный в Key, и имеющий длину l байт. Инициализация начинается с заполнения массива S, далее этот массив перемешивается путем перестановок определяемых ключом. Так как только одно действие выполняется над S, то должно выполняться утверждение, что S всегда содержит все значения кодового слова.

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