Download miễn phí Đồ án Hệ mật đường cong Elliptic và ứng dụng trong mạng điện thoại
MỤC LỤC
LỜI CẢM ƠN 4
LỜI MỞ ĐẦU 5
CHƯƠNG 1: CƠ SỞ TOÁN HỌC 7
1.1. Số nguyên và các định lý về số nguyên 7
1.2. Phương trình đồng dư bậc hai và thặng dư bậc hai 9
1.3. Đại số đại cương 13
1.3.1. Nhóm 13
1.3.2. Vành 15
1.3.3. Ánh xạ 15
1.3.4. Trường 15
1.3.5. Không gian Vectơ 16
1.3.6. Vành đa thức 17
1.3.7. Trường hữu hạn 18
1.3.8. Không gian chiếu 20
CHƯƠNG 2: ĐƯỜNG CONG ELLIPTIC 21
2.1. Khái niệm đường cong Elliptic 21
2.1.1. Phương trình Weierstrass 21
2.1.2. Các nhóm đường cong Elliptic trên trường số thực 21
2.1.2.1. Phép cộng trên đường cong Elliptic : Cách tiếp cận hình học 22
2.1.2.2. Phép cộng trên đường cong Elliptic: Cách tiếp cận đại số 25
2.1.3. Đường cong Elliptic trên các trường nguyên tố hữu hạn Fp 25
2.1.4. Đường cong Elliptic trên trường nhị phân hữu hạn GF(2m) 26
2.2 Các nhóm đường cong Elliptic và bài toán logarithm rời rạc 28
2.2.1. Tích vô hướng 29
2.2.2 Bài toán logarithm rời rạc trên đường cong Elliptic 29
2.3 Đếm số điểm trên đường cong elliptic trên trường Fq 29
2.4 Tính chất đồng cấu của các đường cong elliptic 30
CHƯƠNG 3: CÁC HỆ MẬT TRÊN ĐƯỜNG CONG ELLIPTIC 31
3.1. Lịch sử 31
3.2. Nhúng bản rõ vào các đường cong Elliptic 32
3.2.1. Imbeding 32
3.2.2. Mask 33
3.3. Một số hệ mã hóa trên đường cong elliptic 33
3.3.1. Hệ mã hóa “tựa” Elgamal. 33
3.3.2. Hệ mã hóa Menezes-Vanstone. 34
3.4. Một số sơ đồ chữ ký trên đường cong elliptic 35
3.4.1. Sơ đồ chữ ký ECDSA. 35
3.4.2. Sơ đồ chữ ký Nyberg – Rueppel. 37
3.4.3. Sơ đồ chữ ký mù Harn trên EC. 38
3.4.4. Sơ đồ “ blind multi-signature” của Harn trên EC 39
3.5. Một số thuật toán tấn công các hệ ECC 40
3.5.1. Phương pháp tấn công “baby-step giant - step”. 40
3.5.2. Phương pháp tấn công MOV 41
3.5.3. Các thuật toán tấn công khác 44
3.6. Những chú ý để lựa chọn đường cong Elliptic phù hợp 44
3.6.1. Trường K 44
3.6.2. Dạng của đường cong elliptic 45
3.6.3. Phương pháp lựa chọn 45
3.7. Các chuẩn cho hệ mật ECC 46
3.8. So sánh RSA và ECC 48
CHƯƠNG 4: ỨNG DỤNG CỦA EllIPTIC TRONG MẠNG ĐIỆN THOẠI DI ĐỘNG 51
4.1. Khả năng ứng dụng của hệ mã hóa Elliptic. 51
4.2. Yêu cầu về an toàn truyền tin. 51
4.3. Đặc điểm của môi trường ứng dụng. 52
4.4. Các giao thức trên đường cong Elliptic trong mạng điện thoại di động 53
4.4.1. Mã hóa thông điệp. 53
4.4.2. Xác thực. 56
4.5. Ứng dụng trong việc mã hóa và bảo mật thông tin cá nhân. 57
4.5.1. Mã hóa thông điệp 57
4.5.2. Chương trình ví dụ 58
4.6. Mô hình ứng dụng trong thương mại di động 65
4.6.1. Vấn đề về bảo mật 66
4.6.2. Cơ chế bảo mật 67
KẾT LUẬN 70
TÀI LIỆU THAM KHẢO 72
http://s1.liketly.com/flash/edoc/web-viewer.html?file=jh2i1fkjb33wa7b577g9lou48iyvfkz6-demo-2016-01-14-do_an_he_mat_duong_cong_elliptic_va_ung_dung_trong_mang_dien_VFYO9gseAU.png /tai-lieu/do-an-he-mat-duong-cong-elliptic-va-ung-dung-trong-mang-dien-thoai-87399/ Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn. Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn
Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
p)
ta thấy 4a3 + 27b2 = 4 + 432 = 436 22 (mod 23). Vì vậy, E thực sự là đường cong elliptic.
Theo định lý Hasse, #E(F23) = 29, là một số nguyên tố nên E(F23) là cylic và bất kỳ điểm nào khác O đều là phần tử sinh của E(F23). Ví dụ, G = (0, 2) là phần tử sinh với các tập điểm của E(F23) như sau:
k
kG
k
kG
k
kG
K
kG
k
kG
k
kG
1
(0, 2)
6
(9, 11)
11
(10, 5)
16
(8, 8)
21
(14, 18)
26
(11, 14)
2
(13, 12)
7
(15, 6)
12
(17, 9)
17
(17, 14)
22
(15, 17)
27
(13, 11)
3
(11, 9)
8
(14, 5)
13
(8, 15)
18
(10, 18)
23
(9, 12)
28
(0, 21)
4
(1, 12)
9
(4, 7)
14
(18, 9)
19
(22, 18)
24
(7, 3)
29
O
5
(7, 20)
10
(22, 5)
15
(18, 14)
20
(4, 16)
25
(1, 11)
Bảng 2.1. Các điểm trên E(Z23)
CHƯƠNG 3: CÁC HỆ MẬT TRÊN ĐƯỜNG CONG ELLIPTIC
3.1. Lịch sử
Năm 1976, Diffie và Hellman giới thiệu hệ mã hoá khoá công khai đầu tiên mà sự an toàn của nó dựa trên độ khó của bài toán DLP. Họ đưa ra khái niệm hàm cửa sập một chiều (TOF). Năm 1985, Lenstra thành công trong việc sử dụng các đường cong elliptic cho các số nguyên. Kết quả này mang lại khả năng áp dụng các đường cong elliptic trong các hệ mật mã khoá công khai.
Miller và Kobliz giới thiệu những hệ mật mã elliptic đầu tiên. Họ không phát minh ra các thuật toán mới nhưng đã có đóng góp lớn là chỉ ra việc áp dụng đường cong Elliptic cho các hệ khoá công khai. Miller đề xuất một giao thức trao đổi khoá tựa như Diffie – Hellman vào năm 1985 (nhanh hơn 20% so với giao thức Diffie - Hellman). Kobliz đưa ra thuật toán mã hoá tương tự như hệ Elgamal và Massey – Omura vào năm 1987. Sơ đồ đầu tiên tương tự như sơ đồ RSA và 3 hàm một chiều (có cửa sập) mới dựa trên đường cong Elliptic được đưa ra năm 1991 bởi Koyama, Maurer, Okamoto và Vanstone ( thuật toán này tốc độ thực hiện nhanh gấp 6 lần so với RSA). Cùng thời điểm đó, Kaliski chứng minh rằng các hàm cửa sập một chiều đòi hỏi thời gian là hàm mũ để thực hiện phép tính nghịch đảo. Menezes, Okamoto và Vanstone đã đưa ra một phương pháp tấn công MOV để giải bài toán EDLP trong một số trường hợp riêng. Ngay sau đó, Miyaji đã tìm được các điều kiện để tránh khỏi tấn công MOV và đề xuất một ứng dụng thực tế của các đường cong elliptic cho các sơ đồ chữ ký và định danh trên Smart Card.
Năm 1993, Demytko đưa ra một thuật toán mới tương tự như RSA cho các đường cong Elliptic trên vành Zn vượt qua các hạn chế của các phiên bản 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õ vào các đường cong Elliptic
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à: imbeding, mask.
3.2.1. Imbeding
Cách 1: Để nhúng m lên E(Zp) với p là số nguyên tố, chẳng hạn p 3 (mod 4). Giả sử E(Zp) được cho bởi phương trình (2.1) và giả sử m là số nguyên thỏa mãn . Thêm 3 chữ số vào m sẽ tạo ra x thỏa mãn . Chúng ta sẽ bổ sung các chữ số khác nhau cho đến khi tìm được x sao cho f(x) = x3 + ax + b là một số bình phương trong Zp và y (với f(x) = y2 mod p ) thỏa mãn . Điểm Phần mềm được tạo thành khi nhúng m lên E là:
Có thể dễ dàng khôi phục lại m từ bằng cách loại bỏ 3 chữ số cuối của tọa độ x của điểm Pm.
Cách 2
Bước 1: Sử dụng bảng chữ cái gồm N ký tự. Chia bản rõ thành các khối có độ dài cố định l. Các ký tự được đánh số là 0,, N-1. Một khối văn bản w cùng với các số tạo thành một ánh xạ:
Bước 2: Chọn một giá trị k thích hợp sao cho kNl < q. Với mỗi j là phần tử của Fq tính kxw + j. Lấy điểm Pw đầu tiên mà tọa độ x kxw , ví dụ Pw = (kxw + j, *)
Bước 3: Khôi phục lại khối bản rõ từ Pw bằng cách tính
3.2.2. Mask
Để biểu diễn lại các cặp phần tử (m1, m2) thành các điểm trên E có thể áp dụng phương pháp masking bằng cách nhân m1 và m2 với các tọa độ x, y của các điểm trên E.
3.3. Một số hệ mã hóa trên đường cong elliptic
Hệ mã hóa đường cong elliptic (ECC) có thể được thực thi tương tự như các hệ mật mã khác trên trường số nguyên, thay vào đó là các điểm trên đường cong elliptic.
3.3.1. Hệ mã hóa “tựa” Elgamal.
Hệ Elgamal làm việc với nhóm cyclic hữu hạn. Năm 1987, Koblitz đã đưa ra một hệ trên ECC dựa trên hệ Elgamal.
Ta có trường số Zp và một đường cong elliptic E trên Zp là E(Zp) cùng một điểm cơ sở PE. Mỗi người dùng sẽ chọn một số aX làm khóa bí mật, và aXP là khóa công khai.
Giả sử Alice cần gửi một thông điệp m cho Bob. Đầu tiên cô ấy nhúng văn bản m lên E, chẳng hạn m được thể hiện bằng một điểm PmE. Khi đó cô ta phải mã hóa Pm. Ký hiệu aB là khóa bí mật của Bob, vì vậy khóa công khai của Bob là aBP. Alice chọn một số ngẫu nhiên k và gửi cho Bob cặp điểm trên E:
(C1, C2) = (kP, Phần mềm + k(aBP))
Để giải mã, Bob tính:
C2 – aB(C1) = Phần mềm + k(aBP) – aB(kP) = Pm
Chú ý rằng ở đây Phần mềm là một điểm thuộc đường cong elliptic, quá trình mã hóa giải mã được thực hiện trên các điểm thuộc đường cong E. Trong thực tế, để sử dụng được người ta phải tương ứng một số với một điểm thuộc đường cong elliptic. Khi đó mỗi thông điệp cần mã hóa sẽ tương ứng với một dãy số. Mỗi số sẽ tương ứng với một điểm trên đường cong elliptic.
Tính bảo mật
Nếu kẻ tấn công giữa đường, Oscar, có thể giải bài toán EDLP thì anh ta có thể biết được khóa bí mật aB của Bob từ các thông tin công khai P và aBP, và có thể giải mã được thông điệp mà Alice gửi. Như vậy, độ an toàn (bảo mật) của thuật toán trên dựa vào độ an toàn của bài toán EDLP.
Sơ đồ mã hóa trên có ưu điểm là không yêu cầu tính số điểm của E trên Fq (#E(Fq)).
3.3.2. Hệ mã hóa Menezes-Vanstone.
Sự khác biệt của hệ này với hệ tựa Elgamal là Alice áp dụng kỹ thuật Masking thay vì Imbeding khi biểu diễn lại bản rõ thành các điểm trên E.
E là một đường cong elliptic trên trường nguyên tố Zp (p > 3) sao cho E chứa một nhóm con cyclic H, mà trong đó bài toán EDLP là khó. Zp, E(Zp) và điểm PE là công khai. Mỗi người dùng chọn một số nguyên ngẫu nhiên aX làm khóa bí mật và công khai aXP.
Giả sử rằng Alice cần gửi thông điệp M = (x1, x2) cho Bob. Giả sử aB là khóa bí mật của Bob. Alice chọn số ngẫu nhiên k và gửi:
(y0, y1, y2) = (kP, c1x1 mod p, c2x2 mod p) với (c1, c2) = k(aBP)
Để giải mã, Bob tính:
(y1c1-1 mod p, y2c2-1 mod p) = (x1, x2) với aBy0 = (c1, c2)
Việc giải mã là đúng đắn vì: y0 = kP, Bob có thể tính: aBy0 = aB(kP) = k(aBP) = (c1, c2)
vì vậy:
Ví dụ Xét đường cong E có phương trình dạng:
y2 = x3 + x + 13
Trên trường nguyên tố Z31. Như vậy, E có đặc số 2, 3. Chọn điểm cơ sở G = (9, 10). #E(Z31) = 34 và P là phần tử bậc 34. Các điểm trên E được liệt kê như sau:
Bảng 3.1. Các điểm trên E(Z31)
k
kG
k
kG
k
kG
K
kG
k
kG
k
kG
1
(9, 10)
7
(6, 24)
13
(27, 10)
19
(5, 22)
25
(16, 23)
31
(23, 12)
2
(18, 29)
8
(24, 29)
14
(26, 21)
20
(26, 10)
26
(24, 2)
32
(18, 2)
3
(23, 19)
9
(16, 8)
15
(5, 9)
21
(27, 21)
27
(6, 7)
33
(9, 21)
4
(4, 22)
10
(20, 2)
16
(19, 3)
22
(28, 18)
28
(17, 13)
34
O
5
(25, 16)
11
(22, 22)
17
(10, 0)
23
(22, 9)
29
(25, 15)
6
(17, 18)
12
(28, 13)
18
(19, 28)
24
(20, 29)
30
(4, 9)
Chúng ta sử dụng phương pháp masking thay cho imbeding nên không gian bản rõ là Z34*xZ34*. Mỗi bản rõ (x1, x2) thể hiện 2 chữ cái trong đó “a” là 1, “b” là 2, , “z” là 26. Phép tính nghịch đảo modulo được thực hiện bằng thuật toán Euclid mở rộng. Phép tính kG sử dụng thuật toán nhân đôi và cộng.
3.4. Một số sơ đồ chữ ký trên đường cong elliptic
3.4.1. Sơ đồ chữ 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 Fq với đặc số p sao cho phù hợp, điểm cơ sở G E(Fq).
Một số khuyến nghị khi lựa chọn các tham số:
Kích thước q của trường, hay q = p (p > 2) hay q = 2m.
Hai phần tử a, b thuộc Fq xác định phương trình đường cong elliptic:
y2 = x3 + ax + b (p>2) hay y2 + xy = x3 + ax2 + b (p =2)
Hai phần tử xG và yG thuộc Fq xác định điểm cơ sở G = (xG, yG).
Bậc n của điểm G với n > 2160 và
Tham số phụ h = #E(Fq)/n.
Sinh khóa
Chọn số ngẫu nhiên d trong khoảng [1, n – 1]
Tính Q = dG.
Khóa công khai là Q, khóa bí mật là d
Ký trên bản rõ m
Chọn một số ngẫu nhiên k,
Tính kG = (x1, y1).
Tính r = x1 mod n. Nếu r = 0, quay lại bước 1.
Tính k-1 mod n.
Tính s = k-1 (m + dr) mod n. Nếu s = 0 quay lại bước 1.
Chữ ký trên thông điệp m là (r, s)
Kiểm tra chữ ký
Kiểm tra r và s có là các số tự nhiên trong khoảng [2, n – 1]
Tính w = s-1 mod n
Tính u1 = mw mod n và u2 = rw mod n
Tính X = u1G + u2Q
Nếu X = O thì phủ nhận chữ ký. Ngược lại tính v = x1 mod n.
Chữ ký chỉ được chấp nhận nế...
