Криптографія після висадки інопланетян

Автор статті: Брюс Шнайер — американський криптограф, письменник і фахівець з комп’ютерної безпеки. Автор кількох книг з безпеки, криптографії та ІБ. Засновник криптографічного компанії Counterpane Internet Security, Inc., член ради директорів Міжнародної асоціації криптологических досліджень і член консультативної ради Інформаційного центру електронної приватності.

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

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

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

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

З симетричною криптографією, що використовується для шифрування повідомлень, файлів і дисків, цей дисбаланс экспоненциален і посилюється у міру збільшення ключів. Додавання одного біта ключа збільшує складність шифрування менше ніж на відсоток (грубо кажучи), але подвоює складність злому. Таким чином, 256-бітний ключ здається лише вдвічі важче, ніж 128-бітний, але (з нашими поточними знаннями математики) його в 340 282 366 920 938 463 463 374 607 431 768 211 456 разів складніше зламати.

Читайте також  Загадка про пробоїни в «Союзі»

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

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

Квантові комп’ютери обіцяють змінити багато чого з цього. За своєю природою вони добре пристосовані до обчислень, які необхідні для обігу цих односторонніх функцій. Для симетричної криптографії це не так вже погано. Алгоритм Гровера показує, що квантовий комп’ютер прискорює атаки настільки, що ефективна довжина ключа зменшується вдвічі. Тобто 256-бітний ключ так само складний для квантового комп’ютера, як 128-бітний ключ для звичайного комп’ютера: обидва вони безпечні в осяжному майбутньому.

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

З приводу двох останніх абзаців є багато застережень, головне з яких полягає в тому, що квантові комп’ютери, здатні робити що-небудь подібне, в даний час не існує, і ніхто не знає, коли ми зможемо побудувати такий — і зможемо взагалі. Ми також не знаємо, які практичні труднощі виникнуть, коли ми спробуємо реалізувати алгоритми Гровера або Шора на чому-небудь крім ключів іграшкового розміру (механізм корекції помилок на квантовому комп’ютері легко може стати непереборною проблемою). З іншого боку, ми не знаємо, які ще методи будуть виявлені, як тільки люди почнуть працювати зі справжніми квантовими комп’ютерами. Я ставлю на те, що ми подолаємо інженерні проблеми, і що буде багато досягнень і нових методів, але знадобиться час, щоб їх винайти. Так само, як нам знадобилися десятиліття, щоб сконструювати кишенькові суперкомп’ютери, будуть потрібні десятиліття, щоб опрацювати всі інженерні проблеми, необхідні для створення досить потужних квантових комп’ютерів.

Читайте також  Після вимоги вказувати точну швидкість з'єднання провайдери Великобританії знизили рекламні цифри в середньому на 41%

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

Але завжди є ймовірність, що алгоритми зламають інопланетяни з кращими квантовими технологіями. Я менше переживаю про симетричної криптографії, де алгоритм Гровера — по суті максимальний межа можливості квантових обчислень. А ось алгоритми з відкритим ключем, засновані на теорії чисел, здаються більш крихкими. Цілком можливо, що квантові комп’ютери коли-небудь зламають їх всі — навіть ті, які сьогодні вважаються квантово-стійкими.

Якщо це відбудеться, ми залишимося в світі без криптографії з відкритим ключем. Це стане величезним ударом з безпеки і зламає багато системи, але ми зможемо адаптуватися. У 1980-х роках Kerberos була повністю симетричною системою аутентифікації і шифрування. І зараз стандарт стільникового зв’язку GSM виконує аутентифікацію, так і розподіл ключів — у великому масштабі — тільки з симетричною криптографією. Так, ці системи мають централізовані точки довіри і відмови, але можна розробити інші системи, які використовують як секретне поділ, так і секретне спільне використання, щоб звести до мінімуму цей ризик. (Уявіть, що пара учасників зв’язку отримує частину ключа сеансу від кожного з п’яти різних серверів ключів). Повсюдне поширення комунікацій полегшує ситуацію. Ми можемо використовувати внеполосные протоколи: наприклад, ваш телефон допоможе згенерувати ключ для комп’ютера. Для додаткової безпеки можна використовувати особисту реєстрацію: можливо, в магазині, де ви купуєте смартфон або реєструєте інтернет-сервіс. Розвиток апаратного забезпечення також допоможе захистити ключі в цьому світі. Я нічого не намагаюся винайти, тільки кажу, що є багато можливостей. Ми знаємо, що криптографія заснована на довірі, і у нас набагато більше методів управління довірою, ніж у перші роки існування інтернету. Деякі важливі технології, такі як пряма секретність, стануть набагато складніше, але поки симетрична криптографія працює, у нас збережеться захист.

Це дивне майбутнє. Можливо, вся ідея криптографії на теорії чисел, як сучасні системи з відкритим ключем — це тимчасовий феномен, який існує завдяки прогалинам у моделі обчислень. Тепер, коли модель розширилася і включила в себе квантові обчислення, ми можемо опинитися там, де були в кінці 1970-х і початку 1980-х: симетрична криптографія, криптографія на основі кодів, підписи Тьмяніла. Це буде забавно і іронічно.

Читайте також  Створення 1k intro Chaos для ZX-Spectrum

Так, я знаю, що розподіл квантових ключів є потенційною заміною криптографії з відкритим ключем. Але давайте чесно: хто-небудь взагалі вірить, що система, що вимагає спеціалізованого комунікаційного обладнання та кабелів, буде використовуватися для чого-небудь, крім нішевих додатків? Майбутнє — за мобільними, постійно включеними обчислювальними пристроями. Всі системи безпеки для них будуть тільки програмними.

Є ще один сценарій майбутнього, не кажучи про квантові комп’ютери. В основі односторонніх функцій лежать кілька математичних теорій, які ще не доведені. Це одна з відкритих проблем в комп’ютерній науці. Так само, як розумний криптограф може знайти новий трюк, який полегшує злом певного алгоритму, ми можемо уявити собі інопланетян з достатньою математичної теорією, щоб зламати всі алгоритми шифрування. Для нас сьогодні це просто смішно. Криптографія з відкритим ключем — це теорія чисел, потенційно вразлива для математично більш грамотних прибульців. Симетрична криптографія настільки нелінійно складна, а довжина ключа так легко збільшується, що майбутнє складно уявити. Уявіть варіант AES з 512-бітовим блоком і розміром ключа, і шифруванням 128 раундів. Якщо тільки не придумати принципово нову математику, таке шифрування буде безпечно до тих пір, поки комп’ютери не зроблять з чогось іншого, крім матерії, в якомусь іншому вимірі.

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

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

Степан Лютий

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

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *