Hệ mật khóa công khai

CHƯƠNG II. HỆ MẬT MÃ KHÓA CÔNG KHAI

2.1. Tổng quan về các hệ mật mã

2.1.2. Hệ mật khóa công khai

Phương pháp mã hóađối xứng (symmetric cryptography) có ưu điểm là tốc độ mã hóa và giải mã rất nhanh. Tuy nhiên phương pháp này có nhược điểm là cần một kênh an toàn để trao đ ổi khóa bí mật (không luôn dễ dàng tìmđược).

Hệ mật khóa công khai đã giải quyết được vấn đề này bằng cách sử dụng hai khóa: khóa công khai (public key) và khóa riêng (private key). Hai khóa này có vai trò ngược nhau, một khóa để mã hóa còn một khóa dùng để giải mã.

2.1.2.1. Giới thiệu chung về hệ mật khóa công khai Hệ mật khóa công khai sử dụng hai khóa:

 Khóa công khai: có thể công bố cho mọi người biết, sử dụng để mã hóa thông điệp và xác thực chữ ký.

 Khóa riêng: chỉ người nhận thông điệp biết, sử dụng để giải mã thông điệp và ký số.

Hình 2.2. Sơ đồ mã hóa thông tin bằng hệ mật khóa công khai

Giả sử A muốn gửi thông điệp Pcho B. Khi đó Asẽsử dụng khóa công khai

P E C D P B

A

Bản rõ Mã

hóa Kênh

truyền

Bản mã

Giải mã

PU

B

PR

B

cho B. B nhận được bản mã C sẽ sử dụng khóa riêng PRB của mìnhđể giải mã C bằng thuật toán giải mã Dthu được thông điệp Pban đầu.

Các yêu cầu của hệ mật khóa công khai: Thuật toán mã hóa công khai, tính bảo mật nằm trong chìa khóa chứ không dựa vào thuật toán.

Nguyên tắc mã hóa hệ mật khóa công khai:

Trong hệ thống có Nđối tượng cùng trao đổi thông tin mật. Mỗi đối tượng sẽ chọn cho mình một khóa lập mã k, sau đó xây dựng hàm mã hóa Ek và hàm giải mã Dktương ứng, hàm mã hóa Ekđược công bố công khai. Vậy sẽ có N khóa lập mã tương ứng:k1, k2,... kN

Khi đối tượng thứ i (1≤ i≤ N)muốn gửi thông điệp cho đối tượng thứ j trong hệ thống (1≤ j ≤ N), thông điệp sẽ được chuyển thành từng khối P với độ dài quy định nào đó, mỗi khối này sẽ được mã hóa bằng hàm mã hóa đối tượng thứ j.

Thông điệp sau khi mã hóađược gửi đi sẽ có dạng:

Đối tượng j khi nhận được M sẽ giải mãđể thu được P:

Do hàm giải mã là hàm giải mã của riêng đối tượng thứ j nên các đối tượng khác trong hệ thống dù có thu được bản mã M cũng khó có thể giải mãđược M trong thời gian chấp nhận được.

2.1.2.2. Một số hệ mật khóa công khai

a. Hệ mậtRSA

Hệ mật RSA được xây dựng dựa trên bài toán mũ. Chọn n = p × qđủ lớn, p, q là các số nguyên tố. Cặp khóa lập mã là b và n. Trong đó b là số mũ, được xác

định ngẫu nhiên sao cho , với là hàm Euler của n, được xác định bởi:

Định nghĩa là không gian khóa.

K = (n, p, q, e, d) ta có hàm mã hóa và giải mã như sau:

EK(x) = xemod n (hàm mã hóa) DK(y) = ydmod n (hàm giải mã)

Nhận xét: Để hệ mật RSA được coi là an toàn thì cần phải chọn p và q là các số nguyên tố lớn (khoảng 100 chữ số).

Hệ mật RSA có độ an toàn cao và thuật toán đơn giản nên được sử dụng rộng rãi. Tuy nhiên tốc độ mã hóa chậm nên RSA không dùng để mã hóa khối dữ liệu lớn mà dùng để trao đổi khóa hay xác thực,…

b. Hệ mật Rabin

Chọn hai số nguyên tố p và q sao cho p≡3 (mod 4), q≡ 3 (mod 4), n = p×q Giả sửR = C = Zn, ta định nghĩa:

K={(n, p, q, B): 0≤ B ≤ n-1}

Với mỗiK = (n, p, q, B) ta có:

Hàm mã hóa:

Hàm giải mã:

Từ mô tả hệ mật trên ta có thể thấy hàm mã hóa không phải là một phép nội xạ đơn ánh. Do đó hàm giải mã không thể thực hiện một cách rõ ràng được.

Trong thực tế có thể thấy, ứng với một bản mã bất kỳ có thể có bốn bản rõ.

Giả sử w là một trong bốn căn bậc 2 không tầm thường của 1 mod n, xϵ Zn. Ta có phương trình sau:

Như vậy có bốn bản rõ có thể mã hóa thành là x; - x – B;

; và , với w là một căn bậc 2 không tầm thường của 1 modulo n. Vấn đề đặt ra là không có cách nào để người nhận có thể phân biệt đâu là bản rõ chính xác trừ khi có đủ tài liệu để loại bỏ ba bản còn lại.

Xét từ phía người nhận, khi nhận được bản mã y và muốn xác định x thỏa mãn:

x2+ Bx≡ y (mod n)

Đây là phương trình bậc 2 với ẩn x. Thay hay . Khi đó phương trình trở thành:

Hay

Thay ta có phương trìnhđồng dư sau:

Khi đó, việc giải mã chỉ còn là việc tìm căn bậc 2 theo modulo n. Việc này tương đương với giải hai phương trình sau:

Có hai căn bậc 2 củaC theo modulo pvà hai căn bậc 2 của C theo modulo q.

Sử dụng định lý phần dư Trung Hoa có thể tìm ra bốn giá trị theo modulo n. Chúng ta có thể sử dụng tiêu chuần Euler để kiểm tra xem C có phải là thặng dư bậc 2 modulo p (và modulo q) hay không. Trong thực tế, nếu việc mã hóađược thực hiện chính xác thì C sẽ là thặng dư bậc 2. Nhưng tiêu ch uẩn này không giúp tính toán giá trị căn bậc 2.

Khi p≡ 3 (mod 4),có một công thức đơn giản để tính căn bậc 2 của thặng dư bậc 2 theo modulo p. Giả sửC là thặng dư bậc 2 và p≡ 3 (mod 4). Khi đó ta có:

Sử dụng tiêu chuẩn Euler ta có: Nếu C là thăng dư bậc 2 modulo p thì . Do đó, có hai căn bậc 2 của C modulo p là . Tương tự như vậy ta có hai căn bậc 2 của C modulo q là . Từ đó thu được bốn căn bậc 2 của x1modulo n.

Khi đã xác định được giá trị x1 ta xác định giá trị của . Từ đó có công thức giải mã:

c. Hệ mật ElGamal Mô tả hệ mật:

Hệ mật Elgamal được xây dựng trên bài toán logarithm rời rạc. Việc mô tả bài toán được thiết lập trong trường hữu hạn Zp, p là số nguyên tố.

Thuật toán tạo khóa:

Mỗi cá thể A tham gia quá trình traođổi phải tạo ra một khóa công khai và khóa bí mật tương ứng theo các bước sau:

Bước 1: Tạo số nguyên tố lớn ngẫu nhiên p và số sinh α của nhóm nhân Zpvà số nguyên p.

Bước 2: Chọn số nguyên ngẫu nhiên a: 1≤ a ≤ p-2 và tính giá trị .

Bước 3: Khi đó khóa công khai của A là ( p, α, ), khóa riêng bí mật là a.

Thuật toán mã hóa và giải mã hóa:

B mã hóa thông điệpm gửi cho A, A nhận được và giải mã m.

 Mã hóa

Để mã hóa thôngđiệp, B cần thực hiện các bước sau:

• B thu nhập khóa công khai đáng tin cậy của A gồm (p, α, )

• Biểu diễn thông điệp cần gửi dưới dạng số (số hóa thông điệp) m:

mϵ {1, 2, …, p-1}

• Chọn số nguyên ngẫu nhiên k, 1≤ k ≤ p-2

• Tính và

• Gửi bản mã cho A.

 Giải mã

Để khôi phục thông điệpm từ c, A phải thực hiện các bước sau:

• Sử dụng khóa riêng ađể tính (chú ý rằng:

)

• Khôi phục lại m bằng cách tính giá trị . Ví dụ:

A chọn số nguyên tố p=2357; số sinh củaZ2357làα = 2. A chọn khóa riêng là a=1751 và tính:

Khi đó khóa công khái của A sẽ là bộ: (p=2357, α = 2, = 1185).

Mã hóa:

Để mã hóa m = 2035, B cho một số nguyên k ngẫu nhiên k=1520 và tính giá trị:

B gửi 1430 và =697 cho A.

Giải mã:

Để giải mã, A tính giá trị:

Và khôi phụcm bằng cách tính:

m = 872 697 mod 2357 = 2035

Chú ý:Các bên tham gia trao đổi thông điệp có thể thống nhất cùng chọn số nguyên tố p và số sinh α giống nhau. Trong trường hợp đó p vàα không cần phải

công bố công khai như khóa công khai nữa. Khi đó kích thước của khóa công khai cũng được giảm đi. Một lợi ích nữa khi sử dụng chung giá trị cố định α là có thể tính toán trước các lũy thừa của α. Còn một điều không thuận tiễn khi sử dụng nhiều tham số giá trị lớn là cần phải tính toán nhiều giá trị modulo p.