Về một hệ chữ ký số

Kỷ yếu công trình khoa học 2015 – Phần I 
VỀ MỘT HỆ CHỮ KÝ SỐ 
TS. Nguyễn Công Sứ 
Khoa Toán-Tin, Đại học Thăng Long 
Email: congsu1945@yahoo.com.vn 
 Tóm tắt: Một chữ ký bằng tay "thông thường" gắn liền với một văn bản được sử dụng 
để xác định người tạo ra và chịu trách nhiệm về văn bản đó. Chữ ký được sử dụng trong các 
sự việc hàng ngày như viết thư, rút tiền từ ngân hàng, ký một hợp đồng, vv ... Hệ chữ ký số là 
phương thức ký các văn dạng diện tử. Do đó, một văn bản đã được ký có thể truyền qua mạng 
thông qua các máy tính và thiết bị hỗ trợ. Một hệ chữ ký số gồm 02 thành phần: một thuật 
toán ký và một thuật toán xác minh chữ ký. Một người A có thể ký văn bản x sử dụng (khóa bí 
mật của mình) theo hàm . Kết quả của chữ ký (x) có thể được kiểm tra bởi một thuật 
toán xác minh công khai . Đối với một cặp (x, y), trong đó x là văn bản và y là chữ ký 
của x, thuật toán sẽ kiểm tra và trả về “Đúng” hoặc “Sai” phụ thuộc y là chữ ký hợp lệ của x 
hay không. Trong bài viết này, chúng tôi trình bày kết quả tìm hiểu và triển khai một hệ chữ 
ký số. 
Từ khóa:Chữ ký số, R.S.A, Mật mã, Mã hóa. Khóa bí mật. Khóa công khai. Hệ mật 
phi đối xứng. 
1. Khái niệm về chữ ký số 
Chữ ký suy cho cùng là một hành động tác động vào văn bản nhằm đảm bảo để cả chủ 
nhân của chữ ký lẫn người nhận văn bản được ký tin tưởng rằng: 
• Nội dung của văn bản đã ký đã được người ký đồng ý và không thể từ chối 
trách nhiệm về chủ quyền của văn bản. 
• Chữ ký trong văn bản không thể bị làm giả mạo bởi một người nào khác. 
Tuy nhiên điểm khác biệt giữa chữ ký truyền thống thường được ký trên các văn bản 
“viết tay” và chữ ký điện tử thường được ký trên các văn bản điện tử để lưu trữ, hoặc truyền 
trên mạng máy tính là: 
• Chữ ký truyền thống là một phần vật lý tách rời với văn bản (nó chỉ được gắn 
vào phần dưới của văn bản), còn chữ ký điện tử lại được ``gắn'' với từng yếu tố 
của văn bản. 
• Chữ ký thông thường được kiểm tra bởi các phương tiện vật lý, hóa học, nói 
chung là các thủ pháp xác thực mà độ tin tưởng của các kết quả kiểm tra lại 
chính là vấn đề cần phải kiểm tra, trong khi đó chữ ký số lại có thể và chỉ có 
thể kiểm tra bằng chính thuật toán kiểm tra, có thể công khai với mọi người và 
độ tin tưởng của thuật toán thì đã được chứng minh. 
Như vậy bất kỳ người nào cũng có khả năng (đương nhiên với sự am hiểu cần thiết) 
kiểm tra sự đúng đắn của không chỉ chữ ký mà cả chính văn bản đã được ký (bằng điều đó, 
người ký đã hoàn toàn có khả năng ngăn cản việc giả mạo cả văn bản lẫn chữ ký của mình). 
Ngoài ra chữ ký điện tử còn tránh được việc sử dụng lại hoặc “cắt, dán” vào văn bản 
khác như thường xảy ra với chữ ký thông thường. 
Trường Đại học Thăng Long 93 
Kỷ yếu công trình khoa học 2015 – Phần I 
Để có thể thấy rõ những vấn đề trên, chúng ta cần tìm hiểu qua về bản chất toán học 
của chữ ký điện tử. Trước hết là định nghĩa hình thức về lược đồ chữ ký số: 
Định nghĩa 1.1.Lược đồ chữ ký số là bộ 5 thành phần (P,A,K,S,V) trong đó: 
1. P: tập hữu hạn tất cả các bản ghi có thể có. 
2. A: tập hữu hạn các chữ ký có thể có. 
3. K: không gian khóa, đó là tập tất cả các khóa1 có thể có. 
4. Với mỗi khóa , có một thuật toán và một thuật toán kiểm tra tương 
ứng , trong đó: 
 : 
 còn : 
