М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников



Скачать 93.83 Kb.
Дата07.11.2012
Размер93.83 Kb.
ТипДокументы


УДК 515.171; 681.3.053
М. В. Синьков, Ю. Е. Бояринова,

Я. А. Калиновский, П. В. Трубников

Институт проблем регистрации информации НАН Украины

ул. Н. Шпака, 2, 03113 Киев, Украина

Развитие задачи разделения секрета



Рассмотрен новый подход к методу разделения секрета.

Ключевые слова: разделение секрета, комплексные числа, фундаментальная теорема Гаусса.



Постановка задачи

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

Будем говорить, что участников (законных пользователей) , , осуществляют -хранение секрета С, , если выполняются следующие три условия.

1. Каждый знает некоторую информацию , неизвестную любому другому участнику.

2. Секрет может быть легко вычислен на основе любых секретов .

3. Знание любых частичных секретов не дает возможности восстановить информацию.

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

Выберем совокупность попарно взаимно простых модулей ,.

© М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников

Имеем , — произвольные целые числа, удовлетворяющие условиям
.
Обозначим через произведение всех модулей , .

Пусть далее
.
Обозначим через число, обратное по модулю ,.

Таким образом,
.
Система сравнений

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

Обозначим через наибольшее произведение модулей. Модули следует выбирать так, чтобы разность была велика:
.
Далее требуется, чтобы . В качестве секретов участников возьмем наименьшие неотрицательные вычеты секрета по модулю , так что

Можно утверждать, что множество есть -пороговая схема для секрета .

Доказательством этому является следующее. Пусть, например, известны .

Далее вычислим , , и тогда обратно к по модулю .

Тогда можно вычислить
.
В соответствии с китайской теоремой об остатках

по имеющейся совокупности линейных сравнений может быть определена искомая величина.

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

Теперь предположим, что известны лишь . Тогда

Но это оставляет много возможностей для выбора . Таким образом, необходимо секретов для полного восстановления исходной информации.

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

Рассмотрим некоторые свойства комплексных чисел, которые станут полезными для понимания как построить процедуру разделения секретов в числовой системе второго порядка.

Известно, что сумма, разность, произведение двух целых комплексных чисел также является целым комплексным числом.

Комплексное число будет называться простым комплексным числом, если оно не может быть представлено в виде произведения двух комплексных чисел, отличных от единицы. В противном случае оно называется составным комплексным числом. Отсюда следует, что составное вещественное число является также и составным комплексным числом.

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

Комплексное число будет кратно комплексному числу (или будет делителем числа ), если частное является комплексным числом. Иначе говоря, так как
,
то будет целым числом в том и только в том случае, когда
,
.
Если эти условия не выполняются, то не делится на .

Если таково, что делится на , тогда можно записать, что
,
или является вычетом по модулю .

Можно утверждать, что если и , и выполняются сравнения
, (1)
,
тогда
.
Таким образом, при выполнении этих условий число является вычетом числа по модулю .

Хотя для комплексных чисел не определены понятия «больше» и «меньше», однако представляется возможным определить понятие наименьшего вычета. Основная идея такого определения состоит в том, что поскольку определение комплексного вычета опирается на систему вещественных сравнений (1), то потребовав, чтобы и были соответственно наименьшими вычетами по модулю , получим вполне определенное комплексное число , которое можно назвать наименьшим вычетом числа по модулю , то есть предполагается, что
,
.
Если найдены наименьшие вычеты выражений и
, (2)
,
то наименьший вычет числа по модулю равен
.
Между величинами и (2) существует определенная связь, которая ставит в соответствие каждому возможному значению вполне определенное значение
. (3)
Если и взаимно простые числа, то сравнение (3) имеет одно решение
,
где
,
причем таково, что — целое, меньшее .

Вышесказанное позволяет сделать вывод, что в поле комплексных чисел может быть построена непозиционная система счисления, аналогичная непозиционной системе счисления над полем комплексных чисел [3].

