УДК: 51.681.3 Київський національний університет імені Т.Г. Шевченка м. Київ, просп. Глушкова, 4Д. В роботі пропонується проста криптосистема на основі властивостей абелевих груп та асоціативно-комутативних кілець з одиницею. Приводяться алгоритми побудови таблиць додавання та множення для цих алгебр. Розглянуті приклади використання цієї системи, а також її розширення на випадок роботи з гомофонами. Показано яким чином природним способом знаходяться гомофони з ілюстрацією їх використання на простому прикладі повіломлення. Табл. 5. Бібліогр.: 3 назв. Ключові слова: :абелева група, кільце, криптосистема, гомофон, алгоритм. В работе предлагается простая криптосистема на основе свойств абелевых групп и ассоциативно-коммутативных колец с единицей. Приведены алгоритмы с квадратичной временной и квадратичной сложностью по памяти для построения таблиц сложения и умножения для этих алгебр. Рассмотрены примеры использования этой системы, а также ее расширение на случай работы с гомофонами. Показано каким образом естественным путем находятся гомофоны с иллюстрацией их использования на простом примере сообщения. Табл. 5. Библиогр.: 3 назв. Ключевые слова: абелева группа, кольцо, криптосистема, гомофон, алгоритм. In the paper simple symmetric encryption system is proposed. This system is build on properties of abelian groups an associativecommutative rings with unit. To work in system is necessary to declare key row corresponding to addition with one element of group. Using this row full table of addition of group and full table of multiplication of ring are build. To build groups and rings of larger orders are used operations of direct sum for abelian groups or direct multiply for rings. After definition a correspondence between elements of group or ring and symbols of alphabet. In the paper used a group with complete cycle. Group is called with complete cycle if the key row includeof their elements. All finite groups with complete cycle are isomorphic. The set of all groups of the same orders are equal (/k-2/)!.Having taken key word and using the correspondence between elements of ring and symbols of alphabet is build security message. If we used ring for encryption then we can used two tables of ring and do coding in interleaving manner (one code take from table of addition and next code from table of multiplication). Such approach makes practical impossible using of frequency method. Showed that In such systems space of keys is (/k-2/)!/k/!, where /k/ is power of alphabet (it is order of group or ring).The complexity of algorithms for building group and ring are O(/k^2 /) and the same complexity of encryption and decoding. The guarantee of unambiguous decoding is a well-known property: the mapping of the set A to the set B determines the equivalence relation on the set A. The elements of the partition classes according to this equivalence relation are the homophones of the letters of the alphabet.The work of algorithms isdemonstrated on example group's order25. The equivalents can be different homophones and can then be used in a rotational random manner. In the general case, the homophones of the alphabet symbol, which corresponds to the element of the table m, will be such pairs i, j of the elements of the table of addition (multiplication), which satisfy the condition i + j = m (i · j = m). In this case, if the pair i, j is already selected as a homophone, then the pair j, i should not be taken as a homophone (symmetry of the occurrence of numbers - a hint to the cryptanalyst). All homophones in the addition table will be k, and in the multiplication table (k), where φ is the Euler function. Another possibility to encryption is using the tables of ring for building of gomophones for symbols of alphabet.
GN5 , то перший рядок таблиці 2+4=(1+4)+4=1+(4+4)=1+3=0.
Далі знаходимо значення 2+1=3 і обчислюємо операцію додавання з елементом 3: 3+4=(1+2)+4=1+(2+4)=1+0=1.
Асоціативно-комутативні кільця з одиницею. Ця алгебра будується шляхом розширення сигнатури операцій та множини тотожних співвідношень для цих операцій.
Універсальна алгебра G(A, ) називається асоціативно-комутативним кільцем з одиницею, якщо вона є а) абелевою групою відносно додавання; б) абелевою напівгрупою з одиницею відносно операції множення; Операції додавання і множення задовольняють закон дистрибутивності, тобто для довільних елементів x, x ', x ' справедлива тотожність x(x' + x'') = (xx') + (xx''). Це означає, що включає чотири операції: бінарні 2. Криптографічна система на основі груп і кілець
При побудові абелевої групи була знайдена таблиця Келі для операції додавання. Ця таблиця дозволяє розширити таку побудову і на операцію множення.
Розглянемо як можна побудувати за групою GN6 , яка задана нижченаведеною табл. 4, асоціативнокомутативне кільце з одиницею KGN6 . Роль одиниці буде відігравати 1. На підставі аксіом кільця з одиницею дістаємо: для довільного елемента a із GN5 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, то дістаємо: 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, то це означає, що вся таблиця множення побудована. Із симетричності таблиці випливає, що операція множення елементів KGN6 задовольняє закон комутативності. Легко перевірити, що ця операція задовольняє також закон асоціативності, тобто KGN6 – асоціативно-комутативне кільце з одиницею (табл. 5).
Таблиця 4
Таблиця 5 + T· розмірності k k і виконати такі алгоритми:
ADD-TAB-KG a, k МUL-TAB-KG l, 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 ; Якщо c ' 0 , то СТОП, інакше на крок 4). 0) Занести в T· рядки і стовпчики з результатами множення на 0 і на 1 ; 1) Покласти c 1 ; 2) Взяти в T елемент c ' c 1 ; 3) Для всіх x занести в T· добутки c ' x c 1 x c x x ; 4) Покласти c c ' ; c ' c 1 ; Якщо с ' 0 , то СТОП, інакше на крок 3). Складність першого алгоритму О(k 2 ) , а другого O(k3 ) , де k – порядок кільця (групи).
Правильність цього алгоритму випливає з того, що всі елементи c1 a a, c2 c1 a, …, ck ck 1 a пробігають всі елементи абелевої групи на підставі того, що рівняння a x b в групі має єдиний розв'язок. З цих побудов випливає такий спосіб шифрування з використанням властивостей кільця: RG-EN(k)
RG-DE(T) 1) Будуємо кільце (або тільки групу) порядку k 26 ; 2) Задаючи бієкцію f між елементами кільця (або групи) і символами алфавіту, виконуємо шифрування тексту T . Шифрування можна виконувати з використанням однієї з таблиць, або з використанням обох таблиць. 1) Розшифрування виконується в зворотному порядку: знаходимо значення f 1 на символах шифрограми; потім на основі таблиць кільця повністю дешифруємо отриманий текст (див. нижченаведений приклад).
Розглянемо питання стійкості даного алгоритму та надійності. Оскільки при визначенні групи GNk повинні породжуватися всі елементи, то простір ключів, як випливає з теореми 1, складатиме (k 2)! варіантів. Дійсно, кількість способів, якими можна задати ключ, дорівнює кількості ізоморфізмі групи k -го порядку а це кількість способів упорядкування (k 2) -елементної множини (два елементи 0 і 1 мають фіксовані позиції). Далі, приписування номерів символам алфавіту може виконуватися n! способами , де n – кількість символів алфавіту. Отже, простір ключів має розмір (k 2)!n! .
Наприклад, якщо розглядається група з 25 елементів, то такого простору (23! 25!) вибору ключів достатньо для забезпечення хорошої стійкості шифру.
Побудову групи або кільця, наприклад, KGN25 , маючи в розпорядженні групу порядку GN5 , можна виконати шляхом застосування операції прямого добутку кілець або прямої суми груп GN25 = GN5 GN5 , операції додавання і множення в яких виконуються покомпонентно, тобто a,b c, d a c, b d ,
a,b c, d (a c, b d ) .
Приклад 1. Розглянемо на прикладі групи (яка є прямою сумою абелевих груп GN25 = GN5 GN5 ) кільця KGN25 застосування алгоритму шифрування і дешифрування.
Нехай літери алфавіту англійської мови перенумеровані таким чином:
Розшифрування відбувається в зворотному напрямку. Абоненту, якому адресована ця шифрограма,
відомий ключ таблиці додавання і ключове слово «IPRSР». Виписуємо цифрову шифрограму і цифрові
значення ключового слова; за першим символом a ключового слова знаходимо символ, який є першим
символом шифрограми в таблиці додавання групи (в прикладі за символом a 6 знаходимо значення b 12 ,
тобто розв’язуємо рівняння a x b ); за знайденим значенням в стовпчику, що відповідає цьому значенню b,
знаходимо відповідник (у прикладі це число x 19 , якому відповідає символ u); цей цикл повторюється доти,
доки не буде знайдено весь текст повідомлення.
Наведений в прикладі текст можна зашифрувати, використовуючи таблицю множення. Ця обставина
дозволяє використовувати одночасно дві таблиці для шифрування, тобто одній парі літер ставимо у
відповідність елемент таблиці додавання, а наступній парі літер, яка повторюється, – відповідник з таблиці
множення (тобто відповідником буде елемент m i j ). Але це можливо лише у випадку, коли один з
елементів добутку є дільником одиниці в кільці KGNk . Відомо, що множина дільників одиниці є абелевою
групою в такому кільці [
Теорема 2. Скінченне асоціативно-комутативне кільце з одиницею k-го порядку, адитивна група якого повноциклічна, має (k) дільників одиниці, де – функція Ойлера.
Доведення. Розглянемо Zk – кільце лишків за модулем k. Неважко переконатися в тому, що адитивна група цього кільця є повноциклічною групою. Дільниками одиниці в цьому кільці будуть елементи, які взаємно прості з модулем кільця k , а кількість таких елементів, як відомо, дорівнює значенню функції Ойлера (k) . На підставі теореми 1 існує ізоморфізм між кільцем лишків Zk і кільцем KGNk , який є продовженням ізоморфізму між адитивними групами цих кілець. Звідси випливає справедливість твердження теореми.
Ілюстрацією теореми 2 є кільце KGN6 , задане вищенаведеними табл. 4 і 5. Оскільки кільце лишків за модулем 6 має єдиний елемент 5, який взаємно простий з модулем 6, а цьому елементу при ізоморфізмі відповідає елемент 2, то з таблиці 5 легко побачити, що 2 – дільник одиниці. На підставі теореми 1 побудову таблиці множення можна не приводити, а використати ізоморфізм f: Z25 → KGN25 . Дійсно, таблиця відповідностей має вигляд: f 0 0 , f 1 1, f 2 6 , f 3 8 , f 4 10 , f 5 2 , f 6 4 , f 7 3 , f 8 5 , f 9 7 , f 10 9 , f 11 11, f 12 13 , f 13 15 , f 14 17g , f 15 19 , f 16 21, f 17 12 , f 18 14 , f 19 16 , f 20 18 , f 21 20 , f 22 24 , f 23 22 , f 24 23 .
Дільниками нуля в цьому кільці лишків є елементи 5,10,15, 20. Цим елементам в кільці KGN25 відповідають елементи 2,9,18,19. Решта елементів цього кільця – дільники одиниці, які утворюють абелеву мультиплікативну групу цього кільця. Отже, для знаходження добутку, наприклад, елементів 6 і 7, знаходимо добуток їх відповідників 2 і 9 в кільці лишків 18 = 18 (mod 25). Тоді в кільці KGN25 відповідником є елемент f 18 14 . Отже, 6·7=14 в кільці KGN25 .
Неважко переконатися, що породжуючими елементами цієї мультиплікативної групи є елементи 5 , 6, 8,12,13,15, 22, 24. Це випливає з такої теореми.
Теорема 3. Якщо мультиплікативна група дільників одиниці асоціативно-комутативного кільця з
одиницею має твірний елемент g , то твірними елементами цієї групи будуть елементи g j такі, що
НСД( j, (k)) 1 [
Дійсно, в нашому прикладі мультиплікативної групи кільця KGN25 маємо: а також дільниками одиниці будуть елементи 1,3,5,7,9,11,13,15. Ці елементи мають порядок 2 або 4 і тому група дільників одиниці не буде циклічною. Це одна з причин того, що в криптографії застосовуються скінченні поля а не кільця, оскільки в скінченному полі його мультиплікативна група завжди циклічна. Ця обставина дозволяє використовувати в скінченних полях функцію дискретного логарифму.
Виходячи з того, що порядок мультиплікативної групи кільця дорівнює (k) , то звідси випливає, що найкращий порядок кільця k буде тоді, коли (k) просте число. В цьому випадку мультиплікативна група дільників кільця проста і тому на підставі теореми Лагранжа буде циклічною, тобто породжуватиметься довільним своїм елементом. Але автору невідомо існування такого числа k ! .
Якщо такого числа не існує, то потрібно вибрати число k таким, щоб у розкладі числа (k) на прості множники був великий простий дільник. Така ситуація буде мати місце тоді, коли (k) 2r , де r – просте число. Наприклад, якщо k 9 , то (9) 6 3 2 і тоді мультиплікативна група цього кільця матиме циклічну підгрупу 3-го порядку. Зрештою при шифруванні в разі потреби можна використовувати довільну циклічну підгрупу мультиплікативної групи дільників кільця KGNk .
Можливість використання обох таблиць операцій кільця дозволяє краще «розчинити» частоту появи двознаків у шифрограмі.
Шифри гомофонічні. Відомо, що моноалфавітні шифри ламаються методом частотного аналізу, тоді
запобігти такому криптоаналізу можна відображенням однієї літери в декілька її образів, які називаються
гомофонами [
Приклад 2. Застосуємо гомофонічний шифр до шифрування тексту «kukuriku» з ключовим словом «kuku». Шифрування відбувається на основі таблиці гомофонів, взятих з таблиці додавання вищенаведеної групи : Символ Гомофони адитивні
Гомофони мультиплікативні K – 0402, 0310, 1216, 1522, 2417; U – 0209, 0117, 0902, 1224; R – 1511, 0709, 1206; I – 0318, 0420, 1121, 1317. Ключове слово: Текст відкритий: K Висновки Література Гарантією однозначного розшифрування є добра відома властивість: відображення множини А на множину В визначає на множині А відношення еквівалентності. Елементами класів розбиття за цим відношенням еквівалентності є гомофони літер алфавіту.
Відповідниками можуть бути різні гомофони і їх можна далі застосовувати ротаційно випадковим чином. В загальному випадку гомофонами символу алфавіту, якому відповідає елемент таблиці m, будуть такі пари i, j елементів таблиці додавання (множення), які задовольняють умову i j m (i j m) . При цьому, якщо пара i, j вже вибрана гомофоном, то пару j,i не варто брати гомофоном (симетрія входження цифр – підказка криптоаналітику). Всіх гомофонів в таблиці додавання буде k, а в таблиці множення (k) .
Запропонована проста криптосистема на основі властивостей абелевих груп і асоціативно-комутативних кілець з одиницею. Зауважимо, що при традиційно прийнятому порядку літер англійського алфавіту таблиця додавання кільця лишків Z25 буде відповідає таблиці шифру Віженера. Пропонована система має широкий простір ключів, що є достатнім для стійкості системи. Для побудови такої системи потрібно побудувати таблиці додавання і множення групи і кільця. З цією метою пропонуються алгоритми побудови цих таблиць з квадратичною оцінкою складності. Шифрування і розшифрування теж виконуються в квадратичному часі. Про автора: