CỔNG ĐHQGHN  XEM ĐIỂM  Trang ChínhTrang Chính  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  
Bài gửi sau cùng
Bài gửiNgười gửiThời gian
Happy new year 2013 dodacxuat_nuh Sat Dec 29, 2012 3:45 pm
Lâu rùi anh không thấy chú nào vào diễn đàn nữa hunghanam Mon May 07, 2012 9:26 am
Happy new year 2012. chien2311 Mon Jan 30, 2012 5:05 am
[color=red]Tin "Cực Hot" cho tất cả các bạn và người thân[/color] TranTai Wed Oct 05, 2011 4:44 am
Cách đổi lịch âm dương TranTai Mon Oct 03, 2011 2:24 am
lâu lâu rùi không lên diễn đàn lớp mình chém gió hunghanam Fri Sep 30, 2011 9:44 am
TRIỂN LÃM DU HỌC NHẬT BẢN 2010 Vừa học vừa làm thu nhập 1700USD/1 tháng samaccodon Wed Sep 28, 2011 8:00 am
Vừa đi làm, vừa làm cộng tác viên kiếm tiền... *pepe* Sun Aug 07, 2011 11:37 am
:(((((((((((((((((((((((((((((((((((((((((((((((((((((((( chien2311 Sat Aug 06, 2011 5:05 am
Khánh thành website học tiếng anh của Chiến samaccodon Fri Aug 05, 2011 10:30 am
Funy : Counter strike =)) Che..vankhe Mon Jul 25, 2011 10:43 am
Lịch học hè chien2311 Fri Jul 08, 2011 4:11 pm
Tổng hợp ảnh 24/06/2011 - Lễ tốt nghiệp samaccodon Wed Jul 06, 2011 9:17 am
Câu lạc bộ tiếng anh của Chiến - cơ hội giao lưu người bản xứ Che..vankhe Tue Jun 28, 2011 9:41 pm
[K52A3] CÔNG BỐ TÀI CHÍNH QUỸ LỚP (10/03/2011) samaccodon Thu Jun 23, 2011 5:35 pm
[VPK] DANH SÁCH TỐT NGHIỆP CHÍNH THỨC samaccodon Thu Jun 23, 2011 5:31 pm
[VPK] LỄ TRAO BẰNG TỐT NGHIỆP chien2311 Wed Jun 22, 2011 11:59 am
Pic 21/06 (new and hot) vuthaihoc Wed Jun 22, 2011 10:28 am
Gameloft Hà Nội tuyển dụng Che..vankhe Mon Jun 20, 2011 8:18 pm
[ CTCTSV ] 21 THÁNG 6 ĐI LẤY HỒ SƠ TỐT NGHIỆP chien2311 Sat Jun 18, 2011 9:38 am

Share | 
 

 thuật toán RSA

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
hunghanam
Quan Nhất Phẩm
Quan Nhất Phẩm
avatar

Tổng số bài gửi : 129
Sinh nhật : 05/11/1989

Bài gửiTiêu đề: thuật toán RSA   Sun May 15, 2011 11:28 am

chưa kịp đọc các bác đọc bản tiếng việt này nhé cho nó dễ làm ka ka.
Mô tả sơ lược
Thuật toán RSA có hai khóa: khóa công khai (hay khóa công cộng) và khóa bí mật (hay khóa cá nhân). Mỗi khóa là những số cố định sử dụng trong quá trình mã hóa và giải mã. Khóa công khai được công bố rộng rãi cho mọi người và được dùng để mã hóa. Những thông tin được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói cách khác, mọi người đều có thể mã hóa nhưng chỉ có người biết khóa cá nhân (bí mật) mới có thể giải mã được.
Ta có thể mô phỏng trực quan một hệ mật mã khoá công khai như sau : Bob muốn gửi cho Alice một thông tin mật mà Bob muốn duy nhất Alice có thể đọc được. Để làm được điều này, Alice gửi cho Bob một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. Bob nhận chiếc hộp, cho vào đó một tờ giấy viết thư bình thường và khóa lại (như loại khoá thông thường chỉ cần sập chốt lại, sau khi sập chốt khóa ngay cả Bob cũng không thể mở lại được-không đọc lại hay sửa thông tin trong thư được nữa). Sau đó Bob gửi chiếc hộp lại cho Alice. Alice mở hộp với chìa khóa của mình và đọc thông tin trong thư. Trong ví dụ này, chiếc hộp với khóa mở đóng vai trò khóa công khai, chiếc chìa khóa chính là khóa bí mật.
[sửa]Tạo khóa
Giả sử Alice và Bob cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, Alice đầu tiên cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước 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.
Alice gửi khóa công khai cho Bob, và giữ bí mật khóa cá nhân của mình. Ở đâ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.
[sửa]Mã hóa
Giả sử Bob muốn gửi đoạn thông tin M cho Alice. Đầu tiên Bob chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Quá trình này được mô tả ở phần #Chuyển đổi văn bản rõ.
Lúc này Bob có m và biết n cũng như e do Alice gửi. Bob sẽ tính c là bản mã hóa của m theo công thức:

Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật toán bình phương và nhân) Cuối cùng Bob gửi c cho Alice.
[sửa]Giải mã
Alice nhận c từ Bob và biết khóa bí mật d. Alice có thể tìm được m từ c theo công thức sau:

Biết m, Alice tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì ta có
.
Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ) nên:



Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có:
.
hay:
.
[sửa]Ví dụ
Sau đây là một ví dụ với những số cụ thể. Ở đây chúng ta sử dụng những số nhỏ để tiện tính toán còn trong thực tế phải dùng các số có giá trị đủ lớn.
Lấy:
p = 61 — số nguyên tố thứ nhất (giữ bí mật hoặc hủy sau khi tạo khóa)
q = 53 — số nguyên tố thứ hai (giữ bí mật hoặc hủy sau khi tạo khóa)
n = pq = 3233 — môđun (công bố công khai)
e = 17 — số mũ công khai
d = 2753 — số mũ bí mật
Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là:
encrypt(m) = me mod n = m17 mod 3233
với m là văn bản rõ. Hàm giải mã là:
decrypt(c) = cd mod n = c2753 mod 3233
với c là văn bản mã.
Để mã hóa văn bản có giá trị 123, ta thực hiện phép tính:
encrypt(123) = 12317 mod 3233 = 855
Để giải mã văn bản có giá trị 855, ta thực hiện phép tính:
decrypt(855) = 8552753 mod 3233 = 123
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.
Về Đầu Trang Go down
Xem lý lịch thành viên
 
thuật toán RSA
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Giáo trình môn Kỹ Thuật Điện Tử
» Giải thích thuật ngữ
» Tóm tắt lý thuyết và bài tập kỹ thuật điện
» Thuật ngữ kỹ thuật đóng tàu và đăng kiểm Anh - Việt
» Thác Trắng - Minh Long - Quảng Ngãi

Permissions in this forum:Bạn không có quyền trả lời bài viết
DIỄN ĐÀN TOÁN TIN :: CÁC VẤN ĐỀ CHUNG :: KÌ HỌC 2 NĂM THỨ 4 :: Mật mã và an toàn dữ liệu-
Chuyển đến 
Free forum | © phpBB | Free forum support | Liên hệ | Report an abuse | Create a free blog