Історичні відомості

" Криптографія" - грецьке слово, що походить від слів kryptos (та­ємний, схований) та graphy (запис) і включає методи і засоби забез­печення перетворення даних з метою маскування (шифрування) змі­сту інформації для гарантування конфіденційності та цілісності, а криптоаналіз орієнтований на зламування шифротекстів (шифрів). Шифротекст є даними, представленими в зашифрованій формі і мають прихований семантичний зміст, який утворюються після шифрування (криптографічного перетворення) відкритого тексту (з неприхованим семантичним змістом).

Зародження криптографії почалося з глибокої давнини, з якої до нас дійшов ряд систем шифрування, які швидше за все з'явилися од­ночасно з писемністю в 4 тис. до н. є. Методи секретного перепису­вання були винайдені незалежно в багатьох стародавніх суспільст­вах (€: гипет, Шумер, Китай).

За свідченням Геродота в стародавньому Єгипті роль шифру за­звичай відігравала спеціально створена жрицями мова. Там парале­льно існували три алфавіти: письмовий, священний і загадковий, останній з яких застосовувався пророками для приховування змісту повідомлень.

В епоху розквіту Риму, шифрований зв'язок для його органів вла­ди став життєво необхідним. У цей час застосовувався відомий шифр заміни, пов'язаний з ім'ям Юлія Цезаря, про якого Гай Свето-ній повідомляє: " Існують і його листи до Цицерона і лисги до близь­ких про домашні справи: в них, якщо потрібно було повідомити про що-небудь негласно, він користувався тайнописом, тобто змінював букви так, щоб з них не складалося жодного слова. Щоб розібрати і прочитати їх, потрібно кожного разу читати четверту букву замість першої, наприклад, D замість А і так далі". Наприклад, відповідно до цього шифру послання сенату VENI VEDI VICI (ПРИЙШОВ ПОБАЧИВ ПЕРЕМІГ), зроблене Цезарем після одноденної війни з понгийским царем Фарнаком, представлялося б шифротекстом SBKF SFAF SFZF.

ВІДОМИЙ принципово інший шифр, пов'язаний з перестановкою букв повідомлення за певним (відомим відправнику і одержувачу) правилом. Стародавні помітили, що якщо смужку пергаменту намо-іі пі спіраллю на паличку і написати на ній вздовж палички текст повідомлення, то, після знятгя смужки букви будуть розташовані UOl ично. Це те ж саме, ніби букви писати не підряд, а через домов-ІХЄИЄ число по кільцю доти, доки весь текст не буде вичерпаний. Так відкритий текст АВІАЦІЙНИЙ при діаметрі палички в 3 букви дасть іпифротекст АЦИВІЙШАН, для розшифрування якого слід знати систему засекречування і мати ключ у вигляді палички, прийнятого цімстру (див. рис. 6.1). Цей шифр іменувався скитала (сцитала) за назвою стержня, на який намотувалися свитки папірусу.

Варто сказати, що грецький письменник і історик Полібій ви­їм йшов так званий полібіанський квадрат (II ст. до н. є.) розміром 5х 5, заповнений алфавітом у випадковому порядку. Для шифруван­ня па квадраті знаходили букву тексту і вставляли в шифротекст нижню від неї у тій самій колонці. Якщо буква була в нижньому ря­дку, то брали, верхню з тієї самої колонки.

І Іаведемо спрощений приклад такого квадрату (див. рис. 6.2), для ЯКОГО відкритому тексту АВІАЦІЙНИЙ буде відповідати шифро-і.м гЖИЄЖІЄБЙТБ.

Рис. 6.2. Приклад зашифрованого тексту полібіанським квадратом

