Математика - цариця наук, але чи багато хто знає, вирішення яких прикладних завдань їй під силу? На це питання відповідає проста і захоплююча книга Неллі Литвак і Андрія Райгородського «Кому потрібна математика?». У цій книзі описуються різні розділи прикладної математики, від логістики до математики онлайн-реклами. Ми вирішили познайомити читачів з фрагментом глави, присвяченої криптографії.
Голова 6. Секретні числа
Масовий обмін шифруваннями
Класична музика по радіо перервалася, і голос диктора став зачитувати цифри, які Штірліц швидко записував в акуратні колонки. Диктор називав цифри звично сухо і чітко. «Для нього ці цифри всього лише цифри», - подумав Штірліц. Коли повідомлення закінчилося, Штірліц взяв з полиці томик Шиллера, відкрив на потрібній сторінці і почав перетворювати цифри на слова. «Центр - Юстасу...» Повідомлення передавалося по відкритому радіоканалу, але прочитати його міг тільки Штірліц, тому що тільки він знав, як розшифрувати передані цифри. Шифрування - це не що інше, як приховування інформації від сторонніх.
Шифрування в тому чи іншому вигляді існує багато тисячоліть. Однак у середині XX століття відбулася свого роду революція. Якщо раніше шифровками користувалися, як правило, представники державних спецслужб (або, якщо завгодно, самі спецслужби і навіть держави), то до 70-х років XX століття стало ясно, що зовсім скоро шифрування знадобиться самим звичайним людям, причому не зрідка, а буквально кожен день. Це пов'язано з лавиноподібним розвитком технологій, плоди яких доступні кожному: комп'ютери, стільникові телефони тощо.
Кожен раз, коли ви вводите свій пароль або номер кредитної картки на сайті, ви відправляєте особисту конфіденційну інформацію по відкритих каналах інтернету. У багатьох до цих каналів є доступ, наприклад у вашого інтернет-провайдера. У принципі перехопити ваше повідомлення може навіть комп'ютерник-аматор зі звичайним ноутбуком і відповідним для цієї мети програмним забезпеченням. Конфіденційність інформації забезпечується саме тим, що вона передається у вигляді шифрування. Ви можете легко дізнатися сайти, на яких діє протокол безпечної передачі даних: у цьому випадку веб-адреса починається з https://... HTTP - звичайний протокол передачі даних по інтернету. А додаткова буква S походить від англійського слова secure (безпечний) і означає, що дані будуть передаватися в зашифрованому вигляді.
Як зашифровується і розшифровується щоденний гігантський потік конфіденційної інформації? Природно, математика, як завжди, випереджала технології і стояла біля їхнього витоку. Завданнями шифрування займається криптографія - дуже активна і цікава область математики та інформатики.
Ключ до шифра
У зашифрованому повідомленні кожна буква замінюється якоюсь іншою літерою, числом або знаком. Наприклад, візьмемо найпростіший шифр. Будемо зашифровувати кожну букву наступною буквою алфавіту. Замість А напишемо Б, замість Б - В і так далі, а замість Я - А. Наприклад, слово ПРИВІТ буде виглядати так: РСЙГЬОУ
Це дуже простий шифр, тому що кожна буква завжди зашифровується однією і тією ж буквою, і зламати його - пара дрібниць. Досить вгадати одне слово в повідомленні. Наприклад, ми здогадалися, що повідомлення починається зі слова «привіт», і ось в нашому розпорядженні вже шифри для шести букв: П, Р, І, В, Е і Т. З їх допомогою ми можемо вгадати інші слова, поки нарешті не розшифруємо весь алфавіт. Саме так розшифрував секретні послання Шерлок Холмс в оповіданні «Пляшущі чоловічки».
Звичайно, будь-який серйозний шифр набагато складніший. Наприклад, одна і та ж літера, скажімо А, може кожен раз позначати різні букви. Або, як у фільмі «Сімнадцять миттєвостей весни», літери можуть бути зашифровані за допомогою цифрового коду. Зрозуміло, що у Штірліца в збірці Шиллера були не вірші, а ключі для розшифровки секретних повідомлень. Якби у Штірліца не було цієї книги, то для нього, як і для диктора, цифри так і залишилися б тільки цифрами.
У протоколах інтернету ключем може бути лише одне число, яке необхідно «підставити у формулу» для розшифровки. В даному випадку «формула» - це дуже довга послідовність досить складних операцій.
Якщо ви зуміли перехопити або вирахувати ключ противника, то всі його секрети - у вашому розпорядженні. У цьому розділі ми розповімо, як за допомогою математики вдається генерувати ключі для передачі конфіденційної інформації по інтернету. Причому заволодіти цими ключами неможливо або щонайменше дуже дорого - для це потрібні колосальні комп'ютерні ресурси.
Але для початку давайте познайомимося зі знаменитою шифрувальною машиною «Енігма», яка використовувалася німецькою армією під час Другої світової війни. Це один з найбільш витончених шифрів тієї епохи, коли шифрування ще не було таким масовим і буденним явищем. А ключ до цього шифру знайшов англійський математик Алан Тьюрінг.
Алан Тьюрінг і «Енігма»
Фільм «Гра в імітацію» (2014) - саме про цю приголомшливу історію. На жаль, у ньому не пояснюється, як влаштована «Енігма» і як Тьюрінг зламав цей шифр. Наша розповідь принаймні частково заповнить ці втрачені подробиці. Ми скористаємося відео Кембриджського університету. Дуже рекомендуємо подивитися їх, щоб побачити «Енігму» в дії (перше і друге).
«Енігма» зовсім невелика, за розміром порівнянна з друкарською машинкою. Зовні вона складається з клавіатури і панелі, на якій розташовані букви з підсвічуванням. Якщо натиснути літеру на клавіатурі, скажімо A, на панелі висвітиться інша літера, наприклад Q. Це означає, що в шифруванні в цьому місці замість А з'явиться Q. Всередині у машини три обертові диски, і їх положення змінюється після набору кожної букви. Диск повернувся, дроти з'єдналися по-іншому, і коли ми наступного разу натискаємо А, на панелі висвічується вже не Q, а, скажімо, G.
У набір «Енігми» входять п'ять дисків, можна використовувати будь-які три, в будь-якому порядку. Кожен диск має 26 початкових положень. І це ще не все. У військовому варіанті у «Енігми» була передня панель з буквами і 10 кабелів. Кожен кабель з'єднував дві будь-які букви між собою, і при шифруванні вони мінялися місцями. Диски можна було перебрати досить швидко, але кількість комбінацій на панелі була настільки велика, що перебрати їх було неможливо. Всього у «Енігми» було
158 962 555 217 826 360 000
можливих початкових установок. Кожної доби рівно опівночі вони змінювалися. Нове початкове положення дисків, нові пари літер на панелі. Перебрати всі комбінації за 24 години було абсолютно нереально. Шифр вважався невразливим.
Зашифроване повідомлення передавали по радіо. У німецького офіцера, який його отримував, була така ж машина. Крім того, він мав секретний документ - установки «Енігми» на кожен день поточного місяця. Це був ключ до шифру машини. Офіцер з'єднував потрібні пари букв, ставив диски в задане вихідне положення, набирав Q, і на панелі висвічувалася А. Поступаючи і далі таким чином, він розшифровував секретне повідомлення.
Перехопити документ з установками хоч і було непросто, але іноді вдавалося, а потім місяць закінчувався і розгадати шифр знову не представлялося можливим.
Алан Тьюрінг і його команда зробили справжній прорив. Вони навчилися розгадувати шифр щоранку всього за 20 хвилин! Ми тільки коротко пояснимо, як їм це вдалося.
Насамперед у шифрі було слабке місце. Літера ніколи не перетворювалася сама на себе. Це стало хоч якоюсь зачіпкою. Важливим виявилося і припущення, що повідомлення вранці починаються з чогось однотипного, наприклад з прогнозу погоди. По-німецьки wetterbericht. Знаючи, що буква не перетворюється сама в себе, ми можемо знайти слово на початку шифрування, яке в принципі може позначати wetterbericht. Тепер потрібно відшукати таку початкову установку, щоб шифр збігся з розшифровкою.
Дуже важливо визначити, які букви з'єднані в пари, тому що тут варіантів особливо багато. Оскільки ніяких відомостей немає, починати доводиться навмання. Зате далі з першої здогадки йдуть відразу кілька інших.
Для прискорення процесу Алан Тьюрінг зробив дві суттєві речі. По-перше, він зрозумів, що якщо пара букв виявилася неправильною, то і всі інші пари, що прямували з неї, теж неправильні. А значить, їх вже не треба перевіряти. По-друге, він побудував величезну машину, яка за допомогою електричного струму дозволяла виключити всі неправильні пари одночасно. Залишалося тільки повторити операцію для кожної позиції дисків, а на це йшло всього 20 хвилин.
Цікаво, що принцип рішення Тьюринга полягав не в тому, щоб знайти правильний варіант, а в тому, щоб виключити неправильні варіанти і зробити це максимально швидко! Це була величезна робота і колосальне досягнення, яке сильно вплинуло на хід Другої світової війни.
Зауважимо, до речі, що в математиці є поняття «машина Тьюринга», але це зовсім не та машина, яка обчислювала ключ «Енігми». «Машина Тьюрінга» - абсолютно абстрактна концепція, яка формально описує роботу комп'ютера. Це дуже важлива фундаментальна концепція в математиці та інформатиці, але вона виходить за рамки нашої книги.
Детальніше читайте: Кому потрібна математика? Зрозуміла книга про те, як влаштований цифровий світ/Неллі Литвак, Андрій Райгородський. - М.: Манн, Іванов і Фербер, 2017. - 192 с.