企业官网建设流程全解析

外贸英文网站模板,中国招标信息网,wordpress火箭加速,网站建设在国内外研究现状文章目录计算安全性计算安全的渐进度量方法计算安全的渐进安全度量方法安全规约证明#xff08;重点#xff09;对称加密的窃听不可区分实验#xff08;带n#xff09; #xff08;重点#xff09;计算安全性 计算安全性弱于信息论安全性。它目前也依赖于假设#xff0…文章目录计算安全性计算安全的渐进度量方法计算安全的渐进安全度量方法安全规约证明重点对称加密的窃听不可区分实验带n 重点计算安全性计算安全性弱于信息论安全性。它目前也依赖于假设而实现后者不需要任何假设。计算安全是大多数现代密码学构造方法的目标。计算安全的方案只要给足够的时间和计算能力总能被攻破使用完善保密的加密方案是不必要的。只要在实践上是不可破译的密码方案即可实用如某方案在200年内使用最快的可用的超级计算机也不能以大于10^(−30)的概率攻破。基于计算安全的方法包含两种放宽的完善安全概念对抗可行性时间内运行的敌手安全性存在。敌手成功率很小以至于不关心是否真的存在。计算安全的渐进度量方法渐进方法的核心该方法基于复杂性理论将敌手攻击者的运行时间与成功概率视为安全参数n nn的函数而非具体数值。密码方案包含安全参数n nn诚实双方初始化时选定n nn且假设敌手已知该n nn敌手的运行时间与成功概率均由n nn决定。可行策略与多项式时间将“可行的策略”或“有效的算法”等同于在以n nn为参数的多项式时间内运行的概率算法运行时间表示为a ⋅ n c a \cdot n^ca⋅nc其中a , c a, ca,c为常量。诚实方需在多项式时间内运行敌手虽可能计算能力更强运行时间更长但也在多项式时间内运行超多项式时间的攻击策略因无现实意义而被忽略。小的成功概率与可忽略性将“小的成功概率”等同于成功概率小于任何以n nn为参数的多项式倒数即对任意常量c cc当n nn足够大时概率小于n − c n^{-c}n−c。比任何多项式倒数增长更慢的函数称为“可忽略的negligible”。假设方案安全时敌手运行n 3 n^3n3分钟攻破方案的概率为2 40 ⋅ 2 − n 2^{40} \cdot 2^{-n}240⋅2−n该函数关于n nn可忽略。不同n nn值下的情况当n ≤ 40 n \leq 40n≤40敌手运行约6周40 3 40^3403分钟时攻破概率为1此时n nn无实际意义当n 50 n 50n50敌手运行约3个月50 3 50^3503分钟时攻破概率约1 / 1000 1/10001/1000无法接受当n 500 n 500n500敌手运行超200年时攻破概率仅为2 − 500 2^{-500}2−500。计算安全的渐进安全度量方法有效计算在概率多项式时间内执行的计算。可忽略的成功概率对任意多项式p pp如果攻破该方案的概率渐进小于1 p ( n ) \frac{1}{p(n)}p(n)1​则认为该方案安全否则视为不安全。定义 3.4函数f ff为可忽略的如果对于每个多项式p ( ⋅ ) p(\cdot)p(⋅)存在一个N NN使得对于所有的整数n N n NnN都满足f ( n ) 1 p ( n ) . f(n) \frac{1}{p(n)}.f(n)p(n)1​.等价的公式化的表述是:对所有常量c cc存在一个N NN使得对于所有的n N n NnN满足f ( n ) n − c . f(n) n^{-c}.f(n)n−c.为了方便记忆上面的表述也可以陈述如下对于任意多项式p ( ⋅ ) p(\cdot)p(⋅)以及所有足够大的n nn值满足f ( n ) 1 p ( n ) . f(n) \frac{1}{p(n)}.f(n)p(n)1​.通常将一个可忽略函数表示为negl \text{negl}negl。命题 3.6令negl 1 \text{negl}_1negl1​和negl 2 \text{negl}_2negl2​为可忽略函数。则(1) 函数negl 3 \text{negl}_3negl3​被定义为negl 3 ( n ) negl 1 ( n ) negl 2 ( n ) \text{negl}_3(n) \text{negl}_1(n) \text{negl}_2(n)negl3​(n)negl1​(n)negl2​(n)则该函数是可忽略的。(2) 对于任何正多项式p pp函数negl 4 \text{negl}_4negl4​被定义为negl 4 ( n ) p ( n ) ⋅ negl 1 ( n ) \text{negl}_4(n) p(n) \cdot \text{negl}_1(n)negl4​(n)p(n)⋅negl1​(n)则该函数是可忽略的。安全规约证明重点PPT(Probabilistic Polynomial Time)概率多项式时间。指定有效(概率多项式时间)敌手A \mathcal{A}A攻击方案Π \PiΠ其成功概率为ε ( n ) \varepsilon(n)ε(n)。构造“规约”算法A ′ \mathcal{A}A′将A \mathcal{A}A作为子程序解决难题X \mathcal{X}XA ′ \mathcal{A}A′仅知A \mathcal{A}A想攻击Π \PiΠ对A \mathcal{A}A的内部工作一无所知对难题X \mathcal{X}X的输入实例x xxA ′ \mathcal{A}A′模拟Π \PiΠ的实例使A \mathcal{A}A与Π \PiΠ交互的分布A \mathcal{A}A的分布和A \mathcal{A}A自身与Π \PiΠ交互的分布相同或接近。若A \mathcal{A}A成功“攻破”模拟的Π \PiΠ实例则A ′ \mathcal{A}A′解决X \mathcal{X}X的概率至少为多项式倒数1 / p ( n ) 1/p(n)1/p(n)。若ε ( n ) \varepsilon(n)ε(n)非可忽略则A ′ \mathcal{A}A′解决X \mathcal{X}X的概率为ε ( n ) / p ( n ) \varepsilon(n)/p(n)ε(n)/p(n)非可忽略。因A ′ \mathcal{A}A′有效存在有效算法以非可忽略概率解决X \mathcal{X}X与假设矛盾。结论给定难题X \mathcal{X}X的假设下不存在有效敌手A \mathcal{A}A能以非可忽略概率攻破Π \PiΠ即Π \PiΠ是计算上安全的。对称加密的窃听不可区分实验带n 重点窃听不可区分实验对任何对称密钥方案π ( G e n , E n c , D e c ) \pi (Gen,Enc,Dec)π(Gen,Enc,Dec)任何敌手A \mathcal{A}A以及对任何安全参数n nn的值都适用。窃听不可区分实验PrivK A , Π eav ( n ) : \text{PrivK}_{A,\Pi}^{\text{eav}}(n):PrivKA,Πeav​(n):给定输入1 n 1^n1n给敌手A AA,A AA输出一对长度相等的消息m 0 , m 1 m_0, m_1m0​,m1​运行Gen ( 1 n ) \text{Gen}(1^n)Gen(1n)生成一个密钥k kk, 选择一个随机比特b bb,b ← { 0 , 1 } b \leftarrow \{0,1\}b←{0,1}。一个密文c ← Enc k ( m b ) c \leftarrow \text{Enc}_k(m_b)c←Enck​(mb​)被计算并且给A AA。 把c cc叫做挑战密文。A 输出一个比特b ′ bb′。如果b b ′ b bbb′, 则为1, 否则为0 00。 如果PrivK A , Π eav ( n ) 14 \text{PrivK}_{A,\Pi}^{\text{eav}}(n) 14PrivKA,Πeav​(n)14, 则称A AA成功。定义 3.8如果对于所有的概率多项式时间敌手A \mathcal{A}A存在一个可忽略函数negl \text{negl}negl使得Pr ⁡ [ PrivK A , Π eav ( n ) 1 ] ⩽ 1 2 negl ( n ) \Pr\left[\text{PrivK}_{\mathcal{A},\Pi}^{\text{eav}}(n) 1\right] \leqslant \frac{1}{2} \text{negl}(n)Pr[PrivKA,Πeav​(n)1]⩽21​negl(n)则一个对称密钥加密方案Π ( Gen , Enc , Dec ) \Pi (\text{Gen}, \text{Enc}, \text{Dec})Π(Gen,Enc,Dec)具备在窃听者存在的情况下不可区分的加密其中概率的来源是A \mathcal{A}A的随机性以及实验的随机性。定义 3.9如果对于所有的概率多项式时间的敌手A \mathcal{A}A存在一个可忽略函数negl \text{negl}negl使得∣ Pr ⁡ [ output ( PrivK A , Π eav ( n , 0 ) ) 1 ] − Pr ⁡ [ output ( PrivK A , Π eav ( n , 1 ) ) 1 ] ∣ ⩽ negl ( n ) \left| \Pr\left[\text{output}\left(\text{PrivK}_{\mathcal{A},\Pi}^{\text{eav}}(n,0)\right) 1\right] - \Pr\left[\text{output}\left(\text{PrivK}_{\mathcal{A},\Pi}^{\text{eav}}(n,1)\right) 1\right] \right| \leqslant \text{negl}(n)​Pr[output(PrivKA,Πeav​(n,0))1]−Pr[output(PrivKA,Πeav​(n,1))1]​⩽negl(n)则对称密钥加密方案Π ( Gen , Enc , Dec ) \Pi (\text{Gen}, \text{Enc}, \text{Dec})Π(Gen,Enc,Dec)具有窃听者存在的情况下不可区分性。