對一個背包公鑰密碼的格攻擊

摘要:對一個新的基于MerkleHellman背包密碼和Rabin公鑰密碼的背包公鑰密碼算法進行了安全性分析。使用格規(guī)約算法求解一個聯(lián)立丟番圖逼近問題和一個二元整數(shù)線性規(guī)劃問題就恢復(fù)出了該密碼算法的部分密鑰。重構(gòu)的部分密鑰可以解密任意密文。因此，該背包公鑰密碼算法是不安全的。

關(guān)鍵詞:公鑰密碼; 聯(lián)立丟番圖逼近; 整數(shù)線性規(guī)劃; 格規(guī)約

中圖分類號:TP3097文獻標志碼:A

文章編號:10013695(2010)04146603

doi:10.3969/j.issn.10013695.2010.04.073