libsecp256k1位元幣密碼演算法開源庫（一）

2021SC@SDUSC
本篇博客參考William Stallings的著作《Cryptography and network security》、Douglas R.Stinson的著作《Cryptography Theory and practice》、以及博客園的ECC橢圓曲線詳解
**

目錄

一、專案綜述

**：
專案背景：
本專案為山東大學軟體學院2021-2022學年秋季學期“軟體工程應用與實踐”課程專案，
小組成員：網安工學 徐海華、網安工學 楊鵬宇
專案內容：
大資料安全和隱私保護是當前新型資訊技術的前沿問題，密碼技術是實作大資料安全、隱私保護、聯邦機器學習等問題的關鍵技術，位元幣和區塊鏈引起了國際上對密碼技術的重視，哈希演算法和數字簽名演算法是位元幣和區塊鏈的關鍵技術，
libsecp256k1開源庫是位元幣等區塊鏈開源專案中的核心開源代碼庫，Secp256k1是指位元幣中使用的ECDSA(橢圓曲線數字簽名演算法)曲線的引數，并且在高效密碼學標準（Certicom Research，http://www.secg.org/sec2-v2.pdf）中進行了定義，
Secp256k1為基于Fp有限域上的橢圓曲線，由于其特殊構造的特殊性，其優化后的實作比其他曲線性能上可以特高30％，有明顯以下兩個優點：1）占用很少的帶寬和存盤資源，密鑰的長度很短；2）讓所有的用戶都可以使用同樣的操作完成域運算
自2016年2月13日起，在新發布的bitcoin core 0.12.0版本中，libsecp256k1庫代替了openssl ecdsa，
本專案的目標是讓學生熟悉和掌握 libsecp256k1開源庫的整體結構、編譯執行、關鍵代碼等，能夠撰寫密碼運算的程式，并能夠對關鍵代碼進行分析、修改、優化，提高 libsecp256k1開源庫的性能，
libsecp256k1開源庫特征：
secp256k1 ECDSA簽名/驗證和密鑰生成，
*秘密/公鑰的加法和乘法調整，
*密鑰、公鑰、簽名的序列化/決議，
*恒定時間、恒定記憶體訪問簽名和公鑰生成，
*去隨機化ECDSA（通過RFC6979或呼叫方提供的函式，）
*非常高效的執行，
*適用于嵌入式系統，
*用于公鑰恢復的可選模塊，
*ECDH密鑰交換的可選模塊，
任務分配：
核心代碼：
徐海華負責：密鑰交換協議、針對secp256k1的Schnorr簽名的簽名變體、私鑰決議，
楊鵬宇負責：公鑰恢復、應用于壓縮公鑰的SHA256哈希函式的實作、橢圓曲線數字簽名演算法，
關鍵代碼：徐海華：測驗
楊鵬宇：數乘、擦除資料

二、相關底層知識

本開源庫底層的知識有很多，如大整數的乘法、模乘、Montgomery模乘、擴展歐幾里得演算法、模冪運算等，這個專案是關于大資料安全的，因此在本篇文章中，我會提及一些一些密碼學的基礎知識，并且寫了一些橢圓曲線演算法的知識，

1.安全服務與安全機制：
安全服務：
1）認證（同等物體認證，資料源認證）
2）訪問控制
3）資料保密性（連接保密性、無連接保密性、選擇域保密性、流量保密性）
4）資料完整性（具有恢復功能的連接完整性、無恢復功能的連接完整性、選擇域連接完整性、無連接完整性、選擇域無連接完整性）
5）不可否認性（源不可否認性、宿不可否認性）
安全機制：
1）特定安全機制：加密、數字簽名、訪問控制、資料完整性、認證交換、流量填充、路由控制、公證，
2）普遍安全機制：可信功能、安全標簽、事件檢測、安全審計跟蹤、安全恢復，

2.對稱加密與非對稱加密：
非對稱加密：密鑰成對出現，分為公鑰和私鑰，公鑰加密需要私鑰解密，私鑰加密需要公鑰解密，
對稱加密：采用單鑰密碼系統的加密方法，同一個密鑰可以同時用作資訊的加密和解密
對稱加密和非對稱加密的區別是：
1).對稱加密速度快，非對稱加密速度慢，
2).對稱加密要將密鑰暴漏，和明文傳輸沒有區別，
3).非對稱加密將公鑰暴漏，供客戶端加密，服務器使用私鑰解密，

3.橢圓曲線加密演算法介紹
利用橢圓曲線的數學知識實作的一種非對稱加密演算法，1985年Neal Koblitz和Victor Miller分別提出可以將橢圓曲線演算法用于密碼學中，橢圓曲線演算法的優勢在于可以利用更短的密鑰就可以達到相當高的安全強度，原因是計算橢圓曲線離散對數的問題的最快速度都需要全指數時間復雜度，因此，橢圓曲線演算法被大量應用與位元幣和中國二代身份證中，

