Коди і шифри
визначити незмінні частини. Забігаючи вперед, можна навести як приклад шіфрмашіна "Енігма" (див. Розділ 9), яка містила кілька коліс; всередині цих коліс були дроти; розпаювання проводів всередині коліс не змінювалася, але щодня змінювався порядок розташування коліс всередині самої машини. Таким чином, розпаювання проводів була незмінною частиною, а порядок коліс - змінної. Злом системи - це найбільш трудомістка частина роботи; вона може тривати кілька тижнів або навіть місяців і вимагати застосування математичних методів, пошуку і використання помилок операторів і навіть відомостей, здобутих шпигунами.
Після того, як визначені всі незмінні частини системи, необхідно визначити всі змінні частини (такі, як початкові положення коліс в шіфрмашіна "Енігма", які змінювалися для кожного повідомлення). Це - завдання розтину ключів повідомлення. Після її рішення повідомлення будуть розшифровані.
Отже, злом відноситься до системи шифрування в цілому, а розтин ключів пов'язано з дешифрованием окремих повідомлень.
Хоча слова код і шифр часто вживаються нестрого, ми проведемо розмежування між цими поняттями. У коді часто зустрічаються елементи тексту (які можуть складатися з однієї або більше букв, чисел або слів) зазвичай замінюються чотирма або п'ятьма літерами або числами, які називаються кодовими групами і беруться з кодової книги. Для особливо часто вживаних виразів або знаків кодова книга може пропонувати кілька кодових груп. Це робиться для того, щоб криптограф міг варіювати ними з метою утруднити їх ідентифікацію. Так, наприклад, в чотиризначному цифровому коді для слова "Понеділок" можуть бути три альтернативні кодові групи - наприклад, тисяча п'ятсот тридцять вісім, або 2951, або 7392. Коди ми розглянемо в розділі 6.
Коди - це окремий випадок системи шифрування. проте не всі системи шифрування є кодами. Ми будемо використовувати слово шифр по відношенню до методів шифрування. в яких використовуються не кодові книги. а шифрований текст виходить з вихідного відкритого тексту згідно з визначеним правилом. У наш час замість слова "правило" воліють користуватися словом "алгоритм", особливо якщо мова йде про комп'ютерну програму. Різниця між поняттями коду і шифру іноді не зовсім чітке, особливо для простих систем. Мабуть, можна вважати, що шифр Юлія Цезаря використовує лише однієї сторінки кодову книгу, де кожній букві алфавіту сопоставлена буква, що стоїть в алфавіті на три позиції далі. Однак для більшості систем, які ми розглянемо, це відмінність буде досить чітким. Так, наприклад, "Енігма", яку часто
помилково називають "кодом Енігма", безумовно є зовсім не кодом. а
Історично склалося так, що аж до порівняно недавнього часу в криптографії переважали дві основні ідеї, і багато систем шифрування (в тому числі майже всі з описаних в перших одинадцяти главах цієї книги) були засновані на одній з них або на обох відразу. Перша ідея зводилася до того, щоб перетасувати літери алфавіту (як зазвичай тасують колоду карт) з метою отримати щось, що можна розглядати як випадковий порядок, перестановку або анаграма букв. Друга ідея полягає в тому, щоб перетворити літери повідомлення в числа (наприклад, поклавши A = 0, B = 1. Z = 25), і потім додавати до них (число за числом) інші числа, звані гамою. які, в свою чергу, можуть бути буквами, перетвореними в числа. Якщо в результаті складання виходить число, більше ніж 25, віднімемо з нього 26 (цей спосіб називається складанням по модулю 26). Результат потім перетвориться назад
в літери. Якщо числа, додаємо до тексту, отримані за допомогою досить важко передбачуваного процесу, то зашифроване таким способом повідомлення дуже важко, або навіть неможливо дешифрувати без знання гами.
Цікаво відзначити, що шифр Юлія Цезаря, яким би нехитрим він не був, можна вважати прикладом і того, і іншого типу. У першому випадку наше "тасування колоди" еквівалентно простого переміщення останніх трьох карт в початок колоди, так що всі букви зміщуються вниз на три позиції, а X, Y і Z виявляються на початку. У другому випадку гамою є число 3, яке повторили нескінченне число разів. Не можна собі й уявити нічого "слабкіше" такого гами.
Переклад повідомлення на іншу мову, мабуть, теж можна було б вважати певним видом шифрування з використанням кодової книги (тобто словника), але це все-таки занадто вільне вживання слова код. Однак такий спосіб перекладу на іншу мову, коли за кожним словом лізуть
*) Згадую, як якийсь школяр писав твір французькою мовою про те, як в середні віки один мандрівник приїжджає вночі в готель і стукає в двері. У відповідь він чує "What Ho! Without." ( "Якого біса! Забирайся!" - прим. Перекл.). Цей вислів школяр перевів на французький дослівно, підставивши французькі слова: "Que Ho! Sans." (Вийшло "Що за хо! Без." - прим. Перекл.) .Учітель французької мови, прочитавши це, втратив на мить дар мови, а потім помітив; "Ви, напевно, знайшли ці слова в словнику, який роздають безкоштовно з мішками цукру".
Широке поширення комп'ютерів і можливість практичного побудови складних електронних мікросхем на кремнієвих кристалах зробили революцію як в криптографії, так і в криптоанализе. В результаті деякі сучасні системи шифрування ґрунтуються на передових математичних концепціях і вимагають солідної обчислювальної та електронної бази. Тому в докомпьютерную епоху користуватися ними було практично неможливо. Деякі з них описані в розділах 12 і 13.
Оцінка стійкості системи шифрування
Коли пропонується нова система шифрування, то дуже важливо оцінити її стійкість до всіх вже відомим методам розтину в умовах, коли криптоаналітику відомий тип використовуваної системи шифрування, але не у всіх деталях. Оцінювати стійкість системи шифрування можна для трьох різних ситуацій:
(1) криптоаналітику відомі тільки шифровані тексти;
(2) криптоаналітику відомі шифровані тексти і вихідні відкриті тексти до них;
(3) криптоаналітику відомі як шифровані, так і відкриті тексти, які він сам підібрав.
Перший випадок відображає "типову" ситуацію: якщо в цих умовах систему шифрування можна розкрити за короткий час, то користуватися нею не слід. Друга ситуація виникає, наприклад, якщо однакові повідомлення шифруються як за новою системою, так і за старою, яку
Коди, що виявляють і виправляють помилки
Інший клас кодів призначений для забезпечення безпомилкової передачі інформації, а не для приховування її змісту. Такі коди називаються виявляють і виправляють помилки. вони є предметом широкомасштабних математичних досліджень. Ці коди з найперших днів існування комп'ютерів використовуються для захисту від помилок в пам'яті і в даних, записаних на магнітну стрічку. Найперші версії цих кодів, такі, наприклад, як коди Хеммінга, здатні виявити і виправити одиничну помилку в шестирозрядна символі. Як більш пізнього приклад можна привести код, який використовувався на космічному кораблі "Маринер" для передачі даних з Марса. Створений з урахуванням можливого значного спотворення сигналу на його довгому шляху до Землі, цей код був здатний коригувати до семи помилок в кожному 32-розрядному "слові". Простим прикладом коду іншого рівня, виявляє. але не виправляє помилки, є код ISBN (International Standard Book Number - Міжнародний Стандартний Книжковий Номер) .Він складається з десяти знаків (десяти цифр або дев'яти цифр з буквою X на кінці, яка позначає число 10), і дозволяє здійснити перевірку на відсутність помилок в номері ISBN. Перевірка виконується наступним чином: обчислимо суму
(Перша цифра) 1+ (друга цифра) 2+ (третя цифра) 3+. + (Десята цифра) 10.