密码学、数字签名与比特币

“ 让我们创造一片新的国土，将那些物质的控制者阻拦在外；为了跟随我们，进入我们的领地，他们将耗尽无尽的资源。”

想要了解比特币中的数字签名，就必须先了解一点密码学知识。


01
—
从密码学说起

对谍战片感兴趣的朋友可能听说过密码学，这是一门将数学应用于加密数据和解密数据的科学。利用这门科学，我们可以确保只有信息接收者才能看到信息内容。

具体来说我们根据一定的加密算法，用密钥将明文加密为密文，随后由接收方再使用加密算法和密钥从密文中解密出明文。

传统密码学中，发送方和接受方使用的加密算法和密钥是相同的，因此这类加密算法被称为“对称加密算法”。

历史上一个有名的对称加密算法是凯撒算法，据传说是凯撒大帝用来保护军事信息用的。

凯撒算法很简单。假设收发双方约定密钥为 4，则发送方将明文中的每一个字母用字母表中与其相隔三位的字母替代，即 A 变为 E，B 变为 F，"HELLO" 变为 "LIPPS"。

这种加密方法看起来非常简单，通常攻击者能够从语言学角度找到重复的字母，推断出密钥。

但这类移位算法经过一代代密码学家的增强，最终在二战时期进化为德军的恩尼格玛（Enigma）。

恩尼格玛是二战德军使用的机械加解密机器，其加密原理基于“复式移位替换法”。

同一个字母在明文的不同位置时，可以被不同的字母替换，而密文中不同位置的同一个字母，又可以代表明文中的不同字母。这使得恩尼格玛产生的密文在没有计算机的年代其密文很难被破译。

今天被广泛使用的对称加密算法是 AES（Advanced Encryption Standard），由美国国家标准与技术研究所于2001年建立。使用 128 bits 密钥的 AES 算法被认为足以免于暴力破解法的攻击。

对称加密算法能够保护机密信息不被窥探，但这种算法要求收发双方拥有相同的密钥。

在某些情况下，收发双方无法分享密钥。例如，当收发双方在一个可能受到监听的环境中时，其发送密钥的通道可能被截获，导致密文被破译。

因此一些密码学家开始研究如何在不安全信道上进行密钥交换。

02
—
迪菲－赫尔曼密钥交换协议

为了安全地交换密钥，惠特菲尔德·迪菲和马丁·赫尔曼在 1976 年发表了迪菲－赫尔曼密钥交换协议。



简单来说，假设 Alice 要给 Bob 发送一个密文。为了让 Bob 能够解密， Alice 还需要发送密钥给 Bob。

首先，Alice 和 Bob 各自选择一个足够大的素数 x 、 y。

然后 Alice 和 Bob 约定两个数 g 、 n，这两个数可以公开给所有人。

Alice 计算 g^x mod n 并告知 Bob 结果，Bob 计算 g^y mod n 并告知 Alice 结果。

这样双方就知道密钥为 g^(xy) mod n = (g^y mod n)^x mod n = (g^x mod n)^y mod n。

使用这个对称密钥，Alice 和 Bob 就可以进行安全的加密通讯。

为了破解这个密钥，攻击者必须实验所有的 g^(x*y) mod n 的可能值。当 n 是一个至少 600 位的素数时，就能够保证该对称密钥的安全性。

交换协议解决了如何在不安全信道上交换密钥的问题。但是它要求收发双方必须同时在线，才能生成对称密钥。另外交换协议中还无法保证和 Alice 进行密钥交换的是真正的 Bob，而不是其他人。

03
—
公开密钥加密算法

公开密钥加密算法，也被称为非对称加密算法。

该算法的加密过程需要两个密钥，一个用作加密，另一个则用作解密。使用其中一个密钥把明文加密后所得的密文，只能用相对应的另一个密钥才能解密得到原本的明文。由于加密和解密需要两个不同的密钥，故被称为非对称加密。

虽然两个密钥在数学上相关，但如果知道了其中一个，并不能凭此计算出另外一个。

其中一个可以公开，称为公钥，任意向外发布；不公开的密钥为私钥，必须由用户自行严格保管，不能向向任何人提供，也不需要透露给要通信的另一方。

公开密钥加密算法的关键在于公钥私钥生成，因此通常都根据数学难题设计公钥私钥。常用的三个难题为：质数分解，离散对数和椭圆曲线问题。

