紐約州

1、李榮三 博士國立中正大學(xué)資訊工程學(xué)系,資訊安全技術(shù)的發(fā)展與應(yīng)用,MSN lab,2,Outline,古典密碼學(xué)現(xiàn)代密碼學(xué)模糊傳輸電子商務(wù)應(yīng)用視覺密碼學(xué),MSN lab,3,清朝密碼學(xué)家,「 精神炯炯 老貌堂堂 烏巾白髯 龜鶴呈詳」---紀(jì)曉嵐,MSN lab,4,納瓦荷族密碼兵,二次大戰(zhàn),MSN lab,5,,傳統(tǒng)密碼學(xué),,,,,,,傳統(tǒng)密碼學(xué),換位法,,代換法,,(1),反轉(zhuǎn)換位,,(2,),行換位,,

2、古典密碼學(xué),MSN lab,6,明文：MEET ME MONDAY MORNING密文：GNINROM YADNOM EM TEEM,換位法（1）反轉(zhuǎn)換位,MSN lab,7,換位法（2）行換位,明文：SHIP EQUIPMENT ON THE FOURTH OF JULY,密文：TOFUS OFOIH NJUPI TURMP HLTEE EYHNQ(橫取)金鑰：3-5-4-2-1(數(shù)字),,MSN lab,8,代換法

3、（1）簡單代換,,A B C D E F G H I J K L M N O P Q R S T U V W X Y Z,,H A R P S I C O D B E F G J K L M N Q X T U V W Z Y,明文： HELP ME密文： OSFL GS,,MSN lab,9,代換法（2）凱撒加密法,f(a)=(a+k) mod n, a=該字在字集中原先位置；k=移動的位置；n=此字集的大小。,明文：SECURE

4、 ALL MESSAGES密文：VHFXUH DOO PHVVDJHV,,A B C D E F G H I J K L M N O P Q R S T U V W X Y Z,,D E F G H I J K L M N O P Q R S T U V W X Y Z A B C,取 k=3,MSN lab,10,代換法（3）,密文：依照下列取代法則取代而成,紐約州，Trinity市的墓碑,密文：REMEMBERDEATE

5、,MSN lab,11,現(xiàn)代密碼學(xué),對稱式加密系統(tǒng)公開金鑰加密系統(tǒng)數(shù)位簽章盲簽章,MSN lab,12,對稱式加密系統(tǒng),1976年美國國家標(biāo)準(zhǔn)局公佈為資料加密標(biāo)準(zhǔn)DES (Data Encryption Standard)。十六回合：擴(kuò)充轉(zhuǎn)換、二進(jìn)位加法、代換轉(zhuǎn)換、排列轉(zhuǎn)換,,Key,明文,密文,密文,,明文,MSN lab,13,安全?,金鑰 56 bits (256 ? 1017)若破解速度 106 key/sec ?

6、3 *1013 keys/yr使用暴力搜尋需要約 3000年。但如果使用106 臺電腦同時運(yùn)轉(zhuǎn)， 則只需 3*103/ 106 ? 26.28 小時即可破解。,MSN lab,14,Triple DES,K1=K2 K3, 112bitsK1=K2=K3, 168bits,,K1,明文,密文,密文,,明文,,K2,,,K3,,MSN lab,15,,2000年Vincent Rijmen and Joan DaemenR

7、ijndael Algorithm128, 160, 192, 224, 2562002年美國國家標(biāo)準(zhǔn)局公佈為資料加密標(biāo)準(zhǔn)AES (Advanced Encryption Standard)。AES-128(10), AES-192(12), AES-256(14)Memory, Efficiency,MSN lab,16,公開金鑰加密系統(tǒng),Diffie, Hellman, 1976Rivest, Shamir, Adlema

8、n(RSA), 1977Factorization ProblemElGamal, 1985 Discrete Logarithm Problem,MSN lab,17,Rivest, Shamir, Adleman(RSA),取兩個質(zhì)數(shù) p = 17, q = 11計算 N = pxq =187, ψ(N) = (p-1)(q-1)=160選定公鑰e = 7，(e必須與ψ(N)互質(zhì))計算出私鑰d 滿足ed = 1 mod

9、ψ(N)，可得d = 23加密明文M得密文C = Me mod N C = 887 mod 187 = 11解密密文C得明文M = Cd mod NM = 1123 mod 187 = 88,MSN lab,18,安全基礎(chǔ)—因數(shù)分解問題,ψ(N) = (p-1)(q-1)，如果知悉公開參數(shù)N的兩個質(zhì)因數(shù)(p, q)，則ψ(N)的值將無秘密可言。由於e為公開訊息，並且滿足ed = 1 mod ψ(N)，因此如果ψ(N) 為外

