通過至少一個蒙哥馬利運算確定除餘數和對於密碼應用確定素數候選的製作方法

2023-05-17 19:55:01

通過至少一個蒙哥馬利運算確定除餘數和對於密碼應用確定素數候選的製作方法
【專利摘要】在一種用於確定第一值(b)模第二值(p')之後的除餘數的方法中利用第一值(b)作為因子之一和第二值(p')作為模執行(74.1)第一蒙哥馬利乘法，確定(74.2)校正因子，以第一蒙哥馬利乘法的結果作為一個因子和校正因子作為另一個因子和第二值(p')作為模，執行(74.3)第二蒙哥馬利乘法。在一個用於確定素數候選的方法中確定用於篩法的基礎值(b)，並且執行多個篩遍歷，在所述篩遍歷中分別確定(72)一個標記值(p')並且將標記值(p')的倍數在篩法中作為合數標記，其中在每個篩遍歷中利用包括至少一個蒙哥馬利運算的餘數確定方法確定(74)基礎值(b)對標記值(p')取模之後的除餘數。一種裝置和電腦程式產品具有相應的特徵。提到的方法可以在合適的平臺上有效地實現。
【專利說明】通過至少一個蒙哥馬利運算確定除餘數和對於密碼應用確定素數候選
【技術領域】
[0001]本發明一般地涉及可有效實現的密碼方法的【技術領域】。更具體地，本發明的第一方面涉及除餘數的確定，而本發明的第二方面涉及素數候選的確定一所述素數候選是利用一定的概率表示素數的值。本發明特別適合於在可攜式數據載體中的應用。這樣的可攜式數據載體例如可以是按照不同的構造形式的晶片卡(智慧卡)或晶片模塊或類似的資源受限的系統。
【背景技術】
[0002]用於素數確定的有效方法對於許多密碼應用來說是必須的。因此例如為了產生密鑰，在美國專利4405829描述的RSA方法中必須規定兩個秘密的素數，其乘積形成公鑰的一部分。該素數的大小取決於安全性要求並且通常為數百至數千位。可預見的是，所需要的大小在將來還將明顯增加。
[0003]總體上，素數搜索是在RSA密鑰產生中計算量最大的步驟。從安全性原因出發，通常要求，該密鑰產生通過數據載體本身執行。根據數據載體的類型的不同，該過程在數據載體的生產(例如完成或初始化或個性化)期間導致時間開銷，其可以強烈改變並且可能為數分鐘。因為生產時間是昂貴的，所以為了產生密鑰而需要的時間表示了極大的成本因素。由此值得期望的是，加速密鑰產生並且由此提高可攜式數據載體的生產設備的可實現的產量。
[0004]用於縮短生產時間的一個重要步驟是，使用用於素數搜索的有效方法，其還滿足關於產生的素數的一些邊界條件。這樣的方法已經被建議並且例如從申請公開DE 10 2004044 453 Al 和 EP I 564 649 A2 公知。
[0005]在RSA方法中，在密鑰產生之後進行的加密和解密過程是計算開銷相對大的。特別地對於具有有限的計算能力的可攜式數據載體由此通常採用在解密和產生籤名時使用中國剩餘定理(CRT = Chinese remainder theorem)並且由此也稱為RSA-CRT方法的實現。通過使用RSA-CRT方法，對於解密和產生籤名所需要的計算開銷大約以4倍減小。
[0006]為了準備RSA-CRT方法，在私鑰的確定時，除了這兩個秘密的RSA質因子之外計算另外的值並且作為私鑰的參數存儲。對此的詳細信息例如在申請公開W02004/032411A1中獲得。因為另外的RSA-CRT密鑰參數的計算通常也在可攜式數據載體的生產期間被執行，所以值得期望的是，為此也使用儘可能有效的方法。
[0007]許多可攜式數據載體包含協處理器，其支持特定的計算過程。特別地公知數據載體，其協處理器支持作為蒙哥馬利乘法公知的運算，其在Peter L.Montgomery的 文 章「Modular multiplication without trial division」， Mathematics ofComputation, Vol.44，n0.170，1985年4月，519-521頁中被描述。蒙哥馬利協處理器通常不支持具有對於密碼任務所需的位長度的「正常的」非模乘以及模乘。對於其他協處理器，可能成立的是，模乘或非模乘雖然被支持，但是不如蒙哥馬利乘法有效地被執行。除運算也不能或不能有效地或不能以對於密碼任務所需的位長度由許多常用的蒙哥馬利協處理器支持。值得期望的是，儘可能好地充分利用目前可用的或將來出現在市場上的協處理器的能力。

【發明內容】

[0008]因此，本發明的任務是，提供一種有效的技術，用於確定除餘數或用於確定素數候選。
[0009]按照本發明，上述任務完全或部分地通過具有權利要求1及權利要求8的特徵的方法、按照權利要求14的電腦程式產品和按照權利要求15的裝置，特別是可攜式數據載體解決。從屬權利要求涉及本發明一些構造的可選特徵。
[0010]本發明的第一方面從如下基本思路出發:為了確定除餘數，執行蒙哥馬利乘法而不是其他常用的模除。通過蒙哥馬利乘法引起的誤差然後通過另一個蒙哥馬利乘法來補償，其中合適確定的校正因子作為該另一個蒙哥馬利乘法的因子之一。該方法可以在許多常用的硬體平臺上比帶餘數的模除明顯更有效地實現。
[0011]在一些構造中，第一蒙哥馬利乘法是蒙哥馬利約簡，也就是具有I作為兩個因子之一的乘法。優選地，這兩個蒙哥馬利乘法以不同的蒙哥馬利係數實施。
[0012]校正因子在一些實施方式中作為2的模冪在循環中計算，其中每個循環過程具有中間結果的翻倍和條件減。而在其他實施方式中，校正因子作為具有正整數的校正因子指數和底數1/2的模冪。為此又可以採用蒙哥馬利運算。
[0013]本發明的第二方面從基本思路出發，確定篩法中的素數候選。從基礎值出發，在此執行多個篩遍歷(Siebdurchlaufe ),其中分別確定一個標記值並且將標記值的倍數在篩法中作為合數標記。此外在每個篩遍歷中，利用餘數確定方法確定基礎值模標記值後的除餘數，其在常用的硬體平臺上可特別有效地實現，因為其至少包括一個蒙哥馬利運算。
[0014]在優選的實施方式中(至少一個)標記值是素數。有利地，使用多個素數作為對於篩遍歷的標記值。篩法例如可以從基礎值出發，僅代表預定的步幅的數字。在一些實施方式中，實施其他素數測試，以從素數候選中確定可能的素數。在按照本發明的第二方面的方法的許多構造中使用按照本發明的第一方面的餘數確定方法。
[0015]在方法權利要求中的步驟的編號順序不應當理解為保護範圍的限制。而是還可以設置本發明的如下構造，在這些構造中這些步驟完全或部分按照其他順序和/或完全或部分交叉(交織)和/或完全或部分並行實施。
[0016]按照本發明的電腦程式產品具有程序命令，以實現按照本發明的方法。這樣的電腦程式產品可以是實體介質，例如半導體存儲器或磁碟或CD-ROM。然而電腦程式產品在一些實施方式中也可以是非實體介質，例如經過計算機網絡傳輸的信號。特別地，電腦程式產品可以包含在可攜式數據載體的生產過程中被引入到數據載體中的程序命令。
[0017]按照本發明的裝置特別地可以是可攜式數據載體，例如晶片卡或晶片模塊。這樣的數據載體以公知的方式包含至少一個處理器、多個在不同的技術中構造的存儲器和各種輔助組件。在本文件的選詞中，概念「處理器」應當既包括主處理器也包括協處理器。
[0018]在優選的擴展中，電腦程式產品和/或裝置具有與在本說明書中提到的和/或在從屬的方法權利要求中提到的特徵相應的特徵。【專利附圖】

