Download miễn phí Đề tài Giải thuật RSA
MỤC LỤC
LỜI NÓI ĐẦU ii
MỤC LỤC iii
DANH MỤC HÌNH VẼ iv
CHƯƠNG 1: RSA HOẠT ĐỘNG NHƯ THẾ NÀO 5
1.1 Giới thiệu về RSA 5
1.2 Thuật toán RSA 5
1.3 Tạo chữ ký số 10
1.4 Chuyển đổi văn bản rõ 13
CHƯƠNG 2: TRIỂN KHAI THỰC TẾ 15
2.1 Quá trình tạo khóa 15
2.2 Tốc độ 16
2.3 Phân phối khóa 16
2.4 Bảo mật 17
2.5 Tấn công 22
KẾT LUẬN 23
TÀI LIỆU THAM KHẢO 24
DANH MỤC HÌNH VẼ
Hình 1.1 Mã hóa và giải mã 5
Hình 1.2 Trao đổi khóa bất đối xứng 7
Hình 2.1 Cố gắng phá hoại cặp khóa bất đối xứng 14
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-03-22-de_tai_giai_thuat_rsa.FEDVxRFLwq.swf /tai-lieu/de-tai-ung-dung-tren-liketly-4789/Để 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:
143) ta thực hiện phép tính:
encrypt(50) = 5017 mod 143 = 85
Để giải mã văn bản có giá trị c=545 và cặp khóa bí mật (d,n) là (113,1435) ta thực hiện phép tính:
decrypt(85) = 85113 mod 143 = 50
Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ giải thuật bình phương và nhân.
Hình 1.2. Trao đổi khóa bất đối xứng
Tạo chữ ký số
Giới thiệu chung
Ngày nay, có ba hệ mã hóa thông dụng được sử dụng để xây dựng các lược đồ ký điện tử, đó là hệ mã hóa RSA, hệ mã hóa dựa trên bài toán logarit rời rạc và hệ mã hóa dựa trên đường cong elliptic. Các hàm một chiều sử dụng trong các hệ mã này hiện đang được xem là an toàn theo thừa nhận (tức là không có thuật toán nào hữu hiệu để tính hàm ngược của chúng). Tuy nhiên, một vấn đề cơ bản của tính an toàn đối với một lược đồ ký điện tử lại là tính không thể giả mạo được chữ ký và điều này không suy ra được trực tiếp từ tính an toàn của hệ mã mà nó dựa vào. Trong khoảng mười năm gần đây, vấn đề này đang thu hút rất nhiều sự quan tâm của cộng đồng mật mã trên thế giới. Người ta đang cố gắng đưa ra những lược đồ ký sao cho tính không thể giả mạo được của nó có thể được đánh giá thông qua độ an toàn của các hàm một chiều mà nó sử dụng. Trong bài này chúng tui xem xét một số lược đồ ký sử dụng hàm một chiều của hệ mã RSA (đang được xem là phổ biến nhất hiện nay).
Giả sử A muốn gửi cho B một văn bản có chữ ký của mình. Để làm việc này, A tạo ra một giá trị băm (hash value) của văn bản cần ký và tính giá trị mũ d mod n của nó (giống như khi A thực hiện giải mã). Giá trị cuối cùng chính là chữ ký điện tử của văn bản đang xét. Khi B nhận được văn bản cùng với chữ ký điện tử, anh ta tính giá trị mũ e mod n của chữ ký đồng thời với việc tính giá trị băm của văn bản. Nếu 2 giá trị này như nhau thì B biết rằng người tạo ra chữ ký biết khóa bí mật của A và văn bản đã không bị thay đổi sau khi ký.
Ký điện tử và những mô hình nguyên thủy
Hàm băm mật mã
Người ta thường sử dụng sự hỗ trợ của các hàm băm mật mã trong quá trình Encoding của các lược đồ ký. Một hàm băm với đầu vào là văn bản (có độ dài bất kỳ), sinh ra cho ta xâu H có độ dài xác định, được gọi là mã băm của . Hàm băm mật mã h phải thỏa mãn các điều kiện sau:
• Là hàm một chiều: Tức là nếu cho ta sẽ dễ dàng tính ra H=h(M) . Nhưng nếu chỉ có mã băm H thì rất khó có thể tìm được văn bản M sao cho H=h(M) (rất khó có nghĩa là hiện nay không có thuật toán hữu hiệu nào làm được).
• Không tìm được xung đột: Tức là rất khó để tìm ra hai văn bản M và M’ có cùng mã băm.
• Không tìm được xung đột của văn bản cho trước: Tức là cho trước văn bản M thì rất khó để tìm được văn bản M’có cùng mã băm với văn bản Mđó.
Trong thực tế rất khó có thể tìm ra được một hàm băm thỏa mãn nghiêm ngặt các tính chất trên. Hiện nay, ngày càng có những kết quả thám mã mạnh tấn công vào tính chất thứ hai. Cho nên, các lược đồ ký gần đây thường cố gắng tránh việc dựa trực tiếp vào tính chất này.
Lược đồ ký RSA nguyên thủy
Lược đồ ký RSA sử dụng thao tác sinh khóa của chính hệ mã RSA. Một hàm băm mật mã (công khai) sẽ được sử dụng trong quá trình Encoding của thao tác ký. Ở đây ta mô tả lược đồ RSA có văn bản kèm theo. Thao tác ký nhận đầu vào là văn bản và khóa bí mật sẽ sinh ra chữ ký là x. Thao tác xác minh, nhận đầu vào là M1x và Ph , sẽ cho ra kết quả là 1 nếu như x đúng là chữ ký trên văn bản M của người có bộ khóa (sh,ph), ngược lại sẽ cho kết quả 0.
Thao tác ký RSA-Sign(M) bao gồm các bước như sau:
(1) Tính H=h(M):
(2) Tính y=0x0001FFFF…FF00\\H;
3) Tính x=f-1(y)=ydmodN, x chính là chữ ký trên văn bản M Ở bước (2) của thao tác ký ta thấy có một số các xâu 0xFF được nối vào mã băm H của M. Mục đích của việc này để tạo ra xâu y có độ dài k bit (là độ dài của N trong chìa khóa). Xâu 0x0001 đầu tiên có ý nghĩa là để cho y luôn nhỏ hơn N . Xâu 00 ngăn cách giữa phần mã băm và phần nối thêm có mục đích giúp ta có thể dễ dàng lấy ra được mã băm H từ xâu y. Ở bước (3) ta giả sử xâu y đã chuyển sang thành số y tương ứng.
Thao tác xác min RSA-Verify(M,) Bao gồm các công đoạn sau:
(1) Tính H1=h(M);
(2) Tính y=f(x)=xe mod N v à lấy ra xâu H từ y là kh bit cuối cùng, với kh là độ dài của mã băm ứng với hàm băm công khai h.
(3) Nếu H1=H thì cho ra 1, ngược lại cho ra 0.
Theo lược đồ trên, ta thấy mã băm H chỉ là một phần nhỏ của y. Và việc tìm ra xung đột của hàm h sẽ gây ảnh hưởng trực tiếp đến độ an toàn của lược đồ. Cụ thể là, nếu như tìm được hai văn bản M và M’ có cùng mã băm thì chữ ký trên văn bản M cũng chính là chữ ký trên văn bản M'. Hiện nay, đã có những thuật toán tìm ra được một số điểm xung đột của những hàm băm khá phổ biến trước đây (như MD5, SHA-1,...), khiến cho các lược đồ ký nguyên thủy bị “lung lay”. Tuy nhiên, cũng cần ghi nhận rằng các thuật toán tìm xung đột nêu trên chưa cho phép tìm được một văn bản khác với văn bản M cho trước mà có cùng mã băm với M . Như vậy, cho đến nay, việc “mạo chữ ký” của một văn bản cho trước là vẫn chưa thể thực hiện được.
Lược đồ ký theo chuẩn PKCS#1 (V2.1)
Mô tả lược đồ
Thao tác sinh khóa của PSS2000 cũng giống như của PSS96, có một chút sự khác biệt được ở quá trình Encoding. Ta mô tả quá trình Encoding như sau:
PSS2000 – Encode (H) bao gồm các bước sau:
Như vậy thao tác Encoding ở PSS2000 có sự khác biệt so với phiên bản 96 là ở trong bước (2) hàm băm có nối thêm xâu gồm u chữ số 0 vào trước văn bản được băm. Ở thao tác (4), xâu E được nối vào cuối của xâu kết quả. Xâu E cố định có thể là 0xbc =10111100 hay HID\\cc, v ới HID là chỉ số của hàm băm h. Còn bước (3) chẳng qua cách diễn đạt khác của hàm g1, g2 trong phiên bản 96.
Lược đồ ký PSS2000-SIGN, cho văn bản M, tính giá trị H=h(M) và tính y=PSS2000-Encode(H), kết quả trả lại là x=f-1(y). Ta có thể nhận thấy có thêm một khác biệt giữa PSS2000 và PSS96, đó là ở PSS2000 có thêm thao tác băm văn bản trước khi đưa vào thao tác encoding.
b. Lược đồ ký thu gọn
Nhận xét. Lược đồ ký RSA-GenPSS-Reduced như trên chẳng qua là lược đồ ký thông thường như PSS96, chỉ có một vài điểm khác nhau nhỏ như sau:
• Thứ nhất: lược đồ trên, độ dài các văn bản đầu vào chỉ cho phép là ; hk
• Thứ hai: Một chuỗi gồm u chữ số 0 được nối vào H||r trước khi cho vào băm (bước (2) quá trình GenPSS-Encode) ;
• Thứ ba, đó là sự khác nhau giữa hai quá trình Encoding đã nhận xét ở trên, ở sự tham gia của E trong ảnh của quá trình Encoding.
Yêu cầu thứ nhất là hiển nhiên do lược đồ thu gọn làm việc trên giá trị băm của hàm băm . Yêu cầu thứ hai được đưa vào nhằm mục đích tạo ra sự tương thích cho lược đồ ký có khôi phục văn bản và cũng góp phần làm giảm xung đột. Bởi lẽ sẽ khó hơn nếu khi tìm kiếm hai văn bản xung đột với nhau khi ta yêu cầu cả hai văn bản đó đều phải có u bit đầu tiên là 0. Sự thay đổi thứ ba có thể góp phần làm tăng thêm độ an toàn cho lược đồ ký. Thật vậy, bài toán tìm đầu vào cho h...
