Разработка алгоритмов восстановления информации в задаче разделения секрета
Рассмотрены примеры восстановления секрета, используя изоморфный переход к системе действительных чисел, что исключает необходимость вычисления функции Эйлера в гиперкомплексных числовых системах второго порядка. Розглянуто приклади відновлення секрету, використовуючи ізоморфний перехід до системи д...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2004 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2004
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50709 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Разработка алгоритмов восстановления информации в задаче разделения секрета / Ю.Е. Бояринова, Я.В. Одарич, П.В. Трубников // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 107-112. — Бібліогр.: 5 назв. — pос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860178689821507584 |
|---|---|
| author | Бояринова, Ю.Е. Одарич, Я.В. Трубников, П.В. |
| author_facet | Бояринова, Ю.Е. Одарич, Я.В. Трубников, П.В. |
| citation_txt | Разработка алгоритмов восстановления информации в задаче разделения секрета / Ю.Е. Бояринова, Я.В. Одарич, П.В. Трубников // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 107-112. — Бібліогр.: 5 назв. — pос. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Рассмотрены примеры восстановления секрета, используя изоморфный переход к системе действительных чисел, что исключает необходимость вычисления функции Эйлера в гиперкомплексных числовых системах второго порядка.
Розглянуто приклади відновлення секрету, використовуючи ізоморфний перехід до системи дійсних чисел, що виключає необхідність обчислення функції Ейлера в гіперкомплексних числових системах другого порядку.
Examples of restoring a secret using isomorphic transition to the real numbers system what eliminates necessity of Euler function evaluation in the second-order hypercomplex numerical systems are considered.
|
| first_indexed | 2025-12-07T18:01:03Z |
| format | Article |
| fulltext |
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 107
УДК 515.171; 681.3
Ю. Е. Бояринова, Я. В. Одарич, П. В. Трубников
Институт проблем регистрации информации НАН Украины
ул. Н. Шпака, 2, 03113 Киев, Украина
Разработка алгоритмов восстановления информации
в задаче разделения секрета
Рассмотрены примеры восстановления секрета, используя изоморф-
ный переход к системе действительных чисел, что исключает необхо-
димость вычисления функции Эйлера в гиперкомплексных числовых
системах второго порядка.
Ключевые слова: алгоритм Евклида, задача разделения секрета, ком-
плексные числа, двойные числа, дуальные числа.
Двухмерное расширение поля действительных чисел приводит первоначаль-
но к множеству чисел вида bEa + , где ba, — действительные числа, E — не-
который элемент. Это множество чисел с операциями сложения и умножения яв-
ляется двухмерной алгеброй над полем действительных чисел. Имеется только
три различные алгебры второго порядка над полем действительных чисел: ком-
плексные числа 1, 2 -=+ ibia ; дуальные числа 0, 2 =+ eeba ; двойные числа
1, 2 =+ ebea .
Общая формула нормы для этих гиперкомплексных чисел:
22)( baAN r-= , (1)
где 1-=r для комплексных чисел; 0=r для дуальных чисел; 1=r для двойных
чисел.
В этих алгебрах построена теория сравнений, даны понятия простых и со-
ставных чисел. В дальнейшем вместо слова алгебра будем применять термин ги-
перкомплексная числовая система.
Для этих гиперкомплексных чисел может быть построена непозиционная
система счисления, в которой выбираются взаимнопростые комплексные модули
ni mmm ,...,,...,1 и определяются полные системы наименьших комплексных выче-
тов. Важным здесь является вопрос представимости некоторого комплексного
числа в диапазоне множества комплексных чисел Õ
=
=-
n
i
imM
1
.0 Если в процессе
вычислений и работе с остаточными представлениями в действительных числах
© Ю. Е. Бояринова, Я. В. Одарич, П. В. Трубников
Ю. Е. Бояринова, Я. В. Одарич, П. В. Трубников
108
может быть применена функция Эйлера, то при вычислениях в гиперкомплексных
числах такая возможность отсутствует, и требуется в вычислительный процесс
«включать» алгоритм Евклида.
Построение вычетов для этих гиперкомплексных систем происходит сле-
дующим образом.
Теорема. Пусть qipmbiaA +=+= , , и выполняются сравнения:
),(mod Nyqxpbqap rr -º- (2)
),(mod Nxqypaqbp -º- (3)
где }1,0,1{-=r .
Тогда )(mod mbiaA += .
Если найдены наименьшие вычеты выражений (2) и (3)
,rbqap =- r
raqbp ¢=- ,
то наименьший вычет числа A по модулю m равен:
2222 ba
rbar
ba
brrayix
rr
r
-
+¢
+
-
¢+
=+ .
При этом задача разделения секрета может быть сформулирована в различ-
ных гиперкомплексных системах.
Существует два варианта решения задачи, первый из которых базируется на
том, что используется изоморфный переход к системе действительных чисел, а
второй базируется на использовании алгоритма Евклида. При этом исключается
необходимость вычисления функции Эйлера в гиперкомплексных числах.
Алгоритм восстановления
Даны взаимно простые модули и соответствующие им вычеты
1m 2m 3m
1a 2a 3a
причем 321 mmm >> .
Тогда первое приближение исходного числа можно выразить так:
1111 a+= nmM . (1)
Модуль 1m можно выразить через модуль 1m :
Разработка алгоритмов восстановления информации в задаче разделения секрета
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 109
121 x+= mm . (2)
Подставляя (2) в (1), получим:
)(mod 22111121 mnnmM aax º++= .
Используя свойства сравнений, получаем:
)(mod 22111 mn aax º+ ,
откуда:
)(mod 21211 mn aax -º ,
)(mod)( 2
1)(
1121
2 mn m --º jxaa . (3)
С другой стороны, исходное число можно выразить так:
)(mod 3312212 mMnmmM aº+= . (4)
Иначе модуль 21mm можно выразить через модуль 3m :
2321 x+= mmm . (5)
Подставляя (5) в (4), получим:
)(mod 3312223 mMnnm ax º++ ,
))(mod( 31322 mMn -º ax , (6)
)(mod)( 3
1)(
2132
3 mMn m --º jxa .
Подставляя (6) в (4), получаем исходное число:
12
1)(
11213
1)(
213212 )(mod)()(mod)( 23 axaaxa jj +-+-= -- mmmMmmM mm .
Пример 1.
Восстановить исходную величину, если:
251 =m 172 =m 133 =m
111 =a 92 =a 53 =a
Ю. Е. Бояринова, Я. В. Одарич, П. В. Трубников
110
817251 =-=x ,
)17(mod4)17(mod8)119( 1)17(
1 º×-º -jn ,
111114251 =+×=M ,
)13(mod7)13(mod9)1115( 1)13(
2 º×-º -jn .
Тогда исходное число:
3086111717252 =+××=M .
Пример 2.
Восстановить исходную величину, если модули и вычеты заданы комплекс-
ными величинами:
2)41()43(1 =+-+= iix ,
)41(mod2)22( 1)41(
1 iiin i +×--º -+j .
Для вычислений изоморфным переходом получаем действительные числа:
99121~ 15
1 =×=×=n .
Тогда: in 21 -= ,
iiiiM 482)2)(43(1 -=+-+= ,
iiii 1318)32()41)(43(2 +-=+-++=x ,
)32(mod)2(2)32(mod)1318))(48(( 1)32(1)32(
2 iiiiiin ii +-׺++----º -+-+ jj .
Переходя к действительным числам, получаем:
)13(mod51863113~ 11
2 ºº×º×ºn ,
in -=2 .
Тогда:
im 431 += im 412 += im 323 +=
i21 =a i22 -=a i-=3a
Разработка алгоритмов восстановления информации в задаче разделения секрета
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 111
iiiiiM 924)48())(41)(43(2 +=-+-++= .
Пример 3.
Восстановить исходную величину, если модули и вычеты заданы двойными
величинами:
iii +=+-+= 1)56()67(1x ,
)56(mod)1())11(88(( 1)56(
1 iiiin i ++×+-+º -+j .
Для вычислений изоморфным переходом получаем действительные числа
)11(mod723~ 9
1 º×ºn .
Тогда: in 991 += ,
iiiiM 118118)1()99)(67(1 +=++++= ,
iiii 6767)45()56)(67(2 +=+-++=x ,
)45(mod)44()55()45(mod)6767)(112112( 1)45(1)45(
2 iiiiiin ii ++×+º++--º -+-+ jj .
Переходя к действительным числам, получим:
)9(mod881~ 5
2 º×ºn ,
in 442 += .
Тогда:
iiiiiM 690690)118118()44)(56)(67(2 +=+++++= .
Пример 4.
Восстановить исходную величину, если модули и вычеты заданы дуальными
величинами:
im 671 += im 562 += im 453 +=
i111 +=a i882 +=a i663 +=a
im += 51 im 232 += im += 23
i211 --=a i=2a i--= 13a
Ю. Е. Бояринова, Я. В. Одарич, П. В. Трубников
112
iii -=+-+= 2)23()5(1x ,
)23(mod)2())21(( 1)23(
1 iiiin i +-×---º -+j .
Для вычислений изоморфным переходом получаем действительные числа
)9(mod8)1(1~ 5
1 º-׺n .
Тогда: 11 -=n ,
iiiiM 36)21())(5(1 --=--+-+= ,
iiii 1213)2()23)(5(2 +=+-++=x ,
)2(mod)1213()25( 1)32(
2 iiin i ++×+º -+j .
Переходя к действительным числам, получим:
)4(mod31)1(1~ 3
2 º-º-׺n ,
12 -=n .
Тогда:
iiiiM 1621)36()1)(23)(5(2 --=--+-++= .
Материалы данной статьи подготовлены и написаны при участии научного
руководителя докт. техн. наук, профессора М.В. Синькова.
1. Синьков М.В., Губарени Н.М. Непозиционные представления в многомерных числовых
системах. — К.: Наук. думка, 1979. — 138 с.
2. Синьков М.В., Бояринова Ю.Е., Калиновский Я.А., Трубников П.В. Развитие задачи разде-
ления секрета // Реєстрація, зберігання і оброб. даних. — 2003. — Т. 5, № 4. — С. 90–96.
3. Бояринова Ю.Е., Трубников П.В. Расширение задачи разделения секрета для случая ис-
пользования двойных чисел // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. —
С. 47–52.
4. Бояринова Ю.Е., Одарич Я.В., Трубников П.В. Реализация алгоритма Евклида для задачи
разделения секрета // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 3. — С. 58–65.
5. Виноградов И.М. Основы теории чисел. — М: Наука, 1972. — 168 с.
Поступила в редакцию 08.12.2004
|
| id | nasplib_isofts_kiev_ua-123456789-50709 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Russian |
| last_indexed | 2025-12-07T18:01:03Z |
| publishDate | 2004 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Бояринова, Ю.Е. Одарич, Я.В. Трубников, П.В. 2013-10-28T19:44:55Z 2013-10-28T19:44:55Z 2004 Разработка алгоритмов восстановления информации в задаче разделения секрета / Ю.Е. Бояринова, Я.В. Одарич, П.В. Трубников // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 107-112. — Бібліогр.: 5 назв. — pос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50709 515.171;681.3 Рассмотрены примеры восстановления секрета, используя изоморфный переход к системе действительных чисел, что исключает необходимость вычисления функции Эйлера в гиперкомплексных числовых системах второго порядка. Розглянуто приклади відновлення секрету, використовуючи ізоморфний перехід до системи дійсних чисел, що виключає необхідність обчислення функції Ейлера в гіперкомплексних числових системах другого порядку. Examples of restoring a secret using isomorphic transition to the real numbers system what eliminates necessity of Euler function evaluation in the second-order hypercomplex numerical systems are considered. Материалы данной статьи подготовлены и написаны при участии научного руководителя докт. техн. наук, профессора М.В. Синькова. ru Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Разработка алгоритмов восстановления информации в задаче разделения секрета Розробка алгоритмів відновлення інформації у задачі розділення секрету Development of Algorithms of Information Restoring in the Secret Sharing Task Article published earlier |
| spellingShingle | Разработка алгоритмов восстановления информации в задаче разделения секрета Бояринова, Ю.Е. Одарич, Я.В. Трубников, П.В. Методи захисту інформації в комп’ютерних системах і мережах |
| title | Разработка алгоритмов восстановления информации в задаче разделения секрета |
| title_alt | Розробка алгоритмів відновлення інформації у задачі розділення секрету Development of Algorithms of Information Restoring in the Secret Sharing Task |
| title_full | Разработка алгоритмов восстановления информации в задаче разделения секрета |
| title_fullStr | Разработка алгоритмов восстановления информации в задаче разделения секрета |
| title_full_unstemmed | Разработка алгоритмов восстановления информации в задаче разделения секрета |
| title_short | Разработка алгоритмов восстановления информации в задаче разделения секрета |
| title_sort | разработка алгоритмов восстановления информации в задаче разделения секрета |
| topic | Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet | Методи захисту інформації в комп’ютерних системах і мережах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50709 |
| work_keys_str_mv | AT boârinovaûe razrabotkaalgoritmovvosstanovleniâinformaciivzadačerazdeleniâsekreta AT odaričâv razrabotkaalgoritmovvosstanovleniâinformaciivzadačerazdeleniâsekreta AT trubnikovpv razrabotkaalgoritmovvosstanovleniâinformaciivzadačerazdeleniâsekreta AT boârinovaûe rozrobkaalgoritmívvídnovlennâínformacííuzadačírozdílennâsekretu AT odaričâv rozrobkaalgoritmívvídnovlennâínformacííuzadačírozdílennâsekretu AT trubnikovpv rozrobkaalgoritmívvídnovlennâínformacííuzadačírozdílennâsekretu AT boârinovaûe developmentofalgorithmsofinformationrestoringinthesecretsharingtask AT odaričâv developmentofalgorithmsofinformationrestoringinthesecretsharingtask AT trubnikovpv developmentofalgorithmsofinformationrestoringinthesecretsharingtask |