倍點(diǎn)運(yùn)算的白盒化實(shí)現(xiàn)及應(yīng)用*

潘文倫, 張立廷

摩石實(shí)驗(yàn)室, 成都衛(wèi)士通信息產(chǎn)業(yè)股份有限公司, 北京100070

1 引言

密碼算法的運(yùn)行環(huán)境對其安全性有重要影響. 傳統(tǒng)的密碼設(shè)備需要在安全可信環(huán)境中運(yùn)行, 算法的內(nèi)部狀態(tài)必須絕對保密, 不能夠被外部獲知, 這通常被稱作黑盒模型. 隨著密碼技術(shù)應(yīng)用的多樣化, 密碼產(chǎn)品特別是密碼軟件產(chǎn)品所處的運(yùn)行環(huán)境越來越不可控, 在極端環(huán)境下, 攻擊者甚至具有完全控制算法運(yùn)行過程、監(jiān)控干擾算法運(yùn)行、提取運(yùn)算中間信息等能力, 例如在數(shù)字版權(quán)保護(hù)等應(yīng)用場景中, 惡意用戶在手機(jī)、電腦等終端使用運(yùn)營商提供的數(shù)字資源服務(wù)時, 可能監(jiān)控數(shù)字資源在終端的解密過程, 恢復(fù)密鑰進(jìn)而獲取受版權(quán)保護(hù)的資源, 此類極端環(huán)境被稱為白盒攻擊環(huán)境[1]. 在白盒攻擊環(huán)境中, 傳統(tǒng)實(shí)現(xiàn)的密碼算法毫無安全性可言, 攻擊者通過控制算法運(yùn)行過程, 提取算法中間運(yùn)算信息等, 可以輕易恢復(fù)出完整的密鑰, 徹底破壞算法的安全性.

2002 年, Chow 等提出白盒攻擊環(huán)境概念時, 設(shè)計了首個AES、DES 白盒實(shí)現(xiàn)方案[1,2], 其主要思想是利用分組密碼迭代運(yùn)算的特點(diǎn), 將密碼算法運(yùn)算過程進(jìn)行分解, 將其中部分運(yùn)算結(jié)合起來轉(zhuǎn)換成查找表,以查表的方式完成計算, 將輪密鑰嵌入到查找表中并通過隨機(jī)映射保護(hù)查找表, 以實(shí)現(xiàn)保護(hù)每一輪輪密鑰.基于Chow 等的白盒設(shè)計思想, 人們提出了一系列標(biāo)準(zhǔn)密碼算法如AES、DES、SM4[3-7]等的白盒實(shí)現(xiàn)方案. 然而, 這些方案都在提出不久后就被攻破[8-10], 且大多性能低下, 難以滿足實(shí)際應(yīng)用需求. 基于白盒攻擊環(huán)境的特點(diǎn), 人們也設(shè)計了一些新型白盒密碼算法, 如基于ASASA 結(jié)構(gòu)[11]、SPACE-Hardness 問題[12]、白盒密鑰[13]等的白盒算法, 相比于對標(biāo)準(zhǔn)算法的白盒實(shí)現(xiàn), 這些新型算法在效率、安全性方面具有一定優(yōu)勢, 但缺乏實(shí)際應(yīng)用.

