比特币、区块链基础技术简介(含C#源码)(一) —— 椭圆曲线密码学之secp256k1的C#简易实现

转载请在文章首尾注明原始出处CSDN
前言

原本这个文章的标题是《比特币、区块链基础技术学习笔记》，想做个学习笔记，供有相同兴趣的同学参考；但发到朋友圈后部分朋友反馈说看不懂，于是把这个笔记补充了简介这一章节内容(其余章节也有少量调整或改动)，再把标题改成了《比特币、区块链基础技术简介》

简介

文章的副标题是《椭圆曲线密码学之secp256k1的C#简易实现》，目的在于基于C#语言在两百行左右的代码简易实现了椭圆曲线密码学secp256k1的根据私钥计算公钥的算法。
那么从《笔记》改为《简介》之后，首先就要回答以下几个问题：什么是椭圆曲线密码学？有什么用？在比特币、区块链中又发挥了什么作用？
椭圆曲线密码学，是非对称加密技术的一种。那么什么又是非对称加密技术呢？又有什么用呢？
简单来说，非对称加密技术基本上是用来解决类似于“证明我妈是我妈”这一类问题的。在比特币系统中，就用来“证明我的比特币就是我的比特币(我才能花出去)”；而比特币及大部分区块链系统，都采用了椭圆曲线密码学，并且通常用的是secp256k1。
顺带说一句，大家平常用的网银的UKey，其中也用到了非对称加密技术，作用也就是为了在银行系统“证明我就是我”。
通常非对称加密技术会给不同的人生成不同的私钥，再根据私钥生成公钥；公钥会公布给大众，而私钥则需要妥善保管。
那么非对称加密技术怎么来证明我的比特币就是我的比特币呢？其中的道理在于：用私钥加密的数据，用公钥才能解开；换句话说，用公钥能解读出正确的数据，就能证明你才是私钥的拥有者，那么你就是这些比特币(或者银行账户)的拥有者，你就能顺理成章地支配这些比特币。
目前常用的非对称加密技术有RSA和椭圆曲线密码学(ECC)。RSA目前普遍用于银行、证书等系统；而比特币、区块链系统则基本采用了椭圆曲线密码学。
在比特币系统中，所有账本是公开的；即使没有私钥，你也能清楚的看到，每个比特币从哪里来，到了哪里去；比特币钱包就是你的私钥合集，如果不幸遗失了私钥或钱包，那么私钥对应的比特币将可能会被私钥的拾获者进行支配；如果确定遗失并没有其他人拾获，那么那些比特币，还是你的，只是你再也无法支付出去了（花钱需要私钥）。
简单地说，在比特币系统中：收钱只需要公钥，花钱需要私钥；而椭圆曲线密码学，则是这一切的基础。

椭圆曲线密码学之secp256k1的C#简易实现

本文的内容偏向于C#
的简易实现(两百行代码左右)，所以关于椭圆曲线密码学的介绍只止步于能实现即可，并不完整。同时限于该知识是从搜索引擎中来，加之个人理解能力有限，所以可能有错漏之处，希望懂的朋友能留言指正。

椭圆曲线密码学

对于椭圆曲线，我们用到的方程式是： $y^{2} = x^{3} + ax + b$ ；对于给定的 $a$ 及 $b$ ，该方程在笛卡尔坐标系确定了一条曲线。
椭圆曲线密码学，取某个大质数 $P$ ，对上述方程进行同余处理，得到：
$y^{2} ≡x^{3} + ax + b (mod P)$
当给定整数 $a$ 、 $b$ 、质数 $P$ 时，上述方程的整数解及虚点 $Z e r o$ 构成了点集 $p$ 。(这里的 $Z e r o$ 就是零元素，在简易C#代码中将被实现为null值)
取点集 $p$ 中单位点 $G(x_{g}, y_{g})$ ，定义 $G=(x_{g},-y_{g})$
定义加法 $M(x_{1},y_{1})+N(x_{2},y_{2})=Q(x_{3},y_{3})$ 如下：
$x_{3} ≡ k^{2} − x_{1} − x_{2} (mod P)$
$y_{3} ≡ k(x_{1} − x_{3}) − y_{1}(mod P)$
其中， $k ≡ (y_{2} − y_{1})/ (x_{2} − x_{1}) (mod P,x1!=x2时)$ 或 $k ≡ (3x_{1}^{2}+ a)/2y_{1}(mod P,x1==x2时)$
定义 $G + (- G) = Z e r o$ ，定义 $Z e r o + Q = Q + Z e r o = Q (Q 为任意点)$ ；
根据上述定义的加法， $G + G = 2 G$ ， $2 G + G = G + 2 G = 3 G \dots$ 也在点集 $p$ 内。
对于给定 $P$ 、 $a$ 、 $b$ 、 $G$ ，存在整数 $N$ ，使得 $N G = Z e r o$ 。其中满足 $N G = Z e r o$ 的最小正整数 $n$ 称为 $G$ 的阶。

secp256k1

在上述理论中取以下值即可：
$P$ = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
$2^{256} − 2^{32} − 2^{9} − 2^{8} − 2^{7} − 2^{6} − 2^{4} – 1$
$a = 0, b = 7$
单位点$G = $
(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
则 $n$ = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

应用

在 1 ~ $n - 1$ 之间，随机取一个整数 $p r i v a t e K e y$ ,计算 $p u b l i c K e y = p r i v a t e K e y * G$ 。
椭圆曲线密码学在数学上，有这样的特性：从 $p r i v a t e K e y$ 计算出 $p u b l i c K e y$ ，相对容易（根据上述公式计算即可），计算机只需要毫秒级别的时间即可；但是要从 $p u b l i c K e y$ 计算出 $p r i v a t e K e y$ ，那就相当困难了，即使目前最快的计算机也可能要算上个千年万载的。
其中 $p r i v a t e K e y$ 就是私钥，如果不幸被别人获取了，这个私钥能支配的比特币就可能会立即被转移至其他账户。 $p u b l i c K e y$ 就是公钥，在经过一系列处理后，就可以公开成为你的比特币收款地址。

C#简易实现

根据私钥来计算公钥，实际上就是实现点G的标量乘法，从算法到代码，这里有两个难点：一、需要一个大整数类：这一点还好，通过搜索引擎，找到了C#自身已有的BigInteger类的完美实现，只需要引用 System.Numerics.dll就好了；二、计算公式中的斜率 $k$ 值，用到了费尔玛小定理来实现，不太了解的同学可自行通过搜索引擎进行学习。
上简易代码（两个文件共两百行左右）：

BitcoinTools.cs

using System.Text;
using System.Globalization;
using System.Numerics;

public class BitcoinTools
{
    public class ECPoint
    {
        public BigInteger x;
        public BigInteger y;
    }

    public static readonly BigInteger P = BigInteger.Parse("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", NumberStyles.HexNumber);
    public static readonly BigInteger N = BigInteger.Parse("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", NumberStyles.HexNumber);
    public static readonly ECPoint G = new ECPoint()
    {
        x = BigInteger.Parse("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", NumberStyles.HexNumber),
        y = BigInteger.Parse("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", NumberStyles.HexNumber)
    };

    /// <summary>
    /// N - 1 
    /// </summary>
    private static readonly BigInteger N_1 = BigInteger.Parse("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140", NumberStyles.HexNumber);

    /// <summary>
    /// P - 2
    /// </summary>
    private static readonly BigInteger P_2 = BigInteger.Parse("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2D", NumberStyles.HexNumber);
    private static readonly int MaxBit = 256;
    private static readonly ECPoint[] Power_G = new ECPoint[MaxBit];

    /// <summary>
    /// 为了提高运算效率，将G与2的n次方的积进行缓存
    /// </summary>
    static BitcoinTools()
    {
        for (int i = 0; i < MaxBit; i++)
        {
            if (i == 0)
            {
                Power_G[0] = G;
            }
            else
            {
                Power_G[i] = Addition(Power_G[i - 1], Power_G[i - 1]);
            }
        }
    }

    /// <summary>
    /// 判断某点是否在椭圆曲线 secp256k1 上(mod P)
    /// </summary>
    public static bool IsOnCurve(ECPoint point)
    {
        BigInteger leftSide = BigInteger.Pow(point.y, 2) % P;
        BigInteger rightSide = (BigInteger.Pow(point.x, 3) + 7) % P;
        return leftSide == rightSide;
    }

    /// <summary>
    /// 取得x的倒数(mod P)
    /// 根据费尔玛小定理
    /// </summary>
    private static BigInteger GetReciprocalModP(BigInteger x)
    {
        BigInteger[] array = new BigInteger[MaxBit];
        BigInteger ret = 1;
        BigInteger temp = P_2;
        for (int i = 0; i < MaxBit; i++)
        {
            if (i == 0)
            {
                array[0] = x;
            }
            else
            {
                array[i] = BigInteger.Pow(array[i - 1], 2) % P;
            }

            if (!temp.IsEven)
            {
                ret *= array[i];
                ret %= P;
            }

            temp >>= 1;

            if (temp.IsZero)
                break;
        }
        return ret;
    }

    /// <summary>
    /// 两个点相加
    /// </summary>
    public static ECPoint Addition(ECPoint a, ECPoint b)
    {
        if (a == null)
            return b;
        if (b == null)
            return a;

        BigInteger k;
        if (a.x == b.x)
        {
            if ((a.y + b.y) % P == 0)
            {
                return null;
            }
            k = 3 * BigInteger.Pow(a.x, 2);
            k *= GetReciprocalModP(2 * a.y);
            k %= P;
        }
        else
        {
            k = (b.y + P - a.y) % P;
            k *= GetReciprocalModP((b.x + P - a.x) % P);
            k %= P;
        }
        ECPoint ret = new ECPoint();
        ret.x = (k * k + P - a.x + P - b.x) % P;
        ret.y = (k * (P + a.x - ret.x) + P - a.y) % P;
        return ret;
    }

    /// <summary>
    /// 对点G的标量乘法
    /// </summary>
    public static ECPoint Multiplication(BigInteger pri)
    {
        ECPoint ret = null;
        for (int i = 0; i < MaxBit; i++)
        {
            if (!pri.IsEven)
            {
                if (ret == null)
                {
                    ret = Power_G[i];
                }
                else
                {
                    ret = Addition(ret, Power_G[i]);
                }
            }

            pri >>= 1;

            if (pri.IsZero)
                break;
        }
        return ret;
    }

    /// <summary>
    /// 将字节数组输出为字符串
    /// </summary>
    public static string BytesToString(byte[] bytes)
    {
        StringBuilder builder = new StringBuilder();
        for (int i = bytes.Length - 1; i >= 0; i--)
        {
            builder.Append(bytes[i].ToString("X2"));
        }
        return builder.ToString();
    }
}

Program.cs

using System;
using System.Numerics;

class Program
{
    static void Main(string[] args)
    {
        for (int k = 1; k <= 20; k++)
        {
            var publicKey = BitcoinTools.Multiplication(k);
            Console.WriteLine(" k = {0}", k);
            Console.WriteLine(" x = {0}", BitcoinTools.BytesToString(publicKey.x.ToByteArray()));
            Console.WriteLine(" y = {0}", BitcoinTools.BytesToString(publicKey.y.ToByteArray()));
            Console.WriteLine();
        }

        string[] kArray =
            { "112233445566778899"
            , "112233445566778899112233445566778899"
            , "28948022309329048855892746252171976963209391069768726095651290785379540373584"
            , "57896044618658097711785492504343953926418782139537452191302581570759080747168"
            , "86844066927987146567678238756515930889628173209306178286953872356138621120752"
            };

        foreach (string k in kArray)
        {
            var publicKey = BitcoinTools.Multiplication(BigInteger.Parse(k));
            Console.WriteLine(" k = {0}", k);
            Console.WriteLine(" x = {0}", BitcoinTools.BytesToString(publicKey.x.ToByteArray()));
            Console.WriteLine(" y = {0}", BitcoinTools.BytesToString(publicKey.y.ToByteArray()));
            Console.WriteLine();
        }

        BigInteger kStart = BigInteger.Parse("115792089237316195423570985008687907852837564279074904382605163141518161494317");
        BigInteger kEnd = BigInteger.Parse("115792089237316195423570985008687907852837564279074904382605163141518161494336");
        for (BigInteger k = kStart; k <= kEnd; k++)
        {
            var publicKey = BitcoinTools.Multiplication(k);
            Console.WriteLine(" k = {0}", k);
            Console.WriteLine(" x = {0}", BitcoinTools.BytesToString(publicKey.x.ToByteArray()));
            Console.WriteLine(" y = {0}", BitcoinTools.BytesToString(publicKey.y.ToByteArray()));
            Console.WriteLine();
        }
    }
}

运行结果

运行结果和这个网址的内容能匹配上：
https://crypto.stackexchange.com/questions/784/are-there-any-secp256k1-ecdsa-test-examples-available
暂未发现Bug。结果的略有不同之处是在部分大整数(最高bit为1的大整数)之前额外多了两个十六进制的0。是因为C#实现的大整数，如果最高位(bit)是1的话，则表示是负数；因此正数且最高bit为1的话，会在之前再补充一个字节0。

后记及下节内容预告

椭圆曲线密码学，相信是部分初入门朋友的难点；我也不例外，为这点内容通过搜索引擎搜了n久，然后写了这些代码，整理成文，为的是让别的初学者能快速、初步了解相关的技术。下次的内容是《比特币私钥、公钥及钱包地址的C#简易实现》

第一次在网络上发表文章，排版及错漏之处在所难免，大家请多多见谅。
转载请在文章首尾注明原始出处CSDN。

原文链接：https://blog.csdn.net/budan/article/details/81638782