[数据结构与算法]数字签名算法2--可证明安全与EIGamal算法

密码学中可证明安全

可证明安全理论基础：
一般来讲，可证明安全是指利用数学中的反证法思想，采用一种“归纳”方法。
协议的安全目标：加密方案的安全目标是确保信息的机密性，签名方案的安全目标是确保签名的不可伪造性。
敌手目标：加密方案中，敌手的目标就是能够区分挑战密文所对应的明文；在签名方案中，敌手的攻击目标就是可以获得签名者私钥，也可以说能对任意消息伪造签名或者伪造出一个特定消息的有效签名。
极微本原：密码原语，是指安全方案或者协议的最基本组成构建或者模型，例如某个基础密码算法或者数学难题。
步骤：
（1） 给出密码方案或者协议形式化定义
（2） 给出密码方案或者协议要达到的安全目标
（3） 给出安全模型，也就是攻击者具有的攻击目标或者行为
（4） 通过把攻击者的成功攻击规约到解决一个“极微本原“来达到算法或者协议形式化证明
安全模型：定义方案安全性关键所在，在可证明安全框架下，对一个方案的安全性往往需要从两个方面定义：敌手的攻击目标和攻击行为。攻击行为描述敌手为了达到攻击目标所采取的行动
归约论断：简单来说，就是把一个复杂的方案的安全性问题归结到一个或者几个困难问题。
解释归约：一般地，为了证明方案1的安全性，我们可将方案1归约到方案2，即如果敌手A能够攻击方案1，则敌手B能够攻击方案2，其中方案2是已证明安全的，或是困难问题，或是密码本原。 证明过程是通过思维实验来描述，首先由挑战者建立方案2，方案2中的敌手用B表示，方案1中的敌手用A表示。B为了攻击方案2，它利用A作为子程序来攻击方案1。B为了利用A，它可能需要对A加以训练，因此B又模拟A的挑战者。

对于加密算法来说，图中的方案1取为加密算法，如果其安全目标是语义安全，即敌手A攻击它的不可区分性，敌手B模拟A的挑战者，和A进行IND游戏。
对于签名算法来说，图中的方案1取为签名算法，如果其安全目标是“在适应性选择消息攻击下具有存在不可伪造性”，即敌手A攻击它的不可伪造性，敌手B模拟A的挑战者，和A进行EUF游戏。

数字签名算法安全模型分析

攻击目标：如果敌手A以不可忽略的概率完成以下操作，我们说A攻破了签名方案。
（1） 完全攻破：揭示出签名者私钥
（2） 普遍性伪造：构造出一个可对任意消息进行签名的高成功率伪签名算法
（3） 选择消息伪装：构造出某个特定消息的有效签名
（4） 存在性伪造：攻击者至少能为某个消息产生一个有效签名，但敌手对他获得的消息及其签名没有任何控制作用。
攻击能力：攻击者的攻击能力类型可以分为两大类
（1） 唯密钥攻击：攻击者只知道签名者的公钥，而没有任何其他信息。
（2） 已知签名攻击：攻击者除了知道签名者的公钥外，还可以得到一些消息/签名对，其中已知签名攻击又可以分为以下四种
（i）简单的已知消息攻击：攻击者可以得到一些消息/签名对，但不可以任意选择
（ii）普通的选择消息攻击：攻击者可以选择一些消息请求签名得到消息签名对，但选择是在知道签名者公钥前进行，这类攻击并不针对特定签名者
（iii）定向的选择消息攻击：攻击者可以选择一些消息请求签名得到消息/签名对，但选择是在知道签名者公钥之后进行并完成的，这类攻击指向某个特定签名者。
（iv）适应性选择消息攻击，攻击者可以选择一些消息请求签名以得到消息/签名对,并且他可以根据已得到的消息/签名对选择新的消息请求签名。
为了实现其最强的安全性，总以最强的攻击能力实现最低的攻击目标。因此目前数字签名的安全性定义一般是指适应性选择消息攻击下的签名存在行不可伪造(Existential Unforgeability Against Adaptive Chosen Messages Attacks，EUF-CMA)，简称 为EUF-CMA。
随机语言机模型（random oracle,RO）:在建立起安全模型后，往往需要构造一个算法B来充当挑战者的角色，算法B的输入是困难问题的一个实例，而B的目标就是通过一个假设存在的敌手进行多项式时间内的交互，最终输出该实例的解。由于B并不知道签名密钥或者解密密钥，所以需要用某些手段来掩饰B不知道密钥这件事，即为敌手提供一个真实的攻击环境，让敌手认为他在和一个真实的挑战者在进行游戏。
从Hash函数抽象出来一种计算模型，称为随机预言模型（RO模型）。在证明过程中，把Hash函数的输出认为是随机的，任何人都只能通过访问Hash语言机来求Hash的值，这样子。通过掌控Hash函数的输出，C就有可能在为敌手提供真实攻击环境下。利用敌手的攻击能力去求得困难问题实例的解。

可证明安全的思想就是给定一个算法A，我们提出一个新算法B，B把A作为子程序。输入给B的是我们希望解决的困难问题，输入给A的是某个密码算法然而，如果A是一个积极攻击敌手，即A可以对输入的公钥进行解密预言询问或签名预言询问。算法B要想使用A作为子程序，就需对A的询问提供回答。它的回答应该看起来是合法的。因为加密应该能够解密，签名应该能够被验证,否则算法A就知道它的预言机在撒谎。算法B就不能再确保算法A是以一个不可忽略的概率成功。我们必须让B在不知道私钥的情况下能够解密或者签名，但既然我们的体制是安全的，这一点意味着是不可能的。为了回避这个问题，我们通常使用随机预言模型。
随机预言是一个理想的Hash函数。对于每一个新的询问，随机预言产生一个随机值作为回答，如果进行两次相同的询问，回答一定相同。在随机预言模型中，我们假设敌手并不使用密码算法中定义的那个Hash函数，也就是说，即使我们将随机预言换成真实的Hash函数时，敌手A也是成功的。
对于A的解密预言询问和签名预言询问，算法BA是通过欺骗随机预言的回答来适合自己的需要的。

