網(wǎng)路安全簡介

1、網(wǎng)路安全簡介張仁俊Jcchang.tw1資訊的趨勢共享的系統(tǒng)(Shared system)分散式系統(tǒng)(Distributed system)網(wǎng)路: Internet2資訊安全系統(tǒng)安全(System security)網(wǎng)路安全(Network security)3確保系統(tǒng)安全的方式使用者認(rèn)證控制使用權(quán)限(Access control)審查使用記錄4網(wǎng)路安全(Model)56安全攻擊7被動式攻擊(Passive attacker):讀取訊息內(nèi)容, 流量分析主動式攻擊(Active attacker):偽裝, 重播, 更改資料8網(wǎng)路安全的目的保護(hù)開放網(wǎng)路上資料的傳遞保護(hù)與網(wǎng)路相連之電腦內(nèi)部的資料針對

2、不同的需求建立安全系統(tǒng), 例如,安全電子郵件, 安全電子交易等.9網(wǎng)路安全的要求Confidentiality (privacy, secrecy):(機密性、隱私性、私密性)保護(hù)資料內(nèi)容的機密性.Authentication: (認(rèn)證、確認(rèn))確保通訊的可信性(包括來源及資料內(nèi)容)Integrity: (完整性、真確性)確保資料內(nèi)容的完整性10Non-repudiation: (不可否認(rèn)性、存證性)防止通訊雙方否認(rèn)先前的動作Access control: (存取控制)限制及控制對主機的存取權(quán)Availability: (可用性)確保系統(tǒng)能被合法使用者所使用11網(wǎng)路安全方法加密(Encrypti

3、on):機密性數(shù)位簽章(Digital signature):認(rèn)證及不可否認(rèn)性雜湊函數(shù)(Hash function)完整性安全協(xié)定(Secure protocols)General security12密碼學(xué)技術(shù)加密技術(shù)(Encryption)密鑰密碼系統(tǒng) (Secret-key cryptosystem): DES公鑰密碼系統(tǒng) (Public-key cryptosystem): RSA串流密碼(Stream cipher): LFSR數(shù)位簽章(Digital signature)RSADigital signature algorithm: DSAHashingSHA, MD513課程概要

4、基本概念:加解密演算法數(shù)位簽章演算法Hash functionetc.14通訊協(xié)定 安全登入系統(tǒng)認(rèn)證服務(wù)(Authentication Service)Email Security憑證管理(Certificate Management)Web Security安全電子交易Secure Electronic Transaction (SET)虛擬私人網(wǎng)路Virtual Private Network (VPN)etc.15系統(tǒng)安全侵入者(Intruders)病毒(Viruses)防火牆(Firewall)16侵入者(Intruders)Hacker, cracker, etc三種身份偽裝者濫用職

5、權(quán)者秘密滲透者1718偵察侵入行為Statistical anomaly(不規(guī)則) detectionThreshold detectionProfile basedRule-based detectionAnomaly detectionPenetration(穿透深度) identification審查紀(jì)錄一般的審查紀(jì)錄偵測用途的審查紀(jì)錄19病毒(Viruses)惡意的程式20病毒的分期潛伏期(Dormant phase)繁殖期(Propagation phase)觸發(fā)期(Triggering phase)發(fā)作期(Execution phase)病毒的類型Memory-resident v

6、irusBoot sector virusetc.21防毒方式使用合法軟體安裝防毒軟體先進(jìn)防毒技術(shù)數(shù)位免疫系統(tǒng)(Digital immune system)2223系統(tǒng)入侵對 Server 端的入侵IP SpoofingSniffing (Session Hijacking )取得密碼Other(如：Back door、權(quán)限設(shè)計缺失等)24正常連線時DABC1. A向網(wǎng)路上其他機器詢問B的IP2.D告訴B的正確IP位址DABC3.A和B交談ABCIP Spoofing25IP Spoofing時DABC1. A向網(wǎng)路上其他機器詢問B的IPABC2. C將自己的IP位址傳給AABC3&4. C介