Таким образом, вся процедура разделения секретов может быть сведена к вычислениям в поле комплексных чисел. С точки зрения производительности вычислений этот путь более сложен. Тогда необходимо учесть и применять фундаментальную теорему Гаусса об изоморфизме в классах вещественных и комплексных чисел [4].

Фундаментальная теорема Гаусса. По заданному комплексному модулю , норма которого равна и для которого и являются взаимно простыми числами, каждое целое комплексное число сравнимо с одним и только одним вычетом из ряда .

Из теории чисел известно, что для двух взаимно простых чисел и можно найти такие два целых числа и , что

Выражение , посредством которого устанавливается соответствие между комплексным и вещественным вычетом по модулю , называется коэффициентом изоморфизма.

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

Рассмотрим пример. Определим вещественные наименьшие вычеты, соответствующие комплексным наименьшим вычетам по модулю .

Из теории чисел известно, что . Для данного примера .

Тогда коэффициент изоморфизма .

Таким образом, комплексным вычетам соответствуют такие вещественные вычеты


–3 + 3i

1

–3 + 4i

19

–2 + 2i

9

–2 + 3i

2

–2 + 4i

20

–2 + 5i

13

–1 + i

17

–1 + 2i

10

–1 + 3i

3

–1 + 2i

21

–1 + 5i

14

–1 + 6i

7

0 + 0i

0

i

18

2i

11

3i

4

4i

22

5i

15

6i

8

1 + 2i

12

1 + 3i

5

1 + 4i

23

1 + 5i

16

2 + 3i

6

2 + 4i

24

Выводы

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

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


  1. Берник В., Матвеев С., Харин Ю. Математические и компьютерные основы криптологии. — М.: Новое знание, 2003.

  2. Введение в криптографию / Под ред. В.В. Ященко. — С-Пб.: Питер, 2001.

  3. Акушский И., Юдицкий Д. Машинная арифметика в остаточных классах. — М.: Советское радио, 1968.

  4. Синьков М.В., Губарени Н.М. Непозиционное представление в многомерных числовых системах. — К.: Наук. думка, 1979.


Поступила в редакцию 11.12.2003

90

Похожие:

М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconМ. В. Синьков, Я. А. Калиновский, Т. В. Синькова, Ю. Е. Бояринова
Рассмотрены новые применения квадриплексных чисел в таких важных областях как криптография с открытым ключом и цифровая фильтрация...
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconМ. В. Синьков, Я. А. Калиновский, Ю. Е. Бояринова, Т. В. Синькова
Целью работы является повышение эффективности моделирования различных процессов, описываемых такими дифференциальными уравнениями...
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconМ. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, Т. В. Синькова
Рассмотрены алгоритмы проведения арифметических и алгебраических операций, построение таких нелинейностей как экспонента, тригонометрические...
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconЮ. Е. Бояринова, П. В. Трубников
Рассмотрена возможность использования двойных чисел для решения задачи разделения секрета
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconЯ. А. Калиновский, М. В. Синьков, Т. В. Синькова
Рассмотрено построение логарифмической функции от кватерниона. Предложен вывод основного выражения и сопоставление с логариф-мом...
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconЯ. А. Калиновский, Т. Г. Постникова, М. В. Синьков, Т. В. Синькова
Целью данной работы является исследование возможности построения со-пряженных элементов в различных гиперкомплексных числовых системах,...
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconМ. В. Синьков, Я. А. Калиновский, Т. В. Синькова
Изучены особенности алгоритмов выполнения линейных и нелинейных операций в системе обобщенных комплексных чисел. Успешное решение...
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconРедкоземельные элементы в щелочно-карбонатных метасоматитах северного урала
А. В. Калиновским (Калиновский, 1990; Калиновский, Суханов, 1985). Эти образования были отнесены им к полевошпатовым метасоматитам...
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconПротоиерей Александр Трубников
В оригинале сноски находятся в конце соответствующей страницы, здесь сразу же за текстом!
М. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников iconПетр Калиновский
Издание православного братства во имя Воздвижения Честного и Животворящего Креста Господня
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org