比特幣的簽名演算法

A. 區塊鏈一般概念摘要

雖然是個前端開發，但是阻擋不了我八卦各種熱門的心。下面簡單匯總下一些學習到的概念性東西。

1、區塊鏈技術隨比特幣誕生，因此先了解比特幣概念

2、比特幣是什麼

（1）、基於分布式網路的數字貨幣

3、比特系統運行原理

（1）、所有節點都會保存完整賬本

（2）、賬本保持一致性

4、區塊鏈記賬原理

hash函數在區塊鏈技術中有廣泛的運用

（1）、哈希函數hash:任何信息hash後會得到一個簡短的摘要信息

（2）、hash特點：簡化信息、標識信息、隱匿信息、驗證信息

（3）、區塊鏈記賬會把時間節點的賬單信息hash,構成一個區塊

（4）、比特幣系統約10分鍾記賬一次，即每個區塊生成的時間間隔大約10分鍾

（5）、記錄下一個賬單時，會把上一個區塊的hash值和當前賬單的信息一起作為原始信息進行hash

（6）、每個區塊都包含了之前區塊的信息，這些區塊組合成了區塊鏈

5、比特幣的所有權-非對稱加密應用

比特幣系統使用了橢圓曲線簽名演算法，演算法的私鑰由32個位元組隨機數組成，通過私鑰可以計算出公鑰，公鑰經過一序列哈希演算法和編碼演算法得到比特幣地址，地址也可以理解為公鑰的摘要。

（1）、轉賬是把比特幣從一個地址轉移到另一個地址

（2）、地址私鑰是非對稱的關系，私鑰經過一系列的運算（其中包含兩次hash），就可以得到地址，但是從地址無法得到私鑰

（3）、轉賬成功後廣播其他節點，其他節點驗證成功後再轉發到相鄰的節點，廣播的信息包含了原始的信息和簽名信息

（4）、驗證，其他節點驗證簽名信息是不是付款方用私鑰對交易原始信息簽名產生的，如果是才記錄（再驗證有足夠余額）

6、比特幣如何挖礦

（1）、完成記賬的節點可以獲得系統給予的一定數量比特幣獎勵（這個獎勵過程也就是比特幣的發行過程，因此大家把記賬稱為挖礦）

（2）、一段時間內只有一人可以記賬成功，因此需要收集沒有被收集的原始交易信息，檢查有沒有餘額、正確簽名

（3）、為了提高記賬難度，十分鍾左右只有一人可以記賬，hash結果需要若干0開頭，並且進行hash時引入隨機數變數

（4）、隨著更多礦工的加入，游戲難度越來越大，計算難度加大，電力損耗等加大，國內電力成本低，中國算力占整個網路的一半以上

（5）、網路中只有最快解密的區塊，才會添加到賬本中，其他的節點復制，保證賬本的唯一性。如果有節點作弊，導致整個網路不通過，則會被丟棄再也不會記錄到總賬本中。因此所有節點都會遵守比特幣系統的共同協議。

【關於區塊鏈會延伸到那些領域的思考】：

由以上的概念可以總結出，區塊鏈技術存在這安全性、唯一性、去中心化。

原則上是可以避免部分信息泄露，讓確認方既可以確認你的身份，又無需暴露自己的真是用戶信息等。

目前區塊鏈技術集中被運用再比特幣，我覺得後續更大的意義應該在需要數據私密性、安全性的領域。

【關於區塊鏈目前發展的瓶頸和局限性思考】：

由於每個節點都參與了整個賬本記錄活動，難免造成資源的浪費和損耗。以及加大了每個節點的計算難度，後續的發展和普及需要每個節點的硬體提升。

B. 區塊鏈的密碼技術有

密碼學技術是區塊鏈技術的核心。區塊鏈的密碼技術有數字簽名演算法和哈希演算法。
數字簽名演算法
數字簽名演算法是數字簽名標準的一個子集，表示了只用作數字簽名的一個特定的公鑰演算法。密鑰運行在由SHA-1產生的消息哈希：為了驗證一個簽名，要重新計算消息的哈希，使用公鑰解密簽名然後比較結果。縮寫為DSA。

