對(duì)一種背包公鑰密碼的分析和改進(jìn)

1、對(duì)一種背包公鑰密碼的分析和改進(jìn)費(fèi)向東通信作者：費(fèi)向東，feixd0669，電話丁燕艷，潘郁（南京工業(yè)大學(xué)經(jīng)濟(jì)與管理學(xué)院，南京 210009）摘要：分析一個(gè)稱為隨機(jī)背包的公鑰密碼算法，闡述背包公鑰序列是由初始序列運(yùn)算變換來的，初始序列存在冗余度，因此背包公鑰序列不可能是完全隨機(jī)的。目前大多數(shù)被破譯的背包公鑰算法只使用了屬于混亂技術(shù)的模乘運(yùn)算，這不足以隱藏初始序列的冗余度，利用這些冗余度是破譯成功的必要條件。為此，本文引入加法擴(kuò)散技術(shù)以分散始序列的冗余度，設(shè)計(jì)了新的公鑰密碼算法，攻擊者在破譯過程中無法利用該冗余度。關(guān)鍵詞：背包公鑰密碼；隨機(jī)；冗余度；模乘運(yùn)算；混亂；擴(kuò)散中

2、圖分類號(hào)：TN918.1Analysis and improvement of a knapsack Public-key CryptosystemFei Xiang-dong, Ding Yan-yan，Pan Yu(School of Economics and Management, Nanjing University of Technology, 210009)Abstract：Analyzing a so-called random knapsack public-key cryptosystem，it is expounded that a knapsack public-key

3、 sequence is gained by transforming an initial sequence with redundancy，hence a knapsack public-key sequence is impossibly random. So far，most knapsack cryptosystems that have been broken only use confusion ，such as modular multiplication，as can not conceal the redundancy of the initial sequence ade

4、quately. It is necessary to utilize the redundancy for breaking the cryptosystem successfully. Therefore，addition diffusion is introduced in this paper to diffuse the redundancy of an initial sequence.A new knapsack public-key cryptosystem with diffusion is devised，so that the adversary can not make

5、 use of the redundancy when breaking the cryptosystem. Key words: Knapsack public-key cryptosystem；Radom；Redundancy；Modular multiplication；Confusion；Diffusion；1 引言公鑰密碼是確保信息安全和網(wǎng)絡(luò)安全的重要技術(shù)，背包公鑰作為最早提出的公鑰密碼之一，曾經(jīng)是業(yè)界的希望和熱點(diǎn)，但大多數(shù)背包公鑰算法都被破譯了 1。背包公鑰的安全性是基于求解子集和問題的困難性，設(shè)計(jì)思想通常是把易解背包問題偽裝成一個(gè)看似困難的背包問題，這一偽裝方法就是嵌入陷門，陷門

6、信息作為私鑰僅被合法接收者掌握，運(yùn)用它可以把該問題恢復(fù)成一個(gè)易解背包問題，通過解該易解背包問題重構(gòu)明文；而對(duì)于非法接收者來說，從密文恢復(fù)明文就相當(dāng)于解一個(gè)困難的背包問題。但存在著以下難題：如果陷門隱藏得不充分，則攻擊者可以從公鑰出發(fā)求解出對(duì)應(yīng)的陷門信息；如果隱藏得充分，則背包密度可能降低，Coster等人證明若背包密度小于0.9408的背包公鑰系統(tǒng)都易遭受低密度子集和攻擊2，而若背包密度大于1，又帶來解密不唯一的問題。因此，構(gòu)造一個(gè)安全的背包公鑰密碼系統(tǒng)異常困難，業(yè)內(nèi)普遍認(rèn)為背包公鑰算法已經(jīng)死亡。但由于背包公鑰算法的快速加解密優(yōu)勢(shì)和背包問題的NPC性質(zhì)，特別適合應(yīng)用于物聯(lián)網(wǎng)等資源受限的場(chǎng)合，故

7、背包公鑰算法仍然具有相當(dāng)?shù)奈?。最近，王保倉等學(xué)者提出了基于隨機(jī)背包的公鑰加密算法3（以下簡(jiǎn)稱“王背包算法”），認(rèn)為該算法具有如下優(yōu)點(diǎn)：加解密速度快；基于隨機(jī)背包問題而不是易解背包問題構(gòu)造的；在攻擊者不掌握私鑰情況下該密碼算法能抵抗直接求解背包問題的攻擊，包括低密度攻擊和聯(lián)立丟番圖逼近攻擊等；證明攻擊者能夠恢復(fù)私鑰信息與攻擊者能夠分解一個(gè)大整數(shù)是等價(jià)的?？傊?，該算法是一個(gè)安全高效的公鑰加密算法。如果一個(gè)背包密碼算法是真正基于隨機(jī)背包而不是基于易解背包問題的，那么攻擊者從公鑰出發(fā)所進(jìn)行的推斷將無法驗(yàn)證是否正確，必然是無法破譯的。但本文指出，王背包算法的構(gòu)造并不是隨機(jī)的，公鑰隱藏著陷門信息。分析

8、表明，運(yùn)用格規(guī)約算法4，再使用整數(shù)規(guī)劃方法，就可以不可忽略的概率破譯該密碼算法。 2 王背包算法描述整數(shù)m的二進(jìn)制表示記為(m)2。該公鑰密碼算法描述如下。密鑰生成 該算法的公、私鑰生成算法如下：隨機(jī)選取n個(gè)背包項(xiàng)形成初始序列U = (u1，un ) ，其中ui均為正整數(shù)，計(jì)算序列V = (v1，vn )，其中vi= ui 2n-i，i = 1，n。隨機(jī)選取兩個(gè)不同的素?cái)?shù)p和q，使得：p ，q 2max，- （2-1）使用中國(guó)剩余定理計(jì)算序列A = (a1，an)，0aipq1即，ai ui (mod p)，ai vi (mod q ), i =1，n 這里ai是取模N = pq 的非負(fù)最小剩

9、余。輸出背包序列A為公鑰，用戶保存p和q為私鑰。加密 n比特長(zhǎng)的二進(jìn)制明文(m)2 = ( m1mn ) ，其中mi= 0或1，被加密為c = a1m1+ anmn 。解密 接收到密文c 后，作如下計(jì)算即可恢復(fù)明文。首先計(jì)算cp = c(mod p) , cq = c(mod q )，這里cp 取模p的非負(fù)最小剩余，即0cpp-1，cq取模q的絕對(duì)最小剩余，即q/2 cqq/2。則明文(m)2 =(cpcq)2，即cp cq 的二進(jìn)制表示就是m1mn ，其中m1是cp cq二進(jìn)制表示的最高位，m2是cp cq 二進(jìn)制表示的次高位，依次類推，mn是(cp cq)2的最低位。3 王背包算法的非隨機(jī)

10、性公鑰序列A = (a1，an)，其中0aipq1，p大于序列U的所有項(xiàng)之和，q大于序列v的所有項(xiàng)之和。由于密文c=a1m1+ anmn ，其中mi= 0或1，因此，這是一個(gè)0-1背包問題，背包密度定義為：D=n/log2(max ai)公鑰序列A是由初始序列U和V經(jīng)中國(guó)剩余定理變換而來的。初始序列U和V并不是完全隨機(jī)的，U的項(xiàng)和V的項(xiàng)之間的差為2n-i，該差值為超遞增序列，ui = vi+ 2n-i，i = 1，n 。即，序列U是序列V上疊加了一超遞增序列形成的。由于0aipq1，公鑰項(xiàng)ai的最大長(zhǎng)度可以是pq的長(zhǎng)度，即：log2(max ai) log2(pq)。根據(jù)（2-1）式，p的長(zhǎng)度

11、大于ui的長(zhǎng)度，q的長(zhǎng)度大于vi的長(zhǎng)度，i = 1，n 。如前所述，背包密度須大于0.9408才能保證安全，即，pq的長(zhǎng)度不能大于n/0.9408比特。因此，初始序列U的項(xiàng)ui的取值是不能隨機(jī)的，如u1 =22n，則v1= 22n 2n-1，v1的長(zhǎng)度為2n-1比特，此時(shí)pq的長(zhǎng)度肯定大于n/0.9408比特，背包密度小于0.9408，無法保證安全。為了保證背包密度大于0.9408，ui和vi的長(zhǎng)度必須盡可能小，尤其是對(duì)于u1和v1，其差值最大，為2n-1保證ui和vi的長(zhǎng)度盡可能小的方案是vi取絕對(duì)值盡可能小的負(fù)數(shù)，而ui的最大長(zhǎng)度就是u1的長(zhǎng)度。此時(shí)q的最大長(zhǎng)度r必須滿足以下關(guān)系： 0.9

