LUẬN VĂN: NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT VÀ ỨNG DỤNG

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:68

Thêm vào BST

Báo xấu

412
lượt xem 162
download

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

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

Chủ đề:

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

Lưu

Nội dung Text: LUẬN VĂN: NGHIÊN CỨU 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 Chương 1. CÁC KHÁI NIỆM CƠ BẢN .............................................. 3 1.1. CÁC KHÁI NIỆM TRONG TOÁN HỌC........................................ 3 1.1.1. Một số khái niệm trong số học .......................................................... 3 1.1.2. Một số khái niệm trong đại số ......................................................... 13 1.1.3. Khái niệm độ phức tạp của thuật toán ............................................. 17 1.2. MÃ HÓA ........................................................................................ 21 1.2.1. Khái niệm mã hóa dữ liệu ............................................................... 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 1.3.3. So sánh chữ ký thông thƣờng và chữ ký số .................................... 26 1.3.4. Tạo đại diện tài liệu và hàm băm .................................................... 27 Chương 2. CHỮ KÝ MÙ RSA ............................................................ 30 2.1. KHÁI NIỆM CHỮ KÝ MÙ ........................................................... 30 2.1.1. Sơ đồ chữ ký RSA ........................................................................... 30 2.1.2. Sơ đồ chữ ký mù RSA ..................................................................... 31 2.1.3. Ví dụ minh họa ................................................................................ 32 2.2. ỨNG DỤNG CHỮ KÝ MÙ ........................................................... 33 2.2.1. Ứng dụng trong tiền điện tử ............................................................ 33 2.2.2. Ứng dụng trong bỏ phiếu trực tuyến. .............................................. 34 Chương 3. CHỮ KÝ KHÔNG THỂ CHỐI BỎ ................................ 36 3.1. KHÁI NIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ ......................... 36 3.1.1. Sơ đồ chữ ký không thể chối bỏ Chaum – Van Antwerpen ............ 36 3.1.2. Ví dụ minh họa ................................................................................ 38 3.1.3. Một số đánh giá về sơ đồ................................................................. 39 3.2. HÌNH THỨC TẤN CÔNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ .. 43 3.2.1. Tống tiền ngƣời ký .......................................................................... 43 3.2.2. Nhiều ngƣời cùng xác thực chữ ký mà ngƣời ký không biết .......... 43
3.3. ỨNG DỤNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ ......................... 45 3.3.1. Ứng dụng trong thẻ chứng minh thƣ điện tử. .................................. 45 3.3.2. Ứng dụng trong ký hợp đồng qua điện thoại .................................. 45 Chương 4. THỬ NGHIỆM CÁC CHƢƠNG TRÌNH ...................... 46 4.1. THỬ NGHIỆM ỨNG DỤNG CHỮ KÝ SỐ .................................. 46 4.1.1. Giới thiệu ......................................................................................... 46 4.1.2. Mô tả hoạt động chƣơng trình ......................................................... 47 4.2. THỬ NGHIỆM CHƢƠNG TRÌNH KÝ MÙ RSA ........................ 53 4.2.1. Giới thiệu ......................................................................................... 53 4.2.2. Mô tả hoạt động chƣơng trình ......................................................... 53 4.3. THỬ NGHIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ ..................... 55 4.3.1. Giới thiệu ......................................................................................... 55 4.3.2. Mô tả hoạt động chƣơng trình ......................................................... 56 KẾT LUẬN ................................................................................................ 60
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
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 12 30 = 18 * 1+12 18 12 6 18 = 12 * 1+6 12 6 0 12 = 6 * 2 + 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) + m \ (a – b) (2) + Tồn tại số nguyên t sao cho a = b + m.t (3) + 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
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: n n n n =P1 1.P 2 2...P k k 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
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