Khóa luận Nghiên cứu một số chữ ký số đặc biệt và ứng dụng
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Phạm Thị Vân Anh
NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT
VÀ ỨNG DỤNG
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Phạm Thị Vân Anh
NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT
VÀ ỨNG DỤNG
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hƣớng dẫn: PGS.TS. Trịnh Nhật Tiến
HÀ NỘI - 2010
LỜI CẢM ƠN
Trƣớc hết, em xin gửi lời cảm ơn sâu sắc tới PGS.TS. Trịnh Nhật Tiến đã hƣớng
dẫn em phát triển khóa luận đi từ lý thuyết đến ứng dụng. Sự hƣớng dẫn của thầy trong
suốt thời gian qua đã giúp em tiếp cận tới một hƣớng nghiên cứu khoa học mới: đó là
nghiên cứu trong lĩnh vực an toàn thông tin. Qua đó, những lý thuyết về an toàn thông
tin đã lôi cuốn em và sẽ trở thành hƣớng nghiên cứu tiếp của em sau khi tốt nghiệp.
Em xin bày tỏ lòng biết ơn đến các thầy cô trong trƣờng Đại học Công nghệ đã
giảng dạy và cho em những kiến thức quý báu, làm nền tảng để em hoàn thành khóa
luận cũng nhƣ thành công trong nghiên cứu, làm việc trong tƣơng lai.
Cuối cùng, cho em gửi lời cảm ơn sâu sắc tới gia đình, bạn bè đã động viên kịp
thời để em học tập tốt và hoàn thành đƣợc khóa luận.
Em xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2010
Sinh viên
Phạm Thị Vân Anh
TÓM TẮT KHÓA LUẬN
Những năm gần đây, nhu cầu trao đổi thông tin từ xa của con ngƣời ngày càng
lớn, các ứng dụng trao đổi thông tin qua mạng diễn ra ngày càng nhiều. Tuy nhiên,
mỗi loại ứng dụng có những đòi hỏi riêng khác nhau, ví dụ nhƣ ứng dụng bầu cử từ xa
cần phải che dấu đƣợc thông tin ngƣời bỏ phiếu, hoặc những văn bản đã đƣợc ký
nhƣng không muốn ai cũng có thể xác thực chữ ký khi chƣa đƣợc sự đồng ý của ngƣời
ký. Chữ ký mù và chữ ký không thể chối bỏ đã ra đời để giải quyết vấn đề nêu trên. Ý
tƣởng chính của ký mù là ngƣời ký không biết mình đang ký trên nội dung gì. Ý tƣởng
chính của chữ ký không thể chối bỏ là chữ ký mà ngƣời ký tham gia trực tiếp vào quá
trình xác thực chữ ký. Khóa luận tốt nghiệp này đề cập về mặt lý thuyết của hai loại
chữ ký trên, xây dựng ứng dụng minh họa tƣơng ứng với từng loại chữ ký; đồng thời
xây dựng một ứng dụng thực hiện ký số RSA trên file văn bản tiếng Việt sử dụng thƣ
viện mã nguồn mở OpenSSL.
MỤC LỤC
LỜI MỞ ĐẦU.............................................................................................. 1
1.2. MÃ HÓA ........................................................................................ 21
1.2.2. Phân loại hệ mã hóa ........................................................................22
1.3. KÝ SỐ............................................................................................. 25
1.3.1. Khái niệm chữ ký số........................................................................25
1.3.2. Phân loại chữ ký số. ........................................................................25
2.1.1. Sơ đồ chữ ký RSA...........................................................................30
2.1.3. Ví dụ minh họa................................................................................32
3.1.2. Ví dụ minh họa................................................................................38
4.1.1. Giới thiệu.........................................................................................46
4.2.1. Giới thiệu.........................................................................................53
DANH SÁCH BẢNG
DANH SÁCH HÌNH VẼ
Hình 1: Giao diện chương trình ký số RSA ..........................................................46
Hình 2: Giao diện chức năng “Ký”RSA...............................................................47
Hình 5: Giao diện chức năng giải mã DES ..........................................................51
LỜI MỞ ĐẦU
Trong những năm gần đây, sự bùng nổ của cách mạng thông tin đang diễn ra
nhanh chóng trên phạm vi toàn thế giới. Sự phổ biến rộng rãi của Internet đã kết nối
mọi ngƣời trên toàn thế giới lại với nhau, trở thành công cụ không thể thiếu, làm tăng
hiệu quả làm việc, tăng sự hiểu biết, trao đổi, cập nhật các thông tin một cách nhanh
chóng và tiện lợi.
Tuy nhiên Internet là một mạng mở, nó cũng chứa đựng nhiều hiểm họa đe dọa
hệ thống mạng, hệ thống máy tính, tài nguyên thông tin của các tổ chức, cá nhân. Ví
dụ những tin tức quan trọng nằm ở kho dữ liệu hay đang trên đƣờng truyền có thể bị
trộm cắp, bị làm cho sai lệch hoặc có thể bị làm giả mạo. Vì thế, nảy sinh yêu cầu phải
làm thế nào để văn bản khi đƣợc gửi sẽ không đƣợc nhìn thấy hay khó có thể giả mạo
dù cho có thể xâm nhập vào văn bản. Với sự ra đời của công nghệ mã hóa và chữ ký
số đã trợ giúp cho con ngƣời trong việc giải quyết các bài toán nan giải về an toàn
thông tin. Một tình huống nảy sinh khi trao đổi thông tin trên mạng, đó là khi ngƣời ta
nhận đƣợc một văn bản truyền trên mạng thì làm sao để có thể đảm bảo rằng đó là của
đối tác gửi cho mình. Tƣơng tự, ngƣời nhận nhận đƣợc tờ tiền điện tử thì có cách nào
để xác nhận rằng đó là của đối tác đã thanh toán cho họ. Ngoài ra còn có rất nhiều các
hoạt động kinh tế, xã hội từ xa nhƣ đàm phán, thanh toán, gửi tiền từ xa,... Do đó chữ
ký số đƣợc sử dụng ở rất nhiều lĩnh vực: trong kinh tế với việc trao đổi các hợp đồng
của các đối tác kinh doanh, trong xã hội là các cuộc bỏ phiếu điện tử hay thăm dò
thông tin từ xa,…
Tuy nhiên, yêu cầu về chữ ký đặt ra với các ứng dụng là khác nhau. Có những
ứng dụng đòi hỏi sự nặc danh của tài liệu đƣợc ký nhƣ ứng dụng bỏ phiếu điện tử, tiền
điện tử. Một số ứng dụng khác lại yêu cầu sự tham gia của ngƣời ký vào quá trình xác
thực chữ ký. Chữ ký mù (ra đời năm 1983) và chữ ký không thể chối bỏ ( ra đời năm
1989 ) đã giải quyết hai vấn đề nêu ra ở trên.
Trong khóa luận này, em chú trọng vào tìm hiểu cơ sở lý thuyết của chữ ký mù
và chữ ký không thể chối bỏ kèm theo ứng dụng minh họa với từng loại. Đồng thời
xây dựng một ứng dụng thử nghiệm chữ ký số RSA trên file text tiếng Việt. Khóa luận
bao gồm các phần cụ thể sau:
Chƣơng 1: Các khái niệm cơ bản: nêu lên những lý thuyết toán học cơ bản
mà bất kỳ bài toán an toàn thông tin nào cũng cần tới, các khái niệm cơ bản về mã hóa
và ký số.
1
Chƣơng 2: Chữ ký mù RSA: trình bày về sơ đồ chữ ký mù RSA, ví dụ minh
họa và ứng dụng chữ ký mù.
Chƣơng 3: Chữ ký không thể chối bỏ: trình bày về sơ đồ chữ ký không thể
chối bỏ Chaum van Antwerpen, ví dụ minh họa, các hình thức tấn công chữ ký không
thể chối bỏ và ứng dụng của của chữ ký này.
Chƣơng 4: Thử nghiệm các chƣơng trình: thử nghiệm chƣơng trình chữ ký
số RSA, chƣơng trình chữ ký mù RSA và chƣơng trình chữ ký không thể chối bỏ.
Kết luận.
2
Chương 1. CÁC KHÁI NIỆM CƠ BẢN
1.1. CÁC KHÁI NIỆM TRONG TOÁN HỌC
1.1.1. Một số khái niệm trong số học
1.1.1.1. Ước chung lớn nhất, bội chung nhỏ nhất
1/. Khái niệm
-
Ước số và bội số
+ Cho hai số nguyên a và b, b ≠ 0. Nếu có một số nguyên q sao cho a = b*q, ta
nói rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ước của a, và a là bội của b.
Ví dụ:
a = 6, b = 2, ta có 6 = 2*3, ký hiệu 2\6. Ở đây 2 là ƣớc của 6 và 6 là bội của 2
+ Cho các số nguyên a, b ≠ 0, tồn tại cặp số nguyên (q, r) (0 r < /b/) duy nhất
sao cho a = b * q + r. Khi đó q gọi là thương nguyên, r gọi là số dư của phép
chia a cho b. Nếu r = 0 thì ta có phép chia hết.
Ví dụ:
Cho a = 13, b = 5, ta có 13 = 5*2 + 3. Ở đây thƣơng là q = 2, số dƣ là r = 3.
Ước chung lớn nhất, bội chung nhỏ nhất
-
+ Số nguyên d đƣợc gọi là ƣớc chung của các số nguyên 푎1, 푎2, …, 푎푛 , nếu nó
là ƣớc của tất cả các số đó.
+ Số nguyên m đƣợc gọi là bội chung của các số nguyên 푎1, 푎2, …, 푎푛 , nếu nó
là bội của tất cả các số đó.
+ Một ƣớc chung d > 0 của các số nguyên 푎1, 푎2, …, 푎푛 , trong đó mọi ƣớc
chung của 푎1, 푎2, …, 푎푛 đều là ƣớc của d, thì d đƣợc gọi là ƣớc chung lớn
nhất (UCLN) của 푎1, 푎2, …, 푎푛 .
Ký hiệu d = gcd (푎1, 푎2, …, 푎푛 ) hay d = UCLN(푎1, 푎2, …, 푎푛 ).
Nếu gcd(푎1, 푎2, …, 푎푛 ) = 1, thì các số 푎1, 푎2, …, 푎푛 đƣợc gọi là nguyên tố
cùng nhau.
+ Một bội chung m > 0 của các số nguyên 푎1, 푎2, …, 푎푛 , trong đó mọi bội
chung của 푎1, 푎2, …, 푎푛 đều là bội của m, thì m đƣợc gọi là bội chung nhỏ
nhất (BCNN) của 푎1, 푎2, …, 푎푛 .
Ký hiệu m = lcm(푎1, 푎2, …, 푎푛 ) hay m = BCNN(푎1, 푎2, …, 푎푛 ).
3
Ví dụ:
Cho a =12, b =15, 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.
Tập 풁풏 và 풁풏∗
-
+ 푍푛 = 0, 1, 2, .. . , n-1 là tập các số nguyên không âm < n.
+ 푍푛∗= e 푍푛 , e là nguyên tố cùng nhau với n. Tức là e ≠ 0.
Ví dụ:
Z7 = {0, 1, 2, 3, 4, 5, 6}. Khi đó số phần tử của Z7 là |Z7 | = 7.
푍7∗ = {1, 2, 3, 4, 5, 6}. Khi đó số phần tử của 푍7∗ là |푍7∗| = 6.
2/. Tính chất
-
d = gcd(푎1, 푎2, …, 푎푛 ) tồn tại các số x1, x2,…, xn sao cho:
d = a1x1 + a2x2 + … + anxn
Đặc biệt: a1, a2, …, an nguyên tố cùng nhau tồn tại các số x1, x2,…, xn sao cho:
1 = a1x1 + a2x2 + … + anxn
-
-
-
-
-
d = gcd(푎1, 푎2, …, 푎푛 ) gcd(푎1/푑, 푎2/푑, …, 푎푛 /푑) =1.
m = lcm(푎1, 푎2, …, 푎푛 ) gcd(푚/푎1, 푚/푎2, …, 푚/푎푛 ) =1.
gcd(푚푎1, m푎2, …, m푎푛 ) = m * gcd(푎1, 푎2, …, 푎푛 ) (với m ≠ 0).
Nếu gcd(a, b) =1 thì lcm(a, b) = a * b
Nếu b > 0, a = bq + r thì gcd(a, b) = gcd(b, r)
3/. Thuật toán Euclide tìm ƣớc chung lớn nhất
-
Bài toán
+ Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b.
+ Kết quả: gcd(a,b).
-
Thuật toán (Mô phỏng bằng ngôn ngữ Pascal):
Readln(a, b);
While b>0 do begin
r := a mod b; a := b; b := r;
end;
Writeln(a);
4
Ví dụ: a=30, b=18; gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6
Bảng 1: Ví dụ sử dụng thuật toán Euclide tìm ước chung lớn nhất
a
b
r
a = b.q + r
30 = 18 * 1+12
18 = 12 * 1+6
12 = 6 * 2 + 0
30
18
12
6
12
6
18
12
0
4/. Thuật toán Euclide mở rộng
-
Bài toán:
+ Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b.
+ Kết quả: d = gcd (a,b) và hai số x, y sao cho: a.x + b.y = d.
Thuật toán (Mô phỏng bằng ngôn ngữ Pascal):
Readln(a, b);
-
IF b=0 THEN
Begin
d := a; x := 1; y := 0; writeln(d, x, y);
End
ELSE
Begin
x2 := 1; x1 := 0; y2 := 0; y1 := 1;
While b>0 Do
begin
q := a div b; r := a mod b;x := x2 – q * x1;
y := y2 – q * y1; a := b; b := r;
x2 := x1; x1 := x; y2 := y1; y1 := y;
end;
d := a; x := x2; y := y2;
writeln(d, x1, x2);
End;
5
1.1.1.2. Quan hệ “Đồng dư”
1/. Khái niệm
-
Cho các số nguyên a, b, m (m > 0). Ta nói rằng a và b “đồng dư” với nhau theo
modulo m nếu chia a và b cho m ta nhận đƣợc cùng một số dƣ.
Ký hiệu: a ≡ b (mod m).
Ví dụ: 17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, đƣợc cùng số dƣ là 2.
Nhận xét: Các mệnh đề sau đây là tƣơng đƣơng:
-
+ a ≡ b (mod m)
(1)
(2)
(3)
+ m \ (a – b)
+ Tồn tại số nguyên t sao cho a = b + m.t
Chứng minh:
+ (1) (2):
Nếu có (1), thì theo định nghĩa: a, b chia cho m, phải có cùng số dƣ, do đó:
a = mqa + r; b = mqb + r; Suy ra (a – b) = m.(qa - qb), tức là m \ (a - b).
+ (2) (3):
Nếu có (2), tức là m\(a – b). Nghĩa là có t ∈ Z sao cho a - b = mt hay a = b + mt
+ (3) (1):
Nếu có (3), tức là tồn tại số nguyên t sao cho a = b + m.t.
Lấy a chia cho m, giả sử thƣơng là qa và dƣ r, hay a = mqa + r (0 ≤ r < m), do đó:
b + m.t = a = mqa + r hay b = m(qa - t) + r (0 ≤ r < m).
Điều đó chứng tỏ khi chia a và b cho m đƣợc cùng số dƣ r, hay a ≡ b (mod m).
2/. Các tính chất của quan hệ “đồng dƣ”
-
Quan hệ “đồng dư” là quan hệ tương đương trong Z
Với mọi số nguyên dƣơng m ta có:
+ a ≡ a (mod m) với mọi a ∈ Z (tính chất phản xạ)
+ a ≡ b (mod m) thì b ≡ a (mod m) (tính chất đối xứng)
+ a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m) (tính chất bắc cầu)
6
-
Tổng hay hiệu các “đồng dư”
+ (a+b) (mod n) [(a mod n) + (b mod n)] (mod n)
+ (a- b) (mod n) [(a mod n) - (b mod n)] (mod n)
Tổng quát:
Có thể cộng hoặc trừ từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta
đƣợc một đồng dƣ thức theo cùng modulo m, tức là:
Nếu ai ≡ bi (mod m), i = 1...k, thì:
푘
푘
푡푖푎푖 ≡ 푡푖푏푖(푚표푑 푚) 푣ớ푖 푡푖 = ± 1
푖=1
푖=1
-
Tích các “đồng dƣ”:
(a * b) (mod n) [(a mod n) * (b mod n)] (mod n)
Tổng quát:
Có thể nhân từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta đƣợc một
đồng dƣ thức theo cùng modulo m, tức là:
Nếu ai ≡ bi (mod m) với i = 1...k, thì ta có:
푘
푘
푎푖 ≡ 푏푖 (푚표푑 푚)
푖=1
푖=1
-
Hệ quả:
+ Có thể cộng hoặc trừ cùng một số vào hai vế của một đồng dƣ thức.
+ Có thể chuyển vế các số hạng của đồng dƣ thức bằng cách đổi dấu các số hạng
đó.
+ Có thể cộng vào một vế của đồng dƣ thức một bội của modulo:
a ≡ b (mod m) a + km ≡ b (mod m) với mọi k Z
+ Có thể nhân hai vế của một đồng dƣ thức với cùng một số:
a ≡ b (mod m) ac ≡ bc (mod m) với mọi c Z
+ Có thể nâng lên lũy thừa bậc nguyên không âm cho 2 vế của một đồng dƣ
thức: a ≡ b (mod m) an ≡ bn (mod m) với mọi n Z+
+ Có thể chia 2 vế đồng dƣ thức cho một ƣớc chung nguyên tố với modulo:
c\a, c\b, (c,m) = 1, a ≡ b (mod m) a/c ≡ b/c (mod m)
7
+ Có thể nhân 2 vế đồng dƣ thức và modulo với cùng một số nguyên dƣơng:
Nếu a ≡ b (mod m), c > 0 ac ≡ bc (mod mc)
+ Có thể chia 2 vế đồng dƣ thức và modulo cho cùng một số nguyên dƣơng là
ƣớc chung của chúng:
Nếu c \ (a, b, m) a/c ≡ b/c (mod m/c)
+ a ≡ b (mod m) a ≡ b (mod k) với k \ m
+ a ≡ b (mod m) gcd(a, m) = gcd(b, m)
3/. Các lớp thặng dƣ
-
Quan hệ “đồng dƣ” theo modulo m trên tập Z (tập các số nguyên) là một quan hệ
tƣơng đƣơng (vì có tính chất phản xạ, đối xứng, bắc cầu), do đó nó tạo ra trên tập
Z một phân hoạch gồm các lớp tƣơng đƣơng: hai số nguyên thuộc cùng một lớp
tƣơng đƣơng khi và chỉ khi chúng có cùng một số dƣ khi chia cho m.
-
Mỗi lớp tƣơng đƣơng đại diện bởi một số duy nhất trong Zm = {0, 1, 2,…, m-1}
là số dƣ khi chia các số trong lớp cho m, ký hiệu một lớp đƣợc đại diện bởi số a
là [a]m .Nhƣ vậy [a]m = [b]m a ≡ b (mod m)
Vì vậy ta có thể đồng nhất Zm với tập các lớp tƣơng đƣơng theo modulo m.
-
Zm ={0, 1, 2,…, m-1} đƣợc gọi là tập các “thặng dư đầy đủ” theo modulo m.
Mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Zm một số đồng dƣ với mình
theo modulo m.
1.1.1.3. Số nguyên tố
1/. Khái niệm
Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ƣớc là 1 và chính nó.
Ví dụ:
Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 là số nguyên tố.
2/. Một số định lý về số nguyên tố
-
Định lý: về số nguyên dương > 1
Mọi số nguyên dƣơng n > 1 đều có thể biểu diễn đƣợc duy nhất dƣới dạng:
n1 n2
nk
.
...
n =P1 P2 Pk
trong đó: k, ni (i =1,2,..,k) là các số tự nhiên, Pi là các số
nguyên tố, từng đôi một khác nhau.
8
-
Định lý: Mersenne
Cho p = 2k -1, nếu p là số nguyên tố thì k phải là số nguyên tố.
Chứng minh
Bằng phản chứng, giả sử k không là nguyên tố. Khi đó k = a.b với 1 < a, b < k.
Nhƣ vậy p = 2k -1 = 2ab -1 = (2a)b -1= (2a -1).E
(Trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Newton).
Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử là sai, hay k là số nguyên
tố.
-
Hàm Euler
Cho số nguyên dƣơng n, số lƣợng các số nguyên dƣơng bé hơn n và nguyên tố
cùng nhau với n đƣợc ký hiệu (풏) và gọi là hàm Euler.
+ Nhận xét: Nếu p là số nguyên tố, thì 풑 = 풑 − ퟏ
Ví dụ:
Tập các số nguyên không âm nhỏ hơn 7 là Z7 = {0, 1, 2, 3, 4, 5, 6}.
Do 7 là số nguyên tố, nên tập các số nguyên dƣơng nhỏ hơn 7 và nguyên tố cùng
*
nhau với 7 là Z7 = {1, 2, 3, 4, 5, 6}. Khi đó |Z| = (p) = p - 1 = 7 - 1 = 6
+ Định lý về hàm Euler
Nếu n là tích của hai số nguyên tố p, q thì
푛 = 푝 . 푞 = 푝 − 1 . 푞 − 1
3/. Một số phƣơng pháp kiểm tra tính nguyên tố
Kiểm tra tính nguyên tố của một số nguyên dƣơng là bài toán nảy sinh trong
nhiều ứng dụng, đặc biệt là trong lý thuyết mật mã.
-
Phương pháp cổ điển
Ý tưởng: Kiểm tra tính nguyên tố của một số nguyên dƣơng n theo định nghĩa:
+ Thử lần lƣợt tìm các ƣớc của n, từ 2 đến n / 2.
+ Nếu không tìm đƣợc ƣớc nào thì kết luận n là nguyên tố.
9
Thuật toán:
KT := 0;
for i := 2 to sqrt(n) do
if (n mod i) = 0 then
begin
KT := 1; Break;
end;
IF KT = 1 THEN Writeln (‘n không nguyên tố ‘)
ELSE Writeln (‘n nguyên tố ‘);
-
Phương pháp “xác suất“
+ Trên cơ sở các định lý về số nguyên tố, hiện nay ngƣời ta có các phƣơng pháp
“xác suất“ để kiểm tra tính nguyên tố của một số nguyên dƣơng n.
Ví dụ các phƣơng pháp: Solovay-Strassen [13], Miller-Rabin [7][14],…
+ Định lý Ferma:
Nếu p là số nguyên tố, a là số nguyên, thì ap ≡ a (mod p).
Nếu p nguyên tố, p không chia hết cho a, thì ap-1 ≡ 1 (mod p).
Ví dụ: 47 ≡ 4 (mod 7); 47-1 ≡ 1 (mod 7).
+ Định lý Euler
Nếu gcd(a, m) = 1 thì 푎(푚) ≡ 1 (mod m).
Trƣờng hợp m là số nguyên tố, ta có định lý Ferma.
Ví dụ: m = 10, 푚 = 2 . 5 = 1 ∗ 4 = 4
Ta có 74 ≡ 1 (mod 10), 94 ≡ 1 (mod 10), 214 ≡ 1 (mod 10).
+ Hệ quả 1
Nếu gcd(c, m) = 1 và a ≡ b (mod (푚)) với a, b là các số tự nhiên, thì
ca ≡ cb (mod m) và suy ra ca ≡ 푐푎 푚표푑 (푚) ( mod m ).
Chứng minh: a ≡ b (mod (푚)) nên a = b + k(푚), k
푐푎 = 푐푏+푘(푚) = 푐푏 . (푐(푚))푘 ≡ 푐푏 (mod m), theo định lý Euler.
Z và vì vậy
10
Nhận xét: Hệ quả trên giúp giảm nhẹ việc tính toán đồng dƣ của lũy thừa bậc
cao.
Ví dụ: Ta thấy 15 = 5 . 3 = 4 ∗ 2 = 8 và 1004 ≡ 4 (mod 8).
Do đó 21004 (mod 15) = 24 (mod 15) = 16 (mod 15) = 1.
+ Hệ quả 2
Nếu các các số nguyên e, d thỏa mãn e.d ≡ 1 (mod 푚 ), thì với mọi số c
nguyên tố cùng nhau với m, ta có (ce)d ≡ c (mod m).
Chứng minh: Đặt a = e.d và b = 1, từ hệ quả 1 ta có hệ quả 2.
Hệ quả này đóng vai trò then chốt trong việc thiết lập các hệ mã mũ sau này (ví
dụ: hệ RSA [1][2] ).
4/. Tính toán đồng dƣ của “ lũy thừa” lớn
Để tính đồng dƣ của một số có lũy thừa a lớn theo modulo m, xét hai trƣờng hợp:
Trường hợp a > 풎
-
Trong trƣờng hợp a > m , khi ấy b < a. Ngƣời ta dùng hệ quả 1 để tính “đồng
dƣ” của “ lũy thừa” lớn.
-
Trường hợp 풎 > a
Trong thực tế tính toán thƣờng gặp m lớn, do đó 푚 lớn, thậm chí > a, khi ấy
ngƣời ta dùng kỹ thuật khác, ví dụ phƣơng pháp bình phƣơng liên tiếp.
+ Phương pháp bình phương liên tiếp
Ví dụ: Tính 8743 (mod 103).
Khai triển số mũ 43 dƣới dạng cơ số 2:
43 = 32 + 8 + 2 + 1 = 25 + 23 + 21 + 20 (*)
Tính liên tiếp các “đồng dƣ” bình phƣơng nhƣ sau:
87 (mod 103) = 87 (ứng với 20)
872 (mod 103) = 50 (ứng với 21)
874 (mod 103) = 502 (mod 103) = 28
878 (mod 103) = 282 (mod 103) = 63 (ứng với 23)
8716 (mod 103) = 632 (mod 103) = 55
11
8732 (mod 103) = 552 (mod 103) = 38 (ứng với 25)
Theo khai triển (*), lấy tích của các lũy thừa bậc 25 , 23 , 21 , 20 (rút gọn theo
modulo 103), thu đƣợc kết quả:
8743 (mod 103) = 38 * 63 * 50 * 87 (mod 103) = 85
+ Định lý về Số dư (ĐL Trung Quốc)
Cho tập số nguyên tố cùng nhau từng đôi một m1, m2,…mr. Với mỗi bộ số nguyên
bất kỳ a1, a2,…ar , hệ phƣơng trình đồng dƣ:
x ≡ ai (mod mi), (i =1, 2, …, r),
luôn có nghiệm duy nhất theo modulo m, m = m1.m2.…mr .
Nghiệm này có thể tính theo công thức:
x = a1m2m3…mrb1 + m1a2m3…mrb2 + m1m2a3m3…mrb3 +…+ m1m2…mr-1arbr
(mod m1.m2.…mr),
Trong đó bi = (m1.m2…mi-1mi+1…mr)-1 (mod mi), i =1, 2,…, r.
Nhận xét:
Định lý số dƣ Trung Quốc cho phép tính đồng dƣ theo modulo của một số lớn
(tích của nhiều số nguyên tố cùng nhau), thông qua tính toán đồng dƣ theo modulo các
số nhỏ (từng thừa số).
Ví dụ: Tìm nghiệm của hệ phƣơng trình:
x ≡ 3118 mod 5353
x ≡ 139 mod 391
x ≡ 239 mod 247
Vì các số 5353, 391, 247 nguyên tố cùng nhau, nên theo định lý Trung Quốc về
số dƣ, hệ có nghiệm duy nhất theo modulo m = 5353*391*247 = 516976681.
Để tìm x mod m ta tính:
m1 = m/5353 = 96577 → y1 = 96577-1 mod 5353 = 5329
m2 = m/391 = 1322191 → y2 = 1322191-1 mod 391= 16
m3 = m/247 = 2093023 → y3 = 2093023-1 mod 247 = 238
x = 3118.96577.5329 + 139.1322191.16 + 239.2093023.238 (mod m)
= 13824 (mod m)
12
1.1.2. Một số khái niệm trong đại số
1.1.2.1. Cấu trúc Nhóm
1/. Khái niệm Nhóm
-
Nhóm là một bộ (G, *), trong đó
+ * là phép toán hai ngôi
+ G , trên G thoả mãn ba tính chất sau:
. Phép toán có tính kết hợp: (x*y)*z = x*(y*z)
. Có phần tử phần tử trung lập e G: x * e = e * x = x
. x G, có phần tử nghịch đảo x’ G: x * x’ = x’ * x = e.
(x, y, z G)
(x G)
-
-
Cấp của nhóm G đƣợc hiểu là số phần tử của nhóm, ký hiệu là
Cấp của nhóm có thể là nếu G có vô hạn phần tử.
G
.
Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán.
Tính chất:
Nếu a * b = a * c, thì b = c
Nếu a * c = b * c, thì a = b
Ví dụ:
-
-
Tập hợp các số nguyên Z cùng với phép cộng (+) thông thƣờng là nhóm giao
hoán, có phần tử đơn vị là số 0. Gọi là nhóm cộng các số nguyên.
Tập Q* các số hữu tỷ khác 0 (hay tập R* các số thực khác 0), cùng với phép
nhân (*) thông thƣờng là nhóm giao hoán, gọi là nhóm nhân các số hữu tỷ (số
thực) khác 0.
-
Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán.
2/. Nhóm con của nhóm (G, *)
Nhóm con của G là tập S G, S , và thỏa mãn các tính chất sau:
-
-
-
Phần tử trung lập e của G nằm trong S.
S khép kín đối với phép tính (*) trong G, tức là x*y S
S khép kín đối với phép lấy nghịch đảo trong G, tức 푥−1 S (xS)
(푥, 푦 S)
13
1.1.2.2. Nhóm Cyclic
1/. Khái niệm nhóm Cyclic
Nhóm (G, *) đƣợc gọi là nhóm Cyclic nếu nó đƣợc sinh ra bởi một trong các
phần tử của nó.
Tức là có phần tử g G mà với mỗi a G, đều tồn tại số n N để
gn = g * g * … * g = a. (Chú ý g * g * … * g là g * g với n lần).
Khi đó g đƣợc gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G.
Nói cách khác: G đƣợc gọi là nhóm Cyclic nếu tồn tại g G sao cho mọi phần tử
trong G đều là một luỹ thừa nguyên nào đó của g.
Ví dụ: Nhóm (Z +, +) gồm các số nguyên dƣơng là Cyclic với phần tử sinh g = 1.
2/. Cấp của nhóm Cyclic
Cho (G, *) là nhóm Cyclic với phần tử sinh g và phần tử trung lập e.
-
-
Nếu tồn tại số tự nhiên nhỏ nhất n mà gn = e, thì G sẽ chỉ gồm có n phần tử khác
nhau: e, g, g2 , g3 , . . . , gn - 1 . Khi đó G đƣợc gọi là nhóm Cyclic hữu hạn cấp n.
Nếu không tồn tại số tự nhiên n để gn = e, thì G có cấp .
Ví dụ: (Z +, +) gồm các số nguyên dƣơng là Cyclic với phần tử sinh g = 1, e = 0.
Đó là nhóm Cyclic vô hạn, vì không tồn tại số tự nhiên n để gn = e.
3/. Cấp của một phần tử trong nhóm Cyclic
Phần tử G đƣợc gọi là có cấp d nếu d là số nguyên dƣơng nhỏ nhất sao cho
d = e, trong đó e là phần tử trung lập của G.
Nhƣ vậy phần tử có cấp 1, nếu = e.
1.1.2.3. Nhóm (풁풏∗ , phép nhân mod n)
1/. Khái niệm tập thặng dƣ thu gọn theo modulo
-
Kí hiệu Zn = 0, 1, 2, .. . , n-1 là tập các số nguyên không âm < n.
Zn và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1, phần tử trung
lập e = 0.
(Zn, + ) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n.
14
-
Kí hiệu 푍푛∗ = x Zn , x là nguyên tố cùng nhau với n (tức là x phải 0).
푍푛∗ đƣợc gọi là Tập thặng dư thu gọn theo mod n, có số phần tử là (n).
푍푛∗ với phép nhân mod n lập thành một nhóm (nhóm nhân),phần tử trung lập e=1.
*
-
-
Tổng quát (Zn , phép nhân mod n) không phải là nhóm Cyclic.
Nhóm nhân 푍푛∗ là Cyclic chỉ khi n có dạng: 2, 4, pk, hay 2pk với p là nguyên tố lẻ.
2/. Một số kết quả đã đƣợc chứng minh
-
-
Định lý Lagrange: Nếu G là nhóm cấp n và G, thì cấp của là ước của n.
Hệ quả: Giả sử Zn* có cấp m, thì m là ước của (n).
-
Định lý: Nếu p là số nguyên tố thì Z *p là nhóm Cyclic.
Nếu b Zn* thì 푏(n) 1 (mod n). Nếu p là số nguyên tố thì (p) = p - 1.
Do đó với b Z *p (b nguyên tố với p), thì 푏(p) 1 (mod n), hay bp -1 1 (mod n).
Chú ý:
Theo định nghĩa, phần tử Zn* có cấp d nếu d là số nguyên dƣơng nhỏ nhất
sao cho d = e trong Zn* . Nhƣ vậy trong Zn* ta hiểu là d e (mod n).
Định lý: Nhóm con của một nhóm Cyclic là một nhóm Cyclic.
3/. Phần tử nghịch đảo đối với phép nhân
-
-
Định nghĩa:
Cho a Zn , nếu tồn tại b Zn sao cho a.b 1 (mod n), ta nói b là phần tử
nghịch đảo của a trong Zn và ký hiệu a-1.
Một phần tử có phần tử nghịch đảo, gọi là khả nghịch.
-
-
Định lý: UCLN (a, n) = 1 Phần tử a Zn có phần tử nghịch đảo.
Chứng minh:
Nếu a.a-1 ≡ 1 (mod n) thì a.a-1 = 1 + kn ↔ a.a-1 - kn = 1 → (a, n) =1.
Nếu (a, n) = 1, ta có aa-1 + kn = 1 → a.a-1 = 1+kn, do đó a.a-1 ≡ 1 (mod n).
Hệ quả: Mọi phần tử trong 푍푛∗ đều có phần tử nghịch đảo.
15
-
Tìm phần tử nghịch đảo bằng Thuật toán Euclid mở rộng
Input: a Zn , n
Output: Phần tử nghịch đảo của a.
Procedure Invert(a,n);
begin
g0:=n; g1:=a; u0:=1; u1:=0; v0:=0; v1:=1; i:=1;
while gi 0 do
begin
y := gi-1 div gi;
ui+1 := ui-1 - y.ui; vi+1 := vi-1 - y.vi; i:=i+1;
end; t := vi-1;
if t > 0 then a-1 := t else a-1 := t + n;
end;
gi+1 := gi-1 - y.gi;
Ví dụ: Tìm phần tử nghịch đảo của 3 trong Z7
Tức là phải giải phƣơng trình 3.x ≡ 1 (mod 7), x sẽ là phần tử nghịch đảo của 3.
Bảng 2: Ví dụ sử dụng thuật toán Euclide mở rộng để tìm phần tử nghịch đảo
i
y
푔푖
7
푢푖
1
푣푖
0
0
1
2
3
3
0
1
2
3
1
1
-2
0
Vì t = v2 = -2 < 0 do đó x = a-1 := t + n = -2 + 7 = 5.
Vậy 5 là phần tử nghịch đảo của 3 trong Z7
Chú ý
-
-
Định lý (Euler tổng quát): Nếu (a, n) = 1 thì 푎(푛) mod n = 1
Hệ quả: Nếu p là số nguyên tố và (a, p) = 1, thì 푎푝−1 (mod p) = 1
16
4/. Khái niệm Logarit rời rạc
Cho p là số nguyên tố, g là phần tử nguyên thủy của Zp , 푍푝∗
“Logarit rời rạc” chính là việc giải phƣơng trình x = logg (mod p) với ẩn x.
Hay phải tìm số x duy nhất sao cho: gx (mod p).
5/. Thặng dƣ bậc hai
-
Thặng dƣ bậc hai:
Cho p là số nguyên tố lẻ, x là một số nguyên dƣơng p-1. x đƣợc gọi là “thặng
dư bậc hai” mod p, nếu phƣơng trình y2 x mod p có lời giải.
1.1.3. Khái niệm độ phức tạp của thuật toán
1.1.3.1. Khái niệm thuật toán
1/. Khái niệm bài toán
Bài toán đƣợc diễn đạt bằng hai phần:
-
-
Input: Các dữ liệu vào của bài toán.
Output: Các dữ liệu ra của bài toán (kết quả).
2/. Khái niệm thuật toán
-
”Thuật toán” đƣợc hiểu đơn giản là cách thức để giải một bài toán. Cũng có thể
đƣợc hiểu bằng hai quan niệm: Trực giác hay Hình thức nhƣ sau:
+ Quan niệm trực giác về ”Thuật toán”
Một cách trực giác, thuật toán đƣợc hiểu là một dãy hữu hạn các qui tắc (chỉ thị,
mệnh lệnh) mô tả một quá trình tính toán, để từ dữ liệu đã cho (Input) ta nhận đƣợc kết
quả (Output) của bài toán.
+ Quan niệm toán học về ”Thuật toán”
Một cách hình thức, ngƣời ta quan niệm thuật toán là một máy Turing.
-
Thuật toán đƣợc chia thành hai loại: Đơn định và không đơn định.
+ Thuật toán đơn định (Deterministic): Là thuật toán mà kết quả của mọi phép
toán đều đƣợc xác định duy nhất.
+ Thuật toán không đơn định (Non - deterministic): Là thuật toán có ít nhất
một phép toán mà kết quả của nó là không duy nhất.
17
1.1.3.2. Khái niệm độ phức tạp của thuật toán
1/. Chi phí của thuật toán (tính theo một bộ dữ liệu vào)
Chi phí phải trả cho một quá trình tính toán gồm chi phí về thời gian và bộ nhớ.
-
Chi phí thời gian của một quá trình tính toán là thời gian cần thiết để thực hiện
một quá trình tính toán.
Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản thực hiện
trong quá trình tính toán .
-
Chi phí bộ nhớ của một quá trình tính toán là số ô nhớ cần thiết để thực hiện một
quá trình tính toán.
Gọi A là một thuật toán, e là dữ liệu vào của bài toán đã đƣợc mã hoá bằng cách
nào đó. Thuật toán A tính trên dữ liệu vào e phải trả một giá nhất định.
Ta ký hiệu: tA (e) là giá thời gian và lA(e) là giá bộ nhớ.
2/. Độ phức tạp về bộ nhớ (trong trƣờng hợp xấu nhất)
lA(n) = max{l A (e), với |e| n}. (n là kích thƣớc đầu vào của thuật toán)
3/. Độ phức tạp thời gian (trƣờng hợp xấu nhất) tA(n) = max{tA(e), với |e| n}
4/. Độ phức tạp tiệm cận
Độ phức tạp PT(n) đƣợc gọi là tiệm cận tới hàm f(n), ký hiệu O(f(n)) nếu các
số n0 , c mà PT(n) c.f(n) , n n0.
5/. Độ phức tạp đa thức
Độ phức tạp PT(n) đƣợc gọi đa thức, nếu nó tiệm cận tới đa thức p(n).
6/. Thuật toán đa thức
-
Thuật toán đƣợc gọi là đa thức nếu độ phức tạp về thời gian trong trƣờng hợp
xấu nhất của nó là đa thức.
-
Nói cách khác:
+ Thuật toán thời gian đa thức: là thuật toán có độ phức tạp là O(nt) trong đó t
là hằng số.
+ Thuật toán thời gian hàm mũ: là thuật toán có độ phức tạp O(tf(n)) trong đó t
là hằng số và f(n) là hàm đa thức của n.
18
-
Thời gian chạy của các lớp thuật toán khác nhau:
Bảng 3: Thời gian chạy của các lớp thuật toán khác nhau
Độ phức tạp
O(1)
Số phép tính(n=106)
Thời gian(106phép tính/s)
1
106
1micro giây
O(n)
1 giây
O(n2)
1012
11,6 ngày
O(n3)
1018
32 000 năm
O(2n)
10301030
10301006 tuổi của vũ trụ
-
Có ngƣời cho rằng ngày nay máy tính với tốc độ rất lớn, không cần quan tâm
nhiều tới thuật toán nhanh, chúng tôi xin dẫn một ví dụ đã đƣợc kiểm chứng.
Bài toán xử lý n đối tƣợng, có ba thuật toán với 3 mức phức tạp khác nhau sẽ
chịu 3 hậu quả nhƣ sau: Sau 1 giờ:
+ Thuật toán A có độ phức tạp O(n):
+ Thuật toán B có độ phức tạp O(nlog n):
+ Thuật toán C có độ phức tạp O(2n):
3,6 triệu đối tƣợng.
0,2 triệu đối tƣợng.
21 đối tƣợng.
1.1.3.3. Phân lớp bài toán theo độ phức tạp
1/. Các khái niệm
-
Khái niệm "Dẫn về được"
Bài toán B đƣợc gọi là "Dẫn về đƣợc” bài toán A một cách đa thức, ký hiệu:
B A, nếu có thuật toán đơn định đa thức để giải bài toán A thì cũng có thuật toán
đơn định đa thức để giải bài toán B.
Nghĩa là: Bài toán A "khó hơn" bài toán B, hay B "dễ” hơn A, B đƣợc diễn đạt
bằng ngôn ngữ của bài toán A, hay có thể hiểu B là trƣờng hợp riêng của A. Vậy nếu
giải đƣợc bài toán A thì cũng sẽ giải đƣợc bài toán B.
Quan hệ có tính chất bắc cầu: Nếu C B và B A thì C A.
-
Khái niệm "Khó tương đương"
Bài toán A gọi là “khó tƣơng đƣơng” bài toán B, ký hiệu A ~ B, nếu AB và
BA
19
2/. Phân lớp các bài toán
-
-
-
Cho một bài toán, có 2 khả năng xảy ra:
+ Đã có lời giải
+ Chƣa có lời giải
Cho một bài toán đã có lời giải, có 2 khả năng xảy ra:
+ Giải đƣợc bằng thuật toán
+ Không giải đƣợc bằng thuật toán
Cho một bài toán giải đƣợc bằng thuật toán, cũng chia thành 2 loại:
+ Thực tế giải đƣợc: hiểu là nó có thể giải đƣợc bởi thuật toán, xử lý trong thời
gian đủ nhanh, thực tế cho phép, đó là thuật toán có độ phức tạp thời gian là
“đa thức”. Bài toán này thuộc loại “dễ giải”.
+ Thực tế khó giải: hiểu là nó chỉ có thể giải đƣợc bởi thuật toán, xử lý trong
nhiều thời gian, thực tế khó chấp nhận, đó là thuật toán có độ phức tạp thời
gian là trên đa thức (“hàm mũ”). Bài toán này thuộc loại “khó giải”.
1.1.3.4. Hàm một phía và hàm cửa sập một phía
-
Hàm f(x) đƣợc gọi là hàm một phía nếu tính y = f(x) thì “dễ”, nhƣng tính
x = f -1(y) lại rất “khó”.
Ví dụ: Hàm f(x) = x (mod p), với p là số nguyên tố lớn, ( là phần tử nguyên
thuỷ mod p) là hàm một phía.
-
Hàm f(x) đƣợc gọi là hàm cửa sập một phía nếu tính y = f(x) thì “dễ”, nhƣng
tính x = f -1(y) lại rất “khó”. Tuy nhiên có cửa sập z để tính x = f -1(y) là “dễ”.
Ví dụ: Hàm y = f(x) = xa (mod n) (với n là tích của hai số nguyên tố lớn n = p*q)
là hàm một phía. Nếu chỉ biết a và n thì tính x = f-1(y) = 푦푏 푚표푑 푛 ( b thỏa mãn
ab ≡ 1 푚표푑 훷(푛)) rất khó nhƣng nếu biết cửa sập p và q thì tính đƣợc f-1(y) là khá dễ.
20
1.2. MÃ HÓA
1.2.1. Khái niệm mã hóa dữ liệu
Để bảo đảm an toàn thông tin lƣu trữ trong máy tính (ví dụ: giữ gìn thông tin cố
định) hay bảo đảm an toàn thông tin trên đƣờng truyền tin (ví dụ: trên mạng máy tính,
điện thoại), ngƣời ta phải “che giấu” các thông tin này.
-
“Che” thông tin (dữ liệu) hay “Mã hóa” thông tin là thay đổi hình dạng thông
tin gốc, và ngƣời khác “khó” nhận ra.
Nói cách khác “Mã hóa” thông tin là “che” đi “ý nghĩa” của thông tin, và ngƣời
khác “khó” hiểu đƣợc (“khó” đọc đƣợc) thông tin đã mã hoá.
-
“Giấu” thông tin (dữ liệu) là cất giấu thông tin trong bản tin khác, và ngƣời khác
cũng “khó” nhận ra.
Việc mã hoá phải theo quy tắc nhất định, quy tắc đó gọi là hệ mã hóa.
1.2.1.1. Hệ mã hóa
Hệ mã hóa đƣợc định nghĩa là bộ năm (P, C, K, E, D), trong đó:
P là tập hữu hạn các bản rõ có thể.
C là tập hữu hạn các bản mã có thể.
K là tập hữu hạn các khoá có thể.
E là tập các hàm lập mã.
D là tập các hàm giải mã.
Với khóa lập mã ke K, có hàm lập mã eke E, eke: P C,
Với khóa giải mã kd K, có hàm giải mã dkd D, dkd: C P sao cho
dkd (eke (T)) = T, T P. Ở đây T đƣợc gọi là bản rõ, eke (T) đƣợc gọi là bản mã.
1.2.1.2. Mã hóa và giải mã
Ngƣời gửi G (có khóa lập mã ke) eke (T) Ngƣời nhận N (có khóa giải mã kd)
Tin tặc có thể trộm bản mã eke (T)
21
Ngƣời gửi G muốn gửi bản tin T cho ngƣời nhận N. Để bảo đảm bí mật, G mã
hoá bản tin bằng khóa lập mã ke, thu đƣợc bản mã eke (T), sau đó gửi cho N. Tin tặc có
thể trộm bản mã eke (T), nhƣng cũng “khó” hiểu đƣợc bản tin gốc T nếu không có
khoá giải mã kd.
Ngƣời N nhận đƣợc bản mã, họ dùng khoá giải mã kd, để giải mã eke (T), sẽ nhận
đƣợc bản tin gốc T = dkd (eke (T)).
1.2.2. Phân loại hệ mã hóa
Hiện nay có hai loại mã hóa chính: Mã hóa khóa đối xứng và Mã hóa khoá công
khai.
-
Mã hóa khóa đối xứng: là hệ mã hóa có khóa lập mã và khóa giải mã “giống
nhau”, theo nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia, vì vậy cần phải
giữ bí mật cả 2 khóa.
-
Mã hóa khóa công khai: là hệ mã hóa có khóa lập mã khác khóa giải mã (ke
kd), biết đƣợc khóa này cũng “khó” tính đƣợc khóa kia. Vì thế khóa giải mã cần
phải đƣợc giữ bí mật, khóa lập mã đƣợc công khai.
1.2.2.1. Hệ mã hóa khóa đối xứng
Mã hóa khóa đối xứng là hệ mã hóa có khóa lập mã và khóa giải mã “giống
nhau”, theo nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia. Đặc biệt một số hệ
mã hóa loại này có khoá lập mã và khoá giải mã trùng nhau (ke = kd).
Hệ mã hóa khóa đối xứng còn có tên gọi là Hệ mã hóa khoá bí mật, vì phải giữ
bí mật cả 2 khóa. Trƣớc khi dùng hệ mã hóa khóa đối xứng, ngƣời gửi và ngƣời nhận
phải thoả thuận thuật toán mã hóa và một khoá chung (lập mã hay giải mã), khoá này
phải đƣợc giữ bí mật. Độ an toàn của hệ mã hóa loại này phụ thuộc vào khoá.
Ví dụ
-
Hệ mã hóa cổ điển thuộc loại mã hóa khóa đối xứng: dễ hiểu, dễ thực thi, nhƣng
có độ an toàn không cao. Vì giới hạn tính toán chỉ trong phạm vi bảng chữ cái, sử
dụng trong bản tin cần mã, ví dụ là Z26 nếu dùng các chữ cái tiếng Anh, là Z256
nếu dùng bảng mã ASCII . . . Với hệ mã hóa cổ điển, nếu biết khoá lập mã hay
thuật toán lập mã, ngƣời ta có thể “dễ” xác định đƣợc bản rõ, vì “dễ” tìm đƣợc
khoá giải mã.
-
Hệ mã hóa DES(1973) là mã hóa khóa đối xứng hiện đại, có độ an toàn cao (
[1], [2] ) .
22
1/. Các đặc điểm của hệ mã hóa khóa đối xứng
- Ƣu điểm:
+ Mã hóa khóa đối xứng mã hóa và giải mã nhanh hơn mã hóa khóa công khai.
- Hạn chế:
+ Mã hóa khóa đối xứng chƣa thật an toàn vì:
Ngƣời mã hoá và ngƣời giải mã phải có “chung” một khoá. Khóa phải đƣợc giữ
bí mật tuyệt đối, vì “dễ” xác định khoá này nếu biết khoá kia. Khi hai ngƣời (lập mã,
giải mã) cùng biết “chung” một bí mật, thì khó giữ đƣợc bí mật !
+ Vấn đề thỏa thuận khoá và quản lý khóa chung là khó khăn và phức tạp.
Ngƣời gửi và ngƣời nhận phải luôn thống nhất với nhau về khoá. Việc thay đổi
khoá là rất khó và dễ bị lộ. Khóa chung phải đƣợc gửi cho nhau trên kênh an toàn.
+ Không thể tạo ra chữ ký số.
2/. Phạm vi áp dụng hệ mã hóa đối xứng
-
Hệ mã hóa khóa đối xứng thƣờng đƣợc sử dụng trong môi trƣờng mà khoá chung
có thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ.
-
Hệ mã hóa khóa đối xứng dùng để mã hóa những bản tin lớn, vì tốc độ mã hóa và
giải mã nhanh hơn hệ mã hóa khóa công khai.
1.2.2.2. Hệ mã hóa khóa công khai
Hệ mã hóa khoá công khai do Diffie và Hellman phát minh vào những năm
1970.
Mã hóa khóa công khai là hệ mã hóa có khóa lập mã và khóa giải mã khác nhau
(ke kd), biết đƣợc khóa này cũng “khó” tính đƣợc khóa kia. Hệ mã hóa này đƣợc gọi
là hệ mã hoá khóa công khai, vì:
-
-
-
Khoá lập mã cho công khai, gọi là khoá công khai (public key).
Khóa giải mã giữ bí mật, còn gọi là khóa riêng (private key).
Một ngƣời bất kỳ có thể dùng khoá công khai để mã hoá bản tin, nhƣng chỉ
ngƣời nào có đúng khoá giải mã tƣơng ứng thì mới có khả năng xem đƣợc bản
rõ.
23
Tải về để xem bản đầy đủ
68 trang
16/04/2025
110
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận Nghiên cứu một số chữ ký số đặc biệt và ứng dụng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_nghien_cuu_mot_so_chu_ky_so_dac_biet_va_ung_dung.pdf
