密码学及其应用之研究AStudyonCryptographyandIts课件

密碼學及其應用之研究(AStudyonCryptographyandItsApplications)Min-ShiangHwang(黃明祥)DepartmentofManagementInformationSystemNationalChungHsingUniversityEmail:mshwang@.tw.tw/1密碼學及其應用之研究1理論基礎-基本密碼技術2理論基礎-基本密碼技術2基本密碼技術對稱式加解密技術非對稱式加解密技術One-WayHashFunction(單向雜湊函數)

數位簽章技術(DigitalSignature)

3基本密碼技術對稱式加解密技術3明文加密解密明文密文密文明文解密加密明文密文密文張三李四金鑰SendSend“安全“金鑰分配管道不安全通訊管道私密金鑰密碼系統(對稱式密碼系統)4明文加密解密明文密文密文明文解密加密明文密文密文張三李四金鑰祕密金鑰密碼系統(Secret-KeyCryptosystems)又稱單金鑰密碼系統(One-KeyCryptosystems)也稱對稱密碼系統(SymmetricCryptosystems)優點：加解密速度快缺點：有金鑰管理的問題每位使用者需儲存n-1把Keys

U1U2U5U3U4著名系統如：Triple-DES及AES5祕密金鑰密碼系統(Secret-KeyCryptosystCA明文加密解密明文密文密文明文解密加密明文密文密文張三的密鑰李四的密鑰張三李四李四的公鑰張三的公鑰SendSend金鑰公開金鑰密碼系統(非對稱式密碼系統)6CA明文加密解密明文密文密文明文解密加密明文密文密文張三的密公開金鑰密碼系統(Public-KeyCryptosystems)又稱雙金鑰密碼系統(Two-KeyCryptosystems)也稱非對稱密碼系統(AsymmetricCryptosystems)優點：沒有金鑰管理的問題高安全性具有數位簽章功能缺點：加解密速度慢

著名之公開密碼系統：RSA密碼系統ElGamal密碼系統橢圓曲線密碼系統7公開金鑰密碼系統(Public-KeyCryptosystRSA加密法非對稱式密碼系統的一種。1978年美國麻省理工學院三位教授Rivest、Shamir、Adleman(RSA)所發展出來的。利用公開金鑰密碼系統作為資料加密的方式，可達到資料加密及數位簽章的功能。8RSA加密法非對稱式密碼系統的一種。8RSA演算法1.張三選2個大質數p和q(至少100位數)，令N=p•q2.再計算Ø(N)=(p-1)(q-1)，並選1個與Ø(N)互質數eØ(N)為Euler‘sTotient函數，其意為與N互質之個數(e,N)即為張三的公開金鑰3.張三選1個數d，滿足e•dmodØ(N)=1d即為張三的解密金鑰(亦稱私有金鑰或祕密金鑰)4. 加密法為C=MemodN解密法為M=CdmodNRSA之安全性取決於質因數分解之困難度要將很大的N因數分解成p跟q之相乘，是很困難的9RSA演算法1.張三選2個大質數p和qRSA演算法-例子1.張三選p=3，q=11;此時N=p•q=3x11=332.張三選出1個與(p-1)x(q-1)=(3-1)(11-1) =2x10=20 互質數e=3 (e,N)=(3,33)即為張三的公開金鑰3.張三選1個數d=7當作解密金鑰， 滿足e•d1mod20(7x31mod20) 令明文M=19 加密:C=MemodN=193mod33=28 解密:M=CdmodN=287mod33=1910RSA演算法-例子1.張三選p=3，q=11CdmodN=MedmodN=MaØ(N)+1modN=MEuler通用定理:若A，P互質，則AØ(P)modP=1定理:Ø(P)=P-1若P為質數Ø(N)=Ø(PQ)=Ø(P)Ø(Q)Ø(A)=i=1..tPiei-1(Pi-1)設A=P1e1P2e2…Ptet

Pi為所有質因數費瑪(Fermat)定理:若P為質數且(A,P)互質，則AP-1modP=1RSA演算法11CdmodNEuler通用定理:定理:費瑪(Fe數位簽章(DigitalSignature)MHE||HD比較是否相等SKaPKaESKa[H(M)]為M之數位簽章DPKa[ESKa[H(M)]]=H(M)512位元MH:HashFunction(SHA-1orMD5)簽章者驗證者H(M)12數位簽章(DigitalSignature)MHE||HOne-WayHashFunction一雜湊函數H(.)，任意輸入一訊息x，很容易計算出其輸出值H(x)。若得知一訊息彙記H(x)，我們很難去推導出訊息x。我們很難去找出一訊息y，使的H(y)=H(x)，其中y不等於x。

13One-WayHashFunction一雜湊函數H(非對稱式密碼系統的一種。1985年由ElGamal所發展出來的。安全性導因於離散對數(DiscreteLogarithm)之困難度。相同明文可得到不相同的密文。RSA密碼系統則是相同明文得到相同密文。ElGamalCryptosystem離散對數(DiscreteLogarithm)的問題：若p為很大之質數；g為p之原根(primitiveroot)y=gxmodp雖已知y,g,p，但要導出x值是很困難的14非對稱式密碼系統的一種。ElGamalCryptosyElGamalCryptosystem若g為p之原根(primitiveroot)：gimodpgjmodp其中ij且i,j介於1至(p-1)之間例如：2為11之原根，因為21mod11=222mod11=423mod11=824mod11=525mod11=1026mod11=927mod11=728mod11=329mod11=6210mod11=1若g為p之原根，且a與(p-1)互質，則gamodp亦為p之原根。例如：2為11之原根，且3與10互質，則23mod11=8亦為11之原根。

15ElGamalCryptosystem若g為p之原根張三將明文m以李四之公開金鑰加密：1.張三選一個亂數r2.計算b=grmodPc=m•yrmodP3.張三送(b,c)給李四ElGamal加密法李四之金鑰產生：y=gxmodPy為李四之公開金鑰x為李四之秘密金鑰P為很大之質數g為與P互質之原根4.李四收到(b,c)後計算c•(bx)-1modP=m16張三將明文m以李四之公開ElGamal加密法李四之金鑰產生李四將明文m以李四之祕密金鑰製作簽章：1.李四選一個亂數k使得gcd(k,p-1)=12.計算r=gkmodp3.李四計算s使得m=(xr+ks)mod(p-1)4.李四送(m,r,s)給驗證者(張三)ElGamal數位簽章法李四之金鑰產生：y=gxmodPy為李四之公開金鑰x為李四之秘密金鑰P為很大之質數g為與P互質之原根5.張三收到(m,r,s)後驗證gm=yrrsmodP上式若相等表示m確定為李四所簽署17李四將明文m以李四之祕密ElGamal數位簽章法李四之金鑰應用研究18應用研究18張三任職於臺灣銀行，李四為某企業(有十萬員工)之會計人員，李四每月底必須把所有員工薪資資料簽章後，將此十萬員工薪資資料及其簽章，送交臺灣銀行，以便張三將薪資轉帳給所有員工，問題是張三要一一驗證李四送來之每位員工薪資資料及其簽章，需要做十萬次驗證，顯然沒有辦法即時轉帳給員工，影響其銀行之服務品質，請替張三想辦法解決此煩惱問題。問題一整批驗證多重簽章(BatchVerifyingMultipleDigitalSignatures)19張三任職於臺灣銀行，李四為某企業(有十萬員工)之會計人員，李假設Alice送訊息M1,M2,..,Mt及簽章S1,S2,..,St給BobAlice以PrivateKeyd簽章，Si=h(Mi)dmodnBob使用Alice的PublicKeye驗證訊息M1,M2,..,Mt的簽章是否正確驗證方式整批驗證多重簽章20假設Alice送訊息M1,M2,..,Mt及簽章S1,整批驗證多重簽章弱點兩項弱點訊息與簽章易位無法偵測出錯誤偽造簽章使簽章係數乘積為1的問題21整批驗證多重簽章弱點兩項弱點21訊息與簽章易位假設Alice送三個簽章訊息(M1,S1),(M2,S2),(M3,S3)給BobAlice送出偽造訊息(M2,S1),(M3,S2),(M1,S3)Bob以下列的式子驗證簽章22訊息與簽章易位假設Alice送三個簽章訊息(M1,S1),訊息與簽章易位簽章值正確，但訊息位置對調乘法具有交換律M1xM2xM3=M2xM3xM1S1xS2xS3=S2xS3xS1M2S1M3S2M1S323訊息與簽章易位簽章值正確，但訊息位置對調M2S1M3S2M1偽造簽章使簽章係數乘積為1假設Alice送三個簽章S1,S2,S3給BobAlice送出偽造的三個簽章

Bob以下列的式子驗證簽章24偽造簽章使簽章係數乘積為1假設Alice送三個簽章S1,S偽造簽章使簽章係數乘積為1簽章係數的值為1M1½xS1M2¼xS2M38xS3(½xS1)x(¼xS2)x(8xS3)=S1xS2xS3

25偽造簽章使簽章係數乘積為1簽章係數的值為1M1½xS1M整批驗證多重簽章-研究方向提出一更安全的方法整批驗證其他多重數位簽章方法整批驗證若發現錯誤時，需逐筆驗證簽章才能找出錯誤的地方，相當缺乏效率，有沒有更有效率方法？26整批驗證多重簽章-研究方向提出一更安全的方法26張三將其所有財產鎖在保險櫃，並立下遺囑，將其財產遺留給其五子女。張三很困擾保險櫃的鑰匙如何保管？若自已保管，萬一張三發生意外來不及告知子女鑰匙，將沒有人可以開鎖。但若交給其中一位子女保管，又擔心該子女會私自挪用，也擔心他死後，該保管鑰匙的子女會獨佔所有財產，對其他子女不公平。請替張三想辦法解決此煩惱問題。問題二秘密分享技術(SecretSharing)27張三將其所有財產鎖在保險櫃，並立下遺囑，將其財產遺留給其五子(t,n)秘密分享(SecretSharing)技術…………分成n個次密鑰(orshadow)回復演算法主要密鑰集t個次密鑰主要密鑰28(t,n)秘密分享(SecretSharing)技術……LagrangeInterpolationFormulaPolynomial:Point:npairsAtleasttpairscanuseLagrangeinterpolationformulatoreconstructuniquepolynomialasfollows:29LagrangeInterpolationFormulaTherearenusersinthesystem.Atleasttormoreusersmayeasilyreconstructthesecrets.Butanyt-1orfewer

usersmaynot.TwoPhases:(1)initialphase(2)secretreconstructphasent(users)secret30Therearenusersinthesyst1.Randomlychooseapolynomialf(x)oft-1degree:2.Letf(0)=sbethesecret.3.Randomlychoosedistinctintegerxiasui’spublicvalue.4.Computeyi=f(xi)asui’sshadow.Secretholder:(1)initialphase311.Randomlychooseapolynomia黃明祥(2)secretreconstructphaseAtleasttusers(ui,i=1,...,t)poolstheirshadowsyi(fori=1,...,t),thesecretscanbereconstructedasfollows:32黃明祥(2)secretreconstructphas秘密分享-研究方向防制欺騙者之機制多組別(t1,n1),(t2,n2),…(tm,nm)秘密分享機制解決秘密值只用一次之缺點33秘密分享-研究方向防制欺騙者之機制33張三要跟網路上李四秘密通訊，但他們並沒有一把共同秘密金鑰，也沒有使用公開金鑰密碼系統。請問張三如何與李四做秘密通訊。問題三金鑰交換技術(KeyExchange)34張三要跟網路上李四秘密通訊，但他們並沒有一把共同秘密金鑰，也Diffie-HellmanKeyExchangeAliceBob註:p為很大之質數g為與p互質之原根(primitive)3.傳送X1.選擇很大的亂數a2.計算X=gamodp4.計算秘密金鑰K=Yamodp1‘.選擇很大的亂數b2‘.計算Y=gbmodp4‘.計算秘密金鑰K=Xbmodp3‘.傳送YK=gabmodp35Diffie-HellmanKeyEx