Luận án Nghiên cứu giải pháp nâng cao hiệu quả bảo mật thông tin trên mạng truyền số liệu đa dịch vụ

h Pr ob X m t M          = 2(t). (2.14) Đại lượng F(k) chỉ nhận hữu hạn giá trị do đó kỳ vọng AAF(k) và phương sai 48 của nó, ký hiệu là (k)2 là hữu hạn do đó th o công thức (2.14) ta có công thức đánh giá tương ứng đó là: ( ) Pr ( , ) ( ) k ob AAF k M AAF k t M        = 2(t). (2.15) Ví dụ 1: Với t = . , giá trị ( . ) tra được trong bảng A (trang 72 [5]) (Lưu ý: Với cùng một ký hiệu (t) nhưng trong tài liệu [36] chính là 2(t) trong [6] là 0.999032) điều này có ngh a nếu lấy (k)= ( ) 3.1 k M  thì theo công thức (2.15) ta có  Pr ( , ) ( ) ( )ob AAF k M AAF k k   = 0.9990322. b) Ước lượng giá trị (k) Để áp dụng được công thức (2.15) việc quan trọng tiếp th o là xác định được giá trị (k). Trong điều kiện F(k) chưa biết phân bố nên chúng ta chỉ có thể ước lượng giá trị (k), mà điều cần thiết để ước lượng là một cận trên của nó. Trong mục này sẽ đưa ra cách ước lượng nói trên, ta cần chứng minh bổ đề sau: Bổ đề 1: ho sự kiện ngẫu nhiên có hân hối xác suất Prob( ) , nếu trong h thử độc lậ ta thấy sự kiện này xuất hiện đúng lần thì với mọi >0 cho trước ta có Prob(1p > )=   1 1 M    (2.16) hứng minh Ký hiệu B là sự kiện {trong M phép thử độc lập sự kiện A xuất hiện đúng M lần} ta có Porb(B.(Prob(A)=p)) = p M (2.17) Từ (2.17) ta có Porb(B.(u ≤ Prob(A) ≤ v)) = v M u p dp (2.18) Vì (0 ≤ Prob(A) ≤ ) là sự kiện chắc chắn nên từ (2.18) ta có kết quả 49 Porb(B) = Porb(B.(0 ≤ Prob(A) ≤ )) = 1 0 Mp dp (2.19) Th o công thức xác suất có điều kiện [6] và đẳng thức (2.18), (2.19) ta suy ra: Porb((u ≤ Prob(A) ≤ v)/B) = Pr ( .( Pr ( ) )) Pr ( ) ob B u ob A v ob B   = 1 0 v M u M p dp p dp   (2.20) Với u=0, v= -  và trong biểu thức (2.20) thay Prob(A) bằng p ta có Prob(1p > ) = 0 1 0 1 M p dp M p dp    =   1 1 M    như vậy (2. ) đã được chứng minh. Ví dụ 2. Với M= 07 và =0.0000006908 ta có   1M1  = 0.001. Từ bổ đề ở trên ta thu được kết quả sau dùng để ước lượng cận trên cho giá trị . Hệ quả: ho đ i lượng ngẫu nhiên X có mi n giá trị là {0, 1, ..., n}. Nếu thực hiện h thử độc lậ X chỉ nhận giá trị trong mi n [s,e] và (X) min ; 2 2 s e n      . Khi đó với mọi 0<<1 ta đánh giá 2     2 2 (1 ) (1 ) (1 )e s n s           . (2.21) Thì xác suất sai lầm lo i 2 của đánh giá trên là  =   1M1  . hứng minh: Ký hiệu A = {X [x1, x2]} thì với giả thiết đưa ra, th o bổ đề ta có Prob(1p > ) =   1M1  Điều trên có ngh a nếu ta kết luận " Prob(A) = p > 1 " thì kết luận này có xác suất sai lầm loại 2 là   1M1  . Ta có E(X) =     1s 1i ipi +    e si ipi +    n 1ei ipi     e si ips = (1 )s (2.22) 50 2 =      1s 1i 2 i )X(Eip +     e si 2 i )X(Eip +     n 1ei 2 i )X(Eip (2.23) Từ điều kiện (2.22) và E(X)         2 n ; 2 es min nên các giá trị (i  E(X))2 trong tổng thứ hai trong vế phải của (2.23) thỏa mãn (i  E(X))2 < (e  E(X))2 (2.22)  (e  (1)s)2 (2.24) còn trong tổng thứ nhất và thứ ba trong vế phải của (2.23) thỏa mãn (i  E(X))2 < (n  E(X))2 (2.22)  (n  (1)s)2 (2.25) Thay (2.24) và (2.25) vào (2.23) ta được 2       e si i 2 ps)1(e +               1s 1i n 1ei ii 2 pps)1(n     22 s)1(ns)1(e)1(  và đây là điều cần chứng minh. 2.2.2.5. Thuật toán tính hàm flops(.,.). Việc tính hàm flops(X, ), được thực hiện th o thuật toán 2.5 Thuật toán 2.5. Tính hàm flops(.,.) Input: X, Y là hai dãy k+1 bít biểu di n nhị phân số nguyên [0, 2k). Output: f 1. f=0; 2. while (C0) { f  f+1; B  A And C; A  A Xor C; C  Shiftleft(B); } 3. return f. Trong đó: And: toán tử nhân các bit tương ứng của hai thanh ghi; Xor: toán tử xor các bit tương ứng của hai thanh ghi; Shiftleft: phép dịch trái vị trí. 51 2.2.3. Kết quả tính toán số AAF(k) và AAF(k,M) 2.2.3.1. Cách tính giá trị AAF(k) Chúng ta sử dụng hàm flops(X, ) để tính số nhịp máy; trong trường hợp k nhỏ, cụ thể k14, ta tiến hành đếm toàn bộ số nhịp máy cho tất cả 22k phép cộng, giá trị thu được ký hiệu là Total(k) và khi này ta có AAF(k) = Total(k)22k (2.26) Ngược lại, chọn phương pháp thống kê đó là tiến hành lấy ngẫu nhiên M= 07 cặp số nguyên X,  [0, 2k), tính Total(k,107) tổng của 07 giá trị flops(X,Y) trong mỗi lần lấy ngẫu nhiên đó và khi này: AAF(k,10 7 )=Total(k,10 7 )107 (2.27) Để phục vụ cho việc đánh giá sai số như đã đưa ra trong mục 2.2.2.4, ngoài việc tính Total(k) chúng ta còn phải xác định hai tham số fs(k) và fe(k) (dùng trong công thức 2.28) với fs(k) là giá trị đầu tiên và fe(k) là giá trị cuối cùng có N(k,f)0. 2.2.3.2. K t quả duyệt toàn bộ 22k phép cộng khác nhau với k từ 0 đ n 14 Total(1) = 3, AAF(1) = 0.750000; Total(2) = 21, AAF(2)= 1.312500; Total(3) = 113, AAF(3)= 1.765625; Total(4) = 547, AAF(4)= 2.136719; Total(5) = 2509, AAF(5)= 2.450195; Total(6) = 11135, AAF(6)= 2.718506; Total(7) = 48373, AAF(7)= 2.952454; Total(8) = 206991, AAF(8)= 3.158432; Total(9) = 876061, AAF(9) =3.341908; Total(10)=3677047, AAF(10)=3.506705; Total(11)=15334149, AAF(11)=3.655946; Total(12)=63619791, AAF(12)=3.792035; Total(13)=262861101, AAF(13)=3.91693; Total(14)=1082389767, AAF(14)=4.032216; 2.2.3.3. K t quả thống kê với 107 mẫu cho mỗi k từ 15 đ n 4096 Bảng 2.1 ghi kết quả thống kê được của 2 giá trị k bao gồm k từ 5 đến k từ 9 đến 02 trong dạng k= 2i (i= ,..., 0) k từ 088 đến 20 8 trong dạng k= i (i= ,..., ) và k từ 2 7 đến 09 trong dạng k= 28i (i= ,..., ). Các số liệu được ghi trong bảng bao gồm: k, AAF(k, 07), fs(k), 52 fe(k) và (k). Các số liệu AAF(k, 07), fs(k), fe(k) có được từ thống kê còn (k) được ước lượng th o ví dụ mục 2.2.2.4 a) (để đạt được độ tin cậy 0.999032), giá trị 2 được đánh giá th o công thức (2.28) còn  = 0.000000 908 được lấy th o ví dụ 2 mục 2.2.2.4 b) (để đảm bảo xác suất sai không quá 0.00 ). Tóm lại (k) được tính th o công thức sau: (k) = 2 2 (1 )( (1 ) ) ( 1 (1 ) ) 3.1 7 10 f f k fe s s            (2.28) Bảng 2.1. Kết quả thống kê 112 giá trị của k k AAF(k,107) fs (k) fe (k) (k) k AAF (k,10 7) fs (k) fe (k) (k) 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 4.1399501 4.2386532 4.3320945 4.4200825 4.5026766 4.5807384 4.6553482 4.7249131 4.7923977 4.8568043 4.9183709 4.9770195 5.0349873 5.0876514 5.1409723 5.1919811 5.2410299 5.2881423 5.3332005 5.3778501 5.4209489 5.4637941 5.5035587 5.5434711 5.5817211 5.6189158 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16 17 18 19 20 21 22 23 23 24 23 24 25 24 25 24 26 27 25 25 28 27 26 27 26 26 0.016039 0.017042 0.018044 0.019046 0.020049 0.021051 0.022054 0.023056 0.022054 0.024059 0.022054 0.023056 0.024059 0.023056 0.024059 0.023056 0.025061 0.026063 0.024059 0.024059 0.027066 0.026064 0.025061 0.026064 0.025061 0.025061 288 320 352 384 416 448 480 512 544 576 608 640 672 704 736 768 800 832 864 896 928 960 992 1024 1088 1152 8.4977167 8.6502339 8.7886398 8.9146046 9.0295142 9.1369311 9.2362259 9.3298887 9.4175886 9.5004907 9.5784751 9.6527988 9.7229998 9.7910969 9.8535831 9.9160444 9.9746949 10.0314707 10.0860103 10.1386865 10.1888623 10.2389178 10.2861217 10.3310832 10.4188155 10.5008227 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 6 5 5 6 5 5 6 6 30 34 33 31 31 30 31 31 30 32 33 32 34 31 34 34 33 33 31 32 34 35 32 34 33 35 0.026065 0.030074 0.029072 0.027068 0.027068 0.025064 0.026067 0.026067 0.025065 0.027070 0.028073 0.027071 0.029076 0.026070 0.029077 0.029078 0.028076 0.028077 0.025071 0.027076 0.029081 0.029082 0.027078 0.029083 0.027081 0.029087 53 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 96 128 160 192 224 256 5.6558295 5.6920440 5.7259800 5.7601316 5.7937005 5.8254527 5.8576532 5.8874458 5.9189435 5.9480496 5.9780568 6.0063450 6.0338280 6.0620954 6.0884972 6.1156798 6.1410676 6.1666951 6.1914261 6.2161775 6.2402992 6.2647414 6.2882122 6.3104244 6.9032910 7.3216611 7.6464142 7.9104545 8.1340866 8.3274409 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 2 2 2 2 2 3 3 3 3 4 26 28 27 31 27 27 26 29 28 27 33 27 26 27 29 28 28 33 27 28 33 29 29 27 29 29 29 28 29 30 0.025061 0.027066 0.026064 0.030073 0.026064 0.026064 0.025061 0.028068 0.027066 0.026064 0.032078 0.026064 0.025061 0.026064 0.028068 0.026064 0.026064 0.032078 0.025061 0.027066 0.031076 0.027066 0.027066 0.025061 0.027066 0.026064 0.026064 0.025062 0.026064 0.026064 1216 1280 1344 1408 1472 1536 1600 1664 1728 1792 1856 1920 1984 2048 2176 2304 2432 2560 2688 2816 2944 3072 3200 3328 3456 3584 3712 3840 3968 4096 10.5797636 10.6537093 10.7234819 10.7905204 10.8558274 10.9169641 10.9755471 11.0313155 11.0867588 11.1397614 11.1900650 11.2385736 11.2870085 11.3325767 11.4198410 11.5021737 11.5800870 11.6550679 11.7249838 11.7917189 11.8547999 11.9175576 11.9760081 12.0320870 12.0871429 12.1393587 12.1904356 12.2395965 12.2859574 12.3345439 6 6 6 6 6 6 6 6 6 6 6 7 7 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 34 32 33 34 34 35 33 34 34 33 32 32 30 33 32 32 35 35 35 34 33 33 31 35 32 35 33 34 33 32 0.028086 0.026085 0.027089 0.028093 0.028095 0.029099 0.027099 0.028102 0.028105 0.027107 0.026109 0.025112 0.023115 0.027119 0.025126 0.025134 0.028141 0.028149 0.028157 0.027167 0.026178 0.026188 0.024205 0.028205 0.025225 0.028226 0.026246 0.027254 0.026272 0.024299 2.2.3.4. Đánh giá về hàm AAF(k) K t quả 1: Trong h m vi k từ 1 đến 4096 ta có bất đẳng thức sau với xác suất tin cậy trên 0.998 log2(k)  AAF(k)  log2(k)+1 (2.29) hứng minh: Như đã được đánh giá trong ví dụ mục 2.2.2.4 a) thì |AAF(k)AAF(k,M)| < ( ) 3.1 k M  (2.30) 54 với 2(k) là phương sai của F(k) có xác suất tin cậy là 0.9990 22 hay nói một cách khác là xác suất sai của bất đẳng thức (2.30) là không đến 0.00 . Mặt khác th o bất đẳng thức (2.21) trong hệ quả trong mục 2.2.2.4 b) thì 2     22 s)1(ns)1(e)1(  (2.31) Ví dụ 2 mục 2.2.2.4 b) cho thấy xác suất sai của bất đẳng thức trên trong trường hợp M= 07 và =0.0000006908 là 0.001. Cho nên xác định giá trị (k) th o công thức (2.28) ta có (k)  M )k( 1.3  vì vậy ta có: AAF(k,10 7 )(k)  AAF(k)  AAF(k,107)+(k) (2.32) Với xác suất sai không đến 0.002 và do vậy xác suất tin cậy của (2.32) là trên 0.998. Từ số liệu thống kê về các giá trị AAF(k,107) và (k) tính được đưa ra trong bảng 2. ta có được kết quả , tuy nhiên để d quan sát hơn luận án đã thực hiện vẽ đồ thị của các hàm AAF(k, 07)(k), ký hiệu là AAF- , AAF(k,10 7 )+(k), được ký hiệu là AAF +, log2(k) và log2(k)+1 trong hình 2.1. Như vậy, bất đẳng thức trên là đúng và kết quả đã được chứng minh. Hình 2.1. ồ thị các hàm F(k,107)(k), AAF(k,107)+(k), log2(k) và log2(k)+1 trong khoảng [1, 4096]. 55 2.2.4. Ứng dụng của kết quả Trong thực tế, phép cộng là phép tính cơ sở cho việc thực hiện các phép tính như phép nhân điểm, lũy thừa, nghịch đảo trong các thuật toán mật mã. Luận án đã xây dựng được một công thức tính tương quan gần đúng giữa xung nhịp máy và phép cộng hai số nguyên khi thực hiện trên phần cứng, hay nói cách khác là số xung nhịp máy tiêu tốn trung bình cho phép cộng hai số nguyên. Kết quả này sẽ là cơ sở để đánh giá tính hiệu quả của một số phép nhân số lớn trong các thuật toán mật mã nhằm lựa chọn thuật toán mật mã hiệu quả nhất cho bài toán cụ thể. 2.3. Thực hiện thuật toán nh n i m trên ph n cứng FPGA 2.3.1. Phương pháp thiết kế chung Phương há thiết kế Mô hình phân lớp thiết kế được chỉ ra trong Hình 2.2. Quá trình thực hiện cài đặt thuật toán nhân điểm được thực hiện trên phần cứng FPGA (mức , mức 2, mức ) với chíp XC7Z045-2FFG900C của Xilinx Mức 5 Mức 4 Mức 3 Mức 2 Mức 1 P N CƠ TRÊN NG U N (c ng/t , nhân, chia/ngh ch đ o l n trên t ư ng GF(2^m)) C N TRÊN N C NG FPGAs P NH I Đ M TRÊN Đ NG CONG ELLIPTIC (c ng đi m: P+Q, nhân đôi : 2.P) P N N ÂN Đ M kP P N CƠ ÊN NG U N (c ng/t , nhân, chia/ngh ch đ o l n t ên GF(2m) G AO C AO ĐỔ K ÓA C O BẢO MẬ ỐNG M NG ĐA DỊC Ụ ( ử dụng ECD và ECD A) ECDH + ECDSA ( ử dụng phép nhân đi m k ) Hình 2.2. ô hình hân lớ thiết kế trên kit hát tri n Z 706 của Xilinx 56 Toàn bộ phần hoạt động của giao thức như thủ tục bắt tay, kiểm tra xác thực và điều khiển giao tiếp vào ra dữ liệu của ứng dụng sẽ được thực hiện trên bộ xử lý nhúng A M Cort x A9 của kit phát triển ZC70 của Xilinx. 2.3.2. Lựa chọn ường cong elliptic Trong rất nhiều các đường cong elliptic, không phải đường cong nào cũng có tính chất mật mã tốt. Trong nội dung luận án, đường cong lliptic trên trường GF(2n) th o khuyến nghị của NI T [48] được lựa chọn với các tham số như sau: - Tham số cho đường cong trên GF(n). - a thức bất khả quy 283 12 7 5( ) 1F x x x x x     (2.33) - i m cơ sở ( , )P PP x y trong đó Tọa độ điểm P: X =503213f78ca44883f1a3b8162f188e553cd265f23c1567a16876913b0c2ac2458492836P 1ccda380f1c9e318d90f95d07e5426fe87e45c0e8184698e45962364e34116177dd2259PY  - Bậc của đi m P (là số nguyên tố) n = 3885337784451458141838923813647037813284811733793061324295874997529815829704422603873 ồng thừa số (cofactor) h 4. Giá trị k: k = 3F00000FFFFFFFF800003800F8000E0000E000000FFFFFFE00000FFFFFFC0007E000000 2.3.3. Mô hình cứng h a thuật toán nh n i m 2.3.3.1. Module cứng h a phép nhân điểm elliptic trên FPGA Thực tế việc mô tả về lý thuyết, các cải tiến nhằm tăng tốc độ, hiệu năng thực hiện và thực hiện trên phần cứng cho phép nhân điểm đã được nhiều tác giả công bố, tuy nhiên phương pháp thực hiện cụ thể hầu như không được các tác giả trình bày. Trong phần này, luận án sẽ xây dựng mô hình thực hiện cứng hóa phép nhân điểm elliptic, mô hình này có thể áp dụng cho cả 3 thuật toán 2.1, 2.3, 2.4 được nêu ở trên và luận án sẽ thực hiện mô phỏng 57 với cả 3 thuật toán để so sánh đánh giá kết quả thực tế. Mô hình thực hiện cứng hóa phép nhân điểm như trên Hình 2.3, ta thấy modul cứng hóa cần sử dụng các modul cộng điểm lliptic, modul nhân đôi trên trường GF(2m). Trong phần tiếp theo luận án sẽ giới thiệu phương pháp cứng hóa các modul cộng điểm và modul nhân đôi trên trường GF(2 m ). Initial: K (K+ carry)/2 N ext_k C ng Đi m Nhân Đôi N ew _XP 0 Thanh ghi XP0, YP0 Initial: Xp, Yp N ew _YP0 XQYQ XP0 YP0 Thanh ghi XQ, YQ N ext_XQ N ext_YQ Q _infinity XP p-YP YP N ew _YQ N ew _XQ N EXT_XQ N EXT_YQ ạo c t ạng thái XP0 YP0 K+ carry_reg YP0 XP0 YP0 XP0 01 01 01 0110 YP0_tp 01 Hình 2.3. Sơ đồ thực hiện cứng hóa h nhân đi m elliptic. K(282:0) Xp(282:0) Yp(282:0) reset Xq(282:0) Yp(282:0) clk start done Nhân đi m Hình 2.4. Giao diện module cứng hóa h nhân đi m trên FPGA. 58 Giao diện của module cứng hóa thuật toán mật mã lliptic gồm các cổng sau: - Mầm khóa vào ngẫu nhiên vào: k kích thước 28 -bít. - Tọa độ điểm bí mật P: xP,yP có kích thước 28 -bít. - Tọa độ điểm Q (kết quả h nhân): xQ, yQ có kích thước 28 -bít. - Tín hiệu xung nhịp và r s t: clk, reset kích thước -bít. - Tín hiệu điều khiển quá trình tính toán: start kích thước -bít. Bắt đầu mã hóa mức ‘ ’, dừng quá trình mã hóa mức ‘0’. - Tín hiệu báo trạng thái: done kích thước -bít. Tính xong mức ‘ ’, chưa tính xong mức ‘0’. 2.3.3.2. Nguyên lý hoạt động của module Các giá trị khởi tạo ban đầu của modul nhân điểm lliptic: start ‘0’, reset ‘0’. Các tín hiệu trạng thái lúc ban đầu có giá trị: done ‘0’. Để thực hiện tính toán nhân điểm lliptic ta phải r s t lại toàn bộ modul phần cứng. Quá trình thực hiện bằng cách nâng tín hiệu r s t lên ‘ ’ sau đó hạ về ‘0’. Từ thời điểm này ta có thể bắt đầu quá trình tính toán phép nhân điểm lliptic. Trước hết cần ghi các tham số để tính toán k∙P bao gồm: Mầm ngẫu nhiên k, tọa độ xP, yP của điểm cơ sở P. Các tham số này được ghi vào thanh ghi đệm ở cổng k, xP, yP của modul . Tiếp theo là quá trình điều khiển tính toán phép nhân điểm lliptic bằng cách nâng tín hiệu start lên ‘ ’, quá trình tính toán phép nhân điểm bắt đầu. Khi tín hiệu trạng thái đầu ra done là mức ‘ ’ tức là quá trình tính toán phép nhân điểm k.P đã hoàn thành và cho giá trị kết quả ở cổng xQ và yQ. Để thực hiện tính toán phép nhân điểm lần tiếp th o ta thực hiện chuyển tín hiệu start xuống ‘0’, ghi các tham số mới vào cổng k, xP, yP và lắp lại quá trình như phần trên. 2.3.3.3. Thi t k cứng h a phép cộng điểm elliptic trên FPGA Phép cộng điểm lliptic được định ngh a trong [19] khi đó tọa độ điểm 59 R P Q  được xác định theo (1.1) như sau: 23 1 2 1x x x      ; 3 1 3 3 1( )y x x x y    với 1 2 1 2 y y x x     + Y1 Y2 + + + + mod F(x) nh Phương ( ) Mod F(x) X1 X2 Start_divide Divide_done 1 2 1 2 y y x x     2  2 1 2x x x3 X1 1 3( )x x   Start_mul Mul_done Y1 x3 y3 Hình 2.5. Sơ đồ thực hiện cứng hóa h cộng đi m elli tic. X1(282:0) X2(282:0) Y1(282:0) reset X3(282:0) Y3(282:0) clk start done C ng đi m Y2(282:0) Hình 2.6. Giao diện module thực hiện h cộng đi m elli tic trên FPG . Giao diện mức trên của module cứng hóa phép cộng điểm lliptic gồm: - Tọa độ điểm P(x1,y1), Q(x2,y2): có kích thước 283-bít. 60 - Tọa độ điểm R (kết quả h cộng đi m): x3, y3 có kích thước 283-bít. - Tín hiệu xung nhịp và r s t modul cộng điểm: reset, clk kích thước -bít. - Tín hiệu điều khiển quá trình tính toán modul cộng điểm: start kích thước 1-bít. Bắt đầu tính toán mức ‘ ’, dừng quá trình tính toán mức ‘0’. - Tín hiệu báo trạng thái modul cộng điểm: done kích thước -bít. Tính xong mức ‘ ’, chưa tính xong mức ‘0’. 2.3.3.4. Thi t k cứng h a phép nhân đôi điểm elliptic trên FPGA Mô tả module cứng hóa h nhân đôi elli tic. Phép nhân đôi điểm lliptic được định ngh a trong [19] với tọa độ điểm 2.R Q được xác định theo (1.2) như sau: 2 2 3 1 2 1 b x a x x       ; 2 3 1 3 3y x x x   với 1 1 1 y x x    Y1 + + mod F(x) Mod F(x) X1 Divide_done 1 1 1 y x x   2 2 1 x 1 2x x x3 3 * x  Start_mul Mul_done y3 nh Phương mod F(x)2 1 b x Start_divide Divide_done b Start_divide x3x1 2 3* x Hình 2.7. Sơ đồ thực hiện cứng hóa h nhân đôi đi m elli tic. 61 X1(282:0) Y1(282:0) reset X3(282:0) Y3(282:0) clk start done Nhân đôi Hình 2.8. Giao diện module thực hiện h nhân đôi đi m elli tic trên FPG . Giao diện mức trên của cor cứng hóa phép cộng điểm lliptic gồm: - Tọa độ điểm P(x1,y1), Q(x2,y2): có kích thước 28 -bít. - Tọa độ điểm (kết quả h cộng đi m): x3, y3có kích thước 28 -bít. - Tín hiệu xung nhịp và r s t modul cộng điểm: reset, clk kích thước -bít. - Tín hiệu điều khiển quá trình tính toán modul cộng điểm: start kích thước 1-bít. Bắt đầu tính toán mức ‘ ’, dừng quá trình tính toán mức ‘0’. - Tín hiệu báo trạng thái modul cộng điểm: done kích thước -bít. Tính xong mức ‘ ’, chưa tính xong mức ‘0’. 2.3.3.5. Thi t k cứng h a các module tính toán cơ s trên trường GF(2m) Như Hình 2.5, Hình 2.7 ta thấy để thực hiện phép cộng điểm, phép nhân đôi điểm lliptic trên FPGA cần thực hiện một số modul cơ sở sau: phép cộng modulo 2, phép nhân, phép bình phương, phép chia/nghịch đảo trên trường GF(2m). au đây luận án sẽ trình bày chi tiết giải pháp cứng hóa các phép tính cơ sở trên trường GF(2m). a) Ph cộng trong (2 )mGF Phép cộng trên (2 )mGF là phép toán đơn giản nhất, thực chất là phép cộng lật bit tương tự như phép XO trong phần mềm hoặc phần cứng. C  A + B (mod α)  (am-1  bm-1) α m-1 + + (a1  b1) α + (a0  b0) (2.34) Thuật toán 2.6: Phép cộng trong GF(2m) Input: 2 đa thức A(x), B(x) có bậc m-1 62 Output: C(x) = A(x) + B(x) 1. for i  0, m-1 do 2. C[i]  A[i]  B[i] 3. end for 4. return C b) odule thực hiện h nhân trên trường GF(2m). Để thực hiện cứng hóa phép nhân đa thức trên trường GF(2m) cần thực hiện các thuật toán sao cho quá trình nhân chỉ sử dụng các phần tử cơ bản trong phần cứng là AND, XO tương ứng với các phần tử cơ bản trong FPGA là CLBs và LUTs. Trong nội dung luận án sẽ thực hiện cứng hóa phép nhân th o phương pháp nhân đan x n (Interleaved Multiplication) [33], [34] Nhân đan x n là một thuật toán hiệu quả, d thực hiện trong phần cứng Thuật toán sử dụng phép dịch bit và cộng modulo 2 là các thành tố cơ bản, kết hợp với bước tính modulo lặp. Phương pháp thực hiện như sau: 1 1 0 0 ( ) ( ) ( )mod ( ) ( )( )mod ( ) ( ) mod ( ) m m i i i i i i C x A x B x F x A x b x F x b A x x F x                Vì vậy sau khi khai triển biểu thức nhân trong ngoặc ta được kết quả C(x) như sau:  2 10 1 2 1( ) ( ) ( ) ( ) .... ( ) mod ( )mmC x b A x b A x x b A x x b A x x F x     (2.35) X m xét phương trình trên ta thấy, để tính toán được C(x) ta cần tính toán các phần tử có dạng : D(x) = x∙ (x) mod F(x) Trong đó 2 10 1 2 1( ) .... m mA x a a x a x a x       với (2 ) m ia GF . (2.36) ử dụng tính chất 2 11 2 1( ) 1 .... m m mF x f x f x f x x        với F(x) là đa thức bất khả quy bậc m: 2 1 1 2 11 .... m m mx f x f x f x       (2.37) Thay giá trị xm vào phương trình D(x) ta được: 63 2 1 0 1 2 1( ) .... m mD x d d x d x d x       (2.38) Với 0 1md a  và 1 1; 1..( 1)i i m id f a a i m     . Như vậy việc tính toán D(x) chỉ cần sử dụng các phép toán AND-2 đầu vào và XO -2 đầu vào, cụ thể mạch AND-2 sử dụng để tính x.A(x) bao gồm (am-1 AND f0, am-1 AND f1, ..., am-1 AND fm-1) và phép XO -2 sử dụng để tính phép cộng modulo 2 giữa hai vector X, Y tương ứng (x0 XOR y0, x1XOR y1, ...,xm-1 XOR ym-1,). Có hai phương pháp thực hiện thuật toán nhân lặp [34] là M B và L B. Phương pháp M B thực hiện nhân bit có trọng số cao nhất của B(x) trước và L B thực hiện nhân bit có trọng số thấp nhất của B(x) trước. Trong luận án chỉ giới thiệu phương pháp L B ( hương há SB c ng gần tương tự). Phương pháp L B thực hiện xử lý từ bit có trọng số thấp nhất (b0) của B(x) trước, nên quá trình xử lý có dạng sau: (2.39)  2 10 1 2 1mod ( ) ( ) ( ) ... ( ) mod ( )mmC A B F b A x b A x x b A x x b A x x F x               20 1 2 1( ) ( ) ( ) .... ( ) mod ( )mmC b A x b A x x b A x x x b A x x x F x      Thuật toán 2.7: Thuật toán nhân đan x n th o L B [34] Input: Đa thức bất khả quy F(x) bậc m, hai đa thức (x) và B(x) thuộc (2 )mGF Output: ( ) ( ) ( )mod ( )C x A x B x F x  Thực hiện: Bước 1:C(x) = 0; Bước 2: Cho i = 0 đến m – thực hiện: Bước 2.1: ( ) ( ) ( )iC x C x b A x   ; Bước 2.2: ( ) ( ) mod ( )A x A x x F x  ; Bước 3: Trả về C(x). Từ đây ta có thể xây dựng sơ đồ cứng hóa modul nhân đan x n như sau: 64 MUX TEMP_A(x) 283 bit Thanh ghi & 00 0 a282a282a282a282 . f0f1f281f282 & 00 0 & 00 0 & 00 0 a281 a280 a0 NEW_A(x) 283 bit a232 A(x) 283 bit Thanh ghi & 00 0 & 00 0 B(x) 283 bit Thanh ghi dịch & 00 0 bi bia0a1 a281a282 . . . NEW_C(x) 283 bit Thanh ghi Inc Ce Inc Shift_right Inc C(x) 283 bit Thanh ghi c0c1c281c282 OLD_C(x) reset reset reset reset re se t B_IN A_IN Kết quả C_Out Hình 2.9. Sơ đồ cứng hóa phép nhân theo thuật toán nhân đan xen. A(282:0) B(282:0) reset C(282:0) clk start done Nhân đan xen Interleaved_mult Hình 2.10. Giao diện module thực hiện h nhân đi m trên FPGA. Tương tự như giải pháp thiết kế và điều khiển các modul cứng hóa phép nhân điểm, cộng điểm. Modul thực hiện phép nhân trên GF(2m) gồm: - Giá trị thừa số A, B: kích thước 283 bít. - Kết quả phép nhân Z: kích thước 283 bít. 65 - Tín h