Nghiên cứu các phương pháp mã hoá – giấu tin đa tầng và ứng dụng
- 99 trang
- file .pdf
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
NG
Đ
MÃ HOÁ – GI U TIN A T NG VÀ 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 hi 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 qua.
Đ
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
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
C
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à
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 nguyê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.
2.2.2. Đ
Gi i thi u RC6 ..................................................................14
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 ng 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 ng 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 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
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 ng 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 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
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 ng 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 ng 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 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
TN
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
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 ng 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 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
TT
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
N
6.2. H ng 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
Hình 5.3. Màn hình giao di n nhúng nhìn th y
Đ c ...........................70
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 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
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 ng trình chính ..................................................76
A
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
O
[7] ..................................................................................................................30
H
K
1
Ch ng 1. Gi i thi u
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
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 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
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 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
H
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?
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
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 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 .
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 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 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 qu 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 ng 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 nguyê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 nguyê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
ng 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 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
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 nh ngh a 1.2, ta có:
r0 = r1q1 + r2, 0 ≤ r2 < r1 ;
N
r1 = r2q1 + r3, 0 ≤ r3 < r2 ;
………………
C
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.
A
V y,
O
rn = gcd(a, b);
H
Theo nh 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 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
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 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
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).
nh lý Euler) x ⊥ m ⇒ xϕ(m) =1 (mod m).
nh 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 nguyê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 nghi 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 phé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 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 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 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
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 di n
nh phâ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 = ∑0≤i≤ I pi 2
i
u vào:
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:
c. A = A2 mod m
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 ph 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 ng c g i là mã hoá khoá i x ng 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 nhanh (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 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 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 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
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 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
H
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
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 ng này, các ph n u (header) thông p ph bi n
H
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á.
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.
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 hi n m i cách tìm ki m d li u thì nó c ng ch có ý ngh a
N
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.
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 ng 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 ng 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 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) .
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à:
TN
§ 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
H
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
K
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
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 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
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 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.
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 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 c yêu c u mã hóa
d li u trong 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 ng không dùng cùng mô
hình dòng d li u nh các thao tác i x ng.
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 mu 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 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
K
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.
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 ng ng 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 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
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 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.
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 li 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 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
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 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 ng
pháp s c trình bày chi ti t ph n sau.
2.1.3.2. Phân lo i h th ng mã hóa khóa công:
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:
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 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
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 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.
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
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
C
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 .
A
M t ví d v h th ng d a trên DLP là h th ng DSA mà chính ph hoa
O
k ang s d ng.
q ECC (Elliptic Curve Cryptography): gi i quy t bài toán logarit r i
H
r c trên ng 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 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.
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.
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 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 ) =
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 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).
–
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 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
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 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
A
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
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
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
NG
Đ
MÃ HOÁ – GI U TIN A T NG VÀ 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 hi 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 qua.
Đ
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
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
C
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à
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 nguyê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.
2.2.2. Đ
Gi i thi u RC6 ..................................................................14
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 ng 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 ng 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 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
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 ng 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 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
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 ng 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 ng 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 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
TN
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
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 ng 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 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
TT
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
N
6.2. H ng 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
Hình 5.3. Màn hình giao di n nhúng nhìn th y
Đ c ...........................70
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 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
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 ng trình chính ..................................................76
A
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
O
[7] ..................................................................................................................30
H
K
1
Ch ng 1. Gi i thi u
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
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 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
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 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
H
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?
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
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 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 .
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 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 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 qu 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 ng 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 nguyê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 nguyê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
ng 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 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
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 nh ngh a 1.2, ta có:
r0 = r1q1 + r2, 0 ≤ r2 < r1 ;
N
r1 = r2q1 + r3, 0 ≤ r3 < r2 ;
………………
C
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.
A
V y,
O
rn = gcd(a, b);
H
Theo nh 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 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
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 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
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).
nh lý Euler) x ⊥ m ⇒ xϕ(m) =1 (mod m).
nh 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 nguyê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 nghi 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 phé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 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 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 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
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 di n
nh phâ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 = ∑0≤i≤ I pi 2
i
u vào:
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:
c. A = A2 mod m
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 ph 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 ng c g i là mã hoá khoá i x ng 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 nhanh (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 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 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 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
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 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
H
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
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 ng này, các ph n u (header) thông p ph bi n
H
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á.
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.
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 hi n m i cách tìm ki m d li u thì nó c ng ch có ý ngh a
N
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.
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 ng 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 ng 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 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) .
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à:
TN
§ 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
H
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
K
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
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 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
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 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.
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 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 c yêu c u mã hóa
d li u trong 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 ng không dùng cùng mô
hình dòng d li u nh các thao tác i x ng.
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 mu 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 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
K
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.
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 ng ng 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 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
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 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.
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 li 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 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
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 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 ng
pháp s c trình bày chi ti t ph n sau.
2.1.3.2. Phân lo i h th ng mã hóa khóa công:
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:
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 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
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 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.
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
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
C
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 .
A
M t ví d v h th ng d a trên DLP là h th ng DSA mà chính ph hoa
O
k ang s d ng.
q ECC (Elliptic Curve Cryptography): gi i quy t bài toán logarit r i
H
r c trên ng 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 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.
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.
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 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 ) =
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 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).
–
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 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
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 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
A
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
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