有限域離散對數密碼系統的割圓多項式結構的製作方法

2023-04-29 04:11:51

專利名稱：有限域離散對數密碼系統的割圓多項式結構的製作方法
背景技術：
本發明涉及數據保密、加密，以及通過生成和使用數字籤名，來驗證通信方的身份。
大多數公開密鑰密碼系統包含因子分解問題或離散對數(DL)問題。因子分解問題是，給一個非素數，將其完全分解為素因數。DL問題是，給一個由g生成的群G，以及G中的一個元素h，求出使gm＝h成立的整數m，即求loggh的值。就公開密鑰密碼系統提出的幾種方案都依賴於在有限域的乘法群中求解DL的計算難度。公開密鑰密碼系統包括公開密鑰加密方案和數字籤名方案。假設每個用戶都有一個公開密鑰和一個私人密鑰(該假設不必對所有方案都成立)，並且假設A方希望向B方發送安全消息。在公開密鑰加密方案中，A方用B方的公開密鑰加密，然後B方用自己的公開和私人密鑰解密。在數字籤名方案中，A方用自己的公開和私人密鑰準備消息，而B方用A方的公開密鑰接收消息。也就是說，當準備消息時，在公開密鑰加密方案中，發送方使用接收方的密鑰信息，而在數字籤名方案中，發送方使用自已的密鑰信息。當接收消息時，在公開密鑰加密方案中，接收方使用自己的密鑰信息，而在數字籤名方案中，接收方使用發送方的密鑰信息。
一般的數字籤名方案包括三步系統設定、發送方生成籤名，以及接收方對籤名進行驗證。
假設，系統設定是在對消息籤名和加密之前完成的。一般來說，在對基於DL的公開密鑰密碼系統進行系統設定期間，首先選擇一素數，並用該素數獲得群的生成元，然後選擇一隨機數，將其用作生成元的指數，從而在有限域中產生一結果值。當僅已知生成元和結果值時確定所述隨機數是一個DL問題。
系統設定的結果是一公開密鑰和一私人密鑰。公開密鑰被假定為公知的，該密鑰包括參數、生成元、結果值和其它參數。私人密鑰被假定只有發送方已知，該密鑰包括隨機數。
在對基於DL的公開密鑰密碼系統進行籤名生成期間，選擇第二隨機數，並將其用作生成元的指數，從而在有限域中產生第二結果值。當僅已知生成元和第二結果值時確定第二隨機數是一個DL問題。然後，根據待籤名消息上的私人密鑰和第二結果值，獲得第三值。籤名生成的結果是一數字籤名，它包括第三值和至少另一個參數。
在對基於DL的公開密鑰密碼系統進行籤名驗證期間，對公開密鑰和籤名的第三值部分進行指數組合，產生第四結果值。如果第四結果值等於籤名的至少另一個參數，那麼認為籤名有效。
系統設定、籤名生成和籤名驗證的指數部分計算起來既費錢又費時。希望尋找到這樣的技術，它們在對未授權用戶保持計算難度的同時，又能減輕授權用戶的計算負擔，尤其能夠減輕籤名生成期間的計算負擔。

發明內容
依照本發明的一個方面，提供了一種用於為公開密鑰密碼系統確定公開和私人密鑰的方法和設備，所述方法包括以下步驟選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的所述割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；根據所述生成元和一所選的整數，求一公開值；形成公開密鑰，它包括第一和第二素數、所述生成元和所述公開值；形成私人密鑰，它包括所述所選的整數。
依照本發明的另一方面，可以用最優正規基表示有限域。
依照本發明的又一方面，第二素數q滿足(log2q)+1≈ B，其中B是預定的二進位位數。
依照本發明的再一方面，選擇一控制整數t』，並且割圓多項式是t』次割圓多項式，公開密鑰包括控制整數t』。
依照本發明的另一方面，一種用於為消息生成數字籤名的方法還附加包括以下步驟選擇第二整數；根據第二整數和生成元，求第一籤名值；根據第一籤名值和所述消息，求第二籤名值；以及形成數字籤名，使其包括第一和第二籤名值。
一種用於驗證上述對消息形成的數字籤名的方法，包括以下步驟求一逆整數，它是第二籤名值的逆；根據逆整數和所述消息，求第一中間值；根據逆整數和第一籤名值，求第二中間值；根據生成元、公開值以及第一和第二中間值，求第三中間值；當第三中間值等於第一籤名值時，判定所述籤名有效。
一種用於為公開密鑰密碼系統確定共享密鑰的方法，包括以下步驟選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；選擇一整數；接收一中間值，中間值基於生成元；形成共享密鑰，使其成為所述中間值和所述整數的函數。
一種用於消息保密通信的方法，包括以下步驟選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；選擇一整數；接收一中間值，所述中間值基於生成元；形成共享密鑰，使其成為所述中間值和所述整數的函數；用共享密鑰對消息加密。
一種用於消息保密通信的方法，包括以下步驟接收加密消息，加密消息是用共享密鑰加密的，共享密鑰是一中間值和一所選整數的函數，所述中間值基於一有限域中乘法群之子群的生成元，所述子群的階是第二素數，第二素數是由第一素數計算得到的割圓多項式的因子；用共享密鑰對加密消息解密。
一種用於消息保密通信的方法包括以下步驟選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；根據生成元和第一整數，求一公開值；選擇第二整數；根據生成元和第二整數，求第一加密值；根據消息、公開值和第二整數，求第二加密值；由第一和第二加密值形成加密消息。
一種用於消息保密通信的方法，包括以下步驟接收由第一加密值和第二加密值構成的加密消息，第一加密值基於第一整數和一有限域中乘法群之子群的生成元，所述子群的階是第二素數，第二素數是由第一素數計算得到的割圓多項式的因子，第二加密值基於消息、第一整數和基於生成元和第二整數的公開值；根據第一加密值和私人密鑰，求第一中間值，私人密鑰基於生成元；根據第二加密值和第一中間值對加密消息解密。
並不打算在這裡對本發明進行完整的概括。由以下描述和附圖可以了解本發明的其它特點、方面和長處。
附圖概述

