計算群元的整數(shù)倍的一種算法及其在公鑰密碼體制中的應(yīng)用

1、計算群元的整數(shù)倍的一種算法及其在公鑰密碼體制中的應(yīng)用 計算群元的整數(shù)倍的一種算法及其在公鑰密碼體制中的應(yīng)用孫 琦 張起帆四川大學(xué)數(shù)學(xué)學(xué)院 成都摘要 眾所周知、計算群元素的整數(shù)倍是許多密碼算法的基拙。最近,文提出整數(shù)的一種標(biāo)準(zhǔn)二進(jìn)制表示,當(dāng)群元素求逆運算的計算量很小時,用來計算群元素的整數(shù)倍,比通常的算法節(jié)省計算量。本文介紹這一新算法在三種公鑰密碼體制上的應(yīng)用 特別地,我們對于公鑰密碼體制,給出了一種新的算法群元素的整數(shù)倍 公鑰密碼體制丫關(guān) 群元素夢逆運算引言最近,文引人整數(shù)的一種標(biāo)準(zhǔn)二進(jìn)制表示,當(dāng)群元素求逆運算的計算量很小時,用來計算群元素的整數(shù)倍時,比通常的算法節(jié)省計算盤。例如,與著名的“平

2、方一和一乘法”算法相比,大約可減少 的計算量。本節(jié)介紹這一新算法,有關(guān)命題的證明從略,有興趣的讀者可參閱文熟知 任意的正整數(shù),不妨設(shè) ,通常有二進(jìn)制表示二藝可由下列帶余除法確定二卜 這里。顯然有 現(xiàn)將同樣的 表示為另一種二進(jìn)制,我們用 的廣義二進(jìn)制表示。一 二,一,這樣的表法當(dāng)然不惟一,但有一種標(biāo)準(zhǔn)的表法。它有最少的非的,且表法惟一。,則稱為 的標(biāo)準(zhǔn)定義若。 ,且對任意。 ,有,二。二進(jìn)制表示。命題 正整數(shù) 的標(biāo)準(zhǔn)二進(jìn)制表示惟一。求 的標(biāo)準(zhǔn)二進(jìn)制表示的算法,”、 、十, 氣一、陰, 氣二 或 十其中時。取 或一,使得,三,即,三時,取時,取一 一 設(shè) 、我們有藝 二例 一 一二二氣 內(nèi)憶 氣

3、憶 ,即一 一 。下列例子表明通常的二進(jìn)制可以從低位到高位轉(zhuǎn)換為標(biāo)準(zhǔn)二進(jìn)制 一一 一 一非且命題 若。在二進(jìn)制表示下是 位,則在標(biāo)準(zhǔn)二進(jìn)制表示下是 位或 位,、,二,。川 ,的 標(biāo)己命題 設(shè)。是任意給定的正整數(shù),在。的一切廣義二進(jìn)制表示式。 中準(zhǔn)二進(jìn)制表示含非零元的個數(shù)最少設(shè) 是群,對 中元素 和正整數(shù)。,有什么快速計算 的。倍 的方法 通常有兩種計算量相當(dāng)?shù)念愃扑惴ㄋ惴ㄒ?利用。的二進(jìn)制表示,則有。藝這樣,總共需要 次計算 倍的運算和 次 上的加法運算。這里表示非零的 的個數(shù)。故總共需 一次群 上的基本運算。在最壞的情況下需 次群 上的基本運算,這里,函數(shù)表示不超過實數(shù)二的最大整數(shù)。算法二

4、利用,有總計算量仍為 十 次群 上的基本運算,但這里的加法運算都是加 ,這就是著名的“平方一和一乘法”算法。在最壞的情況下,仍需要 次群 上的基本運算。如在算法二中用標(biāo)準(zhǔn)二進(jìn)制代替二進(jìn)制,可得下列更好的算法。算法三利用 的標(biāo)準(zhǔn)二進(jìn)制表示倆 互,和式 可得一 這樣 總計算量為十一次 卜的基本運算和一次求逆的運算,這里表示非零的 的個門二 數(shù),因此,在最壞的情況下一六一一 ,十一?,?需魚吻,十旦次群 喲基本運算和一次求逆的運算一 對很多有用的群,求元素的逆的計算量小得可以忽略不計,此時算法三的優(yōu)越性立見比算法一和算法二節(jié)約計算量約 在 三節(jié)中 我們分別給出算法三在三種公 密碼體制中的應(yīng)用。這三種

5、公鑰密碼體制中所依賴的群,都是求逆運算簡單的群注 本文完稿后,我們在網(wǎng)上讀到的文章,得知 世紀(jì) 年代國外已有人把整數(shù)的標(biāo)準(zhǔn)二進(jìn)制表示國外叫 。用來計算橢圓曲線公鑰密碼體制中群元的整數(shù)倍稱為上橢圓曲線公鑰密碼體制中的應(yīng)用定義設(shè)凡是一個元有限域, 尸 是素數(shù), 凡,且 凡上的方程的所有解 凡和一個無窮遠(yuǎn)點口組成的點集,稱為凡上由尹 護十十定義的橢圓曲線,記為 。我們在上定義下面的加法運算云口口勻?qū)λ械?凡對所有的 凡,即的負(fù)元是一 設(shè) 凡 凡,如果,則 ,這里一,一 ,一一十當(dāng)又產(chǎn)當(dāng)尸 我們有下面的定理。定理在 凡上定義加法運算滿足一,則凡是一個具有單位元 的交換群。熟知,在凡上可建立公鑰密碼體

