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\,}{\displaystyle p\,} và {\displaystyle q\,}{\displaystyle q\,} với {\displaystyle p\neq q}{\displaystyle p\neq q}, lựa chọn ngẫu nhiên và độc lập.
  2. Tính: {\displaystyle n=pq\,}{\displaystyle n=pq\,}.
  3. Tính: giá trị hàm số Euler {\displaystyle \phi (n)=(p-1)(q-1)\,}{\displaystyle \phi (n)=(p-1)(q-1)\,}.
  4. Chọn một số tự nhiên {\displaystyle e}{\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)\,}{\displaystyle \phi (n)\,}.
  5. Tính: {\displaystyle d}d sao cho {\displaystyle de\equiv 1{\pmod {\phi (n)}}}{\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\,}x\, sao cho {\displaystyle d={\frac {x(p-1)(q-1)+1}{e}}}{\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)}\,}{\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)\,}{\displaystyle \lambda =LCM(p-1,q-1)\,} thay cho {\displaystyle \phi =(p-1)(q-1)\,}{\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 AnhChinese 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}}{\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}}{\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}}}{\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}}}{\displaystyle m^{ed}\equiv m{\pmod {p}}}

và{\displaystyle m^{ed}\equiv m{\pmod {q}}}{\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}}}{\displaystyle m^{ed}\equiv m{\pmod {pq}}}.

hay:{\displaystyle c^{d}\equiv m{\pmod {n}}}{\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 Kp(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):

eZr=Z%eq=z/ey=y0-qxy1y0y1
735201Khởi tạo
27250-50150
1213151-50151
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 KSA = (377,269) và khóa công khai KPA = (377,5), B có khóa bí mật KSB = (437,317) và khóa công khai KPB = (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:

KSA = (377,269) = > nA = 377, dA = 269

KPA = (377,5) => nA = 377, eA = 5

Bên B:

KSB = (437,317) => nB = 437, dB = 317

KPB = (437,5) => nB = 437, eB = 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=meB mod nB = 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 = cdB mod nB = 364317 mod 437 = 10

i1248163264128256
364i mod 43736485233101150213358123271

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 = mdA mod nA = 1232753 mod 3233 = 2746

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

V = SeA mod nA = 274617 mod 3233 = 123

Published by Nhat Truong

Hi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: