1

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
DƯƠNG THỊ MAI THƯƠNG
NGHIÊN CỨU CHỮ KÝ SỐ BỘI VÀ ỨNG DỤNG
TRONG THƯƠNG MẠI ĐIỆN TỬ

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

THÁI NGUYÊN, 2013
2

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
DƯƠNG THỊ MAI THƯƠNG

6
1. Chương 1: CƠ SỞ LÝ THUYẾT 7
1.1 CƠ SỞ TOÁN HỌC 10
1.1.1 ng 10
1.1.1.1  10
1.1.1.2  10
1.1.1.3 ng 10
1.1.2 ng cong Elliptic 13
1.1.2.1 ng cong elliptic 13
1.1.2.2 ng cong Elliptic 14
1.1.2.3 i rng cong elliptic (ECDLP): 16
1.2 HỆ MẬT TRÊN ĐƯỜNG CONG ELLIPTIC 17
1.2.1  ng cong Elliptic 17
1.2.1.1  17
1.2.1.2 Mt n (Mask) 18
1.2.2  ng cong elliptic (ECC) 18
1.2.2.1 H  18
1.2.2.2 H -Vanstone 18
1.2.3 -Hellman s dng cong
elliptic (ECDH) 19
1.2.3.1 -Hellman. 19
1.2.3.2 - Hellman 19
1.2.4 La chnp 19
1.2.5  22
1.2.5.1 Tng quan v  22
1.2.5.2 Thu-1 23
2. Chương 2 : CHỮ KÝ SỐ BỘI TRÊN ĐƯỜNG CONG ELLIPTIC 27
2.1 GIỚI THIỆU VỀ CHỮ KÝ SỐ 27
2.1.1 m v ch  27
2.1.2 Hong ca ch  27

4.2 CÁC THÀNH PHẦN CỦA CHƯƠNG TRÌNH 56
4.2.1 liptic 56
4.2.2 T 56
4.2.3  56
4.2.4 X 57
4.3 CHƯƠNG TRÌNH 58
4.3.1  58
4.3.2  59
4.4 HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH 60
4.4.1  61
4.4.2  63

6

DANH MỤC BẢNG BIỂU

21
-
26

32
Ba thu
33

33

33




60

66

67
 

 
74






H





 1.
2. MỞ ĐẦU
8

 n vinh ca mt nn kinh t  da
 m lc quyt

ng s ch  c n ch 
mt thc tp v thng nhu t x 
cao. Ch     o ra ch         
thu m b tin c
 ch i dng cong Elliptic,
 t hi ci r
ng cong elliptic vt chi  i din cho mt
9

i hay t chc. Ch t ch i duy nhc to ra bi tt c 
a
t o ra ch i n s ng
   thu 
Ch c nh a c 
gii vi ch  ra rng trong
 ca Chen s i

T              
 ch i cho m
nhau vnh th t t  c phc l hng bo
mt so v   c     m b c th t  nh
c.
 nhc s  bo ca PGS.TS
Trnh Nht Tin i la ch “Nghiên cứu chữ ký số bội và ứng dụng trong
thương mại điện tử” t nghip c Lu m mt s ni

Chương 1: Cơ sở lý thuyết - t  c ca h mc
bi  mng cong Elliptic.
Chương 2: Chữ ký số bội trên đường cong Elliptic  ni
thiu tng quan v ch  b xu ch  b

Nu <G,. > u h phn t ca <G,. > c gc c
|G|.
Bc ca phn t a

