具有消息恢復的數字籤名的認證加密的製作方法

2023-09-17 22:56:55 1

專利名稱：具有消息恢復的數字籤名的認證加密的製作方法
具有消息恢復的數字籤名的認證加密技術領域
本文描述的技術總體涉及密碼籤名，且具體地涉及具有消息恢復的密碼籤名的產生和使用。
背景技術：
傳統密碼籤名方案可以用於提供(I)確保籤名者的身份，以及(2)確保接收到的消息在傳輸期間未被改變。典型地，籤名者產生針對消息的不可偽造的籤名，使得接收者隨後可以驗證籤名以認證籤名者的身份和消息的來源。
一般地，期望較小大小的密碼值，因為其可以降低存儲和傳輸要求。基於橢圓曲線離散對數問題的難解性的籤名方案，如橢圓曲線數字籤名算法(ECDSA)，例如在「AmericanNational Standard for Financial Services ANS X9.62-2005:Public Key Cryptographyfor the Financial Services Industry-The Elliptic Curve Digital SignatureAlgorithm(ECDSA) 」，Accredited Standards Committee X9, Inc., 2005 描述的，可以實現使用比其他密碼方案(如Rivest Shamir Adleman (RSA)算法，例如在「PKCS#lv2.1:RSACryptography Standards」，RSA Laboratories, 2002 中描述)更小的籤名，同時仍提供相同水平的安全性。具有部分消息恢復的數字籤名，例如Nyberg等在「Message Recoveryfor Signature Schemes Based on the Discrete Logarithm Problem，，，Advances inCryptology-Eurocrypt 『94, Springer Verlag, New York, 1994 中描述的，也可以通過在籤名值內嵌入消息的一部分(隱藏部分)來降低[消息，籤名]對的傳輸要求，同時不增加籤名的大小。例如，消息的嵌入部分可以包括發送者的地址或對接收者的地址的確認。橢圓曲線Pintsov-Vanstone籤名(ECPVS)方案是具有部分消息恢復的數字籤名方案的示例。ECPVS 方案例如在「American National Standard for Financial Services DraftX9.92-2007-02-21:Public Key Cryptography for the Financial Services Industry,Digital Signature Algorithms Giving Partial Message Recovery Partl:EllipticCurve Pintsov-Vanstone Signatures (ECPVS)，，，Accredited Standards Committee X9,Inc.,2007以及由Vanstone等在美國專利N0.7，249，259中更詳細描述。在ECPVS中，可以將要籤名的消息的全部或部分嵌入或「隱藏」在籤名中並從籤名中恢復。該方案還可以用於通過添加將籤名者的公鑰保持秘密的限制來提供一定水平的機密性，使得只有擁有公鑰的各方可以驗證籤名，且因此僅它們可以計算消息的隱藏部分。
為了能夠驗證ECPVS籤名，要籤名的消息的隱藏部分具有由籤名者選擇並由驗證者達成一致的預定義特性。例如，隱藏部分可以包含特定水平的冗餘，驗證者檢查該特定水平的冗餘以驗證籤名。冗餘允許將消息的隱藏部分識別為屬於有效明文集合。給定充分的冗餘，偽造者應當不能產生滿足所有準則的籤名。消息的隱藏部分中存在的冗餘越多，安全性水平越高，並且要發送的已籤名的消息越長。發明內容
本文提出了一種在具有消息恢復的數字籤名中使用認證加密的框架，由此修改ECPVS方案以移除針對要籤名的消息的隱藏部分的冗餘準則。本文提出的框架通過將ECPVS中傳統使用的加密替換為認證加密，來增強具有真實性的常規對稱密鑰加密的安全性。所提出的框架可以應用於籤名產生和籤名驗證。在一個示例中，一種認證加密-Pintsov Vanstone (AE-PV)方案使用認證加密(AE)函數來加密要籤名的消息的隱藏部分，同時對隱藏部分創建消息認證碼(MAC)，該MAC應當由驗證者用來驗證已籤名的消息。在另一示例中，一種「MAC然後加密」-Pintsov Vanstone (ME-PV)方案使用MAC函數來獲得要籤名的消息的隱藏部分的MAC，接著使用加密函數來加密隱藏部分和MAC的組合，使得該MAC可以由驗證者用來驗證已籤名的消息。在變型中，一種「加密然後MAC'-Pintsov Vanstone (EM-PV)方案先使用加密函數來加密已籤名的消息的隱藏部分，接著使用MAC函數來獲得加密結果的MAC。在另一示例中，一種具有關聯數據的認證加密-Pintsov Vanstone (AEAD-PV)方案使用具有關聯數據的認證加密(AEAD)函數來加密消息的隱藏部分並對隱藏部分以及消息中的非加密關聯數據創建MAC，從而允許認證隱藏部分和關聯數據。


附圖中的圖用於以示例而非限制方式進行說明。圖中相似的附圖標記指示相應、類似或相似的元素。圖1是針對籤名者和驗證者的示例認證加密籤名方案的簡化框圖；圖2是將籤名應用於消息以產生已籤名的消息的第一示例方法的簡化流程圖；圖3是驗證由籤名者籤名的已籤名的消息的第一示例方法的簡化流程圖；圖4是將籤名應用於消息以產生已籤名的消息的第二示例方法的簡化流程圖；圖5是驗證由籤名者籤名的已籤名的消息的第二示例方法的簡化流程圖；圖6是將籤名應用於消息以產生已籤名的消息的第三示例方法的簡化流程圖；圖7是驗證由籤名者籤名的已籤名的消息的第三示例方法的簡化流程圖；圖8是將籤名應用於消息以產生已籤名的消息的第四示例方法的簡化流程圖；圖9是驗證由籤名者籤名的已籤名的消息的第四示例方法的簡化流程圖；以及圖10是示例籤名者設備和示例驗證者設備的簡化框圖。
具體實施例方式儘管使用橢圓曲線上的點的群來實例化本文描述的籤名方案，但是備選地可以使用任何有限循環群來實例化本文描述的籤名方案，例如；P的子群，模素數P的整數的子群。在這種情況下，群的階可以是P-1，生成元G產生η階的子群，其中η整除p-Ι。傳統上，以乘法形式書寫二P的子群中的算術，其中兩個元素P和Q的乘積為PQ，且在橢圓曲線群中與整數k的標量乘法對應於求冪，即Pk。基於橢圓曲線密碼(ECC)的協議依賴於橢圓曲線離散對數問題的難解性。給定橢圓曲線E上的公開知曉的點G和Q，其中點Q等於標量乘法因數d與點G的乘積，即Q =dG，可以推測非常難以確定標量乘法因數d。利用已知算法，解決該問題的計算難度隨G產生的子群的大小呈指數增長。
為了實現基於ECC的協議，所有參與者就橢圓曲線的域參數達成一致。在素數有限域^上定義的橢圓曲線E，即￡1 ),由橢圓曲線域參數D = (p，a，b，G，n，h)來定義，其中P是表示域中的元素數目的奇素數,整數a和b是滿足例如4a3+27b2 Φ O (mod p)(然而由另一方程指定的曲線可以是合適的)的素數有限域％的元素，G是具有η階的橢圓曲線￡"(%)上的基點或生成元，以及餘因子h是相對小的整數，其被定義為橢圓曲線五(％)上的點的數量從(％)與η之比。可以用加法形式來書寫玖％)的子群中的算術，其中兩點P和Q之和為P+Q，與整數k的標量乘法為kP。現有基於ECC的協議的進一步細節在「Standardsfor Efficient Cryptography SECl:Elliptic Curve Cryptography，，，CerticomResearch, Certicom Corp., 2000,以及 「Standards for Efficient Cryptography SEC2:Recommended Elliptic Curve Domain Parameters version2.0，，，Certicom Research,Certicom Corp.，2000中描述。橢圓曲線還可以定義在有限域F2m上，而不是素數有限域p上，有限域F2Hi是具有2m個元素的二進位表示，且可以修改本文中描述的技術以適於在有限域F2Hl上定義的橢圓曲線。
橢圓曲線Pintsov-Vanstone籤名(ECPVS)方案提供了一種具有部分消息恢復的數字籤名方案。ECPVS方案已經用於通過實現在作為結果的籤名分量之一內嵌入或「隱藏」被籤名的消息的一部分來提供一定水平的機密性。ECPVS可以由籤名者用於對數據產生數字籤名，並由驗證者用於驗證籤名的真實性並恢復在籤名內隱藏的消息的該部分。在籤名產生過程中使用籤名者的私鑰，在籤名驗證過程中使用對應的公鑰。為了使消息的隱藏部分保持機密，籤名者的公鑰需要保持秘密。
如本文使用的術語「籤名者」指能夠針對數據產生數字籤名的任何計算機化設備。如本文使用的術語「驗證者」指能夠驗證數字籤名的真實性的任何計算機化設備。
ECPVS方案的一個方面是籤名者針對要籤名的消息的隱藏部分選擇消息冗餘準貝U，其中該冗餘準則對於驗證者已知，以驗證已籤名的消息。冗餘準則的示例包括:消息是ASCII文件、消息具有特定格式、消息包含特定關鍵字、或者每段以句點結束。總冗餘量是被選擇用於實現安全目標的可縮放安全參數。給定充分冗餘，偽造者應當不能針對消息產生滿足冗餘準則的有效籤名。要籤名的消息的隱藏部分中存在的冗餘越多，安全性水平越高，並且要發送的已籤名的消息越長。因此，選擇合適的密碼籤名可能涉及安全要求與存儲/傳輸要求之間的折衷。
本文提出了一種在具有消息恢復的數字籤名中使用認證加密的框架，由此修改ECPVS方案以移除針對要籤名的消息的隱藏部分的冗餘準則。所提出的框架可以應用於籤名產生和籤名驗證。
在一個示例中，一種認證加密-Pintsov Vanstone (AE-PV)方案使用認證加密(AE)函數來加密要籤名的消息的隱藏部分，同時對隱藏部分創建消息認證碼(MAC)，該MAC應當由驗證者用來驗證已籤名的消息。
在另一示例中，一種「MAC然後加密」-Pintsov Vanstone (ME-PV)方案使用MAC函數來獲得要籤名的消息的隱藏部分的MAC，接著使用加密函數來加密隱藏部分和MAC的組合，使得該MAC可以由驗證者用來驗證已籤名的消息。在變型中，一種「加密然後MAC'-Pintsov Vanstone (EM-PV)方案先使用加密函數來加密已籤名的消息的隱藏部分，接著使用MAC函數來獲得加密結果的MAC。
在另一示例中，一種具有關聯數據的認證加密-Pintsov Vanstone (AEAD-PV)方案使用具有關聯數據的認證加密(AEAD)函數來加密消息的隱藏部分並對隱藏部分以及消息中的非加密關聯數據創建MAC，從而允許認證隱藏部分和關聯數據。
本文提出的框架還適用於密鑰ECPVS和其他籤名密碼(signcryption)技術。
在以下示例中，除非另外指明，否則可以假定籤名方案中的籤名者和驗證者已經就合適的域參數達成一致。例如，對於使用橢圓曲線上的點的群的來實例化的籤名方案，籤名者和驗證者就包括基點G在內的對應橢圓曲線域參數達成一致。
如上所述，儘管使用橢圓曲線上的點的群來實例化本文描述的Pintsov-Vanstone (PV)籤名方案,但是可以使用任何有限循環群來實例化這些方案。在這種情況下，籤名者和驗證者將必須就包括生成元G在內的與該群相關聯的域參數達成一致。
使用特定籤名方案的籤名者和驗證者就與該方案相關聯的函數和參數達成一致。例如，對於認證加密-Pintsov Vanstone (AE-PV)方案，籤名者和驗證者就以整數Ii1為密鑰的認證加密(AE)函數達成一致，該函數能夠取消息M作為輸入，並輸出加密值C1和消息認證碼(MAC) mac,即AEk1 (M) = (C1, mac)。籤名者和驗證者還就認證解密(AD)函數達成一致，其是以整數h為密鑰的AE的逆變換，且其取加密值c/和MAC mac』作為輸入，並要麼輸出消息M和有效(validity)指示,要麼輸出空(null)和無效(invalidity)指示，即ADkl (C1，，mac，) = (M, VALID)或 ADkl (C1』，mac』 ) = (NULL, INVALID)。籤名者和驗證者還就密鑰h的比特長度以及MAC mac的比特長度達成一致。
籤名者和驗證者就合適的密鑰導出函數(KDF)達成一致。例如，對於(AE-PV)方案，KDF能夠用於構造適用於認證加密函數AEkl和認證解密函數ADkl的密鑰。可以使用任何ANS1-X9核准的密鑰導出函數，例如在「NIST SP800-108Recommendation for KeyDerivation Using Pseudorandom Functions，，，National Institute of Standards andTechnology, 2009 中描述的 KDF。
在使用散列函數作為籤名方案的一部分的示例中,籤名者和驗證者就密碼散列函數達成一致，密碼散列函數將任意長度輸入映射至固定長度輸出。示例散列函數包括在「FIPS PUB180_3Federal Information Processing Standards Publication:Secure HashStandard(SHS) 」，National Institute of Standards and Technology, 2008 中描述的SHA-2 族。
籤名者和驗證者就用於傳送包括整數和群元素在內的值的編碼方法達成一致。示例編石馬方法是 Dubuisson 在「ASN.1Communication Between Heterogeneous Systems，，，Morgan Kaufmann，2000中描述的ASN.1。籤名者和驗證者還就以下內容達成一致:在對值列表進行散列操作之前，將值列表公共編碼為比特串。例如，它們可以就以下各項達成一致:(1)將所有值轉換為八位字節串，然後(2)對八位字節串的串聯進行散列操作。與散列操作一樣，可以在導出密鑰之前執行編碼。在利用KDF和散列函數的情況下，編碼可以併入附加信息，例如日期、時間、籤名者名稱、驗證者名稱、或與被籤名的消息相關的聯繫信息。
為了籤名方案的安全性,應當謹慎地選擇域參數。對於Pintsov Vanstone籤名方案，參數選擇的進一步細節可以參見「IEEE P1363a/D2, Standard Specifications forPublic Key Cryptography:Pinstov Vanstone Signatures with Message Recovery，，，Institute of Electrical and Electronics Engineers, 2000。還應注意:為了安全性，籤名者可以包括用於產生密鑰和已籤名的消息的安全隨機或偽隨機數生成器。
如上所述，驗證者知道與用於籤名產生過程的私鑰相對應的籤名者的公鑰，以驗證已籤名的消息。此外，對於消息的隱藏部分要保持機密的實現，不應向其他實體公開籤名者的公鑰。
圖1是針對籤名者100和驗證者102的具有消息恢復的數字籤名的認證加密的示例方案的簡化框圖。籤名者100要對消息M104籤名，消息M104包含隱藏部分N和可見部分V。隱藏部分N是消息M104中要被嵌入或「隱藏」在籤名的一部分中的部分。籤名者100要將籤名應用於消息M104以獲得要發送至驗證者102的已籤名的消息106。已籤名的消息106至少包括:第一籤名分量C、第二籤名分量s和消息M104的可見部分V。為了讓驗證者102驗證已籤名的消息106，驗證者102擁有籤名者100的公鑰GA110。公鑰GaIIO可以從籤名者100直接接收，如圖1中虛線所示，或者可以從可信實體(未示出，如證書權威機構)接收。對於消息M104的隱藏部分N要保持機密的實現，這可以通過確保公鑰GaIIO的機密性來實現。驗證者102執行的對已籤名的消息106的認證解密的結果在108示出。如果已籤名的消息106被驗證，則恢復消息M104的隱藏部分N並伴有有效指示。如果已籤名的消息106未被驗證，則不恢復隱藏部分N並存在無效指示。
圖2是要由籤名者(例如籤名者100)執行的用於將籤名應用於消息M104以產生已籤名的消息106的示例認證加密方法的簡化流程圖。在202，籤名者產生第一值k，第一值k是不應向其他實體公開的籤名者的私有值。根據該第一值k和橢圓曲線上的基點G，籤名者根據方程I來計算第二值Q，第二值Q等於第一值k與基點G的標量乘積:
Q = k.G.(I)
在一些實現中，(k，Q)對是短期的。即，針對要被應用籤名的每個消息M產生新的(k，Q)對。
在204，籤名者根據第二值Q來構造導出密鑰匕。例如，可以根據方程2，通過將密鑰導出函數KDF應用於第二值Q來構造導出密鑰Ic1:
Ic1 = KDF (Q).(2)
在206，籤名者將以導出密鑰Ii1為密鑰的AE函數，即AEkl，應用於消息M104的隱藏部分N，以獲得加密值C1和具有必要長度L的消息認證碼(MAC)mac，其中長度L是認證加密函數AE的參數。這在方程3中示出:
(C1, mac) =AEkl(N).(3)
AE函數用於對消息M104的隱藏部分N加密以及用於創建可以由驗證者用於隨後驗證已籤名的消息106的MACmac。不知道導出密鑰Ii1但是觀察到認證加密函數AEkl輸出的多個[加密值，MAC]對的敵方應當不能輸出可以由驗證者用於成功驗證已籤名的消息106並恢復消息M104的隱藏部分N的新[加密值，MAC]對。關於圖3更詳細描述認證解密。
可以使用的一個可能AE函數是具有計數器模式加密(CME)和密碼塊鏈(CBC)的高級加密標準(AES)，也稱為 AES-CCM，在 「NIST SP800-38C Recommendation for BlockCipher Modes of Operation:The CCM Mode for Authentication and Confidentiality，，，National Institute of Standards and Technology, 2007 中描述。可以使用的另一可能AE 函數是具有 Galois 計數器模式的 AES (AES-GCM)，在 「NIST SP800-38D Recommendationfor Block Cipher Modes of Operation:The Galois/Counter Mode (GCM) and GMAC，，，National Institute of Standards and Technology, 2007 中描述。AES 的細節在 「FIPSPUB197Advanced Encryption Standard (AES)」， Federal Information ProcessingStandards,2001, and Section7.2.2of 「Handbook of Applied Cryptography」，CRCPress, ISBN0-8493-8523-7中描述。可以使用的另一可能AE函數是在「AES Key WrapSpecification，，，National Institute of Standards and Technology, November2001 中描述的 AES 密鑰卷繞及其變型。Accredited Standards Committee, X9, Inc.(ASC X9)已經在其2004年11月出版的其草案標準中定義了 4種算法。這4種算法中的任一種是可以使用的合適AE函數:AESKW(AES密鑰卷繞規範的變型)、TDKW (類似於AESKW，但是使用三重DES而不是AES作為 基礎塊密碼)、AKWl (實質上是在網際網路協議工程任務組請求評論(RFC) 3217中提出的算法)、以及AKW2 (在「密鑰塊」規範中隱式定義的算法，已開發用於金融服務業中的受限傳統系統)。還可以想到使用在加密時不顯式輸出MAC值但是仍提供認證的AE函數。例如，這種AE函數在應用於輸入I時輸出加密值AEkl (I)，但是不輸出任何MAC，且其相關聯認證解密函數AD在應用於輸入I』時，要麼輸出I』無效，要麼輸出I以及I有效的指示。返回圖2，在208，籤名者根據加密值C1和MAC mac形成第一籤名分量C。例如，第一籤名分量c可以是加密值C1和MAC mac的串聯，如方程4所示:C = C1II mac (4)備選地,第一籤名分量c可以是MAC mac和加密值C1的串聯，即c = mac I Ic115更一般地，第一籤名分量c可以是將任何可逆函數f應用於加密值C1和MAC mac的結果，即c=f(Cl，mac)，其中f是由籤名者和驗證者達成一致的。本領域普通技術人員還將理解:可以使用特定不可逆函數。例如，取三個元素X、y和z作為輸入並輸出X和I的串聯的函數f(即f(x，y，z) = x| |y)是不可逆的，因為輸出不包含關於元素z的任何信息。然而，仍可以使用該函數。在210，籤名者根據方程5來計算第二籤名分量s:s = Hash (c | | V).dA+k (modn)， (5)其中Hash是如上所述的密碼散列函數，dA是籤名者的私鑰，對應的公鑰Ga已被計算為私鑰dA與基點G的乘積，即Ga = dA.G0儘管圖中未顯式示出，可以預期計算第二籤名分量s的其他方法。例如，可以通過在方程5中交換私鑰屯和第一值k的位置來計算第二籤名分量S，即s =Hash (c I I V).k+dA(modn) 備選地，可以在這些方程中任意一個方程中對這些項中的任意一項取反。如果使用方程5的這種修改來計算第二籤名分量S，則相應地改變驗證過程。儘管未顯式不出，Hash (c I I V)被轉換為整數以用於方程5或方程5的任一備選中。表達式c| IV表示第一籤名分量c和消息M104的可見部分V的串聯。備選地，可以將可見部分V與第一籤名分量C串聯，即Vl |c。更一般地，可以使用任何可逆函數g將第一籤名分量C與可見部分V組合，即g(c，V)，其中g由籤名者和驗證者達成一致。如以上關於方程4所述，也可以使用特定不可逆函數。
在212，籤名者準備已籤名的消息106，已籤名的消息106包括第一籤名分量C、第二籤名分量s和消息M104的可見部分V。儘管第一籤名分量c和可見部分V被示出為已籤名的消息106的分離的元素，但是可以想到:如在210計算第二籤名分量s期間所做的一樣，可以使用可逆函數g將其組合。例如，如果如方程5所示串聯第一籤名分量c和可見部分V，則已籤名的消息106可以包括相同串聯，即c| |V。
圖3是由驗證者(例如驗證者102)執行的用於驗證聲稱由籤名者(例如籤名者100)籤名的已籤名的消息(例如已籤名的消息106)的示例認證解密方法的簡化流程圖。
在301，驗證者從已籤名的消息106中提取第一籤名分量C』、第二籤名分量s』和消息M104的可見部分V』。撇號用於指示尚未被驗證的值。如上所述，如果已經使用可逆函數g將第一籤名分量c和可見部分V組合，則需要函數g的反函數，即g—1，來從已籤名的消息106中提取第一籤名分量c』和可見部分V』。
在302，驗證者使用與認證加密函數AE相關聯的必要長度L(已經由籤名者和驗證者達成一致)，從第一籤名分量c』中提取加密值C1』和MAC mac』。例如，如果第一籤名分量c被定義為加密值C1和MAC mac的串聯，如方程4所示，則驗證者可以通過將第一籤名分量c』的最後L個比特定義為MAC mac』，使得在第一籤名分量c 』的起始處的其餘比特對應於加密值c/，來確定加密值C/。
如果已經如上所述使用某個其他可逆函數f來將加密值C1和MAC mac組合，則需要函數f的反函數，即Γ1，來從第一籤名分量c』中提取加密值C1』和MAC mac』。
應當注意，可以在308處應用認證解密函數之前的任何時間執行在302處描述的提取，如以下更詳細描述的。
在304，驗證者根據方程6來計算值Q』:
Q，= S，.G—Hash(C，||V，).Ga, (6)
其中Hash是籤名者用於如方程5所示在210計算第二籤名分量s的相同密碼散列函數。如上所述，如果使用方程5的修改來計算第二籤名分量S，則將需要相應修改方程6。如方程5中一樣，Hash (c| I V)被轉換為整數用於方程6。可以從籤名者100直接接收公鑰GA110，或者可以從可信實體(如證書權威機構)接收公鑰64110。如上所述，可以想到第一籤名分量c』和可見部分V』的其他組合以取代方程6中所示的串聯c』 I |V』，只要方程6中使用的組合對應於在方程5中計算第二籤名分量s時使用的組合。
在306，驗證者使用籤名者在204構造導出密鑰Ii1的相同方法，根據值Q』來構造導出密鑰k/。例如，如果籤名者已經使用密鑰導出函數KDF來構造導出密鑰匕，如方程2所示，則驗證者要根據方程7來構造導出密鑰k/:
k/ = KDF (Qj ).(7)
在308，驗證者應用AD函數，該AD函數是籤名者在206使用的AE函數的逆變換。以導出密鑰k/為密鑰並表示為ADkl』的AD函數可以用於驗證已籤名的消息106並恢復消息104的隱藏部分N。AD函數的結果108取決於驗證者是否能夠驗證已籤名的消息106。如果驗證者確定已籤名的消息106有效，則結果108包括恢復的消息M104的隱藏部分N和有效指示。如果驗證者確定已籤名的消息106無效，則結果108僅包括無效指示而不包括隱藏部分N。
取代使用在方程3中描述並在206處示出的AE函數來聯合創建加密值C1和MACmac，可以作為兩個分離的步驟來執行加密和MAC的創建。存在這一操作的至少兩種變型，稱為=(I)MAC然後加密(ME)以及⑵加密然後MAC (EM)。(還存在加密並且MAC變型。然而，假如加密並且MAC變型僅對於加密函數和MAC函數的特定選擇是安全的，因此不顯式描述加密並且MAC變型。)
加密函數和MAC函數均可以是安全函數。安全加密函數的示例包括:具有密碼塊鏈的 AES(AES-CBC)和 AES 計數器模式(AES-CTR)，如在「NIST SP800-38A Recommendationfor Block Cipher Modes of Operation，，，National Institute of Standards andTechnology, 2001中描述的。安全MAC函數的示例包括:如在「IS0/IEC9797DataCryptographic Techniques-Data integrity mechanism using a cryptographic checkfunction employing a block cipher algorithm，，， International Organization forStandardization, 1989中描述的AES密碼塊鏈消息認證碼(AES-CBC-MAC)，以及如在「NISTSP800-38B Recommendation for Block Cipher Modes of Operation:The CMAC Mode forAuthentication，，，National Institute of Standards and Technology, 2005 中描述的AES基於密碼的MAC(AES-CMAC)。加密函數和MAC函數由籤名者和驗證者達成一致。
圖4是圖2所示的用於消息M104的AE方法的示例「MAC然後加密」變型的簡化流程圖。如關於圖2所述，圖4所示示例方法包括:在202，產生第一值k並計算第二值Q。如關於圖2所述，在一些實現中，(k，Q)對是短期的。即，針對要被應用籤名的每個消息M產生新的(k，Q)對。然而，在本方法中，在404，籤名者根據值Q來構造第一導出密鑰kn和第二導出密鑰k12。例如，根據方程8，可以通過將密鑰導出函數KDF應用於第二值Q來構造導出密鑰h和k2:
(k1； k2) = KDF (Q), (8)
其中，KDF的輸出長於方程2中使用的KDF的輸出，使得可以將輸出劃分為第一導出密鑰kn和第二導出密鑰k12。備選地，可以通過將KDF應用於第二值Q兩次，每次應用使用不同的輔助信息，來構造第一導出密鑰kn和第二導出密鑰k12。儘管有可能將KDF應用於第二值Q兩次而不針對每次應用使用不同的輔助信息，但是出於安全原因這可能不可取。
在405，籤名者根據方程9，將以第二導出密鑰k12為密鑰的MAC函數T，即Tkl2，應用於消息M104的隱 藏部分N，以獲得MAC mac:
mac = Tkl2 (N),(9)
其中MAC mac具有必要長度L，L是MAC函數T的參數。
在406，籤名者根據方程10，將以第一導出密鑰kn為密鑰的加密函數E，即Ekll,應用於隱藏部分N和MAC mac的組合，以獲得第一籤名分量c:
c = Ekll (N I mac).(10)
表達式N| |mac表示隱藏部分N和MAC mac的串聯。備選地,可以將MAC mac與隱藏部分N串聯，S卩mac I I N。更一般地，可以使用任何可逆函數j將隱藏部分N與MAC mac組合，即j (N，mac)，其中j是籤名者和驗證者達成一致的。如以上關於方程4所示，還可以使用特定不可逆函數。
在406獲得第一籤名分量c時，方法如關於圖2所述繼續，其中在210籤名者計算第二籤名分量S，在212準備已籤名的消息106。
圖5是圖3中所示AD方法的示例「解密然後驗證」變型的簡化流程圖。如關於圖3所述，圖5所示示例方法包括:在301，從已籤名的消息106中提取第一籤名分量C』、第二籤名分量s』和可見部分V』。撇號用於指示尚未被驗證的值。在304，驗證者使用公鑰GaIIO來計算值Q』。在506，驗證者使用籤名者在404用於構造第一導出密鑰kn和第二導出密鑰k12的相同方法，根據值Q』來構造第一導出密鑰kn』和第二導出密鑰k12』。為了解密第一籤名分量c』，在508，驗證者將解密函數D應用於第一籤名分量c』，其中解密函數D是籤名者在406使用的加密函數E的逆變換。解密函數以第一導出密鑰kn』為密鑰，並表示為Dk1/。這在方程11中示出:N』 I I mac』 = Dkl/ (c), (11)其中N』 I |mac』表示已籤名的消息106的隱藏部分N』和MAC mac』的串聯。驗證者能夠使用與籤名者和驗證者達成一致的與MAC函數T相關聯的必要長度L，從串聯N』 I I mac^中提取隱藏部分N』和MAC mac』。如果如上所述在406使用某個其他可逆函數j來將隱藏部分N和MAC mac組合，則需要函數j的反函數，即j—1，來獲得隱藏部分N』和MAC mac』。在510，驗證者使用第二導出密鑰k12』來驗證MAC mac』是已籤名的消息106的隱藏部分N』的有效MAC，並且相應地確定已籤名的消息106是否有效。如以上關於圖3所述，如果驗證者確定已籤名的消息106有效，則結果108包括恢復的消息M104的隱藏部分N和有效指示。如果驗證者確定已籤名的消息106無效，則結果108僅包括無效指示而不包括隱藏部分N。還可以想到:可以使用「加密然後MAC」/ 「驗證然後解密」變型作為「MAC然後加密」/ 「解密然後驗證」變型的備選。圖6是圖2所示的用於消息M104的AE方法的示例「加密然後MAC」變型的簡化流程圖。如關於圖2所示，圖6所示方法包括:在202，產生第一值k並計算第二值Q，使得Q = k*G。如關於圖2所述，在一些實現中，(k，Q)對是短期的。即，針對要被應用籤名的每個消息M產生新的(k，Q)對。然後，如關於圖4所述，在404，籤名者根據值Q來構造第一導 出密鑰kn和第二導出密鑰k12。在606，籤名者根據方程12，將以第一導出密鑰kn為密鑰的加密函數E，即Ekll,應用於隱藏部分N，以獲得加密值C1:C1 = Ekll(N) (12)在607，籤名者根據方程13，將以第二導出密鑰k12為密鑰的MAC函數T，即Tkl2，應用於加密值C1,以獲得MAC mac:mac = Tkl2 (C1),(13)其中MAC mac具有必要長度L，L是MAC函數T的參數。在607獲得MAC mac後，方法如關於圖2所述繼續，其中簽名者在208根據加密值C1和MAC mac形成第一籤名分量C，在210計算第二籤名分量S，在212準備已籤名的消息106。圖7是圖3所示的AD方法的示例「驗證然後解密」變型的簡化流程圖。如關於圖3所述，圖7所示示例方法包括:在301，從已籤名的消息106中提取第一籤名分量C』、第二籤名分量s』和可見部分V』，在302從第一籤名分量c』中提取加密值C1』和MAC mac』，以及在304使用公鑰GaIIO來計算值Q』。撇號用於指示尚未被驗證的值。如關於圖5所述，在506，驗證者使用籤名者在404用於構造第一導出密鑰kn和第二導出密鑰k12的相同方法，根據值Q』來構造第一導出密鑰kn』和第二導出密鑰k12』。
在708，驗證者使用第二導出密鑰k12』來驗證MAC mac』是加密值c/的有效MAC，並相應地確定已籤名的消息106是否有效。
如果驗證者確定MAC mac』是加密值c/的有效MAC，則在710，驗證者繼續將解密函數D應用於加密值C1 』 ,其中解密函數是籤名者在606使用的加密函數E的逆變換。解密函數以第一導出密鑰kn』為密鑰，並表示為Dkll』。這在方程14中示出:
N = Dkl/ (c/ ).(14)
由於驗證者已經在708確定MAC mac』是加密值C1 』的有效MAC從而已籤名的消息106有效，結果108包括恢復的消息M104的隱藏部分N和有效指示。
如果驗證者在708確定MAC mac』不是加密值c/的有效MAC，則驗證者不在710應用解密函數D，且結果108僅包括無效指示而不包括隱藏部分N。
在另一示例中，可以使用具有關聯數據的認證加密(AEAD)作為具有消息恢復的Pintsov-Vanstone籤名方案的一部分。例如，可以利用AEAD函數來代替AE函數。Rogaway在「Authenticated encryption with associated data，，，Proceedings of ACM CCS』 02:98-107，ACM, New York, 2002 中更詳細描述了 AEAD。
與AE-PV、ME-PV 和 EM-PV 方案類似，AEAD-Pintsov Vanstone (AEAD-PV)方案可以用於對消息M的要在籤名中嵌入或隱藏的隱藏部分N進行加密，並對消息的該部分提供真實性和機密性。AEAD-PV方案使用AEAD函數來保證消息的可見部分V的真實性(從而可以避免使用散列函數)。在許多設置中，存在與加密值相關聯的數據，所述數據是公開的，以允許不擁有加密密鑰的中間方處理或路由消息。使用AEAD函數來代替上述籤名方案中的AE函數具有不涉及散列函數的優點。
AEAD-PV方案包括:籤名者和驗證者就以整數Ii1為密鑰的AEAD函數達成一致，該函數能夠取隱藏部分N和可見部分V作為輸入，並輸出加密值C1和MAC mac,即AEADk(N，V) = (C1, mac)。籤名者和驗證者還就具有關聯數據的認證解密(ADAD)函數達成一致,該函數是AEAD的逆變換，其以整數k/為密鑰且取加密值c/和MAC mac』為輸入，並要麼輸出隱藏部分N和有效指示，要麼輸出空和無效指示，即ADADkl』 (Cl，，mac，，V) = (N, VALID)或ADADkl』 (Cl，，mac，，V) = (NULL, INVALID)。籤名者和驗證者還就密鑰Ic1的比特長度和MAC mac的比特長度達成一致。適用於所提出的框架的示例AEAD方案由Kohno等在「CWC:A High-Performance Conventional Authenticated Encryption Mode，，， Proceedings ofFast Software Encryption2004 (FSE，04)，LNCS3017:408-426, 2004 中描述。
圖8是由籤名者(例如籤名者100)執行的用於將籤名應用於消息104以產生已籤名的消息106的示例具有關聯數據的認證加密(AEAD)方法的簡化流程圖。如關於圖2所示，在202，籤名者產生第一值k並計算第二值Q，使得Q = k.G0如關於圖2所述，在一些實現中，(k，Q)對是短期的。即，針對要被應用籤名的每個消息M產生新的(k，Q)對。在204，籤名者根據第二值Q來構造導出密鑰Ic1。
在806，籤名者將以導出密鑰Ii1為密鑰的AEAD函數，即AEADkl，應用於消息M104的隱藏部分N和消息M104的可見部分V，以獲得加密值C1和具有必要長度L的MAC mac，其中長度L是籤名者和驗證者達成一致的與AEAD相關聯的參數。這在方程15中示出:
(C1, mac) = AEADkl (N, V).(15)
AEAD函數用於對消息M104的隱藏部分N加密，並用於創建驗證者可以用於隨後驗證已籤名的消息106的MAC。具體地，AEAD函數的應用可以用於保證可見部分V的真實性，而不涉及散列函數，如以下更詳細描述的。在806獲得加密值C1和MAC mac之後，籤名者如關於圖2所述繼續，以在208根據加密值C1和MAC mac形成第一籤名分量C。在810，籤名者根據方程16來計算第二籤名分量s:s = mac.dA+k (modn), (16)其中，MAC mac已經被轉換為整數用於方程16中。方程16與方程5的比較揭示了在AEAD-PV加密中不涉及AE-PV、ME-PV和EM-PV認證加密方法的散列函數。儘管在圖8中未顯式示出，可以想到計算第二籤名分量s的其他方法。例如，可以通過在方程16中交換私鑰屯和第一值k的位置來計算第二籤名分量S，即s =mac *dA+k (modn)。備選地，可以在這些方程中的任意一個方程中對這些項中的任一項取反。如果使用方程16的修改來計算第二籤名分量S，則相應地改變驗證過程。在208計算第二籤名分量s之後，籤名者如關於圖2所述繼續，在212準備已籤名的消息106。圖9是由驗證者(例如驗證者102)執行的用於驗證聲稱由籤名者(例如籤名者100)籤名的已籤名的消息(例如已籤名的消息106)的示例具有關聯數據的認證解密(ADAD)方法的簡化流程圖。如關於圖3所述，圖9所示示例方法包括:在301從已籤名的消息106中提取第一籤名分量c』、第二籤名分量s』和可見部分V』，在302從第一籤名分量c』中提取加密值c/和MAC mac』。撇號用於指示尚未被驗證的值。在這種情況下，MAC mac』具有必要長度L, L是AEAD函數的由籤名者和驗證者達成一致的參數。在904，驗證者根據方程17，使用公鑰GaIIO來計算值Q』:Q』 = s』.G—mac』.Ga, (17)其中，在用於方程17之前，MAC mac』已經被轉換為整數。方程17與方程6的比較揭示了在AEAD-PV解密中不涉及AE-PV、ME-PV和EM-PV認證解密方法的散列函數。如上所述，如果使用方程16的修改來計算第二籤名分量S，則將需要相應修改方程17。在306，驗證者使用籤名者在204構造導出密鑰Ic1的相同方法，根據值Q』來構造導出密鑰k/。在908，驗證者將ADAD函數應用於加密值C1』、MAC mac』和可見部分V』，其中ADAD函數是籤名者在806使用的AEAD函數的逆變換。以導出密鑰k/為密鑰並表示為ADADk/的ADAD函數可以用於驗證已籤名的消息106並用於恢復消息M104的隱藏部分N。ADAD函數的結果108取決於驗證者是否能夠驗證已籤名的消息106。如果驗證者確定已籤名的消息106有效，則結果108包括恢復的消息M104的隱藏部分N和有效指示。如果驗證者確定已籤名的消息106無效，則結果108僅包括無效指示而不包括隱藏部分N。如上所述，所提出的框架還可以適用於密鑰ECPVS和其他籤名密碼技術。籤名密碼提供了公鑰籤名和加密這兩者的功能。籤名者在創建籤名密碼消息時使用驗證者的公鑰。只有驗證者能夠使用驗證者的秘密密鑰和籤名者的公鑰來解密消息並驗證消息是由籤名者籤名的。這與如ECPVS中保持籤名者的公鑰是秘密的不同，因為通過驗證者的秘密密鑰的私密性來提供機密性，而籤名者的公鑰可以公開。
將認識到，對於非常短的消息M = N| |V，可見部分V可以為空。AE-PV方案可以在無修改的情況下處理可見部分為空的情況。如果隱藏部分N為空，則在AE-PV方案中，應當將隱藏部分N替換為零字節或任何其他公共常數。AEAD-PV方案可能能夠處理空消息。如果不能，則可以將空消息或消息的空部分替換為公共常數。
圖10是籤名者設備1000和驗證者設備1040的簡化框圖。
籤名者設備1000能夠執行圖2、4、6和8所示示例方法中的一個或多個。籤名者設備1000包括處理器1002，處理器1002耦合至存儲器1004和通信接口 1006。籤名者設備1000可以包括隨機或偽隨機數生成器(RNG) 1005。籤名者設備1000可以包含為了清楚而在圖10中未示出的其他元件。
驗證者設備1040能夠執行圖3、5、7和9所示示例方法中的一個或多個。驗證者設備1040包括處理器1042，處理器1042耦合至存儲器1044和通信接口 1046。驗證者設備1040可以包含為了清楚而在圖10中未示出的其他元件。
處理器1002和1042可以包括處理單元、數位訊號處理器、硬體加速器等等的任何組合。存儲器1004的全部或部分可以嵌入處理器1002中。存儲器1044的全部或部分可以嵌入處理器1042中。
通信接口 1006和1046可以是有線通信接口或無線通信接口或光通信接口。例如，通信接口 1006和1046可以是通用串行總線(USB)接口，乙太網接口、綜合業務數字網(ISDN)接口、數字訂戶線(DSL)接口、區域網(LAN)接口、高清多媒體(HDMI)接口、數字視頻接口(DVI)或電氣與電子工程師協會(IEEE) 1394接口，如1.LINK 、LynxSM或:Firewire 。在另一示例中，通信接口 1006和1046可以是無線區域網(WLAN)接口、短距無線通信接口，如無線個域網(WPAN)接口、近場通信接口、無線城域網(WMAN)接口或無線廣域網(WffAN)接口。
可以由籤名者設備1000的處理器1002和存儲器1004中存儲的代碼1008的任意組合來實現在圖2、4、6和8所示示例方法中的一個或多個的功能。存儲器1004還可以存儲處理器1002要執行的籤名者設備1000中安裝的應用(未示出)。
存儲器1004和1044中的每一個能夠存儲已由籤名者設備1000和驗證者設備1040達成一致的參數1010。達成一致的參數1010的示例是:橢圓曲線域參數D、一個或多個密鑰導出函數、一個或多個散列函數、與要實現的籤名方案相關聯的一個或多個函數(例如AE函數、MAC函數、加密函數、和AEAD函數中的一個或多個)以及與籤名方案相關聯的參數，如消息認證碼的必要長度L。
存儲器1004能夠存儲籤名者設備1000的私鑰dA1012，私鑰dA1012對應於籤名者設備1000的公鑰Ga1014。存儲器1004還能夠存儲在202計算的第一值kl016和第二值Q1018(除了(k，Q)對是短期的從而不存儲在存儲器中的實現之外)。存儲器1004能夠存儲要被籤名的消息的隱藏部分N1020和可見部分V1022。此外，存儲器1004能夠存儲在204或404構造的一個或多個導出密鑰1024、在206、606或806計算的加密值C1 1026以及在206,405,607或806確定的消息認證碼macl028。存儲器1004能夠存儲在208或406確定的第一籤名分量C1030和在210或810確定的第二籤名分量sl032。存儲器1004可以存儲在圖10中未顯式示出的附加元素。
如箭頭1034所示，能夠直接或經由一個或多個中間設備從籤名者設備1000向驗證者設備1040發送包括可見部分V1022、第一籤名分量C1030和第二籤名分量sl032在內的已籤名的消息1036，其中，已籤名的消息1036可以存儲在驗證者設備1040的存儲器1044中。儘管未顯式示出，已籤名的消息1036可以經由通信接口 1006從籤名者設備1000發送，並可以經由通信接口 1046由驗證者設備1040接收。
可以由驗證者設備1040的處理器1042和存儲器1044中存儲的代碼1048的任意組合來實現在圖3、5、7和9所示示例方法中的一個或多個的功能。存儲器1044還可以存儲處理器1042要執行的驗證者設備1040中安裝的應用(未示出)。
存儲器1044能夠存儲籤名者設備1000的公鑰GA1014，存儲器1044可以直接從籤名者設備1000或從可信設備(未示出)(可能經由通信接口 1046以及可能由其他手段)接收Ga1014。例如，籤名者設備1000的公鑰GA1014可以包括在驗證者設備1040上安裝的軟體中。存儲器1044還能夠存儲在304或904確定的值Q』 1050、在306或506構造的一個或多個導出密鑰1052、在302提取的加密值c/ 1054和在302或508確定的消息認證碼mac』 1056，以及所恢復的隱藏部分N1020。存儲器1044可以存儲在圖10中未顯式示出的附加元素。
儘管以結構特徵和/或方法動作特定的語言描述了本發明的內容，但是應理解:在所附權利要求中限定的內容不必限於上述特定特徵或動作。而是上述特定特徵和動作僅作為實現權利要求的示例形式來公開。
權利要求
1.一種將籤名應用於原始消息M(104)以產生由籤名者(100，1000)籤名的已籤名的消息(106,1036)的方法，所述原始消息M(104)由第一部分N(1020)和第二部分V (1022)組成，所述方法包括: 選擇第一整數值k(1016)並根據第一整數值k(1016)和橢圓曲線的基點G來計算第二值Q (1018)，使得第二值Q (1018)包括在所述橢圓曲線上的點的集合中； 通過將密鑰導出函數KDF應用於包括第二值Q(IOlS)的輸入來構造導出密鑰Iq (1024)； 將以導出密鑰1^(1024)為密鑰的認證加密函數應用於消息M(104)的第一部分N(1020)以獲得加密值Cl(1026)並獲得消息認證碼mac (1028)； 將加密值(^(1026)和消息認證碼mac (1028)可逆組合，以形成第一籤名分量c (1030)； 使用以下各項來計算第二籤名分量s (1032): ⑴第一整數值k(1016)； ( )籤名者(100,1000)的私鑰dA (1012);以及 (iii)第二整數值，其依賴於第一籤名 分量c(1030)和消息M(104)的第二部分V(1022);以及 將第一籤名分量c (1030)、第二籤名分量s (1032)和消息M(104)的第二部分V(1022)可逆組合，以形成已籤名的消息(106，1036)， 其中，對所述已籤名的消息(106，1036)的驗證和根據所述已籤名的消息(106，1036)來恢復消息M(104)的第一部分N(1020)涉及籤名者(100,1000)的公鑰GA(110，1014)。
2.根據權利要求1所述的方法，其中，籤名者的公鑰Ga包括在橢圓曲線上的點的集合中，並能夠根據私鑰dA(1012)和基點G來計算。
3.根據權利要求1所述的方法，所述方法還包括: 向驗證者(102，1040)發送所述已籤名的消息(106，1036)。
4.根據權利要求1所述的方法，所述方法還包括: 將散列函數應用於第一籤名分量c (1030)和消息M(104)的第二部分V(1022)的可逆組合，以獲得散列結果；以及 計算與散列結果等價的第二整數值。
5.根據權利要求4所述的方法，其中，所述可逆組合還包括籤名者(100，1000)的身份。
6.一種驗證已籤名的消息(106，1036)的方法，所述已籤名的消息(106，1036)是通過將籤名應用於由第一部分N(1020)和第二部分V(1022)組成的原始消息M(104)而產生的，所述方法包括: 接收聲稱由籤名者(100，1000)籤名的已籤名的消息(106，1036)，所述已籤名的消息(106，1036)是根據第一籤名分量c (1030)、第二籤名分量s (1032)和消息M(104)的第二部分V(1022)以可逆方式準備的； 從所述已籤名的消息(106，1036)中提取第一籤名分量c(1030)、第二籤名分量s (1032)和第二部分 V (1022)； 從第一籤名分量c (1030)中提取消息認證碼mac』 (1056)和加密值c/ (1054)； 接收籤名者(100,1000)的公鑰GA(110，1014)； 使用第二籤名分量8(1032)、橢圓曲線的基點6、公鑰64(110，1014)和中間值來計算第一值Q』(1050)，所述中間值依賴於第一籤名分量c(1030)和消息M(104)的第二部分V(1022)； 通過將密鑰導出函數KDF應用於包括第一值Q』 (1050)的輸入來構造導出密鑰k/ (1052)； 將以導出密鑰k/ (1052)為密鑰的認證解密函數應用於加密值c/ (1054)和消息認證碼mac』 (1056)來確定所述已籤名的消息(106，1036)是否有效，以及在所述已籤名的消息(106，1036)有效的情況下恢復原始消息M(104)的第一部分N(1020)。
7.根據權利要求6所述的方法，其中，籤名者的公鑰Ga包括在橢圓曲線上的點的集合中，並能夠根據籤名者(100，1000)的私鑰dA(1012)和基點G來計算。
8.一種籤名者設備(100，1000)，包括: 處理器(1002)； 通信接口(1006)，耦合至所述處理器(1002);以及 存儲器(1004)，耦合至所述處理器(1002)，所述存儲器(1004)存儲代碼(1008)，在由所述處理器(1002)執行時，所述代碼(1008)被配置為執行根據權利要求1至5所述的任一方法。
9.一種驗證者設備(102，1040)，包括: 處理器(1042)； 通信接口(1046)，耦合至所述處理器(1042);以及 存儲器(1044)，耦合至所 述處理器(1042)，所述存儲器(1044)存儲代碼(1048)，在由所述處理器(1042)執行時，所述代碼(1048)被配置為執行根據權利要求6或7所述的方法。
全文摘要
本發明提出了一種用於具有消息恢復的數字籤名的認證加密的框架，由此實現認證而無冗餘要求。通過使用認證加密來修改橢圓曲線Pintsov-Vanstone籤名方案，從而使用消息認證碼(1028)來實現認證。認證加密可以在單一函數中執行，或者作為兩個分離的函數執行。還可以將認證加密應用於要籤名的消息(104)中的關聯數據。
文檔編號H04L9/32GK103155481SQ201180049393
公開日2013年6月12日 申請日期2011年10月11日 優先權日2010年10月15日
發明者馬修·約翰·坎帕尼亞, 丹尼爾·理察·L·布朗, 格雷戈裡·馬克·扎韋魯哈 申請人:塞爾蒂卡姆公司