- PDF 무료 다운로드

Size: px

Start display at page:

Download ""

동영 지
8 years ago
Views:

3 (Cryptology) (Block) (Stream) (Public Key) (Probabilistic Encryption),, (Key Key Management System),, (confidentiality) (authentication) (. ) (data integrity) (notorization) (access control) (availability)

4 (Cryptology) confidentiality Data integrity authentication Non-repudiation Encryption Data integrity Techniques Message authentication identification Digital signatures Stream ciphers Block ciphers Public-key encryption Unkeyed hash functions keyed hash functions signatures Random number generation Public-key parameter Key management Establishment of secret keys (Encryption) PSTN ISDN

Block ciphers Public-key encryption Unkeyed hash functions keyed hash functions signatures

5 (Encryption),, (CONVENTIONAL) = (Secret Secret-key) = (Symmetric Symmetric-key) = (PUBLIC KEY) = (Asymmetric Asymmetric-key) = : DES, SKIPJACK, RSA, ElGamal, ECC IDEA, AES, SEED : A5, LILI, f8, RC4 (, )

6 m n n n m DES, IDEA, SKIPJACK AES, SEED : A5, RC4 =

7 ( ) (insecure) : ISDN() (secure) : (?) ---> 1. :, 2.

8 = = ( ) ( ) 1. n C 2 =n(n-1)/2 ---> n ( ) 2. ( ) 3. ()

9 Dyejsmldmnf mdfnmd,sdd fnfnfnlkfekkfe ekfkjefjefelfee (Hash Algorithm Standard) HAS-160 append padding bits input ( 512bit) append length block...80 blocks of 32 bits... f g ROLs2 A B C D ROLs1 ADD E

10 ( ) = ( ) =

11 (Security)

13 ( ) LFSR

14 LFSR A5 (A5 Stream cipher)

15 A5 A5

19 DES , Water Tuchman Carl Meyer lucifer cipher DES 5 ANSI

20 DES DES (substitution) (permutation) (confusion) : 1 2. (diffusion) : DES,. DES Plaintext IP L 0 R 0 f L i = R i -1 R i = L i-1 f(r i-1, K i ) K 1 L 1 = R 0 R 1 = L 0 f (R 0,K 1 ) L 15 = R 14 R 15 = L 14 f (R 14, K 15 ) f R 16 = L 15 f (R 15, K 16 ) L 16 = R 15 IP -1 K 16 Ciphertext

21 IP(Initial Permutation) IP IP DES IP 58 -> 1 / 50 -> 2 IP > 58 / 2 -> 50 f Function R (32bit) DES E S1 S2 S3 S4 S5 S6 S7 S8 P Output (32bit)

22 DES S-BOX ( ) : Input ( ) : Output DES 1, 2, 3,,64 PC 1 C0 D0 1, 2, 3,,28 1, 2, 3,,28 LS 1 LS 1 C1 D1 1, 2, 3,,28 1, 2, 3,,28 PC 2 K1 LS 2 LS 2 C2. D2. LS 16 LS 16 PC 2... K2 C16 D16 PC 2 K16

23 E D E C = EK1[DE [DK2[EK1[P]]][P]]] D E D P = DK1[ED [EK2[DK1[C]]][C]]] Multiple Encryption

24 Key Length : 16,24,32 bytes Block Size : 16,24,32 bytes speed compact SP-Network code Operation over GF(2 8 ) extension field Plaintext ByteSub ShiftRow MixColumn AddRounKey Nr-1 round ByteSub ShiftRow MixColumn AddRounKey final round ByteSub ShiftRow AddRounKey Ciphertext Key schedule Cipher Key Initial Round Keyaddition Nr-1 1 Rounds final round

25 Block Size : 16 byte(128 bit) 24 byte(192 bit) 32 byte(256 bit) Key Size : 16 byte(128 bit) 24 byte(192 bit) 32 byte(256 bit) S-box(substitution table) (non-linearity) 1-byte(State) GF(2 8 ) Affine (over GF(2)) transformation

26 International Data Encryption Algorithm)

28 Single Iteration of IDEA X 1 X 2 X 3 X 4 Z 1 Z 2 Z 3 Z 4 Z 5 Z 6 w 11 w 12 w 13 w 14

29 SEED 16round DES feistal F SEED DES F

30 RSA RSA ISDN() A B p A,q A,d n A A =p A q A,e A n B =p B q B,e B pb,q B, d B A B M A : B e B M eb mod n B = C B d B C db mod n B =M ebdb mod n B =M

31 RSA φ (n) φ (n) φ (n) RSA

