Tài liệu Nghiên cứu một số giao thức tính toán đa bên an toàn sử dụng mã đồng cấu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ——————————————– VŨ MẠNH ĐẠT NGHIÊN CỨU MỘT SỐ GIAO THỨC TÍNH TOÁN ĐA BÊN AN TOÀN SỬ DỤNG MÃ ĐỒNG CẤU LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ——————————————– VŨ MẠNH ĐẠT NGHIÊN CỨU MỘT SỐ GIAO THỨC TÍNH TOÁN ĐA BÊN AN TOÀN SỬ DỤNG MÃ ĐỒNG CẤU Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. Trần Văn Dũng HÀ NỘI, 2017 LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn của TS. Trần Văn Dũng. Tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới TS. Trần Văn Dũng, giảng viên trường Đại học GTVT Hà Nội đã nhiệt tình giúp đỡ, trực tiếp chỉ bảo hướng dẫn để tác giả hoàn thành luận văn này. Tác giả xin bày tỏ lòng biết ơn chân thành tới Phòng Sau đại học, các thầy cô giáo dạy cao học chuyên ngành Toán Ứng dụng trường Đại học Sư phạm Hà Nội 2 đã giúp đỡ tác giả trong suốt quá trình học tập. Cuối cùng tác giả xin gửi lời cảm ơn chân thành đến gia đình, bạn bè, người thân đã luôn động viên và khuyến khích, tạo mọi điều kiện thuận lợi cho tác giả trong quá trình học tập và hoàn thành luận văn. Hà Nội, 15 tháng 07 năm 2017 Tác giả luận văn Vũ Mạnh Đạt LỜI CAM ĐOAN Tôi xin cam đoan rằng những số liệu và kết quả nghiên cứu trong luận văn này là trung thực, không trùng lặp với các luận văn khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Tác giả luận văn Vũ Mạnh Đạt Mục lục Lời mở đầu 3 Chương 1 CÁC KIẾN THỨC CƠ SỞ 5 1.1 Số học Mudulo . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Các số nguyên tố và các số nguyên tố cùng nhau . . . 5 1.1.2 Số học trong lớp số dư . . . . . . . . . . . . . . . . . . 7 1.1.3 Lý thuyết về đồng dư . . . . . . . . . . . . . . . . . . 7 1.1.4 Các số nguyên modulo n . . . . . . . . . . . . . . . . 8 1.1.5 Hàm Euler, định lý Euler, định lý Fermat . . . . . . . 8 1.1.6 Thuật toán Euclide mở rộng . . . . . . . . . . . . . . 10 1.1.7 Định lý phần dư Trung Hoa . . . . . . . . . . . . . . . 12 1.1.8 Căn nguyên thuỷ và logarit rời rạc . . . . . . . . . . . 15 1.2 Mã hóa công khai RSA . . . . . . . . . . . . . . . . . . . . . 19 1.2.1 Mô tả sơ lược . . . . . . . . . . . . . . . . . . . . . . 19 1.2.2 Mã hóa . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.2.3 Giải mã . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.2.4 Tính đúng đắn của thuật toán RSA . . . . . . . . . . 21 1.3 Chữ ký điện tử DSA . . . . . . . . . . . . . . . . . . . . . . 23 1.3.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.2 Tạo khóa DSA . . . . . . . . . . . . . . . . . . . . . . 23 i Luận văn Thạc sĩ toán học Vũ Mạnh Đạt 1.3.3 Tạo chữ ký DSA . . . . . . . . . . . . . . . . . . . . . 24 1.3.4 Xác nhận chữ ký DSA . . . . . . . . . . . . . . . . . . 24 1.3.5 Tính đúng đắn của thuật toán DSA . . . . . . . . . . 24 1.4 Mã hóa ElGamal và mã hóa Paillier . . . . . . . . . . . . . 26 1.4.1 Hệ mã hóa ElGamal . . . . . . . . . . . . . . . . . . . 26 1.4.2 Hệ mã hóa Paillier . . . . . . . . . . . . . . . . . . . . 28 1.5 Mã hóa đồng cấu . . . . . . . . . . . . . . . . . . . . . . . . 30 1.5.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . 30 1.5.2 Tính chất đồng cấu . . . . . . . . . . . . . . . . . . . 30 Chương 2 TÍNH TOÁN ĐA BÊN AN TOÀN DỰA TRÊN MÃ ĐỒNG CẤU 32 2.1 Các khái niệm và mô hình . . . . . . . . . . . . . . . . . . . 32 2.1.1 Các khái niệm . . . . . . . . . . . . . . . . . . . . . . 32 2.1.2 Các mô hình . . . . . . . . . . . . . . . . . . . . . . . 33 2.2 Giao thức Sigma . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2.1 Giao thức định danh Schnorr . . . . . . . . . . . . . . 35 2.2.2 Giao thức Chaum - Pedersen . . . . . . . . . . . . . . 37 2.2.3 Giao thức “Hoặc" . . . . . . . . . . . . . . . . . . . . 37 2.3 Giao thức tổng . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3.2 Mô hình tấn công thụ động . . . . . . . . . . . . . . . 40 2.3.3 Mật mã cơ bản . . . . . . . . . . . . . . . . . . . . . . 41 2.3.4 Mô hình tấn công chủ động . . . . . . . . . . . . . . . 42 2.4 Giao thức cực đại . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4.1 Các vấn đề . . . . . . . . . . . . . . . . . . . . . . . . 46 ii Luận văn Thạc sĩ toán học Vũ Mạnh Đạt 2.4.2 Giao thức 1 . . . . . . . . . . . . . . . . . . . . . . . . 47 2.4.3 Giao thức 2 . . . . . . . . . . . . . . . . . . . . . . . . 50 2.4.4 Thảo luận cho các mô hình tấn công chủ động . . . . 51 Chương 3 MỘT SỐ VÍ DỤ TÍNH TOÁN ĐA BÊN AN TOÀN 54 3.1 Tính toán giao thức Sigma . . . . . . . . . . . . . . . . . . . 54 3.1.1 Ví dụ giao thức định danh Schnorr . . . . . . . . . . . 54 3.1.2 Ví dụ giao thức Chaum – Pedersen . . . . . . . . . . . 56 3.1.3 Ví dụ giao thức “Hoặc” . . . . . . . . . . . . . . . . . 57 3.2 Một số tính toán số học đa bên . . . . . . . . . . . . . . . . 58 3.2.1 Tính toán trong giao thức tổng . . . . . . . . . . . . . 58 3.2.2 Chứng minh tính hợp lệ của bản rõ sử dụng khóa công khai Elgamal . . . . . . . . . . . . . . . . . . . . . . . 66 3.3 So sánh đa bên an toàn . . . . . . . . . . . . . . . . . . . . 70 3.3.1 Mã đồng cấu với tính vô hướng . . . . . . . . . . . . . 70 3.3.2 Mã hóa 0 và mã hóa 1 . . . . . . . . . . . . . . . . . . 71 3.3.3 Giao thức . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.4 Đánh giá an toàn . . . . . . . . . . . . . . . . . . . . . . . . 76 iii Luận văn Thạc sĩ toán học Vũ Mạnh Đạt DANH MỤC KÍ HIỆU, TỪ VIẾT TẮT STT Từ viết tắt Ý nghĩa 1 gcd; UCLN Ước chung lớn nhất 2 max Giá trị lớn nhất 3 Zn Các số nguyên modulo n 4 RSA Mã hóa công khai (Ron Rivest, Adi Shamir và Len Adleman) 5 DSA Chữ ký điện tử (Digital Signature Algorithm) 6 MPC Các giao thức tính toán đa bên (Multi Party Computation) 7 ZKP Chứng minh không tiết lộ thông tin (Zero - Knowledge Proofs) 8 ZKPs (SM − ZKP ) Chứng minh phần tử thuộc tập hợp không tiết lộ thông tin (Set Membership – Zero Knowledge Proofs) 9 ZKPs (P E − ZKP ) Kiểm tra sự bằng nhau của hai bản rõ không tiết lộ thông tin (Plaintext Equality - Zero Knowledge Proofs) 10 DDH Là một phương pháp trao đổi khóa (Decisional Diffie Hellman) 1 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt DANH MỤC HÌNH VẼ Hình vẽ Nội dung Ghi chú Hình 1.1 Sơ đồ mã hóa công khai RSA Trang 20 Hình 2.1 Tổng quan về hoạt động mạng Trang 41 Hình 2.2 Mỗi phần i của mỗi nút nguồn Trang 44 được gửi đến q, mã hóa với mỗi i (điểm đến) và q (xác minh) Hình 2.3 Ở bước 2 phần (b) của giao thức mở rộng, Trang 45 các nút được cung cấp có thể giải mã; họ tổng hợp và gửi kết quả đến q bằng cách tái mã hóa các thông điệp Hình 2.4 Ví dụ về giá trị cực đại Trang 47 Hình 2.5 Sự so sánh của hai nút a và b Trang 48 Hình 2.6 Sự so sánh thông qua giá trị nhị phân Trang 50 Hình 2.7 Thứ tự của các nguy cơ bị rủi ro của một Trang 51 phủ định sai đối với số lượng khác nhau của các bit cho tối đa và cho các giá trị ngẫu nhiên Hình 2.8 Tính toán giá trị là 11111b thay vì 11010b 2 Trang 52 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt LỜI MỞ ĐẦU 1. Lý do chọn đề tài Trong cuộc sống ngày nay, công nghệ thông tin và truyền thông đã có mặt ở nhiều phương diện trong cuộc sống hàng ngày của chúng ta, giờ đây điện thoại di động, máy tính để bàn, thư điện tử và việc sử dụng Internet đã trở thành tâm điểm trong văn hóa và cộng đồng của chúng ta, qua đó nhu cầu trao đổi thông tin dữ liệu giữa các công ty, cơ quan, doanh nghiệp ngày càng cao. Trong quá trình trao đổi thông tin thì vấn đề bảo mật thông tin là một trong những vẫn đề được đặt lên hàng đầu, tuy nhiên trong quá trình trao đổi giữa các bên vẫn còn có các mạng bị tấn công, bị những kẻ gian lận đánh cắp thông tin, gây những ra tổn thất nặng nề. Khi đó nhu cầu về bảo mật thông tin giữa các bên phải được an toàn tuyệt đối. Do đó nó đảm bảo việc tính toán đa bên được an toàn. Giao thức tính toán đa bên an toàn sử dụng mã đồng cấu không phải là một lĩnh vực mới mẻ của an toàn bảo mật thông tin, nhưng hứa hẹn sẽ mang đến những ứng dụng rộng khắp ở tất cả các lĩnh vực, các ngành nghề cần được đảm bảo giữ bí mật riêng tư, khi có nhiều bên cùng tham gia giải quyết một bài toán chung. Mã đồng cấu là loại mã cho phép tái hiện lại việc kết hợp trên các bản rõ thành phần, khi ta dùng kết quả kết hợp các bản mã tương ứng của chúng. Từ đó, mỗi người tham gia có thể mã hoá đầu vào của mình và từ kết quả kết hợp các bản mã thành phần đó có thể biết được kết quả của bài toán chung. Đó là ý tưởng của các giao thức tính toán đa bên an toàn 3 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt dùng mã đồng cấu. Được sự gợi ý của TS. Trần Văn Dũng hướng dẫn và nhận thấy tính thiết thực của vấn đề em đã chọn đề tài “Nghiên cứu một số giao thức tính toán đa bên an toàn sử dụng mã đồng cấu” để làm nội dung cho luận văn. 2. Mục đích nghiên cứu Tìm hiểu một số giao thức tính toán đa bên an toàn dựa trên mã đồng cấu, cơ sở an toàn của chúng. 3. Nhiệm vụ nghiên cứu Hiểu cơ sở toán học của mã công khai có tính chất đồng cấu và việc áp dụng chúng để giải một số bài toán tính toán đa bên an toàn. 4. Đối tượng và phạm vi nghiên cứu 4.1. Đối tượng nghiên cứu Nghiên cứu cơ sở toán học của mã công khai, các giao thức an ninh. 4.2. Phạm vi nghiên cứu Nghiên cứu trên cơ sở toán học, trường số modulo, mã đồng cấu, các giao thức đa bên an toàn. 5. Dự kiến đóng góp mới của đề tài Tóm tắt về mã công khai, mã đồng cấu, trình bày một số giao thức đa bên an toàn sử dụng mã đồng cấu. Nêu các bước chi tiết của các giao thức thông qua các số liệu của riêng mình. 6. Phương pháp nghiên cứu Nghiên cứu cơ sở lý thuyết của các giao thức và áp dụng vào trường số modulo để tính toán giải các bài toán. 4 Chương 1 CÁC KIẾN THỨC CƠ SỞ Trong chương 1 luận văn trình bày những kiến thức cơ sở quan trọng để áp dụng vào các thuật toán, giao thức chia sẻ thông tin bí mật. Cụ thể luận văn đề cập đến một số định nghĩa cơ bản trong số học Modulo như: số nguyên tố, nguyên tố cùng nhau, lý thuyết về đồng dư,. . . , và các định lý quan trọng để áp dụng giải các bài toán về đồng dư trong các thuật toán, giao thức như: định lí Euler, định lí Fermat, định lí phần dư Trung Hoa. Ngoài ra luận văn cũng giới thiệu về logarit rời rạc và căn nguyên thuỷ, một số giao thức mã hóa công khai như: RSA, DSA, Elgamal. 1.1 1.1.1 Số học Mudulo Các số nguyên tố và các số nguyên tố cùng nhau Ta nói rằng b (một số khác 0) là ước số của a nếu a = mb, với một giá trị m nào đó, ở đây a, b, m là các số nguyên. Như vậy, b là ước số của a, nếu như chia a cho b không còn lại số dư. Để kí hiệu b là ước số của a thường sử dụng cách viết b| a. Có các quan hệ sau: 5 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt (1) Nếu a| 1 thì a = 1 hoặc a = −1 (2) Nếu b| a và a| b thì a = b hoặc a = −b (3) Số b bất kỳ khác 0 là ước số của 0 (4) Nếu b| g và b| h, thì b| (mg + nh), trong đó m, n là số nguyên bất kì. Một số nguyên p > 1 được gọi là số nguyên tố, nếu chỉ có −1; 1; −p; p là các ước số. Một số nguyên bất kỳ s > 1 có thể phân tích thành các thừa số và được trình bày dưới dạng: s = pα1 pα2 ...pαt ,, trong đó p1 < p2 < ... < pt là các t 1 2 số nguyên tố, còn các giá trị αi > 0 Một số nguyên dương c là ước chung lớn nhất của hai số nguyên a và b nếu c thỏa mãn: i) c là ước số của a và b ii) Ước số bất kỳ của a và b đều là ước số của c Khi đó ước chung lớn nhất của hai số a và b được ký hiệu là: gcd(a, b) hoặc U CLN (a, b). Theo định nghĩa ta có c = gcd(a, b) hoặc c = U CLN (a, b). Số nguyên a và b được gọi là hai số nguyên tố cùng nhau, nếu ước chung lớn nhất của chúng bằng 1. Nhận xét: (1) UCLN của hai số nguyên là một số dương, bởi vì: gcd(a, b) = gcd(a, −b) = gcd(−a, b) = gcd(−a, −b) (2) Vì tất cả các số nguyên khác không đều là ước số của số 0, chúng ta luôn luôn có: gcd(a, 0) = |a|. (3) Số 1 là nguyên tố cùng nhau với mọi số nguyên (4) Một số nguyên tố là một cặp số nguyên tố với tất cả những số khác loại trừ những số là bội của số đó. 6 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt (5) Cho n số nguyên a1 , a2 , ..., an . Các số này được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của n số đó bằng 1. (6) Nếu a và b là hai số nguyên tố cùng nhau, khi đó tồn tại các số nguyên x và y sao cho ax + by = 1. 1.1.2 Số học trong lớp số dư Cho số nguyên dương b và một số nguyên a bất kỳ, khi chia a cho b ta nhận được một số nguyên q nào đó và số dư r, phù hợp với quan hệ sau: a = qb + r, (0 ≤ r < b) Nếu a là một số nguyên, còn b là một số nguyên dương, thì a mod b, được xác định như phần dư của phép chia a cho b. Như vậy, đối với một số nguyên a bất kỳ có thể viết: a = q × b + (a mod b) 1.1.3 Lý thuyết về đồng dư Định nghĩa 1.1. Cho a, b ∈ Z, n ∈ N . Ta nói a đồng dư với b theo modulo n, khi a và b chia cho n có cùng số dư, và được viết dưới dạng sau: a ≡ b mod n. Tính chất Tính chất 1. Nếu a1 ≡ b1 mod(n); a2 ≡ b2 mod(n) thì: a1 ± a2 ≡ (b1 ± b2 ) mod n Tính chất 2. Nếu a1 ≡ b1 mod(n) và a2 ≡ b2 mod(n) thì: a1 × a2 ≡ (b1 × b2 )mod(n) Tính chất 3. Nếu như gcd(d, n) = 1, a ≡ bmodn, a = a1 d, b = b1 d, thì: a1 ≡ b1 modn. 7 Luận văn Thạc sĩ toán học 1.1.4 Vũ Mạnh Đạt Các số nguyên modulo n Các số nguyên modulo n (ký hiệu Zn ) là tập hợp các số nguyên {0, 1, 2, ..., n − 1} bao gồm 2 phép toán cộng và nhân. Việc cộng và nhân trong Zn được thực hiện giống như cộng và nhân các số nguyên, ngoại trừ một điểm là các kết quả trung gian và cuối cùng sẽ được rút gọn theo modulo n. Các định nghĩa trên phép cộng và phép nhân trong Zn thoả mãn hầu hết các quy tắc quen thuộc trong số học. Sau đây ta sẽ liệt kê mà không chứng minh các tính chất này: (1) Phép cộng là đóng: a + b ∈ Zn , ∀a, b ∈ Zn (2) Phép cộng có tính chất giao hoán: a + b = b + a, ∀a, b ∈ Zn (3) Phép cộng có tính chất kết hợp: (a + b) + c = a + (b + c), ∀a, b, c ∈ Zn (4) 0 là phần tử đơn vị của phép cộng: a + 0 = 0 + a = a, ∀a ∈ Zn (5) Phần tử đối của phép cộng của một phần tử bất kì a ∈ Zn là −a, tức là: a + (−a) = (−a) + a = 0 (6) Phép nhân là đóng: a × b ∈ Zn , ∀a, b ∈ Zn (7) Phép nhân có tính chất giao hoán: a × b = b × a, ∀a, b ∈ Zn (8) Phép cộng có tính chất kết hợp: (a × b) × c = a × (b × c), ∀a, b, c ∈ Zn (9) 1 là phần tử đơn vị của phép nhân: a × 1 = 1 × a = a, ∀a ∈ Zn (10) Phép nhân có tính chất phân phối đối với phép cộng: (a + b) × c = a × c + b × c; a × (b + c) = a × b + a × c, ∀a, b, c ∈ Zn 1.1.5 Hàm Euler, định lý Euler, định lý Fermat Định nghĩa 1.2. Cho n là số nguyên dương, đặt ϕ(n) là số các phần tử của tập hợp các số nguyên trong khoảng [1, n] mà nguyên tố cùng nhau với n, thì ϕ(n) gọi là hàm Euler. 8 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt Ta công nhận một số tính chất quan trọng của hàm Euler: Tính chất 1. ϕ(1) = 1 Tính chất 2. Nếu p là số nguyên tố thì ϕ(p) = p − 1 Tính chất 3. Nếu như p và q là hai số nguyên tố cùng nhau thì: ϕ(pq) = ϕ(p) × ϕ(q) Tính chất 4. ϕ(ps ) = ps−1 (p − 1) Tính chất 5. Nếu như n = pe1 pe2 ...pek , trong đó p1 , p2 , ..., pk là các số 1 2 k nguyên tố khác nhau thì: ϕ(n) = n 1 − 1 p1 1− 1 p2 ... 1 − 1 pk Định lý 1.1. (Định lý Euler) Cho n > 1, gcd(a, n) = 1 và ϕ(n) là hàm Euler. Khi đó ta có: aϕ(n) ≡ 1 mod n Chứng minh: Giả sử x1 , ..., xϕ(n) là các số tự nhiên khác nhau, nhỏ hơn n và nguyên tố cùng nhau với n. Xét tất cả các khả năng của tích xi a, với i ∈ 1, ϕ(n). Bởi vì a nguyên tố cùng nhau với n và xi nguyên tố cùng nhau với n, nên tích xi a cũng nguyên tố cùng nhau với n, do đó có xi a ≡ xj mod (n), chú ý rằng các phần dư của phép chia xi a cho n là khác nhau. Nếu điều này không đúng, có nghĩa là tồn tại i1 = i2 , sao cho: xi1 a ≡ xi2 a mod (n), cho nên (xi1 − xi2 )a ≡ 0 mod n. Bởi vì a nguyên tố cùng nhau với n, nên biểu thức cuối cùng tương đương với: xi1 − xi2 ≡ 0 mod (n) Điều này là mâu thuẫn, bởi các số x1 , ..., xϕ(n) là các cặp khác nhau theo modulo n. Khi đó nhân tất cả đẳng thức xi a ≡ xj mod n thì thu được: x1 ... xϕ(n) aϕ(n) ≡ x1 ... xϕ(n) mod n, hay x1 ...xϕ(n) (aϕ(n) − 1) ≡ 0 mod n Bởi vì số x1 ... xϕ(n) mod n nguyên tố cùng nhau với n nên đẳng thức cuối cùng tương đương với aϕ(n) − 1 ≡ 0 mod n hay aϕ(n) ≡ 1 mod n Hệ quả 1.1. Cho n > 1, gcd(a, n) = 1, và ϕ(n) là hàm Euler. Khi đó ta 9 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt có: aϕ(n)+1 ≡ a mod n Định lý 1.2. (Định lý Fermat) Cho p là số nguyên tố, a là số nguyên dương không chia hết cho p. Khi đó ta có: ap−1 ≡ 1 mod p Chứng minh: Ta có ϕ(p) = p − 1, áp dụng định lý Euler ta có điều phải chứng minh. Hệ quả 1.2. Cho a ∈ Z p là số nguyên tố, thì ta có: ap ≡ a mod p 1.1.6 Thuật toán Euclide mở rộng Định nghĩa 1.3. (phần tử nghịch đảo) Cho a ∈ Zn , phần tử nghịch đảo của a là phần tử b ∈ Zn sao cho a × b ≡ b × a ≡ 1 mod n. Kí hiệu phần tử nghịch đảo của a là a−1 mod n Định lý 1.3. Cho số nguyên a > 0 nguyên tố cùng nhau với n, thì luôn tồn tại phần tử nghịch đảo của a theo modulo n. Chứng minh: Xét tập hợp S = {1, 2, ..., n − 1} (n ≥ 2). Nhân từng phần tử của tập hợp S với a theo modulo n, nhận được tập hợp: S = {a mod n, 2a mod n, ..., (n − 1)a mod n)} Nhận thấy tập S bao gồm các số 1, 2, 3, , (n − 1) (vì khi chia cho n thì số dư trong phép chia nhỏ hơn n), khi đó sẽ tồn tại một số b ∈ S sao cho (b × a) mod n = 1. Ta đi chứng minh b là duy nhất. Thật vậy: Giả sử tìm được hai số b; b ∈ S, sao cho (b × a) mod n = 1 và (b × a) mod n = 1. Mặt khác do a là nguyên tố cùng nhau với n (giả thiết) nên tồn tại số nguyên x và y sao cho: a × x + n × y = 1. Nhân cả hai vế a × x + n × y = 1 với b rồi lấy modulo 10 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt n ta được: (b × a × x) mod n + (b × n × y) mod n = b mod n. Suy ra x = b mod (n). Nhân cả hai vế a × x + n × y = 1 với b rồi lấy modulo n ta được: (b × a × x) mod n + (b × n × y) mod n = b mod n. Suy ra x = b mod n Từ đó suy ra: b mod n = b mod n, mặt khác b; b ∈ S nên suy ra b = b Hệ quả 1.3. Nếu như p là số nguyên tố, thì bất kỳ số a, 0 < a < p, luôn tồn tại phần tử nghịch đảo theo modulo p. Thuật toán Euclide mở rộng (tìm phần tử nghịch đảo) Ta chia a cho b theo thuật toán Euclide như sau: a = bq1 + r1 (0 < r1 < b) ....... rk−2 = rk−1 qk + rk (0 < rk < rk−1 ) Khi đó rk = rk−2 − rk−1 qk , mà rk−1 = rk−3 − rk−2 qk−1 nên rk = rk−2 − rk−1 qk = rk−2 − (rk−3 − rk−2 qk−1 )qk = rk−2 (1 + qk−1 qk ) − rk−3 qk tương tự như thế đến cuối cùng chúng ta có được biểu thức dạng sau: rk = a × x + b × y. Nếu như gcd(a, b) = 1, tức là a × x + b × y = 1, theo định lý trên thì khi đó y là phần tử nghịch đảo của b theo modulo a hay y = b−1 mod a. Ví dụ 1.1. Tính 23−1 mod 262 Ta thực hiện phép chia 262 cho 23 ta được: 262 = 23.11 + 9; 23 = 9 . 2 + 5; 9 = 5 . 1 + 4; 5 = 4 . 1 + 1 Suy ra 1 = 5 – 4 . 1 = 5 – (9 – 5 . 1) . 1 = 5 – 9 + 5 = 5 . 2 – 9 = (23 – 9 . 2) . 2 – 9 = 23 . 2 – 9 . 5 = 23 . 2 – (262 – 23 . 11) . 5 = 23 . 2 262 . 5 + 23 . 55 = 23 . 57 – 262 . 5 Nên phần tử nghịch đảo của 23 modulo 262 là 57, hay 23−1 mod 262 = 57 11 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt Chú ý: Có thể tìm phần tử nghịch đảo được trình bày dưới bảng sau: 1 0 262 0 1 23 11 0 1 23 1 -11 9 2 1 -11 9 -2 23 5 1 -2 23 5 3 -34 4 1 3 -34 4 -5 57 1 Nên phần tử nghịch đảo của 23 modulo 262 là 57, hay 23−1 mod 262 = 57 1.1.7 Định lý phần dư Trung Hoa Định lý 1.4. Giả sử cho các số n1 , n2 , ..., nk là các số nguyên dương nguyên tố cùng nhau từng đôi một và c1 , c2 , ..., ck là các số nguyên khi đó hệ phương trình đồng dư:   x ≡ c1 mod n1       x ≡ c mod n 2 2  ........       x ≡ c mod n k k Có nghiệm duy nhất theo modulo n và nghiệm đó là: k x=( i=1 ci Ni (Ni−1 mod ni ) ) mod (n), trong đó n = n1 n2 ...nk và Ni = n ni Chứng minh: Nếu ta chứng minh hệ trên tương đương với một phương trình sau: x ≡ k x0 mod n ở đây x0 = i=1 ci Ni (Ni−1 mod ni ) thì coi như chúng ta đã chứng minh được định lý trên. Ta có Ni chia hết cho ns , khi s = i. Điều này dẫn đến x0 ≡ Ni (Ni−1 mod ni )ci (modni ), từ đó x0 ≡ ci (modni ). Điều này có nghĩa hệ trên tương 12 Luận văn Thạc sĩ toán học Vũ Mạnh Đạt đương với hệ sau:   x ≡ x0 mod n1       x ≡ x mod n 0 2  ........       x ≡ x mod n 0 k Điều này tương đương với một phương trình sau: x ≡ x0 mod n. Mà ta đã biết phương trình này có nghiệm duy nhất là: x ≡ x0 mod n Ví dụ 1.2. Giải hệ phương trình đồng dư sau:   x ≡ 6 mod 7    x ≡ 8 mod 13     x ≡ 9 mod 17 Lời giải: Ta có n = 7×13×17 = 1547; N1 = n 7 = 221; N2 = n 13 = 119; N3 = n 17 = 91 . Ta đi tính phần tử nghịch đảo của Ni theo modulo ni 221−1 mod 7 = 2; 119−1 mod 13 = 7; 91−1 mod 17 = 3 Khi đó ta có được nghiệm của hệ phương trình là: x = (6 × 221 × 2 + 8 × 119 × 7 + 9 × 91 × 3) mod 1547 = 944 Ngoài ra để tính toán nhanh modulo khi sử dụng định lý phần dư Trung Hoa, người ta dùng thuật toán "bình phương và nhân". Nội dung của thuật toán như sau: Để tính z = xb mod n, ta coi rằng số mũ b được biểu thị ở dạng nhị phân như sau: l b i 2i b= i=0 13