crypto

Mã hóa ứng dụng

1. Hàm băm (Hash function)

Định nghĩa

Hàm hash $h$ biến doc thành signature $\in \mathbb{Z}_{2^l}$ ($l$ bit).

  1. Cho $y = h(m) \rightarrow$ tìm $m$ khó. (tính 1 chiều)
  2. Cho $m$, tìm $m’$ sao cho $h(m) = h(m’)$ khó.
  3. Tìm $m, m’$ sao cho $h(m) = h(m’)$ khó.

Trường hợp 2 và 3: hạn chế đụng độ

Cài đặt

Cách 1: Dùng hệ mã $E$ (AES, 3DES, RSA, ..)

Cách 2: Kết hợp băm VD: $h_1, h_2$ là 2 hàm băm $\rightarrow h_1 \oplus h_2, h_2 \oplus h_1$

Cách 3: Xây dựng thuật giải

VD: MASH: ${0, 1}^{*}\rightarrow {0, 1}^{n/2}$

  1. Chọn $p, q$ nguyên tố, $M = pq$ có $m$ bit.
  2. Chọn $n$ là bội của 16 sao cho $n < m$.
  3. $H_0 = 0, A = 1111 0000 … 0000$ ($n$ bit)
  4. $X$ là thông điệp.
    • Chia $X$ thành $t$ khối $\frac{n}{2}$ bit.
    • Thêm $\frac{n}{2}$ bit là giá trị b (giá trị của chiều dài $x$).
  5. Lặp từ $i = 1 \rightarrow t$:
    • Chia khối $X_i$ thành các khối 4 bit.
    • Chèn 4 bit 1111 vào trước, riêng khối cuối chèn $1010$.

Kết quả là $Y = y_1..y_t$

  1. Lặp từ $i = 1 \rightarrow t$:
    • $F_i = (H_{i - 1} \oplus y_i \lor A)^{257} \pmod M$
    • Lấy $G_i$ là $n$ bit phải $F_i$.
    • Tính $H_i = (a_i \oplus H_{i - 1})$
  2. $H_t$ là kết quả.

Ứng dụng:

  1. Bảo mật passwords
    • Bảo vệ đường truyền: RSA - mã hóa username và password
    • Bảo vệ dữ liệu trong database: hash password
  2. Mã chứng thực văn bản (MAC - Message Authentication Code)
    • Bảo vệ tính toàn vẹn của văn bản.
    • VD: Cho document $M, c = h(M || k)$ (ghép $k$ là khóa bí mật của người chủ văn bản vào $M$)
  3. Chữ ký điện tử (Digital Signature) Văn bản gốc $M$, $C$ có $e, d$ (RSA), $A$ có khóa $k$ bí mật.

Phân tích hàm băm mật mã

Cho $P$, tìm đụng độ $P’$:

  1. Tạo bảng $t = 2^{\frac{n}{2}}$ biến thể của $P: P_1, P_2, ..$
  2. Lặp: $\forall i \in t:$ chèn $(P_i, h(P_i))$ vào $t$.
  3. Tạo $P’$, tra trong $t$.

Kháng: cho $n \geq 80k, (k > 1)$

2. Chữ ký điện tử

Nguyên lí chung: dựa trên hệ mã public key cryptosystem $f$.

Tuy nhiên $f$ ký rất chậm trên $m$. Thay vì vậy người ta ký trên hash $h(m)$, với $h$ là hàm băm mật mã.

Naive version, using RSA:

Tạo key:

Pha ký:

Pha kiểm chứng:

Cài đặt.

DSA (Digital Signature Algorithm) - DSS (Digital Signature Standard)

Quan trọng: Ký cần nhanh, verify không cần nhanh. Giải mã nhanh có cách (CRT).

  1. Các tham số:
    • p là số nguyên tố (khoảng 512 bit).
    • q là số nguyên tố (khoảng 160 bit).
    • $g \in \mathbb{Z}_N$ (bậc $g$ là bội của $q$)
    • $h: {0, 1}^{*} \rightarrow {0, 1}^{160}$
    • $x : 0 < x < q$ (khóa mật)
    • $y \equiv g^x \pmod p$ (Diffie-Hellman - khóa công khai)
  2. Ký văn bản $m$:
    • Chọn ngẫu nhiên $k \in \mathbb{Z}_N$
    • $r \equiv (g^k \pmod p) \pmod q, s \equiv k^{-1}(h(m) + xr) \pmod q$ (Ký bằng khóa $x$)
    • Kết quả là $(r, s)$.
  3. Xác minh chữ ký:
    • $t \equiv s^{-1} \pmod p$
    • $r \equiv (g^{h(m)t}y^{rt} \pmod p) \pmod q$ (Kiểm bằng khóa $y$)

