Bài tập lớn: Xây dựng chương trình mã hóa và giải mã Elgamal chi tiết

Tài liệu bài tập lớn xây dựng chương trình mã hóa và giải mã Elgamal. Trình bày chi tiết thuật toán, cơ sở lý thuyết và code demo ứng dụng.

• Tác giả: Vũ Tuấn Dũng
• Người hướng dẫn: Ths. Trần Phương Nhung
• Trường học: Trường Đại học Công nghiệp Hà Nội
• Chuyên ngành: An toàn và Bảo mật Thông tin
• Đề tài: Xây dựng chương trình mã hóa và giải mã Elgammal
• Loại tài liệu: Bài tập lớn
• Năm xuất bản: 2024
• Địa điểm: Hà Nội

Mục lục chi tiết

• Danh mục các ký hiệu, các chữ viết tắt
• Danh mục các bảng
• Danh mục các hình vẽ, đồ thị
• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: CƠ SỞ TOÁN HỌC
• 1.1. Số học trên modulo
• 1.2. Một số thuật toán trên Zn
• 2. CHƯƠNG 2: NỘI DUNG THUẬT TOÁN
• 2.1. Giới thiệu tổng quan
• 2.2. Nội dung thuật toán
• 2.3. Phương pháp tấn công
• 2.4. Đánh giá độ phức tạp thuật toán
• 2.5. Ưu nhược điểm
• 2.6. Hướng phát triển
• 3. CHƯƠNG 3: THIẾT KẾ XÂY DỰNG CHƯƠNG TRÌNH ỨNG DỤNG
• 3.1. Thiết kế giao diện và mô tả kịch bản
• 3.2. Đặc tả code
• 3.2.1. Đặc tả code JavaScript (Nguyễn Thái Dương)
• 3.2.2. Đặc tả code Java (Nguyễn Văn Dương)
• 3.2.3. Đặc tả code Python (Vũ Tuấn Dũng)

Tóm tắt

I. Giới thiệu về Mã hóa Elgamal và Tầm quan trọng trong Bảo mật Thông tin

Mã hóa Elgamal là một trong những thuật toán mã hóa công khai được sử dụng rộng rãi để bảo vệ thông tin nhạy cảm trong các hệ thống truyền thông. Được phát triển bởi Taher Elgamal vào năm 1984, phương pháp này dựa trên bài toán logarit rời rạc (Discrete Logarithm Problem), đảm bảo độ bảo mật cao. Trong thời đại hiện nay, khi các cuộc tấn công mạng ngày càng tinh vi, Elgamal mã hóa trở thành công cụ không thể thiếu để bảo vệ dữ liệu từ các lỗ hổng bảo mật. Với cơ chế mã hóa bất đối xứng, Elgamal cho phép mọi người có thể mã hóa tin nhắn bằng khóa công khai, nhưng chỉ người sở hữu khóa bí mật mới có thể giải mã. Điều này làm cho Elgamal trở thành lựa chọn lý tưởng cho các ứng dụng bảo mật thông tin hiện đại.

1.1. Lịch sử hình thành và phát triển của Elgamal

Elgamal được tạo ra bởi nhà mật mã học Taher Elgamal vào năm 1984 như một giải pháp mã hóa công khai hiệu quả. Thuật toán này dựa trên độ khó của bài toán logarit rời rạc trong nhóm nhân của trường hữu hạn. Elgamal nhanh chóng được chấp nhận và sử dụng trong các tiêu chuẩn mã hóa quốc tế như DSA (Digital Signature Algorithm). So với RSA, Elgamal cung cấp những ưu điểm riêng biệt trong việc xử lý dữ liệu mã hóa và ký số điện tử.

1.2. Ứng dụng thực tế của Elgamal trong bảo mật hiện đại

Mã hóa Elgamal được áp dụng rộng rãi trong các hệ thống bảo mật thông tin như PGP (Pretty Good Privacy), GnuPG, và nhiều ứng dụng truyền thông an toàn. Nó cũng được sử dụng trong ký số điện tử để xác thực tính xác thực của tài liệu. Với khả năng tạo chuỗi số ngẫu nhiên độc lập cho mỗi lần mã hóa, Elgamal cung cấp mức độ bảo mật cao hơn so với các phương pháp mã hóa xác định khác, làm cho nó trở nên lý tưởng cho các ứng dụng bảo vệ dữ liệu nhạy cảm.

II. Cơ sở Toán học của Thuật toán Elgamal

