Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,118

NEW ENCRYPTION METHOD USING A SEQUENCE OF QUASI-RANDOM NUMBERS

Reizlin V.I. 1
1 Institute of Cybernetics
Разработан криптостойкий метод шифрования информации, основанный на специальных перестановках натурального ряда и применении квазислучайных последовательностей. Рассматривается семейство равномерно распределенных последовательностей, обобщающих аналогичные конструкции Соболя. В таких последовательностях все их последовательные участки определенной длины имеют хорошее распределение. При шифровании данных предлагается использовать специальные перестановки натурального ряда (перемешивания). При этом одна и та же перестановка натурального ряда может быть получена различными перемешиваниями и ни по какому начальному участку перестановки натурального ряда нельзя восстановить последовательности, посредством которых эта перестановка была получена. В связи с этим и непериодичностью квазислучайных последовательностей предлагаемый метод шифрования свободен от проблемы «известного текста». Трудности, связанные с вычислением перестановок, снимаются, если представлять их в виде полиномов над конечными кольцами.
We have developed a cryptographically strong data encryption method based on special permutations of the natural numbers and the application of quasi-random sequences. We consider a family of uniformly distributed sequences generalizing the similar Sobol’s constructions. The successive sections of a certain length in such sequences have a good distribution. We offer to encrypt data to use special permutation natural numbers (mixing). In this case, the same permutation of natural numbers can be obtained by various mixings and no initial permutation portion cannot restore sequences through which this permutation was obtained. In this regard, and what quasi-random sequence is not periodic proposed encryption method is free from the problem of «known text». Difficulties associated with the calculation of permutations removed if present them in the form of polynomials over finite rings.
data encryption
quasi-random sequences
pseudorandom sequences
cryptographic strength
problem of «known text»
1. GOST 28147-89. Available at: http://protect.gost.ru/v.aspx?control=7&id=139177 (accessed 2 December 2014).
2. Vildanov R.R., Meshcheryakov R.V., Bondarchuk S.S. Proceedings of Tomsk State University of Control Systems and Radioelectronics, 2012, no 1, pp. 108–111.
3. Demin A.Yu. and Reizlin V.I. Problems of Informatics, no 4(12), 2011, pp. 6-15.
4. Levitan Ju.L., Sobol’ I.M. Matematicheskoe modelirovanie, 1990, Vol 2, no 8, pp. 119–126.
5. Orlov V.A., Reizlin V.I.. Bulletin of the Tomsk Polytechnic University, 2012, Vol. 320, no 2, pp. 24–26.
6. Spesivcev A.V., Vegner V.A., Krutjakov A.Ju., Seregin V.V., Sidorov V.A. Zashhita informacii v personal’nyh JeVM [Data protection in personal computers]. Moscow: Radio i svjaz’, 1993. 191 p.
7. Hodashinskij I.A., Meshcheryakov R.V., Rubanov S.A. Voprosy zashhity informacii. no 4(102), 2013. pp. 67–72.
8. Hodashinskij I.A., Savchuk M.V., Gorbunov I.V., Meshcheryakov R.V. Proceedings of Tomsk State University of Control Systems and Radioelectronics, 2011. no 2–3, pp. 236–248.
9. FIPS PUB 197, 2001. Available at: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf (accessed 2 December 2014).
10. FIPS PUB 46-3, Federal Information Processing Standards Publication. Available at: http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf (accessed 2 December 2014).
11. Knuth Donald E., The Art of Computer Programming, vol. 2, ch. 3, Addison-Wesley, 1968.
12. R. Lidl and H. Niederreiter, Finite Fields (Encyclopedia of Mathematics and its Applications), Addison-Wesley, 1983.
13. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, Philadelphia: SIAM, 1992.
14. Reyzlin V.I. and Tartakovsky E.A. Solving Problems of Adaptive Optics Using Parallel Algorithms Based on the CUDA Technology, 7th International Forum on Strategic Technology (IFOST-2012), vol. 1, pp. 621–623, Tomsk, September 18-21, 2012.
15. Sobol’ I.M., Zh. Vychisl. Mat. Mat. Fiz., 7:4, 1967, pp. 784–802.

Шифрование данных – давно и широко применяемый метод защиты информации. Существует довольно много различных способов шифрования, есть даже стандартные – такие, как американские новый стандарт шифрования Advanced Encryption Standard (AES) [9] и старый Data Encryption Standard (DES) [10], или ГОСТ 28147-89 – российский стандарт [1]. Обладая несомненными достоинствами, все они имеют и недостатки, порой весьма существенные. Так, например, старый американский стандарт DES рассчитан на реализацию в специальных электронных устройствах, и это существенно ограничивает возможности его использования, а алгоритм, положенный в основу российского стандарта, настолько громоздок, что его программная реализация чрезвычайно сложна и практически лишена смысла из-за крайне низкого быстродействия. Недостатком же алгоритма AES можно считать его слабое теоретическое исследование, поэтому он может содержать неявные уязвимости, которые могут проявиться только через некоторое время с момента начала его распространения.

