Bài giảng Đường cong elliptic

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:42

Thêm vào BST

Báo xấu

84
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Đường cong elliptic được biên soạn nhằm trang bị cho các bạn những kiến thức về giới thiệu chung; đường cong elliptic trên trường số thực; đường cong elliptic trên trường hữu hạn; các phép toán trường hữu hạn, phép cộng, phép nhân; các bài toán kiểm tra điểm thuộc đường cong, đếm số điểm của đường cong, cộng hai điểm, nhân hai điểm, nhân nhanh; đường cong và hệ mã công khai; so sánh với RSA.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Đường cong elliptic

ĐƯỜNG CONG ELLIPTIC
I. GIỚI THIỆU 1.ĐƯỜNG CONG TRÊN TRƯỜNG SỐ THỰC 2. ĐƯỜNG CONG TRÊN TRƯỜNG HỮU HẠN
I. GIỚI THIỆU Định nghĩa: Đường cong elliptic trên trường K là tập hợp các điểm thỏa phương trình: (E):y2+a1xy+a3y=x3+a2x2+a4x+a6 (1) Với một đểm O gọi là điểm tại vô cùng. Phương trình phải thỏa điều kiện không kì dị. Nghĩa là khi viết dưới dạng F(x,y)=0 thì tại mọi điểm (x,y) có ít nhất một trong các đạo hàm riêng khác 0.
• Điều kiện không kì dị nghĩa là nếu xét tập các điểm trên một đường cong, thì dường cong đó không có điểm bội. • Hay nếu biểu diễn y2 như một đa thứ bậc 3 của x thì đa thức không có nghiệm bội.
1.ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG SỐTHỰC • Trong những trường đặc số khác 2,3 phương trình (1) có thể đưa dạng Weierstrass về: (E):y2=4x3+a4x+a6 Biệt thức: Δ=16(4a43+27a62) Điều kiện không kì dị(không có điểm bội): 4a43+27a62≠0
(E):y2+y=x3x (E): y2=x3+1/4*x+5/4
(E):y^2=x^3+2*x+1 (E):y^2=x^33*x+2
2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN Các điểmcủa đường cong (E) KH: E(Fq) trên trường Fq có q phần tử thỏa mãn phương trình trong Fq: y2=4x3+a4x+a6 Ví dụ: (E): y2=x3+1 (a1=0, a6=1) trên F5 Các điểm thuộc đường cong: (0,1),(0,1),(2,2)(2,2),(4,0)
II. CÁC PHÉP TOÁN • 1. TRƯỜNG HỮU HẠN • 2. PHÉP CỘNG • 3.PHÉP NHÂN
1.TRƯỜNG HỮU HẠN • Trường là tập K với hai phép toán cộng (+) và nhân(*) thỏa: • K là nhóm aben với phép toán cộng có phần tử trung hòa (của phép cộng) • K\{O} là nhóm aben với phép táon nhân có phần tử đơn vị • Với mọi a,b,c thuộc K ta có:c(a+b)=ca+cb Và (a+b)c=ca+cb (luật phân phối)
• Trường có thể có vô hạn phần tử( VD: R) • Một trường được gọi là hữu hạn nếu nó có hữu hạn phần tử. VD: • ZP={0,1,…,p2,p1} Với p nguyên tố. • (Zp với phép cộng theo mod p, phép nhân theo mod p)>một trường
• Nếu p ngyên tố thì trường hữu hạn Fp là trừng gồm các phần tử từ 0 đến p1 • Nếu q=pr. Thì phần tử của trường Fq thỏa phương trình: • XqX=0 • Fq là tập nghiệm của pt này. • Phần tử của trường Fq là các đa thức
• Đặc số của trường: • K trường có phần tử đơn vị 1 với phép toán nhân. Khi đó đặc số của K được định nghĩa là: sốn n nhỏ nhất sao cho: • 1+1+…+1=0 (n lần) • KÝ HIỆU: char K=n • Nếu không tồn tại số n như vậy , nghĩa là 1+1+….+1≠ 0 ta cộng thêm “1” bao nhiêu cũng được .=> đặc số bằng 0
• Bậc của a: • Với a thuộc F*q: bậc của a là số k nhỏ nhất không âm thỏa a k=1. • Bậc của a luôn là ước của q1.
• (Lecture Notes on Computer network Security by Avi Kak)
Tính chất: • P+O=O+P=P với mọi P thuộc (E) • Tồn tại –P sao cho P+P=O • Phép công :P+Q với P ≠ ±Q • Phép nhân : nP với P≠P
2. PHÉP CỘNG Đường cong elliptic trên trường số thực: Cộng hai điểm P(x1,y1) + Q(x2,y2).=(x3,y3). Ta có công thức:
• Và phép nhân: • Với:
• Trên Z(2n) (E): y2+xy=x3+ax+b • Điểm –p=(x,(x+y) • Công thức cộng hai điểm P,Q: • Với
3.PHÉP NHÂN Phép nhân ta có 2P=P+P: Phép nhân nP ta thực hiện phép cộng P n lần