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

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

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

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

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

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

Выбор генератора псевдослучайных чисел:

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

Примеры:

1) рассмотрим простейший вариант использования подобного алгоритм: В качестве внутреннего алгоритма возьмем Шифр Цезаря, размер блока возьмем равным одному символу, а в качестве генератора псевдослучайных чисел возьмем k[i+1] = (a*k[i]+b) mod p, то есть каждый следующий ключ нашего алгоритма вычисляется по такой формуле из предыдущего, длину ключа положим равной ~256 бит, соответственно p возьмем 2^256, константы a и b положим соответственно (3+2^255) и 0. Как известно период зацикливания для такого генератора псевдослучайных чисел составляет ~p/4, то есть 2^254 что вполне достаточно для того, чтобы зашифровать файл довольно большой длины исключив возможность многократного повторения цикла, достаточного для проведения частотного анализа. Однако такой алгоритм имеет очевидные минусы, а именно зная какую-то часть зашифрованного текста (скажем криптоаналитик знает, что каждое свое сообщения вы начинаете словом "Привет!"), можно легко восстановить ключ на этом шаге, 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^256, константы a и b положим соответственно (3+2^255) и 0, а функция SumC - функция вычисляющая сумму цифр числа, при этом базовый ключ это уже не k[1], а m[1]. Заметим, что в этом случае вычисление m[i], даже зная k[i] весьма затруднительно.

3) Один из подобных алгоритмов был разработан и реализован Александром Березинским в период с 2005 по 2009 год. В нем в качестве внутреннего алгоритма был взят алгоритм Цезаря на чаровском круге, отличающийся от обычного Шифра Цезаря тем, что вместо 26 символьного алфавита используется таблица ASCII, в качестве же генератора псевдослучайных чисел используется H(i+1)=H(i)^7 mod 10^100, k[i+1] = SumC(H(i)^7 mod 10^100), где H[1] - базовый ключ длина которого ~332 бит, а SumC - функция вычисляющая сумму цифр числа, также предусмотрено от 2 до 10 раундов шифрования (количество раундов равно первой значащей цифре H[1] +1), то есть по окончании зашифровки одного раунда зашифрованный файл подается на вход и шифруется снова, причем H[1] каждого следующего раунда равен последнему H(n) предыдущего.

4) Однако как известно кроме Шифра Цезаря существует множество куда более криптостойких алгоритмов шифрования и куда более хороших генераторов псевдослучайных чисел, чем представленные выше, то есть можно взять в качестве алгоритма шифрования AES, а в качестве генератора псевдослучайных чисел конгруэнтные генераторы по алгоритму, предложенному Национальным бюро стандартов США, который имеет длину периода 2^24. Однако нетрудно понять, что такой алгоритм будет работать дольше чем все вышеперечисленные.

Замечания:

Все приведенные выше примеры - симметричные алгоритмы шифрования. Никаких сведений об асимметричных псевдослучайных алгоритмах шифрования по состоянию на 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. Анализ псевдослучайных последовательностей