目前, 公鑰密碼在白盒環(huán)境中的密鑰防護(hù)成果相對較少. 2014 年, 林璟鏘等采用多方安全計算的思想,設(shè)計了SM2 簽名算法的“云加端” 方案[14]. 在該方案中, 用戶端和云端分別獨(dú)立產(chǎn)生部分私鑰信息, 通過設(shè)計的交互協(xié)議協(xié)同生成公鑰, 兩方聯(lián)合完成SM2 簽名、解密運(yùn)算, 卻無法獲取對方的私鑰信息, 從而達(dá)到保護(hù)私鑰的目的. 之后, 人們基于該思想構(gòu)造了系列密鑰分割方案, 對通信量、效率等進(jìn)行優(yōu)化[15],還有針對不同應(yīng)用場景的擴(kuò)展方案[16]. 2018 年, 候紅霞等構(gòu)造了安全的兩方協(xié)作SM2 簽名方案[17], 該方案采用零知識證明技術(shù)認(rèn)證雙方身份, 用承諾技術(shù)保證輸出完整簽名的正確性, 用同態(tài)加密技術(shù)、時戳機(jī)制等確保只有在特定條件下才能輸出正確的完整的簽名, 具有更高的安全性, 可在通信信道不安全的環(huán)境中使用. 2020 年, Yudi Zhang 等提出了基于同態(tài)加密的SM2 協(xié)同簽名算法[18], 可實(shí)現(xiàn)在不恢復(fù)簽名私鑰的情況下完成SM2 簽名, 并給出了可證明安全保障. 對于單一主機(jī)上公鑰密碼白盒實(shí)現(xiàn)研究, 2018年, 谷大武等提出了SM2 白盒簽名方案[19], 通過構(gòu)造參數(shù)表、組合產(chǎn)生隨機(jī)數(shù)等方式保護(hù)私鑰安全, 但該方案不支持標(biāo)準(zhǔn)SM2 簽名輸入輸出接口, 且需要額外的輔助信息才能完成驗(yàn)簽過程. 一些商業(yè)公司如愛迪德[20]等宣稱開發(fā)了ECC、RSA 等公鑰密碼白盒產(chǎn)品, 但作為商業(yè)秘密并未對外公開技術(shù)細(xì)節(jié).

本文針對公鑰密碼算法中的常見運(yùn)算-橢圓曲線倍點(diǎn)運(yùn)算, 構(gòu)造了白盒實(shí)現(xiàn)方案, 以保護(hù)倍數(shù)(私鑰等秘密) 信息. 我們的主要策略是: 首先將倍數(shù)信息展開成特定的表達(dá)形式, 然后對展開后的每個分量分別構(gòu)造查找表, 以保護(hù)每一分量信息, 然后通過網(wǎng)絡(luò)化查表的方式消除每個查找表的編碼信息, 最后實(shí)現(xiàn)最終結(jié)果的正確計算, 整個過程不泄露分量信息, 進(jìn)而實(shí)現(xiàn)對倍數(shù)信息的保護(hù). 進(jìn)一步, 我們使用余數(shù)系統(tǒng)嵌套分解大數(shù)運(yùn)算, 以實(shí)現(xiàn)查找表的分解, 從而降低查找表的規(guī)模, 使白盒方案所需存儲空間滿足實(shí)際應(yīng)用需求. 最后, 我們基于此構(gòu)造了SM2/9 白盒解密方案, 并將此思想推廣到模冪運(yùn)算的白盒實(shí)現(xiàn), 進(jìn)一步應(yīng)用到RSA 等算法的白盒實(shí)現(xiàn).

2 符號約定

3 基本思路

倍點(diǎn)運(yùn)算Q = [d]C 是橢圓曲線公鑰密碼算法中的常見運(yùn)算, 算法的安全性通常依賴于密鑰的保密,橢圓曲線倍點(diǎn)運(yùn)算的單向性為此提供了基本保障, 即給定點(diǎn)Q,C, 恢復(fù)倍數(shù)信息d 在計算上不可行. 為完成該計算過程, 現(xiàn)實(shí)中人們通常將該運(yùn)算過程分解成多個點(diǎn)加運(yùn)算, 如先將d 展開

然后依次計算

從而可通過依次計算兩點(diǎn)相加, 完成點(diǎn)C 的d 倍點(diǎn)運(yùn)算, 其中, Qm=[dm]C,Q=Q0.

