RSA là gì? Cách thức hoạt động của mã hóa RSA

Hệ thống mã hóa rsa giải quyết một trong những vấn đề bảo mật lớn nhất từ ​​trước đến nay: làm cách nào để gửi một tin nhắn được mã hóa cho ai đó mà không có cơ hội chia sẻ? mã trước đó? Bài viết này sẽ hướng dẫn bạn cách mã hóa rsa, cách nó được phát triển và hoạt động cũng như một số vấn đề bảo mật mà nó phải đối mặt.

rsa là gì?

Giả sử bạn muốn cho bạn mình biết một bí mật. Nếu bạn ở ngay bên cạnh họ, bạn chỉ cần thì thầm điều gì đó. Sẽ không an toàn nếu bạn ở hai quốc gia đối lập nhau. Bạn có thể viết nó ra và gửi cho họ qua thư hoặc điện thoại. Nhưng nó không an toàn và bất kỳ ai có đủ động lực đều có thể chặn tin nhắn.

Nếu bí mật đủ quan trọng, bạn không nên mạo hiểm viết nó ra. Gián điệp hoặc nhân viên bưu điện lừa đảo có thể nhìn thấy nó qua thư của bạn. Tương tự như vậy, ai đó có thể nghe trộm điện thoại của bạn mà bạn không biết và họ sẽ ghi lại mọi cuộc gọi của bạn.

Một giải pháp để ngăn những kẻ nghe trộm truy cập vào nội dung tin nhắn là mã hóa nó. Về cơ bản, điều này có nghĩa là thêm mã vào tin nhắn và nó làm cho tin nhắn trở nên lộn xộn. Nếu mã của bạn đủ phức tạp, những người duy nhất có quyền truy cập vào thư gốc là những người có quyền truy cập vào mã.

Nếu trước đây bạn đã có cơ hội chia sẻ mã với bạn bè của mình, một trong hai người có thể gửi tin nhắn được mã hóa bất kỳ lúc nào. Nhưng nếu bạn không có cơ hội chia sẻ mã đó thì sao?

Đây là một trong những vấn đề cơ bản của mật mã và đã được giải quyết bằng các sơ đồ mã hóa khóa công khai như rsa (còn được gọi là mã hóa không đối xứng).

Theo mã hóa rsa, thư được mã hóa bằng mã được gọi là khóa công khai, mã này có thể được chia sẻ công khai. Do một số thuộc tính tính toán khoa học độc đáo của thuật toán rsa, một khi một thông điệp được mã hóa bằng khóa công khai, nó chỉ có thể được giải mã bằng một khóa được gọi là khóa riêng. Mỗi người dùng rsa có một cặp khóa bao gồm khóa công khai và khóa riêng của họ. Khóa riêng tư cần được giữ bí mật.

Lược đồ khóa công khai khác với khóa đối xứng và cả mã hóa và giải mã đều phải sử dụng khóa riêng tư. Những khác biệt này làm cho mã hóa khóa công khai như rsa trở nên hữu ích cho các giao tiếp mà trước đây không có cơ hội để phân phối khóa một cách an toàn.

Thuật toán khóa đối xứng có các ứng dụng riêng của nó. Chẳng hạn như mã hóa dữ liệu để sử dụng riêng tư hoặc khi có một kênh bảo mật có thể được chia sẻ một cách riêng tư.

Trong mật mã, rsa là một thuật toán mật mã khóa công khai. Đây là thuật toán đầu tiên thích hợp để tạo chữ ký điện tử cùng lúc với mã hóa. Nó đánh dấu một bước tiến lớn trong việc sử dụng khóa công khai trong lĩnh vực mật mã. rsa được sử dụng rộng rãi trong thương mại điện tử và được cho là an toàn nếu độ dài khóa đủ lớn. – Wikipedia

Mã hóa rsa được sử dụng ở đâu?

Mã hóa rsa thường được sử dụng kết hợp với các lược đồ mã hóa khác. Và chữ ký điện tử có thể chứng minh tính xác thực và tính toàn vẹn của thông điệp. Nó thường không được sử dụng để mã hóa toàn bộ tin nhắn và tệp vì nó kém hiệu quả và tốn nhiều tài nguyên hơn so với mã hóa khóa đối xứng.

Để đạt hiệu quả cao, các tệp thường được mã hóa bằng thuật toán khóa đối xứng. Sau đó, khóa đối xứng sẽ được mã hóa bằng mã hóa rsa. Theo quy trình này, chỉ ai đó có quyền truy cập vào khóa cá nhân rsa mới có thể giải mã khóa đối xứng.

