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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Опис[ред. | ред. код]

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

w = (w1, w2, …, wn) і s.

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

x = (x1, x2, …, xn), (xi = 0 або 1), щоб
.

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

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

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

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

.

Неважко переконатися, що для такого набору чисел рішення задачі є тривіальним. Щоб позбутися цієї тривіальності і знадобилося ввести «секретний ключ», а саме два числа: q таке, що и r таке, що НСД(r, q) =1. І тепер замість початкового набору чисел wi будемо використовувати числа bi=rwi mod q. В оригінальних статтях Меркль рекомендував використовувати n порядку 100, де n — число елементів суперзбільшеної послідовності («розмір» рюкзака).

В результаті отримуємо: відкритий ключ — (b1, b2, …, bn), закритий ключ — (w1, w2, …, wn; 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 = (w1, w2, …, wn).

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

.

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

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

β = (β1, β2, …, βn), де кожен елемент обчислюється за наступною формулою
βi = rwi mod q.

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

Шифрування[ред. | ред. код]

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

α = (α1, α2, …, αn), де  — це i-ий біт, тобто {0, 1}, обчислимо число c, яке і буде шифротекстом.

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

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

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

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

Звідси

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

Тоді

Сума всіх wi менше, ніж q. Звідси значення також знаходиться в інтервалі [0,q-1]. Таким чином, одержувач повинен визначити з умови, що

.

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

Приклад[ред. | ред. код]

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

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

Далі виберемо просте число 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.

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