Một giải pháp cứng hóa phép nhân điểm Elliptic trên trường GF(p)

Journal of Science and Technology on Information Security 
 M g ả pháp cứ ó ể 
 E GF(p)
 Nguyễn Văn Long, Hoàng Văn Thức
 Tóm tắt— Bài báo này mô tả thuật toán và P ể ệ ự ệ 
cấu trúc mạch cho việc tính toán và thực thi phép phép tính k*P, ó k 1 ố P là 
tính nhân điểm đường cong Elliptic trên trường ể E ợ 
nguyên tố hữu hạn GF(p) có độ dài 256 bit. Cấu ị ĩ GF(p) [2]. 
trúc mạch được mô tả bằng ngôn ngữ VHDL và 
được thực thi trên nền tảng chip Zynq xc7z030 và T ậ ự ệ ể 
xc7z045. : 
 Abstract— This paper describles an Thuật toán 1: 
algorithm and structure for computing and 
 Đầ : 
implementation point multiplications on Elliptic k ( ktp 1 ,...,, k 1 k 0 ), 2 P E ( F )
cuvers defined GF(p) with 256 bits length. The 
circuits have been describled in VHDL in Đầ : kP 
implemented on chip Zynq xc7z030 and xc7z045. 1. Q  
 Từ khóa— FPGA; Đường cong elliptic trên 
 2. cho i ạ ừ t-1 ế 0 ự ệ 
trường GF(p); nhân điểm. 
 Keywords—FPGA; Elliptic cuvers over 2.1 QQ 2 
GF(p); Point multiplication. 
 2 2 ế ki=1 thì QQP 
 I. GIỚI THIỆU VÀ MÔ TẢ THUẬT TOÁN 3 T ả ề Q 
 NHÂN ĐIỂM Thuật toán 2: 
 P ả Đầ : 
 ậ ậ 
 ể ố Đầ : kP 
 V ệ 1. 
 ứ ạ , ố ề ố 
do ả ự ệ 2. cho i ạ ừ 0 ế t-1 ự ệ 
 ứ ả ậ . T ự ứ ó 
 2 1 Nế ki=1 thì QQP 
 ể FPGA ú ố 
 ả ự ệ , 2.2 PP 2 
ứ ợ ầ ự ế Trong 3 ả ề Q 
 ú ô ì , Đố T ậ 1 [8], ò ặ ạ 
 ự ố ậ ự ố tài 2 1 2 2 ề ế ả là ị 
 ệ ô ì ứ ế Q Kế ả ầ ạ 2 1 ị ầ 
 , ể ừ ó ở ệ ứ 2 2 D ậ ì ự ệ 
 ế ế ứ ó ể ệ ả ố ế ế ú 2 1 ồ 
cong elliptic, ợ ứ ụ ứ ế 2 2 T ó, ở T ậ 2, 
 ó : ECDH, ECHMQV, ố ò ặ ạ 2 ế ả 
ECDSA [1][7], ó ECIES [6]. 2 1 Q 2 2 là P, ợ 
 ự ệ ậ ô ụ 
 ự ệ ó ể 
 ể ố ự 
 T ú ô ự ậ 
 Bài báo ợ ậ ngày 4/9/2018 B ợ ậ 2 ể ế ế ứ ó ể ề 
x ở ả ệ ứ vào ngày 28/10/2018 và ợ 
 ậ ă vào ngày 8/11/2018. Bài báo ợ ậ x ở ả ầ ứ FPGA 
 ả ệ ứ vào ngày 10/11/2018 và ợ ậ T ậ 1 ậ 
 ă ngày 21/11/2018. 
 2 ò ặ ử ụ ể 
52 Số 2.CS (08) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 ô ể . Hai phép tính ợ ể Nếu c1 = 0 và c2 = 0 thì z := z1 mod 2k; 
 ệ : Không thì z := z2 mod 2k; 
 T ậ ô ể : ể Kết thúc. 
 thì x y
P( x11 , y ) E ( Fp ), P P
 ợ : 
2P ( x33 , y )
 c
 2 1 k – bit
 2 Bộ cộng 
 3xa1 
 xx 2 k
 31 Z1 mod 2 2k - p
 2y1
 2
 c2
 3xa1 k – bit
 Bộ cộng 
 y3 x 1 x 3 y 1
 2y k
 1 z2 mod 2
 T ậ ể : 0 1 
P (,) x1 y 1 E (), Fpp Q (,) x 2 y 2 E (), F 
 z 