12、408n/(n-2+r)計(jì)算得：r0.0629n+0.9408V各項(xiàng)的長(zhǎng)度都小于q，故vi是比特位數(shù)更小的負(fù)整數(shù)。此時(shí)序列U的各項(xiàng)雖然可能不形成超遞增關(guān)系，但vi的絕對(duì)值小于2r-1，因此有如下關(guān)系：ui+(2r-1) ui+1+ ui+2+ un等同于超遞增關(guān)系，適合運(yùn)用整數(shù)規(guī)劃方法求解。其中，p的長(zhǎng)度遠(yuǎn)遠(yuǎn)大于q的長(zhǎng)度，可以參照文獻(xiàn)5該算法作者本人演示的方法或文獻(xiàn)15前面部分的方法求出U的各項(xiàng)及p，進(jìn)而破解整個(gè)算法。4 重新認(rèn)識(shí)背包公鑰算法4.1 背包公鑰算法之安全性背包公鑰序列有別于隨機(jī)數(shù)序列是因?yàn)榍罢呤怯沙跏夹蛄凶儞Q而來的，并以此隱藏陷門?？梢园殉跏夹蛄锌醋鞅患用艿南?，初始序列到公鑰的

13、變換過程可以看成是加密過程，背包公鑰序列看作加密后的密文。從計(jì)算復(fù)雜性理論上講，如果加密過程（初始序列到公鑰的變換過程）是安全的，那么從密文（公鑰）出發(fā)破譯該算法的時(shí)間和空間復(fù)雜性極大，甚至等價(jià)于求解一個(gè)NPC問題，那么該算法就被認(rèn)為是一個(gè)安全的背包公鑰密碼算法。初始序列代表著易解背包，是有一定規(guī)律和特性的，如MH背包6中初始序列的超遞增性、“王背包算法”中初始序列差值的超遞增性。這些規(guī)律和特性形成初始序列的冗余度7，冗余度作為算法的一部分，是公開的。背包公鑰序列作為初始序列變換的最終結(jié)果，殘留著這些冗余度。事實(shí)上，任何公鑰密碼的公鑰必然隱藏著私鑰信息（全部或部分），不存在完全隨機(jī)的公鑰。如果

14、初始序列是隨機(jī)數(shù)序列，其冗余度為零，破譯者在沒有獲得初始序列的情況下，無法搜尋和驗(yàn)證所要破譯的密鑰，該背包公鑰是無法破譯的。因此，破譯者利用初始序列的冗余度是破譯成功的最低要求。無論是Shamir對(duì)MH背包的攻擊8，還是其它攻擊法，都必須利用初始序列的冗余度進(jìn)行破譯，其中，Shamir攻擊法的唯一解距離為4，即攻擊者至少需要利用超遞增初始序列中的4項(xiàng)。一個(gè)背包公鑰算法是安全的，其必要條件是能夠防止破譯者從公鑰出發(fā)利用初始序列及冗余度。4.2 混亂和擴(kuò)散Shonnon提出了隱藏被加密消息中冗余度的兩種方法7：混亂（confusion）和擴(kuò)散（diffusion）?；靵y是指在加密變換過程中使明文、

15、密鑰以及密文之間的關(guān)系盡可能地復(fù)雜化，用于掩蓋明文和密文之間的關(guān)系，以防破譯者采用統(tǒng)計(jì)分析法進(jìn)行破譯攻擊?；痉椒ㄊ谴?，明文字符被密文字符代替。一般來說，僅用代替是不夠的。二戰(zhàn)中德國(guó)的恩尼格馬是一復(fù)雜的代替算法，但被破譯了。擴(kuò)散是指要將算法設(shè)計(jì)得使每一比特明文的變化盡可能多地影響到輸出密文序列的變化，就是將明文冗余度度分散到密文中使之分散開來，以便隱蔽明文的統(tǒng)計(jì)特性；擴(kuò)散的另一層意思是將每一位密鑰的影響也盡可能迅速地?cái)U(kuò)展到較多的輸出密文比特中去?；痉椒ㄊ菗Q位（又稱置換）。通常，單獨(dú)用擴(kuò)散也容易被破譯。不論是“混亂”還是“擴(kuò)散”，每一步都必須是可逆的，即密文經(jīng)過逆向的混亂或擴(kuò)散操作以后能還原

