實現橢圓曲線類型公共密鑰加密算法的電子部件中的對策方法
2023-08-11 01:21:31 1
專利名稱：實現橢圓曲線類型公共密鑰加密算法的電子部件中的對策方法
技術領域：
本發明涉及在電子部件中實現橢圓曲線類型公共密鑰加密算法的對策方法(countermeasure)。
在密鑰加密技術的傳統模型中，希望通過一個非安全信道通信的兩個人必須先同意一個加密密鑰K。加密函數和解碼函數實現相同的密鑰K。密鑰加密系統的缺點是上述系統要求在任何已加密的信息在非安全信道上發送之前密鑰必須先在兩個人之間通過一個安全信道優先通信。實際上，發現一個很安全的通信信道通常是困難的，尤其在分離兩個人的距離很遠時。安全信道意味著對它來說知悉或修改在它上面通過的信息是不可能的。這樣的安全信道可以通過連接由上述兩人所擁有的兩個終端的電纜來實現。
公共密鑰加密概念由Whitfield Diffie和Martin Hellman在1976年發明。公共密鑰加密技術使解決在非安全信道上密鑰的分布問題成為可能。公共密鑰加密的原理在於使用一對密鑰，一個公共加密密鑰和一個私有解碼密鑰。由觀察的計算點去從公共加密密鑰找到私有的解碼密鑰是不可行的。希望與B人交流信息的A人使用B人的公共加密密鑰。只有B人擁有與它的公共密鑰相關的私有密鑰。因此只有B人能夠破譯送給他的信息。
密鑰加密技術上公共密鑰加密的另一個優勢是公共密鑰加密允許用電子籤名授權。
公共密鑰加密方案的第一個實施方案在1977年由Rivest Shamir和Adleman開發，他們發明了RSA加密系統。RSA安全性是基於把一個是兩個質數乘積的大數進行因式分解的難度。
其後，提出了很多公共密鑰加密系統，它們的安全性基於不同的計算問題(這個列表不是詳細無遺的)-Merckle-Hellman背包(backpack)這個加密系統基於子集的和的問題的難度。
-McEliece
這個加密系統基於代數代碼的理論。它基於線性代碼的解碼問題。
-E1 Gamal這個加密系統基於有限域中離散對數的難度。
-橢圓曲線橢圓曲線加密系統構成了對已有加密系統的修正以把它們應用於橢圓曲線領域。
橢圓曲線在加密系統中的使用分別由Victor Miller和NealKoblitz在1985年提出。橢圓曲線的實際應用早在二十世紀九十年代就被注意到了。
基於橢圓曲線的密碼系統的優勢是它們用較小的密鑰尺寸提供等價於其它密碼系統的安全性。密碼尺寸中的這個存儲減小了存儲要求並縮短了計算時間，這使得橢圓曲線的使用尤其適合於智慧卡類型的應用。
在一個有限域GF(q^n)(q是一個質數，n是一個整數)上的一個橢圓曲線是點(x，y)的集合且x(X-軸)和y(Y軸)屬於GF(q^n)，方程式的解為y^2＝x^3+ax+b如果q大於或等於3及y^2+x*y＝x^3+a*x^2+b如果q＝2在加密中用得最多的兩類橢圓曲線是下面兩類1)在有限域GF(p)(整數模p的集合，p是一個質數)上定義的曲線，它的方程為y^2＝x^3+ax＝b2)定義在有限域GF(2^n)上的橢圓曲線，它的方程為y^2+xy＝x^3+ax^2+b對這兩類曲線中的每一類來說，定義點的加法操作如下給定兩個點P和Q，和R＝P+Q是曲線上的一個點，它的坐標按照Alfred JMenezes的著作「橢圓曲線公共密鑰密碼系統」中所給出的公式用點P和Q的坐標來表示。
這個加法操作使定義一個標量乘法操作成為可能給定屬於橢圓曲線的一個點P和一個整數d，P由d標量乘的結果是Q＝P+PP+…..+d次P。
橢圓曲線上加密算法的安全性基於橢圓曲線上離散對數的難度，上述問題包括，用屬於橢圓曲線E的點Q和P來找到這樣的整數x使得Q＝x.P，如果存在這樣的x的話。
有很多基於離散對數問題的加密算法。
這些算法可以被很容易地移植到橢圓曲線上。這樣就能夠用算法提供鑑定，機密性，完整性校驗和密鑰交換。
基於橢圓曲線的大部分加密算法的一個共同點是它們包含一個定義在有限域上的橢圓曲線作為參數及該橢圓上的一個點P。私有密鑰是一個隨機選中的整數d。公共密鑰是曲線Q上的一個點，而Q＝d.P。這些加密算法通常都涉及點R＝d.T的計算中的標量乘法，其中d是密鑰。
在這一節中描述了一個基於橢圓曲線的加密算法。這個方案類似於E1 Gamal加密方案。消息m被加密如下加密人員隨機選擇一個整數k並計算曲線上的點k.P＝(x1，y1)和k.Q＝(x2，y2)以及整數c＝x2+m。m的密碼是三元組(x1，y1，c)。
擁有d的解碼人員通過計算(x』2，y』2)＝d(x1，y1)和m＝c-x』2來破譯m。
為了實現前面所描述的計算方法中必要的標量乘法，有幾種現有的算法「加倍與和」算法；「加-減」算法；加法鏈算法；帶窗口算法；有符號表示算法；這個列表並不完整。最簡單且使用最多的算法是「加倍與和」算法。「加倍與和」算法把屬於一個給定橢圓曲線的點P和一個整數d作為它的輸入。整數d被表示為d＝(d(t)，d(t-1)，….，d(0))，這裡d(t)，d(t-1)，….，d(0)是d的二進位表示，d(t)和d(0)分別是最高和最低有效位。算法返回點Q＝d.P作為輸出。
「加倍與和」算法包括下面三個步驟
1)用點P的值初始化點Q2)對i從t-1到0，執行2a)用2Q替代Q2b)如果d(i)＝1用Q+P替代Q3)返回Q越來越明顯的是智慧卡上的橢圓曲線類型公鑰加密算法的實現容易受到包括能夠找到私有解碼密鑰的對當前消耗的微分冪(differential power)分析在內的攻擊。這些攻擊被認為是DPA攻擊，DPA是微分冪分析的首字母縮寫。這些DPA攻擊的原理是基於執行指令的微處理器的當前消耗根據被處理的數據項而變化的事實。
特別地，當一條指令正在處理一個其中有一不變的特定位的數據項時，這裡其它位的值可以變化，對與指令相關的當前消耗的分析根據特定位取值0或1顯示指令的平均消耗而不是相同的。DPA類型的攻擊因此能夠得到在一個加密算法被執行時由卡的處理器操縱的中間數據上的附加信息。這個附加信息在某些情況下揭示了解碼算法的私有參數，使加密系統不夠安全。
在本文檔的剩餘部分中給出了一個橢圓曲線類型算法上的DPA攻擊方法的描述，它執行包括點P由整數d，d是密鑰，標量乘在內的操作。這個攻擊直接揭示了密鑰d。它因此嚴重危脅智慧卡上橢圓曲線的實現的安全。
攻擊的第一步是對應前面所述及的「加倍與和」算法的執行為N個不同的點P(1)，….p(N)記錄當前消耗。在一個基於橢圓曲線的算法中，智慧卡的微處理器將執行N個標量乘法d.P(1)，…..d.P(N)。
為了清楚地描述該攻擊，第一步是描述一個用於得到密鑰d的d(t-1)位的值的方法，這裡(d(t)，d(t-1)，….，d(0))是d的二進位表示，d(t)和d(0)分別是最高和最低有效位。然後給出能夠找到d的值的算法的描述。
點P(1)到P(N)被按照4.P的橫坐標的最後一位的值組合在一起，這裡P指示點P(1)到P(N)中的一個。第一組由其4.P的橫坐標的最後一位等於1的點P組成。第二組由其4.P的橫坐標的最後一位等於0的點P組。對應於每一組計算當前消耗的平均值，並計算這兩個平均值之間的差分曲線。
如果d的d(t-1)位等於0，前面所述的標量乘法算法計算4.P的值並把它存儲在存儲器中。這意味著當該算法在智慧卡中被執行時卡的處理器將實際計算4.P。這種情況下，在第一個消息組中，由微處理器操縱的數據項的最後一位總是1，而第二組中被操縱數據項的最後一位總是0。對應於每一組的當前消耗的平均值因此是不同的。因此在兩個平均值的差分曲線中顯現出一個微分當前消耗的峰值。
另一方面如果d的d(t-1)位等於1，前面所述的求冪算法並不計算4.P。當算法在智慧卡中被執行時，微處理器因此從不操縱數據項4.P。因此沒有微分消耗的峰值出現。
這個方法因此能夠確定d的d(t-1)位的值。
下列節中所描述的算法是前面算法的概括。它能確定密鑰d的值輸入由對應由智慧卡執行的N個計算表示為P(1)到P(N)的N個點定義，輸出由整數h定義。
上述算法實現為下面三個步驟1)執行h＝1；2)對i從t-1到1，執行2)1)按照(4*h).P的橫坐標的最後一位的值給點P(1)到P(N)分類；2)2)為每一組計算當前消耗平均值；2)3)計算兩個平均值之間的差分；2)4)如果上述差分顯示了一個微分消耗的峰值，做h＝2*h，否則做h＝2*h+1；3)返回h。
上面的算法提供了一個整數h，例如d＝2*h或d＝2*h+1。為了得到d的值，它有能力測試兩個可能的假定。
所描述的DPA類型的攻擊因此能夠找到私有密鑰d。
本發明的方法在於設計三個對策以防止上述DPA攻擊。
第一個對策的方法存在於從私有密鑰d和橢圓曲線上點的數目N計算一個新的解碼密鑰d』中，而任意加密信息用d』解碼的結果與用d的結果相同。
在基於橢圓曲線的使用的加密算法執行操作Q＝d.P，這裡d是密鑰Q是曲線上的一個點，的情況下，Q＝d.P的計算由下面四步中的方法取代1)確定一個安全性參數s；實踐中s可以被設置為接近30.
2)提取一個0和2^s之間的隨機數k。
3)計算整數d』＝d+k*n。
4)計算Q＝d』.P。
第一個對策的方法包括涉及整數d』更新的兩個變量。第一個變量包括在解碼算法的每一個新的執行處按照前面所描述的方法計算一個新的解碼整數d』。第二個變量包括在解碼算法的每一個新的執行處遞增一個計數器。當這個計數器達到一個固定的值T時，按照前面所述的方法計算一個新的解碼整數d』，計數器被重新設置為0。實踐中可取T＝16。
第一個對策的方法因此能夠通過改變解碼整數d使前面所述的DPA攻擊不可能實現。
第二個對策的方法適用於前面所述曲線的第一類，也就是定義在有限域上有方程y^2＝x^3+ax+b的曲線。第二個對策的方法在於在每個新的執行上使用一個隨機計算模數。這個隨機模數的形式為p』＝p*r，其中r是一個隨機整數。在基於橢圓曲線的算法中執行的標量乘法操作Q＝d.P這時按照下面方法分五步執行1)確定一個安全參數s；實際應用中s可取接近60的數。
2)提取一個隨機數r，它的二進位表示佔據s位。
3)計算p』＝p*r。
4)執行標量乘法操作Q＝d.P，操作由模數p』執行。
5)執行點Q的坐標對模數p』的減法操作。
第二個對策的方法包括兩個涉及到整數r更新的變量。第一個變量用於在譯算法的每一個新的執行處按照前面所描述的方法計算一個新的整數r，第二個變量用於在解碼算法的每一個新的執行處遞增一個計數器。當這個計數器達到一個固定的值T時，按照前面所述的方法計算一個新的整數r，計數器被重新設置為0.實踐中可取T＝16。
第三個對策的方法在於「屏蔽」點P，希望通過把一個隨機點R加到P上來把標量乘法算法用於點P。
點P由整數d按照Q＝d.P的標量乘法的方法包括下面五個步驟1)在曲線上提取一個隨機點R。
2)計算P』＝P+R。
3)標題乘法操作Q』＝d.P』。
4)標量乘法操作S＝d.P。
5)計算Q＝Q』-S。
第三個對策的方法包括三個變量。第一個變量用於在解碼算法的每一個新的執行上遞增一個計數器。當解碼算法第一次被執行時，算法被按照上面所描述的五步方法執行。只要計數器還沒到限定值T，上面所述方法的步驟1和4就不執行，點R和S保持在前面執行中所取的值。當計數器達到限定值T時，解碼方法被按照前面五步中所描述的方法實現，計數器被重新設置為0.實際應用中可取T＝16。
第二個變量用於卡初始時在存儲器中有兩個橢圓曲線上的點使S＝d.R。前面解碼算法的步驟1和4被下面的步驟1』和4』取代1』)用2.R代替R。
4』)用2.S代替S。
第三個變量用於以在解碼算法的每一個新的執行處遞增計數器為特徵的第二個變量的更正。當解碼算法第一次被執行時，算法被按照上面所描述的第二個變量的五步方法執行。只要計數器還沒到限定值T，上面所述方法的1』和4』步就不被執行，點R和S保持在前面的執行中所取的值。當計數器達到限定值T時，解碼方法被按照前面五步中所描述的方法實現，計數器被重新設置為0.實際應用中可取T＝16。
上面三個對策方法的應用能夠防止任何基於橢圓曲線的加密算法遭到前述的DPA攻擊。已有的三個對策方法都與對方兼容能夠應用於上述對策方法中的RSA解碼算法1，2或3。
權利要求
1.一種在電子部件中基於使用存在於計算中的橢圓曲線實現公鑰加密算法的對策方法，使用密鑰d和上述橢圓曲線上點的個數n來計算一個新的解碼整數d′，用d′按照解碼算法對任何加密信息進行解碼能給出與用d通過執行操作Q＝d*P相同的結果，P是曲線上的一個點，該方法特徵是它包括四個步驟1)確定一個安全參數s；實際應用中s可取為接近30的數。2)提取一個0與2^s之間的隨機數k。3)計算整數d′＝d+k*n。4)計算Q＝d′.P。
2.依照權利要求1的對策方法，其特徵是第一個變量用於在解碼算法的每一個新的執行處計算一個新的解碼整數d′。
3.依照權利要求1的對策方法，其特徵是第二個變量用於在解碼算法的每一個新的執行處遞增一個計數器直到達到一個固定值T。
4.依照權利要求3的對策方法，其特徵是，一旦達到了值T，按照權利要求1中的方法計算一個新的加密整數且計數器被重新設置為0。
5.依照權利要求3的對策方法，其特徵是值T等於整數16。
6.在實現基於定義在有限域GF(p)上的橢圓曲線的使用的公共密鑰加密算法的電子部件中的對策方法，p是一個質數，曲線方程為y^2＝x^3+ax+b，在於在每個新的執行上使用用一個形式為p′＝p*r的隨機計算模數並有一個點P，其中r是一個隨機整數，其特徵是上述方法用五步執行標量乘法操作1)確定一個安全參數s；實際應用中s可取為接近60的數。2)提取隨機數r，它的二進位表示佔用s位。3)計算p′＝p*r。4)執行標量乘法操作Q＝d.P，操作由模數p′執行。5)執行點Q的坐標減去模數p的操作。
7.依照權利要求6的對策方法，其特徵是在解碼算法每個新的執行處計算一個新的整數。
8.依照權利要求6的對策方法，其特徵是計數器在解碼算法每個新的執行處被遞增1.
9.依照權利要求8的對策方法，其特徵是當計數器達到值T時它被重新設置為0.
10.依照權利要求8或9的對策方法，其特徵是值T等於16.
11.在實現基於橢圓曲線使用的公共密鑰加密算法的電子部件中的對策方法在於使用密鑰d和上述橢圓曲線上點的個數n來計算一個新的解碼整數d′使得用d′通過解碼算法對任何加密信息進行解碼給出與用d通過執行操作Q＝d*P相同的結果，P是橢圓曲線上的一個點，標量乘法算法被應用在它上面，按照方程Q＝d*P由整數d給它加上一個隨機點R，該方法的特徵在於它包括下面五個步驟1)提取曲線上的一個隨機點。2)計算P′＝P+R。3)標量操作Q′＝d.P′。4)標量操作S＝d.R。5)計算Q＝Q′-S。
12.依照權利要求12的對策方法，其特徵是在解碼算法的每一個新的執行處計數器被遞增1直到等於值T。
13.依照權利要求12的對策方法，其特徵是當到達值T時計數器被重新設置為0.
14.依照權利要求12的對策方法，其特徵是在解碼算法的每一個新的執行處計數器被遞增1直到等於值T。
15.依照權利要求11的對策方法，其特徵是橢圓曲線在存儲器中有兩個點使得S＝d*R，步驟1和4被替換為步驟1′和4′1′)用2.R替代R。4′)用2.S替代S。
16.依照權利要求15的對策方法，其特徵是在解碼算法的每個新的執行處計數器被遞增1直到值T。
17.依照權利要求15的對策方法，其特徵是在解碼算法的每個新的執行處計數器被遞增1直到值T。
全文摘要
本發明涉及在電子部件中基於公共密鑰算法實現橢圓曲線的對策方法,包括通過進行運算Q=d*p,其中P是曲線上的點,計算新的解碼整數d′,例如基於私有密鑰d和所述橢圓曲線的點個數n在解碼算法的幫助下的加密消息的解碼,其中將d′作為d可以達到相同的結果。本發明的方法的特徵在於它包括4個步驟:1)確定保密參數s,其中在實際應用中,s不可能在30的附近,2)抽取隨機數k,範圍是0－21s,3)計算整數d′=d+k*n,4)計算Q=d′.P。
文檔編號G09C1/00GK1345496SQ00805519
公開日2002年4月17日 申請日期2000年3月22日 優先權日1999年3月26日
發明者J·S·科龍 申請人:格姆普拉斯公司