Bài 5: Ứng dụng ngân hàng giữ tiền bạn an toàn thế nào? RSA, lũy thừa nhanh và hàm băm

Mỗi lần bạn chuyển khoản, quét mã VietQR hay đăng nhập ứng dụng ngân hàng, hàng loạt phép tính số học modulo diễn ra trong vài mili giây. Thứ bảo vệ tiền của bạn không phải là cánh cửa thép, mà là một sự thật toán học: nhân hai số nguyên tố thì dễ, nhưng phân tích ngược lại thì cực kỳ khó.

Bài thứ năm của chuyên mục "Thuật toán trong đời sống". Kiến thức số học trong chuyên đề HSG – lũy thừa nhanh, modulo, nghịch đảo modulo – chính là nền móng của mật mã hiện đại.

1. Bài toán: nói chuyện bí mật qua kênh công khai

Khi điện thoại gửi lệnh chuyển tiền đến ngân hàng, dữ liệu đi qua wifi quán cà phê, nhà mạng, hàng chục máy chủ trung gian. Ai cũng có thể "nghe lén". Làm sao hai bên thống nhất được mã khóa bí mật khi chưa từng gặp nhau?

Năm 1976, Whitfield Diffie và Martin Hellman công bố bài báo "New Directions in Cryptography", đề xuất cách trao đổi khóa dựa trên độ khó của bài toán logarit rời rạc. Một năm sau, năm 1977, ba nhà khoa học MIT là Ron Rivest, Adi Shamir và Leonard Adleman công bố hệ mã RSA – mã hóa khóa công khai dựa trên độ khó của việc phân tích số ra thừa số nguyên tố.

Chuyện thú vị: theo Bruce Schneier, cơ quan tình báo Anh GCHQ công bố vào năm 1997 rằng nhà toán học Clifford Cocks đã tìm ra một hệ mã "về cơ bản là RSA" từ năm 1973, nhưng công trình bị giữ bí mật suốt 24 năm.

2. RSA hoạt động thế nào?

1. Chọn hai số nguyên tố lớn p, q (trong thực tế mỗi số dài hàng trăm chữ số). Tính n = p × q và φ = (p − 1)(q − 1).
2. Chọn số e nguyên tố cùng nhau với φ. Cặp (n, e) là khóa công khai – ai cũng biết.
3. Tính d sao cho e × d ≡ 1 (mod φ) – đây là nghịch đảo modulo. d là khóa bí mật.
4. Mã hóa tin nhắn M: C = M^e mod n. Giải mã: M = C^d mod n.

Muốn tìm d, kẻ tấn công phải biết φ, tức là phải phân tích được n thành p × q. Với số đủ lớn, việc này gần như bất khả thi. Kỷ lục được công bố tháng 2/2020: nhóm nghiên cứu phân tích thành công số RSA-250 (250 chữ số) – tốn khoảng 2.700 năm tính toán của một lõi CPU. Các khóa RSA thực tế còn dài hơn nhiều.

Trái tim của RSA: lũy thừa nhanh

Tính M^e mod n với e có hàng trăm chữ số bằng cách nhân e lần là không thể. Ta dùng lũy thừa nhanh (bình phương và nhân): xét từng bit của số mũ, chỉ cần khoảng 2 × log₂(e) phép nhân. Chính bài báo gốc năm 1977 của RSA đã mô tả cách tính này.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
// Lũy thừa nhanh: a^b mod m trong O(log b)
ull power(ull a, ull b, ull m){
    ull r = 1; a %= m;
    while(b){
        if(b & 1) r = (__uint128_t)r * a % m;
        a = (__uint128_t)a * a % m;
        b >>= 1;
    }
    return r;
}
int main(){
    // RSA "đồ chơi" với số nhỏ (thực tế dùng số 2048 bit trở lên)
    ull p = 61, q = 53;
    ull n = p * q;              // 3233 - công khai
    ull phi = (p - 1) * (q - 1);// 3120 - bí mật
    ull e = 17;                 // khóa công khai
    ull d = 2753;               // khóa bí mật: e*d ≡ 1 (mod phi)
    ull msg = 65;               // tin nhắn (đã đổi thành số)
    ull c = power(msg, e, n);   // mã hóa bằng khóa công khai
    ull back = power(c, d, n);  // giải mã bằng khóa bí mật
    cout << "Ban ma: " << c << "\nGiai ma: " << back << "\n";
}

p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)     # n = 3233, phi = 3120
e = 17
d = pow(e, -1, phi)                    # nghịch đảo modulo -> 2753
msg = 65
c = pow(msg, e, n)                     # mã hóa: lũy thừa nhanh có sẵn trong Python
print("Ban ma:", c, "| Giai ma:", pow(c, d, n), "| d =", d)

Với p = 61, q = 53: n = 3233, e = 17, d = 2753. Tin nhắn 65 được mã hóa thành 2790, và giải mã ra lại đúng 65. Đây là ví dụ "đồ chơi" – hệ thống thật dùng số 2048 bit trở lên cùng nhiều lớp bảo vệ bổ sung.

3. Hàm băm: "dấu vân tay" của dữ liệu

Ngân hàng không lưu mật khẩu của bạn. Họ lưu giá trị băm (hash) của mật khẩu. Hàm băm như SHA-256 (chuẩn FIPS 180-4 của Viện Tiêu chuẩn và Công nghệ Mỹ – NIST) biến dữ liệu bất kỳ thành một chuỗi 256 bit, với tính chất: chỉ thay đổi một ký tự là kết quả khác hoàn toàn, và không thể suy ngược từ hash ra dữ liệu gốc. NIST viết rằng giá trị băm dùng để phát hiện dữ liệu có bị thay đổi hay không.

Với mật khẩu, hướng dẫn bảo mật của OWASP khuyên dùng các hàm băm cố tình chậm như Argon2id, scrypt, bcrypt hoặc PBKDF2 (ví dụ 600.000 vòng với SHA-256), kèm muối (salt) ngẫu nhiên riêng cho từng người – để kẻ gian không thể thử hàng tỷ mật khẩu mỗi giây.

Code Python: băm mật khẩu và kiểm tra

import hashlib, os

# Ứng dụng KHÔNG lưu mật khẩu, chỉ lưu "dấu vân tay" (hash) của mật khẩu + muối
def hash_password(password, salt=None):
    salt = salt or os.urandom(16)                      # muối ngẫu nhiên cho từng người
    h = hashlib.pbkdf2_hmac("sha256", password.encode(), salt, 600_000)
    return salt, h

salt, stored = hash_password("matkhau123")
# Khi đăng nhập: băm lại mật khẩu người dùng nhập và so sánh
print(hash_password("matkhau123", salt)[1] == stored)   # True
print(hash_password("matkhau124", salt)[1] == stored)   # False

# Thay đổi 1 ký tự -> hash khác hoàn toàn
print(hashlib.sha256(b"Chuyen 100000 dong").hexdigest()[:32])
print(hashlib.sha256(b"Chuyen 900000 dong").hexdigest()[:32])

4. Mã VietQR: thuật toán kiểm tra lỗi

VietQR được NAPAS và 14 ngân hàng ra mắt ngày 15/6/2021, tuân thủ tiêu chuẩn thanh toán QR của EMVCo. Bên trong mã QR là một chuỗi văn bản gồm các trường thông tin (mã ngân hàng, số tài khoản, số tiền…). Theo tài liệu của các thư viện tạo VietQR (dẫn đặc tả kỹ thuật của NAPAS), cuối chuỗi có trường số 63 chứa mã kiểm tra CRC-16 – một thuật toán tính "tổng kiểm tra" giúp phát hiện nếu nội dung bị sai lệch. Bản thân mã QR còn có mã sửa lỗi Reed–Solomon, nhờ đó vẫn quét được khi bị bẩn hoặc rách một phần.

5. HTTPS và tương lai "hậu lượng tử"

• Theo Google, tỉ lệ trang web tải qua HTTPS (có mã hóa) trên Chrome tăng từ khoảng 30–45% năm 2015 lên mức 95–99% từ khoảng năm 2020.
• Máy tính lượng tử trong tương lai có thể phá RSA bằng thuật toán Shor. Vì vậy ngày 13/8/2024, NIST đã phê duyệt ba chuẩn mật mã hậu lượng tử: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) và FIPS 205 (SLH-DSA). ML-KEM dựa trên bài toán "Module Learning with Errors" – một bài toán trên lưới (lattice) được cho là khó cả với máy tính lượng tử.

6. Bạn học được gì từ đây?

• Lũy thừa nhanh, modulo, nghịch đảo modulo, số nguyên tố – những chủ đề số học trong đề HSG – là nền tảng bảo vệ tài khoản ngân hàng của hàng triệu người.
• Độ an toàn của mật mã dựa trên độ phức tạp tính toán: bài toán dễ theo một chiều, khó theo chiều ngược lại.
• Đừng bao giờ tự "phát minh" hệ mã cho ứng dụng thật – hãy dùng thư viện chuẩn đã được kiểm chứng.

Bài tập luyện tập

• CSES – Exponentiation (lũy thừa nhanh)
• CSES – Exponentiation II (lũy thừa tầng, định lý Fermat nhỏ)

Thử thách: với p = 61, q = 53, e = 17, hãy tự mã hóa tin nhắn M = 100 bằng tay (hoặc bằng code) và kiểm tra lại kết quả giải mã. Chia sẻ đáp án trong phần bình luận nhé!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 6: Từ sửa lỗi chính tả đến giải mã DNA: khoảng cách chỉnh sửa và quy hoạch động

Đọc tiếp: sửa lỗi chính tả & DNA →

← Bài trước: thuật toán gợi ýXem tất cả 27 bài →

Nguồn tham khảo

• Rivest, Shamir, Adleman (1977) – A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
• Diffie & Hellman (1976) – New Directions in Cryptography
• Bruce Schneier – The Secret Story of Non-Secret Encryption
• Thông báo phân tích RSA-250 (2/2020)
• NIST – FIPS 180-4 Secure Hash Standard
• OWASP – Password Storage Cheat Sheet
• Báo Pháp luật – Ra mắt thương hiệu VietQR (2021)
• EMVCo – The What, Why and How of EMV QR Codes
• Thư viện liopay/vietqr – cấu trúc chuỗi VietQR và CRC
• Google – Báo cáo minh bạch: HTTPS trên Chrome
• NIST – Post-quantum cryptography FIPS approved (2024)