32 RSA M φ ( n ) mod n = 1 φ (n) e d Y = f k (X) X = f -1 k (Y) k Y ed mod φ( n) = 1 M e mod n = C C d = M mod n e = ( M ) d kφ ( n) + 1 = M mod n mod n mod n ( ed modφ( n) = 1 ed = kφ( n) + 1) X = f -1 k (Y) e infeasible M mod n M or d Y k

33 RSA p, q p q n = p q φ( n) = ( p 1)( q 1) gcd( φ ( n), e) = 1;1 < e < φ( n) e d 1 d = e modφ( n) KU = { e, n} KR = { d, n} RSA M < n e C = M (mod n) C d M = C (mod n) p = 7 q = 17 n = p q = 7 17 = 119 φ( n) = ( p 1)( q 1) = 96 e = 5 gcd( 96,5) = 1 5 d = 1 mod 96 d = 77

34 RSA 19 = / 119 = with a remainder of = *10 / 119 = *10 with a remainder of 19 RSA [( a mod n) ( b mod n)]mod n = ( a b) mod n 16 x modn = x x x x x x x x x x x x x x x x modn x mod n = x mod n = 2 ((( x ) ) ) mod n

35 RSA n n n n RSA

36 ECC(Eliptic Curve Cryptosystems) y P Q R x S = P + Q, O P P + O = P. (identity). P P + Q = O Q Q = P R S R + ( S). P P x P (x, y) P (x, y)., P Q P + Q = Q + P., P, Q R P + ( Q + R ) = ( P + Q ) + R. p GF(p) (elliptic curve) a, b GF(p) y 2 mod p = x 3 + ax + b mod p (x, y) O., x, y GF(p) a = 1 and b = 0, y 2 = x 3 + x. (9,5) because : y 2 mod p = x 3 + x mod p 5 2 mod 23 = mod mod 23 = 738 mod 23 2 = 2 The 23 points which satisfy this equation are: (0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5) (13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10) (18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17)

37 2 3 2 y + axy+ by = x + cx + dx+ e (real number) (elliptic curve) a b y 2 = x 3 + ax + b (x, y).

38 Addition of point P and point Q Addition of P and P By definition, P + (-P) = O. As a result of this equation, P + O = P in the elliptic curve group. O = the additive identity of the elliptic curve group; All elliptic curves have an additive identity.

39 Doubling the point P P = (x, y) If y 0, then P. the law for doubling a point on an elliptic curve group : P + P = 2P = R Doubling the point P if y = 0 By definition, 2P = O for such a point P. To find 3P in this situation, one can add 2P + P. Then, P + O = P Thus 3P = P. 3P = P, 4P = O, 5P = P, 6P = O, 7P = P,

40 E p (a,b) (0, 0) (p, p) O 2 3 E 23 (1,1) y = x + x + 1(mod 23) 2 3 y = x + ax + b (mod p) P + O = P O P = (x, y), -P = (x, -y) P = (x 1, y 1 ) Q = (x 2, y 2 ), P + Q = (x 3, y 3 ) x y λ x x (mod p) λ( x 1 1 x ) y (mod p) y2 y1 x2 x1 λ = 3x1 + a 2y1 2P = P + P, 3P = P + P + P,... if if P Q P = Q

41 P = (3, 10) Q = (9, 7) λ = x = = = 11mod = = P + Q = (17, 20) 17 mod 23 y3 = 11(3 ( 6)) 10 = 89 20mod 23 EC y 2 =x 3 +ax+b Addition S=P+Q (x 1, y 1 ), (x 2, y 2 ), (x 3, y 3 ) P, Q, S = P + Q. P + Q = S (x 3, y 3 ) x 1, y 1, x 2, y 2. y = αx + β P Q, α = (y 2 y 1 ) / (x 2 x 1 ), β = y 1 αx 1., (αx + β) 2 = x 3 + ax + b P Q (x, αx + β). y 3 x 3 (αx + β) 2 + ax + b (root). (x 1, αx 1 + β) (x 2, αx 2 + β) P Q x 1 x 2 3. x 1 + x 2 + x 3 = α 2 P Q R S = P + Q x x 3 = α 2 x 1 x 2 P + Q (x 3, y 3 ) y2 y1 2 y2 y x3 = ( ) x1 x2 y 1 3 = y1 + ( )( x1 x3) x2 x x 1 2 x1

