Đồ án tốt nghiệp về Hệ mật đường cong elliptic

Ngày nay với sự phát triển mạnh mẽ của công nghệ thông tin, truyền thông nói chung và Internet nói riêng đã giúp cho việc trao đổi thông tin nhanh chóng, dễ dàng, E-mail cho phép người ta nhận hay gửi thư ngay trên máy tính của mình, E-business cho phép thực hiện các giao dịch trên mạn. Do vậy một vấn đề phát sinh là thông tin có thể bị trộm cắp, có thể là sai lệch, có thể giả mạo. Điều đó có thể ảnh hưởng tới các tổ chứa, các công ty hay cả một quốc gia....
Nội dung trích xuất từ tài liệu:
Đồ án tốt nghiệp về Hệ mật đường cong elliptic Đồ án tốt nghiệp Hệ mật đường cong ellipticMỞ ĐẦU Ngày nay với sự phát triển mạnh mẽ của công nghệ thông tin, truyềnthông nói chung và Internet nói riêng đã giúp cho việc trao đổi thông tinnhanh chóng, dễ dàng, E-mail cho phép người ta nhận hay gửi thư ngay trênmáy tính của mình, E-business cho phép thực hiện các giao dịch trên mạn.Do vậy một vấn đề phát sinh là thông tin có thể bị trộm cắp, có thể là sai lệch,có thể giả mạo. Điều đó có thể ảnh hưởng tới các tổ chứa, các công ty hay cảmột quốc gia. Những bí mật kinh doanh, tài chính là mục tiêu của các đối thủcạnh tranh. Những tin tức về an ninh quốc gia là mục tiêu của các tổ chức tìnhbáo trong và ngoài nước. Để giải quyết tình hình trên an toàn thông tin được đặt ra cấp thiết. Kỹthuật mật mã là một trong những giải pháp của an toàn truyên thông. Kỹ thuậtnày có từ ngàn xưa nhưng nó đơn giản, ngày nay khi có mạng máy tính ngườita dùng mật mã hiện đại. Các nhà khoa học đã phát minh ra những hệ mật mãnhằm che dấu thông tin cũng như là làm rõ chúng để tránh sự giòm ngó củanhững kẻ cố tình phá hoại như các hệ mật: RSA, Elgamal… mặc dù cũng rấtan toàn nhưng có độ dài khoá lớn nên trong một số lĩnh vực không thể ứngdụng được. Chính vì vậy người ta đã phát minh một hệ mật đó là hệ mật trên đườngcong elliptic, hệ mật này được đánh giá là hệ mật có độ bảo mật an toàn caovà hiệu quả hơn nhiều so với hệ mật công khai khác, nó đã được ứng dụngtrên nhiều lĩnh vực và được sử dụng nhiều nơi trên thế giới tuy nhiên cònmới mẻ ở Việt Nam. Trong tương lai gần Hệ mật trên đường cong Ellipticsẽ được sử dụng một cách phổ biến và thay thế những hệ mật trước nó.Đồ án tốt nghiệp Hệ mật đường cong elliptic Vì lý do đó, em đã chọn đề tài “Hệ mật đường cong elliptic” để nghiêncứu, tìm hiểu nhằm tiến tới khai thác hệ mật này phục vụ cho bảo mật thôngtin trong thực tế.Luân văn này gồm 4 chương Chương 1: Cơ sở toán học Chương 2: Hệ mật mã Chương 3: Đường cong Elliptic Chương 4: Hệ mật đường cong Elliptic Chương 5: Một vài ứng dụngNhưng trong báo cáo này em trình bày tóm tắt nội dung chính trong đềtài:”Hệ mật đường cong elliptic”.Đồ án tốt nghiệp Hệ mật đường cong elliptic CHƯƠNG 1 CƠ SỞ TOÁN HỌC1.1. Phương trình đồng dư bậc hai và thặng dư bậc hai Ta xét phương trình đồng dư bậc hai có dạng như sau: x2 ≡ a (mod n) Trong đó n là số nguyên dương, a là số nguyên với gcd(a, n) ≡ 1, và xlà ẩn số. Phương trình đó không phải bao giờ cũng có nghiệm, khi nó cónghiệm thì ta gọi a là thặng dư bậc hai mod n. Ngược lại thì a gọi là một bấtthặng dư bậc hai mod n. Tập các số nguyên nguyên tố với n được phân hoạch thành hai tập con.Tập Qn các thặng dư bậc hai mod n, và tập các bất thặng dư bậc hai mod n.Tiêu chuẩn Euler Khi p là số nguyên tố, số a là thặng dư bậc 2 mod p nếu và chỉ nếu a(p-1)/2 ≡ 1 (mod p)Ký hiệu Legendre Cho p là số nguyên tố, với p >2, số a ≥ 0 là số nguyên. Ta định nghĩa⎛a⎞⎜ ⎟ như sau:⎜ p⎟⎝ ⎠ ⎧ 0 , k h i , a ≡ 0 (m o d p )⎛a⎞ ⎪⎜ ⎟ = ⎨1, k h i , a ∈ Q p ;⎜ p⎟⎝ ⎠ ⎪ − 1, k h i , a ∉ Q p . ⎩Chú ý: ⎛a⎞+ Từ định nghĩa suy ra a là thặng dư bậc hai mod p khi và chỉ khi ⎜ ⎟ = 1 ⎜ p⎟ ⎝ ⎠+ Theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0 ta có:Đồ án tốt nghiệp Hệ mật đường cong elliptic ⎛a⎞ ⎜ ⎟ ≡ a(p-1)/2 (mod p) . ⎜ p⎟ ⎝ ⎠Legendre Symbol thoả mãn các tính chất sau: ⎛a⎞ 1. ⎜ ⎟ chỉ phụ thuộc vào đồng dư của a theo mod p. ⎜ p⎟ ⎝ ⎠ ⎛ ab ⎞ ⎛a⎞⎛b⎞ 2. ⎜ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟; ⎟ ⎜ p⎟ ⎜ p⎟ ⎝ p⎠ ⎝ ⎠⎝ ⎠ ⎛ ab 2 ⎞ ⎛a⎞ 3. b nguyên tố với p thì ⎜ ⎜ ⎟ = ⎜ ⎟; ⎟ ⎜ p⎟ ⎝ p ⎠ ⎝ ⎠ ⎛1⎞ ⎛ 1⎞ 4. ⎜ ⎟ =1 và ⎜ − ⎟ = (-1)(p-1)/2. ⎜ p⎟ ⎜ p⎟ ⎝ ⎠ ⎝ ⎠ Định lý 1: ⎛2⎞ 2 (p – 1)/8 ⎧1 p ≡ ± 1 mod 8 ⎜ ⎟ = (-1) ⎜ p⎟ = ⎨ ⎝ ⎠ ⎩−1 p ≡ ± 3 mod 8 Định lý: Gọi là luật thuận nghịch bình phương. Cho p, q là 2 số nguyên tố lẻ, khi đó: ⎧ ⎛ p⎞ ⎪− ⎜ ⎟ neu p ≡ q ≡ 3mod 4 ⎛q⎞ ⎛ p⎞ ⎪ ⎝ q ⎠ ⎜ ⎟ ⎜ p⎟ = (-1)(p-1)(q-1)/4 .⎜ ⎟ = ⎨ ...