Потаємні дверцята
Щоб було зрозуміло, про що мова, є така спеціяльна картинка:
Правда ж, ви нізащо 😄 не здогадаєтесь, що 🐧 на ній зображено, адже вона 🔏 зашифрована?!
Коли один і той самий шматок інформації шифрується одним і тим самим алгоритмом, тим самим ключем, звісно, виходить той самий результат. І, як на цій картинці, інформація може бути прочитана навіть без спроби її розшифрувати — достатньо помітити, що повтори означають повтори.
Як з цим боротися? Не повторювати! Додати трохи випадковості.
Згенерувати послідовність випадкових чисел можна. Записати шум дощу який-небудь. Сфотографувати бульбашку в банці. Будь-що. Але зашифрована інформація має бути ще й розшифрована. Як передати таємну випадкову послідовність другій стороні? Зашифрувати її іншим таємним ключем? А його ще одним? Ad infinitum? Ні-ні-ні! Насправді є спосіб узгодження ключа без розголошення, але... Це занадто громіздка процедура — вишукувати якісь випадкові процеси, обмінюватись записаними випадковими числами, і таким чином узгоджувати ключ для передачі... кожного блоку, кількох байтів повідомлення. До того ж знайти багато випадкового не так-то легко: краплі дощу падають ритмічно і бульбашки усі доволі округлі...
Ясно, що практичніше справді випадкове число використовувати лише зрідка. Для ініціації псевдовипадкової послідовності.
Генератор псевдовипадкових чисел може працювати дуже просто — бере попереднє число, виконує з ним якісь дії, і отримує наступне.
Наприклад, один з перших таких генераторів, авторства самого фон Ноймана, підносив число до квадрата, відкидаючи в результаті перші і останні цифри, щоб кількість розрядів залишалась незмінною.
Для криптографічно-безпечного генератора псевдовипадкових чисел такі алгоритми не годяться. Адже щойно буде перехоплено одне число в послідовності, ми зможемо згенерувати усі наступні, використавши такий самий генератор. Якщо вгадаєте, якого кольору в пінгвіна пір’я, то побачите, що він тримає у дзьобі, образно кажучи. Треба якось розділити внутрішній стан, який визначає, яке число буде згенероване наступним, від самої послідовності.
Є й інші важливі вимоги, наприклад, рівномірний, але не впорядкований, розподіл отриманих чисел. Погляньте лише, як поганий генератор фон Ноймана любить деякі цифри; спробуйте задати стартове число з нулями!
Щоб зрозуміти фокус з потаємними дверцятами, не треба заглиблюватись в надто складні математичні деталі. Достатньо знати про односторонню функцію як таку собі чорну скриньку. Є функція y = f(k, x). Якщо відомі два числа k й x, то легко і просто порахувати y. А от навпаки — задача дуже складна. Щоб з наведеного рівняння за відомими k й y знайти невідому x (і так само за відомими x і y знайти k) — найкраще, що вдалося вигадати, це підставляти усі числа по порядку замість невідомого, аж поки не виявиться, що рівність виконується (і часу на те, щоб перебрати половину можливих варіантів доведеться витратити трохи більше, ніж існує Всесвіт).
Саме ця одностороння функція і стоїть захисною брамою між черговим числом, яке виходить назовні r, формуючи псевдовипадкову послідовність, і внутрішнім станом s генератора: r = f(p, s).
Аналогічна функція використовується і для зміни стану s, перед тим, як отримати наступне число псевдовипадкової послідовності. s' = f(q, s). Тільки тут використовується зовсім інший ключ, q
замість p. Так що те, що відбувається у внутрішній частині генератора зі станом s, і те, що він видає назовні в r, ніяк не залежить, або будемо чесними, залежить так складно, що аж двічі нерозв’язно.
Хороша ідея, чи не так?!
❔
Гокус-покус полягає в тому, що згадана непролазно заплутана функція f(k, x) все-таки містить трохи чарівної симетрії. А саме f(f(k, a), b) = f(f(k, b), a). Тобто, якщо її послідовно застосувати до двох чисел a і b, то байдуже, в якому порядку виконувати дії, результат не зміниться.
Ну то й що?!
❔
Припустимо... Припустимо, що q = f(p, e). Тоді s' = f(q, s) = f(f(p, e), s) = f(f(p, s), e) = f(r, e). Абракадабра!! чи той, як його, сезаме!! Потаємні дверцята розчинилися і ми пройшли крізь браму, яку нібито ніяк не можливо відчинити ззовні. Достатньо перехопити лише одне згенероване число r і ми знаємо, як налаштувати початковий стан s' генератора, щоб він видав нам усю послідовність наступних чисел. «Такі алгоритми не годяться»?
Математика каже, що розв’язок e рівняння q = f(p, e) для деякої пари p, q існує. Потаємні дверцята справді є. Тільки знайти їх практично неможливо. Якщо тільки... з самого початку q не було розраховане за довільно заданим e.
Насправді саме так воно і робиться.
Коли один і той самий шматок інформації шифрується одним і тим самим алгоритмом, тим самим ключем, звісно, виходить той самий результат. І, як на цій картинці, інформація може бути прочитана навіть без спроби її розшифрувати — достатньо помітити, що повтори означають повтори.
Як з цим боротися? Не повторювати! Додати трохи випадковості.
Згенерувати послідовність випадкових чисел можна. Записати шум дощу який-небудь. Сфотографувати бульбашку в банці. Будь-що. Але зашифрована інформація має бути ще й розшифрована. Як передати таємну випадкову послідовність другій стороні? Зашифрувати її іншим таємним ключем? А його ще одним? Ad infinitum? Ні-ні-ні! Насправді є спосіб узгодження ключа без розголошення, але... Це занадто громіздка процедура — вишукувати якісь випадкові процеси, обмінюватись записаними випадковими числами, і таким чином узгоджувати ключ для передачі... кожного блоку, кількох байтів повідомлення. До того ж знайти багато випадкового не так-то легко: краплі дощу падають ритмічно і бульбашки усі доволі округлі...
Ясно, що практичніше справді випадкове число використовувати лише зрідка. Для ініціації псевдовипадкової послідовності.
Генератор псевдовипадкових чисел може працювати дуже просто — бере попереднє число, виконує з ним якісь дії, і отримує наступне.
Наприклад, один з перших таких генераторів, авторства самого фон Ноймана, підносив число до квадрата, відкидаючи в результаті перші і останні цифри, щоб кількість розрядів залишалась незмінною.
Для криптографічно-безпечного генератора псевдовипадкових чисел такі алгоритми не годяться. Адже щойно буде перехоплено одне число в послідовності, ми зможемо згенерувати усі наступні, використавши такий самий генератор. Якщо вгадаєте, якого кольору в пінгвіна пір’я, то побачите, що він тримає у дзьобі, образно кажучи. Треба якось розділити внутрішній стан, який визначає, яке число буде згенероване наступним, від самої послідовності.
Є й інші важливі вимоги, наприклад, рівномірний, але не впорядкований, розподіл отриманих чисел. Погляньте лише, як поганий генератор фон Ноймана любить деякі цифри; спробуйте задати стартове число з нулями!
Щоб зрозуміти фокус з потаємними дверцятами, не треба заглиблюватись в надто складні математичні деталі. Достатньо знати про односторонню функцію як таку собі чорну скриньку. Є функція y = f(k, x). Якщо відомі два числа k й x, то легко і просто порахувати y. А от навпаки — задача дуже складна. Щоб з наведеного рівняння за відомими k й y знайти невідому x (і так само за відомими x і y знайти k) — найкраще, що вдалося вигадати, це підставляти усі числа по порядку замість невідомого, аж поки не виявиться, що рівність виконується (і часу на те, щоб перебрати половину можливих варіантів доведеться витратити трохи більше, ніж існує Всесвіт).
Саме ця одностороння функція і стоїть захисною брамою між черговим числом, яке виходить назовні r, формуючи псевдовипадкову послідовність, і внутрішнім станом s генератора: r = f(p, s).
Аналогічна функція використовується і для зміни стану s, перед тим, як отримати наступне число псевдовипадкової послідовності. s' = f(q, s). Тільки тут використовується зовсім інший ключ, q
замість p. Так що те, що відбувається у внутрішній частині генератора зі станом s, і те, що він видає назовні в r, ніяк не залежить, або будемо чесними, залежить так складно, що аж двічі нерозв’язно.
Хороша ідея, чи не так?!
❔
Гокус-покус полягає в тому, що згадана непролазно заплутана функція f(k, x) все-таки містить трохи чарівної симетрії. А саме f(f(k, a), b) = f(f(k, b), a). Тобто, якщо її послідовно застосувати до двох чисел a і b, то байдуже, в якому порядку виконувати дії, результат не зміниться.
Ну то й що?!
❔
Припустимо... Припустимо, що q = f(p, e). Тоді s' = f(q, s) = f(f(p, e), s) = f(f(p, s), e) = f(r, e). Абракадабра!! чи той, як його, сезаме!! Потаємні дверцята розчинилися і ми пройшли крізь браму, яку нібито ніяк не можливо відчинити ззовні. Достатньо перехопити лише одне згенероване число r і ми знаємо, як налаштувати початковий стан s' генератора, щоб він видав нам усю послідовність наступних чисел. «Такі алгоритми не годяться»?
Математика каже, що розв’язок e рівняння q = f(p, e) для деякої пари p, q існує. Потаємні дверцята справді є. Тільки знайти їх практично неможливо. Якщо тільки... з самого початку q не було розраховане за довільно заданим e.
Насправді саме так воно і робиться.
Коментарі
Дописати коментар