Методы шифрования с использованием псевдослучайных чисел

Очень популярными являются методы шифрования с использованием последовательностей псевдослучайных чисел (далее – ПСЧ). Они просты, легко реализуются и модифицируются, имеют высокое быстродействие.

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

Обычно для получения псевдослучайных чисел используют конгруэнтные генераторы, например [2, 11]. Они вырабатывают ПСЧ αi, описываемые соотношением

rejz01.wmf

где a и b – специальным образом выбранные константы, а значение M обычно выбирается равным величине наибольшего целого числа, представляемого машинным словом. Очевидно, что последовательности, вырабатываемые по этому правилу, имеют период, равный М. При шифровании больших текстов периодичность приводит к снижению криптостойкости. Можно строить ПСЧ и с большими периодами. Известен ряд генераторов с очень большими периодами [4].
Однако число хороших генераторов как с обычными, так и с большими периодами весьма невелико, что способствует облегчению раскрытия зашифрованных данных.

Построение квазислучайных последовательностей

Можно, однако, использовать все достоинства ПСЧ-шифрования, применяя квазислучайные последовательности вместо псевдослучайных. Эти последовательности не периодичны, что позволяет применять их для шифрования данных произвольного объема. Квазислучайными называют последовательности, распределение элементов в которых в некотором смысле беспорядочно. Это распределение не обязано имитировать независимость соседних значений.

Последовательность Xn точек из d-мерного куба Id = [0,1)×...×[0,1) называется равномерно распределенной в Id, если для любого блока B = [a1,b1)×[a2,b2)× ...×[ad, bd), где 0 ≤ ai, bi ≤ 1 выполняется соотношение rejz02.wmf. Здесь rejz03.wmf означает копроизведение. Другими словами, последовательность равномерно распределена, если при больших n количество ее точек, попавших в какой-либо блок, пропорционально его объему. Если разбить куб на несколько равновеликих частей, то в каждой из них (при достаточно больших n) окажется примерно одинаковое число точек последовательности.

Ряд квазислучайных последовательностей был получен в [13, 15]. Подобные последовательности обычно называют ЛП0-последовательностями, или последовательностями Соболя. В работе [5] получено новое семейство квазислучайных последовательностей, моделирующих хорошее равномерное распределение, как для больших, так и для малых значений числа элементов. Не отступая от традиции, распространим это название и на наши конструкции, так как обозначение «ЛП» в нашем контексте может означать, что любой последовательный участок Xn хорошо распределен.

Эти последовательности строятся следующим образом.

Пусть q = рn, где р – простое число. Назовем q-и отрезками ранга s интервалы rejz04.wmf, 0 ≤ t ≤ qs–1. Эти отрезки получаются при разбиении интервала I = [0,1) на qs равных отрезков. Обобщая это определение на многомерный случай, назовем q-ым блоком ранга s параллелепипед B1×...×Bd в d-мерном кубе Id = [0,1)×...×[0,1), где Bi – q-ые отрезки рангов rejz05.wmf соответственно, причем rejz06.wmf.

Таким образом, q-ые отрезки – это просто одномерные q-ые блоки.

Последовательные участки множества целых неотрицательных чисел kqs + {0,qs – 1}, k = 0, 1, 2, ... назовем q-ыми участками ранга s. Точно так же будем называть и соответствующие участки произвольных последовательностей. Последовательность Xn точек из Id назовем аналогично [5, 13] ЛП-последовательностью, если каждый ее q-ый участок ранга s имеет ровно по одной общей точке с каждым q-ым блоком того же ранга. Как показано в [5], имеет место теорема 1:

1. Проекции ЛП-последовательности на k-мерные грани куба Id также являются ЛП-последовательностями, и ЛП-последовательности равномерно распределены в Id.

Приведем примеры ЛП-последовательностей.

Любое число x из интервала I = [0, 1) можно записать в q-ой системе счисления в виде rejz07.wmf, 0 ≤ xn ≤ q – 1. Заметим, что q-но рациональные числа, т.е. числа вида rejz08.wmf, 0 ≤ t ≤ qs – 1 имеют две различных q-ых записи:

rejz09.wmf и rejz10.wmf.

Каждое неотрицательное целое число n
можно записать в q-ной системе счисления в виде n = n0 + n1q + n2q2 + … + nsqs, 0 ≤ ni ≤ q – 1 и n ≠ 0. Обозначим номер старшей q-ой цифры как r(n). Число rejz11.wmf назовем инверсным к n. Сопоставим каждому n q-но рациональное число rejz12.wmf. Таким образом, множество целых неотрицательных чисел вкладывается отображением h в интервал I = [0,1). Очевидно, что последовательность h(n) является одномерной ЛП-последовательностью.

На самом деле справедливо даже более сильное утверждение:

