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

1、黃明祥密碼學及其應用之研究密碼學及其應用之研究(A Study on Cryptography and Its Applications)Min-Shiang Hwang(黃明祥黃明祥)Department of Management Information SystemNational Chung Hsing UniversityEmail:mshwangnchu.edu.twhttp:/isrc.nchu.edu.tw/1黃明祥技術技術2黃明祥技術技術 對稱式加解密技術對稱式加解密技術 非對稱式加解密技術非對稱式加解密技術 One-Way Hash Function(單向單向雜湊函數雜湊函

2、數)數位簽章技術數位簽章技術(Digital Signature)3黃明祥明文明文加密加密解密解密明文明文密文密文密文密文明文明文解密解密加密加密明文明文密文密文密文密文張三張三李四李四金鑰金鑰SendSend“安全安全“金鑰分配管道金鑰分配管道不安全通訊管道不安全通訊管道私密金鑰密碼系統私密金鑰密碼系統(對稱式密碼系統對稱式密碼系統)4黃明祥祕密金鑰密碼系統祕密金鑰密碼系統(Secret-Key Cryptosystems)又稱單又稱單金鑰密碼系統金鑰密碼系統(One-Key Cryptosystems)也稱對稱也稱對稱密碼系統密碼系統(Symmetric Cryptosystems)優點：

3、加解密速度快優點：加解密速度快缺點：有金鑰管理的問題缺點：有金鑰管理的問題 每位使用者需儲存每位使用者需儲存n-1把把Keys U1U2U5U3U4著名系統如：著名系統如：Triple-DES及及AES5黃明祥CA明文明文加密加密解密解密明文明文密文密文密文密文明文明文解密解密加密加密明文明文密文密文密文密文張三的密鑰張三的密鑰李四的密鑰李四的密鑰張三張三李四李四李四的公鑰李四的公鑰張三的公鑰張三的公鑰SendSend金鑰金鑰公開金鑰密碼系統公開金鑰密碼系統(非對稱式密碼系統非對稱式密碼系統)6黃明祥公開金鑰密碼系統公開金鑰密碼系統(Public-Key Cryptosystems)又稱雙又稱

4、雙金鑰密碼系統金鑰密碼系統(Two-Key Cryptosystems)也稱非對稱也稱非對稱密碼系統密碼系統(Asymmetric Cryptosystems)優點：沒有金鑰管理的問題優點：沒有金鑰管理的問題 高安全性高安全性 具有數位簽章功能具有數位簽章功能缺點：加解密速度慢缺點：加解密速度慢 著名之公開密碼系統：著名之公開密碼系統：RSA密碼系統密碼系統 ElGamal密碼系統密碼系統 橢圓曲線橢圓曲線密碼系統密碼系統7黃明祥RSA 加密法加密法 非對稱式密碼系統的一種。非對稱式密碼系統的一種。1978年美國麻省理工學院三位教授年美國麻省理工學院三位教授Rivest、Shamir、Adle

5、man(RSA)所發展出來的所發展出來的。利用公開金鑰密碼系統作為資料加密的方式，利用公開金鑰密碼系統作為資料加密的方式，可達到可達到資料加密資料加密及及數位簽章數位簽章的功能。的功能。8黃明祥RSA 演算法演算法1.張三選張三選 2 個大質數個大質數 p 和和 q (至少至少100位數位數)，令，令 N=p q2.再計算再計算(N)=(p-1)(q-1)，並並選選 1 個與個與(N)互質數互質數 e (N)為為Eulers Totient函數函數，其意為與其意為與N互質之個數互質之個數 (e,N)即為張三的公開金鑰即為張三的公開金鑰3.張三選張三選 1 個數個數 d，滿足滿足 e d mod