10、人知悉，則可利用歐式演算法計算出私鑰d的值。如果可以有效率地執(zhí)行因數(shù)分解，則RSA密碼系統(tǒng)毫無安全性可言。,MSN lab,19,因數(shù)分解問題,15 = 3×591 = 7×132173 = 41×533776111 = 1889×1999152260502792253336053561837813263742971806811496138068865790849458012296325

11、8952897654000350692006139 = ?,,,,,,MSN lab,20,RSA-200,2799783391122132787082946763872260162107044678695542853756000992932612840010760934567105295536085606182235191095136578863710595448200657677509858055761357909873495014

12、4178863178946295187237869221823983,MSN lab,21,,200 digits, 663 bitsMay 9, 2005, Franke et al.2.2 GHz CPU---55 years80 2.2 GHz CPU---3 months,MSN lab,22,,Factors = 35324619344027701212726049781984643686197400197625023

13、649303468776121253679423200058547956528088349and 7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467,MSN lab,23,30,000 USD. RSA-704 =,74037563479561712828046796097429573

14、142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359212 digits,MSN lab,24,100,000 USD. RSA-102

15、4 =,135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187

16、510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563309 digits,MSN lab,25,200,000 USD. RSA-2048 =,25195908475657893494027183240048398571429282126204032027777137836043662020707595

17、5562640185258807844069182906412495150821892985591491761845028084891200728449926873928072877767359714183472702618963750149718246911650776133798590957000973304597488084284017974291006424586918171951187461215151726546322822

18、1686998754918242243363725908514186546204357679842338718477444792073993423658482382428119816381501067481045166037730605620161967625613384414360383390441495263443219011465754445417842402092461651572335077870774981712577246

19、7962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357 617 digits,MSN lab,26,數(shù)位簽章與憑證(RSA),Certificate Authority (CA)-> Alice {ed = 1 mod ψ(N)}Public key (e, N) ;

20、private key dCertificate: algorithm, issuer, period, … Alice: s=md mod N.Alice sends (s, m) to Bob.Bob: (e, N)m=se mod N.,MSN lab,27,盲簽章,Alice: ed ? 1 (mod ψ(N))Bob: message m, random number rm' = mre mod NA

21、lice: s' = (m')d =mdr mod NBob: s = s'r-1 mod N =(mdr)r-1 mod N = md mod N,MSN lab,28,模糊傳輸 (1-out-of-n),,Alice,Bob,,,Request one message,messages,3. Privacy of Alice,2. Privacy of Bob,1. Correctness,Stocks

22、,Message query,MSN lab,29,t-out-of-n,,Alice,Bob,,,Request t messages,messages,Stocks,Message query,3. Privacy of Alice,2. Privacy of Bob,1. Correctness,MSN lab,30,Chinese Remainder Theorem (CRT),To find a positive intege

23、r C that satisfies the following congruence, C ≡ 2 (mod 3), C ≡ 3 (mod 5), andC ≡ 3 (mod 7).,MSN lab,31,Define Notations,e/d: the public/private key of Alice, a1, a2, …, an: n messages d1, d2, …, dn: n relatively

24、 prime numbers IDi: the identity of message aib1, b2, …, bt: t messages that Bob expected to get,,,MSN lab,32,Alice,Step 1: Computes D = d1* d2* …* dn, and constructs congruence system as, C ≡ a1 (mod d

25、1),C ≡ a2 (mod d2),C ≡ an (mod dn).C = (D/d1)y1a1 + (D/d2)y2a2 + … + (D/dn)ynan mod D by CRT, where (D/di)yi ≡ 1 (mod di),MSN lab,33,Alice,Step 2: ComputesT1 = d1e mod N,T2 = d2e mod N,Tn = dne mod N, Step 3:

26、 Publish,MSN lab,34,MSN lab,35,Bob,Step 1:(IDj?, Tj?), for j = 1, 2 to t Step 2:?1 = r1e * T1? mod N,?2 = r2e * T2? mod N,?t = rte * Tt? mod N, Step 3: Sends {?1, ?2, …, ?t} to Alice,,MSN lab,36,Alice,Step 1:β1 =

27、?1d = r1ed * T1?d = r1 * T1?d mod N,β2 = ?2d = r2ed * T2?d = r2 * T2?d mod N,βt = ?td= rted * Tt?d = rt * Tt?d mod N, Step 2: Sends {β1,β2, …, βt} to Bob,MSN lab,37,Bob,Step 1: d1? = r1-1 *β1 = T1?d = d1 ?ed mod N,

