Journal of Science and Technology on Information Security

M

g ả pháp cứ
E

Tóm tắt— Bài báo này mơ tả thuật tốn và
cấu trúc mạch cho việc tính tố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.
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.
Từ khóa— FPGA; Đường cong elliptic trên
trường GF(p); nhân điểm.
Keywords—FPGA; Elliptic cuvers over
GF(p); Point multiplication.

I. GIỚI THIỆU VÀ MƠ TẢ THUẬT TỐN
NHÂN ĐIỂM
P
ả
ậ
ậ

ể
ố
Vệ
ứ ạ ,
ố
ề
ố
do
ả ự
ệ
ứ
ả
ậ
. T ự
ứ
ó
ể
FPGA ú
ố
ả
ự
ệ
,
ứ
ợ
ầ
ự ế Trong
ú
ơ ì
,

ự
ố
ậ
ự
ố tài
ệ
ơ
ì
ứ
ế
, ể ừ ó
ở
ệ
ứ
ế ế ứ
ó
ể
ệ
cong elliptic,
ợ ứ
ụ
ứ
ó : ECDH, ECHMQV,
ố
ECDSA [1][7],
ó ECIES [6].

x

Bài báo ợ

ậ ngày 4/9/2018 B
ợ
ở
ả
ệ
ứ
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.

52 Số 2.CS (08) 2018

ậ
ở
ậ

ó

ể
GF(p)

Nguyễn Văn Long, Hồng Văn Thức
P
ể

ệ
ự
ệ
phép tính k*P,
ók 1 ố
P là
ể
E
ợ
ị
ĩ
GF(p) [2].

T

ậ
ự
ệ
ể
:
Thuật tốn 1:
Đầ
: k  (k ,..., k , k ) , P  E ( F )
t 1
1 0 2
p
Đầ
: kP
1. Q  
2. cho i ạ ừ t-1 ế 0

2.1 Q  2Q

ự

ệ

2 2 ế ki=1 thì Q  Q  P
3 T ả ềQ
Thuật toán 2:
Đầ
: k  (k ,..., k , k ) , P  E ( F )
t 1
1 0 2
p
Đầ
: kP
1. Q  
2. cho i ạ ừ 0 ế t-1 ự
2 1 Nế ki=1 thì Q  Q  P

ệ

2.2 P  2 P
3 ả ềQ
Đố
T ậ
1 [8],
ò
ặ
21 22 ề

ế
ả là
Q Kế
ả ầ
ạ
21
ị
22 D ậ
ì
ự
ả
ố ế ế ú
21 ồ
ế
22 T
ó, ở T ậ
ị
ặ ạ
2 ế
ả
21
Q
2 2 là P,
ự
ệ
ậ
ơ
ụ
ự
ệ

ó ể
ể
ố
ự
T
ú
ơ ự
ậ
2 ể ế ế ứ
ó
ể
ả
ầ ứ FPGA
T
ậ
1
2
ò
ặ ử ụ

ạ
ị
ầ
ệ
2,
ợ

ề
ậ
ể



Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An tồn thơng tin

ơ
ệ

ể . Hai phép tính

ợ

ể

:
T

ậ

ơ

ể :

ể
thì

P( x1 , y1 )  E ( Fp ), P   P
:
2 P  ( x3 , y3 ) ợ

Nếu c1 = 0 và c2 = 0 thì z := z1 mod 2k;

Khơng thì z := z2 mod 2k;
Kết thúc.
x

c1

2

 3x 2  a 
x3   1
  2 x1
 2 y1 
 3x12  a 
y3  
  x1  x3   y1
 2 y1 

T

ậ

k – bit
Bộ cộng
Z1 mod 2k

k – bit
Bộ cộng
z2 mod 2k

0


P  ( x1 , y1 )  E ( Fp ), Q  ( x2 , y2 )  E ( Fp ),
Hì

ợ

:

2

y y 
y3   2 1   x1  x3   y1
 x2  x1 

ủ

II. THIẾT KẾ CỨNG HĨA CÁC PHÉP TÍNH
SỐ LỚN CƠ SỞ
A. Thiết kế cứng hóa phép cộng số lớn trên
trường GF(p)
C
ố
ự
x,y:
x, y  p 0,1,..., p 1 T ầ

x

GF( )


x

và

y

trên

:

p

x-y
ể

y

x

:

p

ự

ố

óz ả ằ
ị
ặ x - y + p Từ

x
ự
ậ
tính tốn z
:
T ậ
ừ
GF( )
k
Tổng := x + (2 -y);
z1 := Tổng mod 2k;
z2 := z1 + p mod 2k;
c1 := Tổng/2k;
Nếu c1 = 0 thì z := z1;
Khơng thì z := z2;
Kết thúc.

2k – y

z   x  y  mod p . Ta có 0  x  y  2 p do
ó z ả ằ
ặ x+ – Từ
z
:

ú

z   x  y  mod p . Ta có  p  x  y  p do

Trong p ầ ế

ủ
, chúng tơi
ũ
ẽ ì
ậ
ế ú
ầ
ứ
ủ
ố
ố
ụ ụ
ệ ứ
ó
ể
Mụ II
Mụ III Cụ ể ợ ì
ở
ụ
Mụ IV Kế
ả ự
ệ
ố ù
Mụ Kế ậ

x và y trên

1 C

B. Thiết kế cứng hóa phép trừ số lớn trên

trường GF(p)
C
ố
ự
x,
y:
ị
x, y  p 0,1,..., p 1 T ầ

y y 
x3   2 1   x1  x2
 x2  x1 

ủ

1

z

P  Q

ị

2k - p

c2

ể :

Thì P  Q  ( x , y )

3
3

y

ị
ậ

c1

k – bit
Bộ cộng

x+

z1
p

ể
k – bit
Bộ cộng
z2

T ậ
z1 := x + y;
z2 := (z1 mod 2k) + (2k-p);
c1 := z1/2k;
c2 := z2/2k;

GF( ):


0

1

z

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
trường GF(p)
P
GF( )
ợ
ị

ĩ
:

ả

T ậ
GF( ):
r := 0;
với i in 0 to k-1 lặp:
r := (r +r) mod 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  a.b mod p,  a, b  p
Để

ự

ệ ứ
GF( ) ầ

ó
ự

ứ
ệ

,

ố a và b,
ả

ứ
ứ
p.

ế

Có
ề
ự
ó ó
ậ
ề
ặ
ầ
ầ ứ
ử ụ
ứ
AND,
ứ
CLB
LUT
ó
ề
ể ự
GF( ),

ậ


ử ụ
ể
GF( ),
ố
ợ
ầ ứ , ầ
ụ
C
ậ
ử ụ
ầ
ế ế
ì
ầ ử
ả
ầ
OR,
, MU
ầ ử
ả
FPGA
V
ế
ơ
ố
ả
ệ
ậ
ó ể ó

ạ
ố
:
ồ
(multiply and

- P
then divide)
- P
x (Interleaving)
- 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
:
C
ố
ự
x,
y:
T
ầ
x, y  p  0,1,..., p 1
ị

ủ

x và y trên

z  x. y mod p .

:


p

Ta

có

x. y   xk 1.2k 1  xk 2 .2k 2  ...  x0 .20  y

 (...(0.2  xk 1 y )2  xk 2 y )2  ...  x1 y )2  x0 y
,
ể ử ụ
ự
ệ

ằ

ơ
ú

54 Số 2.CS (08) 2018

(

)

ẽ

ợ

ó

ó
ế

GF( ),

z  x. y mod p

y

0

1

Step_type

p
ce_r
x

y

p

Bộ cộng modulo p
z
Shift
Thanh ghi dịch
256 - bit

Mạch tổ

hợp

ce
Thanh ghi 256-bit
clear

x(i)

load

update

load

load

r

z

Hì

3 C

ú

ố

GF(p)


D. Thiết kế cứng hóa phép chia/nghịch đảo trên
trường GF(p)
P
ị
ả
ợ
ủ
a/b
a=1 T x
ợ
,
ố ự
a, b:
a, b  p 0,1,..., p  1 T ầ
ị

ủ

a và b trên

p

:

z  a / b mod p . (1)
Để
ể
ứ (1) ó
ề
ậ

tố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 tốn tính
nghịch đảo theo định lý Fermat’s Little) trong
ầ
ú
ơ ự
ậ
ị
ể
ế ế
ị
ả
GF(p).
C
ố
ự
a,
b:
a, b  p 0,1,..., p 1
- Nế ả
ố ề
,
ó
ó:
GCD(a,b) = 2.GCD(a/2, b/2)
- Nế
ó
ố
, ả ử
ì

GCD(a, b) = GCD(a, b/2).
- Nế
ơ
ó ố
ả ửa≥b


Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An tồn thơng tin

ì
ó GCD(a,b) = GCD(a, a -b)
óa–b
ố
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;
Z := c;
a

b

b

a

a

Bộ trừ

0


Bộ trừ

0

1

b

1

d

p

d

Bộ cộng theo điều
kiện

c

Bộ trừ

b0

d+b0p
/2

0


-1

d2 mod p
p

a

a/b

0 1 2

ce
Thanh ghi
k – bit

a

y b/2

c

d

d

0

1

Bộ trừ


1
d-c/c-d

b-a/a-b

c

0

c

0 1 2

0 1 2

ce
Thanh ghi
k – bit

ce
Thanh ghi
k – bit

ce
Thanh ghi
k – bit

b


d

z.c

Hì

5 C

