Interested Article - Задача о рюкзаке в криптографии

Задача о рюкзаке (или Задача о ранце ) в криптографии ( англ. Knapsack problem ) — это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом . Он носит название криптосистема Меркла-Хеллмана. Для шифрования сообщений использовалось решение задачи о рюкзаке, как известно, являющейся NP-сложной . Потому, как считалось, она могла обеспечивать криптостойкость системы. На данный момент создано множество рюкзачных криптосистем. Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными.

История

Проблема рюкзака лежит в основе первого алгоритма асимметричного шифрования (или иначе шифрования с открытым ключом). Идея криптографии с открытыми ключами была выдвинута американскими криптографами Уитфилдом Диффи , Мартином Хеллманом и независимо от них Ральфом Мерклом . Впервые она была представлена Диффи и Хеллманом на Национальной компьютерной конференции ( англ. National Computer Conference ) в 1976 году, в том же году была опубликована их совместная работа на эту тему — «New Directions in Cryptography» ( рус. «Новые направления в криптографии» ) . Статья Меркла «Secure Communication Over Insecure Channels» ( рус. «Безопасная связь по незащищённым каналам» ) была опубликована только в 1978 году . Новизна по отношению к распространённым на тот момент симметричным криптосистемам заключалась в использовании парных ключей — секретного ( англ. private key, secret key, SK ) и открытого ( англ. public key, PK ), создаваемых пользователем. Секретный ключ, используемый для расшифровки информации, пользователь должен скрывать, тогда как открытый ключ, необходимый лишь для шифрования, может быть общедоступным. Во многих криптосистемах из секретного ключа получают открытый ключ .

Первый алгоритм для шифрования на основе задачи о рюкзаке был разработан Мерклом и Хеллманом в 1978 году и получил название « Алгоритм Меркла-Хеллмана » . Он был опубликован в одностадийном ( англ. singly-iterated ) и мультистадийном вариантах ( англ. multiply-iterated ). Алгоритм мог быть использован только для шифрования, но израильский криптоаналитик Ади Шамир адаптировал его для использования в цифровых подписях . После опубликования схемы Меркл предложил вознаграждение в 100 долларов тому, кто удачно осуществит взлом одностадийного алгоритма. В 1982 году Шамир осуществил успешную атаку и получил обещанное вознаграждение. Но даже после его уплаты Меркл был уверен в криптостойкости мультистадийной системы и предложил 1000 долларов в случае её удачного взлома. В 1984 году американский математик сумел осуществить взлом для сорока-стадийного варианта чуть более чем за 1 час на машине Cray-1 .

Независимо друг от друга ещё в 1980 году американский математик Рон Грэм и Ади Шамир обнаружили способ повысить криптостойкость схемы Меркла-Хеллмана, но уже в 1983 году полученная схема Грэма-Шамира была взломана американским учёным Леонардом Адлеманом . Однако поиски модификаций, лишённых недостатков схемы Меркла-Хеллмана, продолжились. В 1985 году британский адъюнкт-профессор Родни Гудман и американский инженер Энтони Маколи создали схему, основанную на модульных рюкзаках с секретной лазейкой не на основе , а с использованием китайской теоремы об остатках .

Впоследствии стало ясно, что схема уязвима для атак, основанных на поиске секретных лазеек. Однако в 1990 году предложил новую схему на основе той же задачи модульного рюкзака. Она была взломана уже в следующем году , и независимо друг от друга, слегка различными методами. Помимо использования модульных рюкзаков были попытки применения других видов рюкзака.

Так, в 1986 году опубликовал рюкзачную криптосистему на основе алгебраической теории кодирования, которая в дальнейшем была взломана, а в 1988 году и разработали криптосистему с использованием мультипликативного рюкзака . Эта идея оказалась удачной и пока система на мультипликативных рюкзаках не взломана.

В 2001 году , и Масао Касахара предложили усовершенствование схемы Мории-Касахары на основе мультипликативных рюкзаков с использованием алгоритма Schalkwijk .

Также удачной оказалась идея , и , предложивших в 1991 году многостадийную рюкзачную криптосистему ( англ. multistage trapdoor knapsack cryptosystem ). В ней фиксируется рюкзачный вектор для каждого этапа, и выход (зашифрованный текст) после каждой стадии алгоритма используется в качестве входных данных (текста) на следующий этап. Успешной атаки на данную схему не известно (на 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). Тогда справедливо, что:

  1. Задача о рюкзаке с входными данными (A,α) разрешима за линейное время, и если решение существует, то оно единственно;
  2. Задача о рюкзаке с входными данными (B,β) имеет не более одного решения;
  3. Если существует решение для входа (B,β), то оно совпадает с единственным решением для входа (A,α).


