Шифрування даних

Шифрування 

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

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

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

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

Одним з прикладів симетричного шифрування є алгоритм гамування. Він  заснований на випадкових числах. Нехай  маємо датчик псевдо-випадкових чисел, який працює за деяким визначеним алгоритмом. Часто використовують наступний алгоритм: Ti+1 = (a⋅Ti + b) mod c, де  Ti  – попереднє псевдо-випадкове  число,  Ti+1  – наступне  псевдо-випадкове  число,  а коефіцієнти a,  b,  c  сталі та  добре відомі.  Зазвичай  c = 2n,  де  n  – розрядність процесору, a mod 4 = 1, b – непарне. В цьому випадку послідовність псевдо-випадкових чисел має період c.

Процес  шифрування  визначається  наступним  чином.  Шифроване  повідомлення представляється  у  вигляді  послідовності  слів  S0, S1,…,  кожне  довжини  n,  які  додаються  за модулем 2 зі словами  послідовності T0, T1, …, тобто Ci = Si ⊕ Ti.

Послідовність T0, T1, … називається  гамою шифру. Процес  розшифрування  заключається  в тому,  щоби  ще  раз скласти шифровану послідовність з тією самою гамою шифру: Si = Ci ⊕ Ti. Ключем шифру є початкове значення  T0,  яке є секретним та має бути  відоме  тільки відправнику та  адресату  шифрованого повідомлення.  Якщо  період  послідовності псевдо-випадкових  чисел достатньо великий,  щоби  гама  шифру була  довша повідомлення,  то дешифрувати повідомлення можна тільки підбором ключа. При збільшенні n експоненційно збільшується криптостійкість шифру. Описаний  метод має суттєвий  недолік.  Якщо  відома  хоча  б  частина  вихідного повідомлення, то все повідомлення може бути легко дешифроване. Дійсно, нехай відоме одне вихідне слово Si. Тоді: Ti = Ci ⊕ Si, і далі  вся права частина гами шифру визначається  за  вказаною формулою  датчика  псевдо-випадкових чисел.

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

Найважливішими параметрами  всіх алгоритмів симетричного шифрування є:

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

До переваг симетричної  системи можна віднести:

• порівняно  високу швидкість  (приблизно  на  3  порядки  вищу  ніж  у  асиметричних систем);
• простота реалізації (за рахунок більш простих операцій);
• менша необхідна довжина ключа для відповідної стійкості;

Але  є  також  суттєві  недоліки,  які  практично  призводять  до  того,  що  дана  система  майже не використовується на даний час:

• складність  керування  ключами  у  великій  мережі.  Це  означає  квадратичне збільшення  кількості  ключів,  які  необхідно  генерувати,  зберігати,  передавати  та знищувати у мережі. Для мережі з 10 абонентів потрібно 45 ключів, для 100 – вже 4950, для 1000 – 499500;
• складність  обміну  ключами. 

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

23.3. Асиметричні криптосистеми 

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

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

Розглянемо  один  з  найвідоміших  та  найбільш  поширених  алгоритмів  –  RSA.  Цей алгоритм,  зокрема,  використовується  для  передачі  даних  захищеними  каналами  зв'язку мережі  Інтернет  –  HTTPS,  SSH. 

Інший  відомий  алгоритм,  який  був  першим  з  алгоритмів асиметричного шифрування – алгоритм Діффі-Хелмана (DH).

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

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

1. Обрати два випадкових простих числа p та q заданого розміру (наприклад 1024 біт).
2. Обчислити n = pq, яке називається модулем.
3. Обчислити ϕ(n) = (p–1)(q–1).
4. Обрати ціле число e (1 ≤ e ≤ ϕ(n) ), взаємно просте з ϕ(n). Зазвичай у якості e беруть прості числа, які містять невелику кількість одиничних бітів у двійковому записі (наприклад 17, 257, 65537). Число e  називається відкритою експонентою.  Занадто малі  значення  e  потенційно можуть послабити криптостійкість шифру.
5. Обчислити число d, яке є мультиплікативно оберненим до числа e за модулем ϕ(n), тобто число, яке задовольняє умові: de = 1 mod (ϕ(n))  Число d називається секретною експонентою.  Пара  P = (e, n)  публікується  в якості  відкритого  ключа RSA.  Пара  S = (d, n)  відіграє роль закритого (приватного) ключа RSA. Повідомлення мають бути менші за число n. Якщо повідомлення більше за n, то його б'ють на частини. Процес обміну повідомленнями від сторони В стороні А полягає у таких кроках: сторона А генерує за вказаним алгоритмом пару ключів – P = (e, n) та S = (d, n) – і відправляє відкритим каналом стороні В свій відкритий ключ; сторона В шифрує повідомлення М за допомогою ключа P = (e, n): C = Me mod n та відправляє його стороні А; сторона А приймає зашифроване повідомлення  C  та  розшифровує його  своїм закритим ключем S = (d, n): M´ = Cd mod n.