PQ Hì 1 C ú ố GF( ) 
Thì ợ : 
 P Q(,) x33 y B. Thiết kế cứng hóa phép trừ số lớn trên 
 2 trường GF(p) 
 yy21 C ố ự x, y: 
 x3 x 1 x 2
 xx 
 21 x, y p 0,1,..., p 1 T ầ ị 
 yy21 ủ x và y trên p : 
 y3 x 1 x 3 y 1
 xx21 z x y mod p . Ta có p x y p do 
 Trong p ầ ế ủ , chúng tôi ó z ả ằ ị x - y 
 ũ ẽ ì ậ ế ú ầ ặ x - y + p Từ x ự ậ ể 
 ứ ủ ố ố ụ ụ tính toán z : 
 ệ ứ ó ể Mụ II T ậ ừ GF( ) 
Mụ III Cụ ể ợ ì ở ụ Tổng := x + (2k-y); 
 Mụ IV Kế ả ự ệ ố ù k
 Mụ Kế ậ z1 := Tổng mod 2 ; 
 z2 := z1 + p mod 2k; 
II. THIẾT KẾ CỨNG HÓA CÁC PHÉP TÍNH c1 := Tổng/2k; 
 SỐ LỚN CƠ SỞ 
 Nếu c1 = 0 thì z := z1; 
A. Thiết kế cứng hóa phép cộng số lớn trên 
trường GF(p) Không thì z := z2; 
 C ố ự x,y: Kết thúc. 
 y
x, y 0,1,..., p 1 T ầ 
 p x
 ị ủ x và y trên : 
 p 2k – y 
 c
z x y mod p . Ta có 02 x y p do 1 k – bit
 Bộ cộng 
 z1
 ó z ả ằ ị x+ p
 ặ x+ – Từ x ự ậ ể 
 k – bit
 z : Bộ cộng 
 z2 
 T ậ GF( ): 
 0 1 
 z1 := x + y; 
 z2 := (z1 mod 2k) + (2k-p); z 
 c1 := z1/2k; Hì 2 C ú ừ ố trên GF(p) 
 c2 := z2/2k; 
 Số 2.CS (08) 2018 53 
Journal of Science and Technology on Information Security 
C. Thiết kế cứng hóa phép nhân số lớn trên ả GF( ), 
trường GF(p) z x. y mod p 
 P GF( ) ợ ị T ậ GF( ): 
 ĩ : r := 0; 
 C a. b mod p ,  a , b p với i in 0 to k-1 lặp: 
 Để ự ệ ứ ó ứ r := (r +r) mod p; 
 GF( ) ầ ự ệ , 
 if x(k-i-1)=1 thì r := r + y mod p; 
 ứ ố a và b, 
 ứ ế ả kết thúc nếu; 
 p. kết thúc lặp; 
 Có ề ậ ử ụ ể kết quả := r; 
 ự GF( ), ố y
 ó ó ậ ợ ầ ứ , ầ 
 0 1
 ề ặ ầ ụ C ậ ử ụ Step_type
 ầ ứ ầ ế ế ì p
 ử ụ ầ ử ả ầ ce_r
 ứ AND, OR, , MU x y p
ứ ầ ử ả FPGA Bộ cộng modulo p
CLB LUT V ế z
 Shift update
 ó ề ô ố ả Mạch tổ Thanh ghi dịch 
 ce hợp 256 - bit
 ể ự ệ ậ 
 Thanh ghi 256-bit x(i) load
GF( ), ó ể ó ạ ố clear load
 load
 : r
 - P ồ (multiply and z 
then divide) Hì 3 C ú ố GF(p) 
 - P x (Interleaving) D. Thiết kế cứng hóa phép chia/nghịch đảo trên 
 - P M (nhân trường GF(p) 
Montgomery). H ệ ạ , chúng tôi ự ệ P ị ả ợ 
 ứ ó ủ a/b a = 1 T x 
 x , ễ ự ệ ề ợ , ố ự a, b: 
 ả ầ ứ ử ụ 
 T ầ 
và phép nhân 2. T ắ ú a, b p 0,1,..., p 1
 ô ẽ ứ ề ò ạ 
 ị ủ a và b trên p : 
P x ẽ ợ làm rõ 
 . (1) 
trong ậ x ẫ tài z a/ b mod p
 ệ [4], [5]. T ậ x ợ trình Để ể ứ (1) ó ề ậ 