Không thể giải mã tệp gốc nếu không có quyền truy cập vào khóa đối xứng. Phương pháp này có thể được sử dụng để bảo vệ thư và tệp mà không tốn nhiều thời gian và tài nguyên.

Mã hóa rsa có thể được sử dụng trên nhiều hệ thống khác nhau. Nó hoạt động trong openssl, wolfcrypt, cryptlib và một số thư viện mật mã khác.

theo truyền thống được sử dụng trong tls và cũng là thuật toán ban đầu được sử dụng trong mã hóa pgp. RSA vẫn hiện diện trong nhiều trình duyệt web, email, VPN, cuộc trò chuyện và các kênh liên lạc khác.

rsa cũng thường được sử dụng để tạo kết nối an toàn giữa máy khách vpn và máy chủ vpn. Theo các giao thức như openvpn, TLS có thể sử dụng thuật toán RSA để trao đổi khóa và thiết lập một kênh bảo mật.

Mã hóa rsa hoạt động như thế nào?

Phần tiếp theo đơn giản hơn. Bởi vì quá nhiều người đọc có thể bị giáo viên trung học của họ đe dọa để viết mã. Chúng tôi sẽ đơn giản hóa một số khái niệm và sử dụng các số đơn giản hơn. Trong thực tế, mã hóa rsa sử dụng các số nguyên tố lớn hơn theo thứ tự và có một số trường hợp phức tạp.

Có nhiều khái niệm khác nhau mà bạn cần hiểu trước khi chúng tôi giải thích chúng. Chúng bao gồm các hàm cửa sập, bộ tạo số nguyên tố, hàm không phải Carmichael. Và các quy trình riêng biệt liên quan đến việc tính toán các khóa công khai và riêng tư được sử dụng trong mã hóa và giải mã.

Chức năng cửa sập

Tiền đề của mã hóa rsa là thuật toán dễ dàng tính toán theo một hướng. Nhưng làm điều ngược lại gần như là không thể. Ví dụ, nếu bạn được cho biết 701.111 là tích của hai số nguyên tố, bạn có thể tìm xem hai số đó là gì không?

Ngay cả với máy tính hoặc máy tính cá nhân, hầu hết chúng ta đều không biết bắt đầu từ đâu, chưa nói đến việc tìm hiểu. Nhưng sẽ dễ dàng hơn rất nhiều nếu bạn lật lại mọi thứ. Kết quả:

907 x 773

Nếu bạn sử dụng máy tính để làm bài toán này, bạn sẽ thấy rằng câu trả lời là 701.111 và nó đã được đề cập. 907 và 773 là hai số nguyên tố trả lời câu hỏi đầu tiên của chúng tôi. Điều này cho chúng ta thấy rằng một số phương trình có thể được giải một cách dễ dàng, nhưng điều ngược lại dường như là không thể.

Một khía cạnh thú vị khác của phương trình này là nếu bạn đã có một phương trình khác, việc tìm một số nguyên tốt rất đơn giản. Nếu bạn cho 701.111 là kết quả của phép nhân 907 với một số nguyên tố khác, bạn sẽ thấy rằng số nguyên tố này có phương trình sau:

701,111 907 = 773

Do đó, rsa sử dụng một số lớn hơn. Các số nguyên tố có cùng kích thước trong các phép toán rsa. Nhưng trong rsa 2048-bit, chúng sẽ kết hợp để tạo ra một khóa dài 617-bit. Để hình dung nó, các phím sẽ là các số có kích thước sau:

Tạo số nguyên tố

Các chức năng cửa sập được mô tả ở trên tạo cơ sở cho cách thức hoạt động của các lược đồ mã hóa khóa công khai và khóa riêng tư. Thuộc tính của chúng cho phép chia sẻ khóa công khai mà không ảnh hưởng đến tin nhắn hoặc tiết lộ khóa riêng tư. Chúng cũng cho phép dữ liệu được mã hóa bằng một khóa theo cách chỉ có thể được giải mã bằng khóa kia.

Các số nguyên tố trong rsa phải rất lớn và xa nhau. Các số nhỏ hơn hoặc gần hơn sẽ dễ bị bẻ khóa hơn. Tuy nhiên, các ví dụ của chúng tôi sẽ sử dụng các số nhỏ hơn để giúp theo dõi và tính toán mọi thứ dễ dàng hơn.

Giả sử các số nguyên tố 907 và 773 mà chúng tôi đã sử dụng ở trên để kiểm tra tính nguyên thủy. Bước tiếp theo là khám phá module (n), sử dụng công thức sau:

n = p x q

trong đó p = 907 và q = 773

Do đó:

n = 907 x 773

n = 701.111

Hàm không Carmichael

