Mã Hóa RSA – Phần 2: Công Thức Và ứng Dụng | Minh-cly

Trang chủ » Công Thức Rsa » Mã Hóa RSA – Phần 2: Công Thức Và ứng Dụng | Minh-cly

Có thể bạn quan tâm

Trong phần 1, chúng ta đã biết về lý thuyết nhóm và định lý nhỏ Fermat. Phần 2 này sẽ đề cập tới chi tiết về toán và cách sử dụng của mã hóa RSA.

  • Phần 1: Lý thuyết nhóm
  • Phần 3: Chữ ký số và Chứng chỉ số
  • Phần 4: Bẻ khóa

Công thức

Trong phần 1, ta đã chứng minh định lý nhỏ Fermat: với p là số nguyên tố và với mọi a < p, ta có:

a^{p-1} = 1 \pmod p

Với q là một số nguyên tố khác p, và a nguyên tố cùng nhau với cả p và q, ta có:

\left[a^{p-1}\right]^{q-1} = 1 \pmod p

Tương tự với q, ta có:

\left[a^{q-1}\right]^{p-1} = 1 \pmod q

Như vậy, a^{(p-1)(q-1)} - 1 là bội của cả p và q. Do p và q không có ước số chung (lớn hơn 1), nên a^{(p-1)(q-1)} - 1 phải là bội của tích pq:

a^{(p-1)(q-1)} = 1 \pmod{pq}

Lũy thừa 2 vế s lần (s nguyên dương) và nhân 2 vế cho a, ta có công thức cơ bản của mã hóa RSA:

a^{s(p-1)(q-1) + 1} = a \pmod{pq}

Công việc còn lại là phân tích s(p-1)(q-1) + 1 thành tích của 2 khóa. Chọn c là một số nguyên tố cùng nhau với (p – 1)(q – 1), từ lý thuyết nhóm của phần 1, c thuộc G_{(p-1)(q-1)}, do đó, tồn tại một thành phần nghịch đảo d của c, sao cho:

cd = 1 \pmod{(p-1)(q-1)}

Hay nói cách khác:

cd = s(p-1)(q-1) + 1

Kết hợp tất cả lại với nhau, ta có:

a^{cd} = a \pmod{pq}

Gọi N = pq. Nếu chọn c làm khóa công khai và d làm khóa bí mật, và a là văn bản cần được mã hóa, thì cách tạo ra mật văn b là:

b = a^c \pmod{N}

Và cách giải mã từ b sang a là:

a = b^d \pmod{N}

Hai công thức trên đã tóm tắt cơ bản cách hoạt động của mã hóa RSA. Chương sau sẽ nói chi tiết hơn về cách sử dụng mã hóa RSA này.

Cách sử dụng

Để sử dụng mã hóa RSA, một người cần phải sinh ra một bộ khóa công khai c, khóa bí mật d và tích N = pq. Từ chương trước, các bước sinh ra bộ khóa được tóm tắt như sau:

  1. Chọn hai số nguyên tố lớn p và q (cỡ hơn 1000 bit).
  2. Tích pq chính là N.
  3. Chọn một số nguyên dương c nguyên tố cùng nhau với (p – 1)(q – 1). c chính là khóa công khai.
  4. Tính thành phần nghịch đảo d của c. d chính là khóa bí mật.
  5. Công khai 2 số (c, N) và giữ bí mật d.

Tùy vào ứng dụng mà tổ hợp 2 khóa này sẽ được sử dụng. Chúng ta sẽ nói về các ứng dụng sau: chứng thực (authentication) và truyền tải an toàn (secure transmission). Chữ ký điện tử (digital signature) và chứng chỉ điện tử (digital certificate) sẽ được đề cập trong phần sau.

Chứng thực

Chứng thực (authentication) là quá trình một server xác định xem bạn là ai. Phương pháp chứng thực đơn giản nhất mà bạn sử dụng hằng ngày được gọi là “đăng nhập” (log in). Hằng ngày, bạn nhập một mật khẩu tĩnh (không thay đổi trong vài tháng, hoặc cả đời), và server sẽ dò xem mật khẩu của bạn có khớp với mật khẩu được lưu hay không. Tuy nhiên, một số người đặt mật khẩu rất dễ đoán, và mật khẩu có khả năng bị đánh cắp rất cao bằng những thủ thuật đơn giản. Do đó, trong một số các ứng dụng, một “mật khẩu điện tử” sẽ giúp việc chứng thực trở nên an toàn hơn. Phương thức chứng thực này thường được sử dụng trong SSH để đăng nhập vào máy khác (thường là server) mà không cần phải nhập mật khẩu.

Ghi chú: Server không lưu trực tiếp mật khẩu của bạn, mà lưu bản hash của nó, để nếu khi hash bị lộ thì mật khẩu của bạn vẫn tương đối an toàn.

Thay vì một mật khẩu bình thường, người đăng nhập sẽ sinh ra một ra một bộ khóa công khai và bí mật. Sau đó, người đăng nhập sẽ đăng ký khóa công khai lên server (khóa bí mật không bao giờ bị tiết lộ ra ngoài). Mỗi khi cần đăng nhập vào server, các bước sau đây sẽ xảy ra:

  1. Server sinh ra một số ngẫu nhiên a và gửi cho người đăng nhập.
  2. Người đăng nhập sử dụng khóa bí mật để tạo mật văn b gửi lại cho server.
  3. Server sử dụng khóa công khai (được đăng ký trước đó) để giải mã. Nếu kết quả sau khi giải mã lại bằng a, đó là bằng chứng cho việc người đăng nhập sở hữu đúng khóa bí mật.

