Tài liệu Nghiên cứu chữ ký số bội và ứng dụng trong thương mại điện tử

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ DƯƠNG THỊ MAI THƯƠNG NGHIÊN CỨU CHỮ KÝ SỐ BỘI VÀ ỨNG DỤNG TRONG THƯƠNG MẠI ĐIỆN TỬ LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN THÁI NGUYÊN, 2013 2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ DƯƠNG THỊ MAI THƯƠNG NGHIÊN CỨU CHỮ KÝ SỐ BỘI VÀ ỨNG DỤNG TRONG THƯƠNG MẠI ĐIỆN TỬ Nghành: Công nghệ thông tin Chuyên ngành: Công nghệ phần mềm Mã số: 60 48 10 LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS TRỊNH NHẬT TIẾN THÁI NGUYÊN, 2013 4 MỤC LỤC Trang phụ bìa ……………………………………………………………………………………..1 Lời cam đoan………………………………………………………………………………………2 Mục lục…………………………………………………………………………………………….3 Danh mục bảng biểu……………………………………………………………………………….5 Danh mục hình vẽ………………………………………………………………………………….6 1. Chương 1: CƠ SỞ LÝ THUYẾT ........................................................................................ 7 1.1 CƠ SỞ TOÁN HỌC ......................................................................................................... 10 1.1.1 Nhóm, vành, trường ............................................................................................... 10 1.1.1.1 Nhóm ................................................................................................................. 10 1.1.1.2 Vành .................................................................................................................. 10 1.1.1.3 Trường ............................................................................................................... 10 1.1.2 Lý thuyết đường cong Elliptic................................................................................ 13 1.1.2.1 Công thức Weierstrasse và đường cong elliptic ................................................ 13 1.1.2.2 Các phép toán trên đường cong Elliptic ............................................................ 14 1.1.2.3 Bài toán Logarith rời rạc trên đường cong elliptic (ECDLP): ........................... 16 1.2 HỆ MẬT TRÊN ĐƯỜNG CONG ELLIPTIC ................................................................... 17 1.2.1 Cách nhúng bản rõ lên đường cong Elliptic ........................................................... 17 1.2.1.1 Nhúng (Imbeding) ............................................................................................. 17 1.2.1.2 Mạt nạ (Mask) ................................................................................................... 18 1.2.2 Các hệ mã trênđường cong elliptic (ECC) ............................................................. 18 1.2.2.1 Hệ mã hóa “tựa” Elgamal .................................................................................. 18 1.2.2.2 Hệ mã hóa Menezes-Vanstone .......................................................................... 18 1.2.3 Trao đổi khoá theo phương pháp Diffie-Hellman sử dụng lý thuyết đường cong elliptic (ECDH) .................................................................................................................... 19 1.2.3.1 Mô hình trao đổi khoá Diffie-Hellman. ............................................................. 19 1.2.3.2 Mô hình trao đổi khoá Elliptic Curve Diffie- Hellman ..................................... 19 1.2.4 Lựa chọn đường cong Elliptic phù hợp .................................................................. 19 1.2.5 Hàm băm ................................................................................................................ 22 1.2.5.1 Tổng quan về hàm băm ..................................................................................... 22 1.2.5.2 Thuật toán băm SHA-1 ...................................................................................... 23 2. Chương 2 : CHỮ KÝ SỐ BỘI TRÊN ĐƯỜNG CONG ELLIPTIC ............................. 27 2.1 GIỚI THIỆU VỀ CHỮ KÝ SỐ......................................................................................... 27 2.1.1 Khái niệm về chữ ký số .......................................................................................... 27 2.1.2 Hoạt động của chữ ký số ........................................................................................ 27 5 2.1.2.1 Mô hình tổng quát ............................................................................................. 27 2.1.2.2 So sánh giữa các phương pháp mã hóa sử dụng khoá công khai ...................... 30 2.2 SƠ ĐỒ CHỮ KÝ SỐ BỘI TRÊN ĐƯỜNG CONG ELLIPTIC ........................................ 33 2.2.1 Khởi tạo tham số công khai. ................................................................................... 34 2.2.2 Lược đồ chữ ký bội ngang hàng ............................................................................. 34 2.2.3 Lược đồ chữ ký bội tuần tự .................................................................................... 39 3. Chương 3 ỨNG DỤNG CHỮ KÝ SỐ BỘI TRONG THƯƠNG MẠI ĐIỆN TỬ...... 43 3.1 TỔNG QUAN VỀ THƯƠNG MẠI ĐIỆN TỬ ................................................................. 43 3.1.1 Khái niệm thương mại điện tử................................................................................ 43 3.1.2 Vai trò và tác động của TMĐT .............................................................................. 43 3.1.3 Các mô hình TMĐT ............................................................................................... 44 3.1.4 Đặc trưng của TMĐT ............................................................................................. 45 3.2 ỨNG DỤNG CHỮ KÝ SỐ BỘI TRONG THƯƠNG MẠI ĐIỆN TỬ (TMĐT)................. 45 3.2.1 Một số bài toán đặc trưng trong TMĐT ................................................................. 45 3.2.2 Bài toán trong thỏa thuận và ký kết hợp đồng ....................................................... 46 3.2.2.1 Bảo đảm tính toàn vẹn thông tin hợp đồng trực tuyến ...................................... 46 3.2.2.2 Bảo đảm tính xác thực ....................................................................................... 47 3.2.2.3 Chống chối bỏ hợp đồng giao dịch .................................................................... 48 3.2.3 Ứng dụng chữ ký số bội giải quyết một số bài toán trong thỏa thuận và ký kết hợp đồng kinh doanh ............................................................................................................ 49 3.2.3.1 Bài toán bảo đảm tính toàn vẹn thông tin hợp đồng (biên bản) trực tuyến ....... 50 3.2.3.2 Bảo đảm tính xác thực ....................................................................................... 52 3.2.3.3 Chống chối bỏ hợp đồng giao dịch .................................................................... 53 4. Chương 4: THỬ NGHIỆM CHƯƠNG TRÌNH CHỮ KÝ SỐ BỘI TRÊN ĐƯỜNG CONG ELLIPTIC ....................................................................................................................... 55 4.1 CẤU HÌNH HỆ THỐNG ................................................................................................. 55 4.1.1 C u hình phần cứng................................................................................................ 55 4.1.2 C u hình phần mềm................................................................................................ 55 4.2 CÁC THÀNH PHẦN CỦA CHƯƠNG TRÌNH ................................................................ 56 4.2.1 Khởi tạo và thực hiện các phép toán trên đường cong Elliptic .............................. 56 4.2.2 Tạo khóa ................................................................................................................. 56 4.2.3 Tạo chữ ký bội........................................................................................................ 56 4.2.4 Xác thực chữ ký bội ............................................................................................... 57 4.3 CHƯƠNG TRÌNH............................................................................................................ 58 4.3.1 Lược đồ chữ ký bội ngang hàng ............................................................................. 58 4.3.2 Lược đồ chữ ký bội tuần tự .................................................................................... 59 4.4 HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH ................................................................. 60 4.4.1 Chương trình lược đồ chữ ký số bội ngang hàng ................................................... 61 4.4.2 Chương trình lược đồ chữ ký số bội tuần tự .......................................................... 63 6 DANH MỤC BẢNG BIỂU Bảng 1.1 NIST đề xu t các đường cong cho trường nguyên tố………….......... 21 Bảng 1.2 So sánh đặc điểm của các thuật toán SHA-n………………….......... 26 Bảng 2.1 So sánh kích thước khoá RSA và ECC với cùng mức độ an toàn…… 32 Bảng 2.2 Bảng so sánh kích thước khóa của thuật toán RSA và ECC………… 33 Bảng 2.3 So sánh mức độ bảo mật giữa RSA và ECC…………………………. 33 Bảng 2.4 Bảng so sánh thời gian thực hiện thuật toán RSA và ECC………….. 33 Bảng 2.5 Bảng so sánh kích thước khóa và chi phí giải mã của thuật toán RSA và ECC………………………………………………………………………….. 34 Bảng 4.1. Các chương trình con khởi tạo và thực hiện các phép toán trên đường cong Elliptic cho lược đồ ngang hàng………………………………….. 75 7 DANH MỤC HÌNH VẼ Hình 1.1 Phép cộng 2 điểm P + Q = R…………………………………………………... 14 Hình 1.2 Phép cộng P với chính nó P + P = 2P…………………………………………. 15 Hình 1.3 Quá trình băm một bản tin…………………………………………………….. 24 Hình 1.4 Quá trình băm một khối ………………………………………………………. 25 Hình 2.1 Hoạt động của hệ thống chữ ký số……………………………………………. 29 Hình 2.2 Quá trình tạo chữ ký………………………………………………………….. 30 Hình 2.3 Quá trình xác thực chữ ký…………………………………………………….. 31 Hình 2.4 Thuật toán ký trên bản rõ D của lược đồ chữ ký bội ngang hàng……………. 41 Hình 2.5 Thuật toán ký trên bản rõ D của lược đồ chữ ký bội tuần tự…………………. 46 Hình 3.1 Mô hình thanh toán…………………………………………………………... 60 Hình 3.2 Mẫu biên bản thỏa thuận kinh doanh………………………………………….. 66 Hình 3.3 Mẫu phiếu xu t kho…………………………………………………………… 67 Hình 4.1. Chương trình mô phỏng lược đồ chữ k bội ngang hàng…………………….. Hình 4.2. Chương trình mô phỏng lược đồ chữ k bội tuần tự…………………………. Hình 4.3. Khởi tạo chương trình chữ k bội ngang hàng……………………………… Hình 4.4. Tạo khóa bí mật và công khai……………………………………………….. Hình 4.5. Tạo chữ k bội ngang hàng…………………………………………………. Hình 4.6. Xác thực chữ k bội ngang hàng……………………………………………. Hình 4.7. Khởi tạo chương trình và khởi tạo khóa bí mật và công khai……………… Hình 4.8. Tạo và xác thực chữ k bội tuần tự trong trường hợp đúng…………………. Hình 4.9. Tạo và xác thực chữ k bội tuần tự trong trường hợp sai…………………… . 1. 2. MỞ ĐẦU 74 8 Ngày nay, sự phát triển và phồn vinh của một nền kinh tế không còn chỉ dựa vào nguồn tài nguyên thiên nhiên và nguồn lao động, mà ở mức độ lớn được quyết định bởi trình độ công nghệ thông tin và tri thức sáng tạo. Cùng với xu thế đó, thương mại điện tử (TMĐT) xu t hiện đã làm thay đổi bộ mặt kinh tế thế giới bởi những ảnh hưởng to lớn của mình. Cùng với sự phát triển của TMĐT, chữ ký số được tạo ra để cải thiện các khiếm khuyết của những hệ thống xác thực ra đời trước đó. Nó cung c p cho khách hàng nhu cầu đánh giá, yêu cầu bảo mật như toàn vẹn dữ liệu và chống từ chối cũng đều hết sức c p thiết. Cơ sở hạ tầng chủ yếu để xây dựng hệ thống chữ ký số là các thuật toán mã hóa công khai (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) và hàm băm mật mã. Từ năm 1997, các hệ mật trên đường cong elliptic (Elliptic Curve Cryptography - ECC) thu hút sự quan tâm của các chuyên gia mật mã. Tính bảo mật của hệ thống mã hoá 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ố. 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 luỹ thừa [4,5,11,12]. Chính vì vậy các hệ mật được xây dựng trên đường cong Elliptic thực sự làm hài lòng các nhà nghiên cứu do tính nhỏ gọn của khoá, yêu cầu tính toán không nhiều và đặc biệt là có thể triển khai trên các hệ thống nhỏ với sức tính toán yếu, như các thiết bị cầm tay. Đó là những tính ch t và ưu thế vượt trội của ECC so với các hệ mật khác. Các lý thuyết toán học nền tảng của đường cong Elliptic được các nhà khoa học áp dụng khá hiệu quả vào lĩnh vực mã hóa, bảo mật (ECC). Các kết quả nghiên cứu đã được sử dụng trong quy trình mã hóa dữ liệu, trao đổi khoá và chữ ký số. Trong phạm vi luận án tôi xin giới thiệu sơ đồ chữ ký số bội dựa trên đường cong Elliptic Ngày nay chữ ký số [14,15,16] có thể phân loại thành hai lớp chính: chữ ký đơn và chữ ký bội. Chữ ký số đơn được sử dụng trong trường hợp chỉ một người có thẩm quyền ký xác nhận vào một văn bản, trong khi đó chữ ký bội là trường hợp một nhóm người có thẩm quyền cùng hợp tác ký vào một văn bản. Để thực hiện chữ ký bội trên một đối tượng thì có thể sử dụng n chữ ký cá nhân của mỗi người (giả sử nhóm gồm n người hoặc sử dụng một chữ ký đại diện cho cả nhóm người đó. Việc sử dụng n chữ ký cá nhân cho đối tượng sẽ làm cho chữ ký dài, v n đề xác thực n chứ ký đơn cũng m t thời gian và phức tạp, không phù hợp với các hệ thống nhỏ, yêu cầu tốc độ xử lý cao. Chữ ký bội là phương pháp tạo ra chữ ký số có độ dài không đổi, không phụ thuộc vào số lượng người ký mà vẫn đảm bảo độ tin cậy và tính pháp lý. Năm 2004 Chen [7] đã đưa ra lược đồ chữ ký bội dựa trên đường cong Elliptic, ý tưởng chính của lược đồ là kết hợp tính ch t khó giải của bài toán logarit rời rạc trên đường cong elliptic với hàm băm một chiều để đưa ra chữ ký bội đại diện cho một 9 nhóm người hay tổ chức. Chỉ có một chữ ký bội duy nh t được tạo ra bởi t t cả các thành viên trong nhóm (các thành viên có vai trò như nhau) với các khóa riêng của từng thành viên, không có khả năng tạo ra chữ ký bội nếu như không có đủ số lượng thành viên. Chữ ký bội có độ dài không đổi, không phụ thuộc vào số lượng người ký. Chữ ký bội được xác thực nhờ khóa công khai chung của cả nhóm, việc xác thực đơn giản như đối với chữ ký đơn. Tuy nhiên Dou Liu và Ping Luo [8] đã chỉ ra rằng trong lược đồ của Chen sẽ không an toàn nếu như một thành viên luôn luôn là người ký cuối cùng của nhóm. Từ lược đồ do Chen đưa ra, năm 2010 Hemlal Sahu và Birendra Kumar Sharma [10] đã phát triển lược đồ chữ ký bội cho một nhóm thành viên có vai trò khác nhau và đã được xác định thứ tự từ trước, lược đồ này đã khắc phục được lỗ hổng bảo mật so với lược đồ của Chen, nhưng lại không đảm bảo được thứ tự đã được định trước. Trên cơ sở những phân tích trên, được sự định hướng và chỉ bảo của PGS.TS Trịnh Nhật Tiến tôi lựa chọn đề tài: “Nghiên cứu chữ ký số bội và ứng dụng trong thương mại điện tử” làm luận văn tốt nghiệp của mình. Luận văn gồm một số nội dung chính như sau: Chương 1: Cơ sở lý thuyết - trình bày về cơ sở toán học của hệ mật mã, đặc biệt đi sâu vào phân tích hệ mật mã trên đường cong Elliptic. Chương 2: Chữ ký số bội trên đường cong Elliptic – nội dung chương giới thiệu tổng quan về chữ ký số bội, đề xu t hai lược đồ chữ ký số bội ngang hàng và tuần tự trên đường cong Elliptic. Chương 3: Ứng dụng chữ ký số bội trong TMĐT – đưa ra khái niệm, vai trò và các bài toán ứng dụng chữ ký số trong TMĐT, giải quyết bài toán thỏa thuận hợp đồng kinh doanh bằng chữ ký số bội ngang hàng và tuần tự trên đường cong Elliptic (đã được đề xuất ở chương 2). Chương 4: Thử nghiệm chương trình chữ ký số bội trên đường cong Elliptic – chương này sử dụng ngôn ngữ lập trình Matlab mô phỏng và chứng minh tính đúng đắn của hai lược đồ chữ ký số bội ngang hàng và tuần tự trên đường cong Elliptic. 10 3. Chương 1: CƠ SỞ LÝ THUYẾT 1.1 CƠ SỞ TOÁN HỌC 1.1.1 Nhóm, vành, trường 1.1.1.1 Nhóm Nhóm là c u trúc bao gồm tập G và toán tử hai ngôi trường G. Với a,b  G, a b G được định nghĩa như sau: 1. a (b c)=(a b) c với mọi a,b,c  G 2. Tồn tại e  G thoả mãn e a=a e=a với mọi a G, (e được gọi là phần tử trung hoà). 3. Với mỗi a  G, tồn tại một phần tử b G thoả mãn b a=a b=e (b là duy nh t và được gọi là phần tử nghịch đảo của a) Ký hiệu là nhóm nhân và là nhóm cộng. Trong nhóm cộng, phần tử trung hoà là 0 và phần tử nghịch đảo của a là –a. Trong nhóm nhân, phần tử trung hoà là 1 và phần tử nghịch đảo của a la a-1. được gọi là nhóm abel nếu a b=b a với mọi a, b thuộc G. Nếu là nhóm hữu hạn thì số phần tử của được gọi là bậc của G và ký hiệu là |G|. Bậc của phần tử a  G là số nguyên dương nhỏ nh t n thỏa mãn an = 1. Ở đây, trong nhóm nhân an được hiểu là a.a...a (n lần), còn trong nhóm cộng là a+a+...+a (n lần). Trong nhóm nhân với mọi phần tử thuộc nhóm thì n luôn tồn tại. Nếu a  G có bậc m thì H = {ak | k  Z } là nhóm con của G và có bậc m. Nếu G có một phần tử a có bậc n = |G| thì G = {ak | k  Z} và G được gọi là một nhóm cylic, a được gọi là phần tử sinh của G. Ví dụ, tập hợp Zn = {0, 1, 2,…, n - 1} là một nhóm cylic bậc n với toán tử cộng modulo n. 1.1.1.2 Vành Vành là tập R với 2 toán tử cộng (+) và nhân (.) với các điều kiện sau: 1./ + , R là nhóm Abel. 2./ a . (b . c) = (a . b) . c với mọi a, b, c ∈ R. 3./ a . (b + c) = a . b + a . c và (a + b) . c = a . c + b . c với mọi a, b, c ∈ R. 1.1.1.3 Trường 11 Trường F là vành với phần tử đơn vị e ≠ 0 và F* = {a ∈F | a ≠ 0 } là một nhóm nhân. Vành Zp là một trường khi và chỉ khi p là số nguyên tố. 1./ Trường hữu hạn  Khái niệm trường hữu hạn: Trường hữu hạn là khái niệm trừu tượng về hệ thống số có liên quan với nhau (giống như hệ thống số hữu tỷ Q, hệ số thực R, hệ số phức C) và các thuộc tính cơ bản của chúng. Chúng bao gồm tập các phần tử F và 2 toán tử cộng (+) và nhân (.) thoả mãn:  (F, +) là nhóm abel với phần tử trung hoà 0.  (F\ {0}, .) là nhóm abel với phần tử trung hoà 1.  Tuân thủ luật: (a+b).c=a.c+b.c với mọi a,b,c thuộc F Nếu tập F là hữu hạn thì trường được gọi là trường hữu hạn.  Các toán tử của trường. Trường F được trang bị với 2 toán tử, cộng và nhân.  Phép trừ các phần tử của trường được định nghĩa thông qua phép cộng: cho a, b ∈ F, a-b=a+(-b) trong đó –b là phần tử phủ định của b trong F thoả mãn: b+(-b)=0.  Tương tự, phép chia phần tử của trường được định nghĩa thông qua phép nhân: cho a, b ∈ F, b≠0, a/b=a.b-1 với b-1 là phần tử nghịch đảo của b thoả mãn b.b-1=1.  Các phép toán và khái niệm liên quan. Bậc của một trường hữu hạn: Là số phần tử của trường. Nếu tồn tại trường hữu hạn F có bậc q nếu và chỉ nếu q là số mũ nguyên tố, tức q=pm với p là số nguyên tố (được gọi là đặc trưng của F, m là số nguyên dương). o Nếu m=1 thì F được gọi là trường nguyên tố. o Nếu m>=2 thì F được gọi là trường mở rộng. Với b t ký số có mũ nguyên tố q nào, về cơ bản chỉ có một trường nguyên tố có bậc q. Một cách hình thức, điều này có nghĩa là b t cứ 2 trường hưu hạn cùng bậc q một cách c u trúc là khái niệm giống nhau nhưng nhãn được sử dụng để trình bày có thể khác nhau. Chúng ta nói hai trường hữu hạn cú cựng bậc q là đa hình, và đều ký hiệu là Fq. 2./ Trường nguyên tố (Finite fields): Cho p là số nguyên tố. Các số nguyên modul p, bao gồm tập các số {0,1,2,...,p1} với phép cộng và phép nhân được biểu diễn theo modul p, là một trường 12 nguyên tố bậc p. Trường này được ký hiệu là Fp và gọi p là modul của Fp. Với b t kỳ số nguyên a nào, a mod p =r (r là phần dư thoả mãn 0<=r<=p-1) Toán tử này được gọi là reduction modul p. Ví dụ: Trường nguyên tố F29={0,1,2,…,28}  Phép cộng: 17+20=8 vì 37 mod 29=8  Phép trừ: 17-20=26 vì -3 mod 29=26  Phép nhân: 17.20=21 vì 340 mod 29=21  Nghịch đảo: 17-1=12 vì 17.12 mod 29=1 3./ Trường nhị phân (Galois fields): Trường hữu hạn bậc 2m được gọi là trường nhị phân. Theo cách này xây dựng GF(2m) ta dùng đa thức đặc trưng. Ở đây, các phần tử của GF(2m) là các đa thức nhị phân (đa thức có hệ số là phần tử của F2={0,1}) và có bậc ≤ (m-1): GF(2m) ={am-1zm-1+am-2zm-2+…+a1z+a0: ai thuộc {0,1}}. Một đa thức nhị phân bậc b t kỳ được thu nhỏ bởi đa thức thu nhỏ (reduction polynomial f(z)) (giống p trong trường nguyên tố). Phép nhân được biểu diễn theo modul f(z)- được gọi là reduction modul f(z). Ví dụ: Trường nhị nhân GF24. Các phần tử của GF24 có 16 đa thức nhị phần có bậc lớn nh t bằng 3: 0z z2 z3 z3+z2 1z z2+1z z3+1z z3+z2+1 zz z2+zz z3+zz z3+z2+z z+1z z2+z+1z z3+z+1z z3+z2+z+1 Sau đây là ví dụ về các phép toán trong trường nhị phân GF2m với modul thu nhỏ là f(z)=z4+z+1.     Phép cộng (z3+z2+1)+(z2+z+1)=z3+z Phép trừ: (z3+z2+1)-(z2+z+1)=z3+z (chú ý -1=1 trong F2, vì thế -a=a với mọi a thuộc F2m.) Phép nhân: (z3+z2+1)(z2+z+1)=z2+1 Nghịch đảo (z3+z2+1)-1=z2 vì (z3+z2+1).z2 mod (z4+z+1)=1. 3./ Trường mở rộng: Cách biểu diễn dựa trên đa thức cho trường nhị phân có thể được dùng cho t t cả các trường mở rộng như sau. Cho p là số nguyên tố và m>=2. Fp[z] là ký hiệu cho tập các đa thức biến z với hệ số thuộc Fp. Có f(z) là đa thức thu gọn bậc m thuộc Fp[z]. Các phân tử của Fpm là các đa thức trong Fp[z] có bậc <=m-1. 13 Fpm={am-1zm-1+am-2zm-2+…+a2z2+a1z+a0:ai ∈ Fp}. Phép cộng các phần tử là phép cộng đa thức với các phép toán hệ số được biểu diễn trong trường Fp. Phép nhân các phần tử của trường được biểu diễn theo đa thức modul f(z). Ví dụ: (Trường mở rộng) Cho p=251 và m=5. Đa thức không thể tối giản của F251[z] là f(z)=z5+z4+12z3+9z2+7, được xem như là đa thức rút gọn của F2515, trường hữu hạn bậc F2515. Phần tử của F2515 là đa thức trong F251[z] có bậc lớn nh t là 4. Các phép toán với a=123z4+76z2+7z+4 và b=196z4+12z3+225z2+76.     Phép cộng: a+b=68z4+12z3+50z2+7z+80. Phép trừ : a-b=178z4+239z3+102z2+7z+179. Phép nhân : a.b = 117z 4+ 151z 3+ 117z 2+ 182z + 217. Nghịch đảo: a-1 = 109z4 + 111z3 + 250z2 + 98z + 85. 1.1.2 Lý thuyết đường cong Elliptic Như ta đã biết, hệ thống khoá công cộng 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 thực tế hiện nay sử dụng phổ biến hai bài toán để giải quyết v n đề là: bài toán logarit rời rạc 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 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 vào thế kỷ 17 dưới dạng công thức: y2- x3=c với c ∈ Z. Tính bảo mật của hệ thống mã hoá 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 những 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 luỹ thừa. 1.1.2.1 Công thức Weierstrasse và đường cong elliptic 14 Gọi F là một trường hữu hạn hoặc vô hạn. Một đường cong được định nghĩa trên trường F bằng công thức Weierstrass: y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 với ai ∈ F (1.1) Đường cong elliptic trên trường F được ký hiệu E(F). Số lượng các điểm nguyên trường E ký hiệu #E(F) hay #E. Đối với từng trường khác nhau, công thức Weierstrass có thể được biến đổi và đơn giản hoá thành các dạng khác nhau. Một đường cong elliptic là tập hợp các điểm thoả mãn công thức trên với (x, y) ∈ F và điểm vô cùng (ký hiệu O - hay còn gọi là phần tử không). Trong mật mã học, chúng ta chỉ xét các trường hữu hạn. Hai trường được xét là Fp với p là số nguyên tố và Fqm với các phần tử q = pr.  Đường cong Elliptic trên trường nguyên tố hữu hạn Fp Xét trường Fp (p nguyên tố, p > 3) với công thức đổi biến như sau: x  y  a x  a3 a2  y  1 , y 3 2 Thay vào phương trình (3.1) khi đó ta rút ra được định nghĩa sau:  Định nghĩa: Một đường cong Elliptic E trên trường hữu hạn Fp được cho bởi phương trình dạng: y 2  x 3  ax  b với a,b ∈ Fp và  (4a 3  27b 2 )  0 (1.2) Trong phương trình trên, d u “=” được hiểu là “”. Trong toàn bộ luận văn này, quy ước viết ngắn gọn “” là “=”.  Đường cong Elliptic trên trường nhị phân hữu hạn GF(2m) Xét trường GF(2m) có đặc số khác 2. Có thể thực hiện phép đổi biến như sau: a12 a 4  a32 a3 3  a1 y  x  a x  , y  a1 a13 2 1  Định nghĩa: Đường cong elliptic E trên trường hữu hạn GF2m được cho bởi phương trình dạng: y2 + xy = x3 + ax2 + b với a, b ∈ GF2m (1.3) 1.1.2.2 Các phép toán trên đường cong Elliptic Giả sử E là đường cong elliptic trên trường Fp hoặc GF2m và P, Q là 2 điểm trên E. Xét các phép toán sau trên E: 15  Phần tử không: Ký hiệu là O. Nếu P là điểm O thì -P cũng là O. Với mọi điểm Q ta định nghĩa O + Q bằng Q.  Phần tử nghịch đảo: Trong Fp, định nghĩa phần tử nghịch đảo của P = (x, y) là -P = (x, -y). Nếu Q = -P thì P+ Q = O. Trong trường F2m ta định nghĩa -P = (x, x+y).  P + Q: Nếu P  Q, gọi đường thẳng l = P Q giao với E tại một điểm -R. Khi đó P + Q bằng P + Q bằng R. Với P, Q, R có tọa độ như trên hình vẽ ta có các công thức sau: Hình vẽ 1.1 Phép cộng 2 điểm P + Q = R 2 y y  y y  o Trong Fp: x3   2 1   x1  x2 và y3   2 1 x1  x3   y1 .  x2  x1   x 2  x1  m o Trong F2 :  y  y2 x3   1  x1  x2 2  y  y2   1  x1  x2  a x1  x2  y y  2 x1  x3   x3  y1 và y3   1 x  x 2   1 .  2P: l là tiếp tuyến với E tại P, -R là giao điểm của l với E, định nghĩa 2P =R. Với P, R có tọa độ như trên hình vẽ ta cú cỏc công thức sau: Hình vẽ 1.2 Phép cộng P với chính nó P + P = 2P = R 16 2 o  3x12  a   3x12  a      Trong Fp: x3     2 x1 và y3   2 y x1  x3   y1 . 2 y 1 1     o Trong F2m: x3  x12   y1  b 2   x3  x3 . y  x  x  và 3 1 1  x x12 1    kP: kP ∈ E(Zp) với k là số nguyên được tính bằng cách cộng P với chính nó k lần liên tiếp. Để tăng tốc độ tính toán có thể áp dụng thuật toán “nhân đôi và cộng”. 1.1.2.3 Bài toán Logarith rời rạc trên đường cong elliptic (ECDLP): Cho E là một đường cong elliptic và P ∈ E là một điểm có bậc n. Cho Q ∈ E, tìm số nguyên dương m (2 ≤ m ≤ n-2) thoả mãn công thức Q=mP. Hiện nay chưa có thuật toán nào được xem là hiệu quả để giải bài toán này. Để giải bài toán logarit rời rạc trên đường cong ellipse, cần kiểm tra t t cả các giá trị m ∈ [2, n-2]. Nếu điểm P được chọn lựa cẩn thận với n r t lớn thì việc giải ECDLP xem như không khả thi. Độ an toàn của hệ mật mã dựa trên E phụ thuộc vào độ khó của ECDLP. ECDLP được coi là khó hơn DLP vì những thuật toán tốt nh t để giải DLP không hiệu quả khi áp dụng cho ECDLP.  Đếm số điểm của đườ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à Fđườ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 q . Từ định lý Hasse suy ra #E(Fq) = q + 1 – t trong đó |t|  2 q .  Định nghĩa bậc của đường cong Elliptic: Bậc của một đường cong elliptic là số điểm của đường cong đó. Bậc của điểm G thuộc E là số k sao cho kG = O; khi k = #E(Fq ) thì G là điểm cơ sở của điểm cơ sở của E.  Tính chất đồng cấu của đường cong elliptic Xét đường cong elliptic trên trường Fq, E(Fq) là nhóm Abel. Vì vậy, E(Fq) đồng c u với đồng c u với Z n x Z n trong đó n2 chia hết cho n1 và q - 1 với các số n1 và n2 1 2 duy nh t. Zn là ký hiệu của nhóm cyclic bậc n. Nếu n2 = 1 thì E(Fq) là cyclic. Trong trường hợp này E(Fq) là đồng c u với Z n . Khi đó, tồn tại một điểm G ∈ E(Fq) thỏa 1 mãn E(Fq) = {kG | 0  k  n1  1 }; điểm G được gọi là phần tử sinh của E(Fq). 17 Ví dụ: Xét đường cong elliptic E trên trường Fp với p = 23 có phương trình: y2 = x3 + x + 4. 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à một phần tử sinh của E(F23). 1.2 HỆ MẬT TRÊN ĐƯỜNG CONG ELLIPTIC Các lý thuyết toán học nền tảng của đường cong elliptic được các nhà khoa học áp dụng khá hiệu quả vào lĩnh vực mã hóa, bảo mật. Các kết quả nghiên cứu đã được sử dụng trong quy trình mã hóa dữ liệu, trao đổi khoá và chữ ký điện tử. 1.2.1 Cách nhúng bản rõ lên đường cong Elliptic Nhúng một bản rõ lên đường cong (E) là biểu diễn lại bản rõ như là một điểm hoặc toạ độ của 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à nhúng (imbeding) và mặt nạ (mask). 1.2.1.1 Nhúng (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 (3.2) và giả sử m là số nguyên thỏa mãn: 0 ≤ m ≤ p/1000 - 1. - - Thêm 3 chữ số vào m được x thỏa mãn: 1000m ≤ x ≤ 1000(m+1) < p. 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ố chính phương trong Zp và y (với f(x) = y2 mod p ) thỏa mãn y ≠ -1 mod p. Điểm Pm được tạo thành khi nhúng m lên E là: Pm  ( x, f ( x)) . Có thể dễ dàng khôi phục lại m từ Pm  E (Z p ) 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ố 0 ≤ xw ≤ Nl tạo thành một ánh xạ: w  (a0 a1 ...al 1 )  xw  a0 N l 1  a1 N l 2    al 2 N  al 1 , - 0  xw  N t 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, j ≥ 0, 18 - x Bước 3: Khôi phục lại khối bản rõ từ Pw bằng cách tính x w    . k  1.2.1.2 Mạt nạ (Mask) Để biểu diễn lại bản rõ dạng (m1, m2) có thể áp dụng phương pháp mask 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. Giả sử có điểm G  E có tọa độ (xG, yG) thì Pm = (m1xG, m2yG). 1.2.2 Các hệ mã trênđường cong elliptic (ECC) 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óa trên trường số nguyên, thay vào đó là các điểm trên đường cong elliptic. Phụ thuộc vào cách nhúng thông báo trên đường cong mà ta có các hệ mã sau: 1.2.2.1 Hệ mã hóa “tựa” Elgamal Hệ Elgamal làm việc với nhóm cyclic hữu hạn, yêu cầu biểu diễn (nhúng -dùng embedding) thông điệp m như một điểm trên đường cong. Ta có trường số Zp và đường cong elliptic E trên Zp là E(Zp) cùng điểm cơ sở G ∈ E. Mỗi người dùng sẽ chọn một số d là khoá bí mật, dG làm khoá 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 Pm ∈ E. Khi đó cô ta phải mã hóa Pm . Ký hiệu d là khoá bí mật của Bob, vì vậy khoá công khai của Bob là Q= dG. 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) = (kG,Pm+kQ) Để giải mã Bob tính C2-dC1= Pm+kQ-d(kG) = Pm+k(dG)-d(kG) = Pm. 1.2.2.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 mặt nạ (Masking) thay vì nhúng (Imbeding) khi biểu diễn bản rõ thành điểm trên E. E là đườ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 ECDLP là khó. Zp, E(Zp) và điểm G ∈ E là công khai. Mỗi người dùng chọn một số ngẫu nhiên d làm khoá bí mật và khoá công khai là dG. Giả sử Alice cần gửi thông điệp M=(x1, x2) ∈ Zp*/Zp* cho Bob. Giả sử d là khoá bí mật của Bob. Alice chọn số ngẫu nhiên k ∈Z|H| và gửi: (y0,y1,y2) = (kG,ax1 mod p,bx2 mod p) với (a,b) = k(dG) Để giải mã, Bob tính: (y1a-1 mod p, y2b-1 mod p ) = (x1,x2) với dy0=(a,b) Chứng minh: y0=kG, Bob có thể tính dy0 = d(kG)=(a,b) vì vậy: y1a-1= (ax1)a-1= x1 mod p 19 y2b-1= (bx2)b-1= x2 mod p. (dpcm). 1.2.3 Trao đổi khoá theo phương pháp Diffie-Hellman sử dụng lý thuyết đường cong elliptic (ECDH) 1.2.3.1 Mô hình trao đổi khoá Diffie-Hellman. Năm 1976, Whitfield Diffe và Martin Hellman đã đưa ra giao thức để trao đổi các giá trị khoá quy ước giữa các đối tác trên đường truyền có độ bảo mật trung bình. Giao thức này dựa trên nguyên lý của bài toán logarit rời rạc trên trường số nguyên hữu hạn. Các thao tác thực hiện trao đổi khoá Diffie-Hellman giữa hai đối tác A và B như sau:  A và B thống nh t các giá trị g và số nguyên p < g.  A chọn số ngẫu nhiên m, tính QA=gm và gửi QA cho A.  B chọn một số ngẫu nhiên n. B tính giá trị QB= gn và gửi QB cho A.  A nhận QB và tính k = (QB)m = gn*m.  B nhận được QA và tính k = (QA)n = gn*m. k chính là giá trị bí mật được qui ước chung. 1.2.3.2 Mô hình trao đổi khoá Elliptic Curve Diffie- Hellman Mô hình ECDH tương tự mô hình trao đổi khoá Diffie-Hellman. ECDH cũng dựa trên nguyên lý của bài toán logarit rời rạc nhưng áp dụng trên EC. Mô hình này dùng để thiết lập một hay nhiều khoá quy ước chung giữa hai đối tác A và B. Các thao tác trao đổi khoá bằng ECDH được thực hiện như sau:  A và B thống nh t các tham số sẽ sử dụng như: đường cong E, điểm cơ sở P(x,y).  A chọn một giá trị m ngẫu nhiên, tính QA = mP và gửi QA cho B  B chọn một giá trị n ngẫu nhiên, tính QB = nP và gửi QB cho A  A nhận được QB và tính G = m n P  B nhận được QA và tính G = m n P Giá trị điểm G chính là giá trị bí mật qui ước chung. Giả sử có một người C t n công vào đường truyền và l y được các giá trị QA, QB, E, P thì C cần tìm được m hoặc n để tìm G=m n P. Điều này chính là giải bài toán logarit rời rạc trên EC. Bài toán này đòi hỏi chi phí tính toán tương đương với sử dụng thuật toán vét can trên EC. 1.2.4 Lựa chọn đường cong Elliptic phù hợp Để ECDLP trên E(Fq) là khó giải thì cần lựa chọn E và q thích hợp. Độ an toàn của hệ mật mã dựa trên E phụ thuộc vào độ khó của ECDLP. ECDLP được coi là khó 20 hơn DLP vì những thuật toán tốt nh t để giải DLP không hiệu quả khi áp dụng cho ECDLP. Vì thế việc chọn một đường cong elliptic có ảnh hưởng đến tốc độ, tính hiệu quả, độ dài khóa 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ở G  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. Có một số phương pháp để lựa chọn các đường cong elliptic. Phương pháp tự nhiên nh t là chọn ngẫu nhiên. Chọn ngẫu nhiên một đường cong elliptic E trên trường K và một điểm cơ sở P ∈ E. K được chọn và cố định trước. Phương pháp chọn ngẫu nhiên Koblitz cho các đường cong elliptic trên trường Fq (với q lớn) như sau:  Phương pháp chọn ngẫu nhiên Koblitz: 1./ Chọn ngẫu nhiên 3 phần tử từ Fq là x, y, a. 2./ Tính b = y2 – (x3 + ax). 3./ Kiểm tra 4a3+27b2 ≠ 0 để đảm bảo phương trình x3 + ax + b = 0 không có nghiệm kép. 4./ Nếu điều kiện trên không thỏa mãn quay lại 1./ 5./ Đặ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ã hóa không phụ thuộc vào bài toán E 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ã hóa không phụ thuộc vào bài toán ECDLP, 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, việc lựa chọn P phù hợp là r t quan trọng.  Chuẩn FIPS 182-2 NIST đã kiến nghị 15 đường cong elliptic đáp ứng mức bảo mật cho chính phủ liên bang Hoa Kì sử dụng. Những đường cong này chia làm 3 loại:  Đường cong elliptic trên trường nguyên tố Fp;  Đường cong elliptic trên trường nhị phân F 2m; và  Đường cong elltiptic Koblitz trên trường nhị phân F2m. Chuẩn đường cong elliptic trên trường nguyên tố có các tham số: - p: Bậc của trường nguyên tố Fp S: Xâu sinh để tạo hệ số cho đường cong elliptic r: đầu ra của hàm băm SHA-1 a,b: hệ số của ECC; y2=x3+ax+b thoả mãn rb2=a3(mod p) 21 - n: bậc của điểm cơ sở P - h: cofactor - x, y: toạ độ của P Bảng 1.1 NIST đề xuất các đường cong cho trường nguyên tố P-192: p = 2192−264−1, a =−3, h = 1 S = 0x 3045AE6F C8422F64 ED579528 D38120EA E12196D5 r = 0x 3099D2BB BFCB2538 542DCD5F B078B6EF 5F3D6FE2 C745DE65 b = 0x 64210519 E59C80E7 0FA7E9AB 72243049 FEB8DEEC C146B9B1 n = 0x FFFFFFFF FFFFFFFF FFFFFFFF 99DEF836 146BC9B1 B4D22831 x = 0x 188DA80E B03090F6 7CBF20EB 43A18800 F4FF0AFD 82FF1012 y = 0x 07192B95 FFC8DA78 631011ED 6B24CDD5 73F977A1 1E794811 P-224: p = 2224−296+1, a =−3, h = 1 S = 0x BD713447 99D5C7FC DC45B59F A3B9AB8F 6A948BC5 r = 0x 5B056C7E 11DD68F4 0469EE7F 3C7A7D74 F7D12111 6506D031 218291FB b = 0x B4050A85 0C04B3AB F5413256 5044B0B7 D7BFD8BA 270B3943 2355FFB4 n = 0x FFFFFFFF FFFFFFFF FFFFFFFF FFFF16A2 E0B8F03E 13DD2945 5C5C2A3D x = 0x B70E0CBD 6BB4BF7F 321390B9 4A03C1D3 56C21122 343280D6 115C1D21 y = 0x BD376388 B5F723FB 4C22DFE6 CD4375A0 5A074764 44D58199 85007E34 P-256: p = 2256−2224+2192+296−1, a =−3, h = 1 S = 0x C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 r = 0x 7EFBA166 2985BE94 03CB055C 75D4F7E0 CE8D84A9 C5114ABC AF317768 0104FA0D b = 0x 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B n = 0x FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551 x = 0x 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296 y = 0x 4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51F5 P-384: p = 2384−2128−296+232−1, a =−3, h = 1 S = 0x A335926A A319A27A 1D00896A 6773A482 7ACDAC73 r = 0x 79D1E655 F868F02F FF48DCDE E14151DD B80643C1 406D0CA1 0DFE6FC5 2009540A 495E8042 EA5F744F 6E184667 CC722483 b = 0x B3312FA7 E23EE7E4 988E056B E3F82D19 181D9C6E FE814112 0314088F