Tài liệu Nghiên cứu các phương pháp mã hoá – giấu tin đa tầng và ứng dụng

NG I H C KHOA H C T NHIÊN KHOA CÔNG NGH THÔNG TIN B MÔN CÔNG NGH TRI TH C NG TH M TRANG H TR N H NG NG C – TR K H TN TR C N TT – Đ NGHIÊN C U CÁC PH NG PHÁP MÃ HOÁ – GI U TIN A T NG VÀ NG NG K H O A LU N V N C NHÂN TIN H C TP. HCM, 2004 NG I H C KHOA H C T NHIÊN KHOA CÔNG NGH THÔNG TIN B MÔN CÔNG NGH TRI TH C K H TN TR - 0012694 - 0012746 H TR NG TH M TRANG TR N H NG NG C C N TT – Đ NGHIÊN C U CÁC PH NG PHÁP MÃ HOÁ – GI U TIN A T NG VÀ NG NG LU N V N C K H O A T.S Th.S NHÂN TIN H C GIÁO VIÊN H NG D N NGUY N ÌNH THÚC PH M PH M TUY T TRINH NIÊN KHÓA 2000 - 2004 NH N XÉT C A GIÁO VIÊN H NG D N ....................................................................................................................... K H TN ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... H ....................................................................................................................... Đ ....................................................................................................................... – ....................................................................................................................... ....................................................................................................................... C N TT ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... K H O A ....................................................................................................................... ....................................................................................................................... NH N XÉT C A GIÁO VIÊN PH N BI N ....................................................................................................................... K H TN ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... H ....................................................................................................................... Đ ....................................................................................................................... – ....................................................................................................................... ....................................................................................................................... C N TT ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... K H O A ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... IC M N Chúng em xin chân thành cám n Khoa Công Ngh Thông Tin, tr hi n u ki n t t cho chúng em th c K H TN i H c Khoa H c T Nhiên TpHCM ã t o ng tài lu n v n t t nghi p này. Chúng em xin chân thành cám n Th y Nguy n ình Thúc và Cô Ph m Ph m Tuy t Trinh ã t n tình h ng d n, ch b o và óng góp ý ki n cho chúng em trong su t th i gian th c hi n tài. Chúng em xin chân thành cám n quý Th y Cô trong Khoa ã t n tình H gi ng d y, trang b cho chúng em nh ng ki n th c quý báu trong nh ng n m Đ h c v a qua. i v i Ông Bà, Cha M ã – Chúng con xin nói lên lòng bi t n sâu s c ch m sóc, nuôi d y chúng con thành ng i. C N TT Xin chân thành cám n các anh ch và b n bè ã ng h , giúp và ng viên chúng em trong th i gian h c t p và nghiên c u. M c dù chúng em ã c g ng hoàn thành lu n v n trong ph m vi và kh ng cho phép nh ng ch c ch n s không tránh kh i nh ng thi u sót. Chúng em kính mong nh n c s c m thông và t n tình ch b o c a quý Th y Cô và K H O A các b n . Sinh viên Tr n H ng Ng c – Tr ng Th M Trang Tháng 07/ 2004 CL C —¯– K H O A C N TT – Đ H K H TN DANH SÁCH CÁC HÌNH V .........................................................................1 Ch ng 1. Gi i thi u..................................................................................2 Ch ng 2. M t s h th ng mã hoá ............................................................4 2.1. Các khái ni m c b n .......................................................................4 2.1.1. S nguyên t ........................................................................4 2.1.2. Mã hóa khóa bí m t (Private-Key Encryption):....................7 2.1.3. Mã khóa công khai (Public-Key Encyption): .......................9 2.1.3.1. Gi i thi u ..........................................................................9 2.1.3.2. Phân lo i h th ng mã hóa khóa công:.............................11 2.1.4. Ch ký n t ...................................................................11 2.1.4.1. Gi i thi u: .......................................................................11 2.1.4.2. Các c m c a ch ký n t : ....................................13 2.2. Mã hóa i x ng RC6 ....................................................................14 2.2.1. Gi i thi u RC6 ..................................................................14 2.2.2. Thu t toán RC6 .................................................................14 2.2.2.1. L p khóa:.........................................................................14 2.2.2.2. Mã hóa và gi i mã : .........................................................15 2.2.3. Nghi th c RC6...................................................................16 2.2.4. ánh giá RC6 ....................................................................17 2.3. Ph ng pháp mã hóa khóa công RSA ............................................17 2.3.1. Gi i thi u ..........................................................................17 2.3.2. Thu t toán RSA.................................................................17 2.3.3. Nghi th c RSA ..................................................................18 2.3.4. ánh giá RSA....................................................................19 2.4. H mã hóa ECC (Elliptic Curve Cryptography)..............................19 2.4.1. Gi i thi u ..........................................................................19 2.4.2. M t s khái ni m ...............................................................19 2.4.2.1. Tr ng h u h n ...............................................................20 2.4.2.2. M t s c tính Elip trên tr ng h u h n.........................22 2.4.2.3. Kh o sát ng cong Elip................................................23 2.4.3. Các thành t m t mã trong ECC.........................................25 2.4.3.1. Các thông s mi n ng cong Elip ................................25 2.4.3.2. C p khóa ng cong Elip...............................................27 2.4.4. Các l c trong ECC......................................................27 2.4.4.1. c ch ký n t d a trên ECC..............................28 2.4.5. ánh giá ECC....................................................................30 2.5. So sánh RSA và ECC.....................................................................30 Ch ng 3. Hàm b m ................................................................................33 3.1. Tính ch t c a hàm b m ..................................................................34 i K H O A C N TT – Đ H K H TN 3.1.1. Hàm b m m t chi u (OWHF - One-Way Hash Function)..34 3.1.2. Hàm b m ch ng xung t (CRHF - Collision Resistant Hash Function) 34 3.1.3. Các hàm b m l p (Iterated Hash Function) ........................35 3.2. Gi i thi u m t s hàm b m ............................................................36 3.2.1. Hàm MD5..........................................................................36 3.2.1.1. Gi i thi u ........................................................................36 3.2.1.2. Thu t toán .......................................................................36 3.2.1.3. Phân bi t MD5 v i MD4 .................................................40 3.2.2. SHA-1 ...............................................................................41 3.2.2.1. Gi i thi u ........................................................................41 3.2.2.2. Các hàm và các h ng s c dùng trong thu t toán........41 3.2.2.3. Tính giá tr b m ...............................................................42 3.2.3. Tiger..................................................................................43 3.2.3.1. Gi i thi u ........................................................................43 3.2.3.2. c t ..............................................................................45 3.2.3.3. Tính b o m t ...................................................................47 3.3. Hàm b m Whirlpool.......................................................................48 3.3.1. Gi i thi u ..........................................................................48 3.3.2. Các c s và ký hi u toán h c............................................49 3.3.2.1. Tr ng Galois (s bi u di n nh phân).............................49 3.3.2.2. Các l p ma tr n ...............................................................49 3.3.2.3. Mã MDS (MDS code - Maximal Distance Separable code) 49 3.3.2.4. Các thu c tính m t mã .....................................................50 3.3.2.5. Ký hi u khác ...................................................................51 3.3.3. Mô t Whirlpool ................................................................51 3.3.3.1. Nh p và xu t ...................................................................52 3.3.3.2. L p phi tuy n γ...............................................................52 3.3.3.3. Hoán v theo chu k π......................................................52 3.3.3.4. L p lan truy n tuy n tính θ..............................................52 3.3.3.5. Phép c ng khoá σ[k]........................................................53 3.3.3.6. H ng s vòng cr...............................................................53 3.3.3.7. Hàm vòng p[k]................................................................53 3.3.3.8. B ng x p l ch khoá ..........................................................53 3.3.3.9. M t mã kh i n i W.........................................................53 3.3.3.10. Thêm các bit và t ng c ng MD....................................53 3.3.3.11. Ch c n ng nén( Nguyên t c nén) ...................................54 3.3.3.12. Tính thông i p b m......................................................54 3.3.4. ánh giá hàm b m Whirpool .............................................54 Ch ng 4. Gi u d li u – Watermarking ..................................................55 4.1. Gi u d li u ...................................................................................55 4.2. Phân lo i: .......................................................................................55 4.3. Mô hình chung:..............................................................................56 4.4. Các yêu c u c a bài toán gi u d li u.............................................56 4.5. Ph ng pháp gi u d li u...............................................................58 ii K H O A C N TT – Đ H K H TN 4.5.1. Ph ng pháp gi u d li u có th nhìn th y ........................58 4.5.1.1. Ph ng pháp d a vào phép bi n i Cosin t ng ph n......58 4.5.1.2. Ph ng pháp chèn giá tr xám.....................................59 4.5.2. Ph ng pháp gi u d li u không th th y ..........................60 4.5.2.1. Ph ng pháp l ng hoá h s bi n i wavelet ...............60 4.5.2.2. Ph ng pháp d a vào s khác bi t gi a các h s wavelet k nhau ........................................................................................60 4.5.2.3. Ph ng pháp d a vào phép bi n i Wavelet d th a......62 4.5.2.4. Ph ng pháp d a trên vi c chia block thích nghi.............64 4.6. Các d ng t n công ..........................................................................66 4.7. ng d ng c a ph ng pháp gi u d li u ........................................66 Ch ng 5. M t s ng d ng .....................................................................68 5.1. Gi u tin trên nh.............................................................................68 5.1.1. Nghi th c gi u tin a t ng trên nh ....................................68 5.1.2. Giao di n ng d ng ...........................................................70 5.2. Mô hình ch ký n t ..................................................................71 5.2.1. Mô hình t o ch ký............................................................71 5.2.2. Mô hình ch ng th c ch ký n t ...................................72 5.2.3. Giao di n ng d ng ...........................................................73 5.3. Nhúng tin vào phim và ng d ng ...................................................74 5.3.1. Mô hình nhúng c s d li u trên phim .............................74 5.3.1.1. T ch c C s d li u....................................................74 5.3.1.2. T p l nh trên c ng o ...................................................75 5.3.1.3. Thu t toán .......................................................................75 5.3.2. Giao di n ng d ng ...........................................................76 5.4. Giao di n c a ch ng trình chính...................................................76 Ch ng 6. K t lu n – H ng phát tri n ....................................................77 6.1. K t lu n .........................................................................................77 6.2. H ng phát tri n ............................................................................78 Tài li u tham kh o..........................................................................................79 Ph l c A: Bi n i Wavelet ..........................................................................81 Ph l c B: K t qu th nghi m hàm b m Tiger và Whirlpool.........................90 iii DANH SÁCH CÁC HÌNH V nt c g i cùng b n rõ thông i p ............................13 Hình 2.2. Ch ký nt c g i cùng b n mã c a thông Hình 2.3. So sánh m c K H TN Hình 2.1. Ch ký p ....................13 b o m t gi a ECC và RSA ...................................31 Hình 3.1. Phát th o ch c n ng nén c a Tiger .................................................47 Hình 4.1. Hai m u watermark........................................................................55 Hình 4.2. Mô hình chung c a h th ng gi u d li u.......................................56 nhúng watermark b ng ph ng pháp d a trên block thích nghi H Hình 4.3. .......................................................................................................................65 Đ Hình 5.1. Mô hình h th ng nhúng watermark trên nh .................................68 Hình 5.2. Màn hình giao di n nhúng không nhìn th y c......................................71 n t ............................................................71 C N TT Hình 5.4. Mô hình t o ch ký – Hình 5.3. Màn hình giao di n nhúng nhìn th y c ...........................70 Hình 5.5. Mô hình ch ng th c ch ký n t ................................................72 Hình 5.6. Màn hình giao di n phát sinh c p khoá...........................................73 Hình 5.7. Màn hình giao di n t o ch ký n t ...........................................74 Hình 5.8. Màn hình giao di n ch ng th c ch ký Hình 5.9. Màn hình giao di n ng d ng K H O A Hình 5.10.Giao di n c a ch n t ...............................74 c ng o.........................................76 ng trình chính ..................................................76 B ng 2.1.B ng so sánh v kích th c khóa công khai gi a ECC, RSA và AES [7] ..................................................................................................................30 1 Ch ng 1. Gi i thi u K H TN Trong nh ng n m g n ây, s phát tri n nhanh chóng c a Internet và các công c x lý multimedia ã mang l i cho chúng ta nhi u thu n l i trong vi c l u tr d li u, trao i thông tin, sao chép d li u v.v…Tuy nhiên, bên c nh các thu n l i ó, s phát tri n này c ng t o ra nhi u th thách trong v n tìm ra gi i pháp b o m t d li u c ng nh vi c ch ng nh n quy n s h u c a các cá nhân. Nh ng th thách này ã thu hút s chú ý c a nhi u nhà nghiên c u trong l nh v c công ngh thông tin và toán: ó chính là b o m t: Đ H Ø Làm sao b o m t d li u? Ø Làm sao ch ng nh n m t d li u nào ó thu c quy n s h u c a ng i này hay ng i kia? Ø Làm sao ng i nh n bi t c thông tin mà h nh n c là chính xác? Ø Làm sao tin t c truy n i không b ánh c p? C N TT – Hi n ã có nhi u gi i pháp c xu t nh : s d ng m t kh u, mã hoá thông tin, steganography, n d li u (watermarking) v.v….và bên c nh các ph ng pháp b o m t m i ngày càng ph c t p thì c ng xu t hi n nhi u d ng t n công khác nhau và ngày càng tinh vi h n. Do ó, v n làm sao a ra m t gi i pháp hi u qu theo th i gian và s phát tri n m nh m c a khoa h c k thu t và các k thu t ph n c ng là không d . K H O A Trong gi i h n c a lu n v n, chúng tôi s trình bày s nét v các gi i pháp này chúng ta có cái nhìn t ng quát v b o m t thông tin. ng th i, chúng tôi c ng xu t m t s ng d ng. B c c lu n v n g m 6 ch ng và ba ph l c: Ch ng 1. Gi i thi u - Trình bày khái quát v lu n v n và gi i h n m c tiêu c a tài. Ch ng 2. M t s h mã hóa - Trình bày m t s khái ni m c b n, h mã khoá công khai RSA, ECC, h mã i x ng RC6 và so sánh gi a RSA và ECC. Ch ng t c ng 3. Hàm b m - Gi i thi u m t s ph ng pháp b m h tr x lý cho vi c mã hoá d li u trong ng d ng t o ch ký nt . Ch ng 4. Gi u d li u – WaterMarking - Gi i thi u s l c v k thu t gi u d li u và m t s ph ng pháp gi u d li u d a trên phép bi n i Wavelet. 2 Ch ng 5. M t s ng d ng – Mô t m t s d a trên các ki n th c ã trình bày các ch ng trên. Ch ng 6. K t lu n và h ng phát tri n c và a ra h ng phát tri n cho lu n v n. ng d ng c ánh giá các k t qu xu t t K H TN Ph l c 1: Bi n i Wavelet - Trình bày s nét v phép bi n i Wavelet là c s c a các ph ng pháp gi u d li u c trình bày trong Ch ng 4. K H O A C N TT – Đ H Ph l c 2: K t qu th nghi m hàm b m Tiger và Whirlpool. 3 Ch M t s h th ng mã hoá Các khái ni m c b n 2.1.1. S nguyên t K H TN 2.1. ng 2. nh ngh a 2.1: G i Z là t p các s nguyên {0, 1, -1, 2, -2, ...} và N = {n ∈ Z, n ≥ 0}; N* = { n ∈ Z, n ≥ 1}. Cho a, b ∈ Z, n u ∃c ∈ Z : b = ac ta nói a là c s c a b hay b là b i s c a a, ký hi u a|b. – Đ H nh lý 2.1: V i a, b, c, x, y ∈ Z: a|a, 1|a; a|b, b|c ⇒ a|c a|b, a|c ⇒ a|(bx + cy) a|b, b|a ⇒ a = ± b a|b ⇒ (-a)|b, a|(-b), (-a)|(-b) C N TT nh ngh a 2.2: Cho a ∈ Z, b ∈ N*, t n t i duy nh t q ∈ Z, và r ∈ N sao cho: a = bq + r, 0 ≤ r ≤ b. Khi ó: q c ký hi u là a/b và r c ký hi u là a % b (hay a mod b). K H O A nh ngh a 2.3: § M t s nguyên c ∈ Z c g i là c chung c a a,b ∈ Z n u c|a và c|b. § M t c chung d ∈ Z c a a, b ∈ Z, c g i là c chung l n nh t c a a,b ∈ Z , ký hi u d = gcd(a,b) hay d = a ∧ b, n u m i b i s c a m i s chia c a a, b; (c ∈ Z, c|a, c|b ⇒ c|d). nh ngh a 2.4: § M t s nguyên d ∈ Z c g i là b i chung c a a, b ∈ Z n u a|d và b|d. § M t b i chung d ∈ N c a a, b ∈ Z, c g i là b i chung nh nh t c a a, b ∈ Z, ký hi u d = lcm(a,b) hay d = a ∨ b, n u m i b i s c a a, b u chia h t cho d; (c ∈ Z, a|c, b|c ⇒ d|c). nh ngh a 2.5: Hai s nguyên t a,b ∈ Z ⊥ b, n u a ∧ b=1. c g i là nguyên t cùng nhau, ký hi u a 4 4 Ghi chú: 1 ∧ 1 = 1 ⇒ 1 ⊥ 1. a, b ∈ N và a ≥ 2, b ≥ 2, a ⊥ b, thì a ≠ b. Th c v y, n u a = b, ta có a ∧ a ≠ a ≠ 1. c g i là s nguyên t n u nó ch có c s c g i là h p s . Vì th , 1 là h p s . T p t t c K H TN nh ngh a 2.6: M t s nguyên a ≥ 2 ng là 1 và a; ng c l i, a các s nguyên t ký hi u là P. Đ H 4 Ghi chú: § a,b ∈ P, a ≠ b ⇒ a ⊥ b; vì a và b ch có c chung d ng là 1. § N u a ∈ P, ∀ b ∈ Z và không là b i s c a a thì b nguyên t cùng nhau v i a. Th c v y, n u c là c chung d ng c a a, b và c ≠ 1, ta có c = a vì a là s nguyên t . Thì b chia h t cho c là vô lý. § M i s nguyên l n h n hay b ng 2 có ít nh t m t c s là s nguyên t : c chung nguyên t nh nh t c ng s l n h n hay b ng 2. – nh lý 2.2: ∀ a, b ∈ N*, a > b, ta có: a ∧ b = b (a % b) K H O A C N TT Thu t toán 2.1: (Thu t toán Euclid tính c chung l n nh t c a 2 s nguyên d ng) Cho a,b ∈ N, a > b > 1. t a = r0, b = r1. T nh ngh a 1.2, ta có: r0 = r1q1 + r2, 0 ≤ r2 < r1 ; r1 = r2q1 + r3, 0 ≤ r3 < r2 ; ……………… rk-2 = rk-1q k-1 + rk, 0 ≤ rk < rk-1; 2 ≤ k ≤ n; rn-1 = rnq n + rn+1, 0 = rn+1 < rn; ⇒ a = r0 > b = r1 > r2 > … > rn > rn+1 = 0. V y, rn = gcd(a, b); Theo nh lý 2.2: gcd(a,b) = gcd(r0,r1) = gcd(r1,r2) = … = gcd(rn-1,rn) = gcd(rnqn + rn+1, rn) gcd(rnqn, rn) = rn. nh lý 2.3: ( nh lý Eulid m r ng) V i a,b ∈ N, a > b ≥ 1; ta có: ∃ x, y ∈ Z: ax + by = 1; N u a ⊥ b, ∃ x, y ∈ Z: ax + by = 1; a ⊥ b ⇔ ∃ x, y ∈ Z: ax + by = 1. 5 K H TN nh ngh a 2.8: ( nh ngh a phép ng d ) Cho x,y ∈ Z, m ∈ N*: x c g i là ng d c a y mod m, ký hi u: x ≡ y(mod m). n u m là s chia c a x – y; m c g i là mô un c a phép ng d . T p các s nguyên modulo m, ký hi u Zm, là t p: Zm = {0, 1, 2, … , m-1} N u x ∈ Zm , s nguyên x mod m c a Zm c g i là rút g n modulo c a x theo m. nh ngh a 2.9: M t s nguyên a ∈ Zm c g i là modulo m kh ngh ch n u t n t i x ∈ Zm: ax = 1 (mod m). N u t n t i s x này, thì x là duy nh t, và c g i ngh ch o c a a modulo m, ký hi u a-1 (mod m), hay n gi n h n a-1. Đ H nh ngh a 2.10: ( nh ngh a hàm phi-Euler) Cho n ≥ 1, t ϕ(n) là t p các s nguyên trong kho ng [1,n] nguyên t cùng nhau v i n. Hàm ϕ nh th c g i là hàm phi-Euler C N TT – nh lý 2.3: Cho k = card(Zm*) = ϕ(m), m ≥ 2, Zm* = {x1, x2, …, xk}, xZm* = {xy; y ∈ Zm*}, ∀x ∈ Zm*, và u = x1x2…xk. Ta có: xZm* = Zm*, ∀x ∈ Zm*. u = xku (mod m), xk = 1 (mod m). nh lý Euler) x ⊥ m ⇒ xϕ(m) =1 (mod m). nh lý Fermat) p ∈ P, x ⊥ p ⇒ xp-1 = 1 (mod p). p ∈ P, n ∈ Z ⇒ np = n (mod p). p ∈ P, n ∈ Z, r = s (mod ϕ(m)) ⇒ nr = ns (mod p). N u p,q là hai s nguyên t khác nhau và n = pq, thì ϕ(m) = (p-1)(q-1). K H O A nh lý 2.4: ( nh lý s d Trung Hoa) N u các s nguyên n1,…,nk ôi m t nguyên t cùng nhau và n = n 1…n k thì x ≡ a1(mod n1), … , x ≡ ak (mod nk), có duy nh t nghi m trong Zn. Ánh x f: Zn→Zn-1 × … × Znk, xác nh b i f(x) = (x mod n1, … , x mod n k), x ∈ Zn ∑ M t s phép tính nhanh trên các s nguyên: q Phép toán mod trên tr ng Zm Ta có : x = y (mod m) Khi x, y, m là nh ng s nguyên l n, 0 ≤ x,y ≤ m, b ≥ 2 và y = 0 ≤i ≤ I y i b i là bi u di n c s b c a y, ta có: (x * y) mod m = (y0 * x + ∑ 0≤ i ≤ I yi ( x * b i ) mod m)) mod m (x * bi) mod m = (b * ((x * b i) mod m)) mod m, 0 ≤ i ≤ I 6 Vì th ta có th s (x*y)mod m d ng thu t gi i sau tính tích modulo P = K H TN Thu t gi i: (tr ng h p t ng quát) t x = x mod m, y = y mod m, và P = (y0 * x) mod m Cho i t 1 n I, do: a. x = (b * x) mod m; b. Tính x = (yi * x) mod m, và P = (P + x) mod m Return P q Phép l y th a mod nh ngh a 1.11: Cho x ∈ Zm và m t s nguyên p ∈ N* có bi u di n i nh phân p = ∑0≤i ≤ I p i 2 . Vi c tính giá tr y = xp mod m c g i là phép l y th a mod. Ta có: x p = x p 0 * ( x 2 ) p1 * ( x 4 ) p2 * ... * ( x 2 ) p 0≤ i ≤ I pi 2i y = xp mod m – u ra: ∑ Đ Thu t gi i: u vào: x ∈ Zm, p = i H i 2.1.2. C N TT y = 1. N u p = 0, return y A = x. N u p0 = 1 thì y = x Cho I ch y t 1 n I, do: c. A = A2 mod m d. N u pi = 1 thì y = (A*y) mod m Return y Mã hóa khóa bí m t (Private-Key Encryption): K H O A Các thu t toán mã hoá khoá bí m t dùng m t khoá bí m t n mã hóa và gi i mã d li u. C n ph i gi an toàn cho khoá t vi c truy c p b i các tác nhân không c phân quy n b i vì b t k ng i nào có khoá u có th gi i mã d li u. Mã hoá khoá bí m t c ng c g i là mã hoá khoá i x ng b i vì ch cùng m t khoá dùng cho c mã hoá và gi i mã. Thu t toán mã hoá khoá bí m tt c c c k nhanh (so v i các thu t toán khoá công) và thích h p t t v i vi c th c thi bi n i m t mã trên các dòng d li u l n. i n hình, các thu t toán khoá bí m t c g i là m t mã kh i (block cipher) c dùng mã hoá m t kh i d li u t i m t th i m. Các ph ng pháp mã kh i nh RC2, DES, Tripple DES, và Rijindael,… bi n i m t kh i n byte u vào thành m t kh i byte c mã hoá u ra. N u mu n mã hoá hay gi i mã m t chu i byte c n ph i bi n i nó thành t ng kh i, b i vì kích th c n thì nh (n = 8 byte cho RC2, DES và Tripple DES n = 16; n = 24; hay 7 n = 32 byte t i m t th i i v i Rijindael), các giá tr l n h n n ph i m. c mã hoá m t kh i Đ H K H TN Các lo i mã hóa kh i dùng ki u xích c g i là xích kh i m t mã (CBC_Cipher Block Chaining) dùng m t khoá và m t vect kh i t o (IV_Initial Vector) th c thi bi n i m t mã trên d li u. i v i khoá bí m tK c cho, m t m t mã kh i n gi n không dùng IV s mã hoá cùng hai kh i u vào c a v n b n g c gi ng nhau (plaintext) s cho cùng m t kh i u ra v n b n m t mã (ciphertext). N u các kh i c nhân ôi trong chu i d li u n b n g c, thì các kh i c mã hoá c nhân ôi trong chu i v n b n m t mã. N u m t ng i dùng không c phân quy n bi t b t c u gì v c u trúc c a kh i v n b n g c, h có th dùng thông tin ó gi i mã kh i v n b n m t mã c bi t và có th ph c h i khoá. ch ng l i u này, thông tin t kh i tr c ó c tr n vào trong ti n trình mã hoá kh i ti p theo. Vì v y, u ra c a hai kh i v n b n g c gi ng nhau là khác nhau b i vì k thu t này dùng kh i tr c ó mã hoá kh i ti p theo, m t IV c dùng mã hóa kh i u tiên c a d li u. Dùng h th ng này, các ph n u (header) thông p ph bi n có th b nh ng ng i không có quy n bi t n thì h c ng không th dùng công ngh o (reverse engineer) tìm ra khoá. C N TT – Ch có m t cách xâm ph m vào d li u c mã hoá b ng ph ng pháp m t mã này là th c hi n vét c n v i m i khoá có th có. Ph thu c vào kích th c khoá c dùng th c hi n mã hoá, lo i tìm ki m này s d ng r t nhi u th i gian th m chí dùng các máy tính nhanh nh t và do ó không kh thi. Các kích th c khoá l n h n, thì khó gi i mã h n. M c dù vi c mã hoá v m t lý thuy t không có ngh a là không kh thi vi c l y d li u ã mã hóa, nó không a ra các chi phí th i gian ph i tr cho vi c th c hi n gi i mã này. N u m t nhi u tháng th c hi n m i cách tìm ki m d li u thì nó c ng ch có ý ngh a nh vài ngày vì u không có k t qu . Do ó, ph ng pháp vét c n là không th th c hi n. K H O A S b t l i c a khóa bí m t là nó cho hai nhóm ng i tho thu n v khoá và IV và truy n thông các giá tr c a h . C ng v y, khoá ph i c gi bí m t i v i nh ng ng i không quy n. Vì nh ng v n này mà mã hoá khoá bí m t th ng c dùng chung v i mã hóa khóa công truy n thông cá nhân các giá tr c a khóa và IV. M t s thu t toán mã hóa ph bi n nh DES (Data Encrypion Standard), AES (Advanced Encryption Standard), Blowfish, IDEA, RC4,… Gi s A và B là hai nhóm ng i mu n truy n thông trên m t kênh truy n không an toàn, h có th dùng mã hóa khoá bí m t nh sau: C A và B th a thu n v i nhau dùng m t thu t toán c th (ví d Rijindael) v i m t khóa và IV c th . A so n m t thông p và t o m t dòng truy n trên m ng g i i. K ó, A mã hóa v n b n dùng khóa và IV và g i nó thông qua m ng A không g i khóa và IV cho B. B nh n v n b n mã hóa và gi i mã nó b ng khóa và IV ã th a thu n tr c. N u vi c truy n thông b ch n thì ng i ch n không 8 th ph c h i v n b n g c do không bi t khóa và IV. Trong k ch b n này, khóa ph i c gi bí m t còn IV thì không c n ph i gi bí m t. Trong k ch b n th gi i th c, A hay B phát sinh ra khoá bí m t và dùng mã hóa khóa công (b t i x ng) truy n khóa bí m t (b t i x ng) . K H TN Các h th ng mã khóa bí m t tuy c s d ng m t th i gian dài và ít ph c t p v m t toán h c h n các ph ng pháp mã hóa khóa công khai. Tuy nhiên v n còn m t s h n ch làm gi i h n kh n ng c a các h th ng mã hóa khóa bí m t. Hai v n gây h n ch chính là: ng pháp DIFFIE-HELLMAN trong truy n khóa C N TT Gi i thi u ph – Đ H § V n phân ph i khóa: tr c ây các h th ng mã hóa khóa bí m t ch y u ch s d ng trong quân i và các t ch c ngo i giao nên không có tr ng i gì khi thay i khoá hay truy n khóa, nh ng ngày nay nhu c u nhi u ng i mu n truy n tin an toàn mà không c n bi t nhau qua Internet d n n vi c thi t l p kênh truy n an toàn gi a hai ng i b t k không kh thi. § V n qu n lý khóa: trong h th ng có n ng i s d ng, gi s m i ng i mu n liên l c an toàn v i t t c m i ng i thì c n n(n-1)/2 khóa. Trong khi vi c s d ng cho các m c ích th ng m i ngày nay t ng lên r t nhanh, vi c l u tr khóa tr nên khó kh n. K H O A ây là gi i pháp u tiên cho v n phân ph i khóa c a h th ng mã hóa khóa i x ng. Nghi th c th c hi n nh sau: (1) A, B công khai ch n m t nhóm nhân tu n hoàn Γ và m t ph n t g ∈Γ A ch n m t s ng u nhiên a, và g i ga n B B ch n m t s ng u nhiên b, và g i gb n A Sau khi nh n gb, A tính (gb)a ng t , B tính (ga)b A, B cùng chia x m t ph n chung là gab óng vai trò nh khóa bí m t gi a h . N u m t k t n công bi t c g, ga, gb thì c ng r t khó xác nh gab. Bài toán này có quan h ch t ch n bài toán logarit r i r c. 2.1.3. Mã khóa công khai (Public-Key Encyption): 2.1.3.1. Gi i thi u Mã hóa khóa công dùng khóa cá nhân c gi bí m t i v i nh ng ng i không quy n và m t khóa công c m i ng i bi t n. C khóa công và khóa bí m t có quan h toán h c v i nhau; d li u c mã hóa v i khóa công ch có th c gi i mã v i khóa bí m t và d li u c ký v i khoá bí m t có th c ki m tra v i khóa công. Khóa công s n có v i b t k ai. C hai khóa là duy nh t v i phiên truy n. Các thu t toán m t mã khóa công c ng c 9 bi t n nh các thu t toán b t i x ng b i vì m t khóa d li u trong khi khóa kia gi i mã d li u. c yêu c u mã hóa K H TN Các thu t toán m t mã khóa công dùng kích th c vùng nh c nh trong khi các thu t toán m t mã khóa bí m t dùng vùng nh có chi u dài bi n i. Các thu t toán khoá công không th dùng d li u d ng xích v i các chu i d li u theo cách các thu t toán khoá bí m t làm vì ch các kh i l ng d li u nh có th c mã hóa. Do ó, các thao tác b t i x ng không dùng cùng mô hình dòng d li u nh các thao tác i x ng. H Hai nhóm (A và B) có th dùng mã hóa khóa công nh sau: u tiên A phát sinh c p khóa khóa công khai – khoá bí m t. N u B mu n g i cho A m t thông i p c mã hóa, B yêu c u A khoá công khai. A g i cho B khóa công khai c a A trên m ng không an toàn và B dùng khóa này mã hóa thông i p (n u B nh n khóa c a A trên m t kênh truy n không an toàn nh m ng công c ng , B ph i xác nh n v i A r ng B nh n úng b n sao khóa công khai c a A). B g i thông p c mã hóa cho A và A gi i mã b ng khóa bí m t c a A. C N TT – Đ Trong quá trình truy n khoá công khai c a A, m t tác nhân không quy n có th ch n khóa l i. Ngoài ra, cùng tác nhân này có th ch n thông p mã hóa t B. Nh ng tác nhân này không th gi i mã thông i p v i khóa công khai. Thông i p ch có th gi i mã v i khóa bí m t c a A mà khóa này không c truy n. A không dùng khóa bí m t c a A mã hóa thông i p h i âm n B vì b t c ai v i khóa công khai có th gi i mã thông i p c. N u A mu n g i thông p l i cho B, A s yêu c u khóa công khai c a B và mã hóa thông i p dùng khóa công khai ó. K ó, B gi i mã thông i p dùng khóa bí m t t ng ng c a B. Trong th c t , A và B dùng mã hóa khóa công khai (b t i x ng) truy n khóa bí m t ( i x ng) và dùng mã hóa khóa bí m t cho ph n còn l i c a phiên. K H O A Mã hóa khoá công khai có không gian khóa hay ph m vi các giá tr có th cho khóa l n h n, và do ó ít b nh h ng do t n công vét c n h n khi th m i khóa có th . Khóa công khai d phân ph i b i vì nó không ph i b o m t. Các thu t toán khóa công khai có th c dùng t o ch ký s xác nh n nh danh ng i g i d li u. Tuy nhiên, các thu t toán khóa công khai thì r t ch m (so v i các thu t toán khóa bí m t) và th ng không phù h p khi mã hoá kh i l ng d li u l n. i n hình, mã hóa khóa công c dùng mã hóa khóa và IV c dùng b i thu t toán khóa bí m t. Sau khi khóa và IV c truy n, k ó mã hóa khóa bí m t c dùng cho ph n còn l i c a phiên. RSA là m t minh ho n i ti ng c a ph ng pháp mã hóa công khai. Tuy nhiên, RSA r t ch m trong khi yêu c u b o m t ngày nay không ch ng d ng trên m ng có dây mà còn áp d ng cho m ng không dây và các thi t b c m tay b h n ch nhi u v kh n ng l u tr , n ng l ng, t c nên m t ph ng pháp 10 khóa công m i (ECC) ã ra i vá áp ng các yêu c u này. C hai ph pháp s c trình bày chi ti t ph n sau. 2.1.3.2. ng Phân lo i h th ng mã hóa khóa công: q Bài toán phân tích ra th a s Problem IFP) Cho tr nguyên t K H TN Hi n nay, ng i ta chia các h th ng m t mã khóa công khai chu n công nghi p thành 3 lo i d a trên c s toán h c và khó gi i quy t bài toán ng ng: (Integer Factorization c n là tích c a hai s nguyên t l n, tìm hai s n =pq => Tìm p,q? ó. H Các h th ng d a trên IFP g m RSA, Rabin Williams,…Nhi u h th ng ch ng t là an toàn, ngh a là r t khó khi phân tích n thành các th a s nguyên t . Đ q Bài toán logarit r i r c (Discrete Logarithm Problem DLP) C N TT – Cho n là s nguyên t , G = {i: 1≤ i ≤ n-1}, a là m t ph n t sinh c a G ngh a là b c c a a b ng n-1. V y ta có G = {ai: 0 ≤ i ≤ n – 2}. V i m i ph n t y thu c G, có duy nh t m t ph n t x thu c G sao cho y = ax (mod n) ph n t x này c g i là logarit r i r c c a y, v i c s a. K H O A Và ta có phép bi n i logarit r i r c G vào G, dùng mã hóa thông tin. gi i c bài toán logarit r i r c thì c n tìm c x (0 ≤ x ≤ n – 1). Tuy nhiên, hi n t i v n ch a có ph ng pháp nào gi i bài toán logarit r i r c hi u qu . k M t ví d v h th ng d a trên DLP là h th ng DSA mà chính ph hoa ang s d ng. q ECC (Elliptic Curve Cryptography): gi i quy t bài toán logarit r i r c trên ng cong Elip. 2.1.4. Ch ký 2.1.4.1. Gi i thi u: nt Các thu t toán khóa công c dùng t o các ch ký n t là m t ng d ng ch ng th c quan tr ng. Các ch ký n t ch ng th c nh danh ng i g i và b o v s toàn v n d li u. Dùng khóa công khai c phát sinh 11 b i A, ng i nh n d li u c a A có th xác nh n r ng A ã g i b ng cách so sánh ch ký n t v i d li u và khoá công c a A. K H TN M t ph ng pháp ch ký g m 2 thành ph n: thu t toán dùng t o ra ch ký n t và thu t toán xác nh n ch ký n t . Và m t ph ng pháp ch ký n t là m t b n m (P, K, A, S, V) th a các u ki n sau: § P là t p h u h n các thông p. § A là t p h p h u h n các ch ký có th s d ng. § Không gian khóa K là t p h p h u h n các khóa có th s d ng. § V i m i khóa k ∈ K, t n t i thu t toán ch ký và sigk ∈ S, và thu t toán xác nh n ch ký t ng ng verk ∈ V. V i m i thu t toán sigk : P → A, và P x A → {true, false} là các hàm th a u ki n: H  true neáu y = sig (x ) ∀x ∈ P, ∀y ∈ A : ver( x, y ) =  false neáu y ≠ sig (x ) – Đ Chu n DSS c a NIST b t u n m 1994 qui nh các gi i thu t ch ký c ch p nh n, chi u dài khóa, chi u dài thông i p, … m b o tính b o m t cao áp d ng vào các l nh v c kinh t th ng m i, ngân hàng, an ninh, quân i, chính ph , … DSS c ng công nh n 3 gi i thu t ch ký: DSA (Digital Signature Algorithm), RSA, ECDSA (Elipptic Curve Digital Signature Algorithm). K H O A C N TT dùng mã hóa khóa công khai cho vi c ký s m t thông p. u tiên A áp d ng thu t toán b m cho thông p t o mã khoá thông i p. Mã khóa thông i p là th hi n duy nh t và mang tính cô ng c a d li u. K ó A mã hóa mã khóa thông i p v i khóa bí m t c a A t o ra ch ký cá nhân. Khi nh n thông p và ch ký, B gi i mã ch ký dùng khóa công khai c a A ph c h i mã khóa thông i p, và b m thông i p dùng cùng hàm b m mà A dùng. N u mã khóa thông i p mà B làm trùng kh p mã khóa thông i p A g i. B m b o là thông i p này n t ch nhân khóa bí m t và thông i p không b s a i. L u ý là ch ký có th c ki m ch ng b i b t c ng i nào do khóa công khai c a ng i g i thì ph bi n và nó c bao g m trong nh d ng c a ch ký s . Ph ng pháp này không gi bí m t cho thông p i v i nh ng thông p bí m t thì thông i p này ph i c mã hóa (Hình 2.1). Khi g i n B tùy theo m c b o m t c a thông p mà ta s g i b n rõ hay b n mã thông i p. 12