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ó.

, có một thuật toán

4. Với mỗi khóa

ứng

và một thuật toán kiểm tra tươ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
mỗi chữ ký

Cặp

và

:

đượ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).

1
Khá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
hàm một phía có “cửa sập”. Đó là:
Định nghĩa 2.2.Hàm một phía

là

đượ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à do đó tính được

và vì vậy là

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ạ.
thì thuật toán tốt nhất có thể để tính được
Vào thời điểm hiện tại, nếu
khối lượng thời gian vượt khỏi khả năng của công nghệ tính toán.

3

Trư ng Đ i h c Thăng Long

cần một

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

. Khi đó với

còn khóa bí mật
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
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

sao cho
2. Công khai hóa
kiểu danh bạ điện thoại).
3. Thực hiện việc ký

Khi đó chữ ký của A trên

rồi chọn tiếp

.
(thường lưu sẵn trong danh bạ khóa công khai -

bằng thuật toán ký:

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
khai

của

bằng cách lấy khóa công

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

ngẫu nhiên mà là chữ ký ứng với

một cách

. Đ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
Signature

z = h(x)

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:

4

Hàm Hash sẽ được trình bày trong báo cáo riêng.

Trư ng Đ i h c Thăng Long

97