串流密碼相關攻擊法中同位檢查之研究

Abstract

串流密碼系統最常見的是由一個組合器和數個線性反饋移位暫存器 ( Linear Feedback Shift Register，簡稱 LFSR ) 共同組成的。如果其中某個 LFSR 的輸出序列和組合器的輸出序列有太高的相關時，可以用相關攻擊法重建該 LFSR 的起始狀態，即得到該部份的密鑰。 W. Meier 和 O. Staffelbach 提出了使用同位檢查方程式 ( parity check equation ) 的相關攻擊法。 本論文將就此攻擊法在實作上的限制，從幾個方面加以改進：一、計算更多的同位檢查方程式；二、確實計算每個點的同位檢查方程式數目和正確率；三、藉由足夠的線性獨立方程式所構成的聯立方程組，解得 LFSR 的起始狀態，捨棄利用各點之間的關係推算出 LFSR 的輸出序列和起始狀態的方法。

The commonest stream cipher system uses a keystream generator which consists of several LFSRs combined by a combining function. If there exists a measure of correlation between the output sequence of the keystream generator and an arbitrary LFSR, the initial state of the LFSR can be reconstructed by a correlation attack, that is, the partial key in the LFSR is determined. W. Meier and O. Staffelbach proposed a correlation attack method using parity check equations. In this thesis, we discuss the algorithm and its constraints, and then propose some improvements: computing more low-weight parity check equations, accounting the precise number of relations of each digit, and solving the system of linear independent equations from digits instead of calculating the whole output sequence and the initial state of the LFSR from the relations among the digits.