[發(fā)明專利]包括求冪運(yùn)算的加密方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201210040697.6
• 申請(qǐng)日: 2012-02-21
• 公開(kāi)（公告）號(hào): CN102684876A
• 公開(kāi)（公告）日: 2012-09-19
• 發(fā)明（設(shè)計(jì)）人: B·菲克斯;G·加戈納羅特;M·羅瑟萊特;V·韋納伊;C·克拉維耶
• 申請(qǐng)（專利權(quán)）人: 英賽瑟庫(kù)爾公司
• 主分類號(hào): H04L9/32
• 分類號(hào): H04L9/32
• 代理公司: 北京市中咨律師事務(wù)所 11247
• 代理人: 張靜美;楊曉光

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

本發(fā)明涉及一種在電子設(shè)備上實(shí)現(xiàn)的按照指數(shù)d來(lái)對(duì)數(shù)據(jù)m求冪的結(jié)果的迭代計(jì)算方法。

背景技術(shù)

各種已知的加密方法是基于模冪運(yùn)算，其數(shù)學(xué)表示如下：

m^d?modulo(n)，

其中m是輸入數(shù)據(jù)，d是指數(shù)，n是模。模冪函數(shù)用于計(jì)算基數(shù)(potency)為d的m被n相除的余數(shù)。

這樣的函數(shù)由諸如算法RSA(“Rivest，Shamir?et?Adleman”)、算法DSA(“數(shù)字簽名算法”)、El?Gamal等的各種加密算法來(lái)使用。數(shù)據(jù)m通常是要解密或簽名的消息，而指數(shù)d是私鑰。

已知通過(guò)下面的“平方&乘法”算法A1或A1’來(lái)執(zhí)行模冪計(jì)算。

算法A1---“平方&乘法”求冪，從左到右

輸入：

整數(shù)“m”和“n”，例如m＜n

v個(gè)比特的指數(shù)“d”，例如d＝(d_v-1d_v-2...d₀)₂

輸出：a＝m^d?modulo?n

步驟1：a＝1

步驟2：對(duì)于在v-1和0之間的s進(jìn)行：

(步驟2A)a＝(a×a)mod?n???????????????(平方)

(步驟2B)如果d_s＝1，則a＝(a×m)mod?n??(乘法)

步驟3：輸出結(jié)果a

算法A1’---“平方&乘法”求冪，從右到左

輸入：

整數(shù)“m”和“n”，例如m＜n

v個(gè)比特的指數(shù)“d”，例如d＝(d_v-1d_v-2...d₀)₂

輸出：a＝m^d?modulo?n

步驟1：a＝1；b＝m

步驟2：對(duì)于在0和v-1之間的s進(jìn)行：

(步驟2A’)如果d_s＝1，則a＝(a×b)mod?n??(乘法)

(步驟2B’)b＝(b×b)mod?n???????????????(平方)

步驟3：輸出結(jié)果a

算法A1稱為“從左到右”是因?yàn)橛?jì)算循環(huán)的第一步驟從指數(shù)的最高有效位開(kāi)始朝著最低有效位行進(jìn)。算法A1’稱為“從右到左”是因?yàn)橛?jì)算循環(huán)的第一步驟從指數(shù)的最低有效位開(kāi)始朝著最高有效位行進(jìn)。

這些算法包括使兩個(gè)相同的大尺寸變量相乘以及使兩個(gè)不同的大尺寸變量相乘。這通常涉及不同的函數(shù)來(lái)執(zhí)行這些運(yùn)算中的每個(gè)運(yùn)算，使兩個(gè)相同的大尺寸變量相乘是通過(guò)平方函數(shù)或“SQUARE”函數(shù)來(lái)執(zhí)行的，而使兩個(gè)不同的大尺寸變量相乘是通過(guò)乘法函數(shù)或“MULT”函數(shù)來(lái)執(zhí)行的。該區(qū)別是由于以下事實(shí)：當(dāng)x＝y(tǒng)時(shí)，相比于相反的情況，通過(guò)SQUARE函數(shù)可更快地計(jì)算x×y。SQUARE函數(shù)的執(zhí)行時(shí)間和MULT函數(shù)的執(zhí)行時(shí)間之間的比值通常大約為0.8，但是根據(jù)以下情況可以在0.5和1之間變化：所考慮的數(shù)的尺寸、執(zhí)行乘法的方式，等等。

在芯片卡類型的電子設(shè)備中，加密計(jì)算通常由專用處理器(諸如算術(shù)協(xié)處理器或加密處理器)來(lái)執(zhí)行。計(jì)算“m^d?modulo?n”(并且尤其是執(zhí)行乘法)相比于簽名或加密或解密運(yùn)算的總計(jì)算時(shí)間來(lái)說(shuō)占用了處理器的大部分計(jì)算時(shí)間。因此，根據(jù)將要進(jìn)行的計(jì)算類型來(lái)交替使用SQUARE函數(shù)或MULT函數(shù)使得整體加密、簽名或解密計(jì)算時(shí)間得到優(yōu)化。

然而，使用兩個(gè)不同的函數(shù)SQUARE和MULT導(dǎo)致信息泄漏，可通過(guò)SPA(單功率分析)(即，通過(guò)對(duì)卡的電消耗進(jìn)行分析)而檢測(cè)該信息。SQUARE函數(shù)比MULT函數(shù)具有更短的執(zhí)行時(shí)間，通過(guò)觀測(cè)元件的電消耗曲線可以區(qū)分這兩個(gè)運(yùn)算。“電消耗”表示的是指示了執(zhí)行運(yùn)算的電子元件的運(yùn)算的任何可觀察物理量，特別是該元件的電磁輻射或消耗的電流。

圖1示出了執(zhí)行算法A1的元件的電消耗的曲線?？梢郧宄乜吹絊QUARE和MULT函數(shù)的消耗分布。SQUARE運(yùn)算之后是MULT運(yùn)算(步驟2A之后是步驟2B)揭示了指數(shù)d的那個(gè)比特等于1，因?yàn)橥ㄍ襟E2B的條件分支要求驗(yàn)證條件d_s＝1。相反地，SQUARE運(yùn)算之后是另一個(gè)SQUARE運(yùn)算(步驟2A之后是另一個(gè)步驟2A)揭示了指數(shù)的那個(gè)比特等于0。因而，通過(guò)簡(jiǎn)單地觀察電消耗曲線可以接連地發(fā)現(xiàn)指數(shù)d的比特。