là các ánh xạ sao cho phương trình sau đây thỏa mãn với mỗi bản tin và 
mỗi chữ ký : 
Cặp được gọi là bản lưu đã được ký. 
Chú ý rằng với mỗi , các thuật toán , là các ánh xạ với thời gian đa 
thức (độ phức tạp đa thức). Ngoài ra là ánh xạ công khai, còn là bí mật.Với mỗi x 
cho trước, một người nào khác với chủ nhân A của chữ ký không thể tính được ra y sao cho 
. (Nếu một người khác nào đó (C) lại có thể tính ra một cặp (x, y) sao cho 
 và x không phải văn bản đã được ký trước đó bởi A thì chữ ký y được coi 
là giả mạo, tức là chữ ký đó không phải là của A). 
2. Thuật toán tạo chữ ký số - Hệ chữ ký số R.S.A 
2.1. Hệ mật phi đối xứng 
Các hệ mật phi đối xứng, còn gọi là các hệ mật hai khóa, hay khóa công khai là công 
cụ hữu hiệu để thiết kế một hệ chữ ký số (về vấn đề này đã được bàn kỹ trong lĩnh vực mật 
mã cả trên phương diện lý thuyết lẫn thực hành). Đó là một hệ mật (hệ thống mật mã) đặc 
trưng bởi hai điều kiện cốt lõi sau: 
 1. Khóa mã và khóa dịch mã phải khác nhau. 
 2. Giữa hai khóa bị ràng buộc bởi một quan hệ toán học đặc biệt sao cho việc xác 
định một khóa từ khóa kia là “rất khó” về phương diện tính toán, và vì vậy một khóa có thể 
cho công khai (gọi là khóa công khai - ký hiệu K1), khóa còn lại phải giữ ”tuyệt 
đối” bí mật (gọi là khóa bí mật - ký hiệu K2). 
1Khái niệm khóa (key) ở đây khác với khái niệm mật khẩu (password) ở chỗ khóa cần phải tham gia vào quá 
trình mã hóa, biển đổi thông tin. 
Trường Đại học Thăng Long 94 
Kỷ yếu công trình khoa học 2015 – Phần I 
2.2. Hàm một phía và hàm một phía có cửa sập 
Vấn đề trọng tâm của hệ mật phi đối xứng lại nằm ở khái niệm hàm một phía và hàm 
một phía có cửa sập trong toán học. Đó là: 
Định nghĩa 2.1.Hàm2 được gọi là một phía nếu: 
 1. Tồn tại một thuật toán đa thức để tính . 
 2. Từ giá trị y, việc tính được x để (hay là tính được ) 
chỉ với xác suất rất nhỏ và do vậy coi là không tính được trong thực tế. 
Tuy nhiên sự tồn tại hàm một phía cũng chỉ là điều kiện cần để có được hệ mật phi đối 
xứng, bởi lẽ việc khó, hoặc “không tính được”x từ y sẽ dẫn đến việc mà mã không thể giải mã 
được (yêu cầu bắt buộc với hệ mật). Tình trạng trên sẽ được giải quyết nếu hàm là 
hàm một phía có “cửa sập”. Đó là: 
Định nghĩa 2.2.Hàm một phía được gọi là có “cửa sập” nếu khi đưa một 
thông tin bổ sung nào đó vào f thì việc tính ngược x từ y ( ) trở nên dễ dàng, ngoài 
ra việc tìm ra thông tin bổ xung từ y cũng khó tương đương với việc tìm ra x. 
Yêu cầu về tính có “cửa sập” của hàm một phía có vẻ như là một yêu cầu bất khả thi. 
Tuy nhiên rất may là cho đến nay, Toán học đã chỉ ra rằng thực tế là đang tồn tại không ít 
những hàm như vậy. Mà đặc biệt thú vị ở chỗ, những hàm đó lại gắn với các bài toán khá cổ 
điển trong toán học (đương nhiên không phải là tất cả). 
2.3. Hàm một phía có “cửa sập” R.S.A 
Định nghĩa 2.3. Cho hai số nguyên tố lớn p và q, gọi và hàm Euler của 
 (số các số nguyên tố với n và nhỏ hơn n). Khi đó: nếu lấy một số 
