原创：岐山凤鸣
引用需注明本站域名。
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\)
验证完毕