Đồ á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
Đồ á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:
x
2
≡ 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 Q
n
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.
1, , ;
1, , .
khi a p
khi a Qp
khi a Qp
≡
⎧
⎪
∈
⎨
⎪
−∉
⎩
Chú ý:
+ Từ định nghĩa suy ra a là thặng dư bậc hai mod p khi và chỉ khi
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a
= 1
+ Theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0 ta có:
Đồ án tốt nghiệp Hệ mật đường cong elliptic
⎠
⎞
⎜
⎜
⎝
⎛
p
ab
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
b
;
⎜
⎝
⎛
p
1
=1 và
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
p
1
= (-1)
(p-1)/2
.
Định lý 1:
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
b
Định lý 3
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
2
= 1 p
≡ 1 mod 8 hay p ≡ 7 mod 8
-1 p ≡ 3 mod 8 hay p ≡ 5 mod 8
⎟
⎧
⎛⎞
−≡≡
⎪
⎜⎟
⎪⎝ ⎠
⎨
⎛⎞
⎪
⎜⎟
⎪
⎝⎠
⎩Đồ án tốt nghiệp Hệ mật đường cong elliptic
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
∈
Q
401
?
Và tìm x? với x
2
≡ a mod 401
⎟
⎟
⎠
⎞
⎛
401
2
⎟
⎠
⎞
⎜
⎝
⎛
401
93
.
Theo định lý 3:
Vì 401
≡ 1 mod 8
⇒
⎟
⎠
⎞
⎜
⎝
⎛
401
2
=1 vậy
⎟
⎟
⎠
⎞
⎜
⋅
401
313
=
⎟
⎠
⎞
⎜
⎝
⎛
401
3
⎟
⎠
⎞
⎜
⎝
⎛
401
31
Nhưng
⎟
⎠
⎞
⎜
⎝
⎛
401
3
31
= (-1)
4
400.30
⎟
⎠
⎞
⎜
⎝
⎛
3
401
=
⎟
⎠
⎞
⎜
⎝
⎛
3
401
=
⎟
⎠
⎞
⎜
⎝
⎛
31
401 (như trên ta đã chứng minh được
⎟
⎠
⎞
⎜
⎝
⎛
401
3
= -1).
Ta có p-1 = 400 = 2
4
.
⎟
⎠
⎞
⎜
⎝
⎛
3
25
→ b = n
S
= 186
25
mod 401 = 286 mod 401.
Còn r = a
2
1+S
mod 401 = 186 mod 401 = 103.
theo, ta có (br)
2
/a = -1 ⇒ luỹ thừa bậc 2 của nó là 1 ⇒ đặt j
1
=0, cứ thế j
2
=1(2 = K =
α
) Vậy j =5 vì 1.2
2
+1 = 5
⇒ Căn bậc 2 của 186 là b
5
r mod 401 = 304
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Thử lại 304
2
≡ 186 mod 401?
Ta có 304
2
= 92416 vậy 304
2
= 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
⎛⎞
⎜⎟
⎝⎠
………
ak
k
a
p
⎛⎞
⎜⎟
⎝⎠
với a
1
, a
2
, … , a
k
≥ 1
P
1
, P
2
, ….P
k
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, 1(mod 8)
13(mod8)
khi a
khi a
≡±
⎧
⎨
−≡±
⎩
3.
12
mm
n
⎛⎞
⎜⎟
⎝⎠
=
1
m
n
⎛⎞
⎜⎟
⎝⎠
2
m
n
⎛⎞
⎝⎠
⎩
Đồ á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ó:
a
1
2
1
+
−p
≡ a (mod p),
a
)1(2 +m
≡ 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 =
∈
phần tử a
∈
G kà số nguyên dương nhỏ nhất m thoả mãn a
m
= 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
Đồ á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à g
n
= 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 ∈ F luôn luôn tồn tại một số nguyên dương n sao cho: n
aa++
64748
= 0
Định nghĩa
Đồ á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
4434421
p
1 11 +++
= 0 được gọi là đặc số của K.
(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 (p
n
) 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à F
q
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 đó F
q
(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
∈ F
q
nếu cấp của g là q-1 tức là {g
1
, g
2
,……, g
q-1
= 1}
= F
*
q
Đồ á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
2
+a
4
x + a
6 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 −
3
2
a
, Y→ Y −
2
31
aXa
+
Khi đó phương trình Weierstrass có dạng:
X
3
+ aX +b.
Vậy trong trường F
p
(*) trở thành:
Y
2
= X
+ ax +b, x, y
∈
K } ∪ {O} .
Với a, b
∈ K cho trước sao cho 4a
3
+ 27b
2
≠ 0 theo mod p.
Nếu K là trường đặc số 2 thì ta định nghĩa:
S = { (x, y) : y
-2
+ y= x
3
+ ax +b } ∪ {O} (2)
Nếu K là trường đặc số 3 thì ta định nghĩa:
S = { (x, y) : y
2
= x
3
+ ax +bx + c } ∪ {O} (3)
* Tính chất của đường cong elliptic:
• Nếu hai điểm P
1
(x
1
, y
1
) và P
2
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
Đồ á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 = p
r
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
= 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 +
∑
∈Fqx
(1+
λ
(x
3
+ ax + b)) = q + 1 +
∑
∈Fqx
(1+
λ
(x
3
+ ax + b)) (6)
Ta hy vọng rằng
λ
( x
3
+ 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
∑
∈Fqx
(x
3
+ ax + b) bị chặn bởi 2
×Z
p
thoả mãn phương trình:
Y
2
= X
3
+ 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= (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
λ
= (y
2
– y
1
) / (x
2
– x
1
), khi P
≠ Q( nếu x
1
= x
2
th ì
λ
là hệ số góc đường
thẳng qua P và Q) (*)
(3x
2
+ a) / 2 y
1
, khi P = Q (
λ
là đạo hàm của đường cong tại P)
(**)
V
ậy nếu P ≠ Q tức là x
1
≠ x
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
−
12
12
xx
yy
( x
1
– x
3
) - y
1
N ếu P =Q Đồ án tốt nghiệp Hệ mật đường cong elliptic
x
3
=
2
⎛
+
1
1
2
2
3
y
ax
( x
1
– x
3
) - y
1
Hình 2.6.1 Phép cộng trên đường cong Elliptic Chú ý rằng các điểm (x
3
, y
3
), (x
3
, -y
3
) cũng nằm trên đường cong E và xét về
Đồ á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 y
2
= x
3
– 36x
Lấy P =(-3, 9), Q = (-2, 8). Hãy tìm P + Q và 2P?
25
,
8
35
−
)
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 F
q
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à F
q
.
Định lý Hasse
Đồ á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 đó:
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
q
n
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
F
q
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 (F
2
r
) có thể nhanh hơn
Đồ á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 2
r
, nhưng khi r
tăng thì tính # E (F
2
∈
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.
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
F
2
r
. 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ỡ 2
160
.
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ừ F
q
là x, y, a
2. Tính b = y
2
– (x
3
Đồ án tốt nghiệp Hệ mật đường cong elliptic CHƯƠNG 3
HỆ MẬT ĐƯỜNG CONG ELLIPTIC
trước, và Menezes và Vanstone đã đưa ra phương pháp thực thi trên các thiết
bị cứng có thể cài thiện các tính toán trên elliptic trên một trường hữu hạn.
Những năm 1997, 1998 việc tìm ra các hệ mật mã trên các đường cong
Elliptic ngày càng thu hút nhiều sự chú ý và một số thuật toán đã được đưa
thành chuẩn trong các RFC.
3.2. Nhúng bản rõ lên đường cong
Nhúng một 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 mà nhờ đó chúng ta 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à
imbedding và mask.
4.2.1. Imbedding
Muốn mã hoá bản rõ m trên một đường cong elliptic cho trước được
định nghĩa trên trường F
q
trước hết ta phải tìm cách nhúng nó lên E. Giả sử m
được coi là một số nguyên dương nào đó. Bản rõ m được ứng với điểm P
m
trên E.
Trước khi thực hiện “nhúng” điểm m lên E ta cần lưu ý:
1. Sau khi nhận được bản mã, người ta nhận đích thực phải có thể giải được
bản mã một cách dễ dàng.
2. Không có một thuật toán tất định với thời gian đa thức (trong log q) để biết
được một số lớn các điểm trên đường cong elliptic tuỳ ý trên E cả trường F
q
.
Tuy nhiên lại tồn tại một thuật toán xác suất mà đối với nó xác suất sai là rất
bé.
3. Việc tạo ra các điểm ngẫu nhiên của E là không đủ để mã hoá một số lượng
{m
κ
+ j} 1≤ j ≤
κ
Ta lập một ánh xạ 1- 1 tương ứng giữa các số nguyên trên với tập hợp các
phần tử của F
q
. Ví dụ có thể viết một số nguyên như là một số nguyên cơ số p
có độ dài r và coi r như là một phần tử của Z/pZ , là hệ số của một đa thức
cấp r – 1 tương ứng với một phần tử của F
q
. Nghĩa là số nguyên (a
r-1 ,
a
r-
2,…….
a
1,
a
0
)p đặt tương ứng với đa thức
∑
−
=
1
0
r
i
a
đến khi tìm được một số x sao cho f(x) là một bình phương cho đến khi j nhận
giá trị lớn
κ
, có thể khôi phục lại được m từ điểm (x, y) bởi công thức:
m= [(x -1)/
κ
]
Trong đ ó x là một số nguyên ứng với giá trị x bởi phép tương ứng 1-1
giữa các số nguyên và các phần tử của F
q
. Vì f(x) là một bình phương với xấp
xỉ 50% của mọi x cho nên chỉ có khoảng xác suất 2
-
κ
để cho phương pháp
này là sai.
Đồ án tốt nghiệp Hệ mật đường cong elliptic
3.3. Logarit rời rạc trên đường cong Elliptic( Discrete logarithm on
Elliptic)
Định nghĩa:
Nếu E là đường cong Elliptic trên trường F
q
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 x
∈
Z sao cho xB = P (nếu số x như vậy tồn
tại)
) mà
được coi là khoá đối với hệ mã truyền thống của họ. Cụ thể như sau:
Trước hết A, B chọn công khai một điểm B
∈
E. B đóng vai trò như là
phần tử sinh g trong trường hữu hạn của hệ thống Diifie-Hellman. Chúng ta
muốn có một nhóm con được sinh ra bởi B là lớn, tốt nhất là có cùng cấp như
Đồ án tốt nghiệp Hệ mật đường cong elliptic
E. Bây giờ giả sử B là công khai và cố định trên E mà cấp của nó là đủ lớn
(chẳng hạn hoặc là N hoặc là một nhân tử lớn của N).
Để tạo ra khoá, trước hết A chọn ngẫu nhiên một số nguyên a có cấp q
(nó xấp xỉ như số N). Số a được giữ bí mật. Trên cơ sở đó, A tính aB
∈
E, aB
là công khai. Đến lượt B cũng làm như vậy, anh ta chọn ngẫu nhiên số b và
tính bB
∈ E, bB cũng được công khai. Khoá bí mật mà chỉ có hai người A, B
mới có đó là: P =abB
∈ E. Người thứ ba bất kỳ không thể suy ra abB từ aB và
bB nếu không giải bài toán logarit rời rạc trên E của trường F
p
r
.
3.5. Hệ mât mã hoá Elgamal trên đường cong Elliptic
Hệ Elgamal làm việc với nhóm Cyclic hữu hạn. Năm 1978, Kobliz đã
đưa một hệ trên ECC dựa trên hệ Elgamal.
Để xây dựng hệ mã hoá dựa trên đường cong elliptic ta chọn đường
cong E(a, b) và một điểm G trên đường cong làm điểm cơ sở. Mỗi người dùng
A một khoá bí mật n
= { k * G, P
m
+ k * P
B
}, người dùng B thực
hiện tính như sau:
P
m
+ k * P
B
- n
B
* k * G = P
m
+ k * P
B
– k * n
B
* G = P
m
+ k * P
B
- k * P
B
=
P
m
Đồ án tốt nghiệp Hệ mật đường cong elliptic
Đồ án tốt nghiệp Hệ mật đường cong elliptic CHƯƠNG 4
MỘT VÀI ỨNG DỤNG
4.1. Lược đồ chữ ký số trên đường cong elliptic (Elliptic Curve Signature
Algorithm ) - ECDSA
4.1.1. Lược đồ ký ECDSA
Sơ đồ chữ ký ECDSA được xây dựng tương tự như sơ đồ chữ ký ElGamal
tuy nhiên các thuật toán ký và thuật toán kiểm thử được xây dựng dựa
trên đường cong Elliptic.
Để thiết lập sơ đồ chữ ký ECDSA, cần xác định các tham số: lựa chọn
đường cong E trên trường hữu hạn F
q
xác định điểm cơ sở G = (x
G,
y
G
).
4. Bậc n của điểm G với n> 2
160
và n > 4 q .
Sinh khoá
1. Chọn số ngẫu nhiên d trong khoảng [2, n-1 ] làm khoá bí mật
2. Tính Q = dG làm khoá công khai.
Thuật toán ký trên bản rõ m
Người dùng A ký lên thông điệp m theo các bước sau:
1. Chọn một số ngẫu nhiên k, 2
1
−
≤
≤
nk
2. Tính kG = (x
1
, y
1
).
3. Tính r = x
1
mod n. Nếu r =0, quay lại bước 1.
Copyright: Tài liệu đại học ©