插值攻击

在密码学里，插值攻击是一种用来对付分组密码的密码分析手法。

插值攻击使用一个代数函数来代表一个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）.