16、出初始數(shù)據(jù)。4.3 模乘運(yùn)算混亂技術(shù)的實(shí)現(xiàn)方式有多種9，DES采用“S盒”，IDEA采用模乘運(yùn)算。背包公鑰算法都采用模乘運(yùn)算實(shí)現(xiàn)混亂。模乘運(yùn)算表示為：b wu (mod m )其中，m為模，b為w乘以u(píng)后取模m的余。存在如下關(guān)系：b= wu-k*m （4-3-1）k為某個(gè)正整數(shù)。模乘運(yùn)算為乘法群運(yùn)算，在正整數(shù)域中，按照一定的線性關(guān)系，用一個(gè)整數(shù)代替另一整數(shù)。其優(yōu)點(diǎn)是當(dāng)w和u較大時(shí)，雪崩效應(yīng)明顯，即w或u變化一位，將引起b的劇烈變化。其缺點(diǎn)是變換為線性：乘數(shù)u中的每位同等擴(kuò)張后取模p的余，各位之間仍然在模p這個(gè)整數(shù)域中保持著原有的關(guān)系，如果u中的存在冗余度，則被完整地傳遞到b中，容易被破譯者利用

17、。舉兩例：（1）如果u和m存在公因子g，從式（4-3-1）可知，g也是b的因子；（2）對(duì)于b1 wu1 (mod m )，如果b1n-j，d i= ei*2n-j+vi ，“”表示“遠(yuǎn)遠(yuǎn)大于”； (5) 選正整數(shù)t，滿足(ei +t*vi) ，q 運(yùn)用中國(guó)剩余定理，生成n項(xiàng)公鑰A = (a1，an)，即0 a i pq1，ai ui (mod p)，ai vi (mod q ), i =1，n 私鑰為：p，q，t，w-1，m 其中，w-1為w模m的逆。而超遞增初始序列B作為固定值嵌入算法中。5.2 加密二進(jìn)制明文x=(x1，xn )，xi為0或1，被加密為c=a1x1+ +an5.3 解密(1

18、) 計(jì)算 u = c (mod p) , v = c (mod q )(2) 計(jì)算 e = u - t*v(3) 計(jì)算 d = e*2n-j + v(4) 計(jì)算 y = w-1*d mod m (5) 運(yùn)用超遞增初始序列B計(jì)算得明文x5.4 安全性分析以上算法的第(3)和第(6)步為模乘運(yùn)算關(guān)系，屬混亂技術(shù)。第(4)步和第(5)步實(shí)施不對(duì)稱分組，將n比特位的di分為左、右二部分，左部長(zhǎng)度遠(yuǎn)大于右部，右部擴(kuò)展t倍后疊加到左部，使得超遞增初始序列bi各項(xiàng)之間及模乘因子w的微小變化在整個(gè)項(xiàng)分散開來，彌補(bǔ)當(dāng)bi和w低位變化時(shí)，模乘結(jié)果雪崩效應(yīng)不明顯的缺陷。不對(duì)稱分組及擴(kuò)展疊加技術(shù)為項(xiàng)內(nèi)擴(kuò)散技術(shù)。對(duì)于背

19、包公鑰密碼算法有兩種基本的攻擊：明文恢復(fù)攻擊和密鑰恢復(fù)攻擊。前者指從密文出發(fā)來求解明文，后者是指從公鑰出發(fā)尋找密鑰，現(xiàn)討論這兩種攻擊。5.4.1 明文恢復(fù)攻擊如上所述，背包密度只有處在0.9408和1之間背包公鑰算法才是安全的。以n=512為例，說明本算法構(gòu)造的背包密度可以大于0.9408。(1) 選初始序列 B = (b1，bi，b512)(2) 選互素的w和m，m須大于B中所有項(xiàng)的和，由于初始序列B的超遞增性質(zhì)，m最小可選513比特位與w互素的正整數(shù)。(3) 運(yùn)用w和m，對(duì)B序列進(jìn)行模乘運(yùn)算，轉(zhuǎn)換為D序列 di w bi (mod m ) i =1，512 由于m的位數(shù)是513比特，因此，

