Đồ án Hệ mật trên đường cong Elliptic

â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 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: (F, +) là nhóm giao hoán với phần tử đơn vị là “0”. (F\{0}, .) là nhóm giao hoán với phần tử đơn vị là “1”. 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. Ví dụ: Q = { p, q là số nguyên: (p, q) = 1} trên Q có 2 phép toán cộng 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: = 0 Định nghĩa 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 = 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 (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 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: X→X − , Y→ Y − 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 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, yK } {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) : y2 + 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 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). Ví dụ: Nếu q = p là 1 số nguyên tố thì (x) =( ) là ký hiệu Legedre 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 + (1+ (x3 + ax + b)) = q + 1 + (1+ (x3 + ax + b)) (6) 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 đó chính là định lý Hasses được phát triển 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 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) ZpZp 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 x3 =- x1 – x2 (*) y3 = ( x1 – x3) - y1 N ếu P =Q x3 =– 2x2 (**) y3 = ( x1 – x3) - y1 P Q P+ Q R P 2P R -1 -2 2 1 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: 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ó: x3 = +3 + 2 = 1+ 3 +2 = 6. y3 = -9 (-3-6) = -9 + (-1)(-9) =0. Vậy P +Q = (6, 0). Bây giờ ta tính 2P áp dụng (**) ta có: x1= -3, y1 = 9 x3 = và do đó y3= . Vậy 2P = (,) 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 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 .Từ định lý Hasse suy ra #E(Fq) = q +1 – t trong đó |t| ≤ 2 . Đị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 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 Chọn ngẫu nhiên 3 phần tử từ Fq là x, y, a Tính b = y2 – (x3 + ax) Kiểm tra 4a3 + 27b2 ≠ 0 để đảm bảo phương trình x3 + ax + b =0 không có nghiệm kép. Nếu điều kiện trên khôn thoả mãn quay lại bước 1. Còn lại, đặt P = (x, y) và đường cong y2 = x3 + ax +b là đường cong cần chọn. Tuy nhiên phương pháp này có thể tạo ra các đường cong không đảm bảo một số yêu cầu định trước. Một kỹ thuật cải tiến là xây dựng các đường cong với các tính chất cho trước. Cũng có thể chọn những đường cong để tạo các hệ mã hoá không phụ thuộc vào bài toán EDLP, chẳng hạn các hệ elliptic dựa trên RSA. Các hệ mật mã elliptic làm việc với các nhóm con cylic của E với phần tử sinh là điểm P. Vì vậy, việc lựa chọn P phù hợp là rất quan trọng. Để đảm bảo việc chọn điểm thích hợp ta hãy chọn đường cong elliptic của chúng ta và trường hữu hạn sao cho số N các điểm của đường cong là một số nguyên tố. Nếu chọn được như vậy thì mọi điểm B ≠ 0 đều là phần tử sinh. CHƯƠNG 3 HỆ MẬT ĐƯỜNG CONG ELLIPTIC 3.1. Mở đầu và đặt bài toán 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. 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 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õ 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 Fq 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 Pm 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 Fq. 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 lớn tuỳ ý các bản rõ m. Trong lúc đó bản rõ mà ta cần nhúng lại có thể rất lớn. Do đó, một phương pháp xác suất có thể cho phép nhúng (imbed) các bản rõ m được coi là một điểm trên đường cong elliptic E được định nghĩa trên trường Fq với q = pn được giả thiết là đủ lớn. Gọi là một số nguyên dương đủ lớn sao cho thoả mãn xác suất sai xấp xỉ 1/2 . Giả sử khi chúng ta muốn nhúng một bản rõ m, giả sử là một số nào đó(=20, 30 hoặc = 50 là đủ). Với m kà một số nguyên sao cho 0≤ m ≤M (M là số nguyên dương lớn hơn mọi khối rõ m cần nhúng ) Trường hữu hạn đã chọn sao cho q > M.Biểu diễn các số nguyên từ 1 đến M dưới dạ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 Fq. 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 Fq. Nghĩa là số nguyên (ar-1 , ar-2,.a1, a0 )p đặt tương ứng với đa thức ajXj mà nóđược xem như modulo đa thức bất khả quy cấp r cố định trên Fp, cho một phần tử của Fq. Do đó cho trước m với j = 1, 2,3.. sẽ nhận được một phần tử của Fq tương ứng với m+ j Đối với số x đó ta tính: Y2 = f(x) = x3 + ax + b và tìm căn bậc 2 của giá trì f(x) bằng cách sử dụng phương pháp đã nêu trong ví dụ 1.1.4. Nếu tìm được một số y sao cho y2 = f(x) thì lấy Pm = (x, y). Nếu kết quả f(x) là không bình phương thì tăng x bởi 1 và tiếp tục tính toán từ đầu cho đế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 Fq. 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. 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 Fq 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) Hầu như bài toán tính logarit rời rạc trên đường cong elliptic sẽ khó hơn bài toán logarit rời rạc trên trường hữu hạn. Các kỹ thuật mạnh nhất đã được phát triển để sử dụng trong các trường hữu hạn dường như không có giá trị đối với đường cong elliptic. Kết quả này đặc biệt đúng trong trường hợp trường có đặc số 2. Như đã được chứng tỏ bởi Odlzko rằng có một số phương pháp đặc biệt để giải bài toán logarit rời rạc trong G*2r với chúng dễ dàng tính được logarit rời rạc và do đó phá vỡ được hệ mật mã, trừ ra trường hợp số r được chon đủ lớn. Dường như các hệ thống tương tự sử dụng đường cong elliptic được định nghĩa trên trường F2r sẽ đảm bảo an toàn kể cả trong trường hợp giá trị r khá bé. 3.4. Vấn đề trao đổi khoá Diffie- Hellman(D- H) trên Elliptic Giả sử A và B muốn thống nhất một khoá chung để liên lạc có bảo mật giữa hai người bằng mật mã truyền thống. Trước hết hai bên thống nhất công khai chọn một trường hữu hạn Fq và một đường cong elliptic trên nó khoá chung của họ sẽ được xây dựng từ một điểm ngẫu nhiên P của đường cong vừa cho, họ làm cách này bằng cách chọn toạ độ x của P là ngẫu nhiên trong Fq. Sau đó nó được chuyển đổi thành số nguyên cơ số P có r số( q = pr) 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ư 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 Fpr . 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 nA là một số nguyên, và sinh khoá công khai PA = nA * G. Khi đó hệ mã hoá đường cong elliptic được xây dựng tương tự hệ mã hoá ElGamal, trong đó thuật toán mã hoá và giải mã được xác định như sau: Thuật toán mã hoá Giả sử người dùng A muốn gửi thông điệp cần mã hoá Pm tới người dụng B, chọn một số ngẫu nhiên k và gửi thông điệp mã hoá Cm được tính như sau: Cm = {k * G, Pm + k * PB } (PB là khoá công khai của B) Thuật toán giải mã Để giải mã thông điệp Cm = { k * G, Pm + k * PB }, người dùng B thực hiện tính như sau: Pm + k * PB - nB * k * G = Pm + k * PB – k * nB * G = Pm + k * PB - k * PB = Pm Chỉ có B mới có thể giải mã vì B có nB (là khoá bí mật). Chú ý rằng ở đây Pm là một điểm thuộc đường cong elliptic, quá trình mã hoá 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ã hoá 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 khoá bí mật từ nB của B từ các thông tin công khai G và nBG, và có thể giải mã thông điệp mà A gửi. Như vậy độan toàn (bảo mật) của thuật toán trên dựa vào độ khó của bài toán EDLP. 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 Fq với đặc số p sao cho phù hợp và công khai cho tất cả mọi người, đ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ích q của trường, hoặc q = p (p>2) hoặc 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) hoặc 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à n > 4. Sinh khoá Chọn số ngẫu nhiên d trong khoảng [2, n-1 ] làm khoá bí mật 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: Chọn một số ngẫu nhiên k, 2 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 ). Thuật toán kiểm tra chữ ký Người dùng B kiểm tra chữ ký (r, s ) trên thông điệp m theo các bước sau: Kiểm tra r và s có là các số tự nhiên trong khoảng [ 2, n-1 ] không. Tính w = s-1 mod n. Tính u1 = mw mod n và u2 = rw mod n. Tính X = u1G + u2Q = (xX, yX). Nếu X = O thì phủ nhận chữ ký. Ngược lại tính v = xX mod n. Chữ ký chỉ được chấp nhận nếu v = r. 4.1.2. Độ an toàn của sơ đồ chữ ký ECDSA Các hệ mã hoá đường cong elliptic đầu tiên được phát minh năm 1985 bởi Neal Kobliz và Victor Miller. Tuy nhiên sơ đồ chữ ký ECDSA do Scott Vanstone đưa ra năm 1992, được chấp nhận là chuẩn ISO vào năm 1998, là chuẩn ANSI vào năm 1999, và là chuẩn IEEE vào năm 2000. Độ an toàn của sơ đồ ký ECDSA dựa trên bài toán logarit rời rạc đường cong elliptic. Cho đến nay độ an toàn của các hệ mã hoá đường cong elliptic đã được chỉ ra là rất an toàn và hiệu quả. Đối với bài toán logarit rời rạc đường cong elliptic thì có nhiều thuật toán giải nó. Tuy nhiên chưa có thuật toán nào có độ phức tạp tính toán trong