密码学 第4章 Shannon理论

高飞密码学第4章Shannon理论[e-mail]1.安全性准则1949年，ClaudeShannon在《BellSystemsTechnicalJournal》上发表了题为“CommunicationTheoryofSecrecySystems”的论文。这篇论文对密码学的研究产生了巨大的影响。在本章中，我们讨论若干Shannon的思想。评价密码体制安全性的不同准则：计算安全性（computationalsecurity）可证明安全性（provablesecurity）无条件安全性（unconditionalsecurity）计算安全性核心思想：考虑攻破密码体制所需付出的计算代价。如果使用最好的算法攻破一个密码体制需要至少N次操作，这里的N是一个特定的非常大的数字，则这个密码体制是计算安全的。缺点：没有一个已知的实际的密码体制在这个定义下可以被证明是安全的。实际中，人们经常通过几种特定的攻击类型来研究计算上的安全性，例如穷尽密钥搜索攻击。当然对一种类型的攻击是安全的，并不表示对其它类型的攻击是安全的。可证明安全性核心思想：将密码体制的安全性归结为某个经过深入研究的数学难题。例如，可以证明这样一类命题：如果给定的整数n是不可分解的，那么给定的密码体制是不可破解的。我们称这种类型的密码体制是可证明安全的。必须注意，这种途径只是说明了安全和另一个问题是相关的，并没有完全证明是安全的。这和证明一个问题是NP完全的有些类似：证明给定的问题和任何其它的NP完全问题的难度是一样的，但是并没有完全证明这个问题的计算难度。无条件安全性核心思想：对攻击者Oscar的计算量没有限制的时候的安全性。即使提供了无穷的计算资源，也是无法被攻破的，我们定义这种密码体制是无条件安全的。举例：一次一密乱码本；量子密码在讨论密码体制的安全性的时候，我们需指明正在考虑的攻击类型。例如，在前一章中，我们说移位密码，代换密码和维吉尼亚密码对唯密文攻击都不是计算上安全的（如果给了足够的密文）。后面我们将研究一个对唯密文攻击是无条件安全的密码体制。这个理论从数学上证明了：如果给出的密文足够的少，某些密码体制是安全的。例如，可以证明，如果只有单个的明文用给定的密钥加密，移位密码和代换密码都将是无条件安全的。类似地，使用密钥字长度为m的维吉尼亚密码是无条件安全的，如果密钥用于加密一个单位的明文（由m个字母组成）。2.完善保密性假设(,,,,)PCKED是一个特定的密码体制，密钥KK只用于一次加密。假设明文空间P存在一个概率分布。因此明文元素定义了一个随机变量，用x表示。[]xPrx表示明文x发生的先验概率。还假设（Alice和Bob）以固定的概率分布选取密钥K。所以密钥也定义了一个随机变量，用K表示。[]KPrK表示密钥K发生的概率。密钥是在Alice知道明文之前选取的。因此，我们可以合理的假设密钥和明文是统计独立的随机变量。P和K的概率分布决定了C的概率分布。因此，同样可以把密文元素看成随机变量，用y表示。不难计算出密文y的概率[]yPry。对于密钥KK，定义(){():}KCKexxP。也就是说()CK代表密钥是K时所有可能的密文。对于任意的yC，我们有{:()}[][][()]KKyCKyKdyPryPrKPrx同样观察到，对于任意的yC和xP，可以如下计算条件概率{:()}[|][]PryxPrKKKxdyyxK现在可以用Bayes公式计算条件概率{:()}{:()}[][][|][][()]KKxdyKKyCKxKxyKdyPrxPrKPrxyPrKPrx。只要知道了明文、密钥的概率分布，任何人都可以完成这些计算。例4.1假设{,}abP满足[]1/4aPr，[]3/4bPr。设123{,,}KKKK，1[]1/2KPr，23[][]1/4KKPrPr。设{1,2,3,4}C，加密函数定义为1()1Kea，1()2Keb，2()2Kea，2()3Keb，3()3Kea，3()4Keb。这个密码体制可以用如下加密矩阵表示：ab1K122K233K34试计算密文概率分布和给定密文后明文的条件概率分布。计算C的概率分布如下：1[1]8317[2]81616311[3]161643[4]16PrPrPrPr给定密文后，明文空间上的条件概率分布：[|1]11[|2]71[|3]4[|4]0aaaaPrPrPrPr[|1]06[|2]73[|3]4[|4]1bbbbPrPrPrPr通俗地讲，完善保密性就是说Oscar不能通过观察密文得到明文的任何信息。在例4.1中，对于密文3y满足完善保密性的定义，但是对于其它的密文不满足。单字母移位密码的完善保密性：从直觉上看这是很显然的。因为对于任意给定的密文26yZ，任何26xZ都可能是对应的明文。下面给出严格证明。定义4.1：一个密码体制具有完善保密性，如果对于任意的xP和yC，有[|][]xyxPrPr。也就是说，给定密文y，明文为x的后验概率等于明文x的先验概率。定理4.1假设移位密码的26个密钥都是以相同的概率1/26使用的，则对于任意的明文概率分布，单字母移位密码具有完善保密性。证明:这里26ZPCK，对于025K，加密函数Ke定义为26()()mod26()KexxKxZ。首先计算C上的概率分布。假设26yZ，则262626[][][()]1[]261[]26KKKKyKdyyKyKPryPrKPrxPrxPrxZZZ现在固定y，值()mod26yK构成26Z的一个置换。故2626[][]KxyKxPrxPrxZZ得到对于任意的26yZ，1[]26yPr。接下来我们有，对于任意的,xy1[|][()mod26]26yxKyxPrPr（这是因为对于任意的,xy，满足()Kexy的K是唯一的()mod26Kyx）。现在应用Bayes定理，很容易计算出[][|][|][]1[]26126[]xyxxyyxxPrPrPrPrPrPr所以这个密码体制是完善保密的。因此，如果新的随机密钥用来加密每个明文字母，则移位密码是“不可攻破的”。下面考察一般的完善保密性。使用Bayes定理，条件“对于所有的xP和yC，[|][]xyxPrPr”等价于“对于所有的xP和yC，[|][]yxyPrPr”。可以合理的假设对于所有的yC，[]0yPr。固定任意xP。对于任意yC，有[|][]0yxyPrPr。因此，对于任意yC，至少存在一个密钥K满足()Kexy。这样有KC。在任意一个密码体制中，因为加密函数是单射的，一定有CP。当KCP时，我们有一个关于什么时候取得完善保密性的很好的性质。这个性质最早是由Shannon提出。定理4.2假设密码体制(,,,,)PCKED满足KCP。这个密码体制是完善保密的，当且仅当每个密钥被使用的概率都是1K，并且对于任意的xP和yC，存在唯一的密钥K使得()Kexy。证明:假设这个密码体制是完善保密的。由上一页的观察可知，对于任意的xP和yC，至少存在一个密钥K满足()Kexy。因此有不等式：{():}KexKCKK但是我们假设CK。因此一定有{():}KexKKK也就是说，不存在两个不同的密钥1K和2K使得12()()KKexexy。因此对于xP和yC，刚好存在一个密钥K使得()Kexy。记nK。设{:1}ixinP并且固定一个密文yC。设密钥为12,,,nKKK，并且()iKiexy，1in。使用Bayes定理，我们有[|][][][][|][][]iiiiiyxxKxxyyyPrPrPrKPrPrPrPr考虑完善保密的条件[|][]iixyxPrPr。从这里，我们有[][]iKyPrPr，1in。也就是说所有的密钥都是等概率使用的（概率为[]yPr）。但是密钥的数目为K，我们得到对任意的KK，[]1KPrK。相反地，如果两个假设的条件是成立的。类似于定理4.1的证明，很容易得到密码体制是完善保密的。“一次一密”密码体制：由GilbertVernam于1917年提出。“一次一密”很多年来被认为是不可破的，但是一直都没有一个数学的证明，直到30年后Shonnon提出了完善保密性的概念。密码体制4.1一次一密假设1n是正整数，2()nZPCK。对于K2()nZ，定义()Kex为K和x的模2的向量和（或者说是两个相关比特串的异或）。因此，如果1(,,)nxxx并且1(,,)nKKK，则11()(,,)mod2KnnexxKxK解密和加密是一样的。如果1(,,)nyyy，则11()(,,)mod2KnndyyKyK由定理4.2，容易看出“一次一密”提供了完善保密性。这个密码体制加密和解密也很容易，有一定的吸引力。Vernam对此还申请了专利，希望会有广泛的商业用途。不幸的是，“一次一密”存在一个较大的不利因素。KP意味着秘密使用的密钥数量必须至少和明文的数量一样多。例如，在“一次一密”的密码体制中，我们要求用n比特的密钥加密n比特的明文。若相同的密钥可以用于加密不同的消息，这将不是一个重要的问题，但是密码体制的无条件安全性是基于每个密钥仅用一次的事实。例如，“一次一密”对已知明文攻击将是脆弱的，因为K可以通过异或比特串x和()Kex得到。因此，新生成的密钥需要为将要发送的明文在安全的通道上传输。这就带来了一个严峻的密钥管理问题，因此限制了“一次一密”在商业上的应用。但是“一次一密”在要求无条件安全的军事和外交环境中有着很重要的应用。在密码学的发展历史中，人们试图设计出密钥可以加密相对长的明文（也就是一个密钥可以加密许多消息），并且仍然可以保持一定的计算安全性。一个这样的例子就是数据加密标准（DataEncryptionStandard），我们将在后面学习。3.伪密钥和唯一解距离条件熵(|)HKC称为密钥含糊度，度量了给定密文下密钥的不确定性。定理4.3设(,,,,)PCKED是一个密码体制，(|)()()()HHHHKCKPC。证明：首先注意到(,,)(|,)(,)HHHKPCCKPKP。因为()Kyex，所以密钥和明文唯一决定密文。这说明(|,)0HCKP，因此(,,)(,)HHKPCKP。但是K和P是统计独立的，所以(,)()()HHHKPKP。因此，(,,)(,)()()HHHHKPCKPKP。同样地，既然密钥和密文唯一决定明文（即()Kxdy），我们有(|,)0HPKC，因此有(,,)(,)HHKPCKC。所以(|)(,)()(,,)()()()()HHHHHHHHKCKCCKPCCKPC例4.1（续）我们已经计算出()0.81HP，()1.5HK，()1.85HC。由定理4.3知(|)1.50.811.850.46HKC。可以通过条件熵的定义直接验证。密码分析的基本目的是确定密钥。考虑唯密文攻击，并且假设分析者Oscar有无限的计算资源。同时假定Oscar知道明文是某一自然语言，如英语。一般来说，Oscar能排除某些密钥，但是许多可能的密钥存在，只有一个密钥是正确的。那些可能的（即不能排除的）但不正确的密钥称为伪密钥。例如，假设Oscar得到移位密码的密文WNAJW。容易知道，只有两个有意义的明文串，即river和arena，分别对应于可能的加密密钥(5)F和(22)W。这两个密钥，一个是正确的密钥，一个是伪密钥。考虑：对攻击者来说，是否所拿到的密文越长越容易确定正确的密钥？对于给定长度的密文串，我们希望分析后伪密钥越少越好。下面我们的目的是推导伪密钥的期望数的下界。定义自