І Іаралельно з методами шифрування створювалися і засоби їх ре-ВЛІзації. Так, наприклад, винахідливі римляни застосовували два шифруючи диски (TV ст. до н. є.), які були розміщені на спільну вісь. Кожен з них містив на ободі алфавіт у випадковій послідовності. (найшовши на одному диску букву тексту, з іншого диска зчитували

відповідну їй букву шифру. Такі пристрої використовув& чися аж до епохи Відродження. Але з моменту падіння Римської імперії багато досягнень криптоірафії були втрачені і лише в кінці середньовіччя її застосування починає відроджуватися.

В ручних шифрах того часу часто використовуються таблиці, що
дають прості шифрувальні процедури перестановки букв у повідом­
ленні. Тут ключем служать розмір таблиці, фраза, що задає переста­
новку або спеціальна особливість таблиць. Проста перестановка без
ключа - один з найпростіших „методів шифрування, споріднений
шифру скитала. Наприклад, повідомлення НАЦІОНАЛЬНИЙ
АВІАЦІЙНИЙ УНІВЕРСИТЕТ записується в таблицю в рядки. Для
таблиці з 3 рядків і 11 колонок це виглядає так, як показано на рис. 5.3:

Після того, як відкритий текст записали рядками, для утворення шифротексту він зчитується колонками. Якщо його записувати гру­пами по 3 букви, то вийде: НЙУ ААН ЦВІ ІІВ ОАЕ НЦР АІС ЛЙИ ЬНТ НИЕ ИЙТ. Для використання цього шифру відправнику й оде­ржувачу необхідно домовитися про загальний ключ як розмір таб­лиці. Групування букв не входить у ключ шифру і використовується лише для зручності запису беззмістовного тексту.

Середньовічні вчені часто використовували магічний квадрат у вигляді рівносторонньої таблиці з вписаними в їх комірки послідов­ними натуральними числами від 1, що дають у сумі в кожній колон­ці, кожному рядку і кожній діагоналі те саме число. В такі квадрати вписувався відкритий текст відповідно до наведеної в них нумерації. Якщо потім виписати вміст таблиці колонками, то виходить шифро-гекст утворений перестановкою букв. Вважалося, що такі створені шифротексти охороняє не тільки ключ, але і магічна сила. На рис, 6.4 наведено приклад магічного квадрата і його шифротексту.

Отриманий з відкритого тексту ЗАХИСТ ІНФОРМАЦІЇ, шифро-текст ЇСФИХОТ1АРЩАНМЗ має досить вагомий вигляд. На перший погляд здається, начебто магічних квадратів дуже мало, але їх число дуже швидко зростає зі збільшенням розміру квадрату. Так, існує лише один магічний квадрат розміром 3x3 (ие враховуючи його по­вороти), квадратів 4x4 уже 880, а 5x5 близько 250000, тому їх великі розміри стали вагомою основою для надійної системи шифрування того часу, оскільки ручний перебір всіх варіантів ключа для цього шифру був немислимий.

Одна з відомих фігур ренесансної архітектури пов'язана з ім'ям Леона Батисту Альберта, який винайшов шифр поліалфавітної замі­ни, що є стійким до розкриття і докладно описав пристрої з оберта-ючихся колес для його реалізації. Цей шифр можна описати спеціа­льною таблицею шифрування (див. рис. 6.5), яку іноді називають таблицею (квадратом) Віженера, названу ім'ям дипломата Блеза Віженера, який у XVI столітті розвивав і удосконалював криптографічні системи. Кожен рядок у цій таблиці відповідає одному типовому шифру Цезаря для алфавіту з проміжком. Повідомлення, що шифрується, виписують у рядок, а під ним розміщують ключ. Якщо він виявився коротший за відкритий текст, то його циклічно повторюють. Шиф-ротекст формується шляхом знаходження символу у колонці таблиці за буквою тексту і рядка, що відповідає букві ключа. Наприклад, використовуючи ключ НАУ для відкритого тексту АВІАЦІЙНИЙ сформується шифротекст, який наведеїіий на рис.5.6:

і: ---------- 1 1 1 1 1 І і,. і 1 1 .. і

Цей розповсюджений підхід дожив і до наших днів. Практично таку операцію можна реалізувати додаванням кодів ASCII символів відкритого тексту і ключа за деяким модулем.

Крім своїх архітектурних шедеврів, Альберт ще ввів у практику криптографії багатоалфавітні (поліалфавігні) шифри заміни. Його книга " Трактат про шифр" (1466 р.) була першою у світі науковою працею з криптографії (не враховуючи арабських рукописів, які у Європі мало знали).

Історики вважають Йогана Тритемія другим батьком сучасної криптографії, який у роботі «Стеганографія» першим систематично описав застосування таблиць шифрування, які заповнені алфавітом у випадковому порядку, а також зазначив, що можна шифрувати дві букви за один раз. Такі шифри, на відміну від раніше описаних (мо-нограмних), були названі біграмними підстановочними шифрами і різко підсилили їхню стійкість до розкриття. Найбільш відомий шифр біграмами називається Play-fair (Чесна гра), винайдений у 1854 році. Він застосовувався Великобританією в Першу світову війну. Опишемо його на прикладі магічного квадрата (див.

рис. 6. 4):

Відкритий текст розбивався па пари букв (біграми) і шифротекст складався з нього за наступними двома дуже простими правилами.

1. Якщо обидві букви біграми початкового тексту належали одній колонці таблиці, то буквами шифру вважалися ті, що знаходи­лись під ними. Так біграма ЗИ давала текст ВТ. Якщо буква відкри­того тексту знаходилася в нижньому рядку, то для шифру бралася відповідна буква з верхнього ряду і біграма СІ давала шифр ЦС. (Бі-

грама з однієї букви чи пари однакових букв теж підпорядковувала­ся цьому правилу і текст 33 давав шифротекст ВВ).

2. Якщо обидві букви бі грами початкового тексту належа­ли одному рядку таблиці, то буквами шифру вважаються букви, які знаходились праворуч від них. Гак біірама ИД давала шифро­текст ЄС. Якщо буква відкритого тексту знаходилася у правій коло­нці, то для шифру бралася відповідна буква з лівої колонки і біграма СЕ давала шифр КД. Якщо обидві букви бі грами відкритого тексту лежали в різних рядах і колонках, то замість них бралися такі дві букви, щоб уся четвірка їх представляла прямокутник. При цьому послідовність букв у шифрі була дзеркальною початковій парі. На­приклад, ВР шифрувалося як БТ, а ДХ як ИН.

Шифрований текст слова АВІАЦІЙНИЙ за біграмами показано на рис. 5.7 в нижньому рядку.

Починають з'являються професійні і навіть потомствені крипто-графи, типу сімейства Ардженті, який служив у папи Римського.

Починаючи з тих часів, багато видатних математиків стали залу­чатися до криптографічної служби, наприклад, у Росії Леонард Зй-лер, якому історики приписують знаменитий гороскоп Івана VI, а у Фраіщії таким математиком був Франсуа Віст.

У XVII ст. в Англії математик Джон Валліс очолював криптогра­фічну службу і одержав популярність за рідкісні успіхи в розшифру­ванні, а в Німеччині того часу кращим криптографом був Лейбніц.

Роджер Бекон будучи лордом-канцлером при королі Якові І, доб­ре знав потреби держави в надійних шифрах і в 1580 році написав роботу з криптографії, яка одержала успішний практичний розвиток, наприклад, він вперше запропонував двійкове кодування букв ла­тинського алфавіту, що використовується зараз у комп'ютерах.

У XIX столітті почалася автоматизація процесу шифрування, на­приклад, держсекретар Томас Джефферсон (згодом президент США) у 1790 році винайшов шифруюче колесо, що реалізує поліалфавітну заміну тексту повідомлення за ключем, довжина періоду якого ви­значалася найменшим загальним кратним періодів обертів шифрую­чих коліс, наприклад, чотирьом колесам з періодом обертів 13, 15, 17 і 19 відповідала довжина періоду ключа 62985. Відомі також ци­ліндр Базери (запропонований Зтьеном Базери в 1891 p.), крипто-

графічна машина (1917 p.) Жильбера Вернзма та роторна машина Едварда Хеберна (1917 p.), яку згодом назвали Енігмою. У 1942 році Аланом Тьюрингом була створена швидкодіюча ЕОМ під назвою " Колосе", спеціалізована для злому шифрів Енігми.

Завершує історію цього етапу криптографії математик Клод Ел-вуд Шеннон, який під час Другої світової війни, досліджуючи мате­матичними методами надійність шифрування, включив криптологію в загальггу теорію інформації.