基于MILP 的PICO 算法差分和線性區分器的搜索*

石康康，任炯炯，陳少真

戰略支援部隊信息工程大學，鄭州450001

1 引言

伴隨著物聯網的快速發展，以智能卡為代表的資源受限設備得到了廣泛的應用.在這些設備上，傳統密碼算法面臨著硬件實現成本高和電量耗費大等問題，為此，輕量級分組密碼算法應運而生，并逐漸成為了當前密碼領域討論最為活躍的熱點之一.差分分析[1]和線性分析[2]作為當前應用最為廣泛的密碼分析方法，在密碼分析過程中，毫無例外都需要尋找有效的區分器，即具有高概率或者高相關度的攻擊路徑.手動搜索的方法固然可行，但面臨著計算量大、效率低、耗時長、僅能給出部分條數區分器等諸多缺點，一批利用自動化搜索技術來尋找區分器的相關工具因此涌現出來，主要包括混合整數線性規劃(MILP)[3-5]和布爾可滿足問題(SAT)[6-8]等.

MILP 是一類在一定約束條件下求解目標函數最值的優化問題.該技術最早由Mouha 等人[3]引入到密碼分析中，通過MILP 面向字節建模實現了最少活躍S 盒個數的自動化計算.隨后，Sun 等人[4]在ASIACRYPT 2014 上對該技術進行了擴展，給出了基于比特級操作的更加精細的MILP 搜索模型.在FSE 2016 會議上，Fu 等人[5]將MILP 技術應用于ARX 密碼中的差分特征和線性逼近的自動化搜索.目前，該方法已應用于多種區分器的搜索，并取得了顯著成效.

為滿足物聯網應用的需求，Bansod 等人在2016 年提出了輕量級分組密碼PICO 算法[9]，PICO 算法是一種基于替換和排列的SPN 結構的分組密碼.2017 年，馬楚焱等人[10]利用MILP 模型找到大量7輪……