14.5 Протокол порівняння двох величин без їх розголошення власниками

Нехай секретні невід’ємні цілі числа, що належать учасникам і відповідно. Треба з’ясувати, яке число більше, але не розкривати значень .

Параметри:

- - асиметрична криптосистема з множиною ключів відкритих ключів , алгоритмом зашифрування і алгоритмом розшифрування ;

- - відкритий ключ абонента ;

- - натуральне число ;

- - велике секретне натуральне число ;

- - розмір числа (кількість розрядів при запису у двійковій системі счислення);

- просте число , що підбирається у ході протоколу;

- .

Таблиця 14.5 Протокол порівняння двох величин без їх розголошення

1				Відправник вибірає і надсилає , та, у неявній формі, інформацію щодо .
				Отримувач підготовує дані виду . Просте число визначається після аналізу проміжних даних під час формування . Якщо аналіз показує, що не підходить, вибірається знову. Послідовність має наступну властивість: якщо , то , інакше, (разом з тим, значення абоненту невідоме).
2.
4				Відправник надає результат: , якщо , інакше, .

Отримувач, виходячи з та має підготувати послідовність , в який був би якимось чином відмічений елемент з індексом .

Щоб пояснити ідею, розглянемо спочатку елементарний приклад: послідовність, що у початку має п’ятірок, а решта елементів - сімки.

Можна визначити, чи елемент з номером є порівняний з 0 за модулем і, якщо так, зробити висновок, що , інакше, .

У нашому випадку потрібно ще приховати від учасників протоколу та сторонніх, тому алгоритм є більш складним.

Його суть полягає в тому, що реальна послідовність містить замість секретний випадковий елемент, залежний від , а інші елементи залежать від у складний спосіб через криптографічне перетворення.

Абонент будує єлементи послідовності , через відповідні елементи допоміжної послідовності . Під час побудови необхідно вибрати просте число та перевірити деяку умову.

Відповідність між елементами послідовностей встановлюється абонентом наступним чином:

Конкретно, спочатку обчислює , , а саме:

,

,

.

Очевидно, що , а всі різні, оскільки перетворення взаємно однозначне. Припустимо, передає послідовність . Тоді може обчислювати , та визначати . Якщо було змінено на , то значення не буде співпадати з істинним. Тому може визначити . Це означає, що треба перетворювати. і робить висновок, що , при , або що, якщо .

Для цього можна використати коректне - специфичне просте число, , таке, що виконується умова коректності виду .

Виберемо випадково. Позначимо . Зведення за модулем приховує значення .

Учасник покладає для і для .

Далі він перевіряє, чи коректне, якщо ні, вибираемо нове .

В результаті, послідовність , що передається від до має вид: .

Оскільки , то при і при , тобто знання та дозволяє знайти відповідь, а ці дані відомі абоненту .

Оскільки , , всі різні, то при ймовірність того, що серед є співпадіння не є високою.

Тому можна вважати, що всі різні, а це означає, що можливі співпадіння серед з’являються після додавання одиниць до єлементів з індексами більшими і мають вид .

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