第29課 密碼學算法(二)之 RSA

第29課密碼學算法（二）之RSA*******************************************************************************預備理論知識（比較枯燥）：RSA算法是第一個既能用于數據加密也能用于數字簽名的算法。它易于理解和操作，也很流行。算法的名字以三個發(fā)明者的名字命名：RonRivest、AdiShamir和LeonardAdleman。RSA的基礎是數論的歐拉定理，它的安全性依賴于大數因數分解的困難性。但RSA的安全性一直未能得到理論上的證明。它經歷了各種攻擊，至今未被完全攻破。RSA密碼系統(tǒng)為每個用戶分配兩對密鑰(公鑰和私鑰)，即公鑰(e，n)和私鑰(d，n)，其中(e，n)用于加密報文，(d，n)用于解密報文，廣泛應用于加密和數字簽名方面，如現在已延伸到電子納稅申報，公鑰或者私鑰都可用作加密。RSA加密算法的過程是：(1)取兩個素數p和q(保密)；(2)計算n=p×q(n稱為模數，公開)，φ(n)=(p一1)×(q一1)(保密)；(3)隨機選取整數e(e稱為公鑰，公開)，且滿足gcd(e，φ(n))=1(即e與(p一1)×(q一1)互素)；(4)計算d，滿足de=1(modφ(n))(d稱為私鑰，保密)。利用RSA加密，第一步需要將明文數字化，并取長度小于lg2n位的數字做明文塊。加密算法C=E(M)＝Me(modn)，其中，M為明文，C為密文。解密算法M=D(C)＝Cd（modn），用私鑰d對密文C解密，得到明文M。例如:假定用戶A要將明文“HI”加密傳遞給用戶B，則B可以取兩個素數p=5和q=11(保密)；計算n=p×q=5×11＝55(公開，公鑰)，φ(n)=(p一1)×(q一1)=4×10＝40(保密)；隨機選取整數e=3(公鑰)，滿足gcd(e，φ(n))=1；由de=1(modφ(n))得d=27(保密，私鑰)。因為，27×3mod40＝81mod40＝1利用RSA加密，第一步需要將明文數字化，假定A、B統(tǒng)一明文編碼方式為空格=00，A=01，B=02，C=03，...Z=26，則明文數字化HI為08、09，A用B的公鑰(3，55)將數字化明文信息由C=E(M)＝Me(modn)＝83mod55、93mod55，加密得密文信息為l7、l4。用戶B收到密文信息由M=D(C)＝Cdmodn＝1727mod55、1427mod55解密得O8、O9，將其轉化為明文“HI”。(3)解密：M=Cdmodn，用私鑰d對密文C解密，得到明文M。*******************************************************************************[例1]dihux的keygenme1.exe讀程序的“關于”，寫明為RSA200，但這是crackme。我們所對付的一般程序是不會告訴你所采用的密碼學算法的，我們需要自己用鼻子把她的氣息聞出來、嗅探出來。用peid掃描目標程序，用kanal插件分析，如圖1圖1kanal掃描的結果點“Export”按鈕，將掃描結果保存為文件，如下：Cryptoname::Fileoffset::Virtualaddress密碼文件偏移RVAVA內存虛擬地址BASE64table::00001BEE::004041EEBigLibBigMod::00001406::00402006BigLibBigPowMod::00001604::00402204{Bignumber}::00001A1F::BigPowMod可以看出，采用了RSA算法。同時，明確地告訴我們，編程時采用了BigLib庫。下面，用IDAPro打開目標程序，利用圖2的字符參考圖2字符參考很容易來到這里，即圖3圖3很難看出程序在干什么，可讀性極差。下面按如圖4所示的菜單操作圖4圖5選取biglib程序代碼變?yōu)閳D6：可讀性大大提高。關鍵代碼如下：xorecx,ecx.text:004010DA.text:004010DAloc_4010DA:;CODEXREF:DialogFunc+BDj.text:004010DApush0.text:004010DCcall__BigCreate@4;_BigCreate(x).text:004010E1movlpAddress[ecx*4],eax.text:004010E8incecx.text:004010E9cmpecx,6.text:004010ECjnzshortloc_4010DA.text:004010EEpushlpAddress.text:004010F4push10h.text:004010F6pushoffseta8acfb4d27cbc8c;"8ACFB4D27CBC8C2024A.text:004010FBcall__BigIn@12;_BigIn(x,x,x).text:00401100pushdword_404415.text:00401106push10h.text:00401108pushoffsetunk_404019.text:0040110Dcall__BigIn@12;_BigIn(x,x,x).text:00401112pushdword_404425.text:00401118push10h.text:0040111Apushoffsetbyte_404349.text:0040111Fcall__BigIn@12;_BigIn(x,x,x).text:00401124pushoffsetString;lpString.text:00401129calllstrlenA.text:0040112Epushdword_404419.text:00401134pusheax.text:00401135pushoffsetString.text:0040113Acall__BigInB256@12;_BigInB256(x,x,x).text:0040113Fpushdword_404421.text:00401145pushlpAddress.text:0040114Bpushdword_404415.text:00401151pushdword_404425.text:00401157call__BigPowMod@16;_BigPowMod(x,x,x,x).text:0040115Cmoveax,1337h.text:00401161push0.text:00401163pushdword_40441D.text:00401169pusheax.text:0040116Apushdword_404421.text:00401170call__BigDiv32@16;_BigDiv32(x,x,x,x).text:00401175pushdword_40441D.text:0040117Bpushdword_404419.text:00401181call__BigCompare@8;_BigCompare(x,x).text:00401186jnzshortloc_40119C.text:00401188push0;uType.text:0040118ApushoffsetCaption;"iNFO".text:0040118FpushoffsetText;"Serialisvalid".text:00401194push[ebp+hWnd];hWnd.text:00401197callMessageBoxA為動態(tài)提示時察看方便，我們將其導入到ollydbg中。如圖，創(chuàng)建MAP文件。然后，用ollydbg中的LoadMap插件，將其導入：動態(tài)調試可知RSA（序列號）除1337＝姓名的ASCII碼故序列號＝RSA（姓名的ASCII碼×1337）n=0x8ACFB4D27CBC8C2024A30C9417BBCA41AF3FC3BD9BDFFe=0x10001已知n、e，下面計算密鑰d打開RSATOOL2軟件：1―――填入NN＝8ACFB4D27CBC8C2024A30C2―――點FactorN按鈕，幾分鐘后得出P和QP＝970E1A438AQ＝EB3FFE9F5C3―――點CalcD按鈕，立刻得出d＝32593252229255151794D86C1A09C7AFCC2CCE42D最后，用VisualC++和MIRACL大數庫寫出注冊機。我寫了console版和windows版各一個。windows版核心代碼如下：mip->IOBASE=16;//16進制模式 c=mirvar(0);//MIRACL的大數類型 n=mirvar(0); d=mirvar(0); m=mirvar(0);mul=mirvar(0x1337); bytes_to_big(len,szName,c);//將姓名轉換成大數 cinstr(n,"8ACFB4D27CBC8C2024A30C9417BBCA41AF3FC3BD9BDFF cinstr(d,"32593252229255151794D86C1A09C7AFCC2CCE42Dmultiply(c,mul,c);//姓名的大數乘以1337 powmod(c,d,n,m); //計算m=(c^d)modn cotstr(m,szSerial);//將m的16進制串表示寫入szSerial中，即為注冊碼 mirkill(c); mirkill(n); mirkill(d); mirkill(m); mirkill(mul); mirexit(); SetDlgItemText(hWnd,IDC_TXT1,szSerial);//顯示正確的序列號

附錄1如何在VisualC++中使用MIRACLTocreateMIRACLapplicationsunderMicrosoftWindowsusingMicrosoftC++version6.0,followthesesteps.Remembera"Release"buildwillbefasterthana"Debug"build.ForMSVC++.NETseebelow.1.Createanewemptyprojectoftype"Win32ConsoleApplication"Giveitthenameoftheassociatedmainprojectfile,e.g.limleeforlimlee.cpp2.Clickon"Project",andthenon"AddtoProject",andthenon"Files"3.Select"libraryfiles(.lib)"fromthe"Filesoftype"drop-downlist.LookfortheprecompiledMIRACLlibraryfilems32.lib,andinsertitintotheproject.4.Addthemainprojectfile(e.g.limlee.cpp)intotheproject.5.OnlyifitisaC++mainprojectfile,alsoaddintotheprojectanyotherneededfiles,likebig.cpp/zzn.cppetc.Thoserequiredarespecifiedinthecommentsatthestartofthemainprojectfile,e.g.*Requires:big.cppzzn.cppThisstepisnotrequiredforCprojects.6.Nowclickon"Project"andthenon"Settings".ClicktheC/C++tabandselectthe"preprocessor"category.Findthebox"AdditionalIncludeDirectories",andspecifyapathtothemiraclheaderfiles,mirdef.h/miracl.h/big.hetc..7.Makesurethatanyfilesneededbytheapplicationareavailableinthedirectoryfromwhichtheapplicationisrun.Forexample*.key*.dss,or*.ecsfiles8.Nowbuildandruntheproject.TocreateanewversionoftheMIRACLlibrary,1.Compileandruntheconfig.cutility,andrenamethegeneratedmirdef.tsttomirdef.hNotethatMicrosoftChasa64-bitintegerdatatypecalled__int642.Createanewprojectoftype"Win32StaticLibrary".Thenclickon"Finish".3.Addintheappropriatefilesmr*.c.Theonesrequiredarethoselistedinmiracl.lst(alsogeneratedbytheconfigutility).4.Nowclickon"Project"andthenon"Settings".ClicktheC/C++tabandselectthe"preprocessor"category.Findthebox"AdditionalIncludeDirectories",andspecifyapathtothemiraclheaderfilesmirdef.handmiracl.h5.NowbuildtheprojectandcreatetheMIRACLlibrary.--------------------------------------------------------------------------------------------TocreateMIRACLapplicationsunderMicrosoftWindowsusingMicrosoftC++.NET,followthesesteps.1.ClickonNewandProject,andselect"VisualC++Projects","Win32",select"Win32ConsoleProject",andgivetheprojectname,forexamplelimlee,forthelimlee.cppexample.ClickonFinish.2.Nowthingsgetalittletricky.Anemptylimlee.cppfileisprovided.YoumustnowcutandpastefromtheMiraclprovidedfilelimlee.cppintothisone.Notethatthemainprogramisnowcalled_tmain.3.ClickonProject,andon"AddexistingItem",andSelect"Allfiles"fromthe"Filesoftype"drop-downlist.LookfortheprecompiledMIRACLlibraryfilems32.lib,andinsertitintotheproject.4.OnlyifitisaC++mainprojectfile,alsoaddintotheprojectanyotherneededfiles,likebig.cpp/zzn.cppetc.Thoserequiredarespecifiedinthecommentsatthestartofthemainprojectfile,e.g.*Requires:big.cppzzn.cppThisstepisnotrequiredforCprojects.Use"Project",and"AddexistingItem".5.ClickonProjectandthen"Properties".OpenuptheC++Tab,goto"PrecompiledHeaders",andselect"Notusingprecompiledheaders"fromthedrop-downbox.Openthe"General"Tab,andspecifyapathtothemiraclheaderfiles,mirdef.h,miracl.handbig.hetc.6.Buildtheprojectandrunitbyclicking"Debug"and"Start".Theprogramrunstocompletionandexits.TocreateanewversionoftheMIRACLlibrary,firstcreateasuitablemirdef.hasabove,then1.ClickonNewandProject,andselect"VisualC++Projects","Win32",enterthenameMiraclandclickon"Win32Project"andthenOK.2.Clickon"ApplicationSettings",andthenselect"StaticLibrary".ThenclickonFinish3.Addintheappropriatefilesmr*.c.(Projectfollowedby"AddExistingItems").4.ClickonProjectandthen"Properties".OpenuptheC++Tab,goto"PrecompiledHeaders",andselect"Notusingprecompiledheaders"fromthedrop-downbox.Openthe"General"Tab,andspecifyapathtothemiraclheaderfiles,mirdef.handmiracl.h5.Nowbuildtheproject.--------------------------------------------------------------------------------------IfusingMIRACLwithinanMFCbasedWin32project,herearesomehints.1.BuildaMIRACLlibrarywithMR_NO_STANDARD_IOdefinedinmirdef.hTheconfig.cutilitycanbeusedasusualtocreateasuitablemirdef.h2.IfusingtheC++MIRACLclasses,don'tforgettochangethedefaultprojectsettingsfortheMIRACLimplementationfilessuchasbig.cppto"notusingpre-compiledheaders".3.Don'tforgetthatMIRACLisaClibrary,notC++.TocallMIRACLroutinesdirectlyfromaC++programyoumust:-extern"C"{#include"miracl.h"}IfusingC++,itsprobablypreferabletoaccessMIRACLviatheC++wrapperclassessuchasimplementedbybig.h/big.cpp.Seebig.hfileformoretips.4.Todisplayabignumber,convertitfirsttoastring.Seethecommentsatthestartofbig.h

附錄2biglib大數庫使用手冊biglibv.0.01e biglibisanassemblybignumlibrary ?ican'tbeheldresponsibleforwhatyoudowiththislibrary,oranydamageordata lossthatmightresultfromit'suse ?thelibrarydoesn'thandlesignedbignumbers ?thelibraryusesVirtualAllocandVirtualFree(kernel32.dll) ?thelibraryisquiteslow,ihaven'tcodedparticularlyfastalgorithm,ijustwanted tohaveanasmbignumlibrarythatgivesthecorrectresults=) ?beware:ifyoumakeanerrorinoneoftheparameterofafunction,itmayresultin aprogramcrash ?theroutinesprotectebx,ecx,ediandesi ?functions: _BigCreate(dword)InitValue [LIBcore.asm] createsabignumandinitializesitwiththevalueInitValue returnsapointertothebignum _BigDestroy(big*)Big [LIBcore.asm] destroysthebignumBig _BigCopy(big*)BigSrc,(big*)BigDest [LIBcore.asm] copiesBigSrctoBigDest _BigCompare(big*)BigA,(big*)BigB [LIBcore.asm] comparesBigAandBigB returns1ifBigA>BigB 0ifBigA=BigB -1ifBigA<BigB _BigCompare32(big*)BigA,(dword)Value [LIBcore.asm] comparesBigAandValue returns1ifBigA>Value 0ifBigA=Value -1ifBigA<Value _BigInB256(char*)Data,(dword)Len,(big*)Big [LIBio.asm] fillsBigwithLenbytesofDatainbase256 _BigIn32(dword)Value,(big*)Big [LIBio.asm] fillsBigwithValue _BigIn(char*)String,(dword)Base,(big*)Big [LIBio.asm] fillsBigwiththenull-terminatedstringStringinbaseBase(Baseis2-62) returns0ifnoerror,-1ifbasenotsupported _BigInBytes(char*)Buffer,(dword)Len,(dword)Base,(big*)Big [LIBio.asm] fillsBigwithLenbytesofdataatBufferinbaseBase(Baseis2-256) returns0ifnoerror,-1ifbasenotsupported _BigOutB256(big*)Big,(char*)Buffer [LIBio.asm] fillsBufferwiththevalueofBiginbase256 returnsthelengthofthestring _BigOutB16(big*)Big,(char*)Buffer [LIBio.asm] fillsBufferwiththevalueofBiginbase16asanull-terminatedstring returnsthelengthofthestringnotincludingtheterminatingnullcharacter _BigOut(big*)Big,(dword)dtBase,(char*)Buffer [LIBio.asm] fillsBufferwiththevalueofBiginbaseBaseasanull-terminatedstring(Baseis2-62or256) returnsthelengthofthestringnotincludingtheterminatingnullcharacter,-1ifbasenotsupported _BigOutBytes(big*)Big,(dword)dtBase,(char*)Buffer [LIBio.asm] fillsBufferwiththevalueofBiginbaseBaseasdata(Baseis2-256) returnsthelengthofthedatanotincludingtheterminatingnullcharacter,-1ifbasenotsupported _BigAdd32(big*)BigX,(dword)Value,(big*)BigY [LIBbigadd.asm] BigY=BigX+Value _BigAdd(big*)BigX,(big*)BigY,(big*)BigZ [LIBbigadd.asm] BigZ=BigX+BigY _BigSub32(big*)BigX,(dword)Value,(big*)BigY [LIBbigsub.asm] BigY=|BigX-Value| _BigSub(big*)BigX,(big*)BigY,(big*)BigZ [LIBbigsub.asm] BigZ=|BigX-BigY| _BigShr(big*)BigX,(big*)BigY [LIBbigshift.asm] BigY=