crypto

白洪欢[e-mail]本学期要学的《密码学》主要内容：数学基础、古典密码、MD5、DES、RSA、ECC编程工具:VC6()大数库:Openssl()官网为整除整除的定义:设a、b均为整数,且a≠0,若存在整数k使得b=a*k，则称a整除b，记作a|b。整除相关的3个命题:①对于任意整数a，都有1|a；若a≠0，则有a|0且a|a。②若a|b且b|c，则a|c。③若a|b且a|c，则a|(s*b+t*c)，其中s、t为任意整数。1.2素数与互素素数的定义:若整数p只有因子±1及±p,则称p为素数。互素(relativelyprime)的定义:对于整数a、b，若gcd(a,b)=1，则称a、b互素。a=3,b=5gcd(a,b)=1a=3,b=4gcd(a,b)=1a=4,b=9gcd(a,b)=1素数相关的定理:任一整数a(a0)都能唯一分解成以下形式:a=p1*p2*p3*...*pt其中p1、p2、p3、...、pt是素数。1.3最大公约数(greatestcommondivisor)gcd相关的定理:设a、b为整数，且a、b中至少有一个不等于0，令d=gcd(a,b)，则一定存在整数x、y使得下式成立:a*x+b*y=d特别地，当a、b素数时，则一定存在整数x、y使得a*x+b*y=1成立。(证明见P.93)1.4模(mod)运算和同余(congruent)同余的定义:设a、b、n均为整数，且n≠0，当a-b是n的倍数时即a=b+n*k(k为整数)，我们称a、b对于模n同余(aiscongruenttobmodn)，记作:a≡b(modn)可以理解为:a%n==b%n例如:1≡4mod3可以理解为:4%3=1例如:5≡8mod3同余相关的命题:设a,b,c,d,n均为整数，且n≠0，则有①当且仅当n|a时，有a≡0(modn)②a≡a(modn)③当且仅当b≡a(modn)时,有a≡b(modn)④若a≡b且b≡c(modn)，则一定有a≡c(modn)⑤若a≡b(modn)且c≡d(modn)，则有a+c≡b+d,a-c≡b-d,a*c≡b*d(modn)1.5逆元(inverse)1.5.1加法模逆元定义:若a+b≡0(modn),则称a是b的加法模n逆元，b是a的加法模n逆元。例如：恺撒加密法在解密时会用到加法逆元0123456232425x:abcdefg..xyzy:defghij..abc加密算法:y=(x-'a'+3)%26+'a';解密算法:x=(y-'a'+23)%26+'a';这里的+23相当于-33+23≡0(mod26)表示3的加法逆元是233-3≡0(mod26)表示3的加法逆元是-3所以-3≡23(mod26)或者这样推理:-3%26==(-26+23)%26==23%261.5.2乘法模逆元定义:若a*b≡1(modn),则称a是b的乘法模n逆元，b是a的乘法模n逆元。a的乘法逆元记作a-1。(乘法模n逆元计算过程参考P.95)例如：求13模35的乘法逆元设13模35的乘法逆元为x，则13*x≡1(mod35)上述等式成立的充要条件为gcd(13,35)=1(证明见P.94)于是一定存在x、y使得13*x+35*y=1成立，利用扩展欧几里德法(extendedEuclideanalgorithm)可以解出上述方程中的x及y，其中的x就是13模35的逆元。35=2*13+913=1*9+49=2*4+11=9-2*4=35-2*13–(13-1*9)*2=35-2*13–(13-(35-2*13))*2=(35-2*13)*3–13*2=35*3–8*13x=-8,y=3其中-8≡(-35+27)≡27(mod35)所以13模35的乘法逆元为27。2的mod5乘法逆元=31的mod5乘法逆元=13的mod5乘法逆元=24的mod5乘法逆元=42的mod6乘法逆元=不存在，因为gcd(2,6)=2≠1第2章古典密码encryption(加密):密钥(key)明文(plaintext)----------密文(ciphertext)加密Theprocessofencodingdatatopreventunauthorizedaccess,especiallyduringtransmission.Encryptionisusuallybasedononeormorekeys,orcodes,thatareessentialfordecoding解密,orreturningthedatatoreadableform.decryption(解密):密钥(key)密文(ciphertext)----------明文(plaintext)Theprocessofrestoringencrypteddatatoitsoriginalform.2.1单表密码单表密码只使用一张密码字母表，且明文字母与密文字母有固定的对应关系。频率分析法可以对付单表密码。《连城诀》EdgarAllanPoeTheGold-BugArthurConanDoyleTheDancingMen2.1.1加法密码[demo]JuliusCaesar:恺撒加密法序号加密前加密后0AD1BE2CF.........23XA24YB25ZC加密算法:y=(x-'A'+3)%26+'A';解密算法:x=(y-'A'-3)%26+'A';或x=(y-'A'+23)%26+'A'2.1.2乘法密码加密算法:y=x*k%n;解密算法:x=y*k-1%n;其中k-1是k的乘法逆元2.1.3仿射密码加密算法:y=(x*k1+k2)%n;解密算法:x=(y-k2)*k1-1%n;2.2多表密码多表密码是对每个明文字母采用不同的单表代换，即同一明文字母对应多个密文字母。2.2.1Playfair(P.10)2.2.2Vigenere(P.11)加密算法:y=(x+ki)%n;解密算法:x=(y-ki)%n;例如:明文=thiscryptosystemisnotsecure(19,7,8,18,2,17,24,15,19,14,...)密钥=cipherciphercipher...(2,8,15,7,4,17)密文=VPXZGIAXIV...(21,15,23,25,6,8,0,23,8,21,...)'t'-'a'=19明文'c'-'a'=2密钥+)21(19+2)%26=2121+'A'='V'密文2.2.3Beaufort(P.12)2.2.4Vernam(P.14)2.2.5Hill(P.14)2.2.6Enigma10对字母在接线板上的组合=P2010/2102对字母的组合如下:ABCDACBDADBCEnigma模拟软件()加密过程要经过5个元件:假定明文为A1.plugboard假定接线板设置为:A-B,C-Dcharplug[27]=BADCEFGHIJKLMNOPQRSTUVWXYZ;/*ABCDEFGHIJKLMNOPQRSTUVWXYZ*/charc='A',e;e=plug[c-'A'];//e='B';AB2.rotorIcharrotor[27]=EKMFLGDQVZNTOWYHXUSPAIBRCJ;//ABCDEFGHIJKLMNOPQRSTUVWXYZcharc='B',e;e=rotor[c-'A'];//e='K';BK3.rotorIIAJDKSIRUXBLHWTMCQGZNPYFVOEABCDEFGHIJKLMNOPQRSTUVWXYZKL4.rotorIIIBDFHJLCPRTXVZNYEIWGAKMUSQOABCDEFGHIJKLMNOPQRSTUVWXYZLV5.reflectorcharreflector[27]=YRUHQSLDPXNGOKMIEBFZCWVJAT;//ABCDEFGHIJKLMNOPQRSTUVWXYZVW经过上述5步,A转成W,但W还不是密文,接下去还要走一条逆向路径:4-3-2-1,把W进一步转化成密文,步骤如下:4.rotorIIIcharrotor[27]=BDFHJLCPRTXVZNYEIWGAKMUSQO;//ABCDEFGHIJKLMNOPQRSTUVWXYZWR注意按逆向路径经过3个齿轮时要反查表,即在数组rotor中寻找元素'W',得到该元素的下标设为i,再把i+'A',就得到'R'。3.rotorIIAJDKSIRUXBLHWTMCQGZNPYFVOEABCDEFGHIJKLMNOPQRSTUVWXYZRG2.rotorIEKMFLGDQVZNTOWYHXUSPAIBRCJABCDEFGHIJKLMNOPQRSTUVWXYZGF1.plugboardBADCEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZFF注意接线板查表既可以正向查,也可以反向查,结果是一样的。经过上述4步,W转成F,其中F就是密文。各位可以尝试把F当作明文重新把前面的9步走一遍,最后出来的一定是A,这就实现了解密。要注意在Enigma模拟器中,除了把3个齿轮按从左到右顺序设成III、II、I外，还需要把MessageKey设成010126即AAZ，因为Enigma是先转动齿轮再查表的，当你敲A键时，齿轮I会从26转到1。另外还有两个齿轮在上面的例子中没有用到，现列出它们的转化表。齿轮IV的转换表如下所示:ESOVPZJAYQUIRHXLNFTGKDCMWBABCDEFGHIJKLMNOPQRSTUVWXYZ齿轮V的转换表如下所示:VZBRGITYUPSDNHLXAWMJQOFECKABCDEFGHIJKLMNOPQRSTUVWXYZ5个齿轮使下一个齿轮发生跳转的字母:QEVJZ;齿轮的当前位置,从左到右对应齿轮IIIIIIIVVRFWKA;齿轮的下一步位置;RoyalFlagsWaveKingsAbove假定3个齿轮为III、II、I,齿轮I的当前位置=Q且II的当前位置=A,现在敲任何一个键，都会使I转到R这个位置,此时I会带动II旋转,于是II会从A转到B。另外,还要注意一个doublestepping现象:假定III=1=A,II=4=D,I=17=Q现在I旋转，从Q变成R，一定会带动II旋转:III=1=A,II=5=E,I=18=R此时再旋转I的话，I本来是不应该带动II转的(因为当前I不在Q这个位置),但是II还会再转(doublestepping)，同时II带动III旋转:III=2=B,II=6=F,I=19=S归纳起来讲,II有两种情况会转动:(1)I从Q转到R(2)II当前在E位置,I不管在什么位置doublestepping是由Enigma的机械结构决定的，该现象只会出现在中间那个齿轮上。每个齿轮有一个内部设置叫ringsetting:假定I齿轮的RingSetting=B(内部),MessageKey=A(外部)现在按键盘A的时候,A进入I齿轮后,要做以下运算:charc='A';intdelta=MessageKey-RingSetting;c=((c-'A')+delta+26)%26+'A';此时c='Z';接下去拿c去查齿轮I的表得J现在J要出去的时候，还得减去delta，即:c=c-delta;即c=K所以从齿轮I出来的字母就是K。另外两个齿轮的处理跟I一样。从III到II到I逆向走回来的时候，同样，从左到右进入要加delta，右边出来要减delta。假定I的RingSetting=C,MessageKey=A现在按A，此时MessageKey=B