ĐẠ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

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

Cán bộ hướng dẫn: PGS.TSKH Phạm Huy Điển

HÀ NỘI - 2010

2

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

qp,

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

3

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

4

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

5

điểm và yêu cầu cấp phát khóa, sẽ xảy ra hiện tượng nghẽn mạng, tắc cổ chai nếu phần

sinh khóa không đáng ứng được về thời gian. Hệ thống như thế được xem là không đạt yêu cầu. Một giải pháp được đưa ra là xử lý song song trong quá trình sinh khóa của

hệ thống CA.

Thời gian trước, công nghệ xử lý song song được thực hiện trên các cụm nhiều

máy chủ do thời ấy một CPU (central processing unit) không có nhiều nhân. Ngày nay, với sự phát triển vượt bậc của công nghệ phần cứng, các hãng phần cứng nổi

tiếng thế giới đã nghiên cứu và liên tục cho ra đời nhiều bộ xử lý tích hợp nhiều lõi

bên trong (2, 4, 8 thậm chí 16 lõi). Đây là một thời điểm thuận lợi để ứng dụng công

nghệ xử lý song song trên một CPU có nhiều nhân. Một phương án khác có lợi hơn về mặt kinh tế là tính toán trên card đồ họa (graphic card). Card đồ họa tuy có thế mạnh

về xử lý vector (xử lý nhiều bộ số một lúc) nhưng công nghệ song song còn chưa phát

triển (chưa có thư viện cần thiết để sinh được một cặp số nguyên tố lớn và kiểm tra tính nguyên tố mạnh của chúng). Vì vậy, xử lý song song trên CPU nhiều nhân là một

phương án hợp lý, cân đối về mặt kinh tế và công nghệ hỗ trợ cũng như là tốc độ. Tập

đoàn Microsoft mới cho ra đời bộ công cụ Visual Studio 2010 hỗ trợ xử lý song song

trên CPU nhiều nhân, đồng thời có thư viện xử lý số nguyên lớn. C Sharp (C#) – một ngôn ngữ lập trình trong bộ công cụ này sẽ được sử dụng để phát triển giai đoạn quan

trọng ban đầu của một hệ thống CA – sinh khóa.

2

Chương 1. Những vấn đề của an toàn thông tin hiện đại

NỘI DUNG

Chương 1. Những vấn đề của an toàn thông tin hiện đại

1.1. An toàn thông tin hiện đại

Hiện nay, ở tất cả các nước phát triển cũng như đang phát triển, mạng máy tính

đang đóng vài trò thiết yếu trong mọi lĩnh vực hoạt động của toàn 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 An ninh, Quốc phòng, Quản

lý 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 …

An toàn thông tin ngày nay không đơn thuần là việc giữ bí mật những thông tin quan trọng (được áp dụng trong quân đội, bộ quốc phòng, an ninh quốc gia …) mà còn

là chứng thực thông tin (thông tin đó thuộc về một cá nhân, tập thể cụ thể nào đó).

Những ứng dụng của an toàn thông tin dân sự, đặc biệt là chữ ký số ngày càng phát

triển, mở rộng và có phần áp đảo so với quân sự. Bởi lẽ những thành phần tham gia

hoạt động mã hóa thông tin trong quân đội hay bộ quốc phòng chỉ là một nhóm người

còn tham gia vào hoạt động này ở dân sự là tất cả những ai có nhu cầu chứng thực

thông tin, cung cấp, tiếp nhận thông tin trên hệ thống mạng máy tí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 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.

1.2. Chứng thực và chữ ký số

1.2.1. Hệ mã khóa công khai và việc tạo chữ ký số

Nguyên lý hoạt động của hệ mã khóa công khai [4]

Hệ mã khóa công khai (hay còn gọi là các hệ mã phi đối xứng) được phát minh ra

E D , trong đó

)

(

,

k

k

trong những thập kỷ cuối của thế kỷ vừa qua. Nó sử dụng 2 chìa khóa riêng biệt cho việc lập mã và giải mã văn bản. Chìa dùng cho việc lập mã có thể được công bố cho mọi người biết (chìa công khai), còn chìa dùng cho việc giải mã thì được giữ bí mật tuyệt đối. Việc biết được chìa khóa công khai không cho phép tính ra chìa khóa giải

kE là chìa khóa lập mã, còn

mã. Mỗi cá thể k tham gia vào hệ thống được cấp phát riêng một cặp chìa khóa kD là chìa khóa giải mã. Khi mã hóa

C

=

)

E P ( k

kE ) ta sẽ được một văn bản mã ký hiệu là

một văn bản P (bằng chìa .

kD (cùng cặp với

kE ), nghĩa là

Văn bản này chỉ có thể được giải mã bằng chìa khóa

)

=

D E P (

(

))

=

P

D C ( k

k

k

.

3

Chương 1. Những vấn đề của an toàn thông tin hiện đại

chìa khóa lập mã

C

=

)

E M ( k

đi dưới dạng thông điệp mã Khi một cá thể i nào đó muốn giử thông điệp M cho đối tác k thì anh ta dùng kE của đối tác k (đã được biết công khai) để mã hóa văn bản và gửi . Khi đối tác k nhận được thông điệp này thì

kD ) để giải mã ra theo nguyên lý đã nêu

dùng chìa khóa giải mã của mình (là

)

=

(

(

))

=

M

