Tài liệu Luận văn một số giao thức chuyển giao không lộ thông tin và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 === === PHAN VĂN ĐƢƠNG MỘT SỐ GIAO THỨC CHUYỂN GIAO KHÔNG LỘ THÔNG TIN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 === === PHAN VĂN ĐƢƠNG MỘT SỐ GIAO THỨC CHUYỂN GIAO KHÔNG LỘ THÔNG TIN VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số: 8 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 - 2018 LỜI CẢM ƠN Luận văn này đƣợc thực hiện tại Trƣờng Đại học Sƣ phạm Hà Nội 2. Để hoàn thành đƣợc luận văn này tôi đã nhận đƣợc rất nhiều sự động viên, giúp đỡ của nhiều cá nhân và tập thể. Trƣớc hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến thầy giáo TS. Trần Văn Dũng – Giảng viên trƣờng ĐHGTVT Hà Nội đã nhiệt tình giúp đỡ, trực tiếp chỉ bảo, hƣớng dẫn tôi trong suốt quá trình thực hiện luận văn cao học. Xin cùng bày tỏ lòng biết ơn chân thành tới các thầy cô giáo trong trƣờng Đại học Sƣ phạm Hà Nội 2, ngƣời đã đem lại cho tôi những kiến thức bổ trợ, vô cùng có ích trong những năm học vừa qua. Cũng xin gửi lời cám ơn chân thành tới Ban Giám hiệu, Phòng Đào tạo sau đại học, Khoa Toán trƣờng Đại học Sƣ phạm Hà Nội 2 đã tạo điều kiện cho tôi trong quá trình học tập. Cuối cùng tôi xin gửi lời cám ơn đến gia đình, bạn bè, những ngƣời đã luôn bên tôi, động viên và khuyến khích tôi trong quá trình thực hiện đề tài nghiên cứu của mình. Hà Nội, ngày 06 tháng 11 năm 2018 Học viên thực hiện Phan Văn Đƣơng LỜI CAM ĐOAN Tôi xin cam đoan: Những số liệu và kết quả nghiên cứu trình bày trong luận văn này là hoàn toàn trung thực, của tôi không vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật Việt Nam. 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 đều đƣợc ghi rõ nguồn gốc. Những kiến thức tôi trình bày trong luận văn này chƣa đƣợc trình bày hoàn chỉnh trong bất cứ tài liệu nào. Hà Nội, ngày 6 tháng 11 năm 2018 Học viên thực hiện Phan Văn Đƣơng MỤC LỤC MỞ ĐẦU ........................................................................................................... 1 1. Lý do chọn đề tài ....................................................................................... 1 2. Mục đích nghiên cứu ................................................................................. 2 3. Nhiệm vụ nghiên cứu................................................................................. 2 4. Đối tƣợng nghiên cứu: ............................................................................... 2 5. Phƣơng pháp nghiên cứu ........................................................................... 3 6. Dự kiến nội dung. ...................................................................................... 3 CHƢƠNG I KIẾN THỨC CƠ SỞ .................................................................... 4 1.1. Số học modulo ........................................................................................ 4 1.1.1. Các phép toán trên modulo .............................................................. 4 1.1.2. Logarit rời rạc ................................................................................... 9 1.2. Hệ mật mã khóa công khai ................................................................... 13 1.2.1. Mã khoá công khai RSA ................................................................ 13 1.2.2. Khởi tạo khóa RSA ........................................................................ 13 1.2.3. Sử dụng RSA .................................................................................. 14 1.2.4. Cơ sở của RSA ............................................................................... 14 1.3. Mã Elgamal ........................................................................................... 15 1.3.1. Hệ mã hóa Elgamal ........................................................................ 15 1.3.2. Khái niệm mã hóa đồng cấu ........................................................... 16 1.4. Chữ ký điện tử DSA ............................................................................. 16 1.4.1. Tạo chữ ký DSA ............................................................................. 17 1.4.2. Kiểm chứng chữ ký DSA ............................................................... 17 Tóm tắt chƣơng I ......................................................................................... 18 CHƢƠNG II MỘT SỐ GIAO THỨC CHUYỂN GIAO KHÔNG LỘ THÔNG TIN ................................................................................................... 19 2.1. Giao thức chuyển giao không lộ thông tin ........................................... 19 2.2. Giao thức chuyển giao không lộ thông tin 1 từ 2 ................................. 21 2.3. Giao thức chuyển giao không lộ thông tin 1 từ n ................................. 24 2.4. Giao thức chuyển giao không lộ thông tin k từ n ................................. 27 Tóm tắt chƣơng II ........................................................................................ 31 CHƢƠNG III MỘT SỐ ỨNG DỤNG CỦA GIAO THỨC CHUYỂN GIAO KHÔNG LỘ THÔNG TIN ............................................................................. 32 3.1. Lƣợc đồ chia sẻ thông tin mật Shamir .................................................. 32 3.1.1. Phân phối mảnh cho các thành viên. ............................................. 33 3.1.2. Khôi phục khoá K từ t thành viên. ................................................. 35 3.2. Giao thức ngƣỡng chuyển giao không lộ thông tin 1 từ n .................... 36 3.3. Ví dụ Giao thức ngƣỡng chuyển giao không lộ thông tin (3, 4)-OT21.39 3.4. Ứng dụng trong lƣợc đồ truy vấn dữ liệu riêng tƣ ............................... 43 3.5. Ứng dụng với truy vấn thích nghi......................................................... 44 Tóm tắt chƣơng III ....................................................................................... 46 KẾT LUẬN ..................................................................................................... 47 TÀI LIỆU THAM KHẢO ............................................................................. 48 1 MỞ ĐẦU 1. Lý do chọn đề tài Ngày nay máy tính ngày càng thể hiện rõ vai trò thiết yếu trong mọi lĩnh vực của xã hội. Nó đã trở thành phƣơng tiện điều hành các hệ thống giúp cho mọi công việc rút ngắn khoảng cách về không gian và thời gian. Chữ ký số ra đời giúp cho doanh nghiệp tiết kiệm rất nhiều thời gian, công sức trong một số công việc giao dịch với ngân hàng, cơ quan hành chính. Hoạt động giao dịch điện tử cũng đƣợc đẩy mạnh. Với mạng máy tính ngày càng phổ biến trên toàn cầu ngƣời ta đã dùng mạng Internet một cách thông dụng. Nhiều dịch vụ điện tử nhƣ: thƣ điện tử, chuyển tiền, thƣơng mại điện tử, chính phủ điện tử… đã đƣợc áp dụng rộng rãi. Do đó yêu cầu về an toàn mạng và an ninh dữ liệu càng trở lên cấp bách và cần thiết. Đặc biệt trên thực tế cần thực hiện các giao thức truyền dữ liệu giữa các bên không tin cậy lẫn nhau, nhƣ chia sẻ thông tin mật giữa một số thành viên (chìa khóa mở tài khoản), cam kết biết một thông tin mật nào đó, chứng minh không tiết lộ thông tin (xác thực danh tính), bầu cử điện tử (lá phiếu và kết quả bầu cử hợp lệ) hay tính toán đa bên an toàn khi các bên che giấu thông tin đầu vào của mình (đấu thầu hợp đồng). Đó là các hƣớng nghiên cứu của các giao thức an ninh nâng cao, khi các bên tham gia không tin cậy lẫn nhau. Cần tạo ra các sơ đồ, môi trƣờng và kỹ thuật trao đổi để các bên phối hợp thực hiện nhiệm vụ chung, nhƣng đảm bảo yêu cầu an ninh cho các bên. Đƣợc sự gợi ý của giáo viên hƣớng dẫn và nhận thấy tính thiết thực của vấn đề em đã chọn đề tài “Một số giao thức chuyển giao không lộ thông tin và ứng dụng” để làm nội dung cho luận văn. Bài toán có nội dung đại thể nhƣ sau: hai ngƣời cần trao đổi thông tin, trong đó một ngƣời cung cấp một số 2 dữ liệu khác nhau và một ngƣời đƣợc quyền lựa chọn và chỉ xem đƣợc một hoặc một số trong số các dữ liệu đó và ngƣời cung cấp cũng không đƣợc biết là ngƣời nhận chọn các dữ liệu nào. Cần phải thiết lập giao thức tức là các qui tắc và các bƣớc thực hiện để giải bài toán đó. 2. Mục đích nghiên cứu - Nghiên cứu cách thức tạo ra một số Giao thức chuyển giao không lộ thông tin. - Ứng dụng vào bài toán thực tế nhƣ: truy xuất dữ liệu đảm bảo tính riêng tƣ, tính toán đa bên an toàn. 3. Nhiệm vụ nghiên cứu - Đọc hiểu tài liệu, trình bày lại một số giao thức chuyển giao không lộ thông tin hiện đại, hiệu quả, chứng minh một số tính chất an ninh của chúng. - Ứng dụng Giao thức chuyển giao không lộ thông tin kết hợp với một số giao thức nâng cao khác nhƣ chia sẻ thông tin mật, cam kết và chứng minh không tiết lộ thông tin thông qua một số ví dụ tự giải theo các bƣớc của giao thức. - Đối tƣợng và phạm vi nghiên cứu: trình bày các giao thức không lộ thông tin 1 từ 2, 1 từ n, k từ n và giao thức chuyển giao không lộ thông tin khắc phục lỗi (t, p), ở đó hai bên chuyển giao thông qua p máy chủ, nhƣng chỉ cần t máy hoạt động. 4. Đối tƣợng nghiên cứu: Nhiều khi trong quá trình trao đổi thông tin giữa hai bên không tin cậy, cần sử dụng một giao thức với hộp đen trung gian giữa hai bên A và B nhƣ sau: bên A gửi vào hộp đen trung gian hai thông điệp M 0 và M1, bên B lựa chọn bit c = 0 hoặc c = 1 rồi gửi đến hộp đen trung gian, tùy thuộc vào lựa chọn c, bên B sẽ nhận đƣợc thông điệp Mc từ hộp đen. Giao thức đảm bảo bên B chỉ nhận đƣợc thông điệp Mc mà không đƣợc nhận thông điệp còn lại, bên A không biết bên B nhận đƣợc thông điệp nào. Giao thức đó đƣợc gọi là giao 3 thức chuyển giao không lộ thông tin 1 từ 2. Sau này các nhà khoa học đƣa ra các định nghĩa khác nhau của giao thức chuyển giao không lộ thông tin nhƣ Giao thức chuyển giao không lộ thông 1 từ n, k từ n, mà ở bên A gửi n thông điệp và B nhận đƣợc 1 hoặc k thông điệp. Ngoài ra giao thức chuyển giao không lộ thông tin (t, p) kết hợp với giao thức chia sẻ thông tin mật để khắc phục lỗi xảy ra trên môi trƣờng mạng. Cụ thể bên A gửi các mảnh thông điệp cho p máy chủ, B sẽ trao đổi với ít nhất t máy chủ để nhận đƣợc thông điệp lựa chọn của mình. 5. Phƣơng pháp nghiên cứu Đọc hiểu, trình bày lại một số giao thức chuyển giao không lộ thông tin hiệu quả và đƣa ra một số ví dụ của mình minh họa cho các giao thức đó, đồng thời cũng sử dụng các giao thức chuyển giao không lộ thông tin trong các giao thức an ninh nâng cao khác nhƣ: chia sẻ thông tin mật, chứng minh không tiết lộ thông tin, tính toán đa bên an toàn và truy suất dữ liệu cá nhân riêng tƣ. 6. Dự kiến nội dung. Luận văn đƣợc chia làm 3 chƣơng cộng với phần mở đầu, kết luận và tài liệu tham khảo. Nội dung trong các dự kiến đƣợc phân bổ nhƣ sau: 4 CHƢƠNG I KIẾN THỨC CƠ SỞ Chƣơng này sẽ trình bày về các lý thuyết toán học để bổ trợ và xây dựng phƣơng pháp bầu cử điện tử dừa trên mã đồng cấu nhƣ lý thuyết về toán học modulo, các bài toán Logarit rời rạc, hệ mã hóa công khai, mã Elgamal cũng nhƣ các định lý Fermat, Euler..v.v. Tiếp đó, luận văn mô tả các khái niệm về chữ ký điện tử DSA cách tạo và cách kiểm chứng chữ ký DSA đƣợc dùng trong việc xây dựng một số giao thức an ninh nâng cao [1, 2, 3]. 1.1. Số học modulo 1.1.1. Các phép toán trên modulo a. Định nghĩa 1.1 Cho m là số nguyên dƣơng. Giả sử a, b là các số nguyên: Ta ký hiệu a º b (mod m), khi và chỉ khi b = a + km trong đó k là số nguyên. Khi đó ta nói a và b đồng dƣ với nhau theo modulo m. Nếu trong đó a là số nguyên dƣơng nhỏ hơn m, thì a đƣợc gọi là phần dƣ của b khi chia cho m, đôi khi a đƣợc gọi là thặng dƣ của b theo modulo m. Tập hợp các sô nguyên từ 0 đến m − 1 đƣợc gọi là tập hợp thặng dƣ hoàn toàn modulo m. Điều này có nghĩa là, với mỗi số nguyên a, thặng dƣ modulo m là một số từ 0 đến m − 1. Modulo số học cũng nhƣ số học bình thƣờng, bao gồm các phép giao hoán, kết hợp và phân phối. Mặt khác, giảm mỗi giá trị trung gian trong suốt quá trình tính toán. (a + b) mod m = ((a mod m) + (b mod m)) mod m (a - b) mod m = ((a mod m) − (b mod m)) mod m (a ´ b) mod m = ((a mod m) ´ (b mod m)) mod m (a ´ (b +c)) mod m = ((a ´ b) + (a ´ c)) mod m Ví dụ 1.1: 10 º 7 (mod 3) vì 10 = 3.3 + 1 và 7 = 2.3 + 1 5 b. Quan hệ đồng dƣ Quan hệ đồng dƣ theo modulo m trên Z là một quan hệ tƣơng đƣơng có nghĩa là: i) a Î Z, a º a (mod m) ii) a, b Î Z, a º b (mod m) b º a (mod m) iii) a, b, c Î Z, a º b, b º c a º c (mod m) (Tính phản xạ) (Tính đối xứng) (Tính bắc cầu) c. Các phép toán trên modulo: Nếu ta có: a1 º a2 (mod n) b1 º b2 (mod n) Thì ta có: · (a1 + b1) º (a2 + b2) (mod n) · (a1 − b1) º (a2 − b2) (mod n) · (a1b1) º (a2b2) (mod n) · , với k nguyên dƣơng 1.1.1.1 Số nghịch đảo Modulo Số nghịch đảo của 10 là 1/10, bởi vì 10 ´ 1/10 = 1. Trong số học modulo thì vấn đề nghịch đảo phức tạp hơn. 4 ´ x º 1 mod 7 Phƣơng trình trên tƣơng đƣơng với tìm x và k sao cho: 4x = 7k + 1 với điều kiện cả x và k đều là số nguyên. Vấn đề chung đặt ra tại đây là tìm x sao cho: 1 = (a ´ x) mod n Có thể viết lại nhƣ sau: a-1 º x (mod n) Ví dụ 1.1: Nghịch đảo của 5 modulo 14 là 3 bởi: 5 ´ 3 = 15 º 1 (mod 14) 6 Trong trƣờng hợp chung a-1 º x (mod n) chỉ duy nhất một lời giải nếu a và n là một cặp số nguyên tố cùng nhau. Nếu a và n không phải là một cặp số nguyên tố cùng nhau, thì a-1 º x (mod n) không có lời giải nào. Thuật toán Euclid có thể mở rộng tính ra đƣợc số nghịch đảo của số modulo n, đôi khi thuật toán này còn gọi là thuật toán Euclid mở rộng. Ví dụ 1.2: Tìm nghịch đảo theo Euclide mở rộng. Tìm số nghịch đảo (nếu có) của 30 theo môđun 101 Bƣớc i m a r q y0 y1 y 0 101 30 11 3 0 1 -3 1 30 11 8 2 1 -3 7 2 11 8 3 1 -3 7 -10 3 8 3 2 2 7 -10 27 4 3 2 1 1 -10 27 -37 5 2 1 0 . . . . Kết quả tính toán trong bảng cho ta −37. Lấy số đối của 37 theo mođun 101 đƣợc 64. Vậy 30-1 mod 101 = 64. 1.1.1.2. Định lý Fermat Nếu m là số nguyên tố và a không phải là bội số của m thì định lý Fermat phát biểu nhƣ sau: am – 1 º 1 (mod m) (xem [1, 2]). Ví dụ 1.3: 27-1 mod 7 = 1 (= 2 6 mod 7 = 64 mod 7 = 1) 35-1 mod 5 = 1 (= 34 mod 5 = 81 mod 5 = 1) 7 1.1.1.3. Định lí Euler Định lí 1: Hàm Euler. Cho n là một số nguyên dƣơng. Khi thực hiện ph p tính đồng dƣ n của mọi số nguyên khác ta nhận đƣợc tập đầy đủ các phần dƣ có thể có là: 0, 1, 2,…, n – 1. Từ tập trên ta tìm tập rút gọn bao gồm các số nguyên tố cùng nhau với n và quan tâm đến số lƣợng các phần tử nhƣ vậy đối với số nguyên dƣơng n cho trƣớc. Ví dụ 1.4: Với n = 10: Tập đầy đủ các phần dƣ là {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Tập rút gọn các phần dƣ nguyên tố với 10 là {1, 3, 7, 9} Số các phần tử của tập rút gọn trên là giá trị của hàm Euler Ф(n). Nhƣ vậy, Ф(10) = 4. Muốn tính Ф(n) việc đếm số các số nguyên tố cùng nhau với n và nhỏ hơn n đƣợc loại bỏ vì đây là bài toán tốn nhiều công sức. Nói chung có thể tính hàm Euler của một số dựa trên biểu thức phân tích ra thừa số của số đó. · Dễ dàng thấy, nếu p là số nguyên tố, thì Ф(p) = p − 1 · Nếu p và q là hai số nguyên tố khác nhau, thì có thể chứng minh đƣợc rằng: Ф (p.q) = (p − 1).(q − 1) · Nếu p là số nguyên tố, thì Ф (p n) = pn – pn - 1 · Nếu s và t là hai số nguyên tố cùng nhau, thì Ф(s.t) = Ф(s).Ф(t). Ví dụ 1.5: Ф(37) = 37 – 1 = 36 Ф(21) = (3–1).(7–1) = 2.6 = 12 Ф(72) = Ф(8.9) = Ф(8). Ф(9) = Ф(2 3). Ф(32) = (23 – 22).(32 – 31) = 4.6 = 24 Định lý Euler là tổng quát hoá của Định lý Ferma, khẳng định nhƣ sau: aF(n) mod n= 1với mọi cặp số nguyên dƣơng nguyên tố cùng nhau a và n: 8 gcd(a,n) =1. Ví dụ 1.6: a = 3; n = 10; Ф(10) = 4; Vì vậy 34 = 81 = 1 mod 10 a = 2; n = 11; Ф(11) = 10; Do đó 210 = 1024 = 1 mod 11 a = 4; n = 15; Ф(15) = 8; Do đó 48 mod 15 = 1, Ta có thể tính trực tiếp 48 mod 15 = (42)4 mod 15 = 1 Nhƣ vậy, cho các số nguyên dƣơng a, n, m bất kỳ, áp dụng tính chất của ph p nhân modulo và Định lý Euler ta luôn có: am mod n = (a mod n)(m modF(n)) mod n Chẳng hạn: 45 18 mod 20 = (45 mod 20)18 mod F(20) mod 20 = 52 mod 20 = 1. 1.1.1.4. Định lí phần dư Trung Hoa Nếu bạn biết cách tìm thừa số nguyên tố của một số n, thì bạn có thể đã sử dụng, một số điều gọi là phần dƣ Trung Hoa để giải quyết trong suốt hê phƣơng trình. Bản dịch cơ bản của định lý này đƣợc khám phá bởi toán học Trung Hoa vào thế k thứ nhất. Định lí 2: Giả sử, sự phân tích thừa số của n = p1´ p2´ …´ pt thì hệ phƣơng trình: (x mod pi) = ai, với i = 1,2….t có duy nhất một nghiệm với x nhỏ hơn n. Bởi vậy, với a, b tùy ý sao cho a < p và b < q (với p, q là số nguyên tố) thì tồn tại duy nhất a, x khi x nhỏ hơn p ´ q thì: x º a (mod p) và x º b(mod q). Để tìm ra x, đầu tiên cần sử dụng thuật toán Euclid để tìm u, u ´ q º 1 (mod p), khi đó cần tính toán: x = (((a − b)xu) mod p).q + b Ví dụ 1.7: Cho hai số nguyên dƣơng p, q nguyên tố cùng nhau. Chứng minh rằng tồn tại số nguyên k sao cho (pq−1) n.k + 1 là hợp số với mọi số nguyên dƣơng n. 9 Lời giải: X t hệ đồng dƣ nên theo định lí phần dƣ Trung Hoa thì hệ này chắc chắn có nghiệm. Nếu n chẵn, thì (pq−1)n.k + 1 ≡ k + 1 ≡ −1 + 1= 0 (mod q), suy ra (pq−1)n.k + 1 là hợp số. Nếu n lẻ, thì (pq−1)n.k + 1 ≡ −k + 1 ≡ −1 + 1 = 0 (mod p), suy ra (pq −1)n.k +1 là hợp số. Vậy luôn tồn tại số k sao cho (pq −1)n.k + 1 là hợp số với mọi số nguyên dƣơng n. 1.1.2. Logarit rời rạc 1.1.2.1. Bài toán logarit trên trường số thực R Định nghĩa 1.2: Cho hai số dƣơng a, b với a ¹ 1. Số x thỏa mãn đẳng thức b = ax đƣợc gọi là logarit cơ số a của b và đƣợc ký hiệu là x = logab. Nhƣ vậy ta có: - Bài toán thuận: b = ax (a,x Î R) - Bài toán ngƣợc: x = logab (a,b > 0, a ¹ 1) Một số tính chất của hàm logarit: Với a, b, c, d > 0, a ¹ 1, a Î R, ta có: y = loga1 = 0 y = logaa = 1 y = loga(aa) = a y = loga(c.d) = log a|c| + loga|d| y = loga(c/d) = log a|c| − loga|d| 1.1.2.2. Bài toán logarit trên trường hữu hạn X t vành số Zp, với p là số nguyên tố, vậy ta có Zp= GF(p). Tất cả các phần tử a ¹ 0 của trƣờng tạo thành nhóm nhân: . 10 Nếu cấp của a bằng p thì ta nói a là căn nguyên thủy của Zp X t bài toán thuận: Cho y = ax Ví dụ 1.8: Cho p = 19, a = 2. Ta tính y = a x mod 19 với x Î Zp= GF(p), dễ dàng thấy 2 là căn nguyên thủy và các giá trị đƣợc cho bởi bảng sau: Tính y = 2x mod 19, các cặp nghịch đảo Z19 x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2x 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 Nhận xét: - Do a là phần tử nguyên thủy nên ax sẽ đi qua hết các phần tử trong vành Zp. - Từ phần tử nguyên thủy a = 2 đã cho ban đầu ta có thể tìm đƣợc các phần tử nguyên thủy khác theo công thức b = ai mod n với (i,j(n)) = 1. Vậy tập các phần tử nguyên thủy của Z19 là: {2, 13, 14, 15, 3, 10}. - Các phần tử nguyên thủy tạo thành các cặp nghịch đảo: 2 = 10-1 (do2.10 mod19 = 1) 13 = 3-1 (do 3.13mod19 = 1) 14 = 15 -1 (do14.15mod19 = 1) X t bài toán ngƣợc: y = loga x với a, x Î Z *p . Dựa trên tính chất các hàm logarit ta có: y = loga bc = (log a b + loga c) mod (p y = loga b/c = (log a b log a c) mod (p 1) 1) 11 y = log a 1 = p 1= 0 Ví dụ 1.9: Cho p = 19, a =2. Ta tính y = log ax mod19 với x Î Zp= GF(p). Từ bảng đã tính ở trên ta có các giá trị ngƣợc: x 1 2 3 4 2x 2 4 8 16 13 7 Log2x 18 1 13 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 14 9 18 17 15 11 3 16 14 6 3 8 17 12 15 5 6 12 5 10 1 7 11 4 10 9 Do 218 = 1 vậy nên ta có log2 1 = 18; 21 = 2, vậy nên ta có log2 2 = 1, tƣơng tƣ ta tính đƣợc các phần tử y = log2 x khác. 1.1.2.3. Bài toán logarit rời rạc Cho Zp, với p là số nguyên tố, a là phần tử nguyên thủy a Î Z *p . Hãy tìm: Y = logax với a, x Î Z *p Nhận xét: với a, x Î Z *p thì bài toán: y = log ax có nghiệm khi a là phần tử nguyên thủy, bài toán có thể không có nghiệm khi a bất kỳ. Ví dụ 1.10: Giải bài toán với p = 19, ta có 6 điểm nguyên thủy (3 cặp nghịch đảo). Tacó: X t cặp nguyên thủy (2, 10): Ta có: log10 x = p −1 – log2 x với p = 19 ta lập đƣợc bảng: 12 Bảng 2.3 Tính các logarit rời rạc y = log2 x mod 19 và y = log10 x modulo 19 x 1 2 3 2x 2 4 8 Log 2 1 x 8 1 Log 1 1 1 0x 7 8 1 3 5 4 5 1 1 6 3 2 1 6 6 7 1 1 6 4 2 4 7 1 4 8 9 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 1 1 1 1 8 7 5 1 3 6 1 1 1 7 2 5 5 7 1 6 3 1 1 3 1 9 6 3 8 1 1 1 2 5 0 1 2 1 1 7 5 4 1 4 1 0 1 0 8 1 9 9 1.1.2.4. Bản chất của bài toán logarit rời rạc Từ những ví dụ trên ta rút ra đƣợc những kết luận sau: Logarit rời rạc là sƣ tiếp nối của ph p tính logarit trên trƣờng số thực vào các nhóm hữu hạn. Chúng ta đã biết với 2 số thực x, y và cơ số a > 0, a ¹ 1, nếu a x thì x đƣợc gọi là logarit cơ sô a của y, ký hiệu là: x = log a y. Tuy nhiên trong logarit rời rạc, các số a, x, y đều là các phần tử của nhóm hữu hạn. Logarit rời rạc có ứng dụng trong hê mã khóa công khai hê mật mã Elgamal. Cho p là một số nguyên tố. X t nhóm nhân các số nguyên modulo p: Z *p = {1,2,3,…,p-1} với phép nhân modulo p. Nếu ta tính lũy thừa bậc k của một số trong nhóm rồi rút gọn theo modulo p thì ta đƣợc một số trong nhóm đó. Quá trình này gọi là lũy thừa rời rạc modulo p. Chẳng hạn p = 17, lấy a = 3, k = 4, ta có: 34 = 81 º 13(mod17). Logarit rời rạc là ph p tính ngƣợc lại: biết 3k º 13(mod17), hãy tìm k. Để giải chúng ta phải thông qua phép thử lần lƣợt tính lũy thừa rời rạc, chẳng hạn tính 32 mod 17 = 9, 33 mod 17 = 10, 34 mod 17 = 13 và tìm đƣợc k = 4. 13 Nhƣ vậy bài toán logarit rời rạc là bài toán khó. 1.2. Hệ mật mã khóa công khai 1.2.1. Mã khoá công khai RSA RSA là mã công khai đƣợc sáng tạo bởi Rivest, Shamir & Adleman ở MIT (Trƣờng Đại học Công nghệ Massachusetts) vào năm 1977. RSA là mã công khai đƣợc biết đến nhiều nhất và sử dụng rộng rãi nhất hiện nay. Nó dựa trên các ph p toán lũy thừa trong trƣờng hữu hạn các số nguyên theo modulo nguyên tố. Cụ thể, mã hóa hay giải mã là các ph p toán luỹ thừa theo modulo số rất lớn. Việc thám mã, tức là tìm khóa riêng khi biết khóa công khai, dựa trên bài toán khó là phân tích một số rất lớn đó ra thừa số nguyên tố. Nếu không có thông tin gì, thì ta phải lần lƣợt kiểm tra tính chia hết của số đó cho tất cả các số nguyên tố nhỏ hơn căn của nó. Đây là việc làm không khả thi. Ngƣời ta chứng minh đƣợc rằng, ph p lũy thừa cần O((log n)3) phép toán, nên có thể coi lũy thừa là bài toán dễ. Cần chú ý rằng ở đây ta sử dụng các số rất lớn khoảng 1024 bit, tức là cỡ 10350. Tính an toàn dựa vào độ khó của bài toán phân tích ra thừa số các số lớn. Bài toán phân tích ra thừa số yêu cầu O(elogn log logn) ph p toán, đây là bài toán khó. Mã công khai RSA gồm hai giai đoạn: khởi tạo khóa RSA và giai đoạn mã hóa/giải mã. 1.2.2. Khởi tạo khóa RSA Mỗi ngƣời sử dụng A tạo một cặp khóa công khai – riêng nhƣ sau: Chọn ngẫu nhiên hai số nguyên tố lớn p và q khác nhau. Tính số N làm modulo của hệ thống: N = p.q. Ta đã biết Ф(N) = (p 1)(q 1). Chọn ngẫu nhiên khóa mã e làm khóa công khai, sao cho 1 < e < Ф(N) và gcd (e,Ф(N)) = 1, tức là e và Ф(N) là hai số nguyên tố cùng nhau. Nghịch đảo của e theo modulo Ф(N) là khóa riêng d, vậy tìm d từ 14 phƣơng trình (e.d) mod Ф(N) = 1, với 0 < d < Ф(N) hay d = e -1mod Ф(N). Chú ý: Vai trò của e và d c th thay đổi cho nhau, tức là c th lấy e làm khóa mật, khi đ tính d nghịch đảo của e làm khóa công khai. Ngƣời sử dụng A in khóa mã công khai: KU = {e, N} và thông báo cho mọi ngƣời biết. Ngƣời sử dụng A giữ bí mật khóa riêng: KR = {d, p, q}. 1.2.3. Sử dụng RSA Để mã hóa mẩu tin M, ngƣời gửi B: Lấy khóa công khai của ngƣời nhận A: KU = {e, N}. Mã hóa thông điệp M bằng khóa công khai của ngƣời nhận A: C = Me mod N, trong đó 0 ≤ M < N. Để giải mã bản mã, ngƣời sử dụng A: Sử dụng khóa riêng KR = {d, p, q}. Giải mã thông điệp, tính M = Cd mod N. Lƣu ý rằng bản tin M < N, do đó khi cần chia khối bản rõ thành các khối nhỏ để thỏa mãn tính chất này. 1.2.4. Cơ sở của RSA Ta sẽ chứng minh rằng: Cd mod N = M. Thật vậy, ta có e và Ф(N) nguyên tố cùng nhau, nên tồn tại số nghịch đảo d, tức là: (e.d) mod Ф(N) = 1, Do đó tồn tại số nguyên dƣơng k nào đó, sao cho e.d = 1 + k.Ф(N), Suy ra Cd = (Me)d = M1 + k.Ф(N) = M1.M k.Ф(N), Vì dựa theo định lý Euler có thể chứng minh đƣợc rằng M Ф(N) mod N = 1 Nên Cd Mod N = M1.M k.Ф(N)mod N = M1 mod N.(MФ(N) mod N)k = M.1 mod N = M. Ví dụ 1.11: Tạo khóa công khai cho ngƣời sử dụng A, sau đó ngƣời sử dụng B dùng khóa công khai của A mã hóa thông điệp gửi cho A và cuối cùng A sử