Giáo trình Bảo mật thông tin - Chương 4: Hệ mật mã khoá công khai (RSA) tại ĐH Sư phạm Kỹ thuật Nam Định

Giáo trình bảo mật thông tin phần 2 của Đại học Sư phạm Kỹ thuật Nam Định cung cấp kiến thức chuyên sâu về mã hóa dữ liệu, bảo mật hệ thống mạng, quản lý rủi

• Trường học: Trường Đại học Công nghệ Thông tin
• Chuyên ngành: Bảo mật thông tin
• Loại tài liệu: Giáo trình
• Năm xuất bản: 2022

Tóm tắt

I. Tổng quan về mật mã khóa công khai hệ thống giáo trình

Mật mã khóa công khai là phương pháp bảo mật thông tin sử dụng hai loại khóa riêng biệt: khóa công khai (public key) để mã hóa dữ liệu và khóa bí mật (private key) để giải mã. Hệ thống này khắc phục nhược điểm của mật mã khóa bí mật truyền thống khi yêu cầu chia sẻ khóa an toàn trước khi truyền thông tin. Giáo trình Bảo mật thông tin tại Đại học Sư phạm Kỹ thuật Nam Định trình bày chi tiết nguyên lý hoạt động, ưu điểm vượt trội và ứng dụng thực tế của hệ mật này. Nội dung phân tích các bài toán cơ sở như phân tích số nguyên tố, bài toán RSA, cùng các thuật toán giải quyết vấn đề phân phối khóa. Hệ thống giáo trình cung cấp ví dụ minh họa sinh động giúp sinh viên dễ dàng nắm bắt kiến thức phức tạp này.

1.1. Nguyên lý hoạt động cơ bản

Hệ mật khóa công khai hoạt động dựa trên nguyên tắc bất đối xứng giữa khóa mã hóa và khóa giải mã. Bob tạo cặp khóa gồm khóa công khai ek (công bố rộng rãi) và khóa bí mật dk (giữ bí mật). Alice sử dụng ek để mã hóa thông điệp gửi Bob, trong khi chỉ Bob mới có thể giải mã nhờ dk. Giáo trình giải thích quá trình này thông qua ví dụ cụ thể: Bob công bố khóa ek=5, giữ dk=29. Alice mã hóa thông điệp m=12 thành c=12^5 mod 33=12. Bob giải mã c=12 thành m=12^29 mod 33=12 nhờ dk=29. Cơ chế này đảm bảo an toàn ngay cả khi kẻ tấn công biết ek.

1.2. Lịch sử phát triển và ứng dụng

Ý tưởng mật mã khóa công khai lần đầu được giới thiệu năm 1976 bởi Diffie và Hellman. Hệ mật RSA, do Rivest-Shamir-Adleman phát triển năm 1977, trở thành chuẩn mực ngành nhờ độ bảo mật cao. Giáo trình phân tích sự tiến hóa từ hệ mật cổ điển đến hiện đại, nhấn mạnh ứng dụng trong thương mại điện tử, chữ ký số, xác thực danh tính. Tại Đại học Sư phạm Kỹ thuật Nam Định, sinh viên được hướng dẫn triển khai hệ mật này trong các bài tập lập trình, nghiên cứu ứng dụng blockchain. Hệ thống giáo trình tích hợp lý thuyết toán học nền tảng với thực hành kỹ thuật, phù hợp chương trình đào tạo kỹ sư an toàn thông tin.

II. Phân tích các bài toán cơ sở trong mật mã khóa công khai

