Задача о рюкзаке (или Задача о ранце) в криптографии () — это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом. Он носит название криптосистема Меркла-Хеллмана. Для шифрования сообщений использовалось решение задачи о рюкзаке, как известно, являющейся NP-сложной. Потому, как считалось, она могла обеспечивать криптостойкость системы. На данный момент создано множество рюкзачных криптосистем. Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными.
История Проблема рюкзака лежит в основе первого алгоритма асимметричного шифрования (или иначе шифрования с открытым ключом). Идея криптографии с открытыми ключами была выдвинута американскими криптографами Уитфилдом Диффи, Мартином Хеллманом и независимо от них Ральфом Мерклом. Впервые она была представлена Диффи и Хеллманом на Национальной компьютерной конференции () в 1976 году, в том же году была опубликована их совместная работа на эту тему — «New Directions in Cryptography» (). Статья Меркла «Secure Communication Over Insecure Channels» () была опубликована только в 1978 году. Новизна по отношению к распространённым на тот момент симметричным криптосистемам заключалась в использовании парных ключей — секретного () и открытого (), создаваемых пользователем. Секретный ключ, используемый для расшифровки информации, пользователь должен скрывать, тогда как открытый ключ, необходимый лишь для шифрования, может быть общедоступным. Во многих криптосистемах из секретного ключа получают открытый ключ.
Первый алгоритм для шифрования на основе задачи о рюкзаке был разработан Мерклом и Хеллманом в 1978 году и получил название «Алгоритм Меркла-Хеллмана». Он был опубликован в одностадийном () и мультистадийном вариантах (). Алгоритм мог быть использован только для шифрования, но израильский криптоаналитик Ади Шамир адаптировал его для использования в цифровых подписях. После опубликования схемы Меркл предложил вознаграждение в 100 долларов тому, кто удачно осуществит взлом одностадийного алгоритма. В 1982 году Шамир осуществил успешную атаку и получил обещанное вознаграждение. Но даже после его уплаты Меркл был уверен в криптостойкости мультистадийной системы и предложил 1000 долларов в случае её удачного взлома. В 1984 году американский математик Эрнест Брикелл сумел осуществить взлом для сорока-стадийного варианта чуть более чем за 1 час на машине Cray-1.
Независимо друг от друга ещё в 1980 году американский математик Рон Грэм и Ади Шамир обнаружили способ повысить криптостойкость схемы Меркла-Хеллмана, но уже в 1983 году полученная схема Грэма-Шамира была взломана американским учёным Леонардом Адлеманом. Однако поиски модификаций, лишённых недостатков схемы Меркла-Хеллмана, продолжились. В 1985 году британский адъюнкт-профессор Родни Гудман и американский инженер Энтони Маколи создали схему, основанную на модульных рюкзаках с секретной лазейкой не на основе сверхвозрастающих векторов, а с использованием китайской теоремы об остатках.
Впоследствии стало ясно, что схема уязвима для атак, основанных на поиске секретных лазеек. Однако в 1990 году Валттери Ниеми предложил новую схему на основе той же задачи модульного рюкзака. Она была взломана уже в следующем году Чи Е Мэном, Антуаном Жу и Жаком Штерном независимо друг от друга, слегка различными методами. Помимо использования модульных рюкзаков были попытки применения других видов рюкзака.
Так, в 1986 году опубликовал рюкзачную криптосистему на основе алгебраической теории кодирования, которая в дальнейшем была взломана, а в 1988 году Масакацу Мории и Масао Касахара разработали криптосистему с использованием мультипликативного рюкзака. Эта идея оказалась удачной и пока система на мультипликативных рюкзаках не взломана.
В 2001 году Синъя Киути, Ясуюки Мураками и Масао Касахара предложили усовершенствование схемы Мории-Касахары на основе мультипликативных рюкзаков с использованием алгоритма Schalkwijk.
Также удачной оказалась идея Хусейна Али Хусейна, Джафара Вади Абдулы Сада и М. Калифа, предложивших в 1991 году многостадийную рюкзачную криптосистему (). В ней фиксируется рюкзачный вектор для каждого этапа, и выход (зашифрованный текст) после каждой стадии алгоритма используется в качестве входных данных (текста) на следующий этап. Успешной атаки на данную схему не известно (на 2001 год).
Цюй Минхуа и Скотт Ванстоун в 1992 году предложили гибридную криптосистему которая основана прежде всего на задаче о ранце, но также включает в себя логарифмические подписи. В 1994 году Р. Блэкберн, Мерфи, Шон и Жак Штерн показали, что упрощённый вариант У-Вастон криптосистемы небезопасен. Эти криптосистемы были более тщательно изучены Фонг Нгуеном и Жаком Штерном в 1997 году.
Продолжались и улучшения классического алгоритма Меркла-Хеллмана. В 1994 году Ортон предложил модификацию мультистадийной схемы Меркла-Хеллмана, но уже через два года она была взломана Риттером.
В 1995 году были предложены сразу два новых подхода к задаче. Первый, на основе диофантовых уравнений принадлежит Линь Чжусину, Чжан Чжэньчэну, и Ли Цзятуну. Почти сразу Лай Цисун и Блэкберн, Мерфи, Шон и С. Г. Патерсон независимо друг от друга показали, что эта криптосистема не является криптостойкой.
, основанный на задаче о мультипликативном рюкзаке, был предложен и . Наккаше и Штерн предлагали 1024 немецких марок тому, кто успешно взломает их криптосхему, но информации о том, что кто-то получил это вознаграждение пока не было (на 2001 год).
В 1996 году Куникацу Кобаяси и Масаки Кимура предложили улучшенную рюкзачную криптосистему на основе новой концепции, где отправитель может выбрать ключ шифрования из целого набора ключей. Через два года Хидэнори Кувакадо и Хацукадзу Танака показали, что система потенциально небезопасна.
Последний вариант алгоритма был предложен Б. Шором и Р. Л. Ривестом в 2006 году. В 2002 году алгоритм Chor-Rivest считался безопасным.
В 2015 году появилось сообщение, что Нэйтан Хэмлин и Уильям Уэбб из Вашингтонского государственного университета создали рюкзачный алгоритм, лишённый недостатков прежних реализаций.
В дальнейшем было предложено много алгоритмов с открытым ключом, не основанных на рюкзачных системах. Наиболее известные из них: RSA, EIGamal и Rabin. Их можно использовать и для шифрования и для цифровых подписей. Однако они медленны и не подходят для быстрой шифровки/дешифровки больших объёмов сообщений. Решением этой проблемы являются гибридные криптосистемы, шифрование сообщений осуществляется быстрым симметричным алгоритмом со случайным ключом, а алгоритм на открытых ключах применяется для шифрования самого случайного (сеансового) ключа.
Постановка задачи Задача о рюкзаке звучит так: задан набор из различных положительных целых чисел. Пусть есть число так же целое и положительное. Задачей является нахождение такого набора , чтобы в сумме они давали ровно . Ясно, что решение этой задачи существует не всегда.
Согласно определению систем с открытым ключом, для успешного шифрования/расшифровки нужно иметь два ключа. Законный получатель сообщения знает секретный ключ A, а отправитель владеет лишь открытым ключом B. Как же помешать злоумышленнику дешифровать сообщение в случае если ему стал известен открытый ключ? Ответ прост, открытый ключ должен получаться из секретного ключа при помощи какого-либо преобразования f, обладающего следующими двумя свойствами: Легко вычислить , зная Определение , зная , вероятно, трудновыполнимая задача. В качестве трудновыполнимых задач обычно рассматриваются NP-полные задачи, поэтому задача о ранце подходит для построения систем на открытом ключе.
Шифрование с помощью задачи о рюкзаке Сообщение шифруется как решение набора задач о ранце.
Def.Рюкзачным вектором назовём упорядоченный набор из n предметов.
Для шифрования открытого текста в двоичном представлении его разбивают на блоки длины (например, соответствует 5-ти предметам в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие. Шифровать можно двумя способами:
1) Шифр сообщения получается возведением элементов рюкзачного вектора в степень соответствующих им бит шифруемого сообщения и дальнейшим перемножением результатов, то есть если , а сообщение , то шифром будет число . Такой способ называют мультипликативным.
2) Шифр сообщения получается путём умножения элементов рюкзачного вектора на соответствующий им бит шифруемого сообщения и дальнейшим сложением результатов, то есть если , а сообщение , то шифром будет число . Такой способ называют аддитивным.
Пример шифротекста, полученного по аддитивному алгоритму.
Пусть задан рюкзачный вектор Α = (3 4 6 7 10 11) с длинной n = 6. открытый текст 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 вещи в рюкзаке 3 4 6 7 10 11 3 4 6 7 10 11 3 4 6 7 10 11 3 4 6 7 10 11 шифротекст 3 + 4 + 6 + 7 + 10 = 30 6 + 7 = 13 0 11 Для заданного Α все криптосистемы есть числа, не превышающие 41, суммарный вес всех предметов в рюкзачном векторе. Для каждого исходного текста существует единственный криптотекст.
Сложность шифра заключается в том, что существуют две проблемы рюкзака: «лёгкая» и «трудная». «Лёгкая» проблема может быть решена за линейное время, «трудная» нет. Открытый ключ — «трудная» проблема, так как её легко применять для шифрования и невозможно для дешифровки сообщения. Закрытый ключ — «лёгкая» проблема, так как позволяет легко дешифровать сообщение. При отсутствии закрытого ключа нужно решать «трудную» проблему рюкзака. Меркл и Хеллман, используя модульную арифметику, разработали способ трансформации «лёгкого» рюкзака в «трудный».
«Лёгкая» проблема Для некоторых векторов Α задача о рюкзаке легко решаема. Этим свойством обладают сверхрастущие векторы.
Def. Рюкзачный вектор называется сверхрастущим, если для , т.е каждый член последовательности больше суммы предыдущих.
Пример
Пусть полный вес рюкзака , а рюкзачный вектор задан как сверхрастущий .
Для этого рюкзачного вектора алгоритм решения задачи о ранце прост. Берется самый большой вес, 52. Так как 52 < 70, то соответствующий предмет помещается в рюкзак. Свободное место в рюкзаке стало равным 70 — 52 = 18-ти. Далее берем предмет с весом 27. Так как 27 > 18, то в рюкзак этот предмет не войдёт. Третий предмет с весом 13 < 18 поместится в рюкзак, а свободного места останется 5. Следующий предмет с весом 6 не поместится. Аналогично предметы с весами 2 и 3 помещаются в рюкзак. Остаточный вес рюкзака стал 0, решение найдено!
«Трудная» проблема Нормальный рюкзак — не со сверхвозрастающим рюкзачным вектором A. Единственный способ решения такой задачи — это проверка всех возможных, пока не найдётся правильное решение. Самый быстрый алгоритм имеет экспоненциальную зависимость от числа предметов.
Криптосистема с открытым ключом на основе задачи о ранце Как и раньше под вектором A понимается секретный ключ, под вектором B открытый ключ.
Создание открытого ключа из закрытого Для целых и обозначим .
Пусть — сверхвозрастающий рюкзачный вектор. Введем целое число и натуральное число , такое что наибольший общий делитель .
Def. Если такое, что для , то говорят, что получен из сильным модульным умножением.
Создатель криптосистемы выбирает параметры так, чтобы A был сверхрастущим, а B получался из A сильным модульным умножением относительно m и t.
Справедлива Лемма: Пусть A — сверхрастущий вектор, а B получен из A сильным модульным умножением относительно m и t. Предположим, что u = 1/t, β — произвольное натуральное число и α =(uβ,modm). Тогда справедливо, что: Задача о рюкзаке с входными данными (A,α) разрешима за линейное время, и если решение существует, то оно единственно; Задача о рюкзаке с входными данными (B,β) имеет не более одного решения; Если существует решение для входа (B,β), то оно совпадает с единственным решением для входа (A,α).
Пример
Создание вектора B из вектора A.