Chương 1 TỔNG QUAN VỀ MẬT MÃ HỌC
6. Mật mã hóa công khai
6.4.8. Sơ đồ cải tiến THA 1
Trong sơ đồ này, khóa bí mật là hai số nguy n tố có dạng: và khóa công khai là số nguy n .
Thuật toán mã hóa
Biết bản rõ M thuộc bản mã được xác định theo các bước:
Bước 1: Xác định :
Bước 2: Xác định bản mã theo công thức:
Thuật toán giải mã
Biết bản mã , bản rõ được xác định theo các bước:
Bước 1: Tính
Bước 2: Xét phương trình:
Nếu hoặc thì xác định nghiệm , còn nếu hoặc xác định nghiệm của phương trình tr n theo các công thức trong mục 1.10
Bước 3: Bản rõ được xác định theo và hoặc như sau:
1. Nếu ,
2. Nếu
3. Nếu
4. Nếu β = 3
Tính đúng đắn của sơ đồ THA1
Từ Bước 2 thuật toán mã hóa và Bước 1 thuật toán giải mã suy ra và . Như vậy, là thặng dư bình phương của , n n phương trình ở Bước 2 trong thuật toán giải mã chính là phương trình Rabin và bốn nghiệm
có thể được tính theo các công thức trong mục 1.10
Mặt khác, bản rõ hiển nhi n cũng là một nghiệm của phương trình này. Do đó, phải trùng với một trong bốn nghiệm nói tr n.
Vì , nên có thể nhận một trong bốn giá trị từ 0 đến 3. Ta sẽ lần lượt xét từng trường hợp trong Bước 3 của thuật toán giải mã.
(1) Nếu , thì từ Bước 1 thuật toán mã hóa suy ra hoặc 1 và thuộc nửa tr n ]
2 , 1 0 [ N
. N n theo Bổ đề 2.2, hoặc . Vì vậy, nếu thuộc nửa tr n và nếu trái lại.
(2) Nếu , lập luận tương tự chỉ khác thuộc nửa dưới, do đó nếu thuộc nửa dưới và nếu trái lại.
(3) Nếu , theo thuật toán mã hóa suy ra và thuộc nửa tr n. Do n n theo Bổ đề 2.2, hoặc . Vậy nếu thuộc nửa tr n và nếu trái lại.
(4) Nếu , lập luận tương tự chỉ khác thuộc nửa dưới, do đó nếu thuộc nửa dưới và nếu trái lại.
Vậy, tính đúng đắn của sơ đồ được chứng minh.
Xét thí dụ minh họa lược đồ THA1
Để làm rõ hơn nội dung của sơ đồ THA1, phần này sẽ trình bày hai ví dụ minh họa quá trình mã hóa và giải mã với hai số nguy n tố như sau:
và ,
vậy .
Cặp nguy n được chọn như vậy không thể sử dụng trong lược đồ Shimada và Chen-Tsu, nhưng sử dụng được trong sơ đồ THA1.
Ví dụ 1: Xét
uá tr nh mã hóa:
Bước 1:
(Tính theo thuật toán trong 3 , trang 110).
Do nên
Bước 2:
uá tr nh giải mã:
Bước 1:
Bước 2: Do , xác định nghiệm như sau:
Giải hệ phương trình đồng dư:
thay số ta có:
,
được nghiệm .
Bước 3:
Do và nên . Vậy .
Ví dụ 2: Xét
Quá trình mã hóa:
Bước 1:
(Tính theo thuật toán trong 3 , trang 110).
Do nên .
Bước 3:
Quá trình giải mã:
Bước 1:
Bước 2: Do , xác định nghiệm như sau:
Giải hệ phương trình đồng dư:
, thay số vào ta có:
Được nghiệm .
Bước 3:
Do nên . Vậy .
So sánh các sơ đồ cải tiến
Trong mục này sẽ phân tích, so sánh sơ đồ THA1 với hai sơ đồ Shimada và Chen-Tsu tr n các phương diện: Độ phức tạp tính toán, mức độ bảo mật và phạm vi ứng dụng.
Độ ph c t p tính toán
Độ phức tạp tính toán của thuật toán mã hóa trong cả ba sơ đồ tr n là tương đương vì đều phải tính và . Vì vậy, ở đây chỉ so sánh độ phức tạp tính toán của các thuật toán giải mã.
Trước hết dễ dàng nhận thấy, những tính toán chủ yếu của thuật toán giải mã Shimada gồm:
(1) Tính . Các đại lượng này, trong trường hợp tổng quát, tính theo công thức:
và
Nếu xem phép tính cơ bản là phép nhân và phép chia mod, thì theo [5], số phép tính cần thực hiện xấp xỉ bằng:
(2) Tính các nghiệm của phương trình theo các công thức trong mục 2.2. Trong số đó, hai công thức phức tạp nhất là:
,
Cũng theo [5], thì số phép tính cần dùng xấp xỉ bằng
(3) Tính hai hàm và đối với ít nhất một nghiệm, nhiều nhất 4 nghiệm. Do đó, trung bình phải tính và đối với hai trong số bốn nghiệm , n n số phép tính xấp xỉ bằng
Từ (1), (2) và (3) suy ra, độ phức tạp tính toán của thuật toán giải mã Shimada xấp xỉ bằng:
So với Shimada thì thuật toán giải mã Chen-Tsu giảm được các phép tính ở (3), n n độ phức tạp xấp xỉ bằng:
Thuật toán giải mã trong sơ đồ đề xuất chỉ phải thực hiện các phép tính trong (2), n n độ phức tạp xấp xỉ bằng:
Các kết quả phân tích tr n được trình bày trong bảng sau đây.
Sơ đồ Số ph p toán cơ bản
Sơ đồ đề xuất Chen-Tsu Shimada
Bảng 1. Độ phức tạp tính toán của các thuật toán giải mã
Bảng phân tích tr n cho thấy khối lượng tính thuật toán giải mã trong sơ đồ THA1 chỉ bằng so với sơ đồ Chen-Tsu và bằng so với sơ đồ Shimada. Điều này cũng được thể hiện thông qua kết quả thực nghiệm.
M c độ ảo mật
Trong cả 3 sơ đồ, khóa bí mật là hai số nguy n tố và khóa công khai là số nguyên . Do vậy, mức độ bảo mật của chúng chính là độ khó của bài toán phân tích một số ra hai thừa số nguy n tố.
h m vi ng dụng
Trong cả hai sơ đồ Shimada và Chen-Tsu đều cần dùng tính chất
và Để có được tính chất này, cần chọn p có dạng và q có dạng Cả hai dạng này đều là các trường hợp ri ng của dạng . Thực tế cho thấy tập các số nguy n tố dạng và nhỏ hơn nhiều so với tập các số nguy n tố dạng . Do trong sơ đồ THA vẫn sử dụng các số nguy n tố p, q có dạng , n n sơ đồ này có phạm vi ứng dụng rộng hơn so hai sơ đồ tr n.
Kết quả th c nghiệm
Trong chương trình thực nghiệm sử dụng các số nguy n tố p, q có độ lớn khoảng 60 chữ số. Cụ thể như sau:
p = 430606897333168273518201112510828692695315291101473646891711 q = 196996179941292068795331733133608048430672235582931
Việc so sánh được thực hiện tr n 8 tệp bản rõ với các kích thước khác nhau.
Chương trình chạy tr n máy tính HP 6530s. Thời gian giải mã của các sơ đồ ứng với các tệp bản rõ được thống k ở bảng sau:
ST T
Kích thước tệp
Thời gian giải mã gi y
Shimada Chen - Tsu Sơ đồ THA
1. 100KB 12.2 8.2 7.12
2. 167 KB 37.68 12.68 8.67
3. 267 KB 40.4 17.4 9.53
4. 394 KB 57.3 26.3 10.57
5. 501 KB 73.56 30.56 13.34
6. 1.229 MB 145.34 78 33.46
7. 1.558MB 189.67 107.8 42.34
8. 5.2 MB 674.25 289.74 130
Bảng 2. Thời gian thực hiện của các thuật toán giải mã