4.橢圓曲線概念
一條橢圓曲線是在射影平面上滿足威爾斯特拉斯方所有點的集合 Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
1）橢圓曲線方程是一個齊次方程
2）曲線上的每個點都必須是非奇異的（光滑的），偏導數FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同為0，
3）圓曲線的形狀，并不是橢圓的，只是因為橢圓曲線的描述方程，類似于計算一個橢圓周長的方程故得名，

5.橢圓曲線加密：
考慮K=kG ，其中K、G為橢圓曲線Ep(a,b)上的點，n為G的階（nG=O∞ ），k為小于n的整數，則給定k和G，根據加法法則，計算K很容易但反過來，給定K和G，求k就非常困難，因為實際使用中的ECC原則上把p取得相當大，n也相當大，要把n個解點逐一算出來列成上表是不可能的，這就是橢圓曲線加密演算法的數學依據
點G稱為基點（base point）
k（k<n）為私有密鑰（privte key）
K為公開密鑰（public key)

6.ECC保密通信演算法
1.Alice選定一條橢圓曲線E，并取橢圓曲線上一點作為基點G 假設選定E29(4,20)，基點G(13,23) , 基點G的階數n=37
2.Alice選擇一個私有密鑰p（p<n），并生成公開密鑰K=pG 比如25, K= pG = 25G = (14,6）
3.Alice將E和點K、G傳給Bob
4.Bob收到資訊后，將待傳輸的明文編碼到上的一點M（編碼方法略），并產生一個隨機整數r（r<n,n為G的階數） 假設r=6 要加密的資訊為3,因為M也要在E29(4,20) 所以M=(3,28)
5.Bob計算點C1=M+rK和C2=rG C1= M+6K = (3,28)+6*(14,6)=(3,28)+(27,27)=(6,12) C2= 6G =(5,7)
6.Bob將C1、C2傳給Alice
7.Alice收到資訊后，計算C1-kC2，結果就應該是點M C1-kC2 =(6,12)-25C2 =(6,12)-25*6G =(6,12)-2G =(6,12)-(27,27) =(6,12)+(27,2) =(3,28)

7.橢圓曲線演算法優缺點
優點：安全性能更高、處理速度更快、帶寬要求更低、存盤空間更小
缺點：
1.設計困難，實作復雜
2.如果序列號設計過短，那么安全性并沒有想象中的完善

三、環境配置

首先在github上把要分析的專案原始碼包下載下來，
在github檔案下載readme.md檔案中對專案情況做了一些說明，關于專案構建其中提到libsecp256k1（要分析的C庫）是使用autotools構建的，
鑒于本專案是一個C庫而且檔案包中有一個makefile.am檔案，自然聯想到這個專案應該要放到Linux環境下運行，
說明檔案中提到，此C庫是使用autotools構建的，這就表明，這個專案不會直接提供makefile檔案，我們需要在linux環境下利用包中的檔案生成makefile檔案，

本實驗需要gcc編譯器，一個比較簡單的配置gcc編譯器的方法就是終端輸入
sudo apt-get install build-essential即可
0.配置autotools：在Ubuntu中安裝aclocal、autoscan、autoconf、autoheader、automake檔案，在命令列中輸入 sudo apt-get install autoconf 即可
1.第一步，我們需要在我們的專案目錄下執行autoscan命令，這個命令主要用于掃描作業目錄，并且生成configure.scan檔案，然后要使用mv configure.scan configure.ac陳述句將configure.scan重命令成configure.ac
2.執行aclocal，生成aclocal.m4檔案
aclocal會根據configure.ac檔案的內容，自動生成aclocal.m4檔案，而aclocal.m4檔案中，包含了生成configure檔案所必須的宏，
3. 執行autoconf，生成configure檔案
autoconf會根據configure.ac和aclocal.m4檔案，生成configure檔案，
4.執行autoheader命令，該命令生成 config.h.in 檔案，該命令通常會從 "acconfig.h” 檔案中復制用戶附加的符號定義，
5. 執行automake命令，產生Makefile.in
具體命令為：automake --add-missing（automake后面有一個空格）
automake會根據Makefile.am檔案產生一些檔案，包含最重要的Makefile.in，前面所生成的configure，會根據Makefile.in檔案，來生成最終的Makefile檔案，

這幾步輸入陳述句如下：

6. 執行configure命令，生成Makefile檔案
   這樣，就產生了編譯所需要的Makefile檔案，
   

7.運行make，即可編譯，

等待一段時間后生成五個可執行檔案，在終端中輸入 ./檔案名 即可執行

生成可執行檔案如下：
等待一段時間后生成五個可執行檔案，在終端中輸入 ./檔案名 即可執行
生成可執行檔案如下：