當(dāng)倍點(diǎn)運(yùn)算運(yùn)行在不可信平臺上時, 攻擊者具有監(jiān)控甚至干擾整個計算過程的能力, 因此可根據(jù)上述運(yùn)算過程輕易依次獲取每個di, 進(jìn)而恢復(fù)d. 為保護(hù)倍數(shù)信息d, 我們可以將運(yùn)算過程Q=[d]C 制作成查找表, 即預(yù)先將點(diǎn)C 的每個取值按順序遍歷, 依次存儲其倍數(shù)Q, 構(gòu)成一張查找表Lookup_Table, 然后當(dāng)輸入信息C 時, 根據(jù)C 的取值查詢Lookup_Table, 即可得到其倍點(diǎn)Q. 在白盒攻擊環(huán)境下, 攻擊者只能獲取到查找表Lookup_Table 的信息, 由于倍點(diǎn)運(yùn)算的單向性, 攻擊者無法據(jù)此恢復(fù)d, 從而實(shí)現(xiàn)對d的保護(hù). 該方法雖然簡單有效, 但由于點(diǎn)C 的取值范圍很大, 如若C = (x,y,z) ∈E(Fq), 當(dāng)E(Fq) 的階為N 時, 查找表Lookup_Table 的規(guī)模將達(dá)到3q·2N比特, 無法在實(shí)際中存儲該查找表, 因此, 將倍點(diǎn)運(yùn)算白盒化實(shí)現(xiàn)的首要目標(biāo)是研究如何分解上述查找表以降低存儲規(guī)模.

Chow 等提出的AES、DES 白盒實(shí)現(xiàn)方案有以下三點(diǎn)主要思想: (1) 利用分組密碼迭代結(jié)構(gòu)特點(diǎn)將算法分解, 并將分解后每一塊計算過程轉(zhuǎn)換成查找表, 以查表的方式完成計算; (2) 將輪密鑰嵌入查找表, 并使用隨機(jī)置換保護(hù)查找表, 以保護(hù)每一輪的輪密鑰; (3) 使用小規(guī)模置換(如4 比特置換) 級聯(lián)組合成較大規(guī)模的置換(如32 比特置換), 以實(shí)現(xiàn)對查找表的分解, 降低存儲規(guī)模.

我們借鑒該思想來構(gòu)造倍點(diǎn)運(yùn)算的白盒實(shí)現(xiàn)方案: 首先將倍數(shù)信息分解, 以實(shí)現(xiàn)對倍點(diǎn)運(yùn)算的分解,然后將分解后的每一塊轉(zhuǎn)換成查找表; 其次, 將倍數(shù)分解后的每塊信息嵌入到查找表中, 并使用隨機(jī)置換保護(hù)查找表, 以保護(hù)倍數(shù)信息分解后的每個分量的信息; 最后, 采用小規(guī)模置換實(shí)現(xiàn)對每個查找表的分解,使所需存儲空間降低至現(xiàn)實(shí)可用的范圍.

若我們按如下方式分解倍數(shù)信息d

并將點(diǎn)加運(yùn)算Qi?1=[di?1]C+[2]Qi中含有信息di?1的運(yùn)算部分轉(zhuǎn)換成查找表并編碼保護(hù)

其中, F 為隨機(jī)置換. 此時, 由于di?1∈{0,1}, 攻擊者選擇兩組((x0,y0,z0),(x1,y1,z1)) 查詢該查找表,根據(jù)查詢結(jié)果是否變化就可判斷出di?1的值, 因此我們不能將倍數(shù)d 簡單地按上述形式展開.

考慮到倍點(diǎn)運(yùn)算和點(diǎn)加運(yùn)算的復(fù)雜性, 為使查找表Lookup_Table 不泄露di?1的值, 我們將d 表示成±1 的形式, 即di?1∈{1,?1}. 此時, 由于[di?1](x,y,z) = (x,di?1y,z), 對任意由函數(shù)F 與di?1生成的查找表Lookup_Table, 均存在隨機(jī)置換F′與?di?1可以生成相同的查找表, 從而攻擊者無法根據(jù)給定的查找表區(qū)分出di?1的取值. 因此, 我們首先將倍數(shù)d 展開成如下形式

