Конференции ИВТ СО РАН

VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

27 - 29 ноября 2007 года, Новосибирск

Тезисы докладов

Информационные технологии

Анализ проблем противодействия атакам на рюкзачные криптосистемы

Амербаев В.М., Максименко А.В.

Московский Институт Электронной Техники (Москва)

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

Первая рюкзачная криптосистема была предложена в работе Меркля и Хеллмана в 1978 году. Их идея сразу привлекла многих криптографов во всем мире, так как предложенная схема была легко реализуема и имела высокую скорость работы. Однако в последствии практически все рюкзачные криптосистемы были взломаны.

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

а) не использовать быстрорастущие рюкзаки, идеальным вариантом является использование равномерно распределенных рюкзаков (критерий Варновского);

б) рюкзак должен иметь высокую разрядность элементов (больше 32 бит) и большую размерность;

в) плотность рюкзака должна превышать значение 0.9408, чем ближе плотность рюкзака к единице, тем лучше (критерий Костера- Одлизко).

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]