Вступ до криптології

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

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

Чому проблема використання криптографічних методів в інформаційних системах стала в даний момент особливо актуальною?

З одного боку, розширилося використання комп'ютерних мереж, зокрема глобальної мережі Internet, по яких передаються великі обсяги інформації державного, військового, комерційного і приватного характеру, що не допускає можливість доступу до неї сторонніх осіб. З іншого боку, поява потужних комп'ютерів, технологій мережних і нейронних обчислень уможливило дискредитацію криптографічних систем, для яких ще недавно розкриття вважалося практично неможливим.

Проблемою захисту інформації шляхом її перетворення займається криптологія (kryptos – таємний, logos – наука). Криптологія розділяється на два напрямки – криптографію і криптоаналіз. Мети цих напрямків прямо протилежні.

Криптографія займається пошуком і дослідженням математичних методів перетворення інформації. Сфера ж інтересів криптоаналізу – дослідження можливості розшифровування інформації без знання ключів.

Криптографія– це сукупність методів перетворення даних, спрямованих на те, щоб зробити ці дані марними для супротивника. Такі перетворення дозволяють вирішити дві головні проблеми захисту даних: проблему конфіденційності(шляхом позбавлення супротивника можливості витягти інформацію з каналу зв'язку) і проблему цілісності(шляхом позбавлення супротивника можливості змінити повідомлення так, щоб змінився його зміст або ввести помилкову інформацію в канал зв'язку).

Проблеми конфіденційності і цілісності інформації тісно зв'язані між собою, тому методи рішення однієї з них часто застосовні для рішення обох.

З основних напрямків використання криптографічних методів відзначимо передачу інформації каналами зв'язку (наприклад, електронна пошта), встановлення дійсності переданих повідомлень, збереження інформації (документів, баз даних) на носіях у зашифрованому виді.

Сучасна криптографія містить у собі чотири великих розділи:

1. Симетричні криптосистемы.

2. Криптосистемы з відкритим ключем.

3. Системи електронного підпису.

4. Керування ключами.

Однією з найважливішіх характеристик криптосистем є їх криптостійкість. Криптостійкістю називається характеристика шифру, що визначає його стійкість до дешифрування без знання ключа (тобто криптоаналізу). Є декілька показників криптостійкості, серед яких:

* кількість усіх можливих ключів;

* середній час, необхідний для криптоаналізу.

Для сучасних криптографічних систем захисту інформації сформульовані наступні загальноприйняті вимоги:

· зашифроване повідомлення повинне піддаватися читанню тільки при наявності ключа;

· число операцій, необхідних для визначення використаного ключа шифрування по фрагменту шифрованого повідомлення і відповідного йому відкритого тексту, повинно бути не менше загального числа можливих ключів;

· число операцій, необхідних для розшифровування інформації шляхом перебору всіляких ключів повинно мати строгу нижню оцінку і виходити за межі можливостей сучасних комп'ютерів (з урахуванням можливості використання мережних обчислень);

· знання алгоритму шифрування не повинно впливати на надійність захисту;

· незначна зміна ключа повинна приводити до істотної зміни виду зашифрованого повідомлення навіть при використанні того самого ключа;

· структурні елементи алгоритму шифрування повинні бути незмінними;

· додаткові біти, що вводяться в повідомлення в процесі шифрування, повинні бути цілком і надійно сховані в шифрованому тексті;

· довжина шифрованого тексту повинна бути рівною довжині вихідного тексту;

· не повинно бути простих і легко встановлюваних залежностей між ключами, послідовно використовуваними в процесі шифрування;

· будь-який ключ з множини можливих повинен забезпечувати надійний захист інформації;

· алгоритм повинен допускати як програмну, так і апаратну реалізацію, при цьому зміна довжини ключа не повинна вести до якісного погіршення алгоритму шифрування.

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

Як інформацію, що підлягає шифруванню і дешифруванню, розглядають тексти, побудовані на деякому алфавіті.

Алфавіт– кінцева множина використовуваних для кодування інформації знаків. Текст– упорядкований набір з елементів алфавіту.