Hệ mật khóa công khai dựa trên các bài toán toán học khó giải quyết, đảm bảo an toàn cho hệ thống. Giáo trình Bảo mật thông tin tại Đại học Sư phạm Kỹ thuật Nam Định tập trung phân tích ba bài toán cốt lõi: phân tích số nguyên thành thừa số nguyên tố, bài toán RSA, và bài toán logarit rời rạc. Mỗi bài toán đóng vai trò quan trọng trong thiết kế hệ mật khác nhau. Phần này cung cấp định nghĩa chính xác, ví dụ minh họa, và đánh giá độ phức tạp tính toán. Sinh viên được hướng dẫn phân biệt ưu nhược điểm của từng bài toán khi ứng dụng vào thực tế. Nội dung cũng đề cập đến mối liên hệ giữa các bài toán này với độ bảo mật của hệ mật hiện đại.

2.1. Bài toán phân tích số nguyên tố

Bài toán yêu cầu phân tích số nguyên dương n thành tích các thừa số nguyên tố, ví dụ n=15=3×5. Giáo trình giải thích ứng dụng trong hệ mật RSA khi n=p×q (p,q là số nguyên tố lớn). Độ khó của bài toán tăng theo kích thước số nguyên, đảm bảo an toàn cho hệ mật. Sinh viên được hướng dẫn sử dụng thuật toán Pollard Rho, thuật toán Fermat để giải quyết bài toán này. Nội dung nhấn mạnh tầm quan trọng của việc lựa chọn số nguyên tố đủ lớn (ít nhất 1024 bit) trong triển khai thực tế.

2.2. Bài toán RSA và logarit rời rạc

Bài toán RSA liên quan đến việc tìm m từ phương trình m^e ≡ c (mod n), khi biết e,n,c. Giáo trình phân tích điều kiện tồn tại nghiệm dựa trên hàm Euler φ(n). Phần logarit rời rạc nghiên cứu phương trình g^x ≡ h (mod p), khó giải khi p là số nguyên tố lớn. Cả hai bài toán đều cung cấp nền tảng cho các hệ mật hiện đại. Sinh viên được hướng dẫn triển khai thuật toán giải quyết bằng phương pháp brute-force, baby-step giant-step. Nội dung so sánh độ khó tương đương giữa hai bài toán, ảnh hưởng đến lựa chọn hệ mật phù hợp.

III. Phương pháp triển khai hệ mật khóa công khai trong thực tế

Triển khai hệ mật khóa công khai đòi hỏi hiểu biết sâu sắc về toán học và kỹ thuật lập trình. Giáo trình Bảo mật thông tin tại Đại học Sư phạm Kỹ thuật Nam Định cung cấp hướng dẫn từng bước từ lý thuyết đến ứng dụng. Nội dung bao gồm lựa chọn thuật toán phù hợp, quản lý khóa, xử lý lỗi, và tối ưu hiệu suất. Sinh viên được hướng dẫn triển khai hệ mật RSA, ElGamal, và ECC trong môi trường lập trình C++, Python. Phần này nhấn mạnh tầm quan trọng của quản lý khóa (key management) trong hệ thống an toàn thông tin. Giáo trình cũng đề cập đến các chuẩn công nghiệp như PKCS#1, X.509 cho việc triển khai thực tế.

3.1. Lựa chọn thuật toán và thông số kỹ thuật

Việc lựa chọn thuật toán phụ thuộc vào yêu cầu bảo mật, hiệu suất, và ứng dụng cụ thể. Giáo trình so sánh ưu nhược điểm giữa RSA, ECC, và hệ mật dựa trên dãy số. Nội dung hướng dẫn sinh viên tính toán kích thước khóa tối ưu (2048 bit cho RSA, 256 bit cho ECC). Phần này cung cấp bảng tham chiếu giữa mức bảo mật (bits) và thời gian tấn công ước tính. Sinh viên được hướng dẫn sử dụng thư viện mật mã như OpenSSL, Crypto++ cho triển khai thực tế. Nội dung cũng đề cập đến các tiêu chuẩn lựa chọn khóa theo NIST SP 800-57.

3.2. Quản lý khóa và triển khai hệ thống

