Chương 1: CƠ SỞ LÝ THUYẾT 1.1 CƠ SỞ TOÁN HỌC 1.1 Nhóm, vành, trường 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. 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à). 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 <G,.
>là nhóm nhân và <G,+> 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.
> là nhóm hữu hạn thì số phần tử của <G,. > đượ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 (n lần), còn trong nhóm cộng là a+a+.
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.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.3 Trường TIEU LUAN MOI download : skknchat@gmail.com 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ố./ 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.) là nhóm abel với phần tử trung hoà 1. Tuân thủ luật: (a+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. 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./ 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,.,p- 1} với phép cộng và phép nhân được biểu diễn theo modul p, là một trường TIEU LUAN MOI download : skknchat@gmail.com 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./ 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./ 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ác phân tử của Fpm là các đa thức trong Fp[z] có bậc <=m-1. TIEU LUAN MOI download : skknchat@gmail.com 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.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 Công thức Weierstrasse và đường cong elliptic TIEU LUAN MOI download : skknchat@gmail.com 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: a2 a x a3 x y , y y 1 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: a a a a 2 2 a x 3 , y x 2 1 a13 y 1 4 3 3 a1 a1 Đị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.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: TIEU LUAN MOI download : skknchat@gmail.com 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.