读书频道 > 安全 > 深入浅出密码学——常用加密技术原理与应用
1.6 要点回顾
2012-09-26 14:03:28     我来说两句 
收藏    我要投稿   
本书拥有的诸多特征使得它成为密码学从业者和学生独一无二的资源—本书介绍了绝大多数实际应用中使用的加密算法,并重点突出了它们的实用性。对于每种加密模式,我们都给出了最新的安全评估和推荐使用的密钥长度...  立即去当当网订购

1.7  习题

1.1   以下密文是使用替换密码加密得到的。请在不知道密钥的情况下解密该密文。

1rvmnir bpr sumvbwvr jx bpr lmiwv yjeryrkbi jx qmbm wibpr xjvni mkd ymibrutjx irhx wi bpr riirkvr jx ymbinlmtmipw utn qmumbr dj w ipmhh but bj rhnvwdmbrbpr yjeryrkbi jx bpr qmbm mvvjudwko bj yt wkbrusurbmbwjk lmird jk xjubt trmuijx ibndt
 
Wb wi kjb mk rmit bmiq bj rashmwk rmvp yjeryrkb mkd wbi iwokwxwvmkvr mkd ijyr ynib urymwk nkrashmwkrd bj ower m vjyshrbr rashmkmbwjk jkr cjnhd pmer bj lr fnmhwxwrd mkd wkiswurd bj invp mk rabrkb bpmb pr vjnhd urmvp bpr ibmbr jx rkhwopbrkrd ywkd vmsmlhr jx urvjokwgwko ijnkdhrii ijnkd mkd ipmsrhrii ipmsr wdj kjb drry ytirhx bpr xwkmh mnbpjuwbt lnb yt rasruwrkvr cwbp qmbm pmi hrxb kj djnlb bpmb bpr xjhhjcwko wi bpr sujsru msshwvmbwjk mkd wkbrusurbmbwjk w jxxru yt bprjuwri wk bpr pjsr bpmb bpr riirkvr jx jqwkmcmk qmumbr cwhh urymwk wkbmvb

(1)  请计算密文中所有字母A…Z的相对频率。你可以使用工具来完成这个任务,比如开源程序CrypTool [50] 。但是,使用笔和纸来完成也是可以的。

(2)  请利用英文语言中相对字母频率来解密该密文( 参见第1.2.2 节的表1-1) 。注意,这个文本长度较短,所以字母频率与表格中英文字母的频率可能不是那么一致。

(3)  谁写的这个文本?

1.2    假设我们收到使用移位密码加密的以下密文:

Xultpaajcxitltlxaarpjhtiwtgxktghidhipxciwtvgtpilpitghlxiwiwtxgqadds.

(1)  请基于字母频率计数对该密文发起攻击:为了得到密钥你需要通过频率计算确定多少个字母?明文是什么?

(2)  这个消息是谁写的?

1.3   现在考虑密钥长度为128 位的AES(Advanced Encryption Standard ,AES)抵抗穷尽密钥搜索攻击的长期安全性。AES 可能是目前使用最广泛的对称密码。

(1)  假设某个攻击者拥有一个特殊目的的专用集成电路(Application specific integrated circuit ,ASIC) ,该电路每秒可以检查5 ⋅ 108个密钥。该攻击者拥有一百万美元的预算。一个专用集成电路总共花费50 美元,我们考虑了集成ASIC的全部开销( 生产印刷电路板、电力供应、制冷等) 。请问在给定的预算里,我们可以同时并行运行多少个ASIC?每个密钥搜索平均需要多长时间?将这个时间与宇宙的年龄( 大概1010年) 比较一下。

(2)  现在我们将计算机技术加到考虑范围内。准确预测未来可能非常棘手,但用摩尔定律来估测未来是可以的。根据摩尔定律,在集成电路的成本保持不变的情况下,计算能力每隔18 个月就会翻番。请问需要等待多少年才能建造一个密钥搜索机器,能在24小时的平均搜索时间内破解128 位的AES 密码?同样地,假设其预算为一百万美金( 不考虑通货膨胀) 。

1.4  现在考虑密码和密钥大小之间的关系。首先考虑一个需要用户以密码形式输入密钥的密码体制。

(1)  假设这个密码由8 个字母组成,而且每个字母都是ASCII 方案编码( 每个字符占7位,即128 个可能字符) 。请问使用这样的密码构建的密钥空间有多大?

(2)  对应的密钥长度是多少位?

(3)  假设大多数用户只使用字母表中的26个小写字母,而不是ASCII 编码的全7 位的字符作为密码,请问其对应的密钥长度是多少位?

(4)  假设字符分别由以下两种组成形式,请问生成一个长度为128 位的密钥至少需要多少个字符组成的密码?

1) 7 位的字符;

2) 字母表中26个小写字母。

1.5  从本章的内容可知,模运算是很多密码体制的基础。因此,我们将在这里和后续章节里讨论这个话题。

