斯坦福Dan Boneh密码学——02 计算密码与语义安全
语义安全这块内容实在是被书绕晕了,虽然模型就那么一个,但有各种各样的数学符号交织证明,还有官方深奥的语言表述。第一次看是一知半解的,后面势必还要再返回来精读几遍完善笔记。以篇幅来看,语义安全是密码学中非常重要的一个版块。
计算密码与语义安全
我们还是希望能够使用短密钥加密长消息。围绕香农定理的唯一方法是放宽我们的安全要求。我们这样做的方式不是考虑所有可能的对手,而是只考虑计算上可行的对手,即“真实世界”的对手,他们必须使用合理的时间和内存在真实计算机上执行计算。这将导致称为语义安全的安全性定义减弱。
计算密码的定义
计算密码本身是一对有效的算法E和D。加密算法E将密钥k和消息m作为输入,并将密文c作为输出。其实类似于香农密码,只是其密钥位于某个有限密钥空间k中,消息位于有限消息空间m中,密文位于有限密文空间c中。我们将允许加密函数E是一种概率算法,这意味着对于固定输入k和m,E(k,m)的输出可能是多个值之一。
这表示一个执行E(k,m)并将输出分配给程序变量c的过程。虽然可以允许解密算法具有概率性,但我们不需要这样做,因此只讨论具有确定性解密算法的密码。然而,有时允许解密算法返回一个特殊的拒绝值(不同于所有消息)会很方便,这表明解密过程中发生了某种错误。在一般情况下,我们可以更正式地声明正确性要求:
确定性密码与香农密码
一次性密码、可变长度一次性密码和附加一次性密码都是确定性密码。如果字母∑不太大,那么替换密码也是如此。任何确定性密码都是香农密码;然而,计算密码不必是香农密码(如果它有概率加密算法),香农加密不必是计算密码(如果其加密或解密操作没有有效的实现)。
语义安全
在完美安全性公式中,我们对于密文空间上的所有谓词φ,以及所有消息m0、m1,都有以下定义:
上述式子中k是均匀分布在密钥空间k上的随机变量。现在我们做出一些改变,不再坚持k的取值概率相等,我们只要求它们非常接近;也就是说:
这里的
ϵ
\epsilon
ϵ 当然可以取一些非常小或可以忽略不计的值。它的意义在于,我们不要求完美安全的式子对每一个可能的φ、m0和m1都成立,虽然并非完全安全,但我们可能愿意说,该密码在所有实际用途上都是安全的。
要了解语义安全,首先可以从理解完美保密性和实际保密性的概念入手。我们都知道,加密算法中有三个必备的东西:被加密的消息m,加密密钥k,以及加密算法对(E, D)。我们首先来定义一下什么叫做加密算法的完美保密性:
这个定义的意思是,对于任意等长的消息m,只要这个m属于消息空间(就是说用这个加密算法可以加密m),那么用加密密钥k加密后,加密结果“看起来都一样”,没法看出来这是从m,还是从其他什么消息加密得来的。密码学中证明了,唯一能达到这个安全条件的加密算法是一次性密码,其问题在于加密时使用的密钥长度至少要跟消息长度一样才行。
上面这个定义说的是加密结果让谁看,“看起来都一样”,这完美得太完美了。现在我们稍作变动,选一个迄今为止计算能力最强的人来看加密的结果,要是他都觉得“看起来都一样”。那就足够了!到现在为止,计算能力最强的就是计算机了。这样的话就引出了实际保密性:
与上面相比,就一个符号改变了,就是等号变成了约等于号。
那么如何用计算机的计算能力来描述实际保密性呢?
我们用两个计算机来定义。一个计算机是来攻击这个加密算法的,叫攻击者(Adversary);一个计算机是运行这个加密算法的,接受攻击者的攻击挑战,叫挑战者(Challenger),挑战者拿着密钥k,攻击者的目的就是看看挑战者运行加密算法后,输出的加密结果是不是“看起来一样”。我们定义两个实验:实验0,实验1。
实验0:
- 攻击者自己任意选择两个消息m0、m1(注意,这个m0、m1是攻击者自己选的)
- 攻击者把这两个消息发送给挑战者。
- 挑战者运行加密算法,加密m0,把加密结果发送给攻击者。
实验1:
- 攻击者自己任意选择两个消息m0、m1(注意,这个m0、m1是攻击者自己选的)
- 攻击者把这两个消息发送给挑战者。
- 挑战者运行加密算法,加密m1,把加密结果发送给攻击者。
攻击者的目的呢?就是看到加密结果后,猜这个加密结果是由m0加密来的,还是由m1加密来的。这两个实验唯一的区别就是,挑战者是返回m0的加密结果,还是返回m1的加密结果。而且,执行哪个实验是挑战者说了算!好啦,现在我们把这两个实验合起来:
实验b:
- 攻击者自己任意选择两个消息m0、m1(注意,这个m0、m1是攻击者自己选的)
- 攻击者把这两个消息发送给挑战者。
- 挑战者运行加密算法,加密mb,把加密结果发送给攻击者。
如果挑战者以 1 2 \frac12 21的概率执行实验0,以 1 2 \frac12 21的概率执行实验1。那么,如果加密结果真的没办法反映出原始消息的一点点信息,那么攻击者判断正确的概率是多少呢?也应该是 1 2 \frac12 21,因为加密结果没法帮助到他,所以他也只能随便猜,猜对了就撞大运了。
语义安全的定义泛化
某些特定的安全属性(称为“X”),对于某些密码系统(称为“S”)可以定义为一个包含两个实验的攻击博弈,实验0和实验1,其中对手A的协议在两个实验中是相同的,而挑战者的协议是不同的。对于b = 0,1,我们定义Wb为A在实验b中输出1的事件,我们定义:
成为A的" X优势"如上所述,我们总是可以定义一个攻击博弈的“猜位”版本,挑战者随机选择b∈{0,1},然后运行实验b作为其协议。如果W是对手的输出等于b的事件,那么我们定义:
成为A的“猜位X优势”。我们还可以得出:
上面这条公式是根据以下过程例证出来的:
设p0为攻击博弈实验0中对手输出1的概率,设p1为对手输出1的概率。如果我们以b = 0的事件为条件,那么在这个条件概率空间中,挑战者和对手所做的所有其他随机选择的分布方式与实验0的对应值完全相同。因此,如果在攻击游戏中,对手的输出是b,我们有:
依次可以得到等号左右的两倍关系。
可忽略函数
一个函数f:Z≥1→R被称为可忽略函数,如果对于所有的c∈R>0,存在n0∈Z≥1,使得对于所有的整数n≥n0,我们有|f(n)|<1/nc。
定理:函数 f:Z≥1→R 可忽略当且仅当对于所有的c > 0,我们有:
比如说有这些函数,2-n,n-logn,它们都是可忽略函数。
超聚函数
函数 f:Z≥1→R 如果 1/f 可以忽略,则称为超聚函数。
多有界函数
函数 f::Z≥1→R 称为多有界函数,如果存在c, d∈R>0,使得对于所有n≥0的整数,我们有|f(n)|≤nc + d。
注意,如果f是一个多界函数,那么1/f肯定不是一个可以忽略的函数。例如,定义f: Z≥1→R,使f(n)对于所有偶整数n = 1/n, f(n)对于所有奇整数n = 2−n,则f不可忽略,且1/f既非聚有界也非超聚。
计算密码的规范
我们说计算密码 ϵ \epsilon ϵ =(E,D)是在(K,M,C)上定义的,其中K是密钥空间,M是消息空间,C是密文空间,而这些空间中的每一个都是有限集,我们并没有说出全部真相。在数学模型中(虽然在实际系统中并不总是如此),我们将密钥、消息和密文空间的E族关联起来,索引方式为:
(1)一个安全参数,它是一个正整数,用λ表示
(2)一个系统参数,它是位串,用∧表示
因此,我们有了有限集族,而不仅仅是有限集K、M和C。
出于这个定义的目的,我们将其视为一组位字符串(它可以通过一些规范的编码函数来表示数学对象)。其思想是,当部署密码
ϵ
\epsilon
ϵ 时,安全参数λ固定为某个值。一般来说,λ值越大,意味着安全级别越高(即对拥有更多计算资源的对手的抵抗力),但密钥大小也越大,加密和解密速度也越慢。因此,安全参数就像我们可以转动的“拨号盘”,在安全性和效率之间进行权衡。一旦选择λ,系统参数∧将使用特定于密码的算法生成。
这一个固定实例可以部署在一个更大的系统中,并由多方使用—— λ 和 ∧ 的值是公开的,并且为所有人(包括对手)所知。
用一个例子来理解计算密码的规范,附加一次性密码,该密码是以模n来描述的。为了部署这样的密码,会生成一个合适的模n,并将其公开。模n是该密码的系统参数。安全参数的每个特定值决定n的长度(以位为单位)。值n本身由一些可能是概率的算法生成,其输出分布可能取决于预期应用。文章来源:https://www.toymoban.com/news/detail-477613.html
计算密码由一对算法E和D以及三个具有系统参数化P的空间族组成:文章来源地址https://www.toymoban.com/news/detail-477613.html
到了这里,关于斯坦福Dan Boneh密码学——02 计算密码与语义安全的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!