Баричев З Криптографія без секретів

Від автора

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

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

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

Масу корисної інформації можна знайти на сервері ftp.rsa.com. У faq5.doc Ви якщо і не знайдете відповідь на будь-яке питання по криптографії, то спостерігається велика кількість посилань на інші джерела.

Автор буде вдячний за будь-які зауваження і питання, які найпростіше направити за адресою: bar@glasnet.ru

Баричев Сергій

Введення

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

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

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

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

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

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

Проблемою захисту інформації шляхом її перетворення займається кріптологія (kr y p to s - таємний, lo g o s - наука). Криптологія поділяється на два напрямки - криптографію і криптоаналіз. Мета цих напрямків прямо протилежні.

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

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

У цій книзі основна увага буде приділена криптографічним методам.

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

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

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

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

4. Управління ключами.

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

Термінологія

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

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

Алфавіт - кінцеве безліч використовуваних для кодування інформації знаків.

Текст - упорядкований набір з елементів алфавіту.

В якості прикладів алфавітів, які в сучасних ІС можна навести такі:

• алфавіт Z ₃₃ - 32 літери російського алфавіту і пробіл;

• алфавіт Z ₂₅₆ - символи, що входять в стандартні коди ASCII і КОІ-8;

• бінарний алфавіт - Z ₂ = {0,1};

• восьмеричний алфавіт або шістнадцятковий алфавіт;

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

Криптографічна система

Дешифрування - зворотний шифруванню процес. На основі ключа шифрований текст перетвориться у вихідний.

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

Криптографічна система являє собою сімейство T перетворень відкритого тексту. Члени цього сімейства індексуються, чи позначаються символом k; параметр k є ключем. Простір ключів K - це набір можливих значень ключа. Зазвичай ключ являє собою послідовний ряд букв алфавіту.

Криптосистеми поділяються на симетричні й з відкритим ключем.

У симетричних криптосистемах і для шифрування, і для дешифрування використовується один і той самий ключ.

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

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

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

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

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

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

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

Вимоги до криптосистемам

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Симетричні

криптосистеми

Моно-і Многоалфавитная підстановки.

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

Перестановки.

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

Гаммирование.

Цей метод полягає в накладенні на вихідний текст деякої псевдовипадковою послідовності, що генерується на основі ключа.

Блокові шифри.

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

Перестановки

Перестановкою  набору цілих чисел (0,1 ,..., N-1) називається його переупорядоченіе. Для того щоб показати, що ціле i переміщено з позиції i в позицію  (i), де 0  (i) <n, будемо використовувати запис

 = ( (0),  (1 ),...,  (N-1)).

Число перестановок з (0,1 ,..., N-1) одно n! = 1 * 2 *...*( N-1) * N. Введемо позначення  для взаємно-однозначного відображення (гомоморфізму) набору S = {s _0, s _1, ..., s _N-1}, що складається з n елементів, на себе.

: S  S

: s _i  s _{ (i),} 0  i <n

Будемо говорити, що в цьому сенсі  є перестановкою елементів S. І, навпаки, автоморфізм S відповідає перестановці цілих чисел (0,1,2, .., n -1).

Криптографічним перетворенням T для алфавіту Z _m називається послідовність автоморфізмів: T = {T ^(n): 1  n <}

T ^(n): Z _{m, n}  Z _{m, n,} 1  n <

Кожне T ⁽ⁿ⁾ є, таким чином, перестановкою n-грам з Z _{m, n.}

Оскільки T ⁽ⁱ⁾ і T ^(j) можуть бути визначені незалежно при i  j, число криптографічних перетворень вихідного тексту розмірності n дорівнює (m ^{n)! 2} . Воно зростає непропорційно при збільшенні m і n: так, при m = 33 та n = 2 число різних криптографічних перетворень одно 1089!. Звідси випливає, що потенційно існує велика кількість відображень вихідного тексту в шифрований.