签名体制语义安全

签名体制 ∏? = (KeyGen, Sign, Ver) 一般由以下三个算法 组成：
1 密钥生成(KeyGen)：该算法输入1 k，输出密钥对(pk, sk);
2 签名：输入消息m，秘密钥sk ，输出𝜎 = Sign(m, sk) ;
3 验证：输入𝜎，消息m，公开钥pk，输出Ver(𝜎, m, pk) = T或⊥。
签名体制的语义安全性，由以下不可伪造（Existential Unforgeability）游戏（简称EUF游戏）来刻画。
1 初始阶段：挑战者产生系统的密钥对(pk, sk) ，敌手A获得系统的公开钥;
2 阶段1(签名询问)：A执行以下的多项式有界次适应性询问; A提交mi ，挑战者计算𝜎i = Sign(mi , sk) 并返回给A;
3 输出：A输出(m, 𝜎) ，如果m不出现在阶段1且Ver(𝜎, m, pk) = T ，则A攻击成功。
举例：ElGamal的安全性
定理：如果DDH问题是困难的，那么EIGamal加密体制在选择明文攻击下是多项式安全的。
证明:为了显示EIGamal是多项式安全的，我们首先假设存在一个能够攻
ElGamal加密算法
密钥产生：设G是阶为大素数q的群,g为G的生成元，随机选 ,计算y = $g^x$ modq. 以x为秘密钥，(y, g, q)为公开密钥
加密：设消息 , 随机选一与q-1互素的整数k，计算c1 = $g^k$modq, c2 = $y^k$mmodq, 密文为c = (c1, c2).
解密：
EIGamal多项式安全性。多项式时间算法A，然后我们给出一个使用算法A作
为子程序的算法B来解决DDH问题。
EIGamal密文为:($g^k$, m$h^k$)其中k是一个随机整数，h是公钥。
给定$g^x$、$g^y$和$g^z$，解决DDH问题的算法B执行如下步骤:
② 令h=$g^k$
②(m0,m1,s) =A (寻找阶段, h)
③ 设置c1=$g^y$。
④ 从{0,1}中随机选择一个数b。
⑤ 设置c2=mb$g^z$。
⑥ b’=A ( 猜测阶段, (c1, c2), h, m0, m1,s) // 区分$g^x$、$g^y$和$g^z$
⑦ 如果b=b’，输出“TRUE”，否则输出“FALSE”。
分析为什么算法B解决了DDH问题。
当z=xy，在猜测阶段输入给算法A的将是mb的一个合法加密。如果算法A真正能够攻破EIGamal的语义安全性，那么输出的b’将是正确的，算法B将输出“TRUE”。
当z≠xy时，在猜测阶段输入给算法A的几乎不可能是合法的密文，即不是m;或m的加密，在猜测阶段输出的b’与b将是独立的。因此，算法B将以相
等的概率输出“TRUE”"或“FALSE”

Elgamal加密体制不是CCA2安全的。
假设敌手想解密:c=(c1 ,c2)=($g^k$,m$g{h}^x$)
敌手首先生成一个相关的密文c’=(c1, 2c2)并询问解密预言机。敌手得到c’的明文m’。然后敌手计算: （倍数关系）

ElGamal签名算法

在系统中有两个用户A和B，A要发送消息到B，并对发送的消息进行签名。B收到A发送的消息和签名后进行验证。
选取一个大的素数p，g是GF§的生成元。h：GF§→GF§，是一个单向Hash函数。系统将参数p、g和h存放于公用的文件中，在系统中的每一个用户都可以从公开的文件中获得上述参数。
数字签名：
假定用户A要向B发送消息m∈[1,p-1] ，并对消息m进行签名
第一步：用户A选取一个 k∈[1,p-1]作为秘密密钥，计算y=$g^x$modp 作为公钥。将公钥y存放于公用的文件中。
第二步：随机选取 k∈[1,p-1] 且gcd(k,p-1)=1
第三步：计算 r=$g^k$modp及s=$k^{?}1$(m-xr)modp
第四步：A将 (m,r,s)发送到B
签名验证：
B接收到A发送的消息 ，从系统公开文件和A的公开文件中获得系统公用参数p，g，h和A的公钥y。
第一步：B计算 left=$g^m$modp
第二步：B计算 right=$y^r{r}^s$modp
第三步：比较left和right，相等则通过验证

分析，无法抵抗普通的选择消息攻击：攻击者可以选择一些消息请求签名得到消息签名对，但选择是在知道签名者公钥前进行，这类攻击并不针对特定签名者
向任意用户请求消息m1的签名，得到 r1=$g^{k}1$modp及s=$k{1}^{?}1$(m1-xr1)modp ；
向任意用户请求消息m2的签名，得到 r2=$g^{k}2$modp及s=$k{2}^{?}1$(m2-xr2)modp ；
发送签名（ m1+m2, r1xr2,s1xs2 ）
验证
改进，对m进行hash
注，CSDN公式输入有点难搞啊，其中1,2数字均为小标，就不一一改正了，参考证明过程中用到的符号，如有错误，望指正