第十八講密碼執行

《第十八講密碼執行》由會員分享，可在線閱讀，更多相關《第十八講密碼執行（31頁珍藏版）》請在裝配圖網上搜索。

1、第十八講 密碼執行(2)本講提要 q 模冪1 關于模冪計算 情況是綜合兩者。的乘法次數。最理想的法是減少計算模冪需要的時間；另一種方結構上兩個元的乘法一種是減少在某個代數減少計算模冪的時間。模冪。通常有兩種方法的算術操作之一就是公鑰密碼系統的最重要eg ElGamal (3)RSA (2)(1)類算法。加密簽名都可以使用這任意選擇?？梢怨潭ǘ笖禂倒潭ǖ讛的缢惴?。底類算法。加密簽名都可以使用這任意選擇?？梢怨潭ǘ讛禂倒潭ㄖ笖的缢惴?。指的情況。與指數意選擇底數基本模冪技術?？梢匀蝺缢惴?。我們考慮三種類型的模eggeeg1 關于模冪計算(續)2 模冪計算問題模型 1 1 (2)1(1)121

2、。使得，和，存在某個對于每一個；，滿足，序列的加法鏈是一個正整數kjilluuuikjkjile uuuuue定義1定義12.1 加法鏈值為零的函數。趨于無窮時其表示為底數，表示以這里，很大時，有的確切值。當相對較小情況下們僅知道在的最短加法鏈長度。我為令。，計算：的方法：個快速計算的最短加法鏈給出了一eo eeoeeleeleeelgggggelluuuue(1)2loglog log log(1)(1)log()()()(2)(1)132解釋.解釋.2.1 加法鏈(續)2.2 加-減法鏈 1 1 (2)1(1)121。，使得，和，存在某個對于每一個；，滿足，數序列的加減法鏈是一個正整kji

