上海交大密码学课件-第三讲古典替换密码.ppt

第三讲古典替换密码Classicalsubstitutionciphers 上海交通大学dzheng Tel 021 34207015zhengdong 1 古典加密技术 两个基本组成部分 替换与置换 substitutionandtransposition 2 恺撒密码CaesarCipher Caesar密码的数学表示设 Athevalue0 B1 C2 Y24 Z25 加密算法 Ek i i k mod26 解密算法 Dk i i k mod26 3 密码分析 CryptanalysisofCaesarciphers 只有26种可能 onlyhave26possibleciphers AmapstoA B Z可以简单的实验每个密钥 穷密钥搜索 给定一些密文 实验每个密钥 LIZHZLVKWRUHSODFHOHWWHUVOriginalciphertextKHYGYKUJVQTGRNCEGNGVVGTUtryshiftof1JGXFXJTIUPSFQMBDFMFUUFSTtryshiftof2IFWEWISHTOREPLACELETTERStryshiftof3 plaintextHEVDVHRGSNQDOKZBDKDSSDQRtryshiftof4GDUCUGQFRMPCNJYACJCRRCPQtryshiftof5 MJAIAMWLXSVITPEGIPIXXIVWtryshiftof25eg breakciphertext GCUAVQDTGCM 4 语言冗余度与密码分析 人类语言是有冗余度的字母使用的频率是不相同的在英语中 e的使用率是最高的其次 T R N I O A S其它字母使用的较低 5 英语字母使用频率 6 字母频率在密码分析中的应用 计算密文中字母出现的频率与已知字母分布比较单码替换不改变相对字母出现的频率阿拉伯科学家提出此方法 7 英语字母中常见的组合 8 打乱的密码代换 不仅仅是简单的移位变换每个字母可以避免随意变换到其它不重复的字母每个字母变换到不同的字母密钥长度是26个字母eg Plain ABCDEFGHIJKLMNOPQRSTUVWXYZCipher DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext IFWEWISHTOREPLACELETTERSCiphertext WIRFRWAJUHYFTSDVFSFUUFYA 9 打乱的密码代换的安全性 密钥总数 26 如此多的密钥 可以认为安全吗 NO 仍然有语言统计规律需要其它方法隐藏这种规律性 10 一般单码替换密码 简单的方法给出密钥写出密钥 删除重复字母 writekey withrepeatedlettersdeleted 在其下面依次写出剩余字母 以横 纵行 按列读取字母得到密文 thenreadoffbycolumnstogetciphertextequivalents 11 一般单码替换密码举例 给定密钥字 STARWARS 去掉重复字母得到 STARW 填写剩余字母 STARWBCDEFGHIJKLMNOPQUVXYZ按列读取字母得到密文Plain ABCDEFGHIJKLMNOPQRSTUVWXYZCipher SBGLQZTCHMUADINVREJOXWFKPY可以用这个密钥加密 解密例如Plaintext IKNOWONLYTHATIKNOWNOTHINGCiphertext HUINFNIAPOCSOHUINFINOCHIT 12 一般单码替换密码的密码分析 根据频率统计进行分析确定每个字母被映射到什么字母如果知道单词之间的间隙知道 则破译会很容易 单个字母出现的可能是A或I一般来说个字母出现的可能是THE或AND还可以用其他通常出现的双字母或三字母组合 还可以应用其它很少应用的字母 12 一般单码替换密码的密码分析 续 甚至能够恢复出关键字关键字总是使得其它字母连续出现分析密钥排列的 宽度 eg intheaboveexample ifhaverecoveredthemapping Plain ABCDEFGHIJKLMNOPQRSTUVWXYZCipher SBGLQZTCHMUADINVREJOXWFKPY seepattern BCDEF and LMNOP 你能够重新构造替换表 并恢复出keyword STARW 13 信息论与熵 C E Shannon 香农 1948 Amathematicaltheoryofcommunication 确立了现代信息论 1949 Communicationtheoryofsecrecysystems 定义了密码系统的精确数学模型 13 2熵entropy 熵 Entropy 定义为事件集X中事件出现的信息的统计平均值它表示X中出现一个事件平均给出的信息量 或事件的平均不确定性 Exercises encryptandthendecryptbyhand thetextbelowusingageneralmonoalphabeticcipherwithakeyof NIFTY thecatonlygrinnedwhenitsawaliceitl