首先从一个简单的问题入手:在不使用计算器的情况下计算以下结果:
(1) 15 ⋅ 29 mod 13
(2) 2 ⋅ 29 mod 13
(3) 2 ⋅ 3 mod 13 
(4) -11 ⋅ 3 mod 13 

得到的结果应该在0, 1,…,模数-1 的范围内。请概述这个问题中不同部分之间的联系。

1.6   请在不使用计算器的情况下计算以下结果:

(1) 1/5 mod 13 
(2) 1/5 mod 7 
(3) 3 ⋅ 2/5 mod 7

1.7  请构建环Z4内所有元素之间相加得到的表:

(1)  请构建环Z4 的乘法表。
(2)  构建Z5的加法表和乘法表。
(3)  构建Z6的加法表和乘法表。
(4) Z4和Z6 内有些元素没有乘法逆元,请问这些元素是哪些?为什么Z5内所有的非零元素都存在乘法逆元呢?

1.8   请问在Z11 、Z12 和Z13中5 的乘法逆元分别是什么?你可以使用计算器或PC实现试错法搜索。

我们利用这个简单的问题想强调的一个事实是:给定环中某个整数的逆元完全依赖于这个环。这意味着如果模数改变了,则对应的逆元也随之改变。所以,在没有弄清模数的情况下来讨论一个元素的逆元是没有任何意义的。这个事实在RSA 密码体制(参见本书第7 章) 中至关重要。本书第6.3 节将介绍扩展的欧几里德算法,它可以高效地计算逆元。

1.9   请在不使用计算器的情况下尽可能快地计算x 。如有必要,可参考第 1.4.1一节中巧妙指数分解的例子。
(1) x  = 32 mod 13
(2)  x  = 72 mod 13  
(3)  x  = 310 mod 13
(4)  x  = 7100 mod 13
(5) 7x = 11 mod 13

最后一个问题称为离散对数,它是一个非常难的问题(请参见第8 章) 。很多公钥方案的安全性都基于求解大整数( 比如超过1 000 位的整数) 的离散对数的难度。

1.10   对于m =4,5 ,9 ,26,请找出与m 互素的所有整数n ,其中0  ≤   n  <  m。我们将所有满足此条件的整数n 的个数记作φ (m ),比如φ (3)=2。此函数也称为欧拉(Euler's phi)函数。m=4,5 ,9 ,26对应的φ ( m) 分别是多少?

1.11   这个问题与仿射加密相关,其中密钥参数a =7,b =22 。

(1)  请解密以下密文:

falszztysyjzyjkywjrztyjztyynaryjkyswarztyegyyj

(2)  这行内容是谁写的?

1.12    现在,我们想将第1.4.4节中介绍的仿射加密扩展为可以加密和解密所有用德国字母表写的消息。德国字母表是由英文字母表,三个元音变体Ä ,Ö,Ü ,以及 (非常罕见)双s 字符β 组成。我们使用下面的规则将字符映射为整数:


 

(1)  请问此密码的加密等式和解密等式分别是什么?
(2)  此字母表仿射密码的密钥空间是多大?
(3)  以下密文是使用密钥(a =17 ,b =1)得到的,请问它们对应的明文是什么?

ä u β w  β 

(4)  上述明文来自哪个村庄?

1.13   在攻击场景中,我们假设攻击者Oscar能够用某种方式设法让Alice得到她加密的一些明文片段。请说明 Oscar如何使用两个明文- 密文对( x1 ,y1) 和(x2 ,y2) 来破解此仿射密码。选择x1 和x2 的条件是什么?

注意,事实上,这个假设在某些设置下也是有效的,比如Web 服务器的加密等。因此,这种攻击情景非常重要,而且常被叫做选择明文攻击(chosen plaintext attack) 。
 
1.14   增加对称算法安全性的一个最显而易见的方法就是使用两次相同的加密,即:

y  = ek2(ek1(x ))

事情非常微妙,结果总是与预期大相径庭,这样的情形在密码学中非常常见。我们希望通过下面这个问题说明,放射密码两次加密的安全性和加密一次的安全性没什么区别!假设两个仿射密码为:ek1 =  a1x  + b1  和  ek2 =  a2x  + b2

(1)  请证明存在单个仿射加密ek3 =  a3x  + b3  ,它与组合加密ek2( ek1(x ) 执行相同的加密和解密。
(2)  当a1=3,b1=5和a2=11,b2=7时,请找出对应的a3 、b3的值。
(3)  请验证:(1)使用密钥ek1 加密字母K ,然后使用ek2 加密得到的结果;(2)使用密钥ek3 加密字母K 。
(4)  请简单描述对双重加密放射密文发起穷尽密钥搜索攻击会发生什么?有效密钥空间是否增加了?

注意,在DES 中,多重加密问题具有非常重要的实际意义,因为多重加密( 尤其是三重加密)的确在一定程度上增加了安全性。
 

点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:1.6 要点回顾
下一篇:概述
相关文章
图文推荐
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站