Практична реалізація криптографічних систем вимагає, щоб перетворення {T _k: k  K} були визначені алгоритмами, залежними від відносно невеликого числа параметрів (ключів).

Системи підстановок

Визначення Підстановкою  на алфавіті Z _m називається автоморфізм Z _m, при якому літери початкового тексту t заміщені літерами шифрованого тексту  (t):

Z _m  Z _m; : t   (t).

Набір всіх підстановок називається симетричною групою Z _m і буде надалі позначатися як SYM (Z _m).

Затвердження SYM (Z _m) c операцією твору є групою, тобто операцією, володіє наступними властивостями:

1. Замкнутість: твір підстановок  ₁  ₂ є підстановкою:

: t   ₁ ( ₂ (t)).

2. Асоціативність: результат твори  ₁  ₂  ₃ не залежить від порядку розстановки дужок:

( ₁  ₂₎  ₃ =  ₁ ( ₂  ₃₎

3. Існування нейтрального елемента: постановка i, обумовлена ​​як i (t) = t, 0  t m) за операції множення: i  =  i для    SYM (Z _m).

4. Існування зворотного: для будь-якої підстановки  існує єдина зворотна підстановка  ^-1, що задовольняє умові

    ¹ =    ¹  = i.

Число можливих підстановок у симетричній групі Z _m називається порядком SYM (Z _m) і одно m! .

Визначення. Ключем підстановки k для Z _m називається послідовність елементів симетричної групи Z _m:

k = (p _0, p ₁ ,..., p _{n -1} ,...), p _n  SYM (Z _m), 0  n <

Підстановка, обумовлена ​​ключем k, є криптографічним перетворенням T _k, за допомогою якого здійснюється перетворення n-грами вихідного тексту (x _0, x _1, .., x _n-1) у n-граму шифрованого тексту (y _0, y _1, ..., y _n-1):

y _i = p (x _i), 0  i

де n - довільне (n = 1,2 ,..). T _k називається моноалфавитной підстановкою, якщо p незмінно при будь-якому i, i = 0,1 ,..., в іншому випадку T _k називається Многоалфавитная підстановкою.

Примітка. До найбільш істотних особливостей підстановки T _k належать такі:

1. Вихідний текст шифрується посимвольно. Шифрування n-грами (x _0, x _1, .., x _n-1) і її префікса (x _0, x _1, .., x _{s -1)} зв'язані співвідношеннями

T _k (x _0, x _1, .., x _n-1) = (y _0, y ₁ ,..., y _n-1)

T _k (x _0, x _1, .., x _{s -1)} = (y _0, y ₁ ,..., y _{s -1)}

2. Буква шифрованого тексту y _i є функцією тільки i-й компоненти ключа p _i і i-й літери початкового тексту x _i.

Підстановка Цезаря

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

Визначення. Підмножина C _m = {C _k: 0  k m), що містить m підстановок

C _k: j  (j + k) (mod m), 0  k <m,

називається підстановкою Цезаря.

Множення комутативними, C _k C _j = C _j C _k = C _{j + k,} C ₀ - ідентична підстановка, а зворотної до C _до є C _k ^-1 = C _m-k, де 0 <k 3.

Підстановка визначається за таблицею заміщення, що містить пари відповідних букв "вихідний текст - шифрований текст". Для C ₃ підстановки наведені у Табл. 1. Стрілка () означає, що літера в повідомленні (ліворуч) шифрується за допомогою C ₃ в букву шифрованого тексту (праворуч).

Визначення. Системою Цезаря називається моноалфавитной підстановка, перетворююча n-граму вихідного тексту (x _0, x _1, .., x _n-1) у n граму шифрованого тексту (y _0, y ₁ ,..., y _n-1) відповідно до правила

y _i = C _k (x _i), 0  i

Наприклад, ВИШЛІТЕ_НОВИЕ_УКАЗАНІЯ допомогою підстановки C ₃ перетвориться в еюиолхіврсеюівцнгкгрлб.

Таблиця 1.

При своїй простоті система легко вразлива. Якщо зловмисник має

1) шифрований і відповідний вихідний текст або

