МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
||||||||||||||||||||||||||||||||||||||||||||||
Ймовірнісне криптування4.1. Ідея.Шафі Гольдвассер і Сільвіо Мікелі [99] запропонували ймовірнісну модифікацію криптографічної схеми з відкритим ключем (див. § 1). їх ідея полягає в тому, щоб зробити алгоритм шифрування Е ймовірнісним. Ймовірнісний алгоритм шифрування ставить у відповідність повідомленню М не один криптотекст С, а деяку родину криптотекстів cm, причому кожен член цієї родини вибирається з певною ймовірністю. Іншими словами, для кожного повідомлення М результат роботи алгоритму Е(М) є випадковою величиною, розподіленою на множині cm. Щоб уможливити дешифрування, для будь-якої пари різних повідомлень М1 та М2 відповідні їм множини криптотекстів cmi та cm2 не повинні перетинатися. Більше того, має бути ефективний алгоритм дешифрування, який використовує таємний ключ і за будь-якимвизначає М. Таку криптосистему вважають надійною, якщо для будь-якої пари повідомлень М1 та М2 однакової довжини l, випадкові величини Е(М1) та Е(М2) неможливо відрізнити одну від одної ніяким ймовірнісним поліноміальним алгоритмом із ймовірністю, вищою за 1/l. Тобто лише з незначною ймовірністю за двома криптотекстами можна визначити, відповідають вони одному й тому ж повідомленню чи різним. Такий рівень надійності в принципі недосяжний для детермінованих систем, у випадку яких пара різних криптотекстів С1 і С2 завжди відповідає різним відкритим текстам М1 і М2. Ймовірнісне криптування вирішує також проблему, зауважену нами на початку пункту 2.4, що детерміноване шифрування не маскує належним чином деякі з повідомлень, наприклад 0 та 1 у випадку системи RSA. Зупинимось на понятті надійності ймовірнісної криптосистеми з відкритим ключем докладніше. Нехай А — ймовірнісний алгоритм, який завжди подає на вихід одне із двох значень — 1 або 2. Неформально це треба розуміти так, що отримавши на вхід криптотекст С, алгоритм А намагається з'ясувати, що саме має місце, чи Результат роботи А на вході С позначимо через А(С). означення 4.1. Ймовірнісну криптосистему з відкритим ключем вважаємо надійною, якщо для будь-якого ймовірнісного поліноміального алгоритму A, для будь-якої пари повідомлень М1 і М2 однакової досить великої довжини l, ймовірності того, що А(Е(Мi) = 1, для і = 1 та i = 2 відрізняються не більш, ніж на 1/l, тобто j. Ймовірність вимірюється за вибором випадкових послідовностей як алгоритмом А, так і алгоритмом шифрування Е. Таким чином, ймовірнісне криптування можна розцінювати як добре наближення до ідеалу надійності у теоретико-інформаційному сенсі, що досягається для шифру одноразового блокноту. Різниця полягає в тому, що йдеться все ж про надійність в обчислювальному сенсі — це ціна, яку доводиться платити за прийнятну, у порівнянні з шифром одноразового блокноту, довжину ключа. 4.2. Реалізація на основі квадратичності. У [99] ідея ймовірнісного криптування була втілена на основі задачі розпізнавання квадратичних лишків (див. пункти IV.1.2 і IV.4.3). Введемо позначення Jn для підмножини групи , що об'єднує елементи х із властивістю . Нагадаємо, що у випадку коли п = pq є добутком двох різних простих, множина квадратичних лишків Qn є власною підмножиною в Jn. Множина називається множиною псевдоквадратів за модулем п, і має рівно стільки ж елементів, що й Qn (пункт а вправи IV.1.15). Перейдемо до опису криптосистеми. Генерування ключів. Вибирають великі прості числа р та q, і обчислюють їх добуток п = pq. Вибирають випадковий псевдоквадрат Покладають Відкритий ключ: п, а. Таємний ключ: р, q. Шифрування. Двійкове повідомлення М = т1т2...ті, де ,перетворюють у криптотекст виглядуС = c1c2... сl де.Для і = 1,...,l елемент ci генерують за допомогою такої ймовірнісної процедури:
Дешифрування. За криптотекстом С = с1с2...сl відкритий текст М = m1m2...ml визначають за таким правилом: для і = 1,...,l Коректність. Очевидно, що бітові повідомлення mi = 0 у криптотексті відповідає квадратичний лишок сi. Бітові mi = 1 відповідає елемент ci, який є добутком квадратичного лишка і псевдоквадрату, що завжди є псевдоквадратом (див. пункт ь вправи IV. 1.15). Отже, повідомлення М однозначно визначається криптотекстом С незалежно від випадкових виборів елемента ri алгоритмом шифрування. Ефективність. Зупинимось на виборі псевдоквадрату а, компоненти відкритого ключа. В вибирають випадковий квадратичний нелишок а1, а в — випадковий нелишок а2 (див. пункт IV. 4.1). Елемент а визначають з умов і за алгоритмом з Китайської теореми про остачі. Таке а є квадратичним нелишком, бо нелишками є і а1, і a2 — достатньою була б навіть одна з цих причин. З іншого боку, маємо Отже, а є псевдоквадратом. Неважко зрозуміти, що а є випадковим елементом із , тобто розподілене на цій множині рівномірно. При дешифруванні треба вміти відрізняти квадратичні лишки від псевдоквадратів. Для цього можна використати зведення задачі розпізнавання квадратичних лишків за модулем n = pq до факторизації числа п з пункту IV.4.3, оскільки співмножники р і q даються таємним ключем. Приклад 4.2. Візьмемо р = 7 і q = 11. Обчислимо n = 77. Щоб отримати а, вибираємо а1 = 3 і a2 = 2. Для них а = 24. Формування ключів завершено. Припустимо, що ми хочемо зашифрувати повідомлення НІ.1[1] Його двійковим еквівалентом е 010001 001011 (див. пункт 1.3.1). Почнемо шифрування з першого біта m1 = 0. Нехай r1 = 26. Тоді c1 = 262 mod 77 = 60. Наступним бітом є m2 = 1. Нехай r2 = 41. Тоді c2 = 24•412 mod 77 = 73. Продовжуємо в такому ж дусі. Можливий результат наведено в таблиці.
Отримуємо криптотекст 60 73 25 53 37 13 23 71 10 15 68 06. Надійність. Зрозуміло, що задача знаходження біта mi відкритого тексту за компонентою ci криптотексту є задачею розпізнавання квадратичних лишків за модулем n = pq, для якої невідомо жодного ефективного алгоритму (без використання множників р і q, див. зауваження IV.4.5). Для mi = 0 елемент сi є випадковим квадратичним лишком, а для mi = 1 випадковим псевдоквадратом за модулем п. Останнє випливає з пункту ь вправи IV.1.15. На сьогодні невідомо ймовірнісного поліноміального алгоритму, який би відрізняв випадковий квадратичний лишок від випадкового псевдоквадрату за модулем n з імовірністю кращою, ніж 1/logn. Більше того, в [99] показано, що якби такий алгоритм існував, його можна було б перетворити у ймовірнісний алгоритм, який розпізнавав би квадратичні лишки за поліноміальний час. Таким чином, надійність криптосистеми еквівалентна важкості розпізнавання квадратичних лишків за модулем n = pq.
4.3. Реалізація на основі RSA функції. Генерування ключів відбувається таким же чином, як і для системи RSA. Відкритий ключ: е, п, де n = pq, НСД (е, ф(п)) = 1. Таємний ключ: d таке, що ed 1 (mod ф(п)). Шифрування. Двійкове повідомлення М = т1т2...ml, де перетворюють у криптотекст виду C = c1.c2...cl, де .Для і = 1,...,l елемент ci генерують за допомогою такої імовірнісної процедури. • Якщо mi = 0, то в Znвибирають випадкове парне число xi; якщо mi = 1, то вибирають випадкове непарне xi. • Обчислюють . Дешифрування. За криптотекстом C = c1.c2...cl відкритий текст М М = т1т2...ml визначають за таким правилом: для і = 1,...,l
В [67] доведено, що надійність цієї криптосистеми рівносильна припущенню, що RSA не може бути розкрита поліноміальним алгоритмом.
|
|||||||||||||||||||||||||||||||||||||||||||||||
|