Алгоритмы шифрования

Алгоритми шифрування  
Розглянемо докладніше методи криптографічного захисту даних, про які було сказано в попередньому пункті (п. 2.4).  
Алгоритми заміни (підстановки)  
У цьому найбільш простому методі символи шіфруемого тексту замінюються іншими символами, взятими з одного-(одно-або моноалфавитной підстановка) або декількох (багато-або поліалфавітного підстановка) алфавіту.  
Найпростішою різновидом є пряма (проста) заміна, коли літери шіфруемого повідомлення замінюються іншими літерами того ж самого чи деякого іншого алфавіту. Таблиця заміни може мати наступний вигляд (таблиця 3.1.1):

 
Таблиця 3.1.1 Таблиця простої заміни  

Використовуючи цю таблицю, Зашифруємо текст: In this book the reader will find a comрrehensive survey ... Отримаємо наступне зашифроване повідомлення: At omiy рbbe omr nrsirn fadd zail s xbwgnrmrtjafr jcnfru ... Однак такий шифр має низьку стійкість, так як зашифрований текст має ті ж статистичні характеристики, що й вихідний. Наприклад, текст англійською мовою містить символи з наступними частотами появи (в порядку убування): Е - 0,13, Т - 0,105, А - 0,081, О - 0,079 і т.д. У зашифрованому тексті найбільші частоти появи в порядку убування мають літери R - 0,12, O - 0,09, A і N по 0,07.  
Природно припустити, що символом R зашифрована літера Е, символом О - літера Т і т.д. Це дійсно відповідає таблиці заміни. Подальша розшифровка не складає труднощів.  
Якби обсяг зашифрованого тексту був набагато більше, ніж у розглянутому прикладі, то частоти появи літер у зашифрованому тексті були б ще ближче до частот появи літер в англійському алфавіті і розшифровка була б ще простіше. Тому просту заміну використовують рідко і лише в тих випадках, коли шіфруемий текст короткий.  
Для підвищення стійкості шрифту використовують поліалфавітні підстановки, в яких для заміни символів вихідного тексту використовуються символи кількох алфавітів. Відомо кілька різновидів поліалфавітному підстановки, найбільш відомими з яких є одне-(звичайна і монофонічна) і Багатоконтурна.  
При поліалфавітному одноконтурною звичайної підстановці для заміни символів вихідного тексту використовується кілька алфавітів, причому зміна алфавітів здійснюється послідовно і циклічно, тобто перший символ замінюється відповідним символом першого алфавіту, другий - символом другого алфавіту і т.д., поки не будуть використані всі вибрані алфавіти. Після цього використання алфавітів повторюється.  
Схема шифрування Вижинера. Таблиця Вижинера являє собою квадратну матрицю з n 2 елементами, де n - число символів використовуваного алфавіту. На Ріс.3.1.2 показана верхня частина таблиці Вижинера для кирилиці. Кожен рядок отримана циклічним зсувом алфавіту на символ. Для шифрування вибирається буквений ключ, відповідно до якого формується робоча матриця шифрування.

Рис. 3.1.2 Таблиця Вижинера

 
Здійснюється це таким чином. З повної таблиці вибирається перший рядок і ті рядки, перші літери яких відповідають буквам ключа. Першою розміщується перший рядок, а під нею - рядки, відповідні буквах ключа в порядку проходження цих букв в ключі шифрування. Приклад такої робочої матриці для ключа «книга» наведено на Рис. 3.1.3.  
Процес шифрування здійснюється наступним чином:

 
Рис. 3.1.3 Робоча матриця шифрування для ключа «книга».  
1. під кожною буквою шіфруемого тексту записуються літери ключа. Ключ при  
цьому повторюється необхідну кількість разів.  
2. кожна літера шіфруемого тексту замінюється по підматриць літерами знаходяться на перетині ліній, що з'єднують букви шіфруемого тексту в першому рядку підматриці і перебувають під ними букв ключа.  
3. отриманий текст може розбиватися на групи по кілька знаків.  
Нехай, наприклад, потрібно зашифрувати повідомлення: максимально допустимої ціною є п'ятсот руб. за штуку. Відповідно з першим правилом записуємо під буквами шіфруемого тексту букви ключа. Одержуємо:  
 