D C ( k

D E M k

k

.

Các cá thể khác trong hệ thống, nếu nhận được văn bản mã C , thì cũng không thể nào

kD của cá thể K .

giải mã ra M , vì họ không có chìa khóa giải mã

Ký điện tử trong hệ mã khóa công khai [3][5][13]

Với hệ mã khóa công khai, một quy trình ký văn bản điện tử được thiết lập dựa

trên ý tưởng của hai nhà khoa học Diffie và Hellman [5][13]:

 Người gửi (chủ nhân văn bản) ký văn bản bằng cách mã hóa nó với khóa bí mật

của mình rồi gửi cho người nhận.

 Người nhận văn bản (đã ký) tiến hành kiểm tra chữ ký bằng cách sử dụng chìa khóa công khai của người gửi để giải mã văn bản. Nếu giải mã thành công thì

văn bản ký là đúng của người gửi.

Giao thức này mang đầy đủ các thuộc tính của thủ tục ký thông thường. Thật vậy:

 Chữ ký là sản phẩm của người đã chủ động tạo ra nó, tức là người đã dùng

chiếc chìa khóa bí mật của mình để mã hóa văn bản.

 Chữ ký cho biết chủ nhân của nó chính là người sở hữu chiếc chìa khóa bí mật đã được dùng để mã văn bản (kiểm tra bằng cách cho giải mã bằng chìa khóa

công khai của người đó). Không ai làm giả được “chữ ký” vì rằng chỉ có duy

nhất một người có chìa khóa bí mật đã dùng để “ký” (mã hóa).

 Chữ ký cho văn bản này không thể “tái sử dụng” cho văn bản khác. Thật vậy, việc biết chữ ký (văn bản mã) không cho phép tìm ra được chìa khóa bí mật của

người gửi (để có thể ký một văn bản khác).

 Văn bản đã ký không thể thay đổi (xuyên tạc) được nội dụng. Thật vậy, nếu đã mở ra để thay đổi thì không thể “ký lại” được nữa, vì không có chiếc chìa khóa bí mật của “người đã ký” (như đã nói ở trên).

 Người ký văn bản không thể thoái thác việc mình “đã ký”, vì ngoài ông ta ra

không còn ai có cái chìa khóa đã được dùng để “ký” văn bản.

4

Chương 1. Những vấn đề của an toàn thông tin hiện đại

Rõ ràng, về mặt logic thì quy trình ký như trên là rất hợp lý. Mọi thành viên tham gia

sử dụng một hệ mã khóa công khai đều có được khả năng ký văn bản điện tử (bằng chìa khóa bí mật của riêng mình) và kiểm tra chữ ký của những người khác (bằng chìa

khóa công khai mà họ đã công bố).

Việc dùng chìa khóa bí mật để mã hóa văn bản được gọi là ký điện tử, và kết quả

tạo ra là một dữ liệu dạng số, sẽ được gọi là chữ ký số [6]..

Trong thực tiễn triển khai, mọi người đều biết tốc độ mã hoá của các hệ mã

khoá công khai là vô cùng chậm. Cho nên, việc ký một văn bản dài (như thông tư,

nghị định, văn kiện,...) theo quy trình nêu trên là không khả thi trên thực tiễn.

Để khắc phục khó khăn này, người ta sử dụng một hàm “chiết xuất” đặc trưng văn bản. Hàm này nhận giá trị đầu vào là văn bản (độ dài tùy ý) và cho đầu ra là một

dãy số có độ dài xác định, gọi là mã băm (message digest). Hàm chiết xuất có thuộc

tính quan trọng là rất “nhạy” đối với các thay đổi của văn bản, theo đó chỉ cần một

thay đổi cực nhỏ trong văn bản (như thay dấu chấm, dấu phẩy,…) cũng sẽ kéo theo sự

thay đổi rõ rệt trong giá trị mã băm của nó. Chính vì vậy mã băm có tính đặc trưng rất

cao, và thường được gọi là đặc trưng văn bản. Để nhận biết sự toàn vẹn của một văn

bản người ta chỉ cần xem đặc trưng của nó có bị thay đổi hay không. Hai thuộc tính quan trọng khác của hàm chiết xuất là tính một chiều và tốc độ nhanh. Tính một chiều

thể hiện ở chỗ không thể tạo ra được một văn bản có mã băm (đặc trưng) là một xâu số

cho trước, và do đó không thể mạo ra một “văn bản giả” có cùng đặc trưng với một

văn bản cho trước. Tốc độ nhanh có nghĩa là thời gian tính đặc trưng cho văn bản là

không đáng kể [3][13].

Rõ ràng, việc đặc trưng văn bản không bị thay đổi cũng đồng nghĩa với việc bản

thân văn bản không bị thay đổi. Từ đây ta có một quy trình ký các văn bản dựa vào đặc

trưng của nó. Theo quy trình này, khi một cá thể A muốn ký một văn bản P thì cần

phải thực hiện các bước sau đây [3][13]:

 Tính đặc trưng văn bản của P (bằng hàm chiết xuất có sẵn trên hệ thống).

 Dùng chìa khóa bí mật của mình để mã hóa dãy số đặc trưng văn bản thu được ở bước trên. Đặc trưng văn bản sau khi được mã (bằng chìa bí mật của A) thì được gọi là chữ ký số (của ông A đối với văn bản P ).

Tức là tuân theo sơ đồ sau:

5

Chương 1. Những vấn đề của an toàn thông tin hiện đại

Hình 1.1: Quy trình ký điện tử [13]

Dễ dàng thấy rằng chữ ký số được tạo ra trong quy trình trên có đầy đủ các thuộc

tính đã nêu trong mục đầu. Thời gian tạo chữ ký được giảm đi rất nhiều và gần như

không phụ thuộc vào độ dài của văn bản. Thật vậy, do thời gian tính đặc trưng văn bản

là không đáng kể, thời gian tạo chữ ký chỉ còn là việc mã hóa đặc trưng của văn bản

(có độ dài như nhau với mọi văn bản, và nhỏ hơn độ dài văn bản nhiều lần).

Một người nào đó, nhận được văn bản P cùng với chữ ký số đi kèm, muốn tiến

hành kiểm tra thì cần tiến hành các bước sau [3][13]:

 Tính đặc trưng của văn bản P (bằng hàm chiết xuất có sẵn trên hệ thống).

 Giải mã chữ ký số (bằng chìa khóa công khai của ông A) để có một đặc trưng nữa của P , rồi so sánh nó với đặc trưng thu được ở bước trên. Nếu chúng khớp

nhau thì chứng tỏ văn bản nhận được chính là văn bản đã được ông A ký và nội

dung của nó không bị thay đổi so với khi ký.

Tức là tuân theo sơ đồ sau:

6

Chương 1. Những vấn đề của an toàn thông tin hiện đại

Hình 1.2: Quy trình kiểm tra chữ số ký số [13]

Như vậy, chữ ký số không phải là một nét vẽ ngoằn ngoèo khó bắt chước (như

chữ ký tay thông thường trên giấy) mà là một dãy số được tạo nên từ đặc trưng của

văn bản bằng phép mã hóa với chìa khóa bí mật của người ký.

So với thủ tục ký thông thường (trên văn bản giấy), thủ tục ký điện tử có những

ưu thế vượt trội. Hơn thế:

 Chữ ký số là chính xác tuyệt đối (không còn mối e ngại về việc chữ ký không

giống nhau trong mỗi lần ký, như khi phải ký bằng tay).

 Trong khi việc kiểm định chữ ký viết tay, con dấu giả,… là không đơn giản (vì thường đòi hỏi phương tiện kỹ thuật đặc biệt) thì chữ ký số có thể được kiểm

định một cách dễ dàng và chính xác (bằng thiết bị luôn có sẵn trong chương

trình). Mọi sự giả mạo, gian lận vì thế đều bị phát hiện tức khắc.

Như vậy, bằng việc triển khai giải pháp ký điện tử ta có thể nói lời kết thúc cho

các loại văn bằng chứng chỉ giả, mở đường cho các dịch vụ giao dịch trực tuyến với độ tin cậy cao. Tuy nhiên, điều này chỉ có thể đạt được nếu như mỗi người sở hữu đúng

cặp chìa khóa công khai và bí mật của chính mình. Nếu như có một ông B nào đó có thể đánh lừa được mọi người rằng cặp chìa khóa công khai (mà ông đang có) là của ông A, thì sẽ xảy ra hiện tượng “mạo danh” vô cùng nguy hiểm. Một mặt, ông B sẽ đọc được tất cả các tin mật mà người khác muốn gửi cho ông A nếu tin được mã bằng chìa khóa công khai của ông B, và mặt khác ông B có thể ký các văn bản “vô tội vạ” và đánh lừa mọi người rằng ông A đã ký những văn bản đó. Tóm lại, để cho chữ ký số có thể phát huy được thế mạnh của mình thì trước hết cần phải có giải pháp xác định

7

Chương 1. Những vấn đề của an toàn thông tin hiện đại

một cách chính xác “ai là ai” trên toàn hệ thống. Một giải pháp như vậy có thể có được

bằng việc dùng một “bên thứ ba đáng tin cậy”, một bộ máy trung thực đảm nhiệm việc cấp phát cho mỗi thực thể (người, máy tính, phương tiện,…) một định danh duy nhất

và gắn cho mỗi định danh một cặp chìa khóa (bí mật – công khai) duy nhất, để rồi vào

mọi lúc, mọi nơi bất kỳ ai cũng có thể thông qua nó để kiểm định xem một chìa khóa

công khai nafon đó thuộc về thực thể có định danh nào. Bộ máy trung thực đó còn được gọi là Cơ quan thẩm quyền cấp chứng thực, gọi tắt là CA (Certificate Authority).

1.2.2. Chứng thực số

Khái niệm chứng thực số [3][7][13]

Trong mật mã học, chứng thực số (còn gọi là chứng thực điện tử) là một chứng

thực sử dụng chữ ký số để gắn một chìa khóa công khai với một thực thể (một cá nhân,

hay một máy chủ, hoặc một công ty…). Nói cách khác, chứng thực số là phương tiện

giúp người ta khẳng định được một chìa khóa công khai nào đó thuộc về thực thể nào

[7].

Một chứng thực số chuẩn mực thường bao gồm chìa khóa công khai và một số

thông tin về thực thể sở hữu chìa khóa đó (tên, địa chỉ,…). Như vậy, thông tin trên

chứng thực số không chỉ cho biết một chìa khóa công khai nào đó thuộc về ai, ta còn

có thể biết được các thông tin liên quan khác, mà đôi khi cũng rất quan trọng trong

một hệ thống cụ thể, như là danh phận, chức vụ,… của người sở hữu [3].

Trong một mô hình với hạ tầng khóa công khai (PKI) chuẩn mực, chữ ký trong

chứng thực thuộc về nhà cung cấp chứng thực số (Cerfiticate Authority, viết tắt là

CA). Chữ ký trong chứng thực là sự đảm bảo của người ký về mối liên hệ giữa chìa

khóa công khai và thực thể được chứng nhận.

Nội dung của chứng thực số theo chuẩn X.509 [3][13]

Tiêu chuẩn về chứng thực số trên cơ sở hạ tầng khóa công khai phổ biến nhất

hiện nay là X.509 được ban hành bởi ITU-T (International Telegraph Union – Telecom, tổ chức viễn thông quốc tế (về lĩnh vực viễn thông), thuộc liên hợp quốc).

Bao gồm:

 Version: Chỉ định phiên bản của chứng nhận X.509.

 Serial Number: Số loạt phát hành được gán bởi CA. Mỗi CA nên gán một mã

số loạt duy nhất cho mỗi giấy chứng nhận mà nó phát hành.

 Signature Algorithm: Thuật toán chữ ký và chỉ rõ thuật toán mã hóa được CA sử dụng để ký giấy chứng nhân. Trong chứng nhận X.509 thường là sự kết hợp

8

Chương 1. Những vấn đề của an toàn thông tin hiện đại

giữa thuật toán băm (chẳng hạn như MD5) và thuật toán khóa công khai (chẳng

hạn như RSA).

 Issuer Name: Tên tổ chức CA phát hành chứng thực. Hai CA khác nhau không

được sử dụng cùng một tên phát hành.

 Validity Period: gồm hai giá trị chỉ định khoảng thời gian mà giấy chứng nhận có hiệu lực: not-before và not-after. Not-before: thời gian chứng nhận bắt đầu có hiệu lực; Not-after: thời gian chứng nhận hết hiệu lực.

Các giá trị thời gian này được đo theo chuẩn thời gian Quốc tế, chính xác đến

từng giây.

 Subject Name: Tên chủ thể được cấp chứng thực.

 Public Key: Chìa khóa công khai của chủ thể được cấp chứng thực.

 Issuer Unique ID & Subject Unique ID: Được đưa vào sử dụng từ X.509 phiên bản 2, dùng để xác định hai tổ chức CA hoặc hai chủ thể khi chúng có cùng

DN. RFC 2459 đề nghị không nên sử dụng hai trường này.

 Extensions: Chứa các thông tin bổ sung cần thiết mà người thao tác CA muốn

đặt vào chứng nhận. (Mới được đưa ra trong X.509 phiên bản 3).

 Signature: chữ ký số được tổ chức CA áp dụng.

Tổ chức CA tạo chữ ký bằng khóa bí mật với kiểu thuật toán mã được quy định

trong trường thuật toán chữ ký.

Chữ ký bao gồm tất cả các phần khác trong giấy chứng nhận. (Qua đó thể hiện CA

chứng nhận cho tất cả các thông tin khác trong giấy chứng thực, chứ không chỉ cho tên

chủ thể và khóa công khai).

9

Chương 1. Những vấn đề của an toàn thông tin hiện đại

Hình 1.3: Những nội dung thông tin cơ bản theo chuẩn X.509 [13]

1.3. Vai trò của CA và vấn đề then chốt trong thiết lập CA

1.3.1. Vai trò của CA

Chứng thực số là tiền đề cho nhiều ứng dụng của mật mã khóa công khai. Đối

với các hệ mã đối xứng (bí mật), việc trao đổi chìa khóa (bí mật) giữa những người sử

dụng trên quy mô rộng là vô cùng khó khăn, hầu như không thể thực hiện được. Với

các hệ mã hóa khóa công khai, người ta có thể thoát ra khỏi khó khăn này. Trên

nguyên tắc, nếu cá nhân A muốn người khác giử thông tin mật cho mình thì chỉ cần

công bố chìa khóa công khai của chính mình. Bất kỳ ai có được chìa khóa này đều có

thể gửi thông tin mật cho A. Tuy nhiên, khi ấy lại nảy sinh một vấn đề khác. Thật vậy,

nếu chìa khóa công khai của A không được chứng thực, một người nào đó (D) cũng có khả năng đưa ra một chìa khóa công khai khác và giả mạo rằng đó là chìa khóa của A. Bằng cách làm như vậy kẻ “mạo danh” này có thể đọc được một số thông tin mà người khác gửi cho A. Nếu như chìa khóa công khai của A có trong một chứng thực số (được chứng thực bởi một bên thứ 3, chẳng hạn như là T, với công nghệ chữ số) thì bất kỳ ai tin tưởng vào T cũng có thể kiểm tra chìa khóa công khai của A. Nói cách khác, kẻ mạo danh D ắt sẽ bị lật tẩy. Trong mô hình hạ tầng khóa công khai thì T chính là nhà cung cấp chứng số (CA – Certificate Authority).

1.3.2. Sử dụng chứng thực số

10

Chương 1. Những vấn đề của an toàn thông tin hiện đại

Khi áp dụng chứng thực số ở quy mô lớn, có rất nhiều CA cùng hoạt động. Vì

vậy một cá thể A có thể không quen thuộc (không đủ tin tưởng) với CA của một cá thể B khác. Do đó chứng thực của B có thể phải bao gồm chữ ký của CA ở mức cao hơn.

Quá trình này dẫn đén việc hình thành một mạng lưới quan hệ phức tạp và phân tầng

giữa các CA. Trong tiêu chuẩn X.509 về hệ thống hạ tầng khóa công khai, mạng lưới

CA tạo thành cây từ trên xuống với gốc là một CA trung tâm mà không cần được chứng thực bởi một bên thứ 3 nào khác.

Cũng giống như giấy CMND, một chứng thực điện tử cũng có thời hạn lưu hành

nhất định, và có thể bị thu hồi trước thời han. Một chứng thực số có thể bị thu hồi nếu

như chìa khóa bí mật (cùng cặp với chìa khóa công khai của nó) đã bị lộ, hoặc mối liên hệ giữa khóa công khai và chủ thể sở hữu đã thay đổi. Điều này có thể xảy ra ở mức

độ không thường xuyên, nhưng người sử dụng phải luôn kiểm tra tính pháp lý của

chứng thực số mỗi khi sử dụng. Việc kiểm tra có thể thực hiện bằng cách so sánh chứng thực với danh sách các chứng thực bị thu hồi (Certificate Revocation List –

CRL). Việc đảm bảo danh sách này luôn chính xác và được cập nhật kịp thời là chức

năng cơ bản của hạ tầng khóa công khai tập trung [13].

1.3.3. Các chức năng cơ bản của CA

Hình 1.4: Các chức năng của hệ thống CA [13]

Cấp phát chứng thực [13]

11

Chương 1. Những vấn đề của an toàn thông tin hiện đại

Cấp phát chứng thực là nhiệm vụ đầu tiên của một CA. Công việc này được thực

hiện trên cơ sở một yêu cầu được đưa ra từ phía người dùng. Trong các hệ thống không lớn lắm, các yêu cầu này được trực tiếp gửi cho CA để trực tiếp xử lý, còn với

các hệ thống lớn thường có thêm một khâu trung gian (đăng ký – registration) nhận

yêu cầu từ phía người dùng chuyển cho CA và nhận chứng thực từ CA trả về cho

người dùng. Để tạo ra một chứng thực số, CA phải sinh được một cặp chìa khóa phi đối xứng có độ an toàn cao để gán cho chủ thể (người yêu cầu) và tuân thủ một số quy

định nghiêm ngặt trong việc cấp phát (ví dụ tránh để xảy ra nhầm lẫn cấp một chứng

thực cho hai chủ thể khác nhau, hoặc tránh dùng hai định danh quá giống nhau có thể

dẫn đến khả năng mạo danh). Thông tin ghi trong chứng thực là những thông tin cơ bản nhất về chủ thể và cơ quan cấp chứng thực (như trong giấy CMND), ngoài ra có

một thông tin mang tính đặc thù cho chứng thực số (vốn không có trong CMND thông

thường) đó là chìa khóa công khai. Đây chính là chìa khóa mà người khác dùng để

kiểm tra chữ ký số của chủ nhân mang chứng thực. Để không thể xảy ra khả năng mạo

nhận chìa khóa (như đã thấy với hiện tượng mạo danh), người phát hành chứng thực

(tức là CA) sẽ dùng chìa khóa bí mật của mình ký lên cụm thông tin có trong chứng

thực (trong đó có tên chủ thể cùng chìa khóa công khai). Chữ ký được đặt ngay dưới cụm thông tin đã được ký để người khác dể dàng kiểm tra (xem sơ đồ kèm theo).

Hình 1.5: Sơ đồ minh họa chức năng cấp phát chứng thực của CA [13]

12

Chương 1. Những vấn đề của an toàn thông tin hiện đại

Kiểm tra chứng thực [13]

Để kiểm tra một chứng thực của người dùng, người ta cần phải có được

thông tin chính xác về chìa khoá công khai của CA. Tốt nhất là lấy từ trong Chứng thực số của chính CA. Người ta dùng chìa khoá này để giải mã phần chữ ký số có

trong chứng thực của người dùng rồi lấy kết quả tìm được đem so với mã băm của

phần thông tin công khai trong chứng thực số (tức là phần còn lại từ chứng thực số sau

khi đã bỏ đi phần chữ ký số). Sơ đồ minh họa:

Hình 1.6: Sơ đồ minh họa chức năng kiểm tra chứng thực của CA [13]

Các chứng năng còn lại của CA mang tính kỹ thuật thuần túy, ta không đề cập

đến ở đây.

1.3.4. Vấn đề then chốt trong thiết lập CA

Bước đầu tiên và cũng là quan trọng nhất của một hệ thống chứng thực số CA là cấp phát khóa. Các hệ thống CA có thể sử dụng nhiều thuật toán tạo chữ ký số khác

13

Chương 1. Những vấn đề của an toàn thông tin hiện đại

nhau của hệ mã phi đối xứng. Trong các hệ mã phi đối xứng thì hệ mã RSA được sử

dụng rộng rãi và phổ biến nhất. Hệ mã RSA có độ bảo mật cao, luôn là thách thức cho giới thám mã. Nước ta đã đưa ra chuẩn chữ ký số, trong đó RSA được sử dụng như

qp,

một hệ mã chuẩn trong một thời gian dài sắp tới. Việc sinh khóa trong hệ mã RSA về

thực chất là tạo ra một cặp số lớn là các số nguyên tố mạnh. Để sinh được một

cặp số nguyên tố như vậy, chúng ta phải tìm hiểu các lý thuyết toán học có liên quan

đến số nguyên tố, số giả nguyên tố như: các định lý của số nguyên tố, kiểm tra số

nguyên tố và số giả nguyên tố, và cách kiểm tra số giả nguyên tố mạnh sẽ được đề cập

ở chương tiếp theo.

14

Chương 2. Một số công cụ toán học liên quan

Chương 2. Một số công cụ toán học liên quan

2.1. Số nguyên tố và hệ mã khóa công khai RSA

2.1.1. Hệ mã khóa công khai RSA

Trước khi đi vào các lý thuyết toán học có liên quan đến việc sinh, kiểm tra số nguyên tố để làm khóa cho CA, ta tìm hiểu kỹ hơn về hệ mã RSA được ứng dụng

trong hệ thống chứng thực số.

Hệ mã đối xứng và hệ mã phi đối xứng [1]

Khái niệm mã đối xứng được dùng để chỉ các hệ mã mà trong đó, khi biết khóa

lập mã, ta có thể tìm ra khóa giải mã, đồng thời, việc giải mã cùng đòi hỏi thời gian

như việc lập mã. Cho đến những năm cuối của thập niêm 70 của thế kỉ 20, người ta

mới chỉ biết đến một loại mã như vậy. Đối với các hệ mã này, cần phải giữ bí mật khóa lập mã, vì để lộ nó cũng tức là để lộ cách giải mã. Do đó, chỉ những người hoàn

toàn chia sẻ mọi thông tin mật với nhau mới có thể trao đổi với nhau bằng mật mã.

Điều này giải thích nguyên nhân của việc cho đến rất gần đây mật mã thường chỉ được

dùng trong quân sự, ngoại giao, tức là khi những đối tượng cần trao đổi thông tin mật

với nhau là khá it, hơn nữa, lại cùng chung quyền lợi nên sẵn sàng bảo vệ bí mật cho

nhau trong quá trình trao đổi thông tin.

Sự phát triển của xã hội dẫn đến việc ngày nay mật mã không những chỉ được

dùng trong bí mật quân sự và ngoại giao, mà còn dùng, và có thể chủ yếu là dùng

trong bí mật kinh tế, tài chính, thương mại. Vì thế xuất hiện những đòi hỏi mới đối với

các hệ mật mã hiện đại, khác về nguyên tắc so với mật mã thường dùng trước đây.

Không giống như các hoạt động quân sự hoặc ngoại giao, trong hoạt động kinh doanh,

số lượng đơn vị phải cùng trao đổi thông tin thường là rất lớn. Thậm chí, những người

có quyền lợi cạnh tranh nhau cũng có nhu cầu trao đổi những thông tin mặt với nhau.

Bởi thế, những mật mã đối xứng khó có thể thích hợp. Hiển nhiên, muốn gửi một

thông báo mật cho một đối tượng nào đó, ta cần phải biết khóa lập mã của họ, vì thế, những người cùng dùng một chìa trong hệ mã đối xứng đều biết hết bí mật của nhau. Các hệ thống mật mã hiện đại, mật mã khóa công khai, hay còn gọi là mã phi đối xứng, khắc phục được những nhược điểm đó: mỗi người tham gia trong hệ thống chỉ cần giữ bí mật chìa khóa giải mã của mình (còn gọi là chìa khóa bí mật), trong khi khóa lập mã được thông báo công khai (và thường được gọi là chìa khóa công khai).

Việc biết khóa lập mã không cho phép tìm ra khóa giải mã trong một thời gian chấp nhận được, ngay cả khi sử dụng những máy tính hiện đại nhất. Những hệ mã phi đối xứng tìm thấy đầu tiên là những mật mã dùng các hàm số học.

15

Chương 2. Một số công cụ toán học liên quan

Hệ mã RSA [1]

Trong các hệ mã phi đối xứng thì hệ mã RSA (phát minh năm 1978 bởi Rivest,

Shamir và Adleman) được sử dụng rộng rãi và phổ biến nhất. Hệ mã RSA có độ bảo

mật cao, luôn là thách thức cho giới thám mã. Nước ta đã đưa ra chuẩn chữ ký số,

trong đó RSA được sử dụng như một hệ mã chuẩn trong một thời gian dài sắp tới.

),( en

,( dn

)

Hệ RSA được xây dựng trên cơ sở mã mũ, trong đó khóa lập mã (công khai) là

qp,

cặp , gồm số mũ e và modulo n . Khóa giải mã (bí mật) là cặp . Với d là

)(n . Số n là tích của hai số nguyên tố rất lớn

n

. qp

số nghịch đảo của e modulo nào

)(n , trong đó

)(n là giá

đó, , còn e được chọn là số nguyên tố cùng nhau với

trị hàm Euler của n . Để mã hóa một thông báo, trước tiên ta chuyển nó sang dạng số

và nhóm thành các khối với độ dài lớn nhất có thể (tùy thuộc khả năng tính toán và tốc

PE (

:)

e PC

(mod

n

)

độ yêu cầu) với một số chẵn chữ số. Để mã hóa một khối P trong văn bản, ta tính

.

Khi ấy, do một hệ quả của Định lý Euler (sẽ được trình bày ở phần sau), quá trình giải

ed

1 (mod

 (

n

))

)(n , tức là thỏa mãn

mã không đòi hỏi phải “khai căn bậc e modulo n ” của khối văn bản mã, nếu như biết

e  (,(

n ))

1

. Nghịch được số nghịch đảo d của e modulo

d

de

de

CD (

:)

C

P

P

(mod

n

)

đảo này tồn tại theo điều kiện và, do hệ quả đã nêu, ta có

,

 P

(

nP

1),

khi . Chú ý rằng, xác suất để P và n không nguyên tố cùng nhau là hết sức

nhỏ, vì điều này chỉ có thể xảy ra khi P là bội của p hoặc q . Thông thường P chỉ là

(

nP

1),

những “khối văn bản” có độ dài không lớn, nói chung là nhỏ hơn hẳn p và q , cho nên

điều kiện là luôn xảy ra, và công thức trên cho thấy việc giải mã một khối

,( dn

)

n . Cặp

trong văn bản mật cũng chính là việc nâng lên lũy thừa bậc d rồi rút gọn theo modulo

),( en

được gọi là khóa giải mã.

,( dn

)

)(n . Việc tìm

)(n không dễ hơn

Việc biết chìa khóa lập mã không dẫn đến việc tìm được chìa khóa giải mã

. Để có thể tìm được d thì ta phải tìm được

qp



n

n 1)( 

với việc phân tích n ra tích của hai số nguyên tố rất lớn là p và q . Thật vậy, ta có:

2

2

qp



 qp

4

pq

 qp

4

n

;

.

16

Chương 2. Một số công cụ toán học liên quan

Từ các công thức đó để tìm được p và q thì với khả năng của con người, thậm chí là

máy tính có tốc độ xử lý cao là không thể.

Độ an toàn của RSA [1]

Nếu ta chọn các số p và q khoảng 100 chữ số thập phân, thì n sẽ có khoảng

200 chữ số thập phân. Để phân tích một số nguyên cỡ lớn như thế, với các thuật toán

nhanh nhất hiện này và với những máy tính hiện đại nhất, ta mất hàng tỷ năm!

Sau khi tìm ra hệ mã, Rivesst, Shamir và Adleman có viết một bài báo công bố

phát minh dưới dạng một thông báo khoa học của MIT và, trên cột Martin Gardner’s

của tờ báo Scienfitic American, họ có đưa ra lời thách thức bạn đọc bẻ khóa một mẩu

tin nhỏ đã được mã hóa với:

n=1143816257578888676692357799761466120102182967212423625625618429357 06935245733897830597123563958705058989075147599290026879543541

e = 9007.

Mẩu tin

“first solver wins one hundred dollars” xuất hiện trong dạng mã hóa (với A = 01, B=02, C=03 …) chỉ được giải mã vào ngày

26/4/1994, bằng một cố gắng tổng lực mang tính quốc tế (qua Internet) với việc sử

dụng 1600 workstations, mainframes, và supercomputers tấn công trong 8 tháng liên

tục để phân tích số nêu trên ra thừa số nguyên tố.

Thực tế này cho thấy rằng thuật toán RSA là rất an toàn, vì không mấy khi có

điều kiện để huy động một lực lượng tính toán hùng hậu như thế vào một công việc

giải mã một mẩu tin.

Có một vài điều cần chú ý khi chọn các số p và q để tránh rơi vào trường hợp

1p

1q

tích pq bị phân tích nhanh nhờ những thuật toán đặc biệt: p và q cần chọn sao cho

(

p

 q ,1

)1

và không chỉ có toàn các ước nguyên tố nhỏ (có phân tích “vụn”). Ngoài ra,

ước chung lớn nhất phải là số nhỏ, p và q phải có số chữ số trong khai

triển thập phân khác nhau không nhiều.

2.1.2. Lý thuyết toán học về số nguyên tố và các vấn đề liên quan

Số nguyên tố [2]

Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho số nguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải là số nguyên tố được gọi là hợp

số.

17

Chương 2. Một số công cụ toán học liên quan

Các Định lý về số nguyên tố [2]

Mọi hợp số n đều có ước nguyên tố nhỏ hơn n .

Mọi số nguyên tố lớn hơn 1 đều phân tích được một cách duy nhất thành tích các

số nguyên tố, trong đó các thừa số được viết với thứ tự không giảm.

Định lý số nguyên tố được Gauss phát biểu năm 1773:

)(x là số các số nguyên tố

x /)(

1

Với mỗi số thực dương x cho trước, ta ký hiệu

không vượt quá x. Khi đó, ta có: .

lim

x log

x

x



ba,

Ước chung lớn nhất [2]

gcd( ba ),

),( ba

Ước chung lớn nhất của 2 số tự nhiên là số lớn nhất trong tập các ước chung

của 2 số đó, được ký hiệu là hay đơn giản là .

Khi 2 số tự nhiên có ước chung lớn nhất là 1 thì chúng được gọi là nguyên tố cùng

nhau.

Phi hàm Euler [1]

n

)5( 

4

 )6(

2

 )7(

6

Với , số lượng các số tự nhiên bé hơn n và nguyên tố cùng nhau với n

)(n . Ví dụ:

được ký hiệu là , , .

p (

)

 p

1

Rõ ràng, khi p là số nguyên tố thì mọi số tự nhiên bé hơn nó đều là nguyên tố

r

r

 1

r

 (

p

)

p

(

p

)1

p

 /11(

p

)

r là một số tự nhiên bất kỳ thì

cùng nhau với nó và do đó ta có . Tổng quát hơn, khi p là số nguyên tố và

.

n )(

 (

).

3

4

nm,  và do đó để tính  của một số tự nhiên nào đó người ta phân tích nó ra các thừa số nguyên tố rồi áp dụng các công thức trên. Ví dụ: 4  ( ).2(

)15)(13(3)12(2

2 )5.3.2(

2 ).3(

720

192

)5(

)

Có thể chứng minh được rằng khi nm ). là các số nguyên tố cùng nhau thì ta có  m (

.

Phép tính đồng dư [1]

a 

b

(mod m

)

Giả sử m là một số nguyên dương. Ta nói hai số nguyên a và b là đồng dư với

ba  chia hết cho m . Ký hiệu

nhau theo modulo m nếu hiệu .

Phép tính đồng dư theo modulo m dẫn đến việc tách tập số nguyên ra thành m

mmod

lớp, mỗi lớp chứa các số nguyên đồng dư với nhau theo . Tập các lớp này được

 m/

ký hiệu là ( Z là tập các số nguyên) và chứa đúng m phần tử. Mỗi lớp trong tập

18

,0[

m

]1

Chương 2. Một số công cụ toán học liên quan

 m/

có đúng 1 số nằm trong đoạn , cho nên mỗi số nguyên trong đoạn này

được xem “đại diện” của một lớp.

a  c  ca

(mod m db

b  b  d

ca  .

) ) )