28、d2? = r2-1 *β2 = T2?d = d2 ?ed mod N,dt? = rt-1 *βt = Tt?d = dt ?ed mod N. Step 2:b1 = C mod d1?,b2 = C mod d2?,bt = C mod dt?.,MSN lab,38,Comparisons,MSN lab,39,電子商務(wù)應(yīng)用,MSN lab,40,電子支票,先交易後付款 金額較大的交易 簽名效果公開金鑰系統(tǒng)

29、的數(shù)位簽章驗(yàn)證付款者和銀行的身份 數(shù)位憑證,MSN lab,41,電子支票,,消費(fèi)者,網(wǎng)路商店,消費(fèi)者開戶之銀行,商店開戶之銀行,票據(jù)所,1.選擇商品，並決定以電子支票付款,,,2.驗(yàn)證支票,4.存入電子支票,,,5.票據(jù)處理與匯款,3.傳送商品,,,,6.更新帳戶資料,MSN lab,42,電子旅行支票,傳統(tǒng)旅行支票個人使用 護(hù)照簽章仿冒護(hù)照->盜領(lǐng)電子Smart card聲紋、指紋先付款公開金鑰系統(tǒng)的數(shù)位

30、簽章,MSN lab,43,電子旅行支票,,旅行者,1.核發(fā)憑證,開票銀行,憑證中心,,,1.核發(fā)憑證,,1.核發(fā)憑證,,2.購買電子旅行支票,,3.要求兌現(xiàn),,4.請求驗(yàn)證,,5.同意放款,,6.傳送現(xiàn)金,,7.結(jié)算金額,MSN lab,44,電子競標(biāo),English auction: Yahoo, ebayDutch auctionSealed-bid auction數(shù)位簽章技術(shù) 通訊金鑰,MSN lab,45,Englis

31、h Auction,,競標(biāo)者,拍賣商,3.產(chǎn)生標(biāo)單,2.確認(rèn)無誤後廣播,OK,,4.確認(rèn)標(biāo)單公佈最高價,MSN lab,46,Sealed-bid/Dutch auction,,3.傳送標(biāo)單,,,,,1.要求競標(biāo),1.要求競標(biāo),,2.確認(rèn)無誤後廣播,OK,3.傳送標(biāo)單,1.要求競標(biāo),4.公佈得標(biāo)之最高價,MSN lab,47,電子投票,傳統(tǒng)時間限制地理限制開票慢電子任何時間任何地點(diǎn)高效率合法性---公開金鑰技術(shù)正確性

32、---AES匿名性---盲簽章,MSN lab,48,電子投票,,註冊中心,計票中心,投票者,轉(zhuǎn)址伺服器,憑證中心,,2.要求選票,,3.要求盲簽章,4.送出選票,,1.協(xié)調(diào)共享金鑰,5.轉(zhuǎn)換選票位址,,6.傳送選票,7.公開選票結(jié)果,MSN lab,49,視覺密碼學(xué),MSN lab,50,Counterfeit Transparency 1,Counterfeit Transparency 1+ Basis Transparency

33、=secret information: “中國人的世紀(jì)”,Basis Transparency,MSN lab,51,,SecretInformation,,,,,,,,Basis Transparency(Random Dots),Counterfeit Transparency,,,,Picture,MSN lab,52,,SecretInformation,,,,Basis Transparency(Random D

34、ots),,,,Counterfeit Transparency,,Stack,,MSN lab,53,3*3像素擴(kuò)充法,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,白,白,白,白,黑,黑,黑,黑,,,MSN lab,54,,Case 2,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

35、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Secret image,Basis transparency,Counterfeit transparency,Counterfeit picture,,MSN lab,55,,Basis Transparency,MSN lab,56,Counterfeit Transparency 1,Counterfeit Tr

36、ansparency 1+ Basis Transparency=secret information: “中國人的世紀(jì)”,Basis Transparency,MSN lab,57,Counterfeit Transparency 2,Counterfeit Transparency + Basis Transparency=secret information: “電腦密碼學(xué)”,Basis Transparency,MSN la

37、b,58,白,白,白,黑,白,黑,白,白,黑,黑,白,白,白,黑,白,黑,黑,黑,白,黑,黑,黑,黑,白,,,,,,,,,,3*3像素擴(kuò)充法 (有意義),MSN lab,59,Counterfeit 1,Counterfeit 2,MSN lab,60,Conclusions,2.2 GHz CPU- 700 bits, Franke et al.--8 months, No perfect securityCracked =？