20、di的位數(shù)不大于513比特。(4) 將513比特位的di進(jìn)行不對(duì)稱分組：在第352比特的位置分為左、右二部分，形成ei和vi，長(zhǎng)度分別為352比特和161比特，d i= ei*2161+ vi (5) 選正整數(shù)t，滿足ei +t*vi ，q 運(yùn)用中國(guó)剩余定理，生成512項(xiàng)公鑰A = (a1，a512)，即0a ipq1，ai ui (mod p)，ai vi (mod q ), i =1，512下面考察p和q的位數(shù)：512個(gè)ui相加，最多擴(kuò)展log2512=9比特。因此，p可以取361比特位的素?cái)?shù)。同理，q可以取170比特位的素?cái)?shù)。由此，公鑰A的項(xiàng)應(yīng)該為361+170=531比特。背包密度D=

21、512/531=0.9642，處在0.9408和1之間。5.4.2 密鑰恢復(fù)攻擊本算法的初始序列B是固定的，可以公開的，因此，對(duì)安全性的要求類似于要求一個(gè)對(duì)稱密碼能夠抵御“已知明文攻擊”。首先，本算法運(yùn)用不對(duì)稱分組方法，將序列D分成序列U和V，各序列中的項(xiàng)存在以下關(guān)系：di= (ui-t vi)*2n-i+ vi 。其中，t可以是100比特以上的整數(shù)，由于t的存在，破譯者無法運(yùn)用解多重MH背包的方法10，11破譯本算法。其次，即使攻擊者從公鑰出發(fā)逆向破譯得到了U和V序列，必須猜測(cè)t獲得D序列后，再進(jìn)行格攻擊5或Shamir攻擊法8繼續(xù)破譯。5.4.1節(jié)已經(jīng)闡明，對(duì)于512項(xiàng)的背包算法，ui和v

22、i的長(zhǎng)度可以相差191比特，t可以是100比特位以上的正整數(shù)，要猜測(cè)攻擊100比特以上的正整數(shù)是不可計(jì)算的。由此，t的存在，使得破譯者難以獲得D序列，無法從公鑰出發(fā)利用初始序列及冗余度。再則，如果破譯者從初始序列B出發(fā)，也不能以此恢復(fù)私鑰，證明如下：第（3）步運(yùn)用模乘因子w對(duì)序列B= (b1，bn)進(jìn)行模乘運(yùn)算，將B序列轉(zhuǎn)換序列D：di wbi (mod m) （5-4-2）D = (d1，dn) i =1，n由（5-4-2）式，可得：bi w-1di (mod m) i =1，n 上式可以認(rèn)為是一個(gè)MH背包關(guān)系：D作為初始序列，B作為公鑰序列，w-1作為模乘因子。但破譯者不知道序列D的信息，

23、對(duì)于破譯者來說，序列D的冗余度是零，無論是運(yùn)用格攻擊法5還是Shamir破譯法8，都不能恢復(fù)私鑰w和m 。5.5 舉例說明取超遞增序列為：b1=58037，b2=29018，b3=14510，b4=7253，b5=3627，b6=1813，b7=907，b8=453，b9=227，b10=113，b11=57，b12=28，b13=15，b14=7，b15=3，b16=2取模m=965613=(11101101110000001001 )2w=724210，w 模m的逆w-1=4計(jì)算得：d1=738719=(10110100010110011111 )2 d2=490061=(01110111

24、101001001101)2d3=486434=(01110110110000100010)2d4=726023=(10110001010000000111)2d5=242310=(00111011001010000110)2d6=724663=(10110000111010110111)2d7=241630=(00111010111111011110)2d8=724323=(10110000110101100011)2d9=241460=(00111010111100110100)2d10=724238=(10110000110100001110)2d11=724224=(101100001

25、10100000000)2d12=7=(00000000000000000111)2d13=241407=(00111010111011111111)2d14=241405=(00111010111011111101)2d15=241404=(00111010111011111100)2d16=482807=(01110101110111110111)2在第13比特位與第14比特位間（從左到右）分割di，形成ei和vi ，取t=3，得：u1=e1+t*v1=(1011011101000)2=5864 v1=(0011111)2=31u2=e2+t*v2=(0111111011011)2=405

