密码的加密与解密.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,返回,（一）引言,随着社会的信息化，通信技术迅速发展，信息高速公路的建立，使网络安全问题受到重视。当网络中从计算机到计算机传输的财务报告、医疗记录以及其他敏感的信息很容易被截取破译时，有关信息安全以及保障隐私权的担心也就与日俱增。信息的发送方为了保护自己的信息不被敌方轻易破解，通常会先将信息进行加密，形成一堆普通人无法看懂的乱码，然后再发送出去；而接收方接到加密信息后，则对其进行解密，还原出原始信息，从而既完成信息的传递，又达到保密的目的。,事实上，密码作为军事和政治斗争中的一种技术，古已有之，自从人类有了战争，也就产生了密码。如何使敌人无法破译密文而又能使盟友容易译出密文，一直是外交官和军事首脑关心的重要问题。近三四十年来，随着计算机科学的蓬勃发展，数据安全作为一个新的分支已活跃在计算机科学领域，各种加密方法如雨后春笋般的出现，20世纪70年代后半期出现的数据加密标准和公开密钥系统就是其中两种重要的加密方法。,密码学涉及的数学理论,数论,信息论,概率统计,代数几何中的椭圆曲线,性质2,同余式可以相加，即若有,则,性质3,同余式可以相乘，即若（1）成立，则,（1）,性质4,同余式,等价于,特别的，当,（2）,(mod7),a 1 2 3 4 5 6,a,-1,1,4,5,2,3,6,例,a 1 5 7 11,a,-1,(mod12),1,5,7,11,a 1 2 3 4 5 6 7 8 9 10 11 12,(mod13),a,-1,1,7,9,10,8,11,2,5,3,4,6,12,定义2,同余式,(二)置换密码,将每个字母由某个其他的字母来替换，替换的规律可以是随机的，也可以是系统的，总共有26！种可能的密码。,古罗马伟大的军事家和政治家凯撒大帝在公元前50世纪使用的凯撒密码就是一个典型的系统置换密码。,凯撒密码就是把明文中的每个字母用按顺序后移3位之后的字母来表示形成密文，即,AD,BE,.,WZ,XA,YB,ZC,这个密码可以用数学模型描述：,Step1：将26个字母与整数025建立一一对应关系,A B C D E F G H I J K L M,0 1 2 3 4 5 6 7 8 9 10 11 12,N O P Q R S T U V W X Y Z,13 14 15 16 17 18 19 20 21 22 23 24 25,Step2:建立数学模型,例：MATHEMATICAL MODELING用凯撒密码表示出来就是,A B C D E F G H I J K L M,0 1 2 3 4 5 6 7 8 9 10 11 12,N O P Q R S T U V W X Y Z,13 14 15 16 17 18 19 20 21 22 23 24 25,PDWKHPDWLFDO PRGHOLQJ,为了迷惑敌人，密文通常都写成5个字母一组的形式，,PDWKH PDWLF DOPRG HOLQJ,显然在凯撒密码中，整数3就是,密钥,，,如果要对一个用凯撒密码加密的密文进行解密，只要对p求解同余式,称由下面公式给出的密码为移位置换密码,对于移位置换密码来说，破译的关键在于如何确定移位因子k的数值。,如何确定移位因子k？,方法一：穷举法,对k从1到m-1分别计算,直到出现有明确意义的明文为止。,缺点：,这种方法仅对,移位,置换密码有效，如果是,随机,置换密码，此方法就会失效，因为枚举次数将达到m!,方法二：字母频率法,书面语言的一个重要特征是单个字母不是以同样的频率出现的。在英文常用文章中，平均说来，字母“E”出现的频率最高，可以占到所有字母的13%，其次是字母“T”，大致可占所有字母的10%左右，而字母“Z”出现的频率远远小于1%。,英文字母出现频率分布表,A B C D E F G,0.0856 0.0139 0.0279 0.0378 0.1304 0.0289 0.0199,H I J K L M N,0.0528 0.0627 0.0013 0.0042 0.0339 0.0249 0.0707,O P Q R S T U,0.0797 0.0199 0.0012 0.0677 0.0007 0.1045 0.0249,V W X Y Z,0.0092 0.0149 0.0017 0.0199 0.0008,例：已知下面的密文是用,移位置换,密码编写的，试破译该密文,UQJFX JLTYT YMJBT WQIYW FIJHJ,SYJWY TFYYJ SIYMJ SLFYY MWJJU,RSJCY BJISJ XIFD,容易看出，其中出现频率最高的字母是J，将其与字母“E”相对应，这样可求出k=5,于是破译出相应的有明确意义的明文为,A B C D E F G H I J K L M,0 1 2 3 4 5 6 7 8 9 10 11 12,N O P Q R S T U V W X Y Z,13 14 15 16 17 18 19 20 21 22 23 24 25,PLEAS EGOTO THEWO RLDTR ADECE,NTERT OATTE NDTHE MEETI NGATT,HREEP MNEXT WEDNE SDAY,即PLEASE GO TO THE WORLD TRADE CENTER TO ATTEND THE MEETING AT THREE PM NEXT WEDNESDAY,请在下周三下午3点到世界贸易中心参加会议,（三）仿射变换密码,数学模型,其中自然数a必须与模m互素,仿射变换的解密公式可以通过求解（1）得到,（1）,（2）式两边同时乘以a,-1,即得,（2）,在移位置换密码下明文中相邻的字母对应的密文字母也是相邻的，而对于仿射变换密码来说，明文中相邻的字母对应的密文字母分别为D和E，但在仿射变换,对应的密文字母分别为F和I，它们之间有3个字母的间隔（a=3）,例：假设下面的密文是使用,仿射变换,加密的，试破译此段密文,FSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHK,FSPVM RDSKA RLVUU RRIFE FKKAN EHOFZ FUKRE SVVS,对于这个问题，假设明文是由26个英文字母组成的，可取m=26,由于a与26互素，于是a的数值有12种可能取法,3 5 7 9 11 13 15 17 19 21 23 25,b有26种不同的取法，所以仿射变换总有,种可能变化,如果采用穷举法破译这段密码，就要进行312次尝试。当字符系统更为复杂时，如考虑标点符号和数字等，需要枚举的次数将会大为增加，因此采用其他更为有效的破译方法是需要的。,计算密文中各字母出现的频率，,FSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHK,FSPVM RDSKA RLVUU RRIFE FKKAN EHOFZ FUKRE SVVS,发现“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）得,GTGAE RCSGT KESRE DGQET DICHH AEEDG TGXQJ GTCKD GTAMH ECTDJ ESMXX EEZGR GDDJW RKLGU GXDER TMMT,这是一串没有意义的文字，解密失败,假设3：,令“R”对应“E”，“K”对应“T”，可得同余式,(1)-(2)，得,于是得到一个加密公式,关于p求解这个方程就可以求得解密公式,（1）,（2）,带入（1）得,最后利用解密公式得破译后的明文为,ANAME RICAN SECRE TAGEN TWILL MEETA NAFGH ANIST ANMOL EIHTH ECOFF EEBAR ATTHU RSDAY AFTER NOON,即,AN AMERICAN SECRET AGENT WILL MEET AN AFGHANISTAN MOLE IN THE COFFEE BAR AT THURSDAY AFTERNOON,周四下午一个美国特工将在咖啡馆与一位阿富汗间谍接头,（四）Hill密码,前面介绍了如何破译置换密码，即使是在字母的置换是,随机,的情况下，仍然可以利用字母出现的频率，同时考虑字母组合出现的频率进行解密，从而达到破译密码的目的。,究其原因，问题出在明文中给定的字母在密文中总是用同一个字母来表示。这样明文中文字的所有性质都会在密文中体现出来，可以利用这些性质对密文进行解密。,为了防止利用,字母频率,解密，可以采用下面的加密方式，,每次加密一组字母而不是加密单个字母。把n个明文字母组成一组，用n个密文字母来代替，这种加密方法称为Hill,n,密码。,Hill密码是密文中字母出现的频率变得不规则起来，也就是说它将使明文中同一个字母在密文中大量的表示方式，从而彻底改变明文中的文字性质。,例：设明文为MEET，采用Hill,2,密码对其进行加密，即对每两个字母一组进行加密。假设加密矩阵为,求这段明文的Hill,2,密文,将明文分为两组ME ET,由此构造出两个二维列向量,在上述两个向量的左边乘以矩阵A，得到两个新的列向量,再对这两个列向量关于模26作余运算，得,于是对应的密文为UUQR,注意：明文中的一个字母“E”在密文中分别用两个不同字母“U”和“Q”表示，而密文中的同一个字母“U”则对应不同的明文字母“M”和“E”。由此明文中字母出现的频率就被完全打乱了，从而使破译变得困难起来,Hill,n,密码加密过程,S1,：选择一个n阶可逆整数方阵A作为加密矩阵，它是这个加密系统的,密钥,S2,:将明文字符按顺序进行分组，每n个字符一组，若最后一组不足n个字符，则补充一些没有实际意义的虚设字符，使每一组都由n个字符组成,S3,：将每个明文字符对应于一个整数，构成一组n维列向量a,S4,：用加密矩阵A左乘每一个列向量a，得到新的n维列向量,S5,：对,的每个分量关于模m取余运算,S6,：将,的n个分量分别对应于n个字符，即得密文信息,解密过程只需将上述过程反向进行即可,命题1,：元素属于Z,m,的方阵A模m可逆的充要条件是：m和detA没有公共的素数因子,推论1,：若方阵A的每个元素都属于Z,m,而且detA=1，则A是模m可逆的，且它的逆矩阵A,-1,(modm)就是A的模m逆矩阵,构造Hill加密矩阵的方法,设,于是，在模m意义下，方程组A,a=,(modm),的解为,在例题中，明文字母共26个，即m=26。由于26素数因子为2和13.所以Z,26,上方阵A可逆的充要条件为detA不能被2和13整除。现在,满足命题1条件，故A关于模26的逆为,于是对密文UUQR进行解密，得到,即明文为MEET,Hill密码的加密与解密过程类似于在n维向量空间中进行线性变换及其逆变换。每个明文向量是一个Zm上的n维向量，乘以加密矩阵并对m取余后，仍为Zm上的一个n维向量。由于加密矩阵A为模m的可逆矩阵，所以，如果知道了n个,线性无关,的n维明文向量与其对应的密文向量，就可以求出它的加密矩阵A及其模m的逆矩阵A,-1,(modm),例5假设截获一段密文,VOEMO LGFSF MTGFK SPWVO EMOLG,FEHDV BPKYG UZSRF MTCGX HCW,经分析，这段密文是由Hill2密码编写的，且EHDV分别表示DKIN.试破译这段密文,记加密矩阵为A，仍然假设字母AZ对应于数字025,则有,它们关于模26都是可逆的，所以a1,a2在模26的意义下线性无关，,1，2在模26的意义下也线性无关。,利用公式,这样可求得这段密文的明文为,THEUN ITEDS TATES ANDTH EUNIT EDKIN GDOMW ILLAT TACKI RAQ,即,THE UNITED STATES AND UNITED KINGDOM WILL ATTACK IRAQ,美国和英国将进攻伊拉克,（五）公开密钥系统,利用Hill密码对明文进行加密，明文中文字的特性被打乱，字母组合的信息也不复存在，使解密变得困难。但是这里还有一个的传递问题。,由于信息发送方和接收方共同使用同一个密钥，发送方使用某个密钥对将要发生的明文进行加密，而接收方使用同一个密钥对收到的密文进行解密。这样的系统称为,单,密钥系统。,在,单,密钥系统中，密钥必须保持秘密。又要被收发双方共同使用。那么收发双方如何传递这个密钥呢？此外，如果在一通讯系统中有一个联络站被间谍渗入或被敌方占领，则密码的机密可能全盘暴露。,解决这个问题的一个有效方法是使用,双,密钥系统，即在信息传递过程中，设置两个密钥，加密和解密分别使用两个不同的密钥。双密钥系统又称为公开密钥系统，密钥的拥有者将其中一个密钥公开，放入公开密钥词典中，而保持另一个密钥的私密性。这样，即使发方被捕，敌人仍榨不出解密码的机密来。,注意：在,双,密钥系统中，两个密钥是互逆的，任何一个都可以作为加密的密钥，而用另一个进行解密,双密钥系统的程序是这样的：,（S1）收发先告诉发方如何把情报制成密码（敌人也听到了这个做法）,（S2）发方依法发出情报的密码（敌人也听到了这个信号）,（S3）收方将密码还原成原始信息（但敌人却解不开此密码）,例如：A希望发送一个信息M给B，A首先在公开密钥的词典中查到B的公开密钥E,B,，A使用E,B,对M进行加密，得到密文C=E,B,（M），然后将C发送给B。B收到信息C后，使用他的私密密钥D,B,对C进行解密，即M=D,B,(C),注意到E,B,与D,B,是互逆的，因此,B将密文C还原为原来的明文信息M。由于解密密钥D,B,未曾公开，B是唯一知道这一密钥的人。这就决定了B是唯一可以对C进行解密的人，从而保证了信息发送的安全。由此可见，如果两个人加入了公开密钥系统，他们就可以在无须事先交换密钥的前提下进行保密性的通信，比以前收发双方都知道密钥的保密性高多了。,双密钥系统的思想最早是由迪费和海曼提出的。由于两个密钥中有一个是公开的，而另一个又与之互逆，因此这一系统实现的关键在于如何保证从已知的密钥计算出来未知密钥是无法做到的，至少是困难的。,公开密钥加密的第一个算法是由默克和海曼开发的背包算法，它的安全性由背包难题所保证，因为这是一个NP完全问题。不过很可惜，这个算法后来被发现是不安全的。,背包问题是计算机科学里的经典问题。在最简单的形式中，包括试图将不同重量的数据项放到背包中以使背包最后达到指定的总重量。不需要把所有的选项都放入背包中。举例来说，假设想要背包精确地承重20磅，并且有5个可以选择放入的数据项，它们的重量依次为11磅、8磅、7磅、6磅和5磅。对于选择放入的数据项数量不大时，人类很善于通过观察就可以解决这个问题。于是大概可以计算出只有8磅、7磅和5磅的数据项加在一起和为20磅。,背包算法出现后不久，李弗斯特、夏麦和阿特曼提出了第一个切实可行的方法实现了双密钥系统，这个方法称为RSA公开密钥系统。在已提出的公开密钥算法中，RSA系统是最容易理解和实现的。,RSA密码系统的基础是初等数论的有关理论,定义1,同余类（剩余类）：,全体整数可按对模m是否同余分为若干个两两不相交的集合，使得在同一个集合中的任意两个数对模m一定同余，而属于不同集合中的两个数对模m一定不同余。每一个这样的集合称为是模m的同余类，或模m的剩余类。以,表示r所属的模m的同余类,定义2,：设n为正整数，由模n的所有不同剩余组成的集合称为模n的完全剩余组。在模n的完全剩余组中，删除那些与模n不互素的剩余，剩下的便组成与模n互素的剩余组。与模n互素的剩余组的个数，称为欧拉（Euler）函数，记为,命题2,：若(a,b)=1,则,命题3,：若p为素数，则,证：,将这些同余式逐项相乘，得到,均与n互素，两边消去,即得证！,命题5（费马（Fermat）小定理）,：若p为素数，则对所有整数a成立,证：,由欧拉定理，,两边乘以a得（1）式,（1）,利用命题25可以得到RSA密码系统的建立步骤,S1,：随机选取两个,大素数,p，q（pq），计算n=pq,S2,:计算欧拉函数n),由命题2和命题3可知,(n)=(p-1)(q-1),S3,:任意选取一个正整数e作为公开的加密密钥，要求数e与欧拉函数,(n)互素，并且2,e,n,S4,:由数e求出解密密钥d，它是e关于模,(n)的同余逆，即它是同余方程,的解。由于e与,(n)互素,因此d总是存在的,命题2,：若(a,b)=1,则,命题3,：若p为素数，则,用RSA密码系统加密明文M过程,(1)将明文M数字化，如果M太大，可以将M分成若干块，通常要求Mn,(2)将编码后的数字作以下运算,即得密文C,（3）解密时，只要利用解密密钥d，对密文作相同的运算,即可还原出明文M,则由命题4可得,由命题2，有,命题2,：若(ab)=1,则,例：取p=11,q=19,计算可得n=pq=209,假设明文为CODE对它进行加密，将明文数字化为,M=02140304。这里的M太大，分成几组，使得每一组都小于n，于是M1=02,M2=14,M3=03,M4=04,于是加密后的密文为C=128174097082,加密,利用解密密钥d=13解密,使用RSA系统还可以对信息的真伪进行鉴别。由于加密密钥是公开的，任何人都可从公开密钥词典中得到这个密钥，因此敌方也可以利用这个密钥伪造信息，传递虚假消息。为了判别收到的消息是否真的是对方发送的，可以按以下过程来实现：,设发送发A发送消息M给B，B希望在收到信息的同时确认这个消息是否确实是A发送的。,（1）A首先使用它的解密密钥D,A,把M加密，得到D,A,（M）,（加密密钥与解密密钥是互逆，它们可以互换使用）,（2）用B的公开密钥把它加密，得到密文C=E,B,(D,A,(M),（3）A把密文C发送给B。,（4）当B收到密文C后，首先用自己的解密密钥D,B,去解密，得到,（5）使用A的公开密钥进行解密，得到结果,由于EA与DA是互逆的，B就恢复了明文信息,注意：最后一个步骤是检验信息是否由A发出，因为只有A拥有他自己的解密密钥,RSA密码系统中，整数对(e,n)是公开密钥，它们被载入公开密钥词典中，任何人都可以查询得到。而整数对,和素数p,q都是保密的，只有使用者知道它,对使用者来说，使用RSA密码系统进行加密和解密都是很容易的（当然要依赖计算机的帮助）,由于RSA系统使用的两个密钥是互逆的，而且其中一个密钥是公开的，那么窃密者能否通过公开密钥反解出解密密钥呢？,RSA系统加密、解密都是对一个充分大的数n做取余运算得到的，而n是由两个大素数p和q相乘得到的。因此如果某人不知道保密的密钥d，又希望把它找出来，他就需要知道p和q。直接解决的方法就是对n进行因式分解，得到两个素数因子。这样解密密钥d就可以由,通常素数p和q选取的相当大（100位或更大的十进制数），这样数n是一个至少有200位长的很大的整数。从计算上说进行因式分解要比区分素数与合数困难的多。使用计算机检验一个200位的整数是否是素数最多需要10min，然而要求对同样大小的一个合数进行因式分解所需要的计算时间是令人不敢想象的。可以做如下估计：使用当前已知的最快的因子分解的算法对一个200位的整数分解它的素数因子，大约需要做1.210,23,次计算机运算，假设每次运算需要10,-6,s,则因子分解的时间大约是3.810,9,年,