例如被广泛使用的 RSA 算法就是基于极大整数因数分解难题设计的。



下面演示一下简化版的 RSA 加密解密流程：

Alice 随意选择两个素数（实际使用中会使用足够长的素数）p = 11 和 q = 13。

p 和 q 的模数为 n = p * q = 143，其欧拉函数值为 r = (p-1)*(q-1) = 120。

接下来是公钥私钥生成。公钥是从小于 r 且与 r 互质的数中选择一个数字，例如 e = 7。私钥则是 e 关于 r 的模反元素。

根据扩展欧几里得算法可以计算出私钥 d = 103，可以验证 e * d = 7 * 103 = 721，721 与 1 关于 120 同余。

此时对于 Alice 来说，其公钥为（n, e)，私钥为（n, d)。

当 Bob 要向 Alice 传递信息时，那么 Bob 首先要获取 Alice 的公钥，然后 Bob 开始加密信息。

假设发送信息为 m = 9（实际中双方按照约定格式将信息转为一个小于 n 且与 n 互质的整数形式）。

则加密后的密文为 c = m^e mod n = 9^7 mod 143 = 48。

Alice 收到密文后用自己的私钥解密。 c^d mod n = 48^103 mod 143 = 9。

当攻击者获得 Alice 的公钥(n, e) 以及密文 c 时，他无法直接获取到私钥(n, d)。获得 d 的最简单方法是将 n 分解为 p 和 q。只要人类无法改进对极大整数进行因数分解的算法，那么用足够长(4096位或以上) RSA 公钥加密的信息就可以被认为是无法破解的。

当然，实际使用要比理论上复杂得多。例如，非对称加密通常要比对称加密算法计算复杂、性能差，一般会先用对称加密算法生成密文，再由非对称加密算法来加密对称密钥。

另外，为了防止中间人攻击，公开密钥加密算法需要由可靠的第三方机构签发数字证书，用来证明公开密钥拥有者的身份。。

除了用于加密，公开密钥加密算法还有一个重要的应用：数字签名。

04
—
数字签名

经过以上密码学知识的铺垫，我们初步了解了常见的加密算法。

下面可以思考一个场景，假如你发送一个信息给你的朋友，你该如何证明你是信息发送者，又该如何保证信息在途中没有被第三方修改呢？

这个问题中本聪设计区块链网络时也遇到过：每个节点产生的交易都要发送给其他节点。那么接收节点如何判断这个交易信息是由交易中记录的发送节点发来的？

这种情况下，可以利用公开密钥加密算法来生成发送信息的数字签名，接收方可以通过数字签名判断信息是否可信。

将公开密钥加密算法用于数字签名的步骤与加密解密步骤稍有不同。



假设 Alice 要给 Bob 发送消息。Alice 生成公钥私钥密码对，然后公布该公钥，再将消息哈希值用私钥加密后与消息一同发送给 Bob。

Bob 接收到消息后，就可以用 Alice 公布的公钥来解密得到消息哈希值，这能够表明信息发送方为 Alice。

然后将解密出的哈希值与接收到的哈希值比对，能够检验消息在中途是否被第三方篡改。

数字签名是用于鉴别数字信息所有权的技术，同时还能够提供数字信息完整性的验证。

05
—
比特币系统中的数字签名


比特币中使用的公开密钥加密算法是椭圆曲线加密算法（ECDSA）。

当比特币钱包生成新的比特币地址时，它实际上使用椭圆曲线加密算法生成了一对公钥私钥。

公钥私钥对就保存在生成的钱包文件中。生成地址时通常会要求你设置钱包密码，并尽量备份保管好钱包。

比特币系统就像一个巨大的收支账本。它没有记录每个地址里有多少钱，它记录的是每个地址中每次转账记录。

因此，如果你想知道自己一个地址中有多少个比特币，就需要遍历整个区块链，找出所有和这个地址有关的转账记录再计算余额。



当创建一次转账记录时，你需要给其他节点发送转账信息，其中包括用私钥对转账记录签名后的结果和未哈希的公钥。

其他节点接收到你的转账信息后，会从中解析出你的公钥验证数字签名是否有效。

只有当验证过数字签名有效后，接收节点才会将这个转账记录添加到区块的默克尔树上，并执行工作量证明过程。

因此，拥有一个地址对应的私钥，就完全拥有了该地址对应比特币的所有权。保管好自己的私钥至关重要，任何时候都不应该在网络上发送自己的私钥。