Nghiên cứu hệ mật đường cong ELLIPTIC và ứng dụng

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "Nghiên cứu hệ mật đường cong ELLIPTIC và ứng dụng": http://123doc.vn/document/1040616-nghien-cuu-he-mat-duong-cong-elliptic-va-ung-dung.htm

5


Định nghĩa 9:
Đường cong Elliptic E định nghĩa trên
p
thỏa mãn
 
#
p
Ep
được gọi là các đường
cong bất quy tắc.
1.1.2 Hệ mật dựa trên đường cong Elliptic
Tập hợp tất cả các điểm
 
,xy
với
,
p
xy
thỏa mãn phương trình của đường cong E
và với một điểm

ở vô cực cùng với một phép toán cộng sẽ tạo thành một nhóm, gọi là
nhóm các điểm trên đường cong Elliptic trong
p
, ký hiệu là
 
p
E
.
 Phép cộng điểm: Cho hai điểm
1
P
và
2
P
phân biệt trên đường cong Elliptic
E. Tổng của
1
P
và
2
P
, ký hiệu là
3
P
, được định nghĩa như sau:
Kẻ một đường thẳng đi qua
1
P
và
2
P
. Đường thẳng này sẽ cắt E tại một điểm thứ 3,
được ký hiệu là
'
3
P
. Tiếp tục kẻ đường thẳng đi qua
'
3
P
và vuông góc với trục
x
, đường
thẳng này sẽ cắt
E
tại điểm thứ hai chính là điểm
3
P
.
 Phép nhân đôi một điểm: Cho
1
P
là một điểm trên
E
. Nhân đôi điểm
1
P
, ký
hiệu là
1 1 1
2P P P
, được định nghĩa như sau: Kẻ qua
1
P
một tiếp tuyến của
E
, tiếp
tuyến này cắt
E
tại điểm thứ hai, ký hiệu là
R
. Kẻ đường thẳng đi qua
R
và vuông
góc với trục
x
, đường thẳng này cắt
E
tại điểm thứ hai chính là
1
2P
.
Cho
E
là một đường cong Elliptic xác định bởi phương trình
23
y x x B   
. Gọi
1
11
( , )P x y
và
2 2 2
( , )P x y
là các điểm trên
E
với
12
,PP
. Khi đó
1 2 3 3 3
( , )P P P x y  
với
33
,xy
được tính như sau:
(1) (Công thức cộng điểm) Nếu
12
xx
, thì
2
3 1 2
x m x x  
,
 
3 1 3 1
y m x x y  
, với
21
21
yy
m
xx



.
(2) Nếu
12
xx
nhưng
12
yy
, thì
12
PP  
.
(3) (Công thức nhân đôi điểm) Nếu
12
PP
và
1
0y 
, thì
2
3 1 2
x m x x  
,
 
3 1 3 1
y m x x y  
với
2
1
1
3
2
xA
m
y



(4) Nếu
12
PP
và
1
0y 
, thì
12
PP  
.
(5)
1 1 1
;P P P E   
.
Phép cộng điểm trên đường cong Elliptic
E
thỏa mãn các tính chất sau:
(1) Tính giao hoán:
1 2 2 1
P P P P  
với mọi
12
,PP
trên
E
.
(2) Tồn tại phần tử đơn vị:
PP  
với mọi
P
trên
E
.
(3) Tồn tại phần tử nghịch đảo: Với điểm
P
cho trước trên
E
, tồn tại một điểm
'
P
trên
E
sao cho
'
PP  
. Điểm
'
P
thường được kí hiệu là
P
.
(4) Tính kết hợp:
 
1 2 3 1 2 3 1 2 3
( ) , ,P P P P P P P P P E      
.


6


1.1.2.1 Các tự đồng cấu
Một tự đồng cấu
E
nghĩa là một đồng cấu
: ( ) ( )EE


được cho bởi các hàm hữu
tỉ. Nói cách khác,
     
1 2 1 2
P P P P
  
  
, và có các hàm hữu tỉ (thương của các đa chức)
 
1
,R x y
,
 
2
,R x y
với các hệ số trong sao cho
     
 
 
 
12
, , , , ,x y R x y R x y x y E

  

Một tự đồng cấu
 
,0xy


được gọi là tự đồng cấu tách được nếu đạo hàm
 
