1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thanh Hào
XỬ LÝ SONG SONG QUÁ TRÌNH SINH KHÓA
CỦA HỆ THỐNG CẤP PHÁT CHỨNG THỰC SỐ
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
2
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thanh Hào
XỬ LÝ SONG SONG QUÁ TRÌNH SINH KHÓA
CỦA HỆ THỐNG CẤP PHÁT CHỨNG THỰC SỐ
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.TSKH Phạm Huy Điển
HÀ NỘI - 2010
3
TÓM TẮT NỘI DUNG
Khóa luận có trình bày về một số vấn đề của an toàn thông tin hiện đại. Các vấn
đề đó đều dẫn đến một nhu cầu bức thiết là phải xây dựng một hệ thống chứng thực số,
tạo điều kiện cho các ứng dụng chữ ký số phát triển. Phần tiếp theo là các lý thuyết về
chứng thực và chữ ký số, hệ thống chứng thực số CA ứng dụng hệ mã RSA mà cốt lõi
là quá trình sinh khóa. Thực chất của quá trình sinh khóa là sinh ra một cặp số nguyên
tố
q
p
,
thỏa mãn được các tính chất là số nguyên tố xác suất mạnh. Với yêu cầu về số
nguyên tố như thế, phần tiếp theo khóa luận có đề cập đến các lý thuyết về số nguyên
tố, việc kiểm tra số nguyên tố, và các tính chất để một số nguyên tố được gọi là mạnh.
Với một khối lượng tính toán trên số nguyên lớn như vậy, xử lý tuần tự là không đáp
ứng được nhu cầu về thời gian, cho nên một phương pháp xử lý song song trên CPU
(central processing unit) đã được nhắc đến. Đó chính là bộ công cụ Visual Studio 2010
của Microsoft. Phần cuối của khóa luận là các kết quả đạt được và định hướng cho
tương lai.
4
MỤC LỤC
LỜI MỞ ĐẦU .............................................................................................................5
NỘI DUNG .................................................................................................................3
Chương 1. Những vấn đề của an toàn thông tin hiện đại ..........................................3
1.1. An toàn thông tin hiện đại .............................................................................3
1.2. Chứng thực và chữ ký số...............................................................................3
1.2.1. Hệ mã khóa công khai và việc tạo chữ ký số ..........................................3
1.2.2. Chứng thực số ........................................................................................8
1.3. Vai trò của CA và vấn đề then chốt trong thiết lập CA ................................10
1.3.1. Vai trò của CA .....................................................................................10
1.3.2. Sử dụng chứng thực số .........................................................................10
1.3.3. Các chức năng cơ bản của CA.............................................................11
1.3.4. Vấn đề then chốt trong thiết lập CA......................................................13
Chương 2. Một số công cụ toán học liên quan........................................................15
2.1. Số nguyên tố và hệ mã khóa công khai RSA ...............................................15
2.1.1. Hệ mã khóa công khai RSA..................................................................15
2.1.2. Lý thuyết toán học về số nguyên tố và các vấn đề liên quan .................17
2.2. Việc tính toán số nguyên tố và khái niệm số giả nguyên tố. Kiểm tra số giả
nguyên tố mạnh..................................................................................................20
2.2.1. Thuật toán kiểm tra số nguyên tố thông thường và khái niệm số giả
nguyên tố.......................................................................................................20
2.2.2. Kiểm tra số giả nguyên tố mạnh ...........................................................20
2.2.3. Tính nguyên tố mạnh của một số..........................................................25
2.3. Chìa khóa an toàn........................................................................................26
Chương 3. Tính toán song song..............................................................................28
3.1. Xử lý song song, cơ hội và thách thức [8]....................................................28
3.1.1. Cơ hội ..................................................................................................29
3.1.2. Những thách thức: Các vấn đề khó khăn gặp phải khi xử lý song song.30
3.1.3. Giải pháp: Các công nghệ song song trong Visual Studio 2010 Microsoft
.......................................................................................................................32
3.2. Lập trình song song với Visual Studio 2010 [8]...........................................33
3.2.1. Thư viện...............................................................................................33
3.2.2. Các mô hình lập trình song song và ví dụ.............................................34
3.2.3. Kết luận................................................................................................38
Chương 4. Kết quả triển khai và tính thử nghiệm...................................................39
4.1. Giới thiệu về chương trình ứng dụng...........................................................39
4.1.1. Mục đích và hoạt động của chương trình..............................................39
4.1.2. Một số hình ảnh về chương trình ..........................................................40
4.2. Một số thống kê khi chạy chương trình trên chip intel core2duo 2.2 GHZ...43
PHỤ LỤC..................................................................................................................44
A. Thuật toán Miller-Rabin....................................................................................44
B. Thuật toán Lucas...............................................................................................44
C. Thuật toán kiểm tra nguyên tố mạnh..................................................................45
KẾT LUẬN ...............................................................................................................47
TÀI LIỆU THAM KHẢO..........................................................................................48
5
LỜI MỞ ĐẦU
Hiện nay, ở các nước phát triển cũng như đang phát triển, mạng máy tính đóng
vài trò quan trọng trong mọi lĩnh vực hoạt động của xã hội, và một khi nó trở thành
phương tiện điều hành các hệ thống thì nhu cầu bảo mật thông tin được đặt lên hàng
đầu. Nhu cầu này không chỉ có ở các bộ máy của nhà nước, mà đã trở thành bức thiết
trong nhiều hoạt động kinh tế xã hội: tài chính, ngân hàng, thương mại … Những ứng
dụng trong dân sự của an toàn thông tin ngày càng được phát triển, mở rộng đặc biệt là
chữ ký số. Khi các văn bản tài liệu đã được số hóa, được chuyển đi rất nhanh trong hệ
thống mạng thì ký tay thông thường là một trở ngại cho các hoạt động trao đổi thông
tin. Bên cạnh đó, một hệ thống chứng thực thông tin, chứng thực số là cần thiết được
phát triển khi mà nhu cầu trao đổi thông tin, xác thực thông tin của các cơ quan, xí
nghiệp, ngân hàng,… ngày càng tăng đi kèm với sự phát triển mạnh của cơ sở hạ tầng
mạng. Hệ thống chứng thực số CA (certificate authority) là một giải pháp cho vấn đề
này.
Với CA, mỗi người tham gia vào hệ thống được cấp phát một cặp chìa khóa bí
mật, công khai. Khi muốn gửi thông tin người sử dụng lấy chìa khóa bí mật mã hóa
văn bản và gửi đi, người nhận sẽ lấy chìa khóa công khai của người gửi để giải mã.
Đồng thời với sự chứng thực của hệ thống CA, đoạn thông tin đó sẽ được đảm bảo là
thuộc về người gửi. Ngoài ra, với những giấy tờ, hợp đồng kinh tế, … cần có chữ ký
của các bên liên quan, người ký có thể sử dụng chìa khóa bí mật để mã hóa văn bản.
(Hành động này giống như ký tay trên giấy tờ hành chính thông thường). Như vậy,
việc xây dựng hệ thống CA là quan trọng, cần thiết trong đời sống xã hội mà công
nghệ thông tin đóng vài trò chủ chốt trong giao dịch, buôn bán.
Một ví dụ cụ thể, trung tâm tin học thuộc viện nghiên cứu khoa học và công nghệ
Việt nam đang có dự án xây dựng hệ thống CA để phát triển các ứng dụng của chữ ký
số và chứng thực điện tử. Kết quả của khóa luận này sẽ được dùng trong quá trình rất
quan trọng của hệ thống CA sắp tới được phát triển – cấp phát khóa.
Vấn đề then chốt của hệ thống CA là quá trình cấp phát và chứng thực một khóa
có thuộc về một cá thể nào đó hay không. Quá trình cấp phát khóa về thực chất là sinh
ra một cặp số nguyên tố thỏa mãn các yếu cầu để được là nguyên tố mạnh. Những tính
toán trên số nguyên lớn đòi hỏi thời gian rất lâu để sinh ra một cặp số như vậy, chưa
kể đến thời gian kiểm tra thỏa mãn tính nguyên tố mạnh. Hơn thế nữa, một hệ thống
CA khi được triển khai nếu gặp tình trạng có nhiều người sử dụng truy cập tại một thời