生成被驗證適用於晶片卡的素數的方法

2023-06-29 11:38:16

生成被驗證適用於晶片卡的素數的方法
【專利摘要】本發明涉及一種在電子設備(DV)中實現的用於生成素數的方法，該方法包括步驟：使用公式Pr＝2P?x?R+1(其中P是素數，且R是整數)計算具有位數(L)的候選素數(Pr)；對候選素數應用波柯林頓素性測試；如果候選素數未能通過波柯林頓測試，則丟棄該候選素數；從屬於一組乘法逆元素的乘法逆元素(X)對屬於一組大於2的小素數的數(Qj)的乘積(Pv)取模所得的結果生成整數(R)，使得候選素數(Pr)不能被所述組中的任何數整除。素數P的位數減1等於候選素數的位數的一半或1/3。
【專利說明】生成被驗證適用於晶片卡的素數的方法

【技術領域】
[0001] 本發明涉及加密，並且特別涉及素數的生成。本發明還涉及諸如智慧卡中實現的 集成電路，以及這些集成電路中素數的生成。

【背景技術】
[0002] 自從1976年Diffie和Heilman發明以來，公鑰加密飛速地發展。如今，其被用在各 種應用中，諸如支付、電子商務、識別應用以及密碼數據和籤名數據，以及許多設備中，諸如 智慧卡、USB驅動器和許多微處理器和計算機。例如RSA(Rivest，Shamir，Adleman)、DSA (數 字籤名算法）和DH(Diffie Heilman密鑰交換）的大部分加密系統是基於使用大素數來生成 加密密鑰，或者更一般地，生成易被用在需要一定安全級別的交易中的秘密數據。因此，這 些加密系統的安全直接與使用的素數的大小相關聯。
[0003] 由於技術、特別是計算機計算能力的持續演進，加密系統使用日益變大的加密密 鑰並因此使用日益變大的素數。因此，一些銀行組織如今建議在某些應用中使用1，024位、 甚至2, 048位素數。
[0004] 通常，生成素數包括隨機選擇數字，並通過例如應用素性測試（諸如埃拉託色尼 選篩法或米勒-拉賓測試）檢驗其是否是素數。如果選擇的數字沒有通過素性測試，則選 擇新的數字。新數字的選擇從一種方法到另一種方法而變化。其使得生成素數構成了當前 使用的加密系統中執行的最複雜的計算任務。
[0005] 十年前，由於低計算能力及其存儲能力，在智慧卡電路中執行該素數生成的任務 是不可想像的。因此，該任務由功能強大的計算機執行，並且從素數生成的秘密數據在電路 的出廠初始化步驟期間被安全地傳輸到微電路。
[0006] 當前的智慧卡電路一般配備有加速某些諸如大數字乘法和模冪運算的操作的加 密協處理器，並具有日益變大的存儲容量。這些改進使得能夠考慮直接在智慧卡中生成大 素數。由於生成秘密數據的計算機或到智慧卡的數據傳輸不存在被竊用的風險，該方法提 供更多的安全性。此外，由於該方法，如果秘密數據是在卡中生成，則發行智慧卡的實體不 能知道該秘密數據。該方法也使微電路能夠重新生成素數，並在必要時基於該素數重新生 成秘密數據。
[0007] 然而，與桌面計算機相比，智慧卡微電路的計算和存儲能力仍然較低。此外，在操 作模式下，密鑰的生成時間必須保持低於用戶能夠接受的極限。因此，存在對於一種遵照智 能卡中實現的大素數生成、且需要小的計算和存儲裝置的生成大素數的方法的需求。
[0008] 常規生成素數的方法是基於諸如米勒-拉賓和盧卡斯測試（Lucas test)的概率素 性測試的使用。然而，概率測試沒有通過定義提供生成的數是素數的任何絕對確定性，並因 此沒有使驗證素數能夠被獲得。然而，這種確定性會提供一般在加密系統中尋求的更高安 全級別。
[0009] 這種測試的信任級別可以通過執行測試的若干迭代而增加。因此，生成具有足夠 信任級別的1，024位素數需要米勒-拉賓測試的40次迭代。當米勒-拉賓測試後面是盧 卡斯測試時，該迭代數量可以被降為3。然而，盧卡斯測試被驗證與智慧卡的能力很少兼容。 [0010] 此外，儘管對集成到智慧卡內的微電路做出了顯著改進，開發適用於這種微電路 的軟體仍然敏感。與桌面計算機或多媒體設備中實現的微處理器相比，智慧卡電路構成具 有多個限制的環境。事實上，這些微電路中存在的內存的容量仍然較低。由諸如DES(數字 加密系統）、AES (高級加密系統）、RSA和ECC (橢圓曲線密碼）的加密算法實現的一些加 密操作需要被移動到協處理器以便被足夠高效地執行。因此，模冪運算構成嵌入在智慧卡 微電路中諸如RSA和DSA的加密系統中的最昂貴操作。這些求冪操作還可能被要求生成素 數。
[0011] 同樣必要的是，微電路保持防範旨在發現微電路所存儲或處理的秘密數據的攻 擊。過去的這些年，已經出現了大量類型的攻擊，因此開發防範所有已知類型攻擊的微電路 是一個挑戰。
[0012] 因此，可能希望通過避免涉及概率素性測試、並可以嵌入到智慧卡微電路中的安 全方法生成素數。
[0013] 為了該目的，存在從可能比32位少的相對小的驗證素數生成大驗證素數的迭代 方法。因此，出版物[3]和[4]描述了這些方法。
[0014] 可能合乎期望的是降低這些方法的執行時間。


【發明內容】

[0015] 一些實施例涉及電子設備中實現的加密方法，該方法包括以下步驟：生成素數； 生成整數；使用以下公式生成具有期望位數的候選素數：
[0016] Pr = 2P · R+1,
[0017] Pr是候選素數，P是素數，且R是整數，並且
[0018] P是素數並具有比候選素數的位數更少的位數，且R是整數；以及在候選素數通過 波柯林頓素性測試時提供該候選素數作為驗證素數。根據一個實施例，該方法包括以下步 驟：存儲一組大於2的小素數，計算和存儲所存儲的組中的素數的乘積，以及生成屬於一組 可逆元素的可逆數對所存儲的乘積取模所得的結果，整數從可逆數生成，使得候選素數不 能被所存儲的組中的任何數整除，素數的位數減1等於候選素數位數的一半或1/3。
[0019] 根據一個實施例，整數R被選擇為等於：
[0020] R= (X- (2P)_1modnv)+Z · Πν
[0021] R是整數，X是可逆數對所存儲的乘積取模所得的結果，Ρ是素數，並且Ζ是整數且 被選擇為使得數R的大小使候選素數Pr具有期望的位數。
[0022] 根據一個實施例，本方法包括以下步驟：如果候選素數沒有通過波柯林頓素性測 試，則從可逆數乘以2後對所存儲的乘積取模所得的結果生成新的候選素數，以及對新的 候選素數應用波柯林頓素性測試。
[0023] 根據一個實施例，使用以下等式生成可逆數以便低於存儲的乘積：
[0024] ΧλΠν = lmodnv
[0025] X是生成的可逆數，Πν是存儲的乘積，λ Πν是一組可逆元素對存儲的乘積取模 所得的卡麥可數。
[0026] 根據一個實施例，可逆數是通過隨機選擇小於存儲的乘積的可逆候選數、並將其 加1直到其使等式ΧλΠν = lmodriv成立為止來生成的，其中X是可逆候選數，Πν是存儲 的乘積，λ Πν是一組可逆元素對存儲的乘積取模所得的卡麥可數。
[0027] 根據一個實施例，可逆候選數X以小於存儲的乘積的值被隨機選擇，並被增加數 量：Β · (1 - XAnvmodnv)，其中Β是在1和存儲的乘積之間隨機選擇的整數，X是可逆候選 數，Πν是存儲的乘積，λ Πν是一組可逆元素對存儲的乘積Πν取模、直到其使等式成立為 止的卡麥可數，整數Β以小於存儲的乘積的值被隨機選擇。
[0028] 根據一個實施例，候選素數的以位數表示的大小等於素數的大小的三倍減1，生成 的候選素數僅在整數除以前一生成步驟中生成的素數的整數除法的商是奇數時才被保留 作為候選素數。
[0029] 根據一個實施例，在區間[1+1，21]中選擇整數，其中：
[0030]

【權利要求】
1. 一種在電子設備（DV)中實現的加密方法，所述方法包括以下步驟： 生成素數； 生成整數； 使用以下公式生成具有期望位數（L)的候選素數（Pr): Pr = 2P · R+1, Pr是所述候選素數，P是所述素數並且具有比所述候選素數的位數更少的位數，並且R 是整數；以及 如果所述候選素數通過波柯林頓素性測試，則提供所述候選素數作為驗證素數； 其特徵在於所述方法包括以下步驟： 存儲一組大於2的小素數（Qj); 計算和存儲所存儲的組中的素數的乘積（Πν);以及 生成屬於一組可逆元素的可逆數（X)對所存儲的乘積取模的結果，所述整數從所述可 逆數生成，使得所述候選素數（Pr)不能被所存儲的組中的任何數整除，所述素數的位數減 1等於所述候選素數的位數的1/2或1/3。
2. 根據權利要求1所述的方法，其中所述整數R被選擇為等於： R= (X- (2P)_1modnv)+Z · Πν R是整數，X是可逆數對所存儲的乘積取模的結果，Π ν是所存儲的乘積，Ρ是所述素數， 並且Ζ是整數且被選擇為使得所述整數的大小使所述候選素數具有所述期望位數。
3. 根據權利要求1或2所述的方法，包括以下步驟： 如果所述候選素數沒有通過所述波柯林頓素性測試，則從所述可逆數乘以2後對所存 儲的乘積取模的結果生成新的候選素數；以及 對所述新的候選素數應用所述波柯林頓素性測試。
4. 根據權利要求1至3中的一項所述的方法，其中使用以下等式將所述可逆數生成為 小於所存儲的乘積： χλ Πν = lmodllv X是生成的可逆數，πν是所存儲的乘積，並且λ Πν是所述一組可逆元素對所存儲的 乘積取模所得的卡麥可數。
5. 根據權利要求4所述的方法，其中通過隨機選擇小於所存儲的乘積的可逆候選數、 並將其加1直到其使等式Χλ Πν = lmodllv成立為止而生成所述可逆數，其中X是所述可逆 候選數，Πν是所存儲的乘積，λ Πν是所述一組可逆元素對所存儲的乘積Πν取模所得的 卡麥可數。
6. 根據權利要求4所述的方法，其中可逆候選數X被隨機選擇為小於所存儲的乘積的 值，並被增加數量： Β · (1 -XAnvmodnv)， 其中B是在1和所存儲的乘積之間隨機選擇的整數，X是所述可逆候選數，Πν是所存 儲的乘積，λ Πν是所述一組可逆元素對所存儲的乘積Πν取模、直到其使所述等式成立為 止的卡麥可數，所述整數Β被隨機選擇為小於所存儲的乘積的值。
7. 根據權利要求1至6中的一項所述的方法，其中所述候選素數（Pr)的以位數表示的 大小（L)等於所述素數（P)的大小的三倍減1，所述方法包括步驟：計算所述整數（R)除以 所述素數的整數除法的商（u)，所生成的候選素數僅在所述商是奇數的情況下才被保留作 為候選素數。
8. 根據權利要求1至7中的一項所述的方法，其中在區間[1+1，21]中選擇所述整數 (R)，其中
L是所述候選素數的期望位數。
9. 根據權利要求1至8中的一項所述的方法，包括以下若干步驟：生成新的素數的步 驟；從第一素數提供素數的第一生成步驟；每個隨後的生成步驟，其從在前一生成步驟中 獲得的素數提供素數，直到獲得由期望位數形成的素數為止，每個生成步驟包括生成候選 素數的步驟和波柯林頓測試的步驟。
10. 根據權利要求9所述的方法，其中生成新的素數的第一步驟包括： a_使用以下公式計算具有位數（L)的候選素數（Pr): Pr = 2P · R+1 P是驗證素數，所述驗證素數的位數減1等於所述候選素數的位數的1/2或1/3,並且 R是隨機選擇的整數； b_測試所述候選素數被所存儲的組中的素數（Qj)的可整除性； c-如果所述候選素數不能被所存儲的組中的素數整除，則對所述候選素數Pr應用所 述波柯林頓素性測試； d-如果對於所述候選素數（Pr)，未能通過所述可整除性和波柯林頓測試之一，則將所 述整數（R)加1，將所述候選素數增加所述素數（P)的兩倍，並且只要增加後的候選素數未 能通過所述可整除性和波柯林頓測試，就再次執行步驟b至d。
11. 根據權利要求10所述的方法，其中測試所述候選素數被所存儲的組中的數（Qj)的 可整除性包括以下步驟： 存儲所述候選素數（Pr)除以所存儲的組中的每個數的整數除法的餘數（Wj)作為第一 餘數，所述候選餘數在所述第一餘數之一為〇時不是素數； 存儲所述素數（P)的兩倍除以所存儲的組中的每個數的整數除法的餘數（Gj)作為第 二餘數；以及 如果通過向所述候選素數增加所述素數的兩倍而從所述候選素數計算新的候選素數， 則通過向每個第一餘數增加與所存儲的組中的同一素數相對應的第二餘數對所存儲的組 中的同一素數取模所得的結果來更新每個第一餘數。
12. 根據權利要求11所述的方法，其中當從在前一生成步驟中獲得的素數生成新的候 選素數時，通過接收與所存儲的組中的同一素數（Qj)相對應的第一餘數（Wj)的兩倍對所 存儲的組中的同一素數取模所得的結果來更新每個第二餘數（Gj)。
13. 根據權利要求12所述的方法，其中通過隨機選擇由比最大位數小的位數形成的數 (P)，並接連對其應用包括以不同底數（A)應用的多個米勒-拉賓測試（MR a，A = 2、7、61 ;3、 5、7、11、13、17)的有限數量的素性測試，直到獲得通過所述米勒-拉賓測試的數為止，來獲 得所述第一素數（Pr)，所述最大位數和所述底數的值被選擇為驗證所述第一素數的素性。
14. 根據權利要求13所述的方法，其中用被選擇為小於或等於32的最大位數（LL)以 2、7和61為底數、或者用被選擇為小於或等於48的最大位數〇^)以2、3、5、7、11、13和17 為底數，執行應用到隨機選擇的數（P)的所述米勒-拉賓測試（MR a)。
15. 根據權利要求13至14中的一項所述的方法，其中在應用到隨機選擇的數的所述米 勒-拉賓測試（MRA)之前的是，測試隨機選擇的數（P)被最小素數的列表（Q)中的數的可 整除性的可整除性測試。
16. 根據權利要求1至15中的一項所述的方法，包括從驗證素數生成加密密鑰的步驟。
17. -種電子設備，包括用於執行大數字乘法和/或模冪運算的計算時鐘（CRU)， 其特徵在於，所述電子設備被配置成執行根據權利要求1至16中的一項所述的方法。
18. -種半導體晶片上的集成電路，包括根據權利要求17所述的設備。
【文檔編號】G06F7/72GK104067217SQ201280062261
【公開日】2014年9月24日 申請日期:2012年12月12日 優先權日:2011年12月15日
【發明者】B·菲克斯, C·克拉維耶, P·派裡爾, L·蒂埃裡 申請人:英賽瑟庫爾公司