2016•Research Repository Saint Petersburg State University (Saint Petersburg State University)Open access
Knapsack public key cryptosystem
Терехов Антон Юрьевич, Terekhov Anton
Open full text 0 citations
Abstract
Распространённая на данный момент система с открытым ключом RSA основана на задаче факторизации, которая находится под угрозой решения при использовании квантовых компьютеров. Криптосистемы, основанные на задаче о ранце, могут оказаться хорошей альтернативой. В данной статье исследуется ранцевая криптосистема Меркла-Хеллмана, одна из первых криптосистем с открытым ключом. На настоящий момент известна атака этой системы, работающая за полиномиальное время, однако не каждый полиномиальный алгоритм возможно выполнить за разумное время. В статье описываются алгоритмы и детали реализации этой атаки, а также эмпирические оценки времени её работы.
Open-access reader