6、(N)=1 d 即為張三的解密金鑰即為張三的解密金鑰(亦稱私有金鑰或祕密金鑰亦稱私有金鑰或祕密金鑰)4.加密法為加密法為 C=Me mod N 解密法為解密法為 M=Cd mod N RSARSA之安全性取決於質因數分解之困難度之安全性取決於質因數分解之困難度 要將很大的要將很大的N N因數分解成因數分解成p p跟跟q q之相乘之相乘，是很困難的是很困難的9黃明祥RSA 演算法演算法-例子例子1.張三選張三選 p=3，q=11;此時此時 N=p q=3 x 11=332.張三選出張三選出 1 個與個與(p-1)x(q-1)=(3-1)(11-1)=2 x 10=20互質數互質數 e=3(e,N

7、)=(3,33)即為張三的公開金鑰即為張三的公開金鑰3.張三選張三選 1 個數個數 d=7 當作解密金鑰，當作解密金鑰，滿足滿足 e d 1 mod 20 (7 x 3 1 mod 20)令明文令明文 M=19加密加密:C=Me mod N=193 mod 33=28解密解密:M=Cd mod N=287 mod 33=1910黃明祥 Cd mod N=Med mod N=Ma(N)+1 mod N=MEuler通用定理通用定理:若若A，P互質互質，則，則 A(P)mod P=1 定理定理:(P)=P-1 若若P為質數為質數 (N)=(PQ)=(P)(Q)(A)=i=1.t Piei-1(Pi

8、-1)設設A=P1e1P2e2Ptet Pi為所有質因數為所有質因數 費瑪費瑪(Fermat)定理定理:若若P為質數且為質數且(A,P)互質互質，則，則 AP-1 mod P=1 RSA 演算法演算法11黃明祥數位簽章數位簽章(Digital Signature)MHE|HD比較是否相等比較是否相等SKaPKaESKaH(M)為為M M之數位簽章之數位簽章DPKaESKaH(M)=H(M)512位元位元MH:Hash Function(SHA-1 or MD5)簽章者簽章者驗證者驗證者H(M)12黃明祥One-Way Hash Function 一雜湊函數一雜湊函數H(.)H(.)，任意輸入一

9、訊息任意輸入一訊息x x，很容易計很容易計算出其輸出值算出其輸出值H(x)H(x)。若得知一訊息彙記若得知一訊息彙記H(x)H(x)，我們很難去推導出訊我們很難去推導出訊息息x x。我們很難去找出一訊息我們很難去找出一訊息y y，使的使的H(y)=H(x)H(y)=H(x)，其中其中y y不等於不等於x x。13黃明祥 非對稱式密碼系統的一種。非對稱式密碼系統的一種。1985年由年由ElGamal所發展出來的所發展出來的。安全性導因於離散對數安全性導因於離散對數(Discrete Logarithm)之困難度之困難度。相同明文可得到不相同的密文相同明文可得到不相同的密文。RSA密碼系統則是密碼

10、系統則是相同明文得到相同密文相同明文得到相同密文。ElGamal Cryptosystem離散對數離散對數(Discrete Logarithm)的問題：的問題：若若p為很大之質數；為很大之質數；g為為p之原根之原根(primitive root)y=gx mod p雖已知雖已知y,g,p，但，但要導出要導出x值是很困難的值是很困難的 14黃明祥ElGamal Cryptosystem 若若g為為p之原根之原根(primitive root)：gi mod p gj mod p 其中其中i j且且i,j介於介於1至至(p-1)之間之間例如：例如：2為為11之原根之原根，因為因為 21 mod

11、11=2 22 mod 11=4 23 mod 11=8 24 mod 11=5 25 mod 11=10 26 mod 11=9 27 mod 11=7 28 mod 11=3 29 mod 11=6 210 mod 11=1 若若g為為p之原根之原根，且且a a與與(p-1)p-1)互質互質，則，則g ga a mod p mod p亦亦為為p p之原根之原根。例如：例如：2為為11之原根之原根，且且3 3與與1010互質互質，則則2 23 3 mod 11=8mod 11=8亦為亦為1111之原根之原根。15黃明祥張三將明文張三將明文m以李四之公開以李四之公開金鑰加密金鑰加密：1.張三選

12、一個亂數張三選一個亂數r2.計算計算 b=gr mod P c=m yr mod P3.張三送張三送(b,c)給李四給李四ElGamal 加密法加密法李四之金鑰產生：李四之金鑰產生：y=gx mod Py為李四之公開金鑰為李四之公開金鑰x為李四之秘密金鑰為李四之秘密金鑰P為很大之質數為很大之質數g為與為與P互質之原根互質之原根4.李四收到李四收到(b,c)後後計算計算 c (bx)-1 mod P =m16黃明祥李四將明文李四將明文m以李四之祕密以李四之祕密金鑰製作簽章金鑰製作簽章：1.李四選一個亂數李四選一個亂數k使得使得gcd(k,p-1)=12.計算計算r=gk mod p3.李四計算李