2) шифрований текст обраного зловмисником вихідного тексту,

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

Більш ефективні узагальнення підстановки Цезаря - шифр Хілла і шифр Плейфера. Вони засновані на підстановці не окремих символів, а 2-грам (шифр Плейфера) або n-грам ³ (шифр Хілла). При більш високій криптостійкості вони значно складніше для реалізації і вимагають досить великої кількості ключової інформації.

Многоалфавитная системи. Системи одноразового використання.

Слабка крипостійкість моноалфавитной підстановок долається із застосуванням підстановок Многоалфавитная.

Многоалфавитная підстановка визначається ключем  = ( _1,
 _2, ...), містить не менше двох різних підстановок. На початку розглянемо Многоалфавитная системи підстановок з нульовим початковим зміщенням.

Нехай {K _i: 0  i m

P кл {(K _0, K _1, ..., K _n-1) = (k _0, k _1, ..., k _n-1)} = (1 / m) ⁿ

Система одноразового використання перетворює вихідний текст

X = (X _0, x _1, ..., x _n-1)

в шифрований текст

Y = (Y _0, y _1, ..., y _n-1)

за допомогою підстановки Цезаря

Y _i = C _{K i} (x _i) = (K _i + X _i) (mod m) i = 0 ... n-1 (1)

Для такої системи підстановки використовують також термін "одноразова стрічка" і "одноразовий блокнот". Простір ключів До системи одноразової підстановки є вектором рангів (K _0, K _1, ..., K _n-1) і містить m ⁿ точок.

Розглянемо невеликий приклад шифрування з нескінченним ключем. Як ключ приймемо текст

"БЕСКОНЕЧНИЙ_КЛЮЧ ....".

Зашифруємо з його допомогою текст "ШІФР_НЕРАСКРИВАЕМ". Шифрування оформимо в таблицю:

Оригінальний текст неможливо відновити без ключа.

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

Чому ж ці системи незастосовні для забезпечення секретності при обробці інформації? Відповідь проста - вони непрактичні, оскільки вимагають незалежного вибору значення ключа для кожної літери початкового тексту. Хоча така вимога може бути і не занадто важким при передачі по прямому кабелю Москва - Нью-Йорк, але для інформаційних воно непосильно, оскільки там доведеться шифрувати багато мільйонів знаків.

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

Системи шифрування Вижинера

Почнемо з кінцевої послідовності ключа

k = (k _0, k ₁ ,..., k _n),

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

k = (k _0, k ₁ ,..., k _n), k _j = k _{(j mod r,} 0  j <.

Наприклад, при r =  і ключі користувача 15 8 2 10 11 4 18 робочий ключ буде періодичною послідовністю:

15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ...

Визначення. Підстановка Вижинера VI G _k визначається як

VI G _k: (x _0, x _1, ..., x _n-1)  (y _0, y _1, ..., y _n-1) = (x ₀ + k, x ₁ + k,. .., x _n-1 + k).

Таким чином:

1) вихідний текст x ділиться на r фрагментів

x _i = (x _i, x _{i + r,} ..., x _{i + r (n-1)),} 0  i <r;

2) i-й фрагмент вихідного тексту x _i шифрується за допомогою підстановки Цезаря C _k:

(X _i, x _{i + r,} ..., x _{i + r (n-1))}  (y _i, y _{i + r,} ..., y _{i + r (n-1)),}

Варіант системи підстановок Вижинера при m = 2 називається системою Вернама (1917 р).

У той час ключ k = (k _0, k ₁ ,..., k _к-1) записувався на паперовій стрічці. Кожна літера в повідомленні в алфавіті, розширеному деякими додатковими знаками, спочатку переводилася з використанням коду Бодо в пятібітовий символ. До початкового тексту Бодо додавався ключ (по модулю 2). Старовинний телетайп фірми AT & T зі зчитувальним пристроєм Вернама та обладнанням для шифрування, використовувався корпусом зв'язку армії США.