7、於A和B之間，可任意妄為26ABCC竊聽A和B的談話ABCA和B彼此傳輸資料正常連線時Sniffing 時Sniffing27預(yù)防方式入侵途徑IP Spoofing =All layerHardware/ARP/ICMP/ Routing/DNS/TCP.Sniffing (Session Hijacking) = Low layer需硬體支援來配合軟體必須讓機器位在可竊聽之路徑上防堵方法Below routersStop using/Using Server/DetectBelow bridges/switchesHub 啟動防竊聽/建立 Security PathProtocol/Cryp

8、t/Zero Knowledge28入侵途徑取得密碼暴力式侵害法：用程式不斷嘗試到成功為止。字典式侵害法：依字典來算出加密後的密碼Other防堵方法啟動自動關(guān)閉帳號，停止使用一段時間。以分析來避免 weak密碼、強迫定期改變密碼29對 Client 端的入侵直接攻擊Ping of Death, Smurf, SYN, OOB.間接攻擊瀏覽器的漏洞Java, JavaScript, ActiveX, CGI, URL30Ping of Death 封包假設(shè)達(dá) 112,000 bytes目標(biāo)系統(tǒng)殺手封包正常封包最大為 65,536 bytes駭客系統(tǒng)直接攻擊Ping of Death (Win 9

9、5/NT 可抵抗)使用超過65,536 bytes標(biāo)準(zhǔn)封包大小的封包進(jìn)行攻擊，某些系統(tǒng)接到這些錯誤封包後便會當(dāng)機鎖死或重開機。31回應(yīng)封包目標(biāo)路由器Multiplenetworksubnets回應(yīng)封包川流不息的 Ping駭客系統(tǒng)從假造的IP位址發(fā)出Ping要求網(wǎng)際網(wǎng)路SmurfSmurf 攻擊是利用假造的IP位址欺騙被攻擊的系統(tǒng)，接著再向其所屬的子網(wǎng)路發(fā)出 PING 廣播要求，結(jié)果氾濫的垃圾封包便淹沒了整個網(wǎng)路。 32網(wǎng)際網(wǎng)路TCPSYN-ACK封包Backlog佇列假造來源和目的IP的Ping要求封包未完成的程序目標(biāo)系統(tǒng)駭客系統(tǒng)SYNSYN 攻擊模式利用建立連結(jié)時期的三個步驟，在送出初始封包

10、後，便不回應(yīng)接下來的部分，被攻擊系統(tǒng)佇列將因此而塞滿等待回應(yīng)的封包，由於佇列的空間有限，系統(tǒng)將無法再接受其他的進(jìn)入請求。33間接攻擊病毒特洛依木馬(Trojan Horse)Windows 95/98 中目前最盛行的有：Back Orifice (BO), NetBus, .瀏覽器的漏洞JavaJavaScriptActiveXCGIURL34加解密技術(shù)35傳統(tǒng)加密技術(shù)模型3637專門用語密文(Ciphertext): Y = EK(X)明文(Plaintext): X = DK(Y)例如：E100101(001110)=101000D100101(101000)=00111038密碼系統(tǒng)系統(tǒng)

11、明文空間 P (plaintext space)密文空間 C (ciphertext space)密鑰空間 K (key space)加密演算法 E (encryption algorithm)解密演算法 D (decryption algorithm)目標(biāo): 混亂訊息使其不可讀傳統(tǒng)加密方式one-key ciphersymmetric cipher39安全性假設(shè):E 已知D 已知只有密鑰 k 未知40無條件地安全(Unconditionally secure)無論有多少時間都不可能破密 只有one-time pad cipher 有此特性計算上的安全(Computationally secu

12、re)要破密所花費的時間金錢超過破密後的價值41密碼分析42暴力窮舉法Average time required for exhaustive key search43 Reference MagnitudeSeconds in a year3107Age of our solar system (years)6109Seconds since creation of solar system21017Clock cycles per year of a 500 MHz CPU1.61016Binary strings of length 553.61016Binary strings of

13、length 641.81019Binary strings of length 1283.41038Binary strings of length 2561.21077Number of 75-digit primes5.21072Electrons in the universe8.37107744古典加密技術(shù)替代密碼法Caesar CipherMonoalphabetic CiphersHill CipherRotor MachinesMulti-stage ciphers45Caesar Cipher已知最早的替代密碼法每個英文字位移 k 位plain:meet me after t

