Псевдослучайный алгоритм

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

Особенности построения

• За основу любого такого алгоритма шифрования может браться любой алгоритм шифрования (зачастую довольно простой), такой алгоритм называется внутренним.
• Исходное сообщение разбивается на некоторое количество блоков, желательно не большее, чем период выбранного генератора псевдослучайных чисел.
• Каждый блок с номером i шифруется выбранным алгоритмом шифрования при помощи i-го ключа (ключ равен i-му члену псевдослучайной последовательности).
• Зашифрованный текст представляет собой совокупности зашифрованных таким образом блоков записанных в той же последовательности.

Выбор внутреннего алгоритма

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

Выбор генератора псевдослучайных чисел также зависит от требований к псевдослучайному алгоритму шифрования. Если максимальная длина сообщений довольно большая (от 16 Мб) и требования к длине блока высокие (например не более 1 байта на блок или ещё выше), то даже самые лучшие конгруэнтные генераторы не могут быть использованы в качестве необходимого нам генератора псевдослучайных чисел. Зато, если область применения нашего псевдослучайного алгоритма — шифрование относительно коротких сообщений (длиной меньше 1 Кб), а их актуальность во времени не значительна, то в качестве генератора псевдослучайных чисел может быть выбран довольно простой генератор, что также повысит скорость зашифровки и расшифровки.

Примеры

1. Рассмотрим простейший вариант использования подобного алгоритма. В качестве внутреннего алгоритма возьмем шифр Цезаря, размер блока возьмём равным одному символу, а в качестве генератора псевдослучайных чисел возьмем k_i+1 = (a k_i + b) mod p, то есть каждый следующий ключ нашего алгоритма вычисляется по такой формуле из предыдущего, длину ключа положим равной ~256 бит, соответственно p возьмём 2²⁵⁶, константы a и b положим соответственно (3 + 2²⁵⁵) и 0. Как известно период зацикливания для такого генератора псевдослучайных чисел составляет ~p/4, то есть 2²⁵⁴, что вполне достаточно для того, чтобы зашифровать файл довольно большой длины, исключив возможность многократного повторения цикла, достаточного для проведения частотного анализа. Однако такой алгоритм имеет очевидные недостатки. А именно, зная какую-то часть зашифрованного текста (скажем, криптоаналитик знает, что каждое своё сообщения вы начинаете словом «Привет!»), можно легко восстановить ключ на 1—7 шаге, а значит и все ключи. Это приводит нас к небольшой модернизации этого алгоритма.
2. В качестве внутреннего алгоритма возьмём всё тот же шифр Цезаря, размер блока возьмём равным одному символу, в качестве генератора псевдослучайных чисел возьмем m_i+1 = (a m_i + b) mod p, k_i+1 = SumC((a m_i + b) mod p), длину ключа также положим равной ~256 бит, соответственно p возьмём 2²⁵⁶, константы a и b положим соответственно (3 + 2²⁵⁵) и 0, а функция SumC — функция вычисляющая сумму цифр числа, при этом базовый ключ это уже не k₁, а m₁. Заметим, что в этом случае вычисление m_i, даже зная k_i, весьма затруднительно.
3. Один из подобных алгоритмов был разработан и реализован Александром Березинским в период с 2005 по 2009 год. В нем в качестве внутреннего алгоритма был взят алгоритм Цезаря на чаровском круге, отличающийся от обычного шифра Цезаря тем, что вместо 26-символьного алфавита используется таблица ASCII, в качестве же генератора псевдослучайных чисел используется H_i + 1 = H_i⁷ mod 10¹⁰⁰, k_i+1 = SumC(H(i)⁷ mod 10¹⁰⁰), где H₁ — базовый ключ, длина которого ~332 бит, а SumC — функция, вычисляющая сумму цифр числа. Также предусмотрено от 2 до 10 раундов шифрования (количество раундов равно первой значащей цифре H₁ + 1), то есть по окончании зашифровки одного раунда зашифрованный файл подаётся на вход и шифруется снова, причём H₁ каждого следующего раунда равен последнему H_n предыдущего.
4. Однако, как известно, кроме шифра Цезаря существует множество куда более криптостойких алгоритмов шифрования и куда более хороших генераторов псевдослучайных чисел, чем представленные выше, то есть можно взять в качестве алгоритма шифрования AES, а в качестве генератора псевдослучайных чисел конгруэнтные генераторы по алгоритму, предложенному Национальным бюро стандартов США, который имеет длину периода 2²⁴. Однако нетрудно понять, что такой алгоритм будет работать дольше, чем все вышеперечисленные.

Замечания

Все приведенные выше примеры — симметричные алгоритмы шифрования. Никаких сведений об асимметричных псевдослучайных алгоритмах шифрования по состоянию на 2009 год нет. Существуют как потоковые, так и блочные шифры, реализованные в концепции псевдослучайного алгоритма шифрования.

Литература

1. «Введение в криптографию», под ред. В. В. Ященко.

2. Варновский Н. П. «О стойкости схем электронной подписи с аппаратной поддержкой». Технический отчет. Лаборатория МГУ по математическим проблемам криптографии, 1997.

3. Гэри М., Джонсон Д. «Вычислительные машины и трудно решаемые задачи». М.: Мир, 1982.

4. Impagliazzo R. , Levin L., Luby M. Pseudo-random generation from one-way functions // Proc. 21st Annu. ACM Symp. on Theory of Computing. 1989. P. 12-24.

5. Анохин М. И., Варновский Н. П., Сидельников В. М., Ященко В. В. «Криптография в банковском деле». М.: МИФИ, 1997.

6. Blum M., Micali S. How to generate crytographically strong sequences of pseudo-random bits // SIAM J. Comput. V. 13, No 4, 1984. P. 850-864.

7. Goldwasser S., Micali S., Rackoff C. The knowledge complexity of interactive proof systems // SIAM J. Comput. V. 18, No 1, 1989. P. 186-208.

8. Goldreich O., Micali S., Wigderson A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems // J. ACM. V. 38, No 3, 1991. P. 691-729.

9. Hastad J. Pseudo-random generators under uniform assumptions // Proc. 22nd Annu. ACM Symp. on Theory of Computing. 1990. P. 395-404.

10. Impagliazzo R., Luby M. One-way functions are essential for complexity based cryptography // Proc. 30th Annu. Symp. on Found. of Comput. Sci. 1989. P. 230-235.

Внешние ссылки

1. Простейшие алгоритмы генерации

2. Анализ псевдослучайных последовательностей