Ранцева криптосистема Меркле — Геллмана

Ранцева криптосистема Меркле-Геллмана, заснована на «задачі про рюкзак», була розроблена Ральфом Меркле i Мартіном Геллманом в 1978 році.^[1] Це була одна з перших асиметричних криптосистем, але вона виявилася криптографічно нестійкою^[2] і, як наслідок, не набула популярності.

Опис ред.

«Задача про рюкзак» полягає в наступному: знаючи підмножину вантажів, покладених в ранець, легко підрахувати сумарну вагу, але, знаючи вагу, непросто визначити підмножину вантажів. Більш докладно, нехай задана послідовність з n додатних чисел (n — «розмір» рюкзака)

w = (w₁, w₂, …, w_n) і s.

Завдання полягає в тому, щоб знайти такий бінарний вектор

x = (x₁, x₂, …, x_n), (x_i = 0 або 1), щоб

s=\sum _{i=1}^{n}x_{i}w_{i}

.

Якщо кожному двійковому числу x поставити у відповідність деяку літеру алфавіту, то її можна було б передавати в зашифрованому вигляді просто як суму s. Для довільного набору чисел w_i завдання відновлення x по s є NP-складним.

Р.Мерклю вдалося отримати зворотню до числа ''s'' функцію, яка давала б вектор x, знаючи тільки якийсь «секретний» ключ, і він запропонував $ 100 тому, хто зможе розкрити ранцеву систему Меркле — Геллмана.

Розглянемо її докладніше.

Меркль використав не довільну послідовність w_i, а суперзбільшену (superincreasing), тобто таку, що

w_{k+1}>\sum _{i=1}^{k}w_{i}

.

Неважко переконатися, що для такого набору чисел рішення задачі є тривіальним. Щоб позбутися цієї тривіальності і знадобилося ввести «секретний ключ», а саме два числа: q таке, що $q>\sum _{i=1}^{n}w_{i}$ и r таке, що НСД(r, q) =1. І тепер замість початкового набору чисел w_i будемо використовувати числа b_i=rw_i mod q. В оригінальних статтях Меркль рекомендував використовувати n порядку 100, де n — число елементів суперзбільшеної послідовності («розмір» рюкзака).

В результаті отримуємо: відкритий ключ — (b₁, b₂, …, b_n), закритий ключ — (w₁, w₂, …, w_n; q, r).

Шифрування

  – повідомлення x = (x₁, x₂, ..., x_n)
  - обчислюємо y = b₁x₁ + b₂x₂ + b_nx

Розшифровка

  - обчислюємо s = y'r^-1 mod q
  - вирішуємо задачу для s для суперзбільшеної послідовності  (w₁, w₂, ..., w_n), знаходимо число x

Нагорода дісталась А. Шамиру (Adi Shamir) після публікації ним в березні 1982 року повідомлення про відкриття ранцевої системи Меркле-Геллмана з однією інтерацією.

Це була одна з невдалих, але дуже цікавих спроб побудови криптосистеми на основі задачі про рюкзак.

Генерація ключа ред.

В системі Меркле-Геллмана ключі складаються з послідовностей. Відкритий ключ являє собою «складну» послідовність, закритий ключ складається з «простої» або суперзбільшеної послідовності, а також двох додаткових чисел — множника і модуля, які використовуються як для перетворення суперзбільшеної послідовності в «складну» (генерація відкритого ключа), так і для перетворення суми підмножини «складною» послідовності в суму підмножини «простої» (розшифровка). Останнє завдання вирішується за поліноміальний час.

Шифрування ред.

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

Розшифровка ред.

Розшифровка є можливою в силу того, що множник і модуль, використовувані для генерації відкритого ключа з суперзбільшеної послідовності, використовуються також і для перетворення шифротекста в суму відповідних елементів суперзбільшеної послідовності. Далі, за допомогою простого жадібного алгоритму, можна розшифрувати повідомлення, використовуючи O(n) арифметичних операцій.

Математичний опис алгоритму ред.

Генерація ключа ред.

Щоб зашифрувати n-бітове повідомлення, виберемо суперзбільшену послідовність з n ненульових натуральних чисел

w = (w₁, w₂, …, w_n).

Далі випадковим чином виберемо цілі взаємно прості числа q і r такі, що

q>\sum _{i=1}^{n}w_{i}

.

Число q вибирається таким чином, щоб гарантувати єдиність (унікальність) шифротексту. У випадку, якщо воно буде хоча б трохи менше, може виникнути ситуація, що одному шифротексту будуть відповідати кілька вихідних (відкритих) текстів. r повинно бути взаємно простим з q, в іншому випадку воно не буде мати мультиплікативного оберненого по модулю q, існування якого необхідно для розшифрування.

