Bài giảng Cài đặt các giao mật mã dùng đường cong elliptic trên trường hữu hạn

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

Thêm vào BST

Báo xấu

119
lượt xem 17
download

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

Mục tiêu của bài giảng Cài đặt các giao mật mã dùng đường cong elliptic trên trường hữu hạn là nhằm giúp cho các bạn có kiến thức cơ bản về đường cong elliptic; biết cách cài đặt một số giao thức mật mã dùng đường cong. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này.

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 Cài đặt các giao mật mã dùng đường cong elliptic trên trường hữu hạn

CÀI ĐẶT CÁC GIAO MẬT MÃ DÙNG ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN
Mục tiêu • Kiến thức cơ bản về đường cong elliptic • Cài đặt một số giao thức mật mã dùng đường cong
I. CÁC KIẾN THỨC LIÊN QUAN 1. TRƯỜNG HỮU HẠN 2. ĐƯỜNG CONG ELLIPTIC 3. ĐƯỜNG CONG ELLIPTIC TRÊN R 4. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG Fp 5. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG Fq
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.
II GIỚI THIỆU ĐƯỜNG CONG ELLIPTIC Đị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.
4.ĐƯỜ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=x3+2x+1 (E):y2=x33x+2
(E):y2+y=x3x (E): y2=x3+1/4*x+5/4
5. ĐƯỜ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. PHÉP CỘNG • 2.PHÉP NHÂN NHANH • 3. TƯƠNG Ứ NG MỘT SỐ VỚI MỘT ĐIỂM TRÊN CONG • ĐẾM SỐ ĐIỂM CỦA ĐƯỜNG CONG
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