精华内容
下载资源
问答
  • 可证明安全
    千次阅读
    2021-05-03 15:05:54

    总述

    现代密码学中的安全标准有3个:
    (1) 计算安全: 考虑攻破一个密码算法所需的计算开销. 若攻破一个密码算法的最优算法所做操作是n次, 则称该密码算法是计算安全的. 但实际上没有一个实例属于计算安全, 目前仅是一个理论概念.

    (2) 可证明安全: 基本思想基于数学中的反证法, 通过"规约"的方式将密码算法安全性规约到某个公认的数学难题, 比如大数分解, 素数域离散对数分解问题. 若存在攻破密码算法的攻击方式, 则可以利用该方式构造出攻破数学难题的方法.
    实现一个密码算法的可证明安全, 大致步骤有

    • 给出密码算法的形式化定义
    • 给出密码算法的安全目标
    • 给出密码算法的安全模型, 包括攻击者的目标和攻击者的攻击能力
    • 对攻击者的攻击过程进行规约, 利用攻击方法解决数学难题

    (3) 无条件安全: 假设攻击者拥有无限计算能力, 无限计算资源, 仍然不能攻破密码算法, 则密码算法是无条件安全的. 显然这是一种理想化的概念, 实际中基本不存在.

    安全模型

    可证明安全中需要证明攻击者采取最强的攻击能力, 依然不能实现最弱的攻击目标, 则称密码算法是可证明安全的.

    安全目标

    主要分为3类
    (1) 不可区分性 (IND)
    需要攻击者成功攻破算法的优势是多项式时间内不可区分的函数, 攻击者提交等长明文消息 M 0 , M 1 M_0 , M_1 M0,M1, 挑战者随机选择 M β , β ∈ { 0 , 1 } M_\beta, \beta \in \{0,1\} Mβ,β{0,1}, 加密后得到密文 C C C, 发送给攻击者, 攻击者对 C C C进行判断, 是 M 0 M_0 M0或者 M 1 M_1 M1加密后的结果, 即判断 β ′ ∈ { 0 , 1 } \beta' \in \{0,1\} β{0,1}, 定义攻击者攻破密码算法的优势为
    A d v ( A ) = ∣ 2 P r [ β ′ = β ] − 1 ∣ Adv(\mathcal{A}) = | 2 Pr[\beta' = \beta] - 1| Adv(A)=2Pr[β=β]1
    如果优势是可以忽略的, 则称密码算法实现了多项式时间内的不可区分性安全.
    解释: 如果单纯随机猜测 β ′ \beta' β显然概率是50%, 则攻击者的优势为0, 可忽略, 所以单纯猜测是不能攻破密码算法的, 需要某种方式(或许不存在)把攻破密码算法的优势提升到不可忽略的地步, 才能算攻破算法.

    (2) 非延展性安全 (NM)
    得到明文M对应的密文C, 要求攻击者 A \mathcal{A} A无法构造不同的密文C’, 使C’对应的明文M’和M存在某种关联, 且 A \mathcal{A} A可以得知这种关联关系.

    (3) 单向安全性 (OW)
    要求公钥密码方案实现单向安全性, 即攻击者从公开参数不能解密密文.

    小结:
    通常OW要求比IND和NM低, NM的安全性证明最困难, 所以大部分安全性证明是基于IND.


    攻击能力

    攻击者的攻击能力分为4类
    (1) 唯密文攻击 (COA)
    攻击者只知道密文.

    (2) 已知明文攻击 (KPA)
    攻击者知道一些明文-密文对

    (3) 选择明文攻击 (CPA)
    攻击者可以选择特定明文-密文对, 如果还可以在攻击过程中, 调整明文选择, 且得到对应密文, 称为适应性CPA.

    (4) 选择密文攻击 (CCA)
    攻击者可以选择特定密文-明文对, 如果还可以在攻击过程中, 调整密文选择, 且得到对应明文, 称为适应性CCA. 普通CCA称为CCA1, 适应性CCA称为CCA2.

    总结

    同时考虑安全目标和攻击能力两个方面, 主要的安全组合有6类

    • IND-CPA
    • IND-CCA1
    • IND-CCA2
    • NM-CPA
    • NM-CCA1
    • NM-CCA2

    IND-CCA2, NM-CCA2安全性最强. IND-CPA又称为语义安全, 主要的CP-ABE问题都是基于IND-CPA安全. 另外IND-CPA下安全方案有某种通用方法转换为IND-CCA.

    更多相关内容
  • 《密码学中的可证明安全性》书籍扫描版,杨波,清华大学出版社
  • 长期以来,人们对于可证明安全的认识存在着一些误区:可证明安全的方案一定是安全的,归约证明紧的一定比归约松的更安全。总结了与方案安全性有关的几个要素,分析了公钥密码方案可证明安全的实质,纠正了以往的一些...
  • 密码学中的可证明安全性-杨波-2014.11.11
  • 针对社交网络隐私保护方案的安全性证明问题,提出了一种可证明安全的社交网络隐私保护方案。首先,通过分析社交网络中节点隐私的安全需求(不区分的节点结构和不区分的发送消息),分别建立其安全模型;其次,...
  • 采用归约的可安全证明方法证明该方案的安全性归约为计算Diffie-Hellman难题、分布式密钥生成协议(DKG)和联合的零秘密共享协议(JZSS)的安全性,从而说明该方案有存在性、不伪造和抗合谋攻击的安全特性。
  • 针对理性委托计算中的安全性需求问题,提出了一种可证明安全的理性委托计算协议。首先,在委托计算中引入博弈理论并分析理性参与者的行为偏好,并且在博弈论框架下构建理性委托计算博弈模型;其次,根据博弈模型中的...
  • 通过对RFID系统特殊安全问题的系统研究,从可证明安全论证的角度出发,本文提出了一种可证明安全的RFID通信安全协议——rPAP。在随机预言模型下,使用形式化描述方式,系统地建立了RFID通信安全模型,并在该模型下,...
  • 摘 要:提出一种可证明安全的智能移动终端私钥保护方案。充分利用口令保护、密钥分割与服务器动态交互获取部分私钥等技术保证用户私钥安全。与其他方案相比,该方案的优势在于:减少了智能移动终端的计算量和存储量...
  • 学习可证明安全的入门资料,非常值得读一遍,经典PPT
  • 论文研究-可证明安全的基于RSA的远程用户口令认证协议.pdf, 身份认证是确保信息系统安全的基本手段,基于RSA的认证协议由于实用性较强而成为近期研究热点.讨论了Xie等...
  • 为了全面清晰地描述可证明安全公钥加密体制的研究现状,从时间和核心技术两个角度对主流基础公钥加密体制可证明安全性研究进行了系统的描述。给出了可证明安全公钥加密体制研究的发展历程、核心技术流派和研究现状,...
  • 可证明安全理论基础: 一般来讲,可证明安全是指利用数学中的反证法思想,采用一种“归纳”方法。 协议的安全目标:加密方案的安全目标是确保信息的机密性,签名方案的安全目标是确保签名的不伪造性。 敌手目标:...

    密码学中可证明安全

    可证明安全理论基础:
    一般来讲,可证明安全是指利用数学中的反证法思想,采用一种“归纳”方法。
    协议的安全目标:加密方案的安全目标是确保信息的机密性,签名方案的安全目标是确保签名的不可伪造性。
    敌手目标:加密方案中,敌手的目标就是能够区分挑战密文所对应的明文;在签名方案中,敌手的攻击目标就是可以获得签名者私钥,也可以说能对任意消息伪造签名或者伪造出一个特定消息的有效签名。
    极微本原:密码原语,是指安全方案或者协议的最基本组成构建或者模型,例如某个基础密码算法或者数学难题。
    步骤:
    (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 g^x gx modq. 以x为秘密钥,(y, g, q)为公开密钥
    加密:设消息 , 随机选一与q-1互素的整数k,计算c1 = g k g^k gkmodq, c2 = y k y^k ykmmodq, 密文为c = (c1, c2).
    解密:
    EIGamal多项式安全性。多项式时间算法A,然后我们给出一个使用算法A作
    为子程序的算法B来解决DDH问题。
    EIGamal密文为:( g k g^k gk, m h k h^k hk)其中k是一个随机整数,h是公钥。
    给定 g x g^x gx g y g^y gy g z g^z gz,解决DDH问题的算法B执行如下步骤:
    ② 令h= g k g^k gk
    ②(m0,m1,s) =A (寻找阶段, h)
    ③ 设置c1= g y g^y gy
    ④ 从{0,1}中随机选择一个数b。
    ⑤ 设置c2=mb g z g^z gz
    ⑥ b’=A ( 猜测阶段, (c1, c2), h, m0, m1,s) // 区分 g x g^x gx g y g^y gy g z g^z gz
    ⑦ 如果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 g^k gk,m g h x gh^x ghx)
    敌手首先生成一个相关的密文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 g^x gxmodp 作为公钥。将公钥y存放于公用的文件中。
    第二步:随机选取 k∈[1,p-1] 且gcd(k,p-1)=1
    第三步:计算 r= g k g^k gkmodp及s= k − 1 k^-1 k1(m-xr)modp
    第四步:A将 (m,r,s)发送到B
    签名验证:
    B接收到A发送的消息 ,从系统公开文件和A的公开文件中获得系统公用参数p,g,h和A的公钥y。
    第一步:B计算 left= g m g^m gmmodp
    第二步:B计算 right= y r r s y^rr^s yrrsmodp
    第三步:比较left和right,相等则通过验证

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

    展开全文
  • 可证明安全的基于RSA的远程用户口令认证协议
  • CFL可证明安全性分析 域名系统安全
  • 具有可证明安全性的Schnorr签名的无下意识变体
  • 高效可证明安全的基于属性的在线/离线加密机制
  • 针对标准模型下抗适应性选择密文攻击语义安全的公钥加密方案存在的效率比较低或者所基于的计算假设比较强的问题,基于最近提出的d-判定性Diffie-Hellman问题构造了一个新的可证明安全的公钥加密方案。方案的构造和...
  • 可证明安全的抗量子两服务器口令认证密钥交换协议.docx
  • 安全技术-网络信息-AdHoc网络可证明安全的群组密钥协商协议研究.pdf
  • 研究了聚合签名技术,分析了基于RSA算法的顺序聚合签名体制的安全性,发现算法存在安全缺陷,为了克服原方案的安全缺陷,基于PSS(probabilistic signature scheme)算法下,提出了一种可证明安全的顺序聚合签名方案...
  • 密码学可证明安全CCA1

    千次阅读 2020-08-04 17:50:28
    密码学可证明安全CCA1 安全规约推荐书目: 《密码学中的可证明安全性》杨波 清华大学出版社 《Introduction to Security Reduction》Fuchun Guo;Willy Susilo;Yi Mu Springer 首先,关于密码学中的可证明安全放...

    密码学可证明安全CCA1

    安全规约推荐书目:

    《密码学中的可证明安全性》杨波 清华大学出版社     

    《Introduction to Security Reduction》Fuchun Guo;Willy Susilo;Yi Mu Springer

    首先,关于密码学中的可证明安全放一张老图:

                                   

    证明方法大类是两种:基于游戏的证明,基于模拟的证明;

    基于游戏的证明又分为 安全规约,游戏跳跃。

    安全规约部分在这本书中有比较详细的描述:

    《Introduction to Security Reduction》Fuchun Guo;Willy Susilo;Yi Mu Springer

    CCA1 安全方案及证明 在《密码学中的可证明安全性》有一个较好的游戏跳跃的例子如下:

    Noar-Yung CCA方案

    方案描述如下:

                              

    证明:

    安全定理描述如下:

                             

    证明思路:

                按照CCA安全模型,有以下的两个实验即为敌手输出两个等长消息m0,m1 模拟者随机选择加密,敌手不可区分,这里分别独立出这两个实验路径如下:

                                 

    如果能证明这两个实验不可区分,那么就能证明这个方案是CCA安全的。实验的不可区分这里是使用一个一个不可区分游戏传递的。通过将逐步的修改实验1的参数,生成一个一个游戏,然后逐步证明这些游戏不可区分,最终就能证明这两个游戏不可区分。与安全规约不同的是,安全规约这里一般直接将区分方案规约到敌手拥有解决某个困难问题的能力上来。

    《可证明安全性》对这两个实验不可区分证明动机描述如下:

                            

    7个游戏主要特点如下:

    最终证明的图示如下:

    1. Exp0与 Exp1 不可区分:由于零知识证明的零知识性可得。

    2. Exp1 与 Exp2 不可区分:对于敌手而言,这相当于区分CT1是M1的密文还是M0的密文,由该方案的CPA安全,可得不可区分,并且此处不需要解密CT1。

    3. Exp2 与 Exp3 不可区分:如果敌手能伪造一个不同明文的合法挑战密文,则就可以区分这个两个实验,因为解密结果会变得不同,但是由于零知识系统的可靠性,敌手不能伪造出整个证明,所以不可能发生敌手使用不同秘钥鉴别出区别的情况,所以不可区分。如果对应明文相同,那么CT0.CT1 用任意秘钥解出内容没有差别。

    4 Exp3与Exp4 不可区分:由于加密方案的CPA安全,所以不可区分。

    5.Exp4与Exp5 不可区分:与第三项实验2 与3 的不可区分原因相同。

    6.Exp5 与 Exp6 不可区分:与第一项实验0与实验1的不可区分原因相同。

     

    展开全文
  • 可证明安全变门限代理重签名方案
  • 可证明安全的基于证书聚合签名方案
  • 关于无需配对的可证明安全的基于环的证书的安全性
  • 第11届可证明安全国际会议论文集(2017年ProvSec),该会议于2017年10月23日至25日在中国西安召开。会议由陕西师范大学,西安电子科技大学和西安邮电大学共同组织。
  • 格上基于密文标准语言的可证明安全两轮口令认证密钥交换协议.docx
  • 可证明安全的基于证书的密钥隔离签名方案
  • 船用无线传感器网络中可证明安全的双模式公开验证计算协议
  • 迈向基于多项式同构的可证明安全的代理签名方案

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 264,508
精华内容 105,803
关键字:

可证明安全

友情链接: ok4.zip