0-区块链密码学基本原理

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。

简介

有数据结构的继承，学起来会很轻松的。不要有心里负担，其实区块链难不了。

之后的全部内容都是参考自北京大学肖臻老师的公开课。

https://www.bilibili.com/video/BV1Vt411X7JF/?spm_id_from=333.337.search-card.all.click&vd_source=a07523372ea1438247b770c295f20822

概念

一、**collision resistance **： 冲突阻力的，指的是不容易 出hash冲突。

二、hiding： 隐藏性质，反算很难。

三、puzzle friendly： 像迷一样，只能一个一个试。

cryptographic hash function ：就是散列表的hash函数，参考我以前的算法数据结构笔记就行。

brute- force： 蛮力

digest：摘要，非对称加密 用来 防篡改

digital commitment： 数字承诺

sealed envelope ： 密封 信封 collision resistance hiding 结合实现。

proof of work： 工作量证明

secure hash algorithm： SHA ，像 SHA256 就是 一种。

asymmetric encryption algorithm：非对称加密

保密传输

用 （public key）加密，传输，（private key）再 解密 自己看。

数字签名

证明 是我在操作，而不是冒名顶替；

（private key）加密这个文件，也就是 数字签名，然后，别人用我的 （public key） 去解密验证 是不是我的签名。

生成 公私钥对 要用好的随机源，数字签名时候也要用好的 随机源。

例子说明为什么 随机源 重要

公钥和私钥是怎么生成的？

以最常见的 RSA 算法 为例，我们来看看如何生成一对公钥和私钥。

RSA 密钥对生成步骤

  1. 选择两个大素数：随机生成两个不同的大素数 ppp 和 qqq。
    • 这些素数越大，密钥的安全性就越高。通常会选择 2048 位或更大的素数。
  2. 计算 nnn：
    • n=p×qn = p \times qn=p×q。
    • nnn 是公钥和私钥的一部分。
  3. **计算欧拉函数 ϕ(n)\phi(n)ϕ(n)**：
    • ϕ(n)=(p−1)×(q−1)\phi(n) = (p - 1) \times (q - 1)ϕ(n)=(p−1)×(q−1)。
  4. 选择公钥指数 eee：
    • 选择一个整数 eee，使得 1<e<ϕ(n)1 < e < \phi(n)1<e<ϕ(n) 且 eee 与 ϕ(n)\phi(n)ϕ(n) 互质（即 gcd⁡(e,ϕ(n))=1\gcd(e, \phi(n)) = 1gcd(e,ϕ(n))=1）。
    • 通常选择 e=65537e = 65537e=65537，因为它既是素数，又能确保计算效率。
  5. 计算私钥 ddd：
    • 根据 eee 和 ϕ(n)\phi(n)ϕ(n)，找到一个整数 ddd，使得 d×e≡1 (mod ϕ(n))d \times e \equiv 1 \ (\text{mod} \ \phi(n))d×e≡1 (mod ϕ(n))。
    • 这意味着 ddd 是 eee 关于模 ϕ(n)\phi(n)ϕ(n) 的乘法逆元。
  6. 生成密钥对：
    • 公钥由 (n,e)(n, e)(n,e) 组成，可以公开。
    • 私钥由 (n,d)(n, d)(n,d) 组成，必须保密。

例子

假设我们生成的素数为：

  • p=61p = 61p=61
  • q=53q = 53q=53

计算得到：

  • n=61×53=3233n = 61 \times 53 = 3233n=61×53=3233
  • ϕ(n)=(61−1)×(53−1)=3120\phi(n) = (61 - 1) \times (53 - 1) = 3120ϕ(n)=(61−1)×(53−1)=3120

选择 e=17e = 17e=17，因为 gcd⁡(17,3120)=1\gcd(17, 3120) = 1gcd(17,3120)=1。

接下来，找到 ddd，使得 d×17≡1 (mod 3120)d \times 17 \equiv 1 \ (\text{mod} \ 3120)d×17≡1 (mod 3120)。计算得 d=2753d = 2753d=2753。

