Bài giảng Mật mã hóa hiện đại: Chương 4 - TS. Phạm Việt Hà

Mục tiêu chương 4 Hệ mật khóa công khai thuộc bài giảng Mật mã hóa hiện đại trình bày nội dung hệ mật khoá công khai, hệ mật RSA, hạ tầng khóa công khai PKI...bài giảng hữa ích này dành cho sinh viên ngành toán học ứng dụng và viễn thông.
Nội dung trích xuất từ tài liệu:
Bài giảng Mật mã hóa hiện đại: Chương 4 - TS. Phạm Việt HàTT CNTT HN Wednesday, April 25, 2012 MẬT MÃ HÓA HIỆN ĐẠI Chương 4: Hệ mật khóa công khai TS. Phạm Việt Hà VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 4. Hệ mật khoá công khai 4.1 Hệ mật RSA 4.2 Hạ tầng khóa công khai PKI VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 2 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆCCIT/RIPT 1TT CNTT HN Wednesday, April 25, 2012 4.1 Hệ mật RSA  RSA là mã công khai được sáng tạo bởi Rivest, Shamir & Adleman ở MIT (Trường Đại học Công nghệ Massachusetts) vào năm 1977.  RSA là mã công khai được biết đến nhiều nhất và sử dụng rộng rãi nhất hiện nay.  RSA dựa trên các phép toán lũy thừa trong trường hữu hạn các số nguyên theo modulo nguyên tố. Cụ thể, mã hoá hay giải mã là các phép toán luỹ thừa theo modulo số rất lớn.  Việc thám mã, tức là tìm khoá riêng khi biết khoá công khai, dựa trên bài toán khó là phân tích một số rất lớn đó ra thừa số nguyên tố. Nếu không có thông tin gì, thì ta phải lần lượt kiểm tra tính chia hết của số đó cho tất cả các số nguyên tố nhỏ hơn căn của nó. Đây là việc làm không khả thi! VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 3 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ 4.1 Hệ mật RSA  Người ta chứng minh được rằng, phép lũy thừa cần O((log n)3) phép toán, nên có thể coi lũy thừa là bài toán dễ.  Cần chú ý rằng ở đây ta sử dụng các số rất lớn khoảng 1024 bit, tức là cỡ 10350.  Tính an toàn dựa vào độ khó của bài toán phân tích ra thừa số các số lớn. Bài toán phân tích ra thừa số yêu cầu O(elogn log logn) phép toán, đây là bài toán khó. VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN Trang 4 © 2009 | CCIT/RIPT TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆCCIT/RIPT 2TT CNTT HN Wednesday, April 25, 2012 4.1 Hệ mật RSA  Khởi tạo khoá RSA • Mỗi người sử dụng tạo một cặp khoá công khai – riêng như sau: – Chọn ngẫu nhiên 2 số nguyên tố lớn p và q – Tính số làm modulo của hệ thống: N = p.q • Ta đã biết Ф(N)=(p-1)(q-1) • Và có thể dùng Định lý Trung Hoa để giảm bớt tính toán • Chọn ngẫu nhiên khoá mã e • Trong đó 1TT CNTT HN Wednesday, April 25, 2012 4.1 Hệ mật RSA  Cơ sở của RSA • Theo Định lý Ole – a(n) mod N = 1 trong đó gcd(a,N)=1 – Ta có N=p.q – Ф(N)=(p-1)(q-1) – e.d=1 mod Ф(N) – e.d=1+k.Ф(N) đối với một giá trị k nào đó. • Suy ra ...