[發(fā)明專利]一種在嵌入式系統(tǒng)中生成大素數(shù)的方法

有效

• 申請?zhí)枺?/td>: 201110439890.2
• 申請日: 2011-12-23
• 公開（公告）號: CN102591618A
• 公開（公告）日: 2012-07-18
• 發(fā)明（設(shè)計）人: 陸舟;于華章
• 申請（專利權(quán)）人: 飛天誠信科技股份有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及密碼學(xué)領(lǐng)域，特別涉及一種在嵌入式系統(tǒng)中生成大素數(shù)的方法。

背景技術(shù)

在密碼實現(xiàn)過程中，特別是公開密鑰密碼的實現(xiàn)過程中，需要嵌入式系統(tǒng)生成大素數(shù)供加密等過程使用，例如，RSA加密過程中的密鑰參數(shù)需要使用嵌入式系統(tǒng)生成的大素數(shù)。

現(xiàn)有技術(shù)中，大素數(shù)的生成過程包括：首先生成長度足夠的隨機數(shù)；然后判斷該隨機數(shù)是否為素數(shù)；當確定該隨機數(shù)不為素數(shù)時，則重新生成一組新隨機數(shù)或?qū)Ξ斍半S機數(shù)進行適度變換，然后再次判斷新隨機數(shù)是否為素數(shù)，直到生成一個符合要求的隨機數(shù)。

在上述生成大素數(shù)的過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術(shù)中至少存在如下問題：在大素數(shù)產(chǎn)生的過程中，需要對很多隨機數(shù)進行素性檢測以判斷該隨機數(shù)是否為素數(shù)，由于素性檢測需要用到很消耗時間的模冪運算，且素性檢測通過的概率并不高，大多數(shù)情況下需要尋找數(shù)百甚至上千次隨機數(shù)后才能找到大素數(shù)，不適于運用在嵌入式系統(tǒng)中。

發(fā)明內(nèi)容

鑒于現(xiàn)有技術(shù)的不足，為了有效的解決現(xiàn)有技術(shù)的不足，本發(fā)明提出了一種在嵌入式系統(tǒng)中生成大素數(shù)的方法。

本發(fā)明采用的技術(shù)方案如下：

一種在嵌入式系統(tǒng)中生成大素數(shù)的方法，應(yīng)用于包括第一存儲區(qū)和第二存儲區(qū)的系統(tǒng)中，所述第一存儲區(qū)存儲有預(yù)設(shè)大小的標識組，所述標識組中的標識的序號為包括0在內(nèi)的數(shù)值連續(xù)的整數(shù)，且不同的標識具有不同的序號；所述第二存儲區(qū)包括多個存儲單元，不同的存儲單元中存儲有不同的素數(shù)，所述方法包括以下步驟：

①、將所述第一存儲區(qū)中存儲的標識組中的全部標識置位；生成預(yù)定位數(shù)長度的隨機數(shù)，將所述隨機數(shù)存儲到第三存儲區(qū)，以所述第二存儲區(qū)中的存儲單元存儲的數(shù)據(jù)為模數(shù)，對所述第三存儲區(qū)存儲的數(shù)據(jù)取模，得到取模值；根據(jù)所述取模值以及所述取模值對應(yīng)的存儲單元存儲的數(shù)據(jù)，確定所述標識組中需要被復(fù)位的標識的序號，并對所述序號對應(yīng)的標識進行復(fù)位；

②、判斷所述標識組中是否存在置位的標識，如果存在，則執(zhí)行步驟③；如果不存在，則返回步驟①；

③、根據(jù)所述隨機數(shù)和所述標識組中置位的標識的序號確定待測數(shù)，對所述待測數(shù)進行素性檢測，如果所述待測數(shù)通過素性檢測，則將所述待測數(shù)作為大素數(shù)輸出；如果所述標識組中所有置位的標識對應(yīng)的待測數(shù)均未通過素性檢測，則返回步驟①。

其中，所述根據(jù)所述取模值以及所述取模值對應(yīng)的存儲單元存儲的數(shù)據(jù)，確定所述標識組中需要被復(fù)位的標識的序號，具體為：

當所述取模值為0時，將所述取模值與所述取模值對應(yīng)的存儲單元存儲的數(shù)據(jù)的整數(shù)倍的和，作為所述需要被復(fù)位的標識的序號；

當所述取模值為奇數(shù)時，獲取所述取模值對應(yīng)的存儲單元存儲的數(shù)據(jù)與所述取模值之間的差，將所述差除以2得到的結(jié)果作為所述需要被復(fù)位的標識的序號；

當所述取模值為非零偶數(shù)時，獲取所述當前取模值除以2得到的商，將所述當前素數(shù)與所述商的差作為所述需要被復(fù)位的標識的序號；

所述根據(jù)所述隨機數(shù)和所述標識組中置位的標識的序號確定待測數(shù)，具體為：

將所述置位的標識的序號的2倍與所述隨機數(shù)相加得到的結(jié)果，作為所述待測數(shù)。

或者，所述根據(jù)所述取模值以及所述取模值對應(yīng)的存儲單元存儲的數(shù)據(jù)，確定所述標識組中需要被復(fù)位的標識的序號，具體為：

當所述取模值為0時，將所述取模值與所述取模值對應(yīng)的存儲單元存儲的數(shù)據(jù)的整數(shù)倍的和，作為所述需要被復(fù)位的標識的序號；

當所述取模值為奇數(shù)時，獲取所述取模值對應(yīng)的存儲單元存儲的數(shù)據(jù)與所述取模值的和，將所述和除以2得到的商作為所述需要被復(fù)位的標識的序號；

當所述取模值為非零偶數(shù)時，將所述取模值除以2得到的商作為所述需要被復(fù)位的標識的序號；

所述根據(jù)所述隨機數(shù)和所述標識組中置位的標識的序號確定待測數(shù)，具體為：

將所述隨機數(shù)與所述置位的標識的序號的2倍的差，作為所述待測數(shù)。

其中，所述生成預(yù)定位數(shù)長度的隨機數(shù)，包括：

生成預(yù)定位數(shù)長度的二進制數(shù)；

判斷所述二進制數(shù)的最低位是否為1，如果所述最低位為1，則將所述二進制數(shù)作為所述隨機數(shù)；如果所述最低位不為1，則將所述最低位置為1，并將所述二進制數(shù)作為所述隨機數(shù)。

其中，所述生成預(yù)定位數(shù)長度的隨機數(shù)，包括：

生成預(yù)定位數(shù)長度的二進制數(shù)；

判斷所述二進制數(shù)的最高位是否為1，如果所述最高位為1，則將所述二進制數(shù)作為所述隨機數(shù)；如果所述最高位不為1，則將所述最高位置為1，并將所述二進制數(shù)作為所述隨機數(shù)。