Xem mẫu
-
Luận văn
Hệ mật đường cong
elliptic
..........., tháng ... năm ........
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
MỤC LỤC
MỤC LỤC ........................................................................................................ 1
LỜI CẢM ƠN ................................................................................................... 2
MỞ ĐẦU ........................................................................................................... 3
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 Lớp CT702
-1-
- Đồ á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 Lớp CT702
-2-
- Đồ á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 Lớp CT702
-3-
- Đồ á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 Lớp CT702
-4-
- Đồ á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(p-
1)/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
0, khi, a 0 (mod p)
a
= 1, khi, a Qp;
p
1, khi, a Qp.
Chú ý:
a
+ Từ định nghĩa suy ra a là thặng dƣ bậc hai mod p khi và chỉ khi = 1
p
+ Theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0 ta có:
Phan Thị Thu Hiền Lớp CT702
-5-
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
a (p-1)/2
≡a (mod p) .
p
Legendre Symbol thoả mãn các tính chất sau:
a
1. chỉ phụ thuộc vào đồng dƣ của a theo mod p.
p
ab
ab
= ;
2.
p p
p
ab 2 a
3. b nguyên tố với p thì = ;
p
p
1 1
4. =1 và = (-1)(p-1)/2.
p p
Định lý 1:
1 p 1 mod 8
2 2
(p – 1)/8
= (-1)
=
p
1 p 3 mod 8
Đị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 đó:
p
neu p q 3 mod 4
q p q
= (-1)(p-1)(q-1)/4 . =
p q
p
q
trong truong hop khac
Định lý 2
a b
Nếu a ≡ b mod p → =
p
p
Định lý 3
2
= 1 p ≡ 1 mod 8 hay p ≡ 7 mod 8
p
-1 p ≡ 3 mod 8 hay p ≡ 5 mod 8
Ví dụ: Cho a = 186, p= 401 (p là số nguyên)
Phan Thị Thu Hiền Lớp CT702
-6-
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
Tìm a có là thặng dƣ bậc hai không nghĩa là a Q401?
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:
Vì 401 ≡ 1 mod 8
2
=1 vậy
401
a 3 31 3 31
186 93
= = = =
p
401 401 401 401 401
2.400
3 401 2
Nhƣng = = -1 (định lý 1)
= (-1) 4 .
401 3 3
30.400
Và
31
= (-1) 4
401 401 29 2
= = = =-1.
401 3 3 31 29
a
Vậy = 1.(-1).(-1) = 1 Do đó a Q401
p
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
3
= -1).
401
Ta có p-1 = 400 = 24. → b = nS = 18625 mod 401 = 286 mod 401.
25
3
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. r2 = 1032 . 235 mod 401 = 98 vì -2 = 4-2 =2 do đó ta nâng
luỹ thừa 22 = 4 = của 98 và có 984 ≡ -1 mod 401 = -1 (984 mod 401 = (982
mod 401)( 982 mod 401) mod 401 = 3812 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
5
Căn bậc 2 của 186 là b r mod 401 = 304
Thử lại 3042 ≡ 186 mod 401?
Phan Thị Thu Hiền Lớp CT702
-7-
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
Ta có 3042 = 92416 vậy 3042 = 186 = 92230 ≡ 0 mod 401 x= 304
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ì
ak
a1 a2
a
a a
a
= ………
n p1 p2 pk
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ì 1 = 2 .
m m
n n
1, khi a 1(mod8)
2. =
2
1 khi a 3(mod8)
n
3. 1 2 = 1 2 .
mm m m
n nn
4. Nếu m và n đều là số là thì:
n
m khi m 3 mod 4 & n 3mod 4
m
=
n n khi m 1mod 4 n 1mod 4
m
Bây giờ xét việc giải phƣơng trình đồng dƣ bậc hai:
x2 ≡ a (mod n) (*)
Phan Thị Thu Hiền Lớp CT702
-8-
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
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ố
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ó:
p 1
1
≡ a (mod p),
a 2
a 2( m1) ≡ 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:
1. Tính kết hợp: (a * b) * c = a * (b * c) với mọi a, b, c G.
2. 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
G (e đƣợc gọi là phần tử trung hoà).
3. Phần tử nghịch đảo: với mỗi a G, tồn tại một phần tử b G thoả 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
Phan Thị Thu Hiền Lớp CT702
-9-
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
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ử * ): n N mà gn = x
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 = { p, q là số nguyên: (p, q) = 1} trên Q có 2 phép toán cộng
q
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 Zp.
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:
n
a ....... a = 0
Định nghĩa
Phan Thị Thu Hiền Lớp CT702
- 10 -
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
Trƣờng K với phần tử đơn vị nhân là 1. Với p dƣơng nhỏ nhất thoả
mãn 1 1 = 0 đƣợc gọi là đặc số của K.
1........
p
(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 Fq khi đó Fq
khi đó Fq chứa trƣờng nguyên tố Fp = 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 Fp. Lấy f ký hiệu là chiều
của nó coi Fp 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 Fp 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 = pf 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à {g1, g2,……, gq-1 = 1}
= F*q
Phan Thị Thu Hiền Lớp CT702
- 11 -
- Đồ á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 Fp (p nguyên tố, p>3 ) với
công thức biến đổi nhƣ sau:
a1X a3
a2
X→X − , Y→ Y −
3 2
Khi đó phƣơng trình Weierstrass có dạng:
X3 + aX +b.
Vậy trong trƣờng Fp (*) 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 K sao cho (1) không có các nghiệm bội
Phan Thị Thu Hiền Lớp CT702
- 12 -
- Đồ á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) : y2 = 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 P1 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 Lớp CT702
- 13 -
- Đồ á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 Fq 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 Fq. 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 Fq, nghĩa là điểm vô cùng với 2q cặp (x, y) trong đó x, y Fq 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 x3 + 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 Fq (lấy (0) = 0).
x
Ví dụ: Nếu q = p là 1 số nguyên tố thì (x) =( ) là ký hiệu Legedre
p
Symbol). Do đó trong tất cả mọi trƣờng hợp số các nghiệm y Fq 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+ (x3 + ax + b)) = q + 1 + (1+ (x3 + ax + b)) (6)
1+
xFq xFq
Ta hy vọng rằng ( 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 q đó chính là định lý Hasses đƣợc phát triển
xFq
nhƣ sau:
Định lý: Gọi N là số các điểm trên đƣờng cong elliptic đƣợc định nghĩa trên
Fq. Khi đó | N−(q + 1) | ≤ 2 q
Phan Thị Thu Hiền Lớp CT702
- 14 -
- Đồ á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 = X3 + aX + b trên Zp đƣợc định nghĩa là tập hợp tất
cả các điểm (x, y) Zp Zp 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 đó
x3 = 2 - x1 – x2 , y3 = (x1 – x3 ) –y1,
Với
= (y2 – y1 ) / (x2 – x1), khi P ≠ Q( nếu x1 = 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 = 2 1 - x1 – x2 (*)
x x
2 1
y 2 y1
y3 = ( x1 – x3) - y1
x2 x1
N ếu P =Q
Phan Thị Thu Hiền Lớp CT702
- 15 -
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
3x a
2
x3 = 1 – 2x2 (**)
2y
1
3x 2 a
y3 = 1 ( x1 – x3) - y1
2 y1
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 Lớp CT702
- 16 -
- Đồ á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 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ạ 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ó:
(8 9) 2
x3 = +3 + 2 = 1+ 3 +2 = 6.
23
89
y3 = -9
(-3-6) = -9 + (-1)(-9) =0.
2 3
Vậy P +Q = (6, 0). Bây giờ ta tính 2P áp dụng (**) ta có: x1= -3, y1 = 9
35 25 35
25
và do đó y3= . Vậy 2P = ( ,
x3 = )
4 8 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 Lớp CT702
- 17 -
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
N là số điểm của E trên trƣờng Fq (trƣờng hữu hạn q phần tử). Khi đó:
|N – (q +1)| ≤ 2 q .Từ định lý Hasse suy ra #E(Fq) = q +1 – t trong đó |t| ≤ 2
q.
Đị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 F2r
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 F2r có thể bị tấn công bởi
MOV, trong khi các đƣờng cong trên trƣờng Fp (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ố Fp và trên trƣờng Fqn 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
thƣớc và đặc số của trƣờng K. Ví dụ với r nhỏ, tính # E (F2r) có thể nhanh hơn
Phan Thị Thu Hiền Lớp CT702
- 18 -
- Đồ án tốt nghiệp Hệ mật đường cong elliptic
một chút so với tính # E(Fp), trong đó p lớn hơn đáng kể so với 2r, nhƣng khi r
tăng thì tính # E (F2r) mất nhiều thời gian hơn tính # E (Fp).
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 y2 +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. Tính b = y2 – (x3 + ax)
Phan Thị Thu Hiền Lớp CT702
- 19 -
nguon tai.lieu . vn