Однонаправленная функция с секретом

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

1976 г. - впервые предложена в статье "New Directions In Cryptography" (Diffie, Hellman).

TemplateDifinitionIcon.svg Определение «Определение - Однонаправленная функция с секретом (Trapdoor one-way function, TOWF)»
TOWF - функция т.ч. при известной дополнительной информации о ней можно найти полиномиальные алгоритмы:
позволяющие легко вычислять области определения и прообраз области значений этой функции. Однако без знания дополнительной информации k, даже при известном алгоритме почти для всех возможных значений и нахождение вычислительно невозможно (т.е. не известно такого полиномиального алгоритма).

Применение TOWF




- секретный ключ зашифрования
Алгоритм зашифрования известен
Получает информацию из справочника
передается в справочник открытых ключей на хранение
Расшифровывает: (по открытому каналу) Шифрует: открытый текст
Злоумышленник
(знает алгоритм преобразования, но не знает значит, не может восстановить преобразование)

В данной схеме сохраняется секретность, но нарушается аутентичность: А точно не знает, кто послал ему сообщение: В или кто-либо другой.

Система асимметричного шифрования

TemplateDifinitionIcon.svg Определение «Система асимметричного шифрования»
Системой асимметричного шифрования называется тройка детерминированных алгоритмов , где:
- алгоритм генерации ключей, необходимый только на "входе".

Вход: - секретный параметр и случайный начальный вектор фиксированной длины, соответственно.

Выход: - ключевая пара, состоящая из открытого и секретного ключей, соответственно.

- алгоритм шифрования.

Вход: - сообщение (открытый текст), - случайный вектор фиксированной длины.

Выход: - шифртекст.

- алгоритм расшифрования.

Вход: - секретный ключ, - шифртекст.

Выход: - открытый текст либо символ ошибки.

Для должно быть

Цифровая подпись

TemplateDifinitionIcon.svg Определение «Электронно-цифровая подпись»
Электронно-цифровая подпись — реквизит электронного документа, позволяющий установить отсутствие искажения информации в электронном документе с момента формирования ЭЦП и проверить принадлежность подписи владельцу сертификата ключа ЭЦП. Значение реквизита получается в результате криптографического преобразования информации с использованием закрытого ключа ЭЦП.

Использование цифровой подписи позволяет осуществить:

  • Контроль целостности передаваемого документа
  • Защиту от изменений (подделки) документа
  • Невозможность отказа от авторства
  • Доказательное подтверждение авторства документа

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

Ранцевая система

Ранцевая криптосистема Меркля-Хеллмана была разработана Ральфом Мерклем и Мартином Хеллманом в 1978 году. Это была одна из первых криптосистем с открытым ключом, но она оказалась криптографически нестойкой и, как следствие, не приобрела популярности.

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

и

Задача состоит в том, чтобы найти такой бинарный вектор

чтобы

.

Меркль использовал не произвольную последовательность , а возрастающую (superincreasing), то есть такую, что

Нетрудно убедиться, что для такого набора чисел решение задачи является тривиальным. Чтобы избавиться от этой тривиальности и понадобилось ввести "секретный ключ", а именно два числа: такое, что и такое, что . И теперь вместо первоначального набора чисел будем использовать числа . В оригинальных статьях Меркль рекомендовал использовать порядка 100, где - число элементов возрастающей последовательности ("размер" рюкзака).

В итоге получаем: открытый ключ – (), закрытый ключ - ().

Генерация ключа

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

.

Далее случайным образом выберем целые взаимно простые числа и такие, что

.

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

Теперь построим последовательность

где каждый элемент вычисляется по следующей формуле

.

β будет открытым ключом, в то время как закрытый ключ образует последовательность ().

Шифрование

  • сообщение
  • вычисляем

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

  • вычисляем
  • решаем задачу для для возрастающей последовательности (), т.е. находим двоичное число