14、he toga partycipher:PHHW PH DIWHU WKH WEJD SDUWBKey:Plain: 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 zcipher: 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 CC = E(P) = (P + k) mod (26)P = D(C) = (C - k) mod (26)46只有25 個可能的 keyK=1 plain: oggv og chvgt vjg vqic rctvaK=2 plain: nffu nf bgfs

15、 uif uphb absuzK=3 plain: meet me after the toga partyK=4 = K=347觀察:加解密演算法都已知密鑰空間必須夠大以防止暴力窮舉法明文一般是可辨識的語言48Monoalphabetic Ciphers允許任意的替換A-F; B-R; C- G; . 有 26! (4 1026) 個可能的 keyExample:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTM

16、OHMQ49利用統(tǒng)計分析來攻擊.5051利用前面的柱狀圖，可以得知：Z = t, S = a, P = e, W = h.UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ t a e e te a that e e a aVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX e t ta t ha e ee a e th t aEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ e e e tat e the t再利用試誤法 Trial and error 得出全部訊息it was disclosed y

17、esterday that several informal butdirect contacts have been made with politicalrepresentatives of the viet cong in moscow52Hill cipher Key: 3x3 matrixK= 17 7 5 21 18 21 2 2 19Encryption: C=K 18 8 4T (mod 26) =20 9 24=uiyDecryption: P=K-1CK must have an inverse53Rotor Machines54Cipher 1Cipher 2Cipher

18、 nPCK1K2Kn. . .Multi-stage ciphers將多個密碼技術(shù)組合:55Tradeoff:More stages= more secure, more time, longer keyLess stages= less secure, less time, shorter key56Data Encryption Standard (DES)57歷史1971年由IBM 研發(fā)1977年 U.S. NBS (National Bureau of Standards)制訂為加密標(biāo)準(zhǔn), NBS後來改名NIST(National Institute of Standards and

19、Technology)64-bit 明文64-bit 密文56-bit 密鑰58大綱Simplified DES (S-DES)Substitution(替換) and permutation(排列)Data encryption standard (DES)運作的模式Block cipher 設(shè)計原則59Simplified DES (S-DES)精簡版的DES加密(Encryption)8-bit block of plaintext and 10-bit key as input8-bit block of ciphertext as outputE1111100000(11110000

20、)=10110101解密(Decryption)8-bit block of ciphertext and the same 10-bit key as input8-bit block of plaintext as outputD1111100000(10110101)=1111000060Seven functions密鑰產(chǎn)生(Key generation)P10: a permutation of 10 bitsShift: shift (rotate) the inputP8: a permutation of 8-bit加密(Encryption)IP: initial permu

