Luận văn:Nghiên cứu các phương pháp mã hoá – giấu tin đa tầng và ứng dụng

Chia sẻ: Nguyen Bao Ngoc | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

196
lượt xem 39
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn:Nghiên cứu các phương pháp mã hoá – giấu tin đa tầng và ứng dụng

TR 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 TN TR N H NG NG C – TR NG TH M TRANG H K H NGHIÊN C U CÁC PH NG PHÁP MÃ HOÁ – GI U TIN A T NG VÀ NG Đ NG – TT LU N V N C NHÂN TIN H C N C A O H K TP. HCM, 2004
TR 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 TN TR NG TH M TRANG - 0012694 TR N H NG NG C - 0012746 H K H NGHIÊN C U CÁC PH NG PHÁP Đ MÃ HOÁ – GI U TIN A T NG VÀ NG NG – TT LU N V N C NHÂN TIN H C N GIÁO VIÊN H NG D N T.S NGUY N ÌNH THÚC C Th.S PH M PH M TUY T TRINH A O H K NIÊN KHÓA 2000 - 2004
NH N XÉT C A GIÁO VIÊN H NG D N ....................................................................................................................... ....................................................................................................................... TN ....................................................................................................................... ....................................................................................................................... H ....................................................................................................................... K ....................................................................................................................... ....................................................................................................................... H ....................................................................................................................... Đ ....................................................................................................................... – ....................................................................................................................... ....................................................................................................................... TT ....................................................................................................................... ....................................................................................................................... N ....................................................................................................................... C ....................................................................................................................... A ....................................................................................................................... O H K
NH N XÉT C A GIÁO VIÊN PH N BI N ....................................................................................................................... ....................................................................................................................... TN ....................................................................................................................... ....................................................................................................................... H ....................................................................................................................... K ....................................................................................................................... ....................................................................................................................... H ....................................................................................................................... Đ ....................................................................................................................... – ....................................................................................................................... ....................................................................................................................... TT ....................................................................................................................... ....................................................................................................................... N ....................................................................................................................... C ....................................................................................................................... A ....................................................................................................................... O ....................................................................................................................... H K
IC M N Chúng em xin chân thành cám n Khoa Công Ngh Thông Tin, tr ng i H c Khoa H c T Nhiên TpHCM ã t o u ki n t t cho chúng em th c TN hi n 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 H chúng em trong su t th i gian th c h i n tài. K Chúng em xin chân thành cám n quý Th y Cô trong Khoa ã t n tình 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 h c v a q ua. Đ Chúng con xin nói lên lòng bi t n sâu s c i v i Ông Bà, Cha M ã – ch m sóc, nuôi d y chúng con thành ng i. Xin chân thành cám n các anh ch và b n b è ã ng h , giúp và TT 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 N n g cho phép nh ng ch c ch n s không tránh kh i n h ng thi u sót. Chúng C em kính mong nh n c s c m thông và t n tình ch b o c a q uý Th y Cô và các b n A . O Sinh viên H Tr n H ng Ng c – Tr ng Th M Trang K Tháng 07/ 2004
CL C —¯– DANH SÁCH CÁC HÌNH V .........................................................................1 Ch ng 1. Gi i thi u ..................................................................................2 TN 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 n guyên t ........................................................................4 H 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 K 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 H 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 TT 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 N 2.3.2. Thu t toán RSA.................................................................17 2.3.3. Nghi th c RSA ..................................................................18 C 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 A 2.4.2. M t s khái ni m ...............................................................19 2.4.2.1. Tr n g h u h n ...............................................................20 O 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 n g cong Elip................................................23 H 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 K 2.4.3.2. C p khóa n g 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
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 TN 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 n g s c dùng trong thu t toán........41 H 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 K 3.2.3.2. c t ..............................................................................45 3.2.3.3. Tính b o m t ...................................................................47 H 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 n g 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 TT 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 N 3.3.3.2. L p phi tuy n γ ...............................................................52 3.3.3.3. Hoán v theo chu k π ......................................................52 C 3.3.3.4. L p lan truy n tuy n tính θ ..............................................52 3.3.3.5. Phép c n g khoá σ[k]........................................................53 A 3.3.3.6. H ng s vòng cr...............................................................53 3.3.3.7. Hàm vòng p[k]................................................................53 O 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 H 3.3.3.11. Ch c n n g nén( Nguyên t c nén) ...................................54 3.3.3.12. Tính thông i p b m ......................................................54 K 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
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 n g 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 TN 4.6. Các d ng t n công ..........................................................................66 4.7. ng d n g c a ph ng pháp gi u d li u ........................................66 Ch ng 5. M t s n g d ng .....................................................................68 H 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 n g d ng ...........................................................70 K 5.2. Mô hình ch ký n t ..................................................................71 5.2.1. Mô hình t o ch ký............................................................71 H 5.2.2. Mô hình ch ng th c ch ký n t ...................................72 5.2.3. Giao di n n g d ng ...........................................................73 5.3. Nhúng tin vào phim và ng d n g ...................................................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 TT 5.3.2. Giao di n n g 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 N 6.2. H n g phát tri n ............................................................................78 Tài li u tham kh o..........................................................................................79 C 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 A O H K iii
DANH SÁCH CÁC HÌNH V Hình 2.1. Ch ký nt c g i cùng b n rõ thông i p ............................13 TN Hình 2.2. Ch ký nt c g i cùng b n mã c a thông p ....................13 Hình 2.3. So sánh m c 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 Hình 4.1. Hai m u watermark ........................................................................55 K Hình 4.2. Mô hình chung c a h th ng gi u d li u .......................................56 Hình 4.3. nhúng watermark b ng ph ng pháp d a trên block thích nghi H .......................................................................................................................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 ...........................70 Hình 5.3. Màn hình giao di n nhúng nhìn th y c......................................71 – Hình 5.4. Mô hình t o ch ký n t ............................................................71 TT Hình 5.5. Mô hình ch n g 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 N 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ý n t ...............................74 C Hình 5.9. Màn hình giao di n ng d ng c ng o .........................................76 Hình 5.10.Giao di n c a ch n g trình chính ..................................................76 A B ng 2.1.B n g so sánh v kích th c khóa công khai gi a ECC, RSA và AES O [7] ..................................................................................................................30 H K 1
Ch ng 1. Gi i thi u Trong nh ng n m g n ây, s p hát tri n n hanh chóng c a Internet và các công c x lý multimedia ã m ang 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 TN 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 p háp b o m t d li u c n g nh vi c ch ng nh n quy n s h u c a các cá nhân. Nh n g th thách này ã thu hút s chú ý c a n hi u n hà nghiên H c u trong l nh v c công ngh thông tin và toán: ó chính là b o m t: Ø Làm sao b o m t d li u? K Ø Làm sao ch n g 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 H ng i n h n b i 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 ? Đ 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 h i n n hi u d ng TT 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 p hát tri n m n h m c a khoa h c k thu t và các k thu t ph n c ng là không d . N 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, C 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: A 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. O 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 h mã khoá công khai RSA, ECC, h mã i x ng RC6 và so sánh gi a RSA và ECC. K Ch ng 3. Hàm b m - Gi i thi u m t s ph ng pháp b m h tr ng t c x lý cho vi c mã hoá d li u trong n g 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 ng d ng c xu t 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 - ánh giá các k t q u t c và a ra h ng phát tri n cho lu n v n. 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 n g pháp gi u d li u c trình bày trong TN Ch ng 4. Ph l c 2: K t qu th nghi m hàm b m Tiger và Whirlpool. H K H Đ – TT N C A O H K 3
Ch ng 2. M t s h th ng mã hoá 2.1. Các khái ni m c b n 2.1.1. S nguyên t TN 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 H hay b là b i s c a a, ký hi u a|b. K nh lý 2.1: V i a, b, c, x, y ∈ Z: a|a, 1|a; H 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) – 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, TT 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). N nh ngh a 2.3: § M t s n guyên c ∈ Z c g i là c chung c a a,b ∈ Z n u c|a C 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 A c a m i s chia c a a, b; (c ∈ Z, c|a, c|b ⇒ c|d). O nh ngh a 2.4: § M t s n guyên d ∈ Z c g i là b i chung c a a, b ∈ Z n u a|d H và b|d. § M t b i chung d ∈ N c a a, b ∈ Z, c g i là b i chung nh K 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 c g i là nguyên t cùng nhau, ký hi u a ⊥ b, n u a ∧ b=1. 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. nh ngh a 2.6: M t s nguyên a ≥ 2 c g i là s nguyên t n u nó ch có c s n g là 1 và a; ng c l i, a c g i là h p s . Vì th , 1 là h p s . T p t t c TN các s nguyên t ký hi u là P. 4 Ghi chú: § a,b ∈ P, a ≠ b ⇒ a ⊥ b; vì a và b ch có c chung d ng là 1. H § 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 K 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 h ay b ng 2 có ít nh t m t c s là s nguyên t : c chung nguyên t nh n h t c ng s l n h n h ay H b ng 2. Đ nh lý 2.2: ∀ a, b ∈ N*, a > b, ta có: a ∧ b = b (a % b) – 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) TT Cho a,b ∈ N, a > b > 1. t a = r0, b = r1. T n h ngh a 1.2, ta có: 0 ≤ r2 < r1 ; r0 = r1q1 + r2, N 0 ≤ r3 < r2 ; r1 = r2q1 + r3, ……………… C 0 ≤ rk < rk-1; 2 ≤ k ≤ n; rk-2 = rk-1q k-1 + rk, 0 = rn+1 < rn; rn-1 = rnq n + rn+1, ⇒ a = r0 > b = r1 > r2 > … > rn > rn+1 = 0. A V y, O rn = gcd(a, b); H Theo n h lý 2.2: gcd(a,b) = gcd(r0,r1) = gcd(r1,r2) = … = gcd(rn-1,rn) K = 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
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 n g 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 n guyên x mod m c a Zm TN c g i là rút g n modulo c a x theo m. nh ngh a 2.9: H 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 K o c a a modulo m, ký hi u a-1 (mod m), hay n gi n h n a-1. nh ngh a 2.10: ( nh ngh a hàm phi-Euler) H Cho n ≥ 1, t ϕ(n) là t p các s n guyên trong kho n g [1,n] nguyên t cùng nhau v i n. Hàm ϕ nh th c g i là hàm phi-Euler Đ 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*. TT u = xku (mod m), xk = 1 (mod m). n h lý Euler) x ⊥ m ⇒ xϕ(m) =1 (mod m). n h lý Fermat) p ∈ P, x ⊥ p ⇒ xp-1 = 1 (mod p). N p ∈ P, n ∈ Z ⇒ np = n (mod p). p ∈ P, n ∈ Z, r = s (mod ϕ(m)) ⇒ nr = ns (mod p). C N u p ,q là hai s n guyên t khác nhau và n = pq, thì ϕ(m) = (p-1)(q-1). nh lý 2.4: ( nh lý s d Trung Hoa) A 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 n ghi m trong Zn. O Ánh x f: Zn→Zn-1 × … × Znk, xác nh b i f(x) = (x mod n1, … , x mod n k), x ∈ Zn H M t s p hép tính nhanh trên các s nguyên: K q Phép toán mod trên tr ng Zm Ta có : x = y (mod m) Khi x, y, m là nh n g s nguyên l n, 0 ≤ x,y ≤ m, b ≥ 2 và y = ∑ y i b i là bi u di n c s b c a y, ta có: 0 ≤i ≤ I ∑ yi ( x * b i ) mod m)) mod m (x * y) mod m = (y0 * x + 0≤ i ≤ I (x * bi) mod m = (b * ((x * b i) mod m)) mod m, 0 ≤ i ≤ I 6
Vì th ta có th s d ng thu t gi i sau tính tích modulo P = (x*y)mod m Thu t gi i: (tr ng h p t n g quát) t x = x m od 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 TN 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 d i n nh p hân p = ∑0≤i ≤ I p i 2 . Vi c tính giá tr y = xp mod m H i c g i là phép l y th a mod. Ta có: K x p = x p 0 * ( x 2 ) p1 * ( x 4 ) p2 * ... * ( x 2 ) p i i H Thu t gi i: ∑ x ∈ Zm, p = pi 2i u vào: 0≤ i ≤ I Đ u ra: y = xp mod m – y = 1. N u p = 0, return y A = x. N u p0 = 1 thì y = x TT Cho I ch y t 1 n I, do: A = A2 m od m c. d. N u pi = 1 thì y = (A*y) mod m Return y N 2.1.2. Mã hóa khóa bí m t (Private-Key Encryption): C 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 p h i gi an toàn cho khoá t vi c truy c p b i các tác A 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 n g c g i là mã hoá khoá i x n g b i vì O 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 n hanh (so v i các thu t toán khoá công) và thích h p t t v i H vi c th c thi bi n i m t mã trên các dòng d li u l n. K 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 b yte c n p h 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 i v i Rijindael), các giá tr l n h n n ph i c mã hoá m t kh i t i m t th i m. 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 n g 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 TN 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 b i 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 H m t mã c bi t và có th ph c h i khoá. ch n g 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 K 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 n g này, các ph n u (header) thông p ph b i n H có th b nh n g 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á. Đ Ch có m t cách xâm ph m vào d li u c m ã hoá b n g 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 h i 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. TT 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 h i n m i cách tìm ki m d li u thì nó c n g ch có ý ngh a N nh vài ngày vì u không có k t q u . Do ó, ph ng pháp vét c n là không th th c hi n. C 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 n g v y, khoá ph i c gi bí m t A 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 n g c d ùng chung v i mã hóa khóa công truy n thông cá nhân O 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, H RC4,… K 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 n g gi i. K ó , A mã hóa v n b n dùng khóa và IV và g i n ó thông qua m n g 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 n g 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 p h 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) . 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 n g mã hóa khóa bí m t. Hai v n gây h n ch chính là: TN § Vn 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 n go i giao H nên không có tr ng i gì khi thay i khoá hay truy n khóa, nh n g ngày nay nhu c u nhi u n g i mu n truy n tin an toàn mà không c n bi t n hau qua Internet d n n vi c thi t l p kênh K truy n an toàn gi a hai ng i b t k không kh thi. § Vn qu n lý khóa: trong h th ng có n ng i s d ng, gi s H 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. – Gi i thi u ph ng pháp DIFFIE-HELLMAN trong truy n khóa TT â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 ∈Γ N A ch n m t s n g u nhiên a, và g i ga n B B ch n m t s n g u nhiên b, và g i gb n A C 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 A gi a h . N u m t k t n công bi t c g, ga, gb thì c n g r t khó xác n h gab. Bài toán này có quan h ch t ch n bài toán logarit r i r c. O 2.1.3. Mã khóa công khai (Public-Key Encyption): H 2.1.3.1. Gi i thi u K 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 n g c 9
bi t n nh các thu t toán b t i x ng b i vì m t khóa c yêu c u m ã hóa d li u t rong khi khóa kia gi i mã d li u . 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 n g không dùng cùng mô hình dòng d li u nh các thao tác i x n g. TN 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 m u n g i cho A m t H 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 n h n khóa c a A trên m t kênh truy n không an toàn nh m ng công K c n g , 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. H 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 TT 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 n g n g c a B. N Trong th c t , A và B dùng mã hóa khóa công khai (b t i x n g) truy n khóa bí m t ( i x n g) và dùng mã hóa khóa bí m t cho ph n còn l i C c a phiên. Mã hóa khoá công khai có không gian khóa hay ph m vi các giá tr có A th cho khóa l n h n , và do ó ít b nh h n g 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. O 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 l i u . Tuy nhiên, các thu t toán khóa công khai thì r t H 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 n g d li u l n . i n hình, mã hóa khóa công c dùng mã hóa khóa K 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 n hi u v kh n ng l u tr , n ng l n g, t c nên m t ph ng pháp 10
khóa công m i (ECC) ã ra i vá áp n g các yêu c u n ày. C hai ph ng pháp s c trình bày chi ti t p h n sau. 2.1.3.2. Phân lo i h th ng mã hóa khóa công: Hi n n ay, 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: TN q Bài toán phân tích ra th a s nguyên t (Integer Factorization Problem IFP) H Cho tr c n là tích c a hai s nguyên t l n , tìm hai s ó. n =pq => Tìm p,q? K Các h th n g 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 n guyên H t. q Bài toán logarit r i r c (Discrete Logarithm Problem DLP) Đ 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}. TT V i m i ph n t y thu c G, có duy nh t m t p h 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. N Và ta có phép bi n i logarit r i r c G vào G, dùng mã hóa thông c x (0 ≤ x ≤ n – 1). Tuy tin. gi i c bài toán logarit r i r c thì c n tìm C nhiên, hi n t i v n ch a có ph n g pháp nào gi i bài toán logarit r i r c hi u qu . A M t ví d v h th ng d a trên DLP là h th n g DSA mà chính ph hoa O k ang s d ng. q ECC (Elliptic Curve Cryptography): gi i q uy t b ài toán logarit r i H r c trên n g cong Elip. K 2.1.4. Ch ký nt 2.1.4.1. Gi i thi u: 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 n g 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 n h 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. 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 n g 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. TN § 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 n g n g 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 )=  K false neáu y ≠ sig (x ) H 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 n h 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). – dùng mã hóa khóa công khai cho vi c ký s m t thông p. u tiên TT 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 h i 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 N 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 C 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 n g b i b t c n g i nào do khóa công khai c a n g i g i thì ph bi n và nó c bao g m trong A nh d n g c a ch ký s . P h n g 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 O 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. H K 12