Ранцевые криптосистемы

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

Самая известная ранцевая криптосистема — криптосистема с открытым ключом Меркла-Хеллмана , одна из первых криптосистем с открытым ключом , опубликованная в том же году, что и криптосистема RSA . Однако эта система была нарушена несколькими атаками: одна со стороны Шамира , один от Адлемана, и атака низкой плотности .

Однако существуют современные ранцевые криптосистемы, которые до сих пор считаются безопасными: среди них — Насако-Мураками 2006.

Считается, что ранцевые криптосистемы, если они не подлежат классическому криптоанализу, сложны даже для квантовых компьютеров. Это не относится к системам, которые полагаются на факторизацию больших целых чисел, таких как RSA , или вычисление дискретных логарифмов , таких как ECDSA , задачи, решаемые за полиномиальное время с помощью алгоритма Шора .

Библиография

• Адлеман, Леонард (1983). «О взломе итерированной криптосистемы Меркла-Хеллмана с открытым ключом». Достижения криптологии . Спрингер. стр. 303–308. дои : 10.1007/978-1-4757-0602-4_29 . ISBN  978-1-4757-0604-8 .
• Шамир, Ади (1982), «Алгоритм с полиномиальным временем для взлома основных криптосистем Меркла-Хеллмана», Focs '82 : 145–152, doi : 10.1109/SFCS.1982.5
• Насако, Т.; Мураками, Ю. (2006), «Рюкзачная криптосистема высокой плотности с использованием комбинированного люка» , Японское общество промышленной и прикладной математики , 16 (4): 519–605, doi : 10.11540/jsiamt.16.4_591