Дуже поширена погана з точки зору секретності практика використовувати слово або фразу в якості ключа для того, щоб k = (k _0, k ₁ ,..., k _к-1) було легко запам'ятати. У ІВ для забезпечення безпеки інформації це неприпустимо. Для отримання ключів повинні використовуватися програмні або апаратні засоби випадкової генерації ключів.

Приклад. Перетворення тексту за допомогою підстановки Вижинера (r = 4)

Оригінальний текст (ІТ1):

НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ

Ключ: КЛЮЧ

Розіб'ємо вихідний текст на блоки по 4 символу:

НЕ_С Леду ЕТ_В ИБІР АТЬ_ НЕСЛИ УЧАЙ НИЙ_ КЛЮЧ

і накладемо на них ключ (використовуючи таблицю Вижинера):

H + К = Ч, Е + Л = Р і т.д.

Отримуємо зашифрований (ЗТ1) текст:

ЧРЕЗ ХРБЙ ПЕЕЩ ДМЕЖ КЕЩЦ ЧРОБ ЕБЮ_ ЧЕЖЦ ФЦИН

Можна висунути та узагальнену систему Вижинера. ЇЇ можна сформулювати не тільки за допомогою підстановки Цезаря.

Нехай x - підмножина симетричної групи SYM (Z _m).

Визначення. R-Многоалфавитная ключ шифрування є r-набір  = ( _0,  _1, ...,  _{r -1)} з елементами в x.

Узагальнена система Вижинера перетворює вихідний текст (x _0, x ₁ ,..., x _n-1) у шифрований текст (y _0, y ₁ ,..., y _n-1) за допомогою ключа  = ( _0,  _1, ...,  _{r -1)} за правилом

VI G _k: (x _0, x ₁ ,..., x _n-1)  (y _0, y ₁ ,..., y _n-1) = ( ₀ (х _0),  ₁ (х _1), ...,  _n-1 (x _n-1)),

де використовується умова  _i =  _{i mod r.}

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

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

Гаммирование

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

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

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

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

Метод гамування стає безсилим, якщо зловмисникові стає відомий фрагмент вихідного тексту і відповідна йому шифрограма. Простим вирахуванням за модулем виходить відрізок ПСП і по ньому відновлюється вся послідовність. Зловмисники може зробити це на основі припущень про зміст вихідного тексту. Так, якщо більшість посилаються повідомлень починається зі слів "СОВ.СЕКРЕТНО", то криптоаналіз всього тексту значно полегшується. Це слід враховувати при створенні реальних систем інформаційної безпеки.

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

Датчики ПСЧ

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

Конгруентні датчики

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

Одним із добрих конгруентних генераторів є лінійний конгруентний датчик ПСЧ. Він виробляє послідовності псевдовипадкових чисел T (i), описувані співвідношенням

T (i +1) = (A * T (i) + C) mod m,

де А і С - константи, Т (0) - вихідна величина, вибрана в якості породжує числа. Очевидно, що ці три величини і утворюють ключ.

Такий датчик ПСЧ генерує псевдовипадкові числа з певним періодом повторення, що залежать від вибраних значень А і С. Значення m зазвичай встановлюється рівним 2n, де n - довжина машинного слова в бітах. Датчик має максимальний період М до того, як генерується послідовність почне повторюватися. З причини, зазначеної раніше, необхідно вибирати числа А і С такі, щоб період М був максимальним. Як показано Д. Кнутом, лінійний конгруентний датчик ПСЧ має максимальну довжину М тоді і тільки тоді, коли С - непарне, і А mod 4 = 1.