G   nht n tha
n
= 1.  
trong  a
n
c hia.a a (n lng la+a+ +a (n
ln). Trong  vi mi phn t thuc  th n ti.
Nu a

G c m H = {a
k
| k

Z } a G c m. Nu G
t phn t a c n = |G| G = {a
k
| k

Z} G c gcylic,
a c gn t sinh ca G.
, tp hp Z
n
= {0, 1, 2,…, n - 1} cylic bc n v cng
modulo n.
1.1.1.2 Vành
p R v cu kin sau:

tho b.b-1=1.
 Các phép toán và khái niệm liên quan.
Bc ca mng hu hn:
L phn t cng. Nu tn tng hu hn F c q n nu
q  , tc q=p
m
vi p   c ga
F, m  
o Nc g.
o N    c g  ng m rng. Vi b    
  n ch  c q. Mt
t c c q
mm gic s d
 ng hu hng bc

2./ Trường nguyên tố (Finite fields):
Cho p   modul p, bao gm t {0,1,2, ,p-
1} v      c biu din theo modul p   ng
12

 bc pFp i p modul ca Fp. Vi bt
k s a 
a mod p =r (r  0<=r<=p-1)
 c g
Ví dụt F
29
={0,1,2,…,28}
 ng: 17+20=8 vì 37 mod 29=8
 : 17-20=26 vì -3 mod 29=26
 17.20=21 vì 340 mod 29=21

Mc nh c bt k c thu nh bc thu nh (reduction
polynomial f(z)) (gic biu din theo
modul f(z)- c g
Ví dụng nh GF2
4
n t ca GF2
4
c nh ph
bc ln nht bng 3:
0z z
2
z
3
z
3
+z
2

1z z
2
+1z z
3
+1z z
3
+z
2
+1
zz z
2
+zz z

 : (z
3
+z
2
+1)-(z
2
+z+1)=z
3
- -a=a vi
mi a thuc F
2
m
.)
 
3
+z
2
+1)(z
2
+z+1)=z
2
+1
 Ngho (z
3
+z
2
+1)-1=z
2

3

z
2
+a
1
z+a
0
:a
i

∈
Fp}.
n t c v s c biu
ding Fp. Php  phn t cc biu di
thc modul f(z).
Ví dụng m rng)
Cho p=251 và m=5     ti gin ca F251[z 
f(z)=z
5
+z
4
+12z
3
+9z
2
+7n ca F
251
5
ng hu
hn bc F
251

 a.b = 117z
4
+ 151z
3
+ 117z
2
+ 182z + 217.
 Ngho: a-1 = 109z
4
+ 111z
3
+ 250z
2
+ 98z + 85.
1.1.2 Lý thuyết đường cong Elliptic
t, h thng dc s d
gii quyt. V  y chc s n thi t
li git ln. Trong thc t hin nay s dng ph bin h 
gii quyt v     logarit ri r      a s ca s

c
l xut ng d
ng hu hn.
ng cong elliptic -   i s  c -   u r 
   lc mt s kt qu  .
n l k i dc:
y
2
- x
3

x + a
6
với a
i

∈
F
(1.1)
        hiu E(F). S   m
trng  i vi t   c
   c bi           t
p hm tho i (x, y)
∈
F m
u O -  gn t 
Trong m xt cng hu h
F
p
v  F
q
m
vn t q = p
r
.
 Đường cong Elliptic trên trường nguyên tố hữu hạn F
p

ng F
p
, p > 3) vi bi

 Đường cong Elliptic trên trường nhị phân hữu hạn GF(2m)
ng GF(2
m
c s  thc hii bi
1
3
2
1
a
a
xax 
,
3
1
2
34
2
1
3
1
a
aaa
yay



 Định nghĩa:
ng hu hn GF
2
m

= (x, -y). Nu Q = -P P+ Q = Ong F
2
m
-P = (x, x+y).
 P + Q: Nu P

Q, gng thng l =
QP
giao vi E ti mm -RP
+ Q bng P + Q bng R. Vi P, Q, R    c
thc sau:

Hình vẽ 1.1 Phép cộng 2 điểm P + Q = R
o Trong F
p
:
21
2
12
12
3
xx
xx
yy
x 






m
:
axx
xx
yy
xx
yy
x 














21
21
21
2
21
21
3


o Trong F
p
:
1
2
1
2
1
3
2
2
3
x
y
ax
x 











 
131
1

xx 

33
1
1
1
2
13
xx
x
y
xxy 









.
 kP: kP ∈ E(Z
p
) v ng P v
l    ng thu
1.1.2.3 Bài toán Logarith rời rạc trên đường cong elliptic (ECDLP):
∈ c n. Cho Q ∈ E,
 -2) tho c Q=mP.
Hin nau qu  gi

 Tính chất đồng cấu của đường cong elliptic