максимально допустимої ціною є п'ятсот руб. за штуку  
кнігакнігак нігакнігак нігак нігакніг акнігак ніг ак нігак  
Далі здійснюється безпосереднє шифрування відповідно до другого правилом, а саме: беремо першу літеру шіфруемого тексту (М) і відповідну їй букву ключа (К); по букві шіфруемого тексту (М) входимо в робочу матрицю шифрування і вибираємо під нею букву, розташовану в рядку, що відповідає букві ключа (К), - у нашому прикладі такою буквою є Ч; обрану таким чином букву поміщаємо в зашифрований текст. Ця процедура циклічно повторюється до зашифрування всього тексту.  
Експерименти показали, що при використанні такого методу статистичні характеристики вихідного тексту практично не виявляються в зашифрованому повідомленні. Неважко бачити, що заміна за таблицею Вижинера еквівалентна простій заміні з циклічним зміною алфавіту, тобто тут ми маємо поліалфавітного підстановку, причому число використовуваних алфавітів визначається числом літер у слові ключа. Тому стійкість такої заміни визначається твором стійкості прямої заміни на число використовуваних алфавітів, тобто кількість літер в ключі.  
Розшифровка тексту проводиться в такій послідовності:  
1. над буквами зашифрованого тексту послідовно надписуються букви ключа, причому ключ повторюється необхідну кількість разів.  
2. у рядку підматриці Вижинера, відповідної букви ключа відшукується буква, відповідна знаку зашифрованого тексту. Що знаходиться під нею буква першого рядка підматриці і буде буквою вихідного тексту.  
3. отриманий текст групується в слова за змістом.  
 
Неважко бачити, що процедури як прямого, так і зворотного перетворення є строго формальними, що дозволяє реалізувати їх алгоритмічно. Більше того, обидві процедури легко реалізуються за одним і тим же алгоритмом.  
Одним з недоліків шифрування за таблицею Вижинера є те, що при невеликій довжині ключа надійність шифрування залишається невисокою, а формування довгих ключів пов'язане з труднощами.  
Недоцільно вибирати ключі з повторюваними літерами, так як при цьому стійкість шифру не зростає. У той же час ключ повинен легко запам'ятовуватися, щоб його можна було не записувати. Послідовність же букв не мають сенсу, запам'ятати важко.  
З метою підвищення стійкості шифрування можна використовувати вдосконалені варіанти таблиці Вижинера. Наведу тільки деякі з них:  
· В усіх (крім першої) рядках таблиці літери розташовуються в довільному порядку.  
· Як ключ використовується випадковість послідовних чисел. З таблиці Вижинера вибираються десять довільних рядків, які кодуються натуральними числами від 0 до 10. Ці рядки використовуються відповідно до чергуванням цифр у вибраному ключі.  
 
Відомі також і багато інших модифікації методу.  
Алгоритм перестановки  
Цей метод полягає в тому, що символи шіфруемого тексту переставляються за певними правилами всередині шіфруемого блоку символів. Розглянемо деякі різновиди цього методу, які можуть бути використані в автоматизованих системах.  
Найпростіша перестановка - написати вихідний текст задом наперед і одночасно розбити шифрограму на п'ятірки букв. Наприклад, із фрази  
ХАЙ БУДЕ ТАК, ЯК МИ ХОТІЛИ.  
вийде такий шифротекст:  
Ілето ХИМКА ККАТТ ЕДУБ' ТСУП  
В останній групі (п'ятірці) не вистачає однієї літери. Значить, перш ніж шифрувати вихідне вираз, слід його доповнити незначущий буквою (наприклад, О) до числа, кратного п'яти:  
ХАЙ-БУДЕ-Такка-КМИХО-ТЕЛІО.  
Тоді шифрограма, незважаючи на настільки незначні зміни, буде виглядати по-іншому:  
ОІЛЕТ ОХИМК АККАТ ТЕДУБ ЬТСУП  
Здається, нічого складного, але при розшифровці виявляються серйозні незручності.  
Під час Громадянської війни в США в ходу був такий шифр: вихідну фразу писали в кілька рядків. Наприклад, по п'ятнадцять букв у кожній (з заповненням останнього рядка незначущими літерами).  
 
П У С Т Ь Б У Д Е Т Т А К К А  
До М И Х О Т Е Л І К Л М Н О П  
Після цього вертикальні стовпчики по порядку писали в рядок з розбивкою на п'ятірки літер:  
ПКУМС ИТХЬО БТУЕД ЛЕІТК ТЛАМК НКОАП  
Якщо рядки вкоротити, а кількість рядків збільшити, то вийде прямокутник-решітка, в який можна записувати вихідний текст. Але тут вже буде потрібно попередня домовленість між адресатом і відправником послань, оскільки сама грати можуть бути різної довжини-висоти, записувати до неї можна по рядках, по стовпцях, по спіралі туди чи по спіралі назад, можна писати і по діагоналями, а для шифрування можна брати теж різні напрямки. Загалом, тут маса варіантів.  
   
Алгоритм гамування  
Суть цього методу полягає в тому, що символи шіфруемого тексту послідовно складаються з символами деякої спеціальної послідовності, яка називається гамою. Іноді такий метод представляють як накладення гами на вихідний текст, тому він отримав назву «гамування». Процедуру накладення гами на вихідний текст можна здійснити двома способами. При першому способі символи вихідного тексту і гамми замінюються цифровими еквівалентами, які потім складаються за модулем k, де k - число символів в алфавіті, тобто  
R i = (S i + G) mod (k -1),  
де R i, S i, G - символи відповідно зашифрованого, вихідного тексту і гамми.  
Рис. 3.3.1 Приклад шифрування гаммированием  
При другому методі символи вихідного тексту і гамми представляються у вигляді двійкового коду, потім відповідні розряди складаються за модулем 2. Замість  
додавання за модулем 2 при гамування можна використовувати й інші логічні операції, наприклад перетворення по правил логічної еквівалентності і нееквівалентності.

Така заміна рівнозначна введення ще одного ключа, який є вибір правила формування символів зашифрованого повідомлення із символів вихідного тексту і гамми (Рис 3.3.1).  
Стійкість шифрування методом гамування визначається головним чином властивістю гами - тривалістю періоду і рівномірністю статистичних характеристик. Остання властивість забезпечує відсутність закономірностей у появі різних символів в межах періоду.  
Зазвичай розділяють два різновиди гамування - з кінцевої і нескінченної гамами. При хороших статистичних властивостях гами стійкість шифрування визначається тільки довгої періоду гами. При цьому, якщо довжина періоду гами перевищує довжину шіфруемого тексту, то такий шифр теоретично є абсолютно стійким, тобто його не можна розкрити за допомогою статистичної обробки зашифрованого тексту. Це, однак, не означає, що дешифрування такого тексту взагалі неможливо: при наявності деякої додаткової інформації вихідний текст може бути частково або повністю відновлений навіть при використанні нескінченної гами.  
Як гами може бути використана будь-яка послідовність випадкових символів, наприклад, послідовність цифр числа p і т.п. При шифруванні за допомогою, наприклад, апаратного шифратора послідовність гами може формуватися за допомогою датчика псевдовипадкових чисел (ПСЧ). В даний час розроблено декілька алгоритмів роботи таких датчиків, які забезпечують задовільні характеристики гами.  
Алгоритми, засновані на складних математичних перетвореннях  
Алгоритм RSA  
    Алгоритм RSA (за першими літерами прізвищ його творців Rivest-Shamir-Adleman) заснований на властивостях простих чисел (причому дуже великих). Простими називаються такі числа, які не мають дільників, крім самих себе і одиниці. А взаємно простими називаються числа, що не мають спільних дільників, крім 1.  
Для початку виберемо два дуже великих простих числа (великі вихідні числа потрібні для побудови великих криптостійкі ключів. Наприклад, Unix-програма ssh-keygen за замовчуванням генерує ключі довжиною 1024 біта). Визначимо параметр n як результат перемноження р і q. Виберемо велике випадкове число і назвемо його d, причому воно повинно бути взаємно простим з результатом множення (р -1) * (q -1). Відшукаємо таке число e, для якого правильне співвідношення  
(E * d) mod ((р -1) * (q -1)) = 1  
(Mod - залишок від ділення, тобто якщо e, помножене на d, поділити на ((р -1) * (q -1)), то у залишку отримаємо 1).  
Відкритим ключем є пара чисел e і n, а закритим - d і n. При шифруванні вихідний текст розглядається як числовий ряд, і над кожним його числом ми здійснюємо операцію  
C (i) = (M (i) e) mod n.  
У результаті виходить послідовність C (i), яка і складе криптотекст. Декодування інформації відбувається за формулою  
M (i) = (C (i) d) mod n.  
Як бачите, розшифровка передбачає знання секретного ключа.  
Давайте спробуємо на маленьких числах. Встановимо р = 3, q ​​= 7. Тоді n = р * q = 21. Вибираємо d як 5. З формули (e * 5) mod 12 = 1 обчислюємо e = 17. Відкритий ключ 17, 21, секретний - 5, 21.  
Зашифруємо послідовність «2345»:  
C (2) = лютого 1917 mod 21 = 11  
C (3) = 17 Березня mod 21 = 12  
C (4) = 17 Квітня mod 21 = 16  
C (5) = 17 травня mod 21 = 17  
Криптотекст - 12 листопада 1916 17.  
Перевіримо розшифровкою:  
M (2) = 11 травня mod 21 = 2  
M (3) = 12 травня mod 21 = 3  
M (4) = 16 травня mod 21 = 4  
M (5) = 17 травня mod 21 = 5  
Як бачимо, результат збігся.  
 
Криптосистема RSA широко застосовується в Інтернеті. Коли ви під'єднуйтеся до захищеного сервера по протоколу SSL, встановлюєте на свій ПК сертифікат WebMoney або підключаєтеся до віддаленого сервера з допомогою Oрen SSH або SecureShell, то всі ці програми застосовують шифрування відкритим ключем з використанням ідей алгоритму RSA. Чи справді ця система така надійна?  
З моменту свого створення RSA постійно піддавалася атакам типу Brute-force attack (атака методом грубої сили, тобто перебором). У 1978 р. автори алгоритму опублікували статтю, де призвели рядок, зашифровану щойно винайденим ними методом. Першому, хто розшифрує повідомлення, було призначено винагороду в розмірі 100 дол, але для цього було потрібно розкласти на два співмножники 129-значне число. Це був перший конкурс на злом RSA. Завдання вирішили лише через 17 років після публікації статті.  
Крипостійкість RSA грунтується на тому припущенні, що так важко, якщо взагалі реально, визначити закритий ключ з відкритого неба. Для цього було потрібно вирішити задачу про існування дільників величезного цілого числа. До цих пір її аналітичними методами ніхто не вирішив, і алгоритм RSA можна зламати лише шляхом повного перебору. Строго кажучи, твердження, що завдання розкладання на множники складна і що злом системи RSA важкий, також не доведено.  
Компанія RSA (httр: / / www.rsa.ru) регулярно проводить конкурси на злом власних (і не тільки власних) шифрів. Попередні конкурси виграла організація Distributed.net (htt р: / / www. Distributed. Net /), що є Інтернет-спільнотою добровольців.  
Учасники Distributed.net завантажують до себе на ПК невелику програму-клієнт, яка приєднується до центрального сервера і отримує шматочок даних для обчислень. Потім усі дані завантажуються на центральний сервер, і клієнт отримує наступний блок вихідної інформації. І так відбувається до тих пір, поки всі комбінації не будуть перебрані. Користувачі, учасники системи, об'єднуються в команди, а на сайті ведеться рейтинг як команд, так і країн. Наприклад, що бере участь в конкурсі по злому RC5-64 (блочний шифр компанії RSA, що використовує ключ довжиною 64 біта) організації Distributed.net вдалося здійснити злом через п'ять років (1757 днів) роботи. За цей час у проекті брали участь 327 856 користувачів і було перебрати 15 268 315 356 922 380 288 варіантів ключа. З'ясувалося, що була (не без гумору) зашифрована фраза «some things are better left unread» («деякі речі краще залишати непрочитані»). Загальні рекомендації по шифру RC5-64 такі: алгоритм досить стійкий для повсякденних потреб, але шифрувати їм дані, що залишаються секретними протягом більш ніж п'яти років, не рекомендується ».