Псевдослучайный алгоритм (Hvyf;kvlrcgwudw glikjnmb)
 | Эту статью необходимо исправить в соответствии с правилом Википедии об оформлении статей. |
 | В статье есть список источников, но не хватает сносок. |
Псевдослучайный алгоритм шифрования — такой алгоритм шифрования, что каждый блок (символ) исходного текста шифруется своим собственным ключом, причём каждый следующий ключ является следующим членом псевдослучайной последовательности, а основной (базовый) ключ — первым элементом этой последовательности.
Особенности построения
[править | править код]- За основу любого такого алгоритма шифрования может браться любой алгоритм шифрования (зачастую довольно простой), такой алгоритм называется внутренним.
- Исходное сообщение разбивается на некоторое количество блоков, желательно не большее, чем период выбранного генератора псевдослучайных чисел.
- Каждый блок с номером i шифруется выбранным алгоритмом шифрования при помощи i-го ключа (ключ равен i-му члену псевдослучайной последовательности).
- Зашифрованный текст представляет собой совокупности зашифрованных таким образом блоков записанных в той же последовательности.
Выбор внутреннего алгоритма
[править | править код]Выбор внутреннего алгоритма сильно зависит от требований, предъявляемых к псевдослучайному алгоритму шифрования. Так существует ряд задач, для которых даже внутренний алгоритм выбирается наиболее криптостойким, однако куда более широкое распространение получили псевдослучайные алгоритмы, где в качестве внутреннего алгоритма шифрования применяются довольно простой, поэтому сам по себе не криптостойкий алгоритм. Выбор простого алгоритма напрямую связан с требованиями к скорости зашифровки и расшифровки.
Выбор генератора псевдослучайных чисел также зависит от требований к псевдослучайному алгоритму шифрования. Если максимальная длина сообщений довольно большая (от 16 Мб) и требования к длине блока высокие (например не более 1 байта на блок или ещё выше), то даже самые лучшие конгруэнтные генераторы не могут быть использованы в качестве необходимого нам генератора псевдослучайных чисел. Зато, если область применения нашего псевдослучайного алгоритма — шифрование относительно коротких сообщений (длиной меньше 1 Кб), а их актуальность во времени не значительна, то в качестве генератора псевдослучайных чисел может быть выбран довольно простой генератор, что также повысит скорость зашифровки и расшифровки.
Примеры
[править | править код]- Рассмотрим простейший вариант использования подобного алгоритма. В качестве внутреннего алгоритма возьмем шифр Цезаря, размер блока возьмём равным одному символу, а в качестве генератора псевдослучайных чисел возьмем ki+1 = (a ki + b) mod p, то есть каждый следующий ключ нашего алгоритма вычисляется по такой формуле из предыдущего, длину ключа положим равной ~256 бит, соответственно p возьмём 2256, константы a и b положим соответственно (3 + 2255) и 0. Как известно период зацикливания для такого генератора псевдослучайных чисел составляет ~p/4, то есть 2254, что вполне достаточно для того, чтобы зашифровать файл довольно большой длины, исключив возможность многократного повторения цикла, достаточного для проведения частотного анализа. Однако такой алгоритм имеет очевидные недостатки. А именно, зная какую-то часть зашифрованного текста (скажем, криптоаналитик знает, что каждое своё сообщения вы начинаете словом «Привет!»), можно легко восстановить ключ на 1—7 шаге, а значит и все ключи. Это приводит нас к небольшой модернизации этого алгоритма.
- В качестве внутреннего алгоритма возьмём всё тот же шифр Цезаря, размер блока возьмём равным одному символу, в качестве генератора псевдослучайных чисел возьмем mi+1 = (a mi + b) mod p, ki+1 = SumC((a mi + b) mod p), длину ключа также положим равной ~256 бит, соответственно p возьмём 2256, константы a и b положим соответственно (3 + 2255) и 0, а функция SumC — функция вычисляющая сумму цифр числа, при этом базовый ключ это уже не k1, а m1. Заметим, что в этом случае вычисление mi, даже зная ki, весьма затруднительно.
- Один из подобных алгоритмов был разработан и реализован Александром Березинским в период с 2005 по 2009 год. В нем в качестве внутреннего алгоритма был взят алгоритм Цезаря на чаровском круге, отличающийся от обычного шифра Цезаря тем, что вместо 26-символьного алфавита используется таблица ASCII, в качестве же генератора псевдослучайных чисел используется Hi + 1 = Hi7 mod 10100, ki+1 = SumC(H(i)7 mod 10100), где H1 — базовый ключ, длина которого ~332 бит, а SumC — функция, вычисляющая сумму цифр числа. Также предусмотрено от 2 до 10 раундов шифрования (количество раундов равно первой значащей цифре H1 + 1), то есть по окончании зашифровки одного раунда зашифрованный файл подаётся на вход и шифруется снова, причём H1 каждого следующего раунда равен последнему Hn предыдущего.
- Однако, как известно, кроме шифра Цезаря существует множество куда более криптостойких алгоритмов шифрования и куда более хороших генераторов псевдослучайных чисел, чем представленные выше, то есть можно взять в качестве алгоритма шифрования AES, а в качестве генератора псевдослучайных чисел конгруэнтные генераторы по алгоритму, предложенному Национальным бюро стандартов США, который имеет длину периода 224. Однако нетрудно понять, что такой алгоритм будет работать дольше, чем все вышеперечисленные.
Замечания
[править | править код]Все приведенные выше примеры — симметричные алгоритмы шифрования. Никаких сведений об асимметричных псевдослучайных алгоритмах шифрования по состоянию на 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.