于是我们可以根据Kerckhoffs原则把加密系统的general picture进行改写:
Alt text
是明文消息
密钥从均匀分布中抽取
暴露给攻击者
注意到,和加密系统的最一般情况相比,这里我们引入了密钥,希望攻击者没法获取到和的相关信息。
2 完美的安全性
一些记号:
Alt text
现在的问题是,在Kerckhoffs原则的框架下,我们怎么去定义一个密码系统的安全性?
想法一: 定义. 如果攻击者没办法计算,那么这个scheme就是安全的。
——密钥不让人知道是确实有道理...吧。
一个反例就是,。这种情况下,你确实没暴露任何的的信息,但是在裸奔,加密的安全性效果类似于皇帝的新衣。
Alt text
想法二: 定义. 如果攻击者没办法计算,那么这个scheme就是安全的。
如果一个攻击者只需要计算密文的某些特征就能推断出足够的信息,那这个scheme还安全吗?
比如我猜一个四字地名是齐齐哈尔还是乌鲁木齐。我甚至只需要这四个字里带几个齐字或者有没有重复字就能推测出答案。
想法三: 定义. 如果攻击者不能获得的任何相关信息,那么这个scheme就是安全的。
但是攻击者可能已经获得了一些先验信息,比如知道消息是用英语写的。
想法四: 定义. 如果攻击者不能获得的任何额外信息,那么这个scheme就是安全的。
这个是比较靠谱的,但是怎么正式表述它?
一个例子是使用概率分布/信息论进行描述:
Alt text
上半拉图是通信前。在Alice手里,攻击者什么都不知道,它有关于的一个先验分布。
下半拉图是通信后。在Alice手里,攻击者知道,在知道的前提下,攻击者的先验没有产生丝毫的变化。这就是所谓的“攻击者不能获得关于的任何额外信息”。
于是,我们得到基于条件概率表述的完美安全性定义:
Alt text
如果系统是安全的,那么你攻击者对再怎么折腾,最后输出的结果和瞎猜的效果是一样的。
于是我们可以定义不可区分性: 定义. 定义在明文空间上的密码系统是不可区分的,如果:
3 一次性密码本
现实中就存在一个具有完美安全性的加密方案:一次性密码本(One Time Pad, OTP)。
对于一个二进制串,我们随机生成和等长的二进制串,其中的每一位都是独立的均匀分布,,其中被定义为异或运算。
Alt text
OTP的安全性是显然的。因为,对每个而言,的每一位都是均匀分布的。
Alt text
我们将OTP进行一般化:
为加群。。于是,
构成了一次性密码本。
但是OTP不实用,因为:
密钥和明文等长
一次一密,用后即焚,否则可能会泄露信息。
比如在OTP中,如果相同的密钥加密后得到,那么攻击者就知道——这泄露了明文的信息。
Alt text
此外,我们可以证明,一个密码系统如果是具有完美安全性的,那么必然是。
(原因很简单,假如,原本攻击者是要去猜的,现在攻击者猜的胜算还比猜的胜算还大,这意味着加密过程泄露了信息。)
于是,OTP就成了完美安全性中最高效的方案。
Alt text
“可以收手了吗,阿祖?”
4 限制攻击者的能力:不可区分性和语义安全性
Alt text
要想做出实用性更强的密码系统,一个想法是对攻击者的能力进行限制。
限制方法包括:
限制攻击者的计算能力——计算安全性。
其他方法:量子密码学、内存限制模型etc
量子密码学的特征是:攻击者(Eve)不可能在通信方(Alice和Bob)不知情的情况下实现窃听。一旦攻击者成功实施窃听,那么量子的状态就会被干扰,通信方可以通过基于量子状态传输的通信内容知道自己被窃听了。
Alt text
Alt text
(需要注意一点,量子密码和量子计算不是一个东西)
主流方法是对攻击者进行计算能力的限制。如果攻击者可以不计成本地做穷举攻击,那么什么样的密码都会被破解。
Alt text
问题来了:如何定义对攻击者计算能力的限制?
攻击者可以买若干块V100并且用到报废、或者一年内租若干台云服务器吗?
即使有这些个计算资源,那攻击者运行什么样的攻击算法呢?
所以说这种定义在理论上不是太美观的,也不方便分析。
Alt text