传统密码与密码学基本概念.doc

第1章 传统密码与密码学基本概念11 基本概念随着计算机通讯被广泛地应用于商业、金融、政府及军事部门，如何防止日益严重的计算机犯罪，防止信息在通讯过程中被非法泄露、删除和修改，已成为全社会关心的问题。密码技术作为信息加密、鉴别和签名的手段，引起了数学家和计算机科学工作者的日益浓厚的兴趣。什么是密码? 简单地说它就是对一组信息在参数的参与下进行变换，得到密文。设已知信息，通过变换得密文（或密码）。即 这个变换过程称之为加密。加密前的信息称为明文，一般用(或)表示。加密后得到的密码称为密文，一般用(或)表示。对明文实施变换得到密文的过程称为加密变换（简称为加密），记为。加密变换所使用的一组规则称为加密算法。加密操作通常在一组指定参数的控制下进行，所指定的参数称为加密密钥，一般用（或，即Key，密钥）表示。从密文恢复明文的变换过程称之为解密变换（简称为解密），记为，即。解密变换所使用的一组规则称为解密算法。解密过程是加密过程的逆过程，解密过程也在指定的参数（密钥）的控制下进行。传统密码加密用的密钥与解密用的密钥相同，称之为对称加密（也称为单密钥加密或常规加密）。对称加密的两个例子：1、设已知明文为security将明文先分成2个字母1组，再将各组逆序书写，得密文为esuciryt。这里加密变换是将明文先分组再逆序书写，密钥是每组的字符长度2。解密过程是加密过程的逆过程，密钥相同。2、将已知明文为security将明文写成矩阵形式 s c r t e u i y然后按行的顺序重新书写即可得出密文scrteuiy。解密时，将密文分成两半（两行）后按列的顺序读出即为明文。密钥为行的长度2。上述两例加密算法的加密密钥与解密密钥相同都等于2，称之为对称加密。如果加密密钥与解密密钥不同，并且在计算上无法相互推导出，则称此加密变换为非对称加密（或公开密钥加密）。密码学是研究通信安全保密的学科，由密码编码学和密码分析学组成。密码编码学主要研究如何保护传递的信息不被非法窃取、解读和利用。密码分析学主要研究如何分析和破译密码，窃取被保护的信息。非授权者借助窃听到的密文以及其他一些信息通过各种方法推断原来的明文甚至密钥，这一过程称为密码分析或密码攻击。从事这一工作的人称作是密码分析员。对密码的攻击分为主动攻击和被动攻击。被动攻击是从传输信道上截取信息（或从存储的载体上偷窃信息），通过分析使需要保密的明文信息遭到泄露。主动攻击是利用对传输过程中或对存储的数据进行非法删除、更改、插入和重放等手段，损害信息的完整性。如果密码分析者可以由密文推出明文或密钥，或者由明文和密文可以寻求密钥，那么就称该密码系统是可破译的系统。相反地，则称该密码系统不可破译系统。对于一个密码系统来说，若攻击者无论得到多少密文也求不出确定明文的足够信息，称该密码系统就是理论上不可破译的，例如，“一次一密” 密码系统属于理论上不可破译的。此密码系统要求每发送一条消息都要使用一个新的密钥，密钥每次发送前需安全地传送给接收者。虽然这给密钥管理带来了很大的难度，但是由于这种密码体制能够提供很高的安全性，所以在某些军事或外交场合仍然在使用。若一个密码系统原则上虽可破译，但为了由密文得到明文或密钥却需十分艰巨的计算，而不能在预料的时间内或实际可能的经济条件下（或合理的代价下）求出答案，这种密码系统就是实际不可破译的。例如，一个保护10万元财产的密码系统如果其破译代价高于10亿元，那么从经济角度看此系统是实际上安全的。又如，政府的一些决策只需要在发布前的一段时间内严格保密，其保密时效性只要求维持一段时间的不可破译。衡量不可破译性的尺度叫保密强度。对于任何一个密码系统，如果达不到理论上不可破译，就必须满足实际不可破译的保密强度。实际不可破译的保密强度必须与这个密码系统的应用目的、保密时效要求和当前的破译水平相适应。全体可能出现的明文的集合称为明文空间。全体可能出现的密文的集合称为密文空间。全体可能出现的密钥的集合称为密钥空间。明文空间、密文空间、密钥空间和算法的合在一起组成密码系统。从上面的讨论中我们可以得到如下的对密码系统的基本要求：(1)密码系统的密钥空间必须足够地大；如果密钥空间小的话，攻击者可以采用穷举方法搜索整个密钥空间寻找密钥，从而攻破密码系统。(2)加密与解密运算必须在计算上是可行的，必须能够被方便地实现。(3)整个密码系统的安全性系于密钥上，即使密码算法（变换方法）被公布，在密钥不泄露的情况下，密码系统的安全性也可以得到保证。另外，对密码系统还存在一些其他的要求，例如：如何防止攻击者通过其他的非技术手段(例如用金钱收买密钥管理人员等)攻破一个密码系统。因此，一个密码系统必须同时拥有完善技术与制度要求，才能保证整个系统的安全。12 恺撒密码及频率分析攻击法了解传统密码是学习现代密码的基础。传统密码加密技术主要采用两种方法：替代和置换。将明文的字母由其他字母或数字或符号代替得密文的方法称为替代方法。替代方法又分单字母替代和多字母替代。通过对明文字母位置的置换，得到排列结果完全不同的密文的方法称为置换方法。下面用凯撒密码为例来说明单字母替代原理。凯撒密码是最简单的单字母替代密码，由公元前50年罗马皇帝朱里斯凯撒（Julius Caesar）发明。他把字母表中的每个字母用该字母后面第3个字母代替，字母表是循环的，z后面的字母为a。例如：明文为security替代后得到的密文为vhfxulwb。恺撒密码属于序列密码或流密码，其特点是每次一位地对明文进行加密。对单字母替代密码最有效攻击方法为频率分布分析法等。下面举一个例子解释频率分布分析法的破译原理。设密文为：uifsfxfsfuxpcspuifstkpioboeqfufskpioxbtuxpzfbstzpvohfsuiboqfufscvuifxbtbdmfwfscpzifxbthppebufohmjtiboenbuitqfufsxbtopubdmfwfscpzifxbtopuhppebubozuijohkpioifmqfeqfufsupepijtipnfxpslcvuifxbtbmxbztjouspvcmfxjuiijtufbdifstpofebzuifcpztxfouupbofxtdippm先确定字母的频率分布，经过统计英文中单字母相对百分比频率如下（明文的字母越多规率越明显）：E12.75% T9.25% R8.5% I7.75% N7.75% O7.5% A7.25% S6% D4.25% L3.75% C3.5% H3.5% F3% U3% M2.75% P2.75% Y2.2% G2% V1.5% W1.5% B1.25% K0.5% Q0.5% X0.5% J0.25% Z0.25%英文中除单字母的频率分布的规律外，还有多字母的分布规律规律。th是最常见的双字母组合，the是英语中出现最为频繁的三字母组合。上述密文中单各字母出现的次数为：f34 u24 s15 j6 o16 p25 b21 t16 e7 m7 d4 i21 g0 v4 n2 q5 z8 h5 w2 x14 c7 l1 r0 y0 k3 a0 ui9 uif4。字母f出现的次数最多（34次）很可能对应明文字母e。字母p、u、b、o、s、i和t出现的相对频率较高，可能包括在明文集合：t， r， i，n，o，a，s中。字母a、g、r、y和l出现的相对频率最低，可能包括在明文集合：l，r，y，k，a中。多字母组合ui出现了9次，uif出现了4次，u很可能对应明文字母t，i很可能对应明文字母h，f很可能对应明文字母e。将密文分组尝试是否它们可形成了一个完整的词。在第一行的前4个字母UIFSF可能对应明文字母thee，但如果它们是个词，则很可能对应的单词是there，因此，S对很可能应于字母r。继续进行试探，最终可得出完整的明文如下：There were two brothers, John and Peter. John was two years younger than Peter but he was a clever boy. He was good at English and Maths. Peter was not a clever boy. He was not good at anything. John helped Peter to do his homework but he was always in trouble with his teachers. One day the boys went to a new school.为了预防频率分布分析法对单字母替代密码系统的攻击，减少明文字母频率结构仍能保留在密文中的程度。加密时可以使用多字母的加密方法。13 Vergenere 密码本节用Vigenere为例来说明多字母替代原理。Vigenere技术是处理明文时使用不同的单字母替代， 它是最简单的一种多字母密码算法，由16世纪法国人Blaise de Vigenere发明。表11 Vigenere表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 za 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 Zb 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 Ac C D E F G H I J K L M N O P Q R S T U V W X Y Z A Bd D E F G H I J K L M N O P Q R S T U V W X Y Z A B Ce E F G H I J K L M N O P Q R S T U V W X Y Z A B C Df F G H I J K L M N O P Q R S T U V W X Y Z A B C D Eg G H I J K L M N O P Q R S T U V W X Y Z A B C D E Fh H I J K L M N O P Q R S T U V W X Y Z A B C D E F Gi I J K L M N O P Q R S T U V W X Y Z A B C D E F G Hj J K L M N O P Q R S T U V W X Y Z A B C D E F G H Ik K L M N O P Q R S T U V W X Y Z A B C D E F G H I Jl L M N O P Q R S T U V W X Y Z A B C D E F G H I J Km M N O P Q R S T U V W X Y Z A B C D E F G H I J K Ln N O P Q R S T U V W X Y Z A B C D E F G H I J K L Mo O P Q R S T U V W X Y Z A B C D E F G H I J K L M Np P Q R S T U V W X Y Z A B C D E F G H I J K L M N Oq Q R S T U V W X Y Z A B C D E F G H I J K L M N O Pr R S T U V W X Y Z A B C D E F G H I J K L M N O P Qs S T U V W X Y Z A B C D E F G H I J K L M N O P Q Rt T U V W X Y Z A B C D E F G H I J K L M N O P Q R Su U V W X Y Z A B C D E F G H I J K L M N O P Q R S Tv V W X Y Z A B C D E F G H I J K L M N O P Q R S T Uw W X Y Z A B C D E F G H I J K L M N O P Q R S T U Vx X Y Z A B C D E F G H I J K L M N O P Q R S T U V Wy Y Z A B C D E F G H I J K L M N O P Q R S T U V W Xz Z 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在这个方案中，同一个字符具有不同的密文，从而改变了单字母替代中密文的惟一性。该方案的加密过程是，第一行代表明文字母，弟一列代表密钥字母。加密的过程很简单：给定一个密钥字母x和一个明文字母y，密文字母则位于标为x的行和标为y的列的交叉点；在此情况下密文为v。假设明文为：brother。密钥为：boy得密文CFMUVCS。第一个C是在b行b列上；第二个F是在r行o列上；同样的道理M在o行y列上；重复使用密钥boy，第四个U是在t行b列上。其余依此类推。加密时用明文、Vigenere表和密钥。解密时用密文、同样Vigenere表和同样密钥。为了加密一个消息，需要一个与该消息一样长的密钥。通常，该密钥为一重复的关键词。解密也同样简单。密钥字母标识行。密文字母所在行的位置决定列，该明文字母位于该列的顶部。该密码的强度在于对每个明文字母由多个密文字母对应，每个明文字母对应于该关键词的每个独特的字母，因此，该字母的频率信息是模糊的。然而，并非所有明文结构的所有知识都丢失了。虽然对Vigenere密码分析极为困难，但只要有了充足的密文，使用已知的或可能的明文序列仍能够破译该系统。为了避免关键词的重复降低密码系统的强度，Joseph Mauborgne，提出使用一种真正与消息一样长度的随机密钥，该密钥没有重复。这种方案被称之为一次一密，是理论上不可破译的，因为它产生不带有与明文有任何统计关系的随机输出。因为该密文不包含任何的明文信息，因此无法直接破译这样的编码。对这种方法的实际困难在于，发送者和接收者必须拥有并保护该随机密钥，因此，该密码尽管在密码中性能卓越，但很少使用。14 单表置换密码本节用栅栏技术为例来说明置换原理。栅栏技术是最简单的置换密码。它通过执行对明文字母位子的某种置换，取得一种类型完全不同的映射。在该密码中以对角线顺序写下明文，并以行的顺序读出。例如，用深度2的栅栏密码加密消息security，消息写成如下形式： s c r t e u i y加密后的密文为 scrteuiy如果用深度3的栅栏密码加密，消息security写成如下形式： s u t e r y c I加密后的密文为 suteryci15 恺撒密码的JAVA编程程序流程图进行恺撒加密运算按加密钮？进行恺撒解密运算显示结果输入单词显示图形界面关闭图形界面按解密钮？按退出钮？是否否否图1.1恺撒密码流程图是是加、解密算法编程思路 将26个英文字母分别用整数025替代（Z=0,A=1,B=2,以此类推），凯撒密码的JAVA编程实质上就是求余的运算。设加密变换是用密文字母替代明文字母：将凯撒密码写成公式是：。如果移位可以是任何量，则通用的凯撒算法是：，在1到25的范围取值。解密算法则是：。例如,明文为 security对应的数据序列为 19 5 3 21 18 9 20 25。当3时,求得密文序列为 22 8 6 24 21 12 23 28(2)对应的密文为 vhfxulwb。16 恺撒密码实验指导及JAVA源程序实验指导1、 安装Sun公司JDK1.3（也可用VJ+或Jbuilder），JDK1.3(或J2SE)可由网址下载。2、 将恺撒密码JAVA源程序取名C1.java 存盘、编译和运行。3、 将明文security输入到方框内4、 点击加密按钮，显示加密后的密文VHFXULWB5、 将密文VHFXULWB输入到方框内6、 点击解密按钮，显示解密后的明文SECURITY7、 实验结束后点击Exit按钮退出。实验说明1、 输入的英文字母不分大小写。2、 如果输入的不全是英文字母，系统将只取其中的英文字母处理，例如：1a2B3等同于AB。3、 系统输出为大写的英文字母。4、 凯撒密码的密钥在程序中已经定义为3。如想修改，需重新定义程序中密钥k,再编译和运行。恺撒密码的JAVA源程序/ 程序名 ： C1.java/ 目的 ： 用于JAVA课凯撒密码演示和实验 / 编写时间： 2004年3月20日import java.awt.*;import java.awt.event.*;class Gf Label a1=new Label(input); Label a2=new Label(output); Button b1=new Button(Encrypt); Button b2=new Button(Decrypt); Button b3=new Button(Exit); TextField t1=new TextField( ); dd1 d1=new dd1(); dd2 d2=new dd2(); dd3 d3=new dd3(); void grun( ) a1.setBounds(40,50,50,20); a2.setBounds(40,130,200,20); b1.setBounds(new Rectangle(30,85,60,30); b2.setBounds(new Rectangle(120,85,60,30); b3.setBounds(new Rectangle(210,85,60,30); t1.setBounds(100,50,100,25); Frame ww=new Frame(欢迎使用凯撒加密实验软件); ww.setLayout(null); ww.add(a1); ww.add(a2); ww.add(b1); ww.add(b2); ww.add(b3); ww.add(t1); ww.setBounds(100,100,300,200);