1、李榮三 博士國立中正大學資訊工程學系,資訊安全技術的發展與應用,MSN lab,2,Outline,古典密碼學現代密碼學模糊傳輸電子商務應用視覺密碼學,MSN lab,3,清朝密碼學家, 精神炯炯 老貌堂堂 烏巾白髯 龜鶴呈詳-紀曉嵐,MSN lab,4,納瓦荷族密碼兵,二次大戰,MSN lab,5,傳統密碼學,傳統密碼學,換位法,代換法,(1),反轉換位,(2,),行換位,古典密碼學,MSN lab,6,明文：MEET ME MONDAY MORNING密文：GNINROM YADNOM EM TEEM,換位法（1）反轉換位,MSN lab,7,換位法（2）行換位,明文：SHIP EQUIP
2、MENT ON THE FOURTH OF JULY,密文：TOFUS OFOIH NJUPI TURMP HLTEE EYHNQ(橫取)金鑰：3-5-4-2-1(數字),MSN lab,8,代換法（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=此字集
3、的大小。,明文：SECURE 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,MSN lab,11,現代密碼學,對稱式加密系統公開金鑰加密系統數位簽章盲簽章,MSN lab,12,對稱式加密系統,1976年美國國家標準局公佈
4、為資料加密標準DES (Data Encryption Standard)。十六回合：擴充轉換、二進位加法、代換轉換、排列轉換,Key,明文,密文,密文,明文,MSN lab,13,安全?,金鑰 56 bits (256 1017)若破解速度 106 key/sec 3 *1013 keys/yr使用暴力搜尋需要約 3000年。但如果使用106 台電腦同時運轉， 則只需 3*103/ 106 26.28 小時即可破解。,MSN lab,14,Triple DES,K1=K2 K3, 112bitsK1=K2=K3, 168bits,K1,明文,密文,密文,明文,K2,K3,MSN lab,15
5、,2000年Vincent Rijmen and Joan DaemenRijndael Algorithm128, 160, 192, 224, 2562002年美國國家標準局公佈為資料加密標準AES (Advanced Encryption Standard)。AES-128(10), AES-192(12), AES-256(14)Memory, Efficiency,MSN lab,16,公開金鑰加密系統,Diffie, Hellman, 1976Rivest, Shamir, Adleman(RSA), 1977Factorization ProblemElGamal, 1985 D
6、iscrete Logarithm Problem,MSN lab,17,Rivest, Shamir, Adleman(RSA),取兩個質數 p = 17, q = 11計算 N = pxq =187, (N) = (p-1)(q-1)=160選定公鑰e = 7，(e必須與(N)互質)計算出私鑰d 滿足ed = 1 mod (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,安全基礎因數分解問題,(N) = (p-1)(q-1)，如果
7、知悉公開參數N的兩個質因數(p, q)，則(N)的值將無秘密可言。由於e為公開訊息，並且滿足ed = 1 mod (N)，因此如果(N) 為外人知悉，則可利用歐式演算法計算出私鑰d的值。如果可以有效率地執行因數分解，則RSA密碼系統毫無安全性可言。,MSN lab,19,因數分解問題,15 = 3591 = 7132173 = 41533776111 = 188919991522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 = ?,MSN lab,
8、20,RSA-200,27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983,MSN lab,21,200 digits, 663 bitsMay 9, 2005, Franke et al.2.2 GHz CPU-55 years80 2.2 GHz
9、CPU-3 months,MSN lab,22,Factors = 35324619344027701212726049781984643686197400197625023649303468776121253679423200058547956528088349and 7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467,MSN lab,23,30,000 USD. RSA-704 =,740375634795617128280467960974
10、29573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359212 digits,MSN lab,24,100,000 USD. RSA-1024 =,135066410865995223349603216278805969938881475605667027524485143851526510
11、604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563309 digits,MSN lab,25,200,000 USD. RSA-2048 =,25195908475657893
12、494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422
13、433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
14、 617 digits,MSN lab,26,數位簽章與憑證(RSA),Certificate Authority (CA)- Alice ed = 1 mod (N)Public key (e, N) ; 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 mo
15、d NAlice: s = (m)d =mdr mod NBob: s = sr-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,Message query,MSN lab,29,t-out-of-n,Alice,Bob,Request t messages,messages,Stocks,Message query,3
16、. Privacy of Alice,2. Privacy of Bob,1. Correctness,MSN lab,30,Chinese Remainder Theorem (CRT),To find a positive integer 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
17、, d2, , dn: n relatively 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 d1),C a2 (mod d2),C an (mod dn).C = (D/d1)y1a1 + (D/d2)y2a2 + + (D/dn)ynan mod D
18、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: 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,
19、Alice,Step 1:1 = 1d = r1ed * T1d = r1 * T1d mod N,2 = 2d = r2ed * T2d = r2 * T2d mod N,t = td= rted * Ttd = rt * Ttd mod N, Step 2: Sends 1,2, , t to Bob,MSN lab,37,Bob,Step 1: d1 = r1-1 *1 = T1d = d1 ed mod N,d2 = r2-1 *2 = T2d = d2 ed mod N,dt = rt-1 *t = Ttd = dt ed mod N. Step 2:b1 = C mod d1,b2
20、 = C mod d2,bt = C mod dt.,MSN lab,38,Comparisons,MSN lab,39,電子商務應用,MSN lab,40,電子支票,先交易後付款 金額較大的交易 簽名效果公開金鑰系統的數位簽章驗證付款者和銀行的身份 數位憑證,MSN lab,41,電子支票,消費者,網路商店,消費者開戶之銀行,商店開戶之銀行,票據所,1.選擇商品，並決定以電子支票付款,2.驗證支票,4.存入電子支票,5.票據處理與匯款,3.傳送商品,6.更新帳戶資料,MSN lab,42,電子旅行支票,傳統旅行支票個人使用 護照簽章仿冒護照-盜領電子Smart card聲紋、指紋先付款公開金
21、鑰系統的數位簽章,MSN lab,43,電子旅行支票,旅行者,1.核發憑證,開票銀行,憑證中心,1.核發憑證,1.核發憑證,2.購買電子旅行支票,3.要求兌現,4.請求驗證,5.同意放款,6.傳送現金,7.結算金額,MSN lab,44,電子競標,English auction: Yahoo, ebayDutch auctionSealed-bid auction數位簽章技術 通訊金鑰,MSN lab,45,English Auction,競標者,拍賣商,3.產生標單,2.確認無誤後廣播,OK,4.確認標單公佈最高價,MSN lab,46,Sealed-bid/Dutch auction,3.
22、傳送標單,1.要求競標,1.要求競標,2.確認無誤後廣播,OK,3.傳送標單,1.要求競標,4.公佈得標之最高價,MSN lab,47,電子投票,傳統時間限制地理限制開票慢電子任何時間任何地點高效率合法性-公開金鑰技術正確性-AES匿名性-盲簽章,MSN lab,48,電子投票,註冊中心,計票中心,投票者,轉址伺服器,憑證中心,2.要求選票,3.要求盲簽章,4.送出選票,1.協調共享金鑰,5.轉換選票位址,6.傳送選票,7.公開選票結果,MSN lab,49,視覺密碼學,MSN lab,50,Counterfeit Transparency 1,Counterfeit Transparency
23、 1+ Basis Transparency=secret information: “中國人的世紀”,Basis Transparency,MSN lab,51,SecretInformation,Basis Transparency(Random Dots),Counterfeit Transparency,Picture,MSN lab,52,SecretInformation,Basis Transparency(Random Dots),Counterfeit Transparency,Stack,MSN lab,53,3*3像素擴充法,白,白,白,白,黑,黑,黑,黑,MSN lab
24、,54,Case 2,Secret image,Basis transparency,Counterfeit transparency,Counterfeit picture,MSN lab,55,Basis Transparency,MSN lab,56,Counterfeit Transparency 1,Counterfeit Transparency 1+ Basis Transparency=secret information: “中國人的世紀”,Basis Transparency,MSN lab,57,Counterfeit Transparency 2,Counterfeit
25、 Transparency + Basis Transparency=secret information: “電腦密碼學”,Basis Transparency,MSN lab,58,白,白,白,黑,白,黑,白,白,黑,黑,白,白,白,黑,白,黑,黑,黑,白,黑,黑,黑,黑,白,3*3像素擴充法 (有意義),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 =？insecure,Thanks!,資訊安全技術的發展與應用,
