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ụ

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 1
mọi >0 cho trước ta có Prob(1 p > )= 1  (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)) = pM (2.17) 
Từ (2.17) ta có 
 v
 M
 Porb(B.(u ≤ Prob(A) ≤ v)) = p dp (2.18) 
 u
Vì (0 ≤ Prob(A) ≤ ) là sự kiện chắc chắn nên từ (2.18) ta có kết quả 
 49 
 1
 M
 Porb(B) = Porb(B.(0 ≤ Prob(A) ≤ )) = p dp (2.19) 
 0
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: 
 v
 Prob ( B .( u Pr ob ( A ) v )) pM dp
 Porb((u ≤ Prob(A) ≤ v)/B) = = u (2.20) 
 1
 Prob ( B ) pM dp
 0
Với u=0, v= -  và trong biểu thức (2.20) thay Prob(A) bằng p ta có 
 1 
 pM dp
 0 M 1
 Prob(1 p > ) = 1 = 1  
 pM dp
 0
 như vậy (2. ) đã được chứng minh. 
Ví dụ 2. Với M= 07 và =0.0000006908 ta có 1  M 1= 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) 
 s e n
min  ; . 
 22
Khi đó với mọi 0<<1 ta đánh giá 
 22
 2 (1  ) e (1  ) s  n (1  ) s . (2.21) 
Thì xác suất sai lầm lo i 2 của đánh giá trên là  = 1  M 1. 
 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 > ) = 1  M 1 
Đ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à 1  M 1. Ta có 
 s 1 e n e
 E(X) = i pi + i pi + i pi s  pi = (1 ) s (2.22) 
 i 1 i s i e 1 i s
 50 
 s 1 e n
 2 2 2 2
  = pi i E(X) + pi i E(X) +  pi i E(X) (2.23) 
 i 1 i s i e 1
 s e n  2
Từ điều kiện (2.22) và E(X) min ;  nên các giá trị (i E(X)) trong 
 2 2
