Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
§11.4. Шифрсистемы на основе “проблемы рюкзака"
“Проблема рюкзака” (или “ранца”) может быть сформулирована следующим образом. Пусть задано множество натуральных чисел А = {а19а2,...9ап} и натуральное число S. Требуется установить, имеется ли такое подмножество множества А, сумма элементов которого была бы равна S. Эквивалентной является следующая формулировка: существует ли такой набор чисел х;є{0,1}, і<п9 для которого
Данная проблема получила свое название в связи с тем, что поставленная задача может быть переформулирована также в следующем виде. Имеется набор предметов с известными весами и рюкзак, который может выдержать вес, не превышающий заданной величины. Можно ли выбрать набор предметов для погрузки в рюкзак так, чтобы они в точности имели максимально возможный вес.
“Проблема рюкзака” является весьма сложной, ее решение с полиномиальной сложностью в настоящее время не известно.
п
і=1
323
І лава 11
Идея построения системы шифрования на основе “проблемы рюкзака” заключается в выделении некоторого подкласса задач об укладке рюкзака, решаемых сравнительно легко, и “маскировки” задач этого класса (с помощью некоторого преобразования параметров) под общий случай. Параметры подкласса определяют секретный ключ, а параметры модифицированной задачи — открытый ключ. В качестве легко решаемой задачи Р. Меркль и М. Хеллман в 1978 г. [Мег81] предложили задачу об укладке “супервозрастающего” рюкзака. Изложим ее суть.
Назовем супервозрастающей последовательность натуральных чисел (Jbl,Ь2,...,Ъп ), обладающую свойством
/-і
bt > ^bj, 2 < / < п .
7=1
Можно убедиться в том, что “проблема рюкзака” для супервозрастающей последовательности может быть решена с помощью процедуры, состоящей в выполнении следующих шагов:
1. Положить і = п .
2. Если / > 1, то положить X1 равным 1 и S равным
S — Ь{, если S >Ь{, и положить X1 равным 0 в противном случае.
3. Положить і равным / -1 и возвратиться к шагу 2.
В системе, основанной на проблеме рюкзака, величина п является параметром системы.
Для вычисления открытого и соответствующего секретного ключа каждый из абонентов системы осуществляет следующую последовательность действий.
324
Системы с открытыми ключами
1. Выбирает супервозрастающую последовательность
п
(bx,b2,...,Ьп) и модуль т , такой, что т > ^bl .
і=і
2. Выбирает случайное число W9 IcWcm-I9 такое, что НОД(Ж,т) = 1.
3. Выбирает случайную перестановку /г чисел {1,2,..., и}.
4. Вычисляет Cii =W • mod т для / = 1, л .
Открытым ключом является набор (а,,а2,...,а„), секретным ключом — набор (n9m9W.
Чтобы зашифровать сообщение M9 предназначенное для абонента А , абонент В осуществляет следующие шаги с помощью открытого ключа (aX9a29...9an) абонента А :
1. Представляет M в виде бинарной последовательности M = MxM2...Mrl длины п.
п
2. Вычисляет C = YuMrQl и направляет его к А .
і=і
Абонент А , получив С, вычисляет H = W~* Cmod т, а затем, решая “проблему рюкзака” для супервозрастающей последовательности, находит числа Z1 є {0,1}, такие, что
H = YlZrb,.
/ = 1
Биты последовательности M1 вычисляются по формуле
Ml=Zltil), і = \,п.
Корректность проведенной процедуры расшифрования вытекает из следующих рассуждений. Поскольку
325
І лава 11
H = W-' -C = W-' -YjM1 -a, ^ ?м, •KU)imodm)
I=I I= I
n
и OcH <т,то H = YjMr Ьящ , и, следовательно, алгоритм
/=і
решения “проблемы рюкзака” действительно находит биты открытого текста, переставленные в соответствии с перестановкой Tt.
Вместе с тем доказано, что существует алгоритм полиномиальной сложности, который может быть использован противником для получения открытого текста M по шифртексту С. Этот алгоритм, исходя из Cil, находит пару таких целых
чисел w19ml5 что отношение Ujml близко к отношению и/т
(где u = W~l modт, a W9 т являются частью секретного ключа). Кроме того, числа B1 =щ- Ctl (modm), 1 < / < л, образуют супервозрастающую последовательность. Эта последовательность затем используется противником вместо (6],...,?„) для дешифрования сообщения.
Контрольные вопросы
1. В чем состоят преимущества систем с открытыми ключами перед симметричными шифрсистемами?
2. Сложностью какой математической задачи определяется стойкость системы RSA?
3. К какому типу принадлежит схема шифрования, используемая в системе Эль-Гамаля? В чем ее преимущества?
4. Чем вызваны трудности в практической реализации системы Мак-Элиса?
5. Придумайте алгоритм вычисления ad(mod «), имеющий сложность 0(1п п).
6. Постройте пример шифра Эль-Гамаля для р = 127. Зашифруйте и расшифруйте выбранное Вами т < 126.
326
Глава 12
Идентификация
Все протоколы идентификации включают двух участников:
1) А — доказывающего — участника, проходящего идентификацию,
и
2) В — проверяющего — участника, проверяющего аутентичность доказывающего.
Целью протокола является проверка того, что проверяемым действительно является^.
С точки зрения проверяющего возможными исходами протокола являются либо принятие решения об идентичности доказывающего А, либо завершение протокола без принятия такового решения.