Для шифрування даних за допомогою датчика ПСЧ може бути обраний ключ будь-якого розміру. Наприклад, нехай ключ складається з набору чисел x (j) розмірністю b, де j = 1, 2, ..., n. Тоді створювану гаму шифру G можна представити як об'єднання непересічних множин H (j).

Датчики М-послідовностей ⁵

М-послідовності також популярні, завдяки відносній легкості їх реалізації.

М-послідовності є лінійними рекурентні послідовності максимального періоду, що формуються k-розрядними генераторами на основі регістрів зсуву. На кожному такті надійшов біт зрушує k попередніх і до нього додається їх сума по модулю 2. Витісняється біт додається до гами.

Строго це можна представити у вигляді наступних відносин:

r _1: = r ₀ r _2: = r ₁ ... r _k-1: = r _k-2

r _0: = a ₀ r ₁  a ₁ r ₂  ...  a _k-2 r _k-1

Г _i: = r _k-

Тут r ₀ r ₁ ... r _k-1 - K однобітних регістрів, a ₀ a ₁ ... a _k-1 - коефіцієнти неприводимого двійкового полінома ступеня k-1. Г _i - i-е значення вихідної гами.

Період М-послідовності виходячи з її властивостей дорівнює 2 ^k -1.

Іншою важливою властивістю М-послідовності є обсяг ансамблю, тобто кількість різних М-послідовностей для заданого k. Ця характеристика наведена в таблиці:

k	Обсяг ансамблю
5	6
6	8
7	18
8	16
9	48
10	60
16	2048

Очевидно, що такі обсяги ансамблів послідовності неприйнятні.

Тому на практиці часто використовують послідовності Голда, що утворюються підсумовуванням декількох М-послідовностей. Обсяг ансамблів цих послідовностей на кілька порядків перевершують обсяги ансамблів породжують М-послідовностей. Так при k = 10 ансамбль збільшується від 1023 (М-послідовності) до 388000.

