多個(gè)指數(shù)運(yùn)算的乘子法

多個(gè)指數(shù)運(yùn)算的乘子法

1快速shamir算法在sra公鑰被盜密碼系統(tǒng)中，需要將m正整數(shù)m作為zn的模型操作，并將官僚主義-希存爾曼密鑰交換協(xié)議和elgamal密碼系統(tǒng)中的具體數(shù)字操作進(jìn)行驗(yàn)證。計(jì)算指數(shù)運(yùn)算ga的基本方法是“二進(jìn)制方法”,首先將a表示為二進(jìn)制形式,然后對(duì)a中的每一比特需一次平方,對(duì)a中的每一個(gè)1作一次乘g的運(yùn)算。對(duì)于tbit的數(shù)a,該方法需要t-1次平方和平均t-2次乘法。在很多情況下,需要計(jì)算多個(gè)指數(shù)運(yùn)算的乘積例如在除RSA之外的大多數(shù)字簽名算法(如ElGamal簽名算法)的驗(yàn)證簽名階段需要計(jì)算形如gahb的值。若采用二進(jìn)制方法分別計(jì)算ga和hb,再將它們相乘得到結(jié)果,則平均需要2(t-1)次平方和t次乘法。Shamir方法將兩個(gè)指數(shù)運(yùn)算并行計(jì)算,大大提高了運(yùn)算速度,平均僅需要t-1次平方和t次乘法;如果再預(yù)計(jì)算gh,則平均需t次平方和3t/4次乘法,此方法被稱為快速Shamir算法。各種形式的Shamir算法中平方都大約需要t-1次,只能盡可能減少乘法的次數(shù),兩個(gè)整數(shù)a,b中如果只有一個(gè)的Hamming重量較小,不一定能減少乘法運(yùn)算的次數(shù),需要的是整數(shù)對(duì)的非零列----聯(lián)合Hamming重量盡可能小。2001年,Solinas提出了整數(shù)對(duì)的聯(lián)合稀疏形(Jointsparseform)的概念,并證明:任意整數(shù)對(duì)的聯(lián)合稀疏形,在所有取0,±1三個(gè)值的聯(lián)合Hamming重量中是最小的,其聯(lián)合Hamming重量為l/2。考慮到在橢圓曲線加法點(diǎn)群中求點(diǎn)的逆元與兩點(diǎn)的加法運(yùn)算相比,所需運(yùn)算量可以忽略不計(jì),Solinas將聯(lián)合稀疏形與快速Shamir算法結(jié)合,來(lái)計(jì)算橢圓曲線群中的多點(diǎn)乘運(yùn)算aP+bQ,其中a,b為tbit整數(shù),P,Q為橢圓曲線上的點(diǎn),平均需要大約t次倍點(diǎn)運(yùn)算和大約t/2次點(diǎn)加運(yùn)算。2003年,JohnProos將該結(jié)果推廣到k個(gè)整數(shù)的情形,并給出計(jì)算整數(shù)組e0,e1,…,ek-1的聯(lián)合稀疏形的算法,用來(lái)高效計(jì)算多點(diǎn)乘e0P0+e1P1+…+ek-1Pk-1。但對(duì)于乘法半群Zn={0,1,…,n-1}(n為合數(shù))和有限域Fp(p為素?cái)?shù))的乘法群Fp·={1,2,…,p-1},求其中元素的乘法逆元的運(yùn)算量較大,不能忽略,本文針對(duì)這種情況提出了兩種有效的實(shí)現(xiàn)算法。本文在k個(gè)指數(shù)運(yùn)算的乘積中的指數(shù)組e0,e1,…,ek-1事先未知的前提下,首先在k個(gè)基元素g0,g1,…,gk-1都固定的條件下,將指數(shù)組e0,e1,…,ek-1表示成系數(shù)在{-1,0,1}中的聯(lián)合稀疏形,然后與快速Shamir算法相結(jié)合;其次,如果基g0,g1,…,gk-1中至少有一個(gè)不固定,則將e0,e1,…,ek-1表示成系數(shù)在{0,1,3,…,2n-1}中的串代換表示,再與快速Shamir算法相結(jié)合。最后,以ElGamal數(shù)字簽名算法的簽名驗(yàn)證為例與現(xiàn)有算法進(jìn)行比較。分析表明,算法有效降低了現(xiàn)有算法中運(yùn)算的次數(shù)。2指數(shù)運(yùn)算的乘子法設(shè)指數(shù)e0,e1,…,ek-1都是長(zhǎng)為tbit的非負(fù)整數(shù),某些指數(shù)的最高位比特可能是0,但至少存在一個(gè)指數(shù)的最高位比特為1。這些指數(shù)形成一個(gè)k×t陣列EA(稱為指數(shù)陣列),每一行就是ei(0≤i≤k-1)的二進(jìn)制表示,令I(lǐng)j為非負(fù)整數(shù),EA的第j(0≤j≤t-1)列是Ij的二進(jìn)制表示,其中低位比特位于列的上端。指數(shù)運(yùn)算乘積的Shamir算法輸入:k個(gè)元素g0,g1,…,gk-1及k個(gè)tbit非負(fù)整數(shù)e0,e1,…,ek-1。輸出:。步驟1預(yù)計(jì)算。對(duì)于i=0,1,…,2k-1,執(zhí)行,其中i的二進(jìn)制表示為i=(ik-1…i0)2。步驟2A←1。步驟3對(duì)于i從0到t-1,重復(fù)執(zhí)行A←A2,A←AGIi。步驟4返回A。該算法是進(jìn)行多個(gè)指數(shù)運(yùn)算的乘積的基本算法。注意到步驟3中的乘法對(duì)全0列是平凡的,而k×t陣列EA中全0列的個(gè)數(shù)平均為2-kt。因此,當(dāng)基g0,g1,…,gk-1都固定時(shí),步驟1可預(yù)先完成,此時(shí)平均需要執(zhí)行t-1次平方和(1-2-k)t次乘法;其次,如果基g0,g1,…,gk-1不固定,則算法平均需要執(zhí)行t-1次平方和(2k-k-1)+(1-2k)t次乘法,此外,不需要對(duì)所有的Gi(0≤i≤2k-1)都預(yù)先計(jì)算,只需對(duì)那些二進(jìn)制表示是EA的某一列的i進(jìn)行計(jì)算。例如,在計(jì)算gagb時(shí),只需要預(yù)計(jì)算gh,此時(shí)需要執(zhí)行t-1次平方和平均次乘法。3模型的聯(lián)合稀疏形法Solinas提出了整數(shù)對(duì)e0,e1的聯(lián)合稀疏形(JSF)的概念,并給出計(jì)算整數(shù)對(duì)的聯(lián)合稀疏形的算法。JohnProos給出計(jì)算整數(shù)組e0,e1,…,ek-1的聯(lián)合稀疏形的算法。如果將k個(gè)tbit非負(fù)整數(shù)e0,e1,…,ek-1表示為其中ei=(ei,l,ei,l-1,…,ei,0)分別為ei,i=0,1,…,k-1的一種帶符號(hào)二進(jìn)制表示,ei,j∈{-1,0,1},則在所有e0,e1,…,ek-1的帶符號(hào)二進(jìn)制表示中,其聯(lián)合稀疏形至多比其二進(jìn)制表示長(zhǎng)1bit,并且具有最少的非0列數(shù)目,即:e0,e1,…,ek-1的聯(lián)合稀疏形具有最小的聯(lián)合Hamming重量。特別地,當(dāng)k=2時(shí),整數(shù)對(duì)e0,e1的聯(lián)合稀疏形的非0列的平均數(shù)目為。利用聯(lián)合稀疏形的特點(diǎn),可在乘積中的基g0,g1,…,gk-1都固定的條件下,將指數(shù)組e0,e1,…,ek-1表示成系數(shù)在{-1,0,1}中的聯(lián)合稀疏形,然后與快速Shamir算法相結(jié)合,以有效減少Shamir算法中乘法的次數(shù)。算法1聯(lián)合稀疏形方法輸入:k個(gè)元素g0,g1,…,gk-1及k個(gè)tbit非負(fù)整數(shù)e0,e1,…,ek-1。輸出:步驟1預(yù)計(jì)算:所有可能的其中i0,…,ik-1∈{-1,0,1};步驟2計(jì)算k個(gè)整數(shù)e0,e1,…,ek-1的聯(lián)合稀疏形(1);步驟4對(duì)于i從0到t,利用預(yù)計(jì)算結(jié)果重復(fù)執(zhí)行:A←A2,步驟5返回A。在上述算法中,首先預(yù)計(jì)算所有可能的,其中i0,…,ik-1∈{-1,0,1},并存儲(chǔ)在一個(gè)表中,此時(shí),步驟4中的每次循環(huán)中i=0,1,…,t的值只需查表就可得到。特別地,當(dāng)k=2時(shí),由于整數(shù)對(duì)e0,e1的聯(lián)合稀疏形的非0列的平均數(shù)目為,因此該算法需要執(zhí)行t次平方和平均次乘法。該算法還可以利用滑動(dòng)窗口法進(jìn)行改進(jìn),進(jìn)一步減少運(yùn)算次數(shù)。算法2聯(lián)合稀疏形與滑動(dòng)窗口法相結(jié)合輸入:窗口寬度w,k個(gè)元素e0,e1,…,ek-1及k個(gè)tbit非負(fù)整數(shù)e0,e1,…,ek-1。輸出:。步驟1預(yù)計(jì)算:所有其中步驟2計(jì)算k個(gè)整數(shù)e0,e1,…,ek-1的聯(lián)合稀疏形(1)式。步驟3A←1,j←t。步驟4若e0,j=e1,j=…=ek-1,j=0,則j←j-1,A←A2。否則,(1)若j≥w,則j≥j-w,否則w←j,j←0;(3)尋找非負(fù)整數(shù)s=mmax{2m|gcd(f0,f1,…,fk-1),m≥0}(4)對(duì)于i從0到k-1,重復(fù)執(zhí)行fi←fi/2s;步驟5若j←0,則返回;否則轉(zhuǎn)至步驟4。4e+kn型若個(gè)元素g0,g1,…,gk-1事先已知,則上述算法1和算法2可將部分運(yùn)算轉(zhuǎn)移到預(yù)計(jì)算部分,從而節(jié)省大量運(yùn)算時(shí)間,但是,如果g0,g1,…,gk-1中至少有一個(gè)元素gi事先未知,則由于求元素gi的乘法逆元所需要的運(yùn)算量較大,不能忽略不計(jì),算法1和算法2將失去優(yōu)勢(shì)。此時(shí)采用串代換表示法來(lái)計(jì)算多個(gè)指數(shù)運(yùn)算的乘積以減少Shamir算法中運(yùn)算的次數(shù)。定義設(shè)n為正整數(shù),e是非負(fù)整數(shù),若則稱(ft-1,ft-2…f1f0)為e的一個(gè)n元串代換表示,記為SR(n)。二進(jìn)制表示是一個(gè)一元串代換表示。串代換表示一般是不唯一的。若n=3,e=987=(1111011011)2,則e的其它串代換表示還有(303003003)SR(3)(71003003)SR(3)等。算法3n元串代換表示輸入:e=(et-1,et-2…e1e0)2,正整數(shù)n≥2。步驟1對(duì)于i從n遞減到2,執(zhí)行:從e=(et-1,et-2…e1e0)2的最高位數(shù)字開始,依次找到所有長(zhǎng)為i的全1串,并分別用2i-1代換串的最低位,其余i-1位用0來(lái)代替。步驟2返回(ft-1,ft-2…f1f0)SR(n)。該算法不能保證得到的SR(n)表示具有最少的非零項(xiàng),但實(shí)際上這種表示接近于最少的非零項(xiàng)表示,研究表明:對(duì)一個(gè)隨機(jī)選取的tbit指數(shù),如果選擇合適的n,其SR(n)表示約有t/4個(gè)非零項(xiàng)。算法4用SR(n)表示的多指數(shù)運(yùn)算輸入:k個(gè)元素g0,g1,…,gk-1及k個(gè)tbit非負(fù)整數(shù)e0,e1,…,ek-1。步驟1預(yù)計(jì)算:對(duì)于i從0到k-1,執(zhí)行:對(duì)于j從2到n,計(jì)算步驟2計(jì)算k個(gè)整數(shù)e0,e1,…,ek-1的聯(lián)合SR(n)表示步驟3A←1。步驟4對(duì)于i從t-1遞減到0,重復(fù)執(zhí)行:A←A2,步驟5返回。由于每個(gè)tbit指數(shù)的SR(n)表示中每一位非零的概率約為0.25,故k個(gè)整數(shù)e0,e1,…,ek-1的聯(lián)合SR(n)表示的每一列非0元素的數(shù)目是j的概率約為0.25j(1-0.25)k-j,因此該算法需要執(zhí)行t-1+k(n-1)次平方和平均約次乘法。特別地,當(dāng)k=2時(shí),該算法需要執(zhí)行t-1+2(n-1)次平方和平均次乘法。另一種選擇是預(yù)計(jì)算所有而在步驟4只需查表即可,此時(shí)該算法需要執(zhí)行t-1+k(n-1)次平方和平均(1-0.75k)t+(k+n-1)(n-1)次乘法。這比上述策略所需乘法的數(shù)量要多。類似于算法1,該算法也可以利用滑動(dòng)窗口法進(jìn)行改進(jìn)。5快速shamir算法以ElGamal簽名方案的簽名驗(yàn)證階段的實(shí)現(xiàn)為例,將所提出算法的效率與快速Shamir算法進(jìn)行比較。ElGamal簽名方案的簽名驗(yàn)證方程是:其中p是一個(gè)大素?cái)?shù),!是Zp·的一個(gè)生成元,!a是公開密鑰,(r,s)是消息m的簽名,因而驗(yàn)證方程需要三次指數(shù)運(yùn)算和一次乘法運(yùn)算,如果t=「log2p-,那么所需的平方次數(shù)是3(t-1),乘法的平均次數(shù)是1.5t,故約進(jìn)行(9t-4)/2次模的乘法和平方運(yùn)算。首先,將驗(yàn)證方程(2)寫成形式1:!h(m)(!-a)r≡rs(modp),由于!和!-a=(!a)-1事先已知,因此可以先計(jì)算!h(m)(!-a)rs(modp),再計(jì)算rs(modp)。如果利用快速Shamir算法,則平均需要執(zhí)行2(t-1)次平方和0.75t+0.5t=1.25t次乘法。但是,如果利用算法1,則平均需要執(zhí)行2(t-1)次平方和0.5t+0.5t=t次乘法。故算法1比快速Shamir算法減少了0.25t次乘法運(yùn)算。其次,將方程(2)重新寫成形式2:!h(m)(!-a)rr-s≡1(modp),取g0=!,g1=!-a,g2=r,e0=h(m)mod(p-1),e1=rmod(p-1),e2=-smod(p-1)則ElGamal簽名方案的簽名驗(yàn)證階段轉(zhuǎn)化為計(jì)算3個(gè)指數(shù)運(yùn)算的乘積:其中基g0,g1固定,而g2=r事先未知,不能利用聯(lián)合稀疏形進(jìn)行計(jì)算。如果利用快速Shamir算法,則平均需要執(zhí)行t-1次平方和(23-3-1)+(1-2-3)t=4+0.875t次乘法,乘法和平方的期望次數(shù)是1.875t+3。但是,如果利用算法4,則平均需要執(zhí)行t-1+3(n-1)次平方和平均0.28125t+3(n-1)次乘法,乘法和平方的期望次數(shù)是1.28125t+6n-7。故算法1比快速Shamir算法減少了0.59375t-6n+11次運(yùn)算。不妨設(shè)t=「log2p-=1024,n=3則表1給出了算法1和算法4與快速Shamir算法的比較結(jié)果。結(jié)果表明,利用所提出的算法可實(shí)質(zhì)性地減少運(yùn)算次數(shù)。由此可見,本文提出的算法可以廣泛應(yīng)用于大多數(shù)數(shù)字簽名算法中,用來(lái)提高簽名驗(yàn)證的實(shí)現(xiàn)速度。6elgamal