Шифрование данных – давно и широко применяемый метод защиты информации. Существует довольно много различных способов шифрования, есть даже стандартные – такие, как американские новый стандарт шифрования Advanced Encryption Standard (AES) [9] и старый Data Encryption Standard (DES) [10], или ГОСТ 28147-89 – российский стандарт [1]. Обладая несомненными достоинствами, все они имеют и недостатки, порой весьма существенные. Так, например, старый американский стандарт DES рассчитан на реализацию в специальных электронных устройствах, и это существенно ограничивает возможности его использования, а алгоритм, положенный в основу российского стандарта, настолько громоздок, что его программная реализация чрезвычайно сложна и практически лишена смысла из-за крайне низкого быстродействия. Недостатком же алгоритма AES можно считать его слабое теоретическое исследование, поэтому он может содержать неявные уязвимости, которые могут проявиться только через некоторое время с момента начала его распространения.
Методы шифрования с использованием псевдослучайных чисел
Очень популярными являются методы шифрования с использованием последовательностей псевдослучайных чисел (далее – ПСЧ). Они просты, легко реализуются и модифицируются, имеют высокое быстродействие.
Принцип шифрования очень прост: на данные, подлежащие защите, с помощью операции «исключающее или» байт за байтом, либо слово за словом (или в каком-либо другом порядке) накладывается сгенерированная ПСЧ – шифр. Расшифровка сводится к повторному наложению той же последовательности на зашифрованные данные (для этого-то и применяется «исключающее или»). Зашифрованный текст достаточно труден для раскрытия, если длина шифра превышает длину всего шифруемого текста и если неизвестна никакая значительная часть исходного текста.
Обычно для получения псевдослучайных чисел используют конгруэнтные генераторы, например [2, 11]. Они вырабатывают ПСЧ αi, описываемые соотношением
где a и b – специальным образом выбранные константы, а значение M обычно выбирается равным величине наибольшего целого числа, представляемого машинным словом. Очевидно, что последовательности, вырабатываемые по этому правилу, имеют период, равный М. При шифровании больших текстов периодичность приводит к снижению криптостойкости. Можно строить ПСЧ и с большими периодами. Известен ряд генераторов с очень большими периодами [4].
Однако число хороших генераторов как с обычными, так и с большими периодами весьма невелико, что способствует облегчению раскрытия зашифрованных данных.
Построение квазислучайных последовательностей
Можно, однако, использовать все достоинства ПСЧ-шифрования, применяя квазислучайные последовательности вместо псевдослучайных. Эти последовательности не периодичны, что позволяет применять их для шифрования данных произвольного объема. Квазислучайными называют последовательности, распределение элементов в которых в некотором смысле беспорядочно. Это распределение не обязано имитировать независимость соседних значений.
Последовательность Xn точек из d-мерного куба Id = [0,1)×...×[0,1) называется равномерно распределенной в Id, если для любого блока B = [a1,b1)×[a2,b2)× ...×[ad, bd), где 0 ≤ ai, bi ≤ 1 выполняется соотношение 
. Здесь 
означает копроизведение. Другими словами, последовательность равномерно распределена, если при больших n количество ее точек, попавших в какой-либо блок, пропорционально его объему. Если разбить куб на несколько равновеликих частей, то в каждой из них (при достаточно больших n) окажется примерно одинаковое число точек последовательности.
Ряд квазислучайных последовательностей был получен в [13, 15]. Подобные последовательности обычно называют ЛП0-последовательностями, или последовательностями Соболя. В работе [5] получено новое семейство квазислучайных последовательностей, моделирующих хорошее равномерное распределение, как для больших, так и для малых значений числа элементов. Не отступая от традиции, распространим это название и на наши конструкции, так как обозначение «ЛП» в нашем контексте может означать, что любой последовательный участок Xn хорошо распределен.
Эти последовательности строятся следующим образом.
Пусть q = рn, где р – простое число. Назовем q-и отрезками ранга s интервалы 
, 0 ≤ t ≤ qs–1. Эти отрезки получаются при разбиении интервала I = [0,1) на qs равных отрезков. Обобщая это определение на многомерный случай, назовем q-ым блоком ранга s параллелепипед B1×...×Bd в d-мерном кубе Id = [0,1)×...×[0,1), где Bi – q-ые отрезки рангов 
соответственно, причем 
.
Таким образом, 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-ой системе счисления в виде 
, 0 ≤ xn ≤ q – 1. Заметим, что q-но рациональные числа, т.е. числа вида 
, 0 ≤ t ≤ qs – 1 имеют две различных q-ых записи:
и 
.
Каждое неотрицательное целое число n
можно записать в q-ной системе счисления в виде n = n0 + n1q + n2q2 + … + nsqs, 0 ≤ ni ≤ q – 1 и n ≠ 0. Обозначим номер старшей q-ой цифры как r(n). Число 
назовем инверсным к n. Сопоставим каждому n q-но рациональное число 
. Таким образом, множество целых неотрицательных чисел вкладывается отображением h в интервал I = [0,1). Очевидно, что последовательность h(n) является одномерной ЛП-последовательностью.
На самом деле справедливо даже более сильное утверждение:
Любые qs последовательных точек из 
лежат в разных q-ых отрезках ранга s.
Построим теперь целое семейство ЛП-последовательностей.
Каждому целому неотрицательному числу n = n0 + n1q + … + nsqs, представленному его q-ой записью, сопоставим бесконечномерный вектор 
, n1,…,ns, 0, 0,… >.
Пусть A = (aij)i, j∈{0,1,…,∞}, 0 ≤ aij ≤ q – 1, бесконечная матрица над конечным полем Fq, такая, что все ее подматрицы As = (aij), i, j∈{0,1,…,s} не вырождены, и пусть A(n) – число, соответствующее произведению 
,
(вычисления здесь проводятся в арифметике поля 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.
Библиографическая ссылка
Рейзлин В.И. НОВЫЙ МЕТОД ШИФРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ ПОСЛЕДОВАТЕЛЬНОСТЕЙ КВАЗИСЛУЧАЙНЫХ ЧИСЕЛ // Фундаментальные исследования. – 2014. – № 12-3. – С. 505-508;URL: https://fundamental-research.ru/ru/article/view?id=36139 (дата обращения: 19.04.2024).