Nếu một kẻ mạo nhận muốn đăng nhập vào server, sau khi được nhận a từ server, hắn không có đúng khóa bí mật và gửi lại mật văn giả b’, thì khi server giải mã ra lại sẽ có a’ khác a và do đó hắn không thể đăng nhập. Mặt khác, hắn không thể đoán hay tái sử dụng mật văn b, bởi vì a là ngẫu nhiên và sẽ thay đổi cho mỗi lần đăng nhập khác nhau.

Một điều bất tiện khi sử dụng “mật khẩu điện tử” này là khóa bí mật chỉ hợp lệ trên một máy duy nhất (bạn có thể copy sang máy khác, nhưng điều đó làm khóa bí mật của bạn gặp nhiều rủi ro bị tiết lộ hơn). Tuy nhiên, bạn hoàn toàn có thể tạo một bộ khóa riêng cho mỗi máy và đăng ký nhiều khóa công khai cho một tài khoản, như vậy bạn có thể đăng nhập ở bất kỳ máy nào.

Tuy nhiên, nếu kẻ tấn công nghe lén những gói tin của bạn, mặc dù hắn không biết được mật khẩu, hắn vẫn có thể biết được những thông tin bạn truyền sau khi bạn đăng nhập, ví dụ lịch sử giao dịch ngân hàng của bạn. Do đó, bạn cần phải có một cách để bảo vệ đường truyền của bạn.

Truyền tải an toàn

Truyền tải an toàn (secure transmission) là phương pháp để truyền đi những thông tin cần bảo mật cao như thông tin ngân hàng, lịch sử tìm kiếm. Hiện nay, chúng ta đều sử dụng nó hằng ngày dưới giao thức HTTPS, kể cả Facebook và trang WordPress này mà các bạn đang theo dõi. Truyền tải an toàn ngăn chặn kiểu tấn công nghe lén bằng cách mã hóa thông tin được truyền đi.

Thông thường, thông tin được mã hóa sử dụng một phương pháp mã hóa khóa đối xứng (symmetric-key encryption). Mã hóa khóa đối xứng tốn ít tài nguyên hơn mã hóa RSA, do đó thích hợp để mã hóa lương thông tin lớn. Tuy nhiên, vấn đề với mã hóa khóa đối xứng là việc mã hóa và giải mã sử dụng chung một khóa (gọi là khóa phiên – session key), và do đó, khóa này cần phải được truyền đi một cách bảo mật. Nếu khóa đó bị lộ, việc mã hóa là vô nghĩa. Trong quá khứ, khóa này có thể được truyền đi trực tiếp (bưu điện) hay qua điện thoại. Hiện nay, khóa này được truyền đi sử dụng mã hóa RSA.

Để thiết lập một đường truyền tải an toàn, ví dụ giữa Alice và Bob, các bước sau đâu được thực hiện:

  1. Alice tạo ra một bộ khóa công khai và khóa bí mật theo RSA.
  2. Alice gửi khóa công khai cho Bob.
  3. Bob tạo ra một khóa phiên a ngẫu nhiên.
  4. Bob mã hóa a sẽ dụng khóa công khai để cho ra mật văn b và gửi cho Alice.
  5. Alice nhận mật văn b, dùng khóa bí mật để giải mã ra a.
  6. Alice và Bob cùng sử dụng a làm khóa phiên cho một thuật toán mã hóa khóa đối xứng khác.

Nếu kẻ tấn công nghe lén được cuộc hội thoại, tất cả thứ hắn nghe được chỉ là:

  • Khóa công khai từ Alice
  • Mật văn b
  • Tất cả thông tin sau đó bị mã hóa bởi a (mà chỉ có Alice và Bob biết).

Kẻ tấn công không thể tái tạo a từ mật văn b và khóa công khai (nếu hắn có thể tức hắn biết cách bẻ mã RSA), do đó hắn không thể giải mã những gói tin sau đó. Đường truyền giữa Alice và Bob đã được bảo mật.

Tuy nhiên, kẻ tấn công (ví dụ tên là Charlie) vẫn có thể đánh chặn được những gói tin của Alice và Bob (man-in-the-middle attack). Charlie có thể giả mạo là Bob trước mặt Alice, và giả làm Alice trước mặt Bob (OK, hắn lưỡng tính). Alice và Bob không truyền trực tiếp với nhau, nhưng thông qua Charlie. Giữa Alice và Charlie, và giữa Charlie và Bob vẫn là những “đường truyền an toàn”, nhưng truyền tải an toàn chỉ bảo vệ thông tin khỏi những kẻ nghe lén bên ngoài, chứ không bảo vệ khỏi những kẻ mạo danh như Charlie. Để phát hiện những kẻ mạo danh như vậy, cơ chế bảo mật tiếp theo: chứng chỉ điện tử, sẽ được đề cập trong phần sau. Cảm ơn các bạn đã theo dõi.

Chia sẻ:

  • X
  • Facebook
  • Email
  • In
  • Thêm
  • Reddit
Thích Đang tải...

Từ khóa » Công Thức Rsa