3. Zero-knowledge - tri thức trị không

$A$ sử dụng khóa công khai $\pmod n$, $n = pq, p, q$ là số nguyên tố, $p, q \equiv 3 \pmod 4$.

$A$ thuyết phục người $B$ về khóa công khai là của mình:

  1. $A$ làm:
    • Chọn một $s$ là số chính phương $\pmod n$, công bố $(n, s)$
    • Tính $t^2 \equiv s \pmod n$ và giữ bí mật $t$.
  2. $A$ làm:
    • Chọn ngẫu nhiên $r < n$
    • $z_1 \equiv r^2 \pmod n, z_2 \equiv sz_1^{-1} \pmod n$
    • Gửi $(z_1, z_2)$ cho $B$.
  3. $B$ làm:
    • Kiểm $s \equiv z_1z_2 \pmod n$
    • Chọn 1 bit $c \in {0, 1}$
    • Gửi $c$ cho $A$.
  4. $A$ làm:
    • $c = 0$ thì gửi $r$.
    • $c = 1$ thì gửi $t^{r - 1}$.
  5. $B$ làm:
    • $c = 0$ thì kiểm $r^2 \equiv z_1 \pmod n$.
    • $c = 1$ thì kiểm $(t^{r - 1})^2 \equiv z_2 \pmod n$.

Cách trên là Interactive Proving.

4. Hệ bảo mật thông tin

Bảo mật CSDL

Không giống CSDL quan hệ thường học, CSDL có thể là file, record, row, col, ..

Xét CSDL $D = {f_1, f_2, .., f_n}$ - plain. Ta muốn mã hóa $D$ thành $C$

Pha 1: Mã hóa CSDL

Sử dụng CRT để mã hóa CSDL.

  1. Sinh $n$ số nguyên tố $p_i$ khác nhau thỏa $p_i > f_i \forall i \in [1, n]$
  2. Giải hệ
    • $X \equiv f_1 \pmod{p_1}$
    • …
    • $X \equiv f_n \pmod{p_n}$
  3. $C = X$ là mã hóa của $D$, $p_i$ là khóa để đọc $f_i$, gửi khóa $p_i$ này cho chủ của $f_i$

Pha 2: $u_i$ đọc $f_i$

  1. $f_i \equiv C \pmod{p_i}$

5. Chia sẻ bí mật

a. Đa thức nội suy Lagrange.

Định nghĩa

Đa thức $P_n(x)$ bậc $n$ được sinh bởi $n$ cặp $(x_i, y_i)$. Khi đó

$\displaystyle P_n(x) = \sum_{j = 1}^{n} y_j L_j(x)$

Với $\displaystyle L_j(x) = \prod_{1 \leq m \leq n, m \neq j} \frac{x - x_m}{x_j - x_m}$

Ví dụ:

b. Ứng dụng: bài toán ngưỡng

Ví dụ: với ngưỡng $n = 3$ và $N = 5$ người, hàm $P_3(x) = ax^2 + bx + c$. Khi đó $c$ là bí mật cần phải có 3 người cùng mở khóa mới có thể giải mã.

Ở đây ta chọn $a = 5, b = 6, c = 4$, các phép toán thực hiện trong $\mathbb{Z}_7$. Hàm $P(x) = 5x^2 + 6x + 4$. Nên nhớ bước này hoàn toàn do người chọn, $a, b$ được giữ bí mật và $c$ là bí mật được chia sẻ. Ta cũng quy định mỗi người có cặp $(i, P(i))$ là khóa. Vậy 5 người lần lượt có các khóa $u_1 = (1, 1), u_2 = (2, 1), u_3 = (3, 4), u_4 = (4, 3), u_5 = (5, 5)$.

Khi đó, nếu cần biết $c$ thì cần 3 người dùng khóa của mình để mở. Khi đó ta tính $P(0)$ với các $x_1, x_2, x_3, y_1, y_2, y_3$ từ khóa của người dùng.

Ví dụ:

This site is open source. Improve this page.