密码学系列 - 签名

作者: tpkeeper | 来源:发表于2019-10-28 18:07 被阅读0次

签名是用于消息的认证,保证该条消息不被伪造。本文主要讨论RSA签名、DSA、ECDSA 和 Schnorr 签名算法。

RSA签名

安全性建立在大数分解问题

公钥:E、N
私钥:D、N
签名:签名 = 消息^D mod N
验证:消息' = 签名^E mod N ,如果消息'==消息则验证成功

DSA

由NIST(美国国家标准技术研究所)1991年制定的数字签名技术规范,是Schnorr算法的变体。

安全性建立在离散对数问题

密钥生成(1024bits):

  1. 生成素数 p,2^{1023} < p < 2^{1024}
  2. 找到 p-1 的一个素数 q,且 2^{159} < q < 2^{160}
  3. 找到 ord(a)=q 的元素 a,a 生成了拥有 q 个元素的子群
  4. 生成随机数,0 < d < q
  5. b = a^d mod p
  6. 则密钥对为:k_{pub} = (p,q,a,b),k_{pri} = (d)

签名生成:

  1. 随机生成一个整数最为随机的临时密钥 k_E,且满足 0 < k_E < q。
  2. 计算 r = (a^{k_E} mod p) mod q
  3. 计算 s = (SHA(x)+d * r)k_E^{-1} mod q

签名的验证:

  1. 计算辅助值 w = s^{-1} mod q
  2. 计算辅助值 u_1 = w * SHA(x) mod q
  3. 计算辅助值 u_2 = w * r mod q
  4. v = (a^{u_1} * b^{u_2} mod p) mod q
  5. v' = r mod q,如果 v == v' 则签名正确

Golang SDK dsa 签名过程代码:

for attempts = 10; attempts > 0; attempts-- {
        k := new(big.Int)
        buf := make([]byte, n)
        for {
            _, err = io.ReadFull(rand, buf)
            if err != nil {
                return
            }
            //生成随机数密钥
            k.SetBytes(buf)
            // priv.Q must be >= 128 because the test above
            // requires it to be > 0 and that
            //    ceil(log_2(Q)) mod 8 = 0
            // Thus this loop will quickly terminate.
            if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
                break
            }
        }

        //求密钥的逆
        kInv := fermatInverse(k, priv.Q)

        //计算 r
        r = new(big.Int).Exp(priv.G, k, priv.P)
        r.Mod(r, priv.Q)

        if r.Sign() == 0 {
            continue
        }

        z := k.SetBytes(hash)

        //计算s
        s = new(big.Int).Mul(priv.X, r)
        s.Add(s, z)
        s.Mod(s, priv.Q)
        s.Mul(s, kInv)
        s.Mod(s, priv.Q)

        if s.Sign() != 0 {
            break
        }
    }

ECDSA

安全性建立在基于椭圆曲线的离散对数问题

密钥的生成:

  1. 使用曲线 E

    • 模数为 p
    • 系数为 a 和 b
    • 生成元为 G,G 生成的循环群的阶(即元素的个数)为 n
  2. 选择一个随机数 d,0 < d < n

  3. 计算 K = dG

  4. 密钥对则为:k_{pub} = (K),k_{pri} = (d)

签名的生成(x 为消息):

  1. 随机生成一个整数最为临时密钥 k_E,且 0 < k_E < q。
  2. R_{(x_R,y_R)} = k_EG
  3. r = x_R mod n
  4. s = (hash(x)+d * r)k_E^{-1} mod n

签名的验证:

  1. 计算辅助值 w = s^{-1} mod n
  2. 计算辅助值 u_1 = w * hash(x) mod n
  3. 计算辅助值 u_2 = w * r mod n
  4. P_(x_P,y_P) = u_1G + u_2K
  5. 如果 x_P == r mod n,则签名有效

Golang SDK ecdsa 签名过程代码:

for {
        for {
            k, err = randFieldElement(c, csprng)  //生成临时密钥
            if err != nil {
                r = nil
                return
            }

            //计算 k的逆
            if in, ok := priv.Curve.(invertible); ok {
                kInv = in.Inverse(k)
            } else {
                kInv = fermatInverse(k, N) // N != 0
            }

            //计算 r
            r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
            r.Mod(r, N)
            if r.Sign() != 0 {
                break
            }
        }

        e := hashToInt(hash, c)
        //计算 s
        s = new(big.Int).Mul(priv.D, r)
        s.Add(s, e)
        s.Mul(s, kInv)
        s.Mod(s, N) // N != 0
        if s.Sign() != 0 {
            break
        }
    }

pubkey recovery:

从签名信息中恢复公钥

比特币跟以太坊都有实现,但最终的签名信息序列化格式不同

// btc 中的格式
<(byte of 27+public key solution)+4 if compressed >< padded bytes for
signature R><padded bytes for signature S>

// 以太坊中的格式
[R || S || V] format where V is 0 or 1.

以太坊中的 go 实现也引用了btcd的代码,所以需要转换一下,具体可参考以太坊代码signature_nocgo.go

另:btc签名脚本中同时含有签名和公钥

公钥长度:

  • compressed: 65 byte (1+32+32)
  • uncompressed: 33 byte (1+32 )

Schnorr

相关文章

  • 密码学系列 - 签名

    签名是用于消息的认证,保证该条消息不被伪造。本文主要讨论RSA签名、DSA、ECDSA 和 Schnorr 签名...

  • 前后端数据传输安全——加密浅析

    加密 本文内容: 密码学起源 古典密码学 现代密码学 对称加密 非对称加密 数字签名 哈希 密码学起源: 在战争中...

  • RSA加密原理&密码学&HASH

    前情概述 由于后续会持续更新 iOS 应用安全系列文章 , 在此先更几篇密码学 , 应用签名 , 为后续展开代码注...

  • iOS签名机制,梳理各种加密算法

    什么是数字签名 小苹果的签名机制 密码学深入理解 ---demo含全图 密码学是研究编制密码和破译密码的技术科学...

  • 环签名与群签名

    环签名:2001年,Rivest, shamir和Tauman三位密码学家首次提出了环签名。是一种简化的群签名,只...

  • 自学区块链(一)

    咱先了解下比特币的密码学原理 主要用到了密码学中的哈希和签名, 这个哈希函数(密码学中要求)的主要性质是 1、首先...

  • 双钥加密 数字签名 数字证书 HTTPS SSH

    密码学笔记 公钥和私钥的解释 数字签名是什么&HTTPS ssh

  • 区块链学习

    比特币中的密码学 比特币主要应用了密码学中的两个技术:哈希、签名 哈希 哈希函数性质:collision resi...

  • iOS逆向之签名原理

    前言 本篇文章虽然是介绍iOS开发中ipa包的签名原理。但因为签名涉及到密码学中的概念。在了解签名之前,我们需要明...

  • 软考密码学(二)

    密码学应用 更多内容请访问我的博客 数字签名 完善的签名需要满足三个条件: 签名者事后不能抵赖 任何其他人不能伪造...

网友评论

    本文标题:密码学系列 - 签名

    本文链接:https://www.haomeiwen.com/subject/giobvctx.html