tổng thứ hai trong vế phải của (2.23) thỏa mãn 
 (2.22)
 (i E(X))2 < (e E(X))2 (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 
 (2.22)
 (i E(X))2 < (n E(X))2 (n (1 ) s)2 (2.25) 
Thay (2.24) và (2.25) vào (2.23) ta được 
 e s 1 n
 2 2 2 
  e (1 ) s  pi + n (1 ) s  pi  pi 
 i s i 1 i e 1 
 (1 ) e (1 ) s 2  n (1 ) s 2 
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: 
 7 7 7
 AAF(k,10 )=Total(k,10 ) 10 (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 
 7
(i= ,..., ). Các số liệu được ghi trong bảng bao gồm: k, AAF(k, 0 ), fs(k), 
 52 
fe(k) và (k). 
 7
 Các số liệu AAF(k, 0 ), 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: 
 22
 (1  )(fe (1  ) f s )  ( k 1(1  ) f s )
 (k) = 3.1 7 (2.28) 
 10
 Bảng 2.1. Kết quả thống kê 112 giá trị của k 
 7 7
 k AAF(k,10 ) fs (k) fe (k) (k) k AAF (k,10 ) fs (k) fe (k) (k) 
 15 4.1399501 0 16 0.016039 288 8.4977167 4 30 0.026065 
 16 4.2386532 0 17 0.017042 320 8.6502339 4 34 0.030074 
 17 4.3320945 0 18 0.018044 352 8.7886398 4 33 0.029072 
 18 4.4200825 0 19 0.019046 384 8.9146046 4 31 0.027068 
 19 4.5026766 0 20 0.020049 416 9.0295142 4 31 0.027068 
 20 4.5807384 0 21 0.021051 448 9.1369311 5 30 0.025064 
 21 4.6553482 0 22 0.022054 480 9.2362259 5 31 0.026067 
 22 4.7249131 0 23 0.023056 512 9.3298887 5 31 0.026067 
 23 4.7923977 1 23 0.022054 544 9.4175886 5 30 0.025065 
 24 4.8568043 0 24 0.024059 576 9.5004907 5 32 0.027070 
 25 4.9183709 1 23 0.022054 608 9.5784751 5 33 0.028073 
 26 4.9770195 1 24 0.023056 640 9.6527988 5 32 0.027071 
 27 5.0349873 1 25 0.024059 672 9.7229998 5 34 0.029076 
 28 5.0876514 1 24 0.023056 704 9.7910969 5 31 0.026070 
 29 5.1409723 1 25 0.024059 736 9.8535831 5 34 0.029077 
 30 5.1919811 1 24 0.023056 768 9.9160444 5 34 0.029078 
 31 5.2410299 1 26 0.025061 800 9.9746949 5 33 0.028076 
 32 5.2881423 1 27 0.026063 832 10.0314707 5 33 0.028077 
 33 5.3332005 1 25 0.024059 864 10.0860103 6 31 0.025071 
 34 5.3778501 1 25 0.024059 896 10.1386865 5 32 0.027076 
 35 5.4209489 1 28 0.027066 928 10.1888623 5 34 0.029081 
 36 5.4637941 1 27 0.026064 960 10.2389178 6 35 0.029082 
 37 5.5035587 1 26 0.025061 992 10.2861217 5 32 0.027078 
 38 5.5434711 1 27 0.026064 1024 10.3310832 5 34 0.029083 
 39 5.5817211 1 26 0.025061 1088 10.4188155 6 33 0.027081 
 40 5.6189158 1 26 0.025061 1152 10.5008227 6 35 0.029087 
 53 
 41 5.6558295 1 26 0.025061 1216 10.5797636 6 34 0.028086 
 42 5.6920440 1 28 0.027066 1280 10.6537093 6 32 0.026085 
 43 5.7259800 1 27 0.026064 1344 10.7234819 6 33 0.027089 
 44 5.7601316 1 31 0.030073 1408 10.7905204 6 34 0.028093 
 45 5.7937005 1 27 0.026064 1472 10.8558274 6 34 0.028095 
 46 5.8254527 1 27 0.026064 1536 10.9169641 6 35 0.029099 
 47 5.8576532 1 26 0.025061 1600 10.9755471 6 33 0.027099 
 48 5.8874458 1 29 0.028068 1664 11.0313155 6 34 0.028102 
 49 5.9189435 1 28 0.027066 1728 11.0867588 6 34 0.028105 
 50 5.9480496 1 27 0.026064 1792 11.1397614 6 33 0.027107 
 51 5.9780568 1 33 0.032078 1856 11.1900650 6 32 0.026109 
 52 6.0063450 1 27 0.026064 1920 11.2385736 7 32 0.025112 
 53 6.0338280 1 26 0.025061 1984 11.2870085 7 30 0.023115 
 54 6.0620954 1 27 0.026064 2048 11.3325767 6 33 0.027119 
 55 6.0884972 1 29 0.028068 2176 11.4198410 7 32 0.025126 
 56 6.1156798 2 28 0.026064 2304 11.5021737 7 32 0.025134 
 57 6.1410676 2 28 0.026064 2432 11.5800870 7 35 0.028141 
 58 6.1666951 1 33 0.032078 2560 11.6550679 7 35 0.028149 
 59 6.1914261 2 27 0.025061 2688 11.7249838 7 35 0.028157 
 60 6.2161775 1 28 0.027066 2816 11.7917189 7 34 0.027167 
 61 6.2402992 2 33 0.031076 2944 11.8547999 7 33 0.026178 
 62 6.2647414 2 29 0.027066 3072 11.9175576 7 33 0.026188 
 63 6.2882122 2 29 0.027066 3200 11.9760081 7 31 0.024205 
 64 6.3104244 2 27 0.025061 3328 12.0320870 7 35 0.028205 
 96 6.9032910 2 29 0.027066 3456 12.0871429 7 32 0.025225 
 128 7.3216611 3 29 0.026064 3584 12.1393587 7 35 0.028226 
 160 7.6464142 3 29 0.026064 3712 12.1904356 7 33 0.026246 
 192 7.9104545 3 28 0.025062 3840 12.2395965 7 34 0.027254 
 224 8.1340866 3 29 0.026064 3968 12.2859574 7 33 0.026272 
 256 8.3274409 4 30 0.026064 4096 12.3345439 8 32 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ì 
  ()k
 |AAF(k) AAF(k,M)| < 3.1 (2.30) 
 M
 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 (1 ) e (1 ) s 2  n (1 ) s 2 (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)
 (k) 3.1 vì vậy ta có: 
 M
 AAF(k,107) (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- , 
 7
AAF(k,10 )+ (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. 
 7 7
 Hình 2.1. ồ thị các hàm F(k,10 ) (k), AAF(k,10 )+ (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 
 G AO C AO ĐỔ K ÓA C O BẢO MẬ ỐNG M NG 
 Mức 5 ĐA DỊC Ụ 
 ( ử dụng ECD và ECD A)
 Mức 4 ECDH + ECDSA ( ử dụng phép nhân đi m k )
 C N TRÊN N C NG FPGAs
 Mức 3 P N N ÂN Đ M kP
 Mức 2 P NH I Đ M TRÊN Đ NG CONG ELLIPTIC
 (c P n g N đ i C Ơm : P +TRQÊ,N n h â n đNôGi : 2U.P ) N
 (c ng/t , nhân, chia/ngh ch đ o l n trên t ư ng GF(2^m))
 P N CƠ ÊN NG U N 
 Mức 1 m
 (c ng/t , nhân, chia/ngh ch đ o l n t ên GF(2 )
 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: 
 n
 - Tham số cho đường cong trên GF( ). 
 283 12 7 5
 - a thức bất khả quy F( x ) x x x x 1 
 (2.33) 
 - i m cơ sở P(,) xPP y trong đó 
Tọa độ điểm P: 
 XP =503213f78ca44883f1a3b8162f188e553cd265f23c1567a16876913b0c2ac2458492836
YP 1ccda380f1c9e318d90f95d07e5426fe87e45c0e8184698e45962364e34116177dd2259
 - 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(2m). 
 X
 Y
 P
 P
 0
 0
 K+ carry_reg
 Y
 P
 0
 (K+ carry)/2
 1 0
 N
 X
 X
 Y
 e
 P
 Q
 Q
 Y
 x
 0
 t
 P
 _
 0
 k
 _
 t
 p
 C ng Đi m Initial: K
 N
 e
 w
 p
 _
 Y
 N
 X
 X
 Y
 -
 Y
 P
 P
 e
 Y
 P
 P
 Q
 0
 0
 w
 P
 _
 X
 ạo c t ạng thái
 Q
 1 0
 1 0 1 0
 Y
 P
 0
 0 1 1 0
 X
 P
 0
 N
 N
 E
 E
 X
 X
 T
 T
 _
 _
 X
 Y
 Q
 Q Nhân Đôi
 N
 N
 e
 e
 w
 w
 0
 _
 _
 Y
 Thanh ghi XQ, YQ X
 P
 P
 0
 Thanh ghi XP0, YP0
 Q
 N
 N
 _
 e
 e
 i Initial: Xp, Yp
 n
 x
 x
 t
 f
 t
 i
 _
 _
 n
 X
 Y
 i
 t
 Q
 Q
 y
 Hình 2.3. Sơ đồ thực hiện cứng hóa h nhân đi m elliptic. 
 K(282:0) done
 Xp(282:0)
 Nhân đi m
 Yp(282:0) Xq(282:0)
 clk
 reset
 start Yp(282:0)
 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 
 RPQ được xác định theo (1.1) như sau: ; 
 với 
 Y1 Y2 X1 X2
 + +
 Start_divide
 yy12 
 Divide_done  mod F(x)
 xx12 
 
 xx12
 nh Phương 
 (  2 )
  2 +
 x3 X1
  +
 Start_mul
 Mul_done
 ()xx13 Mod F(x)
 x3
 Y1
 +
 y3
 Hình 2.5. Sơ đồ thực hiện cứng hóa h cộng đi m elli tic. 
 X1(282:0)
 X3(282:0)
 X2(282:0)
 Y1(282:0)
 C ng đi m
 Y2(282:0) done
 clk
 2
 x3  xr 1es et x 2 1
 start Y3(282:0)
 yy12 
 y3 () x 1 x 3 x 3 y 1  
 Hình 2.6. Giao diện module thực hiện h cộng đixx 12m 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ểm22 R (kết quả h b cộng đi m): x3, y3 có kích thước 283-bít. 
 x31  a x 2
- Tín hiệu xung nhịp và r s t xmodul1 cộng điểm: reset, clk kích thước -bít. 
- Tín hiệu điều2 khiển quá trình tính toán moduly1 cộng điểm: start kích thước 
 y3 x 1  x 3 x 3  x1
 1-bít. Bắt đầu tính toán mức ‘ ’, dừng quáx1 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 
 RQ 2. được xác định theo (1.2) như sau: ; 
 với 
 X1
 nh Phương 
 b Y1
 2
 x1
 Start_divide Divide_done
 b 2 y1
 Divide_done   x1 mod F(x)
 2 mod F(x) Start_divide
 x1
 x1
 xx12
 
 +
 x3
 Start_mul
 Mul_done
  * x3 Mod F(x)
  * x3
 2
 x1 + x3
 y3
 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) X3(282:0)
 Y1(282:0)
 Nhân đôi
 clk done
 reset
 start Y3(282:0)
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 GF(2m ) 
 Phép cộng trên 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. 
 m-1
C  A + B (mod α)  (am-1  bm-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: 
 mm 11 
 ii 
 Cx() AxBx ()()mod() Fx Ax ()( bxii )mod() Fx bAxx () mod() Fx
 ii 00 
 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: 
Cx() bAx () bAxxbAxx () ()21 .... bAxx ()m mod() Fx 
 0 1 2m 1 (2.35)
 X