13、四計算s使得使得m=(xr+ks)mod(p-1)4.李四送李四送(m,r,s)給驗證者給驗證者(張三張三)ElGamal 數位簽章法數位簽章法李四之金鑰產生：李四之金鑰產生：y=gx mod Py為李四之公開金鑰為李四之公開金鑰x為李四之秘密金鑰為李四之秘密金鑰P為很大之質數為很大之質數g為與為與P互質之原根互質之原根5.張三收到張三收到(m,r,s)後驗證後驗證 gm=yrrs mod P 上式若相等表示上式若相等表示m確定為李四所簽署確定為李四所簽署17黃明祥18黃明祥張三張三任職於臺灣銀行任職於臺灣銀行，李四李四為某企業為某企業(有有十十萬員工萬員工)之會計人員之會計人員，李四李四每月

14、底必須把所有員工薪資資每月底必須把所有員工薪資資料簽章後料簽章後，將此十萬員工薪資資料及其簽章，送，將此十萬員工薪資資料及其簽章，送交交臺灣臺灣銀行，以便銀行，以便張三張三將薪資轉帳給所有員工，將薪資轉帳給所有員工，問題是問題是張三張三要一一驗證要一一驗證李四李四送來之每位員工薪資送來之每位員工薪資資料及其簽章，需要做十萬次驗證，顯然沒有辦資料及其簽章，需要做十萬次驗證，顯然沒有辦法即時轉帳給員工，影響其銀行之服務品質，法即時轉帳給員工，影響其銀行之服務品質，請請替替張三張三想辦法解決此煩惱問題。想辦法解決此煩惱問題。問題一問題一整批驗證多重簽章(Batch Verifying Multipl

15、e Digital Signatures)19黃明祥假設假設Alice送訊息送訊息M1,M2,.,Mt及簽章及簽章S1,S2,.,St給給BobAlice以以Private Key d簽章，簽章，Si=h(Mi)d mod nBob使用使用Alice的的Public Key e驗證訊息驗證訊息M1,M2,.,Mt的簽章是否正確的簽章是否正確驗證方式驗證方式nMhStiieitimod)()(11整批驗證多重簽章20黃明祥整批驗證多重簽章弱點兩項弱點兩項弱點訊息與簽章易位無法偵測出錯誤訊息與簽章易位無法偵測出錯誤偽造簽章使簽章係數乘積為偽造簽章使簽章係數乘積為1的問題的問題21黃明祥訊息與簽章易

16、位假設假設Alice送三個簽章訊息送三個簽章訊息(M1,S1),(M2,S2),(M3,S3)給給BobAlice送出偽造訊息送出偽造訊息(M2,S1),(M3,S2),(M1,S3)Bob以下列的式子驗證簽章以下列的式子驗證簽章22黃明祥訊息與簽章易位訊息與簽章易位簽章值正確，但訊息位置對調簽章值正確，但訊息位置對調乘法具有交換律乘法具有交換律M1 x M2 x M3=M2 x M3 x M1S1 x S2 x S3=S2 x S3 x S1M2S1M3S2M1S323黃明祥偽造簽章使簽章係數乘積為1假設假設Alice送三個簽章送三個簽章S1,S2,S3給給BobAlice送出偽造的三個簽章

17、送出偽造的三個簽章 Bob以下列的式子驗證簽章以下列的式子驗證簽章,2111SS,4122SS 338SS 24黃明祥偽造簽章使簽章係數乘積為1簽章係數的值為簽章係數的值為1M1 x S1M2 x S2M38 x S3(x S1)x(x S2)x(8 x S3)=S1 x S2 x S3 25黃明祥整批驗證多重簽章-研究方向提出一更安全的方法提出一更安全的方法整批驗證其他多重數位簽章方法整批驗證其他多重數位簽章方法整批驗證若發現錯誤時，需逐筆驗證簽整批驗證若發現錯誤時，需逐筆驗證簽章才能找出錯誤的地方，相當缺乏效率，章才能找出錯誤的地方，相當缺乏效率，有沒有更有效率方法？有沒有更有效率方法？2

18、6黃明祥張三張三將其所有財產鎖在保險櫃將其所有財產鎖在保險櫃，並立下遺囑，將其，並立下遺囑，將其財產遺留給其五子女財產遺留給其五子女。張三很困擾張三很困擾保險櫃的鑰匙保險櫃的鑰匙如何保管如何保管？若自已保管？若自已保管，萬一萬一張三張三發生意外來不發生意外來不及告知子女鑰匙，將沒有人可以開鎖及告知子女鑰匙，將沒有人可以開鎖。但若交給。但若交給其中一位子女保管其中一位子女保管，又擔心該子女會私自挪用，又擔心該子女會私自挪用，也擔心他死後，該保管鑰匙的子女會獨佔所有財也擔心他死後，該保管鑰匙的子女會獨佔所有財產，對其他子女不公平產，對其他子女不公平。請替。請替張三張三想辦法解決此想辦法解決此煩惱問

19、題。煩惱問題。問題二問題二秘密分享技術秘密分享技術(Secret Sharing)27黃明祥(t,n)(t,n)秘密分享秘密分享(Secret Sharing)(Secret Sharing)技術技術分成分成n個次密鑰個次密鑰(or shadow)回復演算法回復演算法主要密鑰主要密鑰集集t個次密鑰個次密鑰主要密鑰主要密鑰28黃明祥Lagrange Interpolation Formula11221)(ttxaxaxasxfPolynomial:Point:),(iiyxn pairsAt least t pairs),(iiyxcan use Lagrange interpolation f

20、ormula toreconstruct unique polynomial11221)(ttxaxaxasxfas follows:sxxxyftiijtjijji1,10)0(tiijtjijjixxxxyxf1,1)(29黃明祥 There are n users in the system.At least t or more users may easily reconstruct the secret s.But any t-1 or fewer users may not.Two Phases:(1)initial phase (2)secret reconstruct phas

21、ent(users)secret30黃明祥1.Randomly choose a polynomial f(x)of t-1 degree:2.Let f(0)=s be the secret.3.Randomly choose distinct integer xi as uis public value.4.Compute yi=f(xi)as uis shadow.11221)(ttxaxaxasxfSecret holder:(1)initial phase31黃明祥黃明祥(2)secret reconstruct phasesaxxxyftiijtjijji01,10)0(At le

22、ast t users(ui,i=1,.,t)pools their shadowsyi(for i=1,.,t),the secret s can be reconstructed as follows:32黃明祥秘密分享-研究方向防制欺騙者之機制防制欺騙者之機制多組別多組別(t1,n1),(t2,n2),(tm,nm)秘密分享機制秘密分享機制解決秘密值只用一次之缺點解決秘密值只用一次之缺點 33黃明祥張三張三要跟網路上要跟網路上李四李四秘密通訊秘密通訊，但他們並沒有一把，但他們並沒有一把共同秘密金鑰，也沒有使用公開金鑰密碼系統共同秘密金鑰，也沒有使用公開金鑰密碼系統。請問請問張三如何與李四

23、做秘密通訊張三如何與李四做秘密通訊。問題三問題三金鑰交換技術金鑰交換技術(Key Exchange)34黃明祥Diffie-Hellman Key ExchangeAliceBob註註:p:p為很大之質數為很大之質數 g g為與為與p p互質之原根互質之原根(primitive)primitive)3.傳送傳送X1.1.選擇很大的亂數選擇很大的亂數a a2.2.計算計算 X=X=g ga a mod p mod p4.4.計算秘密金鑰計算秘密金鑰 K=K=Y Ya a mod p mod p1.1.選擇很大的亂數選擇很大的亂數b b2.2.計算計算 Y=Y=g gb b mod p mod p

