Bảo mật của thuật toán RSA là gì?

Phần này thảo luận về tính bảo mật của thuật toán mã hóa khóa công khai RSA. Khóa riêng RSA không an toàn 100%. Nhưng nếu khóa riêng sử dụng giá trị n = p*q lớn hơn, sẽ mất rất nhiều thời gian để bẻ khóa khóa riêng

Tính bảo mật của thuật toán mã hóa khóa công khai RSA chủ yếu dựa trên bài toán phân tích thừa số nguyên, có thể được mô tả như sau:

Given integer n as the product of 2 distinct prime numbers p and q, 
find p and q.

Nếu vấn đề trên có thể được giải quyết thì mã hóa RSA hoàn toàn không an toàn. Điều này là do khóa công khai {n,e} được công chúng biết đến. Bất kỳ ai cũng có thể sử dụng khóa chung {n,e} để tìm ra khóa riêng {n,d} bằng các bước sau

• Tính p và q bằng cách phân tích n
• Tính m = (p-1)*(q-1)
• Tính d sao cho d*e mod m = 1 để lấy khóa riêng {n,d}

Nếu n nhỏ, bài toán phân tích thành thừa số nguyên rất dễ giải quyết bằng cách kiểm tra tất cả các số nguyên tố có thể có trong khoảng (1, n)

Ví dụ: cho 35 là n, chúng ta có thể liệt kê tất cả các số nguyên tố trong phạm vi (1, 35). 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 và 31, và thử tất cả các tổ hợp của chúng để tìm 5 và 7 là thừa số của 35

Khi giá trị của n càng lớn, bài toán phân tích thành thừa số nguyên càng khó giải. Nhưng nó vẫn có thể giải quyết được với việc sử dụng máy tính. Ví dụ: số RSA-100 với 100 chữ số thập phân hoặc 330 bit, đã được Arjen K phân tích. Ống kính vào năm 1991

RSA-100 = 15226050279225333605356183781326374297180681149613
          80688657908494580122963258952897654000350692006139
 
    p*q = 37975227936943673922808872755445627854565536638199
        * 40094690950920881030683735292761468389214899724061

Nếu bạn đang sử dụng số RSA-100 ở trên làm n, thì khóa riêng tư của bạn không còn là khóa riêng tư nữa

Tính đến hôm nay, giá trị cao nhất của n đã được phân tích là số RSA-678 với 232 chữ số thập phân hoặc 768 bit, được phân tích bởi Thorsten Kleinjung et al. vào năm 2009

RSA-768 = 12301866845301177551304949583849627207728535695953
          34792197322452151726400507263657518745202199786469
          38995647494277406384592519255732630345373154826850
          79170261221429134616704292143116022212404792747377
          94080665351419597459856902143413

    p*q = 33478071698956898786044169848212690817704794983713
          76856891243138898288379387800228761471165253174308
          7737814467999489
        × 36746043666799590428244633799627952632279158164343
          08764267603228381573966651127923337341714339681027
          0092798736308917        

Khi máy tính của chúng ta ngày càng mạnh mẽ hơn, việc tính toán n 1024 bit sẽ sớm trở thành hiện thực. Đây là lý do tại sao các chuyên gia khuyên chúng ta

Thuật toán mã hóa Rivest-Shamir-Adleman (RSA) là một thuật toán mã hóa bất đối xứng được sử dụng rộng rãi trong nhiều sản phẩm và dịch vụ. Mã hóa bất đối xứng sử dụng một cặp khóa được liên kết toán học để mã hóa và giải mã dữ liệu. Khóa riêng và khóa chung được tạo, trong đó bất kỳ ai cũng có thể truy cập khóa chung và khóa riêng là bí mật chỉ được biết bởi người tạo cặp khóa. Với RSA, khóa riêng hoặc khóa chung có thể mã hóa dữ liệu, trong khi khóa khác giải mã dữ liệu đó. Đây là một trong những lý do RSA là thuật toán mã hóa bất đối xứng được sử dụng nhiều nhất

RSA hoạt động như thế nào?

Tùy chọn mã hóa bằng khóa riêng hoặc khóa chung cung cấp vô số dịch vụ cho người dùng RSA. Nếu khóa công khai được sử dụng để mã hóa, khóa riêng phải được sử dụng để giải mã dữ liệu. Điều này là hoàn hảo để gửi thông tin nhạy cảm qua mạng hoặc kết nối Internet, nơi người nhận dữ liệu gửi cho người gửi dữ liệu khóa công khai của họ. Người gửi dữ liệu sau đó mã hóa thông tin nhạy cảm bằng khóa chung và gửi cho người nhận. Vì khóa chung đã mã hóa dữ liệu nên chỉ chủ sở hữu khóa riêng mới có thể giải mã dữ liệu nhạy cảm. Do đó, chỉ người nhận dự định của dữ liệu mới có thể giải mã nó, ngay cả khi dữ liệu được lấy trong quá trình vận chuyển

Phương pháp mã hóa bất đối xứng khác với RSA là mã hóa tin nhắn bằng khóa riêng. Trong ví dụ này, người gửi dữ liệu mã hóa dữ liệu bằng khóa riêng của họ và gửi dữ liệu được mã hóa cùng với khóa chung của họ cho người nhận dữ liệu. Sau đó, người nhận dữ liệu có thể giải mã dữ liệu bằng khóa công khai của người gửi, do đó xác minh người gửi là người mà họ nói. Với phương pháp này, dữ liệu có thể bị đánh cắp và đọc trong quá trình chuyển tiếp, nhưng mục đích thực sự của loại mã hóa này là để chứng minh danh tính của người gửi. Nếu dữ liệu bị đánh cắp và sửa đổi trong quá trình truyền, khóa công khai sẽ không thể giải mã tin nhắn mới và do đó người nhận sẽ biết dữ liệu đã được sửa đổi trong quá trình truyền

Các chi tiết kỹ thuật của RSA hoạt động dựa trên ý tưởng rằng có thể dễ dàng tạo ra một số bằng cách nhân hai số đủ lớn với nhau, nhưng việc phân tích số đó trở lại các số nguyên tố ban đầu là vô cùng khó khăn. Khóa công khai và khóa riêng được tạo bằng hai số, một trong số đó là tích của hai số nguyên tố lớn. Cả hai đều sử dụng hai số nguyên tố giống nhau để tính giá trị của chúng. Các khóa RSA có xu hướng dài 1024 hoặc 2048 bit, khiến chúng cực kỳ khó phân tích, mặc dù các khóa 1024 bit được cho là sẽ sớm bị phá vỡ

Ai sử dụng mã hóa RSA?

Như đã mô tả trước đây, mã hóa RSA có một số nhiệm vụ khác nhau mà nó được sử dụng cho. Một trong số đó là ký điện tử cho mã và chứng chỉ. Chứng chỉ có thể được sử dụng để xác minh khóa công khai thuộc về ai, bằng cách ký tên đó bằng khóa riêng của chủ sở hữu cặp khóa. Điều này xác thực chủ sở hữu cặp khóa là một nguồn thông tin đáng tin cậy. Ký mã cũng được thực hiện với thuật toán RSA. Để đảm bảo chủ sở hữu không gửi mã nguy hiểm hoặc không chính xác cho người mua, mã được ký bằng khóa riêng của người tạo mã. Điều này xác minh rằng mã không bị chỉnh sửa ác ý trong quá trình truyền và người tạo mã xác minh rằng mã thực hiện những gì họ đã nói.

RSA đã được sử dụng với Transport Layer Security (TLS) để bảo mật thông tin liên lạc giữa hai cá nhân. Các sản phẩm và thuật toán nổi tiếng khác, như thuật toán Pretty Good Privacy, sử dụng RSA hiện tại hoặc trong quá khứ. Mạng riêng ảo (VPN), dịch vụ email, trình duyệt web và các kênh liên lạc khác cũng đã sử dụng RSA. VPN sẽ sử dụng TLS để thực hiện bắt tay giữa hai bên trong quá trình trao đổi thông tin. Bắt tay TLS sẽ sử dụng RSA làm thuật toán mã hóa của nó, để xác minh cả hai bên là những người họ nói họ là ai

Lỗ hổng RSA

Mặc dù khả thi trong nhiều trường hợp, vẫn còn một số lỗ hổng trong RSA có thể bị kẻ tấn công khai thác. Một trong những lỗ hổng này là việc triển khai khóa dài trong thuật toán mã hóa. Các thuật toán như AES không thể bị phá vỡ, trong khi RSA dựa vào kích thước của khóa để khó bị phá vỡ. Khóa RSA càng dài thì càng an toàn. Sử dụng phép tính thừa số nguyên tố, các nhà nghiên cứu đã tìm cách bẻ khóa thuật toán RSA khóa 768 bit, nhưng họ đã mất 2 năm, hàng nghìn giờ làm việc và một lượng điện toán vô lý, vì vậy độ dài khóa hiện đang được sử dụng trong RSA vẫn an toàn. Viện Khoa học và Công nghệ Quốc gia (NIST) hiện khuyến nghị độ dài tối thiểu của khóa là 2048 bit, nhưng nhiều tổ chức đã sử dụng khóa có độ dài 4096 bit. Các cách khác RSA dễ bị tổn thương là

Thuật toán RSA an toàn đến mức nào?

Làm cách nào để tăng tính bảo mật của một thuật toán như RSA?

Thuật toán RSA trong mật mã và an ninh mạng là gì?