§42密码的设计,解码与破译」心 密码的设计和使用至少可从追溯到四千多年前的埃及,巴 比伦、罗马和希腊,历史极为久远。古代隐藏信息的方法 主要有两大类: 其一为隐藏信息载体,采用隐写术等; 其二为变换信息载体,使之无法为一般人所理解。 在密码学中,信息代码被称为密码,加密 前的信息被称为明文,经加密后不为常人 所理解的用密码表示的信息被称为密文 ciphertext),将明文转变成密文的过程被 称为加密( enciphering),其逆过程则被称 为解密( deciphering),而用以加密、解密 的方法或算法则被称为密码体制 crytosystem)
§4.2 密码的设计,解码与破译 密码的设计和使用至少可从追溯到四千多年前的埃及 ,巴 比伦、罗马和希腊,历史极为久远 。古代隐藏信息的方法 主要有两大类: 其一为隐藏信息载体,采用隐写术 等; 其二为变换信息载体,使之无法为一般人所理解 。 在密码学中,信息代码被称为 密码,加密 前的信息被称为 明文,经加密后不为常人 所理解的用密码表示的信息被称为 密文 (ciphertext),将明文转变成密文的过程被 称为加密(enciphering),其逆过程则被称 为解密(deciphering),而用以加密、解密 的方法或算法则被称为 密码体制 (crytosystem)
记全体明文组成的集合为U,全体密文组成的集合为V,称U 为明文空间,V为密文空间。加密常利用某一被称为密钥的东 西来实现,它通常取自于一个被称为密钥空间的含有若干参 数的集合K。按数学的观点来看,加密与解密均可被看成是 种变换:取一k∈K,∨u∈U,令u V∈V,v为明 文u在密钥K下的密文,而解码则要用到K的逆变换K1,。由 此可见,密码体系虽然可以千姿百态,但其关键还在于密钥 的选取。 随着计算机与网络技术的迅猛发展,大量各具特色的密码体 系不断涌现。离散数学、数论、计算复杂性、混沌 许多相当高深的数学知识都被用上,逐步形成了(并仍在迅 速发展的)具有广泛应用面的现代密码学
记全体明文组成的集合 为U,全体密文组成的集合 为V,称U 为明文空间,V为密文空间。加密常利用某一被称为密钥的东 西来实现,它通常取自于一个被称为密钥空间的含有若干参 数的集合K。按数学的观点来看,加密与解密均可被看成是一 种变换:取一k∈K, u∈U,令 ,v为明 文u在密钥K下的密文,而解码则要用 到K的逆变换K-1,。由 此可见,密码体系虽然可以千姿百态,但其关键还在 于密钥 的选取。 u v V k ⎯→ 随着计算机与网络技术的迅猛发展,大量各具特色的密码体 系不断涌现。离散数学、数论、计算复杂性、混沌、……, 许多相当高深的数学知识都被用上,逐步形成了(并仍在迅 速发展的)具有广泛应用面的 现代密码学
早期蜜码 >替代密码 移位密码 >代数密码
早期密码 替代密码 移位密码 代数密码
1代替法密码 代替法密码采用另一个字母表中的字母来代替明文中的字母, 明文字母与密文字母保持一一对应关系,但采用的符号改变 了。加密时,把明文换成密文,即将明文中的字母用密文字 母表中对应位置上的字母取代。解密时,则把密文换成明文, 即把密文中的字母用明文字母表中对应位置上的字母代回, 解密过程是加密过程的逆过程。在代替法加密过程中,密文 字母表即代替法密钥,密钥可以是标准字母表,也可以是任 意建立的 明文字母表 ABCDEFGHIJKLMNOPQRSTUVXYZ 密文字母表 KLMNOPQRSTUVXYZABCDEFGHIJ 密钥常用一密钥单词或密钥短语生成混淆字母表。密钥单词 或密钥短语可以存放在识别码、通行字或密钥的秘密表格中
代替法密码采用另一个字母表中的字母来代替明文中的字母, 明文字母与密文字母保持一一对应关系,但采用的符号改变 了。加密时,把明文换成密文,即将明文中的字母用密文字 母表中对应位置上的字母取代。解密时,则把密文换成明文, 即把密文中的字母用明文字母表中对应位置上的字母代回, 解密过程是加密过程的逆过程。在代替法加密过程中,密文 字母表即代替法密钥,密钥可以是标准字母表,也可以是任 意建立的。 1.代替法密码 明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJ 密钥常用一密钥单词或密钥短语生成混淆字母表。密钥单词 或密钥短语可以存放在识别码、通行字或密钥的秘密表格中
混合一个字母表,常见的有两种方法,这两种方法都采用 了一个密钥单词或一个密钥短语。 方法1: 日选择一个密钥单词或密钥短语,例如: construct b)去掉其中重复的字母,得: constru c在修改后的密钥后面接上从标准字母表中去掉密钥中已有 的字母后剩下的字母,得: 明文字母表 ABC DEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 CONSTRUABDEFGHIJKLMPQWXYZ 在设计密钥时,也可在明文字母表中选择一个特定字母,然 后从该特定字母开始写密钥单词将密钥单词隐藏于其中。例 如,对于上例,选取特定字母k,则可得: 明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 KLMPQWXYZCONSTRUABDEFGHIJ
混合一个字母表,常见的有两种方法,这两种方法都采用 了一个密钥单词或一个密钥短语。 方法1: a)选择一个密钥单词或密钥短语,例如:construct b)去掉其中重复的字母,得:constru c)在修改后的密钥后面接上从标准字母表中去掉密钥中已有 的字母后剩下的字母,得: 明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZ 在设计密钥时,也可在明文字母表中选择一个特定字母,然 后从该特定字母开始写密钥单词将密钥单词隐藏于其中。例 如,对于上例,选取特定字 母 k,则可得: 明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ
方法2 a)选择一个密钥单词或密钥短语,例如: construct b)去掉其中重复的字母,得: constru c)这些字母构成矩阵的第一行,矩阵的后续各行由标准字母 表中去掉密钥单词的字母后剩下的字母构成 d将所得矩阵中的字母按列的顺序排出 得: cugmyoahn takwrflx 按照此方法产为增加保密性,在使用表 还可以使用混汐代替法时还可利用一些 a选一密钥单 其他技巧,如单字母表 的按照这些字母对多字母表、单字母对它们编号, 对序中复的多字母、多重代替等。 instruct 143675928 c 方选出这些数字得到一个混淆数字组:143675928, 从小到大的顺序取矩阵中相应列得出
方法2: a)选择一个密钥单词或密钥短语,例如: construct b)去掉其中重复的字母,得:constru c)这些字母构成矩阵的第一行,矩阵的后续各行由标准字母 表中去掉密钥单词的字母后剩下的字母构成 d)将所得矩阵中的字母按列的顺序排出 得: cugmyoahpznbiqsdjvrtekwrflx 按照此方法产生的字母表称为 混淆字母表。 还可以使用混淆数。混淆数由以下方法产生: a)选一密钥单词或密钥短语,例如:construct b)按照这些字母在标准字母表中出现的相对顺序给它们编号, 对序列中重复的字母则自左向右编号,得 :construct 143675928 c)自左向右选出这些数 字,得到一个混淆数字 组:143675928, 混淆字母表由从小到大的顺序取矩阵中相应列得出。 为增加保密性,在使用 代替法时还可利用一些 其他技巧,如单字母表 对多字母表、单字母对 多字母、多重代替等
2移位密码体制 移位密码采用移位法进行加密,明文中的字母重新排列,本 身不变,只是位置改变了。 种移位法采用梅字母表中的字母平移若干位的方法来构陆 好李4莢齄闺撒最草徙咱械 域迷柳密逍早母表被羯展母舶草舞弹御呼衾向 才确定的抄来构遭呼球布件排上,当取下纸带 时,宝量的次序就被打乱 息时,要骚纸带菲 的员 到正通的消息 的直径起到 的作 以上两种移位较易被人破译,为打破字母表中原有的顺序还可 采用所谓路线加密法,即把明文字母表按某种既定的顺序安排 在一个矩阵中,然后用另一种顺序选出矩阵中的字母来产生密 文表
2.移位密码体制 移位密码采用移位法进行加密,明文中的字母重新排列,本 身不变,只是位置改变了。 早在4000多年前,古希腊人就用一种名 叫“天书”的器械 来加密消息。该密码器械是用一条窄长的草纸缠绕在一个 直径确定的圆筒上,明文逐行横写在纸带上,当取下纸带 时,字母的次序就被打乱了,消息得以隐蔽。收方阅读消 息时,要将纸带重新绕在直径与原来相同的圆筒上,才能 看到正确的消息。在这里圆筒的直径起到了密钥的作用。 另一种移位 法采用将字母表中的字母平移若干位的方法来构造 密文字母表,传说这类方法是由古罗马皇帝凯撒最早使用的, 故这种密文字母表被称为凯撒字母表。例如,如用将字母表向 右平移3位的方法来构造密文字母表,可 得: 明文字母表: ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表: DEFGHIJKLMNOPQRTSUVWXYZABC 因此 “THANK YOU” “WKDQN BRX” 以上两种移位较易被人破译,为打破字母表中原有的顺序还可 采用所谓路线加密法,即把明文字母表按某种既定的顺序安排 在一个矩阵中,然后用另一种顺序选出矩阵中的字母来产生密 文表
例如,对明文: THEHSTORY OF ZJU| S MORE THAN ONE HUNDRED YEARS以7列矩阵表示如下: THEHIST ORYOFZJ UISMORE THANONE HUNDRED YEARS 再按事先约定的方式选出密文。例如,如按列选出,得到 MXX: touthyhrihueeysanahomndrifoorsszrnetjeed 攤來超鱖矩编莺和琎择可协县耦到獅种不閏的蕗 獅黼数劝手阉阵塽夾晡息短嵥在椠陪朿岡锕铔蛛 式用簿窬「蓉塘瀘矩阵同的
例如,对明文:THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以7列矩阵表示如下: THEHIST ORYOFZJ UISMORE THANONE HUNDRED YEARS 再按事先约定的方式选出密文。例如,如按列选出,得到 密文:touthyhrihueeysanahomndrifoorsszrnetjeed 使用不同的顺序进行编写和选择,可以得到各种不同的路 线加密体制。对于同一明文消息矩阵,采用不同的抄写方 式,得到的密文也是不同的。 当明文超过规定矩阵的大小时,可以另加一矩阵。当需要 加密的字母数小于矩阵大小时,可以在矩阵中留空位或以 无用的字母来填满矩阵
移位法也可和代替法结合使用,并使用约定的单词或短语作 密钥,以进一步加强保密性,这就是钥控列序加密法。 例如,用密钥单词 construct对明文 MATHEMATICAL MODELING IS USEFUL加密: CONSTRUCT 143675928 MATHEMATI CALMODELI NGISUSEFU 按混淆数的顺序选出各列,得到密文: MCNLTLFTLIAAGMDSHMSEOSIUAEE 移位法的使用可重复多次,只进行一次移位加密的称为 次移位法,经多次移位的则称为多次移位法
移位法也可和代替法结合使用,并使用约定的单词或短语作 密钥,以进一步加强保密性,这就 是钥控列序加密 法。 例如,用密钥单词 construct对明文MATHEMATICAL MODELING IS USEFUL加密: CONSTRUCT 1 4 3 675 9 28 MATHEMATI CALMODELI NGISUSEFU L 按混淆数的顺序选出各列,得到密文: MCNLTLFTLIAAGMDSHMSEOSIIUAEE 移位法的使用可重复多次,只进行一次移位加密的称为一 次移位法,经多次移位的则称 为多次移位法
代替法与移位法密码的破译 对窃听到的密文进行分析时,穷举法和统计法是最基本的 破译方法。 穷举分析法就是对所有可能的密钥或明文进行逐一试探, 直至试探到“正确”的为止。此方法需要事先知道密码体 制或加密算法(但不知道密钥或加密具体办法)。破译时 需将猜测到的明文和选定的密钥输入给算法,产生密文, 再将该密文与窃听来的密文比较。如果相同,则认为该密 钥就是所要求的,否则继续试探,直至破译。以英文字母 为例,当已知对方在采用代替法加密时,如果使用穷举字 母表来破译,那么对于最简单的一种使用单字母表一单字 母一单元代替法加密的密码,字母表的可能情况有26!种 可见,单纯地使用穷举法,在实际应用中几乎是行不通的, 只能与其它方法结合使用
代替法与移位法密码 的破译 对窃听到的密文进行分析时 ,穷举法和统计法是最基本的 破译方法 。 穷举分析法 就是对所有可能的密钥或明文进行逐一试探, 直至试探到“正确”的为止。此 方法需要事先知道密码体 制或加密算法(但不知道密钥或加密具体办法)。破译时 需将猜测到的明文和选定的密钥输入给算法,产生密文, 再将该密文与窃听来的密文比较。如果相同,则认为该密 钥就是所要求的,否则继续试探,直至破译。以英文字母 为例,当已知对方在采用代替法加密时,如果使用穷举字 母表来破译,那么对于最简单的一种使用单字母表-单字 母-单元代替法加密的密码,字母表的可能情况 有26!种, 可见,单纯地使用穷举法,在实际应用中几乎是行不通的, 只能与其它方法结合使用