Створення криптографії за допомогою модулярної математики, Стаття у журналі «Молодий ученый»
Бібліографічний опис:
У цій статті розглядаються основи криптографії, а також модулярної арифметики, які лягли в основу багатьох шифрів. Особливе місце у криптографії посідає шифр Цезаря, що також будується на основах модулярної арифметики. Вивчивши механізм побудови даного шифру, вдалося зашифрувати слово, розшифрування якого є зворотним процесом.
Ключові слова:криптографія, шифр, алгоритм шифрування, модулярна арифметика, шифр Цезаря.
Абстракт.Ця стаття включає в себе основи криптографії, як добре як modulary аритметичні, які формуються основою багатьох цифер. А особливе місце в криптографії є Caesar cipher, який є також заснований на принципах modular аритмічного. Маючи вивчений mechanismus for constructing this cipher to encrypt word transcript of which is the reverse process.
Keywords:криптографії, цифера об'яви algoritm, modular аритмічний, Caesar цифер.
Ще з давніх-давен люди стали замислюватися про те, що будь-яку інформацію можна приховати шляхом створення спеціального коду, тобто. алфавіту, за допомогою якого можна приховати інформацію від сторонніх очей, тим самим залишити її конфіденційною. З настанням інформаційного століття кодування та шифри стали необхідними для нормального функціонування суспільства. З'явилася потреба у криптографії.
Криптографія – це мистецтво кодованого листа, яка з'явилася ще з появою писемності.
Основним завданням криптографії є передати інформацію, яка потребує секретності. У таких випадках говорять, що інформація містить таємницю або є захищеною,приватної, конфіденційної. Для ситуацій такого типу, що часто зустрічаються, існують спеціальні поняття, які представлені в схемі 1 [3, с.7].
 |