Quản lý khóa là yếu tố quan trọng quyết định độ an toàn của hệ thống mật mã khóa công khai. Giáo trình trình bày các phương pháp lưu trữ khóa an toàn, phân phối khóa, và thu hồi khóa. Nội dung hướng dẫn sinh viên triển khai cơ sở hạ tầng khóa công khai (PKI) sử dụng giao thức X.509. Sinh viên được hướng dẫn xây dựng hệ thống chứng chỉ số, quản lý chu kỳ sống khóa. Phần này cũng đề cập đến các thách thức trong triển khai hệ thống thực tế như cân bằng giữa bảo mật và hiệu suất, xử lý khóa bị mất hoặc bị đánh cắp.

IV. Kết luận và ứng dụng giáo trình bảo mật thông tin

Giáo trình Bảo mật thông tin tại Đại học Sư phạm Kỹ thuật Nam Định cung cấp nền tảng vững chắc về mật mã khóa công khai, từ lý thuyết toán học đến triển khai thực tế. Nội dung hệ thống hóa kiến thức từ cơ bản đến nâng cao, phù hợp chương trình đào tạo kỹ sư an toàn thông tin. Kết luận nhấn mạnh tầm quan trọng của mật mã khóa công khai trong kỷ nguyên số, đặc biệt trong bảo vệ dữ liệu cá nhân, giao dịch điện tử, và hạ tầng quan trọng quốc gia. Giáo trình cũng đề xuất hướng nghiên cứu mở rộng như mật mã hậu lượng tử, blockchain. Sinh viên sau khi hoàn thành khóa học có thể áp dụng kiến thức vào phát triển ứng dụng bảo mật, nghiên cứu chuyên sâu, hoặc tham gia vào lực lượng lao động ngành an toàn thông tin.

4.1. Đánh giá hiệu quả đào tạo

Giáo trình đã được triển khai thử nghiệm tại Đại học Sư phạm Kỹ thuật Nam Định trong hai năm học, thu nhận phản hồi tích cực từ sinh viên và giảng viên. Kết quả khảo sát cho thấy 85% sinh viên nắm vững kiến thức sau khi hoàn thành khóa học. Phần thực hành được đánh giá cao khi sinh viên có thể triển khai hệ mật RSA trong môi trường lập trình. Giáo trình cũng nhận được sự quan tâm từ doanh nghiệp khi sinh viên tốt nghiệp có thể ngay lập tức áp dụng kiến thức vào công việc. Nội dung được cập nhật thường xuyên theo tiến bộ công nghệ, đảm bảo tính thời sự và thực tiễn.

4.2. Hướng phát triển tương lai

Tương lai của mật mã khóa công khai gắn liền với sự phát triển của công nghệ lượng tử. Giáo trình đề xuất bổ sung nội dung về mật mã hậu lượng tử, chuẩn bị cho sinh viên đối mặt với thách thức từ máy tính lượng tử. Nội dung cũng hướng đến ứng dụng trong lĩnh vực mới như Internet vạn vật (IoT), blockchain, và điện toán đám mây. Đại học Sư phạm Kỹ thuật Nam Định đang nghiên cứu xây dựng phòng thí nghiệm an toàn thông tin, cung cấp môi trường thực hành hiện đại. Giáo trình sẽ tiếp tục cập nhật để đáp ứng nhu cầu ngày càng cao về chuyên gia bảo mật thông tin trong kỷ nguyên số.

Trích đoạn nội dung tài liệu