算法1 Expand(d)Input: d Output: {d′0,d0,d1,··· ,dm}1 tag = d % 4;2 switch tag do 3 Case 0:4 d′0 = 1,d0 = 1,d1 = ?1;5 Case 1:6 d′0 = 2,d0 = 1,d1 = ?1;7 Case 2:8 d′0 = 1,d0 = ?1,d1 = 1;9 Case 3:10 d′0 = 2,d0 = ?1,d1 = 1;11 end 12 for i = 2 to m do 13 if (d ?i) % 2 == 0 then 14 if di?1 == 1 then 15 di?1 = ?1,di = 1;16 end 17 else 18 di?1 = 1,di = ?1;19 end 20 end 21 else 22 di = 1;23 end 24 end

算法2 Mul_Point(C)Input: C Output: Q,Q = ∑m?1 i=0 [di ·2i]C 1 R0 = [d0]C;2 Q0 = R0;3 for i = 1 to m ?1 do 4 Ri = [2didi?1]Ri?1;5 Qi = Qi?1 +Ri;6 end 7 Q = Qm?1;

其中

對i=1,2,··· ,m ?1

且G0=F0,Gm?1=I.

由以上分析, 我們可得倍點(diǎn)運(yùn)算白盒初始化過程如算法3. 在初始化過程中, 輸入倍數(shù)信息d, 然后將其展開成±1 表達(dá)形式, 再根據(jù)每個分量構(gòu)造系列查找表, 輸出查找表, 刪除其它信息以完成初始化. 每個查找表的具體構(gòu)造過程我們將在下一節(jié)中介紹.

算法3 Inital_WB(d)Input: d Output: d′0,T0,T1,··· ,Tm?1,T′1,T′2,··· ,T′m?1 1 {d′0,d0,d1,··· ,dm} = Expand(d);2 Gen(F0) ;3 T0 : (x′,y′,z′) = F0([d0](x,y,z));4 for i = 1 to m ?1 do 5 Gen(Fi);6 Gen(Gi);7 Ti : (x′,y′,z′) =Fi([2didi?1]F?1 i?1(x,y,z));8 T′i : (x′,y′,z′) =Gi(G?1 i?1(x1,y1,z1)+F?1 i (x2,y2,z2));9 end

算法4 WB_Mul_Point(C)Input: C Output: Q 1 R0 = T0(C);2 Q′0 = R0;3 for i = 1 to m ?1 do 4 Ri = Ti(Ri?1);5 Q′i = T′i(Q′i?1,Ri);6 end 7 Q = [d′0]C +Q′m?1 +[2m]C;

以下簡要說明倍點(diǎn)運(yùn)算白盒計算過程的正確性. 由算法3 中查找表的構(gòu)造過程, 易知, 當(dāng)算法4 輸入點(diǎn)C 時, 有

4 具體構(gòu)造

4.1 查找表的構(gòu)造過程

本節(jié)我們逐一介紹查找表T0,T1,··· ,Tm?1,T′1,T′2,··· ,T′m?1的構(gòu)造過程.

首先考慮T0. 因[d0](x,y,z) = (x,d0·y,z), 我們只需對分量y 進(jìn)行編碼保護(hù), T0的構(gòu)造過程如算法5, 對輸入信息(x,y,z) 查詢T0的過程如算法6.

算法5 T0 =Initial_T0(d0)Input: d0 Output: T0 1 Gen(g0);2 T0 : y = g0(d0 ·x);

算法6 (x′,y′,z′)=T0,j(x,y,z)Input: (x,y,z)Output: (x′,y′,z′)1 x′ = x;2 y′ = T0(y);3 z′ = z;

查找表

表示輸入點(diǎn)(x1,y1,z1),(x2,y2,z2), 然后對此兩點(diǎn)解碼后的真實(shí)點(diǎn)作加法運(yùn)算, 最后對運(yùn)算結(jié)果使用隨機(jī)置換Gi編碼保護(hù). 由第3 節(jié)的分析可知, 當(dāng)白盒方案正常運(yùn)行時, 點(diǎn)(x1,y1,z1),(x2,y2,z2) 解碼后對應(yīng)的真實(shí)點(diǎn)為

易知, 當(dāng)C ?=0 時,