ú



y2  y1
x2  x1

ể
GF(p)

B. Thiết kế cứng hóa phép nhân đơi điểm
Elliptic trên trường GF(p)
P
ơ
ợ ị
ĩ
ở ầ
ó
ể R  2P
ợ
2
x

ị
:
x3    2 x1 ;

y3   ( x1  x3 )  y1

x

0 1 2

y3   ( x1  x3 )  y1

3x 21  a

2 y1

ce

Hình 4. C u trúc phép chia/nghị
ảo theo thuật
tố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
ị
:

x3   2  x1  x2

Hì

6 C

ú

ơ

ể

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

trên trường GF(p)
Vệ ứ
ó
ể
GF( )
ì
ố
ế ế ứ
ó ở
ụ
,
ú
ự
ệ
ể
GF( )
:
K+ carry_reg
YP0

p-YP0

IV. KẾT QUẢ THỰC HIỆN
M
ể
GF( )
ợ
ú
ơ
ợ

02 ề
chip xc7z030
x 7z045
ợ ứ
ụ
ề
“N
ứ
ế
ế, ế ạ
ả
ậ
ầ ứ HSM,
ứ
ụ
ệ ố
ả
ậ
x
ự
ô
” D
ế
ả
ợ
ể
02 ề ả
ầ ứ
khác nhau


(K+ carry)/2
0

1

Next_k

XQ

YQ

YP0_tp

XP0

Cộng Điểm

0

1

0

1

0

1

New_XQ

XP

XP0

YP

p-YP

New_YQ

YP0

T ậ
toán
nhân
ể

Tạo cờ trạng thái

ặ
ứ

YP0

XP0

0

1


1

0

NEXT_X
Q

NEXT_Y
Q

New_YP
0

New_XP
0

Xc7z030
T ậ
tốn 1

Q_infinity

XQ

YQ

7 C

Chip
FPGA


ú

Xc7z045

Tầ

ố
ạ

Tài
ngun
ế ế

(M
Hz)

(L
UTs)

136.1

34472

256

157.3

34486


ể
GF( )

ệ

C ề
dài
ỗ
bit

ậ
FPGA

Nhân Đơi

Initial: Xp, Yp

G

ả
ầ

Initial: K

Thanh ghi XQ, YQ

Hì

1. Kế
ề ả


Bả
ể

ự ệ
GF( ) ự

V. KẾT LUẬN
ể
ơ

ệ

FPGA:

T

ó
ệ ,
ể

ố
ệ

ả ì
ậ
ệ

, ự
ậ

ự
ậ
ệ
ế ế ứ
ụ II và phép

ở
Để ừ ó
ở
ó
phép tính
ở
ể
ụ 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 tồn thơng tin

[1].

[2].

[3].

[4].

[5].

[6].
[7].

[8].

TÀI LIỆU THAM KHẢO
American Bankers Association. ANSI X9.621998: Public Key Cryptography for the
Financial Services Industry: The Elliptic Curve
Digital Signature Algorithm (ECDSA).
N. Koblitz, S. Vastone, and A. Menezes. The
State of Elliptic Curve Cryptography, Design,
Codes and Cryptography, 19(2/3):173-193,
March 2000.
J. Lutz. High Performance Elliptic Curve
Cryptographic coM
’
,
University of Waterloo, 2003.

Đề tài c B “N
ứu thiết kế, chế tạo
module bảo mậ
ặt an tồn, cứng hóa các
thuật tố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
SEC1. Elliptic Curve Cryptography: Standards
for
Eficient
Cryptography
Group,

TC03-2:2015, “Thuật tốn chữ ký số ECDSA”,
B
ếu Chính phủ.
The FIPS 186-3 Elliptic Curve Digital Signature
Algorithm Validation System (ECDSA2VS),
January 17, 2012.
Cryptographic Algorithms on Reconfigurable
Hardware, Springer.

SƠ LƯỢC VỀ TÁC GIẢ

H
FPGA, ô

H
H

Mậ

ệ Kỹ
,Vệ K

KS. Nguyễn Văn Long
Đ
ị ơ
:Vệ K
–
Cơ
ệ ậ
, B C ế
ủ
Email:
Q
ì
ạ : N ậ ằ
ỹ
ă 2014
ứ
ệ
: Cơ
ệ
ạ ,
ệ ú L x
TS. Hồng Văn Thức
Đ
ị ô tác: V ệ K
Cô

ệ ậ
, B C
ế
C
ủ.
Email:
Q
ì
ạ :N ậ ằ
ỹ
ă 1998
T ạ ĩ ă 2004
Kỹ
ậ
ậ
,
ậ ậ
N ậ ằ Tế ĩ T
- Cô
ệq
ự ă 2012
ứ
ệ
: K
- Cô
ệ

Số 2.CS (08) 2018

57