《2.密码与解密技术.pptx》由会员分享，可在线阅读，更多相关《2.密码与解密技术.pptx（73页珍藏版）》请在三一文库上搜索。
1、1 密码与解密技术 最朴素的密码 2 天王盖 地虎！ 宝塔镇 河妖！ 最早的古典密码 凯撒密码 3 attackattackattackattack defensedefensedefensedefense 最早的古典密码 凯撒密码 4 dwwdfndwwdfndwwdfndwwdfn ? farmfarmfarmfarm 凯撒密码原理 简单的移位替换 当偏移量是3的时候，所有的字母A将被替换成 D，B变成E，以此类推。 偏移量=1,25 5 课堂挑战实践-恺撒密码破译 o 某个女生递给你的字条上写着以下密文： n 密文： yqqf yq mrfqd ftq bmdfk n 明文 = ? 字母
2、表：(密码本） 密文：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 明文：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 L 解密过程：pi=Di（Ci）=Ci-12 加密算法：C = E（p）= （p+12）mod（26） 解密算法：P = D（C）= （C-12）mod（26） meet me after the party 凯撒密码的破解分析 o 暴力破解 n 25种可能性 o 常见词模式分析 n ftq o f-q+26=12 o t-q = 3 n ftq - the 7 D
3、ecryptionCandidate plaintext 0exxegoexsrgi 1dwwdfndwrqfh 2cvvcemcvqpeg 3buubdlbupodf 4attackatonce 5zsszbjzsnmbd 6yrryaiyrmlac . 23haahjrhavujl 24gzzgiqgzutik 25fyyfhpfytshj 凯撒密码的改进 o 加入密钥 n 有意改变字母的排列顺序，可增大密钥空间 n key phases=The quick brown fox jumps over the lazy dog. n key=thequickbrownfxjmpsvlazyd
4、g o 密钥空间 n 26! = 4X1026 o Unbreakable? 8 频率统计分析 9 频率统计分析破解密码实例 o 密文: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESX UDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDT SVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZ WPFUPZHMDJUDTMOHMQ o 统计字母的频率 10 0 2 4 6 8 10 12 14 ABCDE F GHI J KLMNOP QRS TUVWXYZ 频率密文字母频率 频率统计分析破解密码实例(2) 猜测P Z可能是e和t； 统计字母
5、的相对频率-双字母 猜测ZW可能是th，因此ZWP可能是the 经过反复猜测、分析和处理，明文： it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow 11 其他单表(mono-alphabetic) 替换加密-pigpen cipher 12 其他单表(mono-alphabetic) 替换加密-福尔摩斯破解跳舞人 13 Am here Ape Slaney Com
6、e Elsie Never Elsie prepare to meet thy god 泰坦尼克号悲剧 14 o天灾 冰山 o人祸 无线电首席不学无术 o摩斯电码: 电报编码 国际标准（1835-1999） o1908年之前海难求救电码: CQD o1909年SOS正式成为遇难信号求 救电码标准并开始使用 o1912年泰坦尼克号海难发生初期 仍发出过时的CQD o直到船快沉没时才由下级建议发出 SOS 摩斯电码 15 课堂挑战-http:/ 16 17 多表替换加密 18 多表替换加密经典方法: Vigenre(维基尼亚) cipher Plaintext: ATTACKATDAWN Key:
7、 LEMONLEMONLE Ciphertext: LXFOPVEFRNHR Ki=11,4,12,14,13,11,4,12, 14,13 1467,1508,1553 19 频率统计分析: Vigenre(维基尼亚) cipher 20 Vigenre Cipher: Unbreakable? Charles Babbage,1791-1871 (查理 斯.巴贝奇) In 1846 , Babbage breaked Vigenre cipher Part of Babbages difference engine http:/en.wikipedia.org/wiki/Charles_B
8、abbage 21 如果我们知道key的长度 o If the length of the keyword is 5, then we know that the 1st, 6th, 11th ,letters are encoded by the same row in the Polyalphabetic substitution, o This equals a mono-alphabetic cipher. Plaintext: ATTAC KATDA WNONE ATTAC K Key: LEMON LEMON LEMON LEMON Ciphertext: LXFOP VEFRN
9、HR . . . LXFOP 22 o Find repeated sequences, spaces in the ciphertext 那我们如何知道key的长度呢？ 中国的经典密码 藏头诗 23 24 经典密码 移位密码 CANY OUUN DERS TAND 输入方向 输出方向 明文：Can you understand codtaueanurnynsd 密文： 25 更多的移位 6 3 2 4 1 5 W E A R E D I S C O V E R E D F L E E A T O N C E Q K J E U WE ARE DISCOVERED. FLEE AT ONCE.
10、 EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE 26 第一次世界大战: 美国为什么参战? On the first of February, we intend to begin unrestricted submarine warfare. In spite of this, it is our intention to endeavor to keep the United States of America neutral. In the event of this not succeeding, we propose an alliance on the fo
11、llowing basis with Mexico: That we shall make war together and make peace together. We shall give generous financial support, and an understanding on our part that Mexico is to reconquer the lost territory in New Mexico, Texas, and Arizona. The details of settlement are left to you. You are instruct
12、ed to inform the President of Mexico of the above in the greatest confidence as soon as it is certain that there will be an outbreak of war with the United States and suggest that the President, on his own initiative, invite Japan to immediate adherence with this plan; at the same time, offer to med
13、iate between Japan and ourselves 解密的密码电报促使美国参战 1917年2月24日，美国驻英大使佩奇收到破获的齐默曼电报 ，电报称如果墨西哥对美国宣战，德国将协助把美国西南部还 给墨西哥，加上在之前德国使用无限制潜艇战，使美国多只船 只被击沉，于是美国以此为根据，在 该年4月6日向德国宣战。 27 28 一战中的德国密码： ADFGVX CIPHERS 第一步: 替换 29 一战中的德国密码： ADFGVX CIPHERS (2) Codes oArray: S256, K256; 8bits Registers: i, j ; Less than 100 li
14、nes C code Key- scheduling algorithm (KSA) PRGA 62 reuse the random sequence C1 XOR C2 = (P1 XOR R ) XOR (P2 XOR R) = P1 XOR P2 n If we know P1, then we can get P2 n Or, we can recover P1, P2 only from P1 XOR P2 o E. Dawson and L. Nielsen. Automated cryptanalysis of XOR plaintext strings. Cryptologi
15、a, (2):165181, Apr. 1996. 63 流加密最普遍的应用 WEP (Wired Equivalent Privacy) 64 WEP Frame 40bits 伪随机数 ，24 bits 65 WEP Encryption and Decryption IV: 24 bits, password 40bits 66 Attacks on WEP oKey size is not the only problem oKEYSTREAM REUSE nIV : 24 bits ，如果两次加密使用相同的IV，结果？ n两个Packet重用IV，Collision o需要多少Pac
16、kets ? 224 ？ oBirthday attack: n1% chance of collision after 582 encrypted frames; n10% after 1,881 n50% after 4,823; 99% after 12,430 n从监听数据中构造IV Dictionary o224 X 1500 B = 24+10+10 *1.5 KB=24G B o选择明文，比想象的容易 o How to Crack WEP? To be continued 现代密码技术 非对称加密 oRSA: 1977年由Ron Rivest, Adi Shamir, Lenar
17、d Adleman在MIT发明 n1973年英国Clifford Cocks更早发明，列为机密 o密钥生成算法 n两个素数p,q, N=p*q n选择一个整数e, 公钥(加密密钥)=(N, e) n私钥(解密密钥) = (N, d) , d：(d * e) 1 (mod (p-1)(q-1) ) o加密: n加密成c o解密: c解密到n 67 RSA的数学基础与破解 o 可计算性的数学基础 大整数因数分解难题 n给定N（大整数），求解p, q不可能 o 成立吗？ - 曾经成立 o 现在呢？（分布式计算、量子计算） n1999年，RSA-155（512 bits）被成功分解，花了五个 月时间（
18、约8000 MIPS 年） n2002年，RSA-158也被成功因数分解。 n2009年，RSA-768 （768 bits, 232 digits）数也被成 功分解 o RSA被破解了吗? n 只能说1024bit已存在破解风险 68 69 Lessons we should learned o From Caser to Vigenere, from Enigma to RC4 nThe attack and defense never stopped nCritical thinking o The development of cryptography technologies is
19、a process of evolution n图灵、雷杰夫斯基、RSA等天才也是站在前人肩膀上 o Advanced cryptography is based on the attacking of old technologies n证伪：并非证明技术无效，而是找出它有效的边界 n对密码技术不懈的攻击，导致密码算法越来越安全 n如果不允许密码算法的破解会怎样？ o 加密体制的安全不能建立在算法保密的基础上 n算法开放，密钥保密 n密钥的管理通常加密体制中最薄弱的环节？ 等待挖掘的密码宝藏 o 1885年美国一位神秘人物出版 的小册子 o 毕尔宝藏(Beale Treasure) n大批黄
20、金埋藏在Virginia 州某处 n将藏宝秘密加密后写在三页纸上 n寄存在旅馆，后来此人失踪了 o 破解密码与寻宝热 n吸引许多专家，仍在尝试 70 毕尔宝藏(Beale Treasure)的三页密码 71 第二页已经被神秘人物破解 o 第二页：宝藏内容 n第一页：藏宝地点 n第三页：藏宝人的伙伴与亲人名单 o 第二页如何被破解？（Book cipher） n美国独立宣言 72 I HAVE DEPOSITED IN THE COUNTY OF BEDFORD ABOUT FOUR MILES FROM BUFORDS IN AN EXCAVATION OR VAULT SIX FEET BE
21、LOW THE SURFACE OF THE GROUND THE FIRST DEPOSIT CONSISTED OF TEN HUNDRED AND FOURTEEN POUNDS (1014 lbs.) OF GOLD AND THIRTY EIGHT HUNDRED AND TWELVE POUNDS (3812 lbs.) OF SILVER, DEPOSITED NOV. EIGHTEEN NINETEEN.(NOV.1819) THE SECOND WAS MADE DEC. EIGHTEEN TWENTY- ONE (DEC 1821) AND CONSISTED OF NINETEEN HUNDRED AND SEVEN POUNDS (1907lbs.) OF GOLD AND TWELVE HUNDRED AND EIGHTY EIGHT (1208 lbs.)OF SILVER; ALSO JEWELS OBTAINED IN ST. LOUIS IN EXCHANGE TO SAVE TRANSPORTATION, AND VALUED AT THIRTEEN THOUSAND DOLLARS ($13,000) HASH算法 o MD5 o SHA 73