Залог секретного бита с применением однонаправленной функции

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 09:01, 12 мая 2016.

Залог секретного бита (Bit commitment, BC) - небольшой (базовый) протокол. Как правило, на его основе строят более сложные протоколы[1]. Применение протокола BC исключает возможность повторной платы одной и той же "монетой" (т.е. главной проблемы системы электронных платежей[2]). Идея подобной реализации заключается в том, что если Клиент повторно потратит электронную монету, то теряется его анонимность ( здеcь предполагается, что общение ведется между двумя сторонами: Банком и Клиентом).

Еще одно преимущество данного протокола: он позволяет обойтись без использования третьей (доверенной) стороны (в отличие, от, например, протокола "бросание монеты по телефону").

Принцип работы протокола

Предположим, что передача ведется от к . Пусть однонаправленная функция (т.е. легко вычисляется ее образ, при условии, что невозможно найти ее прообраз).




Момент времени  :












Вырабатывает 2 случайные строки;
выбор (0 или 1), однако не обязательно закладывать бит - можно и более сложную информацию
Передает:
особо влияет на стойкость системы.






Когда получил , не может узнать, каков выбор А, т.к. тогда ему бы пришлось найти

Момент времени  :








 

свой выбор ()

Момент времени  :
















Подставляет:  ? Если да, то выбрал то, что нужно. не может обмануть



Пусть находит значения . Тогда сможет обмануть - ; предъявив сначала , скрыв b, затем предъявив или

  • Коллизия:

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

Хэш-функции

Для хэш-функций помимо однонаправленности вводится дополнительное свойство:

  1. Устойчивость к коллизиям
  2. Устойчивость к нахождению прообраза
  3. Устойчивость к нахождению второго прообраза: пусть знаем: - должно быть очеь сложно найти при

Один из претендентов на отечественный стандарт на хэш-функцию: Whirpool (участвовал в NESSIE; для него не найдено хороших атак; описание - в открытом доступе, согласно условиям конкурса (коммерческое использование и патентование не допускается); по-прежнему, неясным остается вопрос касательно его быстродействия и хорошей реализации на современной элементной базе).

ГОСТ Р 34.11-94

- старший вектор хэширования, открытый (необходим для разделения хэшей по системам и др.).

Функция, отображающая любую двоичную последовательность в вектор длины 256 бит.

  • А. Пошаговая функция хэширования.
  • В. Итеративная процедура вычисления значения h ("хэш-кода", "message digest")
где: - "куски" хэшируемого текста,
- результат с предыдущего такта.

Примечания

  1. Например, протокол Орамото или достаточно сложные протоколы для систем электронных платежей, где основная цель - решение проблемы повторной траты монеты.
  2. http://ru.bmstu.wiki/RSA_(криптосистема)#.Протокол_электронных_платежей