[發(fā)明專利]一種嵌入式安全芯片及其的蒙哥馬利模乘運(yùn)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510178336.1
• 申請(qǐng)日: 2015-04-15
• 公開（公告）號(hào): CN104765586B
• 公開（公告）日: 2018-09-28
• 發(fā)明（設(shè)計(jì)）人: 陳金強(qiáng);徐浩
• 申請(qǐng)（專利權(quán)）人: 深圳國(guó)微技術(shù)有限公司
• 主分類號(hào): G06F7/72
• 分類號(hào): G06F7/72
• 代理公司: 深圳市康弘知識(shí)產(chǎn)權(quán)代理有限公司 44247
• 代理人: 胡朝陽;孫潔敏

本發(fā)明提供了嵌入式安全芯片和其的蒙哥馬利模乘運(yùn)算方法，所述運(yùn)算方法包括以下步驟獲取兩個(gè)第一預(yù)設(shè)參數(shù)，和第二預(yù)設(shè)參數(shù)，其中第一預(yù)設(shè)參數(shù)為常數(shù)1；根據(jù)兩個(gè)第一預(yù)設(shè)參數(shù)和蒙哥馬利模乘函數(shù)，得到第一運(yùn)算結(jié)果A；根據(jù)第一運(yùn)算結(jié)果A、第一預(yù)設(shè)參數(shù)、第二預(yù)設(shè)參數(shù)和次方計(jì)算函數(shù)，得到第二運(yùn)算結(jié)果B；根據(jù)第一運(yùn)算結(jié)果A、第二運(yùn)算結(jié)果B和所述蒙哥馬利模乘函數(shù)，得到蒙哥馬利模乘轉(zhuǎn)換系數(shù)D；根據(jù)第一輸入?yún)?shù)NA、第二輸入?yún)?shù)NB、蒙哥馬利模乘轉(zhuǎn)換系數(shù)和所述蒙哥馬利模乘函數(shù)，得到最終模乘結(jié)果。該蒙哥馬利模乘運(yùn)算方法可以避開大數(shù)模冪方式的計(jì)算轉(zhuǎn)換系數(shù)，而且不需要事先計(jì)算好系數(shù)，可以節(jié)省存儲(chǔ)空間。

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

本發(fā)明涉及密碼學(xué)中非對(duì)稱密鑰算法領(lǐng)域，尤其涉及一種嵌入式安全芯片及其的蒙哥馬利模乘運(yùn)算方法。

背景技術(shù)

信息安全的安全保障基于安全算法，安全算法有一類是非對(duì)稱密鑰算法。非對(duì)稱密鑰算法的基本運(yùn)算是大數(shù)的模乘運(yùn)算，模乘運(yùn)算算法中效率高、便于實(shí)現(xiàn)的算法是蒙哥馬利模乘算法。蒙哥馬利模乘使用過程中需要把普通數(shù)轉(zhuǎn)換成蒙哥馬利數(shù)，然后在根據(jù)系數(shù)進(jìn)行蒙哥馬利模乘運(yùn)算，那么轉(zhuǎn)換過程中需要用到轉(zhuǎn)換系數(shù)，該轉(zhuǎn)換系數(shù)一般通過大數(shù)模冪算法計(jì)算得到，使得現(xiàn)有的嵌入式安全芯片中需要進(jìn)行復(fù)雜的大數(shù)運(yùn)算，那么嵌入式安全芯片中的算法需要花費(fèi)較多的運(yùn)行時(shí)間和資源。

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

本發(fā)明的目的旨在至少解決上述技術(shù)缺陷之一，提供一種嵌入式安全芯片及其的蒙哥馬利模乘運(yùn)算方法。

本發(fā)明提供一種嵌入式安全芯片的蒙哥馬利模乘運(yùn)算方法，所述運(yùn)算方法包括以下步驟：

獲取兩個(gè)第一預(yù)設(shè)參數(shù)，和第二預(yù)設(shè)參數(shù)，其中第一預(yù)設(shè)參數(shù)為常數(shù)1；