26、9 v2=(1001101)2=77u3=e3+t*v3=(0111100111110)2=3902 v3=(0100010)2=34u4=e4+t*v4=(1011000111101)2=5693 v4=(0000111)2=7u5=e5+t*v5=(0011101110111)2=1911 v5=(0000110)2=6u6=e6+t*v6=(1011011000010)2=5826 v6=(0110111)2=55u7=e7+t*v7=(0100001111001)2=2169 v7=(1011110)2=94u8=e8+t*v8=(1011101000011)2=5955 v8=(11

27、00011)2=99u9=e9+t*v9=(0011111111010)2=2042 v9=(0110100)2=52u10=e10+t*v10=(1011001000100)2=5700 v10=(0001110)2=14u11=e11+t*v11=(1011000011010)2=5658 v11=(0000000)2=0u12=e12+t*v12=(0000000010101)2=21 v12=(0000111)2=7u13=e13+t*v13=(0100011011010)2=2266 v13=(1111111)2=127u14=e14+t*v14=(0100011010100)2=2

28、260 v14=(1111101)2=125u15=e15+t*v15=(0100011010001)2=2257 v15=(1111100)2=124u16=e16+t*v16=(1000000100000)2=4128 v16=(1110111)2=119取p=59713，q=977運(yùn)用中國(guó)剩余定理計(jì)算公鑰，得：a1=43775493 a2=41206029 a3=28188438 a4=42342210a5=57863808 a6=40789805 a7=54758990 a8=39237396a9=56311401 a10=42342217 a11=50403430 a12=25139

29、194a13=44667590 a14=12482277 a15=25559421 a16=10513616設(shè)需加密的明文為x=1010100100100101計(jì)算得密文c= a1+ a3+ a5+ a8+ a11+ a14+ a16=242464458解密運(yùn)算：u=c mod p=242464458 mod 59713=29678v=c mod q=242464458 mod 977=414e=u-3*v=28436d=e*27+v=3640222b= w-1d mod m=4*3640222 mod 965613=76693解超遞增背包得：x=1010100100100101從例中可得出以

30、下結(jié)論：w應(yīng)盡可能接近m，以便使初始序列各項(xiàng)的細(xì)微變化引起模乘結(jié)果的較大變化，形成雪崩效應(yīng)；初始超遞增序列的各項(xiàng)盡量不要形成倍數(shù)關(guān)系，否則，倍數(shù)關(guān)系可能會(huì)傳遞到模乘運(yùn)算的結(jié)果中。6 小結(jié)在業(yè)內(nèi)普遍認(rèn)為背包公鑰算法已經(jīng)死亡的環(huán)境下，本文以一種稱為隨機(jī)的背包公鑰密碼為例，從新角度看待背包公鑰算法。本文認(rèn)為，背包公鑰序列是由初始序列變換來的，初始序列代表著易解背包，可以看作需加密的文本，變換可以看作加密過程，公鑰序列可以看作密文，因此背包公鑰序列不可能是完全隨機(jī)的，殘留著初始序列的冗余度。背包公鑰算法的安全性有兩個(gè)方面：首先是必須保證背包密度，以抵御低密度子集和攻擊；其次是把變換過程（相當(dāng)于加密過程

31、）設(shè)計(jì)牢固，使得攻擊者難以從公鑰序列出發(fā)利用初始序列及冗余度。目前大多數(shù)被破譯的背包公鑰算法只使用了模乘運(yùn)算，該運(yùn)算屬混亂技術(shù)，還不足以隱藏初始序列的冗余度，本文引入了加法分散技術(shù)，進(jìn)一步隱藏初始序列的冗余度，使攻擊者在破譯過程中難于利用該冗余度。分析表明，運(yùn)用了分散技術(shù)后，攻擊者無法利用初始序列的冗余度，目前已知的破譯方法不再奏效。參考文獻(xiàn)(References)：1 A. M. Odlyzko，The rise and fall of knapsack cryptosystems，Cryptology and Computational Number Theory，1990，vol 42，pp.75-882 Coster M J, Joux A, LaMacchia B A, et al. Improved low-density subset sum algorithmsJ. Computational Complexity, 1992, 2(2): 111-128. 3 王保倉，韋永壯，胡予濮. 基于隨機(jī)背包的公鑰密碼J. 電子與信息學(xué)報(bào)，2010，32(7)：1580-15844 LENSTRA A. K,，LENSTRA H.