【附圖說明】
[0019]本發明的其他特徵、任務和優點從以下對多個實施例和實施替選方案的描述得出。參見示意性附圖。
[0020]圖1示出了用於確定兩個素數以及RSA-CRT密鑰的其他參數的方法的流程圖，
[0021]圖2示出了用於確定素數候選的方法的流程圖，
[0022]圖3示出了對於圖1和圖2的方法的實施是合適的可攜式數據載體的組件的示意圖，
[0023]圖4示出了用於產生候選域的方法的流程圖，和
[0024]圖5示出了在使用蒙哥馬利運算的條件下具有底數1/2和正整數指數e的模冪計算的方法的示例流程。
【具體實施方式】
[0025]在本文件中特別地結合對RSA-CRT密鑰對的一個、多個或所有參數的確定來描述本發明。然而本發明也可以對於其他應用目的被採用，特別地用於如對於各種密碼方法所需的相對大的和隨機的素數的確定。
[0026]一般地，RSA-CRT密鑰對的參數從兩個秘密素數P和q以及公開指數e導出。在此公開指數e是與(p-1).(q-Ι)互素的數，其可以隨機選擇或固定預先給出。例如在一些實施例中使用第四個費馬(Fermat)素數F4 = 216+1作為公開指數e。公鑰包含公開指數e和公開的模N: =p*q。私有RSA-CRT密鑰除了包含兩個素數P和q之外還包含模逆pinv:=Pernod q 以及通過 dp: = e_1mod(p-l)及 dq: = e_1mod(q-l)定義的兩個 CRT 指數 dp 和 dq。
[0027]按照圖1的方法示出了在預先給出的公開指數e的情況下秘密的RSA-CRT密鑰的所有參數的計算。該方法由在圖1的左邊和右邊欄中示出的兩部分組成。第一部分(步驟
10、12、16和20)包括一個素數P和與之相關的密鑰參數七的確定，而第二部分(步驟24、26、30、34和38)涉及另一個素數q和密鑰參數d,和pinv的確定。
[0028]可以理解，該方法在實施替選方案中可以這樣變化，使得計算剛才提到的參數的僅一些。為此當一些密鑰參數被另外計算或根本不需要時，例如可以省略或縮短方法步驟。特別地可以設置，當僅需要確定唯一一個素數時，執行在圖1中示出的兩個方法部分的一個(也就是或者僅步驟10、12、16和20或者僅步驟24、26、30、34和38)。
[0029]在圖1中和其他附圖中實線箭頭示出了規則的程序流程，虛線箭頭示出了在一定的條件下一特別是當素數候選或預期的素數證明是合數時一被執行的替換的程序流程。點線箭頭表示了數據流。
[0030]在圖1中示出的流程在步驟10以第一素數候選m的產生開始，其滿足一定的邊界條件(特別是邊界條件m = 3mod4)。在此處描述的實施例中在每個素數候選m的確定時作出預先選擇，其確保，素數候選m不會已經通過小的素數(例如2，3，5，7，...)可除。具有預先選擇的合適的確定方法在圖2中示出並且在以下被詳細描述。
[0031]在步驟12中對素數候選m進行費馬測試。費馬測試是一種概率性素數測試，其將合數以高的概率作為合數來識別，而絕不會將素數錯誤地看作為合數。費馬測試基於費馬小定理，其說明，對於每個素數P和每個自然數a，成立關係:ap = amodp。反過來不一定成立，但是反例如此罕見，使得通過了費馬測試的素數候選m以幾乎確定的概率是一個素數。
[0032]如果素數候選m在步驟12中在費馬測試時被識別為合數，則跳回14到步驟10，在該步驟10中確定新的素數候選。否則方法繼續，其中素數候選m被看作為預期的素數P。
[0033]在步驟16中計算CRT指數dp,其通過dp: = e mod(p-l)定義。對此使用本身公知的反演方法。當e和p-Ι是互素的時,也就是當成立gcd(p_l, e) = I時，CRT指數dp作為公開指數e的模逆存在。如果不是這樣，則跳轉18到方法的開始。否則在步驟16中確定CRT指數dp並且方法然後在步驟20以預期的素數P的Miller-Rabin測試繼續。
[0034]Miller-Rabin 測試是從在 Journal of Number Theory I2, 1980,第 I28-138 頁發表的 Michael 0.Rabin 的文章 「Probabilistic algorithms for testing primality，，中公知的。在Miller-Rabin測試的每輪測試中將合數以一定的概率識別為合數，而素數絕不會被錯誤地看作為合數。Miller-Rabin測試的錯誤概率取決於測試輪數並且可以通過執行足夠多輪的測試來保持為任意小。
[0035]由於已經提到的在步驟12中的費馬測試的高的準確性，預期的素數在步驟20中的Miller-Rabin測試中被識別為合數的概率可以忽略。在步驟16中CRT指數dp的計算由於gcd(p-l，e)辛I而失敗並且必須執行跳轉18的概率相反地以數量級更高。由此更有效的是，在步驟20之前執行步驟16，因為由此避免了不需要的Miller-Rabin測試。
[0036]儘管如此，本發明還包括如下的實施例，在這些實施例中在Miller-Rabin測試之後才計算或者在另一個時刻計算CRT指數dp。此外在實施替選方案中可以建議，CRT指數dp的計算與在此描述的用於素數確定的方法分開地執行；於是可以省去步驟16。
[0037]在步驟20中執行Miller-Rabin測試，以便能夠數學地探測例如可以為2_1(1°的期望的最大錯誤概率。在Miller-Rabin測試中執行多輪測試，其數量取決於該錯誤概率。對於預期的素數P的一輪測試在於，隨機數被提高到((P-1)/2)次冪模P，並且在於檢查，結果是否是± I模P。在此假定邊界條件P = 3mod4。
[0038]在最不可能的情況下，即在預期的素數P在步驟20中的Miller-Rabin測試的一輪測試中被識別為合數的情況下，跳轉22到方法的開始。在其他情況下將素數P作為在此描述的方法的結果輸出。
[0039]在圖1的右邊欄中示出的第二方法部分除了步驟34之外是按照圖1的左邊欄的第一方法部分的重複，其中計算第二素數q。由此很大程度參見上面的解釋。
[0040]步驟24、26和30類似於步驟10、12和16。當在步驟24中選擇的素數候選m在步驟26中的費馬測試中被證明是合數時，跳轉28到在步驟24中對新的素數候選的選擇。否貝1J，在步驟30中計算CRT指數dq: = e_1mod(q-l)。如果e和q_l不是互素的,貝U進行到步驟24的跳轉32。否則，方法以預期的素數d,繼續。與在第一方法部分中類似地在此也進行修改，在所述修改中在另一個時刻結合在此描述的方法或與之分離地計算CRT指數d,。[0041 ] 在步驟34中進行組合的測試和反演方法,其中對於預期的素數q的Mi 11 er-Rabin測試的第一輪測試與逆Pinv: =P-1Hiodq的計算耦合。因為q是素數，所以逆Pinv可以利用費馬小定理確定為Pinv = P—1 = Ptr2Hiod q。因為P是隨機數，所以在該計算中可以利用小的額外開銷立即執行對於預期的素數q的第一輪Miller-Rabin測試，其中檢查，P的第((q_l)/2)次冪模q是否等於±1。
[0042]如果預期的素數q沒有通過第一輪Miller-Rabin測試，則在步驟34中進行到步驟24的跳轉36。否則在步驟38中進行Miller-Rabin測試的另外還需要的測試輪。如果該測試輪失敗，則在步驟24之後進行到新的素數候選的選擇的跳轉40。否則已知第二素數q，並且方法結束。
[0043]在一些實施方式中在圖1中示出的方法如下變化，即，不設置組合的測試和反演方法。由此例如可以替代步驟36而進行在步驟38中的附加一輪的Miller-Rabin測試。逆Pinv的計算於是可以作為單獨的步驟-作為在此描述的方法的部分或與其分離地-被執行，如果這樣的計算是根本上需要的話。由此例如逆Pinv在RSA-CRT計算時僅用於提高效率。在不使用中國剩餘定理的RSA計算中根本不需要逆pinv。
[0044]圖2示出了素數候選m的確定，如在圖1的步驟20和24中被執行的。在該描述的實施例中在此使用提供多個素數候選m的候選域。候選域例如可以是打包的位域(bitarray,位數組)S，其位S [i]說明，具有取決於位位置i的、與基礎值b的偏移的數字是否是素數候選m。
[0045]在按照圖2的方法中首先在測試42中檢查，是否存在一個合適的和非空的候選域。如果否，則在步驟44中產生滿足條件b = 3mod4的隨機的基礎值b。
[0046]在步驟46中然後產生候選域。作為用於候選域的數據結構，在本實施例中使用位域S，其位位置i分別相應於與基礎值b相差SWi的偏移(以SW作為步幅)。完成的候選域的每個位S[i]由此顯示，數字b+SWi是否能夠作為素數候選m被使用。
[0047]為了在步驟46中產生候選域，首先將所有的位S[i]初始化到第一值(例如值「I」)。然後按照厄拉多塞篩法的原理將與能夠被小的素數除盡的數字b+SWi相應的那些位s[i]改變到第二值(例如值「O」)。候選域的大小和篩遍歷的數量一根據可用的存儲容量一這樣選擇，使得總方法的平均運行時間被最小化。這是一個優化任務，其解取決於與用於失敗的費馬測試的開銷相比用於預先選擇的相對開銷。對於具有2048個位的RSA密鑰例如可以執行數千個篩遍歷，其中然後需要大約40個費馬測試用於確定素數P和q中的一個。
[0048]在步驟48中最後從填滿的候選域中選擇一個素數候選m。該選擇例如可以隨機地或按照預先給出的順序進行。在圖2中示出的方法的其他調用時將步驟48緊接著測試42進行，並且一直從曾經佔據的候選域中選擇另外的素數候選m，直到域為空或低於預先給出的最小填充量。
[0049]在圖1和圖2中示出的方法在一些實施方式中由可攜式數據載體的至少一個處理器執行。圖3示出了這樣的數據載體50，其例如作為晶片卡或晶片模塊構造。數據載體50具有微控制器52，其中以公知的方式將主處理器54、協處理器56、通信接口 58和存儲器組件60集成在唯一一個半導體晶片上並且通過總線62互相連接。
[0050]存儲器組件60具有多個按照不同的技術構造的存儲器陣列，其例如包括只讀存儲器64 (掩模編程ROM)、非易失性可覆蓋存儲器66(EEPR0M或快閃記憶體)和工作存儲器68 (RAM)。在此描述的方法以在只讀存儲器64和部分地也在非易失性可覆蓋存儲器66中包含的程序命令70的形式實現。
[0051]數據載體50的協處理器56構造為用於有效執行各種密碼運算。特別地對於在此描述的實施例重要的是，協處理器56支持具有如對於密碼應用所需的位長度的蒙哥馬利乘法。在一些構造中協處理器56不支持「正常的」模乘，從而這樣的乘法必須以極高的開銷通過主處理器54執行。
[0052]對於自然數X，y和奇數自然數m(其中X，ym)，χ和y關於R的蒙哥馬利乘積模m —般地通過如下來定義:
[0053]x*m』R y: = χ.y.R_1mod m
[0054]一般地在本文件中在式子「a = z modm」的模關係的說明中使用等號「=」以及定義符號「:=」，以表達，a是來自於(Z + Z) Π [O, W[中的清楚定義的元素，對於該元素
成立模關係。而符號表示「a = z modm」僅表達,成立等效的模m。
[0055]當蒙哥馬利係數R從上下文中得出時，在本文件中對於蒙哥馬利乘積通常也使用簡短的符號表示x*m y來替代詳細的符號表示x*m，R I。
[0056]儘管上面定義的蒙哥馬利乘法是模運算，但是其可以沒有除法地被實現，如本身公知的並且例如在開頭提到的文章「Modular multiplication without trial division」中描述的那樣。對於蒙哥馬利乘法，需要兩個非模乘，一個事先根據m和R計算的輔助值，一些加法和從m的終止條件減法。這些計算可以通過協處理器56有效執行。
[0057]在目前商業上可得的微控制器52中公知協處理器56』、56"、56』 』 』的構造，其不是精確地執行上面定義的蒙哥馬利乘法，而是執行其修改。對於這些修改的原因主要在於，對於是否應該執行蒙哥馬利乘法的終止條件減法的判斷，可以按照不同的方式來優化。一般地，修改的協處理 器56』、56"、56』』』在蒙哥馬利乘法的計算中提供如下結果，該結果與上面定義的結果潛在地以模m的小的數倍而不同。此外這樣擴展對於在修改的協處理器56』、56"、56』』』中因子χ和y的允許的值域，使得計算的結果始終又將允許的輸入值表示為蒙哥馬利乘法的因子。
[0058]更具體而言，第一修改的協處理器56』計算第一修改的蒙哥馬利乘積χ*』 ffl y，其如下定義:
[0059]X*，m y: = (χ.y.Ir1Iiiod m) +k.m
[0060]在此對於確定的寄存器大小η為R = 2n，n是16的倍數。用於因子χ和y的值域被擴展到[0，...，R-1]，並且k是自然數，其這樣小，使得成立χ*』 ffl y〈R。
[0061]而第二修改的協處理器56〃計算第二修改的蒙哥馬利乘積x*〃m y，其如下定義:
[0062]x*"m y: = (χ.y.Tri mod m) _ ε.m
[0063]因子χ和y在此是在範圍_m≤x，y〈m中的整數。此外成立ε e {0，1}，並且指數η』對於精度P = 1，2或4具有值η』 = η+16ρ、塊尺寸c (其中160≤c≤512)，其是32的倍數、和寄存器大小n = c.p。對於模m成立m〈2n，並且值R定義為R: = 2n』。
[0064]最後，第三修改的協處理器56〃』計算第三修改的蒙哥馬利乘積x*〃’m y，其如下定乂:
[0065]χ*"，m y: = (χ.y.2-t.c mod m) + ε.m
[0066]因子χ和y在此是自然數(其中眾2卜。並且y〈2*m.)。此外成立ε e {0，1}。塊大小c是固定的並且為c = 128。用於因子χ的寄存器大小為t*c。用於其他變量的寄存器大小利用η表示並且為塊大小c的倍數。當成立n = t 時，則因子χ不是需要滿足條件χ〈2ι 『c而是僅需要滿足條件x〈max {2.m, 2n}。
[0067]當如下並不起作用或從前後關係中得出時，即，涉及的恰好是按照初始給出的定義的協處理器56的蒙哥馬利乘積x*m y還是協處理器56』、56"、56』 』 』之一的三個修改的蒙哥馬利乘積X*』 m y及X*〃m y及X*"』 m y之一，在本文件中兩個因子關於模m的蒙哥馬利乘積一般地通過X*m I表示。
[0068]當輸入值X，y首先藉助蒙哥馬利變換被變換到其相應的蒙哥馬利表達X』，?並且然後結果值從其蒙哥馬利表達X』被變換回值X時，一般地可以將每個「正常的」模乘X.y=z mod m通過蒙哥馬利乘法X』 *m y』 = z』來代替。蒙哥馬利變換例如可以通過計算X』:= x*R mod m來進行。在反變換中可以有效地通過具有因子I的蒙哥馬利乘法，也就是通過計算 z: = z』*ml,來確定結果 z: = z』.Ir1IIiod m。
[0069]由於所需的來回變換，通過蒙哥馬利乘法來代替唯一的模乘通常不是有效的。但是當先後要執行多個乘法時-例如在模冪中那樣，則可以將這些乘法完全在蒙哥馬利數字空間中執行。於是僅需要在計算序列的開始時的唯一的前向變換和在計算序列結束時的唯一的反向變換。
[0070]按照剛才描述的原理，在圖1和圖2中示出的方法中可以將唯一的或全部模乘作為蒙哥馬利乘法來實現。可以理解，在此在蒙哥馬利數字空間中進行的計算片段應當儘可能被綜合，以便減少所需的前向和反向轉換的數量。加法和減法可以在「正常的」數字空間中和在蒙哥馬利數字空間中沒有區別地進行。
[0071]當數據載體50具有雖然支 持蒙哥馬利乘法但是不支持正常的模乘的協處理器56，、56"、56』』』時，蒙哥馬利乘法的使用是特別有利的。即使協處理器56』、56"、56』』 』支持兩種乘法種類，也通常更有效地執行蒙哥馬利乘法。根據所需的變換的數量-特別是與反向變換相比更麻煩的前向變換的數量-得到極大的節省，甚至在蒙哥馬利乘法比正常的模乘僅稍微有效地要被執行時。
[0072]在此處描述的實施例中，在圖1和圖2中示出的方法特別地關於步驟46中(圖
2)的候選域的產生被優化。如上所述，該描述的解從如下基本思路出發，即，通過按照厄拉多塞篩法原理的篩過程來確定素數候選。但是在這裡描述的實施例中篩法在一個隨機的基礎值b的情況下開始，該基礎值已經大約具有待確定的素數的數量級，並且其包含(以步幅Sff)分別與值b+SWi相應的項目。
[0073]此外在這裡描述的實施例中僅執行預先給出數量的篩遍歷，分別具有一個小的素數P』或者多個素數的乘積P』作為標記值r，r』。在這些篩遍歷之後在篩法中剩餘的值(其稱為素數候選m)僅以一定的概率表示一個素數。如上所述，篩遍歷的數量在對於整個方法的計算時間的優化過程中被規定。例如可以執行數千個篩遍歷，其中然後在篩法中剩餘的數字以大約2.5%的概率是一個素數。
[0074]因為篩法不是在零的情況下開始，所以對於每個篩遍歷，確定作為篩遍歷的基礎的、基礎值b模標記值p』後的餘數。從該餘數中然後確定第一個要從篩法中刪除的合數b+Sffk,並且從該數字b+SWk 出發將其他倍數b+SWk+SWp』，b+Sffk+2 *SWp』，b+Sffk+3 *SWp』，..?從篩法中刪除。
[0075]這裡描述的實施例特別地涉及剛才提到的餘數z: = b mod p』的有效確定。該實施方式的基本思路是，為了確定餘數z，不使用具有餘數的「正常的」模除，而是使用具有至少另一個校正步驟的蒙哥馬利運算。該蒙哥馬利運算特別地可以是具有P』作為模的蒙哥馬利約簡。蒙哥馬利約簡在此理解為其中因子之一具有值I的蒙哥馬利乘法。
[0076]在第一實施例中假定，對於循環過程採用的標記值P』 -例如素數-具有d位(例如16位)的寬度，並且基礎b具有η.(!位的寬度。然後執行蒙哥馬利約簡b*p，:nl，其按照定義提供值b.UinHiodp^對於bmodp』的期望結果，由此得出以因子2_d『nmodp』的「誤差」，其通過一個或多個校正步驟補償。
[0077]所需的校正可以以任意的方式執行。但是在本實施例中設置，為此又執行蒙哥馬利運算，也就是關於蒙哥馬利係數2d來模p』的蒙哥馬利乘法。
[0078]通過蒙哥馬利乘法，產生與期望結果的另一個偏差，也就是以附加的因子2_d modP』的偏差。由此有利的是，在校正時就考慮該附加的因子，使得該校正作為蒙哥馬利約簡的結果與因子2d.ZdImodp' =2d『(n+1)modp』的蒙哥馬利乘法被執行。
[0079]總體上由此如下計算餘數b mod p』:
[0080](b*p』』2d.nl)*p』』2d2d.(η+1)—ρ』
[0081]在此校正因子2d『(n+1)m°dp』可以在特別簡單的方法中通過循環確定。從起始值I出發在該循環中在每個循環過程中分別將當前值翻倍，並且如果結果至少為P』，則將P』減去。
[0082]剛才描述的方法的以下表示詳細地反映了示例性計算流程。該表示涉及更一般的任務，對於在寄存器X中一個b位寬的值X和在寄存器Y中一個(η.(1)位寬的值Y確定在寄存器Z中的具有Ζ: =YmodX的餘數Ζ。顯然該方法容易地用於在此所需的對餘數ζ:=b mod p』的確定，其中將標記值P』存儲在寄存器X中和將基礎b存儲在寄存器Y中。但是該方法也可以結合另外的密碼計算被使用，在所述密碼計算中必須確定餘數:
[0083]方法A
[0084]輸入值:寄存器X中的d位寬的值(例如素數P』 )
[0085]寄存器Y中的η.d位寬的值(例如基礎b)
[0086]寄存器:B，C，X，Y，Z
[0087]輸出值:寄存器Z中的餘數Y mod X
[0088]方法流程:
[0089]設置B = Y*2-d.n mod X (A.1)
[0090]設置C = 2d.(n+1)mod X (A.2)
[0091 ]設置 Z = B*C*2-d mod X (A.3)
[0092]在行(A.1)中的過程通過蒙哥馬利乘法Y*x，2d『nl執行，其因子Y和I具有不同的長度。在行(A.3)中的過程通過具有因子B和C的蒙哥馬利乘法B*x，2d C執行。
[0093]但是一般的方法A可以被優化，如在以下對於修改的方法A』和A"所示的那樣。
[0094]如果標記值是素數P』，則可以取消第一蒙哥馬利乘法。
[0095]方法A』
[0096]輸入值:寄存器X中的d位寬的值(例如素數P』 )
[0097]寄存器Y中的η.d位寬的值(例如基礎b)
[0098]寄存器:C，X，Y，Z
[0099]輸出值:寄存器Z中的餘數Y mod X
[0100]方法流程:
[0101]設置C = 2d.n mod X (A，.2)
[0102]設置Z = Y*C*2-d.n mod X (A，.3)
[0103]在行(A』.2)中的過程在於，將寄存器C設置到取決於X的校正值。在行(A』.3)中的過程通過蒙哥馬利乘法Y*x，2d『n C執行，其因子Y和C具有不同的長度。
[0104]相反如果執行同時具有兩個(或多個)標記值r和r』的標記流程，則以下構造是有利的。
[0105]方法A"(示例性對於兩個素數r和r』)
[0106]輸入值:寄存器X中的d位寬的值(例如素數r和r』的乘積p』 = r*r』)
[0107]寄存器Y中的η.d位寬的值(例如基礎b)
[0108]寄存器:B,C，C，，X，X』，Y, Z, Z』
[0109]輸出值:寄存器Z中的餘數Ymodr
[0110]寄存器Z』中的餘數Ymod r』
[0111]方法流程:
[0112]設置B = Y*2+nmodX (A".1)
[0113]設置X= r(A".a)
[0114]設置C = 2d.(n+1)mod X (A".2.a)
[0115]設置Z = B*C*2 -d mod X (A ".3.a)
[0116]設置X』 = r(A".b)
[0117]設置C』 = 2d.(n+1)mod X』 (A".2.b)
[0118]設置Z』 = B*C』 *2-d mod X』 (A ".3.b)
[0119]在行(A".1)中的過程如在方法A中那樣通過蒙哥馬利乘法Y*x,2d『nl執行，其因子Y和I具有不同的長度。在行(A".3.a)和(A".3b)中的過程如在方法A中那樣通過具有因子B和C的蒙哥馬利乘法B*x，2d C執行。
[0120]相應地對於每個標記值計算餘數值(b MOD r和b MOD r』)，以便能夠將標記流程中的兩個標記值從篩法中刪除。
[0121]行(A.2), (Α，.2)和(A".2a和2b)中的模冪可以如上所述通過循環來實現，所述循環在d.(n+1)個循環過程中分別執行一個翻倍(以一個位位置向左逐位地移動)和一個條件減法。在此處使用的偽代碼符號表示中也就是例如可以將行(A.2)通過以下的行(A.2.1)-(A.2.5)來代替:
[0122]設置C= I (A.2.1)
[0123]執行d.(n+1)次 (A.2.2)
[0124]將C向左移動I個位 (A.2.3)
[0125]如果C ≤ X 則設置 C = C-X (A.2.4)
[0126]結束(A.2.5)
[0127]通過如下，即，在此描述的實施例將具有長被除數的除法通過至少一個蒙哥馬利乘法來代替，其特別好地適用於在不支持或不如蒙哥馬利乘法那樣有效地支持長除法的數據載體50中的使用。該配置在許多通常的數據載體50中給出，因為對於長除法的有效的硬體支持將會要求高的開銷。
[0128]因此例如具有協處理器56"的數據載體50根本不支持除法運算，而協處理器56』 』 』雖然提供除法功能，但是用於執行除法需要比用於相同位長度的蒙哥馬利乘法長大約128倍。相反在具有協處理器50』的數據載體50的情況下甚至有利的是，不使用在此描述的技術，因為在該數據載體50的主處理器54上可以實現對小的素數取模的快速餘數值計算。
[0129]可以理解，這些描述的方法步驟可以以不同的程度分布到數據載體50的主處理器54和協處理器56、56』、56"、56』』 』上。例如在具有協處理器56"的數據載體50的情況下有利的是，行(A.1)-(A.3)的所有的方法步驟可以由主處理器54執行，因為協處理器56"對於具有不同長因子的蒙哥馬利乘法工作效率不高並且此外限制於絕對值比模P』小的因子。相反在具有協處理器56"的數據載體50的情況下主處理器54相對慢並且不支持除法，而協處理器56』』』對於在此描述的方法非常合適。由此有利的是，對於行(A.1)-(A.3)的所有的方法步驟使用該協處理器56』 』 』。
[0130]圖4示例性示出了在步驟46 (圖2)中的候選域的產生的各個方法步驟。作為輸入值已經呈現在前面的步驟44中確定的基礎值b。方法包括預定數量的篩遍歷，在這些篩遍歷中分別執行步驟72-78。
[0131]在每個篩遍歷的開始在步驟72中確定標記值P』，其倍數在篩法中應當作為合數被標記。在至此描述的構造中標記值P』是具有例如最大16位長度的小的素數，而在另外的實施方式中合數一例如兩個或多個素數r，r"的乘積一作為對於素數r和r"的乘積p』=r*r』可 以作為標記值被使用。
[0132]在步驟74中然後確定基礎值b對標記值P』取模後的餘數。為此例如執行已經描述的方法A或在以下要示出的修改之一。按照圖4的步驟74包括三個子步驟74.1, 74.2和74.3。在與方法A的行(A.1)相應的第一子步驟74.1中，執行蒙哥馬利約簡Y*x，2d『nl。第二子步驟74.2相應於行(A.2)或行(A.2.1)-(A.2.5)。在此計算校正因子C。在與方法A的行(A.3)相應的第三子步驟74.3中藉助蒙哥馬利乘法B*x，2d(^t子步驟74.1的蒙哥馬利約簡的結果執行所需校正。
[0133]基於餘數b mod p』，然後在步驟76中執行標記流程。為此首先確定在位域S中的第一位s[k]，其對應的值b+SW*k與標記值P』的倍數，也就是與合數相應。該位S[k]被相應地標記，也就是例如被置為值「O」。從該第k個位出發，然後按順序將其他與p』間隔的位一也就是位S[k+p』]，S[k+2*p』]，S[k+3*p』]，...一分別置為代表了合數的值。這些位相應於值b+SWk+SWp』，b+Sffk+2.SWp』，b+Sffk+3.SWp』，等等。不需要考慮P』的中間倍數，因為在位域S中不表示這些倍數。
[0134]如在方法A』中已經說明的，當標記值是素數時，可以取消在步驟74.1中的蒙哥馬利約簡。
[0135]相反如果一如在方法A中說明的一 P』應當是(兩個或多個)素數的乘積，則對於作為標記值的每個這些素數執行標記流程。跟隨步驟74.1對於(兩個)標記值r，!.』的每一個進行步驟74.2和74.2。從對於每個標記值分離地確定的餘數(b mod r)出發也可以對於每個標記值進行步驟76。
[0136]在步驟76的標記流程結束之後在步驟78中檢查，是否應當進行另一個篩遍歷。如果是，則進行到步驟72的跳轉。否則終止候選域的產生，並且方法以步驟48 (圖2)繼續。
[0137]在至此描述的實施例中在步驟74.2中一相應於行(A.2)或者說(A.2.1)-(A.2.5)通過具有底數2的模冪計算確定了校正因子。發明人認識到，當計算1/2的冪而不是2的冪時，在此處處理的硬體平臺上可以實現極大的速度提高；使用蒙哥馬利乘法的合適的方法在以下詳細描述。但是首先說明，如何能夠將在行(A.2)中通過0 = 2<1『(11+1)1110(1乂說明的、在寄存器C中的校正因子C作為1/2的冪來表達。
[0138]首先要注意，模X的因式分解是已知的，因為X例如是素數P』或一在實施替選方案中一是素數的乘積。由此也已知歐拉f函數# (I)的值，因為例如並且對於
素數Pc^B P1有爐(po'pi) =此外對於與X互素的所有的a成立#w =I modXo
由此對於合適選擇的k成立2d.(n+1)mod X= 2.(剛部.'))mod X0由此可以將行(A.2)中
的計算 C = 2d.(n+1)mod X 通過C = (1A) k’m—d.力 modX 來代替。
[0139]以下描述在使用蒙哥馬利運算的條件下用於有效確定1/2的正的冪的方法，如對於剛才提到的計算C = (V2)晴部+1) mod X可以採用的。但是為了更好理解，首先示出
比較方法(「方法1」)，其使用「正常的」模乘a*Mb: =a*bmodM，以計算2的冪。
[0140]比較方法I從公知的平方-和-乘法技術出發，在所述平方-和-乘法技術中對於指數的每個位進行中間結果的平方以及-根據指數位的值-還進行中間結果與待求冪的底數的乘法。但是當通過測量電流消耗或其他參數可以確定，在指數的位的處理中中間結果是否翻倍-也就是向左移動時，平方-和-乘法技術容易潛在地受到側信道攻擊。由此在比較方法I中使用修改的技術，其可以稱為「平方八次-和乘法一次技術」。
[0141]在平方八次-和乘法一次技術」中分別執行八次平方，但是所屬的潛在的乘法分別綜合為唯一一個乘法。對於移動的乘法的指數位分別被收集在一個字節ei中，並且執行的乘法然後以因子2ε?進行。總體上該方法可以利用以下偽代碼符號標記來描述:
[0142]方法I
[0143]輸入值:指數e = e0+ei.256+...+en.256n
[0144]寄存器M中的模
[0145]寄存器:M，X，Y
[0146]輸出值:寄存器Y中的冪2e mod M
[0147]方法流程:
[0148]設置(U)
[0149]對於i = η-l向下計數到O (1.2)
[0150]執行8 次 (1.3)
[0151]設置Y* = Y mod M (1.4)
[0152]結束(1.5)
[0153]設置X =2肖(1.6)
[0154]設置Y* = X mod M (1.7)
[0155]結束(I.8)
[0156]在上面的偽符號表示中符號A* = B mod M意味著,寄存器A中的內容通過A ?B modM代替。寄存器M，X和Y分別具有至少256位的大小。值ei對於O < i < η表示具有基礎256的位置值系統中的指數e的「數位」;成立O < ei < 255。
[0157]在行(1.1)中進行寄存器Y的初始化。對於指數e的每個字節然後執行循環過程，該循環過程分別包括行(1.3)-(1.7)。在此在行(1.3)和(1.4)中將寄存器Y的內容平方八次。在行(1.6)和(1.7)中進行寄存器Y中的中間結果與因子#的乘法。在行(1.1)和(1.6)中的冪計算可以有效地通過以下來執行，即，例如為了計算A=2ek首先將寄存器A置為零，然後將一從最低位的位開始計算的一第(k+Ι)個位反轉到「I」。
[0158]只要具有不同的2的冪的乘法不能通過攻擊來區分，則上面的比較方法I可以防側信道攻擊。
[0159]發明人認識到，剛才描述的比較方法I可以被擴展為使得使用蒙哥馬利乘法並且由此可以在具有合適的協處理器56，56』，56〃，56〃』的數據載體50上有效地執行。令人吃驚地可以通過方法流程的相對小的修改實現這一點。特別地在以下稱為「方法2」的擴展的方法中，計算2的負的冪作為結果，即2_e= (1/2)%而不是在方法I中計算的值2%此外在方法2中設置附加的步驟，在該步驟中將指數e合適地再編碼，以補償蒙哥馬利運算而不是方法I中的「正常的」模乘和平方。
[0160]與在比較方法I中同樣地，在方法2中使用兩個寄存器X和Y以及用於模m的一個恆定的第三寄存器M。寄存器Y具有與M相同的大小，而寄存器X必要時可以更小。所有三個寄存器具有至少256位，並且模m為至少2255。
[0161]方法2可以對於上面提到的所有協處理器56，56』，56〃，56〃』使用。該通用性通過如下實現，即，方法2使用僅兩個在所有常用的平臺上可用的普通的蒙哥馬利命令。這些命令首先是寄存器Y的蒙哥馬利平方並且其次是寄存器X和Y的蒙哥馬利乘法。在蒙哥馬利平方中將寄存器Y的值通過Y*m，K Y來代替。該蒙哥馬利平方在以下通過偽代碼命令「設置Y* = Y*R^mod Μ」表達。其中將寄存器Y的值通過X*m，K Y代替的蒙哥馬利乘法在以下通過偽代碼命令「設置 Y* = X*R_1mod Μ」表達。
[0162]此外，在方法2中將寬度r的寄存器(X或Y)以2的冪2k(其中O≤k〈r)來初始化。該過程通過偽代碼命令「設置Z = 2k」來表達。方法2於是可以被如下描述:
[0163]方法2
[0164]輸入值:指數e = e0+ei.256+...+en.256n
[0165]寄存器M中的模
[0166]寄存器:M，X，Y
[0167]輸出值:寄存器Y中的冪2_e mod M
[0168]方法流程:
[0169]執行「方法3」 (2.0)
[0170](從指數e產生具有f= fo+f!.256+...+fn.256n的再編碼的指數f)
[0171]設置Y = /?(2.1)
[0172]對於i = n-Ι向下計數到O (2.2)
[0173]執行8 次(2.3)
[0174]設置Y* = Y*R_1mod M (2.4)
[0175]結束(2.5)
[0176]設置Χ4Λ(2,6)
[0177]設置Y* = X*R_1mod M (2.7)
[0178]結束(2.8)[0179]除了在行(2.0)中的準備步驟之外，方法2的結構精確地相應於方法I的結構。在行(2.1)中對寄存器Y初始化之後又執行具有作為循環體的行(2.3)-(2.7)的循環。在行(2.3)和(2.4)中對寄存器Y中的中間結果執行八次蒙哥馬利平方，並且在行(2.6)和(2.7)中進行寄存器Y與因子2fi的蒙哥馬利乘法。也就是方法I和2僅通過步驟(2.0)中的指數的再編碼並且通過如下，即，使用蒙哥馬利乘法和平方而不是正常的模乘和平方而相區別。
[0180]在上面描述的方法2的修改中可以將兩個行(2.6)和(2.7)綜合為唯個命令，在該命令中將寄存器Y的值通過乘積Y*2fi_nm0dM來代替；在此η』是蒙哥馬利參數R的二進位對數，從而成立R = 2η』。在此處使用的偽符號表示中可以將該綜合的命令利用「設置 Y* = 2fi*2-n mod Μ」 來表達。
[0181]方法2的結果可以對於在此處理的協處理器56，56』 , 56"，56〃』中的一些協處理器在必要時以模M的小的倍數與期望的最終結果2_ε mod M不同。由此可以需要，作為終止校正步驟執行寄存器Y模M的模約簡。
[0182]在這裡描述的實施例中按照如下方法執行在行(2.0)中指數e的再編碼:
[0183]方法3
[0184]輸入值:指數e = e0+ei.256+...+en.256n
[0185]蒙哥馬 利參數R對底數2的對數η』 (由此成立R = 2η』)
[0186]輸出值:具有f = f。+^.256+…+4.2561^^再編碼的指數f，用於在方法2中的應用
[0187]方法流程:
[0188]設置f = η，.(256+2562+2563+...+256n)_e (3.1)
[0189]存儲f0，f」...，fn (3.2)
[0190]其中f = fo+A.256+...+fn.256n (3.3)
[0191 ]並且 0 ≤ fi<256 對於 0 ≤ i〈n (3.4)
[0192]通過以下討論可以解釋，具有按照方法3對指數的再編碼的方法2提供正確的結果:首先要注意，在方法流程期間寄存器X和Y中的所有值始終是2的模冪(具有模M)，因為寄存器利用2的冪被初始化，並且因為蒙哥馬利運算可以寫成具有作為因子的2的(必要時負的)冪的模乘。執行的計算由此可以更清楚地寫做關於模M的相對於底數2的其對數的形式。
[0193]對於Y = 2>^PR = 2n』，在行(2.4)中的蒙哥馬利平方可以寫成翻倍和減法，其中y通過2*y-n』來代替(運算「S」)。可以在寄存器平面上寫成「設置Y* = 2k*2_nm0dM」的、行(2.7)和(2.8)的組合的運算，在對數表達中將y通過y+k-n』來代替(運算「Mk」)。
[0194]在方法2中分別執行八次運算S並且然後執行一次組合的運算Mk。在對數表達中該方法流程可以如下表示:
[0195]y — S 2.y - η' — S4*y_3*n， — S8.y~7.η' — S......—S256.y-255.η』 — Mk256.(y_n，)+k
[0196]為了顯示指數e的合適的再編碼，再編碼的指數f的字節fn，4-!,..., fο必須具有特徵，即，在以下定義的序列yn，Yn^1, -,y0中得出結果I, = -e ;函數的級聯通過符號「 ο 」表達:[0197]yn: = fn
[0198]Y1: = Mfi o S8(yi+1) = 256.(yi+「n，)+A 對於 i=n_l，...，0
[0199]可以通過關於n的歸納顯示，在方法3中定義的再編碼具有剛才提到的特徵並且由此得到方法2的正確結果。
[0200]圖5示出了剛才描述的方法2和3的示例流程。在步驟80中按照方法3進行指數e的再編碼，以從具有其位組82 —在此是字節en，—的原始的指數e中獲得具有其位組84 —在此是字節fn，fn_1；..., fο 一的再編碼的指數f。
[0201]在步驟80中的再編碼之後的方法流程可以劃分為初始化86和η個片段88。在初
始化86的過程中在步驟90中執行按照方法2的行(2.1)的命令「設置Y = 2厶」。η個片
段88的每一個分別相應於方法2的一個循環過程並且分別對應於再編碼的指數f的位組84的一個。
[0202]每個片段88具有三個主要步驟92、94和96。在步驟92中按照方法2的行(2.3)和(2.4)對在寄存器Y中包含的中間結果執行八次蒙哥馬利平方。在與行(2.6)相應的步驟94中，在寄存器X中存儲具有指數的2的冪，該指數通過再編碼的指數f的對應的位組84形成。該步驟94可以有效地通過如下實現，即，寄存器X首先被刪除並且然後將其位位置通過對應的位組84說明的位設為值「I」。步驟96相應於方法2的行(2.7)並且包含寄存器Y和X的蒙哥馬利乘法。
[0203]在總共執行了 η個片段88之後，在寄存器Y中-在必要時還需要的通過步驟98中的模約簡進行的校正之後-呈現期望的結果2_emodM。
[0204]以下示出至此描述的方法2和3的一些可選的簡化和擴展。在不同的實施變型中可以利用這些簡化和擴展的不同組合，以便例如將採用的方法特別好地匹配到確定的蒙哥馬利協處理器56，56』, 56"，56〃』或者以便進一步提高窺探安全性。
[0205]首先討論按照方法3的指數再編碼中的潛在困難，即，對於fn可能出現大於255
的值。對於小的％於是可能在方法2的步驟(2.1)中確定的值大於模m並且由此對於
作為初始值存儲在寄存器Y中來說太大了。然而對於所有在此處理的蒙哥馬利協處理器56，56』，56"，56〃』可以這樣選擇用於模m的寄存器大小，使得對於各自的蒙哥馬利係數η』滿足不等式〗~5).1^!^〗11』。條件2Λ0如下被放大:
[0206]fn = η，.(256/255).(1- ε ) -en e [0，(4/5).η，]
[0207]剛才提到的條件當在以下利用(*)表示的不等式1/4.η』 <en〈n』成立時總是滿足。
[0208]如果方法3得到對於fn的過大的值，則該值可以在圖5的步驟90之前利用模m來模約簡，從而然後在步驟90中將寄存器Y置為得到的餘數。對於非常小的en(en〈n』/256)也可以將第η個片段82容納到第(η-1)個片段82中。在該情況下將η減小1，並且將eiri提高en.256。此外在一些構造中可以設置，這樣設置指數e的值，使得fn保持足夠小。
[0209]總之也就是可以通過以下方法B來進行在步驟74.2(圖4)中的校正因子C的計算:
[0210]方法B
[0211]輸入值:寄存器X中的d位寬的值(例如素數p』)
[0212]在寄存器Y中的η.d位寬的值(例如底數b)[0213]寄存器:B，C，X，Y，Z
[0214]輸出值:寄存器Z中的餘數Y mod X
[0215]方法流程:
[0216]設置B = Y*2-d.n mod X (B.1)
[0217]設置C=《丨/2) Α' φ,Λ) - 士 _) mod X
[0218]應用方法2和3
[0219]對於合適選擇的k (B.2)
[0220]設置Z = B*C*2-d mod X (B.3)
[0221]行(B.1)和(B.3)相應於方法A中的行(A.1)和(A.3)並且分別包含一個蒙哥馬利乘法。在行(B.2)中執行用於底數1/2的模冪計算的上面描述的方法2和3。在此這樣選擇值k，使得指數fn+lj是正的，並且滿足不等式(*)。在許多實施方式中模X和指數分別具有最高16位的長度，從而為了行(B.2)中的校正因子的計算，16個蒙哥馬利平方和4個蒙哥馬利乘法足夠。
[0222]以下描述剛才示出的方法B的另一個優化的修改，其特別好地適合於通過協處理器56〃』的執行。在具有協調處理器56〃的數據載體50中具有微小修改的方法可以通過主處理器54執行。
[0223]在以下描述的方法既關於其實施速度也關於其窺探安全性最優化。關於窺探安全性也就是基於如下事實而存在潛在的攻擊可能性，即，計算篩法的基礎值b對非常小的素數取模後的餘數。攻擊在理論上可以確定該模約簡的電流曲線(Stromverlaufskurve) —或其他側信道信息一併且對於側信道攻擊進行分析，在該側信道攻擊中建議基礎值b的最高或最低字並且然後關於每個約簡的開始窺探數據。
[0224]為了防禦這樣的攻擊，在一些實施例中一例如在以下方法中一建議，蒙哥馬利約簡不是進行對每個素數取模，而是進行對每個素數對取模。作為正面的副作用，由此也加速了篩過程，因為僅需要進行一半的費時的長的約簡。在其他修改中也可以使用多於兩個素數的元組。
[0225]對於以下方法Ptl和P1分別是小的素數，並且m = Ptl -P1是該素數對的乘積。首先執行基礎值b對該素數乘積m取模的蒙哥馬利約簡，如與圖4中的步驟74.1或方法A中的行(A.1)相應的那樣。也就是通過蒙哥馬利乘法計算具有以下特徵的值r:
[0226]r = b*ml = b.R_1mod m
[0227]蒙哥馬利係數R在此為2128『\其中最小可能的寄存器大小選擇2128『\其足以容納基礎值b。在此假定，其中存儲了蒙哥馬利約簡的因子b和I的寄存器分別是128位長。
[0228]對於這兩個素數Ptl和P1的每一個現在執行以下步驟(方法C)，以便從中間結果r中獲得餘數b mod p』。也就是在方法C的第一執行中設置P』 = P0,並且在第二執行中設置P』 = P1O方法C由此相應於圖4中的74.2和74.3或方法A中的行(A.2)和(A.3):
[0229]方法C
[0230]輸入值:d位寬的合數m
[0231]素數p』，其中p』〈214，其除以m
[0232]如上面給出的值r = b.2_d『nmodm[0233]寄存器:A，B，F，R，X，Y
[0234]輸出值:寄存器R中的餘數bmodp』
[0235]方法流程:
[0236]設置X = p』 -1 (C.1)
[0237]將X 翻倍，直到 X ≥(1〈〈15) (C.2)
[0238]設置Y = ((l〈〈16)-X) + ((n+l)〈〈8) (C.3)
[0239]如果Y ≥(1>>15)則 (C.4)
[0240]設置y = y-(χ>>I) (C.5)
[0241]設置F = Y? I (C.6)
[0242]設置A = 1〈〈(F>>7) (C.7)
[0243]設置B = I (C.8)
[0244]設置R = A*B*2-128mod p』 (C.9)
[0245]執行7 次 (C.10)
[0246]設置R = R*R*2-128mod p， (C.11)
[0247]結束(C.12)
[0248]設置A = F mod (I〈〈7) (C.13)
[0249]設置R = A*R*2-128mod p， (C.14)
[0250]設置A= r(C.15)
[0251]設置R = A*R*2-128mod p』 (C.16)
[0252]在上面描述的方法中X?n表示將寄存器或常數X以η個位位置向右移動，並且Χ?η表示向左的相應移動。
[0253]在行(C.1)-(C.6)中計算寄存器F中的合適的校正因子指數f，其具有如行(B.2)中的形式，但是附加地如在方法3中那樣被再編碼。在此首先在行(C.1)和(C.2)中將寄存器X中的16位整數翻倍，直到其是負的。然後在行(C.3)中將在2和33之間的值加到-X的高字節，其中X是在寄存器X中包含的值。在行(C.4)和(C.5)中將中間結果校正，如果其太大的話。最後在行(C.6)中通過將寄存器Y中的中間結果減半來計算寄存器F中的校正因子指數f。
[0254]在行(C.7)_(C.14)中利用類似於方法2中的步驟計算寄存器R中的校正因子。由於前提條件P』〈214，方法2的最大所需的兩個循環過程在此「被展開」。更具體來說，行(C.7)-(C.9)相應於如方法2的行(2.7)中的第一蒙哥馬利乘法，行(C.10)-(C.12)相應於蒙哥馬利平方7次，並且行(C.13)和(C.14)相應於如方法2的行(2.7)中的第二蒙哥馬利乘法。當在實施替選方案中可以出現更大的素數P』時，則可以通過接受方法2的相應多個其他循環過程來合適地修改方法C。例如可以設有，實施另外7個蒙哥馬利平方和另一蒙哥馬利乘法。
[0255]在行(C.15)和(C.16)中最後將在執行(C.14)之後在寄存器R中包含的校正因子應用於蒙哥馬利約簡的結果r。總體上由此方法C的行(C.1)-(C.15)相應於圖4中的子步驟74.2，而行(C.15)和(C.16)相應於子步驟74.3。
[0256]應當理解，在此描述的對素數候選的有效計算和確定的構造不限制於按照圖1和圖2的方法流程，而是其在實施替選方案中也可以對於其他應用目的，特別是在用於通過一個或多個處理器執行密碼的領域而設計。此外可以理解，在此描述的實施方式和實施變型僅作為例子看待。在此描述的特徵的其他修改和組合對於專業人員來說是明顯的。
【權利要求】
1.一種對於密碼應用確定第一值(b)模第二值(P』)之後的除餘數的方法，其中，該方法通過至少一個處理器(54，56，56』，56〃，56"')執行並且包含: -利用第一值(b)作為因子之一和第二值(P』)作為模執行(74.1)蒙哥馬利乘法， -確定(74.2)校正因子，其中在校正的蒙哥馬利乘法中使用校正因子作為因子，以獲得第一值(b)模第二值(P』)之後的除餘數。
2.根據權利要求1所述的方法，其特徵在於，利用第一值(b)作為因子之一和第二值(P』)作為模的蒙哥馬利乘法的執行是第一蒙哥馬利乘法，並且通過 -以第一蒙哥馬利乘法的結果作為一個因子和校正因子作為另一個因子和第二值(P』)作為模，執行(74.3)第二蒙哥馬利乘法，作為校正的蒙哥馬利乘法，以獲得第一值(b)模第二值(P』)之後的除餘數。
3.根據上述權利要求中任一項所述的方法，其特徵在於，所述第一蒙哥馬利乘法是蒙哥馬利約簡。
4.根據權利要求2或3所述的方法，其特徵在於，在第一蒙哥馬利乘法之後為第二蒙哥馬利乘法確定校正因子。
5.根據權利要求2至4中任一項所述的方法，其特徵在於，所述校正因子用於補償通過第一和第二蒙哥馬利乘法引起的誤差。
6.根據權利要求2至5中任一項所述的方法，其特徵在於，以不同的蒙哥馬利係數執行第一和第二蒙哥馬利乘法。
7.根據權利要求1所述的方法，其特徵在於，以第一值(b)作為因子之一和第二值(P』 )作為模的所執行的蒙哥馬利乘法是校正的蒙哥馬利乘法，其將校正因子用作另一個因子。
8.根據權利要求4和7所述的方法，其特徵在於，如果第二值(P』)是素數的乘積，則該方法按照權利要求4構造否則該方法按照權利要求7構造。
9.根據權利要求1至8中任一項所述的方法，其特徵在於，校正因子作為2的模冪在多個循環過程中被計算，其中每個循環過程具有中間結果的翻倍和條件減。
10.根據權利要求1至9中任一項所述的方法，其特徵在於，所述校正因子作為具有正整數校正因子指數和底數1/2的模冪被計算。
11.根據權利要求10所述的方法，其特徵在於，所述校正因子的計算具有中間結果的多個蒙哥馬利平方的系列，按照這些蒙哥馬利平方執行中間結果與取決於校正因子指數的因子的蒙哥馬利乘法。
12.一種對於密碼應用確定以特定的概率表示素數的素數候選的方法，其中，所述方法通過至少一個處理器(54, 56, 56』, 56"，56，，，)執行並且包含: -確定(44)用於篩法的基礎值(b)，和 -執行多個篩遍歷，在所述篩遍歷中分別確定(72) —個標記值(p』 ；r, r)並且將該標記值(P』 ；r, r')的倍數在篩法中作為合數標記，其中在每個篩遍歷中利用包括至少一個蒙哥馬利運算的餘數確定方法確定(74)基礎值(b)對標記值(p』 ；r，r』)取模之後的除餘數。
13.根據權利要求12所述的方法，其特徵在於，所述標記值(p』；r, r)是素數。
14.根據權利要求12或13所述的方法，其特徵在於，所述篩法通過位域(S)代表，其位(S[i])相應於如下的值，所述值從基礎值(b)出發具有預定的步幅，該步幅大於等於或大於2。
15.根據權利要求12至14中任一項所述的方法，其特徵在於，對每個確定的素數候選進行至少一個概率性素數測試(12，20, 28，34，38)。
16.根據權利要求12至15中任一項所述的方法，其特徵在於，作為餘數確定方法使用按照權利要求1至11中任一項所述的方法。
17.根據權利要求16所述的方法，其特徵在於，在篩遍歷中的一個篩遍歷中: -對於標記值(r，r』)的乘積(p』)執行第一蒙哥馬利運算， -分別對於標記值(r，r』)執行第二蒙哥馬利運算，並且 -分別標記所述標記值(r，r』)的倍數。
18.根據權利要求1至17中任一項所述的方法，其特徵在於，所述方法用於確定RSA密鑰或RSA-CRT密鑰的至少一個參數。
19.一種電腦程式產品，具有多個程序命令，所述程序命令允許至少一個處理器(54，56，56』，56"，56』』』)、特別是可攜式數據載體(50)的至少一個處理器(54，56, 56』, 56"，56，，，)執行按照權利要求1至18中任一項所述的方法。
20.一種裝置，特別 是可攜式數據載體(50)，具有至少一個處理器(54，56，56』，56"，56，，，)和至少一個存儲器(60，64，66，68)，其中所述裝置構造為執行按照權利要求1至18中任一項所述的方法。
【文檔編號】H04L9/08GK104012029SQ201280064238
【公開日】2014年8月27日 申請日期:2012年10月25日 優先權日:2011年10月28日
【發明者】J.普爾庫斯 申請人:德國捷德有限公司