信息安全基础2(密码编码学与网络安全).ppt

《信息安全基础2(密码编码学与网络安全).ppt》由会员分享，可在线阅读，更多相关《信息安全基础2(密码编码学与网络安全).ppt（181页珍藏版）》请在装配图网上搜索。

1、Chapter 2 Cryptography,2012,Foundation of Information Security,1,2,3,4,Overview,Overview of Cryptography,Classical Ciphers,Block Ciphers,5,6,1 Overview of Cryptography,1.1 History of Cryptography,1.2 Cryptosystem,1.3 Cryptanalysis,1.4 Cryptography,Before 1949 Classical Encryption古典加密 Before computer

2、 was invented, cryptography was art more than science. There were some cipher algorithms, encryption machines Germany (Enigma), Japan (Purple), Sweden (Hagelin),Rotor Machine (cont d),Each rotor corresponds to a substitution cipher A one-rotor machine produces a polyalphabetic substitution cipher wi

3、th 26 alphabets After each press, the rotor is rotated 旋转 by one scale Output of each rotor is input to next rotor After a full-round rotation, the adjacent rotor is rotated (like odometer里程表) by one scale - An 3-rotor machine produces 263=17576 alphabets,Three-Rotor Machines,3 Steganography 隐写术,Hid

4、e messages in other messages An alternative to encryption - encryption: make information unreadable - steganography: hide message to conceal its existence Simmons Prisoner Problem (1983) 囚犯问题 Art of covered writing - Character marking - Invisible ink - Pin punctures - First letter of each word 藏头诗 -

5、 Letter position on page - Typewriter correction ribbon - Microdots 微缩胶片 Drawbacks - high overhead to hide relatively few info bits by using redundancy of media,Example,News Eight Weather: Tonight increasing snow. Unexpected precipitation Smothers Eastern towns. Be extremely cautious and use snowtir

6、es especially heading east. The highway is not knowingly slippery. Highway evacuation is suspected. Police report emergency situations in downtown ending near Tuesday First letter of each word yields: Newt is upset because he thinks he is President This example was created by Neil F. Johnson, and wa

7、s published in Steganography,Technical Report TR_95_11_nfj, 1995. From WWII German spy (Kahn): Apparently neutrals protest is thoroughly discounted and ignored. Isman hard hit. Blockade issue affects pretext for embargo on by products, ejecting suets and vegetable Oils. Second letter of each word yi

8、elds: Pershing sails from NY June 1.,Exercise,What is the message embedded in the left figure?,LSB algorithm,Least Significant Bit 最低有效位 - For digital image, modify the low bits denoting colors to hide information - A pixel contain 24-bit RGB color information, the LSB of which can be changed withou

9、t greatly affecting the quality of the image - Advantages: simple, fast - Disadvantages: may be destroyed by some information processing, e.g. signal transforming, size compression,Digital Watermark 数字水印,By adding an undetectable copyright 版权 information (exclusive identity 唯一标识符 or serial number) t

10、o digital media, digital watermark can be extracted (when needed) to be a proof of unauthorized copy. Characteristic: embed or extract copyright information into or from the host media without affecting the normal use of the host. Requirement: transparent 透明性, robust鲁棒性 Compared with covered writing

11、 same technology but for different aim whether the algorithm and key used is public or private,Digital Watermark (contd),4 Block Ciphers,4.1 Block Cipher Principles,4.2 Feistel Cipher Structure,4.3 DES Cipher Algorithm,4.1 Block Cipher Principles,Modern ciphers One of the most widely used cryptograp