Також перспективними представляються нелінійні датчики ПСП (наприклад зсувні регістри з елементом І в колі зворотного зв'язку), однак їх властивості ще недостатньо вивчені.

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

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

Стандарт шифрування даних ГОСТ 28147-89 ^червня

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

Більш ефективним є вітчизняний стандарт шифрування даних.

Він рекомендований до використання для захисту будь-яких даних, представлених у вигляді двійкового коду, хоча не виключаються й інші методи шифрування. Даний стандарт формувався з урахуванням світового досвіду, і зокрема, були прийняті до уваги недоліки і нереалізовані можливості алгоритму DES, тому використання стандарту ГОСТ переважно. Алгоритм досить складний і нижче буде описана в основному його концепція.

Введемо асоціативну операцію конкатенації, використовуючи для неї мультипликативную запис. Крім того будемо використовувати наступні операції додавання:

• A  B - побітове додавання за модулем 2;

• A [+] B - додавання за модулем 2 ^32;

• A {+} B - додавання за модулем 2 ³² -1;.

Алгоритм криптографічного перетворення передбачає кілька режимів роботи. У всіх режимах використовується ключ W довжиною 256 біт, представлений у вигляді восьми 32-розрядних чисел x (i).

W = X (7) X (6) X (5) X (4) X (3) X (2) X (1) X (0)

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

Найпростіший з можливих режимів - заміна.

Нехай відкриті блоки розбиті на блоки по 64 біт у кожному, які позначимо як T (j).

Чергова послідовність біт T (j) розділяється на дві послідовності B (0) і A (0) по 32 біта (правий і лівий блоки). Далі виконується ітеративний процес шифрування описуваний наступними формулами, вид який залежить від: i:

• Для i = 1, 2, ..., 24, j = (i-1) mod 8;

A (i) = f (A (i-1) [+] x (j))  B (i-1)

B (i) = A (i-1)

• Для i = 25, 26, ..., 31, j = 32-i;

A (i) = f (A (i-1) [+] x (j))  B (i-1)

B (i) = A (i-1)

• Для i = 32

A (32) = A (31)

B (32) = f (A (31) [+] x (0))  B (31).

Тут i позначає номер ітерації. Функція f - функція шифрування.

Функція шифрування включає дві операції над 32-розрядним аргументом.

Перша операція є підстановкою K. Блок підстановки До складається з 8 вузлів заміни К (1) ... До (8) з пам'яттю 64 біта кожен. Вступник на блок підстановки 32-розрядний вектор розбивається на 8 послідовно що йдуть 4-розрядних вектора, кожен з який перетвориться в 4-розрядний вектор відповідним вузлом заміни, які представляють з себе таблицю з 16 цілих чисел у діапазоні 0 ... 15. Вхідний вектор визначає адресу рядки в таблиці, число з якої є вихідним вектором. Потім 4-розрядні вектори послідовно об'єднуються в 32-розрядний вихідний.

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

Т = А (32) У (32).

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

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

Інший режим шифрування називається режимом гамування.

Відкриті дані, розбиті на 64-розрядні блоки T (i) (i = 1,2 ,..., m) (M визначається обсягом шифрованих даних), зашифровуються в режимі гамування шляхом порозрядного складання по модулю 2 з гамою шифру Г _ш, яка виробляється блоками по 64 біт, тобто

Г _ш = (Г (1), Г (2 ),...., Г (m)).

Рівняння шифрування даних в режимі гамування може бути представлене в наступному вигляді:

Ш (i) = A (Y (i-1)  C2, Z (i-1)) {+} C (1)  T (i) = Г (i)  T (i)

У цьому рівнянні Ш (i) позначає 64-розрядний блок зашифрованого тексту, А - функцію шифрування в режимі простої заміни (аргументами цієї функції є два 32-розрядних числа). С1 і С2 - константи, задані в ГОСТ 28147-89. Величини y (i) і Z (i) визначаються ітераційно по мірі формування гами наступним чином:

(Y (0), Z (0)) = A (S), S - 64-розрядна двійкова послідовність

(Y (i), Z (i)) = (Y (i-1) [+] C2, Z (i-1) {+} C (1)), i = 1, 2, ..., m .

64-розрядна послідовність, звана сінхропосилку, не є секретним елементом шифру, але її наявність необхідна як на передавальній стороні, так і на приймальній.

Режим гамування зі зворотним зв'язком дуже схожий на режим гамування. Як і в режимі гамування відкриті дані, розбиті на 64-розрядні блоки T (i), зашифровуються шляхом порозрядного складання по модулю 2 з гамою шифру Г _ш, яка виробляється блоками по 64 біт:

Г _ш = (Г (1), Г (2), ..., Г (m)).

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

Ш (1) = A (S)  T (1) = Г (1)  T (1),

Ш (i) = A (Ш (i-1)  T (i) = Г (i)  T (i), i = 2, 3, ..., m.

У ГОСТ 28147-89 визначається процес вироблення імітовставки, який единообразен для всіх режимів шифрування. Имитовставка - це блок з р біт (имитовставка І _р), який виробляється або перед шифруванням усього повідомлення. або паралельно із шифруванням по блоках. Параметр р вибирається у відповідності з необхідним рівнем імітозащіщенності.

Для отримання імітовставки відкриті дані представляються також у вигляді блоків по 64 біт. Перший блок відкритих даних Т (1) піддається перетворенню, що відповідає першим 16 циклам алгоритму режиму простої заміни. Причому в якості ключа використовується той же ключ, що і для шифрування даних. Отримане 64-розрядно число підсумовується з відкритим блоком Т (2) і сума знову піддається 16 циклам шифрування для режиму простої заміни. Дана процедура повторяться для всіх m блоків повідомлення. З отриманого 64-розрядного числа вибирається відрізок І _р довжиною р біт.

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

Системи з відкритим ключем

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

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

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

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

Система

з відкритим ключем

Система

з відкритим ключем