Tìm hiểu RSA

Trong mật mã học, RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn.

Tạo khóa

Giả sử An và Bình cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, An đầu tiên cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau:

1. Chọn 2 số nguyên tố lớn {\displaystyle p\,} và {\displaystyle q\,} với {\displaystyle p\neq q}, lựa chọn ngẫu nhiên và độc lập.
2. Tính: {\displaystyle n=pq\,}.
3. Tính: giá trị hàm số Euler {\displaystyle \phi (n)=(p-1)(q-1)\,}.
4. Chọn một số tự nhiên {\displaystyle e} sao cho {\displaystyle 1<e<\phi (n)\,}<img src=”https://wikimedia.org/api/rest_v1/media/math/render/svg/8c597e0ad6f269188b76ca858f2039192edd22c9&#8243; alt=”{\displaystyle 1<e và là số nguyên tố cùng nhau với {\displaystyle \phi (n)\,}.
5. Tính: {\displaystyle d} sao cho {\displaystyle de\equiv 1{\pmod {\phi (n)}}}. (xem Đồng dư để hiểu rõ hơn)

Một số lưu ý:

• Các số nguyên tố thường được chọn bằng phương pháp thử xác suất.
• Các bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng (xem thêm: số học môđun).
• Bước 5 có thể viết cách khác: Tìm số tự nhiên {\displaystyle x\,} sao cho {\displaystyle d={\frac {x(p-1)(q-1)+1}{e}}} cũng là số tự nhiên. Khi đó sử dụng giá trị {\displaystyle d\mod {(p-1)(q-1)}\,}.
• Từ bước 3, PKCS#1 v2.1 sử dụng {\displaystyle \lambda =LCM(p-1,q-1)\,} thay cho {\displaystyle \phi =(p-1)(q-1)\,}).

Khóa công khai bao gồm:

• n, môđun, và
• e, số mũ công khai (cũng gọi là số mũ mã hóa).

Khóa bí mật bao gồm:

• n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và
• d, số mũ bí mật (cũng gọi là số mũ giải mã).

Một dạng khác của khóa bí mật bao gồm:

• p và q, hai số nguyên tố chọn ban đầu,
• d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1),
• (1/q) mod p (thường được gọi là iqmp)

Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc (tiếng Anh: Chinese Remainder Theorem – CRT). Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật.

An gửi khóa công khai cho Bình, và giữ bí mật khóa cá nhân của mình. Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa.

Mã hóa

Giả sử Bình muốn gửi đoạn thông tin M cho An. Đầu tiên Bình chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Quá trình này được mô tả ở phần #Chuyển đổi văn bản rõ.

Lúc này Bình có m và biết n cũng như e do An gửi. Bình sẽ tính c là bản mã hóa của m theo công thức:{\displaystyle c=m^{e}\mod {n}}

Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật toán bình phương và nhân) Cuối cùng Bình gửi c cho An.

Giải mã

An nhận c từ Bình và biết khóa bí mật d. An có thể tìm được m từ c theo công thức sau:{\displaystyle m=c^{d}\mod {n}}

Biết m, An tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì ta có{\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}.

Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ) nên:{\displaystyle m^{ed}\equiv m{\pmod {p}}}

và{\displaystyle m^{ed}\equiv m{\pmod {q}}}

Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có:{\displaystyle m^{ed}\equiv m{\pmod {pq}}}.

hay:{\displaystyle c^{d}\equiv m{\pmod {n}}}.

Giải bài tập

Bài 1: Giả sử A muốn sử dụng mật mã khóa công khai RSA và để sinh cặp khóa cho mình, A đã sinh được hai số nguyên tố p=23,q=17 và chọn số mũ công khai e=7. Bạn hay xác định cặp khóa của A.

Giải:

n = p.q = 391

φ(n) = (p-1)(q-1) = 352

Khóa công khai K_p(391,7)

Khóa bí mật d sao cho d×e≡1 mod φ(n) <=> 7^-1 mod 352

Áp dụng thuật toán ơ cờ lít mở rộng (Đang viết):

e	Z	r=Z%e	q=z/e	y=y0-qxy1	y0	y1
7	352	–	–	–	0	1	Khởi tạo
2	7	2	50	-50	1	50
1	2	1	3	151	-50	151
		0

Bài 2: Cho biết A và B sử dụng mật mã khóa công khai RSA trong đảm bảo an toàn thông tin, A có khóa bí mật K_SA = (377,269) và khóa công khai K_PA = (377,5), B có khóa bí mật K_SB = (437,317) và khóa công khai K_PB = (437,5). Giả sử A muốn gửi thông điệp bí mật m=10 cho B. Bạn hãy trình bày quá trình mã hóa và giải mã mà A và B cần thực hiện để gửi/nhận thông điệp nói trên.
Giải:

Bên A:

K_SA = (377,269) = > n_A = 377, d_A = 269

K_PA = (377,5) => n_A = 377, e_A = 5

Bên B:

K_SB = (437,317) => n_B = 437, d_B = 317

K_PB = (437,5) => n_B = 437, e_B = 5

A muốn gửi thông điệp bí mật m=10 cho B thì:

Áp dụng khóa công khai của B để mã hóa:

Bản mã: c=m^eB mod n_B = 10^5 mod 437 = 364

B sử dụng khóa bí mật của mình để giải mã:

Bản rõ: x = c^dB mod n_B = 364³¹⁷ mod 437 = 10

i	1	2	4	8	16	32	64	128	256
364i mod 437	364	85	233	101	150	213	358	123	271

x = (364^256 mod 437)* (364^32  mod 437) * (364^8  mod 437) * (364^8  mod 437) * (364^8  mod 437) * (364^4  mod 437) * (364  mod 437) = (271*213*101*101*101*233*364) mod 437 = 6 * 293 mod 437 = 10

(Lưu ý: x chính là m, tuy nhiên do có thể bị nhiễu trong quá trình truyền tin nên gán là x :))

Bài 3: Cho biết A và B sử dụng mật mã khóa công khai RSA trong đảm bảo an toàn thông tin, A có khóa bí mật KSA = (3233,2753) và khóa công khai KPA = (3233,17), B có khóa bí mật KSB = (377,269) và khóa công khai KPB = (377,5). Giả sử A muốn gửi thông điệp m=123 cho B trong đó có ký số để xác thực thông điệp. Bạn hãy trình bày quá trình ký và kiểm tra chữ ký mà A và B cần thực hiện để gửi/nhận thông điệp nói trên.

Giải:

A sẽ sử dụng khóa bí mật của mình để ký:

S = m^dA mod n_A = 123²⁷⁵³ mod 3233 = 2746

B sẽ sử dụng khóa công khai của A để xác thực:

V = S^eA mod n_A = 2746¹⁷ mod 3233 = 123