db .

Một số tính chất của phép tính đồng dư: ; ) (mod m (mod m (mod m ; ) (mod m )  (mod m a a   Nếu a  b  Nếu a  b  Nếu a  b thì và , c  ,

vu,

gcd(

mx ,

1)

; ) a (mod m thì c (mod m ) thì (mod (mod m ) Như vậy, ta có thể tự do thực hiện các phép tính số học thông thường trên tập . ; m )  m/

 m/

xu  .

1 (mod

m

)

Nếu x là một phần tử trong và thì tồn tại các số sao cho

ux

 vm

1

 m/

u , và thường ký hiệu phần tử nghịch đảo này là

1x , hay

, tức là , nên người ta nói x có nghịch đảo (trong ) là

x/1

)

(mod p

(mod

p )

a

0

.

1 (mod

) thì

. Nếu a không chia hết cho p (tức là . )

14 17 

4 17 

1 (mod

(mod

(mod

4 7 

)7

)7

)7

0

Định lý Fermat (bé)[2]: Nếu p là một số nguyên tố còn a là một số nguyên thì a p  a a p  1 p Ví dụ. Dễ dàng thấy rằng 4 ; ; .

a 

p

Thặng dư bình phương [1]

2 x 

a

(mod

p

)

)

(mod p nếu như tồn tại số nguyên x thỏa mãn phương trình

Cho số nguyên tố p . Số nguyên được gọi là thặng dư bình phương

.

2p

Ký hiệu Legendre [1]

a

1 p 2

,( paL

:)

mod

p

a

p

  

  

paL ,(

)

Với số nguyên tố và số nguyên bất kỳ a người ta ký hiệu

)

Và chỉ ra rằng sẽ bằng 0 khi a chia hết cho p , bằng 1 khi a là một thặng dư

(mod p và bằng -1 trong trường hợp còn lại.

bình phương

Có thể mở rộng khái niệm ký hiệu trên ra cho trường hợp p không phải là

nguyên tố, nhưng chỉ xét những số a trong tập thặng dư rút gọn của p (tức là những

thặng dư nguyên tố cùng nhau với p ).

n

. pp

...

i

,...,1

k

Ký hiệu Jacobi [1]

1

2

kp

ip ,

Với số nguyên , trong đó , là các số nguyên tố, còn a

nằm trong tập thặng dư rút gọn của n , ta ký hiệu

19

naJ ),(

xpaL

,(

)

...

)

Chương 2. Một số công cụ toán học liên quan

1

kpaxL ,(

.

Như vậy trong trường hợp riêng khi n là số nguyên tố thì ký hiệu Jacobi trùng với ký

hiệu Legendre.

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.

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ố

Thuật toán: Sàng Eratosthenes [2]

Để kiểm tra n có phải là số nguyên tố hay không, ta thực hiện phép chia cho tất

cả các số nguyên tố không vượt quá n .

n

O

(log

n

log

m

)

Độ phức tạp: Theo định lý số nguyên tố của Gauss, số các số nguyên tố không vượt

2

2

2 log

n n

log

n

quá n là vào khoảng . Để chia n cho m , ta cần phép

tính bít. Như vậy, nếu n vào cỡ khoảng 100 chữ số thập phân, số các phép tính bit

5010 . Với những máy tính thực hiện một triệu phép tính một giây,

3610.1,3

phải dùng sẽ vào cỡ

thời gian cần thiết sẽ vào khoảng năm! Điều này dẫn đến một phương án khác

thay thế: số giả nguyên tố.

Số giả nguyên tố [2]

b n 

b

(mod n

)

b n 

b

(mod n

)

Theo định lý Fermat, nếu n là số nguyên tố và b là số nguyên tùy ý, thì

thì n phải là hợp số. Như . Do đó nếu tồn tại số b sao cho

vậy, nếu một số nguyên thỏa mãn các giả thiết của định lý Fermat bé thì “có nhiều khả

năng” nó là một số nguyên tố! Ta có định nghĩa sau:

b n 

b

(mod n

)

Giả sử b là một số nguyên dương. Nếu n là hợp số nguyên dương và

, thì n được gọi là số giả nguyên tố cơ sở b .

1010 , nhưng chỉ có 14884 số giả nguyên tố cơ có tất cả 455052512 số nguyên tố bé hơn sở 2 trong khoảng đó. Sự kiện này giải thích cách nói ở trên: Các số thỏa mãn định lý Fermat bé có nhiều khả năng là số nguyên tố.

Nói chung các số giả nguyên tố ít hơn nhiều so với các số nguyên tố. Chẳng hạn,

2.2.2. Kiểm tra số giả nguyên tố mạnh

Kiểm tra Miller [2]

20

n

t

Chương 2. Một số công cụ toán học liên quan

s21  , trong đó s là số nguyên không âm, t là số nguyên dương lẻ. Ta nói n trải qua được kiểm tra Miller cơ sở b , nếu

2

b tj

 1 (mod

n

)

b t 

1 (mod

n

)

0



s

j

1

Giả sử n là số nguyên dương lẻ,

, hoặc , với j nào đó, .

Số nguyên n được gọi là giả nguyên tố mạnh cơ sở b nếu nó là hợp số và trải

qua được kiểm tra Miller cơ sở b .

Cách làm trên có thể kiểm tra nguyên tố những số không lớn lắm. Đối với những

số lớn, ta có thể dùng thuật toán xác suất dựa trên định lý :

1



b

n

1

1n 4

Nếu n là một hợp số dương lẻ thì tồn tại không quá , sao b ,

cho n trải qua được kiểm tra Miller đối với các cơ sở đó.

Từ định lý trên suy ra rằng, nếu số b được chọn ngẫu nhiên trong khoảng

1



b

n

1

1 4

. Như vậy, thì n trải qua kiểm tra Miller cơ sở b với xác suất bé hơn

nếu ta chọn k số ngẫu nhiên thì xác suất để n trải qua kiểm tra Miller đối với k cơ sở

20k

1 k4

đó sẽ bé hơn , xác suất đó quá nhỏ, nên với n trải qua . Khi k đủ lớn, với dụ

20 cơ sở ngẫu nhiên thì có thể tin “gần chắc chắn” rằng n là số nguyên tố. Từ đó ta có

thuật toán xác suất sau:

Thuật toán Miller-Rabin [9], [11]

RGB là bộ sinh bít ngẫu nhiên

,

,

or

qpp 2 1 1

Input: 1. w

2. iterations The odd integer to be tested for primality. This will be either p or q , or one of the auxiliary primes 2q . The number of iterations of the test to be performed; the value shall be consistent with Table 3 or 4.

Output: 1. status

The status returned from the validation procedure, where status is either PROBABLY PRIME or COMPOSITE.

a2 divides

Process:

1w

a

( 

wm  wlen 

2/)1 (w )

len

.

. .

1i

1. Let a be the largest integer such that 2. 3. 4. For to iterations do

4.1 Obtain a string b of wlen bits from an RBG.

1



wb

1

b ((

)1

wbor

(

))1

Comment: Ensure that .

4.2 If , then go to step 4.1.

21

Chương 2. Một số công cụ toán học liên quan

))1  do . w , then go to step 4.7. )1