3、lluuuikjkjile uuuuue定定義義2 22.2 加-減法鏈(續)。限域離散對數密碼系統用于橢圓曲線密碼和有加減法鏈可以有效的應。，鏈，我們可以得到更短的但是如果允許使用減法，的最短加法鏈是如，減法。舉例來說，方法是允許其它操作，一種縮短加法鏈長度的解釋(2)31 32 16 8 4 2 131 21 11 10 5 3 2 131 (1).2.3 加法序列和向量加法鏈。，這里，是，的最短加法序列長度，證明了。，就是，算一組乘冪的情況，也加法序列可以應用于計。，它包含了，鏈的加法序列是一個加法，max log log log)1(log)()(Yao(2)(1)2121212121

4、212121tttteeetlteeeeeeoteeeeleeeleeegggeeeuuueeet 解釋.解釋.定義3定義32.3 加法序列和向量加法鏈(續)0 (2)1 0 0 0 1 0 0 0 1 (1)1101021。，使得，和，存在某個對于每一個；，滿足，向量序列是一個，一個向量加法鏈kjiltltDDDikjkjtilDDDDDDDDeeeD定定義義4 42.3 加法序列和向量加法鏈(續)全問題。完法序列問題是等人證明了尋找最短加。，就是，法序列的問題等價，也量的問題與尋找最短加證明了尋找最短加法向的最短加法向量。，是，令。是，算多乘冪的情形，也就向量加法鏈可以用來計續NPDown

5、ey)3()1()()(Olivos )(2)(1)(212121212121teeeleeeleeeeeelgggtttteteet 解釋.解釋.3 一般模冪技術3.1 二進制方法。則，如果。則，如果：。輸出：。和一個正整數輸入：從左向右二進制模冪)Return(3)1 (2.2)(2.1)following thedo 0 down to from For (2)1(1)(2011AgAAeAAAtit iAge eeeeGgiett算法1算法1)(100011011 283 8 2283。和。注意計算tg3.1 二進制方法(續)。平均：，最?。?，最大：因此，乘的總數量為：。我們有。在二進

6、制表示中的數量重量的是，這里：步第乘擴張的位數。的二進制比特是，這里：步第平方1/22/31)/2(1 1 12 1)(1)(1)(1Hamming)()()(2.2)(1)(2.1)(ttttttttteHeeHeHett效率.效率.3.1 二進制方法(續)3.1 二進制方法(續)。則，如果。則，如果。，。輸出：。和一個正整數輸入：從右到左二進制模冪算法)Return(3)(2.2)1 (2.1):following thedo to0 from For (2)1(1)(2011ASSStiSAAet igSAge eeeeGgiett2 。計算283g3.1 二進制方法(續)。平均：，最小

7、：，最大：因此，乘的總數量為：。我們有。：步第乘。：步第平方1/22/31)/2(1 1 12 1)(1)(1)()(2.1)()(2.2)(ttttttttteHeHt效率.效率.3.1 二進制方法(續)。的乘法效率可能高于任意的計算乘法，。對于特定選擇的某些為任意值代替乘法為固定值則是用乘法模冪的從左向右二進制。時計算乘法僅當定。要由計算平方的時間限的總體運行時間主，則個乘法和平方處理單元供一可以并行。假定可以提一個循環中的兩個操作相互獨立的，因此，計算過程中平方和乘是在。注意器存儲中需要一個額外的寄存在SASgAgSSAggASAeSi 算法1算法1算法2算法2算法2算法2算法2算法2算

8、法2算法2評述.評述.)()(1(2)(1)3.1 二進制方法(續)3.2 k-ary方法比特位。的。接著依次掃描，的值，這里方法首先計算。和注意。我們可以定義。個端添加，則最多在指數的最前不能整除。如果的塊，因此，有每個長度為的二進制表示可以分成方法二進制方法的思想：計算kei gkeeef fffeknknktkekeeeeeffffegkiiktiikijkjjkikikkikkiibttnne1232 =ary-2 1202)(0111)1(ary-)()(01022101120113.2 k-ary方法(續)。則，如果。，則如果：。因此，。：。預計算。輸出：。，這里，正整數和輸入：模

9、冪從左向右)Return(4)0 (3.2)(3.1)following thedo 0 down to from For(3)1(2)(do)12(to2 from For (1.2)(1.1).(1)1 2 )(ary-211011AgAAeAAtit iAggg ggigggkbeeeeegkikeiiiiikekbtt算算法法3 33.2 k-ary方法(續)個空間。，需要，存儲。平均：，最?。?，最大：為：。因此，總的乘法數量我們有。個數的非重量的是，這里：步第乘。：步第平方。：步第預計算計算 12 121 (2)2/11()1(22 122 1 22 1)(1)0(Hamming)(

10、)()(3.2)()(3.1)(22112 )(1.2)(1)kkikkkkbbbbkkigttktkttkteHeeHeHtk效率.效率.3.2 k-ary方法(續)。則，如果：。：。，預計算。輸出：。，這里和正整數輸入：模冪修改從左向右)Return(4)2/)(0 following thedo 0 down to from For(3)1(2)do)12(to1 from For (1.2)(1.1).(1)1 2)(ary-22212121221011AuegAAut iAg ggigggggkbeeeeegkihiuiiikekbttiihiihk算法4算法43.2 k-ary方法

11、(續)2(0 0 0 2 0 0(1)少預計算開銷。的略微修改，目的是減實際是對。和則令，如果是奇數；，這里則定可以寫，如果，對于每一個算算法法3 3算算法法4 4 解解釋釋.iiiiihiiuheuueetiii3.3 窗口方法次乘法。僅需要）（而另一種劃分是：次乘法。需要）（可得指數劃分為：方法，如果采用）（，其二進制表示為考慮指數15111 0 101 0 1001 1001 1111 00000 11 1011 000000 1 0 1101 1001 0 1001 0 111 000000 1 00 111 000 101118111 1010 0010 0011 1111 0001

12、 1100 1011 0000 0100 1101 1001 0010 1101 0001 1000 1100 0001 10114ary-10010101011011111001110111100000000011101010011010010100010000001101100011119189536631832623594742222eekkee3.3 窗口方法(續)。，并且做：，和，滿足找出最長的比特串，否則。，則如果：。，。：。，預計算。輸出：。而整數這里，和正整數輸入：窗口模冪)Return(4)1 1 1 0)(3.2)1 0 (3.1)following thedo 0 Whi

13、le(3)1(2)do)12(to1 from For (1.2)(1.1).(1)1 1)(211+)(2122121212212011AligAAekl+i eeeeiiAA eitiAg ggigggggkeeeeeegliili eeelliiiiiikettt算法5算法5。和3 00101)(101101111 117492ke3.3 窗口方法(續)在許多情況下，我們需要計算指數為固定值而底數不斷變化的模冪。例子有RSA加密和解密，以及ElGamal解密。這時我們可以考慮選擇一條優化的加法鏈計算。4 固定指數模冪算法4 固定指數模冪算法(續)。：。輸出：。，里這，以及相關的序列，的加法鏈的一條長度為正整數，輸入：加法鏈模冪)Return(3)do to1 from For (2)(1)()(210212110siiieissggggsigggiiwwwwuuuVseg 算法6算法64 固定指數模冪算法(續)。，的一條加法鏈是的長度為。計算15126 3 2 15 15 54321015uuuuuueg4 固定指數模冪算法(續)法鏈。法鏈通常不是最短加樣建立的給定指數的加比較容易，但是，這到一條加法鏈相對來說找的二進制表示，從表示給定一個指數乘法。次恰好需要，計算對于任意，的加法鏈給定的一條長度為對正整數esggsee(2)1 (1)算算法法6 6解解釋釋.謝謝!