Batohy kryptosystémy - Knapsack cryptosystems - Wikipedia
Batohy Cryptosystems jsou kryptosystémy jehož bezpečnost je založena na tvrdosti řešení batoh problém. Zůstávají docela nepopulární, protože jednoduché verze těchto algoritmů byly několik desetiletí prolomeny.[1] Tento typ kryptosystému je však dobrým kandidátem postkvantová kryptografie.[Citace je zapotřebí ]
Nejznámějším kryptosystémem batohu je Kryptosystém veřejného klíče Merkle-Hellman, jeden z prvních kryptosystémy veřejného klíče, publikovaný ve stejném roce jako Kryptosystém RSA. Tento systém však byl rozbit několika útoky: jedním z Shamire,[2] jeden od Adlemana,[3] a útok s nízkou hustotou.
Existují však moderní kryptosystémy batohu, které jsou dosud považovány za bezpečné: mezi nimi je Nasako-Murakami 2006.[4]
Pokud se na kryptosystémy batohu nevztahuje klasická kryptoanalýza, je to považováno za obtížné i pro kvantové počítače. To neplatí pro systémy, na které se spoléhají factoring velká celá čísla, jako RSA nebo výpočetní technika diskrétní logaritmy, jako ECDSA, problémy řešené v polynomiální čas s Shorův algoritmus.[5]
Reference
- ^ Schneier, Bruce (2004). Tajemství a lži. Wiley Publishing, Inc. str.95. ISBN 978-0-471-25311-2.
- ^ Shamir 1982.
- ^ Adleman 1982.
- ^ Nasako & Murikami 2006.
- ^ Shor, Peter (1997). "Algoritmy polynomiálního času pro Prime Factorization a diskrétní logaritmy na kvantovém počítači". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph / 9508027. doi:10.1137 / s0097539795293172. S2CID 2337707.
Bibliografie
- Leonard Adleman (1982), „O rozbití titrovaného kryptosystému veřejného klíče Merkle-Hellman“, Crypto'82Springer: 303–308, doi:10.1007/978-1-4757-0602-4_29, ISBN 978-1-4757-0604-8
- Adi Shamir (1982), „Polynomiální časový algoritmus pro rozbití základních kryptosystémů Merkle-Hellman“, Focs'82: 145–152, doi:10.1109 / SFCS.1982.5
- T. Nasako; Y. Murakami (2006), „Kryptosystém batohu s vysokou hustotou využívající kombinované padací dveře“, Japonská společnost pro průmyslovou a aplikovanou matematiku, 16 (4): 519–605, doi:10.11540 / jsiamt.16.4_591
 | Tento článek týkající se kryptografie je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |