密码的加密与解密

密码的加密与解密（一）引言（二）置换密码（三）仿射变换密码（四）Hill密码（五）公开密钥系统（一）引言随着社会的信息化，通信技术迅速发展，信息高速公路的建立，使网络安全问题受到重视。当网络中从计算机到计算机传输的财务报告、医疗记录以及其他敏感的信息很容易被截取破译时，有关信息安全以及保障隐私权的担心也就与日俱增。信息的发送方为了保护自己的信息不被敌方轻易破解，通常会先将信息进行加密，形成一堆普通人无法看懂的乱码，然后再发送出去；而接收方接到加密信息后，则对其进行解密，还原出原始信息，从而既完成信息的传递，又达到保密的目的。 事实上，密码作为军事和政治斗争中的一种技术，古已有之，自从人类有了战争，也就产生了密码。如何使敌人无法破译密文而又能使盟友容易译出密文，一直是外交官和军事首脑关心的重要问题。近三四十年来，随着计算机科学的蓬勃发展，数据安全作为一个新的分支已活跃在计算机科学领域，各种加密方法如雨后春笋般的出现，20世纪70年代后半期出现的数据加密标准和公开密钥系统就是其中两种重要的加密方法。密码学涉及的数学理论数论信息论概率统计代数几何中的椭圆曲线明文加密密钥加密密文公共信道解密原始明文破译密码解密密钥如果甲方要通过公共信道向乙方传送信息（message），为了保护信息不被第三方窃取和篡改，在发送信息之前需要把它变成秘密的形式，将要传送的原始信息称为明文（plaintext），而将在公共信道中传递的明文的秘密形式成为密文（ciphertext）。用某种方法把明文变成密文的过程称为加密（encryption），利用密码把密文还原为明文的过程称为解密（decryption），密码中的关键信息称为密钥。显然，密钥在保密通信中占有极其重要的地位，通常由通信双方秘密商定。初等数论基础知识性质1：同余是一种等价关系，即性质2同余式可以相加，即若有则性质3

同余式可以相乘，即若（1）成立，则（1）性质4

同余式等价于特别的，当（2）(mod7)a123456a-1145236例a15711a-1(mod12)15711a123456789101112(mod13)a-1179108112534612定义2

同余式(二)置换密码

将每个字母由某个其他的字母来替换，替换的规律可以是随机的，也可以是系统的，总共有26！种可能的密码。

古罗马伟大的军事家和政治家凯撒大帝在公元前50世纪使用的凯撒密码就是一个典型的系统置换密码。

凯撒密码就是把明文中的每个字母用按顺序后移3位之后的字母来表示形成密文，即A→DB→E….W→ZX→AY→BZ→C这个密码可以用数学模型描述：Step1：将26个字母与整数0~25建立一一对应关系ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425Step2:建立数学模型例：MATHEMATICALMODELING用凯撒密码表示出来就是ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425PDWKHPDWLFDOPRGHOLQJ为了迷惑敌人，密文通常都写成5个字母一组的形式，PDWKHPDWLFDOPRGHOLQJ显然在凯撒密码中，整数3就是密钥，如果要对一个用凯撒密码加密的密文进行解密，只要对p求解同余式称由下面公式给出的密码为移位置换密码对于移位置换密码来说，破译的关键在于如何确定移位因子k的数值。如何确定移位因子k？方法一：穷举法对k从1到m-1分别计算直到出现有明确意义的明文为止。缺点：这种方法仅对移位置换密码有效，如果是随机置换密码，此方法就会失效，因为枚举次数将达到m!方法二：字母频率法书面语言的一个重要特征是单个字母不是以同样的频率出现的。在英文常用文章中，平均说来，字母“E”出现的频率最高，可以占到所有字母的13%，其次是字母“T”，大致可占所有字母的10%左右，而字母“Z”出现的频率远远小于1%。英文字母出现频率分布表ABCDEFG0.08560.01390.02790.03780.13040.02890.0199HIJKLMN0.05280.06270.00130.00420.03390.02490.0707OPQRSTU0.07970.01990.00120.06770.00070.10450.0249VWXYZ0.00920.01490.00170.01990.0008例：已知下面的密文是用移位置换密码编写的，试破译该密文UQJFXJLTYTYMJBTWQIYWFIJHJSYJWYTFYYJSIYMJSLFYYMWJJURSJCYBJISJXIFD容易看出，其中出现频率最高的字母是J，将其与字母“E”相对应，这样可求出k=5,于是破译出相应的有明确意义的明文为ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425PLEASEGOTOTHEWORLDTRADECENTERTOATTENDTHEMEETINGATTHREEPMNEXTWEDNESDAY即PLEASEGOTOTHEWORLDTRADECENTERTOATTENDTHEMEETINGATTHREEPMNEXTWEDNESDAY请在下周三下午3点到世界贸易中心参加会议（三）仿射变换密码数学模型其中自然数a必须与模m互素仿射变换的解密公式可以通过求解（1）得到（1）（2）式两边同时乘以a-1,即得（2）