12、hic algorithms Provide secrecy/authentication services Mostly based on a Feistel Cipher Structure Using idea of a product cipher,Stream Ciphers else for machine, calculate Cm1=E(M,Km). for attacker, get Ca directly. if Ca=Cm1, then Km=Ka, exit.,Triple DES (112/156-bit key),C = EK3(DK2(EK1(P) P = DK1

13、(EK2(DK3(C) Backwards compatible with existing single DES (K1 = K2 = K3) Two-key TDES (K1 = K3) or three-key TDES Security of TDES - no known practical attacks - brute force search impossible (O(2112), O(2168) Major disadvantage is speed (3x slower),5 Public Key Cryptography,5.1 Principles of Public

14、-Key Cryptosystems,5.2 RSA Algorithm,Drawback of Conventional Cryptography,Hard for key distribution Complex for key administration Difficult for digital signature,Secret-Key Cryptography - Secret /single key cryptography uses one key, shared by both sender and receiver - If this key is disclosed, c

15、ommunications are compromised - Because of symmetric, parties are equal, hence cant prevent the sender from denying sending a message, and cant prevent the receiver forging a message in this case, e = 7 5. Determine d. de 1 mod 160 and d (n). The correct value is d = 23 (7 23 = 161 = 160 + 1) 6. PU

16、= 7, 187, PR = 23, 17, 11, 160,Security Analysis,PU = e, n, PR = d, p, q, (n) d (n) p, q factoring n,Exchangeability,D(E(M)=(Me)d=Med=(Md)e=E(D(M) mod n Guarantee secrecy & authentification, e.g. encryption & digital signature,Reversibility,In RSA: - carefully chosen e & d to be inverses mod (n) - h

17、ence e*d=1+k*(n) for some k D(E(M,PU),PR)=M Cd = (Me)d = M1+k*(n) To proof M1+k*(n) mod n = M (M,n)=1, M(n) mod n = 1 (Eulers Theorem) left= M*(M(n)k = M*(1)k = M (mod n) = M =right, (M,n)1, assume: (M,n)=p M=ap Mn q is a prime number (M,q)=1 M(q)=1 mod q(Eulers Theorem) Mk(p-1)(q)=1 mod q (q)=q-1 M

18、k(n)=1 mod q Mk(n)=bq+1 Both left & right is multipled by M：Mk(n)+1=bqM+M=abpq+M=abn+M mod n：Mk(n)+1=M mod n,Computational Aspects,Encryption and Decryption - Both require modular exponentiation, using square and multiply - Acceleration of computation using CRT cf. P173 &P194 Key Generation - Determ

19、ining two prime numbers, p and q (Miller-Rabin Test) cf. P171 &P194 - Selecting e and calculating d (Euclid Algorithm),Modular Exponentiation 模幂,(a*b) mod n = (a mod n)*(b mod n) mod n ab mod n = (a mod n)b mod n 887mod 187=(884 mod 187)*(882 mod 187)*(881 mod 187) mod 187 881mod 187=88 882mod 187=8

20、82 mod 187=77 884mod 187=772 mod 187=132 887mod 187=(88*77*132) mod 187=11,Use the Square and Multiply Algorithm 反复平方乘 A fast, efficient algorithm for exponentiation Look at binary representation of exponent 指数 Only takes O(log2b) multiples for number b,Modular-Exponentiation (a, b, n) 1.c 0 f 1 2.l

21、et bkbk-1b0 be the binary representation of b 3.for i k downto 0 do c 2 c f (f f) mod n if bi = 1 then c c+1 f (f a) mod n 4.return f,Example,ab mod n, a=7, b=560=1000110000, n=561 The smaller e, faster exponentiation, more dangerous - Often choose e = 65537 (216 + 1) - Also see choices of e = 17 If

22、 e fixed, must ensure gcd(e, (n) = 1,Calculate Inverse 求逆,Calculate gcd (Greatest Common Divisor，最大公约数) by Euclid Algorithm 欧几里德算法 gcd(a,b)=gcd(b,a mod b) Gcd(156,117) 156=1*117+39 117=3*39+0 gcd156,117=39,Euclid (a, b) 1.A a B b 2.If B=0 return A=gcd (a, b) 3.R=A mod B 4.A B 5.B R 6.goto 2,Given a

23、& b, calculate b-1, let bb-1= 1 mod a gcd(a,b)=1 1=xa+b-1b (mod a) Example a=35,b=13,b-1=? 35=2*13+9 13=1*9+4 9=2*4+1 4=4*1+0 -gcd(a,b)=1 1=9-2*4=9-2*(13-1*9)=3*9-2*13 =3*(35-2*13)-2*13=3*35-8*13 1=3*35+(35-8)*13 (mod 35) b-1=35-8=27,Question a=40, b=17, b-1=?,9=35-2*13 4=13-1*9 1=9-2*4,Attacks on R

24、SA Algorithm,Brute force (Key space search) - Try all possible private keys - Use large keys Mathematical Attacks - Several approaches, all equivalent to factoring Timing attacks 计时攻击 - Based on the running time of the decryption algorithm Chosen ciphertext attacks - Exploit properties of the RSA, e

25、.g., multiplicative property: f(xy) = f(x)f(y),Mathematical Attacks,For a large n with large prime factors, factoring is a hard problem RSA factoring challenge - Sponsored by RSA Labs - To encourage research into computational number theory and the practical difficulty factoring large integers - The

26、 length of n is between 1024 to 2048 bits for security currently,Timing Attacks,Big integer multiplication takes a long time By observing the time taken for modular multiplication, it is possible to infer bits in d (PR) - If di is 1, f (f a) mod n will be executed (It may be much slower than the cas

27、e of di = 0, for special “a”, given that the special value “a” are known to attacker) - By designing values of a (ciphertext), and observing the execution (decryption) times carefully, values of dkdk-1d0 (private key) may be inferred Only depend on the ciphertext,Timing Attack Countermeasures,Consta

28、nt exponentiation time - Ensure that all exponentiations take the same amount of time - Simple fix, but degrade the performance Random delay - Add a random delay to the exponentiation algorithm to confuse the timing attack Blinding 隐蔽 - Multiply the ciphertext by a secret random number before perfor

29、ming the exponentiation to destroy the known a - RSA Data Securitys blinding method Generate a secret random r, 0 r n-1 Compute C = Cre mod n, where e is the public exponent Compute M = (C)d mod n Compute M = M r-1 mod n = (Cre)dr-1 mod n = Cd mod n - 2% to 10% performance penalty,Chosen Ciphertext

30、Attack,RSA is vulnerable to a chosen ciphertext attack (CCA) - Choose ciphertexts & gets decrypted plaintext back - EPU(M1) EPU(M2) = EPU(M1 M2) A simple example of a CCA against RSA - Can decrypt C = Me mod n using a CCA Compute X = (C 2e) mod n Submit X as a chosen ciphertext and receive back Y =

31、Xd mod n Y = Xd mod n = (C 2e)d mod n = Cd 2 (mod n) = 2M (mod n) M = Y*2-1(mod n) To counter such CCAs, the plaintext requires random padding such as OAEP(Optimal Asymmetric Encryption Padding，最优非对称加密填充) prior to encryption,Encryption Using OAEP,6 Stream Ciphers (Sequence Ciphers),Shannon proved th

32、e one-time pad system to be unconditional security绝对安全 in 1940s Key密钥 is as long as the message, with no repetitions Plaintext明文 and ciphertext密文 are statistically independent Application Difficulty Generation and distribution of the real-random真随机 and endless-long key sequence,Stream Cipher,Princip

33、le: imitate one-time pad, generating long key stream of good pseudo randomicity 伪随机性 by short root key Core: process message bit by bit as a stream, XOR with key stream,XOR Example,Plaintext M: 0 1 0 1 0 1 0 1 k (from K): 1 0 1 0 1 0 1 0encryption Cipertext C: 1 1 1 1 1 1 1 1 k (from K): 1 0 1 0 1 0

34、 1 0 decryption Plaintext M: 0 1 0 1 0 1 0 1,RC4 Overview,Ron Rivest designed in 1987, simple but effective Variable root key size (1256 bytes) key period 10100 Widely used in real-time communication (Web SSL/TLS, Wireless WEP) Key forms by random permutation 随机置换 of all 8-bit values from 0 through

35、255,S K keylen T (a) initial state of S and T,RC4 Step1initialization state,RC4 Steps2initial permutation,T S,swap,j=j+Si+Ti,(b) initial permutation of S,j=j+Si S swap t=si+sj k (c) Stream Generation,RC4 Step3stream generation,m,Initial state and initial permutation,Starts with an array S of numbers

36、: 0.255 Use key K to well and truly shuffle S forms initial state of the cipher for i = 0 to 255 do Si = i Ti = Ki mod keylen) j = 0 for i = 0 to 255 do j = (j + Si + Ti) mod 256 swap (Si, Sj),Stream Generation,Encryption continues shuffling array values Sum of shuffled pair selects stream key value

37、 from permutation Xor St with next byte of message to en/decrypt i = j = 0 for each message byte Mi i = (i + 1) mod 256 j = (j + Si) mod 256 swap(Si, Sj) t = (Si + Sj) mod 256 Ci = Mi XOR St,Example,Plaintext: security 73 65 63 75 72 69 74 79 (ASCII code) Key: 12345 31 32 33 34 35 (ASCII code) n: 8 (entry number of S & T instead of 256) S00 01 02 03 04 05 06 07 T 31 32 33 34 35 31 32 33 SP06 00 01 04 03 07 05 02 k 05 02 07 07 04 01 05 04 M 73 65 63 75 72 69 74 79 encryption C 76 67 64 72 76 68 71 7D k 05 02 07 07 04 01 05 04 decryption M 73 65 63 75 72 69 74 79 security,Thank you,2012,