Шифрування– процес перетворення: вихідний текст, що носить також назву відкритого тексту, заміняється шифрованим текстом.

Дешифрування– зворотний шифруванню процес. На основі ключа шифрований текст перетворюється у вихідний. Ключ– інформація, яка необхідна для безперешкодного шифрування і дешифрування певним методом.

Як відкритий текст, так і зашифрований утворяться з букв, що входять до алфавіту. Прикладами алфавітів є кінцева множина усіх заголовних букв, кінцева множина усіх заголовних і малих літер і цифр і т.д. У загальному вигляді деякий алфавіт Σ довжини m можна представити так: å={a₀,a₁,...,a_m-1}.

Поєднуючи за певним правилом букви з алфавіту Σ, можна створити нові алфавіти:

· алфавіт Σ², що містить m² біграмм а₀а₀, a₀a₁, ..., a_m-1a_m-1;

· алфавіт Σ³, що містить m³ триграмм a₀a₀a₀, a₀a₀a₁,..., a_m-1a_rn-1a_m-1.

У загальному випадку, поєднуючи по n букв, одержуємо алфавіт Σ^r. утримуючий mⁿ n-грам.

Наприклад, англійський алфавіт å={A,B,C,D,...,X,Y,Z} обсягом m=26 букв дозволяє згенерувати за допомогою операції конкатенації алфавіт з 26²=676 биграмм АА, АВ, ..., ΧΖ, ΖΖ, алфавіт з 26³=17576 триграмм ААА, ААВ, ..., ZZZ і т.д.

При виконанні криптографічних перетворень корисно та зручно замінити букви алфавіту цілими числами 0,1,2,3,.... Це дозволяє спростити виконання необхідних алгебраїчних маніпуляцій. Наприклад, можна установити взаємно однозначну відповідність між російським алфавітом å_рос={A,Б,B,Г,Д,Е,...,Ю,Я} і множиною цілих å₃₂={0,1,2,3,...,31} між англійським алфавітом å_англ={A,B,C,D,...,X,Y,Z} і множиною цілих (див. табл. 5.1. і 5.2.). Надалі буде звичайно використовуватися алфавіт å_m={0,1,3,...,m-1}, що утримуює m «букв» (у вигляді чисел). Заміна букв традиційного алфавіту числами дозволяє більш чітко сформулювати основні концепції і прийоми криптографічних перетворень. У той же час у більшості ілюстрацій буде використовуватися алфавіт природної мови.

Таблиця 5.1. Відповідність між російським алфавітом і множиною цілих å₃₂={0,1,…,31).

Таблиця 5.2. Відповідність між англійським алфавітом і множиною цілих Z₂₆={0,1,…,25}.

Текст із n буквами з алфавіту å_m можна розглядати як n-грами x={x₀,x₁,x₂,...,x_n-1} де х_іÎå_m, 0£і<n для деякого цілого n=1,2,3,.... Через Z_mn будемо позначати множину n-грам, утворених з букв множини å_m. Криптографічне перетворення Ε являє собою сукупність перетворень

E={E⁽ⁿ⁾ : 1£n<¥}, E⁽ⁿ⁾ : Z_mn®Z_mn.

Перетворення Ε визначає, як кожна n-грама відкритого тексту xÎZ_mn заміняється n-грамою шифртексту y, тобто y=E⁽ⁿ⁾(x), причому x,yÎZ_mn; при цьому обов'язковим є вимога взаємної однозначності перетворення E⁽ⁿ⁾ на множині Z_mn. Криптографічна система може також трактуватися як сімейство криптографічних перетворень

E={E_k : kÎK},

члени якого індексуються чи позначаються символом k; параметр k є ключем. Простір К – це набір можливих значень ключа. Звичайно ключ являє собою послідовний ряд букв і алфавіту. Перетворення тексту визначається відповідним алгоритмом і значенням параметра k. Ефективність шифрування з метою захисту інформації залежить від збереження таємниці ключа і криптостійкості ключа.