數字簽名是電子簽名的特殊形式。到目前為止，至少已經有 20 多個國家通過法律 認可電子簽名，其中包括歐盟和美國，我國的電子簽名法於 2004 年 8 月 28 日第十屆全 國人民代表大會常務委員會第十一次會議通過。數字簽名在 ISO 7498-2 標准中定義為： 「附加在數據單元上的一些數據，或是對數據單元所作的密碼變換，這種數據和變換允許數據單元的接收者用以確認數據單元來源和數據單元的完整性，並保護數據，防止被人（例如接收者）進行偽造」。數字簽名機制提供了一種鑒別方法，以解決偽造、抵賴、冒充和篡改等問題，利用數據加密技術、數據變換技術，使收發數據雙方能夠滿足兩個條件：接收方能夠鑒別發送方所宣稱的身份；發送方以後不能否認其發送過該數據這一 事實。
數字簽名是密碼學理論中的一個重要分支。它的提出是為了對電子文檔進行簽名，以 替代傳統紙質文檔上的手寫簽名，因此它必須具備 5 個特性。
（1）簽名是可信的。
（2）簽名是不可偽造的。
（3）簽名是不可重用的。
（4）簽名的文件是不可改變的。
（5）簽名是不可抵賴的。
哈希（hash）演算法
Hash，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，其中散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，但是不可逆向推導出輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
哈希（Hash）演算法，它是一種單向密碼體制，即它是一個從明文到密文的不可逆的映射，只有加密過程，沒有解密過程。同時，哈希函數可以將任意長度的輸入經過變化以後得到固定長度的輸出。哈希函數的這種單向特徵和輸出數據長度固定的特徵使得它可以生成消息或者數據。
以比特幣區塊鏈為代表，其中工作量證明和密鑰編碼過程中多次使用了二次哈希，如SHA(SHA256(k))或者RIPEMD160(SHA256(K)),這種方式帶來的好處是增加了工作量或者在不清楚協議的情況下增加破解難度。
以比特幣區塊鏈為代表，主要使用的兩個哈希函數分別是：
1.SHA-256，主要用於完成PoW（工作量證明）計算；
2.RIPEMD160，主要用於生成比特幣地址。如下圖1所示，為比特幣從公鑰生成地址的流程。