m mod 4.3  z b 4.4 If z ((  )1 4.5 For 1j 4.5.1 z 4.5.2 If 4.5.3 If

, then go to step 4.7.

. w  ( wzor to 1a 2 mod z  (  wz , then go to step 4.6. ( z )1

4.6 Return COMPOSITE. 4.7 Continue. Comment: Increment i for the do- loop in step 4. 5. Return PROBABLY PRIME.

Mã code cụ thể của thuật toán này xem ở phần phụ lục.

Thuật toán Miller-Rabin nâng cao [9]: cung cấp thêm thông tin chi tiết khi gặp một

lỗi, có thể hữu dụng khi sinh và xác thực số nguyên tố trong mã hóa khóa công khai

RSA.

,

,

or

qpp 2 1 1

RGB là bộ sinh bít ngẫu nhiên Input: 1. w

2. iterations The odd integer to be tested for primality. This will be either p or q , or one of the auxiliary primes 2q . The number of iterations of the test to be performed; the value shall be consistent with Table 3 or 4.

Output: 1. status

The status returned from the validation procedure, where status is either PROBABLY PRIME, PROVABLY COMPOSITE WITH FACTOR (returned with the factor), and PROVABLY COMPOSITE AND NOT A POWER OF A PRIME.

a2 divides

Process:

1w

a

( 

 wm wlen 

2/)1 (w )

len

.

. .

1i

1. Let a be the largest integer such that 2. 3. 4. For to iterations do

4.1 Obtain a string b of wlen bits from an RBG.

1



wb

1

))1

Comment: Ensure that .

( g

(( b  )1 GCD g  )1

 ( wbor . ,( wb ) , then return PROVABLY COMPOSITE WITH

, then go to step 4.1.

m mod  )1

w (

))1

. wzor  4.2 If 4.3 4.4 If FACTOR and the value of g . 4.3 b  z 4.4 If z (( , then go to step 4.15.

22

1j

Chương 2. Một số công cụ toán học liên quan

do

1x

wx 

and Comment:

w )1

4.7 For

(  w

2/)1

x

mod

w

1a mod  , then go to step 4.12. Comment: b

, then go to step 4.15.

wx 

and

mod )1

4.8 4.9 .

)1

