A. (p+1)(p-4)+7p+8公式法
導語
本課堂用通俗易懂的系列內容為大家呈現區塊鏈與密碼學領域相關知識。這里有知識也有故事，從感興趣到有樂趣，點寬課堂等你來學。
這個系列中的課程內容首先從比特幣著手進行入門介紹，再延伸至區塊鏈的相關技術原理與發展趨勢，然後深入淺出地依次介紹在區塊鏈中應用的各類密碼學技術。歡迎大家訂閱本公眾號，持續進行學習。
【本課堂內容全部選編自PlatON首席密碼學家、武漢大學國家網路安全學院教授、博士生導師何德彪教授的《區塊鏈與密碼學》授課講義、教材及互聯網，版權歸屬其原作者所有，如有侵權請立即與我們聯系，我們將及時處理。】
6.3
其他數字簽名演算法
EIGamal演算法
數字簽名一般利用公鑰密碼技術來實現，其中私鑰用來簽名，公鑰用來驗證簽名。ElGamal公鑰密碼演算法是在密碼協議中有著重要應用的一類公鑰密碼演算法，其安全性是基於有限域上離散對數學問題的難解性。它至今仍是一個安全性良好的公鑰密碼演算法。它既可用於加密又可用於數字簽名的公鑰密碼體制。
假設p是一個大素數，g是GF(p)的生成元。Alice的公鑰為y = gx mod p, g，p私鑰為x。
簽名演算法：
Alice用H將消息m進行處理，得h=H(m).
Alice選擇秘密隨機數k，滿足
0
計算
r=gk (mod p)
s=(h－ x · r) · k-1(mod (p－1))
Alice將(m，r，s)發送給Bob
驗證簽名過程：
接收方收到M與其簽名(r，s)後：
計算消息M的Hash值H(M)
驗證公式
成立則確認為有效簽名，否則認為簽名是偽造的
PSS演算法的編碼操作過程
上述方案的安全性是基於如下離散對數問題的：已知大素數p、GF(p的生成元g和非零元素y∈GF(p)，求解唯一的整數k, 0≤k≤p – 2，使得y≡gk (mod p)，k稱為y對g的離散對數。
在1996年的歐洲密碼學會(Proceedings of EUROCRYPT 96)上，David Pointcheval和Jacques Stern給出一個ElGamal簽名的變體，並基於所謂分叉技術證明了在隨機預言模型下所給方案是安全的(在自適應選擇消息攻擊下能抗擊存在性偽造)。
Schnorr演算法
Schnorr簽名方案是一個短簽名方案，它是ElGamal簽名方案的變形，其安全性是基於離散對數困難性和哈希函數的單向性的。
假設p和q是大素數，是q能被p-1整除，q是大於等於160 bit的整數，p是大於等於512 bit的整數，保證GF(p)中求解離散對數困難；g是GF(p)中元素，且gq≡1mod p。
密鑰生成：
Alice選擇隨機數x為私鑰，其中1
Alice計算公鑰y≡gx (mod p)
簽名演算法：
①Alice首先隨機數k，這里1
②Alice計算e=h(M, gk mod p)
③Alice計算s=k-x·e(mod q)
④Alice輸出簽名(e, s)
驗證演算法：
Bob計算gkmod p=gs·ye mod p
Bob驗證e = h(M, gk mod p)是否成立，如果成立則輸出「Accept」，否則輸出「Reject」。
Schnorr簽名與ElGamal簽名的不同點：
安全性比較：在ElGamal體制中，g為域GF(p)的本原元素；而在Schnorr體制中， g只是域GF(p)的階為q的元素，而非本原元素。因此，雖然兩者都是基於離散對數的困難性，然而ElGamal的離散對數階為p-1， Schnorr的離散對數階為q
簽名長度比較：Schnorr比ElGamal簽名長度短
ElGamal：(m，r，s)，其中r的長度為|p|， s的長度為|p-1|
Schnorr：(m，e，s)，其中e的長度為|q|， s的長度為|q|
DSA演算法
1991年，美國政府頒布了數字簽名標准(Digital Signature Standard, DSS)，也稱為數字簽名演算法(Digital Signature Algorithm, DSA) 。
和DES一樣，DSS也引起了激烈的爭論，反對者認為：密鑰太短、效率不如RSA高、不能實現數據加密並懷疑NIST在DSS中留有後門。
隨後，美國政府對其做了一些改進，目前DSS的應用已經十分廣泛，並被一些國際標准化組織採納為國際標准。2000年，美國政府將RSA和橢圓曲線密碼引入到數字簽名標准中，進一步豐富了DSA演算法。
DSA的主要參數：
全局公開密鑰分量，可以為用戶公用
p：素數，要求2L-1
q : (p-1)的素因子，2159
g : =h(p-1)/q mod p.其中h是一整數，11
用戶私有密鑰
x：隨機或偽隨機整數，要求0
用戶公開密鑰
y：=gx mod p
隨機數k
隨機或偽隨機整數，要求0
DSA簽名過程：
用戶隨機選取k
計算e=h(M)；
計算r=(gk mod p) mod q
計算s=k-1(e+x · r) mod q
輸出(r, s)，即為消息M的數字簽名
DSA驗證過程：
接收者收到M, r, s後，首先驗證0
計算e=h(M)；
計算w=(s)-1 mod q
計算u1=e · w mod q
計算u2=r · w mod q
計算①v=[(gu1 · yu2) mod p] mod q
如果v=r，則確認簽名正確，否則拒絕
DSA演算法的工作流程
今天的課程就到這里啦，下一堂課我們將學習基於橢圓曲線的數字簽名演算法，帶大家繼續了解數字簽名，敬請期待！
關注點寬學園，每周持續更新區塊鏈系列課程，小寬頻你進入區塊鏈世界。我們下節課見啦。
【區塊鏈與密碼學】課堂回顧：
FOLLOW US
© DigQuant
點擊「閱讀原文」，登錄官網www.digquant.com，一起解鎖更多金融科技姿勢：涵蓋 Python 、 金融基礎 、 量化投資 、 區塊鏈 、 大數據 、 人工智慧 。 Dig More, Learn More！