Пример

Создание вектора B из вектора A .

Пусть задан сверхрастущий вектор (секретный ключ) с . Сумма его компонент равна 55 205. Выбираем , а . Тогда условие выполнено.

Находится по формуле . В данном случае:

1061 * 25 236 — 1= 485 * 55 207

Следовательно .

Вычисляется открытый ключ B по и α =(uβ,modm). Например, для

и α1 = 1061 * 4579 = 103 + 88 * 55 207 = 103,

и α6 = 1061 * 17 953 = 1718 + 345 * 55 207 = 1718,

и α10 = 1061 * 53 620 = 27 610 + 1030 * 55 207 = 27 610

Сделав аналогичные вычисления для остальных элементов получается вектор

Шифрование

Применим открытый ключ B и зашифруем сообщение: DEATH GODS EAT ONLY APPLES

Вначале используется цифровое кодирование, пробелу присваивается значение 0, буквам от A до Z — значение от 1 до 26. Цифровые коды выражаются двоичными наборами. Так как вектор B имеет длину 10, то может быть использован для шифрования блоков сразу из двух букв. Шифр блока, как и раньше, получается суммированием весов предметов вошедших в рюкзак.

Блок исходного текста Двоичный код Шифр блока
DE 00100 00101 95097
AT 00001 10100 61616
H 01000 00000 50316
GO 00111 01111 207922
DS 00100 10011 118572
E 00000 00101 70173
AT 00001 10100 61616
O 00000 01111 124980
NL 01110 01100 155433
Y 11001 00000 82005
AP 00001 10000 45063
PL 10000 01100 53864
ES 00101 10011 149480

Расшифровка

Расшифруем первое число 95 097.

1061* 95 097 = 1827 * 55 207 + 34 728

Рассматривается задача о ранце (A,34728). Решение получается просмотром рюкзачного вектора A справа налево. Когда число в левом столбце становится не меньше текущей просматриваемой компоненты A, пишется 1, а новое число в левом столбце получается вычитанием компоненты из предыдущего числа. В противном случаем пишется 0 и число в левом столбце не меняется. Результат приведён в таблице:

Число Компонента A Символ
34728 27610 1
7118 13807 0
7118 6907 1
211 3449 0
211 1718 0
211 863 0
211 430 0
211 211 1
0 107 0
0 103 0

Считыванием правой колонки снизу вверх получается двоичный вектор 00100 00101,то есть DE.

Предположим, мы попытались действовать в обратном порядке. Шифрование осуществлялось бы с помощью вектора A и получалось некое число a. Но тогда пара (B,a) не обладала решением, так как нельзя вывести обычное равенство чисел из их равенства по модулю.

Криптостойкость

Безопасность рюкзачных систем

Для небольших рюкзачных векторов, задачу о ранце легко решить даже вручную. Реальный рюкзак должен содержать большое число элементов. Вскрытие такого рюкзака при помощи грубой силы, т.е перебором, будет трудной (невозможной) задачей. Однако рюкзачные системы не являются безопасными для криптоанализа . Шамир и Циппел ( англ. Zippel ) обнаружили, что зная числа ( «секретную лазейку» ) можно восстановить сверхвозрастающий вектор по нормальному открытому вектору . Важно то, что числа («секретная пара») не обязательно должны быть теми же, что использовались при создании системы легальным пользователем. Достаточно найти любую пару , такую что даст нам сверхрастущий вектор .

Как искать секретную лазейку

Задача: известен рюкзачный вектор , используемый в качестве открытого ключа. Он получен из A — сверхвозрастающего вектора, сильным модульным умножением относительно модуля m и числа t. Нужно найти не известные нам A,t, m, а точнее m и (по ним можно вычислить A). Зная их, можно расшифровать криптотекст .

Нахождение секретной пары

Описанный ниже подход был предложен А.Шамиром . Получаемый алгоритм будет работать за полиномиальное время. Однако следует быть осторожными в выборе размера вектора B, относительно которого алгоритм является полиномиальным. Стоит помнить, что размер вектора B зависит от числа компонент n и размеров . Следовательно существуют ограничение на их выбор

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

Для построения алгоритма не обязательно искать u и m, в действительности использованные для шифрования. Подойдет любая пара (u, m), назовем её секретной парой , удовлетворяющая отграничения на сильное модульное умножение в отношении B, что вектор A в результате этого умножения свехрастущий, а m больше суммы его компонент. После нахождения хотя бы одной секретной пары, применяем лемму и начинаем расшифровку. Существование её очевидно, так как создатель криптосистемы использовал одну такую пару при шифровании.

