RSA (cryptosystem)
===
- RSA là mã hóa được đặt theo tên của 3 nhà toán học phát minh ra nó.
- Khác với AS(mã hóa đối xứng) chỉ có mỗi private key và phương pháp truyền tải 2 chiều, thì RSA(mã hóa bất đối xứng) có cả public key và private key và chỉ mang tính truyền thông tin 1 chiều.

## Mục lục

[TOC]

## Phát biểu bài toán

Bob cần liên lạc, truyền tải thông tin cho Alice, là người đang ở sở chỉ huy. Vì đang là thời kì chiến tranh nên Carl ở phe đối địch sẽ luôn theo dõi và biết được thông tin liên lạc Bob gửi cho Alice. Alice và Bob cần làm gì để Bob có thể truyền tải thông tin cho Alice ở sở chỉ huy mà Carl dù xem được hết mọi thông tin liên lạc vẫn không giải mã được ?

Các khái niệm
---

$M$ là thông tin Bob muốn gửi cho Alice đã được hash.
$C$ là số Bob mã hóa $M$ dựa vào public key mà Alice gửi.
$M'$ là số sau khi mã hóa mà Alice nhận được số $C$ của Bob.
**Public key** là thông tin mà ai cũng nhận được và dùng nó để mã hóa.
**Private key** là thông tin mà chỉ có Alice biết và sử dụng để giải mã thông tin do Bob gửi.
> Hash là phương pháp chuyển đổi chữ sang số theo nguyên tắc biểu diễn số học. Hash được sử dụng khá nhiều trong lập trình thi đấu.

Hoạt động
---
Alice chuẩn bị:
- $p, q$ là 2 số nguyên tố.
- $n = p*q$.
- $\phi(n) = (p - 1)*(q - 1)$ là số lượng số nguyên tố cùng nhau với $n$ và bé hơn $n$.
> những số không nguyên tố cùng nhau với $n$ là bội của $p$ hoặc $q$.
> Bội của $p$ lần lượt là $p, 2p, 3p, 4p, ..., n$.
> Bội của $q$ lần lượt là $q, 2q, 3q, 4q, ..., n$.
- $e$ thỏa mãn $GCD(e , \phi(n)) = 1$.
- $d$ thỏa mãn $e * d \equiv 1 \ (mod \ \phi(n))$ $\Leftrightarrow d \equiv e^{-1} \ (mod \ \phi(n))$.

Alice gửi cho Bob 2 số $n, e$ và giữ kín $d$.

:::spoiler
**Private key là $d$.
Public key là $n, e$.**
Những thông tin Alice có: $n, e, d, \phi(n)$.
Những thông tin Bob có: $n, e, M$.
Những thông tin Carl có: $n, e$.
:::

Bob mã hóa thông tin $M$ như sau:

- Tính $C = M^e (mod \ n)$.

Bob gửi cho Alice số $C$

:::spoiler
Những thông tin Alice có: $n, e, d, \phi(n), C$.
Những thông tin Bob có: $n, e, M, C$.
Những thông tin Carl có: $n, e, C$.
:::

Alice giải mã thông tin $C$ như sau:

- Tính $M' = C^d \ (mod \ n)$.

Alice nhận được $M'$ là thông tin mà Bob muốn gửi.

Tính đúng đắn
---
Để chứng minh tính đúng đắn của RSA ta cần chứng minh $M = M'$.

Ta có:
$\ \ \ \ \ \ M' = C^d \ (mod \ n)$
$\Leftrightarrow M' = M^{e^d} \ (mod \ n)$
$\Leftrightarrow M' = M^{ed} \ (mod \ n) \ (1)$

Ta có:
$\ \ \ \ \ ed \equiv 1 \ (mod \ \phi(n))$
$\Leftrightarrow ed = k \phi(n) + 1 \ (k \in \mathbb{Z})$

Quay về $(1)$. Ta được:
$\ \ \ \ \ \ M' = M^{ed} \ (mod \ n)$
$\Leftrightarrow M' = M^{k \phi(n) + 1} \ (mod \ n)$
$\Leftrightarrow M' = M * M^{k \phi(n)} \ (mod \ n)$
$\Leftrightarrow M' = M * M^{k (p - 1)(q - 1)} \ (mod \ n)$ vì $\phi(n) = (p - 1)*(q - 1) \ (2)$

> Định lý fermat nhỏ: $m^{p - 1} \equiv 1 \ (mod \ p)$ với p là số nguyên tố.
$\\ \ \ \ \ \ M^{k (p - 1)(q - 1)} \equiv \ 1^{k(q - 1)} \ \equiv 1 \ (mod \ p)$
$\\ \ \ \ \ \ M^{k (p - 1)(q - 1)} \equiv 1 \ (mod \ q)$

Áp dụng **định lý fermat nhỏ** và **định lý số dư Trung Hoa** vào $(2)$. Ta được:

$\ \ \ \ \ \ M^{k (p - 1)(q - 1)} \equiv 1 \ (mod \ n)$
$\Rightarrow M' = M*M^{k (p - 1)(q - 1)} \equiv M \ (mod \ n)$ $(Q.E.D)$

Vậy là thông tin đã không có sự thay đổi nào.

## Tính an toàn
Để chứng minh tính an toàn của RSA ta cần chứng minh không tồn tại bất kì cách nào tìm $d, p, q$ trong 1 khoảng thời gian đủ ngắn.
Carl biết được: $C = M^e \ (mod \ n)$
Để giải mã được $C$ Carl cần tìm được private key là $d$
Để để tìm ra $d$, Carl cần biết được 2 số nguyên tố $p, q$
- Cách duy nhất là Carl phải phân tích n thành 2 thừa số nguyên tố $p, q$. Với $n$ nhỏ thì thực hiện khá dễ dàng nhưng nếu $n$ đủ lớn thì việc phân tích sẽ mất rất nhiều thời gian.
> Để an toàn tuyệt đối $n$ cần thể hiện được ở bit 2048.

###### tags: `RSA` `Crypto` `ATTT` `CTF`