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文件。
这几步输入语句如下：
- 执行configure命令，生成Makefile文件
这样，就产生了编译所需要的Makefile文件。
7.运行make，即可编译。
等待一段时间后生成五个可执行文件，在终端中输入 ./文件名 即可执行
生成可执行文件如下：
等待一段时间后生成五个可执行文件，在终端中输入 ./文件名 即可执行
生成可执行文件如下：