24、4.4.計算秘密金鑰計算秘密金鑰 K=K=X Xb b mod p mod p3.傳送傳送YK=gab mod p35黃明祥Man-in-the-Middle AttackAliceBobXX=X=g ga a mod mod p pY=Y=g gb b mod p mod pYKah=gah mod pKbh=gbh mod pHackerK Kahah=Z Za a mod p mod p =g gahah mod p mod pZ=Z=g gh h mod mod p pZZK Kbhbh=Z Zb b mod p mod p =g gbhbh mod p mod p36黃明祥Ellip

25、tic Curve Diffie-Hellman Key AgreementE:y2=x3+ax+bP:a point on E(We call the point P is a base point).AliceBobQA=dAP QA as her public key.dA as her private key.QB=dBP QB as his public key.dB as his private key.QAQAB=dBQA QBQAB=dAQB QAB=dAdBP37黃明祥金鑰交換技術-研究方向防制防制Man-in-the-Middle攻擊之機制攻擊之機制金鑰交換過程中如何確認彼此身份？金鑰交換過程中如何確認彼此身份？三方或多人如何做金鑰交換？三方或多人如何做金鑰交換？(Conference Key Scheme)38黃明祥其他研究公平賭博公平賭博公正且安全的電子投票公正且安全的電子投票群體簽章群體簽章代理簽章代理簽章電子錢幣電子錢幣/小額付款機制小額付款機制/電子信用卡電子信用卡/電子支票電子支票行動通訊之認證行動通訊之認證網路使用者身份認證網路使用者身份認證安全的電子競標安全的電子競標39黃明祥40