Для наглядности построим графики функций . Это прямолинейные отрезки с точками разрыва , .

Для нахождение секретной пары строится график функции , который имеет пилообразную форму

Вспоминая, что и запишем:

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

Для , значение близко к минимуму функции . Тогда два минимума функций и близки друг к другу. Таким образом, можно рассмотреть и остальные пилообразные кривые. Ясно, что минимумы всех этих кривых близки друг другу. Можно построить малый интервал, содержащий «точки накопления» минимумов пилообразных кривых . Исходя из этого малого интервала, находятся и значение из секретной пары.

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

Алгоритм нахождения секретной пары:

1) Отыскание кандидатов для целого , таких, что -й минимум функции -искомая точка накопления.

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

В первой части алгоритма не обязательно рассматривать сразу все , следует ввести параметр и рассматривать компонент.

-координата -го минимума на кривой .

Условие близости минимумов кривых и можно записать следующим неравенствами:

,

,

Умножим первое неравенство на :

.

Всего таких неравенств , по одному для каждого

Так, первая часть алгоритма дает все такие натуральные , для которых существуют натуральные , такие что все неравенств выполняются.

2) Последовательная проверка каждого из кандидатов.

Во второй части алгоритма проверяются все . Кандидат будет отброшен, если для некоторого нет минимума кривой , лежащего около -го минимума кривой .

Зафиксируем . Упорядочиваем по возрастанию все точки разрыва в интервале . Возьмем две соседние точки из отсортированного списка и . В образованном ими интервале , каждая кривая — прямолинейный отрезок (уравнение описывают эти отрезки).

Исходя из вышесказанного, запишем систему неравенств:

— условие сверхроста

Чтобы два числа и образовывали секретную пару, необходимо и достаточно, чтобы принадлежала построенному таким образом для некоторой пары интервалу. , кандидат из первой части алгоритма, а индекс точки из отсортированного списка точек, соответствующего данному .

Поиск закончится, когда будет найден не пустой интервал .

Пример .

Пускай открытый ключ из трех компонент

1) Согласно приведённым выше неравенствам:

,

, , .

В таблице перечислены наименьшие значения такие, что неравенства выполняются:

p 1 2 3 4 5 6
E 5 3 2 2 3 5

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

Запишем неравенства:

Константы меняются в пределах , , в зависимости от выбора интервала.

Применяя обозначения , , перепишем неравенства в более простой форме:

Соберем в таблицу все значения констант для разных интервалов:

Интервал 1/7 2/7 1/3 3/7 1/2 4/7 2/3 5/7 6/7 1
i' 0 1 2 2 3 3 4 4 5 6
i 0 0 0 1 1 1 1 2 2 2
i 0 0 0 0 0 1 1 1 1 1
i 1 2 3 4 5 6 7 8 9 10
j 0 1 2 1 2 2 3 2 3 4
k 0 1 2 3 4 3 4 5 6 7
12u<i PART PART NOT NOT NOT NOT PART NOT PART NOT
4u<j NOT PART SAT NOT SAT NOT SAT NOT PART SAT
8u<k NOT NOT NOT PART SAT NOT NOT NOT PART PART

В последних трех строках указано, выполняется или нет каждое из неравенств : SAT - выполняется, PART-частично выполняется (появляется, когда неравенство выполняется на правой части подынтервала), NOT - не выполняется (появляется когда неравенство не выполнено на левой части подынтервала).

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

Варианты задачи о ранце в криптографии

1) Рюкзак Меркла-Хеллмана ( англ. Merkle-Hellman Cryptosystem ).

Открытый ключ A — сверхвозрастающий вектор, секретный ключ B получен из A сильным модульным умножением.

2) Рюкзак Грэм-Шамира ( англ. Graham-Shamir Cryptosystem ) .

Открытый ключ A — сверхвозрастающий вектор. Его элементы записываются в битовом представлении. Далее генерируются случайные числа, называемые шумом. Их битовое представление дописывается к битам рюзачного вектора слева, то есть в старший разряд.

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

Бинарное представление Со случайным префиксом
1 = 001 101 001 = 41
3 = 011 111 011 = 59
5 = 101 100 101 = 37

Получившийся рюкзачный вектор не обладает свойством сверхвозрастания. Следовательно, добавление случайного шума скрывает свойство сверхвозрастания у исходного вектора A и схема становится безопаснее .

3) Рюкзак Мории-Касахара ( англ. Morii-Kasahara Cryptosystem )

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

Пусть вектор . Выбираем , простое число (в этой схеме ) и , такое что . Секретный ключ B получаем из A по формуле , то есть . Пусть шифруемое сообщение , тогда шифр .