Cơ sở toán học của Elgamal dựa trên số học modulo và bài toán logarit rời rạc. Thuật toán sử dụng các khái niệm như phần tử sinh, phép lũy thừa modulo, và phần tử nghịch đảo để thực hiện mã hóa và giải mã an toàn. Để hiểu rõ cách thức hoạt động của mã hóa Elgamal, cần nắm vững các phép toán số học trên modulo như phép cộng, trừ, nhân và chia trong không gian modulo. Thuật toán Euclid mở rộng được sử dụng để tìm phần tử nghịch đảo modulo, là yếu tố quan trọng trong quá trình giải mã. Ngoài ra, kiểm tra số nguyên tố Miller-Rabin giúp xác định các số nguyên tố lớn cần thiết cho việc sinh khóa an toàn.

2.1. Số học modulo và các phép toán cơ bản

Số học modulo là nền tảng của mã hóa Elgamal. Cho số nguyên a và số nguyên dương n, phép chia a cho n thu được: a = q×n + r, trong đó 0 ≤ r < n. Phép modulo trả về phần dư r, ký hiệu (a mod n). Các phép toán modulo bao gồm cộng, trừ, nhân theo quy tắc: (a±b) mod n = ((a mod n) ± (b mod n)) mod n. Phép lũy thừa modulo (a^b mod n) được tối ưu hóa bằng thuật toán bình phương và nhân để xử lý các số lớn hiệu quả.

2.2. Bài toán logarit rời rạc và độ khó tính toán

Bài toán logarit rời rạc là nền tảng của tính bảo mật Elgamal. Cho nhóm nhân modulo Z*p và phần tử sinh g, tìm x sao cho g^x ≡ y (mod p) là bài toán khó. Với các số nguyên tố p lớn (1024 bit trở lên), không có thuật toán thời đa thức được biết đến để giải quyết bài toán này. Độ khó này bảo vệ khóa bí mật khỏi các cuộc tấn công. Số nguyên tố an toàn và phần tử sinh bậc cao được chọn cẩn thận để đảm bảo mức độ bảo mật tối đa.

III. Quy trình Sinh khóa và Mã hóa trong Elgamal

Quá trình sinh khóa Elgamal bao gồm ba bước chính: chọn số nguyên tố an toàn p lớn, tìm phần tử sinh g có bậc lớn, và chọn khóa bí mật x ngẫu nhiên. Khóa công khai được tính bằng y = g^x mod p. Quá trình mã hóa Elgamal yêu cầu người gửi chọn số ngẫu nhiên k cho mỗi tin nhắn m, rồi tính C1 = g^k mod p và C2 = m × y^k mod p. Bộ (C1, C2) là bản mã hóa. Quá trình giải mã sử dụng khóa bí mật x để tính m = C2 / (C1^x) mod p. Cơ chế này đảm bảo rằng chỉ người sở hữu khóa bí mật mới có thể giải mã tin nhắn thành công.

3.1. Các bước sinh khóa công khai và khóa bí mật

Sinh khóa Elgamal bắt đầu bằng việc chọn số nguyên tố lớn p (1024 bit hoặc hơn) thông qua kiểm tra Miller-Rabin. Tiếp theo, tìm phần tử sinh g có bậc (p-1) hoặc (p-1)/2 trong nhóm Z*p. Khóa bí mật x được chọn ngẫu nhiên từ khoảng [2, p-2]. Khóa công khai y được tính bằng y = g^x mod p sử dụng thuật toán bình phương và nhân. Cặp (p, g, y) tạo thành khóa công khai, trong khi x là khóa bí mật cần được giữ kín tuyệt đối.

3.2. Chi tiết quá trình mã hóa và giải mã dữ liệu

Mã hóa Elgamal nhận bản rõ m và khóa công khai (p, g, y). Người gửi chọn số ngẫu nhiên k từ [2, p-2], tính C1 = g^k mod p và C2 = m × y^k mod p, gửi (C1, C2). Giải mã sử dụng khóa bí mật x: tính s = C1^x mod p, rồi m = C2 × s^(-1) mod p. Điều này hoạt động vì s = g^(kx) = y^k, nên C2 × s^(-1) = m × y^k × (y^k)^(-1) = m. Tính ngẫu nhiên k đảm bảo bản mã hóa khác nhau ngay cả với cùng bản rõ.

IV. Hướng dẫn Xây dựng Chương trình Mã hóa Elgamal

Xây dựng chương trình Elgamal yêu cầu thực hiện các module chính như sinh khóa, mã hóa, giải mã và xử lý file. Chương trình có thể được phát triển bằng nhiều ngôn ngữ lập trình như Python, Java, JavaScript. Giao diện người dùng (GUI) giúp người dùng dễ dàng thực hiện các thao tác mã hóa và giải mã mà không cần hiểu sâu về toán học phức tạp. Thư viện cryptography hoặc thư viện số học có sẵn có thể hỗ trợ tính toán phép lũy thừa modulo và kiểm tra số nguyên tố hiệu quả. Quản lý file cho phép lưu/tải khóa công khai, khóa bí mật, và dữ liệu mã hóa một cách an toàn.

