您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【密码学】第六章、数字签名

基本概念

  • 数字签名
    • 用于对消息进行签名,以防消息的伪造或者篡改,也可用于鉴别通信双方的身份
    • 可以做到身份认证保持数据完整性不可否认性

特性

  • 可信
    • 可验证签名的有效性
  • 不可伪造
    • 除合法签名者,其他人伪造签名是困难的
  • 不可复制
    • 一个消息的签名不能复制为另一个消息的签名。
  • 不可改变
    • 签名后的消息不能被篡改
  • 不可抵赖
    • 签名者事后不能否认自己的签名

RSA数字签名

体制参数(重要

  • 选取大素数pq100-200位十进制数字);
  • 计算n=pq,其欧拉函数为:
    ϕ ( n ) = ( p − 1 ) ( q − 1 ) \phi(n)=(p-1)(q-1) ϕ(n)=(p1)(q1)
  • 随机选取一整数e,保证:
    1 ≤ e < ϕ ( n ) , g c d ( ϕ ( n ) , e ) = 1 1 \leq e < \phi(n),gcd(\phi(n),e)=1 1e<ϕ(n)gcd(ϕ(n),e)=1
  • 计算e的逆元d
    d = e − 1 ( m o d ϕ ) ( n ) d=e^{-1}\pmod \phi(n) d=e1(modϕ)(n)
  • ne为公钥,d为私钥。

签名

  • 设消息为m
    m ∈ Z n , s ≡ ( m o d n ) m\in Z_n,s\equiv \pmod n mZn,s(modn)

验证

  • 接收方收到消息m和签名s
    m = = s d ( m o d n ) m==s^d\pmod n m==sd(modn)
  • 成立则有效。

安全性

困难问题

  • 大数分解

缺点

情景一

对 任 意 y ∈ Z n 可 计 算 x ≡ y e ( m o d n ) 对任意y\in Z_n\\ 可计算x\equiv y^e\pmod n yZnxye(modn)

  • 任何人可伪造对随机消息x的签名。

情景二

攻 击 者 获 得 已 签 名 消 息 x 1 , x 2 y 1 ≡ x 1 e ( m o d n ) y 2 ≡ x 2 e ( m o d n ) 则 可 伪 造 消 息 x 1 x 2 的 签 名 y 1 y 2 攻击者获得已签名消息x_1,x_2\\ y_1\equiv x_1^e\pmod{n}\\ y_2\equiv x_2^e\pmod{n}\\ 则可伪造消息x_1x_2的签名y_1y_2 x1,x2y1x1e(modn)y2x2e(modn)x1x2y1y2

情景三

  • 签名速度慢

解决方案

  • 签名之前求消息的哈希值

一般化描述