Đặt vấn đề: Liệu có các phƣơng pháp tấn công RSA khác với phƣơng pháp phân tích n không ? Nếu thám mã tính đƣợc (n): Nếu đã biết n, (n) và n là tích của 2 số nguyên tố p và q thì có thể dễ dàng phân tích đƣợc n bằng cách giải 2 phƣơng trình sau để tìm hai số p và q chƣa biết: n=p*q (n)=(p-1)*(q-1) Nếu thay q=n/p vào phƣơng trình thứ 2 thì ta sẽ thu đƣợc phƣơng trình bậc 2 của biến chƣa biết p : p2- (n- (n) + 1)p + n=0 Hai nghiệm của phƣơng trình này là p và q là các nhân tử của n. Nhƣ vậy thám mã biết đƣợc (n) thì có thể phân tích đƣợc n và phá đƣợc hệ mật. Ví dụ: Giả sử thám mã đã biết đƣợc n = 84773093 và (n) = 4754668, thông tin này dẫn tới phƣơng trình p2 - 18426p + 84773093 = 0 Giải phƣơng trình này thu đƣợc hai nghiệm 9539 và 8887 là hai thừa số của n. Số mũ giải mã Một kết quả đã đƣợc chứng minh là một thuật toán bất kỳ để tính số mũ giải mã d đều có thể đƣợc dùng nhƣ một chƣơng trình con (hay một điều kiện) trong thuật toán 109 Giáo trình Bảo mật thông tin xác suất phân tích n.

Bởi vậy việc tính d không dễ hơn việc phân tích n. Tuy nhiên, có một điều không ngoài quy luật là vẫn có thể phá hệ mật mà không cần tính d. Kết quả này có ý nghĩa nhiều hơn về mặt lý thuyết. Nó cho thấy rằng nếu d bị lộ thì giá trị n cũng không còn khó phân tích nữa.Nếu điều này xẩy ra thì việc Bob chọn một số mũ mới cũng chẳng có ý nghĩa; Điều cần thiết là Bob phải chọn lại n.

Thuật toán mà ta sẽ mô tả là một thuật toán xác suất kiểu Las Vegas. Sau đây là định nghĩa của kiểu thuật toán này. Định nghĩa: Giả sử 0    1 là một số thực. Thuật toán Las Vegas là một thuật toán xác suất sao cho với một trƣờng hợp bất kỳ của bài toán i, thuật toán có thể không cho kết quả với một xác suất  nào đó (chẳng hạn thuật toán có thể kết thúc với thông báo “không trả lời”).

Tuy nhiên, nếu thuật toán cho lời giải thì lời giải này là đúng. Nhận xét: Thuật toán Las Vegas có thể không cho câu trả lời nhƣng một câu trả lời bất kỳ mà thuật toán cho là đều là câu trả lời đúng. Ngƣợc lại, thuật toán Monte - Carlo luôn luôn cho câu trả lời nhƣng câu trả lời này có thể sai. Nếu ta có một thuật toán Las Vegas để giải một bài toán thì đơn giản ta chỉ chạy lặp đi lặp lại thuật toán này cho tới khi nó tìm ra một câu trả lời.

Xác suất để thuật toán không trả lời sau m lần liên tiếp là m. Số lần chạy trung bình để thu đƣợc câu trả lời thực tế là 1/. Giả sử A là một thuật toán giả định tính số mũ giải mã d từ e. Ta sẽ mô tả một thuật toán Las Vegas dùng A nhƣ một chƣơng trình giả định (oracle) con.

Thuật toán sẽ phân tích n với xác suất tối thiểu là 1/2. Bởi vậy nếu thuật toán chạy m lần thì n sẽ đƣợc phân tích với xác suất tối thiểu là 1-1/2m. Thuật toán đƣợc xây dựng trên cơ sở một số nguyên tố nhất định liên quan tới các căn bậc 2 của một theo modulo n, trong đó n = p*q là tích của hai số nguyên tố lẻ phân biệt ta biết rằng phƣơng trình đồng dƣ x2  1(mod p) có hai nghiệm theo modulo p là x = 1 mod p. Tƣơng tự, phƣơng trình đồng dƣ x2  1(mod q) cũng có hai nghiệm là x = 1 mod q.

