arc_ngothanhhai
New Member
Download miễn phí Báo cáo Hệ mã hóa công khai RSA
Tóm nội dung báo cáo
I. Giới thiệu Trang 2
II. Hệ mã hóa công khai .Trang 3
III. Chuẩn bị toán học .Trang 5
IV. Hệ mã hóa công khai RSA .Trang 7
1. Giới thiệu
2. Cách tạo khóa
3. Mã hóa
4. Giải mã
5. Tính bảo mật
6. Quá trình tạo khóa
7. Tốc độ
8. Các cách xâm nhập
V. Chữ kí điện tử Trang 15
VI. Chương trình cài đặt thuật toán .Trang 16
VII. Nhận xét đánh giá .Trang 23
VIII. Tài liệu tham khảo .Trang 23
.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
yên chỉ chia chẵn được cho 1 và cho chính nó mà thôi. Ví dụ : 2, 3, 5, 7, 11, 13, 17, 23... 2- Khái niệm nguyên tố cùng nhau (relatively prime or coprime) Với hai số nguyên dương a và b . Ta ký hiệu GCD (a,b) : Ước chung lớn nhất của a và b ( Greatest Common Divisor) Để đơn giản ta ký hiệu GCD(a,b) =(a,b) Ví dụ : (4,6)=2 (5,6)=1 Hai số a và b gọi là nguyên tố cùng nhau khi (a,b)=1 Ví dụ : 9 và 10 nguyên tố cùng nhau vì (9,10)=13-Khái niệm modulo Với m là một số nguyên dương .Ta nói hai số nguyên a va b là đồng dư với nhau modulo m nếu m chia hết hiệu a-b ( Viết là m|(a-b) ) Ký hiệu a ≡ b ( mod m) Như vậy a ≡ b (mod m ) khi và chỉ khi tồn tại số nguyên k sao cho a = b +km Ví dụ : 13 ≡ 3 ( mod 10 ) vì 13= 3 + 1*10
4-Phi – Hàm EULER
Định nghĩa : Phi – Hàm Euler Φ(n) có giá trị tại n bằng số các số không vượt quá n và nguyên tố cùng nhau với n Ví dụ : Φ(5) = 4 , Φ(6) = 2 ,Φ(10) = 4
5-Một số định lý cơ bản Định lý Euler : nếu m là số nguyên dương và P nguyên tố cùng nhau với m thì P^Φ(m) ≡ 1 (mod m ) Vậy nếu m và p nguyên tố cùng nhau . Ta đặt s = Φ(m) thì P^s ≡ 1 (mod m) Suy ra với a= 1 + k*s Ta có : P^a ≡ P*(P^s)^k ≡ P*1^k(mod m) ≡ P (mod m) với e là số nguyên dương nguyên tố cùng nhau với s ,tức là (e,s)=1 Khi đó tồn tại một nghịch đảo d của e modulo s tức là e*d ≡ 1 (mod s) e*d = 1 + k*só Đặt E(P) ≡ C ≡ P^e(mod m) Đặt D(C) ≡ C^d (mod m) Ta thấy D(C) ≡ C^d ≡ P^e*d ≡ P^(1 + k*s )≡ P (mod m) Ví dụ : m = 10 , P = 9 ta có (10,9)=1 s = Φ(10) = 4 e = 7 ta có (7,4) = 1 nghịch đảo của 7 modulo 4 la d = 3 vì 7*3 =1 + 5*4 Lúc đó ta có E(P) ≡ C ≡ P^e ≡ 9 ^ 7 ≡ 4.782.969 ≡ 9 (mod 10) => C=9 D(C) ≡ C^d ≡ 9^3 ≡ 729 ≡ 9(mod 10) Vậy D chính la hàm ngược của E đây là cơ sở cho việc xây dựng thuật toán RSA mà chúng ta sẽ bàn kỹ ở phần sau
Tính Φ (m ) khi biết m . Chúng ta có định lý sau đây : Giả sử m = p1^a1*p2^a2*… *pk^ak .Khi đó Φ(m) =( p1^a1 – p1^(a1-1) )* … * (pk^ak – pk^(ak-1) ) Ví dụ : m= 10 Ta phân tích 10 =2*5 => Φ(10) =( 2^1 – 2^0) *(5^1 – 5^0) = 1*4 = 4
IV. Hệ mã hóa RSA:
1. Giới thiệu
RSA được Rivest, Shamir và Adleman phát triển, là một thuận toán mật mã hóa khóa công khai. Nó đánh dấu một sự tiến hóa vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công khai. RSA đang được sử dụng phổ biến trong thương mại điện tử và được đánh giá là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn.
Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT). Tên của thuật toán lấy từ 3 chữ cái đầu của tên 3 tác giả.
Trước đó, vào năm 1973, Clifford Cocks, một nhà toán học người Anh làm việc tại GCHQ, đã mô tả một thuật toán tương tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không khả thi và chưa bao giờ được thực nghiệm. Tuy nhiên, phát minh này chỉ được công bố vào năm 1997 vì được xếp vào loại tuyệt mật.
RSA là một thí dụ điển hình về một đề tài toán học trừu tượng lại có thể áp dụng thực tiễn vào đời sống thường nhật . Khi nghiên cứu về các số nguyên tố, ít có ai nghĩ rằng khái niệm số nguyên tố lại có thể hữu dụng vào lãnh vực truyền thông.
Cách tạo khóa:
Chúng ta cần tạo ra một cặp khóa lập mã và giải mã theo phương pháp sau:
Chọn 2 số nguyên tố lớn và với , lựa chọn ngẫu nhiên và độc lập.
Tính: .
Tính: giá trị hàm số Ơle .
Chọn một số tự nhiên e sao cho và là số nguyên tố cùng nhau với .
Tính: d sao cho .
Một số lưu ý:
Các số nguyên tố thường được chọn bằng phương pháp thử xác suất.
Các bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng (xem thêm: số học môđun).
Bước 5 có thể viết cách khác: Tìm số tự nhiên sao cho cũng là số tự nhiên. Khi đó sử dụng giá trị .
Từ bước 3, PKCS#1 v2.1 sử dụng thay cho ).
Khóa công khai bao gồm:
n, môđun, và
e, số mũ công khai (cũng gọi là số mũ mã hóa).
Khóa bí mật bao gồm:
n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và
d, số mũ bí mật (cũng gọi là số mũ giải mã).
Một dạng khác của khóa bí mật bao gồm:
p and q, hai số nguyên tố chọn ban đầu,
d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1),
(1/q) mod p (thường được gọi là iqmp)
Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc (tiếng Anh: Chinese Remainder Theorem - CRT). Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật.
Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa.
*Chuyển đổi thông tin:
Trước khi thực hiện mã hóa, ta phải thực hiện việc chuyển đổi thông tin (chuyển đổi từ M sang m) sao cho không có giá trị nào của M tạo ra văn bản mã không an toàn. Nếu không có quá trình này, RSA sẽ gặp phải một số vấn đề sau:
Nếu m = 0 hay m = 1 sẽ tạo ra các bản mã có giá trị là 0 và 1 tương ứng
Khi mã hóa với số mũ nhỏ (chẳng hạn e = 3) và m cũng có giá trị nhỏ, giá trị me cũng nhận giá trị nhỏ (so với n). Như vậy phép môđun không có tác dụng và có thể dễ dàng tìm được m bằng cách khai căn bậc e của c (bỏ qua môđun).
RSA là phương pháp mã hóa xác định (không có thành phần ngẫu nhiên) nên kẻ tấn công có thể thực hiện tấn công lựa chọn thông tin bằng cách tạo ra một bảng tra giữa thông tin và bản mã. Khi gặp một bản mã, kẻ tấn công sử dụng bảng tra để tìm ra thông tin tương ứng.
Trên thực tế, ta thường gặp 2 vấn đề đầu khi gửi các bản tin ASCII ngắn với m là nhóm vài ký tự ASCII. Một đoạn tin chỉ có 1 ký tự NULL sẽ được gán giá trị m = 0 và cho ra bản mã là 0 bất kể giá trị của e và N. Tương tự, một ký tự ASCII khác, SOH, có giá trị 1 sẽ luôn cho ra bản mã là 1. Với các hệ thống dùng giá trị e nhỏ thì tất cả ký tự ASCII đều cho kết quả mã hóa không an toàn vì giá trị lớn nhất của m chỉ là 255 và 2553 nhỏ hơn giá trị n chấp nhận được. Những bản mã này sẽ dễ dàng bị phá mã.
Để tránh gặp phải những vấn đề trên, RSA trên thực tế thường bao gồm một hình thức chuyển đổi ngẫu nhiên hóa m trước khi mã hóa. Quá trình chuyển đổi này phải đảm bảo rằng m không rơi vào các giá trị không an toàn. Sau khi chuyển đổi, mỗi thông tin khi mã hóa sẽ cho ra một trong số khả năng trong tập hợp bản mã. Điều này làm giảm tính khả thi của phương pháp tấn công lựa chọn thông tin (một thông tin sẽ có thể tương ứng với nhiều bản mã tuỳ từng trường hợp vào cách chuyển đổi).
Một số tiêu chuẩn, chẳng hạn như PKCS, đã được thiết kế để chuyển đổi thông tin trước khi mã hóa bằng RSA. Các phương pháp chuyển đổi này bổ sung thêm bít vào M. Các phương pháp chuyển đổi cần được thiết kế cẩn thận để tránh những dạng tấn công phức tạp tận dụng khả năng biết trước được cấu trúc của thông tin. Phiên bản ban đầu của PKCS dùng một phương pháp đặc ứng (ad-hoc) mà về sau được biết là không an toàn trước tấn công lựa chọn thông tin thích ứng (adaptive chosen ciphertext attack). Các phương pháp chuyển đổi hiện đại sử dụng các kỹ thuật như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal A...