a sao cho tồn tại thì với mỗi hàm: 
 (1) 
là hàm một phía3. 
Tuy nhiên đây là hàm một phía có cửa sập với “tham số cửa sập” là . 
Thật vậy: Do biết và vì vậy là và do đó tính được 
 bằng thuật toán đa thức Euler mở rộng. Đến đây, việc tính ngược 
 (2) 
được thay bởi 
2Ở đây ta đồng nhất khái niệm hàm với ánh xạ. 
3Vào thời điểm hiện tại, nếu thì thuật toán tốt nhất có thể để tính được cần một 
khối lượng thời gian vượt khỏi khả năng của công nghệ tính toán. 
Trường Đại học Thăng Long 95 
Kỷ yếu công trình khoa học 2015 – Phần I 
cũng như phép tính thuận (1) là dễ. 
Dễ dàng chỉ ra rằng việc tính ra từ n và a cũng tương đương với việc tính ra p và 
q và việc tính logarit trong trường số nguyên. 
Như vậy ở đây p, q là tham số cửa sập trong hàm một phía n = p.q. Và do 
vậy . 
2.4. Hệ chữ ký số R.S.A 
Hệ chữ ký số R.S.A là hệ chữ ký được thiết kế dựa trên hàm một phía có cửa sập 
R.S.A hay hệ một phía phi đối xứng R.S.A tương tự như với hệ mật R.S.A. Khi đó: 
Định nghĩa 2.4. Hệ chữ ký số R.S.A là hệ chữ ký số mà 
 1. 
 2. 
. 
 3. Khóa công khai còn khóa bí mật . Khi đó với 
 thì: 
Như vậy theo lược đồ trên thì khi bên A (người ký văn bản) muốn ký văn bản của 
mình để gửi cho bên B, anh ta phải thực hiện liên tiếp các bước sau: 
 1. Chọn từ đó tính ra rồi chọn tiếp 
 sao cho . 
 2. Công khai hóa (thường lưu sẵn trong danh bạ khóa công khai - 
kiểu danh bạ điện thoại). 
 3. Thực hiện việc ký bằng thuật toán ký: 
Khi đó chữ ký của A trên sẽ là cặp được gửi đến cho B.Bất kỳ người nào, 
chứ không phải chỉ riêng B, đều có thể kiểm tra chữ ký của A trên bằng cách lấy khóa công 
khai của A từ danh bạ khóa công khai để thực hiện thuật toán kiểm tra 
Trường Đại học Thăng Long 96 
Kỷ yếu công trình khoa học 2015 – Phần I 
Một câu hỏi đặt ra là liệu có chăng khả năng một người nào đó tạo được một cách 
ngẫu nhiên mà là chữ ký ứng với . Điều đó là có thể (dù với xác suất rất nhỏ). Tuy nhiên có 
thể ngăn cản khả năng này bằng một thủ pháp hữu hiệu là bổ xung vào một “độ dư ngẫu 
nhiên” và sử dụng hàm đặc biệt - hàm Hash4và khi đó lược đồ ký một văn bản sẽ là: 
Signing a message digest: 
Message x 
Message digest z = h(x) 
Signature 
y = 
Ở đây h(x) là một hàm hash của x. 
3. Thiết kế một hệ chữ ký số thực tế 
Chữ ký số nói riêng và mật mã nói chung, suy cho cùng là một khoa học của các 
phương pháp toán học và các thủ pháp (protocol). Điều đó có nghĩa là khoa học của các quy 
tắc toán học chặt chẽ, phổ dụng (công khai) với các thủ thuật mẹo mực (nhưng lại cũng cần có 
chứng minh chặt chẽ). 
Do vậy không có, hay nói chính xác là không thể có một tài liệu nào trình bày đủ chi 
tiết về cách thức xây dựng một hệ chữ ký thực tế, thích dụng. 
Xây dựng một hệ chữ ký số đủ đáp ứng một số yêu cầu cơ bản về mức độ xác thực dữ 
liệu trong trường Đại hoc Thăng Long là nhiệm vụ cụ thể, mới và mang tính đặc thù, nhưng 
lại cần phù hợp với các quy định cả về phương diện hành chính lẫn luật pháp. 
Do vậy việc thiết kế hệ chữ ký số dùng “thử nghiệm”trong trường Đại học Thăng 
Long đã được xây dựng thành một chương trình nghiên cứu bao gồm các đề tài sau: 
Đề tài thứ nhất:Xây dựng hệ quản lý chứng thư số hay hạ tầng cơ sở khóa công khai, 
chữ ký số và các thủ tục xác thực khác. 
Đề tài thứ hai:Tạo các số ngẫu nhiên, các cặp số nguyên tố mạnh cho một không gian 
khóa đủ dùng khi xây dụng hệ chữ ký số R.S.A. 
Đề tài thứ ba:Hàm băm - Hàm băm mật mã (Hash) trong hệ thống chữ ký số có độ 
xác thực cao. 
Đề tài thứ tư:Các thuật toán và thủ tục mã, ký, kiểm tra chữ ký và kỹ thuật đảm bảo 
cho việc ký văn bản bằng hệ chữ ký số R.S.A. 
Sau gần một năm học tập, nghiên cứu, thử nghiệm, cuối cùng chúng ta có thể khẳng 
định các kết quả sau: 
4Hàm Hash sẽ được trình bày trong báo cáo riêng. 
Trường Đại học Thăng Long 97 
Kỷ yếu công trình khoa học 2015 – Phần I 
• Có một đội ngũ chuyên gia đủ am hiểu về lĩnh vực mật mã khóa công khai nói 
chung và chữ ký số nói riêng, đáp ứng yêu cầu đào tạo lĩnh vực an toàn thông 
tin của nhà trường trong tương lai. 
• Xây dựng được một hệ thống tư liệu, tài liệu, bài giảng đủ đáp ứng yêu cầu 
nghiên cứu, học tập và giảng dạy cho nhiều loại đối tượng trong trường. 
• Có được một hệ chữ ký số R.S.A đủ đáp ứng yêu cầu sử dụng của nhà trường 
cả trong thời gian hiện tại lẫn tương lại gần. 
Các báo cáo tiếp theo là các nội dung và kết quả cơ bản thu được trong từng đề tài của 
chương trình. 
4. Tài liệu tham khảo 
[1] Doug R. Stinson, Cryptography: Theory and Practice, third edition, 2015. 
[2] C. Г. Бapигeв, B. B. Гoнчaнoв, P. E. Cepoв, Oснoвы Coвpeмeннoй 
Kpиптoгpaфии, Mocквa 2002. 
[3] Nguyễn Công Sứ, Cơ sở lý thuyết mật mã, bài giảng cho khoa Công nghệ thông 
tin - Đại học Phương Đông, lưu hành nội bộ, Hà Nội 2002. 
Abstract:A "conventional" handwritten signature attached to a document is used to 
specify the person responsible for it. A signature is used in everyday situations such as 
writing a letter, drawing money from bank, singing a contract, etc... A signature scheme is a 
method of signing a message stored in electronic form. As such, a signed message can be 
transmitted over a computer network. A signature scheme consists of two components: a 
signing algorithm and a verification algorithm. A person A can sign a message x using a 
(private) signing algorithm which depends an a private key k. The resulting signature 
(x) can subsequently be verified using a public verification algorithm . Given a pair 
(x, y), where x is a message and y is a purported signature on x, the verification algorithm 
returns an answer "true" or "false" depending on whether y is a valid signature for the 
message x. In this paper, we will study one signature schemer, which are also called digital 
signature schemer. 
Trường Đại học Thăng Long 98