密码学中的可证明安全性-杨波.pdf
《密码学中的可证明安全性-杨波.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: 敌手向挑战者(或解密谕言机)做
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 密码学 中的 证明 安全性 杨波
链接地址:https://www.31doc.com/p-3333173.html