4) Рюкзак Гудмана-Макколи ( англ. Goodman-McAuley Cryptosystem ) .

Как и в первой схеме в рюкзаке Гудмана-Макколи для получения открытого ключа из секретного используется модульное умножение, однако секретный ключ не является сверхвозрастающим вектором. Схема основана на сложности целочисленной факторизации, поэтому схожа с криптосистемой RSA.

5) Рюкзак Накаше-Штерна ( англ. Naccache-Stern Cryptosystem ) .

Данная схема объединяет два метода: рюкзак Меркла-Хеллмана и алгоритм Полига-Хеллмана . Дано простое число , S подмножество ( англ. subset product ), а рюкзачный вектор , где все взаимно простые числа. Нужно найти бинарный вектор , такой что

6) Рюкзак Шор-Ривеста ( англ. Chor-Rivest )

Основаны на алгебре в конечных полях (полях Галуа) . Пусть и открытый ключ A состоит из элементов подполя поля , то есть . Секретный ключ состоит из следующих элементов:

  • элемент из с алгебраической степенью
  • генератор из
  • целое из

Тогда открытый ключ B состоит из элементов .

Будущее рюкзачных систем

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

Для рюкзака весом одна итерация алгоритма Меркла-Хеллмана может быть более чем в 100 раз быстрее RSA (с модулем в 500 бит) .

Примечания

  1. Diffie W. , Hellman M. E. (англ.) // / — IEEE , 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN ; —
  2. , p. 19.1.
  3. , p. 19.2.
  4. Габидулин Э. М. , , : учебное пособие М. : МФТИ , 2011. — 225 с. — ISBN 978-5-7417-0377-9
  5. Kin Ming Lai. (англ.) . — 2001. 17 ноября 2012 года.
  6. . (англ.) . — 2001.
  7. (англ.) . (недоступная ссылка)
  8. (англ.) . — springer.
  9. (англ.) . — springer. 2 апреля 2016 года.
  10. Masakatu Morii,Masao Kasahara. (англ.) . — springer. 28 декабря 2014 года.
  11. Shinya Kiuchi, Yasuyuki Murakami, Masao Kasahara. (англ.) . 17 ноября 2015 года.
  12. Hussain Ali Hussain, Jafar Wadi Abdul Sada, Klipha S. M. (англ.) . 26 декабря 2014 года.
  13. Harald Ritter. (англ.) . 31 марта 2012 года.
  14. Davis Naccache, Jacques Stern. (англ.) . — 2006. 9 марта 2012 года.
  15. (англ.) . 5 марта 2016 года.
  16. . Дата обращения: 2 ноября 2015. 17 августа 2015 года.
  17. , p. 76.
  18. , p. 103.
  19. , p. 104.
  20. , p. 113.
  21. , p. 112.
  22. , p. 114.
  23. , p. 117.
  24. B. Chor, R. L. Rivest. (англ.) . — 1988. 13 апреля 2013 года.
  25. Serge Vaudenay. (англ.) . (недоступная ссылка)
  26. A. M. Odlyzko. (англ.) . 31 мая 2012 года.

Литература

на русском языке
  1. М. : , 2006. — С. 160—163. — 576 с. — ISBN 978-5-8459-0987-9
  2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-ое. — М. : , 2006. — С. 1296. — ISBN 0-07-013151-1 .
  3. Роберт Седжвик . Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е. — Россия, Санкт-Петербург: , 2002. — С. 688. — ISBN 5-93772-047-4 , 0-201-35088-2.
  4. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М. , 1974. — 232 с.
  5. В. Н. Бурков, Д. А. Новиков. . — 2001. — С. 28.
  6. С. Окулов. Программирование в алгоритмах. — 2007. — С. 383.
  7. Б. Шнайер. . — 2-ое. — 2002. от 28 февраля 2014 на Wayback Machine
  8. А. Саломаа. = Public-Key Cryptography. — Springer-Verlag, 1990. — С. 102—150. от 19 ноября 2011 на Wayback Machine
  9. Коблиц Н. — 2-е издание — М. : , 2001. — 254 с. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5
на английском языке
  1. Silvano Martelo, Paolo Toth. Knapsack problems. — Wiley, 1990. — 306 с.
  2. David Pisinger. . — 1995. от 22 декабря 2012 на Wayback Machine
  3. Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack problems. — 1995.

Ссылки

  • Денис Алексеев. . « Яндекс.Народ ». Дата обращения: 6 декабря 2012. 7 января 2013 года.
  • Михаил Чегодарь. . Underground InformatioN Center. Дата обращения: 6 декабря 2012.
Источник —

Same as Задача о рюкзаке в криптографии