明 文 消 息 : m 私 钥 : x 公 钥 : y 签 名 算 法 : s ≡ S i g x ( m ) 验 证 算 法 : V e r y ( s , m ) V e r y ( s , m ) = { T r u e   s = S i g x ( m ) F a l s e   s ≠ S i g x ( m ) 明文消息:m\\ 私钥:x\\ 公钥:y\\ 签名算法:s\equiv Sig_x(m)\\ 验证算法:Ver_y(s,m)\\ Ver_y(s,m)=\left\{ \begin{aligned} True\ s=Sig_x(m)\\ False\ s\neq Sig_x(m) \end{aligned} \right. mxysSigx(m)Very(s,m)Very(s,m)={True s=Sigx(m)False s=Sigx(m)

  • 安全性
    • 通过ms难以:求x或者伪造m’使得m’s验证为真。

DSS

密钥生成

选 取 素 数 p : 2 L − 1 < p < 2 L 其 中 512 ≤ L ≤ 1024 , 64 ∣ L 选 取 素 数 q : q ∣ p − 1 , 2 159 < q < 2 1 60 选 取 生 成 元 g : g ≡ h ( p − 1 ) / q ( m o d p ) 其 中 1 < h < p − 1 , h ( p − 1 ) / q ( m o d p ) > 1 随 机 选 取 x : 0 < x < q , 得 y = g x ( m o d p ) 选取素数p:2^{L-1}<p<2^L\\ 其中512\leq L\leq 1024,64|L\\ 选取素数q:q|p-1,2^{159}<q<2^160\\ 选取生成元g:g\equiv h^{(p-1)/q}\pmod{p}\\ 其中1<h<p-1,h^{(p-1)/q}\pmod{p}>1 随机选取x:0<x<q,得y=g^x\pmod{p}\\ p2L1<p<2L512L1024,64Lqqp1,2159<q<2160ggh(p1)/q(modp)1<h<p1,h(p1)/q(modp)>1x0<x<q,y=gx(modp)

  • 公开参数:pqg
  • 公钥:y
  • 私钥:x

签名

  • 随机选取一个整数k,满足0<k<q
  • 计算:
    r = ( g k ( m o d p ) ) ( m o d q ) s = k − 1 ( h ( m ) + x r ) ( m o d q ) r=(g^k\pmod{p})\pmod{q}\\ s=k^{-1}(h(m)+xr)\pmod{q} r=(gk(modp))(modq)s=k1(h(m)+xr)(modq)
  • 消息m的签名为(r,s)

h为哈希函数,DSS中其为SHA-1

验证

  • 计算:
    w = s − 1 ( m o d q ) u 1 = h ( m ) w ( m o d q ) u 2 = r w ( m o d q ) v = ( g u 1 y u 2 ( m o d p ) ) ( m o d q ) w=s^{-1}\pmod{q}\\ u_1=h(m)w\pmod{q}\\ u_2=rw\pmod{q}\\ v=(g^{u_1}y^{u_2}\pmod{p})\pmod{q} w=s1(modq)u1=h(m)w(modq)u2=rw(modq)v=(gu1yu2(modp))(modq)
  • 验证v=r,等式成立则为有效签名

ElGamal签名体制

体制参数

  • 大素数p
  • 生成元g
  • 密钥x
  • 公钥y=g^x mod p

签名

选 取 随 机 数 k ∈ Z p − 1 ∗ 定 义 S i g ( m , k ) = ( r , s ) r = g k ( m o d p ) s = k − 1 ( H ( m ) − x r ) ( m o d p − 1 ) 选取随机数k\in Z^*_{p-1}\\ 定义Sig(m,k)=(r,s)\\ r=g^k\pmod{p}\\ s=k^{-1}(H(m)-xr)\pmod{p-1} kZp1Sig(m,k)=(r,s)r=gk(modp)s=k1(H(m)xr)(modp1)

验证

y r r s ≡ g H ( m ) ( m o d p ) y^rr^s\equiv g^{H(m)}\pmod{p} yrrsgH(m)(modp)

交互证明系统

  • 概念
    *

Fiat-Shamir身份识别方案

  • 证明者P
  • 验证者V

协议

1. P 随 机 选 r ( 0 < r < n ) , 计 算 a ≡ r 2 ( m o d n ) , 将 a 发 给 V 2. V 随 机 选 e ∈ { 0 , 1 } , 将 e 发 给 P 3. P 计 算 b ≡ r y e ( m o d n ) , 将 b 发 给 V 4. 若 b 2 ≡ a x e ( m o d n ) , 则 V 接 受 证 明 1.P随机选r(0<r<n),计算a\equiv r^2\pmod{n},将a发给V\\ 2.V随机选e\in\{0,1\},将e发给P\\ 3.P计算b\equiv ry^e\pmod{n},将b发给V\\ 4.若b^2\equiv ax^e\pmod{n},则V接受证明 1.Pr(0<r<n)ar2(modn)aV2.Ve{0,1}eP3.Pbrye(modn)bV4.b2axe(modn)V

  1. P申明自己知道a的平方根。
  2. eV询问
  3. bP对询问的应答

性质

  • 完备性
    • PV遵守协议,若P知道y则应答正确,V接受证明。
  • 可靠性
    • 假冒者最高能以1/2的概率欺骗。
    • 通过执行多次降低欺骗率。

Schnorr身份识别方案

体制参数

  • pq是大素数,且q|(p-1)

q至少140位,p至少512位。

  • gq阶元。
    g q ≡ 1 ( m o d p ) g^q\equiv 1\pmod{p} gq1(modp)
  • h是输出t位的单向函数

t安全参数

  • 公钥y和私钥x
    y = g − x ( m o d p ) y=g^{-x}\pmod p y=gx(modp)

pqhy公开,x保密。

签名&验证

P 任 选 整 数 k , 1 ≤ k ≤ q − 1 , 计 算 r ≡ g k ( m o d p ) , 将 r 发 给 V V 计 算 e = H ( r , m ) , 将 e 发 给 P P 计 算 s = k + x e ( m o d q ) , 将 s 发 给 V V 验 证 r = g s × y e ( m o d p ) P任选整数k,1\leq k \leq q-1,计算r\equiv g^k\pmod{p},将r发给V\\ V计算e=H(r,m),将e发给P\\ P计算s=k+xe\pmod{q},将s发给V\\ V验证r=g^s\times y^e\pmod{p} Pk1kq1rgk(modp),rVVe=H(r,m)ePPs=k+xe(modq)sVVr=gs×ye(modp)


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进