Đề tài Một sơ đồ cải tiến hệ mật mã khóa công khai rabin

Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 279 MỘT SƠ ĐỒ CẢI TIẾN HÊ ̣MẬT MÃ KHÓA CÔNG KHAI RABIN Đỗ Văn Tuấn1, Trần Đăng Hiên2, Phạm Văn Ất3 1 Trường Cao đẳng Thương mại và Du lịch Hà Nội 2Trường Đaị hoc̣ Công nghê ̣ 3 Trường Đại học Giao thông Vận tải Tóm tắt. Sơ đồ mật mã khóa công khai Rabin có ưu điểm là thuật toán mã hóa nhanh hơn so với hệ mật mã khóa công khai RSA. Nhưng, thuật toán giải mã của sơ đồ này lại tồn tại nhược điểm là từ một bản mã sẽ nhận được tới bốn bản rõ, dẫn đến khó khăn trong việc xác định đâu là bản rõ thực sự và đâu là bản rõ phát sinh thêm. Để khắc phục hạn chế này, đã có một số nghiên cứu cải tiến sơ đồ mã hóa Rabin, như sơ đồ Shimada[7], Chen-Tsu[4], và Harn[5]. Tuy nhiên, các sơ đồ cải tiến này có nhươc̣ điểm chung là phải tính toán khá nhiều và cần sử duṇg các số nguyên tố p , q có daṇg khá đăc̣ biêṭ làm giảm phaṃ vi ứng duṇg của chúng . Trong bài báo này, chúng tôi đề xuất một sơ đồ cải tiến hệ mâṭ mã Rabin, cho phép xác định duy nhất bản rõ từ một bản mã . Ngoài ra , so với các sơ đồ Shimada và sơ đồ Chen -Tsu, sơ đồ đề xuất có khối lươṇg tính toán nhỏ hơn và phaṃ vi ứng duṇg rôṇg hơn . Từ khóa: Cryptography, Public key, RSA, RABIN, Jacobi 1. Giới thiệu Sơ đồ mật mã khóa công khai Rabin có ưu điểm là độ an toàn đã được chứng minh tương đương với độ khó của bài toán phân tích một số ra thừa số nguyên tố, thuật toán mã hóa thưc̣ hiêṇ nhanh hơn so với hệ mật mã khóa công khai RSA. Tuy nhiên, thuật toán giải mã có nhược điểm là từ một bản mã lại nhận được tới bốn bản rõ, dẫn đến khó khăn trong việc xác định đâu là bản rõ thực sự và đâu là bản rõ phát sinh thêm. Điều này không những làm chậm tốc đô ̣thưc̣ hiêṇ của thuật toán giải mã, mà còn gây ra những khó khăn, nhâp̣ nhằng khi triển khai ứng dụng. Để khắc phục hạn chế của sơ đồ Rabin , có một số sơ đồ cải tiến được đề xuất như : sơ đồ Shimada[7], Chen - Tsu[4] và Harn[5]. Trong các sơ đồ Shimada và Chen-Tsu yêu cầu hai số nguyến tố p, q có dạng p=7(mod 8) và q=3(mod 8), điều này dâñ đến phạm vi ứng dụng bị thu hẹp khi triển khai thưc̣ tế . Ngoài ra , các sơ đồ này có hạn chế chung là phải tính toán khá nhiều. Sơ đồ của Harn vâñ sử duṇg các số nguyên tố p , q dạng 3(mod 4) như trong hê ̣mâṭ ma ̃Rabin , nhưng đòi hỏi môṭ khối lươṇg tính toán còn lớn hơn. Bài báo này đề xuất một sơ đồ cải tiến hệ mật mã Rabin, cho phép xác định duy nhất bản rõ từ bản mã và có khối lượng tính toán thưc̣ sư ̣ít hơn so với ba sơ đồ trên. Măṭ khác, sơ đồ đề xuất sử Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 280 dụng hai số nguyên tố p , q có daṇg 3(mod 4), nên phaṃ vi ứng dụng của sơ đồ mới cũng rôṇg hơn so với hai sơ đồ Shimada và Chen-Tsu. Nôị dung tiếp theo của bài báo đươc̣ tổ chức như sau : Phần 2 trình bày một số khái niêṃ và điṇh nghiã đươc̣ sử duṇg trong bài báo . Phần 3 giới thiêụ tóm tắt hai sơ đồ Shimada và Chen-Tsu, với muc̣ đích so sánh đô ̣phức tap̣ tính toán và phạm vi ứng dụng với sơ đồ đề xuất. Phần 4 trình bày nôị dung của sơ đồ đề xuất. Mục 5 sẽ tiến hành so sánh đô ̣phức tap̣ tính toán của các sơ đồ bằng cả phân tích lý thuyết và thưc̣ nghiêṃ trên máy . Cuối cùng là một số kết luận. 2. Môṭ số khái niêṃ và điṇh nghiã 2.1. Ký hiệu Legendre[2] Giả sử p là số nguyên tố lẻ và a nguyên, khi đó ký hiệu Legendre được định nghĩa như sau: 𝐿 𝑎 𝑝 = 0,𝑛ê 𝑢 𝑝|𝑎 1, nê u a la thặng dư bậc 2 của p −1, nê u a không la thặng dư bậc 2 của p Ở đây ký hiệu p|a có nghĩa p là ước của a (a chia hết cho p). Tiêu chuẩn Euler[2] Với moị a nguyên, ta có: 𝐿 𝑎 𝑝 = 𝑎(𝑝−1)/2 𝑚𝑜𝑑 𝑝 2.2. Ký hiệu Jacobi[2] Giả sử n = p×q, trong đó p, q là 2 số nguyên tố lẻ, a nguyên, khi đó ký hiệu Jacobi được định nghĩa thông qua ký hiệu Legendre như sau:                   q a L p a L n a J 2.3. Phương trình Rabin Xét phương trình đồng dư bậc hai: X 2 = θ mod N (2.1) Trong đó: θ và N đã biết, X là nghiệm cần tìm Ngoài ra θ và N có các tính chất:  N=p×q và p, q là hai số nguyên tố có dạng 3 mod 4.  θ là thặng dư bình phương của N và 0 ≤ θ < N Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 281 Phương trình này đươc̣ sử duṇg trong thuâṭ toán giải ma ̃của sơ đồ Rabin , nên ở đây gọi là phương trình Rabin. Theo [2], phương trình này có tối đa bốn nghiệm phân biêṭ x1, x 2, x 3, x 4 và khi biết p, q thì các nghiêṃ này có thể đươc̣ xác điṇh như sau: xp= θ (p+1)/4 mod p, xq= θ (q+1)/4 mod q x 1= Root(xp,xq), x 2 = Root(xp,q-xq), x 3 = Root(p-xp,xq), x 4 = Root(p-xp,q-xq) Trong đó ký hiêụ Root(u,v) là nghiệm của hệ phương trình đồng dư:      qvx pux mod mod Nghiêṃ của hê ̣này có thể tính theo Định lý số dư Trung Quốc[3]. Bổ đề 1: Ta có: (1) Nếu p|θ, thì x1 = x3 , x2 = x4 , x2 = N – x1 , 𝐽 𝑥1 𝑁 = 𝐽 𝑥2 𝑁 = 0 (2) Nếu q|θ, thì x1 = x2, x3 = x4 , x3 = N – x1 , 𝐽 𝑥1 𝑁 = 𝐽 𝑥3 𝑁 = 0 (3) Nếu 𝑝⏋θ va q⏋θ, thì 𝐽 𝑥1 𝑁 = 𝐽 𝑥4 𝑁 = 1, va 𝑥4 = 𝑁 − 𝑥1 𝐽 𝑥2 𝑁 = 𝐽 𝑥3 𝑁 = −1, va 𝑥3 = 𝑁 − 𝑥2 Ở đây ký hiệu 𝑝⏋θ (𝑞⏋θ ) có nghĩa θ không chia hết cho p (q). Chứng minh: (1) Nếu p|θ thì xp=0 và p-xp=0 mod p. Từ đó suy ra: x1 = x3, x2 = x4, J x1 N = J x2 N = 0 Như vâỵ phương trình (2.1) có hai nghiệm x1 và x2 nên x2= N – x1 Vâỵ, (1) đươc̣ chứng minh. (2) Được chứng minh tương tư.̣ (3) Do 𝑝⏋θ, q⏋θ và các giả thiết về θ, p, q, N suy ra xp là thặng dư bậc hai của p và xq là thặng dư bậc hai của q, nên: 𝐿 𝑥𝑝 𝑝 = 𝐿 𝑥𝑞 𝑞 = 1, 𝐿 𝑝−𝑥𝑝 𝑝 = 𝐿 𝑞−𝑥𝑞 𝑞 = −1 Từ đó suy ra: 𝐽 𝑥1 𝑁 = 𝐽 𝑥4 𝑁 = 1, 𝐽 𝑥2 𝑁 = 𝐽 𝑥3 𝑁 = −1 Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 282 Măṭ khác có thể thấy, nếu x là nghiêṃ của phương trình (2.1) và 𝐽 𝑥 𝑁 = 1 hoăc̣ -1, thì N-x cũng là nghiêṃ của phương trình (2.1) và 𝐽 𝑁−𝑥 𝑁 = 𝐽 𝑥 𝑁 . Từ đó suy ra , x4= N-x1 và x3= N-x2. Vâỵ Bổ đề 1 đươc̣ chứng minh. Từ Bổ đề 1 trưc̣ tiếp suy ra: Bổ đề 2: Giả sử M là nghiêṃ cần tìm của phương trình (2.1), thì M có thể được xác định như sau: 1 Nê u 𝐽 𝑀 𝑁 = 0 hoă c 1, thi M = x1 hoă c M = N− x1 2 Nê u 𝐽 𝑀 𝑁 = −1, thi M = x2 hoă c M = N− x2 Từ Bổ đề 2 suy ra: Nhâṇ xét: Khi biết 𝐽 𝑀 𝑁 và biết M thuôc̣ nửa trên [0, 𝑁−1 2 ] hoăc̣ nửa dưới [ 𝑁+1 2 ,𝑁 − 1] của đoạn [0,N-1], thì từ Bổ đề 2 có thể xác định duy nhất giá trị M thông qua x1 hoăc̣ x2. Ý tưởng này se ̃đươc̣ sử duṇg trong sơ đồ đề xuất ở mục 4. 3. Các sơ đồ Shimada và Chen-Tsu 3.1. Sơ đồ Shimada Trong sơ đồ này, khóa bí mật là hai số nguyên tố p , q có daṇg : p=7(mod 8) và q=3(mod 8), khóa công khai là số nguyên N = p×q. Ngoài ra , trong thuâṭ toán ma ̃hóa sử dụng hai hàm te, ue và thuật toán giải mã sử dụng thêm hai hàm td, ud. Nôị dung sơ đồ đươc̣ mô tả như sau: Thuâṭ toán mã hóa: Biết bản rõ M thuộc {0, 1,..., N-1}, bản mã C được tính theo các bước: Bước 1: Tính te(M) te M = 𝟏, nê u 0 ≤ M ≤ N−1 2 −𝟏, nếu N+1 2 ≤ M ≤ (N− 1) Bước 2: Tính ue(M) 𝑢𝑒 𝑀 = 1, 𝑛ế𝑢 𝐽 𝑀 𝑁 = 0 ℎ𝑜ặ𝑐 1 2, 𝑛ế𝑢 𝐽 𝑀 𝑁 = −1 Bước 3: Tính θ θ=M2 mod N Bước 4: Tạo bản mã C C=te (M) ×ue (M) × θ mod N Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 283 Thuâṭ toán giải mã: Biết bản mã C thuộc {0, 1, ..., N-1}, bản rõ M được xác định theo các bước: Bước 1: Tính td(C) 𝑡𝑑 𝐶 = 1, 𝑛ế𝑢 𝐿 𝐶 𝑝 = 𝐿 𝐶 𝑞 = 0 𝐿 𝐶 𝑝 , 𝑛ế𝑢 𝐿 𝐶 𝑝 = 0 𝑣à 𝐿 𝐶 𝑞 ≠ 0 𝐿 𝐶 𝑞 , 𝑛ế𝑢 𝐿 𝐶 𝑝 ≠ 0 Bước 2: Tính ud(C) 𝑢𝑑 𝐶 = 1, 𝑛ế𝑢 𝐿 𝐶 𝑝 × 𝐿 𝐶 𝑞 = 0 ℎ𝑜ặ𝑐 1 2, 𝑛ế𝑢 𝐿 𝐶 𝑝 × 𝐿 𝐶 𝑞 = −1 Bước 3: Tính θ θ=C × [td(C)] -1 × [ud(C)] -1 mod N Bước 4: Tìm bản rõ M Giải phương trình Rabin : X2=θ mod N để tìm một nghiệm thỏa mãn các điều kiêṇ: te(x) = td(C) và ue(x) = ud(C) Nghiệm tìm được chính là bản rõ M 3.2. Sơ đồ Chen-Tsu Sơ đồ Chen-Tsu là sự cải tiến sơ đồ Shimada. Hai sơ đồ này có cùng thuâṭ toán ma ̃ hóa. Chen-Tsu cải tiến thuâṭ toán giải ma ̃nhằm giảm khối lươṇg tính toán, cụ thể như sau : Thuâṭ toán giải mã: Biết bản mã C  {0,1,…,N-1}, bản rõ M được xác định theo các bước: Bước 1: Tính td(C), ud(C) và θ như trong thuật toán giải mã Shimada Bước 2: Xác định hai nghiệm x1, x2 của phương trình : X 2 = θ mod N theo các công thức trong muc̣ 2.3 Bước 3: Bản rõ M đươc̣ xác điṇh tùy thuôc̣ vào giá tri ̣ của mỗi nghiêṃ và của td(C), ud(C), chi tiết như sau : 1. td(C) =1 và ud(C) =1 Nếu ] 2 1 ,0[1   N x thì M = x1, trái lại M = N-x1 Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 284 2. td(C) =1 và ud(C) =2 Nếu ] 2 1 ,0[2   N x thì M = x2, trái lại M = N-x2 3. td(C) = -1 và ud(C) =2 Nếu ]1, 2 1 [2    N N x thì M = x2, trái lại M = N-x2 4. td(C) = -1 và ud(C) = 1 Nếu ]1, 2 1 [1    N N x thì M = x1, trái lại M = N-x1 4. Sơ đồ đề xuất Trong sơ đồ này , khóa bí mật là hai số nguyên tố p , q có daṇg : p=3(mod 4) và q=3(mod 4), khóa công khai là số nguyên N=p×q. 4.1. Thuật toán mã hóa Biết bản rõ M thuộc {0, 1, ..., N-1}, bản mã C được xác định theo các bước: Bước 1: Xác định α: α = 0, nếu J(M/N) = 0 hoặc 1 và M  ] 2 1 ,0[ N α = 1, nếu J(M/N) = 0 hoặc 1 và M  ]1, 2 1 [   N N α = 2, nếu J(M/N) = -1 và M  ] 2 1 ,0[ N α = 3, nếu J(M/N) = -1 và M  ]1, 2 1 [   N N Bước 2: Xác định bản mã C theo công thức: C = 4× (M 2 MOD N) + α 4.2. Thuật toán giải mã Biết bản mã C, bản rõ X đươc̣ xác điṇh theo các bước: Bước 1: Tính β = C MOD 4 θ = C DIV 4 Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 285 Bước 2: Xét phương trình: X 2 = θ mod N Nếu β = 0 hoăc̣ β=1 thì xác định nghiệm x 1, còn nếu β =2 hoăc̣ β =3 xác định nghiệm x2 của phương trình trên theo các công thức trong muc̣ 2.3 Bước 3: Bản rõ M đươc̣ xác điṇh theo β và x1 hoăc̣ x2 như sau: 1. β = 0 Nếu ] 2 1 ,0[1   N x thì M = x1, trái lại M = N-x1 2. β = 1 Nếu ]1, 2 1 [1    N N x thì M = x1, trái lại M = N-x1 3. β = 2 Nếu ] 2 1 ,0[2   N x thì M = x2, trái lại M= N-x2 4. β = 3 Nếu ]1, 2 1 [2    N N x thì M = x2, trái lại M = N-x2 4.3. Chứng minh tính đúng đắn Từ Bước 2 thuâṭ toán ma ̃hóa và Bước 1 thuâṭ toán giải ma ̃suy ra β = α và θ = M2 mod N. Như vậy, θ là thặng dư bình phương của N, nên phương trình ở Bước 2 trong thuâṭ toán giải mã chính là phương trình Rabin và bốn nghiệm x1, x2, x3, x4 có thể đươc̣ tính theo các công thức trong muc̣ 2.3. Măṭ khác, bản rõ M hiển nhiên cũng là môṭ nghiêṃ của phương trình này. Do đó, M phải trùng với môṭ trong bốn nghiêṃ nói trên . Vì β= α, nên β có thể nhâṇ môṭ trong bốn giá tri ̣ từ 0 đến 3. Ta se ̃lần lươṭ xét từng trường hơp̣ trong Bước 3 của thuâṭ toán giải mã. (1) Nếu β =0, thì từ Bước 1 thuâṭ toán ma ̃hóa suy ra 𝐽 𝑀 𝑁 = 0 hoặc 1 và M thuôc̣ nửa trên ] 2 1 ,0[ N . Nên theo Bổ đề 2, M = x1 hoăc̣ M = N- x1. Vì vậy, M = x1 nếu x1 thuôc̣ nửa trên và M=N-x1 nếu trái laị. (2) Nếu β =1, lâp̣ luâṇ tương tư ̣chỉ khác M thuôc̣ nửa dưới , do đó M = x1 nếu x1 thuôc̣ nửa dưới và M= N-x1 nếu trái laị. Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 286 (3) Nếu β =2, theo thuâṭ toán ma ̃hóa suy ra J M N = −1 và M thuộc nửa trên . Do J M N = −1 nên theo Bổ đề 2, M = x2 hoăc̣ N-x2. Vâỵ M = x2 nếu x2 thuôc̣ nửa trên và M= N – x2 nếu trái laị. (4) Nếu β=3, lâp̣ luâṇ tương tư ̣chỉ khác M thuôc̣ nửa dưới , do đó M = x2 nếu x2 thuôc̣ nửa dưới và M= N- x2 nếu trái laị. Vâỵ, tính đúng đắn của sơ đồ được chứng minh. 4.4. Ví dụ minh họa Để làm rõ hơn nôị dung của sơ đồ đề xuất , phần này se ̃trình bày hai ví du ̣minh hoạ quá trình mã hóa và giải mã với hai số nguyên tố p, q như sau: p = 43 = 3 + 4×10 và q= 31 = 3 + 4×7. Vâỵ N = p×q =1333. Cặp nguyên p , q đươc̣ choṇ như vâỵ không thể sử du ̣ng trong lươc̣ đồ Shimada và Chen-Tsu, nhưng sử duṇg đươc̣ trong sơ đồ đề xuất. Ví dụ 1: Xét M = 213  Quá trình mã hóa: Bước 1: J(M/N) = J(213 / 1333)= -1 (Tính theo thuâṭ toán trong[3], trang 110). Do 𝑀 ∈ 0, 𝑁−1 2 va 𝐽 𝑀 𝑁 = −1 nên α = 2 Bước 2: C= 4 𝑀2 MOD 𝑁 + 𝛼 = 4 1232 MOD 1333 + 2 = 190  Quá trình giải mã: Bước 1: 𝛽 = 𝐶 MOD 4 = 190 MOD 4 = 2 𝜃 = 𝐶 DIV 4 = 190 DIV 4 = 47 Bước 2: Do β = 2, xác định nghiệm x2 như sau: 𝑥𝑝 = 𝜃 (𝑝+1)/4 mod 𝑝 = 4711 mod 43 = 41 𝑥𝑞 = 𝜃 (𝑞+1)/4 mod 𝑞 = 478 mod 31 = 4 Giải hê ̣phương trình đồng dư: 𝑥2 = 𝑥𝑝 mod 𝑝 𝑥2 = 𝑝−𝑥𝑞 mod 𝑞  𝑥2 = 41 mod 43 𝑥2 = 31 − 4 mod 31  𝑥2 = 41 mod 43 𝑥2 = 27 mod 31 Được nghiêṃ x2 = 213. Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 287 Bước 3:Do β = 2 và 𝑥2 ∈ 0, 𝑁−1 2 nên M = x2. Vâỵ M = 213. Ví dụ 2: Xét M = 913  Quá trình mã hóa: Bước 1: J(M/N) = J(913 / 1333) = 1 (Tính theo thuật toán trong[3], trang 110). Do 𝑀 ∈ 𝑁+1 2 , 𝑁 − 1 va 𝐽 𝑀 𝑁 = 1 nên α =1. Bước 3: 𝐶 = 4 𝑀2 MOD 𝑁 + 𝛼 = 4 913𝟐 MOD 1333 + 1 = 1777  Quá trình giải mã: Bước 1: 𝛽 = 𝐶 MOD 4 = 1777 MOD 4 = 1 𝜃 = 𝐶 DIV 4 = 1777 DIV 4 = 444 Bước 2: Do β = 1, xác định nghiệm x1 như sau: 𝑥𝑝 = 𝜃 (𝑝+1)/4 mod 𝑝 = 44411 mod 43 = 10 𝑥𝑞 = 𝜃 (𝑞+1)/4 mod 𝑞 = 4448 mod 31 = 14 Giải hệ phương trình đồng dư: 𝑥1 = 𝑥𝑝 mod 𝑝 𝑥1 = 𝑥𝑞mod 𝑞  𝑥1 = 10 mod 43 𝑥1 = 14 mod 31 Được nghiệm x1 = 913. Bước 3: Do β = 1 và 𝑥1 ∈ 𝑁+1 2 ,𝑁 − 1 nên M= x1. Vâỵ M = 913. 5. So sánh các sơ đồ mã hóa Trong muc̣ này se ̃phân tích , so sánh sơ đồ đề xuất với hai sơ đồ Shimada và Chen-Tsu trên các phương diêṇ: Độ phức tạp tính toán, mức đô ̣bảo mâṭ và phaṃ vi ứng duṇg. 5.1. Độ phức tạp tính toán Độ phức tạp tính toán của thuật toán mã hóa trong cả ba sơ đồ trên là tương đương vì đều phải tính 𝐽 𝑀 𝑁 và M2mod N. Vì vậy, chúng ta chỉ so sánh độ phức tạp tính toán của các thuâṭ toán giải mã. Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 288 Trước hết dê ̃dàng nhâṇ thấy , những tính toán chủ yếu của thuật toán giải mã Shimada gồm: (1) Tính 𝐿 𝐶 𝑝 va 𝐿 𝐶 𝑞 . Các đại lượng này , trong trường hơp̣ tổng quát , tính theo công thức: 𝐿 𝐶 𝑝 = C(p−1)/2mod p và 𝐿 𝐶 𝑞 = C(q−1)/2mod q Nếu xem phép tính cơ bản là phép nhân và phép chia mod , thì theo [1], số phép tính cần thưc̣ hiêṇ xấp xỉ bằng: 2 × 𝑙𝑜𝑔2 𝑝−1 2 + 2 × 𝑙𝑜𝑔2 𝑞−1 2 ≈ 2 × 𝑙𝑜𝑔2[ 𝑝+ 1 × 𝑞 + 1 ] (2) Tính các nghiệm x1, x2, x3, x4 của phương trình X2 = θ mod N theo các công thức trong muc̣ 2.3. Trong số đó, hai công thức phức tap̣ nhất là: 𝑥𝑝 = 𝑎 (𝑝+1)/4 mod 𝑝, 𝑥𝑞 = 𝑏 (𝑞+1)/4 mod 𝑞 Cũng theo [1], thì số phép tính cần dùng xấp xỉ bằng 2 × 𝑙𝑜𝑔2 𝑝+1 4 + 2 × 𝑙𝑜𝑔2 𝑞+1 4 ≈ 2 × 𝑙𝑜𝑔2 𝑝+ 1 × (𝑞 + 1) (3) Tính hai hàm te(x) và u e(x) đối với ít nhất một nghiệm , nhiều nhất 4 nghiêṃ. Do đó, trung bình phải tính te(x) và ue(x) đối với hai trong số bốn nghiêṃ x1, x2, x3, x4, nên số phép tính xấp xỉ bằng 2 × 𝑙𝑜𝑔2 𝑝 − 1 2 + 2 × 𝑙𝑜𝑔2 𝑞 − 1 2 ≈ 2 × 𝑙𝑜𝑔2 𝑝 + 1 × 𝑞 + 1 Từ (1), (2) và (3) suy ra, đô ̣phức tap̣ tính toán của thuâṭ toán giải ma ̃Shimada xấp xỉ bằng: 8 × 𝑙𝑜𝑔2 𝑝 + 1 × (𝑞 + 1) So với Shimada thì thuâṭ toán giải ma ̃Chen-Tsu giảm đươc̣ các phép tính ở (3), nên đô ̣ phức tap̣ xấp xỉ bằng: 4 × 𝑙𝑜𝑔2 𝑝 + 1 × (𝑞 + 1) Thuâṭ toán giải mã trong sơ đồ đề xuất chỉ phải thực hiện các phép tính trong (2), nên đô ̣phức tap̣ xấp xỉ bằng: 2 × 𝑙𝑜𝑔2 𝑝 + 1 × (𝑞 + 1) Các kết quả phân tích trên được trình bày trong bảng sau đây . Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 289 Sơ đồ Số phép toán cơ bản Sơ đồ đề xuất ≈ 2 × 𝑙𝑜𝑔2[ 𝑝 + 1 × 𝑞 + 1 ] Chen-Tsu ≈ 4 × 𝑙𝑜𝑔2[ 𝑝 + 1 × 𝑞 + 1 ] Shimada ≈ 8 × 𝑙𝑜𝑔2[ 𝑝 + 1 × 𝑞 + 1 ] Bảng 1- Độ phức tạp tính toán của các thuật toán giải mã Bảng phân tích trên cho thấy khối lươṇg tính thuâṭ toán giải ma ̃ trong sơ đồ đề xuất chỉ bằng ½ so với sơ đồ Chen -Tsu và bằng ¼ so với sơ đồ Shimada . Điều này cũng đươc̣ thể hiêṇ thông qua kết quả thưc̣ nghiêṃ trong muc̣ 5.4. 5.2. Mức đô ̣bảo mâṭ Trong cả 3 sơ đồ, khóa bí mật là hai số nguyên tố p, q và khóa công khai là số nguyên N=p×q. Do vâỵ, mức đô ̣bảo mâṭ của chúng chính là độ khó của bài toán phân tích một số ra hai thừa số nguyên tố. 5.3. Phạm vi ứng dụng Trong cả hai sơ đồ Shimada và Chen -Tsu đều cần dùng tính chất t e(M)=td(C) và ue(M)=ud(C). Để có đươc̣ tính chất này, cần choṇ p có daṇg 7(mod 8) và q có dạng 3(mod 8). Cả hai dạng này đều là các trường hợp riêng của dạng 3(mod 4). Thưc̣ tế cho thấy tâp̣ các số nguyên tố dạng 7(mod 8) và 3(mod 8) nhỏ hơn nhiều so với tập các số nguyên tố dạng 3(mod 4). Do trong sơ đồ đề xuất vâñ sử duṇg các số nguyên tố p , q có daṇg 3(mod 4), nên sơ đồ mới có phạm vi ứng dụng rộng hơn so hai sơ đồ trên. 5.4. Kết quả thưc̣ nghiệm Trong chương trình thưc̣ nghiêṃ sử duṇg các số nguyên tố p , q có độ lớn khoảng 60 chữ số. Cụ thể như sau: p = 430606897333168273518201112510828692695315291101473646891711 q = 196996179941292068795331733133608048430672235582931 Viêc̣ so sánh đươc̣ thưc̣ hiêṇ trên 8 têp̣ bản rõ với các kích thước khác nhau . Chương trình chạy trên máy tính HP 6530s. Thời gian giải ma ̃của các sơ đồ ứng với các tệp bản rõ đươc̣ thống kê ở bảng sau: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011 290 STT Kích thước tệp Thời gian giải mã (giây) Shimada Chen - Tsu Sơ đồ đề xuất 1. 100KB 12.2 8.2 7.12 2. 167 KB 37.68 12.68 8.67 3. 267 KB 40.4 17.4 9.53 4. 394 KB 57.3 26.3 10.57 5. 501 KB 73.56 30.56 13.34 6. 1.229 MB 145.34 78 33.46 7. 1.558MB 189.67 107.8 42.34 8. 5.2 MB 674.25 289.74 130 Bảng 2 - Thời gian thưc̣ hiêṇ của các thuật toán giải mã Kết luận Bài báo đề xuất một sơ đồ cải tiến phương pháp mã hóa khóa công khai Rabin , cho phép xác định được bản rõ duy nhất từ môṭ bản mã . Độ phức tạp tính toán của sơ đồ đề xuất thấp hơn so với hai sơ đồ cải tiến trước đó của Shimada và của Chen -Tsu. Ngoài ra , sơ đồ đề xuất vâñ sử duṇg hai số nguyên tố p , q dạng 3(mod 4), trong khi hai sơ đồ Shimada, Chen-Tsu sử duṇg p , q daṇg 7(mod 8) và 3(mod 8), nên phạm vi ứng dụng của sơ đồ mới cũng rôṇg hơn so với hai sơ đồ trên. Tài liệu tham khảo [1] Phạm Văn Ất, Nguyễn Văn Long, Nguyễn Hiếu Cường, Đỗ Văn Tuấn, Cao Thị Luyên, Trần Đăng Hiên, Đề xuất thuật toán xử lý số nguyên lớn và ứng dụng trong các hệ mật mã khóa công khai, Kỷ yếu hội thảo quốc gia lần thứ XII Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông, Đồng Nai - 8/2009, tr. 107-118 [2] Phan Đình Diệu, Lý thuyết mật mã và An toàn thông tin, NXB ĐHQG HN, (2006). [3] Hà Huy Khoái, Phạm Huy Điển, Số hoc̣ thuâṭ toán, NXB ĐHQG HN, (2003). [4] Chin-Chen Chang and Sun-Min Tsu, An improvement on Shimada’s public-key cryptosystem, Journal of Science and Engineering, vol. 3, no. 2, pp. 75-79, (2000). [5] Harn,L., and Kiesler, Improved Rabin’s scheme with high efficiency, Electron. Lett., 25, (1 l), pp. 726-728,(1989). [6] Rabin, M. O, Digital Signatures and Public Key Functions as Intractable as Factorization, MIT/LCS/TR-212, (1979). [7] Shimada, M, Another Practical Public-Key Cryptosystem, {\em Electronics Letters}, Vol. 28, No.23, pp. 2146-2147, Nov. (1992).