Процеси шифрування і розшифрування здійснюються в рамках деякої криптосистеми. Узагальнена схема криптографічної системи, що забезпечує шифрування переданої інформації, показана на рис. 5.1. Відправникгенерує відкритий текствихідного повідомлення М, що повинне бути передане законному одержувачупо незахищеному каналі. За каналом стежить перехоплювачз метою перехопити і розкрити передане повідомлення. Для того, щоб перехоплювач не зміг довідатися зміст повідомлення М, відправник шифрує його за допомогою оборотного перетворення E_k і одержує шифртекст(або криптограму) C=E_k(М), що відправляє одержувачу.

Законний одержувач, прийнявши шифртекст C, розшифровує його за допомогою зворотного перетворення D_k=E_k^-1 і одержує вихідне повідомлення у виді відкритого тексту М:

D_k(C)=E_k^-1(E_k(M))=М.

k

М С М

Рис.5.2. Узагальнена схема криптосистеми

Криптосистема має різні варіанти реалізації: набір інструкцій, апаратні засоби, комплекс програм комп'ютера, що дозволяють зашифрувати відкритий текст і розшифрувати шифртекст різними способами, один із яких вибирається за допомогою конкретного ключа k.

Говорячи більш формально, криптографічна система – це однопараметричне сімейство (E_k) kÎK оборотних перетворень E_k : M®C, із простору М повідомлень відкритого тексту в простір C шифрованих текстів. Параметр k (ключ) вибирається з кінцевої множини К, називаного простором ключів.

Узагалі говорячи, перетворення шифрування може бути симетричним або асиметричним щодо перетворення розшифрування. Це важлива властивість функції перетворення визначає два класи криптосистем:

•симетричні (одноключові) криптосистеми;

•асиметричні (двохключові) криптосистеми (з відкритим ключем).

Фактично на рис. 5.1. показано схему дії симетричної криптосистеми.

Усе різноманіття існуючих криптографічних методів можна звести до наступних класів перетворень:

Шифрування перестановкоюполягає в тому, що символи тексту, що шифрується, переставляються за певним правилом у межах деякого блоку цього тексту. При достатній довжині блоку, у межах, якого здійснюється перестановка, і складному неповторюваному порядку перестановки можна досягти прийнятної для простих практичних додатків стійкості шифру. Використовується як правило в сполученні з іншими методами. Шифри перестановки є найпростішими і, імовірно, самими древніми шифрами.

З початку епохи Відродження (кінець XIV сторіччя) почала відроджуватися і криптографія. Поряд із традиційними застосуваннями криптографії в політику, дипломатії і військовій справі з'являються й інші задачі – захист інтелектуальної власності від переслідувань інквізиції або запозичень зловмисників. У розроблених шифрах перестановки того часу застосовуються таблиці, що шифрують, які, по суті, задають правила перестановки букв у повідомленні. Як ключ у таблицях, що шифрують, використовуються:

· розмір таблиці;

· слово або фраза, що задають перестановку;

· особливості структури таблиці.

Одним із самих примітивних табличних шифрів перестановки є проста перестановка, для якої ключем служить розмір таблиці. Наприклад, повідомлення ТЕРМІНАТОР ПРИБУВАЄ СЬОМОГО ОПІВНОЧІ записується в таблицю по черзі по стовпчиках. Результат заповнення таблиці з 5 рядків і 7 стовпчиках показаний на рис. 5.2.

Рис. 5.2. Заповнення таблиці з 5 рядків і 7 стовпчиків

Після заповнення таблиці текстом повідомлення по стовпчиках для формування шифртексту зчитують уміст таблиці по рядках. Останні дві клітини для зручності та цілісності тексту містять будь-які символи, наприклад, Х. Якщо шифртекст записувати групами по п'ять букв, виходить таке шифроване повідомлення: ТНПВО ООЕЕАР АМПЧР ТИЄОІ ІМОБС ГВХІР УЬОНХ. Природно, відправник і одержувач повідомлення повинні заздалегідь умовитися про загальний ключ у виді розміру таблиці та порядку запису – саме це є ключем шифрування. Зауважимо, що об'єднання букв шифртексту в 5-буквені групи не входить у ключ шифру і здійснюється тільки для зручності запису та читання тексту. При розшифруванні дії виконують у зворотному порядку.

