防dpa類型的攻擊的模取冪方法

2023-04-25 11:14:36

專利名稱：防dpa類型的攻擊的模取冪方法
在保護加密算法以防DPA攻擊的領域中，本發明涉及一種執行類型x^d的模取冪的方法，其中d是m+1位的整數指數，在由從m變化到0的i為索引的循環中從左向右掃描d的位，進行計算並且存儲在記憶裝置(R0)中，在序號(rank)i每次循環(turn)時，所更新的部分結果等於x^b(i)。b(i)相當於指數d的m-i+1個最高有效位b(i)＝dm-＞i。由d的具有權重j至k的位所組成的數通過下式來定義dk->j=(dk,...,dj)2=i=jkdi.2^(i-j).]]>模取冪是在諸如RSA(Rivest，Shamir和Adleman)密碼系統或者DH(Diffie和Hellman)密碼系統的許多密碼系統中所使用的基本運算之一。對於這種應用來說，x例如是待加密或者解密、待籤名或者鑑權的消息，而d例如是公開密鑰、秘密密鑰或者這種密鑰的一部分。
自從由Diffie和Hellman發明了公開密鑰密碼術以來，已經建議了許多公開密鑰密碼系統。在抵抗密碼分析的那些密碼系統中，RSA密碼系統無疑被最廣泛地使用。其固有的安全性在於難以對大的整數進行因子分解。儘管進行了深入細緻的研究，因子分解的問題仍被認為是重要的問題，從而使RSA密碼系統對於諸如數據或者數字籤名的加密的敏感應用來說是安全的。
因此，密碼術已變成對RSA密碼系統的具體實施感興趣，而不是嘗試在數學層面上破解RSA算法。這已經導致錯誤攻擊和隱蔽信道攻擊的巨大增加，所述錯誤攻擊和隱蔽信道攻擊的目的在於在由執行密碼運算的計算設備實施一個或者其他步驟期間發現所處理的特別機密的信息(例如密鑰或者密鑰的部分)。
最廣泛已知的隱蔽信道攻擊據說是簡單的或者差分的。簡單(SPA)或者差分(DPA)隱蔽信道攻擊意味著基於對來自設備外部的物理量的測量的攻擊，對所述測量的直接分析(簡單攻擊SPA)或者根據統計分析的分析(差分攻擊DPA)使得能夠發現在設備中所處理的信息。這些攻擊尤其由Paul Kocher(Advances in Cryptology-CRYPTO′99，vol.1666 of Lecture Notes in Computer Science，第388-397頁，Springer-Verlag，1999年)公開。
在可被用於這些目的的物理量中，可以引用執行時間、電流消耗、由被用於執行計算的組件的一部分所輻射的電磁場等等。這些攻擊基於以下事實，即在執行算法、處理一個位、也就是說該位由特定指令使用期間，根據該位的值和/或根據該指令留下對所考慮的物理量的特定影響。
存在兩類使得能夠估計y＝x^d mod N的值的取冪算法的執行即所謂的右至左執行和所謂的左至右執行。
在左至右執行中，從最高有效位至最低有效位掃描指數的位。在第二類取冪算法中，尤其已知的是SAM算法(代表平方再乘)和其變型、例如滑動窗口算法。與所謂的右至左算法相比較，左至右算法需要較小的存儲器，並且允許使用預先計算的冪x^i，以便加速y的計算。所有左至右算法都共同使用記憶裝置(或者寄存器)，該記憶裝置在整個計算過程中被更新，以便存儲x^dm-＞imod N的值，用於減小i的值直至記憶裝置包含終值y＝x^dm-＞0＝x^d mod N。dk-＞j是由d的具有權重j至k的位組成的字。
SAM算法的一般原理如下。d的具有權重i的位被表示為d=(dm,...,d0)2=i=0mdi.2^i,]]>即指數d的二進位表示，其中diε{0，1}。對於d的每個位，SAM算法在記憶裝置(寄存器R0)中存儲根據遞歸方程x^dm-＞i＝(x^dm-＞i+1)2*x^di(其中x^dm-＞m＝x^dm)所計算的更新結果，這通過以下算法來概括輸入x，d＝(dm，...，d0)2輸出y＝x^d mod NR0＜-1；R2＜-x，i＜-m只要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod Ni＜-i-1結束只要返回R0R0＜-x意味著x的值被存儲在寄存器R0中。R0xR0意味著寄存器R0的內容自乘。R0xR2意味著寄存器R0的內容乘以寄存器R2的內容。最後，di-＞j指的是d的序號j至i的位。
為了防止執行攻擊，已知有必要使算法是隨機的。在RSA密碼系統的情況下，當前已知兩類對策，用於使y＝x^d mod N的計算為隨機的。
第一類對策包括使算法的輸入數據為隨機的。
該第一對策的第一例子包括在執行模取冪之前通過將隨機項加到x上並且在最後以N為模之前進行以2^k N為模的計算而使數據項x為隨機的x＜-x+r1.N，其中r1是k位的隨機數，並且在最後簡化以N為模之前進行以(2^k).N為模的計算。由P Kocher所描述的該第一對策具有獨立於取冪算法的優點。
該第一對策的第二例子包括在執行模取冪之前通過將隨機項加到指數d上而使指數d為隨機的d＜-d+r2.φ(N)，r2是k位的隨機數。
通常，這兩種解決方案被組合，以便執行運算y＝y mod N，其中y＝x^d mod(2k.N)。
在被單獨使用的該第一對策的第三例子中，例如當x是(例如利用PSS或者概率籤名方案功能的)概率格式化的結果時，因為在該情況下x已經被屏蔽，所以直接計算y＝x^d mod N，其中d＝d+r2.φ(N)，其中r2是隨機的。
不幸地，指數d的這種隨機化局限於RSA密碼系統的被稱為CRT執行的特定執行，因為通常不能根據標準版本(也即不是CRT)的私有取冪算法得知歐拉常數φ(N)的值。
第二對策包括使取冪算法本身為隨機的。將第二對策最好地付諸於實踐是Walter的MIST算法。MIST算法隨機地產生指數d的新的加法鏈，以便實現x^d mod N。為了使寄存器的數目最小化，根據除法鏈通過修改取冪算法快速地執行加法鏈。另一例子是滑動窗口算法的改進版本(參見Kouichi Itoh，Jun Yajima，Masahiko Takenaka和NaoyaTorii的「DPA countermeasures by improving the window methodCHES 2002」，Voluime 2523 of Lecture Notes in Computer Science，第303-317頁，Springer Verlag 2002)。與第一對策相比較，該對策使得能夠在不需要知道φ(N)的情況下使取冪為隨機的，但是需要用於計算除法鏈的安全的除法算法，並且不引起無關緊要的關於管理計算的擔憂。
為了防止差分攻擊(DPA)，本發明建議一種新穎方法，用於使模取冪的執行為隨機的，該方法具有兩種已知的對策的優點如在第一對策中，根據本發明的方法不利用任何特定的取冪算法，並且適用於任何取冪算法，並且如在第二對策中，在本發明中使算法自身為隨機的，而不僅僅使算法所處理的數據為隨機的。因此，該算法在RSA取冪時不必知道φ(N)和/或公共密鑰e(該密鑰e通常不可用於籤名或者解密算法)。
根據本發明的方法引入自動隨機取冪的方案，意味著在取冪過程中指數d本身被用作附加的隨機源。
因此，本發明涉及一種加密方法，其中通過在步驟1中在由從m至0遞減的i為索引的循環中從左至右掃描d的位、進行計算並且存儲在記憶裝置來執行x^d類型的模取冪，其中d是m+1位的整數指數，在序號i每次循環時，所更新的部分結果等於x^b(i)，b(i)是指數d的m-i+1個最高有效位。
根據本發明的方法的特徵在於-在隨機選擇的序號i(j)的一次循環結束(i＝i(0))時，隨機化步驟E1被執行，其中E1從在該方法中還未被使用的d的位(di-1-＞0)的一部分中減去隨機數z(z＝b(i(j))，z＝b(i(j)).2τ，z＝u)，-然後，在已經使用了通過隨機化步驟E1所修改的位之後，合併步驟E2被執行，其中E2記憶裝置的內容(x^b(i))乘以一個數的結果被存儲(R0＜-R1xR0)在記憶裝置R0中，所述數是寄存器(R1)中所存儲的x^z的函數。
從實踐的觀點來看，在步驟E1期間，從最初存儲有指數d的寄存器的內容中減去數z，並且將減法的結果存儲在相同的寄存器中，然後繼續掃描b的位。
為了取冪x^d mod N的結果在該方法結束時是正確的，隨機化步驟E1不必改變在計算中已經使用的d的位(我們記得該方法採用左至右算法)。隨機選擇的索引i(j)(以該索引執行隨機化E1)必須這樣來選擇，使得最初包含指數d的寄存器的m-i(j)+1個最高有效位在步驟E1期間保持不變。該條件在下文中將被稱為「一致性」條件。
因此，本發明的基本思想是使用以下形式的x^d mod N的計算的限幅(在法國專利申請號02 04117(待確認的號)中所描述的)x^d＝x^(d-z)*x^z，其中z是被用作屏蔽指數d的工具的隨機數。優選地，這樣選擇z的適當的值，以致在該方法過程中可以容易地從此外已被計算的x^b中獲得x^z。應該注意的是，完全隨機地選擇z導致幾乎使計算時間加倍。
根據本發明的方法獨立於左至右取冪算法而適用。此外，序號i(j)被如此選擇，以致是隨機的，其中以該序號執行步驟E1，並且因此該方法本身是隨機的，而不僅僅是該方法所處理的數據是隨機的。
如隨後將在SAM算法的例子中更好地看到的那樣，根據本發明的方法在空間方面(它只需要一個附加的計算寄存器)以及在計算時間方面也是有效的。
根據本發明的方法也易於執行該方法所適用的任何算法。該方法不基於任何組特性，並且該方法的執行不需要預先知道組的順序，其中在所述組中執行取冪。
最後，可以與其他算法保護措施、例如由P Kocher所公開的和上述的對策相結合地使用根據本發明的方法。
可以在該方法過程中執行一次隨機化步驟E1。當在0和m之間隨機選擇的序號i(j)的不同循環結束時(也即在序號i＝i(0)時，然後在序號i＝i(1)時，...，並且隨後最後在序號i＝i(f)時)，步驟E1也可以被執行多次。這裡，該思想是通過使用以下公式進一步提高該方法的安全性x^d＝x^(d-z1-z2-...-zf)xx^z1xx^z2x...xx^zf＝x^(((d-z1)-z2)-...-zf)x((x^z1)xx^z2)x...xx^zf。
在該方法開始時，可以選擇一個或者多個隨機序號i(j)，其中以所述隨機序號執行隨機化E1。例如，在該方法開始時，確定索引i的f+1個(f是隨機的或者不是隨機的)值的預先確定的集合{i(0)，i(1)，...，i(f)}，其中希望針對該索引執行隨機化E1。在這種情況下，在每次循環時，根據當前索引i是否構成預先確定的集合的一部分來決定是否執行隨機化E1。
也可以在每次循環i開始時隨機地選擇是否執行隨機化步驟E1。在這種情況下，布爾變量ρ例如在索引i的每次循環結束時隨機地被使用、被提取。
現在將描述本發明的不同實施方案，所述不同實施方案由於步驟E1的實施方案、並且尤其是由於z的選擇和d的從d中減少的一部分的選擇而基本上彼此不同。
根據第一實施方案，選擇在該方法結束時只執行一次合併步驟。這使得有必要從指數d的最低有效位中例行公事地減去z，以便在該方法結束時獲得正確的結果。
根據該實施方案的第一變型，針對所選擇的隨機數i(j)選擇z＝b(i(j))＝dm-＞i(j)，並且在隨機化步驟E1過程中，從d中、也即從d的最低有效位中減去b(i(j))。
選擇z＝b(i(j))是特別有利的，因為x^b(i(j))＝x^dm-＞i(j)在循環i(j)結束時在記憶裝置中已經是可用的，並且因此不需要被計算。變量i(j)這樣被選擇，使得數d-b(i(j))的具有權重i(j)至m的位等於數d的具有權重i(j)的位，因此計算x^d的最初的m-i(j)+1次循環與x^(d-b(i(j)))的計算的最初的m-i(j)+1次循環是相同的(一致性條件)。在循環i(j)結束時，d-z＝d-b(i(j))被計算，並且記憶裝置的內容x^b被存儲在寄存器(E1)中。
在特定例子中，布爾變量ρ被用於確定在索引i的每次循環結束時是否執行隨機化。如果ρ取有效值，則執行步驟E1數d用數d-b(i(j))來代替，並且存儲x^b(i(j))。
如在傳統的左至右算法中，在索引i每次循環時，記憶裝置R0被用於存儲x^dm-＞i的值。寄存器R1被用於存儲乘積∏jx^dm-＞i(j)。
整個適用於已知的SAM算法，並且獲得下面的算法I輸入x，d＝(dm，...，d0)2輸出y＝x^d mod NR0＜-1；R1＜-1；R2＜-x，i＜-m只要i≥0，進行
R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod Nρ＜-R{0，1}如果((ρ＝1)並且di-1→0≥dm→i，則d←d-dm-＞iR1＜-R1xR0 mod N結束如果i＜-i-1結束只要R0＜-R0xR1 mod N返回R0ρ＜-R{0，1}意味著在集合{0，1}中隨機地選擇ρ的值。因此，ρ是隨機布爾變量。
只有當ρ＝1(也就是說如果必須執行隨機化)並且di(j)-1-＞0≥dm-＞i(j)時，才執行隨機化步驟E1(d＜-d-dm-＞i(j)；R1＜-R1xR0 mod N)。
條件di(j)-1-＞0≥dm-＞i(j)意味著d的具有權重0至i-1的位大於b(i(j))，b(i(j))等於d的具有權重i(j)至m的位。這保證d-b(i(j))的m-i+1個最高有效位與d的m-i+1個最高有效位相同，並且因此保證x^d的最初的m-i+1計算循環與x^(d-b(i(j)))的最初的m-i+1計算循環相同。
「一致性」條件(di(j)-1-＞0≥dm-＞i(j))意味著只使指數d的最低有效位為隨機的。另外，應該注意的是，隨機步驟d＜-d-dm-＞i(j)只改變d的(m-i(j)+1)個最低有效位。
應該注意的是，在算法I中，當在迭代i＝i(j)時，更新步驟d＜-d-dm-＞i不改變d的(m-i+1)個最高有效位，該步驟可以用等價步驟來代替di-1-＞0＜-di-1-＞0-dm-＞i。
根據第一實施方案的第二變型，將z選擇為等於g.b(i)(其中g是隨機數)，以便di(j)-1-＞0.≥g.dm-＞i(j)。在這種情況下，採用公式x^d＝x^(d-z).x^z＝x^(d-g.b(i)).(x^b(i))g，並且從實踐的觀點來看，為了在索引i(j)的循環結束時執行隨機化E1
-計算z＝g.b(i)，並且從指數d中減去該結果，-通過寄存器R1的內容乘以記憶裝置的內容(x^b(i))的g次冪來更新寄存器R1。這具體地可以通過指令R1＜-R1xR0^g mod N來執行。
優選地選擇g＝2τ，τ是隨機整數。由於g.b(i)＝g.dm-＞i(j)的計算相當於位的簡單移位，並且(x^b(i))^g mod N的估計相當於執行τ平方的計算，所以這大大簡化計算。
由於乘以2τ相當於位的移位，所以計算d-g.b(i)的指令d＜-d-2τ.dm-＞i可以用dm-＞τ＜-dm-＞τ-dm-＞i來代替，或者更好地用等價指令di-1-＞τ＜-di-1-＞τ-dm-＞i來代替。
另外，至於其他實施方案，必須驗證，在迭代i＝i(j)時，di-1-＞0≥2τ.dm-＞i。該一致性條件可以用等價的但是更有效的測試di-1-＞τ≥dm-i來代替。
優選地，隨機地在集合{0，...，T}中選擇τ。定界符T被選擇為d的最高有效位的隨機化和τ平方的計算的(尤其在計算時間方面的)效力之間的最佳折衷。
在SAM算法的特定例子中，最終得到下面的算法I′輸入x，d＝(dm，...，d0)2輸出y＝x^d mod NR0＜-1；R1＜-1；R2＜-x，i＜-m只要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod Nρ＜-R{0，1}；τ＜-R{0，...，T}如果((ρ＝1)並且(di-1→τ≥dm-i))，則di-1→τ←di-1→τ-dm-＞iR3＜-R0隻要(τ＞0)，進行R3＜-R3^2 mod N；τ＜-τ-1結束只要R1＜-R1xR3 mod N結束如果i＜-i-1
結束只要R0＜-R0xR1 mod N返回R0算法I′的一個優點在於d的上面一半被部分地隨機化，並且因此熵(也即隨機性)增加。另一方面，附加的寄存器R3對於計算R0^2τ來說是必要的。
在某些情況下，算法I和I′可以足以保護指數。例如，如果相應的公共指數小，則RSA密碼系統由於其構造而總是暴露私有指數d的最高有效的一半。因此，使d的最高有效位為隨機的將不會為這種算法提供保護。
然而，對於其他算法來說以及在其他情形中，使d的所有位為隨機的將提供附加的安全性。
為此目的，在第二實施方案中建議針對隨機數i(j)選擇z＝b(i(j))＝dm-＞i(j)，並且在步驟E1的過程中，不從d中、而是從對應於具有權重i(j)-c(j)至i(j)-1的d的位的、d的一些位中減去b(i)(其中c(j)是整數)，以便i(j)≥c(j)≥0。這可以通過以下指令來表示dm-＞i(j)-c(j)＜-dm-＞i(j)-c(j)-dm-＞i(j)。
優選地，如在序號i(j)的隨機化的步驟E1時，d的具有權重i(j)-c(j)至i(j)-1的位被改變，並且僅僅選擇每次執行一個隨機化，並且選擇在序號結束時利用在先前的隨機化步驟E1期間(而不是在該方法結束時)、也就是說在估計了部分結果x^(dm-＞i(j)-c(j))mod N之後所改變的d的最後一位來執行合併步驟。
這相當於施加條件i(j+1)≤i(j)-c(j)，i(j+1)是接下來的隨機化的索引。這使得不能利用附加的寄存器來存儲在先前的隨機化期間所改變的指數的位。同樣地，i(j)-c(j)＜0被選擇，以便i(j)-c(j)可以被用於為計算x^(dm-＞i(j)-c(j))mod N定義d的位的序號。
可以通過使用指示更新是否被授權的布爾信號σ來使該兩個條件變得具體只要i≥i(j)-c(j)，σ就具有無效值，而當i＜i(j)-c(j)時σ被激活。一旦i(j)-c(j)＜0，σ就也變得不可用。
如果(一致性條件)
di(j)-1→i(j)-c(j)≥dm→(j)(i(j)-1)-(i(j)-c(j))≥m-i(j)c(j)≥m-i(j)+1，則d的(m-i(j)+1)個最高有效位在隨機化步驟期間保持不變。
根據第二實施方案的第一變型，c(j)被選擇為等於m-i(j)+1。如果2.i(j)≥m+1，則在條件i(j)≥c(j)≥0下滿足條件c(j)≥m-i(j)+1。
因此，根據該變型所改變的SAM算法可以被寫為(算法II)輸入x，d＝(dm，...，d0)2輸出y＝x^d mod NR0＜-1；R1＜-1；R2＜-x，i＜-m；c＜--1；σ＜-1隻要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod N結束如果如果(2i≥m+1)並且(σ＝1)，則c＜-m-i+1否則σ＝0結束如果ρ＜-R{0，1}ε＜-ρ和(di-1-＞i-c≥dm-＞i)和σ如果ε＝1，則R1＜-R0；σ＜-0di-1-＞i-c＜-di-1-＞i-c-dm-＞i結束如果如果c＝0，則R0＜-R0xR1 mod N；σ＜-1結束如果c＜-c-1；i＜-i-1結束只要返回R0應該注意的是，在對於任何j來說c(j)＝i(j)的情況下，算法I對應於算法II。還應該注意的是，在算法II中，在算法的第一部分期間，滿足一致性條件(di(j)-1→i(j)-c(j)≥dm→i(j))，近似地認為di(j)-1→i(j)-c(j)和dm→i(j)是(m-i(j)+1)位的隨機數。應該注意的是，在該算法中，指數的所有位被隨機化。
根據第二實施方案的第二變型，c(j)被隨機地選擇，並且處於i(j)和m-i(j)+1之間。
先前已看出，條件c(j)≥m-i(j)+1必須被滿足。因此，通過形成c(j)＝m-i(j)+1+v(j)，必然滿足v(j)≥0。此外，在條件i(j)≥c(j)≥0下，得到2.i(j)≥m+1+v(j)。因此，v(j)的最大可能值是2.i(j)-m-1，並且因此當v(j)≥0時，參數c(j)＝m-i(j)+1+v(j)可以取集合{m-i(j)+1，...，i(j)}中的任何值。於是，可以通過隨機地在集合{m-i(j)+1，...，i(j))中選擇c(j)來使算法II一般化。
在算法II的特定例子中，這相當於用指令如果(2i≥m+1)並且(σ＝1)，則c＜-R{m-i+1，i}來代替指令如果(2i≥m+1)並且(σ＝1)，則c＜-m-i+1。
這給出以下算法III輸入x，d＝(dm，...，d0)2輸出y＝x^d mod NR0＜-1；R1＜-1；R2＜-x，i＜-m；c＜--1；σ＜-1隻要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod N結束如果如果(2i≥m+1)並且(σ＝1)則c＜-R{m-i+1，i}否則σ＝0結束如果ρ＜-R{0，1}ε＜-ρ和(di-1-＞i-c≥dm-＞i)和σ如果ε＝1，則
R1＜-R0；σ＜-0di-1-＞i-c＜-di-1-＞i-c-dm-＞i結束如果如果c＝0，則R0＜-R0xR1 mod N；σ＜-1結束如果c＜-c-1；i＜-i-1結束只要返回R0v(j)的大的值增加一致性條件(並且因此隨機化選擇)成功的概率。另一方面，這也減小滿足條件2.i(j)≥m+1+v(j)的索引i的可能的值。
布爾變量ρ的值ρ＝0的出現頻率是該方法的參數，該參數使得能夠根據所設想的應用選擇性能和安全性之間的最佳折衷執行越多的隨機化步驟，對總計算時間的損害越大；相反，執行越少的隨機化步驟，就便於通過窮舉搜索進行更多的攻擊。
用於使附加運算的成本最小化的好的方法包括輕微地改變產生數ρ的隨機數發生器，以便當d-z的Hamming權重(根據所設想的實施方案，z可以具有作為b(i)的函數的不同值)小於d的Hamming權重時，ρ具有等於1的較大的概率，反之亦然。利用該技巧，該算法將傾向於選擇具有最小Hamming權重、也即最快速分支的情況。
僅僅應該注意的是，該算法不能總是選擇最快速分支，否則它將變為確定性的並且因此可容易地被攻擊。
根據本發明的第三實施方案，v位的隨機數u在該方法開始時被選擇，並且x^u被存儲在寄存器R1中。在該方法的過程中，數u優選地被多次改變，以便增加該方法中的隨機因數。
然後，在計算過程中，對於給定的序號i(j)，想知道，對於以致w＞u的d的v位的包w來說，計算x^w是否比x^(w-u)*x^u的計算更昂貴(在計算時間方面)。
為了回答該問題，只要確定是否H(w)＞H(w-u)+1就足夠了。H(w)是w的Hamming權重，並且表示運算x^w的成本。H(w-u)是x^(w-u)的Hamming權重，表示x^(w-u)。項「+1」表示x^(w-u)乘以x^u(x^u也被存儲)的成本。
如果x^w的計算比x^(w-u)*x^u的計算便宜，則該方法被繼續。否則，如果x^w的計算比x^(w-u)*x^的計算昂貴，則d的位的包w用數w-u來代替。當d的所有被改變的位都已被使用時，將執行合併步驟(這裡乘以x^u，這通過運算R0＜-R0xR1 mod N來表示)。
與前述的兩個實施方案相比較，該第三實施方案具有更快的優點，因為為了實現隨機化，每次選擇最快路徑(最小花費)。因此，實驗上表明該方法的複雜性大約為1.4。複雜性是為指數d的每一位所執行的、寄存器內容的乘法的平均數。不受保護的SAM算法的複雜性是1.5；根據本發明的第一或者第二實施方案的方法的複雜性對其來說稍微大於1.5。
此外，在該第三實施方案中，隨機源(數u)在該方法的外部。最後，所使用的資源(尤其是寄存器的數目)是相同的。
該第三實施方案可以具體地通過以下算法IV來表示輸入x，d＝(dm，...，d0)2參數v，k輸出y＝x^d mod NR0＜-1；R2＜-x；i＜-m；L＝{}只要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod N結束如果如果i＝m mod((m+1)/k))，則σ＜-1結束如果如果σ＝1並且L＝{}，則(在該方法的過程中改變數u)σ＜-0u＜-R{0，...，2v-1}；R1＝x^u mod N結束如果w＜-di-＞i-v+1h＜-H(w)如果w≥u，則Δ＜-w-u；hΔ＜-1+H(Δ)否則hΔ＜-v+2結束如果
ρ＜-R{0，1}如果[(σ＝0)^(i-v+1≥0)]^[(h＞hΔ)或((ρ＝1)並且(h＝hΔ))]，則(選擇實現x^(w-u))di-＞i-v+1＜-Δ；L＜-L∪{i-v+1}結束如果如果(iεL)，則R0＜-R0xR1 mod NL＜-L\{i}結束如果i＜-i-1結束只要返回R0在該例子中，集合L包含索引的列表，針對所述索引必須執行合併步驟。指令「如果di＝1，則R0＜-R0xR2 mod N結束如果」是SAM算法的針對i的每個值所執行的常規指令。
這裡，如果m+1可被k除，則指數d被劃分成相同大小的k個塊，或者否則指數d被劃分成與在一個單位內相同的大小的k個塊。
在塊每次開始時(也即對於i＝m mod((l+1)/k)))，變量σ被設為1。接下來，當σ等於1時，在執行新的隨機化設置之前，有必要等待集合L為空。在每個合併步驟中，從集合L中去除相應的索引i(j)(指令L＜-L\{i})。當集合L為空時，u的新的值可以被選擇，並且x^u藉助常規的SAM算法利用寄存器R1和R2來計算。
在每個塊的中間(σ＝0)，當h＞hΔ或(ρ＝1並且h＝hΔ)時執行一個或者多個隨機化步驟，並且每次(指令L＜-L∪{i-v+1})存儲索引i(j)-v+1，其中在所述索引時將有必要執行合併步驟。因此，有必要使i-v+1為有效的合併索引，也就是說i-v+1≥0(一致性條件)。在每個隨機化步驟中，如果h＞hΔ，則選擇執行便宜的運算x^(w-u)*x^u，並且相應地改變d的位(di-＞i-v+1＜-Δ)。如果h＜hΔ，則選擇實現便宜的x^w，並且不改變d。如果h＝hΔ，則隨機地(ρ隨機地等於0或者1)選擇實現x^(w-u)*x^u或x^w。
通過表明對於利用SAM算法執行長度1024的取冪來說必要的模數乘法的平均數是否被保護，給出●不具有保護的SAM1536次乘法●通過添加多個被加到指數d上的Φ(n)(r.Φ(n)，其中r為64位)(現有技術)而受保護的SAM1536+96次乘法●根據算法II或者III的受保護的SAM1536+10次乘法●根據算法I′的受保護的SAM1536+512次乘法。ρ，ρ是ρ的平均值●根據算法IV的受保護的SAM1443次乘法通過這些例子可以看出，根據本發明的受保護的算法在所執行的乘法(並且因此執行時間)方面是非常有效的。
權利要求
1.電子元件中的加密方法，在該加密方法期間通過在由從m至0變化的i為索引的循環中從左至右掃描d的位以及進行計算並且存儲在記憶裝置(R0)中來執行類型x^d的模取冪，其中d是m+1位的整數指數，在序號i每次循環時，所更新的部分結果等於x^b(i)，b(i)是指數d的m-i+1個最高有效位(b(i)＝dm-＞i)，所述方法的特徵在於，在隨機選擇的序號i(j)的循環結束(i＝i(0))時，執行隨機化步驟E1，在該隨機化步驟E1期間E1從在所述方法中還未被使用的d的位(di-1-＞0)的一部分中減去隨機數z(z＝b(i(j))，z＝b(i(j))·2τ，z＝u)，然後在已經使用了通過隨機化步驟E1所改變的d的位之後，執行合併步驟E2，在該合併步驟E2期間E2記憶裝置的內容(x^b(i))乘以一個數的結果被存儲(R0＜-R1xR0)在記憶裝置(R0)中，所述數是寄存器(R1)中所存儲的x^z的函數。
2.按照前述權利要求所述的方法，其中，當在0和m之間隨機選擇的序號i(j)(i＝i(0)，i＝i(1)，…)的不同循環結束時，步驟E1被重複一次或者多次。
3.按照前述權利要求所述的方法，其中，在每次循環i時，隨機地(ρ＝1)決定是否執行步驟E1。
4.按照權利要求1至3之一所述的加密方法，其中，數z(z＝b(i(j))，z＝b(i(j))·2τ)是指數d的函數，其中，在隨機化步驟期間，記憶裝置的內容(x^b(i))乘以寄存器(R1)的內容的結果也被存儲(R1＜-R0xR1)在所述寄存器(R1)中。
5.按照權利要求4所述的方法，其中，在等於0的序號i的最後一次循環之後，執行合併步驟E2。
6.按照前述權利要求所述的方法，在該方法期間，在步驟E1期間，從d中減去數b(i)。
7.按照權利要求6所述的方法，在該方法期間，以下被實現輸入x，d＝(dm，…，d0)2輸出y＝x^d mod NR0＜-1；R1＜-1；R2＜-x，i＜-m只要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod Nρ＜-R{0，1}如果((ρ＝1)並且di-1→0≥dm→i，則d←d-dm-＞iR1＜-R1xR0 mod N結束如果i＜-i-1結束只要R0＜-R0xR1 mod N返回R0。
8.按照權利要求5所述的方法，在該方法期間，如下改變步驟E1E1從d中減去等於g.b(i)的數，g是正整數；取當前的部分結果(x^b(i))的g次冪，並且將結果存儲在寄存器(R1)中。
9.按照前述權利要求所述的方法，其中，g等於2τ，τ是在0和T之間所選擇的隨機數。
10.按照前述權利要求所述的方法，其中，以下被實現輸入x，d＝(dm，…，d0)2輸出y＝x^d mod NR0＜-1；R1＜-1；R2＜-x，i＜-m只要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod Nρ＜-R{0，1}；τ＜-R{0，…，T}如果((ρ＝1)並且(di-1→τ≥dm-i))，則di-1→τ←di-1→τ-dm-＞iR3＜-R0隻要(τ＞0)，進行R3＜-R3^2mod N；τ＜-τ-1結束只要R1＜-R1xR3 mod N結束如果i＜-i-1結束只要R0＜-R0xR1 mod N返回R0。
11.按照權利要求1至4之一所述的方法，其中，在序號結束時利用在步驟E1期間所改變的d的最後一位來執行合併步驟E2。
12.按照權利要求11所述的方法，在該方法的過程中，在步驟E1期間，從具有序號i(j)-c(j)至i(j)-1的d的位中減去數b(i)，c(j)是整數，並且將記憶裝置的內容(x^b(i(j)))存儲在寄存器(R1)中。
13.按照前述權利要求所述的方法，在該方法的過程中，在序號i(j+1)的循環期間，只要i(j+1)≤i(j)-c(j)，就隨機地選擇執行步驟E1。(σ＝1自由信號)。
14.按照權利要求12或者13所述的方法，其中，c(j)等於m-i(j)+1。
15.按照前述權利要求所述的方法，在該方法期間，以下步驟被執行輸入x，d＝(dm，…，d0)2輸出y＝x^d mod NR0＜-1；R1＜-1；R2＜-x，i＜-m；c＜--1；σ＜-1隻要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod N結束如果如果(2i≥m+1)並且(σ＝1)，則c＜-m-i+1否則σ＝0結束如果ρ＜-R{0，1}ε＜-ρ和(di-1-＞i-c≥dm-＞i)和σ如果ε＝1，則R1＜-R0；σ＜-0di-1-＞i-c＜-di-1-＞i-c-dm-＞i結束如果如果c＝0，則R0＜-R0xR1 mod N；σ＜-1結束如果c＜-c-1；i＜-i-1結束只要返回R0。
16.按照權利要求12或者13所述的方法，其中隨機地在i(j)和m-i(j)+1之間選擇c(j)。
17.按照前述權利要求所述的方法，在該方法期間，以下被實現輸入x，d＝(dm，…，d0)2輸出y＝x^d mod NR0＜-1；R1＜-1；R2＜-x，i＜-m；c＜--1；σ＜-1隻要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod N如果(2i≥m+1)並且(σ＝1)則c＜-R{m-i+1，i}否則σ＝0ε＜-ρ和(di-1-＞i-c≥dm-＞i)和σ如果ε＝1，則R1＜-R0；σ＜-0di-1-＞i-c＜-di-1-＞i-c-dm-＞i結束如果如果c＝0，則R0＜-R0xR1 mod N；σ＜-1結束如果c＜-c-1；i＜-i-1結束只要返回R0。
18.按照權利要求1至2之一所述的方法，其中，數z是隨機選擇的v位的數u(z＝u)，並且數z獨立於指數d。
19.按照前述權利要求所述的方法，其中，在步驟E1期間，從d的v位的包w中減去數u。
20.按照前述權利要求所述的方法，在該方法期間●如果H(w-u)+1＜H(w)，則選擇執行隨機化步驟E1，●如果H(w-u)+1＞H(w)，則選擇不執行步驟E1，●如果H(w-1)+1＝H(w)，則隨機地選擇是否執行隨機化步驟E1。
21.按照前述權利要求所述的方法，在該方法期間，以下被實現輸入x，d＝(dm，…，d0)2參數v，k輸出y＝x^d mod NR0＜-1；R2＜-x；i＜-m；L＝{}只要i≥0，進行R0＜-R0xR0 mod N如果di＝1，則R0＜-R0xR2 mod N結束如果如果i＝m mod((m+1)/k))，則σ＜-1結束如果如果σ＝1並且L＝{}，則s＜-0u＜-R{0，…，2v-1}R1＝x^u mod N結束如果w＜-di-＞i-v+1h＜-H(w)如果w≥u，則Δ＜-w-u；hΔ＜-1+H(Δ)否則hΔ＜-v+2結束如果ρ＜-R{0，1}如果[(σ＝0)(i-v+1≥0)][(h＞hΔ)或((ρ＝1)並且(h＝hΔ))]，則di-＞i-v+1＜-Δ；L＜-L∪{i-v+1}結束如果如果(iεL)，則R0＜-R0xR1 mod NL＜-L\{i}結束如果i＜-i-1結束只要返回R0。
全文摘要
本發明涉及保護加密方法以防DPA類型的隱蔽信道攻擊，並且尤其涉及一種執行x^b類型的模取冪的加密方法，其中d是m+1位的整數指數，該方法在於在由在m和0之間變化的i為索引的循環中從左至右掃描d的位；並且在序號i每次循環時，計算等於x^b(i)的所更新的部分結果並且將其存儲在記憶裝置(R0)中，b(i)是指數的m－i+1個最高有效位(b(i)＝d
文檔編號G06F21/72GK1918543SQ200480041877
公開日2007年2月21日 申請日期2004年12月14日 優先權日2003年12月19日
發明者B·舍瓦利耶－馬梅 申請人:格姆普拉斯公司