在移位置换密码下，明文中相邻的字母对应的密文字母也是相邻的，而对于仿射变换密码来说，明文中相邻的字母对应的密文字母分别为D和E，但在仿射变换对应的密文字母分别为F和I，它们之间有3个字母的间隔（a=3）例：假设下面的密文是使用仿射变换加密的，试破译此段密文FSFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHK

FSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS对于这个问题，假设明文是由26个英文字母组成的，可取m=26,由于a与26互素，于是a的数值有12种可能取法35791113151719212325b有26种不同的取法，所以仿射变换总有种可能变化如果采用穷举法破译这段密码，就要进行312次尝试。当字符系统更为复杂时，如考虑标点符号和数字等，需要枚举的次数将会大为增加，因此采用其他更为有效的破译方法是需要的。计算密文中各字母出现的频率，FSFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHK

FSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS发现“F”出现12次，“R”出现11次，“S”出现9次，“K”出现8次，其他字母出现的次数较少，使用字母频率法。假设1：密文中出现频率最高的字母对应于英文中最常见的字母，“F”对应“E”，“R”对应“T”，得到如下两个同余式两式相减，可得因为15关于26的同余逆为7但是a=6与26不是互素的，无法对密文进行解密假设2用“R”对应“E”，“S”对应“T”，得到另外两个同余式（1）-（2）得得加密公式解密公式利用解密公式解密得到（1）（2）代入（1）得GTGAERCSGTKESREDGQETDICHHAEEDGTGXQJGTCKDGTAMHECTDJESMXXEEZGRGDDJWRKLGUGXDERTMMT这是一串没有意义的文字，解密失败假设3：令“R”对应“E”，“K”对应“T”，可得同余式(1)-(2)，得于是得到一个加密公式关于p求解这个方程就可以求得解密公式（1）（2）带入（1）得最后利用解密公式得破译后的明文为ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEIHTHECOFFEEBARATTHURSDAYAFTERNOON即ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON周四下午一个美国特工将在咖啡馆与一位阿富汗间谍接头（四）Hill密码

前面介绍了如何破译置换密码，即使是在字母的置换是随机的情况下，仍然可以利用字母出现的频率，同时考虑字母组合出现的频率进行解密，从而达到破译密码的目的。究其原因，问题出在明文中给定的字母在密文中总是用同一个字母来表示。这样明文中文字的所有性质都会在密文中体现出来，可以利用这些性质对密文进行解密。为了防止利用字母频率解密，可以采用下面的加密方式，每次加密一组字母而不是加密单个字母。把n个明文字母组成一组，用n个密文字母来代替，这种加密方法称为Hilln密码。Hill密码是密文中字母出现的频率变得不规则起来，也就是说它将使明文中同一个字母在密文中大量的表示方式，从而彻底改变明文中的文字性质。例：设明文为MEET，采用Hill2密码对其进行加密，即对每两个字母一组进行加密。假设加密矩阵为求这段明文的Hill2密文将明文分为两组MEET由此构造出两个二维列向量在上述两个向量的左边乘以矩阵A，得到两个新的列向量再对这两个列向量关于模26作余运算，得于是对应的密文为UUQR注意：明文中的一个字母“E”在密文中分别用两个不同字母“U”和“Q”表示，而密文中的同一个字母“U”则对应不同的明文字母“M”和“E”。由此明文中字母出现的频率就被完全打乱了，从而使破译变得困难起来Hilln密码加密过程S1：选择一个n阶可逆整数方阵A作为加密矩阵，它是这个加密系统的密钥S2:将明文字符按顺序进行分组，每n个字符一组，若最后一组不足n个字符，则补充一些没有实际意义的虚设字符，使每一组都由n个字符组成S3：将每个明文字符对应于一个整数，构成一组n维列向量aS4：用加密矩阵A左乘每一个列向量a，得到新的n维列向量S5：对β的每个分量关