42 P + Q P = Q α P y 2 = x 3 + ax + b 2yy = 3x 2 + a P = (x 1, y 1 ) α = (3x 12 + a) / 2y 1. P + Q = S (x 3, y 3 ) x 1, y 1, x 2, y x1 + a 2 x3 = ( ) 2x1 2 y1 2 3x ( 1 + a y3 = y1 + )( x1 x3) 2y1 P y R x S = P + P GF(p), where p is a prime( ) P (order) t : tp = 0 t GF(p) Q, t P, Q = xp x [0, t 1] P, 2P = P + P, 3P = P + P + P, y 2 mod 23 = x 3 + 9x + 17 mod 23, What is the discrete logarithm x of Q = (4,5) to the base P = (16,5)? Q = xp P = (16,5) 2P = (20,20) 3P = (14,14) 4P = (19,20) 5P = (13,10) 6P = (7,3) 7P = (8,7) 8P = (12,17) 9P = (4,5) Since 9P = (4,5) = Q, the discrete logarithm of Q to the base P is x = 9.

43 What is the discrete logarithm of Q(-0.35,2.39) to the base P(-1.65,-2.79) in the elliptic curve group y 2 = x 3-5x + 4 over real numbers? ECC ElGamal : { g, p, y = g x mod p } { G, p, Y = xg } : { x } { x } : [ c 1, c 2 ] = [ g x mod p, y x m mod p ] [ C 1, C 2 ] = [ x G, x Y + M ] : c 2 c x 1 mod p C 2 xc 1 Where x =random [] p = 11, a =1, b = 6 GF(p) y 2 = x 3 + x (2, 4) (2, 7) (3, 5) (3, 6) (5, 2) (5, 9) (7, 2) (7, 9) (8, 3) (8, 8) (10, 2) (10, 9) x = 7, G = (2, 7), Y = 7(2, 7) = (7, 2), x = 3 M = (10, 9) C 1 = 3(2, 7) = (8, 3), C 2 = 3(7, 2) + (10, 9) = (10, 2).

44 2P = P + P 100P = 2( 2( P + 2( 2( 2( P + 2P ) ) ) ) ) 100(D) = (B) key where, 1 =double & addition, 0 =double M 2 = M x M M 100(D) => (B) key where, 1 =square & multiple, 0 =square x mod n = x mod n = 2 ((( x ) ) ) mod n ag = P PG E p (a, b) a Generate Calculate Calculate random n P = n G A K = n A A P A = n n G A B B < n A B P P Generate Calculate Calculate random n P = n G B B K = n B B P < n = n n G B A A

45 m P m C m = {kg, P m + kp B } k C m -n B (kg) = P m + kp B -k (n B G) = P m P m m 1 mips 1 40, mips 1 (40,000)( ) t Pollard rho,. 1,000 mips 10,000 t = ,000 year π t 2 p(bits) t (bits) mips year πt n (bits) mips year

46 ECC, RSA, DSA Key Size 0.8 (Bits) ECC 3000 RSA &DSA E+12 1E+20 1E+36 Time to Break Key (mips-years) / INTERNET SERVER

47 PEM ( Privacy Enhanced Mail ) PGP ( Pretty Good Privacy ) S/MIME(Secure/Multipurpose Internet Mail Extensions), by RSA MOSS(MIME Object Security Service) PGP Phil Zimmerman RSA, IDEA, MD5 RSA, IDEA RSA, MD5 ZIP 64

48 PGP m MD5 m MD5 RSA ZIP m RSA(h(m)) PGP ZIP 1 RSA RSA(h(m)) m k s RSA RSA m k s ZIP IDEA IDEA(ZIP(m)) RSA(k s ) IDEA ZIP 1 WWW Browser (Explorer, Netscape) Server (NCSA HTTP, httpd) URL (Uniform Resource Locator) HTML (HyperText Manipulation Language) CGI (Common Gateway Interface) - e.g. form processing Security Holes FTP Server WWW Browser HTML WWW Server result query CGI Scripts Gopher Server Other Server

49 W W W Client / Server / W W W SSL ( Secure Socket Layer ) PCT ( Privacy Communication Technology ) S-HTTP SSL ( secure socket layer ) Netscape Communications Privacy, Data Integerity, Server [Client] Authentication, RSA, Diffie-Hellman, Fortezza for Key Exchange DES, 3DES, IDEA, RC2, RC4[stream cipher] for Data Encryption MD5, SHA for Hash Function ( MAC ) SSL TCP IP SSL Handshake SSL Record Algorithm Negotiation, Key Exchange, Authentication Data Encapsulation for data protection

