Luận văn Nghiên cứu, tìm hiểu và trình bày về chữ ký số trên đường cong elliptic, ứng dụng của đường cong elliptic trong hệ thống bỏ phiếu điện tử và hệ thống tiền điện tử
TRƯỜNG………………………
KHOA……………………………..
LUẬN VĂN TỐT NGHIỆP
NGHIÊN CỨU, TÌM HIỂU VÀ TRÌNH BÀY VỀ CHỮ KÝ SỐ TRÊN
ĐƯỜNG CONG Elliptic, ỨNG DỤNG CỦA ĐƯỜNG CONG Elliptic TRONG
HỆ THỐNG BỎ PHIẾU ĐIỆN TỬ VÀ HỆ THỐNG TIỀN ĐIỆN TỬ.
1
LỜI CẢM ƠN
Lời đầu tiên, em xin được gửi lời cảm ơn sâu sắc tới PGS.TS. Trịnh Nhật
Tiến, người thầy đã giúp đỡ em trong suốt quá trình làm khóa luận, đồng thời cũng
là người thầy đã hướng dẫn em những bước đi đầu tiên để khám phá một lĩnh vực
đầy bí ẩn và thách thức – lĩnh vực an toàn và bảo mật dữ liệu.
Em xin được cảm ơn các thầy, các cô đã giảng dạy em trong suốt bốn năm
qua. Những kiến thức mà các thầy, các cô đã dạy sẽ mãi là hành trang giúp em vững
bước trong tương lai .
Em cũng xin được cảm ơn tập thể lớp K50CC, một tập thể lớp đoàn kết với
những người bạn không chỉ học giỏi mà còn luôn nhiệt tình giúp đỡ mọi người,
những người bạn đã giúp đỡ em trong suốt bốn năm học tập trên giảng đường Đại
học.
Cuối cùng, em xin được gửi lời cảm ơn sâu sắc tới gia đình em, những người
luôn kịp thời động viên, khích lệ em, giúp đỡ em vượt qua những khó khăn trong
cuộc sống.
Hà nội, tháng 05 năm 2009
Sinh viên
Nguyễn Minh Hải
2
TÓM TẮT NỘI DUNG KHÓA LUẬN
Khóa luận là sự nghiên cứu, tìm hiểu và trình bày về chữ ký số trên đường
cong Elliptic, ứng dụng của đường cong Elliptic trong Hệ thống bỏ phiếu điện tử và
Hệ thống tiền điện tử. Khóa luận được trình bày thành bốn chương với nội dung
như sau:
Chương 1 : Tóm tắt các khái niệm cơ bản trong số học và trong đại số học.
Chương 2 : Trình bày về khái niệm đường cong Elliptic, các dạng đường cong
và các phép toán trên đường cong Elliptic.
Chương 3 : Trình bày một số chữ ký số trên đường cong Elliptic và phương
pháp tấn công hệ mã hóa đường cong Elliptic.
Chương 4 : Trình bày ứng dụng của đường cong Elliptic trong Hệ thống bỏ
phiếu điện tử và Hệ thống tiền điện tử.
3
CÁC KÝ HIỆU VIẾT TẮT
Tom
Người gửi tin hoặc người thực hiện việc ký
Ban đăng ký
BĐK
BKP
Ban kiểm phiếu
Jerry
Người nhận tin hoặc người yêu cầu ký
Đường cong Elliptic (Elliptic Curve)
Mã hóa đường cong Elliptic (Elliptic Curve Cryptosystem)
Thuật toán ký trên EC
EC
ECC
ECDSA
EDLP
E-Voting
gcd
Bài toán Logarith rời rạc trên EC
Bỏ phiếu điện tử (Electronic Voting)
Ước số chung lớn nhất (Greatest Common Divisor)
Trường hữu hạn (Galois Field)
GF
IEEE
IETF
IFP
Institute of Electrical and Electronics Engineers
Internet Engineer Task Force
Bài toán ước số nguyên (Integer Factorization Problem)
Bội số chung nhỏ nhất (Least Common Multiple)
Phương pháp tấn công Menezes – Okamoto - Vanstone
National Institute of Standards
lcm
MOV
NIST
RFC
Request For Comments
RIPEMD-160
RSA
Hàm băm 160 bit
Hệ mã hóa khóa công khai Rivest – Shamir – Adleman
Hàm cửa sập một chiều (Trapdoor One-way Function)
TOF
4
CÁC KÝ HIỆU TOÁN HỌC
< g >
#E
C
Nhóm cyclic được sinh bởi g
Số phần tử của đường cong elliptic
Tập các bản mã có thể
dK
Thuật toán giải mã
E
Đường cong elliptic
eK
Thuật toán mã hóa
F*
Fq
Nhóm nhân trên trường F
Trường hữu hạn với q phần tử
Điểm cơ sở của E
G
K
Không gian các khóa
O
Phần tử trung hòa của E
sigK
verK
Zp
Thuật toán ký số
Thuật toán kiểm tra chữ ký
Vành các số nguyên dương p
Hàm phi Euler các số nguyên trong Zn nguyên tố cùng nhau với n.
φ(n)
5
DANH MỤC CÁC HÌNH VẼ TRONG KHÓA LUẬN
Hình 1: Một ví dụ về đường cong Elliptic....................................... Error! Bookmark not defined.
Hình 2: Điểm ở vô cực................................................................... Error! Bookmark not defined.
Hình 3: Phép cộng trên đường cong elliptic.................................... Error! Bookmark not defined.
Hình 4: Phép nhân đôi trên đường cong elliptic.............................. Error! Bookmark not defined.
6
MỤC LỤC
LỜI MỞ ĐẦU ..............................................................................................................................1
Chương 1 : CÁC KHÁI NIỆM CƠ BẢN ..................................................................................11
1.1. KHÁI NIỆM TRONG SỐ HỌC ..........................................................................................11
1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất .......................................................................11
1.1.2. Quan hệ đồng dư ................................................................................................................12
1.1.3. Số nguyên tố .....................................................................................................................13
1.2. KHÁI NIỆM TRONG ĐẠI SỐ ............................................................................................15
1.2.1. Nhóm................................................................................................................................15
1.2.2. Vành ..................................................................................................................................17
1.2.3. Trường..............................................................................................................................18
1.2.4. Không gian vector ............................................................................................................22
Chương 2. ĐƯỜNG CONG ELLIPTIC....................................................................................23
2.1. CÔNG THỨC WEIERSTRASSE VÀ ĐƯỜNG CONG ELLIPTIC.......................................24
2.2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG R2 .................................................................24
2.2.1. Phép cộng ..........................................................................................................................25
2.2.2. Phép nhân đôi.....................................................................................................................28
2.3. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN ...................................................29
2.3.1. Đường cong elliptic trên trường Fp (p là số nguyên tố)........................................................29
m
2.3.2. Đường cong elliptic trên trường F2 ....................................................................................30
2.3.3. Các phép toán trên đường cong elliptic trong hệ tọa độ Affine ............................................30
2.3.4. Các phép toán trên đường cong elliptic trong hệ tọa độ chiếu..............................................32
2.3.5. Chuyển đổi giữa hệ tọa độ Affine và hệ tọa độ chiếu ..........................................................33
2.3.6. Các phép toán đường cong trong hệ tọa độ chiếu ................................................................33
2.3.6. Phép nhân đường cong .......................................................................................................34
2.4 BÀI TOÁN LOGARIT RỜI RẠC TRÊN ĐƯỜNG CONG ELLIPTIC...................................36
Chương 3. CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTC....................................................37
3.1. CHỮ KÝ SỐ........................................................................................................................37
3.1.1. Khái niệm chữ ký số.........................................................................................................37
3.1.2. Sơ đồ chữ ký số................................................................................................................38
3.2. MỘT SỐ SƠ ĐỒ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC......................................41
3.2.1. Sơ đồ chữ ký ECDSA......................................................................................................41
3.2.2. Sơ đồ chữ ký Nyberg- Rueppel........................................................................................43
3.2.3. Sơ đồ chữ ký mù Harn trên EC .........................................................................................44
7
3.2.4. Sơ đồ đa chữ ký mù của Harn trên EC .............................................................................47
3.3. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG HỆ ECC ................................................................49
3.3.1. Phương pháp tấn công “baby - step giant - step” ...............................................................49
3.3.2. Phương pháp tấn công MOV ............................................................................................50
Chương 4 . ỨNG DỤNG CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC ..........................53
4.1.ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ.........................................................................54
4.1.1. Quy trình bỏ phiếu điện tử................................................................................................54
4.1.2. Sử dụng ECC trong bỏ phiếu điện tử.................................................................................55
4.2. ỨNG DỤNG TRONG HỆ THỐNG TIỀN ĐIỆN TỬ ..........................................................57
4.2.1. Tạo tiền ecash ...................................................................................................................57
4.2.2 Tiêu tiền ecash ..................................................................................................................58
4.2.3 Đổi tiền ..............................................................................................................................58
4.2.4 Kết thúc giao dịch .............................................................................................................58
KẾT LUẬN ................................................................................................................................59
TÀI LIỆU THAM KHẢO .........................................................................................................61
8
LỜI MỞ ĐẦU
Mục tiêu cơ bản của mật mã học là đảm bảo tính bí mật. Nó cho phép 2 đối tác
trao đổi thông tin với nhau một cách an toàn trên những kênh truyền thông công
khai. Hệ mật mã khóa bí mật có thể định nghĩa như sau: Giả sử ký hiệu M là tập tất
cả các bản rõ có thể. C là tập tất cả các bản mã có thể. K là tập các khóa có thể. Hệ
mật mã khóa bí mật gồm 2 hàm: ek : M C , dk : C M ,
sao cho
k K
dk (ek (m)) m với mọi
và
. Trong hệ mật mã này, người gửi (giả sử là
k K
m M
Tom)và người nhận (Jerry) cùng thỏa thuận một khóa bí mật, bằng cách gặp mặt
nhau trực tiếp hoặc nhờ một trung tâm tin cậy phân phối khóa. Nếu Tom muốn gửi
cho Jerry một thông điệp
, cô ấy sẽ gửi bản mã c e (m) cho Jerry. Jerry sẽ
m M
k
khôi phục bản rõ m bằng việc dùng hàm giải mã dk . Hệ mật mã khóa bí mật phải
đảm bảo rằng các hàm ek và dk phải dễ áp dụng nhưng vẫn an toàn trước kẻ tấn
công, khi có bản mã c vẫn khó tính được m (hoặc khóa k). Dù hệ mật mã khóa bí
mật vẫn đang được dùng trong nhiều ứng dụng, nhưng vẫn còn một số nhược điểm
như vấn đề phân phối khóa, vấn đề quản lý khóa và nó không hỗ trợ việc tạo chữ ký
điện tử.
Ý tưởng chính của các thuật toán khóa công khai là sử dụng 2 khóa khác nhau
cho 2 quá trình mã hóa và giải mã. Ý tưởng này được phát minh bởi Whitfield
Diffie và Martin Hellman (1976), độc lập với Ralph Merkle (1978). Từ đó, nhiều hệ
mật mã khóa công khai được đưa ra, nhưng hầu hết chúng đều hoặc không an toàn
hoặc không khả thi. Các thuật toán khóa công khai đều chậm hơn rất nhiều so với
các thuật toán khóa bí mật.
Thuật toán RSA chậm hơn 1000 lần so với các thuật toán khóa bí mật phổ
biến như DES khi triển khai trong các thiết bị phần cứng; và chậm hơn 100 lần
trong các phần mềm mã hóa khi mã hóa cùng một khối lượng dữ liệu như nhau. Tuy
nhiên, hệ mật mã khóa công khai có một ưu điểm nổi trội là cho phép tạo chữ ký
điện tử. Khóa riêng được người sở hữu giữ bí mật và nó được sử dụng để tạo chữ ký
điện tử hoặc để giải mã các thông điệp đã được mã hóa bằng khóa công khai. Khóa
công khai không cần thiết phải giữ bí mật do tính chất “khó tính được khóa riêng từ
khóa công khai” của cặp khóa. Vì vậy, người dùng có thể công bố khóa công khai
9
trên các kênh công cộng cho những ai muốn gửi thông tin cho họ hoặc xác minh
chữ ký của họ.
Trong lịch sử hơn 20 năm của mật mã khóa công khai, đã có nhiều bài toán
“khó” được đưa ra xem xét để ứng dụng cho các vấn đề mật mã học. Trong đó có 2
bài toán nổi bật nhất là bài toán logarith rời rạc trên trường hữu hạn và bài toán tìm
ước số nguyên tố. Năm 1985, Neal Koblitz và V.S.Miller đã độc lập nhau cùng đề
xuấtviệc sử dụng các đường cong elliptic cho các hệ mã hóa khóa công khai. Họ
không phát minh ra thuật toán mã hóa mới với các đường cong elliptic trên trường
hữu hạn, mà họ dùng những thuật toán đã có như Diffie – Hellman, sử dụng các
đường cong elliptic. Các đường cong Elliptic có thể dùng trong nhiều ứng dụng như
kiểm thử số nguyên tố hoặc bài toán tìm ước số nguyên tố. Các hệ mật mã trên
đường cong elliptic (ECC) được dự báo là sẽ phổ biến hơn RSA do khóa nhỏ gọn
hơn nhiều (khoảng 163 bit) so với RSA (1024 bit). Vì vậy, tốc độ mã hóa nhanh
hơn so với RSA. Như vậy ECC có thể được dùng trên các thiết bị cầm tay (có bộ
nhớ nhỏ, và tốc độ tính toán không cao) .
Việc thương mại hóa ECC đã được một số nơi thực hiện như công ty Certicom
và công ty RSA đã hỗ trợ mã hóa ECC trong các bộ công cụ phát triển. Tuy nhiên,
một vấn đề có thể ảnh hưởng đến sự chấp nhận ECC rộng rãi như một phần của cơ
sở hạ tầng khóa công khai là các kỹ thuật thực thi đường cong elliptic, thói quen,
các thuật toán, và các giao thức. ECC đòi hỏi các thủ tục toán học phức tạp trong
việc khởi tạo các đường cong. Các chuyên gia công nghệ thông tin vẫn chưa hiểu
thấu đáo để thiết kế các hệ thống bảo mật dựa trên mật mã học, trong khi hệ RSA
thì không quá phức tạp và khó hiểu.
10
Chương 1. CÁC KHÁI NIỆM CƠ BẢN
1.1. KHÁI NIỆM TRONG SỐ HỌC
1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất
a. Khái niệm
Cho hai số nguyên a và b, b ≠ 0. Nếu có một số nguyên q sao cho a = b*q, thì
ta nói rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ước của a và a là bội của b.
Số nguyên d được gọi là ước chung của các số nguyên a1, a2, …, an , nếu nó
là ước của tất cả các số đó.
Số nguyên m được gọi là bội chung của các số nguyên a1, a2, …, an , nếu nó
là bội của tất cả các số đó.
Một ước chung d >0 của các số nguyên a1, a2, …, an , trong đó mọi ước
chung của a1, a2, …, an đều là ước của d, thì d được gọi là ước chung lớn nhất
của a1, a2, …, an . Ký hiệu d = gcd (a1, a2, …, an) hay d = UCLN(a1, a2, …, an).
Nếu gcd(a1, a2, …, an) = 1,thì a1, a2, …, an được gọi là nguyên tố cùng nhau.
Một bội chung m >0 của các số nguyên a1, a2, …, an , trong đó mọi bội
chung của a1, a2, …, an đều là bội của m, thì m được goi là bội chung nhỏ nhất
của a1, a2, …, an . Ký hiệu m = lcm(a1, a2, …, an) hay m = BCNN(a1, a2, …, an).
b. Ví dụ
Cho a =12, b =15, gcd(12,15) = 3,
Hai số 8 và 13 là nguyên tố cùng nhau, vì gcd(8, 13) = 1.
c. Tính chất
lcm(12,15) = 60.
1. d = gcd(a1, a2, …, an) tồn tại x1, x2,…, xn sao cho: d = a1x1+a2x2+…+anxn
a1,a2,..an nguyên tố cùng nhautồn tại x1,x2,.. xn sao cho: 1 = a1x1+a2x2+…+anxn
2. d = gcd(a1, a2, …, an) gcd(a1/d, a2/d,…, an/d) =1.
3. m = lcm(a1, a2, …, an) gcd(m/a1, m/a2,…, m/an) =1.
4. gcd(m a1, m a2, …, m an) = m * gcd(a1, a2, …, an) (với m ≠ 0).
5. Nếu gcd(a, b) =1
thì lcm(a, b) = a * b
6. Nếu b>0, a = bq+r thì gcd(a,b) = gcd(b, r).
11
1.1.2. Quan hệ đồng dư
a. Khái niệm
Cho các số nguyên a, b, m (m > 0). Ta nói rằng a và b “đồng dư” với
nhau theo modulo m, nếu chia a và b cho m, ta nhận được cùng một số dư.
Ký hiệu: a ≡ b (mod m).
b. Ví dụ
17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, được cùng số dư là 2.
c. Tính chất
1. Quan hệ “đồng dư” là quan hệ tương đương trong Z:
Với mọi số nguyên dương m ta có:
a ≡ a (mod m) với mọi a Z;
(tính chất phản xạ).
a ≡ b (mod m) thì b ≡ a (mod m); (tính chất đối xứng).
a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m); (tính chất bắc cầu).
2. Tổng hay hiệu các “đồng dư ”:
(a+b) (mod n) [(a mod n) + (b mod n)] (mod n)
(a- b) (mod n) [(a mod n) - (b mod n)] (mod n)
Tổng quát:
Có thể cộng hoặc trừ từng vế nhiều đồng dư thức theo cùng một modulo m,
ta được một đồng dư thức theo cùng modulo m, tức là:
k
k
Nếu ai ≡ bi (mod m) , i = 1...k, thì
t a t b (mod m) với ti = ± 1.
i i i
i
i1
i1
3.. Tích các “đồng dư”:
(a* b) (mod n) [(a mod n) * (b mod n)] (mod n)
Tổng quát:
Có thể nhân từng vế nhiều đồng dư thức theo cùng một modulo m, ta được một
đồng dư thức theo cùng modulo m, tức là:
k
k
Nếu ai ≡ bi (mod m) với i=1..k, thì ta có:
a b (mod m)
i
i
i1
i1
12
1.1.3. Số nguyên tố
a. Khái niệm
Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước là 1 và chính nó.
b. Ví dụ
10 số nguyên tố lớn đã được tìm thấy :
rank Prime
Digits
Who when reference
232582657-1
1
2
3
4
5
6
7
8
9
10
9808358
9152052
7816230
7235733
6320430
4053946
3918990
2759677
2357207
2116617
G9
G9
G8
G7
G6
G5
2006 Mersenne 44??
2005 Mersenne 43??
2005 Mersenne 42??
2004 Mersenne 41??
2003 Mersenne 40??
2001 Mersenne 39
230402457-1
225964951-1
224036583-1
220996011-1
213466917-1
19249·213018586+1
27653·29167433+1
28433·27830457+1
33661·27031232+1
SB10 2007
SB8 2005
SB7 2004
SB11 2007
c. Định lý
1. Định lý: về số nguyên dương > 1.
Mọi số nguyên dương n > 1 đều có thể biểu diễn được duy nhất dưới dạng:
n1
n2
nk
.
...
, trong đó:
n =P1 P2 Pk
k, ni ( i =1,2,..,k) là các số tự nhiên, Pi là các số nguyên tố, từng đôi một khác nhau.
2. Định lý Mersenne.
Cho p = 2k -1, nếu p là số nguyên tố, thì k phải là số nguyên tố.
13
Chứng minh
Bằng phản chứng, giả sử k không là nguyên tố. Khi đó k = a.b với 1< a, b < k.
Như vậy :
p = 2k -1 = 2ab -1 = (2a)b -1= (2a -1).E
(Trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Niu-tơn).
Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử sai, hay k là số nguyên tố.
3. Hàm Euler:
Cho số nguyên dương n, số lượng các số nguyên dương bé hơn n và nguyên
tố cùng nhau với n được ký hiệu (n) và gọi là hàm Euler.
Nhận xét: Nếu p là số nguyên tố, thì (p) = p-1
Ví dụ:
Tập các số nguyên không âm nhỏ hơn 7 là Z 7 = {0, 1, 2, 3, 4, 5, 6, 7}.
Do 7 là số nguyên tố, nên Tập các số nguyên dương nhỏ hơn 7 và nguyên tố
cùng nhau với 7 là Z 7 * ={1, 2, 3, 4, 5, 6, 7}. Khi đó /Z/ = (p) = p-1 =8-1 = 7.
Định lý hàm Euler.
Nếu n là tích của hai số nguyên tố n = p.q, thì (n) = (p). (q) = (p-1).(q-1).
14
1.2. KHÁI NIỆM TRONG ĐẠI SỐ
1.2.1. Nhóm
a. Khái niệm
Nhóm là một bộ (G, *), trong đó G , * là phép toán hai ngôi trên G
thoả mãn ba tính chất sau:
+ Phép toán có tính kết hợp: (x*y)* z = x*(y*z) với mọi x, y, z G.
+ Có phần tử phần tử trung lập e G: x*e = e*x = x với mọi x G.
+ Với mọi x G, có phần tử nghịch đảo x’ G: x * x’ = x’ * x = e.
Cấp của nhóm G được hiểu là số phần tử của nhóm, ký hiệu là G .
Cấp của nhóm có thể là nếu G có vô hạn phần tử.
Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán.
Tính chất:
Nếu a * b = a * c, thì b = c.
Nếu a * c = b * c, thì a = b.
* Tập hợp các số nguyên Z cùng với phép cộng (+) thông thường là nhóm giáo
hoán, có phần tử đơn vị là số 0. Gọi là nhóm cộng các số nguyên.
* Tập Q* các số hữu tỷ khác 0 (hay tập R* các số thực khác 0), cùng với phép
nhân (*) thông thường là nhóm giao hoán. Gọi là nhóm nhân các số hữu tỷ (số
thực) khác 0.
* Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán.
b. Nhóm Cyclic
Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một trong
các phần tử của nó.
Tức là có phần tử g G mà với mỗi a G, đều tồn tại số n N để
g n = g * g * … * g = a. (Chú ý g * g * … * g là g * g với n lần).
Khi đó g được gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm
G. Nói cách khác: G được gọi là Nhóm Cyclic nếu tồn tại g G sao cho mọi
phần tử trong G đều là một luỹ thừa nguyên nào đó của g.
Nhóm (Z+ , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1.
15
Cho (G, *) là Nhóm Cyclic với phần tử sinh g. và phần tử trung lập e.
n
Nếu tồn tại số tự nhiên nhỏ nhất n mà g = e, thì G sẽ chỉ gồm có n
phần tử khác nhau: e, g, g2 , g3 , . . . , g n - 1 . Khi đó G được gọi là nhóm Cyclic
hữu hạn cấp n.
Nếu không tồn tại số tự nhiên n để g n = e, thì G có cấp .
*
c. Nhóm (Zn , phép nhân mod n)
* Kí hiệu Zn = 0, 1, 2, .. . , n-1 là tập các số nguyên không âm < n.
Zn và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1, pt trung lập e = 0.
(Zn , + ) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n.
*
* Kí hiệu Zn = x Zn , x là nguyên tố cùng nhau với n. Tức là x phải 0.
*
Zn được gọi là Tập thặng dư thu gọn theo mod n, có số phần tử là (n).
*
Zn với phép nhân mod n lập thành một nhóm (nhóm nhân), pt trung lập e = 1.
*
Tổng quát (Zn , phép nhân mod n ) không phải là nhóm Cyclic.
*
Nhóm nhân Zn là Cyclic chỉ khi n có dạng: 2,4, pk, hay 2pk với p là nguyên tố lẻ.
* Định lý Lagrange: Nếu G là nhóm cấp n và G, thì Cấp của là ước của n.
* Hệ quả: Giả sử Zn* có Cấp m, thì m là ước của (n).
* Định lý: Nếu p là số nguyên tố thì Z *p là nhóm Cyclic.
Nếu b Zn* thì b (n) 1 (mod n). Nếu p là số nguyên tố thì (p) = p-1.
Do đó với b Z *p (tức b nguyên tố với p), thì b(p) 1 (mod n), hay bp -1 1(mod n).
d. Phần tử nghịch đảo đối với phép nhân
* Định nghĩa
Cho a Zn , nếu tồn tại b Zn sao cho a b 1 (mod n), ta nói b là phần
tử nghịch đảo của a trong Zn và ký hiệu a -1.
Một phần tử có phần tử nghịch đảo, gọi là khả nghịch.
* Định lý: UCLN (a, n) = 1 Phần tử a Zn có phần tử nghịch đảo.
Chứng minh
Nếu a a-1 ≡ 1 (mod n) thì a a-1 = 1 + kn ↔ a a-1 - kn = 1 → (a, n) =1.
Nếu (a, n) = 1, ta có a a-1 + kn = 1 → a a-1 = 1+kn, do đó a a-1 ≡ 1 (mod n).
16
*
* Hệ quả: Mọi phần tử trong Zn đều có phần tử nghịch đảo.
1.2.2. Vành
Vành là một tập R với 2 toán tử + và . với các điều kiện sau:
R, là một nhóm Abel
a . (b . c) = (a . b) . c với mọi a, b, c R.
a . (b + c) = a . b + a . c và (a + b) . c = a . c + b . c với mọi a, b, c R.
Vành tuyến tính
F là một vành. Một đa thức bậc n trên F có dạng:
n
f (x) a xi a a x ... a xn
i
0
1
n
i0
với n là số nguyên dương, các hệ số a F (
).
0 i n
i
n
n
Cho 2 đa thức f (x) a xi và g(x) b xi
i
i
i0
i0
n
Ta định nghĩa tổng của f(x) và g(x) là f (x) g(x) (a b )xi
i
i
i0
n
m
Cho 2 đa thức f (x) a xi và g(x) b x j
i
j
i0
j0
mn
Ta định nghĩa tích của f(x) và g(x) là f (x)g(x) c xk với c
a b
k
k
i
j
k 0
i jk
0i n,0 jm
Vành được tạo thành bởi tất cả các đa thức trên F với toán tử thông thường là cộng
và nhân được gọi là vành đa thức trên F và ký hiệu là F[x].
Định lý
(Thuật toán chia cho F[x])
Giả sử f(x) và g(x) F[x] có bậc nguyên dương, tồn tại duy nhất đa thức q(x),
r(x) F[x] thỏa mãn f(x) = g(x) . q(x) + r(x) với bậc của r(x) nhỏ hơn bậc của g(x).
Nếu r(x) là đa thức 0 thì g(x) được gọi là ước của f(x). Đa thức bất định f(x)
trong F[x] là tối giản nếu nó không có ước có bậc thấp hơn f(x) trong F[x]. a F là
nghiệm của f(x) F[x] nếu f(a) = 0.
Hệ quả
Một phần tử a F là nghiệm của đa thức f(x) F[x] khi và chỉ khi x – a là ước
của f(x) trong F[x].
17
Chứng minh
Vì a là nghiệm nên f(a) = 0. Vì f(x) = (x –a).g(x) + r(x) nên bậc của r(x) nhỏ
hơn 1, tức là r(x) = c F. Vì vậy, c = f(a) = 0. Ngược lại, nếu f(x) = (x – a). q(x) thì
f(a) = 0.
Hệ quả
Một đa thức khác không f(x) F[x] bậc n có nhiều nhất n nghiệm trong F.
1.2.3. Trường
Trường F là một vành với phần tử đơn vị e 0 sao cho F* = {a F | a 0 }
là một nhóm nhân.
Định lý
Vành Zp là một trường khi và chỉ khi p là số nguyên tố
Chứng minh
Với a, b Z, ta có p là số nguyên tố
p|ab tức là p|a hoặc p|b
Nếu Zp là một trường thì Z *p tạo thành một nhóm nhân. Nếu p a thì a 0 mod p.
Điều này nghĩa là a Z *p và tồn tại a-1. Do đó nếu p|ab và p a thì p|(ab)-1 = b. Vậy
p là số nguyên tố.
Ngược lại, giả sử p là số nguyên tố. Để chỉ ra rằng Z *p là một nhóm nhân ta
chỉ cần chỉ ra rằng với mọi x Z *p sẽ luôn tồn tại nghịch đảo x-1. Với a, b Zp và
x Z * , nếu xa xb mod p thì a b mod p
a – b 0 mod p.
p
Vì p|x(a–b) p|x hoặc p|a – b và x Z * tức là p x. Điều này suy ra
p
xZp = {xa | a Zp} = Zp trong đó xa = 1 với a Zp vì luôn tồn tại phần tử 1 trong Zp.
Vậy mỗi x Z *p luôn có phần tử nghịch đảo.
Định nghĩa
F là một trường. Một 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 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.
18
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ó đặ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ử. Mọi trường hữu hạn có
một số nguyên tố là đặc số của trường. Một trường F có đặc số thì với mọi a F,
p
a a
pa =
= 0
Định nghĩa
Trường K với phần tử đơn vị nhân là 1. Với p thỏa mãn 11 ...1 0 được
p
gọi là đặc số của K. [5]
(Các trường hữu tỷ Q, số thực R, số phức C có đặc số là 0 )
Với p là nguyên tố thì GF(pn) có đặc số p.
Nếu H là trường con của K thì H và K có cùng đặc số.
F là trường mở rộng của trường K. Ký hiệu F = K( ) nếu F là trường mở
rộng nhỏ nhất của K chứa . Nếu F là trường hữu hạn đặc số p thì nhóm nhân F* =
F \ {0} là nhóm cylic và F = Zp( ) với là phần tử sinh của nhóm F* và được
gọi là phần tử nguyên thủy của F.
Với 2 toán tử nhị nguyên * và trên các tập A và B, một ánh xạ f : A B nếu
với mọi a, b A ta có:
f(a * b) = f(a)
f(b)
Giả sử A và B là 2 nhóm (hoặc 2 trường), ta gọi h: A B là một đẳng cấu
A đến B nếu h đảm bảo các tính chất của toán tử nhóm của A.
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ử.
Định lý
F là trường mở rộng bậc n trên trường hữu hạn K. Nếu K có q phần tử thì F có
qn phần tử.
Chứng minh
Giả sử {1 ,...,n }là cơ sở của F như là một không gian vector trên K.
Mọi F sẽ có dạng c11 ... cnn trong đó ci K (i = 1,…, n). Vì mỗi ci có
thể là một trong q phần tử của K nên số các tổ hợp tuyến tính là qn.
19
Định lý
Nếu F là một trường hữu hạn có đặc số p thì F có pn phần tử với n nguyên dương.
Vì vậy, mọi trường hữu hạn là một mở rộng của trường đẳng cấu Zp với p là
đặc số của F.
Định lý
Trường hữu hạn F = Fpn là một trường mở rộng của Zp bậc n và mọi phần tử
n
x p x
của Fpn là một nghiệm của đa thức
Chứng minh
trên Z .
p
Đặc số của Fpn là p. Tập hợp F* = F \ {0} tạo thành nhóm nhân bậc
pn -1. Với , bậc của trong nhóm chia hết cho bậc của F*, pn – 1. Vì vậy, với
F *
n
n
n 1
có nhiều nhất pn
F *
p 1
p
x p x
mọi
, chúng ta có
hay
. Vì
n
x p x
nghiệm, Fpn gồm tất cả các nghiệm của
Ví dụ
trên Z .
p
Trường F2r chứa F2(hoặc Z2).Nếu viết toán tử cộng trong F2r như là phép cộng
vector và viết phép nhân k và v(k,v F2r )là một tích vô hướng của kF2 và v
F 2r .Khi đó F2r được xem là không gian vector trên F2 với chiều r. Ký hiệu d là
chiều của không gian vector này. Có thể thực hiện ánh xạ 1 – 1 giữa các phần tử
trong không gian vector d chiều và các d-tuple của các phần tử trong F2. Vì
vậy,có2d phần tử trong không gian vector này.Vì d = r, F2r là không gian vector r
chiều.
Fqm là một mở rộng của Fq. 2 phần tử , Fqm là liên hợp trên Fq nếu và
2
m1
là các nghiệm của cùng một đa thức tối giản bậc m trên Fq. , q , q ,..., q là
các liên hợp của Fqm với Fq.
Fqm là một mở rộng của Fq. Một cơ sở của Fqm (không gian vector trên Fq)
2
m1
của {, q , q ,..., q } gồm Fqm và các liên hợp của nó với Fq , được gọi là cơ
sở trực giao của Fqm trên Fq. Mọi trường mở rộng bậc hữu hạn của một trường hữu
hạn có một cơ sở trực giao.
Không gian chiếu
20
Xét L = Kn+1 \{0} với K là một trường. Với A = (a0, a1, …, an), B = {b0, b1, …,
bn} L, định nghĩa một quan hệ A ~ B gồm A, B và gốc O = (0, 0,…,0) là cộng
tuyến, nghĩa là tồn tại
thỏa mãn : ai bi , (i = 0, 1, …, n).
K
Quan hệ ~ là quan hệ tương đương và định nghĩa một phân hoạch của L. Tập
thương số là không gian chiếu ký hiệu là Pn(K).
Mặt phẳng chiếu là tập các lớp tương đương của bộ ba (X, Y, Z) với
((X,Y,Z) ) ~ (X, Y, Z) (
). Mỗi lớp tương đương (X, Y, Z) được gọi là một
K
điểm chiếu trên mặt phẳng chiếu. Nếu một điểm chiếu có Z 0, thì (x, y, 1) là một
X
Z
Y
thể hiện của lớp tương đương với x =
, y = . Mặt phẳng chiếu có thể được
Z
định nghĩa là tập tất cả các điểm(x, y)của mặt phẳngAffine cộng với các điểm Z = 0.
21
1.2.4. Không gian vector
K là một trường và V là một nhóm cộng Abel. V được gọi là không gian vector
trên trường K nếu một toán tử K x V V được định nghĩa thỏa mãn các điều kiện
sau:
a(u + v) = au + av
(a + b)u = au + bu
a(bu) = (ab)u
1u = u
Các phần tử của V được gọi là các vector và các phần tử của K được gọi là
các vô hướng. V là một không gian vector trên trường K và các v1, …, vm V.
Vector trong V có dạng c1v1 + c2v2 + …+ cmvm với ci K (i = 1, …, m) là một tổ
hợp tuyến tính của v1, …, vm. Tập hợp tất cả các tổ hợp tuyến tính gọi là span của v1,
…,vmvà ký hiệu là span(v1, …, vm). v1, …, vm được gọi là span nếu của V nếu
V = span(v1, …, vm).
V là không gian vector trên trường K. Các vector v1, …, vm V được gọi là
độc lập tuyến tính trên K nếu không có các vô hướng c1,…, cm K thỏa mãn:
c1v1 + c2v2 + …+ cmvm = 0
Tập S = {u1, u2,…,un} của các vector tạo thành cơ sở của V khi và chỉ khi
u1, u2,…,un là độc lập tuyến tính là span của V. Nếu S là một cơ sở của V thì mọi
phần tử của V được biểu diễn duy nhất dưới dạng tổ hợp tuyến tính của các phần tử
của S. Nếu không gian vector V có cơ sở là một số hữu hạn các vector thì bất kỳ cơ
sở nào của V cũng sẽ có cùng số phần tử. Khi đó nó chính là chiều của V trên K.
Nếu F là một trường mở rộng của trường K thì F là một không gian vector
trên K. Chiều của F trên K được gọi là bậc mở rộng của F trên K.
22
Chương 2. ĐƯỜNG CONG ELLIPTIC
Hệ thống mã khóa khóa công khai dựa trên việc sử dụng các bài toán khó giải
quyết. Vấn đề khó ở đây chính là việc số lượng phép tính cần thiết để tìm ra một lời
giải cho bài toán là rất lớn. Trong lịch sử 20 năm của ngành mã hóa bất đối xứng đã
có nhiều đề xuất khác nhau cho dạng bài toán như vậy, tuy nhiên chỉ có hai trong số
các đề xuất đó còn tồn tại đến ngày nay. Hai bài toán đó bao gồm : bài toán logarit
rời rạc (discrete logarithm problem) và bài toán phân tích thừa số của số nguyên.
Cho đến năm 1985, hai nhà khoa học Neal Koblitz và Victor S.Miller đã độc
lập nghiên cứu và đưa ra đề xuất ứng dụng lý thuyết toán học đường cong elliptic
(elliptic curve ) trên trường hữu hạn.
Đường cong elliptic cũng như đại số hình học- được nghiên cứu rộng rãi trong
vòng 150 năm trở lại đây và đã đạt được một số kết quả lý thuyết có giá trị. Đường
cong elliptic được phát hiện lần đầu tiên vào thế kỷ 17 dưới dạng công thức
Diophantine :
y2 – x3 = c
với c
Z
Tính bảo mật của hệ thống mã hóa sử dụng đường cong elliptic dựa trên điểm
mấu chốt là độ phức tạp của bài toán logarit rời rạc trong hệ thống đại số. Trong
suốt 10 năm gần đây, bài toán này nhận được sự quan tâm chú ý rộng rãi của các
nhà toán học hàng đầu trên thế giới. Không giống như bài toán logarit rời rạc trên
trường hữu hạn hoặc bài toán phân tích thừa số của số nguyên, bài toán logarit rời
rạc trên đường cong elliptic chưa có thuật toán nào có thời gian thực hiện nhỏ hơn
cấp lũy thừa. Thuật toán tốt nhất được biết đến hôm nay tốn thời gian thực hiện cấp
lũy thừa.
23
2.1. CÔNG THỨC WEIERSTRASSE VÀ ĐƯỜNG CONG
ELLIPTIC
Gọi K là trường hữu hạn hoặc vô hạn. Một đường cong elliptic được định
nghĩa trên trường K bằng công thức Weierstrasse :
y2 + a1xy + a3y = x3 + a2x2 + a4x + a6
(1)
Trong đó a1 , a2 , a3 , a4 , a5 , a6
K
Đường cong elliptic trên trường k được ký hiệu E(K). Số lượng các điểm
nguyên trên E ký hiệu là #E(K) , có khi chỉ đơn giản là #E. Đối với từng trường
khác nhau, công thức Weierstrasse có thể được biến đổi và đơn giản hóa thành các
dạng khác nhau. Một đường cong elliptic là tập hợp các điểm thỏa mãn công thức
trên.
Hình 1: Một ví dụ về đường cong Elliptic
2.2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG R2
Đường cong elliptic E trên trường số thực R là tập hợp các điểm (x,y) thỏa
mãn công thức:
y2 = x3 + a4x + a6 với a4 , a6
R
(2)
cùng với một điểm đặc biệt O được gọi là điểm tại vô cực (cũng là phần tử
identify). Cặp giá trị (x,y ) đại diện cho một điểm trên đường cong elliptic và tạo
nên mặt phẳng tọa độ hai chiều (Affine) R x R . Đường cong elliptic E trên R2
24
được gọi là định nghĩa trên R , ký hiệu là E (R). Đường cong elliptic trên số thực có
thể dùng để thể hiện một nhóm (E(R), +) bao gồm tập hợp các điểm (x ,y) thuộc R x
R với phép công + trên E(R).
2.2.1. Phép cộng
Hình 2: Điểm ở vô cực
Phép cộng điểm (ESUM) được định nghĩa trên tập E(R) của các điểm (x, y).
Điểm tại vô cực 0 là điểm cộng với bất kỳ điểm nào cũng sẽ ra chính điểm đó.
Như vậy,
P x, y E R , P O O P P
P x, y E R , y x3 a a
(3)
4
6
Như vậy , tương ứng với một giá trị x ta sẽ có hai giá trị tọa độ y.
Điểm (x , -y ) ký hiệu là –P E(R), được gọi là điểm đối của P với :
P + (-P) = (x , y) + (x ,- y) = 0
(4)
Phép cộng trên E(R) được định nghĩa theo phương diện hình học . Giả sử có
hai điểm phân biệt P Và Q , P, Q E(R). Phép cộng trên nhóm đường cong elliptic
là P +Q = R ,R E(R).
25
Hình 3: Phép cộng trên đường cong elliptic
Để tìm ra điểm R , ta nối P và Q bằng đường thẳng L. Đường thảng L sẽ cắt E
tại ba điểm P , Q và -R(x , y). Điểm R (x , -y) sẽ có tung độ là giá trị đối của y.
Thể hiện đường cong elliptic dưới dạng đại số , ta có:
P = (x1 , y1)
Q = (x2 , y2)
R= P + Q = (x3 , y3)
Trong đó P , Q , R E (R) và :
x3 = θ2 – x1 – x2
(5)
y3 = θ(x1 + x3) – y1
(6)
(7)
y2 y1
nếu P ≠ Q
x2 x1
3x12 a4
2y1
Hoặc
nếu P = Q
(8)
26
Thuật toán cộng trên đường cong elliptic
Input:
Đường cong elliptic E(R)với các tham số a4, a6 E(R) ,
Điểm P = (x1, y1) E(R) và Q = (x2, y2) E(R)
Output: R = P + Q, R = (x3, y3) E(R)
If P = O then R ← Q và trả về giá trị R
If Q = O then R ← P và trả về giá trị R
If x1 = x2 then
If y1 = y2 then
3x12 a4
2y1
else if y1 = −y2 then
R ← O và trả về R,
y2 y1
x2 x1
else
end if
x3 = θ2 – x1 – x2
y3 = θ(x1 + x3) – y1
Trả về (x3, y3) = R
27
2.2.2. Phép nhân đôi
Hình 4: Phép nhân đôi trên đường cong elliptic
Xét phép nhân đôi (EDBL): nếu cộng hai điểm P, Q
E(R) với P = Q thì
đường thẳng L sẽ là tiếp tuyến của đường cong elliptic tại điểm P. Trường hợp này
điểm –R sẽ là giao điểm còn lại của L với E. Lúc đó R = 2P.
28
2.3. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN
Đường cong elliptic được xây dựng trên các trường hữu hạn. Có hai trường
hữu hạn thường được sử dụng: trường hữu hạn Fq với q là số nguyên tố hoặc q là 2m
(m là số nguyên).
Tùy thuộc vào trường hữu hạn Fq, với mỗi bậc của q, tồn tại nhiều đường
cong elliptic. Do đó, với một trường hữu hạn cố định có q phần tử và q lớn, có
nhiều sự lựa chọn nhóm đường cong elliptic.
2.3.1. Đường cong elliptic trên trường Fp (p là số nguyên tố)
Cho p là số nguyên tố (p>3), Cho a,b
Fp sao cho 4a3 + 27b2 ≠ 0 trong
trường Fp . Một đường cong elliptic E(Fp) trên Fp (được định nghĩa bởi các tham số
a và b) là tập hợp các cặp giá trị (x ,y) (x, y Fp) thỏa công thức:
y2 = x3 + ax + b
(9)
cùng với một điểm 0 – gọi là điểm tại vô cực. Số lượng điểm của E(Fp) là #E(Fp)
thỏa định lý Hasse:
p 1 2 p # E(Fp ) p 1 2 p
(10)
Các phép toán của đường cong elliptic trên Fp cũng tương tự với E(R). Tập
hợp các điểm trên E(Fp) tạo thành một nhóm thỏa các tính chất sau:
Tính đóng: a, b G, a + b G.
Tính kết hợp: Các phép toán trong nhóm có tính kết hợp
Do đó, (a + b) + c = a + (b + c).
Phần tử trung hòa: có một giá trị 0 G sao cho a + 0 = 0 + a = a,
Phần tử đối: , a G , -a G gọi là số đối của a, sao cho
-a + a = a + (-a) = 0
a
G.
Bậc của một điểm A trên E(Fp) là một số nguyên dương r sao cho:
A A.... A 0
(11)
r
29
m
2.3.2. Đường cong elliptic trên trường F2
m
m
Một đường cong elliptic E(F2 ) trên F2 được đĩnh nghĩa bởi các tham số a , b
m
m
m
F2 (với b ≠ 0 ) là tập các điểm (x,y) với các x F2 , y F2 thỏa công thức:
y2 + xy = x3 + ax2 + b
(12)
m
cùng với điểm 0 là điểm tại vô cực . Số lượng các điểm thuộc E(F2 ) ký hiệu
m
# E(F2 ) thỏa định lý Hasse :
p 1 2 p # E(Fp ) p 1 2 p
(13)
m
Trong đó q = 2m . Ngoài ra # E(F2 ) là số chẵn
m
Tập hợp các điểm thuộc E(F2 ) tạo thành một nhóm thỏa các tính chất sau:
0 + 0 = 0
m
(x , y) + 0 = (x , y) , (x ,y) E(F2 )
m
(x , y) + (x, x + y) = 0 , (x ,y) E(F2 ) Khi đó (x, x + y) là điểm đối của
m
(x , y) trên E(F2 )
Việc xử lý được thực hiện trên hai hệ tọa độ khác nhau: hệ tọa độ Affine và
hệ tọa độ quy chiếu. Với các hệ tọa độ khác nhau, việc tính toán trên đường
cong cũng khác nhau.
2.3.3. Các phép toán trên đường cong elliptic trong hệ tọa độ Affine
m
Hệ mã hóa đường cong elliptic dựa trên bài toán logarit rời rạc trên E(F2 ) và
các tính toán cơ bản trên đường cong elliptic. Phép nhân được thể hiện là một dãy
các phép cộng và phép nhân đôi các điểm của đường cong elliptic. Giống như các
phép tính trên đường cong elliptic trên số thực, phép cộng và phép nhân đôi được
định nghĩa trên hệ tọa độ.
m
Xét đường cong elliptic E trên F2 trong hệ tọa độ Affine. Cho P = (x1 , y1) ,
m
Q = (x2 , y2) là hai điểm trên đường cong elliptic E(F2 ) . Điểm đối của P là:
m
–P = (x1 , y1+x1)
E(F2 ).
30
Tải về để xem bản đầy đủ
61 trang
01/05/2025
120
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Nghiên cứu, tìm hiểu và trình bày về chữ ký số trên đường cong elliptic, ứng dụng của đường cong elliptic trong hệ thống bỏ phiếu điện tử và hệ thống tiền điện tử", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_nghien_cuu_tim_hieu_va_trinh_bay_ve_chu_ky_so_tren.pdf