'
1
,R x y
không đồng nhất bằng không.
1.1.2.2 Các điểm n – xoắn
Các điểm xoắn, chính là các điểm có bậc hữu hạn, đóng một vai trò quan trọng trong
nghiên cứu các đường cong Elliptic. Cho
E
là một đường cong Ellip được xác định trên một
trường . Giả sử n là một số nguyên dương. Theo [6] tập các điểm n-xoắn được định nghĩa
bởi:
 
 
 
|E n P E nP   

(1.7)
1.1.2.3 Đa thức chia
Đa thức chia thứ - m của đường cong Elliptic
E
,
[ , , , ]
m
x y A B


, được xác định bởi
dãy các công thức toán học truy hồi sau đây:
0 1 2
0, 1, 2y
  
  

4 2 2
3
3 6 12x Ax Bx A

   

6 4 3 2 2 2 3
4
4 ( 5 20 5 4 8 )y x Ax Bx A x ABx B A

      

33
2 1 2 1 1m m m m m
    
   

Với
2m

   
 
1
22
2 2 1 2 1
2
m m m m m m
y
     

   

Với
2m
.
Cho
 
,P x y
là một điểm trên đường cong Elliptic
3
Ay x x B  
(trên một trường
nào đó có đặc số khác 2), và
n
là một số nguyên dương. Khi đó:
 
 
 
 
3
2
,
,
,
nn
n
n
x x y
nP
x
xy









(1.8)
1.1.3 Cặp Weil
Cho
E
là một đường cong Elliptic trên một trường và cho
n
là một số nguyên không
chia hết cho đặc số của . Khi đó
 
nn
En 
. Đặt:
 
|1
n
n
xx

  

(1.9)
Là nhóm của các căn bậc
n
của phần tử đơn vị trong . Vì đặc số của không chia
hết cho
n
, nên phương trình
1
n
x 
không có nghiệm bội, do đó nó có
n
nghiệm trong . Do


7


vậy,
n

là một nhóm cyclic bậc
n
. Một phần tử sinh

của
n

được gọi là một căn nguyên
thủy bậc
n
. Điều này tương đương với việc nói rằng
1
k


khi và chỉ khi
n
chia hết cho
k
.
Định lý [6 – Theorem 3.9]:
Cho
E
là một đường cong Elliptic xác định trên một trường và cho
n
là một số
nguyên dương. Giả sử rằng đặc số của trường không chia hết cho
n
. Khi đó một phép
ghép cặp:
   
:
nn
e E n E n



(1.10)
1.2 Đường cong Elliptic
1.2.1 Đặt vấn đề bài toán
Đường cong elliptic là tập hợp các điểm có toạ độ
 
,xy
thoả mãn phương trình có
dạng sau đây:
2 3 2
1 3 2 4 6
y a xy a y x a x a x a     

Trên trường F biểu diễn bằng phương trình Weiretrass:
32
1 3 2 4 6
ay xy a y x a x a x a     

(1.11)
Xét đường cong
E
trên trường nguyên tố hữu hạn
p
F
(
p
nguyên tố,
p
>3 ) với công
thức biến đổi như sau:
23
ab    

(1.12)



Hình 1: Một ví dụ về đường cong Elliptic
Định nghĩa:
Giả sử

là một trường có đặc số khác 2 và khác 3 và xét đa thức
3
ab   
(với a,
b



). Khi đó đường cong elliptic trên trường :
23
ab     
là tập hợp tất cả các
điểm (x, y) với x, y



sao cho (1.12) không có các nghiệm bội tức là
32
4 27 0moda b p
cùng với phần tử O - điểm O này được gọi là điểm vô hạn.
Tính chất của đường cong elliptic:


8


Nếu hai điểm
1 1 1
(x y )
và
2 2 2
(x y )
với
12
xx
nằm trên đường cùng một đường
cong elliptic

, thì đường thẳng qua hai điểm
1


và
2

sẽ cắt một điểm duy nhất
 
3 3 3
x , y
có thể xác định thông qua
1


và
2

nằm trên đường cong

.
Tiếp tuyến của đường cong tại điểm bất kỳ
 
P x, y
trên đường cong

cũng cắt đường
cong elliptic

tại một điểm duy nhất nằm trên đường

, điểm này cũng có thể xác định được
thông qua P.
1.2.2 Đường cong elliptic trên trường hữu hạn
Xét trường hữu hạn
q
F
của
q = p
r
phần tử trên trường hữu hạn . Giả sử E là đường
cong elliptic được định nghĩa trên
q
F
. Nếu đặc số của trường
2p 
hoặc
3p 
thì E được
cho bởi phương trình ở (1.13) và (1.14) .
Định lý: Gọi N là số các điểm trên đường cong elliptic được định nghĩa trên
q
F
. Khi
đó
 
