NỘI DUNG
1. Mô hình thực hiện
2. Phân tích thời gian phá mã
3. Phân tích thời gian thực hiện
4. Các mô hình áp dụng trong lưu trữ,
truyền thông có thể áp dụng được
1


MÔ HÌNH THỰC HIỆN

2


Cơ sở toán học của RSA
 Bài toán
p, q: số nguyên tố
φ (n) = (p-1)*(q-1)
bφ (n)=1 (mod n)
 Công thức tính toán
ab≡ 1 (mod φ (n))
xab = x(tφ (n)+1) = xtφ (n)x1 = 1x = x


3


Khóa công khai

Thông điệp
gốc





Một số vấn đề liên quan đến hệ
RSA
• Hệ thống dựa trên việc khó khăn
phân tích hai thừa số p, q từ n.



Một số khó khăn trong triển khai
• Tính số nguyên tố p, q với số lượng
bit 1024, 2048
• Tính giá trị e, d (euclid mở rộng)
• Tốc độ tính toán của xa, yb
7


PHÁ MÃ RSA

8


TẤN CÔNG VÉT CẠN
•

Là phương pháp thử tất cả các khóa riêng có thể

•

1. a = 2
2. for j = 2 to B do
a = ai mod n
3. d = gcd(a − 1, n)
4. if 1 < d < n then
d là thừa số nguyên tố của n
else
không xác định được thừa số nguyên tố của n
11


TẤN CÔNG TOÁN HỌC
•

Phân tích ra thừa số p -1 (tiếp)
Độ phức tạp của thuật toán là O(B log B(log n)2
+ (log n)3 )
Tuy nhiên xác suất chọn giá trị B tương đối nhỏ
và thỏa điều kiện
(p-1) | B! Là rất thấp
Nếu tăng giá trị B (B ≈n ) thì giải thuật sẽ thành
công nhưng thuật toán này không nhanh hơn
thuật toán đã trình bày bên trên
Giải thuật này chỉ hiệu quả khi tấn công phương
pháp RSA trong
trường hợp n có thừa số
nguyên tố p mà (p -1) có các ước số nguyên
tố rất nhỏ
12



TẤN CÔNG THỜI GIAN
•

Phát triển vào giữa năm 1990

•

Paul Kocher chỉ ra rằng kẻ thám mã có thể xác định
được khóa riêng nếu theo dõi thời gian máy tính cần
để giải mã các bản tin

•

Tấn công thời gian không chỉ áp dụng cho RSA, mà
cả với các hệ mã công khai khác

•

Tấn công thời gian giống như kẻ cướp đoán số điện
thoại bằng cách quan sát một người nào đó trong
bao lâu chuyển quay điện thoại từ số này sang số
khác

14


• Hiện nay mã hóa RSA 1024 bits đã bị phá vỡ
• Các nhà khoa học thuộc đại học Michigan vừa công
bố phát hiện ra một kẽ hở trong hệ thống mật mã

Điều này không cho phép đối phương biết các bit như thế nào của văn bản
mã đã được gia công bổ xung và đồng thời không tạo cho đối phương dẫn ra
sự phân tích theo loạt, đây là xu thế riêng được thực hiện dựa trên sự phân
tích chi phí thời gian.
17


Qua việc tìm hiểu thời gian hoạt
động của mã hóa công khai.Rút
ra một số nhận xét


Việc sử dụng cặp khóa không đối xứng tuy có điểm là quá trình giải mã
nhiều thời gian, nhưng với hệ mã này, bài toán giữ bí mật không những
giải quyết mà còn được ứng dụng rộng rãi, đảm bảo được bốn nội dung cơ
bản là: tính bí mật, tính toàn vẹn, tính xác thực và tính trách nhiệm.



Từ các kết quả trên cho thấy rằng khi dùng thuật toán RSA để mã hóa các
thông tin và chứng thực trong giao dịch điện tử, với mục đích bảo mật và
đảm bảo tính xác thực thì:

- Đỡ tốn công sức đầu tư cho hạ tầng bảo mật
- Độ bảo mật của thông tin tỉ lệ thuận với độ dài của khóa.
- Chiều dài của khóa 2048 bit tỏ ra là hiệu quả cho đến lúc bấy giờ.
- Tận dụng được tốc độ của máy tính trong việc mã hóa, giả mã và xác
thực.

18