Encryption system based on abelian groups and rings
A simple encryption system is based on properties of abelian group an associative and commutative rings with unit is proposed. The algorithms with quadratic time complexity and memory complexity are proposed. The examples of using such system and the generalization of this system for using of gomof...
Saved in:
| Date: | 2020 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
PROBLEMS IN PROGRAMMING
2020
|
| Subjects: | |
| Online Access: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/418 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems in programming |
| Download file: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-418 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/de/6176eabdfd92100d7b0c532ab4fcc5de.pdf |
| spelling |
pp_isofts_kiev_ua-article-4182020-12-02T15:15:48Z Encryption system based on abelian groups and rings Криптосистема на основе абелевых групп и колец Криптосистема на основі абелевих груп і кілець Kryvyi, S.L. abelian group; ring; encryption system; gomofon; algorithm UDC 51.681.3 абелева группа; кольцо; криптосистема; гомофон; алгоритм UDC 51.681.3 абелева група; кільце; криптосистема; гомофон; алгоритм УДК: 51.681.3 A simple encryption system is based on properties of abelian group an associative and commutative rings with unit is proposed. The algorithms with quadratic time complexity and memory complexity are proposed. The examples of using such system and the generalization of this system for using of gomofons are considered. To show how to appear the set of gomofons by natural way is used a simple example of massage. Tab. 5. Ref. 3 titles.Problems in programming 2020; 2-3: 270-277 В работе предлагается простая криптосистема на основе свойств абелевых групп и ассоциативно-коммутативных колец с единицей. Приведены алгоритмы с квадратичной временной и квадратичной сложностью по памяти для построения таблиц сложения и умножения для этих алгебр. Рассмотрены примеры использования этой системы, а также ее расширение на случай работы с гомофонами. Показано каким образом естественным путем находятся гомофоны с иллюстрацией их использования на простом примере сообщения. Табл. 5. Библиогр.: 3 назв.Problems in programming 2020; 2-3: 270-277 В роботі пропонується проста криптосистема на основі властивостей абелевих груп та асоціативно-комутативних кілець з одиницею. Приводяться алгоритми побудови таблиць додавання та множення для цих алгебр. Розглянуті приклади використання цієї системи, а також її розширення на випадок роботи з гомофонами. Показано яким чином природним способом знаходяться гомофони з ілюстрацією їх використання на простому прикладі повіломлення. Табл. 5. Бібліогр.: 3 назв.Problems in programming 2020; 2-3: 270-277 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2020-09-16 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/418 10.15407/pp2020.02-03.270 PROBLEMS IN PROGRAMMING; No 2-3 (2020); 270-277 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2020); 270-277 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2020); 270-277 1727-4907 10.15407/pp2020.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/418/421 Copyright (c) 2020 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2020-12-02T15:15:48Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
abelian group ring encryption system gomofon algorithm UDC 51.681.3 |
| spellingShingle |
abelian group ring encryption system gomofon algorithm UDC 51.681.3 Kryvyi, S.L. Encryption system based on abelian groups and rings |
| topic_facet |
abelian group ring encryption system gomofon algorithm UDC 51.681.3 абелева группа кольцо криптосистема гомофон алгоритм UDC 51.681.3 абелева група кільце криптосистема гомофон алгоритм УДК: 51.681.3 |
| format |
Article |
| author |
Kryvyi, S.L. |
| author_facet |
Kryvyi, S.L. |
| author_sort |
Kryvyi, S.L. |
| title |
Encryption system based on abelian groups and rings |
| title_short |
Encryption system based on abelian groups and rings |
| title_full |
Encryption system based on abelian groups and rings |
| title_fullStr |
Encryption system based on abelian groups and rings |
| title_full_unstemmed |
Encryption system based on abelian groups and rings |
| title_sort |
encryption system based on abelian groups and rings |
| title_alt |
Криптосистема на основе абелевых групп и колец Криптосистема на основі абелевих груп і кілець |
| description |
A simple encryption system is based on properties of abelian group an associative and commutative rings with unit is proposed. The algorithms with quadratic time complexity and memory complexity are proposed. The examples of using such system and the generalization of this system for using of gomofons are considered. To show how to appear the set of gomofons by natural way is used a simple example of massage. Tab. 5. Ref. 3 titles.Problems in programming 2020; 2-3: 270-277 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2020 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/418 |
| work_keys_str_mv |
AT kryvyisl encryptionsystembasedonabeliangroupsandrings AT kryvyisl kriptosistemanaosnoveabelevyhgruppikolec AT kryvyisl kriptosistemanaosnovíabelevihgrupíkílecʹ |
| first_indexed |
2025-07-17T10:00:59Z |
| last_indexed |
2025-07-17T10:00:59Z |
| _version_ |
1850411138873819136 |
| fulltext |
Захист інформації
© С.Л. Кривий, 2020
270 ISSN 1727-4907. Проблеми програмування. 2020. № 2–3. Спеціальний випуск
УДК: 51.681.3 https://doi.org/10.15407/pp2020.02-03.270
КРИПТОСИСТЕМА НА ОСНОВІ АБЕЛЕВИХ ГРУП І КІЛЕЦЬ
С.Л. Кривий
В роботі пропонується проста криптосистема на основі властивостей абелевих груп та асоціативно-комутативних кілець з
одиницею. Приводяться алгоритми побудови таблиць додавання та множення для цих алгебр. Розглянуті приклади використання
цієї системи, а також її розширення на випадок роботи з гомофонами. Показано яким чином природним способом знаходяться
гомофони з ілюстрацією їх використання на простому прикладі повіломлення. Табл. 5. Бібліогр.: 3 назв.
Ключові слова: : абелева група, кільце, криптосистема, гомофон, алгоритм.
В работе предлагается простая криптосистема на основе свойств абелевых групп и ассоциативно-коммутативных колец с единицей.
Приведены алгоритмы с квадратичной временной и квадратичной сложностью по памяти для построения таблиц сложения и
умножения для этих алгебр. Рассмотрены примеры использования этой системы, а также ее расширение на случай работы с
гомофонами. Показано каким образом естественным путем находятся гомофоны с иллюстрацией их использования на простом
примере сообщения. Табл. 5. Библиогр.: 3 назв.
Ключевые слова: абелева группа, кольцо, криптосистема, гомофон, алгоритм.
A simple encryption system is based on properties of abelian group an associative and commutative rings with unit is proposed. The algorithms
with quadratic time complexity and memory complexity are proposed. The examples of using such system and the generalization of this
system for using of gomofons are considered. To show how to appear the set of gomofons by natural way is used a simple example of massage.
Tab. 5. Ref. 3 titles.
Key words: abelian group, ring, encryption system, gomofon, algorithm.
1. Необхідні означення та поняття
В роботі пропонується проста криптосистема, яка побудована на властивостях скінченних абелевих груп
та асоціативно-комутативних кілець з одиницею [1, 2].
Нехай задана деяка скінченна множина цілих чисел, наприклад, 5N = {0,1,2,3,4}. Оскільки потрібно
побудувати адитивну абелеву групу, то ця група обов'язково повинна включати 0. Для того, щоб 5N
перетворити в групу 5GN , необхідно коректно задати значення для операції додавання з одним із елементів
групи, скажімо з 1 [3]. Дійсно, оскільки 0a a для довільного a ∈ 5GN , то перший рядок таблиці додавання
елементів групи визначений (табл. 1), а на підставі комутативності (оскільки група абелева) і перший стовпчик
цієї таблиці. Нехай, наприклад, задано 0 1 1 , 1 1 4 , 1+4=2, 1+2=3, 1+3 = 0. Таке означення коректне,
оскільки має місце однозначність результату (але однозначність результату не достатня умова гарантії
коректності). Тепер послідовно знаходимо результати додавання з елементом 1+1=4, що дає змогу знайти
результати додавання елементів групи з елементом 4:
4+2=(1+1)+2=1+(1+2)=1+3=0, 4+3=(1+1)+3=1+(1+3)=1, 4+4=(1+1)+4=1+(1+4)=1+2=3.
Далі знаходимо значення 4+1=2 і обчислюємо операцію додавання з елементом 2:
2+2=(1+4)+2=1+(4+2)=1+0=1, 2+3=(1+4)+3=1+(4+3)=1+1=4, 2+4=(1+4)+4=1+(4+4)=1+3=0.
Далі знаходимо значення 2+1=3 і обчислюємо операцію додавання з елементом 3:
3+2=(1+2)+2=1+(2+2)=1+1=4, 3+3=(1+2)+3=1+(2+3)=1+4=2, 3+4=(1+2)+4=1+(2+4)=1+0=1.
Заносимо ці значення в таблицю 2 і на цьому закінчуємо побудову групи 5GN .
Варто зауважити, що для визначення групи можна взяти довільний її елемент, а не обов’язково
одиницю. Наприклад, якщо задано такий рядок додавання з елементом 3: 3 0 3 , 3 1 4 , 3 2 1 ,
3 3 2 , 3 4 0 , то за цим рядком дістаємо таблицю 3.
Для побудови абелевої групи kGN , мало вимагати тільки однозначності операції додавання. Якщо
визначити додавання в групі так 0 1 1 , 1+1=0, 1+2=3, 1+3=4, 1+4=2, то, обчислюючи 1+3, отримаємо
1+3 =1+(1+2)=(1+1)+2=0 + 2 = 2, що не збігається з визначеним вище. Справа в тім, що так визначена операція
додавання не охоплює весь цикл елементів групи, тому що має елемент скінченного порядку 2 5 (1+1=0).
Обидві групи, побудовані вище, циклічні на підставі теореми Лагранжа (вони мають простий порядок 5).
Захист інформації
271
Неважко переконатися, що ці групи ізоморфні. Дійсно, бієктивне відображення для перших двох груп має
вигляд: (0) 0f , (1) 1f , (4) 3f , (2) 4f , (3) 2f .
Таблиця 1 Таблиця 2 Таблиця 3
+ 0 1 2 3 4 + 0 1 2 3 4 + 0 1 2 3 4
0 0 1 2 3 4 0 0 1 2 3 4 0 0 1 2 3 4
1 1 4 3 0 2 1 1 4 3 0 2 1 1 3 0 4 2
2 2 3 2 2 3 1 4 0 2 2 0 4 1 3
3 3 0 3 3 0 4 2 1 3 3 4 1 2 0
4 4 2 4 4 2 0 1 3 4 4 2 3 0 1
Поставимо у відповідність операції додавання з елементом групи 1a , за допомогою якого визначається
група, підстановку
1
1 2 1
1 1 2
0 . . .
. . .
k
a
i i ik
a a a
f
a a a a
.
Ця підстановка означає, що
1af (0)=0+ 1a = 1a ,
1 1af a = 1a + 1a = 1ia , 1 1 1 1 2( )a i i if a a a a ,…,
1 1 1 1a k ik ikf a a a a , 1( ) 0ik ikf a a a . Назвемо групу kGN повноциклічною, якщо підстановка 1af є
повним циклом довжини k . Наприклад, групи, представлені таблицями 2 і 3, повноциклічні. Справедлива
Теорема 1. Всі скінченні повноциклічні абелеві групи одного і того порядку ізоморфні між собою.
Доведення очевидним чином випливає з того, що коли дві підстановки 1af i 1bf двох
k-повноциклічних груп визначають ці групи, то ізоморфізмом буде відображення
0 0f , 1 1f a b , 1 111 ( ) ,i ibb ba bf
2 1 1 1 1 1 1 , ( )i i i ij ijf a f a a b b f a f a b , 1 1( )ij ijf a f a b ,
де 2, . . . ,j k .
Асоціативно-комутативні кільця з одиницею. Ця алгебра будується шляхом розширення сигнатури
операцій та множини тотожних співвідношень для цих операцій.
Універсальна алгебра G(A, ) називається асоціативно-комутативним кільцем з одиницею, якщо вона є
а) абелевою групою відносно додавання;
б) абелевою напівгрупою з одиницею відносно операції множення;
Операції додавання і множення задовольняють закон дистрибутивності, тобто для довільних елементів
, ', 'x x x справедлива тотожність x(x' + x'') = (xx') + (xx''). Це означає, що включає чотири операції: бінарні
операції додавання і множення, унарну операцію взяття оберненого відносно операції додавання і нульарну
операцію, яка фіксує нульовий елемент абелевої групи кільця. Цей нульовий елемент називається нулем
кільця.
2. Криптографічна система на основі груп і кілець
При побудові абелевої групи була знайдена таблиця Келі для операції додавання. Ця таблиця дозволяє
розширити таку побудову і на операцію множення.
Розглянемо як можна побудувати за групою 6GN , яка задана нижченаведеною табл. 4, асоціативно-
комутативне кільце з одиницею 6KGN . Роль одиниці буде відігравати 1. На підставі аксіом кільця з одиницею
дістаємо: для довільного елемента a із 5GN a ∙ 0 = 0∙ a = 0, a ∙1 = 1∙ a = a. Таким чином, два рядки і два
стовпчики таблиці множення визначені. Далі, за таблицею додавання і законом дистрибутивності знаходимо
таблицю для операції множення. Дійсно, оскільки 1+1=3, то
3∙2 = (1+1) ∙2 = 2 + 2 = 4; 3∙3 = (1+1) ∙3 = 3 + 3 = 4; 3∙4 = (1+1) ∙4 = 4 + 4 =3; 3∙5=(1+1) ∙5=5+5=0 .
Далі, оскільки 1+3=5, то дістаємо:
Захист інформації
272
5∙2=(1+3) ∙2=2+3∙2=2+4=5; 5∙3=(1+3) ∙3=3+3∙3=3+4=0; 5∙4 = (1+3) ∙4 = 4+3∙4=4+3 = 0; 5∙5=(1+3) ∙5=5+0=5.
За таблицею додавання 5+1 = 4 і це дає змогу знайти значення операції множення з елементом 4, з
елементом 2=1+4 решту елементів табл. 4. Оскільки 1+2=0, то це означає, що вся таблиця множення
побудована. Із симетричності таблиці випливає, що операція множення елементів 6KGN задовольняє закон
комутативності. Легко перевірити, що ця операція задовольняє також закон асоціативності, тобто 6KGN –
асоціативно-комутативне кільце з одиницею (табл. 5).
Таблиця 4 Таблиця 5
+ 0 1 2 3 4 5 * 0 1 2 3 4 5
0 0 1 2 3 4 5 0 0 0 0 0 0 0
1 1 3 0 5 2 4 1 0 1 2 3 4 5
2 2 0 4 1 5 3 2 0 2 1 4 3 5
3 3 5 1 4 0 2 3 0 3 4 4 3 0
4 4 2 5 0 3 1 4 0 4 3 3 4 0
5 5 4 3 2 1 0 5 0 5 5 0 0 5
Нехай операція додавання визначена для елемента групи a . Тоді в загальному випадку для побудови
комутативного кільця kKGN з одиницею, порядок якого k, необхідно задекларувати два двомірні масиви T і
T∙ розмірності k k і виконати такі алгоритми:
ADD-TAB-KG ,a k
0) Занести в T перший рядок і стовпчик результати додавання з нулем кільця;
1) Занести в T рядок, де визначаються результати додавання з елементом a (задати ключ);
2) Покласти c a ;
3) Взяти в T елемент 'c c a ;
4) Для всіх x занести в T суми 'c x c a x c a x ;
5) Покласти 'c c , 'c c a ; Якщо ' 0c , то СТОП, інакше на крок 4).
МUL-TAB-KG ,l k
0) Занести в T∙ рядки і стовпчики з результатами множення на 0 і на 1 ;
1) Покласти 1c ;
2) Взяти в T елемент ' 1c c ;
3) Для всіх x занести в T∙ добутки ' 1 c x c x c x x ;
4) Покласти 'c c ; ' 1c c ; Якщо ' 0с , то СТОП, інакше на крок 3).
Складність першого алгоритму 2( )О k , а другого 3( )O k , де k – порядок кільця (групи).
Правильність цього алгоритму випливає з того, що всі елементи 1 2 1 , ,c a a c c a …,
1 k kc c a пробігають всі елементи абелевої групи на підставі того, що рівняння a x b в групі має
єдиний розв'язок. З цих побудов випливає такий спосіб шифрування з використанням властивостей кільця:
RG-EN(k)
1) Будуємо кільце (або тільки групу) порядку 26k ;
2) Задаючи бієкцію f між елементами кільця (або групи) і символами алфавіту, виконуємо
шифрування тексту T . Шифрування можна виконувати з використанням однієї з таблиць,
або з використанням обох таблиць.
RG-DE(T)
1) Розшифрування виконується в зворотному порядку: знаходимо значення
1f на символах
шифрограми; потім на основі таблиць кільця повністю дешифруємо отриманий текст (див.
нижченаведений приклад).
Захист інформації
273
Розглянемо питання стійкості даного алгоритму та надійності. Оскільки при визначенні групи kGN
повинні породжуватися всі елементи, то простір ключів, як випливає з теореми 1, складатиме ( )2 !k варіантів.
Дійсно, кількість способів, якими можна задати ключ, дорівнює кількості ізоморфізмі групи k -го порядку а це
кількість способів упорядкування ( 2)k -елементної множини (два елементи 0 і 1 мають фіксовані позиції).
Далі, приписування номерів символам алфавіту може виконуватися !n способами , де n – кількість символів
алфавіту. Отже, простір ключів має розмір ( 2 ! !)k n .
Наприклад, якщо розглядається група з 25 елементів, то такого простору )23!( 25! вибору ключів
достатньо для забезпечення хорошої стійкості шифру.
Побудову групи або кільця, наприклад, 25KGN , маючи в розпорядженні групу порядку 5GN , можна
виконати шляхом застосування операції прямого добутку кілець або прямої суми груп 25GN = 5GN 5GN ,
операції додавання і множення в яких виконуються покомпонентно, тобто
, , , a b c d a c b d , , , , ( )a b c d a c b d .
Приклад 1. Розглянемо на прикладі групи (яка є прямою сумою абелевих груп 25GN = 5GN 5GN )
кільця 25KGN застосування алгоритму шифрування і дешифрування.
Нехай літери алфавіту англійської мови перенумеровані таким чином:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
c b a f e d i/j h g m l k p O n s r q v u t y x w z
Група 25AGN має вигляд:
+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 6 4 5 3 7 8 9 10 11 2 13 14 15 16 17 18 19 20 21 24 12 23 0 22
2 2 4 9 13 11 15 3 17 5 19 7 21 24 12 22 14 23 16 0 18 1 20 8 10 6
3 3 5 13 17 15 19 7 21 9 12 11 14 23 16 0 18 1 20 6 24 8 22 2 4 10
4 4 3 11 15 13 17 5 19 7 21 9 12 22 14 23 16 0 18 1 20 6 24 10 2 8
5 5 7 15 19 17 21 9 12 11 14 13 16 0 18 1 20 6 24 8 22 10 23 4 3 2
6 6 8 3 7 5 9 10 11 2 13 4 15 16 17 18 19 20 21 24 12 22 14 0 1 23
7 7 9 17 21 19 12 11 14 13 16 15 18 1 20 6 24 8 22 10 23 2 0 3 5 4
8 8 10 5 9 7 11 2 13 4 15 3 17 18 19 20 21 24 12 22 14 23 16 1 6 0
9 9 11 19 12 21 14 13 16 15 18 17 20 6 24 8 22 10 23 2 0 4 1 5 7 3
10 10 2 7 11 9 13 4 15 3 17 5 19 20 21 24 12 22 14 23 16 0 18 6 8 1
11 11 13 21 14 12 16 15 18 17 20 19 24 8 22 10 23 2 0 4 1 3 6 7 9 5
12 12 14 24 23 22 0 16 1 18 6 20 8 7 10 9 2 11 4 13 3 15 5 19 21 17
13 13 15 12 16 14 18 17 20 19 24 21 22 10 23 2 0 4 1 3 6 5 8 9 11 7
14 14 16 22 0 23 1 18 6 20 8 24 10 9 2 11 4 13 3 15 5 17 7 21 12 19
15 15 17 14 18 16 20 19 24 21 22 12 23 2 0 4 1 3 6 5 8 7 10 11 13 9
16 16 18 23 1 0 6 20 8 24 10 22 2 11 4 13 3 15 5 17 7 19 9 12 14 21
17 17 19 16 20 18 24 21 22 12 23 14 0 4 1 3 6 5 8 7 10 9 2 13 16 11
18 18 20 0 6 1 8 24 10 22 2 13 4 1 3 15 5 17 7 19 9 21 1 3 15 12
19 19 21 18 24 20 22 12 23 14 0 16 1 3 6 5 8 7 10 9 2 11 4 15 17 13
20 20 24 1 8 6 10 22 2 23 4 0 3 15 5 17 7 19 9 21 11 12 13 5 18 14
21 21 12 20 22 24 23 14 0 16 1 18 6 5 8 7 10 9 2 1 4 13 3 17 19 15
22 22 23 8 2 10 4 0 3 1 5 6 7 19 9 21 11 12 13 3 15 5 17 20 24 18
23 23 0 10 4 2 3 1 5 6 7 8 9 21 11 12 13 14 16 15 17 18 19 24 22 20
24 24 22 6 10 8 2 23 4 0 3 1 5 17 7 19 9 21 11 12 13 14 15 18 20 16
Захист інформації
274
Мультиплікативна група 25MGN кільця 25KGN :
Нeобхідно зашифрувати в цій групі текст «UKRPROGtwenty». Для цього вибираємо ключове слово
«IPRSР» і знаходимо пари літер та їх числові відповідники в таблиці додавання, які знаходяться на перетині
відповідного рядка і стовпчика. Дістаємо шифрограму:
І P R S Р U К R Р R O G t
U К R Р R О G t w e n t y
6 12 16 15 12 19 11 16 12 12 13 8 20 – цифровий відповідник ключового слова і тексту;
+ + + + + + + + + + + + +
19 11 16 12 16 13 8 20 23 4 14 20 21 – цифровий відповідник тексту;
= = = = = = = = = = = = =
12 8 15 2 11 6 17 19 21 22 2 23 13 – T (шифрограма цифрова) (сума відповідників);
p g s a e i q u y x b w o – T (шифрограма літерова).
Розшифрування відбувається в зворотному напрямку. Абоненту, якому адресована ця шифрограма,
відомий ключ таблиці додавання і ключове слово «IPRSР». Виписуємо цифрову шифрограму і цифрові
значення ключового слова; за першим символом a ключового слова знаходимо символ, який є першим
символом шифрограми в таблиці додавання групи (в прикладі за символом 6a знаходимо значення 12b ,
тобто розв’язуємо рівняння a x b ); за знайденим значенням в стовпчику, що відповідає цьому значенню b,
знаходимо відповідник (у прикладі це число 19x , якому відповідає символ u); цей цикл повторюється доти,
доки не буде знайдено весь текст повідомлення.
12 8 15 2 11 6 17 19 21 22 2 23 13
6 12 16 15 12 19 11 16 12 12 13 8 20
U К R Р R О G t w e n t y
Наведений в прикладі текст можна зашифрувати, використовуючи таблицю множення. Ця обставина
дозволяє використовувати одночасно дві таблиці для шифрування, тобто одній парі літер ставимо у
відповідність елемент таблиці додавання, а наступній парі літер, яка повторюється, – відповідник з таблиці
множення (тобто відповідником буде елемент m i j ). Але це можливо лише у випадку, коли один з
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
2 0 2 0 9 2 19 9 18 19 0 18 2 9 9 19 19 18 18 0 0 2 2 19 18 9
3 0 3 9 23 12 4 17 15 20 18 8 6 16 7 1 21 5 22 19 2 24 13 11 14 10
4 0 4 2 12 11 22 13 10 14 9 23 21 6 24 5 8 17 7 18 19 1 20 15 16 3
5 0 5 19 4 22 17 21 24 23 2 3 15 11 20 16 10 6 13 9 18 14 8 7 12 1
6 0 6 9 17 13 21 10 14 4 18 5 24 7 23 11 1 15 8 19 2 12 3 20 22 16
7 0 7 18 15 10 24 14 4 6 19 11 23 8 5 13 12 20 1 2 9 17 16 3 21 22
8 0 8 19 20 14 23 4 6 7 2 13 5 1 11 10 17 3 12 9 18 15 22 16 24 21
9 0 9 0 18 9 2 18 19 2 0 19 9 18 18 2 2 19 19 0 0 9 9 2 19 18
10 0 10 18 8 23 3 5 11 13 19 21 16 14 22 24 6 1 4 2 9 7 17 12 20 15
11 0 11 2 6 21 15 24 23 5 9 16 20 13 3 22 14 7 10 18 19 4 1 8 17 12
12 0 12 9 16 6 11 7 8 1 18 14 13 17 10 4 20 22 15 19 2 3 24 21 5 23
13 0 13 9 7 24 20 23 5 11 18 22 3 10 16 21 4 8 14 19 2 6 12 1 15 17
14 0 14 19 1 5 16 11 13 10 2 24 22 4 21 23 7 12 6 9 18 8 15 17 3 20
15 0 15 19 21 8 10 1 12 17 2 6 14 20 4 7 16 24 3 9 18 22 5 23 13 11
16 0 16 18 5 17 6 15 20 3 19 1 7 22 8 12 24 11 21 2 9 23 10 13 4 14
17 0 17 18 22 7 13 8 1 12 19 4 10 15 14 6 3 21 20 2 9 16 23 24 11 5
18 0 18 0 19 18 9 19 2 9 0 2 18 19 19 9 9 2 2 0 0 18 18 9 2 19
19 0 19 0 2 19 18 2 9 18 0 9 19 2 2 18 18 9 9 0 0 19 19 18 9 2
20 0 20 2 24 1 14 12 17 15 9 7 4 3 6 8 22 23 16 18 19 21 11 5 10 13
21 0 21 2 13 20 8 3 16 22 9 17 1 24 12 15 5 10 23 18 19 11 4 14 7 6
22 0 22 19 11 15 7 20 3 16 2 12 8 21 1 17 23 13 24 9 18 5 14 10 6 4
23 0 23 18 14 16 12 22 21 24 19 20 17 5 15 3 13 4 11 2 9 10 7 6 1 8
24 0 24 9 10 3 1 16 22 21 18 15 12 23 17 20 11 14 5 19 2 13 6 4 8 7
Захист інформації
275
елементів добутку є дільником одиниці в кільці kKGN . Відомо, що множина дільників одиниці є абелевою
групою в такому кільці [1]. У випадку скінченного асоціативно-комутативного кільця з одиницею, адитивна
група якого є повноциклічною, легко знайти дільники нуля і їх кількість. Це випливає з такої теореми.
Теорема 2. Скінченне асоціативно-комутативне кільце з одиницею k-го порядку, адитивна група якого
повноциклічна, має ( )k дільників одиниці, де – функція Ойлера.
Доведення. Розглянемо kZ – кільце лишків за модулем k. Неважко переконатися в тому, що адитивна
група цього кільця є повноциклічною групою. Дільниками одиниці в цьому кільці будуть елементи, які
взаємно прості з модулем кільця k , а кількість таких елементів, як відомо, дорівнює значенню функції
Ойлера ( )k . На підставі теореми 1 існує ізоморфізм між кільцем лишків kZ і кільцем kKGN , який є
продовженням ізоморфізму між адитивними групами цих кілець. Звідси випливає справедливість твердження
теореми.
Ілюстрацією теореми 2 є кільце 6KGN , задане вищенаведеними табл. 4 і 5. Оскільки кільце лишків за
модулем 6 має єдиний елемент 5, який взаємно простий з модулем 6, а цьому елементу при ізоморфізмі
відповідає елемент 2, то з таблиці 5 легко побачити, що 2 – дільник одиниці. На підставі теореми 1 побудову
таблиці множення можна не приводити, а використати ізоморфізм f: 25Z → 25KGN . Дійсно, таблиця
відповідностей має вигляд:
0 0f , 25f , 10 9f , 115 9f , 20 18f ,
1 1f , 46f , 11 11f , 216 1f , 21 20f ,
62f , 37f , 112 3f , 117 2f , 222 4f ,
83f , 58f , 113 5f , 118 4f , 223 2f ,
14 0f , 79f , 114 7f g , 119 6f , 224 3f .
Дільниками нуля в цьому кільці лишків є елементи 5,10,15, 20. Цим елементам в кільці 25KGN
відповідають елементи 2,9,18,19. Решта елементів цього кільця – дільники одиниці, які утворюють абелеву
мультиплікативну групу цього кільця. Отже, для знаходження добутку, наприклад, елементів 6 і 7, знаходимо
добуток їх відповідників 2 і 9 в кільці лишків 18 = 18 (mod 25). Тоді в кільці 25KGN відповідником є елемент
118 4f . Отже, 6∙7=14 в кільці 25KGN .
Неважко переконатися, що породжуючими елементами цієї мультиплікативної групи є елементи 5 , 6,
8,12,13,15, 22, 24. Це випливає з такої теореми.
Теорема 3. Якщо мультиплікативна група дільників одиниці асоціативно-комутативного кільця з
одиницею має твірний елемент g , то твірними елементами цієї групи будуть елементи jg такі, що
НСД , ( ) [ ]( ) 1 5j k .
Дійсно, в нашому прикладі мультиплікативної групи кільця 25KGN маємо:
61=6, 62=10, 63=5, 64=21, 65=3, 66=17, 67=8, 68=4, 69=13, 610=23,
611=22, 612=20, 613=12, 614=7, 615=14, 616=11, 617=24, 618=16, 619=15, 620=1,
а також
51=63, 52 = 17, 53=13, 54=20, 55=14, 56=16, 57=6, 58=21, 59=8, 510=23,
511=12, 512=11, 513=15, 514=10, 615=3, 516=4, 517=22, 518=7, 519=24, 520=1.
Отже, в цій групі можна застосувати функцію дискретного логарифму для шифрування повідомлень та
передачі ключів. Наприклад, порівняння 6 20 mod 25x має розв’язок 12x , а 5 24 mod 25x має
розв'язок 19x .
Основною перешкодою використання дискретного логарифму в кільцях є те, що не завжди його
мультиплікативна група буде циклічною. Наприклад, в кільці лишків за модулем k=16, маємо ( ) 8k і
дільниками одиниці будуть елементи 1,3,5,7,9,11,13,15. Ці елементи мають порядок 2 або 4 і тому група
дільників одиниці не буде циклічною. Це одна з причин того, що в криптографії застосовуються скінченні поля
а не кільця, оскільки в скінченному полі його мультиплікативна група завжди циклічна. Ця обставина дозволяє
використовувати в скінченних полях функцію дискретного логарифму.
Виходячи з того, що порядок мультиплікативної групи кільця дорівнює ( )k , то звідси випливає, що
найкращий порядок кільця k буде тоді, коли ( )k просте число. В цьому випадку мультиплікативна група
Захист інформації
276
дільників кільця проста і тому на підставі теореми Лагранжа буде циклічною, тобто породжуватиметься
довільним своїм елементом. Але автору невідомо існування такого числа !k .
Якщо такого числа не існує, то потрібно вибрати число k таким, щоб у розкладі числа ( )k на прості
множники був великий простий дільник. Така ситуація буде мати місце тоді, коли ( ) 2k r , де r – просте
число. Наприклад, якщо 9k , то (9) 6 3 2 і тоді мультиплікативна група цього кільця матиме циклічну
підгрупу 3-го порядку. Зрештою при шифруванні в разі потреби можна використовувати довільну циклічну
підгрупу мультиплікативної групи дільників кільця kKGN .
Можливість використання обох таблиць операцій кільця дозволяє краще «розчинити» частоту появи
двознаків у шифрограмі.
Шифри гомофонічні. Відомо, що моноалфавітні шифри ламаються методом частотного аналізу, тоді
запобігти такому криптоаналізу можна відображенням однієї літери в декілька її образів, які називаються
гомофонами [4]. Кількість гомофонів для кожної літери повинна бути пропорціональна частоті появи цієї
літери в явному тексті. Якщо гомофони використати ротаційно, то можна сподіватися, що частота появи
літер не буде ідентична і це призведе до неможливості використання частотного криптоаналізу. Ідею
застосування гомофонів приписують Карлу Гаусу (гомофонічний шифр ілюструє приклад 2). В гомофонічних
шифрах частотний аналіз стає неможливим, але частота появи комбінацій сусідніх літер дає можливість
застосувати цей тип аналізу. Сусідня пара літер називається двознаком. В англійській мові маємо 676 різних
двознаків, з них 18 становить більше 25 % тексту. Таким чином, гомофони теж проявляють частоту появи літер
і атака методом частотного аналізу стає можливою, але використання гомофонів значно ускладнює роботу
криптоаналітика.
Приклад 2. Застосуємо гомофонічний шифр до шифрування тексту «kukuriku» з ключовим словом
«kuku». Шифрування відбувається на основі таблиці гомофонів, взятих з таблиці додавання вищенаведеної
групи :
Символ Гомофони адитивні Гомофони мультиплікативні
K – 0402, 0310, 1216, 1522, 2417; 1101, 1205, 2415, 1723;
U – 0209, 0117, 0902, 1224; 0802, 0709, 0502, 0207;
R – 1511, 0709, 1206; 0312, 0423, 1921, 2418;
I – 0318, 0420, 1121, 1317. 0311, 0807, 0514, 2322.
Ключове слово: K U K U K U K U
0402 0209 1216 0117 0310 1424 1522 1424
Текст відкритий: K U K U R I K U
1522 1424 0310 0209 1206 0209 0310 0117
Шифрограма: 1608 2203 2322 0423 2304 2203 1806 1611
Гарантією однозначного розшифрування є добра відома властивість: відображення множини А на
множину В визначає на множині А відношення еквівалентності. Елементами класів розбиття за цим
відношенням еквівалентності є гомофони літер алфавіту.
Відповідниками можуть бути різні гомофони і їх можна далі застосовувати ротаційно випадковим
чином. В загальному випадку гомофонами символу алфавіту, якому відповідає елемент таблиці m,
будуть такі пари ,i j елементів таблиці додавання (множення), які задовольняють умову ( ) i j m i j m .
При цьому, якщо пара ,i j вже вибрана гомофоном, то пару ,j i не варто брати гомофоном (симетрія
входження цифр – підказка криптоаналітику). Всіх гомофонів в таблиці додавання буде k, а в таблиці
множення ( )k .
Висновки
Запропонована проста криптосистема на основі властивостей абелевих груп і асоціативно-комутативних
кілець з одиницею. Зауважимо, що при традиційно прийнятому порядку літер англійського алфавіту таблиця
додавання кільця лишків Z25 буде відповідає таблиці шифру Віженера. Пропонована система має широкий
простір ключів, що є достатнім для стійкості системи. Для побудови такої системи потрібно побудувати таблиці
додавання і множення групи і кільця. З цією метою пропонуються алгоритми побудови цих таблиць з
квадратичною оцінкою складності. Шифрування і розшифрування теж виконуються в квадратичному часі.
Захист інформації
277
Література
1. Калужнин Л.А. Введение в общую алгебру. М.: Наука. 1973. 447 с.
2. Сергієнко І.В., Кривий С.Л., Провотар О.І. Алгебраїчні аспекти інформаційних технологій. К.: Інтерсервіс. 2018. 411 с.
3. Кук Д., Бейз Г. Компьютерная математика. М.: Наука. 1990. 384 с.
4. Menezes A., van Oorschot P., Vanstons S. Handbook of Applied Cryptography. CRC Press. 1996. 661 p.
5. Коблиц Н. Курс теории чисел и криптографии. М.: Изд-во ТВП. 2001. 260 с.
References
1. Kaluznin L.A. Introduction to general algebra. М.: Nauka. 1973. 447 p.
2. Sergienko I.V., Kryvyi S.L., Provotar O.I. Algebraic aspects of informational technologies. K.:Interservice. 2018. 411 p.
3. Cooke D.J., Bez H.E. Computer mathematics. Cambridge University Press. Cambridge. 1984. 384 p.
4. Menezes A., van Oorschot P., Vanstons S. Handbook of Applied Cryptography. CRC Press. 1996. 661 p.
5. Coblitz N. A course of number theory and cryptography. М.: ТВП. 2001. 260 p.
Одержано 17.02.2020
Про автора:
Кривий Сергій Лук’янович,
доктор фізико-математичних наук, професор,
професор Київського національного університету імені Т.Г. Шевченка.
Кількість наукових публікацій в українських виданнях – 201.
Кількість наукових публікацій в зарубіжних виданнях – 52.
h-index: Google Scholar – 14;
Scopus – 7.
http://orcid.org/0000-0065-0736-4579.
Місце роботи автора:
Київський національний університет імені Т.Г. Шевченка
м. Київ, просп. Глушкова, 4Д.
Телефон службовий: (044) 259-05-11.
E-mail: sl.krivoi@gmail.com.
|