N q 1 2 q  

1.2.3 Các phép toán trên đường cong Elliptic
1.2.3.1 Phép cộng
Giả sử P = (x
1
, y
1
) và Q (x
2
, y
2
) là hai điểm của E. Nếu x
1
= x
2
và y
1 =
-

y
2
thì ta định
nghĩa P + Q = O. Ngược lại thì P + Q = (x
3
, y
3
)

E trong đó:
 
2
3 1 2 3 1 3 1
x x – x , y x – x – y

  
,
Với:

   
 
2 1 2 1
2
1
y – y x – x
3x a 2 y











Khi P ≠ Q( nếu x
1
= x
2
th ì

là hệ số góc đường
thẳng qua P và Q) (1.17)

Khi P = Q (

là đạo hàm của đường cong tại P) (1.18)



9



Hình 2: Phép cộng trên đường cong Elliptic

Tính chất
 Dễ thấy rằng tập E với phép toán cộng đó tạo thành một nhóm Abelian:
 Tính đóng: Nếu P, Q

E thì P + Q

E.
 Tính kết hợp: Nếu P, Q, R

E thì P + ( Q + R ) = R + ( Q + P ).
 Tồn tại phần tử trung hoà O: với mọi P

E thì P + O = O + P = P (theo định nghĩa).
 Tồn tại phần tử nghịch đảo: với mỗi
 
P , x y E
thì luôn tồn tại phần tử
 
P , -x y E
để P + (-P) = O.
 Tính chất giao hoán: Nếu P, Q

E thì P + Q = Q + P.
1.2.3.2 Phép nhân
Phép nhân một số nguyên k với một điểm P thuộc đường cong elliptic E là điểm Q
được xác định bằng cách cộng k lần điểm P và dĩ nhiên
: P P P P PQ E k     
( k phép cộng điểm P).
P
Q
P+ Q
R
P
2P
R
-1
-2
2
1


10



Hình 3: Ví dụ phép nhân đôi trên đường cong Elliptic
1.2.4 Đếm số điểm trên đường cong Elliptic trên trường
q
F

1.2.4.1 Định lý Hasse
N là số điểm của E trên trường F
q
(trường hữu hạn q phần tử). Khi đó:
 
N – q 1 2 q
. Từ định lý Hasse suy ra
 
#E –
q
q 1 t
trong đó
t 2 q
.
1.2.4.2 Định nghĩa
Bậc của điểm G thuộc E là số k dương bé nhất sao cho kG = O; khi k = #E(F
q
) thì G là
điểm cơ sở của E.
1.2.5 Phương pháp chọn đường cong Elliptic phù hợp và điểm cơ sở
1.2.5.1 Trường
Một đường cong elliptic trên một trường hữu hạn tạo thành nhóm Abelian được sử
dụng trong mật mã học. Một ví dụ là việc chọn trường
r
2
F
giúp thực hiện các phép tính nhanh
và dễ dàng triển khai được trên các thiết bị cứng. Tuy nhiên, các đường cong trên trường
r
2
F

có thể bị tấn công bởi MOV, trong khi các đường cong trên trường
p
F
(p là số nguyên tố lớn)
lại chống lại được kiểu tấn công này. Một chú ý nữa là việc tính số điểm trên #
()E
. Tốc
độ của thuật toán Shoof phụ thuộc vào kích thước và đặc số của trường K.
1.2.5.2 Dạng của đường cong elliptic
Trên trường F
q
có hai lớp đường cong elliptic được dùng trong các hệ mã hoá là
supersingular. Xét F
q
có đặc số là
 
m
2 g 2
. Khi đó:


11


 Tập tất cả các cặp nghiệm (x, y) của phương trình
23
y ax x bx c   
với a, b,
c

F
q
và a = 0 (mod q) cùng với điểm trung hoà O tạo thành một đường cong elliptic
dạng supersin gular.
 Tập tất cả các cặp nghiệm (x, y) của phương trình
23
y ax x bx c   
với a, b,
c