在標(biāo)準(zhǔn)射影坐標(biāo)系下, 橢圓曲線上的非零點(diǎn)P1= (x1,y1,z1),P2= (x2,y2,z2) 的加法運(yùn)算P3=(x3,y3,z3)=P1+P2?=0 如下[21-23].

· 若P1=P2, 則

· 若P1?=P2, 則

輸入信息為經(jīng)隨機(jī)置換Fi?1編碼保護(hù)后的點(diǎn)(x,y,z), 輸出信息使用函數(shù)Fi編碼保護(hù). 記Fj(x,y,z) =(fj(x),gj(y),hj(z)),j =0,1,··· ,m ?1, 則可構(gòu)造以下查找表

即查找表Ti由上述系列查找表組合構(gòu)成, 其中u1,u2,··· ,u6為隨機(jī)置換, f0,h0為恒等置換. 當(dāng)輸入信息(x,y,z) 時, 查詢Ti即依次查詢Table1,Table2,··· ,Table9的過程如下

從而得到Ti的輸出信息(x′,y′,z′). 由查找表T7,T8,T9的構(gòu)造過程知, (x′,y′,z′) 由隨機(jī)置換Fi編碼保護(hù).

4.2 余數(shù)系統(tǒng)與查找表的分解

由于倍點(diǎn)運(yùn)算均在Fq上計算, 若構(gòu)造查找表所選擇的隨機(jī)置換在Fq上選取, 查找表的規(guī)模將無法接受. 例如, 查找表Table1: y ←(x1,x2),y,x1,x2∈Fq, 若所選擇的置換為Fq上的隨機(jī)置換, 則查找表的規(guī)模為q2·log q 比特, 由于q 較大, 該查找表的規(guī)模難以滿足實(shí)際應(yīng)用. 為降低查找表的規(guī)模, 我們首先將含有多個運(yùn)算的查找表進(jìn)行分解, 使每個查找表只包含一種運(yùn)算. 例如, 將查找表

分解為

其中, v1,v2為隨機(jī)生成的置換. Table1由此三個查找表組合構(gòu)成, 查詢Table1由依次查詢此三個查找表實(shí)現(xiàn). 在標(biāo)準(zhǔn)射影坐標(biāo)系下, 橢圓曲線上點(diǎn)的加法運(yùn)算只涉及模乘、模加運(yùn)算, 因此對查找表進(jìn)行分解后,所有查找表均可歸為以下兩類

分別稱為模乘查找表與模加查找表, 其中, 完成平方運(yùn)算的查找表可看作模乘查找表的一種特殊情況. 以下我們首先說明可以采用余數(shù)系統(tǒng)理論將Fq上的模乘、模加運(yùn)算轉(zhuǎn)化為余數(shù)系統(tǒng)上的運(yùn)算, 從而實(shí)現(xiàn)對運(yùn)算過程的分解, 進(jìn)而實(shí)現(xiàn)對此兩類查找表的分解.

其中, x ≡ximod mi,i = 1,2,··· ,t. 對任意給定的余數(shù)表示(x1,x2,··· ,xt), 由中國剩余定理可恢復(fù)[0,M) 內(nèi)的元素

其中, Mi= M/mi,i = 1,2,··· ,t. 由余數(shù)系統(tǒng)的性質(zhì), 對任意x,y ∈ZM, 若x = (x1,x2,··· ,xt),y =(y1,y2,··· ,yt), 則

其中, ⊙表示模乘、模加運(yùn)算. 即ZM上的模乘、模加運(yùn)算可轉(zhuǎn)化為余數(shù)系統(tǒng)上的模乘、模加運(yùn)算.

余數(shù)系統(tǒng)下的蒙哥馬利乘法[24,25],通過使用兩個余數(shù)系統(tǒng)實(shí)現(xiàn)計算X·Y mod q,其中0 ≤X,Y ＜q.文獻(xiàn)[25] 中Algorithm 1 介紹了該過程, 我們對該算法整理如下:

