Đồ á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ó.
Đồ á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”.
Đồ á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
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a như sau:
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a =
0, , 0 (mod )
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
a ≡ a(p-1)/2 (mod p) .
Legendre Symbol thoả mãn các tính chất sau:
1. ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a chỉ phụ thuộc vào đồng dư của a theo mod p.
2. ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
ab = ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
b;
3. b nguyên tố với p thì ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
ab2
= ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a;
4. ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
1 =1 và ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛−p
1 = (-1)(p-1)/2.
Định lý 1:
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
2 = (-1)(p 2– 1)/8 = 1 1 mod 8
1 3 mod 8
p
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 đó:
Định lý 2
Nếu a ≡ b mod p → ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
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
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
q = (-1)(p-1)(q-1)/4 . ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
q
p =
3mod4
pneu p q
q
ptrong truong hop khac
q
⎧⎛⎞
−≡≡
⎪⎜⎟
⎪⎝ ⎠
⎨⎛⎞
⎪⎜⎟
⎪⎝⎠
⎩
Đồ á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
∈
Q401?
Và tìm x? với x2 ≡ a mod 401
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a = ⎟
⎠
⎞
⎜
⎝
⎛
401
186 = ⎟
⎠
⎞
⎜
⎝
⎛
401
93.2 = ⎟
⎠
⎞
⎜
⎝
⎛
401
2⎟
⎠
⎞
⎜
⎝
⎛
401
93 .
Theo định lý 3:
Vì 401 ≡ 1 mod 8 ⇒ ⎟
⎠
⎞
⎜
⎝
⎛
401
2 =1 vậy
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a = ⎟
⎠
⎞
⎜
⎝
⎛
401
186 = ⎟
⎠
⎞
⎜
⎝
⎛
401
93 = ⎟
⎠
⎞
⎜
⎝
⎛⋅
401
313 = ⎟
⎠
⎞
⎜
⎝
⎛
401
3⎟
⎠
⎞
⎜
⎝
⎛
401
31
Nhưng ⎟
⎠
⎞
⎜
⎝
⎛
401
3 = (-1) 4
400.2
. ⎟
⎠
⎞
⎜
⎝
⎛
3
401 = ⎟
⎠
⎞
⎜
⎝
⎛
3
2 = -1 (định lý 1)
Và ⎟
⎠
⎞
⎜
⎝
⎛
401
31 = (-1) 4
400.30
⎟
⎠
⎞
⎜
⎝
⎛
3
401 = ⎟
⎠
⎞
⎜
⎝
⎛
3
401 = ⎟
⎠
⎞
⎜
⎝
⎛
31
29 = ⎟
⎠
⎞
⎜
⎝
⎛
29
2 =-1.
Vậy ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a = 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 ⎟
⎠
⎞
⎜
⎝
⎛
401
3 = -1).
Ta có p-1 = 400 = 24. ⎟
⎠
⎞
⎜
⎝
⎛
3
25 → b = nS = 18625 mod 401 = 286 mod 401.
Còn r = a 2
1+S
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
⇒ Căn bậc 2 của 186 là b5r mod 401 = 304