Трохи більшу стійкість до розкриття має метод шифрування, називаний одиночною перестановкою за ключем. Цей метод відрізняється від попередніх тим, що стовпчики таблиці додатково переставляються за ключовим словом, фразі або набору чисел довжиною в рядок таблиці. Застосуємо як ключ, наприклад, слово ПЕЛІКАН, а текст повідомлення візьмемо з попереднього прикладу. На рис. 5.3. показані дві таблиці, заповнені текстом повідомлення і ключовим словом, при цьому ліва таблиця відповідає заповненню до перестановки, а права таблиця – заповненню після перестановки.

До перестановки Після перестановки

Рис. 5.3. Таблиці, заповнені ключовим словом і текстом повідомлення

У верхньому рядку лівої таблиці записано ключ, а номери під буквами ключа визначені відповідно до природного порядку відповідних букв ключа за алфавітом. Якби в ключі зустрілися однакові букви, вони теж б були пронумеровані. У правій таблиці стовпчики переставлені відповідно до упорядкованих номерів букв ключа. При зчитуванні вмісту правої таблиці по рядках і запису шифртексту групами по п'ять букв одержимо шифроване повідомлення: ОНВОП ОТПАА МРЧЕІ ТЄОИІ РВОСГ БХМНР ЬОУХІ.

Для забезпечення додаткової скритності можна повторно зашифрувати повідомлення, що вже пройшло шифрування. Такий метод шифрування називається подвійною перестановкою. У випадку подвійної перестановки стовпчиків та рядків таблиці перестановки визначаються окремо для стовпчиків і окремо для рядків. Спочатку в таблицю записується текст повідомлення, а потім по черзі переставляються стовпчики, а потім рядки. При розшифруванні порядок перестановок повинний бути зворотним. Приклад виконання шифрування методом подвійної перестановки показано на рис. 5.4. для тексту ПРИЛІТАЮ ВОСЬМОГО. Якщо зчитувати шифртекст із правої таблиці построчно блоками по чотири букви, то вийде наступне: ТЮАІ ООГМ РЛИП ОЬСВ.

Ключем до шифру подвійної перестановки служить послідовність номерів стовпців і номерів рядків вихідної таблиці (у нашому прикладі послідовності 4132 і 3142 відповідно). Такі ключі можна задавати і словами.

Вихідна таблиця Перестановка стовпців Перестановка рядків

Рис. 5.4. Приклад виконання шифрування методом подвійної перестановки

Число варіантів подвійної перестановки швидко зростає при збільшенні розміру таблиці:

· для таблиці 3x3 36 варіантів;

· для таблиці 4x4 576 варіантів;

· для таблиці 5x5 14400 варіантів.

Однак подвійна перестановка не відрізняється високою стійкістю і порівняно просто «зламується» при будь-якому розмірі таблиці шифрування.

У середні століття для шифрування перестановкою застосовувалися і магічні квадрати. Магічними квадратаминазивають квадратні таблиці з уписаними в їхні клітки послідовними натуральними числами, починаючи від 1, що дають у сумі по кожному стовпчику, кожному рядку і кожній діагоналі одне й те саме число.

Текст, що шифрується, вписували в магічні квадрати відповідно до нумерації їхніх кліток. Якщо потім виписати вміст такої таблиці по рядках, то вийде шифртекст, сформований завдяки перестановці букв вихідного повідомлення. У ті часи вважалося, що створені за допомогою магічних квадратів шифртексти охороняє не тільки ключ, але і магічна сила. Приклад магічного квадрата і його заповнення повідомленням ПРИЛІТАЮ ВОСЬМОГО показано на рис. 5.5.

Рис. 5.5. Приклад магічного квадрата 4x4 і його заповнення повідомленням ПРИЛІТАЮ ВОСЬМОГО

Шифртекст, одержуваний при зчитуванні вмісту правої таблиці по рядках, має цілком загадковий вид: ОИРМ ІОСЮ ВТАЬ ЛГОП.