Vì x2  1 (mod n) khi và chỉ khi x2  1 (mod p) và x2  1 (mod q) nên suy ra x2  1 (mod n) khi và chỉ khi x = 1 mod p và x = 1 mod q. Bởi vậy có 4 căn bậc 2 của 1 theo modulo n và các căn này có thể tìm đƣợc thông qua định lý phần dƣ China. Hai trong các nghiệm này là x = 1 mod n; chúng đƣợc gọi là các căn bậc hai tầm thƣờng và là các giá trị đối của nhau theo modulo n. 110 Giáo trình Bảo mật thông tin Ví dụ: Giả sử n = 403 = 13  11 Bốn căn bậc hai của một theo modulo 403 là 1, 92, 311 và 402.

Căn bậc hai 92 nhận đƣợc bằng cách giải hệ x  1 (mod 13) , x  -1 (mod 31) theo định lý phần dƣ China. Nếu tìm đƣợc nghiệm không tầm thƣờng này, nghiệm không tầm thƣờng kia phải là 403 – 92 = 311. Đó là nghiệm của hệ x  -1(mod 13), x  1 (mod 31). Giả sử x là căn bậc hai không tầm thƣờng của 1 modulo n.

Khi đó ta có n(x-1)(x+1) nhƣng n không là ƣớc của một nhân tử nào ở vế phải. Điều đó kéo theo gcd(x+1, n) = p hoặc q(và tƣơng tự gcd(x-1, n) = p hoặc q). Tất nhiên có thể tính ƢCLN bằng thuật toán Euclide mà không cần phải biết phân tích nhân tử của n. Bởi vậy, hiểu biết về căn bậc hai không tầm thƣờng của 1 mod n sẽ làm cho việc phân tích n chỉ cần thực hiện trong thời gian đa thức.

Yếu tố quan trọng này là cơ sở của nhiều kết quả quan trong mật mã. Trong ví dụ trên, gcd(93, 403) = 31 và gcd(312, 403) = 13 Dƣới đây là thuật toán phân tích n bằng cách tìm một căn bậc hai không tầm thƣờng của 1 modulo n (A thực hiện tính số mũ giải mã d theo số mũ mã e). Chọn w ngẫu nhiên sao cho 1 w  n-1 2. Nếu 1 < x < n thì kết thúc ( thành công x = p hoặc x = q) 4.

if v0  -1 (mod n) then kết thúc (không thành công) Else Tính x = gcd(v0+1, n) (thành công x=p hoặc x=q) Ví dụ: Giả sử n = 89855713, e = 34986517 và d = 82330933 và giá trị ngẫu nhiên w = 5. 360059073378795 Trong bƣớc 6, v = 85877701 còn ở bƣớc 10 v=1 Trong bƣớc 12 ta tính gcd(85877702, n) = 9103 Đây là một thừa số của n; thừa số kia là n/9103 = 9871. 111 Giáo trình Bảo mật thông tin Bây giờ sẽ tiến hành phân tích thuật toán. Trƣớc tiên, nhận thấy rằng nếu chọn đƣợc w là bội của p hoặc q thì có thể ngay lập tức phân tích đƣợc n.

Điều này đƣợc biểu thị ở bƣớc 2. Nếu w nguyên tố cùng nhau với n thì ta sẽ tính wr, w2r, w4r,. bằng cách bình phƣơng liên tiếp cho tới khi w2t  1 (mod n) với giá trị t nào đó.r  0 (mod (n)) nên ta có  1 mod n. Bởi vậy, vòng lặp while sẽ kết thúc sau nhiều nhất là s bƣớc lặp.

Kết thúc vòng lặp, ta tìm đƣợc một giá trị v0 sao cho v02  1 (mod n) nhƣng v0  1 (mod n). Nhiệm vụ chính còn lại bây giờ là phải chứng minh rằng, thuật toán thành công với xác suất là . Có hai cách mà theo đó thuật toán có thể không thành công khi phân tích n : 1.  -1 (mod n) với giá trị t nào đó 0 ≤ t ≤ s-t (bƣớc 11) Ta có n+1 phƣơng trình đồng dƣ để xem xét.