Тепер побудуємо послідовність

β = (β₁, β₂, …, β_n), де кожен елемент обчислюється за наступною формулою

β_i = rw_i mod q.

β буде відкритим ключем, в той час як закритий ключ утворює послідовність (w, q, r).

Шифрування ред.

Щоб зашифрувати n-бітове повідомлення

α = (α₁, α₂, …, α_n), де

\alpha _{i}

— це i-ий біт, тобто

\alpha _{i}{\boldsymbol {\in }}

{0, 1}, обчислимо число c, яке і буде шифротекстом.

c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.

Розшифровка ред.

Щоб прочитати вихідний текст, одержувач повинен визначити біти повідомлення  $\alpha _{i}$ , які задовільняли б формулу

c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.

Таке завдання було б NP-складним в разі, якби β_i були випадково вибраними значеннями. Однак значення β_i були вибрані таким чином, що розшифрування зводиться до простого завдання за умови, що закритий ключ (w, q, r) відомий.

Ключ до визначення початкового тексту полягає в тому, щоб знайти ціле число s, яке є мультиплікативним оберненим r по модулю q. Це означає, що s задовільняє рівнянню sr mod q = 1, що еквівалентно існуванню цілого числа k такого, що sr = kq + 1. Оскільки r взаємно просте з q, знайти s і k можливо з використанням розширеного алгоритму Евкліда. Далі одержувач шифротексту обчислює

c'\equiv cs{\pmod {q}}.

Звідси

c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q}}.

З того, що rs mod q = 1 і β_i= rwi mod q, слідує

\beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q}}.

Тоді

c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q}}.

Сума всіх w_i менше, ніж q. Звідси значення $\sum _{i=1}^{n}\alpha _{i}w_{i}$ також знаходиться в інтервалі [0,q-1]. Таким чином, одержувач повинен визначити $\alpha _{i}$ з умови, що

c'=\sum _{i=1}^{n}\alpha _{i}w_{i}.

.

А це вже просте завдання, оскільки w — суперзбільшена послідовність. Нехай w_k — найбільший елемент в w. Якщо w_k > c' , то α_k = 0; якщо w_k ≤c' , то α_k = 1. Далі віднімаємо w_k×α_k з c' і повторюємо ці кроки доти, поки не обчислимо α.

Приклад ред.

w = {2, 7, 11, 21, 42, 89, 180, 354} - суперзбільшена послідовність.

Вона є основою для генерації закритого ключа. Порахуємо суму елементів послідовності

\sum w=706

Далі виберемо просте число q, що перевершує отримане нами значення суми.

q = 881

Виберемо також число r з інтервалу [1,q)

r = 588

w, q і r утворять закритий ключ.

Щоб згенерувати відкритий ключ, побудуємо послідовність β, помноживши кожен елемент з послідовності w на r по модулю q.

2 * 588 mod 881 = 295
7 * 588 mod 881 = 592
11 * 588 mod 881 = 301
21 * 588 mod 881 = 14
42 * 588 mod 881 = 28
89 * 588 mod 881 = 353
180 * 588 mod 881 = 120
354 * 588 mod 881 = 236

Отримаємо  β = (295, 592, 301, 14, 28, 353, 120, 236).

Послідовність β утворить відкритий ключ.

Нехай Аліса хоче зашифрувати «a». Спочатку вона повинна перевести «a» в двійковий код

01100001

Далі вона множить кожен біт на відповідне число з послідовності β, а суму значень відправляє одержувачу.

a = 01100001
0 * 295
+ 1 * 592
+ 1 * 301
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
= 1129

Щоб розшифрувати повідомлення, Боб примножує отримане ним значення на мультиплікативне обернене r по модулю q.

1129 * 442 mod 881 = 372

Після цього Боб розкладає 372 наступним чином. Спочатку він вибирає найбільший елемент з w, який менший, ніж 372, і обчислює їх різницю. Далі він вибирає наступний найбільший елемент, який менший, ніж отримана різниця, і повторює ці дії, поки різниця стане рівна нулю.

372 - 354 = 18
18 - 11 = 7
7 - 7 = 0

Елементи, які були обрані з w , будуть відповідати 1 в двійковому записі вихідного тексту

01100001
Перекладаючи назад з двійкового запису, Боб отримує, нарешті, шукане  "a".

Примітки ред.

↑ Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525-530.
↑ Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279-288. http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF [Архівовано 24 квітня 2005 у Wayback Machine.]

Див. також ред.

[1] Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525-530.

[2] Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279-288. http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF [Архівовано 24 квітня 2005 у Wayback Machine.]

[1]

[2]