密码分析现代加密技术.ppt

第2章电子商务安全的技术保障,加密技术(续),上一堂课内容回顾,2.1加密技术2.1.1加密技术概述(明文、密文、加密、解密、密钥)2.1.2基本加密方法替换法：单表替换法、多表替换法；移位法（或称变换法）：列换位法和矩阵换位法2.1.3对称密码体制（DES）2.1.4公钥密码体制（RSA）,古典加密技术,现代加密技术,stte_erh_noe_dob_mpr_osi_rtd_eog_,密钥k=6,所以按6个一行（包括空格）来分段，得到下面的样子：stte_erh_noe_dob_mpr_osi_rtd_eog然后从上到下，一列一列的连起来，就得到了明文：sendmoretroopstothebridge(sendmoretroopstothebridge),问：以下加密过程是什么方法？,对下列一段文字进行加密，明文如下：theebusinesssecureisveryimportant密钥长度=6明文长度与密钥长度相同的新明文格式:theebusinesssecureisveryimportant明文按列重新排列，形成密文，结果如下：tusrvmnhseepteisroeecstbsuia,答：列换位法算法：先把原文顺序排列，按密钥长度分行，再按列的顺序转换为一行，就为密文。,移位法（变换法）的关键思想：,按一定规则写出明文，按另一规则读出密文。密钥：用于读密文的方法和写明文的方法,替换法打乱的密码替换,补：打乱的密码替换不仅仅是简单的移位变换每个字母变换到不同的字母密钥长度是26个字母eg.Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZCipher:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:IFWEWISHTOREPLACELETTERSCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA,单表替换密码,关键词加密法(使用密钥的单表替换密码)：简单的方法给出密钥写出密钥（删除重复字母）在其下面依次写出剩余字母（以横、纵行）（按列读取字母得到密文）,单表替换密码,举例：给定密钥字STARWARS去掉重复字母得到STARW填写剩余字母：STARWBCDEFGHIJKLMNOPQUVXYZ按列读取字母得到密文Plain:ABCDEFGHIJKLMNOPQRSTUVWXYZCipher:SBGLQZTCHMUADINVREJOXWFKPY可以用这个密钥加密、解密例如Plaintext:IKNOWONLYTHATIKNOWNOTHINGCiphertext:HUINFNIAPOCSOHUINFINOCHIT（或：STARWBCDEFGHIJKLMNOPQUVXYZ）,课堂练习：,例：设密钥为spectacular，china的密文是什么？,elrhs,问：已知采用单表替换法，试分析以下密文的原文？LIZHZLVKWRUHSODFHOHWWHUV,解：实验每个密钥。LIZHZLVKWRUHSODFHOHWWHUVOriginalciphertextKHYGYKUJVQTGRNCEGNGVVGTUtryshiftof1JGXFXJTIUPSFQMBDFMFUUFSTtryshiftof2IFWEWISHTOREPLACELETTERStryshiftof3*plaintextHEVDVHRGSNQDOKZBDKDSSDQRtryshiftof4GDUCUGQFRMPCNJYACJCRRCPQtryshiftof5.MJAIAMWLXSVITPEGIPIXXIVWtryshiftof25eg.breakciphertextGCUAVQDTGCM,补充:密码学中的几个基本概念,密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支，密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问密码分析学(Cryptanalytics)，研究分析破译密码的学问。,补充:密码学中的几个基本概念,明文(消息)(Plaintext)、密文(Ciphertext)或密报(Cryptogram、加密(Encryption)、解密(Decryption)、密钥(Key),加密员或密码员(Cryptographer)：对明文进行加密操作的人员。加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。解密算法：接收者对密文进行解密时所采用的一组规则。截收者(Eavesdropper)：在信息传输和处理系统中的非授权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。,回顾,（2）密码学中的几个基本概念,密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人。被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。,打乱的密码替换的安全性,密钥总数：26！如此多的密钥，可以认为安全吗？!NO!仍然有语言统计规律需要其它方法隐藏这种规律性,2.1.2.3语言冗余度与密码分析,人类语言是有冗余度的字母使用的频率是不相同的在英语中，e的使用率是最高的其次，t,r,n,i,o,a,s其它字母使用的较低,英语字母使用频率,1,2,3,4,4,5,6,7,英语字母中常见的组合,字母频率在密码分析中的应用,计算密文中字母出现的频率与已知字母分布比较确定每个字母被映射到什么字母单个字母出现的可能是A或I一般来说三个字母出现的可能是THE或AND还可以用其他通常出现的双字母或三字母组合还可以应用其它很少应用的字母,例：密码分析,密文:wklvphvvdjhlvqrwwrrkdugwreuhdn,该消息长度太短，很难完全用频率法分析，分析时还需要结合其他知识。空格给出了分词的重要信息。先考虑英语中的短词，如：（双字母组合）amintobehewe（三字母组合）andareyoushe等重要线索：wrr，英文中常用xyy结构的单词只有see和too，次常用的单词还有add,odd,off,特别生疏的单词woo和gee。单词lv，也是wklv的结果，有可能是双字母so,is,in等，lv可能是is。假设第一个单词是this，即密文的K是明文的H。考察已译出的字母，他们均是明文字母后移3位。,Thismessageisnottoohardtobreak!,2.1加密技术（课本P37-P41）,2.1.1加密技术概述2.1.2基本加密方法2.1.3对称密码体制2.1.4公钥密码体制,古典加密技术,现代加密技术,2.1.3.对称密码体制,2.1.3.1对称密码体制概述又称对称密码体系（或对称密钥密码体制），指加密和解密使用同一密钥的加密体系。其中较为流行的对称加密算法有：DES、3DES、IDEA、RC5、AES等，其中DES是对称加密算法中的代表。P=D（E（P，K），K）,加密,解密,密文,明文,明文,密钥,对称密码体制概述,在对称密钥密码体制中，加密运算与解密运算使用同样的密钥。通常，使用的加密算法比较简便高效，密钥简短，破译极其困难。但是，在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题。,2.1.3.2DES(DataEncryptionStandard),数据加密标准DES（DataEncryptionStandard）是美国国家标准局于1976年公布的加密标准，DES主要用于商业界及美国政府当局的非机密应用（除国防部以外的其他部门的计算机系统的数据加密标准），后来被ISO接受为国家标准。现在广泛应用于电子资金转帐系统、电子商务等领域,DES算法,DES是一个分组加密算法，它以64位为分组对数据加密。64位一组的明文从算法的一端输入，64位的密文从另一端输出。DES是一个对称算法：加密和解密用的是同一算法。密钥的长度为56位。（密钥通常表示为64位的数，但其中有8位属于校验位，可以忽略。）所有的保密性依赖于密钥。,DES算法,输入X,X0,L0,输出Y,R0,L16,R16,初始置换,16次迭代运算,逆初始置换,DES加密过程图,明文分组,DES被美国政府确定是很难破译的，因此被美国政府作为限制出口的一种技术。在此标准下有72，000，000，000，000，000（72Q）多种密钥可供使用。对于每条给定的信息，密钥在这72Q个密钥中随机选择。该加密方法属于对称加密方法，加密方和解密方必须使用相同的密钥。,如果每微秒试探一次，用穷举法破解56位密钥加密的密文，需要2283年！,DES的安全性评论,DES公布之后，在整个80年代，密码学家们一致认为它没有弱点，这就意味着破解一条用DES加密的消息最快的方法是用强力攻击，使用当时最快的计算机破解一条信息也要耗费数年时间。到了90年代，计算机速度越来越快。1998年，电子边境基金会（EFF）动用一台价值25万美元的高速电脑，在56h内利用穷尽搜索的方法破译56位密钥长度的DES。结论：利用穷举法搜索攻击，只能说明56位的密钥可能太少；DES的迭代次数可能太少。,2.1.3.33DES（三重DES）,3DES需要执行三次常规的DES加密步骤，但最常用的3DES算法中仅用两个56位DES密钥。缺点是：时间开销较大，时间是DES算法的三倍。但从另一方面看，3DES的112位密钥长度在将来是合适的。,2.1.3.4IDEA算法,IDEA算法又叫国际数据加密算法，是瑞士联邦技术学院开发的一种面向数据分组块的数据加密标准。相对于DES的56位密钥，它使用128位密钥，每次加密一个64位的数据块。IDEA算法的安全性相对DES算法有很大的提高，其密钥是128位，在穷举攻击的情况下，需要经过2128次加密才能恢复出密钥。假设一台计算机每秒产生和运行10亿个密钥，它将检测1013年。,2.1.4公开密钥密码体制RSA（Rivest,Shamir,Adleman）算法,又称非对称加密体系，即加密和解密过程分别使用两个不同的密钥体系。它是现代密码学的最重要的发明，典型算法有：RSA、背包算法、Rabin算法、概率加密算法、McEliece算法等。,1976年，美国斯坦福大学的Diffie和Hellman提出了公钥密码的新思想，一年后，美国麻省理工学院的三位博士Rivest,Shamir,Adleman设计了RSA加密算法。,在“公开密钥密码体制”中，加密密钥不同于解密密钥，加密密钥公之于众，谁都可以用；而解密密钥只有解密人自己知道。它们分别称为“公开密钥”（publickey）和“秘密密钥”（privatekey）。,2.1.4.1公开密钥加密算法的特点,公开密钥密码体制算法：使用一个加密算法E和一个解密算法D，它们彼此完全不同，根据已选定的E和D，即使已知E的完整描述，也不可能推导出D。,密钥对产生源,2.1.4.2RSA,RSA算法是最著名的公开密钥体制。基于大数分解的难度。其公开密钥和私人密钥是一对大素数的函数，从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。RSA算法过程：首先是设计密钥，然后是对消息加密，最后是对密文解密。,（1）设计密钥,在离线方式下，先产生两个足够大的大素数p、q。可得p与q的乘积为n=pxq。再由p和q算出另一个数z=(p-1)(q-1)，然后再选取一个与z互素的奇数e，称e为公开指数；从这个e值可以找出另一个值d，并能满足e*dmod(z)=1条件。舍弃p和q（但绝不能泄露）。由此而得到的两组数(n，e)和(n，d)分别被称为公开密钥和秘密密钥，或简称公钥和私钥。,（2）加密,对于明文M，用公钥(n，e)加密可得到密文C。C=Mmod(n),e,（3）解密,对于密文C，用私钥(n，d)解密可得到明文M。M=Cmod(n)当定义用私钥(n，d)先进行解密后，然后用公钥(n，e)进行加密，就是数字签名。,d,RSA（Rivest,Shamir,Adleman）算法,密钥生成任选两个不同的大素数p,q。计算n=p*qz=(p-1)(q-1)任选e,使与z互质。n和e便是用户的公钥。（注：e的选取是很容易的，例如，所有大于p和q的质数都可用）确定解密密钥d,d*emodz=1。（根据e、p、q很容易确定d）d保密，d是用户的私钥。加密：cmemodn解密：mcdmodn,c是对应于明文m的密文，m是对应于密文c的明文。,举例：用RSA密码算法对信息“publickeyencryptions”进行加密和还原。,将明文以两个字符为一组，并将明文数字化，00表示a,01表示b,24表示y，25表示z。得到：Publickeyencryptions15200111080210042404130217241519081414181.选取p=43和q=59。2.计算n=43*59=2537。3.z=(p-1)(q-1)=42*58=24364.选择e=13,解方程e*dmod2436=1,得到d=937.5.对明文数字m=1520的加密,c=E(m)=me(modn)=152013(mod2537)=00956.对密文数字0095的解密过程，D(c)=cd(modn)=95937mod2537=1520,任选素数p,q。,计算n=p*q,z=(p-1)(q-1),选e,使与z互质。,课堂练习：,已知公开密钥：（n，e）=（15，11）p=3,q=5，求私人密钥（n，d）？假设明文为，试写出加密和解密方程。,课堂练习（讲解）：,选取p=3,q=5，则n=pxq=15，z=(p-1)(q-1)=8选取e=11（大于p和q的质数），通过d*11mod8=1，计算出d=3得到公开密钥：（n，e）=（15，11）私人密钥：（n，d）=（15，3）,假定明文M为整数13。则密文C为C=Mmodn=13mod15=1,792,160,394,037mod15=7复原明文M为：M=Cmodn=7mod15=343mod15=13,e,11,d,3,RSA算法基于两个事实（这些事实保证了RSA算法的安全有效）：已有确定一个是不是素数的快速算法。尚未找到确定一个合数的质因子的快速算法。RSA通常的实现：RSA简洁，但计算速度比较慢，通常加密中并不是直接使用RSA来对所有的信息进行加密，最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用RSA对刚才的加密密钥进行加密。,RSA的安全性取决于从公开密钥计算出秘密密钥的困难程度。等于从n中找出它的质因数p和q。,RSA的优缺点,优点RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。该算法的加密密钥和加密算法分开，使得密钥分配更为方便。,它特别符合计算机网络环境。对于网上的大量用户，可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密通信，只需从公钥簿上查出对方的加密密钥，用它对所传送的信息加密发出即可。对方收到信息后，用仅为自己所知的解密密钥将信息脱密，了解报文的内容。由此可看出，RSA算法解决了大量网络用户密钥管理的难题，这是公钥密码系统相对于对称密码系统最突出的优点。,缺点1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。2)安全性,RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。目前，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击RSA的方法，如选择密文攻击。,3)速度太慢,RSA的分组长度太大。为了速度问题,目前人们广泛使用单,公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA来给文件密钥加密,极好的解决了单钥密码的密钥分发问题。,总结：对加密算法要求要达到以下几点：（1）必须提供高度的安全性；（2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又便于理解和掌握；（3）安全性应不依赖于算法的保密，其加密的安全性仅以加密密钥的保密为基础；（4）必须适用于不同的用户和不同的场合；（5）实现经济、运行有效；（6）必须能够验证，允许出口。,练习-4:1.对称密码体制与非对称密码体制的含义、特点？较为流行的对称加密算法与非对称加密算法有哪些？2.RSA算法原理与过程？RSA算法的优缺点？,再见,Doyouhavemadeaprogresstoday?,