Luận án Các hệ mật dựa trên vành đa thức chẵn - Cao Minh Thắng

ng , giả sử là một đa thức có bậc tối đa là với * 1, 2kp p   , nếu một đa thức 2 1 0 (1 ) k i i p i gg xx f     1 0 p i i i f g x   thì . Chứng minh: Vì deg 1f p  , ta có thể biểu diễn 1 2 0 | p i i i i f f x f Z     và 1 1 1 1 0 0 0 0 . . p p p p i p i i i p i i i i i i i i g f x x f x f x f x                 Đổi biến i j p  ta có 1 2 1 0 p p i p j i j i j p f x f x        và 1 2 1 0 p p i i i i i i p g f x f x        . Rõ ràng , [0, 1] i i f g i p   hay 1 0 . p i i i f g x    Vậy ta có điều phải chứng minh. Bổ đề này chỉ ra rằng nếu bậc của đa thức f đủ nhỏ thì ta có thể tìm đa thức này một cách dễ dàng từ đa thức (1 )pg f x   . Cùng với Bổ đề 2-11, bổ đề này là nền tảng để xây dựng hệ mật khóa công khai IPKE (mục 3.4). 44 2.4.2 Thuật toán tính phần tử nghịch đảo trong 2k R Như đã chứng minh trong Định lý 2-3, mọi phần tử 2k f R có trọng số lẻ đều khả nghịch. Vấn đề đặt ra là nếu sử dụng f làm khóa trong thủ tục mã hóa của các hệ mật thì để giải mã thành công cần phải biết nghịch đảo g của nó. Theo [17], 2kn  được chứng minh là cấp cực đại của tất cả các đa thức 2k f R hay 2 1 k f  . Điều này cho thấy 2 1 k g f  chính là phần tử nghịch đảo của f trong 2k R . Tuy nhiên, cũng theo [17], trong 2k R ord( )f luôn là ước của 2k hay ord( ) 2 | [1, ]if i k  . Do đó, ta có thể tính nghịch đảo của f bằng thuật toán sau hiệu quả hơn phép tính 2 1 k g f  . Thuật toán 2-1 g 2k f I: Thuật toán tính nghịch đảo của đa thức VÀO: Đa thức 2k f I . RA: Đa thức 2k g I , 1g f  . THUẬT TOÁN: g f ; 2a f ; for 1i  to 1k  { if 1g f  exit; g g a  ; 2a a ; }. Lấy ví dụ, trong 32I , để tính nghịch đảo của 5 4 3f x x x   , vì 2ord( ) 2 4,f   sử dụng thuật toán trên, ta có thể tính 3g f tại bước 2i  , thay vì phải tính 7.g f Thuật toán này có số bước lặp tối đa là 1k  . Với các giá trị độ dài khóa 1024n  , ứng với 10k  , số vòng lặp là không đáng kể. 45 2.5 VÀNH ĐA THỨC CHỈ CÓ HAI LỚP KỀ CYCLIC 2CR 2.5.1 Các định nghĩa Định nghĩa 2-10 [18 2 [ ] / ( 1) n nx xR Z ]: Vành đa thức được gọi là vành đa thức ( 1)nx chỉ có hai lớp kề cyclic nếu nhị thức có thể thừa số hóa thành dạng 1 (1 )nx x T    trong đó 1 0 n i i T x    là một đa thức bất khả quy trong 2[ ]Z x . Thuật toán để xác định 2Cn N (tập các số nguyên để nR là một vành đa thức chỉ có hai lớp kề cylic) được mô tả trong [14]. Điểm đặc biệt là các phần tử 2Cn N đều là các số nguyên tố. Một số phần tử 2 , 10000Cn N n  được trình bày trong phụ lục 1. 2.5.2 Tập các phần tử khả nghịch trên vành 2CR Định lý 2-4 2,n CR n N f f: Trong , mọi đa thức là khả nghịch khi và chỉ khi có 2C Ktrọng số lẻ và, hệ quả là , tỉ lệ giữa số phần tử khả nghịch trên tổng số đa thức 2 , C Rtrong đạt cực đại. Chứng minh: Theo [18], nếu 2Cn N thì n là một số nguyên tố lẻ và vì vậy ( )w T luôn chẵn. Khi ( )w f lẻ thì gcd( , 1) gcd( ,( 1) ) 1 nf x f x T     . Theo định lý Euclid, luôn tồn tại 2 , C u v R sao cho ( 1) 1nu f v x   hay 1u f  và f là khả nghịch. Ngược lại nếu ( )w f chẵn, theo Bổ đề 2-5, f không khả nghịch. 46 Ngoài ra, vì tất cả các phần tử có trọng số lẻ trong vành đều khả nghịch mà số các phần tử này chiếm một nửa tổng số đa thức trong vành nên rõ ràng số tỉ lệ 2CK đạt cực đại là 1/2. Vậy ta có điều phải chứng minh. Theo [18], 12 1nm   là cấp cực đại của các đa thức nf R và 1 mf  hay 1mu f  là nghịch đảo của f trong 2|n CR n N . Ví dụ, trong 5R , để tìm nghịch đảo của 4 3 1f x x   , do 5 1max(ord( )) 2 1 15f    , ta có thể tính 15 1 4 3u f x x x    . Bên cạnh đó, trong 2CR , với mỗi một đa thức f có trọng số Hamming lẻ thì luôn tồn tại một đa thức 0n g e f  có trọng số Hamming chẵn. Mặt khác, theo Định lý 2-2, g là nghịch đảo mở rộng của f . Do đó, tập 2|n CE n N sẽ bao gồm tất cả các đa thức có trọng số Hamming chẵn và 12 1n n E   (trừ đa thức tầm thường 0g  ). Ví dụ, trong 3R , có 22 4 đa thức khả nghịch 2 2{1, , ,1 }x x x x  và tương ứng 22 1 3  đa thức khả nghịch mở rộng 2 2{ ,1 ,1 }x x x x   , trừ đa thức 0 . Định lý này chỉ ra rằng 2C R là một vành đặc biệt có một tập các phần tử khả nghịch rất lớn và rất dễ xác định. Điều này rất thuận lợi để xây dựng các hệ mật có khóa là các phần tử khả nghịch trên 2C R vì thuật toán tạo khóa rất đơn giản và không gian khóa đủ lớn để chống lại các tấn công vét cạn khóa. Định lý này sẽ được ứng dụng để xây dựng hệ mật E-RISKE (mục 4.3). 2.5.3 So sánh vành 2CR với vành 2kR Điểm tương đồng của hai lớp vành này là có tỉ lệ số phần tử khả nghịch trên tổng số đa thức trong vành là cao nhất và là 1/2. Và có thể thấy một đa thức f có khả nghịch trong một vành 2CR nào đó thì cũng sẽ khả nghịch trong một vành 2kR nào đó miễn là f cũng thuộc vành đó và ngược lại. Ví dụ, 3 2 1f x x   khả nghịch trong 5R với nghịch đảo 4 3 5 g x x x   cũng khả nghịch trong 16R với nghịch đảo 47 15 13 10 9 8 6 3 2 16 g x x x x x x x x x         . Không những thế, một đặc điểm quan trọng nữa là bậc hữu hạn của hai lớp vành này luôn nguyên tố cùng nhau. Đặc điểm này sẽ được khai thác để xây dựng hệ mật DTRU (mục 4.2). 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 , 2C R ) 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-3, Định lý 2-4) 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). 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 nR 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-5). 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 2C R , một cải tiến của hệ mật RISKE vốn chỉ hoạt động trên 2k R . 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 2n R được nghiên cứu sinh xây dựng (Bổ đề 2-9 và Bổ đề 2-10) là nền tảng quan trọng để đề xuất hệ mật lai ghép QRHE trong mục 3.3. 48 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 2n R 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. Trong đó: RISKE, một hệ mật khóa bí mật có độ an toàn IND- CPA, được xây dựng dựa trên các phần tử khả nghịch trong vành đa thức chẵn tuyệt đối 2k R sẽ được trình bày trong mục 3.2; Hệ mật lai ghép QRHE hoạt động dựa trên đặc tính của các thặng dư bậc hai và các phần tử liên hợp của chúng trong vành chẵn 2n R sẽ được mô tả trong mục 3.3; Cuối cùng, hệ mật khóa công khai IPKE các phần tử khả nghịch trong vành 2k R làm cửa sập sẽ được đề xuất trong mục 3.4. Ngoài các tấn công vét cạn để đánh giá độ an toàn bản rõ và độ an toàn khóa, tấn công CPA sẽ được sử dụng trong thí nghiệm đánh giá độ an toàn không thể phân biệt để đánh giá độ an toàn ngữ nghĩa của các hệ mật được đề xuất. Trong các thuật toán tạo khóa, mã hóa và giải mã của các hệ mật, ta quy ước Alice là bên mã hóa và gửi bản mã còn Bob là bên nhận bản mã và giải mã. 3.2 HỆ MẬT KHÓA BÍ MẬT RISKE 3.2.1 Giới thiệu Hệ mật OTP (One-Time Pad) được Vernam đề xuất vào những năm 1920 và được Shannon chứng minh là có độ an toàn hoàn hảo vào năm 1949 [89]. OTP hoạt động trên trường (2) với các phép mã hóa và giải mã đều là các phép tính XOR rất đơn giản với độ phức tạp tính toán là ( )O n trong đó n là độ dài khóa. Ngoài ra, OTP hiện vẫn là hệ mật an toàn và vẫn được sử dụng trong các lĩnh vực rất đặc thù đòi hỏi độ an toàn rất cao như quốc phòng, an ninh và ngoại giao. Tuy nhiên, nhược điểm lớn nhất của OTP là khóa bí mật phải được chọn ngẫu nhiên và chỉ được sử dụng duy nhất một lần để tránh tấn công KPA. Ngoài ra, khóa bí mật của OTP cần có độ dài ít nhất bằng độ dài bản rõ dẫn đến hiệu quả mã hóa không cao. Những nhược 49 điểm này khiến cho OTP không phù hợp với các ứng dụng trong thương mại. Trên thực tế, các nghiên cứu mật mã khóa bí mật cũng đều đi theo hướng xây dựng các hệ mật có khả năng mã hóa những bản tin dài với khóa ngắn và có thể tái sử dụng mà vẫn đảm bảo độ an toàn ngữ nghĩa thay vì xây dựng các hệ mật có độ an toàn hoàn hảo [89]. Vấn đề đặt ra là có thể sử dụng vành đa thức chẵn 2n R để xây dựng một hệ mật có độ phức tạp mã hóa và giải mã tương đương với OTP nhưng có khóa bí mật ngắn hơn độ dài của bản tin mà vẫn đảm bảo hệ mật có độ an toàn chứng minh được hay không. Quan sát kỹ ta thấy, thuật toán mã hóa và giải mã trong OTP thực ra là một phép cộng trong vành đa thức n R , trong đó độ dài bản rõ, bản mã và khóa đều là n bit. Ý tưởng ở đây nếu thay thế phép cộng đa thức trong OTP bằng một phép nhân trong vành đa thức thì ta có thể sử dụng các phần tử khả nghịch trong n R để làm khóa cho một hệ mật khóa bí mật và nếu tập này đủ lớn thì hệ mật sẽ đạt mức an toàn ngữ nghĩa nào đó. Ngoài ra, nếu chọn khóa ngắn hơn bản rõ mà vẫn đảm bảo mức an toàn ngữ nghĩa thì hệ mật được đề xuất sẽ hiệu quả hơn OTP. Với Định lý 2-3, ta thấy rằng, tất cả các đa thức có trọng số Hamming lẻ trong lớp vành đa thức chẵn tuyệt đối 2k R là khả nghịch. Như vậy, tập này đủ lớn để có thể sử dụng làm khóa trong hệ mật nêu trên. Dựa trên các phần tử khả nghịch trên 2k R , nghiên cứu sinh sẽ đề xuất một hệ mật khóa bí mật, có tên là RISKE (Random Invertible Secret-Key Encryption scheme) có độ phức tạp tính toán 2( )O n với độ dài khóa không nhất thiết phải bằng độ dài bản tin mà vẫn có độ an toàn IND-CPA. 3.2.2 Cấu trúc đại số nền tảng của RISKE Cấu trúc đại số nền tảng của RIKSE so sánh với OTP với cùng kích thước khóa *N  được tóm tắt trong Bảng 3-1. Các giá trị kích thước được tính theo đơn vị bit. 50 Để 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 , 2k n R n  và độ dài bản rõ cùng một số nguyên 2kN  để xác định độ dài khóa bí mật. Việc lựa chọn độ dài khóa N nhỏ hơn độ dài của bản rõ n nhằm đảm bảo hiệu quả mã hóa của RISKE so với OTP, trong đó khóa và bản rõ có cùng độ dài N . Bảng 3-1: Cấu trúc đại số nền tảng của hệ mật RISKE và OTP Các tham số RISKE OTP Vành đa thức * 2 [ ] / ( 1) | 2 ,n k n R Z x x n k    (2) Kích thước khóa *,N n N  N Không gian khóa { | 0 deg 1} n s I s N     { {0,1} }Ns  Không gian bản rõ { | deg ( 1)} n m R m n     Kích thước bản rõ 1n  N Không gian bản mã n R  Kích thước bản mã n N 3.2.3 Thủ tục tạo khóa Với 0 }{ | deg 1 n I s Ns    , 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 ta không thể dùng 1s  làm khóa bí mật trong RISKE. Hệ quả là, 12 1N  . (3.1) 3.2.4 Thủ tục mã hóa Mỗi phiên mã hóa ( 1)n 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 51   1( ) 1 mod 2. nM w m x m   (3.2) sau đó tính n bit bản mã .c M s  (3.3) và gửi c đến Bob. Theo Bổ đề 2-6, ( )w M luôn lẻ do đó, theo Định lý 2-3, cả M và c đều có trọng số lẻ và khả nghịch trong 2k R . 3.2.5 Thủ tục giải mã Để giải mã n bit bản mã c , dựa vào khóa phiên s , đầu tiên Bob tính n bit 1M c s  (3.4) trong đó 1s là nghịch đảo của s trong 2k R tính bằng Thuật toán 2-1, từ đó sử dụng công thức (2.15) khôi phục 1n  bit bản rõ 1 1 . n n m M x M    (3.5) với 1n M  là hệ số ứng với đơn thức 1nx  trong biểu diễn đa thức của M . 3.2.6 Ví dụ minh họa Alice và Bob lựa chọn 32 8n   và 5N  để xây dựng hệ mật RIKSE. a) Tạo khóa Alice và Bob chia sẻ 5 bit khóa bí mật (00111)s  dạng nhị phân hay 2 1s x x   dạng đa thức. Vì ( ) 3w s  nên nghịch đảo của s trong 8R , tính bởi Thuật toán 2-1, là 7 51 4 2x x xs x x     . b) Mã hóa Để mã hóa 7 bit bản rõ (1010011)m  dưới dạng nhị phân hoặc 6 4 1m x x x    dạng đa thức, Alice đầu tiên, bằng công thức (3.2), tính 8 bit 7 6 4 1M x x x x     sau đó, bằng công thức (3.3), tính và gửi 8 bit bản mã 5 4 3 1x x xM xc s       52 dạng đa thức hoặc (00111011)c  dạng nhị phân tới Bob. c) Giải mã Để giải mã 8 bit bản mã (00111011)c  , bằng công thức (3.4), đầu tiên Bob tính 8 bit 1 7 6 4 1M s c x x x x       . Sau đó, bằng công thức (3.5), với 7 1M  , Bob khôi phục 7 bit bản rõ 7 7 6 5 6 4( 1) 1m x x x x x x x x          . 3.2.7 Phân tích độ an toàn lý thuyết của RISKE Để đánh giá độ an toàn cho hệ mật RISKE, trước hết, ta sẽ chứng minh bổ đề sau đây. Bổ đề 3-1 1 1( ) (2 1)nf n    n: là hàm không đáng kể với biến . Chứng minh: Theo [54], 2 n là một hàm không đáng kể và vì tổng của hai hàm không đáng kể cũng là một hàm không đáng kể nên ta có ( 2) 22 2 4.2n n n     là một hàm không đáng kể. Theo Định nghĩa 1-4, với mọi hằng số c luôn tồn tại 0 n sao cho 0 n n thì ( 2)2 n cn   . Vì 1 1 ( 2) 22 2 2.2n n n     và 22 1n  khi 2n  , ta luôn có 2 1 22 2 2 1n n n     hay 1 1 ( 2)(2 1) 2n n     với 2n  . Do đó, với mọi hằng số c luôn tồn tại 0 0 max{ ,2}N n để sao cho 0 n N thì ( 1) 1 ( 2)(2 1) 2n n cn       . Hệ quả là, 1 1( ) (2 1)nf n    là một hàm không đáng kể với biến n và ta có điều phải chứng minh. a) Với các tấn công vét cạn 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à 53 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. b) Với các tấn công EAV Định lý 3-1: RISKE là hệ mật có độ an toàn IND-EAV. Chứng minh: Nhắc lại rằng, với *c M s ta có thể tính 1M s c  với 1s là nghịch đảo của s trong 2k R . Mặc dù kẻ tấn công không biết khóa bí mật, vẫn có thể thử từng giá trị 's  để tính 1' ( ')M s c  cho đến khi 'M M . Bằng cách này, xác suất để giải mã thành công mà không cần biết khóa bí mật là 1 1 1Pr[ ' ] Pr[( ') ] Pr[( ') ]M M s c M s M c         với 1c là nghịch đảo của c trong LR . Vì 's được lựa chọn ngẫu nhiên trong trong khi M và 1c là cố định nên 1 1 1Pr[ ' ] Pr[( ') ]M M s M c      . Trong tấn công EAV, với bản mã thách thức bc M s  nhận được từ thủ tục mã hóa, có thể tính b b  bằng cách đoán đơn giản với xác suất 1/2 hoặc thử lần lượt tất cả các khóa 's  để tính 1' ( ')M s c  cho đến khi 0'M M hoặc 1 'M M . Giả sử rằng phải thử ( )p N lần để có 0'M M hoặc 1'M M , trong đó ( )p N là một đa thức của N (để chắc chắn rằng tấn công này có thể thực hiện trong thời gian đa thức), ta có  eav, 0 1 1 1 Pr[SecK ( ) 1] ( ). Pr[ ' ].Pr[ 0] Pr[ ' ].Pr[ 1] 2 1 1 1 1 ( ) 1 ( ) ( ). . 2 2 2 2 2 2 1n N p N M M b M M b p N p N p N                        54 Theo Bổ đề 3-1, vì ( 1) 1(2 1)N  là một hàm không đáng kể của biến N đồng thời do ( )p N là một đa thức nên, theo Bổ đề 1-2, ( 1) ( ) 2 1N p N   cũng là hàm không đáng kể của N . Vì vậy, theo Định nghĩa 1-6, RISKE có độ an toàn IND-EAV và ta có điều phải chứng minh. c) Với các tấn công CPA Định lý 3-2: RISKE là hệ mật có độ an toàn IND-CPA. Chứng minh: Nhắc lại rằng, với bản mã thu được {0,1* }, b c M s b  . Nếu ' ' b c M s  với 's  thì xác suất để 'c c là 1 1 1Pr[ ' ] Pr[ ' ] Pr[ ' ] b b b c c M c M c s M c          với 1 b M  là nghịch đảo của b M trong 2k R . Do 's được bộ mã hóa chọn ngẫu nhiên trong tại mỗi phiên trong khi 1 b M  và c không đổi nên 1Pr[ '] Pr ] 1 [ ' b c c s M c     Quay trở lại thí nghiệm cpa , SecK ( )N  , với bản mã thách thức * b c M s , có thể đoán đúng b b  bằng một trong hai cách sau: 1. Sử dụng thuật toán tương tự để đoán đúng b như trong thí nghiệm eav , SecK ( )N  ; 2. Chọn ngẫu nhiên ' {0,1}b  và tiếp tục truy vấn bộ mã hóa ( )q N lần với đầu vào 'bM và nhận về bản mã tương ứng 'c cho đến khi 'c c . Ở đây, ( )q N là một đa thức của N để đảm bảo chắc chắn tấn công này có thể thực thi trong thời gian đa thức. Do đó, ta có 55 cpa eav , , eav , 1 Pr[SecK ( ) 1] Pr[SecK ( ) 1] ( ).Pr[ ' ] 1 = Pr[SecK ( ) 1] ( ). 1 ( ) ( ) 1 ( ) ( ) . 2 2 2 1N N N q N c c N q N p N q N p N q N                   Theo Bổ đề 3-1, vì ( 1) 1(2 1)N  là một hàm không đáng kể của biến N đồng thời do ( ) ( ) ( )g N p N q N  cũng là một đa thức nên, theo Bổ đề 1-2, ( 1) ( ) 2 1N g N   là hàm không đáng kể của N . Hệ quả là, theo Định nghĩa 1-7, RISKE có độ an toàn IND-CPA và ta có điều phải chứng minh. 3.2.8 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 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. Nếu hệ mật khóa công khai được chọn có độ an toàn IND-CPA thì hệ mật lai ghép cũng sẽ có độ an toàn IND-CPA [28]. 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.2.9 Lựa chọn tham số Vì RISKE có độ an toàn IND-CPA, xác suất để tấn công được RIKSE là không đáng kể. Tuy nhiên, để ngăn chặn các tấn công vét cạn, giá trị N cần đủ lớn. Giá trị khuyến nghị cho các ứng dụng thực tế hiện nay là 1024N  [64] và do đó 56 10k  . Trong trường hợp này, số khóa cần vét cạn ít nhất sẽ là 1 20132 2N  . Đối với các ứng dụng đòi hỏi độ an toàn cao, giá trị khuyến nghị là 4096N  . Ngoài ra, do n càng lớn hơn so với N thì hiệu quả mã hóa của RISKE càng cao. Điều này đặc biệt hữu ích để cải thiện hệ số mở rộng bản tin của các hệ mật khóa công khai trong sơ đồ lai ghép với RISKE. Mặc dù vậy, giá trị này cần phải được lựa chọn phù hợp cho từng ứng dụng cụ thể. 3.2.10 So sánh RISKE với OTP Các so sánh về độ an toàn và hiệu năng của RIKSE với OTP được tóm tắt trong Bảng 3-2. Với cùng kích thước bản rõ là n , khóa bí mật s của RISKE có kích thước nhỏ hơn. Ngoài ra, khác với OTP, khóa bí mật s trong RISKE có thể sử dụng lại miễn là đảm bảo phân bố đều trong không gian khóa. Tuy vậy, để có thể sử dụng các khóa ngắn hơn bản rõ, thuật toán mã hóa và giải mã trong RISKE phải sử dụng phép nhân đa thức với độ phức tạp 2( )O n . Đây cũng là một nhược điểm của RISKE so với OTP nhưng có thể chấp nhận được vì các phép nhân đa thức trong vành rất dễ thực hiện bằng cả phần cứng lẫn phần mềm. Bảng 3-2: So sánh hiệu năng và độ an toàn của RISKE và OTP Các tham số RISKE OTP Kích thước bản rõ 1n  n Kích thước bản mã n n Kích thước khóa N n n Độ phức tạp mã hóa 2( )O n ( )O n Độ phức tạp giải mã 2( )O n ( )O n Độ an toàn IND-CPA Độ an toàn hoàn hảo 57 3.2.11 Kết luận về hệ mật RISKE Có thể coi RISKE là một biến thể của OTP trên vành đa thức 2k R với một số ưu điểm về sự linh hoạt trong lựa chọn và quản lý khóa bí mật. Tuy nhiên, để đưa vào sử dụng trên thực tế, việc lựa chọn một hệ mật khóa công khai phù hợp để chia sẻ khóa phiên của RISKE là một vấn đề mở. Một kết quả của hướng nghiên cứu này sẽ được trình bày trong mục 4.4. Bên cạnh đó, do RISKE hoạt động dựa trên tập các phần tử khả nghịch nên tìm ra các lớp con của n R khác có hệ số n K đạt cực đại hoặc gần cực đại để lựa chọn linh hoạt cấu trúc đại số nền tảng của RISKE cũng là một hướng nghiên cứu đáng quan tâm. 3.3 HỆ MẬT LAI GHÉP QRHE 3.3.1 Giới thiệu Như đã đánh giá, mặc dù có độ an toàn IND-CPA, hệ mật khóa bí mật RISKE vẫn có một nhược điểm là phải sử dụng khóa phiên (session-key) giống như hệ mật OTP. Để phù hợp với các ứng dụng thực tế, RISKE cần phải được sử dụng kết hợp với một hệ mật khóa công khai phù hợp và thường là theo mô hình KEM/DEM như đã giới thiệu ở mục 1.2.3. Bên cạnh đó, xét về hiệu năng, phép mã hóa và giải mã của RISKE vẫn là phép nhân đa thức có độ phức tạp 2( )O n . Vấn đề đặt ra là có thể xây dựng một hệ mật lai ghép trong đó các thuật toán mã hóa và giải mã đơn giản hơn, ví dụ như sử dụng phép cộng trong vành đa thức với độ phức tạp ( )O n hay không. Ngoài ra, làm thế nào để có thể cải tiến thủ tục tạo khóa của RISKE để giảm độ phức tạp khi sử dụng khóa phiên ngẫu nhiên. Như đã phân tích trong mục 2.3, mỗi trong tổng số 22 n đa thức 2nm R đều là một phần tử liên hợp với thặng dư bậc hai 2f m . Điều này có nghĩa là mọi đa thức, tương ứng với mọi bản tin 2n bit, trong 2nR luôn có thể biểu diễn dưới dạng: 2(1 )n t t U m x x m      (3.6) 58 hay (1 )nm x k l    (3.7) 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. Với phân tích như trên, 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    (3.8) là một bản mã mà , nếu không biết k sẽ không thể phát hiện ra m dù thu được l . Từ Bổ đề 2-9 và Bổ đề 2-10, các phép tính 2l m và t t U k x   đều rất đơn giản với độ phức tạp tính toán chỉ là ( )O n . Với ý tưởng trên, trong mục này, nghiên cứu sinh đề xuất một hệ mật lai ghép theo mô hình KEM/DEM có tên là QRHE dựa trên thặng dư bậc hai và các phần tử liên hợp trong vành đa thức 2nR với các thuật toán tạo khóa, mã hóa và giải mã đơn giản hơn đồng thời không cần sử dụng khóa phiên như hệ mật RISKE. 3.3.2 Sơ đồ hệ mật lai ghép QRHE Sơ đồ hệ mật lai ghép QRHE (Quadratic Residue Hybrid Encryption scheme) theo ý tưởng trên được mô tả chi tiết trong Hình 3-2. Với khối dữ liệu thứ i cần truyền đi dài 2n bit tương ứng với đa thức 2 1 0 n j i ij j m m x     (3.9) Alice sẽ tính toán và mã hóa khóa ik thành bản mã 2,ic (độ dài bit phụ thuộc vào phép mã hóa khóa) rồi truyền tới Bob qua kênh mở. Ở phía nhận, Bob sẽ giải mã 2,i c để lấy khóa ik sau đó sử dụng khóa này để khôi phục được bản rõ im từ 2 1,i i c m . 59 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 Có thể thấy, QRHE là một biến thể của sơ đồ lai ghép KEM/DEM trên Hình 1-1 vì khóa bí mật ik không tồn tại độc lập mà được tính toán từ bản rõ im bằng cách phân tích nó thành một phần tử liên hợp của thặng dư bậc hai 2 i m như trong biểu thức (3.6). 3.3.3 Cấu trúc đại số nền tảng của QRHE Cấu trúc đại số nền tảng của QRHE được tóm tắt trong Bảng 3-3. Các giá trị kích thước được tính theo đơn vị bit. Để xây dựng hệ mật, Alice và Bob thống nhất giá trị n để xác định vành đa thức chẵn 2nR và một hệ mật khóa công khai làm phần KEM. Trong cấu trúc đại số của QRHE, kích thước bản rõ m lớn gấp hai lần kích thước khóa k . Khóa này được sinh ra từ chính bản rõ m và chứa một phần thông tin từ m . Ngoài ra, kích thước bản mã 1c là n bit trong khi kích thước bản mã 2c lại phụ thuộc vào hệ mật được sử dụng làm phần KEM và thường lớn hơn n . Nhìn chung, hệ số mở rộng bản tin của QRHE sẽ lớn hơn 1. Do đó, cần lựa chọn phần KEM phù hợp để đảm bảo hệ số mở rộng bản tin của QRHE không quá lớn qua đó đảm bảo hiệu quả mã hóa. 60 Bảng 3-3: Cấu trúc đại số nền tảng của hệ mật QRHE Các tham số Giá trị Vành đa thức 22 2 *[ ] / ( 1) |n n R Z x x n   Không gian khóa 2 { | 0 deg( ) 1} n k R k n     Kích thước khóa n Không gian bản rõ 2n R Kích thước bản rõ 2n Không gian bản mã