Luận văn Thạc sĩ Khoa học: Chữ ký mù và ứng dụng trong bỏ phiếu kín trực tuyến

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

Thêm vào BST

Báo xấu

30
lượt xem 3
download

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

Đề tài có cấu trúc gồm 3 chương trình bày tổng quan về một số cơ sở mật mã cần thiết và chữ ký mù; bỏ phiếu kín trực tuyến và một số cơ sở mật mã cần thiết áp dụng cho bỏ phiếu kín trực tuyến; phân tích, thiết kế và xây dựng ứng dụng bỏ phiếu kín tín nhiệm lãnh đạo cấp sở, ngành trực tuyến.

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 Thạc sĩ Khoa học: Chữ ký mù và ứng dụng trong bỏ phiếu kín trực tuyến

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TRẦN VĂN ÁNH CHỮ KÝ MÙ VÀ ỨNG DỤNG TRONG BỎ PHIẾU KÍN TRỰC TUYẾN LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TRẦN VĂN ÁNH CHỮ KÝ MÙ VÀ ỨNG DỤNG TRONG BỎ PHIẾU KÍN TRỰC TUYẾN Chuyên ngành: Bảo đảm toán cho máy tính và hệ thống tính toán Mã số: 60 46 35 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. TÔN QUỐC BÌNH Hà Nội – Năm 2014 Trang: 2
LỜI CẢM ƠN Để hoàn thành Luận văn “Chữ ký mù và ứng dụng trong bỏ phiếu kín trực tuyến”, tác giả đã nhận được sự hướng dẫn và giúp đỡ nhiệt tình của nhiều tập thể và cá nhân. Trước hết, tác giả xin trân trọng cảm ơn Ban lãnh đạo cùng Quý thầy cô trong Khoa Toán – Cơ – Tin học, Trường Đại học Khoa học Tự nhiên Hà Nội đã tận tình dạy dỗ; truyền đạt những kiến thức, kinh nghiệm quý báu và tạo điều kiện thuận lợi cho tác giả trong suốt thời gian học tập và thực hiện đề tài. Đặc biệt, tác giả xin gửi lời cảm ơn sâu sắc tới TS. Tôn Quốc Bình đã nhiệt tình hướng dẫn, cung cấp những kinh nghiệm quý báu của Thầy để giúp đỡ tác giả trong quá trình học tập và hoàn thành luận văn. Tác giả cũng xin trân trọng cám ơn Lãnh đạo Trường Chính trị tỉnh Thái Bình, các đồng nghiệp đã tạo mọi điều kiện thuận lợi, động viên tác giả trong suốt quá trình học tập và thực hiện đề tài. Trong phạm vi luận văn tốt nghiệp cao học khó có thể diễn đạt hết ý về mặt lý thuyết cũng như kỹ thuật, mặc dù đã cố gắng hoàn thành luận văn với tất cả sự nỗ lực của bản thân, xong luận văn khó có thể tránh khỏi những thiếu sót. Kính mong nhận được những ý kiến đóng góp để tác giả tiếp tục hoàn thiện kiến thức cũng như giải pháp của mình. Xin chân thành cảm ơn ! Hà Nội, tháng 12 năm 2014 Tác giả Trần Văn Ánh Trang: 3
MỤC LỤC LỜI CẢM ƠN ..................................................................................................................... 1 DANH MỤC CÁC THUẬT NGỮ, TỪ VIẾT TẮT ..................................................... 5 MỞ ĐẦU .............................................................................................................................. 6 1. Lý do chọn đề tài...............................................................................................6 2. Tổng quan về đề tài nghiên cứu. .......................................................................6 3. Mục đích nghiên cứu ........................................................................................7 4. Đối tượng và phạm vi nghiên cứu ....................................................................7 5. Phương pháp nghiên cứu ..................................................................................8 6. Bố cục Luận văn ...............................................................................................8 Chƣơng -1. CHỮ KÝ SỐ, CHỮ KÝ MÙ SỐ ................................................................ 9 1.1. Chữ ký số .....................................................................................................10 1.2. Sơ đồ chữ ký số RSA (Đề xuất năm 1978) .................................................21 1.3. Chữ ký mù. ..................................................................................................23 1.4. Kết luận chương...........................................................................................29 Chƣơng- 2. TỔNG QUAN VỀ BỎ PHIẾU KÍN TRỰC TUYẾN ...........................30 2.1. Một số khái niệm cơ bản .............................................................................30 2.2. Thực trạng bỏ phiếu kín trực tuyến .............................................................32 2.3. Tổ chức hệ thống bỏ phiếu kín trực tuyến ...................................................33 2.4. Một số kỹ thuật áp dụng trong bỏ phiếu kín trực tuyến. .............................37 2.5. Kết luận chương...........................................................................................52 Chƣơng - 3. PHÂN TÍCH THIẾT KẾ ỨNG DỤNG BỎ PHIẾU KÍN TRỰC TUYẾN...............................................................................................................................53 3.1. Phân tích ......................................................................................................53 3.3. Yêu cầu chức năng .......................................................................................56 3.4. Thiết kế chương trình. .................................................................................59 KẾT LUẬN ........................................................................................................68 TÀI LIỆU THAM KHẢO ..............................................................................................69 Trang: 4
DANH MỤC CÁC THUẬT NGỮ, TỪ VIẾT TẮT BTC Ban tổ chức CMTND Chứng minh thư nhân dân CNTT-TT Công nghệ thông tin và truyền thông CT Cử tri ĐK Đăng ký Gcd Ước số chung lớn nhất KP Kiểm phiếu KT Kiểm tra LAN Local- Area- Network: Mạng cục bộ MD5 Message Digest algorithm 5 - giải thuật của hàm băm PKI Public Key Infrastructure – Cơ sở hạ tầng khóa công khai RSA Rivest, Shamir and Adleman - Giải thuật mã hóa công khai Server Máy chủ, cung cấp các dịch vụ, ứng dụng SHA Secure Hash Algorithm – Giải thuật băm an toàn TT Trung thực Website Một loại siêu văn bản (tập tin dạng HTML hoặc XHTML) trình bày thông tin trên mạng Internet, tại một địa chỉ nhất định Trang: 5
MỞ ĐẦU 1. Lý do chọn đề tài Ngày nay với sự phát triển mạnh mẽ của Công nghệ thông tin và Truyền thông, Internet đã thâm nhập vào tất cả mọi lĩnh vực hoạt động của con người. Trong thực tế các hacker, các dạng virus luôn tấn công và là mối đe dọa của các nguồn tài nguyên thông tin. Như vậy những vấn đề đảm bảo an toàn thông tin trong các hệ thống máy tính là rất quan trọng. Mật mã học [1] là một trong kỹ thuật bảo mật thông tin và đảm bảo an toàn thông tin trong truyền thông. Nó không chỉ dừng lại trong lĩnh vực bảo mật thông tin mà còn phục vụ nhu cầu xác thực thông tin trên mạng. Một trong những giải pháp được đưa ra đó là “Chữ ký điện tử”, chữ ký số và đang được sử dụng để đảm bảo an toàn cho các giao dịch trên mạng như: Thương mại điện tử, Chính phủ điện tử, Hành chính công điện tử, bỏ phiếu điện tử.. Trong thực tiễn của đời sống xã hội thì việc bỏ phiếu để bầu cử các chức vụ, chức danh hay thăm dò sự tín nhiệm của lãnh đạo các cấp, các ngành thông qua việc bỏ phiếu kín là hoạt động thường xuyên, liên tục. Nhằm tăng hiệu quả, khách quan và tính chính xác, giảm chi phí trong việc bỏ phiếu, tác giả muốn nghiên cứu các kỹ thuật đảm bảo an toàn cho việc thực hiện bỏ phiếu kín trực tuyến. Xuất phát từ những vấn đề thực tiễn trên, em chọn đề tài: “Chữ ký mù và ứng dụng trong bỏ phiếu kín trực tuyến” là chủ đề chính của luận văn tốt nghiệp. 2. Tổng quan về đề tài nghiên cứu. [17] Nghiên cứu chữ ký điện tử và bỏ phiếu kín trực tuyến ở nước ngoài đã được nghiên cứu và thực hiện cho người dân bỏ phiếu trực tuyến, như ở: St.Alban của Anh do Oracle và British đồng phát triển, cử tri và mã nhận dạng cá nhân được gửi tới qua đường bưu điện và một mã nhận dạng bầu cử, do nhân viên phụ trách bầu cử trao tận tay. Cử tri sau đó có thể bỏ phiếu trực uyến qua internet hoặc qua các ki-ốt điện tử được đặt ở các điểm cố định. Đây Trang: 6
là các hệ thống mang tính bảo mật rất cao, chính vì vậy tác giả không tiếp cận để tìm hiểu các hệ thống đó một cách đầy đủ, mà chỉ tiếp cận để hiểu về một số vấn đề thuyết của các hệ thống bỏ phiếu trực tuyến đó. Ở Việt Nam chưa có hệ thống bỏ phiếu kín trực tuyến. Tuy nhiên cũng có rất nhiều các công trình nghiên cứu khoa học của PGS.TS Trịnh Nhật Tiến về Chữ ký “mù”, Chữ ký “mù nhóm” và ứng dụng của nó trong bỏ phiếu điện tử. Bên cạnh đó cũng có nhiều Luận văn thạc sĩ của tác giả Vương Thị Huyền Trang (CT-1002), Phạm Thị Vân Anh (Đồ án tốt nghiệp, Trường Đại học Công nghệ), Nguyễn Việt Thịnh (Đồ án tốt nghiệp, trường ĐH Dân Lập HP), Vũ Mạnh Khánh (luận văn nghiên cứu các kỹ thuật đảm bảo an toàn thông tin trong việc sử dụng tiền điện tử, trường Đại học công nghệ),.. Ở các công trình nghiên cứu chủ yếu đưa ra các vấn đề về lý thuyết, và minh họa cho lý thuyết, chưa đưa ra một ứng dụng cụ thể để có thể sử dụng trong hoạt động thực tiễn. Do đó luận văn tập trung nghiên cứu về quá trình bỏ phiếu kín trực tuyến, và xây dựng ứng dụng bỏ phiếu kín trực tuyến lấy phiếu tín nhiệm cho lãnh đạo cấp sở, ngành. 3. Mục đích nghiên cứu Luận văn nghiên cứu các kỹ thuật bảo mật thông tin phục vụ cho việc phân tích thiết kế và xây dựng ứng dụng bỏ phiếu kín trực tuyến. 4. Đối tƣợng và phạm vi nghiên cứu Tập trung nghiên cứu, tìm hiểu về quá trình thực hiện bỏ phiếu kín trực tuyến; các tiêu chuẩn, cơ sở mật mã, giải pháp công nghệ; trên cơ sở đó xây dựng ứng dụng bỏ phiếu kín tín nhiệm lãnh đạo cấp sở, ngành trực tuyến. Trang: 7
5. Phƣơng pháp nghiên cứu - Tiếp cận phân tích và tổng hợp: Đọc tài liệu, tổng hợp lý thuyết, phân tích lý thuyết về Hệ mật mã đối xứng, hệ mật mã bất đối xứng (hệ mật mã khóa công khai), chữ ký số, chữ ký mù - Tiếp cận theo định tính và định lượng: Nghiên cứu cơ sở khoa học của mã hóa, chữ ký số, chữ ký mù của các tác giả trong và ngoài nước, các bài báo, thu thập thông tin trên mạng, tìm hiểu các mô hình bảo mật, chứng chỉ số. Từ đó trình bày theo ý tưởng của mình về phân tích thiết kế và xây dựng ứng dụng bỏ phiếu kín trực tuyến. 6. Bố cục Luận văn Luận văn được trình bày trong 03 chương: - Chương 1: Tổng quan về một số cơ sở mật mã cần thiết và chữ ký mù - Chương 2: Bỏ phiếu kín trực tuyến và một số cơ sở mật mã cần thiết áp dụng cho bỏ phiếu kín trực tuyến. - Chương 3: Phân tích, thiết kế và xây dựng ứng dụng bỏ phiếu kín tín nhiệm lãnh đạo cấp sở, ngành trực tuyến. + Tìm hiểu yêu cầu công tác bỏ phiếu tín nhiệm. + Phân tích thiết kế và áp dụng các thuật toán để giải quyết yêu cầu. + Xây dựng ứng dụng bỏ phiếu kín tín nhiệm lãnh đạo cấp sở, ngành trực tuyến Trang: 8
Chƣơng -1. CHỮ KÝ SỐ, CHỮ KÝ MÙ SỐ Đặt vấn đề: An toàn thông tin nghĩa là thông tin được bảo vệ từ các hệ thống và dịch vụ hoạt động trên môi trường mạng có khả năng chống lại những can thiệp bất hợp pháp hay những tai họa không mong đợi; các thay đổi tác động đến độ an toàn của hệ thống là nhỏ nhất. Hệ thống không an toàn là hệ thống tồn tại những điểm như: thông tin bị rò rỉ ra ngoài - dữ liệu trong hệ thống bị người không được quyền truy nhập và lấy sử dụng, các thông tin trong hệ thống bị thay thế hoặc sửa đổi làm sai lệch một phần hoặc hoàn toàn nội dung… Giá trị thực sự của thông tin chỉ đạt được khi thông tin được cung cấp chính xác, kịp thời, đầy đủ, do đó hệ thống phải hoạt động chuẩn xác thì mới có thể đưa ra những thông tin có giá trị cao. Mục tiêu của an toàn bảo mật trong công nghệ thông tin là đưa ra một số tiêu chuẩn an toàn và áp dụng các tiêu chuẩn an toàn này vào chỗ thích hợp để giảm bớt và loại trừ những nguy hiểm có thể xảy ra. [1],[3] Ngày nay, với sự phát triển rất nhanh của khoa học công nghệ, các biện pháp tấn công của các tin tặc ngày càng tinh xảo hơn, độ an toàn của thông tin có thể bị đe dọa từ nhiều nơi, nhiều cách khác nhau, do đó chúng ta cần phải đưa ra các chính sách đề phòng thích hợp. Các yêu cầu cần thiết của việc bảo vệ thông tin và tài nguyên: - Đảm bảo tính bí mật (Security) thông tin không bị lộ đối với người không được phép. - Đảm bảo tính tin cậy (Confidentiality): Thông tin và tài nguyên mà người nhận xác nhận chỉ có duy nhất của người gửi nó. - Đảm bảo tính toàn vẹn (Integrity): Thông tin và tài nguyên không thể bị sửa đổi, thay thế bởi những người không có quyền hạn. - Đảm bảo tính sẵn sàng (Availability): Thông tin và tài nguyên luôn sẵn sàng để đáp ứng sử dụng cho người có quyền hạn. Trang: 9
- Đảm bảo tính không thể chối bỏ (Non-Repudiation): Thông tin và tài nguyên được xác nhận về mặt pháp luật của người cung cấp. 1.1. Chữ ký số 1.1.1. Một số khái niệm trong số học 1.1.1.1. Số nguyên tố và số nguyên tố cùng nhau. * Khái niệm Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước số là 1 và chính nó. Tức là số nguyên p>1 là số nguyên tố nếu p có các ước là ± 1 và ± p [2] * Ví dụ: Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 là số nguyên tố. Số 2 là số nguyên tố chẵn duy nhất. Số nguyên tố có vai trò và ý nghĩa to lớn trong số học và lý thuyết mật mã. Bài toán kiểm tra tính nguyên tố của một số nguyên dương n và phân tích một số n ra thừa số nguyên tố là các bài toán rất được quan tâm. Nếu Ước số chung lớn nhất của a1 , a2 ,..., an , ký hiệu gcd( a1 , a2 ,..., an ) = 1, thì các số a1 , a2 ,..., an gọi là nguyên tố cùng nhau. Ví dụ: Hai số 8 và 13 là nguyên tố cùng nhau, vì gcd(8, 13) = 1. 1.1.1.2. Phần tử nghịch đảo đối với phép nhân * Khái niệm: Cho a  Z n , nếu tồn tại b  Z n sao cho ab  1 (mod n), ta nói b là phần tử nghịch đảo của a trong Z n và ký hiệu a 1 . Với Z n = {0, 1, 2, .., n-1} là tập các số nguyên không âm < n Một phần tử có phần tử nghịch đảo gọi là khả nghịch. * Khái niệm Nhóm: - Nhóm là một bộ (G, *) trong đó: Trang: 10
+ * là phép toán hai ngôi + G  Ø, trên G thỏa mãn các tính chất (x*y)*z = x*(y*z) với mọi x, y, z  G Có phần tử trung lập e  G: x*e = e*x = x Có phần tử nghịch đảo x’ G: x*x‟ = x‟*x = e với mọi x  G - Cấp của nhóm, ký hiệu |G| là số phần tử của nhóm (có thể G có vô hạn các phần tử, cấp của G là vô cùng). * Định lí cơ bản của số học: Mọi số nguyên n > 1 đều có thể được phân tích một cách duy nhất dưới dạng các lũy thừa của các số nguyên tố khác nhau. k n= p i 1 i i  p11 p22 ... pkk , i  0 Trong đó pi (i=1, 2, .., k) là các số nguyên tố, từng đôi một khác nhau. Ví dụ: n= 2, n= 3, n= 4= 2.2, n= 5, n= 6= 2.3 * Hệ quả: Nếu a là một số nguyên tố và a là ước s ố củ a b *c , k ý hi ệu a|(b*c) thì ít nhất một trong 2 số b, c phải chia hết cho a. + Ước chung lớn nhất của 2 số tự nhiên a và b được kí hiệu là gcd(a,b). c là ước chung lớn nhất của a và b, ký hiệu c= gcd(a,b) nếu: + c là ước số của a và b + Bất kì một ước số chung nào của a và b đều nhỏ hơn hoặc bằng c. Tất cả các số nguyên khác 0 đều là ước của số 0. Suy ra: gcd(a,0) = a. * Một số định lý về số nguyên tố (đã đƣợc chứng minh) - Định lý Mersenne: Cho p = 2k -1, nếu p là số nguyên tố thì k phải là số nguyên tố. Trang: 11
- Định lý Lagrang: Nếu G là nhóm cấp n và a  G, thì cấp của a là ước của n. - Định lý Fermat: + Nếu p là một số nguyên tố và a là một số nguyên thì ap  a(mod p) + Nếu a không chia hết cho p tức là a (mod p)  0 thì ap-1  1 (mod p) - Định lý Trung Quốc về số dư: [16] Cho tập số nguyên tố cùng nhau từng đôi một m1, m2,…mk. Với mỗi bộ số nguyên bất kỳ a1, a2,…ak , hệ phương trình dạng: x ≡ ai (mod mi), (i =1, 2, …, k), luôn có nghiệm duy nhất theo modulo m, M = m1.m2.…mk . Nghiệm này có thể tính theo công thức: k x =  ai M i yi (mod M ) , Trong đó yi = Mi-1 (mod mi), i =1, 2,…,k. i 1 Với Mi = M / mi 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 ≡ 2 mod 3 x ≡ 3 mod 5 x ≡ 5 mod 7 Vì các số 3, 5, 7 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 = 3.5.7 = 105, Để tìm x mod m ta tính: M1 = M/3 = 35 → y1 = 35-1 mod 3 = 2 Trang: 12
M2 = M/5 = 21 → y2 = 21-1 mod 5= 1 M3 = M/7 = 15 → y3 = 15-1 mod 7 = 1 x = 2.35.2 + 3.21.1 + 5.15.1 (mod m) = 278 (mod 105)=68 (mod 105) Như vậy x có dạng x= 68 + k.105 (k là số nguyên hoặc số nguyên thích hợp nếu tìm nghiệm tự nhiên) 1.1.1.2. 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 (n) và gọi là hàm Euler. + Nhận xét: Nếu p là số nguyên tố, thì (p) = p -1 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ì (n) = (p) .(q) = (p-1).(q-1) 1.1.1.3 Quan hệ Đồng dư * Khái niệm Cho hai 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. * Tính chất của quan hệ đồng dƣ Trang: 13
- 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) - 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ích các đồng dư: (a*b) (mod n) ≡ [(a mod n) * (b mod n)] (mod n) 1.1.1.4. Tập thặng dư thu gọn theo modulo * Khái niệm Kí hiệu Z n = {0, 1, 2, ..., n-1} là tập các số nguyên không âm < n. Z n 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, (Z n , +) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n. Với phép (+) là phép cộng thông thường của các số nguyên. Kí hiệu Z *n = {x  Z n , x là nguyên tố cùng nhau với n}. Tức là x phải  0. Z *n được gọi là Tập thặng dư thu gọn theo mod n, có số phần tử là (n). Z *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 (Z *n , phép nhân mod n) không phải là nhóm Cyclic. Nhóm nhân Z *n là Cyclic chỉ khi n có dạng: 2 , 4, p k hay 2p k với p là nguyên tố lẻ. * Ví dụ: Cho n = 21, Z *n = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. Trang: 14
1.1.1.6. Độ phức tạp của thuật toán * Bài toán được diễn đạt bằng hai phần: Đầu vào: Các dữ liệu vào của bài toán. Đầu ra: Các dữ liệu ra của bài toán (kết quả). * 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: - 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 đầu vào ta nhận được kết quả đầu ra của bài 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. * Khái niệm Độ phức tạp của thuật toán 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à thuật toán, e là dữ liệu vào của bài toán đã được mã hóa 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à IA(e) là giá bộ nhớ. 1.1.2. Khái niệm chữ ký số: Để chứng thực nguồn gốc hay hiệu lực của một tài liệu văn bản (ví dụ như: Quyết định, công văn, ...), người ta dùng chữ ký “bằng tay” vào phía dưới của mỗi tài liệu. Như vậy người ký phải trực tiếp “ký bằng tay” vào tài liệu. Với các tài liệu được số hóa, người ta cũng có nhu cầu chứng thực nguồn gốc hay hiệu lực của các tài liệu này. Rõ ràng không thể “ký bằng tay” vào tài liệu, vì Trang: 15
chúng không được in ấn trên giấy. Tài liệu “số” (hay tài liệu “điện tử”) là một xâu các bít (0 hay 1), xâu bít có thể rất dài (nếu in trên giấy có thể hàng nghìn trang). “Chữ ký” để chứng thực một xâu bít tài liệu cũng không thể là một xâu bít nhỏ đặt phía dưới xâu bít tài liệu. Một “chữ ký” như vậy chắc chắn sẽ bị kẻ gian sao chép để đặt dưới một tài liệu khác bất hợp pháp. Các nhà khoa học đã phát minh ra “chữ ký số” để chứng thực một “tài liệu số” vào những năm 80 của thế kỷ 20. Đó chính là “bản mã” của xâu bít tài liệu. Người ta tạo ra “chữ ký số” (chữ ký điện tử) trên “tài liệu số” giống như tạo ra “bản mã” của tài liệu với “khóa lập mã”. Như vậy “ký số” trên “tài liệu số” là “ký” trên từng bít tài liệu. Kẻ gian khó thể giả mạo “chữ ký số” nếu nó không biết “khóa lập mã”. Để kiểm tra một “chữ ký số” thuộc về một “tài liệu số”, người ta giải mã “chữ ký số” bằng “khóa giải mã” và so sánh với tài liệu gốc. Ngoài ý nghĩa để chứng thực nguồn gốc hay hiệu lực của các tài liệu số hóa. Mặt mạnh của “chữ ký số” hơn “chữ ký tay” là ở chỗ người ta có thể “ký” vào tài liệu từ xa trên mạng công khai. Hơn thế nữa, có thể “ký” bằng các thiết bị cầm tay (ví dụ điện thoại di động) tại khắp mọi nơi (Ubiquitous) và di động (Mobile), miễn là kết nối được vào mạng. “Ký số” thực hiện trên từng bít tài liệu, nên độ dài của “chữ ký số ” ít nhất cũng bằng độ dài tài liệu. Do đó thay vì ký trên tài liệu dài, người ta thường dùng “hàm băm” để tạo “đại diện” cho tài liệu, sau đó mới “Ký số” lên “đại diện” này. Chúng ta có thể hiểu nôm na về chữ ký số như sau: là những thông tin đi kèm với dữ liệu nhằm xác định chủ của người gửi nó. Chữ ký số bao gồm 3 thành phần: Thuật toán tạo ra khóa, hàm tạo chữ ký và hàm kiểm tra chữ ký. Hàm tạo ra chữ ký là hàm tính toán chữ ký trên cơ sở khóa mật và dữ liệu cần ký. Trang: 16
Hàm kiểm tra chữ ký là hàm kiểm tra xem chữ ký đã cho có đúng với khóa công cộng không. Khóa này mọi người có quyền truy cập cho nên mọi người đều có thể kiểm tra được chữ ký. 1.1.3. Sơ đồ chữ ký số bao gồm các thành phần sau: Sơ đồ chữ ký là bộ năm (P, A, K, S, V), trong đó: P là tập hữu hạn các văn bản có thể. A là tập hữu hạn các chữ ký có thể. K là tập hữu hạn các khóa có thể. S là tập các thuật toán ký. V là tập các thuật toán kiểm thử. Với mỗi khóa k  K, có thuật toán ký Sigk  S, Sigk: P  A, có thuật toán kiểm tra chữ ký Verk  V, Verk: P x A  {đúng, sai}, thỏa mãn điều kiện sau với mọi x  P, y  A: Đúng, nếu y = Sigk (x) Verk (x, y) = Sai, nếu y  Sigk (x) Người ta thường dùng hệ mã hóa khóa công khai để lập “Sơ đồ chữ ký số”. Ở đây khóa bí mật a dùng làm khóa “ký”, khóa công khai b dùng làm khóa kiểm tra “chữ ký”. Ngược lại với việc mã hóa, dùng khóa công khai b để lập mã, dùng khóa bí mật a để giải mã. Do “ký” cần giữ bí mật nên phải dùng khóa bí mật a để “ký”, còn “chữ ký” là công khai cho mọi người biết, nên dùng khóa công khai b để kiểm tra. 1.1.4. Phân loại chữ ký theo đặc trƣng kiểm tra chữ ký * Chữ ký khôi phục thông điệp: Là loại chữ ký, trong đó người gửi chỉ cần gửi “chữ ký”, người nhận có thể khôi phục lại được thông điệp, đã được “ký” bởi “chữ ký” này. Trang: 17
Ví dụ: Chữ ký RSA là chữ ký khôi phục thông điệp. * Chữ ký đi kèm thông điệp: Là loại chữ ký, trong đó người gửi không chỉ cần gửi “chữ ký” mà phải gửi kèm cả thông điệp đã được “ký” bởi “chữ ký” này. Ngược lại, người nhận sẽ không có được thông điệp gốc. Ví dụ: Chữ ký Elgamal là chữ ký đi kèm thông điệp. 1.1.5. Phân loại chữ ký theo mức an toàn 1/. Chữ ký “không thể phủ nhận”: Nhằm tránh việc nhân bản chữ ký để sử dụng nhiều lần, tốt nhất là người gửi tham gia trực tiếp vào việc kiểm thử chữ ký. Điều đó được thực hiện bằng một giao thức kiểm thử, dưới dạng một giao thức mời hỏi và trả lời. Ví dụ: Chữ ký không phủ định (Chaum- van Antverpen). 2/. Chữ ký “một lần”: Để bảo đảm an toàn, “khóa ký” chỉ dùng 1 lần (one-time) trên 1 tài liệu. Ví dụ: Chữ ký một lần Lamport. Chữ ký Fail - Stop (Van Heyst & Pedersen). 1.1.6. Phân loại chữ ký theo ứng dụng đặc trƣng Chữ ký “mù” (Blind Signature). Chữ ký “nhóm” (Group Signature). Chữ ký “bội” (Multy Signature). Chữ ký “mù nhóm” (Blind Group Signature). Chữ ký “mù bội” (Blind Multy Signature). 1.1.7. Thuộc tính của chữ ký số. - Chữ ký phải có độ tin cậy (xác thực) Trang: 18
- Chữ ký không thể giả mạo: Chữ ký chứng minh chỉ có người ký đã ký vào tài liệu một cách chủ định mà không phải ai khác. - Chữ ký không thể được dùng lại: Chữ ký phải là một phần của tài liệu và không thể chuyển chữ ký sang tài liệu khác. - Tài liệu đã ký không thể thay đổi được nội dung. - Chống từ chối. Chỉ người ký mới có khóa bí mật để ký lên m. Các khả năng tấn công đối với chữ ký điện tử: 1. Tin tặc có thể giả mạo chữ ký tương ứng với văn bản đã chọn. 2. Tin tặc thử chọn thông điệp mà tương ứng với chữ ký đã cho. 3. Tin tặc có thể ăn trộm khóa mật và có thể ký trên bất kỳ một bức điện nào nó muốn giống như chủ của khóa mật. 4. Tin tặc có thể giả mạo người ký và ký một bức điện nào đó. 5. Tin tặc có thể đổi khóa công cộng bởi khóa của mình. 1.1.8. Một số vấn đề với chữ ký số - Ký số thực hiện trên từng bít của tài liệu. Trong thực tế, ta cần ký vào các tài liệu số có kích thước lớn. Như vậy tốn nhiều bộ nhớ để lưu trữ chữ ký, mặt khác tốn nhiều vấn đề khác… - Một sơ đồ chữ ký "an toàn" thì tốc độ ký chậm vì phải dùng nhiều phép toán số học phức tạp như số mũ modulo. - Sử dụng hệ mã hóa sơ đồ ký giống nhau (hoặc có thể khác nhau) nhưng thực tế lại cho ra bản mã hay chữ ký giống nhau. Điều này sẽ dẫn đến phức tạp cho việc xác thực. Để giải quyết các tình trạng trên người ta thường sử dụng "hàm băm" để tạo "đại diện" (hay bản tóm lược, thu gọn) cho tài liệu. Sau đó ký số lên "đại diện" này. Trang: 19
1.1.8.1. Hàm băm: (Hash function) * Hàm băm (h) Là hàm một chiều (One-way Hash) với các đặc tính sau: - Với tài liệu đầu vào (thông điệp gốc) x, chỉ thu được giá trị băm duy nhất z = h(x). - Nếu dữ liệu trong thông điệp x bị thay đổi hay bị xóa để thành thông điệp x‟, thì giá trị băm h(x‟)  h(x). - Dù chỉ là một sự thay đổi nhỏ, ví dụ chỉ thay đổi 1 bit dữ liệu của thông điệp gốc x, thì giá trị băm h(x) của nó cũng vẫn thay đổi. Điều này có nghĩa là: hai thông điệp khác nhau, thì giá trị băm của chúng cũng khác nhau. - Nội dung của thông điệp gốc “khó” thể suy ra từ giá trị hàm băm của nó. Nghĩa là: với thông điệp x thì “dễ ” tính được z = h(x), nhưng lại “khó” tính ngược lại được x nếu chỉ biết giá trị băm h(x) (kể cả khi biết hàm băm h). * Tính chất của hàm băm. - Hàm băm không va chạm yếu. Hàm băm h được gọi là không va chạm yếu, nếu cho trước bức điện x, “khó” thể tính toán để tìm ra bức điện x‟  x mà h(x‟) = h(x). - Hàm băm không va chạm mạnh. Hàm băm h được gọi là không va chạm mạnh nếu “khó” thể tính toán để tìm ra hai bức thông điệp khác nhau x‟ và x (x‟  x) mà có h(x‟) = h(x). - Hàm băm một chiều. Hàm băm h được gọi là hàm một chiều nếu khi cho trước một bản tóm lược thông báo z thì “khó thể” tính toán để tìm ra thông điệp ban đầu x sao cho h(x) = z. Ví dụ hàm băm MD5 biến đổi một thông điệp bất kỳ có chiều dài bất kỳ thành một khối có kích thước cố định 128 bits. MD5("cộng hòa xã hội chủ nghĩa việt nam") = 7b8e76fac176d53c53cb24843e31e759 Ngay cả khi một chuỗi rỗng cũng trả về một chuỗi số thập lục phân gồm 32 số liên tiếp: MD5("") = d41d8cd98f00b204e9800998ecf8427e Trang: 20