Число магічних квадратів швидко зростає зі збільшенням розміру квадрата. Існує тільки один магічний квадрат розміром 3x3 (якщо не враховувати його повороти). Кількість магічних квадратів 4x4 складає вже 880, а кількість магічних квадратів 5x5 – близько 250000.

Магічні квадрати середніх і великих розмірів могли служити гарною базою для забезпечення нестатків шифрування того часу, оскільки практично нереально виконати вручну перебір усіх варіантів для такого шифру.

Шифрування заміною (підстановкою)полягає в тому, що символи тексту, що шифрується, заміняються символами того ж або якогось іншого алфавіту відповідно до заздалегідь обумовленої схеми заміни. Для забезпечення високої криптостійкості потрібно використання великих ключів. Часто шифри простої заміни називають шифрами одноалфавітної підстановки.

Шифр Цезаря є окремим випадком шифру простої заміни (одноалфавітної підстановки). Свою назву цей шифр одержав по імені римського імператора Гая Юлія Цезаря, що використовував цей шифр при переписці з Цицероном (близько 50 р. до н.е.).

При шифруванні вихідного тексту кожна буква замінялася на іншу букву того ж алфавіту за наступним правилом. Буква, що заміняє, визначалася шляхом зсуву за алфавітом від вихідної букви на k букв. При досягненні кінця алфавіту виконувався циклічний перехід до його початку. Цезар використовував шифр заміни при зсуві k=3. Такий шифр заміни можна задати таблицею підстановок, що містить відповідні пари букв відкритого тексту і шифртексту. Сукупність можливих підстановок для k=3 показана в табл. 5.3. Наприклад, послання Цезаря VENI VIDI VICI (у перекладі на українську означає ПРИЙШОВ ПОБАЧИВ ПЕРЕМІГ), надіслане його другу Амінтію після перемоги над понтійським царем Фарнаком, сином Мітридата, виглядало б у зашифрованому виді так: YHQL YLGL YLFL.

Таблиця 5.3. Одноалфавітні підстановки (k=3, m=26)

Система Цезаря являє собою одноалфавітну підстановку, що шифрує n-грами (x₀, x₁, x₂, ...,x_n-1) відкритого тексту в n-грами (у₀, y₁, y₂, ...,y_n-1) шифртексту відповідно до наступного правила

y_i=E_k(x_i), 0£i<n, E_k : j®(j+k) (mod n), 0£k<m,

де j-числовий код букви відкритого тексту; j+k – числовий код відповідної букви шифртекста.

На відміну від шифру Цезаря, дана система шифрування утворює сімейство одноалфавітних підстановок для обираних значень ключа k, причому 0<k<m.

Достоїнством системи шифрування Цезаря є простота шифрування і розшифрування. До недоліків системи Цезаря варто віднести наступні:

· підстановки, виконувані відповідно до системи Цезаря, не маскують частот появи різних букв вихідного відкритого тексту;

· зберігається алфавітний порядок у послідовності букв, що заміняють, при зміні значення k змінюються тільки початкові позиції такої послідовності;

· число можливих ключів k мале;

· шифр Цезаря легко розкривається на основі аналізу частот появи букв у шифртексті.

Криптоаналітична атака проти системи одноалфавітної заміни починається з підрахунку частот появи символів: визначається число появ кожної букви в шифртексті. Потім отриманий розподіл частот букв у шифртексті порівнюється з розподілом частот букв в алфавіті вихідних повідомлень, наприклад, в англійському. Буква з найвищою частотою появи в шифртексті заміняється на букву з найвищою частотою появи в англійській мові і т.д. Імовірність успішного розкриття системи шифрування підвищується зі збільшенням довжини шифртексту.

Проте, концепція, що закладена в систему шифрування Цезаря, виявилася досить плідної, про що свідчать її численні модифікації, наприклад, система шифрування Цезаря з ключовим словом.'

Система шифрування Цезаря з ключовим словом є теж одноалфавітною системою підстановки. Особливістю цієї системи є використання ключового слова для зсуву і зміни порядку символів в алфавіті підстановки.

