Чому 256 біт вистачить назавжди

На програмістські форумі StackExchange один з користувачів задався питанням. чому RSA Security рекомендує використовувати ключі довжиною 1024 біта, 2048 біт і навіть 3072 біт, в той час як більшість алгоритмів симетричного шифрування обмежуються довжиною від 112 до 256 біт. Мовляв, чому б нам не збільшити довжину ключів, наприклад, до мільйона - щоб захиститися від потенційного брутфорса з боку суперкомп'ютерів, які ще не винайдено.

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

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

Для злому симетричного шифру потрібно перебрати 2 ^ N комбінацій, де N - довжина ключа. Розшифровка повідомлення в будь-якому випадку відбувається миттєво, маючи симетричний ключ. За оцінкою NIST. 256-бітний симетричний ключ приблизно відповідає 15360-бітного ключа RSA. Найкраще цей приклад описаний в книзі «Прикладна криптографія» Брюса Шнайера, яку можна процитувати.

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

Прийнявши, що k = 1,38 * 10 -16 ерг / K, і що температура навколишнього всесвіту 3,2K, ідеальний комп'ютер, працюючи при 3,2K, споживав би 4,4 * 10 -16 ерга щоразу, коли він встановлює або скидає біт. Робота комп'ютера при температурі нижчій, ніж температура космічного простору, зажадала б додаткових витрат енергії для відводу тепла.

Далі, енергія, яку випромінює нашим Сонцем за рік, становить близько 1,21 * 10 41 ергов. Це досить для виконання 2 * 10 56 змін біта в нашому ідеальному комп'ютері, а цього, в свою чергу, вистачить для того, що б 187-бітовий лічильник пробіг всі свої значення. Якщо ми побудуємо навколо Сонця сферу Дайсона і перехопимо без всяких втрат всю його енергію за 32 роки, ми зможемо отримати комп'ютер для обчислення 2 192 чисел. Звичайно, енергії для проведення яких-небудь корисних обчислень з цим лічильником вже не залишиться.

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

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

Поділися новиною з друзями: