Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

ORGANIZATION OF DATA EXCHANGE USING A SYSTEM OF RESIDUAL CLASSES

Magomedov Sh.G. 1 Mustafaev A.G. 1
1 Dagestan state technical university
Traditional technology of protect restricted information generally involves the use of encryption methods. However, the requirements for such systems, strong enough and, therefore, cumbersome to implement and costly to operate, which often makes them less suitable and difficult to use. This paper proposes a procedure for organizing the process of reception and transmission of data restricted to using the system of residual classes, as to close the data and to perform transformations. The system of residual classes has a number of significant advantages, since other number system, which reduces the bit data to be processed, representing them in the modular code system relatively simple modules, and has the ability to detect and correct errors. The algorithms that implement this procedure are developed.
system of residual classes
algorithm
data reception and transmission
data protection
encryption keys
Технология обеспечения защиты информации ограниченного доступа предполагает использование различных методов шифрования. Однако требования, предъявляемые к системам шифрования, достаточно строгие и, как следствие, не тривиальны в реализации и затратные в эксплуатации, что часто делает их малопригодными и затруднительными для использования. В данной работе предлагается процедура закрытия информации, опирающаяся на использование системы остаточных классов (СОК) [1, 2]. Хотя уровень стойкости к злоумышленным действиям предлагаемой процедуры ниже, чем у существующих методов шифрования, процедура имеет важное преимущество: она достаточно проста в реализации и вполне приемлема для большинства служебных и приватных сообщений, передачи конфиденциальной информации. Безусловно, для передачи особо важных и секретных данных должны быть задействованы стойкие методы и процедуры, в частности, методы шифрования.

Другие достоинства предлагаемой процедуры по сравнению с существующими системами шифрования:

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

Кратко в сжатой форме напомним основные положения СОК [3], одновременно описывая место каждой характеристики СОК в предлагаемой системе ограничения доступа к передаваемым данным. СОК - это непозиционная система счисления, числа в которой представляются остатками от деления на выбранную систему оснований , где числа в системе взаимно просты. Как будет ясно из дальнейшего пояснения, именно этот набор чисел и является основой системы обеспечения конфиденциальности данных. Диапазон представимых чисел от 0 до . Передаваемая информация будет представлена в виде последовательности целых положительных чисел Ai. Каждое целое положительное число А представляется в виде набора наименьших положительных остатков (вычетов) от деления числа А на выбранные основания , результат можно записать в виде А=( ) - это и есть запись числа A в СОК. Основные операции, связанные с преобразованием чисел в процессе их передачи и приема, могут быть сведены к операциям сложения и умножения целых положительных чисел. При этом операции сложения, вычитания и умножения над числами в СОК производятся независимо по каждому основанию без переносов между разрядами (основаниями). Если исходные числа А, В, их сумма А+В и их произведение находятся в диапазоне [0,P), то результаты операций сложения А+В и умножения  могут быть однозначно представлены соответственно остатками  и  по тем же основаниям , то есть А=( ), B=( ), А+В=( ),А*B =( ).

После получения данных необходимо их обратно преобразовать из СОК в ППС. Указанная задача рассмотрена в [4]. Большинство известных алгоритмов преобразования из СОК в ППС основаны на китайской теореме об остатках, в которой приводится следующее соотношение для обратного преобразования [1]: если число  в СОК по модулю , то

,

где , а  есть решения уравнений .

Данная операция является одной из наиболее трудоемких и обычно выполняется после завершения всех вычислений и преобразований, связанных с приемом-передачей данных. Для повышения быстродействия во многих алгоритмах используются преимущества табличных методов. Характерная особенность известных алгоритмов - хранение констант СОК в памяти, таких как: модули, веса позиционных представлений, базисы и др.

Отметим, что при вычислении базисов СОК  наибольшие временные затраты связаны с операциями нахождения обратных весов в уравнении , где - целое положительное число, называемое весом , - остаток от деления полученной величины на модуль .

Таким образом, основные характеристики определяются свойствами набора простых чисел . Предлагается следующая процедура их выбора.

1. Предварительно формируется база всех простых чисел, не превосходящих заданного числа N. Выбор числа N определяется особенностями предметной области, в которой решается проблема приема-передачи данных.

Рассмотрим вначале действия субъекта, передающего информацию.

2. Исходные данные о субъектах, передающем и принимающем информацию, записываются последовательно в виде строки; к этим данным могут быть добавлены (по договоренности сторон) конфиденциальные сведения, известные только передающей и принимающей сторонам, а также дописываются дата и интервал времени передачи с точностью до одной минуты. Полученная строка оцифровывается любым способом; например, путем сопоставления каждому знаку его ASCII кода. В результате получаем число D, однозначно соответствующее данной паре субъектов - передающего и принимающего информацию.

3. Полученное число D разбивается на блоки, каждый из которых как число не превосходит числа N. Все блоки для данного числа складываются по модулю N; в результате получается число M. Если , то M заменяется на , так что всегда выполнено неравенство . Очевидно, значение M зависит от атрибутов как передающего субъекта, так и принимающего.

4. Из базы простых чисел выбирается наибольшее простое число P, меньшее числа M. Полагаем , , вычисляем  и находим , где [ ] - знак целой части числа. (Коэффициент  введен для того, чтобы, с одной стороны, число n простых чисел в окончательном наборе  не оказалось малым, а с другой стороны, соседние простые числа в наборе достаточно сильно различались. Дополнительные пояснения по выбору R1 и n0 приводятся ниже.) Выбираем из базы простых чисел наибольшее простое число P2, меньшее Q2. Процедура формирования простых чисел продолжается аналогичным образом по формулам: ,где  и  - наибольшее целое число, меньшее . Процедура продолжается до тех пор, пока либо достигнем , либо при некотором  получим .Так как , то очевидно  для всех j.

5. Набор чисел  и есть искомый. Отметим, в полученном наборе простые числа расположены не в порядке возрастания, как описано выше, а в порядке убывания.

6. Передаваемое сообщение, аналогично пункту 3, записывается в виде текстовой строки, оцифровывается (получаем число C) и разбивается на блоки , каждый из которых по величине не превосходит значения . Затем каждое из чисел на основе одного из разработанных в {добавить ссылку} алгоритмов записывается в СОК. Получаем множество наборов , где (напомним) . Сформированный набор  с приписанным именем передающей стороны и посылается оппоненту по процессу приема-передачи.

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

1. По имени отправителя формируются все данные об отправителе, необходимые для построения набора , который и формируется на основе описанного выше алгоритма - все данные, необходимые для его построения, у принимающей стороны имеются.

2. На основе обратного преобразования из СОК в ПСС восстанавливаются блоки ,  и формируется число .

3. Полученное число C переводится в символьную форму на основе преобразования, обратного использованному в пункте 2 передающей стороны в процессе оцифровывания текста. Например, если использовались ASCII-коды для оцифровывания, то для восстановления текста число C записывается в двоичной (восьмеричной или шестнадцатиричной) форме, и каждый блок из 8 битов заменяется на соответствующий ASCII-символ. При использовании ЮНИКОДа версии UTF-16 двоичные блоки состоят из 16 битов. Полученный набор символов и есть исходный текст.

Отметим, что дата и время передачи добавлены в пункте 3 алгоритма для защиты от повторной передачи того же сообщении в другое время и в другой день. Интервал времени в одну минуту выделен в связи с тем, что в процессе подготовки передаваемого сообщения и его передачи время могло немного измениться.

Опишем возможный способ разбиения числа Cна блоки. , ,  - остаток от деления  на . Аналогично разбивается на блоки число D.

Рассмотрим возможный способ выбора числа N. Основное требование: N должно быть достаточно большим, чтобы количество наборов  должно быть больше числа возможных субъектов, которые могут участвовать в процессе приема-передачи сообщений. Желательно также, чтобы числа  были в среднем достаточно большими (с точки зрения требований безопасности). По соображениям удобства компьютерной реализации целесообразно также, чтобы число N представлялось степенью двойки, то есть . Число возможных субъектов S не превзойдет в ближайшем будущем 50 миллиардов - пятикратное количество числа людей. Пусть - число простых чисел, не превосходящих числа N. Тогда число наборов  пропорционально количеству подмножеств во множестве первых  простых чисел, то есть пропорциональна числу . По теореме Эйлера при больших N справедливо соотношение . Таким образом, получаем следующую эвристическую оценку: , или , где C - коэффициент пропорциональности, отражающий желаемый уровень запаса всех возможных наборов простых чисел. Полагаем C=0.1. Наименьшее целое решение этого неравенства, представимое в виде , равно 256.Следовательно, требование наличия достаточного запаса наборов простых чисел выполняется для любого . По соображениям безопасности и удобства компьютерной обработки (размер двух байтов) предлагается взять .

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

, или .

Получаем: . Так как  и , то ввиду возрастания по  функции  получаем следующую оценку, справедливую для всех возможных значений : .

Достаточно большая база данных по простым числам приведена в [5]. Эта база может использоваться при формировании оснований модулей в СОК.

Наконец, по поводу выбора n0. Поскольку n0 определяет число возможных параллельных преобразований, оптимальное значение n0 должно соответствовать число ядер современного стандартного процессора. Исходя из этого, можно взять .

Оценим стойкость предлагаемого метода закрытия передаваемых данных ограниченного доступа. Для этого произведем оценку числа вариантов, которые необходимо перебрать злоумышленнику, для нахождения истинных значений модулей  путем перебора.

Будем анализировать возможности злоумышленника для наиболее плохой ситуации, когда злоумышленник имеет возможности доступа к внутренним ресурсам компьютера. Именно, пусть злоумышленник может выполнить на компьютере вычисление и, имея доступ к внутренним ресурсам компьютера, может проконтролировать промежуточные значения в памяти компьютера, то есть ему известны остатки  от деления числа R на модули  соответственно. Оценим среднее число наборов, которое должен перебрать злоумышленник для того, чтобы найти истинные значения , зная R и , при условии, что все сочетания равновероятны. Будем предполагать также, что длины всех модулей приблизительно одинаковы и лежат в пределах от  до l.

Общее количество возможных значений каждого модуля равно . Отсюда следует, вероятность обнаружения истинного набора значений  при одной попытке равна , а среднее число испытаний при полном переборе равно: , где  - общее число всех наборов. Здесь  есть вероятность того, что (i-1) попытки были неудачными, а на i-ой попытке злоумышленнику удалось найти истинный набор . Из формулы видно, что μ является средним значением для геометрического распределения, и по известной формуле получаем . Отметим, что числа k и l связаны соотношением , где n- разрядность чисел, которые преобразуются на основе СОК; обычно это значение соответствует разрядности процессора.

Например, для 64-разрядного процессора можно взять k=8, l=8 и d=2. Тогда имеем: , то есть процессору, имеющему тактовую частоту 5 ГГц, потребуется время равное  сек только на перебор вариантов, что составляет более 11,7 лет непрерывной работы процессора. Последнее означает, что злоумышленник практически не имеет никаких реальных возможностей обнаружить истинный набор оснований .

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

Рецензенты:

  • Рехвиашвили С. Ш., д.ф-м.н., с.н.с., НИИ прикладной математики и автоматизации КБНЦ РАН, КБР, г. Нальчик.
  • Росс Г. В., д.т.н., профессор, зам. директора ФГУП ВНИИ ПВТИ, г. Москва.