Виберемо деяке число з інтервалу 0<k<25 і слово або коротку фразу як ключове слово. Бажано, щоб усі букви ключового слова були різними. Нехай обране слово DIPLOMAT як ключове і число k=5. Ключове слово записується під буквами алфавіту, починаючи з букви, числовий код якої збігається з обраним числом k:

Букви алфавіту підстановки, що залишилися, записуються після ключового слова за алфавітом:

Тепер маємо підстановку для кожної букви довільного повідомлення. Вихідне повідомлення SEND MORE MONEY шифрується як HZBY TGGZ TCBZS.

Слід зазначити, що вимога про розходження всіх букв ключового слова не є обов'язковою. Можна просто записати ключове слово (або фразу) без повторення однакових букв.

Безсумнівним достоїнством системи Цезаря з ключовим словом є те, що кількість можливих ключових слів практично невичерпне. Недоліком цієї системи є можливість злому шифртекста на основі аналізу частот появи букв.

При багаторазовому чергуванні простих перестановок і підстановок, керованих досить довгим секретним ключем, можна одержати дуже стійкий шифр із гарним розсіюванням і перемішуванням. Слід зазначити, що комбінації шифрів перестановок і шифрів заміни утворюють усе різноманіття застосовуваних на практиці сучасних симетричних шифрів.

Шифрування гамуваннямполягає в тому, що символи тексту, що шифрується, складаються із символами деякої випадкової послідовності, іменованою гамою шифру. Принцип шифрування гамуванням полягає в генерації гами шифру за допомогою датчика псевдовипадкових чисел і накладенні отриманої гами на відкриті дані оборотним чином (наприклад, використовуючи додавання за модулем 2).

Процес дешифрування даних зводиться до повторної генерації гами шифру при відомому ключі і накладенні такої гами на зашифровані дані.

Стійкість шифрування визначається в основному довжиною (періодом) неповторюваної частини гами шифру. Оскільки за допомогою ЕОМ можна генерувати практично нескінченну гаму шифру, то даний спосіб є одним з основних для шифрування інформації в автоматизованих системах.

Отриманий зашифрований текст є досить важким для розкриття в тому випадку, якщо гама шифру не містить повторюваних бітових послідовностей. По суті справи гама шифру повинна змінюватися випадковим чином для кожного слова, що шифрується. Фактично ж, якщо період гами перевищує довжину всього зашифрованого тексту і невідома ніяка частина вихідного тексту, то шифр можна розкрити тільки прямим перебором (пробій на ключ). Криптостійкість у цьому випадку визначається розміром ключа.

Метод гамування стає неспроможним, якщо зловмиснику стає відомий фрагмент вихідного тексту і відповідна йому шифрограма. Простим вирахуванням за модулем виходить відрізок тексту і по ньому відновлюється вся послідовність. Зловмисник може зробити це на основі здогадів про зміст вихідного тексту. Так, якщо більшість повідомлень, що надсилаються, починається зі слів «ЦІЛКОМ ТАЄМНО», то криптоаналіз усього тексту значно полегшується. Це варто враховувати при створенні реальних систем інформаційної безпеки.

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

Широко розповсюдженим також вважається шифрування аналітичним перетворенням, яке полягає в тому, що текст, що шифрується, перетвориться за деяким аналітичним правилом (формулою).

Наприклад, можна використовувати правило множення вектора на матрицю, причому множена матриця є ключем шифрування (тому її розмір і зміст повинні зберігатися в секреті), а символами множеного вектора послідовно служать символи тексту, який шифрується.

Однак як би ні були складні і надійні криптографічні системи – їх слабке місце при практичній реалізації – проблема розподілу ключів. Для того, щоб був можливий обмін конфіденційною інформацією між двома суб'єктами інформаційної системи, ключ повинен бути сгенерований одним з них, а потім якимось чином знову ж у конфіденційному порядку переданий іншому. Тобто у загальному випадку для передачі ключа знову ж потрібно використання якойсь криптосистеми.

Для вирішення цієї проблеми на основі результатів, отриманих класичною і сучасною алгеброю, були запропоновані системи з відкритим ключем (СВК) (синоніми – несиметричні, асиметричні, антисиметричні).