21、tationfK: a complex functionSW: a switch function (swapping)IP-1: the inverse of IP6162Overview of S-DESK1=P8(Shift(P10(key)K2=P8(Shift(Shift(P10(key)Ciphertext = IP-1(fk2(SW(fk1(IP(plaintext)Plaintext = IP-1(fk1(SW(fk2(IP(ciphertext)63S-DES key generationP10 (1010000010)(1000001100) 1 0 1 0 0 0 0 0

22、 1 001 02 03 04 05 06 07 08 09 1003 05 02 07 04 10 01 09 08 06 1 0 0 0 0 0 1 1 0 0LS-1, LS-210000 01100)-(LS-1)-(00001 11000)-(LS-2)-(00100 00011)P8 (0000111000)(10100100) 0 0 0 0 1 1 1 0 0 001 02 03 04 05 06 07 08 09 1006 03 07 04 08 05 10 09 1 0 1 0 0 1 0 06465S-DES EncryptionInitial & final permu

23、tations1 1 1 1 0 0 1 11 2 3 4 5 6 7 8 IP2 6 3 1 4 8 5 71 0 1 1 1 1 0 11 0 1 1 1 1 0 11 2 3 4 5 6 7 8 IP-14 1 3 5 7 2 8 61 1 1 1 0 0 1 1IP-1(IP(X) = X6667函數(shù) fK最複雜的部分結(jié)合排列和替換fK(L, R)=(L F(R, SK), R)SK: A sub-key Ki (i = 1, 2, )L: input 的左邊 4 bitsR: input 的右邊 4 bitsF: A mapping from 4-bit strings to 4-b

24、it strings.假設(shè) input 為 (10111101) 且 F(1101, SK) = (1110)則 fK(10111101) = (1011) (1110), (1101) = (01011101)6869The mapping FInput: 4-bit number (n1n2n3n4).先做一個 expansion/permutation(E/P) 的運算然後和 sub-key SK 做 exclusive-or 運算例:Input: 1 1 0 1 1 1 1 0 1 0 1 1 1 2 3 4 0 1 0 1 0 0 1 1 SK E/P 1 0 1 1 1 0 0 0

25、 4 1 2 3 2 3 4 1 1 1 1 0 1 0 1 1 EP(1101) SK = (10111000)7071S-box左邊 4 bits 餵進(jìn) S-box S0 來產(chǎn)生 2-bit output.右邊 4 bits 餵進(jìn) S-box S1來產(chǎn)生另外 2-bit output.S-box 的4-bit input中, 第1、4 bits 用來決定要參考矩陣中的哪一列, 第2、3 bits 則用來決定要參考矩陣中的哪一行, 由此得出矩陣中的某一項, 然後將其化為二進(jìn)位表示式.72 Example:S0(0100)=3 or (11)2S1(0100)=2 or (10)273P4 f

26、unction: a 4-bit permutationP4(b1b2b3b4)=b2b4b3b1例:P4(S-box(01000100)=P4(1110)=10117475The switch function SW左邊 4 bits 和右邊 4 bits 互換.762nd Round 接著用相同的步驟再做一次, 只是所使用的 sub-key 不一樣.最後再經(jīng)過 IP-1 的運算7778例子密鑰: 1010000010Sub-key generationK1 = P8(LS-1(P10(1010000010) = (10100100)K2 = P8(LS-2(LS-1(P10(1010000

27、010) = (01000011)明文: 11110011IP(11110011) = (10111101)E/P(1101)K1= (11101011)(10100100) = (01001111)S0(0100) = (11), S1(1111) = (11), P4(1111) = (1111)F(1101, K1) = P4(S-box(E/P(1101)K1) = (1111)fK(10111101) = (L(F(R, K1), R) = (10111111, 1101) = (01001101)SW(01001101) = (11010100)Round 179E/P(0100)

28、K2= (00101000)(01000011) = (01101011)S0(0110) = (10), S1(1011) = (01), P4(1001) = (0101)F(0100, K2) = P4(S-box(E/P(0100)K2) = (0101)fK(11010100) = (L(F(R, K1), R) = (11010101, 0100) = (10000100)IP-1(10000100) = (01000001)密文: 01000001Round 280分析暴力攻擊法只有 210 = 1024 個可能的 Key K1, K2,給定 (P, C), 檢查E(K1, P)

29、=C ?E(K2, P)=C ?E(K1024, P)=C ?81Block cipher (區(qū)塊密碼)的原理Confusion (混亂):SubstitutionDiffusion (擴散):SwitchFeistel Cipher Structure:DES中 f-function 的結(jié)構(gòu)能夠保持 DK(EK(P)=P 而不用考慮函數(shù)是否可逆8283Block sizeKey sizeNumber of roundsSub-key generation algorithmRound functionFast software/hardware encryption/decryption84

30、85Data Encryption Standard (DES)背景1977 NBS (National Bureau of Standards, U.S.A., now NIST National Institute of Standards and Technology).規(guī)格64-bit 明文及密文56-bit 密鑰16 rounds8687Initial & final Permutations IP and IP-1:64-bit64-bitIPIP-188Expansion permutation (E): 32 bits-48bitsPermutation function (P

31、): 32 bits-32 bitsEP899091令明文 P = L0R0 , 第 i 個 round 之後產(chǎn)生的中間值表示成 LiRi 則密文 C = R16L16Key generation由密鑰 K 產(chǎn)生16 個 48-bit sub-keys Ki, 1i16.Single round i 的設(shè)計(Feistel cipher structure)Li=Ri-1Ri=Li-1F(Ri-1, Ki)928個 6進(jìn)4出的S-boxes Si, 0i7Encryption: Decryption:93Avalanche effect(雪崩效應(yīng))明文或密鑰中一點小小的改變會造成產(chǎn)生的密文很大

32、的改變尤其我們希望明文或密鑰中一個 bit 的改變能造成密文中一半的 bits 都改變94For exampleP1=0000 0000 0000P2=1000 0000 0000K=0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010結(jié)果在 L3R3 中有 21 bits 改變而在 L16R16 中則有 34 bits 改變9596運作的方式Electronic codebook mode (ECB)Cipher block chaining mode (CBC)Cipher feedback mode (CFB)Ou

33、tput feedback mode (OFB)97ECB mode最簡單的方式把明文切成每 64 bits 一個區(qū)塊使用相同的密鑰來對區(qū)塊加密加密過程就如同在查一本很大的密碼書 (codebook)98ECB modeEncryption:If P=P1P2Pm, where Pis are 64-bit blocks, then C=C1C2Cm=EK(P1)EK(P2)EK(Pm).99ECB modeDecryption:P= DK(C1)DK(C2)DK(Cm)=P1P2Pm.100CBC mode把要加密的區(qū)塊先跟前一個區(qū)塊所產(chǎn)生的密文做, 然後再跟密鑰做加密區(qū)塊 Pi 的加密和先

34、前所有的區(qū)塊有關(guān)101CBC modeEncryption:IV: 固定的 64-bit 初始向量(initial vector), 可以是公開的值或由發(fā)送方隨著密文傳給收受方C1=EK(IVP1)Ci=EK(Ci-1Pi), for i2. 102CBC modeDecryption:P1=DK(C1)IVPi=D(Ci-1)Ci-1=Ci-1PiCi-1103CFB mode明文切成每 j 個 bits 一個區(qū)塊, 一般令 j=8這種方式可說是DES的 stream cipher version104CFB modeEncryption:P=P1P2Pm,where Pis are j-b

35、it blocks, 1j64.定義 Sj(X) 表示 X 前 j 個 bitsR 是一個 64-bit 的暫存器, 初始值為 IV.R=IVC1=P1Sj(EK(R)R=Shift-Leftj|Ci-1Ci=PiSj(EK(R)i=i+1Decryption105106107OFB mode和 CFB 類似, 除了當(dāng)作下一個 encryption 的 input 是前一個 DES 的 output 而不是 cipher優(yōu)點在密文傳送過程中產(chǎn)生的 error 不會影響到所有區(qū)塊的解密108OFB modeEncryption R=IV C1=P1Sj(EK(R) R=Shift-Leftj|S

36、j(EK(R) Ci=PiSj(EK(R) i=i+1Decryption109110111Why 56-bit keys?At that time, It seems that 56-bit keys are secure. Facts:1997: distributed exhaustive key search all over the world takes 3 months.1998: specialized key search chips: 56 hours1999: the search devices are improved and achieved the record

37、of 22 hours112Double DESKey size K=(K1, K2): 112 bitsC=EK2(EK1(P)Meet-in-the-middleattackX=EK1(P) =DK2(C)113DEPM1M2MrK1, K2,.K1, K2,.N1N2NrC114Triple DESPlaintext: 64-bitCiphertext: 64-bitKey: 112 bitsK=(K1, K2)115Encryption: C=EK1(DK2(EK1(P)Decryption: P=DK1(EK2(DK1(P)Advantageskey size is larger和標(biāo)

38、準(zhǔn)的 DES 相容Set K1=K2=K (56-bit)P=EK(DK(EK(P)=EK(P)C=DK(EK(DK(P)=DK(P)116Block cipher 設(shè)計原則S-box:S-box 愈大愈安全然而需要額外的空間存 S-box.Number of rounds:Rounds愈多愈安全然而加密所花的時間相對地變長Key generation:Sub-keys 愈獨立愈好.117Advanced encryption standard (AES)118密鑰密碼的保密性119Packet-switchingrouterHost AHost B置放加密演算法的位置Link-to-link

39、 encryptionEnd-to-end encryption120Link-to-link EncryptionHost (主機) A(加密)-(傳送)-(解密) Router (路由器) 1(加密)-(傳送)-(解密) Router 2 Router n(加密)-(傳送)-(解密)Host (主機) B121122特性:網(wǎng)路設(shè)備(Host, Router)提供加密硬體實行提供 Host 間的身份認(rèn)證優(yōu)點:由網(wǎng)路設(shè)備提供加密, 應(yīng)用程式不需做修改缺點: 在路由器上訊息並未加密對所有 links 的兩端都需要做加解密123End-to-end EncryptionHost (主機) A(加密

40、)-(傳送)Router (路由器) 1Router 2Router n(傳送)-(解密)Host (主機) B124特性:發(fā)送端應(yīng)用軟體提供加密軟體實行提供 User 間的身份認(rèn)證優(yōu)點:訊息在傳送過程中是加密的只需要一次加解密的動作缺點: 需對應(yīng)用軟體做修改125OSI網(wǎng)路模型OSI(Open Systems Interconnection)分7層(layer):Application, Presentation, Session, Transport, Network, Data link, Physical加密演算法可以放在任一層放在較低層: 對應(yīng)用軟體來說是看不見的放在較高層: end

41、-to-end encryption126127哪些資料需加密依應(yīng)用的不同分成:Application-level encryptionTCP-level encryptionLink-level encryption如下頁所示(較黑部分表示需要加密)128129密鑰分配(Key Distribution)在A 和 B 之間建立一個 (session) key方法:由 A 選擇一把 key 然後秘密交給 B 由第三者 C 選擇一把 key 然後交給 A 和 B 如果 A 和 B 已經(jīng)有一把共用的 key , 一方就可以選擇一把新的 key 利用舊的 key 加密後交給另一方如果 A 和 B 都

42、有一個加密過的通道連接第三者 C, 則 C 就能透過此秘密通道分配 key 給 A 和 B130如果沒有第三者, N 個使用者必須事先建立 N(N-1)/2 把 secret keys131132如果有個第三者 (key distribution center, KDC), 則對 N 個使用者, 系統(tǒng)只需事先建立好 N 把 secret keys每個使用者都和 KDC 之間建立一把 secret key當(dāng)兩個使用者想傳遞資料時, 就可以請求 KDC 的協(xié)助來建立 (session) key 因為每個使用者和 KDC 之間都有一個加密的通道, 所以這種方法可行133Key Distributio

43、n Center (KDC)令 Kx 表示 KDC 和使用者 X 間的secret key因為這樣的 Kx 是好不容易才建立的, 所以 Kx 最好盡量少用, 因此傳遞資料時通常會建立一把 session key 給目前的交談使用Key distribution scheme:見下圖134135A transparent(透明的) key control scheme利用 front-end processor (FEP)步驟:Host 要求一個 packet connectionFEP 將要送的 packet 先放在 buffer 中, 然後跟 KDC 要求一個 session keyKDC

44、分配 session key 給兩邊的 FEP兩邊的 FEP 開始利用 session key 傳送 packet 136137Decentralized key distributionN 個使用者需要 N(N-1)/2 把 master keys每個使用者自己扮演 KDC 的角色如下圖MKm 表示 A 和 B 之間的 master key 138139亂數(shù)產(chǎn)生器(Random number generator)用途產(chǎn)生 secret keys and session keys.產(chǎn)生 public keys, 如 RSA.產(chǎn)生認(rèn)證過程中使用的 nonces Nonce: Number use

45、d at once140亂數(shù)序列的特性:Uniform distribution: 相同長度的 pattern 出現(xiàn)的機率應(yīng)該一樣 如 #(0)=#(1), #(00)= #(01)= #(10)= #(11), Independence: 無法由其他 bits 推出任一 bit.統(tǒng)計測試如果一個序列通過一些統(tǒng)計上的檢測則稱該序列為亂數(shù)序列141不可預(yù)測性(Unpredictability)給定一個序列, 無法由該序列推出下一個值真正的亂數(shù)是很難產(chǎn)生的, 一般我們用程式產(chǎn)生出一些有好的統(tǒng)計性質(zhì)的 pseudo-random numbers142Pseudo-random Number Gene

46、rator(PNG)Pseudo-random numbers 並不是真正的 random numbers.主要是利用一個短的真正亂數(shù) (seed) 來產(chǎn)生長的 pseudo-random number143Linear Congruential Generator參數(shù)a, c, m: integerX0: the seed (種子)演算法Xn+1=(aXn+c) mod m, for n0.Examplea=3, m=7, c=2, X0=1,then X1=5, X2=3, X3=4, X4=0, X5=2, X6=1, If gcd(a, m)=1, then the period T

47、is the maximum m-1.144Cyclic Encryption PNG145ANSI X9.17 PNG參數(shù)對第 i 個 generation stageDTi: 當(dāng)時 Date/Time 的 64 bits 表示式.Vi: seed value.Ri: 產(chǎn)生的Pseudo-random number K1, K2: Triple DES keys演算法146147Blum, Blum, Shub (BBS) Generator參數(shù)n=pq, where pq3 (mod 4),p and q are prime(質(zhì)數(shù)) and of the same lengthS is t

48、he seed, 1sn-1演算法X0=s2 mod n,Xi=Xi-12 mod n, for i 1Let Bi be the last bit of XiOutput: B1B2B3148Examplen = 192649 = 383503seed = 101355149150公鑰密碼系統(tǒng)151Why public-key system?發(fā)展 pub-key systems 的兩個理由密鑰分配 (Key distribution)在傳統(tǒng)密鑰密碼系統(tǒng)中, 使用者必須透過秘密通道或 KDC 的協(xié)助來達(dá)成密鑰共用, 十分不方便如果透過 KDC 的協(xié)助, 則 KDC 將會知道使用者的密鑰, 並不

49、安全數(shù)位簽章 (Digital signature)在商業(yè)用途或身份證明方面, 需要簽章的機制152雖然公鑰系統(tǒng)的目標(biāo)是解決密鑰分配的問題, 它卻只能降低其複雜度然而, 針對某些特殊的領(lǐng)域, 例如電子商務(wù) (Electronic commerce, EC), 公鑰系統(tǒng)提供了許多有用的應(yīng)用153比較154公鑰系統(tǒng)的安全性每個使用者 A 選擇一把公鑰 (public key KUa), 一把私鑰 (private key KRa)將公鑰 KUa 公開, 使其他使用者能取用當(dāng)使用者 B 要傳送訊息給 A 時, 首先去取得 A 的公鑰 KUa, 利用該公鑰來加密訊息 EKUa(P)=C, 將密文 C

50、傳給 A當(dāng) A 收到 C= EKUa(P) 之後, 利用自己保管的密鑰 KRa 來做解密 DKRa(C)=DKRa(EKUa(P)=P155156157身份認(rèn)證 (Authentication)一些公鑰系統(tǒng), 例如 RSA, 能夠提供身份認(rèn)證的服務(wù), 因為在這些系統(tǒng)中其加密和解密能互換, 即 EKUa(DKRa(M)=M.當(dāng)使用者 A 想要證明某份文件 P, 他就計算 y = DKRa(P).當(dāng)使用者 B 收到 (P, y), 他就去驗證是否 EKUa(y) = P.這份文件 P 能被 y 所證明因為只有 A 知道 KRa, 因此 B 確定這份文件 P 是 A 傳送過來的158159數(shù)位簽章

51、(Digital signature)我們稱這樣的 y 為使用者 A 利用 (KUa, KRa) 對文件 P 做的數(shù)位簽章最重要的地方在於：數(shù)位簽章是由私鑰及文件所計算出來所以, 對不同的文件所簽出來的簽章也不一樣Public-key systems 能達(dá)成機密性 (confidentiality) 和認(rèn)證 (authentication) 兩種用途160161Public-key System 的種類EncryptionRSA, ElGamalDigital signatureRSA, ElGamal, DSA (digital signature algorithm)Key exchang

52、e without trusted serverDiffie-Hellman key exchange162Public-key service Alice: KUa; Bob: KUb; EncryptionDecryptionAliceBobMCMKUbKRbKUb163Public key 的產(chǎn)生對任一使用者來說, 選擇自己的 (公鑰, 私鑰) 必須是容易的然而另一方面, 對其他的使用者來說, 想要由某人的公鑰去推得其私鑰必須是很困難的這似乎有點矛盾, 但是透過 trapdoor one-way functions 的觀念即可達(dá)成164Public key cryptanalysis公鑰

53、密碼系統(tǒng)至少必須能抵抗 chosen plaintext attack (因為加密演算法及公鑰是公開的)攻擊者必須無法由公鑰推出私鑰Trapdoor one-way functions 具有這樣的特性O(shè)ne-wayTrapdoor165RSA public-key systemRivest, Shamir, Adleman, 1977RSA key generationRSA encryption algorithm with public keyRSA decryption algorithm with private key166數(shù)論a|b 表示 a 整除 b, 如 7|35If b|g

54、and b|h, then b|mg+nh.質(zhì)數(shù), 如 2, 3, 5, 7, 11, 13, 17, 19, 23,.互質(zhì), gcd(a, b) = 1標(biāo)準(zhǔn)分解式, 如 3600=243252 167Modular 計算a mod n例如5 mod 3=2.-11 mod 7=-11+14=3.Congruent modulo nab (mod n) a mod n = b mod n n|a-b.例如27 (mod 5).(a mod n b mod n) mod n = (a b) mod n.(a mod n b mod n) mod n = (a b) mod n.168整數(shù)域 Zn

55、Zn=0, 1, 2, , n-1.Zn*=i | 1 i n, gcd(i, n)=1.例如Z6=0, 1, 2, 3, 4, 5Z6*=1, 5.169乘法反元素a-1 mod n is the number b such thatab1 (mod n).例如4-1 mod 7=2.170Eulers Phi-function|Zn*|=(n):比 n 小且跟 n 互質(zhì)的數(shù)的個數(shù)If gcd(m, n)=1, then (mn)=(n)(n).171Euclidean Algorithm (輾轉(zhuǎn)相除法)找 gcd(m, n).利用這個演算法if gcd(m, n)=1, 我們能找到一組 a

56、, b 使得am+bn=1.This is called the Extended Euclidean algorithm.因為 am+bn=1 即 am=1-bn 1 (mod n) 所以ma-1 mod n 172Extended Euclidean algorithm (d, f):Output d-1 mod f1. (X1, X2, X3)(1, 0, f); (Y1, Y2, Y3)(0, 1, d);2. If Y3=0, then return X3=gcd(d, f); no inverse3. If Y3=1, then return Y3=gcd(d, f): Y2=d-

57、1 mod f4. Q=X3/Y35. (T1, T2, T3)(X1-QY1, X2-QY2, X3-QY3)6. (X1, X2, X3)(Y1, Y2, Y3)7. (Y1, Y2, Y3)(T1, T2, T3)8. Goto 2.173Input (d, f)=(550, 1769), output d-1=550174Eulers 定理If gcd(a, n) = 1, then a(n) 1 (mod n)例如28 mod 15=1 since (15)=8.175RSA Key Generation使用者產(chǎn)生自己的 公鑰-私鑰對的方法私下選擇兩個質(zhì)數(shù) p 和 q.計算 n =

58、pq選擇一個數(shù) e, 1 e (n) 使得 gcd(e, (n)=1, where (n)=(p-1)(q-1)計算 d, 1 d (n) 使得 ed 1 ( mod (n) ). 即 d e-1 mod (n)176The public key is (e, n)對所有人公開The private key is (d, n)自己秘密地保管把 p 和 q 的值丟掉例如choose p = 7, q = 17,therefore, n = 119 and (n)=(7-1)(17-1)=96.choose e=5 and compute d=77 since 577 mod 96=1.The p

59、rivate key KR is (77, 119).The public key KU is (5, 119).177RSA Encryption假設(shè)收方的 public key 是 (e, n)Encryption algorithm: for a message M, 0Mn, C = E(e,n)(M) = Me mod n例如For M=19 n, (e, n)=(5, 119)C=195 mod 119= 66178RSA Decryption假設(shè)收方的 private key 是 (d, n)Decryption algorithm:for C, 0Csqrt(n)Mathema

60、tical attacks:分析 n 的結(jié)構(gòu)找 p 和 q選擇好的質(zhì)數(shù)(強質(zhì)數(shù))p-1 和 q-1 要有大的質(zhì)因數(shù)gcd(p-1, q-1) 要小189Public Keys 的分配Man-in-the-middle attackAliceBobActive attackercomputesM=D(dC,nC)(C)(eA, nA)(eC, nC)E(eA, nA)(M)C=E(eC, nC)(M)190任何人將自己的公鑰傳給其他人191利用 public-key directory 存放使用者的公鑰 192Bob 必須去驗證收到的公鑰真的是 Alice 給的利用一個可信任的代理人 (publ