安徽工程大学信息安全原理及应用第2讲密码学理论基础.ppt

第2讲 密码学基础,案例：莫尔斯电码里的爱情,早已被新科技所取代的莫尔斯密码，却在中国的互联网世界里演绎了一段费尽周折的爱情猜谜传奇。 一男子向一女子表白，女子却给了一段莫尔斯密码，以及很少的提示，并表示，破译这个密码，才答应和他约会。男子死活不得求解，又在百度贴吧里将密码贴出以求助网友。 电码如下： “*-/*-/-*/*-/*-/*-/-*/*-/*-/*-/-*/*- /*-/*-/-*/*-/-*/*-/*-/*-/-*/*-/” “她唯一给我的提示就是这个是5层加密的密码，也就是说要破解5层密码才是答案。最终语言是英语。 ” 网友贴出了莫尔斯密码对照表，然后发现相应密码对应的数字组合和英文字母组合分别是：“4194418141634192622374”、“daiddahadafcdaibfbbcgd”,网友“片羿天使”将莫尔斯密码对应的数字“41 94 41 81 41 63 41 92 62 23 74”转换成了手机键盘字母,以41为例，它对应的就是传统手机键盘上的“4”的第一个字母，“94”则是“9”的第4个字母。 这样片羿天使得到了第二步的答案：“G Z G T G O G X N C S ” 。 片羿天使说“因为QWE的格式是被世人所认可的，也就有可能成为密码的码表。码表QWE=ABC依次类推。”按照这样的次序，上面的来自于手机键盘的字母，就转换到了第三步答案：“O T O E O I O U Y V L”。,案例：莫尔斯电码里的爱情,在第四步中，片羿天使用了包括凯撒、乘法等等方法，对第三步几乎可以看出来的答案进行了进一步的解码，最后发现只有栅栏密码才能读得通。片羿天使将这组字母分成了“O T O E O I”和“ O U Y V L”两排，然后对插重组得到第四步的字母排列：“OOTUOYEVOLI”。 第五步于 是变得最为简单起来，那便是将“OOTUOYEVOLI”倒序排列，即“I LOVE YOU TOO”。,案例：莫尔斯电码里的爱情,密码学的发展历史(1),自人类社会出现战争便产生了密码,Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。,Julius Caesar发明了凯撒密码,密码学的发展历史(2),1834年，伦敦大学的实验物理学教授惠斯顿发明了电机，这是通信向机械化、电气化跃进的开始，也为密码通信采用在线加密技术提供了前提条件。 1920年，美国电报电话公司的弗纳姆发明了弗纳姆密码。其原理是利用电传打字机的五单位码与密钥字母进行模2相加。,密码学的发展历史(3),两次世界大战大大促进了密码学的发展。,二战中美国陆军和海军使用的条形密码设备M-138-T4。根据1914年Parker Hitt的提议而设计。25个可选取的纸条按照预先编排的顺序编号和使用，主要用于低级的军事通信。,Kryha密码机大约在1926年由Alexander vo Kryha发明。这是一个多表加密设备，密钥长度为442，周期固定。一个由数量不等的齿的轮子引导密文轮不规则运动。,密码学的发展历史(4),两次世界大战大大促进了密码学的发展。,转轮密码机ENIGMA，由Arthur Scherbius于1919年发明，面板前有灯泡和插接板；4轮ENIGMA在1942年装备德国海军，英国从1942年2月到12月都没能解读德国潜艇的信号。,英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。,密码学的发展历史(5),1949年香农发表了一篇题为保密系统的通信理论的著名论文，该文首先将信息论引入了密码，从而把已有数千年历史的密码学推向了科学的轨道，奠定了密码学的理论基础。 1976年，美国密码学家W.Diffie和M.Hellman在一篇题为密码学的新方向一文中提出了一个崭新的思想，不仅加密算法本身可以公开，甚至加密用的密钥也可以公开。 1977年美国国家标准局颁布了数据加密标准DES 2001年11月26日，正式颁布AES为美国国家标准。,2.2 基本概念,什么是密码学 密码学是关于加密和解密变换的一门科学，是保护数据和信息的有力武器。 密码是什么? 密码就是变换。（信息代码变换、数据电平变换） 变换是什么？变换是一种算法实现过程。 谁来做变换？变换可以由硬件和软件实现。（人、器件部件、计算机）,2.2 基本概念,什么是密码学 密码学是研究密码系统或通信安全的一门学科，分为密码编码学和密码分析学。 密码编码学是使得消息保密的学科 密码分析学实际要研究加密消息破译的学科,Shannon模型,X,明文（plain-text）： 作为加密输入的原始信息。 Y,密文（cipher-text）：对明文变换的结果。 E,加密（encrypt）：是一组含有参数的变换。 D,解密（decrypt）：加密的逆变换。 Z,密钥（key）：是参与加密解密变换的参数。,密码系统（Cryptosystem）,定义: (密码体制）它是一个五元组（P,C,K,E,D)满足条件： （1）P是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间） *（4）任意 ,有一个加密算法 和相应的解密算法 ，使得 和 分别为加密解密函 数，满足 。,密码体制的分类,几种不同的分类标准 按操作方式进行分类 操作方式：是明文变换成密文的方法。 替代操作、置换操作、复合操作。 按照使用密钥的数量进行分类 对称密钥（单密钥）。 公开密钥（双密钥）。 按照对明文的处理方法进行分类 流密码。 分组密码。,按加解密采用的密钥不同,按密码出现的时间不同,古典密码,现代密码,密码学（Cryptology）,(Symmetric cipher),(Asymmetric cipher),分组密码,流密码,公钥密码,按加密的方式,对称密码,非对称密码,(Classical cipher),(Modern cipher),(Block cipher),(Stream cipher),(Public-Key cipher),密码系统的分类(2),根据明文和密文的处理方式分类 分组密码体制（Block Cipher） 设M为明文，分组密码将M划分为一系列明文块Mi，通常每块包含若干字符，并且对每一块Mi都用同一个密钥Ke进行加密。 M=(M1, M2, ,Mn) ，C=(C1, C2 , ,Cn,)，其中Ci=E(Mi,Ke)， i=1,2,n。 序列密码体制（Stream Cipher） 将明文和密钥都划分为位(bit)或字符的序列，并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密。 M=(M1, M2, ,Mn) ， Ke=(ke1, ke2,ken)，C=(C1, C2,Cn)，其中Ci=E(mi,kei) ，i=1,2,n。,密码系统的分类(3),根据加密算法是否变化分类 设E为加密算法，K0, K1,Kn,为密钥，M0,M1,Mn为明文，C为密文 固定算法密码体制 C0=E(M0,K0), C1=E(M1,K1),., Cn=E(Mn,Kn) 变化算法密码体制 C0=E1 (M0,K0), C1=E2 (M1,K1),., Cn=En (Mn,Kn),密码分析,截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。 密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。,密码分析,密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别 密码设计是利用数学来构造密码 密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力，有时还靠点运气。,密码分析方法分析法,确定性分析法 利用一个或几个已知量(比如，已知密文或明文-密文对)用数学关系式表示出所求未知量(如密钥等)。已知量和未知量的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关键步骤。 统计分析法 利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。,密码分析方法-穷举破译法,对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；一般来说，要获取成功必须尝试所有可能密钥的一半。 或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法(Complete trial-and-error Method)。 只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。,柯克霍夫斯(Kerckhoffs)假设,假定：密码分析者知道对方所使用的密码系统 包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法 ）、密钥空间及其统计特性。 不知道密钥。 密码体制的安全性仅应依赖于对密钥的保密，而不应依赖于对算法的保密。只有在假设攻击者对密码算法有充分的研究，并且拥有足够的计算资源的情况下仍然安全的密码才是安全的密码系统。 一切秘密寓于密钥之中,密码分析,密码分析：从密文推导出明文或密钥 。 密码分析：常用的方法有以下4类： 惟密文攻击（cybertext only attack）：密码分析者有一个或更多的用同一个密钥加密的密文，通过对这些截获的密文进行分析得出明文或密钥 已知明文攻击（knownplaintext attack）：除要破译的密文外，密码分析者有一些明文和用同一密钥加密这些明文所对应的密文。,选择明文攻击（chosenplaintext attack）：密码分析者可得到所需要的任何明文所对应的密文，这些密文与要破译的密文是用同一个密钥加密得来的 选择密文攻击（chosenciphertext attack）：密码分析者可得到所需要的任何密文所对应的明文，解密这些密文所使用的密钥与要破译的密文的密钥是相同的,密码分析,密码系统,一个好的密码系统应满足： 系统理论上安全，或计算上安全； 系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密； 加密和解密算法适用于密钥空间中的所有元素； 系统既易于实现又便于使用。,加密的功能,保密性：基本功能，使非授权者无法知道消息的内容。 鉴别：消息的接收者应该能够确认消息的来源。 完整性：消息的接收者应该能够验证消息在传输过程中没有被改变。 不可否认性：发送方不能否认已发送的消息。,古典加密技术,从古到今有无数种加密方法，但归类起来，古代主要是代替密码、置换密码以及两者的结合。 代替密码 简单代替密码 多码代替密码 多字母代替密码 多表代替密码 置换密码：换位密码,传统密码及其破译,Scytale密码和恺撒密码,最先有意识的使用一些技术的方法来加密信息的可能是公元前500年的古希腊人。他们使用的是一根叫scytale的棍子。送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人。如果不知道棍子的粗细是不可能解密里面的内容的，如下图所示。,公元前50年，著名的恺撒大帝发明了一种密码叫做恺撒密码。在恺撒密码中，每个字母都与其后第三位的字母对应，然后进行替换。如果到了字母表的末尾，就回到开始，如此形成一个循环。当时罗马的军队就用恺撒密码进行通信。 恺撒密码明文字母表：A B C D E F G X Y Z 恺撒密码密文字母表：D E F G H I J A B C 26个字符代表字母表的26个字母，从一般意义上说，也可以使用其它字符表，一一对应的数字也不一定要是3，可以选其它数字。,Caesar密码,乘数密码算法,加密函数取形式为 e(x)=ax (mod 26)， aZ26 要求唯一解的充要条件是gcd( a,26)=1 该算法描述为： 设P=C=Z26， K=a Z26|gcd(a,26)=1, 对k=a K, 定义 ek(x)=ax (mod 26)和dk(y)=a-1(y)(mod 26)， x,y Z26 例子: a=9, ABCDEFGHIJKLMNOPQRSTUVWXYZ AJSBKTCLUDMVENWFOXGPYHQZIR 明文 密文 cipher = SUFLKX,乘数密码分析,对于乘数密码，当且仅当a与26互素时，加密变换才是一一映射的，因此a的选择有11种： a=3,5,7,9,11,15,17,19,21,23,25 可能尝试的密钥只有11个,栅栏密码,所谓栅栏密码，就是把要加密的明文分成N个一组，然后把每组的第i个字连起来，形成一段无规律的话。 就是组成栅栏的字母一般不会太多。（一般不超过30个） 一般比较常见的是2栏的栅栏密码。 比如明文：THERE IS A CIPHER 去掉空格后变为：THEREISACIPHER 两个一组，得到：TH ER EI SA CI PH ER 先取出第一个字母：TEESCPE 再取出第二个字母：HRIAIHR 连在一起就是：TEESCPEHRIAIHR,解密的时候，我们先把密文从中间分开，变为两行： T E E S C P E H R I A I H R 再按上下上下的顺序组合起来： THEREISACIPHER 分出空格，就可以得到原文了： THERE IS A CIPHER,栅栏密码,仿射密码,仿射密码是一种替换密码。它是一个字母对一个字母的。 它的加密函数是 ， 其中 a和m互质。 m是字母的数目。 解密函数为：,例 设k（7，3），注意到7-1(mod 26)=15,加密函数是ek(x)=7x+3，相应的解密函数是dk(y)=15(y-3)=15y-19 , 易见 dk(ek(x)=dk(7x+3)=15(7x+3)-19 =x+45-19 =x (mod 26) 若加密明文：hot ，首先转换字母h,o,t成为数字7,14,19, 然后加密： 解密：,希尔密码,希尔密码（Hill Password）是运用基本矩阵论原理的多字母代换密码，由Lester S. Hill在1929年发明。每个字母当作26进制数字：A=0, B=1, C=2. 一串字母当成n维向量，跟一个nn的矩阵相乘，再将得出的结果模26。注意用作加密的矩阵（即密匙） 是可逆的，否则就不可能译码。只有矩阵的行列式和26互质，才是可逆的。,其中所有的运算都是在 中进行。,例 假定密钥K是 ，则K-1 = 。现在我们加密明文july分为两个明文组（9，20）（相应于ju）和（11，24）（相应于ly）。计算如下： 因此，july的加密是DELW。 同理，可使用K-1进行解密。,Vigenre密码,构成 明文：每个字符惟一对应一个025间的数字。 密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如a 表示位移 0，b 表示位移 1，c 表示位移 2， ）。 加密过程： 将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模26），得到密文数字串； 最后，将密文数字串转换为字母串。,例 设m6，且密钥字是k=CIPHER,这相应于密钥。假定明文串是 this cryptosystem is not secure 首先将明文串转化为数字串，按6个一组分段，然后模26“加”上密钥字得： 相应的密文串将是: VPXZGIAXIVWPUBTTMJPWIZITWZT 解密过程与加密过程类似,不同的只是进行模26减,而不是模26加。,置换密码,在简单的纵行置换密码中，把明文按列写入，按行读出，而密钥事实上由两方面信息组成：行宽、列高，读出顺序默认从左到右。一个简单纵行置换密码比如：明文：computer graphics may be slow，按照列宽10个字符的方式写出为： c o m p u t e r g r a p h i c s m a y b e s l o w 可以得到密文：caeopsmhlpioucwtsemragyrb，,下面是一个由密钥确定读出顺序的例子：如果再加上密钥： 密钥： 4 3 1 2 5 6 7 明文： a t t a c k p o s t p o n e d u n t i l t w o a m x y z 按照密钥大小的顺利，按照列的字符得到密文：TTNAAPTMTSUOAODWCOIXPETZ。,置换密码,例 假定m6，密钥是以下置换 ： ；则逆置换 为： 。 给出明文 shesellsseashellsbytheseashore. 首先把明文分为6个字母一组： shesel lsseas hellsb ythese ashore . 每六个字母按重排，得密文： EESLSH SALSES LSHBLE HSYEET HRAEOS 用 类似地解密。,置换密码,置换密码是Hill密码的特例。,Playfair密码,Playfair在1854年发明了Playfair密码。Playfair依据一个5*5的正方形组成的密码表来编写，密码表里排列有25个字母。如果一种语言字母超过25个，可以去掉使用频率最少的一个。如，法语一般去掉w或k，德语则是把i和j合起来当成一个字母看待。英语中z使用最少，可以去掉它。 C I P H E R A B D F G K L M N O Q S T U V W X Y Z,加密规则是按成对字母加密，规则为“相同对中的字母加分隔符(如x)，同行取右边，同列取下边，其他取交叉” 。 明文：balloon 单词中的ll为相同字符，所以分组为：ba lx lo on 明文：he，h和e在矩阵中同一行，都取右边的字符，密文为：EC 明文：dm，d和m在矩阵中同一列，都取下面的字符，密文为：MT 明文：kt，k和t在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：MQ 明文：OD ，O和D在矩阵中不同行也不同列，取交叉顶点上的字符，密文为：TR 以这个55变换矩阵为例，可以对单词进行加密，加密结果如表2-1所示。,表2-1,一次一密乱码本,如上所述的所有密码算法均被破解，那么是否存在无法破解的理想加密方案呢？香农证明了一种密码属于这种情况，它就是一次一密乱码本（one-time pad）。 一般说来，一次一密乱码本就是一个大的不重复的真随机密钥字母集，发送者用乱码本中的每一个密钥准确地加密一个明文字符，加密是明文字符和密钥字符进行模26加法。比如： 明文： onetimepad 密钥： TBFRGFARFM 密文： IPKLPSFHGQ 因为： O+Tmod26=I，N+Bmod26=P，E+Fmod26=K， 如果窃听者不能得到用来加密的一次一密乱码本，这个方案就是完全保密的。给出的密文消息相当于同样长度的任何可能的明文消息。,随机密钥 安全强度取决于密钥的随机性 理论上不可破 实际上不可行 产生大量的随机密钥难 密钥分配与保护更难,明文：To be or not to be that is the