密码学与网络安全(八)EIGamal+Hash+数字签名

Nov 1, 2017


原创:岐山凤鸣

引用需注明本站域名。

EIGamal密码体系

基于:离散对数问题

公开全局的量:\(\alpha, q\), q是人为选定的素数,\(\alpha\)是q的一个素根

Alice生成密钥:选择一个比q-1小的私钥\(X_A\)

Alice生成公开密钥:计算\(Y_A = \alpha^{X_A}mod(q)\),公钥便是{a, alpha, Y_A}作为的集合

注:这个地方,哪怕攻击者知道\(Y_A = \alpha^{X_A}mod(q)\)和里面的三个量,根据离散对数的原理,也是计算不出来X_A的

Bob选取明文和随机数:选取明文M,M是小于q的一个数字,再选取一个随机小于q的数k

Bob计算K:\(K = (Y_A)^kmod(q)\)

Bob计算加密的第一个数C1:\(C_1 = \alpha mod (q)\)

Bob计算加密的第二个数C2: \(C_2 = KM mod (q)\)

Bob得到最终的密文C: C=(C1, C2)

解密方计算K: \(K = (C_1)^{X_A}mod(q)\)

解密方得到明文:\(M = (C_2K^{-1}mod(q)\)

举例

全局量p = 19, \(\alpha = 10\)

Alice选择\(X_A = 5\), 计算\(Y_A = 10^5 mod (19) = 3\), Alice的公钥即为(19, 10, 3)

Bob加密M=17, 首先选一个k=6,计算\(K=(Y_A)^k mod (q) = 7\), 则\(C_1 = 3^k mod (19) = 11\), \(C_2 = KM mod(p) = 5\), 即得到了密文(11, 5)

解密方解密先计算K对mod(p)的乘法逆元: \(K = (C_1)^{X_A} mod(q) = 7\), K对mod19的乘法逆元是11

解密方即可得到明文M:所以\(M=(C_2K_{-1}mod(q))=55mod19=17\)

Hash

用途:主要是【消息认证】

【消息认证】:验证消息完整性的一种机制/服务,确保收到的数据和发送的时候是一样的,不被篡改,而且发送方的身份是真实有效的。主要关注保护消息完整性,验证发送人身份与消息源的不可否认。

三种消息认证的方法:消息加密,消息认证码(MAC),哈希函数

消息加密:比如使用对称加密,默认只有发送方拥有密钥,才能产生可以解密的密文。

消息认证码MAC:使用密钥产生短小的定长数据分组,附加在报文里。例如AB共享密钥K,A发送B报文M,A计算MAC=C(K),夹在报文里发给B。B收到这个MAC后根据报文重新计算比并且对比一下就好了。要注意报文认证不提供保密,而且MAC不提供数字签名,所以双方必须共享密钥。

哈希函数:输入任意长度的消息M,输出一个固定长度的散列值,这个值称为消息摘要。它对所有的M的位都进行了错误检验,任何一位发送变化都会导致散列值的变化。

散列函数的要求:H能用于任何大小的分组,能产生定长的输出,能方便的计算,具有单向性,弱抗冲突性,强抗冲突性。

弱无碰撞:给定消息x属于X中,在计算上无法找到一个x’使得H(x) = H(x’)

强无碰撞:任何情况下,在计算上都无法找到一个x’使得H(x) = H(x’),其中包含了弱无碰撞的所有情况

分类:带密钥的Hash函数散列值有且仅有双方知道的密钥K来控制,生成的散列值叫MAC。不带密钥的Hash函数散列值叫MDC

数字签名

作用:保证了消息的来源和完整性,通过散列值来完成

与消息认证的区别:消息认证主要是看消息有没有被修改过,但是无法解决双方有利害冲突中的纷争,需要更严格的手段,也就是数字签名

基本形式:1、对消息整体签字,也就是对消息整个处理后得到签字。2、对消息摘要签字,附在被签消息后面,嵌在消息后面或者某个特定地方

类别:1、确定性数字签名,明文和签名一一对应。2、概率性数字签名,一个明文能有多个合法签名,每次都不一样。

直接数字签名DDS

要求:仅涉及两个通信方,通常先签名,再对消息和签名一起进行加密,安全性依赖私有密钥的安全性。

  • A->B: \(E_{KRa}[M]\), 仅提供了鉴别和签名
  • A->B: \(E_{KUb}[E_{KRa}[M]]\), 提供了保密,鉴别和签名
  • A->B: \(M||E_{KRa}[H[M]]\),提供了鉴别和数字签名,只有A能够生成M后面附加的那个东西
  • A->B: \(E_{K}[M||E_{KRa[H[M]]}]\), 在上面的基础上增加了保密性

仲裁数字签名

要求:涉及到一个可以信任的仲裁方,仲裁法可以知道消息也可以不知道消息

签名方的报文先签名然后发给仲裁,仲裁者对报文和签名进行测试检验出处和内容,然后注上日期发送给接收方

EIGamal数字签名

EIGamal算法在上面,这里不再重复

若A为B签署m,其中m小于p-1,且m=H(M)

A随机选择小于p-1的与p互素的数k,计算:

\(r = a^kmod(p)\)

再根据r和A的公钥中的Y_A计算:

\(a^m = Y_A^rr^smod(p)\)

\(a^m = a^{X_Ar+ks}mod(p)\)

即:

\(m = (X_Ar+ks) mod (p-1)\)

通过此式求出s,m的数字签名即为(r, s)

例子:

给出p=17, a=3, X_A = 2, X_B = 5, m = 11, k = 5, 求签名并且验证:

解:

先根据k求出\(r = 3^k mod 17 = 5\)

再根据r得到\(m=11=X_Ar+ks = 10+5s mod(17-1)\)得到s = 13

所以数字签名是(5, 13)

验证:

\(a^m mod (p) = 7\)

\(Y_A^r*r^s mod (p) = 7\)

验证完毕