Tài liệu Xây dựng hệ mã rsa trên vành end (zn x znm)

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH Lê Thị Kim Nga XÂY DỰNG HỆ MÃ RSA TRÊN VÀNH 𝑬𝒏𝒅(ℤ𝒏 × ℤ𝒏𝒎 ) LUẬN VĂN THẠC SĨ MÁY TÍNH Thành phố Hồ Chí Minh – 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH Lê Thị Kim Nga XÂY DỰNG HỆ MÃ RSA TRÊN VÀNH 𝑬𝒏𝒅(ℤ𝒏 × ℤ𝒏𝒎 ) Chuyên ngành: Khoa học máy tính Mã số: 8480101 LUẬN VĂN THẠC SĨ MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. TS. TRẦN ĐÌNH LONG 2. PGS.TS. NGUYỄN ĐÌNH THÚC Thành phố Hồ Chí Minh - 2018 LỜI CAM ĐOAN Tôi xin khẳng định tất cả các kết quả được trình bày trong luận văn là kết quả nghiên cứu của riêng tôi dưới sự hướng dẫn của TS. Trần Đình Long và PGS. TS Nguyễn Đình Thúc. Nếu có điều gì không trung thực, tôi xin chịu hoàn toàn trách nhiệm. Học viên Lê Thị Kim Nga LỜI CẢM ƠN Đầu tiên em xin chân thành cảm ơn các thầy cô ở Phòng Sau đại học và Khoa Công nghệ Thông tin, những người đã hết lòng hỗ trợ, hướng dẫn và giảng dạy em trong suốt thời gian học Cao học tại trường. Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến thầy Trần Đình Long và thầy Nguyễn Đình Thúc đã tận tình hướng dẫn em trong suốt thời gian thực hiện luận văn này. Nếu không có những lời hướng dẫn, dạy bảo và sự giúp đỡ của hai thầy thì em rất khó có thể hoàn thành được luận văn. Em cũng xin gửi lời cám ơn đến gia đình, bạn bè những người luôn bên cạnh, ủng hộ và giúp đỡ em trong quá trình học tập và làm việc. Mặc dù đã cố gắng, song chắc chắn luận văn không tránh khỏi những thiếu sót. Em rất mong nhận được sự thông cảm và chỉ bảo tận tình của quý thầy cô và các bạn. Xin chân thành cảm ơn! MỤC LỤC Trang phụ bìa Lời cam đoan Lời cảm ơn Mục lục Danh mục các kí hiệu, các từ viết tắt Danh mục các hình ảnh Danh mục các bảng biểu MỞ ĐẦU ................................................................................................................ 1 Chương 1. KIẾN THỨC CƠ SỞ ........................................................................... 3 1.1. Nhóm (group) ................................................................................................. 4 1.1.1. Phép toán hai ngôi .................................................................................... 4 1.1.2. Nửa nhóm (monoid) ................................................................................. 4 1.1.3. Nhóm ........................................................................................................ 5 1.2. Vành (Ring).................................................................................................... 5 1.2.1. Định nghĩa của vành ................................................................................ 5 1.2.2. Iđêan (Ideal) ............................................................................................. 6 1.2.3. Vành thương (quotient ring) .................................................................... 6 1.3. Đồng dư số học .............................................................................................. 7 1.3.1. Phép đồng dư ........................................................................................... 7 1.3.1. Phần tử nghịch đảo của phép nhân đồng dư ............................................ 8 1.4. Thuật toán lũy thừa nhanh ............................................................................. 9 Chương 2. TỔNG QUAN VỀ RSA ..................................................................... 11 2.1. Hệ mã RSA gốc............................................................................................ 12 2.2. Thám mã RSA .............................................................................................. 12 2.2.1. Phân tích số nguyên lớn ......................................................................... 12 2.2.2. Khóa bí mật có số mũ nhỏ ..................................................................... 13 2.2.3. Khóa công khai có số mũ nhỏ ................................................................ 13 2.2.4. Tấn công thực thi ................................................................................... 14 2.2.5. Tấn công bằng dàn ................................................................................. 15 2.3. Một số biến thể của RSA ............................................................................. 16 2.3.1. RSA trên vành thương các đa thức ........................................................ 16 2.3.2. RSA trên vành thương các số nguyên Gauss ......................................... 17 2.3.3. RSA trên nhóm nhân các ma trận khả nghịch ....................................... 18 2.3.4. RSA trên nhóm đường cong elliptic ...................................................... 19 2.3.5. RSA trên vành Bergman ........................................................................ 20 2.3.6. Nhận xét về các biến thể ........................................................................ 21 Chương 3. XÂY DỰNG HỆ MÃ RSA TRÊN VÀNH 𝑬𝒏𝒅(ℤ𝒏 × ℤ𝒏𝒎 ) ........... 23 3.1. Giới thiệu về vành 𝐸𝑛𝑑(ℤ𝑝 × ℤ𝑝𝑚 ) ............................................................ 24 3.1.1. Đặc điểm của vành 𝐸𝑛𝑑(ℤ𝑝 × ℤ𝑝𝑚 ) ..................................................... 24 3.1.2. Phần tử khả nghịch trong 𝐸𝑛𝑑(ℤ𝑝 × ℤ𝑝𝑚 ) ........................................... 25 3.2. Xây dựng hệ mã RSA trên vành 𝐸𝑛𝑑(ℤ𝑛 × ℤ𝑛𝑚 )....................................... 28 3.2.1. Xây dựng vành 𝐸𝑛𝑑(ℤ𝑛 × ℤ𝑛𝑚 ) ........................................................... 28 3.2.2. Xây dựng hệ mã RSA trên vành 𝐸𝑛𝑑(ℤ𝑛 × ℤ𝑛𝑚 ) ................................ 33 3.3. Cài đặt và đánh giá hệ mã ............................................................................ 35 3.3.1. Cài đặt hệ mã.......................................................................................... 35 3.3.2. Đánh giá hệ mã ...................................................................................... 41 Chương 4. KẾT LUẬN ......................................................................................... 44 4.1. Kết quả đạt được .......................................................................................... 44 4.2. Hướng phát triển .......................................................................................... 44 TÀI LIỆU THAM KHẢO ..................................................................................... 46 Danh mục các kí hiệu, các từ viết tắt Kí hiệu Ý nghĩa CRT Định lý phần dư Trung hoa (Chinese Remainder Theorem) gcd Ước chung lớn nhất (Greatest Common Divisor) lcm Bội chung nhỏ nhất (Least Common Multiple) Danh mục các hình ảnh Hình 3.1. Giao diện tổng quan của hệ mã ................................................................ 36 Hình 3.2. Chức năng sinh khóa ................................................................................ 36 Hình 3.3. Thông báo khi nhập giá trị 𝑚 không hợp lệ............................................. 37 Hình 3.4. Thông báo nhập nội dung mã hóa ............................................................ 38 Hình 3.5. Chức năng mã hóa .................................................................................... 38 Hình 3.6. Chức năng Mã hóa file văn bản ............................................................... 39 Hình 3.7. Thông báo nhập nội dung giải mã ............................................................ 40 Hình 3.8. Chức năng giải mã.................................................................................... 40 Hình 3.9. Chức năng Giải mã file văn bản ............................................................... 41 Danh mục các bảng biểu Bảng 2.1. Độ dài mô-đun và số các phép tính của các biến thể RSA ...................... 21 1 MỞ ĐẦU Hệ mã RSA là một trong số những hệ mã công khai được sử dụng phổ biến nhất hiện nay. Hệ mã được giới thiệu vào 1978 bởi ba tác giả là Ron Rivest, Adi Shamir và Len Adleman. Khi nghiên cứu về hệ mã RSA, trên thế giới có hai xu hướng, đó là: phát triển các biến thể của RSA và thám mã RSA. Sự phát triển các biến thể của RSA có thể chia làm hai hướng. Hướng thứ nhất tập trung vào hệ mã RSA gốc nhưng cải tiến các thuật toán mã hóa và giải mã nhằm giảm độ phức tạp tính toán hoặc xây dựng RSA trên vành ℤ𝑛 với 𝑛 có dạng phức tạp hơn thay vì là tích của hai số nguyên tố phân biệt. Trong hướng thứ hai, các biến thể của RSA được xây dựng trên các cấu trúc đại số phức tạp hơn. Một số biến thể của RSA được xây dựng theo hướng thứ hai như sau:  RSA trên vành thương các đa thức [1]  RSA trên vành thương các số nguyên Gauss [1]  RSA trên nhóm nhân các ma trận [2]  RSA trên nhóm đường cong elliptic [3]  RSA trên vành Bergman [4] Có thể thấy, một số biến thể của RSA được xây dựng trên các cấu trúc khác nhau, đó thường là nhóm hoặc vành thương của vành Euclide. Các phép toán trên các cấu trúc này phải rõ ràng để có thể lập trình trên máy tính. Một cách đơn giản nhất để tạo ra một cấu trúc là xét vành các tự đồng cấu 𝐸𝑛𝑑(𝐺) với 𝐺 là nhóm đã biết. Một ví dụ điển hình của vành các tự đồng cấu 𝐸𝑛𝑑 (𝐺 ) là vành Bergman 𝐸𝑛𝑑(ℤ𝑝 × ℤ𝑝2 ) với 𝑝 là số nguyên tố. Vành Bergman được giới thiệu trong [5] vào năm 1974 nhưng do các phép toán trên vành này là khó nắm bắt nên hầu như không có hệ mã nào được xây dựng trên đó. Mãi đến năm 2011, Climent và các 2 cộng sự mới thiết lập được đẳng cấu giữa vành 𝐸𝑛𝑑(ℤ𝑝 × ℤ𝑝2 ) với vành ma trận 𝑎 cấp 2 × 2: 𝐸𝑝 = {( 𝑝𝑐 𝑏 ) : 𝑎, 𝑏, 𝑐, 𝑑 ∈ ℤ, 0 ≤ 𝑎, 𝑏, 𝑐 < 𝑝, 0 ≤ 𝑑 < 𝑝2 } trong 𝑑 [6]. Và đến năm 2013, các tác giả trong [4] đã định nghĩa 𝐸𝑛 = {( 𝑎 𝑝𝑐 𝑏 ) : 𝑎, 𝑏, 𝑐, 𝑑 ∈ ℤ, 0 ≤ 𝑎, 𝑏, 𝑐 < 𝑛, 0 ≤ 𝑑 < 𝑛2 } và xây dựng được hệ mã 𝑑 RSA trên vành này (với 𝑝, 𝑞 là hai số nguyên tố phân biệt và 𝑛 = 𝑝𝑞). Một mở rộng của vành Bergman là vành 𝐸𝑛𝑑(ℤ𝑝 × ℤ𝑝𝑚 ) đã được giới thiệu trong [7]. Các phần tử của vành này có thể được biểu diễn dưới dạng các ma trận 2 × 2 như sau: 𝐸𝑝,𝑝𝑚 = {( 𝑎 𝑝 𝑚−1 𝑐 𝑏 ) |𝑎, 𝑏, 𝑐 ∈ ℤ𝑝 , 𝑑 ∈ ℤ𝑝𝑚 }. Mặt khác, các 𝑑 phép toán trên vành này là hoàn toàn nắm bắt được. Vì thế, mục đích của đề tài là đi xây dựng vành 𝐸𝑛𝑑(ℤ𝑛 × ℤ𝑛𝑚 ) (với 𝑝, 𝑞 là hai số nguyên tố phân biệt và 𝑛 = 𝑝𝑞) và xây dựng hệ mã RSA trên vành 𝐸𝑛𝑑(ℤ𝑛 × ℤ𝑛𝑚 ) này.  Mục đích nghiên cứu Mục đích nghiên cứu của luận văn là đi tìm hiểu và xây dựng hệ mã RSA trên vành 𝐸𝑛𝑑(ℤ𝑛 × ℤ𝑛𝑚 ).  Nhiệm vụ nghiên cứu  Tìm hiểu về hệ mã RSA gốc và các cách tấn công  Các biến thể của RSA  Tìm hiểu vành 𝐸𝑛𝑑(ℤ𝑝 × ℤ𝑝𝑚 )  Xây dựng vành 𝐸𝑛𝑑(ℤ𝑛 × ℤ𝑛𝑚 ) và hệ mã RSA trên vành đó  Giới hạn đề tài  Xây dựng minh họa một hệ mã RSA trên cấu trúc đã xây dựng  So sánh ưu, khuyết điểm của hệ mã đã xây dựng với hệ mã RSA gốc  Đóng góp của luận văn Luận văn đóng góp thêm một biến thể cho hệ mã RSA. 3 Chương 1. KIẾN THỨC CƠ SỞ Nội dung chương này gồm: 1. Nhắc lại một số kiến thức về nhóm  Phép toán hai ngôi  Nửa nhóm  Nhóm 2. Một số kiến thức về vành  Định nghĩa vành  Iđêan  Vành thương 3. Một số kiến thức về đồng dư số học  Phép đồng dư  Phần tử nghịch đảo 4. Thuật toán lũy thừa nhanh 4 Trong chương này chúng tôi sẽ trình bày lại một số kiến thức cơ sở về nhóm, vành, phép đồng dư và thuật toán lũy thừa nhanh làm tiền đề để trình bày những nội dung cho các chương còn lại. 1.1. Nhóm (group) 1.1.1. Phép toán hai ngôi Cho 𝐴 là một tập hợp khác rỗng. Phép toán hai ngôi xác định trên tập hợp 𝐴 là một ánh xạ từ 𝐴2 vào 𝐴. Ta kí hiệu ánh xạ là °, khi đó, ảnh của (𝑥, 𝑦) ∈ 𝐴2 có thể được kí hiệu là 𝑥°𝑦. Tập hợp 𝐴 với phép toán hai ngôi như vậy sẽ được gọi là tập có trang bị phép toán hai ngôi và kí hiệu là (𝐴, °). Phép toán ° có thể thỏa mãn một vài tính chất nào đó, ví dụ như:  Tính chất giao hoán: ∀ 𝑥, 𝑦 ∈ 𝐴, 𝑥°𝑦 = 𝑦°𝑥  Tính chất kết hợp: ∀ 𝑥, 𝑦, 𝑧 ∈ 𝐴, 𝑥°(𝑦°𝑧) = (𝑥°𝑦)°𝑧  Có phần tử đơn vị: ∃𝑒 ∈ 𝐴, ∀ 𝑥 ∈ 𝐴, 𝑒°𝑥 = 𝑥°𝑒 = 𝑥 Những ví dụ dễ thấy nhất về phép toán hai ngôi chính là phép cộng và phép nhân trên các tập ℕ, ℤ, ℚ, ℝ, ℂ. Phép trừ cũng là phép toán hai ngôi trên các tập ℤ, ℚ, ℝ, ℂ nhưng lại không là phép toán hai ngôi trên tập ℕ. 1.1.2. Nửa nhóm (monoid) Cho (𝑀,∗) là một tập hợp được trang bị phép toán hai ngôi ∗. Nếu phép toán ∗ thỏa mãn tính chất kết hợp: 𝑥 ∗ (𝑦 ∗ 𝑧) = (𝑥 ∗ 𝑦) ∗ 𝑧, ∀ 𝑥, 𝑦, 𝑧 ∈ 𝑀 thì khi đó (𝑀,∗) được gọi là nửa nhóm. Ví dụ: Với phép cộng, tập hợp ℕ chính là một nửa nhóm. Đồng cấu nửa nhóm là một ánh xạ 𝑓: 𝑀 → 𝑁 giữa hai nửa nhóm (𝑀,∗) và (𝑁,∙) sao cho ánh xạ đó bảo toàn phép toán: ∀𝑥, 𝑦 ∈ 𝑀, 𝑓 (𝑥 ∗ 𝑦) = 𝑓(𝑥) ∙ 𝑓(𝑦). 5 1.1.3. Nhóm Tập hợp (𝐺,∗) được trang bị phép toán hai ngôi ∗ được gọi là nhóm khi thỏa mãn các tính chất sau:  Tính kết hợp: 𝑥 ∗ (𝑦 ∗ 𝑧) = (𝑥 ∗ 𝑦) ∗ 𝑧, ∀ 𝑥, 𝑦, 𝑧 ∈ 𝐺  Có phần tử đơn vị 𝑒 ∈ 𝐺: 𝑒 ∗ 𝑥 = 𝑥 ∗ 𝑒 = 𝑥, ∀ 𝑥 ∈ 𝐺  Khả nghịch: ∀ 𝑥 ∈ 𝐺, ∃𝑥 ′ ∈ 𝐺 thỏa mãn: 𝑥 ∗ 𝑥 ′ = 𝑥 ′ ∗ 𝑥 = 𝑒 Trường hợp, phép toán ∗ trên nhóm 𝐺 có tính giao hoán thì ta nói 𝐺 là nhóm giao hoán. Chẳng hạn, tập hợp các số nguyên ℤ với phép cộng chính là một nhóm giao hoán. Trong nhóm (𝐺,∗), nếu có một tập con 𝐻 là một nhóm với phép toán ∗ của 𝐺 thì 𝐻 được gọi là nhóm con của 𝐺. Trong nhóm 𝐺, số lượng phần tử có trong nhóm được gọi là cấp của nhóm và được kí hiệu là |𝐺 |. Còn cấp của phần tử 𝑎 trong nhóm 𝐺 được định nghĩa là một số tự nhiên 𝑘 nhỏ nhất thỏa mãn 𝑎𝑘 = 𝑒. Nếu không tồn tại số 𝑘 như vậy ta nói 𝑎 có cấp vô hạn. Định lý 1.1 (Định lý Lagrange trong lý thuyết nhóm) Nếu 𝐻 là nhóm con của nhóm hữu hạn 𝐺 thì số phần tử của 𝐺 chia hết cho số phần tử của 𝐻. Từ định lý Lagrange trong lý thuyết nhóm có thể suy ra một số hệ quả sau: Hệ quả 1.1 Cấp của mỗi phần tử trong một nhóm hữu hạn là ước của cấp của nhóm đó. Hệ quả 1.2 Cho 𝐺 là một nhóm hữu hạn cấp 𝑛 và 𝑎 là một phần tử của 𝐺. Khi đó 𝑎𝑛 = 𝑒. 1.2. Vành (Ring) 1.2.1. Định nghĩa của vành Tập hợp (𝑅, +, . ) có trang bị đồng thời hai phép toán hai ngôi là + (cộng) và . (nhân) được gọi là vành khi thỏa mãn các điều kiện sau đây: 6  Cấu trúc (𝑅, +) là một nhóm giao hoán  Phép toán nhân của 𝑅 có tính chất kết hợp  Phép nhân có tính chất phân phối hai bên đối với phép cộng, nghĩa là: ∀𝑥, 𝑦, 𝑧 ∈ 𝑅, 𝑥 (𝑦 + 𝑧) = 𝑥𝑦 + 𝑥𝑧 ∀𝑥, 𝑦, 𝑧 ∈ 𝑅, (𝑦 + 𝑧)𝑥 = 𝑦𝑥 + 𝑧𝑥 Một ví dụ điển hình nhất của vành chính là tập hợp các số nguyên ℤ với phép cộng và phép nhân. Trong vành (𝑅, +, . ), nếu có một tập hợp 𝐴 là một vành với hai phép toán + và . trên 𝑅 thì 𝐴 được gọi là vành con của vành 𝑅. 1.2.2. Iđêan (Ideal) Cho 𝑅 là một vành. Một iđêan 𝐼 là một vành con khác rỗng của 𝑅 thỏa mãn:  Nếu 𝑎, 𝑏 ∈ 𝐼 thì 𝑎 + 𝑏 ∈ 𝐼  Nếu 𝑎 ∈ 𝐼 và 𝑟 ∈ 𝑅 thì 𝑎𝑟 ∈ 𝐼 và 𝑟𝑎 ∈ 𝐼 Có thể thấy rằng iđêan là một tập con của 𝑅 đóng với phép cộng và phép nhân. Không chỉ tích của hai phần tử thuộc 𝐼 nằm trong 𝐼, mà tích của một phần tử thuộc 𝐼 với phần tử 𝑟 bất kì cũng thuộc 𝐼. Để dễ hình dung hơn, ta tìm hiểu ví dụ sau: Với 𝑛 là một số nguyên, thì tập 𝑛ℤ = {𝑛𝑎: 𝑎 ∈ ℤ} là một iđêan của ℤ. Do xét điều kiện thứ nhất, nếu 𝑥, 𝑦 ∈ 𝑛ℤ thì ∃𝑎, 𝑏: 𝑥 = 𝑛𝑎, 𝑦 = 𝑛𝑏. Nên 𝑥 + 𝑦 = 𝑛𝑎 + 𝑛𝑏 = 𝑛(𝑎 + 𝑏) ∈ 𝑛ℤ. Thứ hai, với phép nhân, cho 𝑥 = 𝑛𝑎 ∈ 𝑛ℤ và 𝑟 ∈ ℤ thì 𝑟𝑥 = 𝑥𝑟 = 𝑟(𝑛𝑎) = 𝑛(𝑟𝑎) ∈ 𝑛ℤ. Nếu 𝑛 > 0 thì 𝑛ℤ có dạng là 𝑛ℤ = {0, 𝑛, 2𝑛, … , −𝑛, −2𝑛, … }. 1.2.3. Vành thương (quotient ring) Cho vành 𝑅 và 𝐼 là một iđêan của 𝑅. Nếu 𝑎 ∈ 𝑅 thì lớp 𝑎 + 𝐼 được định nghĩa là 𝑎 + 𝐼 = {𝑎 + 𝑥: 𝑥 ∈ 𝐼}. Ví dụ: với 𝑅 = ℤ và 𝐼 = 5ℤ, ta có 5 lớp 𝑎 + 𝐼 như sau: 7 0 + 5ℤ = {0,5,10, … , −5, −10, … }, 1 + 5ℤ = {1,6,11, . . . , −4, −9, −14, . . . }, 2 + 5ℤ = {2,7,12, . . . , −3, −8, −13, . . . }, 3 + 5ℤ = {3,8,13, . . . , −2, −7, −12, . . . }, 4 + 5ℤ = {4,9,14, . . . , −1, −6, −11, . . . }. Cho 𝐼 là một iđêan của vành 𝑅. Tập 𝑅/𝐼 là tập hợp các lớp của 𝐼, có dạng 𝑅/𝐼 = {𝑎 + 𝐼: 𝑎 ∈ 𝑅} được gọi là vành thương của 𝑅 theo 𝐼. Trên vành thương, hai phép toán cộng và nhân được định nghĩa như sau:  (𝑎 + 𝐼 ) + (𝑏 + 𝐼 ) = (𝑎 + 𝑏 ) + 𝐼  (𝑎 + 𝐼). (𝑏 + 𝐼) = (𝑎𝑏) + 𝐼 Ví dụ: Với 𝑛 là số nguyên dương, ta có 𝑛ℤ là iđêan của ℤ. Vành thương ℤ/𝑛ℤ = {0 + 𝑛ℤ, 1 + 𝑛ℤ, … , 𝑛 − 1 + 𝑛ℤ}. 1.3. Đồng dư số học 1.3.1. Phép đồng dư Cho 𝑎 là số nguyên và 𝑛 là số nguyên dương. Khi đó, kí hiệu 𝑎 𝑚𝑜𝑑 𝑛 biểu diễn phần dư của 𝑎 chia cho 𝑚. Nếu hai số 𝑎, 𝑏 có cùng số dư trong phép chia cho 𝑛 thì ta nói rằng 𝑎 và 𝑏 là đồng dư trong phép chia cho 𝑛 và kí hiệu là 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛). Dễ thấy rằng, 𝑎 và 𝑏 là đồng dư trong phép chia cho 𝑛 khi và chỉ khi tồn tại số 𝑘 sao cho 𝑎 = 𝑏 + 𝑘𝑛 hay ta có thể biểu diễn 𝑎 = 𝑏 + 𝑛ℤ. Như vậy có thể thấy rằng lúc đó hai số 𝑎 và 𝑏 cùng nằm trong một lớp của vành thương ℤ/𝑛ℤ. Tập hợp tất cả các số nguyên có cùng số dư trong phép 𝑎 𝑚𝑜𝑑 𝑛 được gọi là lớp đồng dư 𝑎̅. Ví dụ các lớp đồng dư trong phép 𝑚𝑜𝑑 5 là: 0̅ = {0,5,10, … , −5, −10, … } = 0 + 5ℤ, 1̅ = {1,6,11, . . . , −4, −9, −14, . . . } = 1 + 5ℤ, 8 2̅ = {2,7,12, . . . , −3, −8, −13, . . . } = 2 + 5ℤ, 3̅ = {3,8,13, . . . , −2, −7, −12, . . . } = 3 + 5ℤ, 4̅ = {4,9,14, . . . , −1, −6, −11, . . . } = 4 + 5ℤ. Tập các lớp đồng dư khi chia một số nguyên bất kì cho 𝑛 được kí hiệu là ℤ𝑛 = {0̅, 1̅, … , ̅̅̅̅̅̅̅ 𝑛 − 1}. Như vậy, ta có thể thấy rằng vành thương ℤ/𝑛ℤ chính là vành các lớp đồng dư ℤ𝑛 . 1.3.1. Phần tử nghịch đảo của phép nhân đồng dư Nếu hai số nguyên 𝑎 và 𝑛 nguyên tố cùng nhau, thì tồn tại số nguyên 𝑏 sao cho 𝑎𝑏 ≡ 1 𝑚𝑜𝑑 𝑛. Khi đó, ta gọi 𝑏 là phần tử nghịch đảo của 𝑎 trong phép đồng dư cho 𝑛 và kí hiệu là 𝑎−1 . Giá trị của 𝑎−1 sẽ được tính dựa vào thuật toán Euclide mở rộng được trình bày như bên dưới. Thuật toán Euclide mở rộng tìm phần tử nghịch đảo Input: 𝑎 ∈ ℤ𝑛 , 𝑛 Output: phần tử nghịch đảo của 𝑎 hoặc thông báo “𝑎 không có phần tử nghịch đảo” Thuật giải: temp_a = a; temp_n = n; x = 1; y = 0; while (temp_n ≠ 0) { q = temp_a div temp_n; xr = x – q*y; x = y; y = xr; r = temp_a mod temp_n; 9 temp_a = temp_n; temp_n = r; } If (temp_a ≠ 1) then Return “a không có phần tử nghịch đảo”; else { If x<0 then x = x+n; Return x; } 1.4. Thuật toán lũy thừa nhanh Thông thường để tính nhanh lũy thừa tự nhiên của một số, người ta sẽ sử dụng thuật toán bình phương và nhân. Quá trình thực hiện của thuật toán được dựa trên công thức đệ quy sau:  Với 𝑛 = 0 thì 𝑥 𝑛 = 1  Với 𝑛 > 0 ta có công thức (𝑥 𝑘 )2 , 𝑥𝑛 = { 𝑥 ∗ (𝑥 𝑘 )2 , với 𝑛 = 2𝑘 với 𝑛 = 2𝑘 + 1 Dễ thấy rằng, phép tính 𝑥 𝑛 được đưa về thành các phép bình phương và phép nhân, do đó mà thuật toán có tên gọi là thuật toán bình phương và nhân. Thuật toán bình phương và nhân tính 𝑥 𝑛 Input: 𝑥, 𝑛 với 𝑛 ≥ 0 Output: 𝑥 𝑛 Thuật giải Funtion Square_Multi(int x, int n) { If (n = 0) then return 1; 10 Else { xn = Square_Multi(x, n div 2); if (n mod 2 == 0) then return xn*xn; else return x*xn*xn; } } Ta thấy rằng số mũ 𝑛 của thuật toán giảm dần theo lũy thừa của 2 nên độ phức tạp của thuật toán là 𝑂(𝑙𝑜𝑔 𝑛). Thuật toán lũy thừa và nhân thường được sử dụng nhiều trong các bài toán mã hóa và giải mã các hệ mã hóa, đặc biệt là hệ mã hóa công khai. Tuy nhiên trong các hệ mã, kết quả tính lũy thừa còn phải được tính đồng dư cho một giá trị 𝑚 nên thuật toán sẽ thay đổi như sau. Thuật toán bình phương và nhân tính 𝑥 𝑛 𝑚𝑜𝑑 𝑚 Input: 𝑥, 𝑛 với 𝑛 ≥ 0, 𝑚 ≥ 2 Output: 𝑥 𝑛 𝑚𝑜𝑑 𝑚 Thuật giải Funtion Square_Multi_Modulo(int x, int n, int m) { If (n = 0) then return 1; Else { xn = Square_Multi_Modulo (x, n div 2, m); if (n mod 2 == 0) then return (xn*xn) mod m; else return (x*xn*xn) mod m; } } 11 Chương 2. TỔNG QUAN VỀ RSA Nội dung chương này gồm: 1. Giới thiệu sơ lược hệ mã RSA gốc 2. Trình bày một số cách thám mã RSA  Phân tích số nguyên lớn  Khóa bí mật có số mũ nhỏ  Khóa công khai có số mũ nhỏ  Tấn công thực thi  Tấn công bằng dàn 3. Giới thiệu sơ lược các biến thể của RSA  RSA trên vành thương các đa thức  RSA trên vành thương các số nguyên Gauss  RSA trên nhóm nhân các ma trận  RSA trên nhóm đường cong elliptic  RSA trên vành Bergman