Шифрування  з  відкритим  ключем  є  коректним,  тобто M = M´. Розглянемо  приклад  генерації  ключів  та  шифрування/розшифрування  повідомлень методом RSA. 1.  p = 3, q = 11. 2.  n = pq = 33; 3.  ϕ(n) = (p–1)(q–1) = 20; 4.  e = 7 5.  d = 3: de = 3·7 mod 20 = 21 mod 20 = 1. Таким чином, відкритий ключ P = (7, 33), закритий – S = (3, 33). Нехай повідомлення  складається з трьох чисел:  M1 = 3,  M2 = 1,  M3 = 2.  Відповідні шифри, отримані за допомогою ключа (7, 33): C1 = 37 mod 33 = 2187 mod 33 = 9; C2 = 17mod 33 = 1 mod 33 = 1; C3 = 27 mod 33 = 128 mod 33 = 29. Перевіримо розшифрування закодованих повідомлень закритим ключем (3, 33). M'1 = 93mod 33 = 729 mod 33 = 3; M'2 = 13 mod 33 = 1 mod 33 = 1; M'3 = 293mod 33 = 24389 mod 33 = 2.

Розглянемо переваги та недоліки асиметричної криптосистеми. До переваг  можна віднести:

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

Недоліки:

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

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

Так, спочатку, коли А відправляє В свій відкритий ключ PA, сторона  С може перехопити цей ключ  та надіслати до В власний ключ PC. Тоді В буде  кодувати  повідомлення  за  допомогою  неправильного  ключа  PC.  Перехопивши  ці повідомлення,  С  зможе  їх  розкодувати  своїм  приватним  ключем,  а  замість  оригінального повідомлення направити  до А якесь  інше некоректне повідомлення, закодоване вже ключем PA. Описаний тип  атаки має назву «men-in-the-middle».

  Також  асиметрична  система  з  відкритим  ключем  використовується  у  системах цифрових  підписів.  Цей  процес  ґрунтується  на  властивості  комутативності  операцій шифрування та розшифрування: M = (Me)d mod n = Med mod n = Mde mod n = (Md)e mod n = M. Нехай сторона А відправляє стороні В повідомлення М. Для того, щоб підтвердити, що повідомлення дійсно відправлено від А, ця сторона супроводжує його підписом C = Md mod n, таким чином надсилаючи  до  В пару  (M,  C).  Сторона В,  отримавши це  повідомлення  з підписом,  кодує повідомлення  М відкритим ключем  PA:  C' = Me mod n.  Якщо  С = С',  то повідомлення М дійсно прийшло від сторони А неушкодженим.  Інакше, повідомлення було пошкоджено або замінено третьою стороною.

5.5 Коди з виявленням  і виправленням помилок

До найбільш поширених  кодів з виявленням та виправленням помилок відносять код Хемінга, циклічні та рекурентні коди. Розглянемо їх більш детально.

5.5.1 Код Хемінга

Код Хемінга відноситься до систематичних кодів, в яких з п символів, які утворюють комбінацію, n₀ символів є інформаційними, а останні k = п - п₀ с надлишковими (контрольними), призначеними для перевірки (контрольні символи у вcix комбінаціях займають однакові позиції). Коди Xeмінга дозволяють виправити вci одиничні помилки (при кодовій відстані d=3) i визначити вci подвійні помилки (при d=4), але не виправляти їх.

Зв'язок між кількістю  інформаційних та контрольних символів в коді Хемінга знаходять на основі таких міркувань. При передачі комбінації по каналу з шумами може бути спотворений довільний з п символів коду, або комбінація може бути передана без спотворень. Таким чином може бути п + 1 вapiaнтів спотворення (включаючи передачу без спотворення). Використовуючи контрольні символи, необхідно перевірити вci п+1 варіантів. За допомогою контрольних символів k можна описати 2k подій. Для цього повинна бути використана умова:

.

В таблиці 5.3 подана залежність між k i n₀, яка отримана з цієї невірності, де k - число контрольних символів в коді Хемінга, n₀ - інформаційних символів.

Таблиця 5.3 – Розміщення контрольних символів в комбінаціях  коду Хемінга

В коді Хемінга контрольні символи розташовують на місцях, кратних степеню числа 2, тобто на позиціях 1, 2, 4, 8 i т. п. Інформаційні символи розташовують на місцях, що залишилися. Наприклад, для семиелементної закодованої комбінації можна записати

.

Символи коду Хемінга, які обведені прямокутниками, є контрольними, останні – інформаційні, де а₃ – старший (четвертий) розряд вихідної кодової комбінації двійкового коду, який необхідно кодувати, а₇ – молодший (перший) розряд. Після розташування на відповідних місцях кодової комбінації контрольних i інформаційних символів в коді Хемінга складають спеціальні перевірні рівняння, які використовують для визначення наявності спотворень i їx виправлення. 3 перевірних рівнянь i отримують контрольні символи при кодуванні вихідної кодової комбінації двійкового коду. Для визначення контрольних символів необхідно використати такий алгоритм.