Sau khi có n, chúng tôi sẽ sử dụng các hàm không phải carmichael:

λ (n) = lcm (p – 1, q – 1)

Phần này có thể hơi phức tạp. Bạn có thể bỏ qua nó và chỉ cần tin tưởng rằng phép toán hoạt động. Nếu chưa, hãy theo dõi chúng tôi để có thêm những tính toán khác. Mọi thứ sẽ được giải thích chi tiết nhất có thể để giúp bạn nắm vững những điều cơ bản.

Đối với những người chưa biết, λ (n) là ký hiệu cho các hàm không phải carmichael và lcm là bội số chung nhỏ nhất – số nhỏ nhất mà cả p và q đều có thể chia được. Có một số cách khác nhau để giải quyết vấn đề này, nhưng cách dễ nhất là tin tưởng vào một máy tính trực tuyến để tìm ra phương trình cho bạn. Vì vậy, hãy đặt các con số của chúng ta vào phương trình:

(701,111) = lcm (907 – 1, 773 – 1)

(701,111) = lcm (906, 772)

Sử dụng máy tính, chúng tôi nhận được:

(701,111) = 349,716

Tạo khóa công khai

Giờ đây, chúng tôi đã ghi lại số nguyên tố cho các hàm không phải carmichael. Đã đến lúc tìm ra khóa công khai. Theo rsa, khóa công khai bao gồm một số nguyên tố e và một mô-đun n (chúng tôi sẽ giải thích mô-đun là gì trong một vài đoạn văn). Số e có thể là bất kỳ giá trị nào từ 1 đến λ (n), trong ví dụ của chúng ta là 349,716.

Vì khóa công khai được chia sẻ công khai, không quan trọng nếu e là một số ngẫu nhiên. Trong thực tế, e thường được đặt là 65,537. Bởi vì khi các số lớn hơn được chọn ngẫu nhiên, nó làm cho việc mã hóa trở nên tồi tệ hơn. Đối với ví dụ này, chúng tôi sẽ giữ các số nhỏ để tính toán hiệu quả. Nếu:

e = 11

Dữ liệu được mã hóa cuối cùng của chúng tôi được gọi là ciphertext (c). Chúng tôi nhận được nó từ thông báo bản rõ (m). Áp dụng khóa công khai bằng cách sử dụng công thức sau:

c = me mod n

Như đã đề cập trước đó, e mod n là khóa công khai. Chúng tôi đã đặt một giá trị cho e và cũng biết n. Điều duy nhất chúng ta cần giải thích là mod. Về cơ bản nó là phần dư khi hai số bị chia. Ví dụ:

10 mô-đun 3 = 1

Điều này là do 10 chia cho 3 được 3 nhân 3 với phần dư là 1.

Quay lại phương trình của chúng tôi. Để đơn giản, giả sử rằng (m) thông điệp mà chúng ta muốn mã hóa và giữ bí mật chỉ là một số 4.

c = me mod n

c = 411 mod 701.111

c = 4,194.304 mod 701,111

Một lần nữa, để làm cho mô-đun dễ làm việc hơn, chúng tôi sẽ sử dụng máy tính trực tuyến. Bằng cách nhập 4,194.304 vào máy tính, nó sẽ cho chúng ta:

c = 688,749

Vì vậy, khi chúng tôi mã hóa thư của mình bằng rsa, 4. sử dụng khóa công khai, nó sẽ cung cấp cho chúng tôi bản mã là 688,749. Các bước trước có thể hơi nặng về toán học.

Chúng tôi đã có một thông báo 4 mà chúng tôi muốn giữ kín. Chúng tôi đã áp dụng khóa công khai cho nó và nhận được kết quả mã hóa là 688,749. Bây giờ nó đã được mã hóa, số 688,749 có thể được gửi đến chủ nhân của cặp khóa một cách an toàn. Họ là những người duy nhất có thể giải mã thông tin cá nhân của họ. Khi họ giải mã, họ sẽ thấy tin nhắn mà chúng tôi đã gửi, 4.

Tạo khóa cá nhân

Trong mã hóa rsa, một khi khóa công khai được sử dụng để chuyển đổi dữ liệu hoặc tin nhắn thành bản mã. Nó chỉ có thể được giải mã bằng cách sử dụng khóa riêng từ cùng một cặp khóa. Khóa riêng bao gồm d và n. Chúng ta đã biết n, hãy tìm d bằng phương trình sau:

d = 1 / e mod (n)

Trong tạo khóa công khai, chúng tôi chọn e = 11. Một lần nữa, chúng ta biết từ phép tính ở trên rằng λ (n) bằng 349,716. Nhìn vào phần này của công thức, mọi thứ sẽ phức tạp hơn một chút:

