Bài giảng Bảo mật thông tin - Bài 4: Mã hóa công khai RSA

Trình bày: Ths. Lương Trần Hy Hiến 1. Lý thuyết số 2. Mã hóa công khai 3. RSA 2  Phép chia modulo: phép chia lấy dư a mod n = r với a ≥ 0; n > 0; 0 ≤ r ≤ n-1  Đồng dư trong phép chia modulo cho n: a ≡ b (mod n) hay a ≡ b mod n  Phép toán modulo phân hoạch tập số tự nhiên N thành n lớp tương đương đồng dư - ứng với các giá trị của r trong tập {0, 1, 2, 3, , N-1}. VD: N = 4 có 4 lớp tương đương: {0, 4, 8, 12, 16 }, {1, 5, 9, 13, 17 }, {2, 6, 1, 14, 18 }, {3, 7, 11, 15, 19 } 3 Một số tính chất của modulo:  (a + b) mod n = [(a mod n) + (b mod n)] mod n  (a - b) mod n = [(a mod n) - (b mod n)] mod n  (a x b) mod n = [(a mod n) x (b mod n)] mod n 4  Ước số: Nếu a mod n = 0 nghĩa là a chia hết cho n (𝒂 ⋮ 𝒏), hay n là ước số của a (n | a).  gcd(a, b) : ước chung lớn nhất của 2 số, tìm theo thuật toán Euclid.  Số nguyên tố: p được gọi là số nguyên tố nếu p chỉ chia hết cho 1 và chính nó.  Số nguyên tố cùng nhau: gcd(a,b) = 1 thì a, b nguyên tố cùng nhau, kí hiệu: a  b 5  Phần tử nghịch đảo của phép nhân modulo:  Nếu a  n thì:  w sao cho a.w  1 (mod n).  w dgl phần tử nghịch đảo trong phép chia mod n, kí hiệu a-1.  Ví dụ: n = 10, a = 7 là hai số nguyên tố cùng nhau, do đó tìm được a-1 = 3 (21 ≡ 1 mod 10) 6  Nếu p là số nguyên tố và a là số nguyên không chia hết cho p thì ap-1 ≡ 1 mod p  Ví dụ:  p = 5, a = 7  74= 49.49 = 2401, 2401 ≡ 1 mod 5  p = 7, a = 4  46= 64.64 = 4096, 4096 ≡ 1 mod 7 7  Tính y từ a, x và n là các số nguyên: y = ax mod n = (a.a a) mod n (chỉ xét n nguyên tố).  VD: n = 19, a và x = 1..18 8  n = 19, a, x = 1..18  Nhận xét:  hàng a = 11 lặp lại theo chu kỳ 3 giá trị 11, 7, 1.  Cần quan tâm hàng nào đủ giá trị (không tạo chu kỳ)  hàng a = 2, 3, 10, 13, 14, 15.  Như vậy chỉ có a = 2, 3, 10, 13, 14, 15 thì phép lũy thừa modulo trên mới khả nghịch.  Tổng quát với mỗi n chỉ có một số trường hợp của a thì phép lũy thừa là khả nghịch  a được gọi là primitive root của n 9 10  Còn gọi là mật mã hai khóa hay bất đối xứng  Các giải thuật khóa công khai sử dụng 2 khóa  Một khóa công khai ▪ Ai cũng có thể biết ▪ Dùng để mã hóa thông báo và thẩm tra chữ ký  Một khóa riêng ▪ Chỉ nơi giữ được biết ▪ Dùng để giải mã thông báo và ký (tạo ra) chữ ký  Có tính bất đối xứng  Bên mã hóa không thể giải mã thông báo  Bên thẩm tra không thể tạo chữ ký  Có thể phân ra 3 loại ứng dụng  Mã hóa/giải mã ▪ Đảm bảo sự bí mật của thông tin  Chữ ký số ▪ Hỗ trợ xác thực văn bản  Trao đổi khóa ▪ Cho phép chia sẻ khóa phiên trong mã hóa đối xứng  Một số giải thuật khóa công khai thích hợp cho cả 3 loại ứng dụng; một số khác chỉ có thể dùng cho 1 hay 2 loại. Nguồn th. báo Giải thuật mã hóa Giải thuật giải mã Đích th. báo Nguồn cặp khóa Kẻ phá mã Nguồn A Đích B 14 15 Alice Bob Mã hóa Giải mã Khóa công khai của Bob Khóa riêng của Bob Khóa ngẫu nhiên Khóa ngẫu nhiên  Bên B dễ dàng tạo ra được cặp (KUb, KRb)  Bên A dễ dàng tạo ra được C = EKUb (M)  Bên B dễ dàng giải mã M = DKRb (C)  Đối thủ không thể xác định được KRb khi biết KUb  Đối thủ không thể xác định được M khi biết KUb và C  Một trong hai khóa có thể dùng mã hóa trong khi khóa kia có thể dùng giải mã  M = DKRb (EKUb (M)) = DKUb (EKRb (M))  Không thực sự cần thiết  Không thể tìm kiếm vét cạn  Khối lượng cần tính toán là rất lớn  không thể tìm khóa thứ 2.  Mã công khai thường chậm hơn khá nhiều so với mã đối xứng, nên nó thường được dùng mã những thông tin nhỏ quan trọng 18  Đề xuất bởi Ron Rivest, Adi Shamir và Len Adleman (MIT) vào năm 1977  Hệ mã hóa khóa công khai phổ dụng nhất  Mã hóa khối với mỗi khối là một số nguyên < n  Thường kích cỡ n là 1024 bit ≈ 309 chữ số thập phân  Đăng ký bản quyền năm 1983, hết hạn năm 2000  An ninh vì chi phí phân tích thừa số của một số nguyên lớn là rất lớn 19  Mỗi bên tự tạo ra một cặp khóa công khai - khóa riêng theo các bước sau: 1. Chọn ngẫu nhiên 2 số nguyên tố đủ lớn p  q 2. Tính n = pq và (n) = (p-1)(q-1) – dùng ĐL Trung Hoa để giảm bớt tính toán. 3. Chọn ngẫu nhiên khóa mã hóa e sao cho 1 < e < (n) và gcd(e, (n)) = 1 (nguyên tố cùng nhau) 4. Tìm khóa giải mã d ≤ n thỏa mãn e.d ≡ 1 mod (n) (ed – 1 chia hết cho (n)) 5. Công bố khóa công khai KU = {e, n} Giữ bí mật khóa giải mã riêng KR = {d, n} ▪ Các giá trị bí mật p và q bị hủy bỏ Cho biết (e,n) và (d,n) 1. Để mã hóa 1 thông báo nguyên bản M, bên gửi thực hiện:  Lấy khóa công khai của bên nhận KU = {e, n}  Tính C = Me mod n 2. Để giải mã bản mã C nhận được, bên nhận thực hiện:  Sử dụng khóa riêng KR = {d, n}  Tính M = Cd mod n  Lưu ý là thông báo M phải nhỏ hơn n  Phân thành nhiều khối nếu cần  Theo ĐL Ole: aФ(n)mod N = 1 trong đó gcd(a, N)=1.  Ta có N=p.q, với Ф(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: Cd = (Me)d = M1+k.Ф(N) = M1.(MФ(N))k  Nên Cd mod N = M1.(1)k modN = M1 mod N = M mod N 22  Theo định lý Euler   a, n: gcd(a, n) = 1  a(n) mod n = 1  (n) là số các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n  Đối với RSA có  n = pq với p và q là các số nguyên tố  (n) = (p - 1)(q - 1)  ed ≡ 1 mod (n)   số nguyên k: ed = k(n) + 1  M < n  Có thể suy ra  Cd mod n = Med mod n = Mk(n) + 1 mod n = M mod n = M  Chọn 2 số nguyên tố p = 17 và q = 11  Tính n = pq = 17  11 = 187  Tính (n) = (p - 1)(q - 1) = 16  10 = 160  Chọn e: gcd(e, 160) = 1 và 1 < e < 160; lấy e = 7  Xác định d: de ≡ 1 mod 160 và d ≤ 187 Giá trị d = 23 vì 23  7 = 161 = 1  160 + 1  Công bố khóa công khai KU = {7, 187}  Giữ bí mật khóa riêng KR = {23, 187}  Hủy bỏ các giá trị bí mật p = 17 và q = 11 Mã hóa Giải mã Nguyên bản Nguyên bản Bản mã  Cần chọn p và q đủ lớn  Thường chọn e nhỏ  Thường có thể chọn cùng giá trị của e cho tất cả người dùng  Trước đây khuyến nghị giá trị của e là 3, nhưng hiện nay được coi là quá nhỏ  Thường chọn e = 216 - 1 = 65535  Giá trị của d sẽ lớn và khó đoán  Khóa 128 bit là một số giữa 1 và một số rất lớn 340.282.366.920.938.000.000.000.000.000.000.000.000  Có bao nhiêu số nguyên tố giữa 1 và số này ≈ n / ln(n) = 2128 / ln(2128) ≈ 3.835.341.275.459.350.000.000.000.000.000.000.000  Cần bao nhiêu thời gian nếu mỗi giây có thể tính được 1012 số Hơn 121.617.874.031.562.000 năm (khoảng 10 triệu lần tuổi của vũ trụ)  An ninh nhưng cần đề phòng những điểm yếu 28  Phương pháp vét cạn  Thử tất cả các khóa riêng có thể ▪ Phụ thuộc vào độ dài khóa  Phương pháp phân tích toán học  Phân n thành tích 2 số nguyên tố p và q  Xác định trực tiếp (n) không thông qua p và q  Xác định trực tiếp d không thông qua (n)  Phương pháp phân tích thời gian  Dựa trên việc đo thời gian giải mã  Có thể ngăn ngừa bằng cách làm nhiễu  An ninh của RSA dựa trên độ phức tạp của việc phân tích thừa số n  Thời gian cần thiết để phân tích thừa số một số lớn tăng theo hàm mũ với số bit của số đó  Mất nhiều năm khi số chữ số thập phân của n vượt quá 100 (giả sử làm 1 phép tính nhị phân mất 1 s)  Kích thước khóa lớn đảm bảo an ninh cho RSA  Từ 1024 bit trở lên  Gần đây nhất năm 1999 đã phá mã được 512 bit (155 chữ số thập phân) 31