Tóm tắt Luận án Các hệ mật dựa trên vành đa thức chẵn

n cứng lẫn phần mềm. Trong khi đó các vành đa thức 2[ ] ( 1) n nR Z x x  chủ yếu được ứng dụng trong mã sửa sai. Chỉ từ năm 2002, tại Việt Nam, lớp các vành chẵn tuyệt đối | 2knR n  , ký hiệu là 2kR mới được sử dụng để xây dựng một số hệ mật khóa bí mật và hàm băm. 1.2.2. Các hệ mật khoá công khai dựa trên vành đa thức Tại Việt Nam, hệ mật khóa công khai đầu tiên dựa vành đa thức nR được đưa ra năm 2005 thực chất là một biến thể của hệ mật Mc.Eliece, trong đó mã Goppa được thay thế bằng một mã cyclic cục bộ kết hợp với một mã kiểm tra chẵn. Ở nước ngoài, việc sử dụng các vành đa thức , [ ] ( 1) n n q qR Z x x  để xây dựng các hệ mật khóa công khai được 6 khởi xướng từ những năm 1995 khi hệ mật NTRU lần đầu tiên được giới thiệu tại Crypto’96. NTRU có nhiều biến thể trên các cấu trúc đại số khác nhau nhưng đáng chú ý là hai biến thể hoạt động trên các vành đa thức là CTRU hoạt động trên các vành nR và pNE trên vành , , 2 k n qR n  . 1.3. CÁC VẤN ĐỀ MỞ VÀ TIỀM NĂNG ỨNG DỤNG CỦA VÀNH ĐA THỨC CHẴN TRONG MẬT MÃ 1.3.1. Các vấn đề chung với các hệ mật trên vành đa thức Qua các phân tích nêu trên có thể thấy ứng dụng vành đa thức nR nói chung và vành đa thức chẵn 2nR nói riêng trong mật mã còn nhiều hạn chế. Cụ thể là: i. Mới chỉ có các vành đa thức chẵn tuyệt đối 2k R được sử dụng để xây dựng các hệ mật; ii. Chưa có các hệ mật có độ an toàn ngữ nghĩa dựa trên các vành đa thức 2nR (trừ hệ mật pNE); iii. Các phần tử thặng dư bậc hai và lớp các phần tử liên hợp của chúng trên vành đa thức chẵn 2nR hoàn toàn chưa được sử dụng trong mật mã (mới chỉ được ứng dụng trong mã sửa sai); iv. Hầu hết các hệ mật khóa công khai dựa trên các bài toán khó truyền thống hiện nay có hiệu năng tính toán không cao; v. Các hệ mật dựa trên vành đa thức ,n qR điển hình như NTRU có hiệu năng tính toán tốt nhưng vẫn chưa thực sự phù hợp cho các hệ thống có tài nguyên tính toán hạn chế vì khóa và hệ số mở rộng bản tin vẫn khá lớn. 7 1.3.2. Các tiềm năng ứng dụng của vành đa thức chẵn Các vành đa thức nói chung và vành đa thức chẵn 2nR nói riêng có một số đặc điểm phù hợp với các ứng dụng trong mật mã, cụ thể là: i. Trong nR , các phép cộng và nhân đa thức đều chỉ có độ phức tạp tính toán thấp lần lượt là ( )O n hoặc 2( )O n . ii. Trong các vành đa thức chẵn 2nR , có 2 n thặng dư bậc hai, mỗi thặng dư bậc hai đó lại có đến 2n căn bậc hai, hay còn gọi là các phần tử liên hợp. Nếu biết một căn bậc hai sẽ tính được thặng dư bậc hai tương ứng nhưng điều ngược lại sẽ phải thử 2n phương án. Đặc điểm này hoàn toàn có thể khai thác để xây dựng các hệ mật; iii. Trong các vành chẵn 2nR luôn tồn tại các phần tử khả nghịch bên cạnh những phần tử không khả nghịch. Nếu xác định được các thuật toán mật mã phù hợp, các phần tử khả nghịch sẽ chính là khóa để giải mã thông tin tương tự như trường hợp của hệ mật NTRU. 1.4. KẾT LUẬN CHƯƠNG Qua các phân tích trên có thể thấy vành đa thức chẵn 2nR nói riêng và vành đa thức nói chung vẫn còn nhiều tiềm năng có thể khai thác cho các ứng dụng mật mã. Trong chương sau, các kết quả toán học về vành 2nR sẽ được phân tích chi tiết hơn làm cơ sở xây dựng các hệ mật trên nền tảng toán học này. 8 CHƯƠNG 2. VÀNH ĐA THỨC CHẴN 2.1. MỞ ĐẦU CHƯƠNG Trong chương này, một số kết quả toán học mới về vành đa thức chẵn 2nR và một số lớp vành đặc biệt như vành chẵn tuyệt đối 2kR và vành chỉ có hai lớp kề cyclic 2CR sẽ được mô tả làm tiền đề cho các hệ mật ở chương sau. Các kết quả này được tổng hợp từ các nội dung nghiên cứu về cơ sở toán học trong toàn bộ 6 công trình đã công bố của nghiên cứu sinh. 2.2. VÀNH ĐA THỨC CHẴN, CÁC THẶNG DƯ BẬC HAI VÀ CÁC PHẦN TỬ LIÊN HỢP Bổ đề 2-1 2nR 1 0 n i ii l l x    2f: Trong , nếu là căn bậc hai chính của 2 1 0 n i ii f f x    ( )mod 2i i i nl f f  với , thì . Bổ đề này cho thấy độ phức tạp của phép khai căn chỉ là ( )O n tương đương với phép XOR. Phép khai căn này sẽ được sử dụng trong thuật toán mã hóa của hệ mật QRHE (mục 3.3). Bổ đề 2-2 2nR t t U k x  : Trong , đa thức trong biểu thức (1 )ng x k f    (2.1) ik ,0 i 1i i nk f n    ifcó các hệ số được xác định bởi , trong đó 2 1 0 n i ii f f x   là các hệ số của đa thức . Bổ đề này cho phép xác định các phần tử liên hơp của một thặng dư bậc hai là bình phương của một đa thức bất kỳ trong vành đa thức chẵn. Công thức này sẽ được sử dụng trong thủ tục tạo khóa của hệ mật QRHE (mục 3.3). 9 2.3. VÀNH ĐA THỨC CHẴN TUYỆT ĐỐI 2k R 2k f R fĐịnh lý 2-1: Mọi đa thức là khả nghịch khi và chỉ khi có trọng số lẻ. Bổ đề này chứng minh rằng 2k R là một vành đa thức đặc biệt, trong đó một nửa số phần tử của vành là khả nghịch và mọi phần tử này đều có thể sử dụng làm khóa bí mật cho các hệ mật. Tập các phần tử khả nghịch này sẽ được sử dụng làm khóa cho các hệ mật RISKE (mục 3.2), IPKE (mục 3.4) và DTRU (mục 4.2). Thuật toán 2-1 g f: Thuật toán tính nghịch đảo của một đa thức 2k Rkhả nghịch trong . VÀO: Đa thức 2k f R . RA: Đa thức 2k g R , 1g f  . THUẬT TOÁN: g f ; 2a f ; for 1i  to 1k  { if 1g f  exit; g g a  ; 2a a ; }. Thuật toán này có số bước lặp tối đa là ( 1)k  . 2.4. NGHỊCH ĐẢO MỞ RỘNG TRONG nR VỚI n LẺ Định nghĩa 2-1 nR n f: Trong với lẻ, một đa thức được gọi ng Rlà “khả nghịch mở rộng” nếu tồn tại một đa thức thỏa mãn 0 1ng f e   g f và được gọi là nghịch đảo mở rộng của . Trong 0neđó là lũy đẳng nuốt của vành. 10 nR n k Định lý 2-2: Trong với lẻ, giả sử là nghịch đảo mở c m  ( )w mrộng của , nếu biết và , ta có thể tính được 0( )mod 2. nm w m e k c   . (2.2) Với bổ đề này, ta có thể sử dụng một phần tử nghịch đảo mở rộng làm khóa bí mật vẫn giải mã được m từ c m k  . Công thức này sẽ được sử dụng trong thủ tục giải mã của hệ mật E-RISKE (mục 4.3). 2.5. VÀNH ĐA THỨC CHỈ CÓ HAI LỚP KỀ CYCLIC 2CR 2,n CR n N fĐịnh lý 2-3: Trong , mọi đa thức là khả nghịch khi và f 2CKchỉ khi có trọng số lẻ và, hệ quả là , tỉ lệ giữa số phần tử khả 2 ,CRnghịch trên tổng số đa thức trong đạt cực đại. Bổ đề này chứng minh rằng 2CR là một vành đa thức đặc biệt, trong đó một nửa số phần tử của vành là khả nghịch và các phần tử này có thể sử dụng làm khóa bí mật cho các hệ mật. Hệ quả của bổ đề này là tất cả các phần tử có trọng số chẵn của vành 2CR đều là các phần tử khả nghịch mở rộng. Đây cũng là cơ sở để xây dựng hệ mật E- RISKE (mục 4.3). 2.6. KẾT LUẬN CHƯƠNG Kết quả nổi bật nhất trong chương này là nghiên cứu sinh đã chứng minh hai loại vành đa thức đặc biệt ( 2k R , 2CR ) có tỉ lệ giữa số phần tử khả nghịch trên tổng số đa thức của vành là cực đại (Định lý 2-1, Định lý 2-3) và đã đề xuất được một thuật toán hiệu quả để xác định nghịch đảo của các phần tử khả nghịch trên vành 2k R (Thuật toán 2-1). Các kết quả này là cơ sở để đề xuất các hệ mật RISKE (mục 3.2), IPKE (mục 3.4) và DTRU (4.2). 11 Một kết quả đáng chú ý khác của nghiên cứu sinh là chỉ ra trong các vành đa thức 2nR với n lẻ còn tồn tại một lớp phần tử đặc biệt, các phần tử khả nghịch mở rộng có đặc tính tương đồng với các khả nghịch truyền thống (Định nghĩa 2-1). Các phần tử này cũng có thể được sử dụng làm khóa trong các hệ mật (Định lý 2-2) tương tự như các phần tử khả nghịch truyền thống. Kết quả này cho phép linh hoạt trong lựa chọn vành đa thức nền tảng để xây dựng các hệ mật và được cụ thể hóa bằng một hệ mật E-RISKE (mục 4.4) hoạt động cả trên 2CR , một cải tiến của hệ mật RISKE vốn chỉ hoạt động trên 2kR . Ngoài ra, hai công thức tính căn bậc hai chính và phần tử liên hợp của một thặng dư bậc hai trong vành 2nR được nghiên cứu sinh xây dựng (Bổ đề 2-1, Bổ đề 2-2) là nền tảng quan trọng để đề xuất hệ mật lai ghép QRHE trong mục 3.3. 12 CHƯƠNG 3. CÁC HỆ MẬT DỰA TRÊN VÀNH ĐA THỨC CHẴN 3.1. MỞ ĐẦU CHƯƠNG Trong chương này, luận án đề xuất ba hệ mật mới dựa trên vành đa thức chẵn 2nR bao gồm bao gồm RISKE, QRHE và IPKE tương ứng với ba công trình [C2], [J1] và [J3] của nghiên cứu sinh. Các hệ mật được mô tả tường minh từ ý tưởng xây dựng cho đến các thuật toán (tạo khóa, mã hóa và giải mã) cũng như được đánh giá về hiệu năng và độ an toàn với một số tấn công phổ biến. 3.2. HỆ MẬT KHÓA BÍ MẬT RISKE 3.2.1. Giới thiệu Theo Định lý 2-1, tất cả các đa thức có trọng số lẻ trong vành đa thức chẵn tuyệt đối 2k R là khả nghịch. Ý tưởng ở đây là, nếu dùng một phần tử khả nghịch ngẫu nhiên làm khóa bí mật thì không gian khóa sẽ đủ lớn để kẻ tấn công không thể vét cạn khóa với hệ mật này. Bên cạnh đó, nếu thuật toán mã hóa chỉ sử dụng phép nhân đa thức thì hệ mật này sẽ có độ phức tạp tính toán chỉ là 2( )O n . Để xây dựng hệ mật RISKE, Alice và Bob thống nhất một số nguyên dương k để xác định vành đa thức , 2knR n  và một số nguyên 2 kN  để xác định độ dài khóa bí mật. 3.2.2. Thủ tục tạo khóa Với | 0 deg{ 1}nI s N    , Alice và Bob chia sẻ một đa thức khả nghịch ngẫu nhiên s làm khóa bí mật chung. Do deg 1s N  ta có thể biểu diễn s bằng N bit. Điều kiện deg 0s  để đảm bảo không thể dùng 1s  làm khóa bí mật trong RISKE. Hệ quả là, kích thước không gian khóa 12 1N  . 13 3.2.3. Thủ tục mã hóa Mỗi phiên mã hóa 1n  bit bản rõ m nào đó, Alice sử dụng thủ tục tạo khóa trên để tạo và chia sẻ với Bob một khóa ngẫu nhiên mới s . Tiếp theo, Alice tính n bit   1( ) 1 mod 2. nM w m x m   sau đó tính n bit bản mã .c M s  3.2.4. Thủ tục giải mã Để giải mã n bit bản mã c , đầu tiên Bob tính n bit 1M c s  trong đó 1s là nghịch đảo của s trong 2k R tính bằng Thuật toán 2-1. Tiếp đó Bob khôi phục ( 1)n  bit bản rõ 11. n nm M x M    với 1nM  là hệ số ứng với đơn thức 1nx  trong biểu diễn đa thức của M . 3.2.5. Phân tích độ an toàn lý thuyết của RISKE Kẻ tấn công có thể sử dụng phương pháp vét cạn để tìm khóa bí mật s . Tuy nhiên, với độ an toàn khóa 2 1N  xác suất để đoán đúng khóa là 1/ (2 1)N  . Đây một hàm không đáng kể của N nên có thể coi RISKE là an toàn đối với loại tấn công này. Về lý thuyết, có thể sử dụng tấn công vét cạn để tìm bản rõ nhưng điều này là không thực tế vì trong RIKSE độ an toàn bản rõ là 12n còn lớn hơn cả độ an toàn khóa. Ngoài ra, RISKE còn có độ an toàn ngữ nghĩa IND-CPA (được chứng minh chi tiết trong định lý 3-2 của luận án). 3.2.6. Phân tích hiệu năng lý thuyết của RISKE Ưu điểm quan trọng của RISKE là độ phức tạp tính toán thấp, cả thuật toán mã hóa và giải mã chỉ sử dụng một phép cộng và nhân đa thức trong vành đa thức chẵn tuyệt đối 2k R với độ phức tạp tính toán 14 2( )n . So với hệ mật OTP, khóa bí mật s trong RISKE có độ dài N nhỏ hơn độ dài n của bản rõ. Tương tự OTP, nhược điểm của RISKE là phải thay đổi khóa ngẫu nhiên mới s theo từng phiên. Vì lý do này, RISKE nên được sử dụng kết hợp với một hệ mật khóa công khai nào đó để xây dựng một hệ mật lai ghép theo mô hình KEM/DEM. Ngoài ra, nếu hệ mật khóa công khai được chọn có hệ số mở rộng bản tin lớn, ta có thể điều chỉnh N và n để giảm giá trị này. 3.3. HỆ MẬT LAI GHÉP QRHE 3.3.1. Giới thiệu Mọi đa thức trong 2nR , tương ứng với mọi bản tin 2n bit, luôn có thể biểu diễn dưới dạng (1 )nm x k l    trong đó, 2l m và t t U k x   đều là các đa thức bậc tối đa ( 1)n  và được biểu diễn bởi các chuỗi n bit. Ý tưởng chính ở đây là, nếu coi k là một khóa bí mật và che giấu khóa này bằng một hệ mật khóa công khai nào đó theo mô hình KEM/DEM thì (1 )nl x k m    là một bản mã mà nếu không biết k sẽ không dễ phát hiện ra m từ l vì có đến 2n phương án phải thử sai. 3.3.2. Sơ đồ hệ mật lai ghép QRHE Sơ đồ hệ mật lai ghép QRHE (Quadratic Residue Hybrid Encryption scheme) được mô tả chi tiết trong Hình 3-1. 15 DEM DEM 1,i c Alice i m Bob Thám mã KEM i k 2,ic KEM t t U x   ik i m 1, (1 )n i i c k x   2 i m Hình 3-1: Sơ đồ hệ mật QRHE 3.3.3. Thủ tục tạo khóa Với 2n bit bản rõ im , dựa trên Bổ đề 2-2, Alice sẽ tính n bit khóa bí mật ik với ( )ij i j nk m  . Khóa bí mật này sau đó sẽ được mã hóa bằng một hệ mật khóa công khai nào đó (phần KEM), ví dụ như hệ mật RSA để tạo từ mã 2,ic . Kích thước của 2,ic còn phụ thuộc vào hệ mật khóa công khai được chọn. 3.3.4. Thủ tục mã hóa Bằng Bổ đề 2-1, Alice sẽ xác định được các hệ số của bản mã 1,ic với 1, ( )( )mod 2 | 0 1ij ij i j nc m m j n     . Tiếp đó Alice gửi cặp bản mã 1,ic và 2,ic gửi tới Bob. 3.3.5. Thủ tục giải mã Khi nhận được cặp bản mã 1, 2,( , )i ic c , Bob sẽ: 1) Sử dụng thuật toán giải mã của phần KEM tính ik từ 2,ic ; 2) Sử dụng ik để tính im từ 1,ic với 16 1, ( ) ( )mod 2 | 0 1 | 2 1. ij ij ij ij i j n m c k j n m k n j n          3.3.6. Phân tích độ an toàn lý thuyết của QRHE Với độ an toàn khóa 2n , xác suất để kẻ tấn công đoán đúng khóa là 2 n là một hàm không đáng kể của biến n nên có thể coi là an toàn với tấn công này. Trên thực tế cần chọn 1024n  và cỡ khoảng 4096 (tương ứng với độ dài bit của giá trị modulus được khuyến nghị của hệ mật RSA trên thực tế. Về lý thuyết, có thể sử dụng tấn công vét cạn để tìm bản rõ nhưng điều này là không thực tế vì trong QRHE, độ an toàn bản rõ còn lớn gấp đôi độ an toàn khóa. Để tránh được các tấn công EAV và CPA, cần lựa chọn KEM là các hệ mật xác suất, ví dụ OAEP-RSA. Ngoài ra, để khắc phục nhược điểm này, có thể sử dụng QRHE ở chế độ CBC. 3.3.7. Phân tích hiệu năng lý thuyết của QRHE Các thuật toán tạo khóa, mã hóa và giải mã của QRHE đều chỉ là các phép cộng đa thức trong 2nR với độ phức tạp tính toán ( )O n dễ dàng thực hiện bằng phần cứng và phần mềm. 3.4. HỆ MẬT KHÓA CÔNG KHAI IPKE 3.4.1. Giới thiệu Việc sử dụng các phần tử khả nghịch trên vành ,n qR trong mật mã khóa công khai đã được hiện thực hóa với hệ mật NTRU. Tuy nhiên, NTRU phải lưu tới hai khóa bí mật, hệ số mở rộng bản tin trong khá cao (khoảng từ 3 đến 5) và chưa có độ an toàn ngữ nghĩa. Vấn đề đặt ra là có thể xây dựng một hệ mật khóa công khai trên vành đa thức chẵn để khắc phục những hạn chế này. 17 Quay trở lại với RISKE, hệ mật này sử dụng một khóa bí mật s khả nghịch nào đó trong vành đa thức 2k R để che dấu bản rõ M bằng bản mã c M s  và khôi phục lại 1M s c  với 1s là nghịch đảo của s . Trong trường hợp s không khả nghịch sẽ không thể tìm M một cách dễ dàng bằng cách tính 1M s c  . Ý tưởng, ở đây là thay vì chọn s là một khóa khả nghịch và giữ bí mật, liệu có thể sử dụng một đa thức không khả nghịch h trong 2k R làm khóa công khai để che dấu bản rõ bằng phép nhân đa thức c h M  mà vẫn giải mã được bản rõ M nếu biết một cửa sập bí mật nào đó. Với ý tưởng như vậy, trong mục này, nghiên cứu sinh sẽ đề xuất một phương pháp xây dựng hàm cửa sập dựa trên các phần tử khả nghịch trong 2k R qua đó đề xuất một hệ mật khóa công khai có tên là IPKE có thủ tục tính toán đơn giản, chỉ sử dụng một khóa bí mật có kích thước nhỏ, hệ số mở rộng bản tin thấp và có độ an toàn IND-CPA. Để xây dựng hệ mật, Alice và Bob thống nhất chọn một số nguyên dương k xác định vành đa thức nền tảng và một số nguyên dương 2kp  xác định độ dài bản rõ m . 3.4.2. Thủ tục tạo khóa Để tạo khóa, Bob chọn ngẫu nhiên hai đa thức khác zero 121 2 , ks Rs  để tính 12 1 2 k s s x s     . Tiếp đó, Bob sử dụng Thuật toán 2-1 để tính 2k bit khóa bí mật  với đầu vào s . Cuối cùng Bob tính 2k bit khóa công khai ( 1) ph s x   và gửi h tới Alice. Lưu ý rằng, do khóa s cần phải thay đổi theo phiên nên h cũng cần thay đổi theo từng phiên để đảm bảo khả năng chống tấn công CPA. 18 3.4.3. Thủ tục mã hóa Để mã hóa ( 1)p  bit bản rõ m , Alice đầu tiên tính p bit   1( ) 1 mod 2. pM w m x m   sau đó tính p bit bản mã c M h  và gửi c tới Bob. 3.4.4. Thủ tục giải mã Khi nhận được bản mã c , Bob dùng khóa bí mật  tính d c  và khôi phục p bit M bằng cách tính 1 0 p i ii M d x    với , [0, 1]id i p  là các hệ số của đa thức d trong biểu diễn 2 1 0 k i ii d d x    . Cuối cùng, từ d, Bob tính ( 1)p  bit bản rõ 1 1. p pm M x M    với 1pM  là hệ số ứng với đơn thức 1px  trong biểu diễn đa thức của M . 3.4.5. Phân tích độ an toàn lý thuyết của IPKE Kẻ tấn công nhận được c có thể thử vét cạn 2 p bản rõ m cho đến khi đạt được m h c  hoặc thử vét cạn 11 2 2 22 2 k k kS   khóa bí mật  cho đến khi 121 k h x     . Với 11k  và 1023p  thì độ an toàn khóa và độ an toàn bản rõ của IPKE lần lượt là 10232 và 2047 1024(2 2 ) xác suất để kẻ tấn công vét cạn khóa và bản tin là không đáng kể và có thể coi IPKE là an toàn với các tấn công kiểu này. IPKE là hệ mật có độ an toàn IND-CPA nếu s được chọn ngẫu nhiên phân bố đều trong 2k S (được chứng minh chi tiết trong định lý 3-3 của luận án). 19 3.4.6. Phân tích hiệu năng lý thuyết của IPKE Ưu điểm quan trọng của IPKE là cả hai thủ tục mã hóa và giải mã đều sử dụng phép nhân đa thức modulo 2( )O n như NTRU trong khi RSA phải sử dụng hàm mũ modulo với độ phức tạp 3( )O n . Ngoài ra, với cùng độ dài khóa công khai, IPKE chỉ cần sử dụng n bit khóa bí mật s trong khi NTRU sử dụng hai khóa f và pF với tổng độ dài là 2n bit. 3.5. KẾT LUẬN CHƯƠNG Ba hệ mật được giới thiệu trong chương này về cơ bản chứng minh vành đa thức chẵn 2nR hoàn toàn có thể ứng dụng được trong mật mã. Cụ thể hơn, ba hệ mật xây dựng được trên vành chẵn 2nR đều có thuật toán tạo khóa, mã hóa và giải mã đơn giản, đòi hỏi ít tài nguyên tính toán và có hệ số mở rộng bản tin nhỏ. Nếu như RISKE là một hệ mật khóa bí mật có độ an toàn chứng minh được IND-CPA nhưng có nhược điểm phải sử dụng khóa phiên thì QRHE là một biến thể hoạt động theo mô hình lai ghép với khóa bí mật tự sinh từ nội dung bản tin và có hiệu quả mã hóa rất cao. Bên cạnh đó, trong khi QRHE phải hoạt động dựa trên một hệ mật khóa công khai có sẵn theo mô hình lai ghép KEM/DEM thì IPKE là một hệ mật khóa công khai có thể hoạt động độc lập trên vành chẵn 2k R với nhiều mức độ an toàn khác nhau. Ngoài ra, các hệ mật như QRHE và RISKE là nền tảng phù hợp để xây dựng các hệ mật lai ghép có đặc tính tốt. Các hệ mật này hứa hẹn sẽ cải thiện tốt hệ số mở rộng bản tin của một hệ mật khóa công khai như Elgamnal, NTRU, pNE). 20 CHƯƠNG 4. CÁC HỆ MẬT MỞ RỘNG DỰA TRÊN VÀNH ĐA THỨC CHẴN KẾT HỢP VỚI CÁC VÀNH ĐA THỨC KHÁC 4.1. MỞ ĐẦU CHƯƠNG Trong chương này, bằng cách kết hợp vành đa thức chẵn tuyệt đối 2k R và vành đa thức chỉ có hai lớp kề cyclic 2CR , luận án đề xuất ba hệ mật mới bao gồm DTRU, E-RISKE và HpNE tương ứng với ba công trình [J2], [C3] và [C1] của nghiên cứu sinh. Các hệ mật được mô tả tường minh từ ý tưởng xây dựng cho đến các thuật toán (tạo khóa, mã hóa và giải mã) cũng như được đánh giá về hiệu năng và độ an toàn với một số tấn công phổ biến. 4.2. HỆ MẬT KHÓA CÔNG KHAI DTRU 4.2.1. Giới thiệu Ý tưởng then chốt của NTRU là mã hóa một bản rõ m , tương ứng với một đa thức có hệ số nhỏ (theo modulo p trong R ), thành một bản mã e , tương ứng với một đa thức có hệ số lớn (theo phép tính modulo q trong R ) với điều kiện q p và gcd( , ) 1p q  . Bên cạnh đó, để mã hóa và giải mã thành công, NTRU phải sử dụng một khóa bí mật f là một đa thức khả nghịch đồng thời theo hai modulo p và q trong R . Theo Định lý 2-1 và Định lý 2-3, các đa thức có trọng số lẻ trong các lớp vành 2k R hoặc 2CR đều là khả nghịch. Hơn nữa, nếu 2k a N và 2Cb N thì chắc chắn gcd( , ) 1a b  vì a là một số chẵn còn b là một số nguyên tố lẻ. 21 Ý tưởng ở đây là, thay vì một đa thức f khả nghịch trong R theo hai modulo p và q , ta sẽ sử dụng đa thức f khả nghịch đồng thời trong hai vành 2[ ] / ( 1)S Sx xR Z  và 2[ ] / ( 1[ ] ) L L xR xx Z  với 2CS N , 2kL N và S L để xây dựng một biến thể của NTRU có tên là DTRU. 4.2.2. Thủ tục tạo khóa Bob chọn một đa thức Sf R khả nghịch đồng thời trên SR và LR và tìm S SF R và L LF R thỏa mãn 1LF f  trong LR và 1SF f  trong SR . Tiếp đó, Bob chọn ngẫu nhiên một đa thức khác không Sg R và tính L bit khóa công khai ( 1) S L Lh g F x R     . Bob giữ ( , )Sf F làm hai khóa bí mật ( LF có thể bỏ đi). 4.2.3. Thủ tục mã hóa Để mã hóa S bit bản rõ m , Alice chọn ngẫu nhiên một đa thức khác zero SR  và tính Le m Rh   sau đó gửi L bit bản mã e tới Bob. 4.2.4. Thủ tục giải mã Khi nhận được e , Bob tính La f e R   và dựa vào đó khôi phục S Sm F a R   . 4.2.5. Phân tích độ an toàn lý thuyết của DTRU Xác suất để tấn công vét cạn thành công khóa bí mật là 1 ( 1)2 Sf    . Xác suất để tấn công vét cạn thành công bản rõ là 1 ( 1)2 SSR    . Nếu chọn 1024S  thì giá trị này rất nhỏ. Ưu điểm của DTRU là hai giá trị độ an toàn của bản rõ và khóa là luôn cân bằng. 22 Ngoài ra, DTRU là hệ mật có độ an toàn IND-CPA (được chứng minh chi tiết trong Định lý 4-1 của luận án). 4.2.6. Phân tích hiệu năng lý thuyết của DTRU Ưu điểm quan trọng của DTRU là tốc độ tính toán, cả hai thủ tục mã hóa và giải mã trong DTRU đều là các phép nhân đa thức modulo đơn giản với độ phức tạp 2( )O n . Tuy nhiên, bản mã trong DTRU bị mở rộng so với bản rõ /L S lần (tối thiểu 3 lần). Kết quả so sánh cho thấy, ở cùng mức độ an toàn tương đương, DTRU có kích thước khóa (cả công khai và bí mật) và hệ số mở rộng bản tin nhỏ hơn trong NTRU. Chi tiết so sánh được trình bày trong các bảng 4-4, 4-5 và 4-6 trong luận án. 4.3. HỆ MẬT KHÓA BÍ MẬT E-RISKE 4.3.1. Giới thiệu Mục này đề xuất một sơ đồ mật mã hóa khóa bí mật xác suất mới, được gọi là E-RISKE (Extended Random Invertible Secret-Key Encryption). E-RISKE là một biến thể mở rộng của hệ mật RISKE đã được trình bày trong mục 3.2 nhưng lại sử dụng cả các phần tử khả nghịch và khả nghịch mở rộng trong vành 2CR làm khóa. 4.3.2. Phân tích độ an toàn lý thuyết của E-RISKE Tương tự như RISKE, E-RISKE có độ an toàn IND-EAV và cao hơn là IND-CPA (được chứng minh chi tiết trong định lý 4-2 và định lý 4-3) của luận án. 4.3.3. Phân tích hiệu năng lý thuyết của E-RISKE Lợi thế quan trọng nhất của E-RISKE là tốc độ tính toán, thuật toán mã hóa và giải mã của E-RISKE chỉ là một phép cộng và một phép nhân đa thức trong 2,n CR n N và mất ( )O n phép tính bit. Nhược điểm của E-RISKE là mỗi phiên làm việc cần một khóa bí mật ngẫu nhiên mới được chia sẻ giữa bên gửi và bên nhận. 23 4.3.4. Thủ tục tạo khóa Alice và Bob chọn và chia sẻ một đa thức ngẫu nhiên s làm khóa bí mật chung. Vì deg( ) 1s N  nên ta có thể biểu diễn s bằng N bit. Điều kiện deg( ) 0s  đảm bảo rằng ta không sử dụng hai đa thức tầm thường 0s  và 1s  làm khóa bí mật trong E-RISKE. Khi đó 11 2| | | | 2 1 N   và 1 2| | | | | | 2 2 N    . 4.3.5. Thủ tục mã hóa Để mã hóa 1n  bit bản rõ m , đầu tiên Alice tính n bit 1(( ( ) 1)mod2). nM w m x m   sau đó tính n bit bản mã *c M s và gửi tới Bob. 4.3.6. Thủ tục giải mã Để giải mã n bit bản mã c , đầu tiên Bob tính n bit M như sau: Nếu 1s thì bên nhận tính 1*M c s còn khi 2s thì 1 0 *n eM e c s   . Sau đó Bob khôi phục 1n  bit bản rõ 1 1. n nm M x M    . Trong đó, 1nM  là hệ số của đơn thức 1nx  trong biểu diễn đa thức của M , 1s là nghịch đảo của s khi 1s và 1 es  là nghịch đảo mở rộng của s khi 2s . 4.3.7. Phân tích độ an toàn lý thuyết của E-RISKE Tương tự với RISKE, E-RISKE có độ an toàn IND-EAV và cao hơn là IND-CPA (được chứng minh chi tiết trong định lý 4-2 và định lý 4-3 của luận án). 4.3.8. Phân tích hiệu năng lý thuyết của E-RISKE Lợi thế quan trọng nhất của E-RISKE là độ phức tạp tính toán thấp. Các thuật toán mã hóa và giải mã của E-RISKE chỉ là một phép cộng và một phép nhân đa thức trong nR và mất ( )O n phép tính bit. 24 Nhược điểm của E-RISKE là ta phải chọn khóa bí mật s ngẫu nhiên và thống nhất giữa hai phía cho từng phiên. 4.4. HỆ MẬT LAI GHÉP HpNE 4.4.1. Giới thiệu Một trong những biến thể quan trọng của NTRU là hệ mật khóa công khai pNE hoạt động trên vành đa thức chẵn tuyệt đối hệ số nguyên , , 2 k n qR n  . Trong mục này, bằng cách kết hợp giữa pNE và RISKE theo mô hình KEM/DEM, hệ mật lai ghép HpNE sẽ được đề xuất với độ an toàn IND-CPA tương tự như pNE nhưng có hệ số mở rộng bản tin linh hoạt hơn. 4.4.2. Sơ đồ hệ mật lai ghép HpNE Sơ đồ hệ mật lai ghép HpNE được trình bày trên Hình 4-1. Đây là sơ đồ chuẩn theo mô hình KEM/DEM. s 1c 2cm Kênh mở Thám mã Sec  (RISKE) Pub  (pNE ) Sec  (RISKE) Pub  (pNE ) sk m 1c 2c Mã hóa Giải mã Hình 4-1: Sơ đồ mật mã lai ghép HpNE Sơ đồ này sử dụng pNE dựa trên , | 2 k n qR n  là phần KEM và