Mã hóa đối xứng d rằng đã phát triển từ cổ điển đến hiện đại, vẫn tồn tại hai điểm
yếu sau:
Vấn đề trao đổi khóa giữa người gửi và người nhận: Cần phải có một kênh an toàn để
trao đổi khóa sao cho khóa phải được giữ bí mật chỉ có người gửi và người nhận biết.
Việc thiết lập một kênh an toàn như vậy sẽ tốn kém về mặt chi phí và chậm trễ về mặt
thời gian. Điều này tỏ ra không hợp lý khi mà ngày nay khối lượng thông tin luân
chuyển trên khắp thế giới là rất lớn. Vì vậy cần một giải pháp an toàn, nhanh gọn, rẻ
tiền và tận dụng hạ tầng mạng Internet có sẵn.
Tính chịu trách nhiệm về khóa: không có cơ sở quy trách nhiệm nếu khóa bị tiết lộ.
Vào năm 1976 Whitfield Diffie và Martin Hellman đã tìm ra một phương pháp mã mật
khác mà có thể giải quyết được hai vấn đề trên, đó là mã hóa khóa công khai hay còn gọi là
17
mã hóa bất đối xứng, xem Hình 1.6. Đây có thể xem là một bước đột phá quan trọng nhất
trong lĩnh vực mã mật.
Hình 1.6 Mô hình mã hóa khóa công khai:
a)Ứng dụng trong xác thực; b) Ứng dụng trong bảo mật.
Thuật toán mã hóa RSA [49] là một thuật toán điển hình về mã hóa khóa công khai.
RSA được xây dựng bởi các tác giả Ron Rivest, Adi Shamir và Len Adleman tại học viện
MIT vào năm 1977. Cũng như các thuật toán mã hóa công khai khác, nguyên lý của RSA
dựa chủ yếu trên lý thuyết số chứ không dựa trên các thao tác xử lý bit.
RSA là một thuật toán mật mã khối, kích thước khối thông thường là 1024 hoặc
2048 bit. Thông tin gốc của RSA được xử lý như các số nguyên. Ví dụ, khi chọn kích
thước khối của thuật toán là 1024 bit thì thuật toán xử lý các số nguyên có giá trị từ 0 đến
21024 – 1, tương đương với số thập phân có 309 chữ số. Chú ý rằng đây là những số nguyên
cực lớn, không thể xử lý được bằng cách sử dụng các cấu trúc dữ liệu có sẵn của các ngôn
ngữ lập trình phổ biến.
Cơ sở lý thuyết của thuật toán RSA dựa trên lý thuyết về số nguyên tố, phép toán
modulo và định lý Euler.
Nguyên lý làm việc của thuật toán RSA:
Tạo khóa: 1) Chọn hai số nguyên tố đủ lớn p và q và gọi N là tích của chúng, N = pq.
2) Chọn một số e sao cho e và n = (p-1)(q-1) là hai số nguyên tố c ng nhau.
Sau đó tìm số d sao cho e.d = 1 mod n. Ký hiệu mod n là biểu diễn phép
modulo trên cơ số n.
18
+ Khóa công khai (public key) là tổ hợp (N, e)
+ Khóa bí mật (private key) là tổ hợp (N, d)
Mã hóa: Việc mã hóa một khối thông tin gốc M được thực hiện theo công thức:
+ C = Me mod N Ứng với trường hợp bảo mật
+ C = Md mod N Ứng với trường hợp xác thực
Giải mã: Quá trình giải mã C được thực hiện theo tương ứng ngược lại:
+ M = Cd mod N
+ M = Ce mod N
Độ phức tạp của thuật toán RSA:
Có hai vấn đề về độ phức tạp tính toán trong thuật toán RSA. Đó là các phép tính mã
hóa/giải mã và các phép tính sinh khóa.
Phép tính mã hóa và giải mã d ng phép lũy thừa modulo. Nếu thực hiện bằng cách
tính phép lũy thừa trước sau đó rút gọn modulo, thì giá trị của phép lũy thừa là quá lớn để
có thể lưu trữ và tính toán. Tuy nhiên phép modulo có một tính chất sau:
Tóm Tắt
a x b
a mod n x b mod n
mod n (1.3)
Chúng ta có thể sử dụng tính chất này để đơn giản phép tính lũy thừa modulo thông
qua một phương pháp gọi là “bình phương liên tiếp”. Ví dụ cần tính x16 mod n, đầu tiên sẽ
tính a = x mod n , tiếp theo là b = x2 mod n = a2 mod n, tiếp theo là c = x4
mod n = b2 mod
n, tiếp theo là d = x8
mod n = c2 mod n, và cuối c ng x16
mod n = d2 mod n. Các số a, b, c, d
luôn nhỏ hơn n do đó tránh được việc tính số lũy thừa lớn đồng thời nâng cao tốc độ tính
toán.
Phép tính sinh khóa là chọn p và q nguyên tố để tính N. Để phân tích số N thành tích
hai thừa số nguyên tố p, q, chỉ có một cách duy nhất là thử từng số p và q. Do đó phải chọn
p, q đủ lớn để việc thử là không khả thi. Hiện nay chưa có phương pháp nào để sinh ra số
nguyên tố lớn t y ý. Chỉ có cách là chọn một số lẻ ngẫu nhiên nào đó và kiểm tra số đó có
phải là số nguyên tố không. Việc kiểm tra tính nguyên tố cũng gặp nhiều khó khăn. Thuật
toán kiểm tra số nguyên tố hiệu quả hiện nay là thuật toán Miller-Rabin, d rằng không
hoàn toàn chính xác 100%, tuy nhiên có thể đạt sai số nhỏ không đáng kể.
Chúng ta thường chọn trước e là 65537 hoặc 3 hoặc 17, vì các số này khi biểu diễn ở
dạng nhị phân chỉ có 2 chữ số 1, nên khi thực hiện lệnh lũy thừa sẽ giảm đi lệnh nhân. Ta
cần kiểm tra xem e có nguyên tố c ng nhau với n = (p-1)(q-1) hay không. Nếu không ta
phải thử lại với cặp số p và q khác. Sau khi đã có p và q thích hợp, cần tìm d sao cho e.d
1 mod n. Bằng cách d ng thuật toán Euclid mở rộng, chúng ta có thể kết hợp việc kiểm tra
tính nguyên tố c ng nhau của e và n, đồng thời nếu e nguyên tố c ng nhau với n thì thuật
toán cũng cho biết d. Vì vậy không cần tiến hành bước tìm d riêng.
19
Độ an toàn của thuật toán RSA:
Độ an toàn của thuật toán RSA dựa trên độ khó của bài toán phân tích một số thành
nhân tử. Việc đo lường tính bảo mật của RSA đã trình bày trong [57], Kefa Rabah chỉ ra
rằng vào năm 1994 để phân tích số thập phân N có129 số (tương ứng số nhị phân 426 bit)
thành tích hai thừa số nguyên tố lớn c ng nhau phải cần 5.000 MIPS-year (một MIPS-year
bằng một năm hoạt động liên tục của máy tính có tốc độ thực hiện một triệu lệnh trong một
giây), tương đương việc sử dụng thời gian nhàn rỗi của 1.600 máy tính trên toàn thế giới
trong thời gian tám tháng. Điều này cho thấy với N lớn thì việc tìm khóa của thuật toán
RSA vô c ng khó khăn. Khi sử dụng thuật toán mã hóa RSA để mã hóa khóa bí mật, chiều
dài khóa 512 đến 1024 bit là cần thiết, và để bảo vệ các giao dịch giá trị rất cao thì sử dụng
khóa dài trên 1024 bit.
Bảng 1.4 Thử nghiệm độ bảo mật của RSA
Số bit của N Số thao tác Thời gian
100 9,6 x 108 16 phút
200 3,3 x 1012 38 ngày
300 1,3 x 1015 41 năm
400 1,7 x 1017 5.313 năm
500 1,1 x 1019 3,3 x 105 năm
1024 1,3 x 1026 4,2 x 1012 năm
2048 1,5 x 1035 4,9 x 1021năm
