基於橢圓曲線的自認證籤名方法與裝置的製作方法

2023-08-11 01:49:56

專利名稱：基於橢圓曲線的自認證籤名方法與裝置的製作方法
技術領域：
本發明涉及密碼領域的數字籤名技術，自認證技術，通過結合橢圓曲線密 碼技術，並且利用計算機和其他類型的通訊設備，通過網絡或其他途徑實現自 認證籤名系統的設計，從而可以作為構造安全，公平電子商務、電子政務等的 模塊。
背景技術：
數字籤名方案中的私鑰通常情況下，是由實體自己選取，並且秘密保管， 所產生的相應公鑰需要由一個認證權威機構產生一個證書來認證。在籤名過程. 中，籤名實體利用其私鑰可以對任何消息進行籤名，當一個驗證者驗證一個籤 名的有效性時，首先驗證籤名者公鑰證書的有效性，再利用籤名者的公鑰來驗
證消息籤名的有效性。在這種傳統的PKI公鑰體制下，認證權威機構需要對 用戶公鑰證書的產生、更新、撤銷和分發等複雜操作進行管理，從而給認證權 威機構帶來了沉重的負擔，也增大了驗證者驗證的計算量。而基於身份的公鑰 體制，採用用戶的身份，如IP位址或email地址等作為用戶的公鑰，刪除 了傳統PKI公鑰體制中公鑰證書的複雜管理，然而，用戶的私鑰需要一個私 鑰產生中心(PKG)來產生，用戶必須完全信任該PKG，因而，基於身份的 公鑰體制存在著密鑰託管問題。在現實社會中，這種信任無法完全保證。
為了刪除傳統PKI體制中認證權威機構對公鑰證書的複雜管理，以及基
於身份公鑰體制中的密鑰託管問,我們提出一種自認證籤名系統。在該系統中，
用戶私鑰的產生是由用戶和權威認證機構共同完成。
本發明提出的基於橢圓曲線的自認證的籤名方案，區別於傳統公鑰密碼體
制下數字籤名方案，也不同於基於身份公鑰體制下簽名方案，它刪除了這兩種公鑰體制的弊端並繼承了它們的優勢。在這種方案中，籤名實體的私鑰由兩部
分組成， 一部分是由籤名實體在Zp中隨機一個元素來產生，另一部分是由認證
授權機構通過自己的公/私鑰對、籤名實體的身份和公鑰及其系統參數來產生， 這樣不僅可以使得籤名實體的公鑰被隱式的驗證，而且可以有效的解決密鑰的 託管問題，同時，也刪除了對權威認證機構對公鑰證書的複雜管理。有效的 限制了權威認證機構的權利的濫用，杜絕了惡意的權威認證機構以籤名實體的 名義來偽造消息籤名。籤名實體只有在權威認證機構的幫助下，才能獲得有效 的籤名私鑰。因此，不了解密碼知識的實體也可以從這種籤名方案中受益。
橢圓曲線是代數幾何中最重要的一類研究對象，其中橢圓曲線中的雙線
性對即代數曲線的Wdl和Tate對是代數幾何研究的重要工具。橢圓曲線上的 離散對數問題遠難於離散對數問題，在橢圓曲線密碼系統中單位比特強度要遠 高於傳統的離散對數系統。因此在使用較短的密鑰的情況下，ECC可以達到於 DL系統相同的安全性。這帶來的好處就是計算參數更小，密鑰更短，運算速 度更快，籤名也更加短小。因此橢圓曲線密碼尤其適用於處理器速度、帶寬及 功耗受限的場合。目前，許多基於橢圓曲線的數字籤名方案被提出，尤其是許 多基於身份ID的數字籤名。隨著數字籤名的發展，為了能夠滿足不同的實際 情況的要求，出現了適應不同情況的數字籤名方案。但關於籤名密鑰的產生， 密鑰的託管卻一直是研究的難點和重點。
1985年Neal Koblitz和Victor Miller分別提出將橢圓曲線用於公鑰密碼系 統，並用橢圓曲線實現了已存在的公鑰密碼算法。基於橢圓曲線離散對數問題 難解性的密碼算法被稱為橢圓曲線密碼算法(Elliptic Curve Cryptography簡稱 ECC)，成為國際密碼界所廣泛接受的公鑰密碼算法。
US4200770給出了 一個可以在公開信道中交換密鑰的方法和設備，這個方 法稱為公開密鑰交換或稱為Diffie-Hellman密鑰交換方法。該專利使得通信雙 方使用一個模函數協商和傳遞他們的秘密信息，解決了設計安全密碼系統的一些密鑰管理方面的麻煩。公鑰密碼系統中，每個實體擁有自己的私鑰和公鑰， 私鑰只有實體自己知道，公鑰則由系統管理，不需要阻止公鑰的公開，由於它 的秘密在安全通信和數字籤名中是不必要的。但是，公鑰密碼體制面臨著熟悉 的認證問題，例如， 一個實體提供給籤名實體有效的，但是錯誤的公鑰，籤名 實體利用該公鑰將秘密信息編碼，編碼將有可能被籤名實體以外的實體解碼， 或者騙取籤名實體接受含有無效籤名的信息。最熟悉的認證公鑰的方法是利用
明確的證書，像X.509。當某個實體要使用其他實體的公鑰時，前者必須要事 先驗證該公鑰的真實性。攻擊者要想獲得傳遞的秘密信息，必須解決離散對數 問題，如果使用的參數足夠大，解離散對數問題是個難解的問題。
在傳統公鑰PKI框架下，用戶的公鑰是一串沒有意義的字符串v並且有 一個公鑰證書與之相關聯。為了簡化證書的管理，在1984年Shamir提出了基 於身份的公鑰密碼系統。在基於身份的公鑰是由籤名實體的身份產生，相應的 私鑰由一個值得信賴的認證授權機構產生。顯然，這種體制存在著一個致命問 題密鑰託管問題。認證授權機構了解所有籤名實體的私鑰，對於一個不誠實 的認證授權機構，它可以任何偽造籤名實體的籤名。在1991年，Girault提出 的自認證的公鑰體制，作為除了基於身份的密碼系統和傳統的公鑰密碼體系以 外的一種可選公鑰體制。該公鑰體制不僅刪除了傳統公鑰體制下的複雜的證書 管理，也克服了基於身份密碼系統中的密鑰託管問題。籤名實體的私鑰由認證 授權機構和籤名實體本身聯合產生，有效的杜絕了不誠實認證授權機構的非法 操作；在應用中，籤名實體的公鑰證書是以隱式方式被驗證。在1997年Petersen 和Hoster將自認證的公鑰擴展到基於離散對數的密碼系統中，隨之也出現了很 多基於離散對數的自認證的籤名方案，但是由於離散對數的運算量比較大，計 算比較複雜，對於密鑰的選取比較麻煩，所以這類籤名方案不是十分有效，自 認證公鑰體制的優勢沒有體現出來。相對於離散對數，橢圓曲線的計算量小， 運算速度快，但遺憾的是利用橢圓曲線構造自認證的籤名方案還沒有正式的給出盧格定義，因此需要定義基於橢圓曲線的自認證的籤名方案。
一種有效的安全假設，該安全假設是構造基於橢圓曲線的自認證的籤名方
案的安全基礎。對於構造安全的籤名方案，通常利用的是強的Diffie-Hellman 假設(strong Diffie-Hellman(SDH) assumption)和計算性Diffie-Hellman假設 (Computational Diffie-Hellman(CDH) assumption)，為了構造一種安全有效的 基於橢圓曲線的自認證籤名方案，本發明給出了一種新的，可證明安全的假設， 我們稱它為強的Diffie-Hellman假設+可計算的Diffie-Hellman假設，該假設將 兩則安全假設相結合，利用可計算的Diffie-Hellman假設的困難性，說明與所 構造假設的困難性介於熟悉的兩假設之間，是構造安全有效的基於橢圓曲線的 自認證的籤名方案的有效工具。
一種有效的基於橢圓曲線的自認證密鑰產生方法。通常情況下，籤名實體 的私鑰只有自己知道，並且由私鑰所產生的公鑰是一個隨機的字符串，不便於 記憶，並且該公鑰需要一個權威認證機構來進行認證。隨著電子商務與Internet 技術的發展，計算能力小、帶寬與內存有限的行動裝置和便攜設備日益得到普 及，如何設計有效的籤名技術和簡化複雜的管理越來越迫切.1991年Girault的 文章"Self-certified public keys(自認證公鑰)"被發表在Pro. of the Eurocrypt，94， 491-497，提出了自認證公鑰的構造及產生，但對於私鑰的產生及如何構造基於 橢圓曲線的自認證私鑰，沒有給出具體的描述。自認證籤名系統，不僅可以簡 化對公鑰證書的管理和刪除密鑰託管問題，而且也可以減少驗證者對籤名驗證 的計算量。而橢圓曲線密碼具有在同等安全強度下，籤名長度短特點;因此， 我們需要構造一種安全有效的基於橢圓曲線的自認證密鑰的方法。
一種有效的自認證籤名系統，即一個籤名實體利用私鑰對消息M產生籤 名，而驗證者可以利用用戶的身份ID和權威認證中心的公鑰Pea來對這個消 息籤名進行驗證。1997年Petersen和Hoster將自認證的公鑰擴展到基於離散對 數的密碼系統中，文章 "Self-certified keys-concept and application(自認證的密鑰-概念和應用)"發表在Pro. of the Communication and Multimedia Security'97, 102-116。但與橢圓曲線相比，離散對數的計算量，運算速度都不理想，該籤名 方法可以使籤名實體在認證授權機構的幫助下，獲得有效的籤名密鑰，並實現 對消息完的籤名。但是，還未出現基於橢圓曲線的自認證的籤名方案的形式化 定義，因此，需要一種基於橢圓曲線的自認證的籤名方法。
一種有效的聚合籤名方法，即籤名實體對多條消息籤名，驗證者可以對這 些消息籤名進行同時驗證而不是分別驗證。目前存在著許多籤名方案，但這些 方案都不同程度的存在缺陷，比如，驗證者對對多個消息籤名驗證時，籤名的 長度會隨著消息籤名的增加而變大，計算量，運算負擔也相應變大等。需要一 種能夠滿足驗證者能夠對多條消息籤名驗證的籤名方法。因此，需要一種有效 的基於橢圓曲線的自認證的聚合籤名方法。
一種基於橢圓曲線的在線/離線自認證籤名方法，能夠在線/離線狀態下， 為籤名實體產生消息籤名的籤名方案。在實際應用中，在線時間比籤名時間重 要，並不是所有籤名過程都是在線狀態下完成的，如果能夠在離線狀態下，仍 能完成籤名，則可以極大的提高籤名效率，節省不必要的浪費。2001年A. Shamir, Y. Tauman的文章"Improved online/offline signature schemes(改進的在線/離線 籤名方案)"發表在Advances in crypt，2001, 355-367。然而，基於橢圓曲線的， 能夠在/離線狀態下同時完成自認證籤名的方法卻沒有出現。因此，需要一種基 於橢圓曲線的在線/離線自認證的籤名方法，在/離線狀態下都可以對消息進行 處理，產生自認證籤名的籤名方法。
因此，本發明的目的之一是提供一種有效的SDH+CDH假設。本發明的 目的之二是提供一種有效的基於橢圓曲線的自認證籤名方法。本發明的目的之 三是提供一種有效的，基於橢圓曲線的自認證的聚合籤名方法。本發明的目的 之四是提供一種基於橢圓曲線的在/離線自認證籤名方法。 一種困難性低於 Computational Diffie-Hellman(CDH) Assumption而高於q-Strong Diffie-HellmanAssumption的新的假設q-SDH+CDH Assumption,該假設具體內容包括 選取定義的第一個循環群Gi;
選取第一個循環群G'中的一個q元數組化(…，g^和一個數組^，g「、； 利用q-SDH Assumption和CDH Assumption假設來選取^^ z;，使得在
多項式時間內以不可忽略的概率找到^^，。是不可能的。
.一種基於橢圓曲線的，產生關於消息M的自認證籤名Sig的方法以及驗 證， 一個籤名實體對消息M產生籤名^，最後， 一個驗證者利用驗證算法對該 籤名^進行驗證，具體內容包括
在系統初始化階段，選取第一循環群G'和第二循環群A (階數均為大素數
P);
選取一個非退化的雙線性對映射e，滿足能夠由G'中的兩個元素映射到《 中的一個元素；
選取第一循環群G，的生成元g;
隨機選取模p的剩餘類Zp中的一個元素"作為CA的私鑰，並且產生^ 作為CA公鑰；
用戶隨機選取模p的剩餘類Zp中的一個元素^"^，…，"M乍為"的部分私 鑰，並且產生C^ = g" ，& = g('〉作為籤名實體R的部分公鑰；
選取第一哈希函數"'，能由第一串二進位數產生第一循環群Gi中的一個元
素；
選取第二哈希函數A，.能由第二串二進位數產生剩餘類^中的一個元素； 選取第三哈希函數H，能由第三串二進位數產生剩餘類&中的一個元素；
權烕授權中心CA和用戶"進行交互操作來產生用戶"'來產生用戶的私 鑰。當CA接收到用戶"'發送來的信息(IDi,Pi)， CA禾擁它的公鑰和(IDi，Pi) 作為第一哈希函數值的輸入來計算^=//1(^，^，。，然後再利用它的私鑰來產生用戶的部分私鑰《=(W/aW')並返回給用戶"-。
當用戶"'接收到部分私鑰《以後，禾u用w，^，w)通過下面的等式來驗
證"'的部分私鑰《的有效性 e(仏g,.叫),，g)。
最後，籤名實體"'的私鑰為"，化其中(1=1，2，"'，11);
在籤名階段，為了產生對消息M的籤名，用戶"'通過自認證籤名算法來
產生一個籤名。具體如下
1. 隨機選取模p的剩餘類Zp中的一個元素S;
3.產生消息M的自認證的籤名sig-^，W
在籤名驗證階段，把sig-W，^和消息M作為驗證裝置的一個輸入，該驗證
裝置工作如下
1、驗證用戶公鑰"的真實性，步驟為通過確認《，U—^，=,，力來 驗證公鑰的真實性；
2、 通過確認《,，"，W = ,A岸2^f"'。:n來驗證自認證籤名Sig=W ，W 的有效性。
一種基於橢圓曲線的，產生關於消息的自認證聚合籤名Sig的方法以及驗 證，籤名實體可以對不同的消息進行籤名，最後把這些消息籤名聚合生成最終 籤名，在驗證時，驗證者只要驗證聚合所得到的籤名，就意味著所有的消息籤 名是正確的，通過該方法可以使籤名驗證的計算量和速度比較所有單個消息籤 名的驗證有很大提高，且聚合後的籤名長度比所有單個籤名的長度明顯縮短， 該系統包括
一個認證授權機構和籤名實體進行一個交互操作來籤名實體的籤名密鑰； 籤名實體利用所產生的籤名密鑰按照上面的自認證加密籤名方法來對不同消息產生籤名。最後，籤名實體把對不同消息產生的籤名聚合成一個最終的籤名。 當一個驗證者驗證幾個不同消息的聚合籤名時，他利用預先選定的雙線性 對映射和選定的哈希函數來驗證聚合籤名的有效性，如果該聚合籤名滿足驗證 等式，這就意味著這幾個不同消息的籤名是有效的。
一個可以由一個籤名實體，對一個消息M產生籤名的offline/online系統， 該系統分為在線和離線兩個階段。該籤名實體在離線(offline)狀態下，完成 籤名的主要運算過程；在在線狀態下，籤名實體基於離線狀態下的計算結果， 使用較少的計算量來產生消息M籤名。該系統包括
一個認證授權構和籤名實體進行交互操作，產生籤名實體的籤名密鑰，每 個籤名實體對應各自的不同籤名密鑰，籤名實體與認證授權機構共同產生籤名 實體的籤名私鑰；
一個與認證授權機構，籤名實體相互傳遞的處理器，該處理器能夠利用預 先選定的哈希函數，認證機構或者籤名實體的輸入生成一個函數值，並且利用 該函數值和籤名實體的私鑰，相關公鑰生成籤名實體的自認證籤名；而且，該 處理器能夠在離線狀態下，隨機的選擇秘密信息和一個隨機數，利用預先選定 的函數，籤名實體的私鑰，生成一個離線籤名，在在線籤名階段，該處理器能 夠使用在離線狀態下所生成的離線籤名與待籤消息M，共同生成一個在線自認 證籤名；
一個與籤名驗證者相互傳遞的處理器，該處理器能夠利用預先選定的雙線 性對映射，選定的哈希函數，上面處理器生成的在線自認證籤名進行驗證，如 果通過驗證，確定該籤名的真實性。

發明內容
本發明給出了可靠的理論基礎，提出了安全，有效且快速的密鑰，籤名產 生方法。本發明的目的在於提出一種新的有效橢圓曲線自認證籤名方法。該籤名方 法基於橢圓曲線離散對數問題，該問題具有高複雜性，因而具有單位安全強度 更高的特定，可大大縮短具有相同安全強度的數字籤名長度，加快籤名速度。
本發明的內容之一 ，提出了有效的SDH+CDH假設。利用解決強SDH和CDH 假設的困難性，將兩者的困難性相結合，構造了有效的SDH+CDH假設。在多 項式時間內解決SDH假設的概率是可以忽略的，在多項式時間內解決CDH假設 的概率也是可以忽略的，由於提出假設的困難性低於解決CDH假設，而高於解 決SDH假設，得知在多項式時間內解決SDH+CDH假設的概率也是可以忽略的。 利用SDH+CDH假設，可以產生有效的基於橢圓曲線的自認證籤名方案，構造 方案的安全模型和安全性證明。
本發明的內容之二，提出了一種有效的基於橢圓曲線的自認證密鑰產生方 法。傳統的公鑰系統中，用戶的私鑰可以自己產生或由一個認證機構產生，然 後，生成相應的公鑰，這個公鑰是一個隨機的字符串， 一般不容易記憶；同時 相應的公鑰需要一個認證機構來認證該公鑰的有效性。因此，帶來的問題是 當驗證籤名時，驗證者首先需要公鑰的有效性，然後，再利用該公鑰來驗證籤 名的有效性。顯然，不適合目前流行的低計算、低計算的行動裝置。本發明中
籤名實體的私鑰只能在認證授權機構的幫助下才能完成。具體如下產生第一
循環群和第二循環群，選出一個非退化的雙線性映射，使得由第一循環群中的 兩個元素能夠得到第二循環群中的一個元素。選出第一循環群的生成元，並產
生第二循環群的生成元。隨機選取剩餘類Zq中一個的元素，生成認證授權機構 的密鑰。籤名實體在剩餘類Zq中隨機選擇一個數作為部分私鑰，並產生相應的 部分公鑰，認證授權機構利用它的私鑰、籤名實體的身份和第一，第二哈希函 數，生成籤名實體的另外的部分私鑰，最後，籤名實體可以將兩部分密鑰合在 一起，產生籤名密鑰。本發明的內容之三，提出了一種有效的基於橢圓曲線的自認證籤名的方 法。具體如下產生第一循環群和第二循環群，選出一個非退化的雙線性映射， 使得由第一循環群中的兩個元素能夠得到第二循環群中的一個元素。選出第一 循環群的生成元，並產生第二循環群的生成元。隨機選取剩餘類Zq中一個的元 素，生成認證授權機構的密鑰。籤名實體選取的部分私鑰，產生相應的部分公 鑰，認證授權機構利用它的私鑰、用戶的身份和第一，第二哈希函數，生成籤 名實體的另外的部分私鑰。籤名實體利用籤名私鑰，選擇隨機數、利用哈希函 數和自己的身份與認證授權機構的公鑰來對消息進行籤名。自認證籤名可以通 過非退化的雙線性映射，認證授權機構的公鑰和籤名實體的身份，以及哈希函 數來完成籤名的驗證。
本發明的內容之四，提出了一種有效的基於橢圓曲線的，聚合的自認證籤 名方法。籤名實體利用籤名密鑰對不用的消息進行籤名，然後，把這些不同的 消息籤名聚合起來，生成一個聚合籤名。然後，該聚合籤名可以通過非退化的 雙線性映射，認證授權機構的公鑰和籤名實體的身份，及選定的哈希函數來完 成籤名的驗證。
本發明的內容之五，提出了一種基於橢圓曲線的在/離線自認證的籤名方 法，能夠在/離線狀態下，為籤名實體產生消息籤名。利用預先選定的函數，認 證機構或者籤名實體的輸入生成消息函數值，並且利用消息函數值和籤名實體 的私鑰，認證授權機構的公鑰生成籤名實體的自認證籤名；在線時間通常比籤 名時間更重要，離線狀態下，隨機的選擇秘密信息和一個隨機數，隨機選擇一 條消息，利用預先選定的函數，籤名實體的私鑰生成一個離線籤名，在以後的 處理中，該處理器能夠在在線狀態下，能夠利用識別出與所給消息相匹配的籤 名中所包含的隨機數來認證。因此，需要一種基於橢圓曲線的在/離線自認證的 籤名方法，來完成對消息籤名的籤名方法。


圖l是一張流程圖，該圖介紹了本發明的內容之二的操作過程，描述了如
何產生一種有效的基於橢圓曲線的自認證密鑰的方法；
圖2是一張流程圖，該圖介紹了本發明的內容之三的操作過程，描述了如
何產生一種有效的基於橢圓曲線的， 一個籤名實體對一條消息進行自認證籤名
的方法；
圖3是一張流程圖，該圖介紹了本發明的內容之四的操作過程，描述了如 何產生一種有效的基於橢圓曲線的，自認證的聚合籤名方法；
圖4是一張流程圖，該圖介紹了本發明的內容之五的操作過程，描述了如 何產生一種基於橢圓曲線的在/離線自認證的籤名方法；
圖5是本發明的籤名裝置的方框圖。
具體實施例方式
本發明所提出的基於橢圓曲線的自認證的籤名方法，能夠提供安全，快速， 簡潔而且有效的籤名方法，通過對籤名實體的籤名密鑰設置，防止了籤名權利 的外延。本發明提出的基於橢圓曲線的自認證的籤名方法，根據不同的籤名實 體，籤名消息，可以擴展到滿足一對多的聚合籤名，即一個籤名實體對不同消 息進行自認證籤名，然後，把這些消息籤名聚合成一個籤名的方法；為了提高 在線籤名的速度，給出了一種在/離線自認證消息籤名方法。
本發明的基於橢圓曲線的自認證的籤名方法，在用戶的部分私鑰產生中需 要一個認證授權機構CA。籤名實體在產生籤名密鑰的過程中，與該認證授權機 構交互傳遞，籤名實體選擇一個剩餘類Zp中的隨機數作為自己的部分籤名私 鑰，認證授權機構利用籤名實體的身份，部分公鑰等特殊信息，產生籤名實體 的另外部分籤名私鑰，籤名實體將兩部分私鑰結合，得到有效的籤名私鑰。本 發明中的認證授權機構不在是一個完全信任機構，籤名實體的私鑰不再有它完 全產生，它也不能偽造籤名實體的籤名。本發明提出的基於橢圓曲線的自認證的籤名方法包括4個步驟建立模型， 密鑰產生，籤名，以及驗證。離線狀態下的籤名步驟則還需要選取隨機信息和 識別匹配數兩個步驟。
在建立模型中，該算法輸入安全參數ik，認證授權機構CA選取秘密參數作 為私鑰，並用來產生公共參數params,包括第一循環群生成器，哈希函數，雙 線性映射函數和公鑰。私鑰的產生只有認證機構CA知道，參數params是公開的。
在密鑰產生中，籤名實體選取自己的部分私鑰，並生成相應的部分公鑰。 籤名實體將身份信息，部分公鑰傳遞給認證授權機構，認證授權機構利用哈希 函數，經過處理，得到籤名實體的另一部分私鑰，傳遞給籤名實體，通過驗證， 籤名實體確定私鑰的真實性，產生籤名私鑰。
在籤名過程中，籤名實體選取一秘密參數，利用第一循環群生成器，自己 的身份信息，公共參數，哈希函數產生部分籤名，利用該部分籤名和消息得到 消息函數，再籤名私鑰對消息函數籤名得到另一部分籤名，將兩部分籤名合產 生籤名消息的自認證籤名。
在驗證過程中，利用哈希函數值，對公共參數params和消息進行處理，得 到消息函數值。驗證生成參數，消息函數值，自認證籤名等是否滿足驗證等式， 得到結論"接受"(籤名有效)或者"拒絕"(籤名無效)。
橢圓曲線
本發明的高效性是基於橢圓曲線上的運算簡潔性。本發明提出的籤名方法 是基於橢圓曲線的，利用橢圓曲線上的對，比如Tate對和Weil對，來進行運算。 本發明利用兩個階為大素數q的循環群， 一個是橢圓曲線或阿貝爾族上點的加 法群G"它的生成器是g;另一個是有限域上的乘法群G"兩個循環群之間存 在一種雙線性映射函數"GixGi—《，將加法群Gi中的兩個元素映射到乘法群《
中的一個元素。要求該函數滿足首先，雙線性的，對於G'中的元素U， V，整 數a， b，滿足《力^(",v";其次，非退化的，即對於G,中的元素g，滿足々,力"；再次，可計算的，對於G'中的元素U， V，存在有效的算法計算""'"。除了上面 的三個要求，該函數還應該是對稱的，即""，"^""、橢圓曲線上點的運算， 橫縱坐標互相交換的兩點，滿足對稱性，在橢圓曲線上得到的映射點是相同的。
強的Diffie-Hellman +可計算的Diffie-Hellman假設。
本發明的安全性基於強的Diffie-Hellman假設-strong Diffie-Hellman(SDH) assumption和可計算的Diffie-Hellman假設-Computational Diffie曙Hellman(CDH) assumption,其中，前者定義在W，GJ中，& ， &分別是^和《的生成器，給出
一個q+2元數組化，&，《…，gO，對於未知整數c，求出^^，。；後者定義在G'上， g'是^的生成器，給出g" g。對於未知整數x， y，求出^。對於上面的兩種 假設，本發明提出了 一種新的假設強的Diffie-Hellman假設+可計算的 Diffie-Hellman假設。該假設在困難性上，介於強的Diffie-Hellman假設和可計算 的Diffie-Hellman假設之間。該假設同樣定義在G'上，&是《的生成器，給出一
個q元數組^，g'"…，^—、和2元數組^，g。，對於整數c， r，求出((《^，。。如果強 的Diffie-Hellman +可計算的^伍6-1^1111^11假設可以在多項式時間內解決，令 q-2，則該假設轉化為可計算的Diffie-Hdlman假設，說明可以在多項式時間內 解決可計算的Diffie-HeUman假設。實際上可計算的Diffie-Hellman假設等價於求 逆運算，在多項式時間內是不能解決的。因此，提出的強的Diffie-Hdlman+可 計算的Diffie-Hellman假設也同樣不能在多項式時間內，以不可忽略的概率解 決。
如上所述，提出的強的Diffie-Hellman+可計算的Diffie-Hellman假設，定義
在循環加群Gi上，gi是Gi的生成器，輸入一個q元數組^，g'"…，gf、和2元數組
W，g。，對於整數c， r，輸出((&'^，。。輸出結果的概率，決定於g'， c， r選取 的任意性，以及概率算法A。如果一個概率算A法能夠在多項式時間輸出所要 的值，則該算法能以不可忽略的概率解決強的Diffie-Hellman +可計算的Diffie-Hellman假設。但提出的假設，本質上等價於可計算的Diffie-Hellman假設， 而可計算的Diffie-Hellman假設的困難性基於離散對數的求逆問題。離散對數的
求逆問題，定義在循環加群Gi上，g'是G，的生成器，輸入gi'，對於未知整數x， 輸出x。在任意的多項式時間內，不能以不可忽略的概率解決離散對數的求逆 問題，能夠得出，不能以不可忽略的概率在多項式時間內解決可計算的 Diffie-Hellman假設，因此不能以不可忽略的概率在多項式時間內解決強的 Diffie-Hellman +可計算的01卩66- ^11!^11假設。該假設是構造基於橢圓曲線的自 認證籤名方案的理論基礎。由於該假設的困難性，本發明提出的基於橢圓曲線的 自認證籤名方案是安全的。
基於橢圓曲線的自認證密鑰產生方法
在傳統的PKI框架下，籤名私鑰的選取，通常情況下，是籤名實體秘密選 取，然後生成相應的公鑰，並由一個認證機構對該公鑰進行認證，或者，由某 個認證授權機構產生一對公/私鑰，把私鑰返回給用戶，並對公鑰進行認證。這 種私鑰產生方法給公鑰管理以及籤名的驗證帶來一系列的麻煩。在基於身份的 體制下，用戶的私鑰是由一個可信機構來產生，因而，存在著密鑰託管問題。 為了解決傳統公鑰體制和基於身份公鑰體制下，密鑰產生所帶來的問題，我們 研究自認證的密鑰產生方法，籤名實體只能產生部分私鑰，而另一部分，由認 證授權機構對用戶的身份和部分公鑰產生一個BBS籤名作為部分私鑰，最後， 將兩部分私鑰結合在一起，構成籤名私鑰。籤名實體無法單獨產生有效的籤名 私鑰，認證授權機構的引入，將使得用戶的公鑰在籤名驗證時以隱式形式進行 研究。
下面結合圖l來說明基於橢圓曲線的自認證籤名密鑰的具體產生方法。圖l 給出的是一張流程圖，描述了包括籤名密鑰產生及驗證等各個步驟。籤名實 體的信息，作為哈希函數的輸入，傳遞給認證授權機構，產生部分籤名私鑰。 本方法的核心是步驟106和步驟110:步驟106中，籤名實體任意選取部分私鑰；步驟110中，認證授權機構生成籤名實體的另一部分私鑰，兩部分結合產生籤 名私鑰。
步驟101中，產生兩個階數同為大素數q的，第一循環加群G'和第二循環乘
群G"
步驟102中，選取G'的生成元為g;
步驟103中，選取一個非退化的雙線性映射函數e，可以將Gi中的兩個元素 映射到《的元素；
步驟104中，認證授權機構選取秘密整數"作為其私鑰；步驟105中，認證
授權機構產生其公鑰^=^;
步驟106中，籤名實體R任意選取整數^"A…，，i-l，2，)作為其部分私鑰， 不同的籤名實體選取的整數各不相同，不同的籤名過程，同一籤名實體選取的 整數也不同；
步驟107中，籤名實體產生部分公鑰^C^^^g力，部分籤名私鑰的不同， 使得部分公鑰也不相同；
步驟108中，選取第一，第二哈希函數，第一哈希函數能夠由一串二進位 數產生第一循環群中的元素，第二哈希函數能夠由一串二進位數產生一整數；
步驟109中，第一哈希函數巧由認證授權機構的公鑰^，籤名實體的身份 /D'，部分公鑰e組成的一串二進位數產生G'中的元素^。-A(^^，^'^);
步驟110中，利用步驟109中得到的元素，認證授權機構的私鑰"，第二哈
希函數仏產生籤名實體的另一部分私鑰formula see original document page 20認證授權機構將該私鑰 傳給籤名實體，後者將兩部分私鑰結合生成籤名私鑰"，W ;
步驟111中，利用雙線性對映射e，驗證等式formula see original document page 20滿足 驗證等式的私鑰對，籤名實體認為是有效的，接受，否則，拒絕。 基於橢圓曲線的自認證籤名的方法基於橢圓曲線的自認證籤名，就是一個籤名實體對消息籤名。本發明提出 的方法，能夠結合橢圓曲線的運算的高效性，簡單的認證，解決了密鑰託管問 題和公鑰複雜管理問題，同時，本方法的安全性和可行性是基於強的
Diffie-Hellman +可計算的01(56-1^111^11假設的困難性。
下面結合圖2來說明基於橢圓曲線的自認證籤名的生成方法。圖2給出的是 一張流程圖，描述了自認證籤名產生的具體步驟。本方法的核心是步驟210和 步驟213:步驟210，籤名實體將選擇的部分私鑰和由認證授權機構產生的另一 部分私鑰結合，產生籤名私鑰；步驟213，籤名實體利用籤名私鑰，消息的第 三哈希函數值，產生自認證的籤名。
步驟201，產生兩個的循環群，第一個為加群G'，第二個為乘群《，階數 都是大素數q;
步驟202，選取Gi的生成元g，然後再隨機選擇群G'中的兩個元素^，^e^作 為公開參數；
步驟203，選取一個非退化的雙線性映射e，可以將G'中的兩個元素映射到G2
中；
步驟204，認證授權機構選取秘密整數"作為其私鑰。
步驟205，認證授權機構利用其私鑰產生其公鑰^ =gn;
步驟206，籤名實體"'任意選取整數W-"…，，i^,2,)作為其部分私鑰，不 同的籤名實體選取的整數各不相同，不同的籤名過程，同一籤名實體選取的私 鑰也不同；
步驟207，籤名實體產生部分公鑰^Cg"^^g^，部分籤名私鑰的不同， 使得部分公鑰也不相同；
步驟208，選取三個哈希函數，第一哈希函數能夠由一串二進位數產生第 一循環群中的元素，第二哈希函數能夠由一串二進位數產生一整數，第三個哈 希函數能夠由一串二進位數產生一整數；步驟209中，第一哈希函數w'由認證授權機構的公鑰&，籤名實體的身份 /Z)-，部分公鑰《組成的一串二進位數產生^中的元素 =//1(屍 //),^);
步驟210，利用步驟209得到的元素，認證授權機構的私鑰"，第二哈希函
數^產生籤名實體的另一部分私鑰"'=W^("^')，認證授權機構將該私鑰傳給 籤名實體，後者將兩部分私鑰結合生成籤名私鑰"，"入-
步驟211，利用雙線性對映射e，驗證等式e(《，^gW"'")X^g)是否成立， 如果等式成立，籤名實體認為是有效的，接受，否則，拒絕；
步驟212和213，籤名實體分三層來進行籤名。第一層，籤名實體隨機選取 一整數s，籤名實體利用認證授權機構公鑰&，第二哈希函數A，籤名實體身
份信息氣籤名實體的部分公鑰《，生成前籤名^^y";第二層，籤名 實體，利用前籤名、籤名消息M，籤名實體的部分公鑰、生成消息的哈希 值^聯'，A/，/^;第三層，籤名實體利用消息哈希值m，利用籤名私鑰"力，第
一和第二哈希函數A， A，籤名實體身份信息化，籤名實體的部分公鑰《，生 成前籤名《《'"^(^')r，將前籤名和後籤名合在一起，生成消息M的籤名
步驟214，任意的驗證實體，可以通過籤名實體的公鑰、身份信息嗎， 籤名消息M，來驗證籤名5的真實性。首先，計算^柳,力和^-巧^，嗎^);
其次，驗證等式^y'),《)-^，。瓶,(w，)是否成立，成立，則認
為自認證籤名有效，接受，否則，拒絕。 基於橢圓曲線的自認證聚合籤名的方法
基於橢圓曲線的自認證聚合籤名，就是籤名實體對不同消息的籤名，然後 將這些不同的消息籤名聚合成一個籤名的方法。在籤名的過程，類似於上面的 自認證籤名方法，籤名實體首先利用自己的籤名密鑰對不同的消息進行籤名， 然後，通過聚合方法把這些不同消息的籤名聚合成一個長度相對短的籤名；在驗證時，驗證者只要對聚合後的籤名有效進行驗證，如果成立就意味著這些不 同的籤名是有效的。從而，在籤名的長度和驗證的計算量上有較大的縮減。
下面結合圖3來說明基於橢圓曲線的自認證聚合籤名的生成方法。圖3給出 的是一張流圖，描述了籤名實體對消息的自認證聚合籤名產生的具體步驟。本 方法的核心是步驟314，利用籤名實體對不同的消息生成自認i疋的籤名，將這 些消息籤名結合產成一個自認證聚合籤名。
步驟301，產生兩個的循環群，第一個為加群G'，第二個為乘群《，階數 都是大素數q;
步驟302，選取G'的生成元g，然後再隨機選擇群G'中的兩個元素^^eG"乍 為公開參數
步驟303，選取一個非退化的雙線性函數e，可以將G'中的兩個元素映射到《
中；
步驟304，認證授權機構選取秘密整數"作為其私鑰，在不同的籤名過程中， 選取的秘密數不同；
步驟305 ，認證授權機構產生其公鑰& =,;
步驟306，籤名實體任意選取整數W"^，…，"M乍為其部分私鑰，不同的籤名 實體選取的整數各不相同，不同的籤名過程，同一籤名實體選取的私鑰也不同；
步驟307，籤名實體產生部分公鑰^W^^，^-s^，部分籤名私鑰的不同， 使得部分公鑰也不相同；
步驟308，選取三個哈希函數，第一哈希函數能夠由一串二進位數產生第 一循環群中的元素，第二哈希函數能夠由一串二進位數產生一整數，第三個哈 希函數能夠由一串二進位數產生一整數；
步驟309，第一哈希函數巧由認證授權機構的公鑰^，籤名實體的身份嗎，
部分公鑰S組成的一串二進位數產生G'中的元素^。-A(P"，m'^);步驟310，利用步驟309中得到的元素，認證授權機構的私鑰"，第二哈希
函數^產生籤名實體的另一部分私鑰《，認證授權機構將該私鑰傳 給籤名實體，後者將兩部分私鑰結合生成籤名私鑰"，W ;
步驟3U，利用函數e，驗證等式e"，^g—W2(/^')) = e(^^，如果等式驗證成 立，籤名實體認為是有效的，接受，否則，拒絕；
步驟312和313,聚合籤名的過程分為三層。第一層，籤名實體任意選取一 整數、籤名實體利用認證授權機構公鑰的&，第二哈希函數A，籤名實體身 份信息化，籤名實體的部分公鑰、生成前籤名^-(P"^"'^";第二層，籤 名實體利用前籤名&，籤名消息M。
籤名實體的部分公鑰《，生成消息的哈希值^-W(《)，M'，《)；第三層，籤 名實體利用消息哈希值"'，利用籤名私鑰"，W，第一和第二哈希函數w'， A，
籤名實體身份信息氣籤名實體的部分公鑰、生成後籤名^^^2^(^'))""'，
將前籤名和後籤名合在一起，生成消息^'的籤名《=(《'，《2);
步驟314，對於n個消息的籤名WA，…A)，其中滿足《=^，。。籤名實體
的聚合過程如下首先，計算S^'1，接著，對於 1，2，…， 籤名實體計
一 TT 5附'
算m,/Z(^M'^);最後，計算'2 。那麼，所產生的聚合籤名就是WA)。
由此，我們可以看出，我們的聚合籤名長度僅僅是n個籤名長度的l/n。當驗證 者需要驗證該聚合籤名的有效性時，只需要驗證等式
e(PC(^')，^"^。"械，W"))是否成立。如果成立就意味這該聚合籤名
是有效的。從聚合籤名的驗證我們知道，該聚合籤名的驗證僅僅需要3個對 (pairing)計算和l個指數運算。驗證的計算量基本上與單個籤名的驗證相等。注 對計算是橢圓曲線中最耗時的計算。步驟315，任意的驗證實體，可以通過籤名實體的公鑰^，身份信息^，和 系統參數AA，來驗證籤名W，《)的真實性。具體驗證等式 e(PcZ(，，w"(;^)"^，W叫)是否成立，如果成立，則認為自認證聚合
籤名有效，接受，否則，拒絕。
基於橢圓曲線的在/離線自認證籤名方法
技術領域：
本發明的內容之五，提出了 一種基於橢圓曲線的在/離線自認證的籤名方法。 一般來說，籤名過程中，在線籤名要比離線籤名代價更大，帶寬的限制，計算 能力的限制，都對在線操作提出了更高的要求.，本方法能夠利用離線狀態完成 籤名的主要操作，在在線狀態下進行簡單的操作來完成消息的籤名，節省了在 線時間，提高了在線籤名的效率，並通過對所選取的與籤名消息匹配隨機數的 識別，驗證籤名的真實性。
下面結合圖4來說明基於橢圓曲線的在/離線自認證籤名的生成方法。圖4給 出的是一張流程圖，描述了在/離線狀態下產生自認證籤名的過程。本方法的核 心是步驟412和步驟和步驟414。
步驟412中，認證授權機構隨機的選擇秘密信息和一隨機數，利用預先選定 的函數，籤名實體的私鑰，生成一個離線籤名；步驟414中，在在線狀態下， 利用離線籤名，識別出與所給消息相匹配的籤名中所包含的隨機數，驗證籤名 的真實性。
步驟401，產生兩個的循環群，第一個為加群G"第二個為乘群《，階數都 是大素數q;
步驟402，選取^的生成元g，然後再隨機選擇群G'中的兩個元素、&e"作 為公開參數
步驟403，選取一個非退化的雙線性函數e，可以將G!中的兩個元素映射到G2
中；
步驟404，認證授權機構選取秘密整數"作為其私鑰；步驟405，認證授權機構產生其公鑰^=^;
步驟406，籤名實體任意選取整數W'、^，…，"M乍為其部分私鑰，不同的籤名
實體選取的整數各不相同，不同的籤名過程，同一籤名實體選取的私鑰也不同;
步驟407，籤名實體產生部分公鑰爪&=^，^=^、部分籤名私鑰的不同， 使得部分公鑰也不相同；
步驟408，選取三個哈希函數，第一哈希函數能夠由一串二進位數產生第一 循環群中的元素，第二哈希函數能夠由一串二進位數產生一整數，第三個哈希 函數能夠由一串二進位數產生一整數；
步驟409中，第一哈希函數巧由認證授權機構的公鑰&，籤名實體的身份^，
部分公鑰S組成的一串二進位數產生G中的元素^-A^"7A^);
步驟410中，利用步驟409中得到的元素，認證授權機構的私鑰"，第二哈
1
希函數&產生籤名實體的另一部分私鑰"'- W^2^")，認證授權機構將該私鑰 傳給籤名實體，後者將兩部分私鑰結合生成籤名私鑰"，"；
步驟4U，利用函數e，驗證等式"《，&g—""WXA)，g;)是否成立，如果等 式成立，籤名實體認為是有效的，接受，否則，拒絕；
步驟412，選取n和n'，並令籤名信息w'和M分別為M'， M = g"，籤名私 鑰"，"，以及隨機數。其中的信息m'不同於M;
步驟413，利用選取籤名私鑰進行離線籤名，分別生成前籤名《—^,(^，， 消息函數m =，',M'gv'。，以及後籤名《=(W(W)廣；
步驟414，籤名實體需要找出一隨機數r，要使得^g'、嶺 即s"""g，，
可以在在線狀態下的求出""7，將得到的隨機數r，消息M，籤名一起傳遞 給籤名驗證實體。步驟415中，首先，計算附'=/^1 ^)和/^//,0^,/0,";其次，驗證等式
《,，")，w-^，o啦，W)r是否成立，成立，則認為自認證籤名有
效，接受，否則，拒絕。其中的步驟414，僅僅需要簡單加法與乘法，所以計 算效率非常高。
圖5表示了本發明的籤名和驗證籤名裝置。
以上所述，僅為本發明較佳的具體實施方式
，但本發明的保護範圍並不局 限於此，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易 想到的變化或替換，都應涵蓋在本發明的保護範圍之內。因此，本發明的保護 範圍應該以權利要求的保護範圍為準。
權利要求
1、一種基於橢圓曲線的自認證私鑰產生及驗證方法，一個公認的認證機構CA，和一個籤名實體之間進行的，其中的籤名實體Ui(i＝1，2，…，n)是一個集合，籤名實體對應的身份信息集合為IDi(i＝1，2，…，n)，其特徵在於該方案具體內容如下在橢圓曲線上，選取第一循環群G1和第二循環群G2(階數均為大素數p)；選取一個非退化的雙線性對映射e，滿足能夠由G1中的兩個元素映射得到G2中的元素；選取第一循環群G1的生成元g；隨機選取模p的剩餘類Zp中的一個元素α作為CA的私鑰，並且產生PCA＝gα作為CA公鑰；隨機選取模p的剩餘類Zp中的一個元素xi(i＝1，2，…，n)作為Ui的部分私鑰，並且產生作為籤名實體Ui的部分公鑰；選取第一哈希函數H1，能由第一串二進位數產生第一循環群G1中的一個元素；選取第二哈希函數H2，能由第二串二進位數產生剩餘類Zp中的一個元素；產生一個第一哈希函數值h0＝H1(PCA，IDi，Pi)，並利用它產生生成的籤名實體Ui的私鑰為(xi，di，其中(i＝1，2，...，n)；驗證私鑰的真實性，是否接受決定於下面的驗證過程，步驟為確認
2、 根據權利要求l所述的方法，其特徵在於所述第一循環群^是超奇異橢圓曲線或阿貝爾族上的點的加法群，所述第二循環群《則是有限域上的乘法群；所述映射e是一種可行的雙線性對映射。
3、 根據權利要求l-2任一項所述的方法，其特徵在於， 秘密選取認證機構0八的私鑰"和籤名實體"'的私鑰^,(1=1，2,...,11)，產生& =,和= Z' A = f)作為各自的公鑰和部分公鑰；函數值^是利用^，化力的輸入，由第一哈希函數巧產生的； 籤名實體的部分私鑰《是利用"A，d〃^的輸入產生的，並且，籤名實體"的私鑰還包括確認eW，屍c^^"'叫)=e(心力。
4、 一種基於橢圓曲線的，產生關於消息M的自認證籤名Sig的方法以及驗證 方法，該消息M是由一個籤名實體來完成籤名，最後，任何人可以對該籤名Sig 進行驗證，其特徵在於，具體內容包括選取第一循環群Gi和第二循環群G2 (階數均為大素數p);選取一個非退化的雙線性對映射e，滿足能夠由Gi中的兩個元素運算得到《 中的元素；選取第一循環群G'的生成元g和兩個隨機元素&，、隨機選取模p的剩餘類zp中的一個元素"作為CA的私鑰，並且產生& = 作為CA公鑰；隨機選取模p的剩餘類Zp中的一個元素W"W，…，"M乍為"'的部分私鑰，並且產生爪A = Z' A = g"—'〕作為籤名實體"'的部分公鑰；選取第一哈希函數《，.能由第一串二進位數產生第一循環群G，中的一個元素；選取第二哈希函數仏，能由第二串二進位數產生剩餘類Zp中的一個元素； 選取第三哈希函數H，能由第三串二進位數產生剩餘類Zp中的一個元素；產生一個第一哈希函數值、-A(^，嗎，。，並利用它產生《=/^ ;生成籤名實體"'的私鑰為"，化其中^l,2，…,n);為了對消息M進行籤名，籤名實體隨機選取模p的剩餘類；中的一個元素s，並通過下面算法來計算消息M的籤名；KAV"r， ipy'"，其中最後，生成消息M的自認證的籤名為Sig-W，W;為了驗證消息M的有效性，任何人可以通過檢査籤名sig=(《，W是否滿足下面等式通過確認^^,'，^ = 一。，。 ^2(^'))、驗證自認證籤名 Sig 2)。
5、根據權利要求4所述的方法，其特徵在於 所述第一循環群G'是超奇異橢圓曲線或阿貝爾族上的點的加法群，所述第 二循環群G2則是有限域上的乘法群；映射e是一種可行的單向雙線性對映射。
6、 根據權利要求4二5任一項所述的方法，其特徵在於秘密選取認證機構0八的私鑰《和籤名實體"的私鑰《(1=1，2，,..，11)，產生&=和《"==,')分別作為各自的公鑰和部分公鑰。
7、 根據權利要求4-6任一項所述的方法，其中 函數值^是利用^，嗎力的輸入，w'產生的； 籤名實體的部分私鑰《是利用^，"，^"的輸入產生的，並且，籤名實體"'私鑰(^)還包括確認《,^g"2,')) = #。，g);一部分籤名^是利用秘密選取的籤名實體"'的私有信息s，第二哈希函數A，以及認證機構的公鑰&作為輸入，由運算^^,(，y得到的；函數值m是利用消息M，籤名實體的部分公鑰《，部分籤名《，以及第三哈 希函數作為輸入，運算^^辨《'風。產生的；另一部分籤名《是利用秘密選取的籤名實體"'的私有信息s，私鑰"，《)，第二哈希函數A，函數值m，以及函數值^作為輸入，《^(v^('^r產生的，.消息M的自認證籤名是S^W，W ;通過確認e(屍C""") a) = 一。，/x《a《2(""):t來驗證籤名Sig 2)。
8、 一種採用權利要求l-7中任一項方法的裝置，包括密鑰生成器，籤名器，和籤名驗證器，用戶使用所述密鑰生成器生成公鑰Pu，私鑰du及Xu，公布 其公鑰和系統參數，使用所述籤名器利用私鑰對消息M進行籤名。
全文摘要
本發明公開了一種基於橢圓曲線的自認證籤名方法及其拓展的籤名方法，以及籤名的驗證過程。認證授權機構產生籤名實體的部分籤名私鑰，籤名實體利用自己選取的部分私鑰，結合接收的認證授權機構的私鑰，生成籤名私鑰。利用橢圓曲線，提高運算效率，並且提出了基於橢圓曲線的1-1自認證籤名方法，自認證聚合籤名方法，以及離線的狀態下生成自認證籤名的方法，這幾種方法的安全性基於提出的SDH+CDH假設。提出的若干方法不僅能夠滿足籤名協議的安全要求，而且在一定程度上能夠提高籤名效率，滿足某些特殊情況要求。
文檔編號H04L9/08GK101547099SQ20091008318
公開日2009年9月30日 申請日期2009年5月7日 優先權日2009年5月7日
發明者張鍵紅 申請人:張鍵紅