F
q
và b = 0 (mod q) cùng với điểm trung hoà O tạo thành một đường cong elliptic
dạng non-supersingular.
1.2.5.3 Phương pháp lựa chọn
Phương pháp- Phương pháp chọn ngẫu nhiên Kobliz:
(1) .Chọn ngẫu nhiên 3 phần tử từ F
q
là x, y, a
(2) .Tính b = y
2
– (x
3
+ ax)
(3) .Kiểm tra 4a
3
+ 27b
2
≠ 0 để đảm bảo phương trình x
3
+ ax + b =0 không có nghiệm
kép.
(4) .Nếu điều kiện trên không thoả mãn quay lại bước 1.
(5) .Còn lại, đặt P = (x, y) và đường cong y
2
= x
3
+ ax +b là đường cong cần chọn.
1.2.6 Đánh giá các tấn công hệ mật đường cong Elliptic
1.2.6.1 Phương pháp Pohlig - Hellman
Cho
,PQ
là các phần tử trong nhóm hữu hạn G bậc N. Ta muốn tìm một số nguyên k
với
kP Q
. Giả sử biết phân tích ra thừa số nguyên tố của N là:
i
e
i
i
Nn


Phương pháp Pohlig – Hellman thực hiện tốt nếu tất cả các ước nguyên tố của N là
nhỏ. Nếu ước nguyên tố lớn nhất xấp xỉ lớn của N thì phương pháp Pohlig – Hellman rất khó
áp dụng. Vì lý do này, các hệ mật dựa trên logarith rời rạc, nói chung thường chọn bậc của
nhóm có chứa một thừa số nguyên tố lớn.
1.2.6.2 Tấn công MOV
Thuật toán 1: Tấn công MOV
Input:
, ( )
p
P Q E
,
()ord P N
,
gcd( , )N p 1
,
Q kP

Output:
(mod )kN

(1). Chọn một điểm ngẫu nhiên
()
m
p
TE

(2). Tính bậc M của T


12


(3). Đặt
gcd( , )d M N
, đặt
( / )
1
T M d T
. Khi đó
1
T
có bậc
d
chia hết cho
N
,
vậy
 
1
T E N

(4). Tính
( , )
1 N 1
e P T


và
( , )
2 N 2
e P T


. Khi đó cả
1

,
2

đều thuộc vào
*
m
d
p



(5). Giải bài toán log rời rạc
k
21


trong
*
m
p
. Kết quả cho ta
(mod )kd
.
(6). Lặp lại với các điểm ngẫu nhiên T đến khi bội chung nhỏ nhất của các số d khác
nhau thu được là N. Khi đó ta xác định được
(mod )kN

1.2.6.3 Phương pháp Xedni
Thuật toán tính chỉ số ngược đầu tiên là nâng các điểm
, , ,
1 2 n
P P P
, sau đó chọn một
đường cong Elliptic
 
EQ
chứa các điểm đã nâng và hy vọng rằng chúng phụ thuộc tuyến
tính. Nghĩa là thỏa mãn quan hệ
r
ii
i1
n P 0



. Tuy nhiên, xác suất để chúng phụ thuộc tuyến
tính là nhỏ.
1.2.6.4 Các tấn công dựa trên giả thuyết Diffie – Hellman
Cho G là một nhóm Abel bậc nguyên tố
p
và
g
là phần tử sinh của G. Bài toán
logarith rời rạc DLP trong G là bài toán tìm số
p
a
khi biết
g
và
a
g
trong G. Nhiều hệ
mật được thiết kế dựa trên bài toán DLP, tuy nhiên hầu hết chúng có độ an toàn tương đương
với một biến thể yếu hơn của bài toán DLP. Hai biến thể yếu hơn quan trọng nhất là bài toán
DH – Tính toán CDH và bài toán DH – Quyết định DDH.
CDH: Cho
 
,,
ab
g g g
. Tính
ab
g
?
DDH: Cho
 
, , ,
abc
g g g g
. Xác định xem
c ab
trong
p
hay không?
1.2.6.5 Các tấn công cài đặt
Kiểu tấn công cài đặt thứ nhất là dựa trên điểm không hợp lệ của đường cong Elliptic.
Nếu trong quá trình nhận và xử lý một điểm trên đường cong mà không thực hiện việc kiểm
tra xem nó có thực sự nằm trên đường cong đã cho hay không thì lược đồ có thể bị tấn công.
Dạng tấn công thứ hai là kiểu tấn công phân tích năng lượng để khám phá khóa bí mật
Hiệu quả của các kiểu tấn công này phụ thuộc vào cách cài đặt cụ thể.
1.2.6.6 Nhận xét
Tổng hợp các phương pháp trên ta có bảng như sau:


13