圖1A是一流程圖，示出了依照ElGamal方案的系統設定過程；圖1B是一流程圖，示出了依照ElGamal方案的籤名生成過程；圖1C是一流程圖，示出了依照ElGamal方案的籤名驗證過程；圖2A是一流程圖，示出了依照Schnorr和DSA方案的系統設定過程；圖2B是一流程圖，示出了依照Schnorr方案的籤名生成過程；圖2C是一流程圖，示出了依照Schnorr方案的籤名驗證過程；圖2D是一流程圖，示出了依照DSA方案的籤名生成過程；圖2E是一流程圖，示出了依照DSA方案的籤名驗證過程；圖3A是一流程圖，示出了依照ECDSA方案的系統設定過程；圖3B是一流程圖，示出了依照ECDSA方案的籤名生成過程；圖3C是一流程圖，示出了依照ECDSA方案的籤名驗證過程；圖4A是一流程圖，示出了依照本發明的系統設定過程；圖4B是一流程圖，示出了依照本發明的籤名生成過程；圖4C是一流程圖，示出了依照本發明的籤名驗證過程；圖4D是一割圓多項式係數表；圖4E是一流程圖，示出了依照本發明的DES系統設定過程；圖4F是一流程圖，示出了依照本發明對DES系統設定進行加密的過程；圖4G是一流程圖，示出了依照本發明對DES系統設定進行解密的過程；圖4H是一流程圖，示出了依照本發明對ElGamal系統設定進行加密的過程；圖4J是一流程圖，示出了依照本發明對ElGamal系統設定進行解密的過程；圖5A是一表，示出了對公開密鑰密碼系統各方案的籤名生成性能進行比較的比較結果；圖5B是一表，示出了對公開密鑰密碼系統各方案的籤名驗證性能進行比較的比較結果；圖6示出了獲得圖5A和5B的性能結果的加密、解密的消息；圖7A-11D示出了用來獲得圖5A和圖5B性能結果的諸例中各公開密鑰密碼系統的公開密鑰、私人密鑰、籤名和籤名生成參數k；以及圖12是一方框圖，示出了實施本發明的環境。
較佳實施例的詳細描述割圓多項式用於構造有限域中乘法群的子群，可以非常有效地實現基於離散對數的公開密鑰密碼系統，包括公開密鑰加密方案和數字籤名方案。域可用最優正規基來表示，並且域中乘法群之子群的生成元可用來形成公開密鑰。根據應用和執行的類型，依照割圓方案進行公開密鑰加密可以比較傳統的子群或有限域選擇方案快兩倍。
已提議的數字籤名方案包括ElGamal方案、Schnorr方案、數字籤名算法(DSA)方案和橢圓曲線數字籤名算法(ECDSA)方案，其中T.ElGamal在1985年第31期IEEE Trans.Info.Tech中第469-472頁的上發表的論文「基於離散對數的公開密鑰密碼系統和籤名方案」對ElGamal方案作了敘述；C.P.Schnorr在1991年第4期J.Cryptology中第161-174頁上發表的論文「用智慧卡高效地生成籤名」對Schnorr方案作了敘述；申請日為1993年7月27日、發明名稱為「數字籤名算法」的美國專利第5,231,668號(發明人為Kravitz)對DSA方案作了敘述；而Agnew等人在1991年第三期J.Cryptology第63-79頁上發表的論文「實現快速公開密鑰密碼系統」對ECDSA方案作了敘述。DSA被納入美國政府的數字籤名標準中。以下將討論這些被提議的方案，並將它們與本發明在數字籤名方案中使用的割圓方案進行比較。術語m需要籤名的消息，由二進位位串組成p素數qp-1的素因子Lp的位長度，L實際上確定了DL的保密等級Bq的位長度，B實際上確定了子群DL的保密等級F(p) 由p個元素組成的域，用由模p最小剩餘組成的集合{0，1，…，p-1}表示F(p)*F(p)的乘法群＝F(p)-0H(*)抗衝突密碼散列函數，它可以將二進位位串映射為至多具有預定二進位位數的非負整數ElGamal系統設定圖1A示出了在依照ElGamal方案設定電子籤名系統期間，每個用戶要執行的步驟。該過程可以用通用數字計算機中的處理器來完成。另一種方式是，將專用印刷電路板與通用計算機相結合，或者用「智慧卡」(即信用卡大小的、包含微處理器的可攜式裝置)來完成該過程。
在步驟102，選擇具有L-1位的素數q。
在步驟104，計算p＝2q+1的值。
在步驟106，進行測試，以便確定p是否為素數。因為q有L-1位，所以p有L位。
如果p不是素數，那麼過程返回步驟102，並選擇另一個素數。
如果p是素數，那麼過程進至步驟108，並從由p個元素組成的域F(p)的乘法群F(p)*中隨機選擇一個元素g。
在步驟110，進行測試，以便確定是否在F(p)中g2≠1以及gq≠1。如果這些測試中有一個失敗，那麼過程返回步驟108，並從F(p)*中選擇另一個元素，作為元素g。
如果在F(p)中g2≠1並且gq≠1，那么元素g是域F(p)之乘法群F(p)*的生成元。不用步驟102-110中所述的過程，還可以用其它過程來確定域F(p)和生成元g。
在確定生成元g後，過程進至步驟112，並且在範圍2≤a≤p-2內隨機選擇a值。
在步驟114，過程在F(p)中求出y＝ga。
系統設定的結果是公開密鑰(p，g，y)和私人密鑰(a)。公開密鑰的長度為3L位。私人密鑰的長度為L位。
由公開密鑰(p，g，y)求私人密鑰(a)是域F(p)中的離散對數(DL)問題，如果p足夠大，則求解是很難的。目前，當p的長度為L位(L＝1024)，並且p-1的素因子至少有160位時，會呈現相宜的難度。當計算能力變強時，這些參數將增大，以便對未授權用戶保持計算難度。ElGamal籤名生成圖1B示出了依照ElGamal方案為一特定文件生成電子籤名的一方所執行的步驟。將文件視作二進位位串m。實際上，生成方是通用數字計算機的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟122，在2≤k≤p-2範圍內隨機選擇一個整數k，k和p-1的最大公約數(GCD)為1，即選擇k，使其與p-1都為素數。
在步驟124，求k-1mod p-1，即求出滿足(k)(k-1)＝1 mod p-1的值。
在步驟126，在F(p)中獲得r＝gk，其中r在1≤r≤p-1範圍內。
在步驟128，計算s＝k-1(H(m)-ar)mod p-1，其中s在2≤s≤p-2範圍內。H(*)是由系統所有用戶同意的密碼散列函數。例如，合適的標準密碼散列函數是1995年4月17日FIPS 180-1中規定的安全散列算法SHA-1，該算法可以從Virginia州Springfield市的國家技術信息服務機構獲得。
籤名生成的結果是數字籤名(r，s)。籤名的長度為2L位。
只有私人密鑰(a)的擁有者可以正確地對消息籤名。私人密鑰(a)的秘密再次受到DL問題的保護如果通過在F(p)中計算離散對數loggr可以由r求得k，那麼就可以計算出k-1，由此可以從s，m和k-1導出私人密鑰(a)。因此，使k的特定值保持專用且不重複使用是很重要的。ElGamal籤名驗證圖1C示出了依照E1Gamal方案接收已被電子籤名的文件的一方所執行的步驟，這些步驟用以確定籤名是否有效。
假設接收方具有消息(m)、如圖1B中獲得的相應數字籤名(r，s)，以及如圖1A中獲得的且曾經用來獲得籤名(r，s)的公開密鑰(p，g，y)。實際上，接收方是通用數字計算機中的處理器。在一些實施例中，處理器可以在專用數字計算機中，諸如智慧卡。
在步驟134，過程確定r值是否在1≤r≤p-1範圍內。如果不在該範圍內，那麼在步驟142，判定該籤名無效。
如果r在適當的範圍內，那麼在步驟136，在F(p)內計算v1＝yrrs。接著，在步驟138，在F(p)中計算v2＝gH(m)。
在步驟140，進行測試，以便確定是否v1＝v2。如果不成立，那麼在步驟142，判定籤名無效。如果成立，那麼在步驟144，判定籤名有效。Sehnorr/DSA系統設定圖2A示出了在依照Schnorr方案設定電子籤名系統期間，每個用戶必須執行的步驟。
Schnorr方案旨在使用大指數素域之乘法群的小子群，以便因使用較短的指數而使籤名較短，求冪較快。如果子群階是素數，並且足夠大，那麼使用子群不會影響方案的保密性。
除了如下所述具體規定了某些參數(B和L)的長度值外，DSA方案的系統設定與Schnorr方案的系統設定相同。
在步驟202，選擇長度為B位的素數q。在DSA方案中，規定B為160。
在步驟204，隨機選擇一整數k。k的長度最好為750-864位，以便提供足夠的保密性，來抵禦未授權的用戶，但當處理能力增強時，長度也將增加。
在步驟206，計算p＝kq+1，其長度為L位。在DSA方案中，L規定為512+i*64，其中0≤i≤8，且i為整數。
在步驟208，進行測試，以便確定p是否為素數。
如果p不是素數，那麼過程返回步驟204，並選擇另一個整數k。
如果p是素數，那麼過程進至步驟210，並且從F(p)*中隨機選擇一個元素h。
在步驟212，在F(p)中求g＝h(p-1)/q。
在步驟214，進行測試，以便確定是否在F(p)中g≠1。如果測試失敗，即g＝1，那麼過程返回步驟210，並從F(p)*中選擇另一個元素作為值h。
如果在F(p)中g≠1，那麼就為大指數素域F(p)中乘法群的小子群G確定了生成元g。生成元g的階為q，因為在F(p)中g≠1，所以gq＝1。不用步驟202-214中所述的過程，還可以用其它過程來確定生成元g。
在確定生成元g之後後，過程進至步驟216，並且在範圍2≤a≤q-1內隨機選擇a值。該範圍應該比圖1A中關於ElGamal方案的步驟112的相應範圍小。
在步驟218，過程在F(p)中求出y＝ga。如上所述，給出y和g求a值是一個離散對數(DL)問題。
系統設定的結果是一個公開密鑰(p，g，y，q)和一個私人密鑰(a)。公開密鑰的長度為3L+B位。私人密鑰的長度為B位。
為了由公開密鑰(p，g，y，q)求出私人密鑰(a)，必須在域F(p)中求DL問題的解，或者在用g生成的F(p)*的子群G中求DL問題的解。
目前認為在下述域F(p)中解DL問題是不可能的，即該域F(p)具有基數p，p是長度為L位的素數，而q是p-1的素因子，長度至少為B位。
目前認為在F(p)*的下述子群G中解DL問題是不可能的，即該子群G的階為q，q的長度至少為B位。Schnorr籤名生成圖2B示出了依照Schnorr方案為一特定文件生成電子籤名的一方所執行的步驟。實際上，生成方是通用數字計算機中的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟224，在2≤k≤q-1範圍內隨機選擇一整數k。圖1B中ElGamal方案的相應步驟(步驟122)對k的範圍取上限p-2。由於p＞＞q，所以與依照ElGamal的公開密鑰密碼系統相比，依照Schnorr的公開密鑰密碼系統具有較少的元素。例如，當q的長度為160位時，p的長度大約為1024位。
在步驟226，在F(p)中求出r＝gk，其中r在1≤r≤p-1範圍內。由於p＞＞q，所以步驟226的計算要比圖1B步驟126中的相應計算(即，依照ElGamal的公開密鑰密碼系統)快得多。
在步驟228，求出e＝H(m‖r)，這是將散列函數作用於消息m與籤名元素r的並置。假設密碼散列函數H(*)可以產生長度至多為B位的值。
在步驟230，計算s＝(ae+k)mod q，其中s在0≤s≤q-1範圍內。
籤名生成的結果是數字籤名(s，e)。籤名的長度為2B位。Schnorr籤名驗證圖2C示出了依照Schnorr方案接收已被電子籤名的文件的一方所執行的步驟，這些步驟用以確定籤名是否有效。
假設接收方具有消息(m)、如圖2B中獲得的相應數字籤名(s，e)，以及如圖2A中獲得的且曾用來獲得籤名(r，s)的公開密鑰(p，g，y，q)。實際上，接收方是通用數字計算機的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟236，在F(p)中計算v＝gsy-e。接著，在步驟238，計算e』＝H(m‖v)。
在步驟240，進行測試，以便確定是否e＝e』。如果不相等，那麼在步驟242，判定籤名無效。如果相等，則在步驟244，判定籤名有效。DSA籤名生成圖2D示出了依照DSA方案為一特定文件生成電子籤名的一方所執行的步驟。實際上，生成方是通用數字計算機的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟324，在2≤k≤q-1範圍內隨機選擇一整數k。
在步驟326，求k-1mod q，即求滿足(k)(k-1)＝1 mod q的值。
在步驟328，在F(p)*的子群G(由g生成)中求u＝gk，其中u在1≤u≤p-1範圍內。
在步驟330，計算r＝u mod q。
在步驟332，計算s＝k-1(H(m)+ar)mod q，其中s在0≤s≤q-1範圍內。
在步驟333，進行測試，以便確定是否s＝0。如果成立，則過程返回步驟324，為整數k選擇一個新的值。如果s≠0，則過程進至步驟334，並結束。
籤名生成的結果是數字籤名(r，s)。籤名的長度為2B位。DSA籤名驗證圖2E示出了依照DSA方案接收已被電子籤名的文件的一方所執行的步驟，這些步驟用以判斷籤名是否有效。
假設接收方具有消息(m)、如圖2D中獲得的相應數字籤名(r，s)，以及如圖2A中獲得的且曾用來生成籤名(r，s)的公開密鑰(p，g，y，q)。實際上，接收方是通用數字計算機的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟338，過程判斷r值是否為1≤r≤q-1範圍內的整數。如果不是，則在步驟352，判定籤名無效。
如果r在合適的範圍內，則在步驟340，過程判斷值s是否為1≤s≤q-1範圍內的整數。如果不是，則在步驟352，判定籤名無效。
如果s在合適的範圍內，則在步驟342，求整數w，w是s的逆，即求ws＝1 mod q。
在步驟344，計算u1＝wH(m)mod q，並且計算u2＝wr mod q。在步驟346，在F(p)*的子群G(由g生成)中求得c＝gu1yu2，其中c在1≤c≤p-1的範圍內。
在步驟348，計算v＝c mod q。
在步驟350，進行測試，判斷是否v＝r。如果不是，則在步驟352，判定籤名無效。如果是，則在步驟354，判定籤名有效。
ECDSA系統設定圖3A示出了依照ECDSA方案在設定電子籤名系統期間必須執行的步驟。步驟402-416是全局執行的，即針對所有用戶的，因此只需要執行一次。而步驟420-424，則每個用戶都要執行。
ECDSA系統旨在利用對兩個元素組成的域的擴充。藉助擴充域的最優正規基表示(參見，R.C.Mullin等人在《離散應用數學》1988/89年第22期149-11上發表的論文「GF(p)中的最優正規基」)，乘法運算非常快，並可以通過圓弧移動作平方運算，從而高效地完成求冪運算。但是，需要硬體設備。另外，由兩個特徵組成的域被認為比其它相當大小的域更易受到攻擊。
在步驟402，選擇一整數t≥160，其中t∈F(2t)，即t在160≤t≤250範圍內。ECDSA方案使用由2t個元素組成的全系統有限域F(2t)，其中假設t＝B。
在步驟404，就曲線E＝Y2+XY＝X3+αX2+β選擇係數α，β∈F(2t)。ECDSA方案假設在F(2t)的一個子域上用最優正規基表示F(2t)的元素。使用曲線E就意味著使用該最優正規基。
在步驟406，計算μ。μ值是1加上滿足E的差異對(x，y)的個數，其中x，y∈F(2t)。也就是說，E的群具有μ階。另一種說法是，μ是曲線群的基數。
在步驟408，求出μ的因子。
在步驟410，進行測試，以便確定μ是否存在至少有140位的素因子。如果沒有，則過程返回步驟404，並挑選一個新的橢圓曲線E。
如果μ存在至少有140位的素因子，那麼在步驟412，將q設置為該素因子。應該理解，q是橢圓曲線E之群階的素因子。最好，q的長度至少為140位。
在步驟414，在曲線E上選擇一點h(即h(x0，y0))，使得(μ/q)h≠I，其中I是曲線E上的單位元素。符號表示對曲線E作純量乘法。E群的階為μ，並且用q除μ。
在步驟416，將曲線E上的點g選擇為曲線E上的g＝(μ/q)h。曲線E上點g的階為q。曲線E上的點g生成群G，它是曲線群的子群。
步驟402-416的結果為全局公開密鑰(α，β，t，q，g)。眾所周知，全局公開密鑰的長度並不重要，因為該長度大家都知道，並且不由各個加密方或解密方變動。
對於每個用戶，在步驟420，在2≤a≤q-1範圍內隨機選擇a值。
在步驟422，在曲線E上隨機選擇一點P(即，P(x1，y1))，使得在曲線E上，P＝ag。
步驟420-422的結果是長度為B+1位的用戶專用公開密鑰(P)和長度至多為B位的私人密鑰(a)。儘管在ECDSA方案中密鑰較小，但該方案計算費用很高。
為了由用戶專用公開密鑰(P)求出私人密鑰(a)，必須在與曲線E相關的群中解DL問題，或者在與曲線E相關的群的子群G中解DL問題。
目前認為，用橢圓曲線密碼系統的支持器在基數為2t(t≥160)的域上解曲線群的DL問題是不可能的。
目前認為，用橢圓曲線密碼系統的支持器解曲線群中階數為q(q至少有140位)的子群G的DL問題是不可能的。ECDSA籤名生成圖3B示出了依照ECDSA方案為一特定文件生成電子籤名的一方所執行的步驟。實際上，生成方是通用數字計算機的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟428，在2≤k≤q-2範圍內隨機選擇一整數k。
在步驟430，求得k-1mod q，即求出滿足(k)(k-1)＝1 mod q的值。
在步驟432，曲線E上找出點u，即u(x2，y2)，使得在曲線E上u＝kg。
在步驟434，求得整數r＝x(x2)mod q，其中r在0≤r≤q-1的範圍內。函數x(*)是有限域F(2t)和整數集合{0，1，…，2t-1}之間一固定且可有效計算的雙射。系統的所用用戶都知道該雙射。
在步驟435，進行測試，以便確定是否r＝0。如果成立，則過程返回步驟428，為整數k選擇一新的值。如果r≠0，那麼過程進至步驟436。
在步驟436，計算s＝k-1(H(m)+ar)mod q，其中s在0≤s≤q-1範圍內。
在步驟437，進行測試，以便確定是否s＝0。如果成立，則過程返回步驟428，為整數k選擇一新的值。如果s≠0，那麼過程進至步驟438，並結束。
籤名生成的結果是數字籤名(r，s)。籤名的長度至多為2B位。ESDSA籤名驗證圖3C示出了依照ECDSA方案接收已被電子籤名的文件的一方所執行的步驟，這些步驟用以確定籤名是否有效。
假設接收方具有消息(m)、如圖3B中獲得的相應數字籤名(r，s)，以及如圖3A中獲得的且曾用來獲得籤名(r，s)的公開密鑰，該公開密鑰包括(α，β，t，q，g)和(P)。實際上，接收方是通用數字計算機的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟442，過程判斷r值是否為1≤r≤q-1範圍內的一個整數。如果不是，則在步驟456，判定籤名無效。
如果r在合適範圍內，那麼在步驟444，過程判斷s值是否為1≤s≤q-1範圍內的一個整數。如果不是，那麼在步驟456，判定籤名無效。
如果s在合適範圍內，那麼在步驟446，求整數w，w是s的逆，即求ws＝1 mod q。
在步驟448，計算u1＝wH(m)mod q，並且計算u2＝wr mod q。在步驟450，在曲線E上求點c，即曲線E上的c(x3，y3)＝(ulg)(u2P)。符號表示對曲線E作加法。
在步驟452，計算v＝x(x3)mod q，其中v在0≤v≤q-1範圍內。
在步驟454，進行測試，以便確定是否v＝r。如果不成立，則在步驟456，判定籤名無效。如果成立，則在步驟458，判定籤名有效。割圓系統設定圖4A示出了依照本發明割圓方案在設定電子籤名系統期間每個用戶必須執行的步驟。圖4A所示過程的目的是，找出有限域F(pt』)之乘法群F(pt』)*的子群的生成元g，以便g能夠同時滿足所需的離散對數保密等級(它決定L的選擇)和所需的子群離散對數保密等級(它決定B的選擇)，並且在F(p)上有關於F(pt』)的最優正規基。
與Schnorr方案一樣，割圓方案使用子群，並且如ECDSA方案，還使用最優正規基。使用子群導致籤名短和指數短。使用最優正規基導致求冪高效。因此，割圓方案的軟體執行比Schnorr方案的軟體執行快得多。
令R的大小與基數相當。R的值是依賴於機器的，並且可以將其選擇成對快速進行模p計算足夠小，而對快速進行運算求冪又足夠大。較大的p值會產生較小的t』值，並且由於域F(pt』)中的每次乘法運算都需要計算(t』)2，所以希望t』具有較小的值。另外，較大的P值會擴大可構造的密碼系統的選擇範圍。對於目前可採用的32位結構的通用計算機，R＝32是合適的值。對於較新的64位結構，R＝64是合適的值。在其它實施例中，R可以取其它合適的值，不必等於實施本發明技術的計算機字長度(單位為位)。
在步驟502，選擇控制整數t』以及整數t，s，使得(i)s至多為R，並且s不比R小很多，例如，0.8R≤s≤R。較大的s會產生較高的效率。整數s用來限制素數p的大小(參見下文)。例如，25≤s≤32；(ii)t』＞1，最好t』具有因子t＞1，其中t+1為素數，並且t』/t較小，例如t』/t＜5。控制整數t』的使用允許對素數p的位數有較大的選擇範圍，因為它與L中反映的所需離散對數保密等級相關。具體地說，素數p的值依賴於R值，如上所述，R值是依賴於機器的。控制整數t』大致等於L除以素數p的位數。如上所述，t+1必須為素數。在理想情況下，t』＝t。但是可以用t』+1不為素數的t值，只要t』具有因子t＞1，其中t+1為素數，並且t』/t較小。也就是說，同時使用t和t』可以提供較大的靈活性。
(iii)t』*s接近於L；(iv)φ(t』)*s至少為B，但不能比B大得太多，以便很容易求出素因子q(參見步驟510)，也就是說，φ(t』)*s≈B。函數φ(t)是Euler的φ函數，即與t互素的正整數的數目≤t。
在步驟504，選擇一奇素數p，使得(log2P)+1＝s，並且t』*((log2p)+1)≥L。
在步驟506，進行測試，以便確定p是否為F(t+1)*中的本原根mod t+1，即，是否p mod t+1生成F(t+1)*。具體地說，通過對每個整數i(1≤i≤t)計算pimodt+1，並且檢查是否獲得不同數字，來進行該測試。如果不成立，則過程返回步驟504，以便選擇另一個素數p。
如果p是本原根mod t+1，那麼在步驟508，在p處求出第t』個割圓多項式Φt』(p)。
Z[X]中Xt-1的不可約因子分解為Xt-1＝∏d|tΦd(p)其中Φd(p)是第d個割圓多項式，H.Riesel在1985年Birkhouser公司出版的《素數和因子分解計算機方法》中對此作了敘述，該書按參考文獻在此引入。因子Φt(X)是Xt-1中唯一沒有出現在Xs-1之因子分解中的不可約因子，其中s是t的因子，並且s＜t。
求解Φt(X)的一種方法是使用上述因子分解單位。求解Φt(X)的另一種方法是在割圓多項式係數表(諸如圖4D中的表)中查找Φt(X)＝ct-1Xt-1+ct-2Xt-2+…+c1X+c0中的係數ci，0≤i≤t-1。利用圖4D中的表，可以看出，例如Φ18(X)＝X6-X3+1，以及Φ54(X)＝X18-X9+1。
在步驟510，求Φt』(p)中較大的素因子q。由於割圓方案中所用的且如下所述構造的子群具有q階，並且q是Φt』(p)的因子，所以相應的DL計算對於未授權者是很難的。
在步驟512，進行測試，以便確定是否(log2q)+1≥B。該條件確保可以構造足夠大的F(pt』)之乘法群F(pt』)*的子群，該子群不能包含在F(pt』)的真子域中。換句話說，為了解DL問題，即給出y和g，求a值，必須在整個域F(pt』)中解DL問題，或者在由g生成的子群中解DL問題；但是，不可以將DL問題簡化為在F(pt』)的一個真子域中解DL問題，由此對於未授權方不會降低計算難度。
另外，將步驟502中的條件φ(t』)*s≈B與步驟512的條件(log2q)+1≥B合併，得到(log2q)+1≈B的情況。
本發明的一個重要方面是，q是Φt』(p)的因子，並且(log2q)+1≥B。如果(log2q)+1＜B，那麼過程返回步驟504，以便選擇另一個素數p。
如果(log2q)+1≥B，那麼在步驟514，在整個F(pt』/t)上求最優正規基αi，i＝{1，2，…t}，其中每個αi是f1(X)＝(Xt+1-1)/(X-1)＝Xt+X-1+…+X+1的零點。
情況1如果t存在，並且t』＝t，那麼F(pt』/t)可用整數mod p表示，並且F(pt』)中的p次方不需要在F(pt』)中進行任何運算，p次方僅僅是對基元素αi的排列，因此計算費用不大。因此，在F(pt』)中，可以非常高效地進行乘法和平方運算。
情況2如果t存在，但t』≠t，那麼可以用F(p)上合適的基來表示F(pt』/t)的元素。在該情況下，p次方只需要在F(pt』)中進行非常少量的運算，並且可以高效地在F(pt』)中進行乘法和平方運算。如果t』/t很小，那麼情況1和情況2之間實現密碼系統時在F(pt』)中運算的效率差是可以忽略的。
情況3如果t不存在，那麼可以用任何方便的方式來表示F(pt』)，最好用稀疏最小多項式，來加快F(pt』)中的乘法和平方運算。
在步驟516，隨機選擇F(pt』)的元素b。
在步驟518，在F(pt』)中求g=b(pt-1q)]]>由於用最優正規基表示F(pt』)，所以計算g是非常高效的。
在步驟520，進行測試，以便確定是否在F(pt』)中g≠1。如果不成立，即g＝1，那麼過程返回步驟516，以便選擇另一個元素b。
如果g≠1，那麼g是有限域F(pt』)中乘法群F(pt』)*之子群G的生成元。子群G有q階。在步驟522，在2≤a≤q-2範圍內隨機選擇a值。
在步驟524，在F(pt』)中計算y＝ga。給定y和g求解a值是一個DL問題。
系統設定的結果是一個公共密鑰(p，g，y，q，t』)和一個私人密鑰(a)。參數g和y用最優正規基表示。公共密鑰的長度為2L+B+64位。私人密鑰的長度為B位。
與Schnorr方案一樣，保密性得到保證，而且由於子群G具有q階，q是長度至少為B位的、在p處求得的t』次割圓多項式的素因子，所以G實際上不能包含在F(pt』)的真子域中。
如上所述，在割圓方案中，計算p次冪是非常容易的，因為它只對最優正規基的諸元素進行重新排列。這是割圓方案在計算方面的突出優勢。
割圓方案中的計算涉及長度為(log2p)位的短行，它適合用軟體執行，而ECDSA方案涉及長度為1位的長行，更適合用硬體執行。也就是說，割圓基本域F(p)具有長度為(log2P)位的元素，而ECDSA基本域F(2)具有長度為1位的元素。割圓籤名生成圖4B示出了依照割圓方案為一特定文件生成電子籤名的一方所執行的步驟。實際上，生成方是通用數字計算機中的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟530，在範圍2≤k≤q-2內隨機選擇一個整數k。
在步驟532，求k-1mod q，即求出滿足(k)(k-1)＝1 mod q的值。
在步驟534，在F(pt』)中求u＝gk。
在步驟536，求整數r＝x(u)mod q，其中r在0≤r≤q-1的範圍內。函數x(*)是有限域F(pt』)和整數集合{0，1，…，pt』-1}之間一固定且可有效計算的雙射。系統的所用用戶都知道該雙射。這與ECDSA方案中圖3B步驟434中所用的雙射不同。
在步驟537，進行測試，以便確定是否r＝0。如果成立，則過程返回步驟530，為整數k選擇一新的值。如果r≠0，那麼過程進至步驟538。
在步驟538，計算s＝k-1(H(m)+ar)mod q，其中s在0≤s≤q-1範圍內。
在步驟539，進行測試，以便確定是否s＝0。如果成立，則過程返回步驟530，為整數k選擇一新的值。如果s≠0，那麼過程進至步驟540，並結束。
籤名生成的結果是數字籤名(r，s)。籤名的長度為2B位。割圓籤名驗證圖4C示出了依照割圓方案接收已被電子籤名的文件的一方所執行的步驟，這些步驟用以確定籤名是否有效。
假設接收方具有消息(m)、如圖4B中獲得的相應數字籤名(r，s)，以及如圖4A中獲得的且曾用來生成籤名(r，s)的公開密鑰(p，g，y，q，t』)。實際上，接收方是通用數字計算機中的處理器。在一些實施例中，處理器可以位於專用數字計算機中，諸如智慧卡。
在步驟544，過程判斷r值是否為1≤r≤q-1範圍內的一個整數。如果不是，則在步驟558，判定籤名無效。
如果r在合適範圍內，那麼在步驟546，過程判斷s值是否為1≤s≤q-1範圍內的一個整數。如果不是，那麼在步驟558，判定籤名無效。
如果s在合適範圍內，那麼在步驟548，求整數w，w是s的逆，即求ws＝1 mod q。
在步驟550，計算u1＝wH(m)mod q，並且計算u2＝wr mod q。在步驟552，在F(pt』)中，計算v』＝gu1yu2。在步驟554，求v』＝x(v』)mod q。
在步驟556，進行測試，以便確定是否v＝r。如果不成立，則在步驟558，判定籤名無效。如果成立，則在步驟560，判定籤名有效。割圓的其它方式如上所述。割圓方案的適用性不局限於電子籤名系統。割圓方案可以用於保密性依賴於DL問題難度的任何公開密鑰密碼系統，例如，Diffie-Hellman密鑰交換方案、Elgamal公開密鑰加密方案，或者與ElGamal、Schnorr和DSA方案中一樣的數字籤名生成和驗證方案。
已提出的公開密鑰加密方案包括數據加密標準(DES)以及ElGamal方案。1993年FIPS 46-2中敘述了數據加密標準，讀者可以從Verginia州Springfield市的國家技術信息服務機構獲得。T.ElGamal在1985年IEEE Trans.Info.Tech.第31期第469-472頁的論文「基於離散對數的公開密鑰密碼系統和籤名方案」中敘述了ElGamal方案。以下討論將割圓方案應用於這些已提出方案。
假設實施下述技術的用戶具有通用數字計算機，該計算機經編程實施這些技術。另一種方法是，將專用印刷電路板與通用計算機結合，或者用「智慧卡」(即，信用卡大小的、包括微處理器的便攜裝置)實施這些技術。
圖4E是一流程圖，示出了依照本發明的DES系統設定過程。具體地說，圖4E示出了通過應用割圓方案而改進的Diffie-Hellman密鑰交換方案。
在步驟600，假設所有用戶擁有全局共享的公開密鑰(p，g，q，t』)，它們是依照圖4A的步驟500-520獲得的。相反，在上述ElGamal、Schnorr、DSA和割圓數字籤名方案中，每個用戶與一個公開密鑰和一個私人密鑰相關；即沒有全局共享的公開密鑰。
當Δ和Θ兩方希望通信時，它們必須在最初交換信息，以便建立一共享密鑰。如圖4E所示，在步驟602，Δ方在2≤aΔ≤q-2範圍內隨機選擇aΔ值，並在步驟604，在F(pt』)中求y=g]]>在步驟607，Δ方將yΔ發送給Θ方。在步驟608，Δ方接收來自Θ方的yΘ。在步驟610，Δ方在F(pt』)中計算y0=x(y)]]>函數x(*)是有限域F(pt』)和整數集合{0，1，…，pt』-1}之間的固定且可有效計算的雙射，該函數曾在圖4B的步驟536中使用過。儘管應用函數x(*)非絕對必要，但最好能夠使用，以便將用有限域之最優正規基表示的元素轉換成普通整數。
同樣，在步驟603，Θ方在2≤aΘ≤q-2範圍內隨機選擇aΘ值，並在步驟605，在F(pt』)中求y=g]]>在步驟606，Θ方將yΘ發送給Δ方。在步驟609，Θ方接收來自Δ方的yΔ。在步驟611，Θ方在F(pt』)中計算y0=x(y)]]>
在步驟612，Δ方和Θ方已建立了一個共享密鑰(y0)。計算在由g生成的子群中進行。應該理解，未授權方只有解出DL問題，才能對Δ和Θ雙方之間的通信解密。
圖4F是一流程圖，示出了依照本發明對DES系統設定進行加密的過程。最重要的是在步驟622，Δ和Θ中的一方用它們的共享密鑰(y0)對消息加密。
圖4G是一流程圖，示出了依照本發明對DES系統設定進行解密的過程。最重要的是在步驟632，Δ和Θ中的另一方用它們的共享密鑰(y0)對在步驟622中加密的消息解密。
對於ElGamal公開密鑰加密方案(它不同於上述ElGamal數字籤名方案)，假設已執行了圖4A所示的步驟500-526，每位用戶都獲得了一個公開密鑰(p，g，y，q，t』)和一個私人密鑰(a)。應該理解，未授權方只有確定私人密鑰(a)，才能對加密消息解密，這需要解DL問題。
圖4H是一流程圖，示出了依照割圓方案對ElGamal系統設定進行加密的過程。在步驟702，希望對消息加密的一方在2≤k≤q-2範圍內隨機選擇一個整數k。在步驟704，在F(pt』)中求γ＝gk。在步驟706，在F(pt』)中求λ＝x-1(m)*yk。函數x-1(*)是圖4B的步驟536中所用函數x(*)的逆函數。在步驟708，所得結果為經加密的消息(γ，λ)。
圖4J是一流程圖，示出了依照割圓方案對ElGamal系統設定進行解密的過程。在步驟722，希望對加密消息(γ，λ)解密的一方在F(pt』)中求ξ＝γq-a，並在步驟724，在F(pt』)中求η＝λξ。在步驟726，在{0，1，…，pt』-1}中獲取解密消息m』，作為m』＝x(η)。所求冪運算在由g生成的子群中進行。性能比較圖5A是一表，示出了公開密鑰密碼系統各方案之籤名生成性能的比較結果。這些被比較的方案是用軟體實施的ElGamal、DSA和割圓方案。沒有對ECDSA方案進行評價，因為它需要用硬體實施。
由於參數B與ElGamal方案無關，所以對於ELGamal方案，情況「C」和「D」是相同的。實際上，DSA方案只允許B＝160，並且L＝512+i*64，其中0≤i≤8，這隻對應於情況「A」和「C」。
在諸例中，只使用了整數消息，並且對於ElGamal，採用mod p-1，而對其它方案，採用mod q。沒有使用散列法。由於散列的計算時間可以忽略，所以省略散列不會影響性能結果。
具體地說，圖5A示出了各方案用軟體實施時，在166MHz Pentuim處理器上的運行時間(單位為秒)。
從ElGamal方案和Schnorr方案可以看出，由於使用子群，性能有所提高。DSA方案的性能幾乎與Schnorr方案的性能相同。
從Schnorr方案和割圓方案可以看出，由於使用最優正規基，性能有進一步的提高。具體地說，對於圖5A中所舉的例子，割圓方案的性能結果幾乎比Schnorr方案的性能快兩倍。
圖5B是一表，就圖5A列表所舉的例子，示出了公開密鑰密碼系統各方案之籤名驗證性能的比較結果。與籤名生成的情況一樣，割圓方案的性能結果幾乎比Schnorr方案的性能快兩倍。
圖6示出了經籤名的且籤名經驗證的消息，可用來獲得圖5A和5B的性能結果。
圖7A-11D示出了用來獲得圖5A和圖5B性能結果的諸例中各公開密鑰密碼系統的公開密鑰、私人密鑰、籤名和籤名生成參數k。通過對十個不同的代表消息的結果取平均，產生計時結果。實際上，雙方不交換籤名生成參數；這裡，交換該參數，以便於再現結果。
對於割圓方案，g和y的值按F(p)上的基αi給出，其中1≤i≤t』。對於所有其它方案，值均為十進位表示。
通過比較，可以看出，ELGamal方案(圖7A、8A、9A、10A和11A)使用最長的值，而割圓方案(圖7D、8D、9D、10D和11D)使用最短的值。另外，由於在圖5A和5B中，數據保密性從情況「A」到情況「E」增強，所以所有方案中值的長度也增大。
圖12是一方框圖，示出了實施割圓方案的環境。通用計算機10包括密碼處理器11、通信接口12、主處理器13、存儲器14、通信總線15和通信線路16。存儲器14包括RAM、ROM、磁碟、光碟或任何其它的存儲媒體。通信線路16可以是有線線路、射頻無線線路、光路或任何其它通信媒體。智慧卡20包括處理器21、存儲器22、通信接口23、通信總線24和通信線路25。通用計算機10和智慧卡20與通信信道30相連。中央設備40也通過通信線路41與通信信道30相連。中央設備40包括實施割圓方案的合適處理硬體和軟體，至於通用計算機10和智慧卡20，也要這樣理解。
通用計算機10執行存儲在存儲器14中的軟體，該軟體包括主處理器13對密碼處理器11的調用，密碼處理器11包括足夠大的存儲空間，以便根據割圓方案進行操作。
智慧卡20根據割圓方案執行存儲在存儲器22中的軟體。
中央設備40的作用是用割圓方案生成全局信息，並將信息分配給所有當事人。全局信息的一個例子是圖4E中步驟600所示的全局公開密鑰。
儘管在此參照附圖詳細描述了本發明的說明書實施例及其各種變化，但應該理解，本發明不限於此明確的實施例以及所述變化，本領域的熟練技術人員可以不脫離所附權利要求書限定的本發明的範圍和精神作各種改變和進一步的變化。
權利要求
1.一種用於確定公開密鑰密碼系統之公開密鑰和私人密鑰的方法，其特徵在於，包括以下步驟選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的所述割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；根據所述生成元和一所選的整數，求一公開值；形成公開密鑰，它包括第一和第二素數、所述生成元和所述公開值；形成私人密鑰，它包括所述所選的整數。
2.如權利要求1所述的方法，其特徵在於，還包括下述步驟，即用最優正規基表示所述有限域。
3.如權利要求1所述的方法，其特徵在於，所述第二素數q滿足(log2q)+1≈B，其中B是預定的二進位位數。
4.如權利要求1所述的方法，其特徵在於，還包括選擇一控制整數t』的步驟，並且所述割圓多項式是t』次割圓多項式，所述公開密鑰包括所述控制整數t』。
5.一種用於為消息生成數字籤名的方法，其特徵在於，包括以下步驟選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的所述割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；根據所述生成元和第一整數，求一公開值；選擇第二整數；根據第二整數和所述生成元，求第一籤名值；根據第一籤名值和所述消息，求第二籤名值；形成數字籤名，它包括第一和第二籤名值。
6.如權利要求5所述的方法，其特徵在於，還包括用最優正規基表示所述有限域的步驟。
7.如權利要求5所述的方法，其特徵在於，所述第二素數q滿足(log2q)+1≈B，其中B是預定的二進位位數。
8.如權利要求5所述的方法，其特徵在於，還包括選擇一控制整數t』的步驟，並且所述割圓多項式是t』次割圓多項式。
9.如權利要求5所述的方法，其特徵在於，所述第一籤名值基於所述生成元自乘到第二整數次冪的雙射。
10.如權利要求5所述的方法，其特徵在於，所述第二籤名值基於所述第一籤名值與消息之密碼散列的組合。
11.一種用於驗證消息之數字籤名的方法，所述數字籤名是根據權利要求5的方法形成的，其特徵在於，所述方法包括以下步驟求一逆整數，它是第二籤名值的逆；根據所述逆整數和所述消息，求第一中間值；根據所述逆整數和所述第一籤名值，求第二中間值；根據所述生成元、所述公開值以及第一和第二中間值，求第三中間值；當第三中間值等於第一籤名值時，判定所述籤名有效。
12.如權利要求11所述的方法，其特徵在於，所述第三中間值是所述生成元的第一中間值次冪乘以所述公開值的第二中間值次冪的雙射。
13.一種用於為公開密鑰密碼系統確定共享密鑰的方法，其特徵在於，包括以下步驟選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的所述割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；選擇一整數；接收一中間值，所述中間值基於所述生成元；形成共享密鑰，使其成為所述中間值和所述整數的函數。
14.如權利要求13所述的方法，其特徵在於，包括用最優正規基表示所述有限域的步驟。
15.如權利要求13所述的方法，其特徵在於，還包括以下步驟求第二中間值，所述第二中間值基於所述生成元和所述整數；將所述第二中間值發送給將要共享所述共享密鑰的一方。
16.一種用於消息保密通信的方法，其特徵在於，包括以下步驟；選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的所述割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；選擇一整數；接收一中間值，所述中間值基於所述生成元；形成共享密鑰，使其成為所述中間值和所述整數的函數；用所述共享密鑰對所述消息加密。
17.如權利要求16所述的方法，其特徵在於，包括用最優正規基表示所述有限域的步驟。
18.一種用於消息保密通信的方法，其特徵在於，包括以下步驟接收加密消息，所述加密消息是用共享密鑰加密的，所述共享密鑰是一中間值和一所選整數的函數，所述中間值基於一有限域中乘法群之子群的生成元，所述子群的階是第二素數，所述第二素數是由第一素數計算得到的割圓多項式的因子，並且用所述共享密鑰對所述加密消息解密。
19.一種用於消息保密通信的方法，其特徵在於，包括以下步驟選擇第一素數；由第一素數計算一割圓多項式；求第二素數，它是由第一素數計算得到的所述割圓多項式的因子；求一有限域中乘法群的子群的生成元，所述子群的階是第二素數；根據所述生成元和第一整數，求一公開值；選擇第二整數；根據所述生成元和第二整數，求第一加密值；根據所述消息、所述公開值和所述第二整數，求第二加密值；由第一和第二加密值形成加密消息。
20.如權利要求19所述的方法，其特徵在於，還包括用最優正規基表示所述有限域的步驟。
21.一種用於消息保密通信的方法，其特徵在於，包括以下步驟接收由第一加密值和第二加密值構成的加密消息，第一加密值基於第一整數和一有限域中乘法群之子群的生成元，所述子群的階是第二素數，所述第二素數是由第一素數計算得到的割圓多項式的因子，所述第二加密值基於所述消息、所述第一整數和基於所述生成元和第二整數的公開值；根據第一加密值和私人密鑰，求第一中間值，所述私人密鑰基於所述生成元；根據第二加密值和所述第一中間值對所述加密消息解密。
22.一種用於對公開密鑰密碼系統確定公開密鑰和私人密鑰的設備，其特徵在於，包括；用於選擇第一素數的裝置；用於由第一素數計算一割圓多項式的裝置；用於求第二素數的裝置，所述第二素數是由第一素數計算得到的所述割圓多項式的因子；用於求一有限域中乘法群之子群的生成元的裝置，所述子群的階是第二素數；用於根據所述生成元和一所選的整數求一公開值的裝置；用於形成公開密鑰的裝置，所述公開密鑰包括第一和第二素數、所述生成元和所述公開值；用於形成私人密鑰的裝置，所述私人密鑰包括所述所選的整數。
23.如權利要求22所述的設備，其特徵在於，還包括用最優正規基表示所述有限域的裝置。
24.如權利要求22所述的設備，其特徵在於，所述第二素數q滿足(log2q)+1≈B，其中B是預定的二進位位數。
25.如權利要求22所述的設備，其特徵在於，還包括用於選擇一控制整數t』的設備，並且所述割圓多項式是t』次割圓多項式，所述公開密鑰包括所述控制整數t』。
全文摘要
用割圓多項式來構造有限域中乘法群的子群,可以高效率地實現基於離散對數的公開密鑰密碼系統,包括公開密鑰加密方案和數字籤名方案。用最優正規基來表示域,並用域中乘法群之子群的生成元來形成公開密鑰。
文檔編號G09C1/00GK1251715SQ97182092
公開日2000年4月26日 申請日期1997年9月26日 優先權日1997年2月14日
發明者A·K·倫斯特拉 申請人:國有花旗銀行