[發明專利]生成被驗證適用于芯片卡的素數的方法

無效

• 申請號: 201280062261.5
• 申請日: 2012-12-12
• 公開（公告）號: CN104067217A
• 公開（公告）日: 2014-09-24
• 發明（設計）人: B·菲克斯;C·克拉維耶;P·派里爾;L·蒂埃里
• 申請（專利權）人: 英賽瑟庫爾公司
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 北京市中咨律師事務所 11247
• 代理人: 楊曉光;于靜

1.一種在電子設備(DV)中實現的加密方法，所述方法包括以下步驟：

生成素數；

生成整數；

使用以下公式生成具有期望位數(L)的候選素數(Pr)：

Pr＝2P·R+1，

Pr是所述候選素數，P是所述素數并且具有比所述候選素數的位數更少的位數，并且R是整數；以及

如果所述候選素數通過波克林頓素性測試，則提供所述候選素數作為驗證素數；

其特征在于所述方法包括以下步驟：

存儲一組大于2的小素數(Qj)；

計算和存儲所存儲的組中的素數的乘積(Πv)；以及

生成屬于一組可逆元素的可逆數(X)對所存儲的乘積取模的結果，所述整數從所述可逆數生成，使得所述候選素數(Pr)不能被所存儲的組中的任何數整除，所述素數的位數減1等于所述候選素數的位數的1/2或1/3。

2.根據權利要求1所述的方法，其中所述整數R被選擇為等于：

R＝(X–(2P)^-1modΠv)+Z·Πv

R是整數，X是可逆數對所存儲的乘積取模的結果，Πv是所存儲的乘積，P是所述素數，并且Z是整數且被選擇為使得所述整數的大小使所述候選素數具有所述期望位數。

3.根據權利要求1或2所述的方法，包括以下步驟：

如果所述候選素數沒有通過所述波克林頓素性測試，則從所述可逆數乘以2后對所存儲的乘積取模的結果生成新的候選素數；以及

對所述新的候選素數應用所述波克林頓素性測試。

4.根據權利要求1至3中的一項所述的方法，其中使用以下等式將所述可逆數生成為小于所存儲的乘積：

X^λΠv＝1modΠv

X是生成的可逆數，Πv是所存儲的乘積，并且λΠv是所述一組可逆元素對所存儲的乘積取模所得的卡邁克爾數。

5.根據權利要求4所述的方法，其中通過隨機選擇小于所存儲的乘積的可逆候選數、并將其加1直到其使等式X^λΠv＝1modΠv成立為止而生成所述可逆數，其中X是所述可逆候選數，Πv是所存儲的乘積，λΠv是所述一組可逆元素對所存儲的乘積Πv取模所得的卡邁克爾數。

6.根據權利要求4所述的方法，其中可逆候選數X被隨機選擇為小于所存儲的乘積的值，并被增加數量：

B·(1–X^λΠvmodΠv)，

其中B是在1和所存儲的乘積之間隨機選擇的整數，X是所述可逆候選數，Πv是所存儲的乘積，λΠv是所述一組可逆元素對所存儲的乘積Πv取模、直到其使所述等式成立為止的卡邁克爾數，所述整數B被隨機選擇為小于所存儲的乘積的值。

7.根據權利要求1至6中的一項所述的方法，其中所述候選素數(Pr)的以位數表示的大小(L)等于所述素數(P)的大小的三倍減1，所述方法包括步驟：計算所述整數(R)除以所述素數的整數除法的商(U)，所生成的候選素數僅在所述商是奇數的情況下才被保留作為候選素數。

8.根據權利要求1至7中的一項所述的方法，其中在區間[I+1,2I]中選擇所述整數(R)，其中

L是所述候選素數的期望位數。

9.根據權利要求1至8中的一項所述的方法，包括以下若干步驟：生成新的素數的步驟；從第一素數提供素數的第一生成步驟；每個隨后的生成步驟，其從在前一生成步驟中獲得的素數提供素數，直到獲得由期望位數形成的素數為止，每個生成步驟包括生成候選素數的步驟和波克林頓測試的步驟。