Bảng 1: So sánh các phương pháp tấn công hệ mật Elliptic
STT
Phương
pháp
Độ phức tạp của thuật toán
trong nhóm có bậc là N
Yêu cầu
bộ nhớ
Ghi chú
1
Pohlig -
Hellman
OK
với K là ước nguyên tố
lớn nhất của N
Nhỏ
Hiệu quả nếu N chỉ có
các ước nguyên tố nhỏ.
2
MOV
~
 
*
DLP
m
p

Nhỏ
Hiệu quả nếu
m
nhỏ
3
Xedni
()ON

-
Không áp dụng được
trong thực tế
4
Tấn công
dựa vào
một số giả
thuyết DH
( .log )O d p
với d là ước của
3
p d p

p
O
d




Yêu cầu giả thuyết
mạnh, cần bộ nhớ lớn
5
Tấn công
cài đặt
Phụ thuộc vào cách cài đặt cụ
thể
Nhỏ
Thời gian đa thức theo
Conron.
Kết luận chương
Các kết quả mà chương 1 đạt được bao gồm:
(1) Đã nghiên cứu tổng quan về hệ mật Elliptic trên trường hữu hạn, nghiên cứu về các
vấn đề như đa thức chia, nhóm con xoắn, các tự đồng cấu, Weil pairing.
(2) Nghiên cứu, xem xét và đánh giá về độ phức tạp tính toán, yêu cầu bộ nhớ và khả năng
áp dụng trong thực tế của các tấn công đối với hệ mật Elliptic.
CHƯƠNG 2 – MẬT MÃ ĐƯỜNG CONG ELLIPTIC
2.1 Mật mã đường cong Elliptic
2.1.1 Thiết lập cơ sở
Alice muốn gửi một văn bản, thường được gọi là bản rõ (Plaintext), tới Bob. Cô ấy
mã hóa văn bản để thu được bản mã (Ciphertext). Để mã hóa văn bản, Alice sử dụng một
khóa mã hóa (Encryption key). Bob sử dụng một khóa giải mã (Decryption key) để giải mã
bản mã nhận được.
Có hai cách mã hóa cơ bản. Trong mật mã đối xứng (Symmetric Encryption), khóa
mã hóa và khóa giải mã là như nhau,
Một dạng khác của mã hóa là mật mã khóa công khai (Public Key Encryption),
hoặc mật mã không đối xứng (Asymmetric Encryption).


14



Hình 4: Mô phỏng mã hóa công khai
2.1.2 Nhúng bản rõ lên đường cong
Nhúng bản rõ lên E là biểu diễn lại bản rõ đó như là các điểm trên E, nhờ đó có thể
thực hiện được các tính toán trên E. Có một số phương pháp để thực hiện việc này. Trong đó
có 2 phương pháp chính là “nhúng” (Imbeding) và “mặt nạ” (Mask).
2.1.3. Logarith rời rạc trên đường cong Elliptic
Định nghĩa:
E là đường cong Elliptic trên trường Fq và B là một điểm trên E. Khi đó bài toán logarit
rời rạc trên E (theo cơ số B) là một bài toán, cho trước một điểm
P E
, tìm số nguyên
xZ

sao cho xB = P (nếu số x như vậy tồn tại)
2.1.4 Trao đổi khóa Diffie – Hellman
Alice và Bob muốn thống nhất một khóa chung mà họ có thể sử dụng cho việc trao đổi
dữ liệu thông qua một sơ đồ mã đối xứng. Alice và Bob thống nhất một đường cong elliptic
E trên trường hữu hạn F
q
sao cho bài toán logarithm rời rạc là khó trong E(F
q
). Thông tin duy
nhất mà kẻ trộm Eve thấy chỉ là đường cong E, trường hữu hạn F
q
, và các điểm P, aP và bP.
Do đó cô ta cần phải giải quyết các bài toán sau:
2.1.4.1 Bài toán Diffie – Hellman
Cho trước P, aP và bP trong E(F
q
), tính abP?
Nếu Eve có thể giải bài toán log rời rạc trong E(F
q
), khi đó cô ta có thể sử dụng P và
aP để tìm a. Khi đó cô ta có thể tính a(bP) để nhận được abP. Tuy nhiên, liệu có thể có cách
nào để tính abP mà không phải giải bài toán log rời rạc đầu tiên.
2.1.4.2 Bài toán quyết định Diffie – Hellman
Cho trước P, aP và bP trong E(F
q
) và cho trước một điểm Q ∈ E(F
q
). Khi đấy có xác
định được Q = abP hay không?