У СВК використовуються два ключі – відкритий і закритий, котрі математично зв'язані один з одним. Інформація шифрується за допомогою відкритого ключа, що доступний усім бажаючим, а розшифровується за допомогою закритого ключа, відомого тільки одержувачу повідомлення.

Схема симетричної криптосистеми (з одним секретним ключем) була показана на рис. 5.2. У ній використовуються однакові секретні ключі в блоці шифрування і блоці розшифрування.

Узагальнена схема асиметричної криптосистеми з двома різними ключами k₁ і k₂ показана на рис. 5.6. У цієї криптосистеми один із ключів є відкритим, а другий – секретним.

k₁ k₂

М С М

	ВІДПравник		Шифрування Ек(М)		Разшифрування Dк(С)		отримувач

Рис. 5.6. Узагальнена схема криптосистеми з відкритим ключем

У симетричній криптосистемі секретний ключ треба передавати відправникові й одержувачеві по захищеному каналі передачі ключів, наприклад такому, як кур'єрська служба. На рис. 5.2. цей канал показаний «екранованою» лінією. Існують різні способи розподілу секретних ключів, вони будуть розглянуті пізніше.

Суть асиметричної криптосистеми полягає в тому, що кожним адресатом генеруються два ключі, зв'язані між собою за певним правилом. Один ключ з'являється відкритим, а інший закритим. Відкритий ключ публікується і доступний кожному, хто бажає послати повідомлення адресату, тобто передається по незахищеному каналу. Секретний ключ зберігається в таємниці.

Вихідний текст шифрується відкритим ключем адресата і передається йому. Зашифрований текст у принципі не може бути розшифрований тим же відкритим ключем. Дешифрування повідомлення можливе тільки з використанням закритого ключа, що відомий тільки самому адресату.

Алгоритми шифрування з відкритим ключем одержали широке поширення в сучасних інформаційних системах. Так, алгоритм RSA став світовим стандартом де-факто для відкритих систем.

Слід зазначити, що алгоритми криптосистемы СВК можна використовувати в трьох призначеннях.

1. Як самостійні засоби захисту переданих і збережених даних.

2. Як засоби для розподілу ключів. Алгоритми СВК більш трудомісткі, чим традиційні криптосистеми. Тому часто на практиці раціонально за допомогою СВК розподіляти ключі, обсяги яких як інформації незначні. А потім за допомогою звичайних алгоритмів здійснювати обмін великими інформаційними потоками.

3. Засоби автентифікації користувачів.

Концепція асиметричних криптографічних систем з відкритим ключем заснована на застосуванні односпрямованих функцій. Неформально односпрямовану функцію можна визначити в такий спосіб. Нехай X і Y – деякі довільні множини. Функція f: X®Y є односпрямованою, якщо для всіх xÎX можна легко обчислити функцію y=f(x), де yÎY і в той же час для більшості yÎY досить складно одержати значення xÎX, таке, що f(x)=y (при цьому вважається, що існує, принаймні, одне таке значення х).

Основним критерієм віднесення функції f до класу односпрямованих функцій є відсутність ефективних алгоритмів зворотного перетворення Y®X.

Множину класів односпрямованих функцій і породжує вся розмаїтість систем з відкритим ключем. Однак не всяка необоротна функція годиться для використання в реальних інформаційних системах.

У самім означенні односпрямованості присутня невизначеність. Під односпрямованістю розуміється не теоретична необоротність, а практична неможливість обчислити зворотне значення, використовуючи сучасні обчислювальні засоби за доступний для огляду інтервал часу.

Тому, щоб гарантувати надійний захист інформації, до СВК пред'являються дві важливих і очевидних вимоги:

1. Перетворення вихідного тексту повинне бути необоротним і виключати його відновлення тільки на основі відкритого ключа.

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

Узагалі ж усі запропоновані сьогодні криптосистеми з відкритим ключем спираються на один з наступних типів необоротних (або односпрямованих) перетворень:

1. Розкладання великих цілих чисел на прості множники.

2. Обчислення логарифма в кінцевому полі.

3. Обчислення коренів алгебраїчних рівнянь.

