《密码学中的可证明安全性-杨波.pdf》由会员分享，可在线阅读，更多相关《密码学中的可证明安全性-杨波.pdf（118页珍藏版）》请在三一文库上搜索。
1、语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案 密码学中的可证明安全性 杨波 陕西师范大学计算机学院 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案 目录 1 语义安全 IND-CPA IND-CCA IND-CCA2 EUF-CMA 规约 2 IBE的背景 3 IBE的安全性 双线性映射 BDH假设 4 选择明文安全的IBE方案 5 选择密文安全的IBE方案 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAI
2、ND-CCA2EUF-CMA规约 单向加密One way encryption 如果敌手已知某个密文， 不能得出所对应的明文的完 整信息， 该公钥加密方案称为单向加密（One way encryption， 简称OWE） ， 是一个很弱的安全概念， 因为不能 防止敌手得到明文的部分信息。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 语义安全 语义安全（Semantic scurity）的概念 由Goldwasser和Micali于1984年提出， 即敌手即使已知某个
3、消息的密文， 也得不出该消息的任何部分信息,即使是1比特 的信息。这一概念的提出开创了可证明安全性领域的先河， 奠定了现代密码学理论的数学基础， 将密码学从一门艺术 变为一门科学。 获得2012年度图灵奖。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 语义安全 加密方案语义安全的概念由不可区分 性(Indistinguishability)游戏（简称IND游戏）来刻画， 这种游 戏是一种思维实验， 其中有2个参与者， 一个称为挑战者 （challenger)， 另一个
4、是敌手。挑战者建立系统， 敌手对系统 发起挑战， 挑战者接受敌手的挑战。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 语义安全 思维实验(（thought experiment）)是用来考察某种假设、 理论或原理的结果而假设的一种实验， 这种实验可能在现 实中无法做到， 也可能在现实中没有必要去做。思维实验和 科学实验一样， 都是从现实系统出发， 建立系统的模型， 然 后通过模型来模拟现实系统。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全
5、的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 科学实验与思维实验 图1-1:科学实验与思维实验 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 科学实验与思维实验 图1-2:科学实验与思维实验 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 科学实验与思维实验 图1-3:薛定谔的猫 系统是真空的、
6、 无光的 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性(IND-CPA) 公钥加密方案在选择明文攻击下的IND游戏（称 为IND-CPA游戏）如下： 1 初始化：挑战者产生系统， 敌手获得系统的公开钥; 2 挑战： 敌手输出两个长度相同的消息m0和m1。挑战者 随机选择b 0,1， 将mb加密， 并将密文（称为目标 密文）给敌手; 3 猜测： 敌手输出b， 如果b= b,则敌手攻击成功。 杨波Cryptology 语义安全IBE
7、的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性(IND-CPA) 公钥加密方案在选择明文攻击下的IND游戏（称 为IND-CPA游戏）如下： 1 初始化：挑战者产生系统， 敌手获得系统的公开钥; 2 挑战： 敌手输出两个长度相同的消息m0和m1。挑战者 随机选择b 0,1， 将mb加密， 并将密文（称为目标 密文）给敌手; 3 猜测： 敌手输出b， 如果b= b,则敌手攻击成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密
8、文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性(IND-CPA) 公钥加密方案在选择明文攻击下的IND游戏（称 为IND-CPA游戏）如下： 1 初始化：挑战者产生系统， 敌手获得系统的公开钥; 2 挑战： 敌手输出两个长度相同的消息m0和m1。挑战者 随机选择b 0,1， 将mb加密， 并将密文（称为目标 密文）给敌手; 3 猜测： 敌手输出b， 如果b= b,则敌手攻击成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIN
9、D-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 敌手的优势可定义为参数k的函数： Adv,A(k) = |Prb = b 1 2| 其中k是安全参数， 用来确定加密方案密钥的长度。因 为任一个不作为的敌手A， 都能通过对b做随机猜测， 而 以1 2的概率赢得IND-CPA游戏。而|Prb = b 1 2|是敌手通过 努力得到的， 故称为敌手的优势。 Defi nition 1.1 如果对任何多项式时间的敌手A， 存在一个可忽略的函 数negl(k)， 使得AdvCPA ,A (k) negl(k)， 那么就称这个加密算 法在选择明文攻击下具有不可区分性， 或者称为IN
10、D-CPA安 全。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 如果敌手通过mb的密文能得到mb的一个比特， 则有可 能区分mb是m0还是m1， 因此IND游戏刻画了语义安全 的概念; 定义中敌手是多项式时间的， 否则因为它有系统的公开 钥， 可得到m0和m1的任意多个密文， 再和目标密文逐 一进行比较， 即可赢得游戏; 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方
11、案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 如果加密方案是确定的， 如RSA算法、Rabin密码体制 等， 每个明文对应的密文只有一个， 敌手只需重新 对m0和m1加密后， 与目标密文进行比较， 即赢得游戏。 因此语义安全性不适用于确定性的加密方案。 与确定性加密方案相对的是概率性的加密方案， 在每次 加密时， 首先选择一个随机数， 再生成密文。因此同一 明文在不同的加密中得到的密文不同， 如ElGamal加密 算法。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IN
12、D-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 例：ElGamal加密算法 1 密钥产生： 设G是阶为大素数q的群,g为G的生成元， 随 机选x Z* q,计算y = gxmodq.以x为秘密钥，(y,g,q)为 公开钥。 2 加密： 设消息m G,随机选一与p 1互素的整数k， 计 算 c1= gkmodq,c2= ykmmodq 密文为c = (c1,c2). 3 解密：m = c2/cx 1modq. 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CC
13、AIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 例：ElGamal加密算法 安全性基于 Diffi e-Hellman判定性问题： 设G是阶为大素 数q的群，g1,g2为G的生成元。没有多项式时间的算法区分 以下2个分布： 随机4元组R = (g1,g2,u1,u2) G4的分布； 4元组D = (g1,g2,u1,u2) G4的分布， 其 中u1= gr 1,u2 = gr 2,r R Zq. 变形： 做代换g1 g,g2 gx,u1 gy,u2 gxy, 2个分布变 为： 3元组R = (gx,gy,gz) G3的分布； 3元组D = (gx,gy,gxy)
14、 G3的分布. 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 例：ElGamal加密算法 在ElGamal加密算法的IND-CPA游戏中， 敌手输出两个 长度相同的消息m0、m1， 挑战者加密mb(b 0,1)， 得C = (C1,C2) = (gkmod p,ykmbmod p)。 如果b = 0， 则 (C1,y,C2/m0) = (gkmod p,gxmod p,gkxmod p) 为 Diffi e-Hellman3元组
15、。 如果b = 1， 则 (C1,y,C2/m1) = (gkmod p,gxmod p,gkxmod p) 为 Diffi e-Hellman3元组。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 例：ElGamal加密算法 然而，IND CPA安全仅仅保证敌手是完全被动情况时 （即仅做监听）的安全， 不能保证敌手是主动情况时（例如 向网络中注入消息）的安全。例如敌手收到密文 为C = (C1,C2)， 构造新的密文C= (C
16、1,C 2)， 其 中C 2 = C2m， 解密询问后得到M = mm。 或者构造新的密文C= (C 1,C 2)， 其中C 1 = C1gk , C 2 = C2yk m ， 此时 C 1 = gkgk = gk+k ,C 2 = ykmyk m = yk+k mm 解密询问后仍得到M = mm。 再由 M m mod p， 得到C的 明文m。可见，ElGamal加密算法不能抵抗主动攻击。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择密文攻击下的不
17、可区分性(IND-CCA) 为了描述敌手的主动攻击，1990年Naor和Yung提出了 （非适应性）选择密文攻击（Chosen Ciphertext Attack， 简称 为CCA）的概念， 其中敌手在获得目标密文以前， 可以访问 解密谕言机(Oracle)。敌手获得目标密文后， 希望获得目标 密文对应的明文的部分信息。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择密文攻击下的不可区分性(IND-CCA) IND游戏（称为IND-CCA游戏）如下：
18、1 初始化：挑战者产生系统， 敌手A获得系统的公开钥。 2 训练： 敌手向挑战者（或解密谕言机）做解密询问（可 多次） ， 即取密文c给挑战者， 挑战者解密后， 将明文给 敌手。 3 挑战： 敌手输出两个长度相同的消息m0和m1， 再从挑战 者接收mb的密文， 其中随机值b 0,1。 4 猜测： 敌手输出b， 如果b= b， 则A成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择密文攻击下的不可区分性(IND-CCA) IND游戏（称为IND-CC
19、A游戏）如下： 1 初始化：挑战者产生系统， 敌手A获得系统的公开钥。 2 训练： 敌手向挑战者（或解密谕言机）做解密询问（可 多次） ， 即取密文c给挑战者， 挑战者解密后， 将明文给 敌手。 3 挑战： 敌手输出两个长度相同的消息m0和m1， 再从挑战 者接收mb的密文， 其中随机值b 0,1。 4 猜测： 敌手输出b， 如果b= b， 则A成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择密文攻击下的不可区分性(IND-CCA) IND游戏（
20、称为IND-CCA游戏）如下： 1 初始化：挑战者产生系统， 敌手A获得系统的公开钥。 2 训练： 敌手向挑战者（或解密谕言机）做解密询问（可 多次） ， 即取密文c给挑战者， 挑战者解密后， 将明文给 敌手。 3 挑战： 敌手输出两个长度相同的消息m0和m1， 再从挑战 者接收mb的密文， 其中随机值b 0,1。 4 猜测： 敌手输出b， 如果b= b， 则A成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择密文攻击下的不可区分性 以上攻击过程也
21、称为“午餐时间攻击”或“午夜攻击” ， 相当于有一个执行解密运算的黑盒， 掌握黑盒的人在午餐 时间离开后， 敌手能使用黑盒对自己选择的密文解密。午餐 过后， 给敌手一个目标密文， 敌手试图对目标密文解密， 但 不能再使用黑盒了。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择密文攻击下的不可区分性 第2步可以形象地看做是敌手发起攻击前， 敌手对自己 的训练（自学） ， 这种训练可通过挑战者， 也可通过解密谕 言机。谕言机也称为神谕、 神使或传神谕者，
22、神谕是古代希 腊的一种迷信活动， 由女祭祀代神传谕， 解答疑难者的叩 问， 她们被认为是在传达神的旨意。因为在IND-CCA游戏 中， 除了要求敌手是多项式时间的， 我们不能对敌手的能力 做如何限制， 敌手除了自己有攻击IND-CCA游戏的能力外， 可能还会借助于外力， 这个外力是谁？是他人还是神， 我们 不知道， 所以统称为谕言机。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择密文攻击下的不可区分性 敌手的优势可定义为参数k的函数： AdvCCA
23、,A (k) = |Prb= b 1 2| Defi nition 1.2 如果对任何多项式时间的敌手A， 存在一个可忽略的函 数negl(k)， 使得AdvCCA ,A (k) negl(k)， 那么就称这个加密算 法在选择密文攻击下具有不可区分性， 或者称为IND-CCA安 全。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在适应性选择密文攻击下的不可区分性(IND-CCA2) 1991年Rackoff和Simon提出了适应性选择密文攻击 （Adapt
24、ive Chosen Ciphertext Attack， 简称为CCA2）的概念， 其中敌手获得目标密文后， 可以向网络中注入消息（可以和 目标密文相关） ， 然后通过和网络中的用户交互， 获得与目 标密文相应的明文的部分信息。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在适应性选择密文攻击下的不可区分性 IND游戏（称为IND-CCA2游戏）如下： 1 初始化：挑战者产生系统， 敌手获得系统的公开钥; 2 训练阶段1： 敌手向挑战者（或解密谕言机）做
25、解密询问 （可多次） ， 即取密文c给挑战者， 挑战者解密后， 将明 文给敌手; 3 挑战： 敌手输出两个长度相同的消息m0和m1， 再从挑战 者接收mb的密文cb， 其中随机值b 0,1; 4 训练阶段2： 敌手继续向挑战者（或解密谕言机）做解密 询问(可多次)， 即取密文c(c = cb)给挑战者， 挑战者解 密后将明文给敌手; 5 猜测： 敌手输出b， 如果b= b， 则A成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在适应性选择密文攻击下的不
26、可区分性 IND游戏（称为IND-CCA2游戏）如下： 1 初始化：挑战者产生系统， 敌手获得系统的公开钥; 2 训练阶段1： 敌手向挑战者（或解密谕言机）做解密询问 （可多次） ， 即取密文c给挑战者， 挑战者解密后， 将明 文给敌手; 3 挑战： 敌手输出两个长度相同的消息m0和m1， 再从挑战 者接收mb的密文cb， 其中随机值b 0,1; 4 训练阶段2： 敌手继续向挑战者（或解密谕言机）做解密 询问(可多次)， 即取密文c(c = cb)给挑战者， 挑战者解 密后将明文给敌手; 5 猜测： 敌手输出b， 如果b= b， 则A成功。 杨波Cryptology 语义安全IBE的背景IBE
27、的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在适应性选择密文攻击下的不可区分性 IND游戏（称为IND-CCA2游戏）如下： 1 初始化：挑战者产生系统， 敌手获得系统的公开钥; 2 训练阶段1： 敌手向挑战者（或解密谕言机）做解密询问 （可多次） ， 即取密文c给挑战者， 挑战者解密后， 将明 文给敌手; 3 挑战： 敌手输出两个长度相同的消息m0和m1， 再从挑战 者接收mb的密文cb， 其中随机值b 0,1; 4 训练阶段2： 敌手继续向挑战者（或解密谕言机）做解密 询问(可多次)， 即取密文c(c
28、= cb)给挑战者， 挑战者解 密后将明文给敌手; 5 猜测： 敌手输出b， 如果b= b， 则A成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在适应性选择密文攻击下的不可区分性 IND游戏（称为IND-CCA2游戏）如下： 1 初始化：挑战者产生系统， 敌手获得系统的公开钥; 2 训练阶段1： 敌手向挑战者（或解密谕言机）做解密询问 （可多次） ， 即取密文c给挑战者， 挑战者解密后， 将明 文给敌手; 3 挑战： 敌手输出两个长度相同的消息m0和
29、m1， 再从挑战 者接收mb的密文cb， 其中随机值b 0,1; 4 训练阶段2： 敌手继续向挑战者（或解密谕言机）做解密 询问(可多次)， 即取密文c(c = cb)给挑战者， 挑战者解 密后将明文给敌手; 5 猜测： 敌手输出b， 如果b= b， 则A成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在适应性选择密文攻击下的不可区分性 IND游戏（称为IND-CCA2游戏）如下： 1 初始化：挑战者产生系统， 敌手获得系统的公开钥; 2 训练阶段1：
30、 敌手向挑战者（或解密谕言机）做解密询问 （可多次） ， 即取密文c给挑战者， 挑战者解密后， 将明 文给敌手; 3 挑战： 敌手输出两个长度相同的消息m0和m1， 再从挑战 者接收mb的密文cb， 其中随机值b 0,1; 4 训练阶段2： 敌手继续向挑战者（或解密谕言机）做解密 询问(可多次)， 即取密文c(c = cb)给挑战者， 挑战者解 密后将明文给敌手; 5 猜测： 敌手输出b， 如果b= b， 则A成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加
31、密方案在适应性选择密文攻击下的不可区分性 敌手的优势可定义为参数k的函数： AdvCCA2 ,A (k) = |Prb = b 1 2| Defi nition 1.3 如果对任何多项式时间的敌手， 存在一个可忽略的函 数negl(k)， 使得AdvCCA2 ,A (k) negl(k)， 那么就称这个加密算 法在适应性选择密文攻击下具有不可区分性， 或者称 为IND-CCA2安全。 在设计抗击主动敌手的密码协议时（如数字签名、 认 证、 密钥交换、 多方计算等） ，IND-CCA2安全的密码系统是 有力的密码原语。原语是指由若干条指令组成的， 用于完成 一定功能的一个过程。 杨波Crypto
32、logy 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 签名体制的语义安全性(EUF-CMA) 签名体制= (KeyGen,Sign,Ver)一般由以下三个算法 组成： 1 密钥生成(KeyGen)： 该算法输入1k， 输出密钥对(pk,sk); 2 签名： 输入消息m， 秘密钥sk， 输出 = Sign(m,sk) ; 3 验证： 输入， 消息m， 公开钥pk， 输 出Ver(,m,pk) = T或。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文
33、安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 签名体制的语义安全性(EUF-CMA) 签名体制= (KeyGen,Sign,Ver)一般由以下三个算法 组成： 1 密钥生成(KeyGen)： 该算法输入1k， 输出密钥对(pk,sk); 2 签名： 输入消息m， 秘密钥sk， 输出 = Sign(m,sk) ; 3 验证： 输入， 消息m， 公开钥pk， 输 出Ver(,m,pk) = T或。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规
34、约 签名体制的语义安全性(EUF-CMA) 签名体制= (KeyGen,Sign,Ver)一般由以下三个算法 组成： 1 密钥生成(KeyGen)： 该算法输入1k， 输出密钥对(pk,sk); 2 签名： 输入消息m， 秘密钥sk， 输出 = Sign(m,sk) ; 3 验证： 输入， 消息m， 公开钥pk， 输 出Ver(,m,pk) = T或。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 签名体制的语义安全性 签名体制的语义安全性， 由以下不可伪造（Exist
35、ential 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攻击成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 签名体制的语义安全性 签名体制的语义安
36、全性， 由以下不可伪造（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攻击成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 签名
37、体制的语义安全性 签名体制的语义安全性， 由以下不可伪造（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攻击成功。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND
38、-CCA2EUF-CMA规约 签名体制的语义安全性 A的优势为它获胜的概率， 记为AdvSigCMA ,A (k)， 其中k 为安全参数。 Defi nition 1.4 签名体制= (KeyGen,Sign,Ver)称为在适应性选择消息攻 击下具有存在性不可伪造性(Existential Unforgeability Against Adaptive Chosen Messages Attacks，EUF-CMA)， 简称 为EUF-CMA安全， 如果对任何多项式有界时间的敌手， 存在 一个可忽略的函数negl(k)， 使得 AdvSigCMA ,A (k) negl(k) 杨波Crypto
39、logy 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 签名体制的语义安全性 例：RSA签名体制 RSA签名体制不是EUF-CMA安全的， 其EUF游戏如下: 初始阶段： 挑战者产生系统的密钥 对pk = (e,n),sk = (d,n)， 将pk发送给敌手A并且保 密sk; 阶段1(签名询问)：A执行以下的多项式q = q()有界次 适应性询问; A提交mi， 其中某个mj= re m， 挑战者计 算si md i mod n(i = 1,.,q)并返回给A; 杨波Cryptology 语义安
40、全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 签名体制的语义安全性 例：RSA签名体制 输出：A输出(m,) = (m,sj/r)， 因 为sj (rem)dmod n rmdmod n， 所 以sj/r mdmod n， 即为m的签字。 m不出现在阶段1且Ver(,m,pk) = T。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约(reduction) 有了以上安全定义
41、后， 通常使用规约的方法来证明方 案满足定义。 规约是复杂性理论中的概念， 一个问题P1规约到问 题P2是指， 已知解决问题P1的算法M1， 我们能构造另一算 法M2，M2可以以M1作为子程序， 用来解决问题P2。 把规约方法用在密码算法或安全协议的安全性证明， 可把敌手对密码算法或安全协议（问题P1）的攻击规约到一 些已经得到深入研究的密码本原（问题P2） 。即如果敌手能 够对算法或协议发起有效的攻击， 就可以利用敌手构造一 个算法来攻破密码本原， 从而得出矛盾。根据反证法， 敌手 能够对算法或协议发起有效的攻击的假设不成立。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择
42、明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 一般地， 为了证明方案1的安全性， 我们可将方案1规约 到方案2， 即如果敌手A能够攻击方案1， 则敌手B能够攻击 方案2， 其中方案2是已证明安全的， 或是一困难问题， 或是 一密码本原。 证明过程还是通过思维实验来描述， 首先由挑战者建 立方案2， 方案2中的敌手用B表示， 方案1中的敌手用A表 示。B为了攻击方案2， 它利用A作为子程序来攻击方 案1。B为了利用A， 它可能需要对A加以训练， 因此B又模 拟A的挑战者。 杨波Cryptology 语义安全IBE的背景IBE的安
43、全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 图2:两个方案之间的规约 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 具体步骤如下： 1 挑战者产生方案2的系统; 2 敌手B为了攻击方案2， 接受挑战者的训练; 3 B为了利用敌手A， 对A进行训练， 即作为A的挑战者; 4 A攻击方案1的系统; 5 B利用A攻击方案1的结果， 攻击方案2。 杨波Cryptology 语义安全IBE的背景I
44、BE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 具体步骤如下： 1 挑战者产生方案2的系统; 2 敌手B为了攻击方案2， 接受挑战者的训练; 3 B为了利用敌手A， 对A进行训练， 即作为A的挑战者; 4 A攻击方案1的系统; 5 B利用A攻击方案1的结果， 攻击方案2。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 具体步骤如下： 1 挑战者产生方案2的系统; 2 敌手B为了攻击方
45、案2， 接受挑战者的训练; 3 B为了利用敌手A， 对A进行训练， 即作为A的挑战者; 4 A攻击方案1的系统; 5 B利用A攻击方案1的结果， 攻击方案2。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 具体步骤如下： 1 挑战者产生方案2的系统; 2 敌手B为了攻击方案2， 接受挑战者的训练; 3 B为了利用敌手A， 对A进行训练， 即作为A的挑战者; 4 A攻击方案1的系统; 5 B利用A攻击方案1的结果， 攻击方案2。 杨波Cryptology 语义安全I
46、BE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 具体步骤如下： 1 挑战者产生方案2的系统; 2 敌手B为了攻击方案2， 接受挑战者的训练; 3 B为了利用敌手A， 对A进行训练， 即作为A的挑战者; 4 A攻击方案1的系统; 5 B利用A攻击方案1的结果， 攻击方案2。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 对于加密算法来说， 图2中的方案1取为加密算法， 如果
47、 其安全目标是语义安全， 即敌手A攻击它的不可区分性， 敌 手B模拟A的挑战者， 和A进行IND游戏。称此时A对方案1的 攻击为模拟攻击。在这个过程中，B为了达到自己的目标， 而利用A，A也许不愿意被B利用。如果A不能判别是和自己 的挑战者交互还是和模拟的挑战者交互， 则称B的模拟是完 备的。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 规约 对于其他密码算法或密码协议来说， 我们首先要确定 它要达到的安全目标， 如签名方案的不可伪造性等， 然后构 造一个形式化的敌手
48、模型及思维实验， 再利用概率论和计 算复杂性理论， 把对密码算法或密码协议的攻击规约到对 已知困难问题的攻击。这种方法就是可证明安全性。 可证明安全性是密码学和计算复杂性理论的天作之合。 过去30年， 密码学的最大进展是将密码学建立在计算复杂 性理论之上， 并且正是计算复杂性理论将密码学从一门艺 术发展成为一门严格的科学。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案 CA可能成为系统的瓶颈 公钥密码体制 CA（ Certifi cate Authority） ， 负责用户公钥证书生命周期 的每一个环节： 生成、 签发、 存贮、
49、维护、 更新、 撤销等 CA有可能成为系统的瓶颈。 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案 基于身份的公钥密码体制 基于身份的公钥密码体制， 从根本上改变传统CA公钥 体制架构中证书的管理和运作 基于身份的公钥体制的思想最早由Shamir于1984年提 出， 方案中不使用任何证书， 直接将用户的身份作为公 钥， 以此来简化公钥基础设施PKI（Public Key Infrastructure）中基于证书的密钥管理过程 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案 基于身份的加密算法如何工作？ 图3:基于身份的加密方案示例 杨波Cryptology 语义安全IBE的背景IB