Любые qs последовательных точек из rejz13.wmf лежат в разных q-ых отрезках ранга s.

Построим теперь целое семейство ЛП-последовательностей.

Каждому целому неотрицательному числу n = n0 + n1q + … + nsqs, представленному его q-ой записью, сопоставим бесконечномерный вектор rejz14.wmf, n1,…,ns, 0, 0,… >.

Пусть A = (aij)i, j∈{0,1,…,∞}, 0 ≤ aij ≤ q – 1, бесконечная матрица над конечным полем Fq, такая, что все ее подматрицы As = (aij), i, j∈{0,1,…,s} не вырождены, и пусть A(n) – число, соответствующее произведению rejz15.wmf,
(вычисления здесь проводятся в арифметике поля Fq). Тогда последовательность h(A(n)) – ЛП-последовательность и для h(A(n)) справедливо утверждение теоремы 1 [5].

Методы шифрования с использованием квазислучайных чисел

Пусть выбрана последовательность A = {a0, a1,… as…}, где каждое ai – натуральное число, большее 1. И пусть m = 1, m1 = a0,..., ms = ms – 1·as – 1. Любое целое положительное число n может быть представлено в виде n = n0 + n1m1 + … + nsms, где ni – целые числа, удовлетворяющие неравенствам 0 ≤ ni ≤ ai – 1 . Пусть теперь для каждого i выбрана некоторая перестановка Pi множества {0,…, ai – 1}, оставляющая на месте 0.

Бесконечная непериодическая последовательность чисел α(n) = P0(n0) + P1(n1)m1 + … + Ps(ns)ms может использоваться в качестве шифрующей последовательности вместо ПСЧ. Способ построения таких последовательностей назовем (A, P)-
перемешиванием, где P – последовательность рассмотренных выше перестановок. Все способы повышения криптостойкости ПСЧ-методов [6] применимы и для построенных последовательностей. Однако при их бесхитростном применении, например, когда все ai равны друг другу и все Pi представляют собой одну и ту же перестановку, проблема известного текста, так же как и для ПСЧ-шифрования, является слабостью метода.

Речь идет о следующем. Предположим, что шифр неизвестен, но имеется часть исходного текста и соответствующая ему часть зашифрованного, и кроме этого имеется возможность добавлять записи к тексту и проверять зашифрованный текст до и после добавления известной записи. Если шифр представляет собой последовательность чисел, каждое из которых может быть получено из предыдущего, то весь исходный текст можно восстановить из зашифрованного. Все последовательности, элементы которых вычисляются с помощью рекуррентных соотношений, имеют этот недостаток. Все ПСЧ-последовательности и последовательности, полученные (A, P)-перемешиванием с равными ai и Pi, рекуррентно вычислимы, и поэтому их вряд ли стоит применять для шифрования данных без дополнительных усовершенствований, ряд из которых описан в [6–8].

В общем случае (A, P)-перемешивание приводит к шифрам, восстановить которые при известном исходном тексте можно лишь, если известна практически вся последовательность A и все перестановки Pi.

Более изощренным, но и более криптостойким является метод, рассматривае-
мый ниже.

Пусть D = {d0,d1,…,di,…} какая-либо последовательность натуральных чисел, больших 1. Разобьем натуральный ряд на бесконечное число участков ωi с длинами di.
Каждое натуральное число n может быть охарактеризовано двумя номерами s и r, где s – номер участка, которому принадлежит n, а r – его порядковый номер на этом участке.

Переставим числа в каждом участке, применив к номерам r некоторую перестановку Qi множества {0,…, di – 1}, и после этого поменяем порядок следования самих участков, применив к номерам s некоторое (A, P)-перемешивание. Полученную перестановку натурального ряда назовем (A, P, D, Q)-перемешиванием.

Нетрудно проверить следующие утверждения:

1. Одна и та же перестановка натурального ряда может быть получена различными (A, P, D, Q)-перемешиваниями;

2. Ни по какому начальному участку перестановки натурального ряда нельзя восстановить последовательности A, P, D и Q,
посредством которых эта перестановка была получена.

Таким образом (A, P, D, Q)-перемешивание можно эффективно использовать для шифрования текстов любой длины, проблема известного исходного текста при этом не возникает.

Трудности, связанные с вычислением перестановок снимаются, если представлять их в виде полиномов над конечными кольцами. Известно [12], что любая функция над конечным полем может представляться полиномом.

Кроме того, эффективность метода может быть увеличена с помощью параллельных вычислительных технологий [3, 14].

Рецензенты:

Погребной В.К., д.т.н, профессор, профессор кафедры «Информатики и проектирования систем», Национальный исследовательский Томский политехнический университет, г. Томск;

Мещеряков Р.В., д.т.н, профессор, профессор кафедры комплексной информационной безопасности электронно-вычислительных систем, Томский государственный университет систем управления и радиоэлектроники, г. Томск.

Работа поступила в редакцию 16.12.2014.