根據(jù)兩個(gè)第一預(yù)設(shè)參數(shù)和蒙哥馬利模乘函數(shù)，得到第一運(yùn)算結(jié)果A；

根據(jù)第一運(yùn)算結(jié)果A、第一預(yù)設(shè)參數(shù)、第二預(yù)設(shè)參數(shù)和次方計(jì)算函數(shù)，得到第二運(yùn)算結(jié)果B，其中，第二預(yù)設(shè)參數(shù)為W-4，W =φ(N)，φ是歐拉函數(shù)，N是蒙哥馬利模乘中模數(shù)，次方計(jì)算函數(shù)為計(jì)算R^-1 數(shù)的多少次方的函數(shù)，R與 R^-1關(guān)于模數(shù)N互逆；

根據(jù)第一運(yùn)算結(jié)果A、第二運(yùn)算結(jié)果B和所述蒙哥馬利模乘函數(shù)，得到蒙哥馬利模乘轉(zhuǎn)換系數(shù)；

根據(jù)第一輸入?yún)?shù)NA、第二輸入?yún)?shù)NB、蒙哥馬利模乘轉(zhuǎn)換系數(shù)和所述蒙哥馬利模乘函數(shù)，得到最終模乘結(jié)果。

從上述方法的方案可以看出，次方計(jì)算函數(shù)只與蒙哥馬利模乘函數(shù)有關(guān)系。不同的模數(shù)N,通過調(diào)用不同次數(shù)的蒙哥馬利模乘函數(shù)，就能得到蒙哥馬利模乘的轉(zhuǎn)換系數(shù)，從而避開大數(shù)模冪方式的計(jì)算轉(zhuǎn)換系數(shù)，而且不需要事先計(jì)算好系數(shù)，可以節(jié)省存儲(chǔ)空間，另外在沒有復(fù)雜大數(shù)庫基礎(chǔ)上，也能完成非對(duì)稱密鑰運(yùn)算，以及可用于檢查一個(gè)大數(shù)是否為素?cái)?shù)的必要條件和可用于檢查蒙哥馬利模乘算法正確性。如果計(jì)算的數(shù)越來越長(zhǎng)，素?cái)?shù)域多個(gè)情況下，該算法的優(yōu)勢(shì)會(huì)更明顯。

本發(fā)明還提供一種嵌入式安全芯片，所述嵌入式安全芯片包括：

獲取模塊，用于獲取兩個(gè)第一預(yù)設(shè)參數(shù)，和第二預(yù)設(shè)參數(shù)，其中第一預(yù)設(shè)參數(shù)為常數(shù)1；

蒙哥馬利模乘模塊，用于根據(jù)兩個(gè)第一預(yù)設(shè)參數(shù)，得到第一運(yùn)算結(jié)果A；

次方計(jì)算模塊，用于根據(jù)所述蒙哥馬利模乘模塊輸出的第一運(yùn)算結(jié)果A、第一預(yù)設(shè)參數(shù)、第二預(yù)設(shè)參數(shù)和次方計(jì)算函數(shù)，得到第二運(yùn)算結(jié)果B，其中，第二預(yù)設(shè)參數(shù)為W-4，W =φ(N)，φ是歐拉函數(shù)，N是蒙哥馬利模乘中模數(shù)，次方計(jì)算函數(shù)為計(jì)算R^-1 數(shù)的多少次方的函數(shù)，R與 R^-1關(guān)于模數(shù)N互逆；

所述蒙哥馬利模乘模塊，還用于根據(jù)第一運(yùn)算結(jié)果A和第二運(yùn)算結(jié)果B，得到蒙哥馬利模乘轉(zhuǎn)換系數(shù)，以及根據(jù)第一輸入?yún)?shù)NA、第二輸入?yún)?shù)NB和蒙哥馬利模乘轉(zhuǎn)換系數(shù)，得到最終模乘結(jié)果。