(  w mod

w

b

x

, then go to step 4.12.

1x

,1

and .

.

x ( , then return PROVABLY COMPOSITE WITH FACTOR

to x  4.7.1 .z 2 4.7.2 x z 4.7.3 If  wz ( 4.7.4 If ( z )1 x  .z 2 z x w ( z .z GCD )1

4.10 If x  Comment: 4.11 4.12  g w ) 4.13 If ( g and the value of g 4.14 Return PROVABLY COMPOSITE AND NOT A POWER OF

A PRIME. 4.15 Continue. Comment: Increment i for the do- loop in step 4.

5. Return PROBABLY PRIME. Hai thuật toán trên có số vòng lặp (iterations) được xác định dựa theo bảng sau:

Bảng 2.1: Số vòng lặp tối thiểu trong thuật toán Miller-Rabin khi sinh số nguyên

tố sử dụng trong hệ mã RSA [9]

,

,

,

,

Các số nguyên tố Số vòng lặp

qqpp , 1 2

1

2

qqpp , 2 1

1

2

> 100 bits Cho : 28

p và q : 512 bits

802 

Cho p và q : 5

,

,

,

,

Xác suất lỗi

qqpp , 1 2

1

2

qqpp , 2 1

1

2

> 140 bits Cho : 38

p và q : 1024 bits

1122 

Cho p và q : 5

,

,

,

,

Xác suất lỗi

qqpp , 1 2

1

2

qqpp , 2 1

1

2

> 170 bits Cho : 41

p và q : 1536 bits

1282 

Cho p và q : 4

Xác suất lỗi

23

Chương 2. Một số công cụ toán học liên quan

1002

Bảng 2.2: Số vòng lặp tối thiểu trong thuật toán Miller-Rabin khi sinh số nguyên

tố sử dụng trong hệ mã RSA với xác suất lỗi là [9]

,

,

,

,

Các số nguyên tố Số vòng lặp

qqpp , 1 2

1

2

qqpp , 2 1

1

2

p và q : 512 bits

> 100 bits Cho : 38

,

,

,

,

Cho p và q : 7

qqpp , 1 2

1

2

qqpp , 2 1

1

2

p và q : 1024 bits

> 140 bits Cho : 32

,

,

,

,

Cho p và q : 4

qqpp , 1 2

1

2

qqpp , 2 1

1

2

p và q : 1536 bits

> 170 bits Cho : 27

Cho p và q : 3

Ngoài ra còn có thuật toán Lucas để kiểm tra xác suất tính nguyên tố (trong FIPS 186-

3) có liên quan đến ký hiệu Jacobi được trình bày ở trên.

Thuật toán Lucas [9], [11]

status Where status is either PROBABLY PRIME or COMPOSITE.

The candidate odd integer to be tested for primality.

 ,9,7,5{

,13,11

17,15

,...}

Input: C Output: Process: for which the

D C

 1 

  

  

 0 

Jacobi symbol . If for any D in the sequence, 1. Find the first D in the sequence D C

return (COMPOSITE).  CK

r

1rK

.

1 r 

mod

C

1...K 0 and .

temp

 1

i

2

V

2   1

i

i

 1

mod

C

2. 1 3. Let KK r 4. Set 1rU 5. For i 5.1 U . be the binary expansion of K , with 1rV to 0 do VU  1 i

temp

DU 2

(

)1

5.2 V .

iK

U

V

temp

temp

U

mod

C

5.3 If then

i

2

5.3.1 .

24

V

DU

temp

temp

mod

C

Chương 2. Một số công cụ toán học liên quan

V i

2

5.3.2 .

Else

i UU  V  i V

temp

5.3.3 5.3.4 . temp .

0 U (

then return (PROBABLY PRIME). Otherwise, return 6.

If )0 (COMPOSITE).

A mod

2/

C

Bước 5.2, 5.3.1 và 5.3.2 có biểu thức dưới dạng , trong đó A là số nguyên,

2/A

A mod

2/

C

(  CA

2/)

mod

C

A

2/

mod

 CAC

(

2/)1

mod

C

không nguyên (do A lẻ), thì có thể được và C là số nguyên lẻ. Nếu

tính bằng . Một cách khác, , với mọi giá

trị A nguyên.

Mã code cụ thể của thuật toán Lucas xem ở phần phụ lục.

Nhận xét

Một số giả nguyên tố sau khi qua được 2 kiểm tra là thuật toán Miller-Rabin và

Lucas thì có thể tin tưởng là mạnh [11], đồng nghĩa với việc xác suất để nó không phải

số nguyên tố là rất thấp.

2.2.3. Tính nguyên tố mạnh của một số

Một số nguyên tố p được gọi là mạnh khi nó thỏa mãn các tính chất như sau [10],

[12]:

p

 qa

1p

 p lớn.

 111

1a nào đó và

1q là

 có thừa số nguyên tố lớn. Nghĩa là, với

số nguyên tố lớn.

q 1

qa 2

 12

2a nào đó và

2q là

11 q số nguyên tố lớn.

p

1p

 có thừa số nguyên tố lớn. Nghĩa là, với

qa 3

 13

3a nào đó và

3q là

 có thừa số nguyên tố lớn. Nghĩa là, với

số nguyên tố lớn.

qp,

Đôi khi một số nguyên tố chỉ cần thỏa mãn một số trong các trường hợp trên cũng được gọi là mạnh.

Trong trường hợp của bài toán, các điều kiện để một cặp số nguyên tố là

mạnh được đề cập đến ở bảng sau:

25

Chương 2. Một số công cụ toán học liên quan

nlen

,

,

len

(

)

len (

p

)

Bảng 2.3. Điều kiện của các số nguyên tố thành phần [10]

qqpp , 2 1

1

2

p 1

2

len

(

)

len

(

q

)

q 1

2

Độ dài tối thiểu của Độ dài tối đa của ,

1024 > 100 bits < 496 bits

2048 > 140 bits < 1007 bits

p

,1

p

,1

q

,1

q

1

,

,

3072 > 170 bits < 1518 bits

qqpp , 1 2

1

2

len

( p

)

Trong đó lần lượt là các thừa số nguyên tố của ; nlen

là độ dài của modulo n tính theo bit; là độ dài của số p tính theo bit.

Mã code của phần kiểm tra số nguyên tố mạnh xem ở phục lục.

2.3. Chìa khóa an toàn

Để một chìa khóa của hệ mã RSA được gọi là an toàn theo tiêu chuẩn của FIPS

186-3 (Federal Information Processing Standard được ban hành bởi U.S. National

Institute of Standards and Technology (NIST)) nó phải thỏa mãn các điều kiện sau [9]:

qp,

i. Số mũ e công khai phải thỏa mãn:

- Phải được chọn trước để tạo ra và d .

2

e<

<

256 2

- Là 1 số nguyên dương lẻ thỏa mãn: 16 .

- Có thể là số định sẵn hoặc được chọn ngẫu nhiên.

( p

)1

( q

)1

ii. Hai số p và q phải thỏa mãn:

(

nlen

1)2/

nlen

2/

2)(2(

 )

p

2(

)1

- và sẽ nguyên tố cùng nhau với e .

(

nlen

1)2/

nlen

2/

2)(2(



q

)

2(

)1

- .

- / 2) 100

- .

p

-

q

>

2 nlen (

- , nlen là độ dài theo bit của n .

/ 2

iii. Sau khi sinh ra p và q , số mũ d bí mật được chọn phải thỏa mãn:

d >

2nlen

d

  1 e

mod(gcd((

qp 

(),

q

)))1

gcd( ba ),

- Là 1 số nguyên dương và .

- , với là ước chung lớn nhất của a và b .

26

/ 2

, dqp ,

Chương 2. Một số công cụ toán học liên quan

d < =

2nlen

- Nếu phải được chọn lại. Số e có thể được chọn lại nhưng thì

không cần thiết.

27

Chương 3. Tính toán song song

Chương 3. Tính toán song song

3.1. Xử lý song song, cơ hội và thách thức [8]

Giới thiệu: Thời đại xử lý song song

Máy tính cá nhân đã được cải tiến đáng kể trong 30 năm qua. Tăng trưởng theo cấp số mũ trong sức mạnh xử lý đã biến đổi việc quản lý thông tin và năng suất làm

việc cá nhân, và đã mở rộng khả năng của máy tính lên rất lớn. Năng lực máy tính có

thể xử lý nhiều dữ liệu hơn, nhanh hơn, và với đồ họa phong phú đã biến đổi rất nhiều

ở các ngành kinh doanh, khoa học, và y học. Khả năng thu giữ âm thanh, video, và đồ họa ba chiều chất lượng cao trong các môi trường có liên kết đã thay đổi các lĩnh vực

giải trí, giáo dục, và truyền thông. Cho đến gần đây, các ứng dụng này đã tăng trưởng

nhanh hơn và đáp ứng nhiều hơn nhu cầu xã hội, đồng thời được nhân rộng với sự xuất

hiện của bộ vi xử lý nhanh mà không yêu cầu các nhà phát triển phần mềm tìm hiểu mô lập trình mới.

Tuy nhiên, sự phát triển của xử lý tuần từ đã đạt đến mức bão hòa vì bộ xử lý đã

tiếp cận đến các giới hạn vật lý. Định luật Moore về việc tăng gấp đôi mật độ bóng bán

dẫn hai năm một lần vẫn tiếp tục, nhưng tính hiệu quả của Luật Moore không thể được

áp dụng tiếp tục trong tần số đồng hồ. Thay vào đó, bộ xử lý hiện nay đang tiến triển

theo một mô thức mới mà đa lõi được ưu tiên hàng đầu để tăng xử lý tính toán. Các

ứng dụng xử lý tuần tự mà trước đây có lợi thế do chạy trên các bộ xử lý nhanh đã

không thấy phát triển giống như số mức độ tăng của nhân xử lý.

Để khai thác triệt để sức mạnh của các hệ thống nhiều lõi, các ứng dụng phải được thiết kế lại, phân chia thành các phần có thể tính toán song song, và phân phối

đều trên toàn số lõi có sẵn. Nhưng viết các dòng mã song song không hề đơn giản cho

các ngôn ngữ lập trình, công cụ phát triển, và thậm chí cả phần lớn các nhà phát triển.

Ngày nay, các nhà phát triển nhìn chung được đào tạo để viết mã nối tuần tự - song

song đòi hỏi một tư duy về lập trình khác nhau.

Đáp lại, ngành công nghiệp phát triển phần mềm đang có những bước tiến hiện thực hóa song song cho các nhà phát triển dễ tiếp cận hơn, và Microsoft đang giúp đỡ

để tìm lối đi. Microsoft thông báo rằng đã thiết lập nền móng cho việc xử lý song song nhằm khai thác sức mạnh tính toán của các kiến trúc đa lõi.

28

Chương 3. Tính toán song song

3.1.1. Cơ hội

Lập trình song song cung cấp các cơ hội to lớn cho khả năng mở rộng của cả thời

gian đáp ứng và năng lực. Với xử lý song song, một vấn đề lớn, phức tạp, có thể được

chia thành các vấn đề nhỏ hơn và xử lý nhanh hơn nhờ sức mạnh làm việc song song của đa lõi. Như vậy, nhiều khía cạnh của đời sống thực có thể áp dụng xử lý song

song, như:

 Kinh tế tri thức (Business Intelligence: BI)

Các bản báo cáo và phân tích thường sử dụng thủ tục phân tích trong đó có việc lặp lại mô hình với dữ liệu lớn. Song song hóa các thủ tục này có các báo cáo

nhanh hơn và chất lượng cao hơn. Vì dữ liệu BI thường đến từ một máy chủ

nên nếu sử dụng một mô hình song song trong đó tập hợp các dữ liệu từ nhiều

nguồn khác nhau sẽ giúp người sử dụng truy cập vào các kết quả nhanh hơn.

Điều này còn làm cho người sử dụng có thể có các kết quả khác có liên quan và

chính xác hơn về thời gian.

 Đa phương tiện

Tính toán song song có thể đem đến nhiều lợi ích cho các thế hệ tiếp theo của

hệ thống xử lý đa phương tiện. Các ứng dụng đa phương tiện hiện tại thường

dựa vào mô hình lập trình tuần tự để thực hiện các thuật toán mà có thể được

song song hóa ở mức độ cao. Thông qua việc sử dụng các kỹ thuật tính toán

song song và xử lý đa lõi, dữ liệu đa phương tiện có thể được xử lý bằng các

thuật toán song song, giảm thời gian xử lý tổng thể.

 Tài chính

Song song máy tính có thể giảm nguy cơ trong lĩnh vực tài chính bằng cách cho

người sử dụng truy cập nhanh hơn với thông tin tốt hơn. Ví dụ, lựa chọn cổ phiếu đại diện để bắt chước hiệu suất của một chỉ số tài chính lớn hơn liên quan đến việc tối ưu hoá chuyên sâu hơn một số lượng lớn dữ liệu trước đó. Song song quá trình này vì thế có thể dẫn đến hiệu năng tăng đáng kể. Với tính toán song song, có thể xem xét một loạt các thông số như thay đổi theo thời gian cho một tập hợp các công cụ tài chính. Nhiều khía cạnh của cùng một vấn đề có thể được gửi đến các lõi xử lý.

29

Chương 3. Tính toán song song

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

Các nhà phát triển cần xây dựng các ứng dụng song song có hiệu quả và đáng tin

cậy để chia sẻ tài nguyên hệ thống. Tuy nhiên, song song thông qua các mô hình lập

trình đa luồng truyền thống ngày nay là khó thực hiện và dễ bị lỗi trừ các ứng dụng

đơn giản nhất.

Để viết code song song hiệu quả, một nhà phát triển phải thực hiện hai chức năng

chính: xác định khả năng cho xử lý song song vấn đề và ánh xạ các mã tới các phần

cứng đa lõi. Cả hai chức năng là tốn thời gian, khó khăn, và dễ bị lỗi, vì có rất nhiều

các yếu tố phụ thuộc để theo dõi, chẳng hạn như bộ nhớ và lập kế hoạch bố trí cân bằng các lõi. Hơn nữa, các ứng dụng song song có thể được kiểm tra, gỡ lỗi, và phân

tích về tính chính xác của các chức năng, do đó chúng thường xuyên bị phát hiện các

lỗi tinh tế và các vấn đề hiệu suất của chương trình. Các công cụ gỡ lỗi và thiết kế xây

dựng các ứng dụng trên máy tính để lõi đơn gặp khó khăn khi phải đối mặt với những

thách thức như vậy trong xử lý trên nhiều lõi.

Một số thách thức, hoặc các vấn đề khó khăn phải được giải quyết trước khi song

song có thể được triển khai rộng rãi hơn, bao gồm:

 Làm thế nào để thể hiện và khai thác được xử lý song song.

 Làm thế nào để phối hợp các truy cập song song tới trạng thái chung.

 Làm thế nào để kiểm tra tính đúng đắn, gỡ lỗi chương trình và tăng hiệu suất.

Cụ thể hơn:

Thể hiện và khai thác được xử lý song song

Xử lý song song bởi nhiều lõi có một nhiệm vụ là lấy một công việc và phân chia

nó thành các công việc con mà độc lập với nhau, và sau đó có thể được xử lý bởi các

lõi. Sau đó, các chức năng cơ bản của các ngôn ngữ lập trình là để mô tả nhiệm vụ thực hiện dựa trên trình tự các công việc con. Khả năng để xác định việc thực hiện đồng thời các công việc con là một mô hình lập trình mới, vì vậy, nó đòi hỏi một sự thay đổi cơ bản trong phương pháp lập trình. Chúng ta gọi đây là “fine-grained concurrency” để làm nổi bật sự thay đổi sâu sắc này với những tính toán đồng thời

khác, ví dụ như quản lý không đồng bộ vào ra (asynchronous I /O).

Viết chương trình thể hiện và khai thác “fine-grained concurrency” vốn khó khăn

hơn so với viết chương trình tuần tự bởi các khái niệm, tư tưởng mới mà lập trình viên

phải nắm được và những đặc tính của xử lý song song được thể hiện trên chương trình.

30

Chương 3. Tính toán song song

Đứng đầu trong số những vấn đề này là không lường trước được nguy cơ gây ra lỗi khi

tương tác giữa các đối tượng mà bộ nhớ được chia sẻ và những khó khăn khi chứng minh rằng không có lỗi như thế tồn tại trong một chương trình.

Để sử dụng lại code và để tối đa hóa lợi ích của việc song song, các lập trình viên

cần đảm bảo rằng việc tính toán song song bên trong các thành phần không không liên

quan đến đặc tả giao diện bên ngoài. Khi các thành phần mới được phát triển có thể khai thác được xử lý song song, chúng có thể thay thế các thành phần cũ trong khi vẫn

giữ tất cả các giao diện ứng dụng người dùng. Không xây dựng cấu trúc khi tính toán

song song có thể khiến lỗi gặp phải trở nên trầm trọng hơn.

Ngoài ra, khi thành phần con của chương trình có thể được song song hóa thoải mái, một hệ thống phần cứng có thể phải xử lý song song nhiều hơn cần thiết trong sử

dụng các tài nguyên sẵn có. Các nhà phát triển (hoặc các chương trình ứng dụng) phải

có khả năng quản lý các nhu cầu về tài nguyên hệ thống của các thành phần chương trình khác nhau.

Phối hợp truy cập song song tới trạng thái được chia sẻ

Vấn đề khó khăn thứ hai cho các nhà lập trình song song bao gồm việc quản lý

các biến được chia sẻ và bị thay đổi bởi các công việc (tasks) trong một ứng dụng. Lập

trình viên cần có sự trừu tượng hóa tốt hơn so với những gì hiện có để phối hợp truy

cập ứng dụng song song tới trạng thái chung; họ cũng cần có cách làm tốt hơn để xây

dựng tài liệu và hạn chế những ảnh hưởng xấu của các hàm chức năng tới trạng thái

của ứng dụng. Kết hợp các mô hình tính toán song song sang các ngôn ngữ lập trình

phổ biến, chẳng hạn như C + +, C #, và Microsoft Visual Basic, không phải là dễ dàng.

Một cách đơn giản là tăng thêm các cơ chế đồng bộ hóa trong các ngôn ngữ như ổ

khóa và các biến sự kiện nhằm thông tin về mục mới của lỗi không có trong ngôn ngữ

cơ bản.

Bất kỳ giải pháp nào cho vấn đề tính toán song song phải giải quyết ba vấn đề

riêng biệt:

 Trật tự sắp xếp của các tính toán nhỏ.

 Tập hợp các cập nhật chưa được sắp xếp tới trạng thái chia sẻ (ví dụ biến dùng

chung).

 Việc quản lý các nguồn tài nguyên được chia sẻ.

31

Chương 3. Tính toán song song

Kiểm tra và gỡ lỗi, tính đúng đắn và hiệu suất

Một vấn đề khó khăn thứ ba là kiểm tra tính đúng đắ, gỡ lỗi và hiệu suất chương trình. Xử lý song song có thêm các yêu cầu trên tất cả các giai đoạn phát triển của ứng

dụng. Lịch trình kết quả phụ thuộc vào khả năng có thể làm xử lý theo mũ hay không.

Không thể áp dụng các cách gỡ lỗi của chương trình ứng dụng lập trình tuần tự cho

các chương trình được xử lý song song. Một vấn đề phức tạp hơn là việc kiểm soát lượng lớn các trạng thái, các biến dùng chung của hệ thống. Với hàng trăm công việc

con được chạy trong tiến trình, không thể xác định rõ ràng chương trình chạy đang ở

giai đoạn nào hoặc những trạng thái của nó đang được cập nhật đến đâu.

Tính toán song song cũng giới thiệu cái nhìn mới cho những vấn đề về phân tích và điều chỉnh khả năng chạy của chương trình, đồng thời nhấn mạnh về vấn đề này.

Ngoài một số thao tác đơn giản, một chương trình được lập trình song song bây giờ

phải quan tâm về số lượng xử lý đồng thời, các chí phí liên quan đến xử lý ấy, và khả năng xung đột khi các hoạt động đồng thời cùng lúc truy cập vào dữ liệu được chia sẻ.

Đây là tất cả những vấn đề mới mà lập trình viên tuần tự chưa gặp phải.

3.1.3. Giải pháp: Các công nghệ song song trong Visual Studio 2010 Microsoft

Lời mở đầu

Việc chuyển đổi sang lập trình song song trên nhiều nhân là cả cơ hội và khó

khăn cho cả nhà phát triển và các doanh nghiệp. Nếu không có các công cụ cải tiến và

công nghệ, các nhà phát triển có thể phải gặp nhiều khó khăn hơn trong các mô hình

tạo ra mã song song để tạo ra giá trị hiệu quá. Thời gian được dùng trong việc tạo ra

những ứng dụng song song cho người dùng để giải quyết nhiều vấn đề đồng thời có

thể rất lâu. Điều này làm giảm năng suất phát triển và loại bỏ sự hữu ích của chương

trình ứng dụng.

Để đáp lại, Microsoft cung cấp một giải pháp với Visual Studio 2010, dựa trên

bốn mục tiêu:

 Loại bỏ sự phức tạp khi viết mã song song của các nhà phát triển để giúp họ tập trung vào giải quyết các vấn đề quan trọng, do đó tăng năng suất làm việc.

 Đơn giản hóa quá trình viết các ứng dụng song song.

 Có một giải pháp tiếp cận toàn diện, cung cấp các giải pháp đi từ xử lý các

nhiệm vụ đồng thời đến xử lý dữ liệu song song.

 Chú trọng đến nhu cầu của các nhà phát triển.

32

Chương 3. Tính toán song song

Tổng quan

Microsoft Visual Studio 2010 đã đối mặt với những vấn đề khó khăn trong tính

toán song song, hỗ trợ lập trình ở mức cao hơn với các cấu trúc trừu tượng giúp các

nhà phát triển tạo ra các cách song song hợp lý và ánh xạ nó đến phần cứng. Visual

Studio 2010 cũng bao gồm các công cụ phát triển tiên tiến hỗ trợ các kiến trúc lập trình, sửa lỗi ứng với cách xử ly song song được thể hiện trong mã.

Hình 3.1: Công nghệ song song có trong Visual Studio 2010 [8].

3.2. Lập trình song song với Visual Studio 2010 [8]

3.2.1. Thư viện

Đối với việc xây dựng và thực hiện các ứng dụng song song, Visual Studio 2010

có các thư viện mới cho phát triển các ứng dụng với C++ như:

 Parallel Pattern Library (PPL).

 Concurrency Primitives and Algorithms  Concurrency Containers

33

Chương 3. Tính toán song song

 Asynchronous Agents Library.

 Asynchronous Agents  Messaging Blocks

 Parallel Extensions to the Microsoft .Net Framework.

 Parallel LINQ (PLINQ)  Task Parallel Library (TPL)

Chúng ta sẽ đề cập chi tiết hơn về thư viện Parallel Extensions vì nó được sử

dụng để tạo ra chương trình sinh khóa.

Parallel Extensions Là một sự bổ sung cho các thư viện của Microsoft .NET Framework. Nó có cấu trúc song song ở cấp cao cho các ứng dụng quản lý, bao gồm:

 Parallel LINQ (PLINQ). Một mô hình khai báo cho dữ liệu song song dựa trên

Language Integrated Query (LINQ).

 Task Parallel Library (TPL). Một mô hình cho cả nhiệm vụ và dữ liệu song song dựa trên mô hình song song rõ ràng, chẳng hạn như nhiệm vụ và tương lai,

và cấu trúc song song, như Parallel.For.

 Coordinations Data Structures (CDS). Một tập hợp của các thao tác phối hợp và

đồng bộ hóa để đơn giản hóa kết nối và các mẫu khởi tạo.

Parallel Extensions hướng đến các nhà phát triển sử dụng bất kỳ ngôn ngữ. NET nào, chẳng hạn như C #, Visual Basic, C + + / CLI, và F #. Paralle Extensions khiến

mọi việc trở nên dễ dàng khi tự động song song hóa các truy vấn từ LINQ đến đối

tượng, đạt được độ tăng tốc đáng kể với những thay đổi rất ít đến cơ sở mã hiện có của

các nhà phát triển. Task Parallel Library đơn giản hóa việc giới thiệu dữ liệu và song

song các nhiệm vụ (task) vào một ứng dụng, thông qua các cấu trúc song song của

vòng lặp hoặc thông qua song song của thuật toán phức tạp hơn sử dụng fine-grained.

3.2.2. Các mô hình lập trình song song và ví dụ

Visual Studio 2010 hỗ trợ ba mô hình chính để thể hiện các tính toán song song:

Data Parallelism

 Parallel Loops (vòng lặp song song) Ví dụ:

concurrent_vector Query(vector stocks) {

34

Chương 3. Tính toán song song

concurrent_vector results;

parallel_for_each(stocks.begin(), stocks.end(), [&](StockQuote stock) {

if (stock.marketCap > 100000000000.0 &&

stock.changePct < 0.025 &&

stock.volume > 1.05 * stock.volumeMavg3M) { results.push_back(stock);

}

});

return results; }

 PLINQ Ví dụ:

IEnumerable Query(IEnumerable stocks) {

return from stock in stocks.AsParallel()

where stock.MarketCap > 100000000000.0 &&

stock.ChangePct < 0.025 &&

stock.Volume > 1.05 * stock.VolumeMavg3M

select stock;

}

Task Parallelism

 Parallel Invoke Tuần tự:

void quicksort(int * a, int n) {

if (n <= 1) return;

int s = partition(a,n);

quicksort(a,s);

quicksort(a+s,n-s); }

Song song:

void quicksort(int * a, int n) { if (n <= 1) return; int s = partition(a,n); parallel_invoke(

35

Chương 3. Tính toán song song

[&]{quicksort(a,s);},

[&]{quicksort(a+s,n-s);}); }

 Tasks (các nhiệm vụ) Ví dụ:

void quicksort(int * a, int n) {

if (n <= 1) return;

int s = partition(a,n);

task_group tasks; tasks.run([&]{quicksort(a,s);});

tasks.run([&]{quicksort(a+s,n-s);});

tasks.wait();

}

Data Flow Parrallelism

 Futures var symbols = new [] { "MSFT", "INTL", "AAPL", "GOOG" };

var prices = new Dictionary>(symbols.Length);

foreach(var symbol in symbols)

{

prices.Add( symbol, Task.Factory.StartNew( () => GetPrice( symbol ) )

);

}

 Continuations

var c = Task.Factory.StartNew(() => A()) .ContinueWith(a => B(a.Result))

.ContinueWith(b => C(b.Result));

 Messaging blocks and asynchronous agents (truyền khối tin và các agent không

đồng bộ)

HRESULT LogChunkFileParser::ParseFile(){ unbounded_buffer* MsgBuffer = new unbounded_buffer(); // Parsing agent AgentTask* pParserAgent = new AgentTask([&]{

36

Chương 3. Tính toán song song

AgentMessage msg;

while((msg = receive(MsgBuffer))->type != EXIT) {

Parse(msg->pCurrentLine);

delete msg->pCurrentLine;

} });

pParserAgent->start();

// Read the file HRESULT hr = S_OK;

WCHAR* wszLine;

hr = reader->OpenFile(pFileName);

if (SUCCEEDED(hr)){

while(!reader->EndOfFile()){

wszLine = new WCHAR[MAX_LINE];

// Read the next line... hr = reader->ReadLine(wszLine, MAX_LINE);

if (SUCCEEDED(hr)){

// ... and parse it

send(MsgBuffer, AgentMessage(wszLine));

}

}

send(MsgBuffer, AgentMessage(EXIT));

hr = agent::wait(&pParserAgent);

}

return hr;

37

Chương 3. Tính toán song song

Hình 3.2: Kiến trúc lập trình song song trong .Net Frame Work 4.0 [8].

3.2.3. Kết luận

Cải tiến phần mềm trong tương lai phần lớn sẽ xoay quanh sự tận dụng lợi thế

của vi xử lý nhiều lõi thông qua tính toán song song. Ngành công nghiệp phát triển

phần mềm đang có những bước tiến để hiện thực hóa song song sao cho dễ tiếp cận

hơn và khả thi cho tất cả các nhà phát triển. Các giải pháp toàn diện có trong Microsoft

Visual Stuio 2010 hỗ trợ xử lý song song đa lõi từ bên trong hệ điều hành đến các

chương trình ứng dụng. Những công nghệ này cho phép phát triển các ứng dụng và thư

viện với khả năng xử lý song song trên quy mô rộng với bộ xử lý đa lõi và tốc độ xử lý

sẽ vẫn tiếp tục phát triển đi đôi với tốc độ phát triển của lõi xử lý theo cấp số nhân

trong tương lai.

38

Chương 4. Kết quả triển khai và tính thử nghiệm

Chương 4. Kết quả triển khai và tính thử nghiệm

4.1. Giới thiệu về chương trình ứng dụng

4.1.1. Mục đích và hoạt động của chương trình

Mục đích

qp,

Chương trình tạo ra với mục đích sinh khóa cho hệ thống cấp phát chứng thực số.

Cụ thể hơn sinh cặp số nguyên tố mạnh - là yếu tố chủ chốt trong việc sinh khóa

hệ mã RSA được ứng dụng của hệ thống CA.

Mô tả hoạt động

qp,

Đầu vào

Số N: số cặp sẽ được sinh ra sau khi chương trình chạy xong.

Quá trình xử lý sinh một cặp số

 Chương trình sử dụng hàm khởi tạo class mới RSACryptoServiceProvider có namespace System.Security.Cryptography. Về thực chất việc tạo ra class mới

, nqpde ,

,

,

trên chính là sinh ra một chìa khóa RSA mà trong đó có các thành phần như

qp,

.

qp,

 Chuyển 2 số từ dạng dữ liệu byte[] sang kiểu BigInteger (class số nguyên

1002

lớn trong System.Numerics). Sau đó với từng số kiểm tra các test.

 Kiểm tra số p theo: thuật toán Miller-Rabin xác suất lỗi và thuật toán

1002

Lucas.

 Kiểm tra số q theo: thuật toán Miller-Rabin xác suất lỗi và thuật toán

Lucas.

 Kiểm tra điều kiện ràng buộc giữa p và q để chìa khóa RSA trên là an toàn

qp,

,

,

theo chuẩn FIPS 186-3.

qqpp 1 1,2

2

p

,1

p

,1

q

,1

q

1

 Kiểm tra tính nguyên tố mạnh của : tìm các thừa số nguyên tố

lần lượt của và kiểm tra độ dài tính theo bit của chúng dựa

trên bảng 2.3.

qp,

Các kiểm tra Miller-Rabin, Lucas, và tính nguyên tố mạnh là do bản thân em tự code dựa theo hướng dẫn thuật toán ở phần 2.2.2, 2.2.3, và 2.3.

Phân công song song khi sinh N cặp

39

Chương 4. Kết quả triển khai và tính thử nghiệm

 Sử dụng vòng lặp song song Parallel.For trong namespace

qp,

System.Threading.Tasks đi từ 0 đến N-1 bên ngoài quá trình xử lý sinh một cặp số ở trên. Các công việc cụ thể được tự động chia đều lên số lõi hiện có.

,

,

p

,1

p

,1

q

,1

q

1

 Ngoài ra trong quá trình kiểm tra tính nguyên tố mạnh của có bước tìm các

qqpp 1,2 1

2

thừa số nguyên tố lần lượt của . Các bước này

là độc lập nên đã được song song bằng lệnh Parallel.Invoke.

qp,

Đầu ra

thỏa mãn các điều kiện là số giả  Đầu ra của chương trình là N cặp số

p

 q

,1 

1

nguyên tố có xác suất lỗi rất thấp (giả nguyên tố mạnh) và đồng thời có tính

qp,

chất mạnh theo nghĩa số khó bị hacker phân tích ra các thừa số

qp,

nguyên tố vụn khi được dùng làm khóa.

 Chương trình thông báo số cặp đã được sinh bằng thư viện C# không thỏa

mãn kiểm tra Miller-Rabin và Lucas, không thỏa mãn điều kiện nguyên tố

mạnh. Ngoài ra, chương trình còn thông báo thời gian chạy của chương trình có

sai số (trong điều kiện không lý tưởng là vì trong quá trình chương trình chạy

còn có các tiến trình khác của hệ điều hành cũng đang chạy).

4.1.2. Một số hình ảnh về chương trình

Giao diện chính

40

Chương 4. Kết quả triển khai và tính thử nghiệm

Hình 4.1: Giao diện của chương trình

qp,

Trong đó:

N là số cặp

sẽ được sinh ra

Button Generate Sequently để kích hoạt sự kiện sinh các cặp số nguyên tố được lập

trình tuần tự.

Button Generate Parallelly để kích hoạt sự kiện sinh các cặp số nguyên tố được song

song.

Button Show để thể hiện 1 cặp số nguyên tố ra màn hình theo thứ tự lần lượt sau mỗi

lần bấm.

Các thông báo của chương trình

41

qp,

Chương 4. Kết quả triển khai và tính thử nghiệm

Hình 4.2: Số cặp đã bị loại vì không thỏa mãn kiểm tra xác suất tính nguyên

qp,

tố.

Hình 4.3: Số cặp đã bị loại vì không thỏa mãn điều kiện để là số nguyên tố

mạnh.

Hình 4.4: Thời gian chạy của chương trình.

Hình 4.5: Hình ảnh của CPU khi sinh số nguyên tố một cách tuần tự.

42

Chương 4. Kết quả triển khai và tính thử nghiệm

Hình 4.6: Hình ảnh của CPU khi sinh số nguyên tố một cách song song.

Ta có thể thấy lập trình song song tận dụng triệt để tài nguyên của hệ thống, đặc biệt

hiệu quả cao khi có một máy tính đa lõi chuyên dùng cho việc sinh khóa.

4.2. Một số thống kê khi chạy chương trình trên chip intel core2duo 2.2 GHZ

Bảng 4.1: Thống kê khi sinh 2 cặp p, q

Số thứ tự

Thời gian chạy (tính theo giây) Thời gian chạy (tính theo giây)

Xử lý tuần tự Số cặp không qua được điều kiện nguyên tố mạnh Xử lý song song Số cặp không qua được điều kiện nguyên tố mạnh

Số cặp không qua được Miller- Rabin và Lucas test Số cặp không qua được Miller- Rabin và Lucas test 16 8 10 45 24 25 1

68 38 40 25 18 16 2

16 12 11 55 41 26 3

24 17 17 18 16 9 4

25 23 19 35 19 14 5

98 97 90 149 178 118 Tổng

Với xử lý tuần tự: 2 + 149 + 98 = 249 cặp trong 97 giây. Với xử lý song song: 2 + 178 + 118 = 398 cặp trong 90 giây ~ 249 cặp trong 56.3 giây.

Nhận xét: Như vậy, thời gian xử lý song song trong thống kê này giảm xuống đáng kể (còn ~0.6 lần) so với xử lý tuần tự. Có thể đi đến kết luận: thời gian xử lý tỷ lệ nghịch với số lõi. Điều đó cho thấy hiệu quả về mặt thời gian của xử lý song song.

43

PHỤ LỤC

A. Thuật toán Miller-Rabin bool satisfyMillerRabinTest(BigInteger bigP) { // Miller-Rabin algorithm test on prime bigP BigInteger bigP1 = bigP - 1; BigInteger m = bigP1; BigInteger b = new BigInteger(); int a = 0; int wlen = 64; byte[] byteB = new byte[wlen]; while (m % 2 == 0) // find largest number a to have bigP1 divides 2^a; { ++a; m = m / 2; } RNGCryptoServiceProvider random = new RNGCryptoServiceProvider(); // class random number int iterations = 7; for (int i = 0; i < iterations; i++) { // start testing while (true) { random.GetBytes(byteB); // random number b b = transform(byteB); // transform b from byte[] to big integer if (b > 1 && b < bigP1) break; } BigInteger z = BigInteger.ModPow(b, m, bigP); // equals to b ^ m mod bigP if (z.Equals(1) || z.Equals(bigP1)) continue; for (int j = 0; j < a - 1; j++) { z = BigInteger.ModPow(z, 2, bigP); // equals to z ^ 2 mod bigP if (z.Equals(bigP1)) continue; if (z.Equals(1)) return false; }

return false;

} return true; } B. Thuật toán Lucas bool satisfyLucasTest(BigInteger c) { // Lucas algorithm test on prime c BigInteger d = 5; int distance = - 2; while (true) { // find number d satisfy that jacobi(d, c) = -1 BigInteger r = BigInteger.ModPow(d, (c - 1) / 2, c); // equals to (d ^ (c-1)/2) mod c if (r.IsZero) return false; if (!r.Equals(1)) break; // if value of jacobi(d,c) is -1, break; d = d * (-1) + distance; distance *= (-1); } BigInteger k = c + 1; List listK = new List(); listK.Clear();

44

while (k > 0) { // binary expansion of k stored in listK BigInteger r = k % 2; listK.Add((int)r); k = k / 2; } BigInteger u = 1, v = 1; BigInteger uTemp, vTemp; for (int i = listK.Count - 2; i >= 0; i--) { // start testing uTemp = (u * v) % c; BigInteger tmp = d * u * u + v * v; if (!tmp.IsEven) vTemp = ((tmp + c) / 2) % c; else vTemp = (tmp / 2) % c; if (listK.ElementAt(i) == 1) { tmp = uTemp + vTemp; if (tmp.IsEven) u = (tmp / 2) % c; else u = ((tmp + c) / 2) % c; tmp = vTemp + d * uTemp; if (tmp.IsEven) v = (tmp / 2) % c; else v = ((tmp + c) / 2) % c; } else { u = uTemp; v = vTemp; } } if (u.IsZero) return true; // satisfied else return false; // not satisfied } C. Thuật toán kiểm tra nguyên tố mạnh bool satisfyStrongPrimesConditions(RSAParameters para) { BigInteger p = transform(para.P); BigInteger q = transform(para.Q);

BigInteger p1, p2, q1, q2;

Parallel.Invoke( () => { p1 = findFactor(p - 1); }, () => { p2 = findFactor(p + 1); }, () => { q1 = findFactor(q - 1); }, () => { q2 = findFactor(q + 1); } );

45

if (p1 == 0 || p2 == 0 || q1 == 0 || q2 == 0) return false; byte[] bp1 = p1.ToByteArray(); byte[] bp2 = p2.ToByteArray(); byte[] bq1 = q1.ToByteArray(); byte[] bq2 = q2.ToByteArray(); if (bp1.Length < 13 || bp2.Length < 13 || bq1.Length < 13 || bq2.Length < 13) return false; if ((bp1.Length + bp2.Length) > 62 || (bq1.Length + bq2.Length) > 62) return false;

return true; }

46

KẾT LUẬN

Khóa luận nêu lên được vấn đề bức thiết trong xã hội hiện nay là xây dựng hệ

qp,

thống chứng thực số, tạo chữ ký số; có hệ thống các lý thuyết để giải quyết vấn đề.

Khóa luận có chương trình xử lý song song khi sinh cặp số nguyên tố và kiểm tra

tính nguyên tố mạnh của chúng đi kèm – một giai đoạn quan trọng, chủ chốt của hệ thống CA.

qp,

Chương trình sinh khóa được xây dựng từ chương trình sinh hai số nguyên tố

này sẽ đảm bảo mức độ an toàn của hệ thống CA trước sự tấn công của các

hacker chuyên nghiệp. Với sự tìm hiểu không ngừng của giới thám mã (một cộng đồng

có mục đích phát hiện lỗi của hệ mã RSA nhằm đóng góp xây dựng hệ mã ngày càng

an toàn hơn), các lý thuyết về khóa mạnh đã được ra đời và chương trình này dựa trên

những lý thuyết ấy để thực hiện. Một hệ thống CA an toàn sẽ mang lại nhiều ý nghĩa

to lớn cho công cuộc số hóa của đất nước.

Kết quả là khả quan, thể hiện đúng tinh thần của một khóa luận tốt nghiệp có tính thực tiễn, ứng dụng cao. Kết quả này có thể được sử dụng để phát triển cho tương lai

như: xây dựng hệ thống CA hoàn chỉnh; xây dựng công cụ dùng để mã hóa, giải mã

văn bản theo thuật toán của hệ mã RSA, tạo chữ ký số.

47

TÀI LIỆU THAM KHẢO

[1]

Phạm Huy Điển – Hà Huy Khoái. Mã hóa thông tin cơ sở toán học và ứng

dụng. Nhà xuất bản Đại học Quốc gia Hà Nội, 2004, trang 6-12, 31-32, 85-91.

[2] Hà Huy Khoái – Phạm Huy Điển. Số học thuật toán. Nhà xuất bản Đại học

Quốc gia Hà Nội, 2003, trang 21-23, 34-38.

[3] http://tailieu.vn/xem-tai-lieu/giai-phap-xac-thuc-so.176584.html

[4] http://vi.wikipedia.org/wiki/Kh%C3%B3a_c%C3%B4ng_khai

[5] http://soict.hut.vn/~vannk/.../BaiGIangMatMaKhoaCongKhai-NKVan.pdf

[6] http://vi.wikipedia.org/wiki/Ch%E1%BB%AF_k%C3%BD_s%E1%BB%91

[7]

http://vi.wikipedia.org/wiki/Ch%E1%BB%A9ng_th%E1%BB%B1c_kh%C3%

B3a_c%C3%B4ng_khai

[8] Microsoft. Taking Parallelism Mainstream Microsoft October 2009.

http://msdn.microsoft.com/en-us/concurrency/ee847335.aspx, trang 1-21.

[9] NIST - U.S. National Institute of Standards and Technology. FIPS 186-3. Trang

50-51, 68-73.

[10] http://en.wikipedia.org/wiki/Strong_prime

[11] http://www.ece.gmu.edu/courses/ECE543/project/reports_1999/dong_report.pdf

[12] http://people.csail.mit.edu/.../RivestSilverman-

AreStrongPrimesNeededForRSA.pdf

[13] http://www.mediafire.com/?ljvmmhnd2kz

48