Nếu giá trị ngẫu nhiên w là một nghiệm của ít nhất một trong các đồng dƣ thức này thì phép lựa chọn w này là “tồi” và thuật toán sẽ không thành công. Bởi vậy, ta sẽ chuyển sang tính số các nghiệm của mỗi đồng dƣ thức này. Trƣớc tiên xét đồng dƣ thức wr  1 (modn). Phƣơng pháp phân tích một đồng dƣ thức giống nhƣ cách xem xét một cách riêng lẻ các nghiệm theo modulo q.

Sau đó kết hợp chúng nhờ định lý phần dƣ China. Nhƣ vậy, trƣớc hết ta phải xét wr  1 (mod n) .Vì p là một số nguyên tố nên Z*p là một nhóm cyclic. Giả sử g là một phần tử nguyên thuỷ theo modulo p. Ta có thể viết w = gu với số nguyên duy nhất u nào đó, 0  u  p-2.

Khi đó ta có : wr  1(mod p) gur  1 (mod p) (p-1) ur Giả sử biểu diễn p-1 = 2i p1, trong đó p1 là một số lẻ và q -1 = 2jq1, q1 là một số lẻ. Vì (n) = (p-1)(q-1) (ab-1) = 2sr nên ta có 2i+jp1q12sr Bởi vậy: i+j s và p1q1 r 112 Giáo trình Bảo mật thông tin Bây giờ điều kiện p-1ur sẽ trở thành 2ip1 ur. Vì p1r và r lẻ nên điều kiện cần và đủ là 2iu. 2i, 0 k  p1-1 và số các nghiệm của dƣ thức wr1 (mod p) sẽ là p1.

Bằng lập luận tƣơng tự, ta thấy đồng dƣ thức wr  1 (mod q) có đúng q1 nghiệm. Có thể kết hợp nghiệm bất kỳ theo modulo p với nghiệm bất kỳ theo modulo q để thu đƣợc một nghiệm duy nhất theo modulo n nhờ định lý phần dƣ China. Do vậy số các nghiệm của đồng dƣ thức wr 1 (mod n ) sẽ là p1q1. Tiếp theo, xét đồng dƣ thức  1(mod n) với giá trị t cố định (trong đó : 0  t  s-1).

Trƣớc tiên lại xét đồng dƣ thức theo modulo p rồi sau đó xét theo modulo q. Đầu tiên ta xét w 2 r  1mod p . Nếu viết w = gu nhƣ ở phần trên ta nhận t đƣợc: g u 2 r  1mod p  t Vì g(p-1)/2 -1(mod p) nên ta có u2tr (p-1)/2(mod p-1) (p-1) │ (u2tr-(p-1)/2) 2(p-1)│ (u2t+1r-(p-1)) Vì p-1=2ip1 nên ta nhận đƣợc 2i+2 p1 │ (u 2t+1r-2ip1) Loại bỏ thừa số chung ta có Xét thấy nếu t  i thì có thể là không có nghiệm do 2i+1 │ 2t+1 nhƣng 2i+1 │ 2i  u2 t  1 r  2 i1 |   2 i   p1  Mặt khác nếu t  i -1 thì u sẽ là một nghiệm khi và chỉ khi u là bội lẻ của 2i-t-1. Bởi vậy, số các nghiệm trong trƣờng hợp này là p 1 1 t i t 1  =2 p1 2 2 Tƣơng tự, đồng dƣ thức w 2 r  1 (mod q) sẽ : i - Không có nghiệm nếu t  j - Có 2tq1 nghiệm nếu t  j-1 Từ định lý phần dƣ China ta sẽ thấy rằng số các nghiệm của w 2 r  1mod n  là i - 0 nếu t  min{i, j} 113 Giáo trình Bảo mật thông tin - 22t p1q1 nếu t  min{i, j )  1 t có thể nằm trong dải từ 0 tới s-1.