插值攻擊

在密碼學裏，插值攻擊是一種用來對付分組密碼的密碼分析手法。

插值攻擊使用一個代數函數來代表一個S-Box，此函數可以用已知明文攻擊法取得樣本點，再用拉格朗日插值法產生。這個代數函數可能是在有限體上的二次函數、多項式函數或有理函數。也可以用選擇明文攻擊法取得樣本點，如此一來可以簡化所使用的代數函數，讓攻擊更有效率。

Thomas Jakobsen更進一步將概率的概念引入了插值攻擊法，用Madhu Sudan演算法來改善其對Reed-Solomon糾錯碼的解譯能力。如此一來插值攻擊在明文與密文的內容僅有極少的代數關係時也有效。

參考資料

Thomas Jakobsen, Lars Knudsen. The Interpolation Attack on Block Ciphers (PDF/PostScript). 4th International Workshop on Fast Software Encryption (FSE '97), LNCS 1267. Haifa: Springer-Verlag: pp.28–40. January 1997 [2007-07-03]. （原始內容存檔於2008-05-11）.
Thomas Jakobsen. Cryptanalysis of Block Ciphers with Probabilistic Non-linear Relations of Low Degree (PDF/PostScript). Advances in Cryptology — CRYPTO '98. Santa Barbara, California: Springer-Verlag: pp.212–222. August 1998 [2007-07-06]. （原始內容存檔於2008-04-09）.
Shiho Moriai, Takeshi Shimoyama, Toshinobu Kaneko. Interpolation Attacks of the Block Cipher: SNAKE (PDF). FSE '99. Rome: Springer-Verlag: pp.275–289. March 1999 [2007-09-16]. ^{[永久失效連結]}
Amr M. Youssef, Guang Gong. On the Interpolation Attacks on Block Ciphers (PDF). FSE 2000. New York City: Springer-Verlag: pp.109–120. April 2000 [2007-07-06]. （原始內容存檔 (PDF)於2012-09-16）.
Kaoru Kurosawa, Tetsu Iwata, Viet Duong Quang. Root Finding Interpolation Attack (PDF/PostScript). Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography (SAC 2000). Waterloo, Ontario: Springer-Verlag: pp.303–314. August 2000 [2007-07-06]. （原始內容存檔於2008-04-07）.