Mô-đun 1 / e

Phương trình này có thể yêu cầu bạn chia 1 cho 11, nhưng không. Thay vào đó, nó chỉ có nghĩa là chúng ta cần tính nghịch đảo của môđun của e (trong trường hợp này là 11) và λ (n) (trong trường hợp này là 349,716).

Về cơ bản, điều này có nghĩa là thay vì thực hiện phép toán mô đun chuẩn, chúng ta sẽ sử dụng phép toán nghịch đảo. Điều này xảy ra thường xuyên trong Thuật toán Euclid mở rộng, nhưng nằm ngoài phạm vi của bài viết này. Vì vậy, chúng tôi sẽ sử dụng một máy tính trực tuyến. Bây giờ chúng tôi kết hợp thông tin đã có trong công thức:

d = 1/11 bản sửa đổi 349,716

Để thực hiện việc này, chỉ cần nhập 11 (hoặc bất kỳ giá trị nào bạn gán cho e), trong đó số nguyên là 349,716 (hoặc bất kỳ giá trị nào bạn đã tính cho λ (n)). Nếu làm đúng, bạn sẽ nhận được kết quả:

d = 254, 339

Bây giờ chúng ta có giá trị là d, chúng ta có thể giải mã tin nhắn được mã hóa bằng khóa công khai bằng công thức sau:

m = cd mod n

Bây giờ quay lại bản mã (c) được mã hóa trong phần khóa riêng tư. Khi mã hóa một tin nhắn bằng khóa công khai, nó cho giá trị c là 688,749. Như trên, chúng ta đã biết rằng d = 254,339. Chúng ta đã biết rằng n = 701,111. Điều này mang lại:

m = 688,749254,339 mod 701,111.

Bạn có thể nhận thấy rằng cố gắng tăng một số lên lũy thừa của 254,339 có thể hơi quá đối với một máy tính bình thường. Thay vào đó, chúng tôi sẽ sử dụng máy tính giải mã rsa trực tuyến.

Sau khi nhập dữ liệu, nhấn Giải mã, thao tác này sẽ chuyển số thông qua công thức giải mã được liệt kê ở trên. Nếu bạn đã làm đúng mọi thứ, bạn sẽ nhận được câu trả lời là 4. Đây là tin nhắn ban đầu mà chúng tôi đã mã hóa bằng khóa công khai.

Cách mã hóa rsa hoạt động trong thực tế

Phần trên sẽ cung cấp cho bạn sự hiểu biết hợp lý về toán học đằng sau mã hóa khóa công khai, nhưng nó có thể hơi khó hiểu.

Trong các bước được liệt kê ở trên, chúng tôi đã chỉ ra cách hai người có thể giao tiếp an toàn mà không cần chia sẻ mã trước. Đầu tiên, mọi người cần thiết lập cặp khóa của riêng mình và chia sẻ khóa công khai với nhau. Hai người cần giữ bí mật khóa riêng tư để giữ an toàn cho thông tin liên lạc của họ.

Sau khi người gửi có khóa công khai của người nhận, họ có thể sử dụng khóa đó để mã hóa dữ liệu mà họ muốn bảo vệ. Khi nó được mã hóa bằng khóa công khai, nó chỉ có thể được giải mã bằng khóa riêng từ cùng một cặp khóa. Ngay cả cùng một khóa công khai cũng không thể được sử dụng để giải mã dữ liệu. Điều này là do các thuộc tính của chức năng cửa sập đã được đề cập.

Khi người nhận nhận được tin nhắn được mã hóa, họ sẽ sử dụng khóa cá nhân của mình để truy cập dữ liệu. Nếu người nhận muốn gửi lại thông tin liên lạc theo cách an toàn, họ có thể mã hóa tin nhắn của mình bằng khóa công khai. Tương tự như vậy, một khi mã hóa khóa công khai được sử dụng, cách duy nhất thông tin có thể được truy cập là thông qua khóa cá nhân.

Bằng cách này, các bên không xác định trước đây có thể gửi dữ liệu một cách an toàn bằng cách sử dụng mã hóa rsa. vietnix hy vọng rằng bạn đã hiểu rõ về cách hoạt động của mã hóa rsa và bạn có thể áp dụng thành công thuật toán này để bảo vệ dữ liệu của mình.

Kết luận

Hy vọng bài viết trên đã giúp bạn hiểu rõ hơn về bảng mã rsa là gì? Mọi thắc mắc hay ý kiến ​​đóng góp các bạn vui lòng để lại bình luận bên dưới bài viết này. vietnix xin chân thành cảm ơn!