4.1. Cách triển khai các function chính trong chương trình

Chương trình mã hóa Elgamal cần các function cốt lõi như: (1) generate_prime(n) - sinh số nguyên tố ngẫu nhiên n bit, (2) find_generator(p) - tìm phần tử sinh, (3) generate_keys(p, g) - sinh (khóa công khai, khóa bí mật), (4) encrypt(m, p, g, y) - mã hóa bản rõ, (5) decrypt(c1, c2, x, p) - giải mã bản mã, (6) mod_inverse(a, n) - tính phần tử nghịch đảo modulo. Mỗi function sử dụng thuật toán tối ưu như bình phương và nhân cho phép lũy thừa và Euclid mở rộng cho tính nghịch đảo.

4.2. Thiết kế giao diện và xử lý tương tác người dùng

Giao diện chương trình Elgamal nên bao gồm các nút bấm (button) chính: "Sinh khóa", "Mã hóa", "Giải mã", "Lưu file", "Mở file". Vùng nhập liệu cho phép nhập bản rõ hoặc bản mã hóa. Vùng hiển thị kết quả cho phép xem khóa công khai, bản mã hóa và bản rõ sau giải mã. Xử lý sự kiện đảm bảo khi người dùng bấm "Mã hóa", chương trình sẽ kiểm tra dữ liệu đầu vào, thực hiện mã hóa và hiển thị kết quả. Quản lý file cho phép lưu/tải khóa và dữ liệu mã hóa an toàn.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Trong bối cảnh bùng nổ của mạng Internet và công nghệ số, các hình thức tấn công mạng ngày càng gia tăng về số lượng cũng như mức độ tinh vi. Để bảo vệ dữ liệu quan trọng không bị rò rỉ hoặc đánh cắp, kỹ thuật mã hóa thông tin trở thành giải pháp thiết yếu. Nhiều phương thức mã hóa và bảo mật thông tin đã được phát triển như AES, DES, RSA, ECC, SHA, MD5 và ElGamal. Nhóm tác giả lựa chọn nghiên cứu hệ mật mã khóa công khai ElGamal – một cơ chế mã hóa dựa trên nền tảng toán học vững chắc với nhiều ứng dụng trong thực tế.

Đề tài xác định 3 nhiệm vụ nghiên cứu chính:

1. Hệ thống hóa toàn diện cơ sở toán học nền tảng của mật mã học khóa công khai, bao gồm số học modulo, lý thuyết số, giải thuật Euclid mở rộng, thuật toán bình phương và nhân, thuật toán kiểm tra số nguyên tố Miller-Rabin và định lý phần dư Trung Hoa.
2. Phân tích chi tiết nội dung thuật toán ElGamal: quy trình sinh khóa, mã hóa và giải mã; đánh giá độ phức tạp tính toán; khảo sát 7 phương pháp tấn công phổ biến kèm biện pháp phòng ngừa; xác định ưu nhược điểm và tiềm năng ứng dụng.
3. Thiết kế giao diện đồ họa người dùng (GUI) và hiện thực hóa chương trình ứng dụng mã hóa/giải mã ElGamal trên các ngôn ngữ lập trình (JavaScript, Java, Python), hỗ trợ xử lý dữ liệu chuỗi ký tự và tập tin văn bản.

Đối tượng nghiên cứu là hệ mật mã khóa công khai ElGamal và các thuật toán toán học bổ trợ. Phạm vi nghiên cứu được thực hiện trong khuôn khổ học phần "An toàn và Bảo mật thông tin" (Lớp học phần: 20232IT6083005) tại Trường Đại học Công nghiệp Hà Nội (Bộ Công Thương), dưới sự hướng dẫn của ThS. Trần Phương Nhung, hoàn thành vào tháng 6 năm 2024 bởi Nhóm sinh viên số 6 gồm: Vũ Tuấn Dũng (MSV: 2019600050), Lê Đình Dương (MSV: 2022607015), Nguyễn Thái Dương (MSV: 2022603389) và Nguyễn Văn Dương (MSV: 2022600202).

Cơ sở lý thuyết và phương pháp

Đề tài vận dụng các cơ sở lý thuyết toán học và mô hình mật mã học sau:

• Số học modulo và quan hệ đồng dư: Lý thuyết về phép chia có dư $a = q \cdot n + r$ ($0 \le r < n$), khái niệm đồng dư thức $a \equiv b \pmod n$, các tính chất đại số trên modulo (cộng, trừ, nhân, chia) và khảo sát trên vành số học $\mathbb{Z}8$, $\mathbb{Z}{26}$.
• Giải thuật Euclid và Euclid mở rộng: Xác định ước chung lớn nhất $\text{GCD}(a, b)$ và tìm nghiệm nguyên $(x, y)$ cho phương trình Diophantine $ax + by = d$ nhằm tìm phần tử nghịch đảo modulo $a^{-1} \pmod n$.
• Thuật toán Bình phương và nhân (Square and Multiply): Kỹ thuật tính lũy thừa nhanh $A^k \pmod n$ dựa trên việc biểu diễn số mũ $k$ dưới dạng nhị phân.
• Lý thuyết số đại cương: Khái niệm số nguyên tố, phân tích thừa số nguyên tố, số nguyên tố cùng nhau, Định lý nhỏ Fermat ($a^{p-1} \equiv 1 \pmod p$), Hàm số Euler $\varphi(n)$ và Định lý Euler ($a^{\varphi(n)} \equiv 1 \pmod n$).
• Thuật toán kiểm tra số nguyên tố Miller-Rabin: Phép thử xác suất cho các số nguyên lớn dựa trên phân rã $n - 1 = 2^k q$ ($q$ lẻ).
• Định lý phần dư Trung Hoa (Chinese Remainder Theorem - CRT): Phương pháp phân tách phép toán trên modulo lớn $M = \prod m_i$ thành các hệ modulo nhỏ nguyên tố cùng nhau để tăng tốc độ tính toán.
• Nhóm Cyclic và Bài toán Logarithm rời rạc (Discrete Logarithm Problem - DLP): Nền tảng an toàn của hệ mật ElGamal dựa trên tính toán $a^x \equiv b \pmod p$.

Phương pháp nghiên cứu bao gồm: phương pháp phân tích - tổng hợp lý thuyết toán học chuyên sâu; phương pháp mô hình hóa quy trình thuật toán; phương pháp thiết kế kịch bản giao diện người dùng và phương pháp thực nghiệm lập trình, kiểm thử mã nguồn trên các nền tảng công nghệ độc lập. Nguồn dữ liệu sử dụng là các tập dữ liệu số học mẫu, chuỗi ký tự bản rõ và các định dạng tệp tin văn bản phổ biến.

Thiết kế và triển khai hệ thống ứng dụng

Đề tài xây dựng chương trình ứng dụng hoàn chỉnh với giao diện đồ họa người dùng (GUI) và đặc tả chi tiết mã nguồn trên các ngôn ngữ lập trình:

Thành phần / Chức năng	Mô tả chi tiết kỹ thuật và luồng xử lý
Giao diện người dùng (GUI)	Thiết kế trực quan chia thành các phân khu chức năng: Sinh khóa, Mã hóa, Giải mã, Quản lý tệp tin.
Kịch bản Sinh khóa	Người dùng kích hoạt nút "Sinh khóa tự động", hệ thống tự động sinh khóa công khai $K_{pub} = {p, \alpha, \beta}$ và khóa bí mật $K_{pri} = {a}$.
Kịch bản Mã hóa	Nhập dữ liệu vào ô "Bản rõ", nhấn nút "Mã hóa", hệ thống xử lý và hiển thị cặp bản mã $(y_1, y_2)$ tại ô "Bản mã". Hỗ trợ nút "Chuyển" để đẩy bản mã sang phân khu giải mã.
Kịch bản Giải mã	Nhấn nút "Giải mã", hệ thống sử dụng khóa bí mật để khôi phục và hiển thị dữ liệu gốc tại ô "Bản rõ".
Quản lý Tệp tin	Cung cấp chức năng "Lưu file" xuất kết quả ra định dạng .txt hoặc .docx; chức năng "Chọn file" cho phép tải file văn bản có sẵn vào hệ thống để mã hóa/giải mã.
Đặc tả mã nguồn JavaScript	Thành viên Nguyễn Thái Dương cài đặt: hàm đệ quy tìm $\text{GCD}(a, b)$; hàm chuyển đổi thập phân sang nhị phân; hàm squareAndMultiply(); thuật toán oClitMoRong(); kiểm thử nguyên tố millerRabinTest(); hàm sinh số nguyên tố 256-bit taoKhoaP(); hàm generateKeys(); hàm encrypt() sử dụng TextEncoder, Base64 và BigInt; hàm decrypt() sử dụng Uint8Array và TextDecoder.
Đặc tả mã nguồn Java	Thành viên Nguyễn Văn Dương triển khai: thuật toán bình phương và nhân tối ưu, xử lý các trường hợp biên của số mũ (âm/dương), giảm cơ số modulo, phân tách modulo chẵn/lẻ và phương thức oldModPow.
Đặc tả mã nguồn Python	Thành viên Vũ Tuấn Dũng xây dựng và đặc tả các module thuật toán tương ứng.

