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à
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.
P ể ệ ự ệ
phép tính k*P, ó k 1 ố P là
ể E ợ
ị ĩ GF(p) [2].
T ậ ự ệ ể
:
Abstract— This paper describles an
algorithm and structure for computing and
implementation point multiplications on Elliptic
cuvers defined GF(p) with 256 bits length. The
circuits have been describled in VHDL in
implemented on chip Zynq xc7z030 and xc7z045.
Thuật toán 1:
Đầ :
k (kt1,...,k1,k0 )2,PE(Fp )
Đầ : kP
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 ự ệ
2.1
Q 2Q
Keywords—FPGA; Elliptic cuvers over
GF(p); Point multiplication.
2 2 ế ki=1 thì
Q Q P
I. GIỚI THIỆU VÀ MÔ TẢ THUẬT TOÁN
NHÂN ĐIỂM
3 T ả ề Q
Thuật toán 2:
P ả
ậ ậ
ể ố
V ệ
ứ ạ , ố ề ố
do ả ự ệ
ứ ả ậ . T ự ứ ó
ể FPGA ú ố
ả ự ệ ,
ứ ợ ầ ự ế Trong
ú ô ì ,
ự ố ậ ự ố tài
ệ ô ì ứ ế
, ể ừ ó ở ệ ứ
ế ế ứ ó ể ệ
cong elliptic, ợ ứ ụ ứ
ó : ECDH, ECHMQV, ố
ECDSA [1][7], ó ECIES [6].
Đầ :
k (kt1,...,k1,k0 )2,PE(Fp )
Đầ : kP
1.
Q
2. cho i ạ ừ 0 ế t-1 ự ệ
2 1 Nế ki=1 thì
Q Q P
2.2
P 2P
3 ả ề Q
Đố T ậ 1 [8], ò ặ ạ
2 1 2 2 ề ế ả là ị
Q Kế ả ầ ạ 2 1 ị ầ
2 2 D ậ ì ự ệ
ả ố ế ế ú 2 1 ồ
ế 2 2 T ó, ở T ậ 2,
ò ặ ạ 2 ế ả
2 1 Q 2 2 là P, ợ
ự ệ ậ ô ụ
ự ệ ó ể
ể ố ự
T ú ô ự ậ
2 ể ế ế ứ ó ể ề
ả ầ ứ FPGA
Bài báo ợ ậ ngày 4/9/2018 B ợ ậ
x ở ả ệ ứ vào ngày 28/10/2018 và ợ
ậ ă vào ngày 8/11/2018. Bài báo ợ ậ x ở
ả ệ ứ vào ngày 10/11/2018 và ợ ậ
ă ngày 21/11/2018.
T ậ 1 ậ
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 ợ ể
ệ :
T ậ ô ể : ể
Nếu c1 = 0 và c2 = 0 thì z := z1 mod 2k;
Không thì z := z2 mod 2k;
Kết thúc.
thì
y
P(x1, y1)E(Fp ),P P
ợ :
2P (x3, y3)
c1
k – bit
Bộ cộng
2
2
3x1 a
2y1
x3
2x1
Z1 mod 2k
2k - p
2
c2
3x1 a
2y1
k – bit
Bộ cộng
y3
x x y
3
1
1
z2 mod 2k
T ậ ể :
0
1
P (x1, y1)E(Fp ),Q (x2 , y2 )E(Fp ),
P Q
z
Hì 1 C ú ố GF( )
Thì
ợ :
B. Thiết kế cứng hóa phép trừ số lớn trên
trường GF(p)
P Q (x3, y3)
2
y2 y
x2 x1
1
C
ố
ự
x,
y:
x3
y3
x1 x2
T ầ ị
x, y
p 1
ủ x và y trên
:
y2 y1
x2 x1
x x y
3
1
1
. Ta có
do
z x y mod p
p x y p
ó z ả ằ ị x - y
ặ x - y + p Từ x ự ậ ể
tính toán z :
Trong p ầ ế ủ , chúng tôi
ũ ẽ ì ậ ế ú ầ
ứ ủ ố ố ụ ụ
ệ ứ ó ể Mụ II
Mụ III Cụ ể ợ ì ở ụ
Mụ IV Kế ả ự ệ ố ù
Mụ Kế ậ
T ậ ừ GF( )
Tổng := x + (2k-y);
z1 := Tổng mod 2k;
z2 := z1 + p mod 2k;
c1 := Tổng/2k;
II. THIẾT KẾ CỨNG HÓA CÁC PHÉP TÍNH
SỐ LỚN CƠ SỞ
Nếu c1 = 0 thì z := z1;
Không thì z := z2;
Kết thúc.
A. Thiết kế cứng hóa phép cộng số lớn trên
trường GF(p)
C
ố
ự
x,y:
T ầ
x, y
p 1
x
ị ủ x và y trên
:
2k – y
c1
. Ta có 0 x y 2p do
ó z ả ằ ị x+
ặ x+ – Từ x ự ậ ể
z :
k – bit
Bộ cộng
z x y mod p
z1
p
k – bit
Bộ cộng
z2
T ậ GF( ):
z1 := x + y;
0
1
z
z2 := (z1 mod 2k) + (2k-p);
c1 := z1/2k;
c2 := z2/2k;
Hì 2 C ú ừ ố trên GF(p)
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)
P GF( ) ợ ị
ĩ :
z x.ymod p
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( ) ầ ự ệ ,
ứ ố a và b,
ứ ế ả
p.
if x(k-i-1)=1 thì r := r + y mod p;
kết thúc nếu;
kết thúc lặp;
kết quả := r;
Có ề ậ ử ụ ể
ự GF( ), ố
ó ó ậ ợ ầ ứ , ầ
ề ặ ầ ụ C ậ ử ụ
ầ ứ ầ ế ế ì
ử ụ ầ ử ả ầ
ứ AND, OR, , MU
ứ ầ ử ả FPGA
CLB LUT V ế
ó ề ô ố ả
ể ự ệ ậ
GF( ), ó ể ó ạ ố
:
y
0
1
Step_type
ce_r
p
x
y
p
Bộ cộng modulo p
z
update
load
Shift
Thanh ghi dịch
256 - bit
Mạch tổ
hợp
ce
Thanh ghi 256-bit
clear
x(i)
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
Montgomery). H ệ ạ , chúng tôi ự ệ
ứ ó
x , ễ ự ệ ề
ả ầ ứ ử ụ
và phép nhân 2. T ắ ú
ô ẽ ứ ề ò ạ
P x ẽ ợ làm rõ
trong ậ x ẫ tài
ệ [4], [5]. T ậ x ợ trình
bày :
trường GF(p)
P ị ả ợ
ủ a/b a = 1 T x
ợ , ố ự a, b:
T ầ
a,b
, p 1
ị ủ a và b trên
:
. (1)
z a / bmod p
Để ể ứ (1) ó ề ậ
toán khác nhau (thuật toán Euclidean thuật toán
nhị phân, thuật toán cộng-trừ và thuật toán tính
nghịch đảo theo định lý Fermat’s Little) trong
ầ ú ô ự ậ ị
ể ế ế ị ả
GF(p).
C
ố
ự
x,
y:
T ầ
x, y ..., p 1
ị ủ x và y trên
:
.
Ta
có
z x.ymod p
C
a,b
p 1
ố
ự
a,
b:
x.y x .2k1 xk2.2k2 ... x .20 y
k1
0
(...(0.2 xk1y)2 xk2 y)2 ... x1y)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
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)
ó a – b ố
y2 y1
x2 x1
y3 (x x3) y1
1
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;
Hì 5 C ú ể
Kết thúc lặp;
GF(p)
Z := c;
B. Thiết kế cứng hóa phép nhân đôi điểm
b
a
a
d
p
d
c
c
d
c
d
a
b
b
Elliptic trên trường GF(p)
Bộ cộng theo điều
kiện
Bộ trừ
Bộ trừ
Bộ trừ
Bộ trừ
b0
P ô ợ ị ĩ
ở ầ ó ể
x ị :
d+b0p
/2
ợ
R 2P
0
1
0
1
0
1
0
1
x3 2 2x1
d2-1 mod p
d-c/c-d
;
c
0
p
a
y
b/2
1
3x2 a
a/b
b-a/a-b
x
1
1
y3 (x x3) y
1
0
1
2
0
1
2
0
1
2
0
2
2y1
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 ú ô ể
GF( )
x3 2 x1 x2
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 ề ả ầ ứ
khác nhau
K+ carry_reg
(K+ carry)/2
Bả 1. Kế ả ặ ậ
ể ề ả ầ ứ FPGA
Cộng Điểm
Initial: K
Tầ ố
ạ
Tài
nguyên
ế ế
T ậ
toán
nhân
ể
C ề
dài
ỗ
bit
Chip
FPGA
Tạo cờ trạng thái
(M
Hz)
(L
UTs)
Nhân Đôi
Thanh ghi XQ, YQ
Xc7z030
Xc7z045
136.1
157.3
34472
34486
Initial: Xp, Yp
T ậ
toán 1
256
Hì 7 C ú ể
GF( )
V. KẾT LUẬN
G ệ ự ệ ể
GF( ) ự ô ệ
FPGA:
T ó ả ì
ệ , , ự ậ
ể ố ậ ự ệ
ở ệ ậ
Để ừ ó ở ệ ế ế ứ ó
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Ả
KS. Nguyễn Văn Long
[1]. American Bankers Association. ANSI X9.62-
1998: Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve
Digital Signature Algorithm (ECDSA).
Đ ị ô : V ệ K –
Cô ệ ậ , B C ế
ủ
[2]. N. Koblitz, S. Vastone, and A. Menezes. The
State of Elliptic Curve Cryptography, Design,
Codes and Cryptography, 19(2/3):173-193,
March 2000.
Email: longyenkk2@gmail.com
Q ì ạ : N ậ ằ ỹ
ă 2014
H ứ ệ : Cô ệ ạ ,
FPGA, ô ệ ú L x
[3]. J. Lutz. High Performance Elliptic Curve
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
thuật toán GOST (28147-89, R34.11-2012,
R34.10-2012) dựa trên công nghệ FPGA” B
C ếu Chính phủ, Thực hiện 2015- 2016. Chủ
nhiệm Nguyễ B C
Đ ị ô tác: V ệ K -
Cô ệ ậ , B C ế
C ủ.
Email: thuchv@yahoo.com
Q ì ạ : N ậ ằ ỹ
ă 1998 T ạ ĩ ă 2004
Kỹ ậ ậ ,
[5]. SEC1. Elliptic Curve Cryptography: Standards
for
Eficient
Cryptography
Group,
H ệ Kỹ ậ ậ N ậ ằ T ế ĩ T
, V ệ K - Cô ệ q ự ă 2012
[6]. TC03-2:2015, “Thuật toán chữ ký số ECDSA”,
B ếu Chính phủ.
H ứ ệ : K - Cô ệ
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
6 trang
09/04/2022
5480
Bạn đang xem tài liệu "Một giải pháp cứng hóa phép nhân điểm Elliptic trên trường GF(p)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- mot_giai_phap_cung_hoa_phep_nhan_diem_elliptic_tren_truong_g.pdf