bày : toán khác nhau (thuật toán Euclidean thuật toán 
 C ố ự x, y: nhị phân, thuật toán cộng-trừ và thuật toán tính 
x, y 0,1,..., p 1 T ầ nghịch đảo theo định lý Fermat’s Little) trong 
 p ầ ú ô ự ậ ị 
 ị ủ x và y trên p : ể ế ế ị ả 
z x. y mod p . Ta có GF(p). 
 C ố ự a, b: 
x. y x .2kk 1 x .2 2 ... x .2 0 y
 kk 1 2 0 
 a, b p 0,1,..., p 1
 (...(0.2 x y )2 x y )2 ... x y )2 x y
 kk 1 2 1 0 - Nế ả ố ề , ó ó: 
 , ó GCD(a,b) = 2.GCD(a/2, b/2) 
 ể ử ụ ằ ô ó - Nế ó ố , ả ử ì 
 ự ệ ú ( ) ẽ ợ ế GCD(a, b) = GCD(a, b/2). 
 - Nế ô ó ố ả ử a ≥ b 
54 Số 2.CS (08) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 ì ó GCD(a,b) = GCD(a, a -b) 
 yy21 
 y3 () x 1 x 3 y 1  
 ó a – b ố xx 
 Lặ ạ ì ố ạ m 21
 ẽ ì ợ ố x ị GCD(a ,b) 
= GCD( a p , 0) Từ ó ể x ự ậ 
 a
 zp mod : 
 b
 T ậ ị ị ả 
 GF(p): 
 a := p; b := y; c := 0; d := x; 
 Trong khi a > 1 lặp 
 Trong khi (b mod 2) = 0 lặp 
 b := b/2; d := Divide_By_2(d, P); 
 Kết thúc lặp; 
 Nếu b >= a thì b := b-a; d := (d-c) mod 
 P; Nếu không thì 
 Old_b := b; b := a-b; a := Old_b; 
 Old_d := d; d := (c-d) mod P; c := Old_d; 
 Kết thúc nếu; 
 Kết thúc lặp; Hì 5 C ú ể 
 GF(p) 
 Z := c; 
 a b b a a b d p d c c d c d B. Thiết kế cứng hóa phép nhân đôi điểm 
 Elliptic trên trường GF(p) 
 Bộ cộng theo điều 
 Bộ trừ Bộ trừ Bộ trừ Bộ trừ
 kiện b0 P ô ợ ị ĩ 
 d+b0p ở ầ ó ể RP 2 ợ 
 /2
 0 1 0 1 0 1 0 1 2
 x ị : xx31  2
 d2-1 mod p d-c/c-d ; 
 0 c
 p a a/b y b/2 b-a/a-b 2
 x 3xa 
  1
 0 1 2 0 1 2 0 1 2 0 1 2 2y
 1 
 ce
 ce ce ce ce
 Thanh ghi Thanh ghi Thanh ghi Thanh ghi 
 k – bit k – bit k – bit k – bit 
 a b d z.c
 Hình 4. C u trúc phép chia/nghị ảo theo thuật 
 toán nhị ng GF(p) 
 III. THIẾT KẾ CỨNG HÓA PHÉP NHÂN 
 ĐIỂM ELLIPTIC TRÊN TRƯỜNG GF(p) 
A. Thiết kế cứng hóa phép cộng điểm Elliptic 
trên trường GF(p) 
 P ể ợ ị ĩ 
 ở ầ ó ể 
 RPQ 
 ợ x ị : 
 2 Hì 6 C ú ô ể 
 x3  x 1 x 2 GF( ) 
 Số 2.CS (08) 2018 55 
Journal of Science and Technology on Information Security 
C. Thiết kế cứng hóa phép nhân điểm Elliptic IV. KẾT QUẢ THỰC HIỆN 
trên trường GF(p) M ể 
 V ệ ứ ó ể GF( ) ợ ú ô ợ 02 ề 
 GF( ) ì ố chip xc7z030 x 7z045 ợ ứ 
 ế ế ứ ó ở ụ , ú ụ ề “N ứ ế 
 ự ệ ể ế, ế ạ ả ậ ầ ứ HSM, 