因此：

  • 公钥：(n=3233,e=17)(n = 3233, e = 17)(n=3233,e=17)
  • 私钥：(n=3233,d=2753)(n = 3233, d = 2753)(n=3233,d=2753)

数字签名如何工作？

以 ECDSA（椭圆曲线数字签名算法） 为例，说明数字签名的流程：

  1. 消息哈希：
    • 首先，将要签名的消息通过哈希函数生成一个消息摘要 hhh。
  2. 生成随机数 kkk：
    • 生成一个随机数 kkk，这是签名过程中的一个临时密钥，每次签名都应生成新的随机数。
  3. 计算签名：
    • 使用私钥 ddd 和随机数 kkk 计算签名 (r,s)(r, s)(r,s)，其中： r=(k⋅G)xmod  nr = (k \cdot G)_x \mod nr=(k⋅G)xmodn s=k−1⋅(h+d⋅r)mod  ns = k^{-1} \cdot (h + d \cdot r) \mod ns=k−1⋅(h+d⋅r)modn
    • 这里 GGG 是椭圆曲线上的生成点，nnn 是椭圆曲线的阶。
  4. 发布签名：
    • 将签名 (r,s)(r, s)(r,s) 与消息一起发送给接收方。
  5. 验证签名（使用公钥）：
    • 接收方使用发送者的公钥验证签名是否有效。

随机数 kkk 在数字签名中的重要性

在 ECDSA 中，每次生成签名时都需要一个随机数 kkk。如果随机数不够随机，则可能会导致私钥泄露。以下是原因：

  • 随机数 kkk 必须是唯一且不可预测的，因为签名公式中的 sss 取决于 kkk。如果两个不同的消息使用了相同的 kkk，则攻击者可以通过简单的数学运算恢复出私钥 ddd。
  • 如果 kkk 可以被预测或重复使用，签名 (r,s)(r, s)(r,s) 中的 sss 会泄露足够的信息，使攻击者通过已知的签名反推出私钥。

真实案例：Sony PlayStation 3 ECDSA 签名漏洞

一个经典的例子是Sony PlayStation 3 的 ECDSA 签名漏洞事件，这个漏洞最终导致 PS3 系统的完全破解。

事件背景：

  • Sony 使用 ECDSA 为其 PlayStation 3 软件签名，以防止未授权的软件运行。
  • 不幸的是，在其实现的 ECDSA 签名算法中，每次签名使用的随机数 kkk 都是相同的。

攻击者如何利用漏洞恢复私钥？

假设 Sony 对两个不同的消息 M1M_1M1 和 M2M_2M2 使用了相同的随机数 kkk 生成签名：

  1. 对消息 M1M_1M1，签名为 (r,s1)(r, s_1)(r,s1)：

    s1=k−1⋅(h1+d⋅r)mod  ns_1 = k^{-1} \cdot (h_1 + d \cdot r) \mod ns1=k−1⋅(h1+d⋅r)modn

  2. 对消息 M2M_2M2，签名为 (r,s2)(r, s_2)(r,s2)：

    s2=k−1⋅(h2+d⋅r)mod  ns_2 = k^{-1} \cdot (h_2 + d \cdot r) \mod ns2=k−1⋅(h2+d⋅r)modn

  3. 因为两次签名使用了相同的 kkk，可以通过以下公式消去 kkk：

    k=h1−h2s1−s2mod  nk = \frac{h_1 - h_2}{s_1 - s_2} \mod nk=s1−s2h1−h2modn

  4. 一旦计算出 kkk，攻击者可以使用以下公式恢复私钥 ddd：

    d=s1⋅k−h1rmod  nd = \frac{s_1 \cdot k - h_1}{r} \mod nd=rs1⋅k−h1modn

因此，仅仅因为使用了相同的随机数 kkk，攻击者就可以推导出 Sony 的私钥，从而生成合法的数字签名。这使得攻击者可以在 PS3 上运行任何未授权的代码，导致整个系统被破解。