intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST
Báo xấu
40
lượt xem 7
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết này mô tả thuật toán và cấu trúc mạch cho việc tính toán và thực thi phép tính nhân điểm đường cong Elliptic trên trường nguyên tố hữu hạn GF(p) có độ dài 256 bit. Cấu 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à xc7z045.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. 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  (k ,..., k , k ) , P  E ( F ) t 1 1 0 2 p 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 trường GF(p); nhân điểm. 2. cho i ạ ừ t-1 ế 0 ự ệ Keywords—FPGA; Elliptic cuvers over 2.1 Q  2Q GF(p); Point multiplication. 2 2 ế ki=1 thì Q  Q  P 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 ả Đầ : k  (k ,..., k , k ) , P  E ( F ) ậ ậ t 1 1 0 2 p ể ố Đầ : kP Vệ 1. Q   ứ ạ , ố ề ố do ả ự ệ 2. cho i ạ ừ 0 ế t-1 ự ệ ứ ả ậ . T ự ứ ó 2 1 Nế ki=1 thì Q  Q  P ể FPGA ú ố ả ự ệ , 2.2 P  2 P ứ ợ ầ ự ế Trong 3 ả ềQ ú ô ì , Đố T ậ 1 [8], ò ặ ạ ự ố ậ ự ố tài 21 22 ề ế ả là ị ệ ô ì ứ ế Q Kế ả ầ ạ 21 ị ầ , ể ừ ó ở ệ ứ 22 D ậ ì ự ệ ế ế ứ ó ể ệ ả ố ế ế ú 21 ồ cong elliptic, ợ ứ ụ ứ ế 22 T ó, ở T ậ 2, ó : ECDH, ECHMQV, ố ò ặ ạ 2 ế ả ECDSA [1][7], ó ECIES [6]. 21 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
  2. 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. P( x1 , y1 )  E ( Fp ), P   P thì x y 2 P  ( x3 , y3 ) ợ : c1 2 k – bit  3x 2  a  Bộ cộng x3   1   2 x1 Z1 mod 2k  2 y1  2k - p  3x12  a    x1  x3   y1 c2 y3   k – bit Bộ cộng  2 y1  z2 mod 2k T ậ ể : 0 1 P  ( x1 , y1 )  E ( Fp ), Q  ( x2 , y2 )  E ( Fp ), z P  Q Hì 1 C ú ố GF( ) Thì P  Q  ( x , y ) ợ : B. Thiết kế cứng hóa phép trừ số lớn trên 3 3 2 trường GF(p) y y  C ố ự x3   2 1   x1  x2 x, y:  x2  x1  x, y  p 0,1,..., p 1 T ầ ị y y  ủ x và y trên : y3   2 1   x1  x3   y1 p  x2  x1  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 + (2 -y); k Mụ IV Kế ả ự ệ ố ù Mụ Kế ậ z1 := Tổng mod 2k; 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. x, y  p 0,1,..., p 1 T ầ y x ị ủ x và y trên p : 2k – y z   x  y  mod p . Ta có 0  x  y  2 p do c1 k – bit Bộ cộng ó z ả ằ ị x+ z1 p ặ x+ – Từ x ự ậ ể z : k – bit Bộ cộng z2 T ậ GF( ): 0 1 z1 := x + y; z z2 := (z1 mod 2k) + (2k-p); c1 := z1/2k; Hì 2 C ú ừ ố trên GF(p) c2 := z2/2k; Số 2.CS (08) 2018 53
  3. 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 Step_type ề ặ ầ ụ C ậ ử ụ ầ ứ ầ ế ế ì p ử ụ ầ ử ả ầ ce_r ứ AND, OR, , MU x y p ứ ầ ử ả FPGA Bộ cộng modulo p CLB LUT V ế z ó ề ô ố ả Mạch tổ Shift Thanh ghi dịch update ể ự ệ ậ ce Thanh ghi 256-bit hợp 256 - bit load x(i) 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: ả ầ ứ ử ụ và phép nhân 2. T ắ ú a, b  p 0,1,..., p  1 T ầ ô ẽ ứ ề ò ạ ị ủ a và b trên p : P x ẽ ợ làm rõ trong ậ x ẫ tài z  a / b mod p . (1) ệ [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  p  0,1,..., p 1 T ầ nghịch đảo theo định lý Fermat’s Little) trong ầ ú ô ự ậ ị ị ủ x và y trên p : ể ế ế ị ả z  x. y mod p . Ta có GF(p). x. y   xk 1.2k 1  xk 2 .2k 2  ...  x0 .20  y C ố ự a, b: a, b  p 0,1,..., p 1  (...(0.2  xk 1 y )2  xk 2 y )2  ...  x1 y )2  x0 y - 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
  4. 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) y2  y1 óa–b ố y3   ( x1  x3 )  y1  x2  x1 Lặ ạ ì ố ạ m ẽ ì ợ ốx ị GCD(a ,b) = GCD( a p , 0) Từ ó ểx ự ậ a z  mod p : 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ừ kiện b0 Bộ trừ Bộ trừ P ô ợ ị ĩ d+b0p /2 ở ầ ó ể R  2P ợ x3    2 x1 ; 0 1 0 1 0 1 0 1 -1 x ị : 2 d2 mod p d-c/c-d 0 c p a a/b y b/2 b-a/a-b 3x 21  a y3   ( x1  x3 )  y1 x  0 1 2 0 1 2 0 1 2 0 1 2 2 y1 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 ể ợ ị ĩ ở ầ ó ể R  PQ ợ x ị : Hì 6 C ú ô ể x3   2  x1  x2 GF( ) Số 2.CS (08) 2018 55
  5. 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 ế ả ợ K+ carry_reg ể 02 ề ả ầ ứ khác nhau p-YP0 YP0 1. Kế ả ặ ậ (K+ carry)/2 Bả 1 0 ể ề ả ầ ứ FPGA Next_k XP0 YQ XQ YP0_tp Cộng Điểm Initial: K Tầ ố Tài T ậ C ề ạ nguyên New_YQ YP0 p-YP ế ế YP toán Chip dài XP0 XP New_XQ Tạo cờ trạng thái ỗ 1 0 1 0 nhân FPGA 1 0 YP0 ể bit (M (L XP0 1 0 0 1 NEXT_X Hz) UTs) NEXT_Y Q Q Nhân Đôi New_XP New_YP Thanh ghi XQ, YQ Xc7z030 136.1 34472 0 0 Initial: Xp, Yp T ậ Q_infinity YQ XQ 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
  6. 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 Đ ị ô tác: V ệ K - module bảo mậ ặt an toàn, cứng hóa các 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 ậ ằ ỹ [5]. SEC1. Elliptic Curve Cryptography: Standards ă 1998 T ạ ĩ ă 2004 Kỹ ậ ậ , for Eficient Cryptography Group, H ệ Kỹ ậ ậ N ậ ằ Tế ĩ T http://www.secg.org ,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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2