GF( ) : ứ ụ ệ ố ả ậ x 
 ự ô ” D ế ả ợ 
 ể 02 ề ả ầ ứ 
 K+ carry_reg
 p
 Y
 -
 Y
 P khác nhau 
 P
 0
 0
 (K+ carry)/2
 1 0 Bả 1. Kế ả ặ ậ 
 N
 X
 Y X
 e
 P
 Q Q
 Y
 x
 0
 t
 P
 _
 0
 k
 _ ể ề ả ầ ứ FPGA 
 t
 p
 Cộng Điểm Initial: K Tầ ố Tài 
 N
 e
 w T ậ C ề 
 _
 Y
 p ạ nguyên 
 Y
 Y
 X
 -
 P
 X
 Y
 N
 Q
 P
 P
 0
 P
 P
 e
 0
 w
 _ Tạo cờ trạng thái toán Chip dài 
 X
 1 0 ế ế 
 1 0
 Q
 1 0
 Y nhân FPGA ỗ 
 P
 0
 X
 P
 1 0
 0
 0 1 ể bit (M (L
 N
 N
 E
 E
 X
 X
 Q
 Q
 T
 T
 _ Hz) UTs) 
 _
 X
 Y Nhân Đôi
 N N
 e e
 w w
 0 0
 _ _
 Thanh ghi XQ, YQ X Y
 P P Xc7z030 136.1 34472 
 Initial: Xp, Yp
 Q
 Y X
 _
 Q Q
 i
 n
 f
 i
 n T ậ 
 i
 t
 y Xc7z045 256 157.3 34486 
 toán 1 
 Hì 7 C ú ể 
 GF( ) 
 V. KẾT LUẬN 
 G ệ ự ệ ể 
 GF( ) ự ô ệ T ó ả ì 
FPGA: ệ , , ự ậ 
 ể ố ậ ự ệ 
 ở ệ ậ 
 Để ừ ó ở ệ ế ế ứ ó 
 phép tính ở ụ II và phép ể 
 ụ III T ể 
 FPGA ằ n ô ô ả ầ ứ HDL 
 VHDL Đ ế ả ợ ề 
 ế ế, ầ ố ạ ủ 02 
 FPGA x 7z030 x 7z045 Kế ả 
 ạ ị , ứ ợ ầ 
 ề , ợ ứ ụ ề 
 “N ứ ế ế, ế ạ ả ậ 
 ầ ứ HSM, ứ ụ ệ ố 
 ả ậ x ự ô ” 
 Hì 8 G ệ ể 
 GF( ) 
56 Số 2.CS (08) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 TÀI LIỆU THAM KHẢO SƠ LƯỢC VỀ TÁC GIẢ 
[1]. American Bankers Association. ANSI X9.62- KS. Nguyễn Văn Long 
 1998: Public Key Cryptography for the Đ ị ô : V ệ K – 
 Financial Services Industry: The Elliptic Curve Cô ệ ậ , B C ế 
 Digital Signature Algorithm (ECDSA). ủ 
[2]. N. Koblitz, S. Vastone, and A. Menezes. The Email: longyenkk2@gmail.com 
 State of Elliptic Curve Cryptography, Design, Q ì ạ : N ậ ằ ỹ 
 Codes and Cryptography, 19(2/3):173-193, ă 2014 
 March 2000. H ứ ệ : Cô ệ ạ , 
[3]. J. Lutz. High Performance Elliptic Curve FPGA, ô ệ ú L x 
 Cryptographic co- M ’ , 
 University of Waterloo, 2003. 
 TS. Hoàng Văn Thức 
[4]. Đề tài c B “N ứu thiết kế, chế tạo 
 module bảo mậ ặt an toàn, cứng hóa các Đ ị ô tác: V ệ K - 
 Cô ệ ậ , B C ế 
 thuật toán GOST (28147-89, R34.11-2012, 
 C ủ. 
 R34.10-2012) dựa trên công nghệ FPGA” B 
 C ếu Chính phủ, Thực hiện 2015- 2016. Chủ Email: thuchv@yahoo.com 
 nhiệm Nguyễ B C Q ì ạ : N ậ ằ ỹ 
 ă 1998 T ạ ĩ ă 2004 
[5]. SEC1. Elliptic Curve Cryptography: Standards 
 for Eficient Cryptography Group, Kỹ ậ ậ , 
 H ệ Kỹ ậ ậ N ậ ằ T ế ĩ T 
 , V ệ K - Cô ệ q ự ă 2012 
[6]. TC03-2:2015, “Thuật toán chữ ký số ECDSA”, 
 H ứ ệ : K - Cô ệ 
 B ếu Chính phủ. Mậ 
[7]. The FIPS 186-3 Elliptic Curve Digital Signature 
 Algorithm Validation System (ECDSA2VS), 
 January 17, 2012. 
[8]. Cryptographic Algorithms on Reconfigurable 
 Hardware, Springer. 
 Số 2.CS (08) 2018 57