6、制,其加、解密算法的基礎(chǔ)是計算群凡中元素的倍數(shù) 以上可參閱。下面 舉一個用算法三進(jìn)行計算的簡單例子。例 設(shè) 上的橢圓曲線 汽。 一由于 二,我們有 。取點 ,計算 。由于 用群運算規(guī)則和算法三計算 一 ,一 注對于氣上由尹十 十,十 定義的橢圓曲線 氣,其逆元定義為一 十 ,仍然是容易計算的。上圓錐曲線公鑰密碼體制中的應(yīng)用設(shè) 是一個奇素數(shù),仿射平面矛凡上的圓錐曲線 是指 ,一 嶸嶸表示 元域的乘群?顯然原點 在 上。若,令 ,由式 得一 若,則由式 給出 一 一于是有對,。凡 ,我們用表示 上由決定的點,原點 記為 。 尸。,。二 一 一文獻(xiàn)中定義了 中的加法運算。對任意,定義由 設(shè),其中 ,

7、定義 ,其中創(chuàng)竺 存在逆元,其中并證明了是一個加群。顯然 二 是零元, 此外,由式 易知 的逆元為自身。可見在加群 中 逆元極易計算。“一,若居,?若景一。于是,和有限域上橢圓曲線的點組成的加群一樣,可在上構(gòu)造公鑰密碼體制設(shè)凡是一個元有限域,文獻(xiàn)給出了凡上的廣義圓錐曲線 氣。凡在 句中定義加法田田 和九十仁十才幾 、并證明了 是一個加群以及 文獻(xiàn)還證明了 中的可化為耳或叮或叮中的 的問題?因此中的 不比有限域中的 困難由于在群 中逆元計算十分容易,用引言中的結(jié)果,我們給出了計算中點的倍數(shù) 的一個決速算法。下面給一個簡單的例子。例設(shè)上的圓錐曲線 滿足 一,因“,故。,?一,我們來計算點 的倍數(shù)

8、,由,一 ,故由引言中算法三,我們有,一一 二一 由注 對于廣義圓錐曲線 ,由于的逆元為一 ,仍然容易計算,所以,本文的快速算法也可用來算 中的元的倍數(shù) 公鑰密碼體制中的應(yīng)用年, 等利用 序列的性質(zhì)提出了公鑰密碼體制 文中有很好的描述為給定的整數(shù), 序列 一 二 一。 ,且有通頂公式一 ,竹刀 扮一尹是方程尸一 的根。不難驗證下列基本關(guān)系、,告一一粵 好一一 了 熟知,公鑰密碼體制對明文 的加密算法,即計算竹這里 表示兩個不同的大素數(shù) 的乘積文獻(xiàn) ,通過以下的命題,把公鑰密碼體制的加密算法式 ,化為在一個求逆元簡單的群中計算群元 的。倍,即命題 設(shè) 是一個具有單位元 的交換環(huán), 是 的乘法可逆

9、元,定義擴上的運算凡 為一,“一。,其中 為 中一固定元,則護,。構(gòu)成一個含單位元 的交換半群。命題 令凡一 ,則凡為礦, 的一個子群,且的逆元為,一, ?，F(xiàn)取 ,即整數(shù)模 的剩余類環(huán), 二礦一 為奇數(shù),即 是 中的乘法可逆元。在不致混淆的情況下,不區(qū)別整數(shù)和 中的元。可將長和 。都看做 中的序列,由式 和式 確定。關(guān)系式,式 和式 仍然成立。由命題和 知,在礦,。的子群凡中有于是 因為凡的任一元的逆元為,極易計算。所以,我們能夠在凡上用算法三通過計算來得到硯 。,這樣就給出了 公鑰密碼體制一個新算法。例 設(shè) ,加密算法 求牲。的二進(jìn)制表示和標(biāo)準(zhǔn)二進(jìn)制表示分別為一一一,一 一 一,一 ,一 ,

10、一 由 田我們有幾即密文為 下面是一個 較大的例子。例 設(shè),加密算法 求的標(biāo)準(zhǔn)二進(jìn)制表示為一 一 一,一一 ,一我們有 二 ,即密文為在文獻(xiàn)川中分析了用算法三計算 至多需做約次模。的乘法運算。結(jié)語許多公鑰密碼體制都依賴于求某個 群中的元素 的整數(shù)倍 。通常采用所謂“平方一和一乘法”算法計算 ,在最壞的情況下,約需次群加法運算。我們引人廣義二進(jìn)制和標(biāo)準(zhǔn)二進(jìn)制,當(dāng)群元素求逆運算的計算量很小時,采用標(biāo)準(zhǔn)二進(jìn)制設(shè)計類似的算法計算 ,在最壞的情況下,運算次數(shù)約,從而比原算法節(jié)約時間約。本文舉出三類公鑰密碼體制表明,其依賴的 群的群元素的求逆運算的計算量均可忽略不計。其中,我們證明了公解密碼體制的加密算法可以化為在一個求逆元簡單的群中計算群元的整數(shù)倍 從而給出了公鑰密碼體制新的加密算