算法7 R=RNS_Mul(X,Y)參數(shù)設(shè)置:選取余數(shù)系統(tǒng)B : {m1,m2,··· ,mn}, 其中M = ∏n i=1 mi,0 ＜2q ＜M;選取余數(shù)系統(tǒng)B′ : {m′1,m′2,··· ,m′n′}, 其中M′ = ∏n′i=1 m′i,gcd(M,M′) = 1,M ＜M′;Input: X,Y Output: R, 滿足R ≡XY M?1 mod q, 且R ＜2q 1 Q ←(?X ×B Y)×B |q|?1M ;2 將Q 在余數(shù)系統(tǒng)B 中的表示轉(zhuǎn)換為在余數(shù)系統(tǒng)B′ 中的表示;3 R ←(X ×B′ Y +B′ Q×B′ q)×B′ |M|?1 M′;4 將R 在余數(shù)系統(tǒng)B′ 中的表示轉(zhuǎn)換為在余數(shù)系統(tǒng)B 中的表示;5 使用中國剩余定理恢復(fù)R;

由算法7知, 我們首先輸入(X,Y) 得到R = XY M?1mod q, 再次輸入(R,M2) 調(diào)用該算法就可得XY mod q 的值, 即

其中, mx≥n 為輔助模數(shù). 顯然, X +Y mod N 也可按類似的方式完成, 因此, Fq上的模乘、模加運(yùn)算可轉(zhuǎn)化為余數(shù)系統(tǒng)B 與余數(shù)系統(tǒng)B′上的運(yùn)算, 據(jù)此, 我們可將模乘查找表

中的隨機(jī)置換f,g,h 改為分別從余數(shù)系統(tǒng)B,B′上選取, 即

然后, 以編碼保護(hù)的方式實(shí)現(xiàn)算法7, 即實(shí)現(xiàn)

與上一節(jié)中對橢圓曲線上點(diǎn)的加法運(yùn)算構(gòu)造查找表類似, 我們將算法7 中每一步運(yùn)算轉(zhuǎn)換為查找表, 例如,我們將運(yùn)算

中的運(yùn)算X ×BY 轉(zhuǎn)化為查找表

其中, i=1,2,··· ,t.

以查表的方式完成算法7 需要1 次B 中的運(yùn)算, 2 次B′中的運(yùn)算, 以及兩個余數(shù)系統(tǒng)之間的轉(zhuǎn)換各1 次, 構(gòu)造查找表所需存儲空間為

注, 我們?nèi) 與B′規(guī)模接近, 相互轉(zhuǎn)換所需存儲空間相近, 常數(shù)項(xiàng)參與的運(yùn)算可預(yù)置到存儲表中.

進(jìn)一步, 我們采用嵌套分解的方式, 將Fq上的元素運(yùn)算轉(zhuǎn)換到特定的余數(shù)系統(tǒng)中的運(yùn)算. 給定余數(shù)系統(tǒng)

遠(yuǎn)小于未分解之前的規(guī)模.

5 安全性分析

白盒密碼應(yīng)用通常分為兩個階段: 初始化階段與計算階段. 在初始化階段, 算法根據(jù)密鑰等敏感信息,隨機(jī)選取一些置換等, 生成一系列查找表或隨機(jī)參數(shù), 然后刪除敏感信息, 輸出這些查找表與隨機(jī)參數(shù). 該階段涉及對敏感信息的直接處理, 需要在安全服務(wù)器、可信芯片等設(shè)備完成. 在計算階段, 用戶根據(jù)初始化結(jié)束后查找表或隨機(jī)參數(shù)等, 對輸入信息完成運(yùn)算處理過程.

