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

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

Опис

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

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

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

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

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

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

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

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

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

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

Неважко переконатися, що для такого набору чисел рішення задачі є тривіальним. Щоб позбутися цієї тривіальності і знадобилося ввести «секретний ключ», а саме два числа: q таке, що ${\displaystyle 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 = (x1, x2, ..., xn) - обчислюємо y = b1x1 + b2x2 + bnx 

• Розшифровка

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

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

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

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

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

Шифрування

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

Розшифровка

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

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

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

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

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

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

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

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

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

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

β_i = rw_i mod q.

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

Шифрування

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

α = (α₁, α₂, …, α_n), де ${\displaystyle \alpha _{i}}$ — це i-ий біт, тобто ${\displaystyle \alpha _{i}{\boldsymbol {\in }}}${0, 1}, обчислимо число c, яке і буде шифротекстом.

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

Розшифровка

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

${\displaystyle 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 можливо з використанням розширеного алгоритму Евкліда. Далі одержувач шифротексту обчислює

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

Звідси

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

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

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

Тоді

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

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

${\displaystyle 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} - суперзбільшена послідовність. 

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

${\displaystyle \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". 

Примітки

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.]

Див. також

• Асиметричні алгоритми шифрування
• Шифрування