Hoàn thành mã hóa RSA

Là người mới sử dụng mật mã, tôi đang cố gắng hiểu cách hoàn thành mã hóa RSA bằng tay. Tôi chỉ có thể làm theo công thức cho đến nay trước khi trở nên rất bối rối.

Tôi muốn mã hóa giá trị "123"

Đầu tiên, tôi chọn 2 số nguyên tố. Tôi chọn: $$p = 101\ q = 103$$

Tiếp theo, tôi tính toán: $$n = p\cdot q = 10403$$.

Sau đó, tôi tính toán: $$\varphi(n) = (p-1)\cdot(q-1) = 10200$$

Bây giờ, tôi muốn chọn một số mũ công khai, và tôi chọn 3 cho việc này.

Tôi tin rằng công thức để sử dụng là: $$d = e^{â1}\bmod\varphi(n)$$

Tôi không hiểu cách cắm công thức này vào, cũng như không biết cách mã hóa "123" bằng công thức này. Ngoài ra, tôi cũng không biết làm cách nào để tìm số mũ giải mã.

Bất kì sự trợ giúp nào đều được đánh giá cao!

Về cơ bản, Fgrieu đã đưa ra câu trả lời trong nhận xét, tôi sẽ cố gắng giải thích một chút ở dạng câu trả lời.

Bạn có thể sử dụng thuật toán euclide mở rộng để tìm d từ e, nhưng lưu ý rằng e bạn đã chọn sẽ không hoạt động. Vì e không nguyên tố cùng nhau $\varphi(n)$ Bạn cần chọn một cái khác. Để đạt hiệu quả, chúng tôi thường muốn chọn một e nhỏ với một số bit được đặt, thường có dạng $2^k+1$ vì 3 không hoạt động, bạn có thể thử những cái khác. https://en.wikipedia.org/wiki/Extends_Euclidean_algorithm Đây là một máy tính trực tuyến: https://planetcalc.com/3298/

Nó sẽ không chỉ cung cấp cho bạn gcd (cần phải là 1) mà còn cung cấp cho bạn a,b sao cho: $a*e + b*\varphi(n) = 1$ về cơ bản có nghĩa là $a*e = 1 mod \varphi(n)$ đó là những gì chúng tôi muốn.

Sau đó, bạn mã hóa bằng cách tính toán $c = m^e\không gian mod(n)$ và giải mã bằng cách sử dụng $m = c^d\không gian mod(n)$ Cả hai được thực hiện thông qua https://en.wikipedia.org/wiki/Modular_exponentiation