當(dāng)前, 基于Chow 等白盒思想構(gòu)造的AES、DES、SM4 等系列白盒方案, 均存在安全性不高等問題,主要原因在于, 這些方案受限于分組密碼迭代結(jié)構(gòu), 攻擊者可通過組合查找表消除一些用于保護(hù)查找表的較大規(guī)模的隨機(jī)置換, 或通過仿射等價關(guān)系獲取輪密鑰信息, 如BGE 攻擊等[8]. 本方案中, 橢圓曲線倍點(diǎn)運(yùn)算的計算過程與分組密碼迭代結(jié)構(gòu)差異巨大, 我們采用一種新型的實(shí)現(xiàn)策略, 將所有運(yùn)算均轉(zhuǎn)換到較小的有限域上進(jìn)行運(yùn)算, 余數(shù)系統(tǒng)不同模數(shù)之間的關(guān)聯(lián)性較弱, 攻擊者即使猜測確定部分模數(shù)上的查找表所使用的編碼置換, 也難以據(jù)此推出其它模數(shù)上的隨機(jī)置換, 因此, 現(xiàn)有對基于Chow 等白盒思想的對稱密碼白盒方案的攻擊難以直接應(yīng)用到對本方案的攻擊.

6 應(yīng)用

6.1 SM2 解密算法白盒實(shí)現(xiàn)方案

SM2 密碼算法是基于橢圓曲線的公鑰算法, 由國家密碼管理局于2010 年12 月發(fā)布, 2012 年成為我國密碼行業(yè)標(biāo)準(zhǔn)GM/T 0003[21], 并于2016 年成為國家標(biāo)準(zhǔn)GB/T 32918[22]. 在SM2 解密算法中, 私鑰dA只參與運(yùn)算(x2,y2) = [dA]C1, 其中C1是輸入的密文信息. 因此, 我們只需將SM2 解密算法中的這一運(yùn)算過程采用本文所構(gòu)造的倍點(diǎn)運(yùn)算白盒實(shí)現(xiàn)方式實(shí)現(xiàn), 即可得到SM2 解密算法白盒實(shí)現(xiàn)方案.

我們按算法1 將dA展開成特定的表達(dá)形式, 由于SM2 解密算法的私鑰dA＜2256, 我們?nèi)=256.此時, 由算法5 將SM2 解密算法白盒初始化后, 生成查找表

查找表Ti,i=1,2,··· ,255 的規(guī)模為

因此,基于上述余數(shù)基的SM2 倍點(diǎn)運(yùn)算白盒實(shí)現(xiàn)相比于SM2 標(biāo)準(zhǔn)實(shí)現(xiàn)需要額外增多存儲空間約為1.07+(98.56+129.36)·255 ≈56.76 MB, 完成該運(yùn)算需2 次點(diǎn)加運(yùn)算、2 次余數(shù)系統(tǒng)轉(zhuǎn)換運(yùn)算及1+255·(16+21)·(3+10)=122 656 次查表運(yùn)算(注, 每次256 比特數(shù)據(jù)并行查表算作1 次查表). 我們可通過調(diào)整余數(shù)基與用于嵌套分解的余數(shù)基, 實(shí)現(xiàn)存儲空間與查表次數(shù)之間的平衡, 以滿足實(shí)際應(yīng)用需求.

6.2 SM9 解密算法白盒實(shí)現(xiàn)方案

SM9 標(biāo)識密碼算法是一種基于雙線性對的標(biāo)識密碼算法, 由國家密碼管理局于2016 年3 月發(fā)布為密碼行業(yè)標(biāo)準(zhǔn)GM/T 0044[23]. 對于SM9 解密算法, 私鑰deB參與雙線性對運(yùn)算w′=e(C1,deB), 我們基于雙線性對的性質(zhì), 將私鑰參與的上述運(yùn)算進(jìn)行如下變換

其中, α 為預(yù)先選定的隨機(jī)數(shù). 我們公開[α?1]deB, 并將[α]C1的計算過程采用本文所構(gòu)造的方案白盒化實(shí)現(xiàn), 即得到了SM9 解密算法的白盒實(shí)現(xiàn)方案, 方案所需額外的存儲空間及運(yùn)行效率與SM2 解密算法白盒方案相仿.

7 推廣

7.1 模冪運(yùn)算白盒實(shí)現(xiàn)

