[發明專利]一種基于分治的程序高階功耗側信道安全性的證明方法

有效

• 申請號: 202010908485.X
• 申請日: 2020-09-02
• 公開（公告）號: CN112134729B
• 公開（公告）日: 2022-11-04
• 發明（設計）人: 宋富;高鵬飛;謝弘毅
• 申請（專利權）人: 上海科技大學
• 主分類號: H04L41/28
• 分類號: H04L41/28;H04L9/40;H04L9/08
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 徐俊

本發明涉及一種基于分治的程序高階功耗側信道安全性的證明方法，其特征在于，包括以下步驟：對于一個含有n個可觀察變量的程序，為證明程序是d階功耗側信道安全性，即所有大小為d的可觀察變量集合的聯合統計分布都獨立于密鑰，本發明的方法通過證明少量可觀察變量集合的聯合統計分布獨立于密鑰來證明d階功耗側信道安全性。采用本發明的方法可以有效避免組合爆炸問題，從而可以高效地證明程序高階功耗側信道安全性。

技術領域

本發明涉及一種基于分治的程序高階功耗側信道安全性的證明方法，可應用于隨機掩碼高階功耗側信道安全的驗證。

背景技術

現代密碼學是當今計算機信息系統安全的基石。然而，在實踐中，攻擊者可以利用系統運行時的物理信息破解密鑰，比如采用密碼算法程序運行時的時間、功耗、電磁輻射等信息，這種攻擊被稱為側信道攻擊。

為阻止基于功耗的側信道攻擊，主要采用基于隨機數掩碼來避免物理信息與加密密鑰之間統計依賴關系。采用n階掩碼的程序理論上可以抵御n階功耗側信道攻擊。然而，采用安全的n階掩碼模式無法直接保證程序必然能抵御n階功耗側信道攻擊，因此需要自動化的驗證方法來證明程序高階功耗側信道安全性。

基于類型推導的證明方法和基于模型計數求解的證明和檢查方法相繼提出，并應用于證明d階功耗側信道安全性。對于一個含有n個可觀察變量的程序，為證明程序是d階功耗側信道安全性，即所有大小為d的可觀察變量集合的聯合統計分布都獨立于密鑰，需要驗證個變量集合。當可觀察變量數和階數變大時，出現組合爆炸問題，無法快速證明和檢測實際密碼程序的高階功耗側信道安全性。

發明內容

本發明要解決的技術問題是：當可觀察變量數和階數變大時，出現組合爆炸問題，現有的證明程序高階功耗側信道安全性的方法無法快速證明和檢測實際密碼程序的高階功耗側信道安全性。

為了解決上述技術問題，本發明的技術方案是提供了一種基于分治的程序高階功耗側信道安全性的證明方法，其特征在于，通過分治策略，把證明程序d階功耗側信道安全性問題轉化到證明一系列大集合變量的d階功耗側信道安全性問題，而證明一系列大集合變量的d階功耗側信道安全性問題又是遞歸的進行分治驗證，具體包括以下步驟：

步驟1、構造集合{(V,d)}，進入步驟2，其中，V表示可觀察變量集合，d為大于0的整數表示需要驗證的階數；

步驟2、對于給定集合{(V₁,d₁),...,(V_n,d_n)}，V₁,...,V_n為可觀察變量集合；d₁,...,d_n為大于0且小于或等于d的整數，且保證d₁+…+d_n＝d，包括以下步驟：

步驟2.1、對于任意i，i＝1,…,n，從可觀察變量集合V_i中選取d_i個變量組成集合D_i，通過類型推導或基于SMT求解器的方法檢查變量集合的聯合統計分布是否獨立于密鑰變量；

步驟2.2、如果變量集合的聯合統計分布獨立于密鑰變量，則進入步驟2.3；如果變量集合的聯合統計分布不獨立于密鑰變量，則保存該變量集合并進入步驟2.4；

步驟2.3、對于任何i，i＝1,…,n，對于任意集合V_i\D_i中的變量x，驗證變量集合的聯合統計分布是否獨立于密鑰變量，如果是，則將x加入集合D_i，其中，V_i\D_i表示集合V_i減去D_i中的元素得到的集合；

重復步驟2.3直到沒有變量可以加入集合D_i，在所有能加入D_i的變量x加入后，進行分治；