Шифр RSA.

Пусть n = pq (q и p - простые), X = Y = Zn – кольцо вычетов по модулю n.

K = {(n, p, q, a, b): a, b Î Zn, n = pq, ab º 1(mod j(n))}, где j - функция Эйлера.

k = (kз, kр), где kз = (n, b) и kр = (n, p, q, a) – ключи. Правила зашифрования и расшифрования для x Î X и y Î Y определяются формулами

Уточним алгебраическую модель шифра, выбрав за основу модель, в которой открытыми и шифрованными текстами служат шифрвеличины и шифробозначения, с которыми оперирует шифр. Назовем выбранную модель опорным шифром. Будем шифровать фрагменты открытого текста одним из априорно заданных правил зашифрования, составляющих опорный шифр. Назовем эти отображения простыми заменами. Простые замены будем выбирать при помощи вспомогательной последовательности, которую назовем ключевым потоком. Ключевой поток может определяться случайным образом или вычисляться детерминированно в зависимости от выбранного ключа шифра. Большинство шифров использует детерминированный ключевой поток.

Определение: Опорным шифром назовем совокупность

S = (U, K, V, E, D),

состоящую из: U и V - множеств шифрвеличин и шифробозначений с которыми оперирует шифр; K – множества ключей (номеров простых замен); E и D – множеств простых замен Ek : U ® V, k Î K, и обратных к ним отображений Dk : Ek(U) ® U.

Если шифр использует s простых замен, то примем в качестве множества ключей опорного шифра множество целых чисел K = {0, 1, …, s – 1}. Опорный шифр определяет способ зашифрования фрагментов открытого текста – шифрвеличин. Для работы с последовательностью шифрвеличин требуется степеньопорного шифра.

Определение: l-й степенью опорного шифра назовем совокупность множеств

Sl = (U l, K l, V l, E (l), D(l)),

где U l, K l, V l - декартовы степени; множество E (l) состоит из отображений , таких что для и

;

множество D (l) состоит из отображений , таких что для и

.

Теперь рассмотрим построение ключевого потока, то есть последовательности k1kl, kj Î K, , номеров простых замен, используемых для зашифрования открытого текста .

Имеется два принципиально разных способа построения такой последовательности.

В первом случае она строится случайно. Устройство, вырабатывающее случайный ключевой поток называется случайным генератором ключевого потока. Формально его можно представить отображением y : N ® K*, (С* - множество слов конечной длины в алфавите С), ставящим в соответствие натуральному числу l последовательность из l испытаний некоторой случайной величины, принимающей значение из K с некоторыми ненулевыми вероятностями. Простейший случайный генератор – игровая рулетка.

Во втором случае шифр имеет некоторое, априорно заданное, конечное множество ключей K. Каждому ключу ĸ Î K и натуральному числу l Î N ставится в соответствие однозначно определенный ключевой поток k1kl, ki Î K, . Этот поток вырабатывается детерминированным генератором ключевого потока.

Определение: пусть

y : K ´ N ® K*

- произвольное отображение, такое, что для любых ĸ Î K, l Î N, и некоторых ki Î K, , y(ĸ, l) = k1kl, причем {y(ĸ, l), ĸ Î K} = K. Назовем последовательность k1kl ключевым потоком, отвечающим ключу ĸ и числу l, а само отображение y - детерминированным генератором ключевого потока.

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

Определение: Совокупность

SН = (Sl, l Î N; y),

- степеней опорного шифра, в которых для зашифрования последовательностей шифрвеличин u1,…,ul по правилу ключевой поток строится с помощью случайного генератора y, назовем алгебраической моделью шифра с неограниченным ключом (или просто шифром с неограниченным ключом).

Определение: Совокупность

SО = (Sl, l Î N; y),

- степеней опорного шифра, в которых для зашифрования последовательностей шифрвеличин u1,…,ul по правилу ключевой поток строится с помощью детерминированного генератора y, назовем алгебраической моделью шифра с ограниченным ключом (или просто шифром с ограниченным ключом).

Криптографические свойства шифра с ограниченным ключом пределяются в первую очередь, свойствами его генератора ключевого потока. Например, если y(ĸ, l) = k’k’, для любого ĸ Î K и подходящего k’ Î K, то получаем «слабый» шифр простой замены. Если y(ĸ, l) = k1kp k1kp… представляет собой периодическую последовательность (в которой |{k1kp}| ³ 2), то получаем более стойкий шифр периодической замены. Например шифр Виженера.