ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
CHU VĂN HUY
NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP
BẢO MẬT VÀ XÁC THỰC BẢN QUYỀN ẢNH SỐ
LUẬN VĂN THẠC SĨ
HẢI PHÒNG - 2011 3
MỤC LỤC BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT 5
MỞ ĐẦU 6
Chương 1. CÁC KHÁI NIỆM CƠ BẢN 7
1.1. TNG QUAN V AN TOÀN THÔNG TIN 7
1.1.1. Khái nim h thng thông tin và tài sn h thng thông tin 7
1.1.2. Các mi vi h thng thông tin và bin 8
1.1.3. Mc tiêu và nguyên tc chung ca an toàn bo mt thông tin 9
1.1.4. V bo v bn quyn sn phm s 10
1.1.5. Thc trng vi phm bo v bn quyn sn phm s 11
o v bn quyn nh s 12
1.2. MT S KHÁI NIM V TOÁN HC 13
c chung ln nht, bi chung nh nht 13
1.2.2. Quan h 16
1.2.3. S nguyên t 19
Elgamal 97
NG DNH S 103
ng d 103
KẾT LUẬN 107
DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 108
TÀI LIỆU THAM KHẢO 109 5
BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT
Ký hiệu
Viết đầy đủ
Ý nghĩa
DCT
Discrete Cosine Transform
Bii Consine ri rc
DFT
Discrete Fourier Transform
Bii Fourier ri rc
DWT
Discrete Wavelet Transform
Bii sóng ri rc
HVS
Human Visual System
H thng th i
LSB
Least Significant Bit
Bit ít quan trng nht
MSE
, .
,
,
hình nh, âm thanh, video
Chương 1. CÁC KHÁI NIỆM CƠ BẢN
u tiên ta s tìm hiu mt s ni dung n n
v bo v bn quyn nh s s dng.
1.1. TỔNG QUAN VỀ AN TOÀN THÔNG TIN
1.1.1. Khái niệm hệ thống thông tin và tài sản hệ thống thông tin
Khái niệm: H thng thông tin là mt tp hp các máy tính gm các thành
phn phn cng, phn mm và d liu làm vii gian.
Tài sản của hệ thống thông tin bao gồm:
Phn cng
Phn mm
D liu
Truyn thông gia các máy tính ca h thng
ng làm vic
i 8
1.1.2. Các mối đe dọa đối với hệ thống thông tin và biện pháp ngăn chặn
Có 3 hình thức đe dọa đối với một hệ thống thông tin:
Phá hoại ng s phá hng thit b phn cng hoc phn
mm hong trên h thng.
Sửa đổi: Tài sn h thng b sng làm cho h
tha nó. Chng ht khu b i
thì i dùng trong h thng không th truy cp vào h th làm vic.
Can thiệp: Tài sn ca h thng b truy cp bi không có thm quyn.
Các đe dọa đối với một hệ thống thông tin có thể đến từ nhiều nguồn và
đƣợc thực hiện bởi các đối tƣợng khác nhau. Chúng có thể chia làm 3 loại:
Vic thnh v bo mt phi là khó và cn ti tt c các tình hung, kh
n công có th c thc hin.
Thông tin c bo v cho ti khi ht giá tr s dng hoc h
mt.
10
1.1.4. Vấn đề bảo vệ bản quyền sản phẩm số
c (protocol)
(mechanism)
.
c th
u b
th
.
(nó
b.
,
. a thông tin th
, trong khi
u d
. Tuy nhiên s
t ma
̃
(cryptography), giấu tin
(steganography), nén tin (compression), tƣờng lửa (firewall), mạng riêng ảo
(virtual private networks), Các công c ch s
,
,
.
11
1.1.5. Thực trạng vi phạm bảo vệ bản quyền sản phẩm số
trình bày phn m u, ng sn phm s trong lun cp
và tp trung nghiên cu là nh s. Hin nay, có hàng t bc c phân phi trên
các kênh truyn công cng. c tính d sao chép, d chnh sa nên
nhing li dng c ý p, làm sai lch, gi mo bc nh gc. T
có th n uy tín, thit hi v kinh t cho i ch s hu bc
nh c bit trong bi cnh bùng n ca mng Internet.
cho ảnh số bằng các phƣơng pháp “đánh dấu” tài liệu số nhƣ: thủy vân số, chữ
ký số; kết hợp với mã xác thực và hàm băm. 13
1.2. MỘT SỐ KHÁI NIỆM VỀ TOÁN HỌC
hic nhng thut toán s dng trong các h mã mât, trong ch
n tc mt mã. Chúng ta phi có kin thc nn tn
v toán hc, lý thuy
Phn này s h thng li mt s khái nin v toán hđồng dƣ số
học (modulo), số nguyên tố, các thuật toán kiểm tra số nguyên tố,
mt s lý thuyđộ phức tạp thuật toánc s dng trong mt
mã và an toàn d liu.
1.2.1. Ƣớc chung lớn nhất, bội chung nhỏ nhất
1/. Ƣớc số và bội số
Cho hai s u có mt s nguyên q sao cho a = b*q, thì
ta nói rng a chia hết cho b (kí hiu b\a b là ước ca a, và a là bội ca b.
Ví dụ: a = 6, b = 2, ta có 6 = 2*3, ký hiu 2\6. c ca 6, và 6 là
bi ca 2.
Cho các s n ti cp s nguyên (q, r) (0 r < |b|) duy nht
sao cho a = b * q + rq gi là thương nguyên, r gi là số dư ca phép chia
a cho b. Nu r = 0 thì ta có phép chia ht.
Ví dụ: a = 13, b = 5, ta có 12 = 5*2 + 3. = 2, s r = 3.
2/. Ƣớc chung lớn nhất, bội chung nhỏ nhất
S nguyên d c gi là ước chung ca các s nguyên a
1
, a
2
n
. Ký hiu d = gcd(a
1
, a
2
n
) hay d = UCLN(a
1
, a
2
n
).
Nu gcd(a
1
, a
2
n
) = 1, thì các s a
1
, a
2
n
c gi là nguyên tố cùng
nhau.
14
2
n
).
Ví dụ:
Vi a = 12, b = 15 thì gcd(12,15) = 3; lcm(12,15) = 60.
Hai s 8 và 13 là nguyên tố cùng nhau vì gcd(8, 13) = 1.
3/. Tính chất:
d=gcd(a
1
, a
2
,
n
) tn ti các s x
1
,
x
2
n
sao cho: d = a
1
x
1
+ a
2
x
2
n
x
n
d = gcd(a
1
, a
2
n
) gcd(a
1
/d, a
2
n
/d) = 1.
m = lcm(a
1
, a
2
n
) gcd(m/a
1
, m/a
2
n
) = 1.
c). Ví dụ: a = 30, b = 18;
a
b
r
a = b.q + r
30
18
12
30 = 18 * 1+12
18
12
6
18 = 12 * 1+6
12
6
0
12 = 6 * 2 + 0
gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6.
5/. Thuật toán Euclide mở rộng
a). Bài toán
Dữ liệu vào: Cho hai s
Kết quả: d = gcd (a,b) và hai s x, y sao cho: a*x + b*y = d.
b). Thuật toán (Mô phng bng ngôn ng Pascal)
Readln(a, b);
If b=0 Then
Begin
d := a; x := 1; y := 0;
writeln(d, x, y);
End
(a+b) (mod m) [(a mod m) + (b mod m)] (mod m)
(a-b) (mod m) [(a mod m) - (b mod m)] (mod m)
(a*b) (mod m) [(a mod m) * (b mod m)] (mod m)
Tổng quát:
Có th cng hoc tr tng v nhic theo cùng mt modulo m, ta
c mc theo cùng modulo m, tc là:
Nu a
i
i
(mod m), i = 1 k, thì
k
i
k
i
iiii
btat
1 1
(mod m) vi t
i
= ± 1.
Có th nhân tng v nhiu c theo cùng mc
mc theo cùng modulo m, tc là:
Nu a
i
i
n
n
(mod m) vi mi n
Z
+
Có th chia 2 v c cho mc chung nguyên t vi modulo:
Nu c\a, c\b, (c,m) =
Có th nhân 2 v c và modulo vi cùng mt s
Nu
Có th chia 2 v c và modulo cho cùng mt s
c chung ca chúng:
Nu c\(a,b,m) a/c
i k \ m
gcd(a, m) = gcd(b, m)
18
4/. Các lớp thặng dƣ
Quan h p Z (tp các s nguyên) là mt quan
h nh cht phn xi xng, bc co ra trên tp
Z mt phân hoch gm các lhai s nguyên thuc cùng mt lp
khi chúng có cùng mt s m.
Mi li din bi mt s duy nht trong tp Z
m
=-1}
là s trong lp cho m, ký hiu mt li din bi s a là
[a]
Mi s n u có th biu dic duy nhất i dng:
k
n
k
nn
PPPn
21
21
k, n
i
( i =1, 2, , k) là các s t nhiên, P
i
là các s nguyên t, tng
t khác nhau.
b). Định lý Mersenne
Cho p = 2
k
-1, nu p là s nguyên t, thì k phi là s nguyên t.
Chứng minh:
Bng phn chng, gi s k không là nguyên ti 1< a, b< k.
y: p = 2
k
-1 = 2
ab
-1 = (2
a
)
b
(p).
(q) = (p-1).(q-1).
d). Định lý Fecma
Nu p là s nguyên t, a là s nguyên, thì a
p
a (mod p).
Nu p không chia ht a, thì a
p-1
1 (mod p).
Ví dụ: 4
7
7-1
e). Định lý Euler
Nu gcd(a, m) = 1 thì a
(m)
ng hp m là s nguyên t,
nh lý Fecma.
Ví dụ: m = 10,
(m) =
(2).
a
= c
b+k
(m)
= c
b
.(c
(m)
)
k
nh lý Euler.
Nhận xét: H qu trên giúp gim nh via bc
cao.
Ví dụ: Ta thy
(15) =
(5).
:
2
1004
(mod 15) = 2
4
(mod 15) = 16 (mod 15) = 1.
21
(mod 103)
Khai trin s i d 2: 43 = 32+8+2+1 = 2
5
+2
3
+2
1
+2
0
(*)
Tính liên tip các
87 (mod 103) = 87 (ứng với 2
0
)
87
2
(mod 103) = 50 (ứng với 2
1
)
87
4
(mod 103) = 50
2
(mod 103) = 28 (ng vi 2
2
)
87
8
(mod 103) = 28
2
22
1.2.4. Khái niệm Nhóm
1/. Khái niệm Nhóm
Nhóm là mt cp hp khác rng, * là phép toán hai
ngôi trên G tho u kin sau:
Phép toán có tính kt hp: (x*y)*z = x*(y*z), x, y, z G.
Có phn t trung lp e G: x*e = e*x = x, x G.
Vi mi xG, có phn t ngh G:
2/. Nhóm Cyclic
c gi là Cyclic nc sinh ra bi mt trong các phn t ca
nó. Tc là có phn t g G mà mi phn t a u tn ti s n g
n
= a.
c gi là phần tử sinh hay phần tử nguyên thuỷ ca nhóm G.
Cấp ca G là s phn t nu nó hu hn, bng nu nó vô hn.
Ví dụ: Nhóm cng Z gm các s nguyên là nhóm Cyclic có phn t sinh là 1.
Lƣu ý:
Nu không tn ti s t g
n
=e thì G có cp là .
Trong ng hc li, tn ti s t nhiên nh nht n mà g
n
= e thì G s
gm n phn t khác nhau: e, g, g
2,
g
3,
. , g
n-1
n
*
có cp m thì m là ước của (n).
Các tính chất khác:
Z
n
*
thì: b
(n)
1 (mod n).
ì: (p) = p-1.
Định lý: Nu p là s nguyên t thì Z
n
*
là nhóm Cyclic.
4/. Ứng dụng của khái niệm nhóm
Các kt lun trên là nn t thc thi nhiu h n t.
Ví d Elgamal (1985),
24
1.2.5. Độ phức tạp thuật toán
1/. Độ phức tạp thuật toán
gian và
Thut toán đa thức là thu phc tp thi gian O(n
t
1.3.1. Khái niệm ảnh số
1./ Ảnh số là gì?
nh s là mt tp hm c s c biu
din bi mng hai chiu có m dòng và n ct. Ta nói nh gm m x n pixel m
nh)ng kí hi ch mt pixel. Tùy theo loi nh mà mt
pixel có th trên 1, 4, 8 hay 24 bit.
P(x,y) | x = 0n, y = 0 m
2/. Phần tử ảnh
nh trong thc t là nh liên tc v không gian và v giá tr sáng. có th
x lý nh bng máy tính cn thit phi tin hành s hoá nh. Trong quá trình s hoá,
i ta bii tín hiu liên tc sang tín hiu ri rc thông qua quá trình ly mu
(ri rc hóa v không ng hoá thành phn giá tr mà v nguyên tc bng
mng không phân bim k nhau.
i ta s dng khái nim picture element mà ta quen
gi là pixel (phn t nh). Mi pixel bao gm mt cp t ch v trí (x,y) và mt
mc xám nhnh. M pixel trên mt nh s phân gii
ca nh. phân gic li.
Ví dụ: mt nh s phân gii là 800 x m
theo chiu ngang m theo chiu dc.
Copyright: Tài liệu đại học ©