[發(fā)明專利]用于蒙哥馬利模乘中的不均等分塊的數(shù)據(jù)處理方法及裝置

有效

• 申請?zhí)枺?/td>: 201811601122.0
• 申請日: 2018-12-26
• 公開（公告）號: CN109669670B
• 公開（公告）日: 2020-09-22
• 發(fā)明（設(shè)計(jì)）人: 楊帆
• 申請（專利權(quán)）人: 貴州華芯通半導(dǎo)體技術(shù)有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 北京市柳沈律師事務(wù)所 11105
• 代理人: 萬里晴

本公開提供用于蒙哥馬利模乘中的不均等分塊的數(shù)據(jù)處理方法及裝置。方法包括：對aM和bM、以及N和k添加位，并將其分組為不均等的分塊；將分塊的乘積結(jié)果表示為網(wǎng)格；在網(wǎng)格上劃分多個(gè)豎列，從第一豎列起，從低位到高位按豎列順序地計(jì)算大塊a_i×b_j和N_i×k_j并進(jìn)行對齊累加，需要累加到x+1豎列上的部分?jǐn)?shù)值在計(jì)算x+2豎列時(shí)才計(jì)算出來。當(dāng)計(jì)算到第x+1豎列及以后的豎列時(shí)，提前計(jì)算這部分?jǐn)?shù)值，并在計(jì)算下一豎列時(shí)拋棄這些數(shù)值；在所有豎列計(jì)算完成后，得到低2n+2m+1位的數(shù)據(jù)，作為(aM×bM+k×N)的結(jié)果；進(jìn)行移位處理得到pM＝(aM×bM+k×N)×R^?1；將pM作為輸入數(shù)據(jù)aM或bM，循環(huán)執(zhí)行上述過程，直到計(jì)算完一系列蒙哥馬利模乘運(yùn)算；輸出最后一個(gè)pM值。

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

本公開涉及加解密算法領(lǐng)域，更具體地，涉及一種用于蒙哥馬利模乘中的不均等分塊的數(shù)據(jù)處理方法及裝置。

背景技術(shù)

RSA(由Ron Rivest、Adi Shamir和Leonard Adleman共同提出)算法和橢圓曲線密碼學(xué)(Elliptic curve cryptography，ECC)算法是目前廣泛使用的加解密算法，這兩種加解密算法中運(yùn)算量最大的一種運(yùn)算就是大數(shù)模乘運(yùn)算。可以說，大數(shù)模乘直接決定了這兩種加解密算法的性能。大數(shù)模乘指的是p＝a×b mod N這樣的運(yùn)算；其中a、b、N都是較大的整數(shù)，一般大于2^64，其中，×代表乘法，mod代表除法后取余。要計(jì)算p＝a×b mod N，需要有乘法器來計(jì)算a×b。

如何提高大數(shù)模乘的運(yùn)算效率以及降低運(yùn)算負(fù)擔(dān)是需要考慮的問題。

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

技術(shù)問題

現(xiàn)有方法采用蒙哥馬利模乘來進(jìn)行大數(shù)模乘運(yùn)算，但是，因?yàn)槊筛珩R利模乘的特點(diǎn)，模乘的輸出比輸入要多一位，所以一般通過模凈運(yùn)算來將輸出的位寬改變?yōu)榕c輸入的位寬一樣。但是在連續(xù)計(jì)算的過程中，每一次計(jì)算都要插入模凈運(yùn)算，這樣會(huì)大大降低運(yùn)算效率。如果采用超越蒙哥馬利模乘來添加輸入的位，可以不需要模凈運(yùn)算，但是采用均等分塊會(huì)造成大量資源浪費(fèi)的問題，而采用不均等分塊也會(huì)存在“需要累加一個(gè)值的時(shí)候，這個(gè)值還沒有計(jì)算出”的問題，從而導(dǎo)致計(jì)算效率較低和多占用存儲(chǔ)資源。

技術(shù)方案

本公開提供了一種用于蒙哥馬利模乘中的不均等分塊的數(shù)據(jù)處理方法及裝置。