RSA 算法是目前使用最廣泛的公鑰密碼體制之一[27]. 在RSA 解密或簽名運(yùn)算中, 私鑰參與的運(yùn)算均為模冪運(yùn)算y = xdmod N. 模冪運(yùn)算與倍點(diǎn)運(yùn)算均為公鑰密碼算法中常見的運(yùn)算, 本節(jié)將倍點(diǎn)運(yùn)算白盒實(shí)現(xiàn)方法推廣到模冪運(yùn)算白盒實(shí)現(xiàn), 并構(gòu)造RSA 算法白盒實(shí)現(xiàn)方案.

類似地, 我們首先將模冪運(yùn)算y =xdmod N 中的指數(shù)d 展開成如下形式

其中, d0∈{1,3,5},di∈{1,3},i=1,2,··· ,m ?1,dm=1. 具體展開過程如算法8. 易知, 對任意的奇數(shù)d, 均可展開成上述表達(dá)形式. 例如, d=13=(1101)2可按算法8 展開為

與倍點(diǎn)運(yùn)算白盒化處理過程類似, 將模冪運(yùn)算的指數(shù)按上述形式展開后, 將模冪運(yùn)算進(jìn)行分解, 然后采用查找表網(wǎng)絡(luò)完成模冪運(yùn)算過程. 模冪運(yùn)算白盒方案初始化過程如算法9, 網(wǎng)絡(luò)化查表計算過程如算法10, 同樣的, 模冪運(yùn)算白盒實(shí)現(xiàn)方案中的查找表可采用余數(shù)系統(tǒng)進(jìn)行分解.

算法8 Expand(d)Input: d Output: (dm,dm?1,··· ,d0)1 設(shè)d = d′m+1d′m···d′0,d′m+1 = 1,di ∈{0,1};2 令(dm,dm?1,··· ,d1,d0) = (d′m?1 +1,··· ,d′1 +1,d′0 +2);3 tag = 1;4 for i = m to 0 do m +1,d′5 if di == 2 then 6 if tag == 1 then 7(di,di?1,··· ,d0) = (di ?1,di?1 +1,··· ,d1 +1,d0 +2);8 tag = 3;end 10 else 9 11 (di,di?1,··· ,d0) = (di +1,di?1 ?1,··· ,d1 ?1,d0 ?2);12 tag = 1;13 end 14 end 15 end

算法9 Inital_WB(d)Input: d Output: T0,T1,··· ,Tm?1,T′1,T′2,··· ,T′m?1 1 (dm,dm?1,··· ,d0) = Expand(d);2 Gen(f0) ;3 T0 : y = f0(xd0);4 for i = 1 to m ?1 do 5 Gen(fi);6 Gen(f′i);7 Ti : z = fi((f?1 i?1(x))2did?1i?1);8 T′i : z = f′i(f′?1i?1(x)·f?1 i (y));9 end

8 總結(jié)

算法10 WB_Mod_Exp(x)Input: x Output: y 1 X0 = T0(x);2 Y0 = X0;3 for i = 1 to m ?1 do 4 Xi = Ti(Xi?1);5 Yi = T′i(Yi?1,Xi);6 end 7 y = Ym?1 ·x2m;

公鑰密碼算法的運(yùn)行大多依賴于較大規(guī)模的數(shù)學(xué)計算, 若簡單采用傳統(tǒng)的表格化白盒實(shí)現(xiàn)思路, 其存儲規(guī)模遠(yuǎn)遠(yuǎn)超過實(shí)際密碼系統(tǒng)的承受能力. 本文在研究公鑰算法數(shù)學(xué)特征的基礎(chǔ)上, 從算法底層提出了針對倍點(diǎn)運(yùn)算、模乘運(yùn)算的白盒實(shí)現(xiàn)策略, 可應(yīng)用于SM2/9、RSA 等多種標(biāo)準(zhǔn)公鑰算法. 目前公鑰算法白盒化的成果很少, 希望本文的設(shè)計思路有所助益。針對具體業(yè)務(wù)場景, 我們可以通過調(diào)整實(shí)現(xiàn)參數(shù), 在安全-性能-代價之間得到較好的平衡, 以此增強(qiáng)對此類算法的私鑰保護(hù).