ng F
q
, E(F
q
vy, E(F
q
ng
cu vi ng cu vi
1
n
Z
x
2
n
Z

2
chia ht cho n
1
- 1 v n
1

2

duy nht. Z
n
u cc n. Nu n
2


+ x + 4.
The
23
t s  
23
t
k n t sinh ca E(F
23
 t phn t
sinh ca E(F
23
).
1.2 HỆ MẬT TRÊN ĐƯỜNG CONG ELLIPTIC
c nn tng cng cong c
u qu c , bo mt. t qu  cc
s d d lich n t.
1.2.1 Cách nhúng bản rõ lên đường cong Elliptic
t bng u din li bn  m
hoc to  c  thc hi
 t s   thc hin vi  
imbeding) t n (mask).
1.2.1.1 Nhúng (Imbeding)
 Cách 1:
-  m E(Z
p
) vi p  , chng hn p

3 (mod 4).
Gi s E(Z
p

 0 ≤ x
w
≤ N
l
t:
12
2
1
1
0110
) (




ll
ll
wl
aNaNaNaxaaaw 
,
t
w
Nx 0

- c 2: Chn m k p sao cho kN
l
< q. Vi mi j n t ca
F
q
kx

1
m
2
v x, y c E. Gi s m G

E 
t (x
G
, y
G
) P
m
= (m
1
x
G
, m
2
y
G
).
1.2.2 Các hệ mã trênđường cong elliptic (ECC)
H   c th 
m ng s ng cong elliptic.
Ph thu h 
1.2.2.1 Hệ mã hóa “tựa” Elgamal
H c vu hu biu di-
ng cong.
ng s 
G ∈ E. M chn mt s 

u din b
  Zp (p>3) sao cho E cha mt
Zp, E(Zp) m G
∈
E 
n mt s ng

Gi s Alice cn gp M=(x
1
, x
2
)
∈
Zp
*
/Zp
*
cho Bob.
Gi s t ca Bob. Alice chn s ngk
∈
Z
|H|
i:
(y
0
,y
1
,y
2
) = (kG,ax

= (ax
1
)a
-1
= x
1
mod p
19

y
2
b
-1
= (bx
2
)b
-1
= x
2
mod p. (dpcm).
1.2.3 Trao đổi khoá theo phương pháp Diffie-Hellman sử dụng lý thuyết đường
cong elliptic (ECDH)
1.2.3.1 Mô hình trao đổi khoá Diffie-Hellman.
 
 c ging truy bo m
thi rng s u hn.
c hin t-Hellman gi
 ng nh  p < g.
 A chn s ngmQ
A

chung.
1.2.3.2 Mô hình trao đổi khoá Elliptic Curve Diffie- Hellman
 -
dogarit ri r
 thit lp mt hay nhic chung gi
c thc hi
 ng nh s s d P(x,y).
 A chn m m ngi QA cho B
 B chn m n ngi QB cho A
 A nh n P
 B nh n P
  c chung.
Gi s i C tng truy Q
A
,
Q
B
c m hoc n  t G=m n P
logarit ri ri s dng
thu
1.2.4 Lựa chọn đường cong Elliptic phù hợp
 
q
n la ch 
ca h m thu a 
20

ng thut nh giu qu ng cho
ECDLP.
 vic chn mn tu

nghi
4./ Nu kii 1./
5./ ng cong y
2
= x
3
ng cong cn chn.
 tm bo mt s
c. Mt k thut ci ting cong vt
 chn nh t  thuc
 mt s c. Mt k thut ci ting
cong v chn nh t
 thung h elliptic d
 m c vi cc nhm con Cylic ca E vi phn t  
m P, vic la cht quan trng.
 Chuẩn FIPS 182-2
n ngh ng mc bo m
 dng. Nhng i:
  Fp;
 ng nh 
2
m


 ng nh 
2
m
.
Chuẩn đường cong elliptic trên trường nguyên tố có các tham số:
- p: Bc c Fp

2
96
+1, a h = 1
S = 0x BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5
r = 0x 5B056C7E 11DD68F4 0469EE7F 3C7A7D74 F7D12111 6506D031 218291FB
b = 0x B4050A85 0C04B3AB F5413256 5044B0B7 D7BFD8BA 270B3943
2355FFB4
n = 0x FFFFFFFF FFFFFFFF FFFFFFFF FFFF16A2 E0B8F03E 13DD2945
5C5C2A3D
x = 0x B70E0CBD 6BB4BF7F 321390B9 4A03C1D3 56C21122 343280D6
115C1D21
y = 0x BD376388 B5F723FB 4C22DFE6 CD4375A0 5A074764 44D58199 85007E34
P-256: p = 2
256
2
224
+2
192
+2
96
1, a h = 1
S = 0x C49D3608 86E70493 6A6678E1 139D26B7 819F7E90
r = 0x 7EFBA166 2985BE94 03CB055C 75D4F7E0 CE8D84A9 C5114ABC
AF317768 0104FA0D
b = 0x 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6
3BCE3C3E 27D2604B
n = 0x FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84
F3B9CAC2 FC632551
x = 0x 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0
F4A13945 D898C296

00B8F875 E523868C 70C1E5BF 55BAD637
b = 0x 00000051 953EB961 8E1C9A1F 929A21A0 B68540EE A2DA725B
99B315F3 B8B48991 8EF109E1 56193951 EC7E937B 1652C0BD 3BB1BF07
3573DF88 3D2C34F1 EF451FD4 6B503F00
n = 0x 000001FF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
FFFFFFFF FFFFFFFF FFFFFFFA 51868783 BF2F966B 7FCC0148 F709A5D0
3BB5C9B8 899C47AE BB6FB71E 91386409
x = 0x 000000C6 858E06B7 0404E9CD 9E3ECB66 2395B442 9C648139 053FB521
F828AF60 6B4D3DBA A14B5E77 EFE75928 FE1DC127 A2FFA8DE 3348B3C1
856A429B F97E7E31 C2E5BD66
y = 0x 00000118 39296A78 9A3BC004 5C8A5FB4 2C7D1BD9 98F54449 579B4468
17AFBD17 273E662C 97EE7299 5EF42640 C550B901 3FAD0761 353C7086
A272C240 88BE9476 9FD16650

1.2.5 Hàm băm
1.2.5.1 Tổng quan về hàm băm
t ch yu phc v 
c. Chc hih x 
t mi c c nh. Mii t
 c nh t nhiu so vi bu.
M mic sinh ra bng: h= H (M)
n    nh.
i v
-  i d liu vi  
- u ra c nh.
23

- Vi   vi thi vi c phn
mn cng.
- t chii

Y
q
Y
1L
Y
512 bits 512 bits 512 bits 512 bits
SHA
H
SHA
H
SHA
H
SHA
H
512 512 512 512
1 6 0 1 6 01 6 0
1 6 0
160-bit
digest
ABCDE

Hình vẽ 1.3 Quá trình băm một bản tin
 u ra c 
c thc hin:
24

ROUND(ABCDE,Y
q
,K
0

.

Hình vẽ 1.4 Quá trình băm một khối
Bước 1:
m (Append padding bits): Bt chui
m (padding) sao cho chii 448 khi chia cho 512. S 
padding nm trong khong t n 512. Phn padding bao gm mt s
ng cn thit cc b
Bước 2:
t khn
   t s nguyn khng d  ch     c khi
padding.
Bước 3:
Khi to MD buffer (Innitilize MD buffer): Mt b m 160 bt d cha
t qu t qu cua h 

Bước 4:
25

X    i dng khi 512 bit (Process message in 512-bit blocks):
 hi
SHA
gp, mp gc. M
lp li  
q
Y
a trong 5 thanh ghi
p nht ni dung ca buffer. Mp s dng mt hng s ph
K
i

160
56
384
512
Message size
<2
64

<2
64

<2
128

<2
128

Block size
512
512
1024
1024
Word size
32
32
64
64
Number of steps
80
80

80
.
- Tấn công chống lại việc phân tích mã (cryphtanalysis):
Do thit k c b ti vig i vi
SHA-n thit k  b 
- Tốc độ:
C hai thuu dng modulo 2
32
ng hiu
qu -1 cn nhii 64 ca MD5), x 
b m li 128 cy SHA-1 s thc thi ch
t phn cng.
- Tính gọn nhẹ:
C hai thu t.
Trong thc t, bt k h th b ti ta
dc t cc bo
m  o mt.

Trích đoạn Mô hình tổng quát CÁC THÀNH PHẦN CỦA CHƯƠNG TRÌNH CHƯƠNG TRÌNH Chương trình lược đồ chữ ký số bội ngang hàng Chương trình lược đồ chữ ký số bội tuần tự

---