Phần 4 : Public key crytography (mã hóa khóa cộng đồng)
Giả sử , công ty của bạn có 200 khách hàng, mỗi khách hàng trao đổi thư từ qua lại với công ty và phải được bảo mật, tránh trường hợp khách hàng A đọc được nội dung của khách hàng B. Trong trường hợp này, nếu bạn sử dụng Secret-key crytography, thì bắt buộc phải có 200 mật mã khác nhau được sử dụng. Quản lý 200 mật mã không phải là con số quá lớn, nhưng nếu khách hàng lên đến 1 triệu thì sao ? Không ai làm công việc này cả. Để khắc phục tình trạng đó, Public key crytography ra đời. Kỹ thuật này như sau : công ty tạo ra 2 mật mã đó là : public-key và private-key. Public-key được giao đến toàn bộ khách hàng, private-key do công ty bảo mật không công khai với khách hàng. Khách hàng mã hóa thư từ bằng public-key, công ty giải mã nội dung đó bằng private-key. Các bạn thắc mắc, tại sao lại có chuyện như thế này, public-key và private-key có liên quan như thế nào ?Chúng ta hãy bắt đầu tìm hiểu về nó nhé.
Thuật toán mã hóa public-key, còn được gọi là thuật toán mã hóa asymmetric (bất đối xứng), dựa trên sự hoạt động tách biệt sự mã hóa (sử dụng public-key) và sự giải mã (sử dụng private-key). Do đó, thuật toán này đã có một sự tính toán để cho ra đời private-key từ public-key.
Whitfield Diffie và Martin Hellman thiết kế phương pháp public-key crytography vào giữa những năm 1970. Cơ bản là, ai muốn mã hóa và gửi thông điệp tới người khác cần phải tạo ra hai mã khóa. Một mã được giữ bí mật riêng và mã kia được phổ biến công cộng. Nếu có người muốn gửi thông điệp đến cho bạn, anh ta dùng mã khóa công cộng của bạn, mã hóa nó, và gửi tới bạn thông điệp đã mã hóa đó. Chỉ có khóa riêng (private-key) của bạn có thể giải mã, nếu có người ngăn chặn thông điệp thì không thể giải mã nó bằng khóa công cộng của bạn được.
Lưu ý: Dù Diffie và Hellman thiết kế mã hóa khóa công cộng không đối xứng, nhưng chính RSA (Rivest, Shamir, Adleman) và Data Systems (nay thuộc Security Dynamics) đã đưa ứng dụng này vào hệ thống thực tế.
I. Thuật toán mã hóa RSA :
Mặc dù, public-key crytography được thiết kế bởi Deffie và Hellman, nhưng thuật toán về public-key nổi tiếng nhất lại được phát triển bởi Ronald Rivest, Adi Shamir và Len Adleman vào năm 1977. Thuật toán này được đặt tên là RSA lấy kí tự đầu tên của 3 nhà nghiên cứu. thuật toán RSA có ý nghĩa quan trọng trong việc mã hóa lẫn digital signatures (chữ ký điện tử).
Sự bảo mật của RSA dự trên sự khó khăn trong việc phân tích những con số rất lớn, nó được thực hiện như sau:
- b1: chọn số nguyên tố p và q (p và q phải ít nhất 100 chữ số) được tạo ra bởi n=pq.
- b2: một public-key e được lựa chọn là một số nguyên và nguyên tố cùng nhau với (p-1)(q-1). Hai số được xem là nguyên tố cùng nhau nếu chúng không có thừa số chung.
- b3: một private-key d được tính toán dựa trên biểu thức [ed mod ((p-1)(q-1))] bằng 1.
- b4: sự mã hóa được thực hiện dựa trên số lượng kí tự cần mã hóa m phải nhỏ hơn hoặc bằng n với cách tính biểu thức [me mod n].
- b5: Sự giải mã được thực hiện dựa trên ciphertext c bằng biểu thức [cd mod n].
Trong đó:
+ p và q là 2 số nguyên tố bảo mật.
+ n= pq
+ e là nguyên tố cùng nhau (p-1)(q-1)
+ d = e-1 mod ((p-1)(q-1))
+ m là plaintext
+ c là ciphertext.
Ví dụ : chọn p = 11 , q = 13.
+ n = pq = 143.
+ Chọn e, trong đó e là nguyên tố cùng nhau với (p-1)(q-1) = 10.12 = 120, 120 có thừa số là 2,3,5. Vậy chọn e nguyên tố kế tiếp của 5 nên e = 7.
+ Chọn d, trong đó d phải thỏa biểu thức [7d mod 120 = 1]. Chúng ta, nhân 7 với các số từ 2,3,4,…. Cho đến khi thỏa [7d mod 120 =1], trong trường hợp này d = 103.
+ Ví dụ, ký tự mang số 74, trong ASCII code là J. Mã hóa 74 theo biểu thức [747 mod 143] = 35. Vậy trong ciphertext chữ J là số 35. Giả mã 35 trong ciphertext bằng biểu thức [35103 mod 143] = 74, đúng với giá trị ban đầu trong plaintext.
Chỉ có 2 số nguyên tố nhỏ thôi, mà đã có sự tính toán khó khăn như thế, huống chi sử dụng thuật toán pulic-key bắt buộc q và p phải là 2 số nguyên tố cực lớn.
II. Thuật toán ElGamal
Mặc dù RSA là một trong những thuật toán mã hóa public-key phổ biến nhất, nhưng vẫn có một vài thuật toán khác ra đời, đó là thuật toán ElGamal được phát triển bời TaherElGamal vào năm 1984. Thuật toán này miễn phí và không cần bản quyền sử dụng.
Sự bảo mật của thuật toán ElGamal được dựa trên sự khó khăn trong việc tính toán một discrete logarithm (logarit rời rạc). Cách làm việc của nó như sau:
- b1: Lựa chọn số nguyên tố p và 2 số ngẫu nhiên g và x, sao cho g và x nhỏ hơn p.
- b2: Public-key chứa g, p và y, với y=gx mod p. Private-key là x.
- b3: Để mã hóa 1 khối thông điệp m, chọn số ngẫu nhiên k mà nguyên tố cùng nhau với (p-1), tính toán a = [gk mod p] và b = [myk mod p]. ciphertext là giá trị của a và b.
- b4: Giải mã a và b, bằng biểu thức m = [(b/ax) mod p]
Trong đó :
+ p là số nguyên tố.
+ g và x là số ngẫu nhiên và nhỏ hơn p.
+ y=gx mod p
+ k là số ngẫu nhiên, duy nhất và nguyên tố cùng nhau với (p-1)
+ m là plaintext.
+ a và b là ciphertext.
Ví dụ : chọn p = 131, g = 10, x = 7:
+ y = 107 mod 131 = 115
+ giả sử, kí tự J (ASCII giá trị 74) , lựa chọn k =3 ( k là nguyên tố cùng nhau với 130).
+ a = [gk mod p] = 103 mod 131 = 83 và b = [myk mod p] = (74*1153) mod 131 = 30
Như vậy, giá trị của a và b (83 và 30) là ciphertext được kết hợp với 74(J). Để giải mã a và b, tính m=(30/837) mod 131 = 74.
Không có nhận xét nào:
Đăng nhận xét