Mật mã RSA - một ứng dụng của số nguyên tố và lý thuyết đồng dư

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

Thêm vào BST

Báo xấu

4
lượt xem 1
download

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

Bài viết "Mật mã RSA - một ứng dụng của số nguyên tố và lý thuyết đồng dư" trình bày ứng dụng của số nguyên tố và lý thuyết đồng dư trong mật mã RSA.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mật mã RSA - một ứng dụng của số nguyên tố và lý thuyết đồng dư

MẬT MÃ RSA – MỘT ỨNG DỤNG CỦA SỐ NGUYÊN TỐ VÀ LÝ THUYẾT ĐỒNG DƯ Nguyễn Thị Khánh Hòa1 1. Khoa Sư Phạm, Trường Đại học Thủ Dầu Một TÓM TẮT Bài viết trình bày ứng dụng của số nguyên tố và lý thuyết đồng dư trong mật mã RSA. Từ khóa: mật mã RSA; ứng dụng của số nguyên tố; ứng dụng của lý thuyết đồng dư. 1. GIỚI THIỆU “Học toán để làm gì?” hay "Toán học có áp dụng được vào thực tiễn cuộc sống không?" - Đây là những câu hỏi vốn gây nhức nhối cho cả học sinh, sinh viên và phụ huynh Việt Nam trong những năm gần đây. Bên cạnh quan điểm cho rằng học Toán là cần thiết, cũng có không ít người có suy nghĩ ngược lại. Mục đích bài viết này là cung cấp một ví dụ áp dụng toán học vào thực tiễn đời sống. Nó giúp cho những người dạy toán có thêm ví dụ để tạo hứng thú cho người học. Đồng thời có thể giúp các bạn học sinh, sinh viên thấy được những ứng dụng rất hữu ích của toán học trong cuộc sống. Mật mã học là một lĩnh vực liên quan đến các kỹ thuật ngôn ngữ và toán học để đảm bảo an toàn thông tin, cụ thể là trong thông tin liên lạc. Trong lịch sử, mật mã học gắn liền với quá trình mã hóa; nghĩa là nó gắn với các cách thức để chuyển đổi thông tin, làm cho thông tin trở thành dạng không thể đọc được nếu như không có các kiến thức bí mật. Quá trình mã hóa được sử dụng chủ yếu để đảm bảo tính bí mật của các thông tin quan trọng, chẳng hạn trong công tác tình báo, quân sự hay ngoại giao cũng như các bí mật về kinh tế, thương mại. Trong những năm gần đây, lĩnh vực hoạt động của mật mã hoá đã được mở rộng: mật mã hóa hiện đại cung cấp cơ chế cho nhiều hoạt động hơn là chỉ duy nhất việc giữ bí mật và có một loạt các ứng dụng như: chứng thực khoá công khai, chữ ký số, bầu cử điện tử hay tiền điện tử. Trong mật mã học, RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên được sử dụng để tạo ra chữ ký điện tử. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học. Hiện nay RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. Nguyên lý của mật mã RSA chính là dựa trên các kiến thức cơ bản về số nguyên tố và lý thuyết đồng dư. Hay nói cách khác, mật mã RSA chính là một ứng dụng đơn giản nhưng cực kỳ hữu ích của số nguyên tố và lý thuyết đồng dư. 2. NỘI DUNG Phần lý thuyết cơ bản về số nguyên tố cùng nhau (mục 2.1), số nguyên tố (mục 2.2) và lý thuyết đồng dư (mục 2.3) được trình bày theo (Nguyễn Tiến Tài, 1999). 2.1. Số nguyên tố cùng nhau 2.1.1. Định nghĩa 1: Cho hai số nguyên 𝑎, 𝑏 (𝑏 ≠ 0). Nếu có một số nguyên 𝑞 sao cho 𝑎 = 𝑏. 𝑞 thì ta nói 𝑎 chia hết cho 𝑏. Khi đó ta cũng nói 𝑏 là ước của 𝑎. Ví dụ: 3 là ước của 6 vì 6 = 2.3. 2.1.2. Định nghĩa 2: Các số nguyên 𝑎1 , 𝑎2 , … , 𝑎 𝑛 được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Ví dụ: 9 và 16 là hai số nguyên tố cùng nhau vì 𝑈𝐶𝐿𝑁(9; 16) = 1. 286
2.2. Số nguyên tố 2.2.1. Định nghĩa: Số tự nhiên lớn hơn 1 không có ước nào khác ngoài 1 và chính nó được gọi là số nguyên tố. Ví dụ: 2, 3, 5, 7, 11, 13, … là những số nguyên tố. Số 4 không phải số nguyên tố vì nó có ước (khác 1 và 4) là 2. 2.2.2. Phân tích một số tự nhiên thành tích những thừa số nguyên tố: Định lý: Mỗi số tự nhiên lớn hơn 1 đều phân tích được thành tích những thừa số nguyên tố và sự phân tích đó là duy nhất nếu không kể đến thứ tự của các thừa số. Ví dụ: Ta có sự phân tích thành tích của các thừa số nguyên tố của số 12 và 143 như sau: 12 = 22 × 3 và 143 = 11 × 13 2.3. Lý thuyết đồng dư 2.3.1. Định nghĩa đồng dư thức: Cho 𝒎 là một số nguyên dương. Ta nói hai số nguyên 𝒂 và 𝒃 đồng dư với nhau theo môđun 𝒎 nếu trong các phép chia 𝒂 và 𝒃 cho 𝒎 ta được cùng một số dư, khi đó ta viết 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒎) Hệ thức trên được gọi là đồng dư thức. Ví dụ: 𝟓 ≡ 𝟏 (𝒎𝒐𝒅 𝟐); 𝟏𝟐 ≡ 𝟐 (𝒎𝒐𝒅 𝟓). 2.3.2. Một số tính chất của đồng dư thức Tính chất 1: 𝒂 ≡ 𝒃(𝒎𝒐𝒅𝒎) ⟺ 𝒂 = 𝒃 + 𝒎𝒕, 𝒕 ∈ ℤ. Nói thêm, nếu 𝟎 ≤ 𝒃 < 𝒎 thì 𝒃 chính là số dư khi chia 𝒂 cho 𝒎. Tính chất 2: 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒎), 𝒃 ≡ 𝒄 (𝒎𝒐𝒅𝒎) ⟹ 𝒂 ≡ 𝒄 (𝒎𝒐𝒅𝒎). Tính chất 3: 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒎) ⟹ 𝒂 ± 𝒄 ≡ 𝒃 ± 𝒄 (𝒎𝒐𝒅𝒎), ∀𝒄 ∈ ℤ. Tính chất 4: 𝒂 + 𝒄 ≡ 𝒃 (𝒎𝒐𝒅𝒎) ⟹ 𝒂 ≡ 𝒃 − 𝒄 (𝒎𝒐𝒅𝒎), ∀𝒄 ∈ ℤ. Tính chất 5: 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒎) ⟹ 𝒂 + 𝒌𝒎 ≡ 𝒃 (𝒎𝒐𝒅𝒎), ∀𝒌 ∈ ℤ. Tính chất 6: 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒎) ⟹ 𝒂𝒄 ≡ 𝒃𝒄 (𝒎𝒐𝒅𝒎), ∀𝒄 ∈ ℤ. Tính chất 7: 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒎) ⟹ 𝒂 𝒏 ≡ 𝒃 𝒏 (𝒎𝒐𝒅𝒎), ∀𝒏 ∈ ℤ, 𝒏 > 𝟎. 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒑) Tính chất 8: { 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒒) ⟹ 𝒂 ≡ 𝒃 (𝒎𝒐𝒅𝒎) với 𝒎 = 𝒑. 𝒒 𝑼𝑪𝑳𝑵(𝒑, 𝒒) = 𝟏 Ví dụ: Tìm các số nguyên dương 𝑥 nhỏ nhất thoả 727 ≡ 𝑥 (𝑚𝑜𝑑143) Giải: Ta có 722 = 143 × 36 + 36 ⟹ 722 ≡ 36 (𝑚𝑜𝑑143) 723 = 143 × 2610 + 18 ⟹ 723 ≡ 18 (𝑚𝑜𝑑143) Do đó 727 = 722 × 722 × 723 ≡ 362 × 18 (𝑚𝑜𝑑143) Mà 362 × 18 = 143.163 + 19 ⟹ 362 × 18 ≡ 19 (𝑚𝑜𝑑143) Suy ra 727 ≡ 19 (𝑚𝑜𝑑143) Vậy số nguyên dương nhỏ nhất cần tìm là 𝑥 = 19. 2.3.3. Định lý Euler: Cho 𝒎 là một số tự nhiên khác 𝟎 và 𝒂 là một số nguyên nguyên tố với 𝒎. Khi đó ta có 𝒂 𝝋(𝒎) ≡ 𝟏(𝒎𝒐𝒅𝒎) 𝜶 𝜶 𝜶 Với 𝒎 = 𝒑 𝟏 𝟏 𝒑 𝟐 𝟐 … 𝒑 𝒌 𝒌 là sự phân tích 𝒎 thành tích của các thừa số nguyên tố. 𝟏 𝟏 𝟏 và 𝝋(𝒎) = 𝒎. (𝟏 − ) . (𝟏 − ) … (𝟏 − ). 𝒑𝟏 𝒑𝟐 𝒑𝒌 287
𝟏 Nhận xét: i) Nếu 𝒑 là số nguyên tố thì 𝝋(𝒑) = 𝒑 (𝟏 − ) = 𝒑 − 𝟏. 𝒑 ii) Nếu 𝒎 = 𝒑. 𝒒 (𝒑, 𝒒 là số nguyên tố) thì 𝝋(𝒎) = (𝒑 − 𝟏). (𝒒 − 𝟏) 2.3.4. Phương trình đồng dư bậc nhất một ẩn Trong bài viết này ta chỉ xét phương trình có dạng 𝒂𝒙 ≡ 𝒃 (𝒎𝒐𝒅𝒎) với 𝒂 < 𝒎 và 𝑼𝑪𝑳𝑵(𝒂, 𝒎) = 𝟏. Khi đó nghiệm của phương trình này sẽ là: 𝑏 ➢ 𝑥≡ (𝑚𝑜𝑑𝑚) (Nếu 𝑎 là ước của 𝑏). 𝑎 𝑏+𝑘𝑚 ➢ 𝑥≡ (𝑚𝑜𝑑𝑚) với 1 ≤ 𝑘 ≤ 𝑎 − 1 (Nếu 𝑎 không là ước của 𝑏). 𝑎 Ví dụ: Tìm các số nguyên dương 𝑑 nhỏ nhất thoả mãn 7𝑑 ≡ 1(𝑚𝑜𝑑120). Giải: Phương trình đã cho có nghiệm là 1 + 6.120 𝑑≡ (𝑚𝑜𝑑120) ⟹ 𝑑 ≡ 103 (𝑚𝑜𝑑120) ⟹ 𝑑 = 103 + 120𝑘 (𝑘 ∈ ℤ) 7 Vậy số nguyên dương nhỏ nhất cần tìm là 𝑑 = 103. 2.4. Thuật toán mật mã khoá công khai RSA 2.4.1. Mô tả sơ lược Thuật toán RSA được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT). Tên của thuật toán lấy từ 3 chữ cái đầu của tên 3 tác giả. Ta có thể mô phỏng trực quan mật mã khoá công khai RSA như sau: B muốn gửi cho A một thông tin mật và B muốn chỉ mình A có thể đọc được. Để làm được điều này, A gửi cho B một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. B nhận chiếc hộp, cho vào đó một tờ giấy viết thư bình thường và khóa lại (như loại khoá thông thường chỉ cần sập chốt lại. Sau khi sập chốt khóa, ngay cả B cũng không thể mở lại được-không đọc lại hay sửa thông tin trong thư được nữa). Sau đó B gửi chiếc hộp lại cho A. A mở hộp với chìa khóa của mình và đọc thông tin trong thư. Trong ví dụ này, chiếc hộp với khóa mở đóng vai trò khóa công khai, chiếc chìa khóa chính là khóa bí mật. Như vậy quá trình vận hành của mật mã RSA sẽ gồm các bước chính đó là: - A tạo khoá công khai (là chiếc hộp ở ví dụ trên) và khoá bí mật (chiếc chìa khoá của hộp mà A giữ lại, không gửi đi ở ví dụ trên). Sau đó A công bố khoá công khai (gửi cho B). Quá trình này gọi là tạo khoá. - B sẽ mã hoá thông tin muốn gửi cho A (bằng cách sử dụng khoá công khai mà A đã cung cấp). Quá trình này gọi là mã hoá. - Sau khi nhận được thông tin đã mã hoá từ B, A sẽ dùng khoá bí mật để giải mã đoạn thông tin mà B đã gửi. Quá trình này gọi là giải mã. Tiếp theo, chúng ta sẽ đi sâu vào ba quá trình trên để thấy rõ được mật mã khoá công khai RSA chính là một ứng dụng của số nguyên tố và lý thuyết đồng dư. 2.4.2. Tạo khoá - Chọn hai số nguyên tố 𝒑, 𝒒 lớn. - Tính 𝒏 = 𝒑. 𝒒; 𝒎 = (𝒑 − 𝟏). (𝒒 − 𝟏). - Chọn số tự nhiên 𝒆 sao cho 𝒆 và 𝒎 nguyên tố cùng nhau. - Tìm 𝒅 sao cho 𝒅. 𝒆 ≡ 𝟏(𝒎𝒐𝒅𝒎) (nghĩa là 𝒅. 𝒆 khi chia cho 𝒎 sẽ dư 1). Sau đó A gửi khoá công khai là hai số 𝒏, 𝒆 và giữ khoá bí mật là 𝒅. 2.4.3. Mã hoá 288
- Chia đoạn văn bản X cần gửi thành nhiều phần nhỏ, mỗi phần biểu diễn bởi một số 𝒙 thoả mãn 𝟎 ≤ 𝒙 < 𝒏. (Trong phạm vi của bài viết, ta không đi sâu vào bước chuyển đổi văn bản này, nhằm làm cho bài viết ngắn gọn và chỉ tập trung vào ứng dụng của số nguyên tố và lý thuyết đồng dư trong mật mã RSA). - Giả sử 𝒙 là thông tin bí mật cần gửi, B tìm 𝒚 sao cho 𝒚 ≡ 𝒙 𝒆 (𝒎𝒐𝒅𝒏). Sau đó B sẽ gửi 𝒚 cho A. 2.4.4. Giải mã - A nhận 𝒚 từ B rồi dùng khoá bí mật 𝒅 để tìm 𝟎 ≤ 𝒙 < 𝒏 thoả 𝒙 ≡ 𝒚 𝒅 (𝒎𝒐𝒅𝒏). - Từ 𝒙, A sẽ tìm lại văn bản X theo phương pháp chuyển đoạn văn bản mà A và B đã thoả thuận từ trước. 2.4.5. Ví dụ Sau đây sẽ là một ví dụ với những số nguyên tố nhỏ cụ thể để dễ hình dung về thuật toán RSA. Còn trong thực tế người ta sử dụng những số rất lớn. Giả sử B muốn gửi từ “Hi” cho A. Lúc này B phải chuyển đổi đoạn văn bản “Hi” thành số. Hiện nay có rất nhiều phương pháp giúp chuyển đổi đoạn văn bản thành số. Để cho bài viết ngắn gọn và chỉ tập trung vào ứng dụng của số nguyên tố và lý thuyết đồng dư trong mật mã RSA, tôi chỉ chọn cách dùng Bảng mã ASCII (tên đầy đủ là American Standard Code for Information Interchange - Chuẩn mã trao đổi thông tin Hoa Kỳ) mà không đi sâu vào các cách chuyển đổi văn bản khác. Theo bảng mã ASCII, chữ “H” sẽ ứng với số 72 và chữ “i” ứng với số 105. A B Tạo - Chọn 𝑝 = 11, 𝑞 = 13. khoá - Tính 𝑛 = 11.13 = 143; 𝑚 = 10.12 = 120. - Chọn 𝑒 = 7 nguyên tố cùng nhau với 120. - Chọn 𝑑 = 103 để 7𝑑 ≡ 1(𝑚𝑜𝑑120). Khoá công khai là 𝑛 = 143, 𝑒 = 7 (gửi đi). Khoá bí mật 𝑑 = 103 (giữ lại). Mã - Muốn gửi 𝑥1 = 72, 𝑥2 = 105 < 143 cho A. hoá - B mã hoá 𝑥1 = 72, 𝑥2 = 105 thành 𝑦1 = 19, 𝑦2 = 118. từ khoá công khai 𝑛 = 143, 𝑒 = 7 và điều kiện 𝑦1 ≡ 727 (𝑚𝑜𝑑143); 𝑦2 ≡ 7 105 (𝑚𝑜𝑑143). - Gửi "19 118" cho A. Giải - Nhận được 𝑦1 = 19, 𝑦2 = 118 từ B. mã - Từ 𝑑 = 103 và 𝑥1 ≡ 19103 (𝑚𝑜𝑑143); 𝑥2 ≡ 103 (𝑚𝑜𝑑143) 118 A tính được 𝑥1 = 72, 𝑥2 = 105. - Dựa vào Bảng mã ASCII, A sẽ biết được thông điệp B đã gửi là “Hi”. Có một vấn đề trong ví dụ trên cần được làm sáng tỏ đó là: Có rất nhiều giá trị 𝒚 thoả điều kiện 𝒚 ≡ 𝟕𝟐 𝟕 (𝒎𝒐𝒅𝟏𝟒𝟑). Tuy nhiên ta sẽ luôn nhận được một giá trị 𝒙 duy nhất thoả 𝒙 ≡ 𝒚 𝟏𝟎𝟑 (𝒎𝒐𝒅𝟏𝟒𝟑) và 𝒙 < 𝟏𝟒𝟑. Điều này sẽ được chứng minh trong mục 2.4.6. Việc chứng minh này sẽ cho ta thấy rõ ứng dụng của lý thuyết đồng dư trong mật mã RSA. 2.4.6. Tính đúng đắn của thuật toán (Kết quả dưới đây được chứng minh dựa vào các tính chất của mục 2.3.2 và định lý Euler). Giả sử 𝟎 ≤ 𝒙, 𝒙′ < 𝒏 , 𝒚 ≡ 𝒙 𝒆 (𝒎𝒐𝒅𝒏) 𝐯à 𝒙′ ≡ 𝒚 𝒅 (𝒎𝒐𝒅𝒏). Ta sẽ chứng minh 𝒙′ = 𝒙. Từ hai đồng dư thức trên ta suy ra 𝒙′ ≡ 𝒙 𝒅𝒆 (𝒎𝒐𝒅𝒏) (1). Nếu ta chứng minh được 𝒙 𝒅𝒆 ≡ 𝒙(𝒎𝒐𝒅𝒏) thì từ (1) ta suy ra 𝒙′ ≡ 𝒙(𝒎𝒐𝒅𝒏). Mà 𝟎 ≤ 𝒙, 𝒙′ < 𝒏 nên ta suy ra 𝒙′ = 𝒙. Ta được điều phải chứng minh. 289
Phần còn lại là dành để chứng minh 𝒙 𝒅𝒆 ≡ 𝒙(𝒎𝒐𝒅𝒏). * Trường hợp 1: Nếu 𝑼𝑪𝑳𝑵(𝒙, 𝒏) = 𝟏 thì theo định lý Euler ta có 𝒙 𝝋(𝒏) ≡ 𝟏(𝒎𝒐𝒅𝒏) Mà 𝝋(𝒏) = (𝒑 − 𝟏). (𝒒 − 𝟏) = 𝒎 nên 𝒙 𝒎 ≡ 𝟏(𝒎𝒐𝒅𝒏) (2). Mặt khác vì 𝒅𝒆 ≡ 𝟏(𝒎𝒐𝒅𝒎) nên 𝒅𝒆 = 𝟏 + 𝒌𝒎 với 𝒌 ∈ ℕ. Do đó từ (2) suy ra 𝒙 𝒌𝒎 ≡ 𝟏(𝒎𝒐𝒅𝒏) ⟹ 𝒙 𝟏+𝒌𝒎 ≡ 𝒙(𝒎𝒐𝒅𝒏) ⟹ 𝒙 𝒅𝒆 ≡ 𝒙(𝒎𝒐𝒅𝒏). * Trường hợp 2: Nếu 𝑼𝑪𝑳𝑵(𝒙, 𝒏) ≠ 𝟏 thì vì 𝒏 = 𝒑. 𝒒; 𝟎 ≤ 𝒙 < 𝒏 nên 𝑼𝑪𝑳𝑵(𝒙, 𝒏) = 𝒑 hoặc 𝑼𝑪𝑳𝑵(𝒙, 𝒏) = 𝒒. Không mất tính tổng quát, giả sử 𝑼𝑪𝑳𝑵(𝒙, 𝒏) = 𝒑. Khi đó 𝒙 ≡ 𝟎(𝒎𝒐𝒅𝒑) ⟹ 𝒙 𝒅𝒆 ≡ 𝟎(𝒎𝒐𝒅𝒑) ⟹ 𝒙 𝒅𝒆 ≡ 𝒙(𝒎𝒐𝒅𝒑) (3) Mặt khác vì 𝒅𝒆 ≡ 𝟏(𝒎𝒐𝒅𝒎) nên 𝒅𝒆 = 𝟏 + 𝒌𝒎 với 𝒌 ∈ ℕ. Và vì 𝑼𝑪𝑳𝑵(𝒙, 𝒒) = 𝟏 nên theo định lý Euler ta có 𝒙 𝝋(𝒒) ≡ 𝟏(𝒎𝒐𝒅𝒒) ⟹ 𝒙 𝒒−𝟏 ≡ 𝟏(𝒎𝒐𝒅𝒒) ⟹ 𝒙(𝒑−𝟏)(𝒒−𝟏) ≡ 𝟏(𝒎𝒐𝒅𝒒) ⟹ 𝒙 𝒎 ≡ 𝟏(𝒎𝒐𝒅𝒒) ⟹ 𝒙 𝒌𝒎 ≡ 𝟏(𝒎𝒐𝒅𝒒) ⟹ 𝒙 𝟏+𝒌𝒎 ≡ 𝒙(𝒎𝒐𝒅𝒒) ⟹ 𝒙 𝒅𝒆 ≡ 𝒙(𝒎𝒐𝒅𝒒) (4) Từ (3) và (4) suy ra 𝒙 𝒅𝒆 ≡ 𝒙(𝒎𝒐𝒅𝒑𝒒) ⟹ 𝒙 𝒅𝒆 ≡ 𝒙(𝒎𝒐𝒅𝒏). 2.4.7. Độ an toàn của mật mã khoá công khai RSA Nếu kẻ tấn công tìm được 2 số nguyên tố 𝑝 và 𝑞 sao cho 𝑛 = 𝑝𝑞 thì có thể dễ dàng tìm được giá trị (𝑝 − 1)(𝑞 − 1) và qua đó xác định được khoá bí mật 𝑑 từ 𝑒. Tuy nhiên độ an toàn của mật mã khoá công khai RSA tính đến thời điểm hiện tại vẫn được đảm bảo bởi vì bài toán phân tích một số nguyên lớn thành tích của các thừa số nguyên tố nói chung và bài toán phân tích một số nguyên lớn thành tích của hai thừa số nguyên tố nói riêng đã và vẫn đang là vấn đề lớn của toán học. Tính đến tháng 2 năm 2020 số lớn nhất được phân tích bằng một thuật toán thông thường (số này được ký hiệu là RSA-250), một số có 250 chữ số (829 bit) và là tích của hai số nguyên tố lớn. Công trình tính toán này được thực hiện bởi hàng chục nghìn máy tính trên toàn thế giới chạy cùng lúc với nhau và được hoàn thành sau hơn ba tháng (Zimmermann & Paul, 2020). Mặc dù việc phân tích một số thành tích của các thừa số nguyên tố, đặc biệt là bài toán phân tích những số lớn thành tích của 2 số nguyên tố là một bài toán tốn rất nhiều thời gian và công sức để giải quyết, nhưng với sự phát triển không ngừng của ngành khoa học máy tính, các nhà khoa học trên thế giới vẫn quyết định sẽ khuyến cáo người dùng về cách chọn các số nguyên tố p, q, e và độ dài của n như sau: - Các số p, q nên là các số nguyên tố lớn, xa nhau và nên chọn ngẫu nhiên bằng các thuật toán. - Số e và d không nên quá lớn để tiết kiệm thời gian mã hoá và giải mã, nhưng cũng không nên chọn số quá nhỏ vì sẽ rất dễ bị bẻ khoá. Giá trị thường dùng hiện nay của e là một số có 5 chữ số. - Độ dài của n (tính theo bít) cũng được khuyến cáo tăng dần theo các năm. Chẳng hạn, theo khuyến cáo của NIST (Viện tiêu chuẩn và Công nghệ Mỹ) thì từ 2019 đến 2030, độ dài của n nên từ 1024 đến 15360 bít; theo khuyến cáo của ECRYPT-CSA (cơ quan đưa ra các khuyến nghị về sử dụng an toàn mật mã của Liên minh Châu Âu) thì từ 2022 đến 2068, độ dài của n nên từ 3072 đến 15360 bít (Hoàng Văn Thức và nnk.,2023). 3. KẾT LUẬN Trên đây tôi đã trình bày sơ lược về mật mã khoá công khai RSA với mục đích làm rõ ứng dụng của số nguyên tố và lý thuyết đồng dư trong thuật toán này. Qua bài viết, chúng ta có thể thấy rằng chỉ dựa trên những kiến thức đơn giản và cơ bản của số nguyên tố và lý thuyết đồng dư nhưng đã tạo nên một thuật toán về mã hoá rất an toàn. Thuật toán này đang và sẽ tiếp tục được sử dụng 290
rộng rãi trong các thiết bị cũng như các ứng dụng về đảm bảo an toàn, thương mại điện tử, điển hình như chữ ký số RSA. Tuy đã có nhiều cố gắng song không tránh khỏi bài viết sẽ còn thiếu sót. Rất mong sự thông cảm của quý đồng nghiệp và mong nhận được nhiều ý kiến đóng góp để bài viết được hoàn thiện. TÀI LIỆU THAM KHẢO 1. Nguyễn Tiến Tài (chủ biên) (1999). Số học. Nhà xuất bản Giáo dục. 2. TS.Hoàng Văn Thức và TS. Đinh Quốc Tiến (Ban cơ yếu chính phủ) (ngày 3 tháng 3 năm 2023). Xem xét mức an toàn đối với độ dài khoá RSA. An toàn thông tin. https://m.antoanthongtin.vn/mat-ma-dan- su/xem-xet-muc-an-toan-doi-voi-do-dai-khoa-rsa-108774 3. Zimmermann & Paul (ngày 28 tháng 2 năm 2020), Factorization of RSA-250. https://web.archive.org/web/20200228234716/https:/lists.gforge.inria.fr/pipermail/cado-nfs- discuss/2020-February/001166.html 291