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

(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

(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 (, )

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

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

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

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

( ) = ( ) =

(Security)

( ) LFSR

LFSR A5 (A5 Stream cipher)

A5 A5

DES 1973 1.. 2.. 3.. 4.. 5.. 6.,. 7.. 1974 8 2 Water Tuchman Carl Meyer lucifer cipher 1977 1 15 DES 5 ANSI

DES DES 6464 64 (substitution) (permutation) 2 16 1. (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

IP(Initial Permutation) IP IP -1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 DES 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 19 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 IP 58 -> 1 / 50 -> 2 IP -1 1 -> 58 / 2 -> 50 f Function R (32bit) DES E S1 S2 S3 S4 S5 S6 S7 S8 P Output (32bit)

DES S-BOX ( 1 0 1 1 1 1 ) : Input ( 0 1 1 1 ) : 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

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

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

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

International Data Encryption Algorithm)

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

SEED 16round 128 128 DES feistal F SEED DES 2 128 F

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

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

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

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

RSA 19 = 2476099 / 119 = 20807 with a remainder of 66 66 = 1.27...*10 / 119 = 1.06...*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 16 100002 = 2 ((( x ) 2 2 2 ) ) mod n

RSA n n n n RSA

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 = 9 3 + 9 mod 23 25 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)

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

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.

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,

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 3 3 2 λ x x (mod p) λ( x 1 1 x ) y (mod p) 3 2 1 y2 y1 x2 x1 λ = 3x1 + a 2y1 2P = P + P, 3P = P + P + P,... if if P Q P = Q

P = (3, 10) Q = (9, 7) λ = x 7 10 3 1 = = = 11mod 23 9 3 6 2 = 11 2 3 9 = 109 3 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

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 2. 2 3x1 + 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.

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 + 6. (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).

2P = P + P 100P = 2( 2( P + 2( 2( 2( P + 2P ) ) ) ) ) 100(D) = 1 1 0 0 1 0 0 (B) key where, 1 =double & addition, 0 =double M 2 = M x M M 100(D) => 1 1 0 0 1 0 0(B) key where, 1 =square & multiple, 0 =square x mod n = x mod n 16 100002 = 2 ((( x ) 2 2 2 ) ) 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

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,000. 1 mips 1 (40,000)(60 60 24 365) 2 40. t Pollard rho,. 1,000 mips 10,000 t = 2 160 96,000 year π t 2 p(bits) t (bits) mips year πt 2 163 160 2 80 9.6 10 11 191 186 2 93 7.9 10 15 239 234 2 117 1.6 10 23 359 354 2 177 1.5 10 41 431 426 2 213 1.0 10 52 n (bits) mips year 512 3 10 4 768 2 10 8 1024 3 10 11 1280 1 10 14 1536 3 10 16 2048 3 10 20

ECC, RSA, DSA 1.2 1 Key Size 0.8 (Bits) 0.6 0.4 0.2 0 6000 5000 4000 ECC 3000 RSA &DSA 2000 1000 0 10000 100000000 1E+12 1E+20 1E+36 Time to Break Key (mips-years) / INTERNET SERVER

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

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

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

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

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[0x53525652] }

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 -

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

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

FireWall HOST HOST HOST HOST Domain Name Service E-mail Handling Packet Filter Application Gateway (Source routing).

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

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

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 2001. 8, WAP 2.0

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

Wireless Network Internet WAP BROWSER WAP GATEWAY WEB SERVER WTLS SSL

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

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

WTLS Plaintext WTLS Compressed WTLS Compressed + MAC WTLS Ciphertext