Nội dung chính theo từng chương

Chương 1: Cơ sở toán học

Chương này tập trung trình bày toàn bộ nền tảng toán học rời rạc và lý thuyết số phục vụ cho việc xây dựng các hệ mật mã:

• Số học trên modulo: Định nghĩa phép toán chia lấy dư $a \pmod n$, thiết lập quan hệ đồng dư thức và khảo sát các tính chất cộng, trừ, nhân, chia trên modulo. Nhóm tác giả minh họa chi tiết bảng các phép toán số học trên $\mathbb{Z}_8$ gồm phép cộng, nhân, tìm số đối và số nghịch đảo.
• Giải thuật Euclid và Euclid mở rộng: Trình bày thuật toán tìm $\text{GCD}(a, b)$ qua ví dụ $\text{GCD}(4864, 3458) = 38$. Mở rộng thuật toán để giải phương trình Diophantine $ax + by = d$; minh họa từng bước tính toán với đầu vào $a = 814, b = 187$, tìm được $\text{GCD}(814, 187) = 11$ và quan hệ $814 \times 3 + 187 \times (-13) = 11$.
• Tìm phần tử nghịch đảo trong $\mathbb{Z}_n$: Sử dụng Euclid mở rộng để tìm $a^{-1} \pmod n$. Minh họa chi tiết bảng tính tìm $173^{-1} \pmod{1024}$, xác định kết quả nghịch đảo là $805$.
• Thuật toán Bình phương và nhân: Phân tích quy trình tính $A^k \pmod n$ theo chuỗi bit nhị phân của số mũ $k$. Minh họa bảng tính từng bước với $a = 7, k = 560 = (1000110000)_2, n = 561$, cho giá trị kết quả cuối cùng bằng $1$.
• Lý thuyết số và số nguyên tố: Tổng quan danh sách các số nguyên tố nhỏ hơn $200$, nguyên lý phân tích thừa số nguyên tố duy nhất, khái niệm số nguyên tố cùng nhau, Định lý nhỏ Fermat, Hàm số Euler $\varphi(n)$ (minh họa tính $\varphi(10) = 4, \varphi(3600) = 960$) và Định lý Euler.
• Kiểm tra tính nguyên tố: Trình bày 2 tính chất cơ bản của số nguyên tố và giải thuật Miller-Rabin dựa trên phân rã $n - 1 = 2^k q$. Trình bày ví dụ kiểm thử với $n = 2047 = 23 \times 89$ và kiểm tra tính nguyên tố của $n = 29$.
• Định lý phần dư Trung Hoa: Trình bày kỹ thuật tính modulo số lớn $M = \prod m_i$ và phương pháp giải hệ phương trình đồng dư. Minh họa ví dụ tính $A = 17^8 \pmod{77} = 37$ và giải hệ đồng dư $x \equiv 5 \pmod 7, x \equiv 6 \pmod{11}$, thu được nghiệm $x = 61 \pmod{77}$.

Chương 2: Nội dung thuật toán

Chương 2 phân tích chuyên sâu về hệ mật mã ElGamal do nhà toán học Taher ElGamal phát minh năm 1985:

• Cơ sở lý thuyết: Hệ mật hoạt động trên cấu trúc đại số của nhóm cyclic và dựa trên độ khó của bài toán Logarithm rời rạc ($a^x \equiv b \pmod p$).
• Quy trình hoạt động của thuật toán:
  1. Khởi tạo khóa: Chọn số nguyên tố lớn $p$, phần tử nguyên thủy $g \in \mathbb{Z}p^*$, khóa bí mật $x \in {2, 3, \dots, p-2}$. Tính $y = g^x \bmod p$. Khóa công khai là $K{pub} = (p, g, y)$ và khóa bí mật là $K_{pri} = (x)$.
  2. Mã hóa: Với thông điệp $m$, người gửi chọn số ngẫu nhiên $k \in \mathbb{Z}_{p-1}$, tính cặp bản mã $(c_1, c_2)$ với $c_1 = g^k \bmod p$ và $c_2 = m \cdot y^k \bmod p$.
  3. Giải mã: Người nhận dùng khóa bí mật $x$ tính nghịch đảo $(c_1^x)^{-1} \bmod p$ và khôi phục bản rõ: $m = c_2 \cdot (c_1^x)^{-1} \bmod p$.
• Các phương pháp tấn công và biện pháp phòng ngừa:

Tên phương pháp tấn công	Mô tả kỹ thuật tấn công	Biện pháp phòng ngừa do tác giả đề xuất
Giải mã không đầy đủ (Partial Decryption)	Cố gắng giải mã một phần thông điệp dựa trên bản mã và thông tin phụ.	Áp dụng kỹ thuật mã hóa bảo đảm toàn vẹn và chống giải mã từng phần.
Logarithm rời rạc (Discrete Logarithm)	Cố gắng giải bài toán logarithm rời rạc để tìm khóa bí mật $x$.	Sử dụng tham số $p$ và $g$ có độ dài đủ lớn để không khả thi về thời gian.
Phân tích tần số (Frequency Analysis)	Khai thác thông điệp ngắn hoặc lặp lại để tìm mẫu giải mã.	Đảm bảo chiều dài bản rõ, áp dụng kỹ thuật đệm (padding) và tăng entropy.
Bản mã được chọn (Chosen-Ciphertext - CCA)	Gửi bản mã tùy chọn đến hệ thống để suy luận thông tin khóa bí mật.	Sử dụng các giao thức kháng CCA (như mô hình CCA2-secure).
Thông tin bên lề (Side-Channel)	Đo đạc thời gian xử lý, mức tiêu thụ năng lượng hoặc dấu vết vật lý.	Áp dụng kỹ thuật làm mờ (blinding) và bảo vệ vật lý triệt tiêu rò rỉ.
Xác suất (Probability Attack)	Dùng các mô hình thống kê xác suất để suy ra khóa hoặc thông điệp.	Sử dụng tham số ngẫu nhiên lớn và cơ chế tăng cường bảo mật.
Vét cạn (Bruteforce)	Thử toàn bộ không gian khóa cho đến khi tìm được khóa bí mật.	Tăng độ dài không gian khóa để vô hiệu hóa tấn công trong thời gian thực.

• Đánh giá độ phức tạp thuật toán:
  • Khởi tạo khóa: $O(k \cdot \log^3 p)$ (phụ thuộc vào kiểm tra số nguyên tố và lũy thừa modulo).
  • Quá trình mã hóa: $O(\log p)$ (chủ yếu là chi phí tính lũy thừa modulo).
  • Quá trình giải mã: $O(\log p)$ (tính lũy thừa modulo và phần tử nghịch đảo).
• Ưu và nhược điểm:
  • Ưu điểm: Độ an toàn cao dựa trên bài toán khó Logarithm rời rạc; tính bất định (ngẫu nhiên hóa qua giá trị $k$) giúp cùng một bản rõ sẽ cho các bản mã khác nhau ở mỗi lần mã hóa.
  • Nhược điểm: Kích thước bản mã lớn gấp đôi thông điệp gốc (do sinh ra cặp $(c_1, c_2)$); khối lượng tính toán modulo lớn có thể chậm hơn so với RSA trong một số ngữ cảnh.
• Hướng phát triển: Đề xuất ứng dụng hệ mật vào các phần mềm nhắn tin bảo mật và tích hợp chữ ký số để chống chối bỏ trách nhiệm.

Chương 3: Thiết kế xây dựng chương trình ứng dụng

Chương 3 trình bày chi tiết về mặt kỹ thuật, giao diện đồ họa và đặc tả thuật toán trong mã nguồn của nhóm tác giả trên JavaScript, Java và Python. Các chức năng được hiện thực hóa đầy đủ từ việc sinh khóa 256-bit, chuyển đổi dữ liệu chuỗi ký tự sang số học modulo lớn bằng BigInt, xử lý tệp tin văn bản cho đến khôi phục chuỗi bản rõ ban đầu.

Kết quả và đóng góp

• Kết quả thực nghiệm và số liệu:
  • Hệ thống hóa hoàn chỉnh 7 chuyên đề toán học phục vụ mật mã học với các ví dụ số học tường minh (chẳng hạn kiểm thử $173^{-1} \pmod{1024} = 805$, tính $7^{560} \pmod{561} = 1$, giải hệ phương trình đồng dư cho nghiệm $x = 61 \pmod{77}$).
  • Cài đặt thành công thuật toán sinh số nguyên tố ngẫu nhiên $p$ có kích thước 256-bit phục vụ khởi tạo khóa an toàn.
  • Xây dựng hoàn chỉnh ứng dụng GUI hỗ trợ đầy đủ quy trình sinh khóa tự động, mã hóa, giải mã, chuyển giao dữ liệu trực tiếp và đọc/ghi tệp tin định dạng .txt, .docx.
  • Cung cấp đặc tả mã nguồn chi tiết trên 3 ngôn ngữ: JavaScript (xử lý Web/Frontend), Java (tối ưu tính toán số lớn) và Python.
• Giải pháp và kiến nghị đề xuất:
  • Nhóm tác giả đề xuất thiết lập độ dài khóa tối thiểu từ 256-bit trở lên để ngăn ngừa triệt để các hình thức tấn công vét cạn (Bruteforce) và tấn công Logarithm rời rạc.
  • Khuyến nghị tích hợp các kỹ thuật đệm (padding) để tăng entropy của dữ liệu bản rõ nhằm triệt tiêu nguy cơ tấn công phân tích tần số.
  • Áp dụng các giải pháp kỹ thuật làm mờ (blinding) trong quá trình tính toán để phòng chống tấn công kênh kề (Side-Channel).
• Đóng góp của đồ án:
  • Cung cấp tài liệu tham khảo học thuật có tính hệ thống cao, kết nối trực tiếp giữa lý thuyết toán học trừu tượng với các bước triển khai mã nguồn thực tế.
  • Đóng góp một công cụ phần mềm trực quan hỗ trợ công tác giảng dạy, học tập và kiểm nghiệm thuật toán mã hóa ElGamal.

Hạn chế và hướng nghiên cứu tiếp

• Hạn chế:
  • Chương trình ứng dụng được xây dựng dưới dạng ứng dụng thử nghiệm (demo) học tập, chưa tích hợp đầy đủ hệ thống quản lý chứng chỉ khóa công khai (PKI).
  • Kích thước dữ liệu sau mã hóa luôn tăng gấp đôi so với bản rõ ban đầu do đặc thù sinh cặp giá trị $(c_1, c_2)$ của thuật toán ElGamal.
  • Tốc độ xử lý tính toán số học trên các modulo lớn còn phụ thuộc vào hiệu năng của ngôn ngữ thực thi.
• Hướng nghiên cứu tiếp: Nhóm tác giả định hướng phát triển ứng dụng vào hệ thống phần mềm nhắn tin bảo mật thời gian thực và xây dựng sơ đồ chữ ký số điện tử ElGamal nhằm nâng cao tính toàn vẹn và xác thực người dùng.

Giá trị tham khảo

Đồ án là tài liệu học thuật giá trị dành cho:

• Sinh viên chuyên ngành Công nghệ thông tin và An toàn thông tin: Nắm vững cơ sở toán học mật mã (Euclid mở rộng, Miller-Rabin, CRT) và hiểu rõ nguyên lý hoạt động của các hệ mật mã phi đối xứng.
• Lập trình viên và người nghiên cứu phát triển phần mềm an toàn: Tham khảo phương pháp đặc tả thuật toán số học lớn trên JavaScript (BigInt, TextEncoder, TextDecoder) và Java (oldModPow, tối ưu lũy thừa modulo).
• Người làm đồ án, bài tập lớn môn học: Cung cấp mẫu cấu trúc chuẩn mực cho một báo cáo bài tập lớn môn An toàn và Bảo mật thông tin từ lý thuyết đến xây dựng ứng dụng demo.

Câu hỏi thường gặp

1. Bản mã trong hệ mật mã ElGamal gồm những thành phần nào và tại sao kích thước lại tăng gấp đôi? Bản mã ElGamal gồm một cặp hai giá trị $(c_1, c_2)$, trong đó $c_1 = g^k \bmod p$ (thành phần khóa tạm thời) và $c_2 = m \cdot y^k \bmod p$ (thành phần thông điệp đã mã hóa). Do cần lưu trữ cả hai giá trị số học lớn này để phục vụ quá trình giải mã, kích thước bản mã sinh ra luôn lớn gấp đôi kích thước của thông điệp gốc $m$.

2. Độ phức tạp tính toán của các giai đoạn trong thuật toán ElGamal được đánh giá như thế nào? Theo tài liệu, giai đoạn Khởi tạo khóa có độ phức tạp $O(k \cdot \log^3 p)$ do phải thực hiện kiểm tra tính nguyên tố và tính toán lũy thừa modulo lớn. Giai đoạn Mã hóa và giai đoạn Giải mã đều có độ phức tạp là $O(\log p)$, chủ yếu phục vụ việc tính toán lũy thừa và tìm phần tử nghịch đảo modulo.

3. Nhóm tác giả cài đặt thuật toán Miller-Rabin trong chương trình nhằm mục đích gì? Thuật toán Miller-Rabin được cài đặt dưới hàm millerRabinTest() để kiểm tra tính nguyên tố của các số nguyên ngẫu nhiên lớn (như số nguyên tố $p$ có độ dài 256-bit trong hàm taoKhoaP()). Do việc kiểm tra số nguyên lớn bằng cách thử chia thông thường không khả thi về mặt thời gian, Miller-Rabin cung cấp phép thử xác suất nhanh chóng và hiệu quả.

