Pustaka Ilmiah Universitas Padjadjaran

Abstrak

Kriptosistem Knapsack

Merkle-Hellman Knapsack merupakan Kriptosistem yang dibuat oleh Merkle dan Hellman pada tahun 1980 Walaupun sistem ini, dan beberapa variannya, telah dipecahkan sekitar awal tahun 1980, tetapi masih layak untuk dipelajari dengan berbagai alasan.

Masalah yang mendasari matematika adalah masalah penjumlahan himpunan bagian dimana sangat berhubungan dengan masalah knapsack dari operasi pencarian (dengan demikian, “Knapsack” dalam nama dari system ini merupakan misnomer). Suatu masalah bisa dideskripsikan sebagai berikut. Jika setiap elemen dari himpunan S adalah suatu bilangan integer positif. Diberikan suatu himpunan bagian dari S, penjumlah dari elemen terdekat dari bagian himpunan bilangan menghasilkan bilangan integer yang berkoresponden dengan himpunan bagiannya.