Як перший приклад односпрямованої функції розглянемо цілочислене множіння. Пряма задача – обчислення добутку двох дуже великих цілих чисел Р и Q, тобто отримання значення N=P*Q є досить нескладною задачею для ЕОМ.

Зворотна ж задача – розкладання на множники великого цілого числа, тобто отримання дільників Р і Q великого цілого числа N=Р*Q, є практично нерозв'язною задачею при досить великих значеннях N. За сучасними оцінками теорії чисел при цілому N@2⁶⁶⁴ і Р@Q для розкладання числа N буде потрібно близько 10²³ операцій, тобто задача практично нерозв'язна на сучасних ЕОМ.

Наступний характерний приклад односпрямованої функції – це модульна експонента з фіксованою основою і модулем. Нехай А и N – цілі числа, такі, що 1£A<N. Визначимо множину 1£A<N.: Z_N={0,1,2,...,N-1}.

Тоді модульна експонента з основою А за модулем N являє собою функцію

f_AN : Z_N®Z_N,

f_AN(x)=A^x (mod N),

де х – ціле число, 1£х<N-1.

Існують ефективні алгоритми, що дозволяють досить швидко обчислити значення функції f_AN(x). Якщо y=A^x, то природно записати x=log_Aу. Тому задачу обертання функції f_AN(x) називають задачею обчислення дискретного логарифма або задачею дискретного логарифмування. Задача дискретного логарифмування формулюється в такий спосіб. Для відомих цілих A, N, y знайти ціле число х, таке що A^x mod N=y.

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

За сучасними оцінками теорії чисел при цілих числах А@2⁶⁶⁴ і N@2⁶⁶⁴ рішення задачі дискретного логарифмування (отримання показника ступеня х для відомого у) вимагає близько 10²⁶ операцій, тобто ця задача має в 10³ разів більшу обчислювальну складність, чим задача розкладання на множники. При збільшенні довжини чисел різниця в оцінках складності задач зростає.

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

Другим важливим класом функцій, використовуваних при побудові криптосистем з відкритим ключем, є так називані односпрямовані функції з «потайним ходом» (з лазівкою). Дамо неформальне визначення такої функції. Функція f: X®Y відноситься до класу односпрямованих функцій з «потайним ходом» у тому випадку, якщо вона є односпрямованою і, крім того, можливо ефективне обчислення зворотної функції, якщо відомо «потайний хід» (секретне число, рядок або інша інформація, що асоціюється з даною функцією).

Як приклад односпрямованої функції з «потайним ходом» можна указати використовувану в криптосистемі RSA модульну експоненту з фіксованими модулем і показником ступеня. Перемінна підстановка модульної експоненти використовується для вказівки числового значення повідомлення М або криптограми С.

Незважаючи на досить велике число різних СВК, найбільш популярний – криптосистема RSA, яка розроблена в 1977 році і отримала назву на честь її творців: Рона Ривеста, Ади Шамира і Леонарда Адлемана. Алгоритм RSA став першим повноцінним алгоритмом з відкритим ключем, що може працювати як у режимі шифрування даних, так і в режимі електронного цифрового підпису.

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

Надійність алгоритму ґрунтується на труднощах факторизації великих чисел і обчислення дискретних логарифмів.

У криптосистемі RSA відкритий ключ k_e, секретний ключ k_d, повідомлення Μ і криптограма С належать множині цілих чисел Ζ_Ν={0,1,2,...,N-1}, де N – модуль: N=P*Q.

Тут Ρ і Q – випадкові великі прості числа. Для забезпечення максимальної безпеки вибирають Ρ і Q рівної довжини і зберігають у секреті.

Множина Ζ_Ν з операціями додавання і множення по модулю N утворить арифметику за модулем N.

Контрольні запитання

1. Що таке криптологія? Які напрямки вона має?

2. Основні вимоги до сучасних криптосистем.

3. Наведіть узагальнену схему криптосистеми.

4. Що таке шифрування перестановкою?

5. Що таке шифрування підстановкою?

6. Наведіть узагальнену схему криптосистеми з відкритим ключем.