33. Ранцевая криптосистема

Создатели– Меркль и Хеллман. Имеет множество модификаций, из которых одну удалось взломать.

В основекриптосистемы лежитзадача об укладке рюкзака:

Имеется рюкзак объема Vи группа предметов объемов

Задача– набить рюкзак до отказа.

Пример простой задачи об укладке рюкзака:

Есть рюкзак (напр., объемом 55) и ряд предметов объемов (напр., числа 3, 8, 12, 2, 32, 59)

55 = 3+8+12 +32

55 ↔ (111010) – единицы в тех битах, которые соответствуют исходным числам, входящим в разложение.

Очень простая задача об укладке рюкзака:

(числа в списке являются степенями 2)

Есть рюкзак объема 26 и ряд предметов (32, 16, 8, 4, 2, 1)

26 = 16+8+2

26  011010

Основные принципы получения односторонней функции с секретом и постороения на ее основе криптосистемы с открытым ключом на основе задачи об укладке рюкзака.

1. Составляется трудная задача Т, не решаемая за полиномиальное время.

2. Из Т выделяется легкая подзадача Т_л, имеющая простой алгоритм решения.

3. Путем «взбивания» Т_л, превращается в труднорешаемую Т_т, не имеющую никакого сходства с Т_л.

4. На основе ТТ определяется открытая функция зашифрования. Процедура получения Т_л из Т_т держится в секрете.

5. Конструируется криптосистема, причем таким образом, чтобы для противника процедура дешифрования заключалась в решении здачи Т_т, имеющей вид трудной задачи Т, а законный получатель, знающий секрет, решал бы задачу Т_л.

Трудная задача об укладке рюкзака (т.е. вычислительно неразрешимая)

Рюкзак объемом равным 42-разрядному десятичному числу. Список состоит из 100 чисел.

= 40 десятичных разрядов.

Противник должен перебрать чисел.

a0 =0120	001	00357	…
a1 =3520	002	00919	…
a2 =0140	004	00578	…

Нули в конце (выделенные) нужны для предотвращения возможного переполнения

Оставшиеся 100 цифр выбираются случайным образом.

Пример построения и использования рюкзачной криптосистемы

	a0=	28	01	07
√	a1=	17	02	03
√	a2=	53	04	09
√	a3=	49	08	01
	a4=	19	16	02

Открытый ключ:

Секретный ключ:(S,T)

Исходное сообщение:

Зашифрование:

Расшифрование:

1. Умножение шифровки на Sпо модулюT:

2. Перевод из 10-й формы в 2-ю:

34.Цифровые деньги. Структура и основные транзакции централизованной платежной системы

Электронная платежная система на основе цифровых денег

Проблемы:

1. Обеспечение анонимности и неотслеживаемости платежей→ слепая ЭЦП.

2. Защита номинала цифровой купюры:для каждого номинала используется своя пара ключей (открытый и закрытый).

3. Защита цифровой купюры от копирования (повторного использования):решается путём использования банком-эмитентом списка серийных номеров ранее использованных купюр. Эта проверка выполняется и на этапе 2 (когда сумма списывается со счёта и отправляется А) и на этапе 4 (когда на счёт В поступает соответствующая сумма).

4. Защита прав владельца купюры: решается способом полученияS. Абонент А формирует случайное число S’, называемое прекурсором. Хешируя прекурсор,Aформирует серийный номер купюры S = H(S’). Такая последовательность формирования S необходима для защиты прав владельца будущей купюры. Так как только он в силу свойств ХФ в случае возникновения споров может предъявить арбитру прекурсор, на основе которого сформирован серийный номер.

Процедура получения купюры:

1. А:

R – прекурсор (предварительная информация), случайное число.