Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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


1. Опис

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

w = (w 1, w 2,..., w n) і s.

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

x = (x 1, x 2,..., x n), (x i = 0 або 1),

щоб

s = \ sum_ {i = 1} ^ n x_iw_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 = r w i mod q. В оригінальних статтях Меркль рекомендував використовувати n порядку 100, де n - число елементів супервозрастающей послідовності ("розмір" рюкзака).

В результаті отримуємо: відкритий ключ - (b 1, b 2,..., b n), закритий ключ - (w 1, w 2,..., w n; q, r).

 - Повідомлення x = (x 1, x 2,..., x n) - обчислюємо y = b 1 x 1 + b 2 x 2 + b n x 
  • Розшифровка
 - Обчислюємо s = y 'r -1 mod q - вирішуємо завдання для s для супервозрастающей послідовності (w 1, w 2,...,' w n), тобто знаходимо двійкове число x 

Нагорода дісталася А. Шамір (Adi Shamir) після публікації їм у березні 1982 року повідомлення про розкриття ранцевий системи Меркле-Хеллмана з одного ітерацією. Зауважимо, що Шамір зумів побудувати ключ, не обов'язково рівний секретному, але дозволяє розкрити шифр.

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


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

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


1.2. Шифрування

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


1.3. Розшифровка

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

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

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

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

w = (w 1, w 2,..., w n).

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

q> \ sum_ {i = 1} ^ n w_i .

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

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

β = (β 1, β 2,..., β n),

де кожен елемент обчислюється за наступною формулою

β i = rw i mod q.

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


2.2. Шифрування

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

α = (α 1, α 2,..., α n),

де \ Alpha_i - Це i-ий біт, тобто \ Alpha_i \ boldsymbol {\ in} {0, 1}, обчислимо число c, яке і буде шіфротекста.

c = \ sum_ {i = 1} ^ n \ alpha_i \ beta_i.

2.3. Розшифровка

Щоб прочитати вихідний текст, одержувач повинен визначити біти повідомлення \ 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 r s \ 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 'і повторюємо ці кроки до тих пір, поки не обчислимо α.


3. Приклад

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


Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Меркле, Адольф
Криптосистема з відкритим ключем
© Усі права захищені
написати до нас
Рейтинг@Mail.ru