Виникнення шифрування інформації спричинило зворотний процес, тобто створення дешифрування. Першим, хто придумав метод дешифрування, у VIII столітті був Аль-Кінді, цей метод допомагав розкривати будь-яке закодоване повідомлення. З того часу головною зброєю, що застосовується кожною з країн, була математика, від статистики та теорії чисел до модульної арифметики. Основною метою кодування на той момент було полегшити пересилання. Іншими словами, інформацію мають знати лише відправник та законний одержувач, а код має бути зашифрований. Існує багато різних алгоритмів шифрування, але загальна система шифрування представлена так на схемі 2:
Такий алгоритм дуже зручно і корисно використовувати, як у повсякденному житті, так у науці та політиці. Криптографія почала розвиватися, стали виникати різні техніки приховання «святого»: стеганографія, перестановочне шифрування, модульна арифметика і математика шифру Цезаря.
Зупинимося на роботі шифра Цезаря, яка може бути проілюстрована теорією, звичною для математики і ще великою мірою для криптографії – модульною арифметикою, яка іноді називається годинниковою арифметикою. Що таке модульна арифметика і чому вона називається годинниковою? У шифрі Цезаря ключі є число символів, яким зсуваються літери алфавіту. При шифруванні замість кожної літери відкритого тексту ставиться літера, віддалена від неї правіше на число букв, що задається значенням ключа. Розшифровка полягає у зміщенні кожної літери ліворуч на число букв, що задається тим самим значенням ключа, яке використовувалося пришифрування [1, с.26].
Шифр Цезаря заснований на фіксованому зміщенні літер алфавіту. Літери зрушуються по колу, тому після останньої літери алфавіту йде його перша літера.
При шифруванні з ключем алгоритми шифрування та розшифрування можуть бути добре відомі. Але дешифрувальний та (іноді) шифрувальний ключі суворо секретні. Зашифрований текст, отриманий в результаті шифрування відкритого тексту за допомогою конкретного ключа шифрування, може бути розшифрований тільки за допомогою дешифрувального ключа, пов'язаного з шифрувальним ключем.
Перші праці, пов'язані з криптографією, були знайдені в роботах Евкліда, які були тісно пов'язані з арифметичними операціями на кінцевих числових множинах або операціями по модулю, які є однією з основ сучасної теорії криптографії. Для прикладу розглянемо годинник зі стрілками та електронний годинник. Циферблат стрілочного годинника розділений на 12 частин, які в електронному годиннику позначаються, як 0, 1, 2, ,3 ,4 , 5, 6, 7, 8, 9, 10, 11.
У таблиці 1 можна побачити, як час на аналоговому циферблаті відповідає часу після полудня на екрані цифрового годинника.
Допустимо, якщо на годиннику 16:00, то можемо сказати, що час чотири години вечора. Той самий принцип використовується і при розрахунку з кутами. Якщо нам потрібно розрахувати кут 800 градусів, то записуємо, що він дорівнює 80 градусам. При цьому віднімаємо кількість повних оборотів, тобто 800 = (2 * 360) + 80, виходить, що це 80 залишок від розподілу 800 на 360, а в математиці це записується наступним чином:
800 80 (mod 360) («800 порівняно з 80 по модулю 360»).
Що стосується годинника це буде: 16≡4 (mod 12). Іншими словами, у загальному випадку це виглядає так:a≡b(modm), якщо залишок від розподілуaнаmдорівнюєb, за умови щоa,bтаm-цілі числа [2,c. 27].
Отже, простежимо зв'язок між модульною арифметикою та шифром Цезаря. Складемо таблицю 2 стандартного алфавіту та алфавіту зі зрушенням на три літери, додамо титульний ряд із 26 чисел.
Зауважимо, що зашифрована літера під номеромx(у стандартному алфавіті) стоїть на позиціїx+3. Тому необхідно знайти перетворення, яке кожному числу ставить у відповідність число, зсунуте на три одиниці, і взяти результат за модулем 26. Отримуємо, що це і є ключ нашого шифру. Таким чином, наша функція записується як:
деx-початкове значення, а C(x)-зашифроване значення.
Наприклад розглянемо слово TABLE і зашифруємо його.
Літера T стоїть на позиції 19, C(19)= 19+3≡22(mod 26), число 22 відповідає літеріW.
Літера A стоїть позиції 0, C(0)= 0+3≡3(mod 26), число 3 відповідає буквіD.
Літера B стоїть на позиції 1, C(1)= 1+3≡4(mod 26), число 4 відповідає буквіE.
Літера L стоїть на позиції 11, C(11)= 11+3≡14(mod 26), число 14 відповідає буквіO
Літера E стоїть позиції 4, C(4)= 4+3≡7(mod 26), число 7 відповідає буквіH.
У результаті слово TABLE, зашифроване з ключем 3, перетвориться на словоWDEOH.
У випадку, якщо x позначає позицію літери, яку хочемо зашифрувати, то формула виглядає так.
C(x)= (x+k) (modn), деn- довжина алфавіту (в англійському алфавіті),
аk- ключ, який використовується в даному шифрі.
Для розшифровки необхідно провести розрахунки зворотні тим, що використовували при шифруванні, тобто:
Зокрема, для нашого прикладу формула виглядатиме так:
(x) =(X-3) (mod 26).
Отримаємо, що шифр Цезаря є математичним перетворенням на криптографії. Він визначається так:
деаіb— два цілих числа, менших за число (п) літер в алфавіті. Найбільший загальний дільник (НОД) чиселаі п повинен дорівнювати 1
[НОД (a, n) = 1], тому що інакше вийде кілька можливостей для шифрування однієї й тієї ж літери. Ключ шифру визначається парою (а, b).Шифр Цезаря з ключем 3 є, отже, афінним шифром зі значеннями,а =1 іb =3.
Узагальнений аффінний шифр має високий рівень безпеки, ніж звичайний шифр Цезаря. Чому? Як ми бачили, ключем афінного шифру є пара чисел(а,b). ,іbможуть набувати будь-яких значень від 0 до 25. Таким чином, у цій системі шифрування з алфавітом з 26 літер можлива кількість ключів складе 25 х 25 = 625. Зауважимо, що кількість ключів для алфавіту зплітер упразів більше, ніж у шифрі Цезаря. Це значне поліпшення, але афінний шифр все ще можна розшифрувати шляхом перебору всіх можливих варіантів [2,c. 32].
На жаль, шифр Цезаря має низьку стійкість і це не єдиний його недолік, у ньому також (у разі українського алфавіту) можливі лише 32 різні ключі, один з яких відображає відкритий текст у той самий відкритий текст.
На етапі розвиток інформаційно-обчислювальних засобів гостро стоїть проблема захисту, що з наданням користувачеві не всіх, лише виділених йому ресурсів та інформації. Захист – як цілеспрямована діяльність із запобігання витокуінформації, несанкціонованого та ненавмисного впливу на інформацію, що становить цінність для її власника. Ця проблема торкається і питання організації доступу до сховищ інформації – баз та банків даних, інформаційних систем. Основи модулярної математики, теорії чисел, дискретної математики здатні захистити інформацію від випадкового та навмисного втручання у нормальний процес функціонування, а також від спроб розкрадання, зміни чи руйнування її компонентів.
1. Барічев С.В. Криптографія без секретів. - М.: Наука, 2004. -120 с.
2. Гомес Ж. Математики, шпигуни та хакери. Кодування та криптографія. - М.: Де Агостіні, 2014. - 144 с.
3. Медведєв Н.В. Теорія чисел у криптографії: навч. допомога. - М.: Вид-во МДТУ ім. Н. Е. Баумана, 2011. - 223 с.