现代密码学学习报告第一章 概论1.1信息安全与密码技术信息的一般定义属于哲学范畴。
信息是事物运动的状态与方式,是事物的一种区别于物质与能量的属性。
“信息”——数据。
机密性——拥有数据的一方或交换数据的各方不希望局外人或对手获得、进而读懂这些数据。
完整性——数据在交换及保存中不被未授权者删除或改动,或者合法的接受者能方便的判断该数据是否已经被篡改。
认证性——也称“不可否认性”或“抗抵赖”,包括信息源和接收端认证性,即信息系统中的实体不能否认或抵赖曾经完成的发送消息或接收消息的操作。
利用信息源证据可以检测出消息发送方否认已发送某消息的抵赖行为,利用接收端证据可以检测出消息接收方否认已接收某消息的抵赖行为。
此类证据通常还包括时间/时序或“新鲜性”证据。
可用性——授权用户能对信息资源有效使用。
显然,信息系统可靠性是其支撑之一。
公平性——信息具有的社会或经济价值只能在交互中体现。
公平性就是指交换规则或交互协议要使得参与信息交互的各方承担安全风险上处于相同或相当的地位。
可控性——是指对信息的传播及传播的内容以至信息的机密性具有控制能力的特性。
一般指信息系统或(社会)授权机构根据某种法规对信息的机密性、信息的传播通道、特定内容信息的传播具有控制能力的特性,以及获取信息活动审计凭证能力的特性,如“密钥托管”、“匿名撤销”、实时内容检测与过滤、计算机犯罪或诉讼的司法取证等。
1.2密码系统模型和密码体制密码系统基本模型:密码体制的分类:对称密码体制的古典算法有简单代换、多名代换、多表代换等。
非对称密码体制:使用非对称密码体制的每一个用户一个是可以公开的,称为公开密钥,简称公钥,用pku 表示;另外一个则是秘密的,称为秘密秘钥,简称私钥,用sku 表示。
非对称密码体制又称为双钥密码体制或公钥密码体制。
公钥密码体制的主要特点是将加密能力分开并分别并分别授予不同的用户,因而可以实现信 源M 加密器()c m =1k E 非法接入者密码分析员(窃听者)搭线信道(主动攻击)搭线信道(被动攻击)解密器接收者()m c =2k D 密钥源密钥源1K 2K m m 'm c'c 1k 2k 信道密钥信道多个用户加密的消息只能由一个用户解读。
任何一个合格的密码系统均应满足以下要求:(1)解密的一致性(2)系统的保密性不依赖于对加密体制或加密体制或加(解)密算法的保密,而仅依赖于非公开密钥(对称密码的秘钥或公钥密码的私钥)的保密。
此即密码系统安全性分析中著名的kerckhoff假设。
(3)系统或者是理论上不可破的,或者实际上不可破的。
(4)系统便于实现和使用方便。
代换密码:明文空间:M = ZqL明文字母表: Zq ={0,1,…,q-1}明文组(L-报文) : m=(m0, m1,…,mL-1)ZqL密文空间:C = Zq’L’,密文字母表: Zq’={0,1,…,q’-1}密文组: c=(c0, c1,…,cL’-1)Zq’L’密钥空间:K ,k K加密变换: fk : ZqL Zq’L’任给m ZqL ,记fk(m)= f (k,m)=c.设f是单射,则f的逆就是解密变换:Dk(c)= f -1.q=q’L=L’: f可为1-1映射;无数据扩张L<L’: f可为1对多映射;有数据扩张L>L’: f不可逆,不能作加密映射;数据压缩q=q’, Zq= Zq’L=L’=1单表代换(monoalphabetic substitute)对所有的明文字母,都用一种固定的代换进行加密。
多表代换(polyalphabetic substitute)对所有的明文字母,用一个以上的代换表进行加密。
1.3几种简单的密码体制多表代换密码:多表代换密码是以一系列(两个以上)代换表依次对明文消息的字母进行代换的加密方法,如明文字母序列为x=x1x2…,则密文字母序列为c=e(x)=f1(x1)f2(x2)…多表代换密码分为非周期多表代换密码和周期多表代换密码两类。
在非周期多表代换密码中,对每个明文字母都采用不同的代替表进行加密,是一种在理论上唯一不可破的密码,但由于需要的密钥量和明文信息长度相同而难于广泛使用。
周期多表代换密码中,代换表个数有限且能被重复应用,大大减少了密钥量,常用的有维吉尼亚密码,博福特密码,滚动密钥密码,弗纳姆密码。
(1)维吉尼亚密码。
它的构成由明文和密钥组成。
明文:每个字符惟一对应一个0~25间的数字。
密钥:一个字符串,其中每个字符同明文一样对应一个数字,代表位移值,如a 表示位移0,b 表示位移1,c 表示位移2,...... )。
加密过程是将明文数字串依据密钥长度分段,并逐一与密钥数字串相加(模26),得到密文数字串,最后,将密文数字串转换为字母串。
该密码的分析有以下两步第一步:一. 确定密钥的长度,主要方法有:Kasiski测试法和重合指数法。
Kasiski测试法的基本原理是对于密钥长度为的Vigen ère密码,如果利用给定的密钥表周期性地对明文字母进行加密,则当明文中有两个相同的字母组在明文序列中间隔的字母数为的倍数时,这两个明文字母组对应的密文字母组一定相同;反之,如果密文中出现两个相同的字母组,则其对应的明文字母组不一定相同。
重合指数法基本思想是对于长度分别为n的密文串y=y1y2…yn,将其分为长度为n/d的d个子串Yi(i=1,2,…,d),如果密钥长度为d,则Ic(Yi)≈0.065(1≤i≤d) ,否则,因为采用不同的密钥依位加密,子串Yi将更为随机。
对于一个完全随机的密文串,Ic(y)≈26(1*+26)2=0.038。
由于0.038与0.065的差值足够大,所以在一般情况下,依据重合指数法能够判断出正确的密钥长度。
第二步:确定密钥。
通常采用重合互指数法。
对于长度分别为n及n′的字母串x=x1x2…xn和y=y1y2…yn,“重合互指数”指的是x的一个随机元素与y的一个随机元素相同的概率,记为MIc(x,y)。
而且通过采用重合互指数法,可以获得任何两个子串Yi与Yj 的相对移位。
(2)博福特密码。
博福特密码是一种类似于维吉尼亚密码的替代密码,由弗朗西斯·蒲福(Francis Beaufort)发明。
它最知名的应用是M-209密码机。
博福特密码属于对等加密,即加密演算法与解密演算法相同。
博福特密码是按mod q减法运算的一种周期代替密码。
即ci+td=δi(mi+td)≡(ki-mi+td)(mod q)。
所以,它和维吉尼亚密码类似,以ki为密钥的代替表是密文字母表为英文字母表逆序排列进行循环右移ki+1次形成的。
例如,若ki=3(相当于字母D),则明文和密文的对应关系如下:明文:a b c d e f g h i j k l m n o p q r s t u v w x y z;密文:D C B A Z Y X W V U T S R Q P O N M L K J I H G F E。
显然,博福特密码的解密变换为mi+td≡δi(ci+td)≡(ki-ci+td)(modq),因此,博福特密码的解密变换与加密变换相同。
按博福特密码,以密钥ki加密相当于按下式的维吉尼亚加密:ci+td≡[(q-1)-mi+td](modq)若按下式加密:ci+td≡(mi+td-ki)(modq),就得到变异的博福特密码,相应代替表示将明文字母表循环右移ki次而成。
由于循环右移ki次等于循环左移(q-ki)次,即式ci+td≡(mi+td-ki)(modq)等价于以(q-ki)为密钥的维吉尼亚密码。
所以维吉尼亚密码和变异的博福特密码互为逆变换,若一个是加密运算,则另一个就是解密运算。
(3)滚动密钥密码。
对于周期多表代换密码,保密性将随周期d的增大而增大,当d的长度和明文一样长时就变成了滚动密钥密码,如果其中所采用的密钥不重复就是一次一密体制。
一般,密钥可取一篇报告或一本书作为密钥源,可由书名,章节号及标题来限定密钥起始位置。
(4)弗纳姆密码。
①明文,密文,密钥都表示为二进制位:M=m1,m2,… ,mn K =k1,k2,… ,kn C =c1,c2,… ,cn ②加密 : c1= mi⊕ ki ,i=1,2,… ,n 解密 : m1= ci ⊕ ki ,i=1,2,… ,n ③因为加解密算法是模2加,所以称为代数密码。
因为加解密算法是模2 ④对合运算:f=f-1,模 2加运算是对合运算。
对合运算:密码算法是对和运算,则加密算法=解密算法,工程实现工作量减半。
⑤ Vernam密码经不起已知明文攻击。
⑥如果密钥序列有重复,则Vernam密码是不安全如果密钥序列有重复,则 Vernam密码是不安全的. 一种极端情况:一次一密⑦一种极端情况:一次一密密钥是随机序列. 密钥至少和明文一样长. 一个密钥只用一次。
⑧一次一密是绝对不可破译的,但它是不实用的。
⑨一次一密给密码设计指出一个方向,人们用序列密码逼近一次一密。
1.4初等密码分析密码分析方法可分为传统破译方法和物理破译方法两大类。
数学分析法又分为确定性分析法和统计分析法。
在kerchhoff 假设下,按照密码分析者具有的不同破译条件,通常将破译类型分为以下5种:(1)唯密文破译,分析者仅知道有限数量的密文。
(2)已知明文破译,分析者除了拥有有限数量的密文外,还有数量限定的一些已知“明文——密文”对。
(3)选择明文破译,分析者除了拥有有限数量的密文外,还有机会使用注入了为止密钥加密机,通过自由选择明文来获取所希望的若干“明文——密文”对。
(4)非适应选择密文破译,分析者除了拥有有限数量的密文外,在给定挑战密文之前,还有机会使用注入了为止密钥的解密机,通过自由选择密文来获取所希望的若干“密文——明文”对。
(5)适应性选择密文破译,分析者除了拥有有限数量的密文外,在给定挑战密文之前、之后均可使用注入了未知密钥的解密机,通过自由选择(不等于挑战密文的)密文来获取所希望的若干“密文——明文”对。
从唯密文破译到适应性选择密文破译,密码分析者的攻击能力递增。
1.5密码学的信息论基础已知密码体制: (M, C, K , E, D)明文字母表:A={ai, i=0,1,…, q-1}=Zq 的概率分布明文: m=(m0, m1,…, mL-1)AL, 如果信源无记忆,则明文空间:M =AL=ZqL.明文熵:H(M )=H(AL)=H(ZqL ).完善保密性定理1.5.2 任给密码系统 (M, C, K, E, D),有I(M ; C )≥H(M )H(K ).1.5.3唯一解距离、理论保密性与实际保密性理论保密性理论保密性是假定密码分析者有无限的时间、设备和资金条件下,研究唯密文攻击时密码系统的安全性。