5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
MỤC LỤC
MỤC LỤC........................................................................................................1
LỜI ĐẦU
CẢM...........................................................................................................3
ƠN...................................................................................................2
MỞ
CHƯƠNG 1.......................................................................................................5
CƠ SỞ TOÁN HỌC..........................................................................................5
1.1. Phương trình đồng dư bậc hai và thặng dư bậc hai................................5
1.2. Nhóm......................................................................................................9
1.3. Trường..................................................................................................10
1.4. Trường hữu hạn....................................................................................11
CHƯƠNG 2.....................................................................................................12
ĐƯỜNG CONG ELLIPTIC............................................................................12
2.1. Mở đầu và đặt bài toán.........................................................................12
2.2. Đường cong elliptic trên trường hữu hạn.............................................14
2.3. Các phép toán trên đường cong Elliptic...............................................15
2.4. Đếm số điểm trên đường cong elliptic trên trường Fq.........................17
2.5. Phương pháp chọn đường cong Elliptic phù hợp và điểm cơ sở..........18
2.5.1. Trường K.......................................................................................18
2.5.2. Dạng của đường cong elliptic........................................................19
2.5.3. Phương pháp lựa chọn...................................................................19
CHƯƠNG 3.....................................................................................................21
HỆ MẬT ĐƯỜNG CONG ELLIPTIC...........................................................21
3.1. Mở đầu và đặt bài toán.........................................................................21
3.2. Nhúng bản rõ lên đường cong..............................................................22
3.3. Logarit rời rạc trên đường cong Elliptic( Discrete logarithm on
Elliptic)........................................................................................................24
3.4. Vấn đề trao đổi khoá Diffie- Hellman(D- H) trên Elliptic...................24
3.5. Hệ mât mã hoá Elgamal trên đường cong Elliptic..............................25
CHƯƠNG 4.....................................................................................................27
MỘT VÀI ỨNG DỤNG..................................................................................27
4.1. Lược đồ chữ ký số trên đường cong elliptic (Elliptic Curve Signature
Algorithm ) - ECDSA.................................................................................27
4.1.1. Lược đồ ký ECDSA......................................................................27
4.1.2. Độ an toàn của sơ đồ chữ ký ECDSA...........................................28
4.2. Một số chuẩn sử dụng hệ mật ECC......................................................29
KẾT LUẬN.....................................................................................................32
TÀI LIỆU THAM KHẢO...............................................................................33
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
-1-
Lớp CT702
1/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
LỜI CẢM ƠN
Em xin bày tỏ lòng biết ơn tới TS Hồ Văn Canh đã tận tình hướng dẫn
và cung cấp những tài liệu quý báu để em hoàn thành luận văn này.
Em xin chân thành cảm ơn các Thầy cô giáo khoa công nghệ thông tin
trường Đại Học Dân Lập Hải Phòng đã nhiệt tình giảng dạy chúng em trong 4
năm học.
Tôi cũng xin chân thành cảm ơn các bạn bè đồng nghiệp đã giúp đỡ tôi
trong quá trình học tập và hoàn thành tốt luận văn này!
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
-2-
Lớp CT702
2/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
MỞ ĐẦU
Ngày nay với sự phát triển mạnh mẽ của công nghệ thông tin, truyền
thông nói chung và Internet nói riêng đã giúp cho việc trao đổi thông tin
nhanh chóng, dễ dàng, E-mail cho phép người ta nhận hay gửi thư ngay trên
máy tính của mình, E-business cho phép thực hiện các giao dịch trên mạn.
Do vậy một vấn đề phát sinh là thông tin có thể bị trộm cắp, có thể là sai lệch,
có thể giả mạo. Điều đó có thể ảnh hưởng tới các tổ chứa, các công ty hay cả
một quốc gia. Những bí mật kinh doanh, tài chính là mục tiêu của các đối thủ
cạnh tranh. Những tin tức về an ninh quốc gia là mục tiêu của các tổ chức tình
báo trong và ngoài nước.
Để giải quyết tình hình trên an toàn thông tin được đặt ra cấp thiết. Kỹ
thuật mật mã là một trong những giải pháp của an toàn truyên thông. Kỹ thuật
này có từ ngàn xưa nhưng nó đơn giản, ngày nay khi có mạng máy tính người
ta dùng mật mã hiện đại. Các nhà khoa học đã phát minh ra những hệ mật mã
nhằm che dấu thông tin cũng như là làm rõ chúng để tránh sự giòm ngó của
những kẻ cố tình phá hoại như các hệ mật: RSA, Elgamal… mặc dù cũng rất
an toàn nhưng có độ dài khoá lớn nên trong một số lĩnh vực không thể ứng
dụng được.
Chính vì vậy người ta đã phát minh một hệ mật đó là hệ mật trên đường
cong elliptic, hệ mật này được đánh giá là hệ mật có độ bảo mật an toàn cao
và hiệu quả hơn nhiều so với hệ mật công khai khác, nó đã được ứng dụng
trên nhiều lĩnh vực và được sử dụng nhiều nơi trên thế giới tuy nhiên còn
mới mẻ ở Việt Nam. Trong tương lai gần Hệ mật trên đường cong Elliptic
sẽ được sử dụng một cách phổ biến và thay thế những hệ mật trước nó.
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
-3-
Lớp CT702
3/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
Vì lý do đó, em đã chọn đề tài “Hệ mật đường cong elliptic” để nghiên
cứu, tìm hiểu nhằm tiến tới khai thác hệ mật này phục vụ cho bảo mật thông
tin trong thực tế.
Luân văn này gồm 4 chương
Chương 1: Cơ sở toán học
Chương 2: Hệ mật mã
Chương 3: Đường cong Elliptic
Chương 4: Hệ mật đường cong Elliptic
Chương 5: Một vài ứng dụng
Nhưng trong báo cáo này em trình bày tóm tắt nội dung chính trong đề
tài:”Hệ mật đường cong elliptic”.
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
-4-
Lớp CT702
4/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
CHƯƠNG 1
CƠ SỞ TOÁN HỌC
1.1. Phương trình đồng dư bậc hai và thặng dư bậc hai
Ta xét phương trình đồng dư bậc hai có dạng như sau:
x2 ≡ a (mod n)
Trong đó n là số nguyên dương, a là số nguyên với gcd(a, n) ≡ 1, và x
là ẩn số. Phương trình đó không phải bao giờ cũng có nghiệm, khi nó có
nghiệm thì ta gọi a là thặng dư bậc hai mod n. Ngược lại thì a gọi là một bất
thặng dư bậc hai mod n.
Tập các số nguyên nguyên tố với n được phân hoạch thành hai tập con.
Tập Qn các thặng dư bậc hai mod n, và tập các bất thặng dư bậc hai mod n.
Tiêu chuẩn Euler
Khi p là số nguyên tố, số a là thặng dư bậc 2 mod p nếu và chỉ nếu a (p1)/2
≡ 1 (mod p)
Ký hiệu Legendre
Cho p là số nguyên tố, với p >2, số a ≥ 0 là số nguyên. Ta định nghĩa
a
như sau:
p
a
p
=
0, khi, a 0≡(mod
1, khi, a ∈
Qp;
−1, khi,∉
a Qp.
p)
Chú ý:
+ Từ định nghĩa suy ra a là thặng dư bậc hai mod p khi và chỉ khi
a
p
= 1
+ Theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0 ta có:
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
-5-
Lớp CT702
5/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
a
(p-1)/2
p
≡ a
Hệ mật đường cong elliptic
(mod p) .
Legendre Symbol thoả mãn các tính chất sau:
a
1.
p
chỉ
ab
=
p
2.
phụ thuộc vào đồng dư của a theo mod p.
a b
p
;
p
ab
b nguyên tố với p thì p =
2
3.
1
=1 và
p
4.
a
p
;
1
(p-1)/2
.
− p
= (-1)
Định lý 1:
1 p ≡ ± 1 mod 8
(p 2 – 1)/8
2
−1 p ≡ ± 3 mod 8
=
(-1)
=
p
Định lý: Gọi là luật thuận nghịch bình phương.
Cho p, q là 2 số nguyên tố lẻ, khi đó:
= (-1)(p-1)(q-1)/4
.=
Định lý 2
Nếu a ≡ b mod p →
a
p
=
b
p
Định lý 3
2
p
=
1
p ≡ 1 mod 8 hay p ≡ 7 mod 8
-1 p ≡ 3 mod 8 hay p ≡ 5 mod 8
Ví dụ: Cho a = 186, p= 401 (p là số nguyên)
Tìm a có là thặng dư bậc hai không nghĩa là a ∈ Q401?
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
-6-
Lớp CT702
6/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
Và tìm x? với x2 ≡ a mod 401
a 186 2.93 2 93
=
=
.
p
=
401 401 401 401
Theo định lý 3:
2
Vì 401 ≡ 1 mod 8 ⇒ 401
=1 vậy
a 186 93 3 ⋅ 31 3 31
=
=
=
p
=
401 401 401 401 401
2.400
3
401 2
Nhưng 401 = (-1) 4 . 3
= 3 = -1 (định lý 1)
30 .400
31
401
Và
= (-1)
Vậy
4
2
29
401
401
3
3
31
=
=
=
29
=-1.
a
p
= 1.(-1).(-1) = 1 Do đó
a ∈ Q401
Tiếp theo ta cần tìm x: x2 ≡ 186 mod 401.
Lấy n =3 rõ ràng 3 không là đồng dư toàn phương của 186 theo mod
401 (như trên ta đã chứng minh được
= -1).
401
3
25
Ta có p-1 = 400 = 24. 3
→ b = nS = 18625 mod 401 = 286 mod 401.
S +1
Còn r = a
2
mod 401 = 186 mod 401 = 103.
Tính a-1 mod 401 = 186-1 mod 401 = 235 (thuật toán ơclit mở rộng).
Tính a-1. r 2 = 1032 . 235 mod 401 = 98 vì
α
-2 = 4-2 =2 do đó ta nâng
luỹ thừa 22 = 4 = của 98 và có 98 4 ≡ -1 mod 401 = -1 (98 4 mod 401 = (982
mod 401)( 982 mod 401) mod 401 = 381 2 mod 401 = -1) ⇒ đặt j0 = 1 tiếp
theo, ta có (br)2/a = -1 ⇒ luỹ thừa bậc 2 của nó là 1 ⇒ đặt j1 =0, cứ thế j2
=1(2 = K = α ) Vậy j =5 vì 1.22 +1 = 5
⇒ Căn bậc 2 của 186 là b 5r mod 401 = 304
Thử lại 3042 ≡ 186 mod 401?
Ta có 3042 = 92416 vậy 3042 = 186 = 92230 ≡ 0 mod 401 ⇒ x= 304
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
-7-
Lớp CT702
7/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
Ký hiệu Jacobi Symbol
Bây giờ ta mở rộng ký hiệu Legendre để được ký hiệu Jacobi đối với
mọi số nguyên lẻ n ≥ 1 và mọi số nguyên a ≥ 0.
Giả sử a có khai triển chính tắc thành thừa số là n = pa11, pa22,……, pann thì
a
n =
a1
a2
ak
a
a a
p p ……… p
k
1
2
với a1, a2, ….., ak ≥ 1
P1, P2, ….Pk là những số nguyên tố.
Khi n = p là số nguyên tố thì giá trị của các ký hiệu Legendre và Jacobi
là như nhau. Việc tính ký hiệu Legendre có thể phức tạp khi p rất lớn, trong
khi việc tính ký hiệu Jacobi có thể thuận lợi hơn do có thể sử dụng các tính
chất 1- 4 sau đây:
1. Nếu m1 ≡ m2 mod n thì = .
2. =
3. = .
4. Nếu m và n đều là số là thì:
=
Bây giờ xét việc giải phương trình đồng dư bậc hai:
x2 ≡ a (mod n)
(*)
Trong một trường hợp đặc biệt khi n = p là số nguyên tố có dạng p =
4m + 3 tức là p đồng dư với 3 theo mod 4, và a là một số nguyên nguyên tố
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
-8-
Lớp CT702
8/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
với p. Theo tiêu chuẩn Euler ta biết phương trình (*) có nghiệm khi và chỉ
khi a(p-1)/2 ≡ 1 (mod p). Khi đó ta có:
a
p −
1
2
+
1
≡ a (mod p),
a 2( m +1) ≡ a (mod p).
1.2. Nhóm
Định nghĩa: Nhóm là một tập hợp G ≠ cùng với phép toán hai ngôi *
trên G. Với a, b ∈ G, a * b = ∈ G thoả mãn tính chất sau:
2.
Tính kết hợp: (a * b) * c = a * (b * c) với mọi a, b, c ∈ G.
Phần tử đồng nhất: Tồn tại e ∈ G thoả mãn e * a = a *e = a với mọi a
3.
∈ G (e được gọi là phần tử trung hoà).
Phần tử nghịch đảo: với mỗi a ∈ G, tồn tại một phần tử b ∈ G thoả
1.
mãn b * a = a * b = e (b là duy nhất và được gọi là phần tử nghịch đảo
của a). Và người ta ký hiệu của a bởi a-1.
- Ký hiệu là nhóm nhân và G là nhóm cộng. Trong đó
nhóm cộng, phần tử trung hoà là 0 và phần tử nghịch đảo của a là –a. Trong
nhóm nhân, phần tử trung hoà là 1 và phần tử nghịch đảo của a là a -1.
đ ươc gọi là một nhóm giao hoán (nhóm Abelian) nếu b * a = a * b
với a, b ∈ G.
- Một nhóm có cấp hữu hạn được gọi là nhóm hữu hạn
Nếu là nhóm hữu hạn thì số các phần tử của được gọi là
bậc của G và ký hiệu là |G| . Nếu là nhóm nhân hữu hạn, bậc của một
phần tử a ∈ G kà số nguyên dương nhỏ nhất m thoả mãn am = 1. Trong nhóm
có cấp hữu hạn, với mọi phần tử thuộc nhóm, m luôn tồn tại.
Nhóm Cylic
Là nhóm mà mọi phần tử của nó được sinh ra từ một phần tử đặc biệt g
∈ G.
Phần tử này được gọi là phần tử sinh (nguyên thuỷ) tức là:
Với
x ∈ G(G là nhóm với toán tử * ):
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
∃n
-9-
∈ N mà gn = x
Lớp CT702
9/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
Ví dụ: (Z+, *) là nhóm Cylic có phần tử sinh là 1.
1.3. Trường
Giả sử F là một tập hợp khác rỗng, trên đó có hai phép toán cộng và
phép nhân. Khi đó F là một trường nếu và chỉ nếu:
1. (F, +) là nhóm giao hoán với phần tử đơn vị là “0”.
2. (F\{0}, .) là nhóm giao hoán với phần tử đơn vị là “1”.
3. Các phép toán cộng và nhân có tính chất phân bố:
a.(b.c) = (a.b) + (a.c)
Trường có thể định nghĩa như là vành giao hoán với phần tử đơn vị (trừ
phần tử 0) đều có phần tử nghịch đảo cùng thuộc trường.
p
Ví dụ: Q = { q p, q là số nguyên: (p, q) = 1} trên Q có 2 phép toán cộng
và nhân thông thường là một trường.
Định nghĩa
Cho F là một trường. Tập con K của F cũng là một trường với các toán
tử của F, được gọi là trường con của F, hay F là một trường mở rộng của K.
Nếu K≠ F thì K được gọi là một trường con hợp lệ của F. Trường là tối giản
nếu có không có trường con hợp lệ nào. Với trường F bất kỳ, giao F0 của tất
cả các trường con hợp lệ là trường tối giản. Trường F được gọi là có đặc số 0
nếu F0 ≅ Q nghĩa là F chứa Q như một trường con. Trường F được gọi là đặc
số p nếu F0 ≅ Z p.
Trường hữu hạn là trường chứa hữu hạn các phần tử. Đối với một
trường hữu hạn thì ∀ a ∈ F luôn luôn tồn tại một số nguyên dương n sao cho:
7 48
a6+4.......
+a = 0
n
Định nghĩa
Trường K với phần tử đơn vị nhân là 1. Với p dương nhỏ nhất thoả
1 = 0 được gọi là đặc số của K.
mãn 1 +1 +........ +
p
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 10 -
Lớp CT702
10/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
(Các trường hữu tỷ Q, số thực R, số thực C có đặc số là 0). Người ta chứng
minh được rằng đặc số của trường hữu hạn là số nguyên tố.
Với p là nguyên tố thì GF (pn) có đặc số p.
1.4. Trường hữu hạn
Trường hữu hạn là trường có hữu hạn các phần tử ký hiệu là Fq hoặc
GF(q) với q là số các phần tử.
Trường hữu hạn không có đặc số 0. Ta gọi p là đặc số của F q khi đó Fq
khi đó Fq chứa trường nguyên tố F p = Z/ pZ vì vậy một không gian
vector( không cần thiết phải có chiều hữu hạn) trên trường F p. Lấy f ký hiệu là
chiều của nó coi F p như là một không gian vector đó. Bằng cách chọn cơ sở
cho phép chúng ta lập nên một tương ứng 1-1 giữa không gian vector f chiều
với tập hợp tất cả bộ f phần tử trong F p nghĩa là q là luỹ thừa của đặc số p.
Đối với mỗi lũy thừa nguyên tố q = p f có tồn tại một trường q phần tử và đó
là trường duy nhất (theo nghĩa đẳng cấu).
Cấp của các phần tử trong F*q theo nghĩa đối với phép nhân với F*q là tập hợp
tất cả các phần tử khác không của trường Fq (q hữu hạn)
Chú ý rằng đối với mọi nhóm nhân hữu hạn, cấp của bất cứ một số phần tử
khác không nào cũng là ước của số các phần tử trong nhóm. Cụ thể ta có định
lý
Định nghĩa
Giả sử phần tử g ∈ Fq nếu cấp của g là q-1 tức là {g 1, g2,……, gq-1 = 1}
= F*q
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 11 -
Lớp CT702
11/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
CHƯƠNG 2
ĐƯỜNG CONG ELLIPTIC
2.1. Mở đầu và đặt bài toán
Lý thuyết đường cong Elliptic được xác định trên trường số hữu hạn đã
có địa chỉ ứng dụng trong lĩnh vực mật mã đáng lưu ý. Lý do cơ bản của nó là
đường cong Elliptic trên trường hữu hạn đã cung cấp cho chúng ta một cơ sở
xây dựng thuật toán không thể dùng thuật toán vét cạn để thám mã của nhóm
Abelian ngay cả khi nhóm đó có cấp không lớn lắm.
Đường cong elliptic là tập hợp các điểm có toạ độ (x, y) thoả mãn
phương trình có dạng sau đây:
y2 + a1xy + a3y = x3 + a2x2 +a4x + a6.
Trên trường F biểu diễn bằng phương trình Weiretrass:
y2 + a1xy + a3y = x3 + a2x2 +a4x + a6 2
(*)
Xét đường cong E trên trườngnguyên tố hữu hạn F p (p nguyên tố, p>3 ) với
công thức biến đổi như sau:
X→X −
a2
3
, Y→ Y −
a1 X + a3
2
Khi đó phương trình Weierstrass có dạng:
X3 + aX +b.
Vậy trong trường F p (*) trở thành:
Y2 = X3 + aX + b
Định nghĩa:
Giả sử K là một trường có đặc số khác 2 và khác 3 và xét đa thức
X3 + aX + b(với a, b ∈ K)
Khi đó đường cong elliptic trên trường K: Y2 = X3 + aX + b (1) là tập
hợp tất cả các điểm (x, y) với x, y
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
∈ K sao cho (1) không có các nghiệm bội
- 12 -
Lớp CT702
12/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
tức là 4a3 + 27b2 ≠ 0 mod p cùng với phần tử O - điểm O này được gọi là
điểm vô hạn.
Tức là đường cong Elliptic là tập hợp S:
S = { (x, y) : y 2 = x3 + ax +b,
x, y∈ K } ∪ {O} .
Với a, b ∈ K cho trước sao cho 4a3 + 27b2 ≠ 0 theo mod p.
Nếu K là trường đặc số 2 thì ta định nghĩa:
S = { (x, y) : y-2 + y= x3 + ax +b }
{O}
∪
(2)
Nếu K là trường đặc số 3 thì ta định nghĩa:
S = { (x, y) : y2 = x3 + ax +bx + c }
∪
{O} (3)
* Tính chất của đường cong elliptic:
• Nếu hai điểm P1 (x1, y1 ) và P2 (x2, y2) với x1 ≠ x2 nằm trên đường cùng
một đường cong elliptic E, thì đường thẳng qua hai điểm P 1 và P2 sẽ cắt
một điểm duy nhất P3 ( x3, y3) có thể xác định thông qua P1 và P2 nằm
trên đường cong E .
• Tiếp tuyến của đường cong tại điểm bất kỳ P(x, y) trên đường cong E
cũng cắt đường cong elliptic E tại một điểm duy nhất nằm trên đường
E, điểm này cũng có thể xác định được thông qua P.
Dựa vào những tính chất đó người ta đã nghiên cứu và phát hiện ra một
khả năng mới cho kỹ thuật mã hoá nói chung và chứng thực nói riêng, kỹ
thuật mã hoá dựa trên đường cong elliptic.
Người ta đã chỉ ra rằng các hệ mã hoá bằng đường cong elliptic có độ
bảo mật cao hơn nhiều so với các hệ mã hoá công khai khác như RSA,
Elgamal. Độ bảo mật dựa trên độ khó phân tích số nguyên thành các thừa số
nguyên tố cũng như bài toán logarit rời rạc, độ dài khoá giảm đi nhiều lần và
do đó tốc độ thực hiện cũng sẽ nhanh hơn rất nhiều. Chính vì vậy ta áp dụng
kỹ thuật mã hoá bằng đường cong elliptic vào nhiều lĩnh vực khác nhau.
Các kỹ thuật mã hoá bằng phương pháp đường cong elliptic được sử
dụng hiệu quả nhất trong việc xây dựng các giải pháp bảo mật thông tin cho
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 13 -
Lớp CT702
13/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
các thẻ thông minh(Smart Card), các thiết bị điện tử có khả năng tính toán và
không gian bộ nhớ hạn chế.
2.2. Đường cong elliptic trên trường hữu hạn
Xét trường hữu hạn F q của q = pr phần tử trên trường hữu hạn K . Giả sử
E là đường cong elliptic được định nghĩa trên F q. Nếu đặc số của trường p=2
hoặc p=3 thì E được cho bởi phương trình ở (2) và (3) .
Dễ dàng thấy rằng một đường cong như vậy có thể có nhiều nhất là 2p+1
điểm trong F q, nghĩa là điểm vô cùng với 2q cặp (x, y) trong đó x, y ∈ F q thoả
mãn (1) (2) (3) (nếu p=2 hoặc 3), tức là với mỗi q giá trị x có thể có tồn tại
nhiều nhất 2 giá trị y thoả mãn (1). Nhưng vì chỉ có một nửa các phần của F *q
có căn bậc 2 người ta kỳ vọng (nếu x 3 + ax +b là các phần tử ngẫu nhiên của
trường ) chỉ có khoảng một nửa số các điểm của Fq. Chính xác hơn, giả sử
đặc trưng toàn phương của F q (lấy
λ
(0) = 0).
λ
Ví dụ: Nếu q = p là 1 số nguyên tố thì
x
(x) =(
λ
p
) là ký hiệu Legedre
Symbol). Do đó trong tất cả mọi trường hợp số các nghiệm y ∈ F q thoả mãn
phương trình y2 = u là bằng 1 + λ (u). Vì vậy số các nghiệm ở phương trình 1
và điểm vô hạn là:
1 + ∑ (1+
x∈
Fq
(x3 + ax + b)) = q + 1 + ∑ (1+
λ
Ta hy vọng rằng
x∈
Fq
(x3 + ax + b)) (6)
λ
( x3 + ax + b) bằng +1 và -1.
λ
Lấy tổng ngẫu nhiên: tung đồng xu q lần. Người ta thấy rằng
∑ (x3 + ax + b) bị chặn bởi 2
x∈
Fq
q
đó chính là định lý Hasses được phát
triển như sau:
Định lý: Gọi N là số các điểm trên đường cong elliptic được định nghĩa trên
F q. Khi đó | N−(q + 1) | ≤ 2
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
q
- 14 -
Lớp CT702
14/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
2.3. Các phép toán trên đường cong Elliptic
Giả sử p là một số nguyên tố >3. Người ta chứng minh được rằng bằng
phép biến đổi tuyến tính, ta có thể quy phương trình đường cong elliptic về
dạng Weierstrass như sau:
Y2 = X3 + aX + b
Đường cong elliptic Y2 = X 3 + aX + b trên Z p được định nghĩa là tập hợp tất
cả các điểm (x, y) ∈ Z p × Z p thoả mãn phương trình:
Y2 = X3 + aX + b (mod p),
Cùng với một phần tử đặc biệt ký hiệu là O là phần tử trung hoà. Tập hợp đó
được ký hiệu là E .
23.1. Phép cộng
Giả sử P= (x1, y1) và Q (x2, y2) là hai điểm của E .
Nếu x1 = x2 và y1 = - y2 thì ta định nghĩa P + Q = O
Ngược lại th ì P + Q = (x3, y3) ∈ E trong đó
λ 2
x3 =
- x1 – x2 , y3 =
(x1 – x3 ) –y1,
λ
Với
=
(y2 – y1 ) / (x2 – x1), khi P ≠ Q( nếu x 1 = x2 th ì
λ
λ
là hệ số góc đường
thẳng qua P và Q) (*)
(3x2 + a) / 2 y1, khi P = Q ( λ là đạo hàm của đường cong tại P)
(**)
Vậy nếu P ≠ Q tức là x1 ≠ x2
2
y − y
x3 = −
x x
2
2
1
1
- x1 – x2
(*)
y − y
y3 = x − x ( x1 – x3) - y1
2
2
1
1
N ếu P =Q
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 15 -
Lớp CT702
15/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
3 x + a
x3 =
2 y
1
1
Hệ mật đường cong elliptic
2
– 2x2
(**)
3 x + a
( x1 – x3) - y1
y3 =
y
2
2
1
1
2
1
R
Q
P
R
2P
P
P+ Q
-1
-2
Hình 2.6.1 Phép cộng trên đường cong Elliptic
Chú ý rằng các điểm (x3, y3), (x3, -y3) cũng nằm trên đường cong E và xét về
mặt hình học, thì các điểm (x1, y1), (x2, y2), (x3, -y3) cũng nằm trên một đường
thẳng.
Ngoài ra ta định nghĩa thêm: P + O = O + P = P.
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:
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 16 -
Lớp CT702
16/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
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
(theo định nghĩa).
Tồn tại phần tử nghịch đảo: với mỗi P(x, y)
∈ E thì P + O = O + P = P
∈ E thì luôn tồn tạ 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.
Ví dụ: Xét đường cong elliptic y2 = x3 – 36x
Lấy P =(-3, 9), Q = (-2, 8). Hãy tìm P + Q và 2P?
Với x1 = -3, y1 = 9, x2 = -2 , y2 = 8. Do đó áp dụng công thức(*) ta có:
x3 =
(8 − 9)
2
−2 +3
+3 + 2 = 1+ 3 +2 = 6.
−9
y3 = -9 − 2 + 3
(-3-6) = -9 + (-1)(-9) =0.
8
Vậy P +Q = (6, 0). Bây giờ ta tính 2P áp dụng (**) ta có: x1= -3, y1 = 9
x3 =
25
và do đó y3=
4
−35
8
. Vậy 2P = (
25
,
−35
4
)
8
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 Q ∈ E : k
× P = P + P + P……+ P ( k phép cộng điểm P).
Vì vậy nếu G là một điểm thuộc đường cong elliptic E thì với mỗi số
nguyên dương k luôn dễ dàng xác định được điểm Q = k × G
2.4. Đếm số điểm trên đường cong elliptic trên trường Fq
Việc xây dựng các hệ mật mã trên đường cong elliptic bao gồm việc
lựa chọn đường cong E thích hợp và một điểm G trên E gọi là điểm cơ sở. Xét
trường K là Fq.
Định lý Hasse
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 17 -
Lớp CT702
17/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
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
q
.Từ định lý Hasse suy ra #E(Fq) = q +1 – t trong đó |t| ≤ 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(Fq) thì G là điểm cơ sở của E.
2.5. Phương pháp chọn đường cong Elliptic phù hợp và điểm cơ sở
Việc chọn một đường cong elliptic thế nào ảnh hưởng đến tốc độ, tính
hiệu quả, độ dài khoá và tính an toàn của hệ mật mã trên đường cong này. Dù
E, K và điểm cơ sở B ∈ E cố định và công khai nhưng việc chọn các tham số
này phù hợp là bước quan trọng nhất.
2.5.1. Trường K
Trước hết chúng ta xem xét sự ảnh hưởng của trường K đến cấu trúc
nhóm của E(K) và các hệ mật mã trên E (K).
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 F 2r
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 F 2r có thể bị tấn công bởi
MOV, trong khi các đường cong trên trường F p (p là số nguyên tố lớn) lại
chống lại được kiểu tấn công này. Rõ ràng, các đường cong elliptic trên
trường số nguyên tố F p và trên trường F qn có các tính chất giúp chúng có thể
thực thi được trên các thiết bị mà vẫn đảm bảo an toàn.
Một chú ý nữa là việc tính số điểm trên # E (K). Với # E (K) thích hợp
có thể là điều kiện cho phép thực hiện tấn công Pohlig – Hellman. Có thể
dùng thuật toán đơn định thời gian đa thức Shoof để tính trên trường hữu hạn
Fq với đặc số khác 2 hoặc 3. Tốc độ của thuật toán Shoof phụ thuộc vào kích
r
thước và đặc số của trường K. Ví dụ với r nhỏ, tính # E (F ) có thể nhanh hơn
2
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 18 -
Lớp CT702
18/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
Hệ mật đường cong elliptic
một chút so với tính # E(F p), trong đó p lớn hơn đáng kể so với 2r , nhưng khi r
r
tăng thì tính # E (F 2 )
mất nhiều thời gian hơn tính # E (F p ).
2.5.2. Dạng của đường cong elliptic
Trước hết, chúng ta cần xem các dạng đường cong elliptic. Trên trường
Fq có hai lớp đường cong elliptic được dùng trong các hệ mã hoá là
supersinggular. Xét Fq có đặc số là 2 (g = 2m). Khi đó:
Tập tất cả các cặp nghiệm (x, y) của phương trình y 2 +ax = x3 + bx + c
với a, b, c
∈ Fq 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 supersingular.
Tập tất cả các cặp nghiệm (x, y) của phương trình y2 + ax = x3 + bx + c
với a, b, c
∈ Fq 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.
Supersingular Curve: Menezes và Vanstone đã tìm ra các ưu điểm của
các đường cong elliptic supersingular cho các hệ mật mã, đặc biệt trên trường
F2r . Tuy nhiên, các đường cong supersingular có thể bị tấn công bằng MOV.
Nonsupersingular Curve: Ưu điểm của các đường cong nonsupersingular
là nó cung cấp độ bảo mật tương đương như các đường cong supersingular
nhưng với các trường nhỏ hơn. Độ dài khoá ngắn giúp chúng có thể triển khai
trên các thiết bị như smart card. Hơn nữa, các đường cong nonsupersingular
có thể chống lại tấn công MOV, ví dụ nhóm con cylic cỡ 2160.
2.5.3. Phương pháp lựa chọn
Có nhiều cách chọn các đường cong elliptic và điểm cơ sở B thuộc
đường cong đó. Một cách chọn điển hình là:
Phương pháp- Phương pháp chọn ngẫu nhiên Kobliz:
Sơ đồ 3.8. Phương pháp chọn ngẫu nhiên Kobliz
1.
Chọn ngẫu nhiên 3 phần tử từ Fq là x, y, a
2
2.
3
Tính b = y – (x + ax)
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 19 -
Lớp CT702
19/33
5/12/2018
Elliptic - slide pdf.c om
Đồ án tốt nghiệp
3.
Hệ mật đường cong elliptic
Kiểm tra 4a3 + 27b2 ≠ 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ôn thoả mãn quay lại bước 1.
5.
Còn lại, đặt P = (x, y) và đường cong y 2 = x3 + ax +b là đường cong cần
chọn.
Tuy nhiên phương pháp này có thể tạo ra các đường cong không đảm bảo
một số yêu cầu định trước. Một kỹ thuật cải tiến là xây dựng các đường cong
với các tính chất cho trước. Cũng có thể chọn những đường cong để tạo các
hệ mã hoá không phụ thuộc vào bài toán EDLP, chẳng hạn các hệ elliptic dựa
trên RSA.
Các hệ mật mã elliptic làm việc với các nhóm con cylic của E với phần tử
sinh là điểm P. Vì vậy, việc lựa chọn P phù hợp là rất quan trọng.
Để đảm bảo việc chọn điểm thích hợp ta hãy chọn đường cong elliptic
của chúng ta và trường hữu hạn sao cho số N các điểm của đường cong là một
số nguyên tố. Nếu chọn được như vậy thì mọi điểm B ≠ 0 đều là phần tử sinh.
Phan Thị Thu Hiền
http://slide pdf.c om/re a de r/full/e lliptic
- 20 -
Lớp CT702
20/33
- Xem thêm -