[發明專利]包括與標量或求冪的乘法運算的密碼學方法

有效

• 申請號: 201480005200.4
• 申請日: 2014-01-13
• 公開（公告）號: CN104937537B
• 公開（公告）日: 2017-10-24
• 發明（設計）人: B·菲克斯;V·韋爾努爾;C·克拉維耶
• 申請（專利權）人: 英賽瑟庫爾公司
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 北京市中咨律師事務所11247
• 代理人: 楊曉光,于靜

本發明涉及在電子設備中的橢圓曲線密碼學的實現，以及更具體地涉及用于計算與屬于橢圓曲線的點的標量乘法的結果的方法

各種已知的橢圓曲線密碼學方法基于標量乘法，標量乘法的數學表達式是：[k]·P＝P[+]P[+]...[+]P(k次)，P是在橢圓曲線上選擇的點，k是整數，以及“[+]”是應用于橢圓曲線的點的加法運算符。數字k是例如私有密鑰，以及這個運算的結果點[k]·P，或結果點的仿射坐標(affine coordinates)中的一個仿射坐標，能夠用作公開密鑰。實際上，在知道[k]·P和點P的坐標的情況下，找到數目k的值可能是極其困難的。例如在簽名計算期間使用這個運算，或這個運算用于生成密碼學密鑰，或甚至用于將消息譯成密碼。基于橢圓曲線，諸如ECDSA(“橢圓曲線數字簽名算法”)、ECDH(橢圓曲線Diffie-Hellman)、ECIES(橢圓曲線綜合的密碼學方案)等，通過各種密碼學算法來實現這個運算。

在橢圓曲線的點之間的運算相當于在形式F_q的伽羅華域中在這些點的坐標上的運算，q是素數p，或2的冪(形式2^m)。標量乘法運算一般被分解成一連串的對點進行加法和雙倍的運算。因此，一種眾所周知的方法涉及借助于在附錄I中出現的“雙倍&加法”算法A1或A1’來執行標量乘法計算。算法A1可以說是“從左到右”，因為計算環路的第一步驟從處理標量數k的最高位開始，直到最低位。算法A1’可以說是“從右到左”，因為計算環路的第一步驟從處理標量數的最低位開始，直到最高位。

這些算法包括：針對每次迭代，即，指數的每個比特，橢圓曲線的兩個相同點R的加法，以及如果通過迭代所處理的標量的比特等于1，則點R與橢圓曲線的另一個點P的加法。不同的函數一般用于執行這些運算中的每個運算，借助于雙倍函數或“DOUBLE”函數來執行兩個相同點的加法，而借助于加法函數或“ADD”函數來執行兩個不同點的加法。這個區別是由于以下事實：當與相反的情況相比，點P和Q是相同的時，借助于DOUBLE函數能夠更加快速地計算P[+]Q。在某些坐標系統中，兩個相同點的加法能夠導致除以零。因此，另一種計算模式是需要的。

在智能卡類型的電子設備中，密碼學計算一般由諸如算術協處理器或密碼處理器的特定處理器來執行。相對于生成密鑰、計算簽名、檢查簽名或執行加密或解密運算它花費的總時間而言，“[k]·P”的計算，以及更具體地橢圓曲線的點的加法的執行，占據處理器的計算時間的大部分。使用可替代地依賴于將執行的計算的類型的DOUBLE函數或ADD函數優化了總的加密、解密、簽名或簽名檢查計算時間。

然而，使用兩個不同的DOUBLE和ADD函數導致由簡單功率分析(SPA)，即通過分析卡的電流消耗，能夠檢測的信息泄露。因為DOUBLE函數具有比ADD函數短的運行時間，因此，能夠通過觀察組件的電流消耗曲線來區分這兩種運算。“電流消耗”意味著任何可以觀察到的物理值，該可以觀察到的物理值揭示執行運算的電子組件的運算，特別是該組件消耗的電流或電磁輻射。因此，在運行算法A1的組件的電流消耗曲線上，能夠區分DOUBLE函數的消耗輪廓和ADD函數的消耗輪廓。由ADD運算跟隨的DOUBLE運算(由步驟2.2跟隨步驟2.1)揭示了標量數k的比特等于1，因為朝向步驟2.2的條件分支要求的是，滿足條件k_s＝1。相反，由另一個DOUBLE運算跟隨的DOUBLE運算(由另一個步驟2.1跟隨步驟2.1)揭示了標量數k的比特等于0。因此，通過電流消耗曲線的簡單觀察，能夠陸續地發現標量數k的比特。

為了克服這個缺點，能夠(如果可能的話)借助于僅ADD函數而不使用DOUBLE函數來執行算法A1和A1’的步驟2.1和2.2。然而，因為算法A1或A1’不規整(regular)，因此電流消耗的更詳細的分析使得步驟2.1能夠與步驟2.2進行區分。實際上，在這種情況下，當兩個加法對應于兩個步驟2.1的連續執行(比特k_s等于0)或對應于由步驟2.2跟隨的步驟2.1的執行(比特k_s等于1)時，在兩個連續加法之間流逝的時間不是相同的。因此，攻擊者能夠在加法之間延伸的消耗曲線上進行“縮放(zoom)”，以及將看到揭露條件分支的時間不對稱以及從而揭露標量數的比特的值。