Đề tài Xử lý song song quá trình sinh khóa của hệ thống cấp phát chứng thực số

rong 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] 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 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ư 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. 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. 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. Hệ RSA được xây dựng trên cơ sở mã mũ, trong đó khóa lập mã (công khai) là cặp , gồm số mũ và modulo . Khóa giải mã (bí mật) là cặp . Với là số nghịch đảo của modulo . Số là tích của hai số nguyên tố rất lớn nào đó, , còn được chọn là số nguyên tố cùng nhau với , trong đó là giá trị hàm Euler của . Để 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 độ yêu cầu) với một số chẵn chữ số. Để mã hóa một khối 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 mã không đòi hỏi phải “khai căn bậc modulo ” của khối văn bản mã, nếu như biết được số nghịch đảo của modulo , tức là thỏa mãn . Nghịch đảo này tồn tại theo điều kiện và, do hệ quả đã nêu, ta có , khi . Chú ý rằng, xác suất để và 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 là bội của hoặc . Thông thường chỉ là những “khối văn bản” có độ dài không lớn, nói chung là nhỏ hơn hẳn và , 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 trong văn bản mật cũng chính là việc nâng lên lũy thừa bậc rồi rút gọn theo modulo . Cặp được gọi là khóa giải mã. 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 thì ta phải tìm được . Việc tìm không dễ hơn với việc phân tích ra tích của hai số nguyên tố rất lớn là và . Thật vậy, ta có: ; . Từ các công thức đó để tìm được và 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ố và khoảng 100 chữ số thập phân, thì 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=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541 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ố và để tránh rơi vào trường hợp tích bị phân tích nhanh nhờ những thuật toán đặc biệt: và cần chọn sao cho 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ỏ, và 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ố. Các Định lý về số nguyên tố [2] Mọi hợp số đều có ước nguyên tố nhỏ hơ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: Với mỗi số thực dương cho trước, ta ký hiệu là số các số nguyên tố không vượt quá x. Khi đó, ta có: . Ước chung lớn nhất [2] Ướ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] Với , số lượng các số tự nhiên bé hơn và nguyên tố cùng nhau với được ký hiệu là . Ví dụ: , , . Rõ ràng, khi là số nguyên tố thì mọi số tự nhiên bé hơn nó đều là nguyên tố cùng nhau với nó và do đó ta có . Tổng quát hơn, khi là số nguyên tố và là một số tự nhiên bất kỳ thì . Có thể chứng minh được rằng khi là các số nguyên tố cùng nhau thì ta có 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ụ: . Phép tính đồng dư [1] Giả sử m là một số nguyên dương. Ta nói hai số nguyên và là đồng dư với nhau theo modulo nếu hiệu chia hết cho . Ký hiệu . Phép tính đồng dư theo modulo dẫn đến việc tách tập số nguyên ra thành 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 ký hiệu là ( là tập các số nguyên) và chứa đúng phần tử. Mỗi lớp trong tập 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. Một số tính chất của phép tính đồng dư: ; Nếu thì ; Nếu và thì ; Nếu , thì , ; 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 . Nếu là một phần tử trong và thì tồn tại các số sao cho , tức là , nên người ta nói có nghịch đảo (trong ) là , và thường ký hiệu phần tử nghịch đảo này là , hay . Định lý Fermat (bé)[2]: Nếu là một số nguyên tố còn là một số nguyên thì . Nếu không chia hết cho (tức là ) thì . Ví dụ. Dễ dàng thấy rằng ; ; . Thặng dư bình phương [1] Cho số nguyên tố . Số nguyên được gọi là thặng dư bình phương nếu như tồn tại số nguyên thỏa mãn phương trình . Ký hiệu Legendre [1] Với số nguyên tố và số nguyên bất kỳ người ta ký hiệu Và chỉ ra rằng sẽ bằng 0 khi chia hết cho , bằng 1 khi là một thặng dư bình phương và bằng -1 trong trường hợp còn lại. Có thể mở rộng khái niệm ký hiệu trên ra cho trường hợp không phải là nguyên tố, nhưng chỉ xét những số trong tập thặng dư rút gọn của (tức là những thặng dư nguyên tố cùng nhau với ). Ký hiệu Jacobi [1] Với số nguyên , trong đó , , là các số nguyên tố, còn nằm trong tập thặng dư rút gọn của , ta ký hiệu . Như vậy trong trường hợp riêng khi 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 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á . Độ 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 quá là vào khoảng . Để chia cho , ta cần phép tính bít. Như vậy, nếu vào cỡ khoảng 100 chữ số thập phân, số các phép tính bit phải dùng sẽ vào cỡ . Với những máy tính thực hiện một triệu phép tính một giây, 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] Theo định lý Fermat, nếu là số nguyên tố và là số nguyên tùy ý, thì . Do đó nếu tồn tại số sao cho thì phải là hợp số. Như 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: Giả sử là một số nguyên dương. Nếu là hợp số nguyên dương và , thì được gọi là số giả nguyên tố cơ sở . 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, có tất cả 455052512 số nguyên tố bé hơn , nhưng chỉ có 14884 số giả nguyên tố cơ 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ố. 2.2.2. Kiểm tra số giả nguyên tố mạnh Kiểm tra Miller [2] Giả sử là số nguyên dương lẻ, , trong đó là số nguyên không âm, là số nguyên dương lẻ. Ta nói trải qua được kiểm tra Miller cơ sở , nếu , hoặc , với nào đó, . Số nguyên được gọi là giả nguyên tố mạnh cơ sở nếu nó là hợp số và trải qua được kiểm tra Miller cơ sở . 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ý : Nếu là một hợp số dương lẻ thì tồn tại không quá , , sao cho 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ố được chọn ngẫu nhiên trong khoảng thì trải qua kiểm tra Miller cơ sở với xác suất bé hơn . Như vậy, nếu ta chọn số ngẫu nhiên thì xác suất để trải qua kiểm tra Miller đối với cơ sở đó sẽ bé hơn . Khi đủ lớn, với dụ , xác suất đó quá nhỏ, nên với trải qua 20 cơ sở ngẫu nhiên thì có thể tin “gần chắc chắn” rằng 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 Input: 1. The odd integer to be tested for primality. This will be either or , or one of the auxiliary primes or . 2. The number of iterations of the test to be performed; the value shall be consistent with Table 3 or 4. Output: 1. The status returned from the validation procedure, where status is either PROBABLY PRIME or COMPOSITE. Process: 1. Let be the largest integer such that divides . 2. . 3. . 4. For to do 4.1 Obtain a string of bits from an RBG. Comment: Ensure that . 4.2 If , then go to step 4.1. 4.3 . 4.4 If , then go to step 4.7. 4.5 For to do 4.5.1 . 4.5.2 If , then go to step 4.7. 4.5.3 If , then go to step 4.6. 4.6 Return COMPOSITE. 4.7 Continue. Comment: Increment 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. RGB là bộ sinh bít ngẫu nhiên Input: 1. The odd integer to be tested for primality. This will be either or , or one of the auxiliary primes or . 2. The number of iterations of the test to be performed; the value shall be consistent with Table 3 or 4. Output: 1. 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. Process: 1. Let be the largest integer such that divides . 2. . 3. . 4. For to do 4.1 Obtain a string of bits from an RBG. Comment: Ensure that . 4.2 If , then go to step 4.1. 4.3 . 4.4 If , then return PROVABLY COMPOSITE WITH FACTOR and the value of . 4.3 . 4.4 If , then go to step 4.15. 4.7 For to do 4.7.1 Comment: and 4.7.2 4.7.3 If , then go to step 4.15. 4.7.4 If , then go to step 4.12. 4.8 Comment: and 4.9 . 4.10 If , then go to step 4.12. 4.11 Comment: and . 4.12 . 4.13 If , then return PROVABLY COMPOSITE WITH FACTOR and the value of g 4.14 Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME. 4.15 Continue. Comment: Increment 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 > 100 bits và : 512 bits Xác suất lỗi Cho : 28 Cho và : 5 > 140 bits và : 1024 bits Xác suất lỗi Cho : 38 Cho và : 5 > 170 bits và : 1536 bits Xác suất lỗi Cho : 41 Cho và : 4 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 > 100 bits và : 512 bits Cho : 38 Cho và : 7 > 140 bits và : 1024 bits Cho : 32 Cho và : 4 > 170 bits và : 1536 bits Cho : 27 Cho và : 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] Input: The candidate odd integer to be tested for primality. Output: Where status is either PROBABLY PRIME or COMPOSITE. Process: Find the first D in the sequence for which the Jacobi symbol . If for any in the sequence, return (COMPOSITE). Let be the binary expansion of , with . Set and . For to do . . If then . . Else . . If then return (PROBABLY PRIME). Otherwise, return (COMPOSITE). Bước 5.2, 5.3.1 và 5.3.2 có biểu thức dưới dạng , trong đó là số nguyên, và là số nguyên lẻ. Nếu không nguyên (do lẻ), thì có thể được 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ố được gọi là mạnh khi nó thỏa mãn các tính chất như sau [10], [12]: lớn. có thừa số nguyên tố lớn. Nghĩa là, với nào đó và là số nguyên tố lớn. có thừa số nguyên tố lớn. Nghĩa là, với nào đó và là số nguyên tố lớn. có thừa số nguyên tố lớn. Nghĩa là, với nào đó và là số nguyên tố lớn. Đô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: Bảng 2.3. Điều kiện của các số nguyên tố thành phần [10] Độ 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 3072 > 170 bits < 1518 bits Trong đó lần lượt là các thừa số nguyên tố của ; là độ dài của modulo tính theo bit; là độ dài của số 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]: i. Số mũ công khai phải thỏa mãn: - Phải được chọn trước để tạo ra và . - Là 1 số nguyên dương lẻ thỏa mãn: . - Có thể là số định sẵn hoặc được chọn ngẫu nhiên. ii. Hai số và phải thỏa mãn: - và sẽ nguyên tố cùng nhau với . - . - . - , là độ dài theo bit của . iii. Sau khi sinh ra và , số mũ bí mật được chọn phải thỏa mãn: - Là 1 số nguyên dương và . - , với là ước chung lớn nhất của và . - Nếu thì phải được chọn lại. Số có thể được chọn lại nhưng không cần thiết. 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. 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ý. 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ó