C. (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！

D. 比特幣演算法原理

比特幣演算法主要有兩種，分別是橢圓曲線數字簽名演算法和SHA256哈希演算法。

橢圓曲線數字簽名演算法主要運用在比特幣公鑰和私鑰的生成過程中，該演算法是構成比特幣系統的基石。SHA-256哈希演算法主要是運用在比特幣的工作量證明機制中。

比特幣產生的原理是經過復雜的運演算法產生的特解，挖礦就是尋找特解的過程。不過比特幣的總數量只有2100萬個，而且隨著比特幣不斷被挖掘，越往後產生比特幣的難度會增加，可能獲得比特幣的成本要比比特幣本身的價格高。

比特幣的區塊由區塊頭及該區塊所包含的交易列表組成，區塊頭的大小為80位元組，由4位元組的版本號、32位元組的上一個區塊的散列值、32位元組的 Merkle Root Hash、4位元組的時間戳（當前時間）、4位元組的當前難度值、4位元組的隨機數組成。擁有80位元組固定長度的區塊頭，就是用於比特幣工作量證明的輸入字元串。不停的變更區塊頭中的隨機數即 nonce 的數值，並對每次變更後的的區塊頭做雙重 SHA256運算，將結果值與當前網路的目標值做對比，如果小於目標值，則解題成功，工作量證明完成。

比特幣的本質其實是一堆復雜演算法所生成的一組方程組的特解（該解具有唯一性）。比特幣是世界上第一種分布式的虛擬貨幣，其沒有特定的發行中心，比特幣的網路由所有用戶構成，因為沒有中心的存在能夠保證了數據的安全性。

E. 區塊鏈的加密技術

數字加密技能是區塊鏈技能使用和開展的關鍵。一旦加密辦法被破解，區塊鏈的數據安全性將受到挑戰，區塊鏈的可篡改性將不復存在。加密演算法分為對稱加密演算法和非對稱加密演算法。區塊鏈首要使用非對稱加密演算法。非對稱加密演算法中的公鑰暗碼體制依據其所依據的問題一般分為三類:大整數分化問題、離散對數問題和橢圓曲線問題。第一，引進區塊鏈加密技能加密演算法一般分為對稱加密和非對稱加密。非對稱加密是指集成到區塊鏈中以滿意安全要求和所有權驗證要求的加密技能。非對稱加密通常在加密和解密進程中使用兩個非對稱暗碼，稱為公鑰和私鑰。非對稱密鑰對有兩個特點:一是其間一個密鑰(公鑰或私鑰)加密信息後，只能解密另一個對應的密鑰。第二，公鑰可以向別人揭露，而私鑰是保密的，別人無法通過公鑰計算出相應的私鑰。非對稱加密一般分為三種首要類型:大整數分化問題、離散對數問題和橢圓曲線問題。大整數分化的問題類是指用兩個大素數的乘積作為加密數。由於素數的出現是沒有規律的，所以只能通過不斷的試算來尋找解決辦法。離散對數問題類是指基於離散對數的困難性和強單向哈希函數的一種非對稱分布式加密演算法。橢圓曲線是指使用平面橢圓曲線來計算一組非對稱的特殊值，比特幣就採用了這種加密演算法。非對稱加密技能在區塊鏈的使用場景首要包含信息加密、數字簽名和登錄認證。(1)在信息加密場景中，發送方(記為A)用接收方(記為B)的公鑰對信息進行加密後發送給

B，B用自己的私鑰對信息進行解密。比特幣交易的加密就屬於這種場景。(2)在數字簽名場景中，發送方A用自己的私鑰對信息進行加密並發送給B，B用A的公鑰對信息進行解密，然後確保信息是由A發送的。(3)登錄認證場景下，客戶端用私鑰加密登錄信息並發送給伺服器，伺服器再用客戶端的公鑰解密認證登錄信息。請注意上述三種加密計劃之間的差異:信息加密是公鑰加密和私鑰解密，確保信息的安全性；數字簽名是私鑰加密，公鑰解密，確保了數字簽名的歸屬。認證私鑰加密，公鑰解密。以比特幣體系為例，其非對稱加密機制如圖1所示:比特幣體系一般通過調用操作體系底層的隨機數生成器生成一個256位的隨機數作為私鑰。比特幣的私鑰總量大，遍歷所有私鑰空間獲取比特幣的私鑰極其困難，所以暗碼學是安全的。為便於辨認，256位二進制比特幣私鑰將通過SHA256哈希演算法和Base58進行轉化，構成50個字元長的私鑰，便於用戶辨認和書寫。比特幣的公鑰是私鑰通過Secp256k1橢圓曲線演算法生成的65位元組隨機數。公鑰可用於生成比特幣交易中使用的地址。生成進程是公鑰先通過SHA256和RIPEMD160哈希處理，生成20位元組的摘要成果(即Hash160的成果)，再通過SHA256哈希演算法和Base58轉化，構成33個字元的比特幣地址。公鑰生成進程是不可逆的，即私鑰不能從公鑰推導出來。比特幣的公鑰和私鑰通常存儲在比特幣錢包文件中，其間私鑰最為重要。丟掉私鑰意味著丟掉相應地址的所有比特幣財物。在現有的比特幣和區塊鏈體系中，現已依據實踐使用需求衍生出多私鑰加密技能，以滿意多重簽名等愈加靈敏雜亂的場景。

F. 什麼是數字簽名

數字簽名是用於驗證數字和數據真實性和完整性的加密機制。我們可以將其視為傳統手寫簽名方式的數字化版本，並且相比於簽字具有更高的復雜性和安全性。

簡而言之，我們可以將數字簽名理解為附加到消息或文檔中的代碼。在生成數字簽名之後，其可以作為證明消息從發送方到接收方的傳輸過程中沒有被篡改的證據。

雖然使用密碼學保護通信機密性的概念可以追溯到古代，但隨著公鑰密碼學（PKC）的發展，數字簽名方案在20世紀70年代才成為現實。因此，要了解數字簽名的工作原理，我們首先需要了解散列函數和公鑰加密的基礎知識。

哈希是數字簽名中的核心要素之一。哈希值的運算過程是指將任意長度的數據轉換為固定長度。這是通過稱為散列函數的特殊運算實現的。經過散列函數運算而生成的值稱為哈希值或消息摘要。

當哈希值與加密演算法相結合，即使用加密散列函數的方法來生成散列值（摘要），該值可作為唯一的數字指紋。這意味著對於輸入數據（消息）的任何更改都會導致有完全不同的輸出值（散列值）。這就是加密散列函數被廣泛用於驗證數字和數據真實性的原因。

公鑰加密或PKC是指使用一對密鑰的加密系統：公鑰和私鑰。這兩個密鑰在數學上是相關的，可用於數據加密和數字簽名。

作為一種加密工具，PKC相比於對稱加密具有更高的安全性。對稱加密系統依賴於相同的密鑰進行加密和解密信息，但PKC則使用公鑰進行數據加密，並使用相應的私鑰進行數據解密。

除此之外，PKC還可以應用於生成數字簽名。本質上，該過程發送方使用自己的私鑰對消息（數據）的哈希值進行加密。接下來，消息的接收者可以使用簽名者提供的公鑰來檢查該數字簽名是否有效。

在某些情況下，數字簽名本身可能包括了加密的過程，但並非總是這樣。例如，比特幣區塊鏈使用PKC和數字簽名，而並不像大多數人所認為的，這個過程中並沒有進行加密。從技術上講，比特幣又部署了所謂的橢圓曲線數字簽名演算法（ECDSA）來驗證交易。

在加密貨幣的背景下，數字簽名系統通常包含三個基本流程：散列、簽名和驗證。

第一步是對消息或數據進行散列。通過散列演算法對數據進行運算，生成哈希值（即消息摘要）來完成的。如上所述，消息的長度可能會有很大差異，但是當消息被散列後，它們的哈希值都具有相同的長度。這是散列函數的最基本屬性。

但是，僅僅將消息進行散列並不是生成數字簽名的必要條件，因為也可以使用私鑰對沒有進行過散列的消息進行加密。但對於加密貨幣，消息是需要經過散列函數處理的，因為處理固定長度的哈希值有助於加密貨幣的程序運行。

對信息進行散列處理後，消息的發件人需要對其消息進行簽名。這里就用到了公鑰密碼學。有幾種類型的數字簽名演算法，每種演算法都有自己獨特的運行機制。本質上，都是使用私鑰對經過散列的消息（哈希值）進行簽名，然後消息的接收者可以使用相應的公鑰（由簽名者提供）來檢查其有效性。

換句話說，如果在生成簽名時不使用私鑰，則消息的接收者將不能使用相應的公鑰來驗證其有效性。公鑰和私鑰都是由消息的發送者生成的，但僅將公鑰共享給接收者。

需要注意的是，數字簽名與每條消息的內容相關聯。因此，與手寫簽名所不同，每條消息的數字簽名都是不同的。

讓我們舉一個例子說明下整個過程，包括從開始直到最後一步的驗證。我們假設Alice向Bob發送一條消息、並將該消息進行散列得到哈希值，然後將哈希值與她的私鑰結合起來生成數字簽名。數字簽名將作為該消息的唯一數字指紋。

當Bob收到消息時，他可以使用Alice提供的公鑰來檢查數字簽名的有效性。這樣，Bob可以確定簽名是由Alice創建的，因為只有她擁有與該公鑰所對應的私鑰（至少這與我們所假設的一致）。

因此，Alice需要保管好私鑰至關重要。如果另一個人拿到了Alice的私鑰，他們就同樣可以創建數字簽名並偽裝成Alice。在比特幣的背景下，這意味著有人可以使用Alice的私鑰，並可在未經她知曉的情況下轉移或使用她的比特幣。

數字簽名通常用於實現以下三方面目標：數據完整性、身份驗證和不可否認性。

數字簽名可以應用於各種數字文檔和證書。因此，他們有幾個應用程序。一些最常見的案例包括：

數字簽名方案面臨的主要挑戰主要局限於以下三方面因素：

簡而言之，數字簽名可以理解為是一種特定類型的電子簽名，特指使用電子化的方式簽署文檔和消息。因此，所有數字簽名都可認為是電子簽名，但反之並非如此。

它們之間的主要區別在於身份驗證方式。數字簽名需要部署加密系統，例如散列函數、公鑰加密和加密技術。

散列函數和公鑰加密是數字簽名系統的核心，現已在各種案例中使用。如果實施得當，數字簽名可以提高安全性，確保完整性，便於對各類數據進行身份驗證。

在區塊鏈領域，數字簽名用於簽署和授權加密貨幣交易。它們對比特幣尤為重要，因為數字簽名能夠確保代幣只能由擁有相應私鑰的人使用。

雖然我們多年來一直使用電子和數字簽名，但仍有很大的發展空間。如今大部分的公文仍然還是基於紙質材料，但隨著更多的系統遷移到數字化中，我們還會看到更多的數字簽名方案。

G. ECDSA（橢圓曲線數字簽名演算法）

ECDSA（Elliptic Curve Digital Signature Algorithm）

在現實工作和生活中，我們使用簽名的方式表達對一份文件的認可，其他人可以識別出你的簽名並且無法偽造你的簽名。數字簽名就是對顯示簽名的一種電子實現，它不僅可以完全達到現實簽名的特點，甚至能夠做的更好。
常用的數字簽名演算法有RSA（Rivest-Shamir-Adleman Scheme）、DSS（Digital Signature Standard）等。 比特幣使用ECDSA來生成賬戶的公私鑰以及對交易和區塊進行驗證。

1.Alice（密碼學中常用A到Z開頭的人名代替甲乙丙丁等，字母越靠後出現頻率越低）生成一對密鑰，一個是sk（signing key），是非公開的；另一個是vk（verification key），是公開的。
這一對密鑰同時生成，並且在數學上是相互關聯的，同時，根據vk無法推測出關於sk的任何信息。
2.數字簽名演算法接收兩個輸出：信息M和sk，生成一個數字簽名Sm
3.驗證函數接收信息M、Sm以及vk作為輸入，，返回結果是yes或者no。這一步的目的是為了驗證你看到的針對信息M的數字簽名確實是由Alice的sk來簽發的，用於確認信息與簽名是否相符。
與手寫簽名不同，手寫簽名基本都是相似的，但是數字簽名卻受輸入影響很大。對輸入輕微的改變都會產生一個完全不同的數字簽名。一般不會對信息直接進行數字簽名，而是對信息的哈希值進行簽名。由加密哈希函數的無碰撞性可知，這樣和對原信息進行簽名一樣安全。

在數學上，任何滿足以下方程的點所形成的曲線稱為隨機橢圓曲線： 並且 ，a和b可以為任意值。下面展示幾個隨機橢圓函數的示例：

在了解如何通過基於secp256k1橢圓曲線的ECDSA演算法生成公私鑰之前，我們需要了解在隨機橢圓曲線里，點的加法是如何實現的。
首先定義橢圓曲線上點的加法。設橢圓曲線上有兩點，A和B點，那麼作過這兩點的直線與該曲線相交於第三點（C點），然後關於X軸對稱得到D點，則D為這兩個點的和，記作D=A+BD=A+BD=A+B。很明顯，D點也在該曲線上。所以橢圓曲線上兩點之和也是曲線上的點。

特例：
1.如果兩點重合，則做該點的切線，與曲線相交點的對稱點為和，即A+A=C
如圖：

有了加法以後，乘法實現是不過是進行多次加法運算。有了一個基準點P以後，我們可以對其進行乘法運算，最後可以得到曲線上的另外一個點。
設PPP是橢圓曲線上的一個點，那麼正整數kkk乘以點PPP的結果由下面的式子定義，注意式子中的加法是上面提到的橢圓曲線上點的加法：

點的運算滿足結合律：

很顯然，通過累加 的方式計算 是一種很笨的辦法，其時間復雜度是線性的。上面我們提到過，橢圓曲線上點的加法是滿足結合律的，即 ，擴展一下，就有

於是就有這么一種騷操作，比如計算 ，我們可以先計算 ；然後計算 ；再計算 ；最後計算 。這里我們把15次加法減少到了4次。

當然，k的值不可能總是2的冪。實際上上面的操作可以推廣到k為任意正整數的情況。比如計算23P，首先計算 ，然後



因為 ，所以 。總共只需要7次加法。

分析一下，對於任意正整數k，我們都可以利用這個方法將計算k∗P所需的加法計算次數降低到

也就是說，從時間復雜度的角度來看，這個演算法是一個 的演算法。

這個方法被稱為快速冪演算法，原本常用於快速計算某個數的k次冪，這里將其推廣到橢圓曲線點乘的快速計算中。

為什麼要在介紹了橢圓曲線上點的乘法後突然冒出一個快速冪演算法？快速冪演算法對於橢圓曲線加密有什麼意義？因為數學家/密碼學家發現，利用快速冪演算法計算 的時間復雜度是對數級的，但是要在知道 和 的前提下，倒推出 的值，沒有比挨個嘗試 的值快太多的演算法。於是橢圓曲線加密依賴的數學難題就這么誕生了。

如果我們改一種記法，把橢圓曲線上點的加法記作乘法，原來的乘法就變成了冪運算，那麼上述難題的形式跟離散對數問題應該是一致的。即：

所以這個難題叫橢圓曲線上的離散對數問題。

盡管兩者形式一致，但是他們並不等價。實際上這個問題比大整數質因子分解（RSA）和離散對數（DH）難題都要難得多，目前還沒有出現亞指數級時間復雜度的演算法（大整數質因子分解和離散對數問題都有），以致於同樣的安全強度下，橢圓曲線加密的密鑰比RSA和DH的短不少，這是橢圓曲線加密的一大優勢。

假設隨機取一個 ~ 位之間的值x，計算 ，最後的結果一定會落在曲線上的一點。假設該點為 ，在公開 以及具體曲線的方程的情況下，能否反推出最初的隨機值 ？
證：尋找 的過程只能通過暴力計算， 的可能值為 ~ 中的一個，平均來說需要計算 次能夠找到一次 值。那麼問題來了，運行一次 的計算需要多長的時間呢？
假設我們使用的是超級計算機，主頻為 （一秒鍾可以進行一萬億次運算），從宇宙誕生的那一刻開始計算，到現在也就進行了 次。找到 值的概率為 。這個概率和下一秒地球被巨型隕石撞擊而毀滅的概率接近，既然我們讀到了這里，那麼說明這件事沒有發生。
在上面的案例中， 是 ~ 位的一個隨機數，可以作為私鑰。 是隨機橢圓曲線上的一個點，也就是由私鑰生成的公鑰，因此優點可以1得證。

但是密碼學中，並不能使用上面介紹的實數域上的橢圓曲線。因為

所以我們需要引入有限域上的橢圓曲線。
要證明優點2，還需要將隨機橢圓曲線做一些改動：為了保證最後計算出來的點的坐標值相加是512位，secp256k1引入了一個對質數取模的機制。具體來說，隨機橢圓曲線從
變為了 其中 ，是小於 的最大質數。
此時的隨機橢圓曲線函數圖如下：

具體來說，就是向別人證明我知道 ，但不暴露 的任何信息。（有些類似於零知識證明）
證：前面介紹過結合律： 添加一個hash函數，簡單修改可以得出： 使 ，那麼可知 為 。此時方程為： 為了簡單起見，我們記 和 。此時方程化簡為： 上面這個方程是什麼意思呢？
可以這樣假設：在已知 的情況下，如果能夠提供一個 和 滿足上面的方程，就可以證明一個人擁有 。這個假設有一個前提，如果一個人不知道x，那麼他就無法提供 和 滿足上面的等式。
詳細探討這個前提：如果一個人不知道x，又想計算出 和 ，能夠辦到嗎？結論是不能，首先我們無法從 計算出 （在有限時間內）。
還有一個問題：在已知 和 的情況下，能否計算出關於 的任何信息？
根據公式： 只要解出 就可以了。
要想計算出x，就需要知道r，但是在r沒有公開的情況下，有什麼辦法可以計算r嗎？我們知道R=r*P；但是根據這個公式無法倒推出r（剛才介紹的那個數學難題），所以x也是安全的。
至此，可以證明演算法的第二個優點。