4. Nhóm tác giả đề xuất biện pháp gì để phòng chống tấn công phân tích tần số và tấn công kênh kề? Đối với tấn công phân tích tần số, tác giả đề xuất đảm bảo độ dài thông điệp, áp dụng kỹ thuật đệm (padding) hoặc tăng entropy dữ liệu. Đối với tấn công kênh kề (Side-Channel), tác giả khuyến nghị sử dụng kỹ thuật làm mờ (blinding) và các biện pháp bảo vệ vật lý nhằm giảm thiểu rò rỉ thông tin về thời gian xử lý hoặc năng lượng tiêu thụ.

5. Ứng dụng demo hỗ trợ những định dạng tệp tin nào và xử lý chuyển đổi văn bản ra sao? Ứng dụng hỗ trợ đọc và lưu tệp tin ở định dạng văn bản .txt và tài liệu .docx. Trong mã nguồn JavaScript, chuỗi ký tự văn bản được chuyển đổi sang mảng số bằng TextEncoder và mã hóa Base64 trước khi đưa vào cấu trúc BigInt để tính toán modulo; quá trình giải mã sử dụng mảng byte Uint8Array và TextDecoder để khôi phục chính xác chuỗi ký tự ban đầu.

Kết luận

Báo cáo bài tập lớn của nhóm sinh viên Trường Đại học Công nghiệp Hà Nội đã hoàn thành toàn diện việc nghiên cứu và hiện thực hóa hệ mật mã khóa công khai ElGamal. Đề tài hệ thống hóa chặt chẽ các nền tảng toán học mật mã cốt lõi, phân tích cặn kẽ quy trình thuật toán cùng các kịch bản tấn công và giải pháp phòng ngừa thực tế. Ứng dụng demo được thiết kế hoàn chỉnh với giao diện GUI và mã nguồn đa nền tảng (JavaScript, Java, Python), tạo nên một tài liệu học tập và tham khảo có giá trị cao cho môn học An toàn và Bảo mật thông tin.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: CƠ SỞ TOÁN HỌC 1.1 Số học trên modulo 1.1 Định nghĩa modulo Cho một số nguyên a và số nguyên dương n bất kỳ, thực hiện phép chia a cho n thì thu được thương số q và phần dư r thỏa mãn mối quan hệ sau: a = q.x +r 0≤r<n Ví dụ minh họa trên bảng 1. Minh họa thương số và phần dư khi thực hiện phép chia a cho n a = 13 n=4 13 = 3 x 4 + 1 q=3 r=1 a = -13 n=4 -13 = (-4) x 4 + q = -4 r=3 3 Tóm lại, cho một số nguyên a và số nguyên dương n thì ta định nghĩa a mod n là phần dư của phép chia a cho n. Ví dụ: 13 mod 4 = 1 và -13 mod 4 = 3 Hai số nguyên a và b được gọi là đồng dư modulo với n nếu (a mod n) = (b mod n) và được ký hiệu như sau: a ≡ b (mod n) Ví dụ: 13 ≡ 5 (mod 4) vì 13 mod 4=1 và 5 mod 4 = 1 7 ≡ −13 (mod 4) vì 7 mod 4 = 3 và −13 mod 4 = 3 1.2 Ước số 8 Ta nói rằng a chia hết cho số b khác không nếu tồn tại số m nào đó để a = m.b, trong đó m, a, b là các số nguyên. a chia hết cho b được kí hiệu là b|a và b được gọi là ước số của a.

Ví dụ các ước số dương của 15 là 1, 3, 5 và 15.3 Các phép toán trên modulo (A + B) % C = ((A % C) + (B % C)) % C (A - B) % C = ((A % C) - (B % C)) % C (A * B) % C = ((A % C) * (B % C)) % C (A / B) % C = ((A % C) * (B-1 % C)) % C  Nếu (a + b) ≡ (a + c) mod n thì b ≡ c mod n.c) mod n, thì b ≡ c mod n, khi a là nguyên tố cùng nhau với n. Ví dụ: (11 * 19) mod 7 = (11 mod 7 * 19 mod 7) mod 7 = 20 mod 7 = 6 Bảng 1.2 sau minh họa phép toán số học cộng, nhân, số đối và số nghịch đảo trên modulo 8. Số đối của số nguyên x là số nguyên y sao cho (x + y) mod 8 = 0, số nghịch đảo của số nguyên x là số nguyên y sao cho (x. Như vậy, để tìm các số đối của các số nguyên ở cột bên trái bảng cộng bằng cách quét lần lượt các phần từ trong dòng để tìm phần tử 0 và khi đó phần tử ở dòng đầu tiên ứng với cột này là số đối.

Tương tự, để tìm giá trị nghịch đảo của số bên trái của bảng nhân bằng cách quét lần lượt các phần tử trong dòng để tìm phần tử 1 và khi đó phần tử đầu tiên ứng với cột này là số nghịch đảo.