50 SSL Handshake Protocol Client_Hello { R, Ciphersuite } Server_Hello { R, Cipher, X.509 Certificate } Client_Key_Exchange Server Client Session_Key_Generation Client_Finished, Server_Finished SSL Client Hello Phase client SSL version 28-byte random number R session ID cipher_suites compression methods SSL Server Hello Phase Client Server_Hello Client_Hello Server server SSL version 28-byte random number R session ID -> If a new session, server s certificate cipher_suite { key exchange algorithm } compression method

51 SSL Client Key Exchange Key Exchange Algorithm s Parameter in Certificate RSA : public exponent k e, modulus n Diffie-Hellman : g, modulus p, g s mod p From Pre_Master_Key To Mater-Key [ MD5, SHA, R, R ] Master_Key = MD5 (Pre_Master_Key SHA ( A Pre_Master_Key R R ) ) MD5 ( Pre_Master_Key SHA ( BB Pre_Master_Key R R )) MD5 ( Pre_Master_Key SHA ( CCC Pre_Master_Key R R ) ) Client_Key_Exchange Server Client Pre_Master_Key = g cs mod p { 48-byte random } K e [server] SSL Session Key Generation Keys for data encryption and data integrity Key_Block = MD5 (Master_Key SHA ( A Master_Key R R ) ) MD5 ( Master_Key SHA ( BB Master_Key R R )) MD5 ( Master_Key SHA ( CCC Master_Key R R ) )... SSL Client-Server Finished Key Exchange, Authentication Negotiated Algorithm, Parameter All Handshaked Messages Sender s value { client[0x434c4e54], server[0x ] }

52 SSL Record Protocol Fragmentation Compression Protection Application Data SSL Handshake SSL Record SSL TCP IP SSL_plaintext SSL_plaintext SSL_compressed SSL_ciphertext 2 14 bytes or less Stream Cipher ( RC4 ) with MAC Block Cipher ( RC2, DES ) with MAC Change cipher spec - Change cipher spec cipherspec. - - Alert - SSL -

53 ( ) : - / - / ( ) A. (Authentication) :, ; [] One-Time Password B. (Access Control) : C. (Traffic Enciphering) : (DES, RSA, IDEA ) D. (Traffic Log) : E. (Audit)

54 A. Packet Filtering Firewall - (Screening Router) - (Bestion Host) B. Circuit Level Firewall - (Circuit Gateway) C. Application Level Firewall - (Proxy Server Host) - - (Dual-Homed Gateway) D. Hybrid Firewall - (Screened Host) - (Screened Subnet) E. Stateful Inspection Firewall

55 FireWall HOST HOST HOST HOST Domain Name Service Handling Packet Filter Application Gateway (Source routing).

56 (3) Packet Filter Operations yes? no yes yes no no NACK

57 Proxy Server TELNET Client A private LAN TELNET request request ID, Password TELNET Proxy Server FireWall INTERNET Separate Proxy Server for each Application ( FTP, TELNET ) TELNET Server A send ID, Password TELNET request User Authentication [ One-Time Password ] change IP address Externalized FTP Server HOST private LAN FireWall INTERNET HOST anonymous FTP File FTP Server

58 SSL 1.0 Design complete SSL 2.0 Products ships PCT 1.0 published SSL 3.0 published TLS WG formed TLS 1.0 published NCSA Mosaic released Netscape Navigator released Internet Explorer released WTLS published , WAP 2.0

62 HTML/XML, JavaScript HTTP Application Environment (WAE) Session Layer (WSP) Transaction Layer (WTP) other services and applications TLS - SSL TCP/IP UDP/IP Security Layer (WTLS) Transport Layer (WDP) Bearers: GSM IS-136 CDMA PHS CDPD etc.. Client WAP Gateway Web Server WML WML- Script WTAI Etc. WSP/WTP WML Encoder and Decoder WMLScript Compiler Protocol Adapters HTTP CGI Scripts etc. Content WML Decks with WML-Script

63 Wireless Network Internet WAP BROWSER WAP GATEWAY WEB SERVER WTLS SSL

64 WTP Handshake protocol Change cipher Spec protocol Record protocol Alert protocol WDP

65 ClientHello Certificate* ClientKeyExchange CertificateVerify* Changecipherspec Finished Application data data ServerHello Certificate* CertificateRequest* ServerKeyExchange* Changecipherspec Finished Application data data

66 WTLS Plaintext WTLS Compressed WTLS Compressed + MAC WTLS Ciphertext

Subnet Address Internet Network G Network Network class B networ

Subnet Address Internet Network G Network Network class B networ Structure of TCP/IP Internet Internet gateway (router) Internet Address Class A Class B Class C 0 8 31 0 netid hostid 0 16 31 1 0 netid hostid 0 24 31 1 1 0 netid hostid Network Address : (A) 1 ~ 127,