Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TIN HỌC
************

ĐỖ THỊ XUÂN THẮM

TÌM HIỂU VỀ CHỮ KÝ SỐ
(DIGITAL SIGNATURE) VÀ ỨNG
DỤNG

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Tin học

HÀ NỘI - 200

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

1


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

MỤC LỤC
Lời mở đầu
Đặt vấn đề…………………………………………………………...

1

Chƣơng 1: Cơ sở lý thuyết.……………….……………………….

4

1.1. Mật mã.……………………………………………..…………..

4

1.2. Tạo số ngẫu nhiên .………………………………………….….

4

1.3. Tính mã băm của password ……………………………..……..

5

Chƣơng 2: Chữ ký số (Digital Signature)…………………..…….

6

2.1. Lịch sử phát triển của chữ ký số……………...…………..…….

6

2.2. Giới thiệu chung về chữ ký số …………………………..……..

6

2.3. Định nghĩa lược đồ chữ ký số……………………..……..……..

8


2.4. Một vài lược đồ chữ ký số……………………………...………

8

2.4.1. Lược đồ chữ ký RSA ………………………………...………

8

2.4.2. Lược đồ ElGamal…………………………………………….

11

Chƣơng 3: Hàm băm (hash)…………………..…………….…….

15

3.1. Giới thiệu ……………………………………………….……...

15

3.2 Định nghĩa………………………………...…………...…….….

16

3.3. Một số hàm Hash sử dụng trong chữ ký số…………...……….

16

3.3.1. Các hàm Hash đơn giản……………………………...……….


16

3.3.2. Hàm Hash MD5………………………………………………

18

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

2


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

Chƣơng 4: Cách làm việc của chữ ký số Digital Signature)……

26

4.1. Giới thiệu chung………………………………………………..

26

4.2. Ký chữ ký và xác thực chữ ký số……………………………….

26

4.2.1. Ký gửi chữ ký số (mã hóa –Encrypt)..................................…..

26


4.2.2. Xác thực chữ ký số (giải mã – Decrypt)......................…..…...

28

4.3. Chương trình Demo mô phỏng chữ ký số đơn giản........…..…..

29

4.4. Phân loại chữ ký số……………………………………………..

32

Chƣơng 5: Chữ ký số ngƣời dùng không chối bỏ
(undenial signature)……………………………………………….

34

5.1. Giới thiệu……………………………………………………….

34

5.2. Lược đồ chữ ký chống chối bỏ…………………………………

34

5.2.1. Thuật toán ký…………………………………………………

34

5.2.2. Giao thức kiểm tra……………………………………………


35

5.2.3. Giao thức chối bỏ……………………………………………..

37

5.3. Các định lý ………………………………..…………….……...

38

5.4. Vấn đề cần giải quyết ……………………..…………….……..

42

Chƣơng 6: Ứng dụng chữ ký số (Digital Signature)…………......

45

6.1. Ứng dụng chung của chữ ký số………………..……………….

45

6.2. Chữ ký “mù”…………………………………..………………..

48

6.2.1. Ứng dụng trong bỏ phiếu điện tử…………..…………………

48


Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

3


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

6.2.2 Ứng dụng trong hệ thống tiền điện tử…………………………

49

6.3. Ứng dụng chữ ký “nhóm”: Thẻ thanh toán liên ngân hàng…….

50

6.4. Cách sử dụng chữ ký số…………..……………………..……...

50

Kết luận………..……………………..……………………..……….

53

Tài liệu tham khảo…………………..……………………..………..

54

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học


4


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

Lời Mở Đầu
Ngày nay, các ứng dụng Công nghệ thông tin ngày càng phổ biến rộng
rãi đã ảnh hưởng rất lớn đến diện mạo của đời sống, kinh tế, xã hội. Mọi công
việc hàng ngày của chúng ta đều có thể thực hiện được từ xa với sự hộ trợ của
máy tính và mạng internet (từ việc học tập, đi mua sắm,…). Tất cả những
thông tin liên quan đến những công việc này đều do máy tính quản lý và
truyền đi trên hệ thống mạng. Đối với những thông tin bình thường thì không
có ai chú ý đến, nhưng đối với những thông tin mang tính chất sống còn đối
với mỗi cá nhân (hay tổ chức) thì vấn đề bảo mật là hết sức quan trọng.
Trong thời đại mà thương mại điện tử đang lên ngôi, những bức thư
điện tử cũng không còn xa lạ và là công cụ không thể thiếu đối với mỗi con
người năng động, thì sự đảm bảo cho nội dung là hoàn toàn cần thiết. Hãy thử
tưởng tượng bạn đọc được trên một email thông tin rằng sản phẩm nổi tiếng A
đang bán giảm giá một nửa, hơn nữa khi mua sản phẩm A bạn còn được đọc
một năm báo C miễn phí. Thật là một cơ hội hiếm có nhưng làm sao có thể tin
tưởng được điều này? Nếu những email và bài viết kia có được chữ ký điện tử
của những người phát ngôn đáng tin cậy, ta có thể hoàn toàn yên tâm về nội
dung của chúng. Đó là đặc điểm nổi bật của chữ ký số.
Một vai trò quan trọng của chữ ký số (Digital Sinature) là khả năng bảo
mật. Chính vì lý do này mà em đã chọn đề tài “Tìm hiểu về chữ ký số
(Digital Signature) và ứng dụng”. Sau một thời gian tìm tòi, học hỏi cùng
với sự giúp đỡ tận tình của thầy, cô trong khoa đặc biệt là thầy Trần Tuấn
Vinh, em đã hoàn thành đề tài này. Trong quá trình tìm hiểu và nghiên cứu
em không tránh khỏi những thiếu sót. Vì vậy em kính mong nhận được sự
đóng góp của quý thầy cô cùng các bạn.

Sinh viên thực hiện đề tài
Đỗ Thị Xuân Thắm
Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

5


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

ĐẶT VẤN ĐỀ
Ngày nay, khi ứng dụng trên mạng máy tính ngày càng trở nên phổ
biến, thuận lợi và quan trọng thì yêu cầu về an toàn mạng, về an ninh dữ liệu
trên mạng ngày càng trở nên cấp bách và cần thiết. Nguồn tài nguyên trên
mạng rất dễ bị đánh cắp hoặc phá hỏng nếu không có một cơ chế bảo mật cho
chúng hoặc do chúng ta sử dụng cơ chế bảo mật quá lỏng lẻo, sơ hở. Thông
tin trên mạng đang truyền hoặc lưu trữ đều cần được bảo vệ, hoặc các thông
tin ấy phải được giữ bí mật, hoặc chúng phải cho phép người ta kiểm tra để
tin tưởng rằng chúng không bị sửa đổi so với dạng nguyên thủy của mình và
chúng đúng là của người nhận gửi nó cho ta.
Mạng máy tính có đặc điểm nổi bật là có rất nhiều người sử dụng,
nhiều người cùng khai thác một kho tài nguyên, đặc biệt là tài nguyên của
thông tin và các điểm có người sử dụng thường phân tán về mặt địa lý. Các
đặc điểm này thể hiện lợi ích to lớn của mạng thông tin máy tính đồng thời nó
cũng là điều kiện thuận lợi cho những người (hacker) muốn phá hoại an toàn
thông tin trên mạng máy tính.
Do đó cách tốt nhất để bảo mật thông tin là mã hóa thông tin trước khi
gửi đi. Mục tiêu cơ bản của mật mã là cho phép hai người, thường được đề
cập đến như Alice và Bob, liên lạc trên kênh không an toàn theo cách mà đối
thủ Orcar không thể hiểu được cái gì đang được nói. Kênh này có thể là
đường điện thoại hoặc máy tính. Thông tin mà Alice muốn gửi đến Bob sẽ

được gọi là “bản rõ” (plaintext), có thể là bất kỳ tài liệu nào có cấu trúc tùy ý.
Alice mã bản rõ bằng cách dùng khóa xác định trước, và gửi bản rõ thu được
trên kênh không an toàn. Orcar dù thu trộm được mã kênh song không thể
Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

6


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

hiểu được bản rõ là gì, nhưng Bob là người biết khóa mã có thể giải mã và
thiết lập bản rõ (văn bản).
Có hai loại khóa mật mã là khóa bí mật (private key) và khóa công khai
(public key). Trong mật mã bí mật hai người muốn trao đổi thông tin cho
nhau phải thỏa thuận chọn một cách bí mật khóa k. Từ k suy ra quy tắc mã
hóa ek và quy tắc giải mã dk. Trong hệ mật mã này dk hoặc trùng với ek hoặc
dễ dàng rút ra từ ek và tiết lộ ek sẽ làm cho hệ thống không an toàn. Độ an toàn
hệ mật mã chính là độ an toàn tính toán. Trong thực tế, một hệ mật mã là “an
toàn tính toán” nếu phương pháp tốt nhất để nó phá yêu cầu của một số lớn
không hợp lý thời gian tính toán, nghĩa là quá trình thực hiện cực kỳ phức tạp,
phức tạp đến mức ta coi là “không thể được”. Hệ mật khóa công khai đã đáp
ứng được những đòi hỏi đó. Ý tưởng nằm sau hệ mật khóa công khai là ở chỗ
nó có thể tìm ra một hệ mật trong đó không thể tính toán để xác định d k khi
biết ek.. Quy tắc mã ek có thể là công khai. Hàm mã hóa công khai ek phải dễ
dàng tính toán nhưng việc giải mã phải khó đối với bất kỳ người nào ngoài
người lập mã. Tính chất dễ tính toán và khó đảo ngược này thường được gọi
là tính chất một chiều. Muốn giải mã các thông báo nhận được một cách hiệu
quả ta cần có một cửa sập một chiều, điều này đảm bảo độ bí mật cao.
Mã hóa còn có đặc điểm là xác thực và chữ ký số. Xác thực có nhược
điểm là ở đây cả hai bên đều có chung một khóa nên không thể phân xử được

khi một trong hai người chối bỏ thông báo họ chối bỏ gửi cho người kia. Hơn
nữa trong mạng có nhiều người sử dụng, nếu một cặp khóa thỏa thuận như
vậy thì mỗi người phải lưu giữ n – 1 khóa bí mật. Khi n đủ lớn đó là một việc
phiền phức và phức tạp. Chính vì vậy mà chữ ký số ra đời và được sử dụng
nhiều hơn. Chữ ký số có nhiệm vụ giống chữ ký tay nghĩa là nó được dùng để
thực hiện chức năng xác nhận của một người gửi trên văn bản. Nó vừa mang
dấu vết không chối cãi được của người gửi, vừa gắn với từng bit của văn bản

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

7


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

mà nếu thay đổi dù chỉ một bit của văn bản thì chữ ký cũng không còn được
chấp nhận.
Chính vì những lý do trên mà em đã chọn và nghiên cứu đề tài “Tìm
hiều về chữ ký số (Digital Signature) và ứng dụng”. Trên cơ sở tìm hiểu và
nghiên cứu các lược đồ chữ ký, hàm băm và ứng dụng của chữ ký số trong
thực tế hiện nay.

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

8


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

CHƢƠNG 1

CƠ SỞ LÝ THUYẾT
1.1. Mật mã
Mật mã (cryptography) là một trong những mặt phức tạp nhất của quá
trình phát triển phần mềm mà bất kỳ nhà phát triển nào cũng sẽ sử dụng. Lý
thuyết kỹ thuật mật mã hiện đại cực kỳ khó hiểu và đòi hỏi một mức kiến thức
toán học mà tương đối ít người có được. May mắn là thư viện lớp .NET
Framework cung cấp các hiện thực dễ sử dụng cho hầu hết các kỹ thuật mật
mã thông dụng và hỗ trợ các giải thuật phổ biến nhất.
Gồm các vấn đề sau:
- Tạo số ngẫu nhiên
- Tạo và xác minh các mã băm mật mã và các mã băm có khóa.
- Sử dụng giải thuật đối xứng và không đối xứng để mã hóa và giải
mã dữ liệu.
Một số định nghĩa hay dùng:
- Encrypt (động từ, tạm dịch là mật hóa) là mã hóa thông tin theo
cách nào đó để mọi người không thể đọc được nó, trừ những ai có khóa.
- Decrypt (động từ, tạm dịch là giải mật hóa) là giải mã thông tin đã
được mật hóa.
- Key là chuỗi các bit dùng để mã hóa và giải mã thông tin.
- Plaintext là văn bản chưa được mã hóa hay đã được giải mã.
- Ciphertext là văn bản đã được mã hóa.
1.2. Tạo số ngẫu nhiên

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

9


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng


Bạn cần tạo một số ngẫu nhiên dùng cho các ứng dụng mật mã và bảo
mật.
Sử dụng một bộ tạo số ngẫu nhiên mật mã (cryptographic random number
generator), Ví dụ (trong C#):
System.Security.Cryptography.RNGCryptoServiceProvider.
Lớp System.Random là một bộ tạo số giả ngẫu nhiên, nó sử dụng một giải
thuật toán học để mô phỏng việc tạo số ngẫu nhiên.
1.3. Tính mã băm của password
Bạn cần lưu trữ password của người dùng một cách an toàn để bạn có
thể sử dụng nó để xác thực người dùng đó trong tương lai.
Đừng lưu trữ password của người dùng ở dạng plaintext vì đây là một
nguy cơ bảo mật lớn. Thay vào đó, hãy tạo và lưu trữ một mã băm của
password bằng một lớp giải thuật băm dẫn xuất từ lớp (trong C#)
System.Security.Cryptography.HashAlgorithm. Khi xác thực, tạo mã băm của
password và so sánh nó với mã băm đã được lưu trữ.
Các giải thuật băm là các hàm mật mã một chiều, nhận plaintext có
chiều dài thay đổi và tạo một giá trị số có kích thước cố định. Chúng là một
chiều vì gần như không thể tìm lại plaintext gốc từ mã băm. Các giải thuật
băm là tất định (deterministic); áp dụng cùng giải thuật băm cho một mẩu
plaintext luôn tạo ra cùng mã băm.

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

10


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

CHƢƠNG 2
CHỮ KÝ SỐ (DIGITAL SIGNATURE)

2.1. Lịch sử phát triển của chữ ký số
Từ thời xa xưa con người đã sử dụng các hợp đồng điện tử với việc sử
dụng mã Morse. Vào năm 1889, tòa án tối cao Hoa Kỳ đã phê chuẩn tính hiệu
lực của chữ ký điện tử hay còn gọi chữ ký số. Trong những năm gần đây chữ
ký số mới được áp dụng và sử dụng rộng rãi trong các lĩnh vực. Hiện nay, chữ
ký số có thể bao hàm các cam kết gửi bằng email, nhập các số định dạng cá
nhân (PIN) vào các máy ATM, ký bút điện tử với thiết bị màn hình cảm ứng
tại quầy tính tiền, chấp nhận tài khoản người dùng khi cài đặt phần mềm máy
tính,…
2.2. Giới thiệu chung về chữ ký số
Chữ ký số (digital signature) là gì?
Trước đây, nhiều người nhầm tưởng chữ ký số là chữ ký của người
dùng ký trên giấy sau đó được scan thành các hình ảnh đính kèm vào bức thư,
họ cho rằng đó là chữ ký số. Cũng có người cho rằng chữ ký số là các chữ ký
đính kèm, các thông tin nằm dưới mỗi bức thư điện tử được gửi đi luôn được
tự động thêm vào khi tạo email bằng các chương trình kiểm tra email như
Outlook hoặc các Webmail. Một số ý kiến khác có cái nhìn tiến bộ hơn thì
cho rằng chữ chữ ký số được ký trên các thiết bị cảm ứng, sau đó chuyển
những gì người viết trên thiết bị cảm ứng thành các file hình ảnh…Đây là
cách hiểu không chính xác về chữ ký số. Vậy chữ ký số là gì?

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

11


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

Về căn bản chữ ký số cũng giống chữ ký viết tay cùng có nhiệm vụ
chung là ký nhưng có sự khác nhau cơ bản giữa chúng:

Thứ nhất, về việc ký tài liệu: Với chữ ký tay thì chữ ký là bộ phận vật lý
của tài liệu được ký. Tuy nhiên chữ ký số không gắn một cách vật lý với
thông báo được ký mà được gắn với một thông báo logic, do đó thuật toán
được dùng để “trói” chữ ký với thông báo theo một cách nào đó.
Thứ hai, về việc kiểm tra: Chữ ký tay được kiểm tra bằng cách so sánh
nó với những cái khác, những chữ ký đã xác thực. Ví dụ, một người ký trên
một tấm séc mua hàng, người bán phải so sánh chữ ký trên tấm séc với chữ ký
nằm sau trên thẻ tín dụng để kiểm tra. Tất nhiên, phương pháp này không an
toàn lắm vì nó tương đối dễ đánh lừa bởi chữ ký của người khác. Khác với
chữ ký tay, chữ ký số có thể kiểm tra bằng các thuật toán kiểm tra công khai
đã biết. Vì vậy, bất kỳ người nào đó đều có thể kiểm tra chữ ký số. Và việc sử
dụng lược đồ chữ ký an toàn sẽ ngăn chặn khả năng đánh lừa.
Điều khác nhau cơ bản giữa chữ ký “tay” và “chữ ký số” là “bản sao”
thông báo số được ký là đồng nhất với bản gốc. Trong khi đó, bản sao chép
tài liệu giấy đã ký thường là khác với bản gốc. Điều này nghĩa là phải ngăn
chặn một thông báo đã ký số bị sử dụng lại. Ví dụ, nếu Bob ký thông báo số
cho quyền Alice rút $500 từ tài khoản ngân hàng của mình, anh ta chỉ muốn
Alice làm việc đó một lần. Do đó, thông báo tự nó phải chứa thông tin để
ngăn chặn Alice làm việc đó nhiều lần.
Vậy chữ ký số (Digital Signature) là một dạng của chữ ký điện tử, là
đoạn dữ liệu gắn kèm với văn bản gốc để chứng thực tác giả của văn bản và
giúp người nhận kiểm tra được tính toàn vẹn của nội dung văn bản gốc.
Ví dụ: Chữ ký số sử dụng mật mã có khóa công khai; kết hợp chữ ký số
và mật mã; chữ ký số sử dụng thuật toán RSA; chữ ký số tách biệt đoạn tin;

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

12



Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

chữ ký số dùng mật mã đối xứng; chữ ký số và xác thực sử dụng hàm một
chiều; chữ ký có trọng tài.
Lược đồ chữ ký số gồm hai thành phần: Một thuật toán ký và một thuật
toán kiểm tra. Bob có thể ký thông báo x nhờ thuật toán ký (bí mật) Sig. Chữ
ký thu được sig (x) sau đó có thể được kiểm tra nhờ thuật toán kiểm tra công
khai Ver. Khi cặp (x, y) thuật toán kiểm tra sẽ trả lời “đúng” hoặc “sai” phụ
thuộc vào việc chữ ký có đích thực hay không?
2.3. Định nghĩa lược đồ chữ ký số
Định nghĩa: Lược đồ chữ ký số là bộ năm phần tử (P, A, K, S, V) thỏa
mãn các điều kiện sau:
1. P: Là một hữu hạn các thông báo.
2. A: Tập hữu hạn các chữ ký có thể.
3. K: Tập hữu hạn các khóa, không gian khóa.
4. Với mỗi k  K,  sigk  S và verk V
Mỗi sigk: P A, verk: P * A true, false là những hàm sao cho mỗi bức
điện x  P và mỗi chữ ký y  A thỏa mãn:
Ver(x,y) =

 true,

 false,

khi
khi

y  sig x 
.
y  sig x 


* Yêu cầu: Với mỗi khóa k  K, các hàm sigk và verk là các hàm thời gian đa
thức. Với Verk là hàm công khai, sigk là hàm bí mật để tránh trường hợp Orcar
có thể giả mạo chữ ký để thông báo x. Với mỗi x chỉ duy nhất Bob tính được
chữ ký sao cho: Ver(x, y) = True.
Lược đồ chữ ký phải an toàn. Bởi vì Orcar có thể kiểm tra tất cả các
khả năng của chữ ký y nhờ thuật toán kiểm tra công khai Ver cho tới khi đạt
được yêu cầu tức là tìm được chữ ký đúng. Do đó, nếu có đủ thời gian cần
thiết Orcar có thể giả mạo được chữ ký của Bob. Vì vậy mục đích của chúng
ta là tìm lược đồ chữ ký sao cho Orcar không đủ thời gian để thử như thế.
Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

13


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

2.4. Một vài lược đồ chữ ký số
2.4.1. Lược đồ chữ ký RSA
Thuật toán RSA được dùng để tạo chữ ký số cho văn bản. Thuật toán
RSA sử dụng hai khóa khóa công khai (public key) và khóa bí mật (private
key). Mỗi khóa là những số cố định trong quá trình mã hóa và giải mã. Khóa
công khai được công bố cho mọi người dùng và được dùng để mã hóa. Nhưng
thông tin được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng
khóa bí mật tương ứng. Nói cách khác mọi người đều có thể mã hóa nhưng
chỉ có người biết khóa cá nhân mới giải mã được.
Giả sử Alice muốn gửi cho Bob một văn bản có chữ ký của mình để
làm việc này Alice tạo ra một giá trị băm (hash value) của văn bản cần ký và
tính giá trị d mod n của nó (giống như khi Alice thực hiện giải mã). Giá trị
cuối cùng chính là chữ ký số của văn bản đang xét. Khi Bob nhận được văn

bản cùng với chữ ký số, anh ta tính giá trị mũ e mod n của chữ ký đồng thời
với việc tính giá trị băm của văn bản. Nếu giá trị này như nhau thì Bob biết
rằng người tạo ra chữ ký biết khóa bí mật của Alice và văn bản không bị thay
đổi sau khi ký.
Lược đồ chữ ký RSA được định nghĩa như sau:
 Tạo khóa:
Cho n= p.q; với q, p là các số nguyên tố lớn khác nhau, (n) = (p - 1)(q – 1).
Cho P = A = Zn và định nghĩa: K = {(n, p, q, a, b)}: n = p.q; p, q là các số
nguyên tố;
Các giá trị n và b là công khai; các giá trị p, q, a là bí mật.
 Tạo chữ ký: Với K = (n, p, q, a, b) xác định:
Sigk(x) = xa mod n
 Kiểm tra chữ ký: Verk(x, y) = true  x  yb mod n; x, y Zn

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

14


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

Giả sử Bob muốn ký thông báo x, anh ta tính chữ ký y bằng cách:
y = sigk(x) = xa B mod n (aB là khóa công khai của Bob).
Nếu đúng, Alice công nhận là chữ ký trên x của Bob. Ngược lại, Alice sẽ
coi x không phải của Bob gửi cho mình (chữ ký tin cậy).
Người ta có thể giả mạo chữ ký của Bob như sau: chọn y, sau đó tính
x = verk(y), khi đó y = sigk(x). Một cách để khắc phục khó khăn này là việc
yêu cầu x phải có nghĩa. Do đó chữ ký giả mạo nói trên sẽ thành công với các
xác suất rất nhỏ.
Ta có thể kết hợp chữ ký với mã hóa sẽ làm cho độ an toàn của chữ ký

tăng thêm.
Giả sử rằng, Alice sẽ tính chữ ký của cô ta là y = sigAlice(x), và sau mã
hóa cả x và y bằng cách sử dụng mật mã công khai e Bob của Bob. Khi đó cô ta
nhận được z = eBob(x, y). Bản mã z sẽ được truyền tới Bob. Khi nhận được z,
việc trước tiên là anh ta giải mã bằng hàm d Bob để nhận được (x, y). Sau đó
anh ta sử dụng hàm kiểm tra khóa công khai của Alice để kiểm tra xem liệu
verAlice(x, y) = true?
Nếu Alice mã hóa x trước đó rồi sau mới ký lên bảng mã hóa thì sao?
Khi đó Alice tính:
y = sigAlice(eBob(x))
Alice sẽ truyền cặp (z, y) cho Bob. Bob sẽ giải mã z, nhận được x và
kiểm tra chữ ký y trên bảng bằng cách sử dụng verAlice. Một vấn đề tiềm ẩn
trong biện pháp này là nếu Orcar có được cặp (z, y) kiểu này, anh ta có thể
thay thế chữ ký y của Alice bằng chữ ký của anh ta: y’ = sigOrcar(eBob(x)).
Chú ý rằng Orcar có thể ký bản mã ebob(x) ngay cả khi anh ta không
biết rõ x.
Khi đó, nếu Orcar truyền (z, y’) tới Bob, chữ ký của Orcar sẽ được
kiểm tra thử vì Bob sử dụng verOrcar, và Bob có thể suy ra rằng bản rõ x xuất
Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

15


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

phát từ Orcar. Điều này cũng làm cho người sử dụng hiểu rằng nên ký trước
rồi sau đó mới tiến hành mã hóa.
Ví dụ: Giả sử Bob dùng lược đồ chữ ký số RSA với n= 247, (p = 13, q
= 19); (n) = 12.18 = 216. Khóa công khai của Bob là b = 7
 a = 7-1mod 216 = 31.

Bob công khai (n, b) = (247, 7).
Bob ký lên thông báo x = 100 với chữ ký:
y = xa mod n = 10031 mod 247 = 74.
Bob gửi cặp (x, y) = (100, 74) cho Alice. Alice kiểm tra bằng cách sử dụng
khóa công khai của Bob như sau:
b

7

x = y mod n = 74 mod 247 = 100 = x.

 Alice chấp nhận y = 74 là chữ ký tin cậy. (Xem trong [8]).
2.4.2. Lược đồ ElGamal
Lược đồ chữ ký số ElGamal được giới thiệu năm 1985 và được Viện
tiêu chuẩn và Công nghệ quốc gia Mỹ sửa đổi thành chuẩn chữ ký số. Lược
đồ ElGamal không tất định cũng giống như hệ thống mã hóa công khai
ElGamal. Điều này có nghĩa là có nhiều chữ ký hợp lệ cho một thông báo bất
kỳ. Thuật toán kiểm tra có khả năng chấp nhận bất kỳ chữ ký hợp lệ nào khi
xác minh.
Lược đồ chữ ký số ElGamal được định nghĩa như sau:
 Tạo khóa:
Cho p là số nguyên tố sai cho bài toán là logarit rời rạc trong Zp là khó
và giả sử  Z *p là phần tử nguyên thủy.
Cho P = Z *p , A = Z *p  Zp-1 và định nghĩa:
K = {(p, a, , ):  = a mod p }.
Các giá trị p, ,  là công khai, a là bí mật.

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

16



Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

 Tạo chữ ký
Với K = (p, a, , ) và với số ngẫu nhiên k Z *p 1 , định nghĩa: sigk(, ),
Trong đó:
 = k mod p và  = (x - a) k -1mod(p - 1).
 Kiểm tra chữ ký số:
Với x,   Z *p và  Zp-1 ta định nghĩa:
Ver (x, , ) = True  .   x mod p.
Chứng minh:
Nếu chữ ký được thiết lập đúng kiểm tra sẽ thành công vì:
   a. r. mod p
 x mod p ( v × a + r  x mod(p - 1)).
Bob tính chữ ký bằng cách dùng cả giá trị bí mật a (là một phần tử của
khóa) lẫn số ngẫu nhiên bí mật k (dùng ký hiệu trên x). Việc kiểm tra có thể
thực hiện duy nhất bằng thông tin công khai.
Ví dụ: Giả sử p = 467,  = 2, a = 127
Khi đó:  = a mod p = 2127mod 467 = 132
Giả sử Bob có thông báo x = 100 và anh ta chọn ngẫu nhiên k = 213 vì
(213, 466) =1 và 213-1 mod 466 = 431
Bob ký trên x như sau:
 = k mod p = 2213mod 467 = 29
và  = (x - a)k-1 mod(p -1) = (100 – 127. 29).431 mod 466 = 51.
Chữ ký của Bob trên x =100 là (29, 51).
Bất kỳ người nào cũng có thể kiểm tra chữ ký này bằng cách:
13229 . 2951  189 mod 467
2100  189 mod 467
Do đó chữ ký tin cậy. (Xem trong [8]).


Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

17


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

Bây giờ ta xét độ an toàn của lược đồ chữ ký ElGamal.
Giả sử Orcar thử giả mạo chữ ký trên thông báo x cho trước mà không
biết a, Nếu Orcar chọn giá trị  và thử tìm  tương ứng, anh ta phải tính
logarit rời rạc của logx -. Mặt khác, nếu anh ta chọn  trước và sau đó thử
tìm  thì anh ta phải giải phương trình    x mod p, trong đó  là ẩn. Bài
toán này chưa có lời giải, tuy nhiên dường như nó liên quan đến bài toán đã
nghiên cứu. Vẫn còn có khả năng là tìm  và  đồng thời để (, ) là chữ ký.
Hiện thời không ai tìm được cách giải song cũng không ai khẳng định được
nó không có lời giải.
Nếu Orcar chọn  và , sau đó thử giải để tìm x, anh ta sẽ phải tính bài
toán logarit rời rạc, tức phải tính log  . Vì thế Orcar không thể ký một
thông điệp ngẫu nhiên bằng cách này. Tuy nhiên có một cách để Orcar ký lên
thông điệp ngẫu nhiên bằng việc chọn , , x đồng thời.
Giả thiết i và j là các số nguyên 0  i  p – 2; 0  j  p – 2 và (j, p - 1) =1.
Khi đó thực hiện các phép tính:
 = i j mod p
 = -.j-1mod(p - 1)
x = - i.j-1mod(p - 1) = i. mod(p - 1).
Trong đó j-1 được tính theo module (p - 1). Ta thấy rằng (, ) là chữ ký hợp lệ
của x. Điều này được chứng minh qua việc kiểm tra:
   -(i j )-
  -i.j


1



i 1

j

mod p

-

1

 -.i.j mod p
 x mod p.
Ví dụ: p = 467;  = 2;  = 132.
Giả sử Orcar chọn i = 99; j = 179, khi đó j-1 mod(p -1) = 151. Anh ta tính:

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

18


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

 = 299 132179mod 467 = 117
 = - 177. 151 mod 466 = 41
x = 99. 41 mod 466 = 331

Và (117, 41 ) là chữ ký trên x = 331.
Kiểm tra:
132117 11741  303mod 467
và 2331  303 mod 467
Do đó chữ ký đó là hợp lệ. (Xem trong [6]).
Orcar có thể giả mạo chữ ký theo kiểu khác là bắt đầu thông báo x đã được
Bob ký. Giả sử (, ) là chữ ký hợp lệ trên x. Khi đó Orcar có khả năng ký lên
nhiều thông báo khác nhau. Giả sử i, j, h là các số nguyên 0  h; i, j  p – 2 và
(h - j, p - 1) = 1. Thực hiện các phép tính:
 = h i j mod p
 = (h - j)-1mod(p - 1)
x’ = (hx + i)(h - j)-1 mod(p - 1)
Trong đó (h - j)-1được tính theo module (p - 1).
Kiểm tra     x mod p  (, ) là chữ ký hợp lệ của x’.
'

Cả hai phương pháp đều tạo các chữ ký giả mạo hợp lệ song không
xuất hiện khả năng đối phương giả mạo chữ ký trên thông điệp có lựa chọn
của chính họ mà không phải bài toán logarit rời rạc. Vì thế không có gì nguy
hiểm về độ an toàn của lược đồ ElGamal. (Xem trong [8]).

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

19


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

CHƢƠNG 3
HÀM BĂM (HASH)

3.1. Giới thiệu
Đối với xác thực và chữ ký số ta thấy rằng các thuật toán thường nhận
đầu vào là một dòng bit có độ dài rất ngắn (64, 128, 160) và tốc độ thực hiện
chậm. Mặt khác, các thông báo cần ký thường có độ dài khác nhau và trong
nhiều trường hợp chúng có độ dài lớn cỡ vài Kilobyte hoặc Megabyte. Do
vậy, muốn ký một chữ ký ngắn trên một thông báo dài ta cần phải cắt thông
báo ra thành nhiều đoạn có độ dài hữu hạn và cố định rồi tiến hành ký độc lập
từng đoạn đó và gửi từng đoạn đó đi. Khi đó lại xuất hiện nhiều vấn đề như:
- Tốc độ thực hiện rất chậm vì phải ký trên nhiều đoạn.
- Dễ xảy ra trường hợp không sắp xếp được thông báo theo đúng trật tự
ban đầu.
- Có thể bị mất các đoạn riêng biệt trong quá trình truyền tin.
Để giải quyết vấn đề này ta dùng hàm băm (Hash). Hàm Hash chấp
nhận một thông báo có độ dài bất kỳ làm đầu vào, hàm hash sẽ biến đổi thông
báo thành một thông báo rút gọn, sau đó sẽ dùng lược đồ chữ ký để mô tả
thông báo rút gọn.
Ta có mô hình chung như sau:
Thông báo

x

độ dài tùy ý

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

20


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng



Thông báo rút gọn

z = h(x)

160 bit


Chữ ký

y = sigK(x)

320 bit

Nếu không cần bí mật x, ta sẽ gửi cặp (x, y) cho người nhận. Nếu cần
giữ bí mật x thì ta sẽ mã hóa thông báo x thành x’ và gửi cặp (x’, y).
3.2. Định nghĩa
- Hàm Hash là một hàm tính toán có hiệu quả khi ánh xạ các dòng nhị
phân có độ dài tùy ý thành dòng nhị phân có độ dài cố định nào đó.
- Hàm hash yếu: Hàm hash được gọi là yếu nếu cho một thông báo x
thì về mặt tính toán không tìm ra được thông báo x’ khác với x sao cho:
h(x’) = h(x)
- Hàm hash mạnh: Hàm hash được gọi là mạnh nếu về mặt tính toán
không tìm ra được thông báo x và x’ sao cho:
x’  x và h(x’) = h(x)
- Hàm hash có tính chất một chiều: Hàm hash có tính chất một chiều
nếu cho trước thông báo rút gọn z thì về mặt tính toán không tìm ra được
thông báo x sao cho h(x) = z.
- Hàm hash yếu làm cho chữ ký số trở nên tin cậy giống như việc ký
trên toàn thông báo.

- Hàm hash mạnh có tác dụng chống lại kẻ giả mạo tạo ra hai bản thông
báo có nội dung khác nhau, sau đó thu nhận chữ ký hợp pháp cho mỗi thông
báo dễ được xác nhận rồi lấy nó giả mạo làm chữ ký của thông báo thứ hai.
3.3. Một số hàm Hash sử dụng trong chữ ký số

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

21


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

3.3.1. Các hàm Hash đơn giản
Tất cả các hàm Hash đều được thực hiện theo nguyên tắc chung là: Đầu
vào được biểu diễn dạng một dãy các khối có độ dài n bit. Các khối bit này
được xử lý theo cùng một kiểu và lặp đi lặp lại để cuối cùng cho đầu ra có số
bit cố định.
Hàm Hash đơn giản nhất là thực hiện phép XOR từng bit một của mỗi
khối. Nó được biểu diễn như sau:
Ci = b1i  b2i …bmi
Trong đó:
Ci : Là bit thứ i của mã Hash.
m: Là số các khối đầu vào.
bji: Là bit thứ i trong khối thứ j.
: Là phép cộng module 2.
Sơ đồ hàm Hash sử dụng phép XOR:
Khối 1:

b11


b12

…

b1n

Khối 2:

b21

b22

…

b2n

…

…

…

…

…

Khối m:

bm1


bm2

…

bmn

Mã Hash:

C1

C2

…

Cn

Ci là bit kiểm tra tính chẵn lẻ cho vị trí thứ i khi ta chia tệp dữ liệu thành từng
khối, mỗi khối có n vị trí. Nó có tác dụng như kiểm tra tổng hợp tính toàn vẹn
của dữ liệu.
Khi mã hóa một thông điệp dài thì sử dụng mode CBC (The Cipher
Block Chaining), thực hiện như sau:
Giả sử thông báo X được phân thành các khối 64 bit liên tiếp:
X = X1X2 …XN
Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

22


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng


Khi đó mã Hash C là:
C = XNH = X1 X2 … Xn.
Sau đó mã hóa toàn bộ thông báo nối với mã Hash theo mode CBC để sản
sinh ra bản mã: Y1Y2 …YN+1
3.3.2. Hàm Hash MD5
Năm 1990, Ronald Rivest đã đề xuất hàm Hash MD4, sau đó một phiên
bản mạnh hơn MD4 đã ra đời vào năm 1991 đó là MD5. Cùng thời điểm đó
SHS (Secure Hash Standard) phức tạp hơn ra đời. Nhưng MD5 và SHS đều
dựa trên nền tảng của MD4.
Ở đây ta đi sâu vào đặc điểm nguyên tắc hoạt động của MD5. Và tìm hiểu
ứng dụng của nó trong thực tế hiện nay, MD5 có thể coi là phương pháp mã
hóa cực nhanh dùng trong chữ ký số.
MD5 (Message- Digest algorithm 5) là một hàm băm để mã hóa với các
giá trị băm là 128 bit. Được xem là một chuẩn trên Internet, MD5 được sử
dụng rộng dãi trong các chương trình an ninh mạng, và cũng thường được
kiểm tra tính nguyên vẹn của tập tin.
MD5 có hai ứng dụng quan trọng:
1/ MD5 được sử dụng rộng rãi trong thế giới phần mềm để đảm bảo
rằng tập tin tải về không bị hỏng. Các nhà phát triển ứng dụng thường dùng
MD5 trong việc cho phép tải về. Khi chúng ta tải file về thì file chúng ta vừa
tải sẽ có một tín hiệu md, nếu tín hiệu này khớp với tín hiệu các nhà phát triển
ứng dụng đã “xuất bản”. Thì đồng ý tải và không có vấn đề gì. Nếu hai tín
hiệu md này khác nhau, có thể file tải về có virus hay một dạng tương tự.
2/ MD5 dùng để mã hóa mật khẩu. Mục đích của việc mã hóa này là biến đổi
một chuỗi mật khẩu thành một đoạn mã khác, sao cho đoạn mã đó không thể

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

23



Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

nào lần trở lại mật khẩu. Có nghĩa là giải mã là không thể hoặc làm mất một
khoảng thời gian vô tận (đủ làm nản lòng các hacker).
Tính chất
- Có thể áp dụng trên dữ liệu có kích thước bất kỳ.
- Kết quả hàm băm là một chuỗi n-bit (n là cố định).
- Hàm băm là hàm một chiều.
- Hàm băm an toàn với hiện tượng “đụng độ”.
Thuật toán thực hiện MD5:
MD5 biến đổi một thông điệp có chiều dài bất kì thành một khối có kích
thước cố định 128 bits. Thông điệp đưa ra sẽ bị cắt thành các khối 512 bits.
Các bước thực hiện
Bước

Mô tả

1

A = 0x67452301
B = 0xefcdab89
C = 0x89badcfe
D = 0x10325476

2

For i: = 1 to N/16 do

3


For j: = 0 to 15 do X[j]: = M[16i + j]

4

AA: = A; BB: = B; CC: = C; DD: = D

5

Round 1

6

Round 2

7

Round 3

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

24


Đề tài: Tìm hiểu về chữ ký số (Digital Signature) và ứng dụng

8

AA: = A +AA; BB: = B + BB; CC: = C + CC;
DD: = D + Dd mod 2332


Giải thích thuật toán thực hiện MD5:
Giả sử x là một thông báo cần Hash. Đầu tiên bổ sung số nối vào x, sau
đó là dãy các số 0 sao cho độ dài thu được là đồng dư với 448 mod 512. Cuối
cùng, gắn thêm 64 bit nữa vào để được thông báo mở rộng. Đây là 64 bit biểu
diễn nhị phân độ dài nguyên thủy của x. Kết quả ta được thông báo mở rộng
M có độ dài chia hết 512. Vì vậy khi cắt thành những từ có độ dài 32 bit ta sẽ
được số N chia hết cho 16.
Biểu diễn M dưới dạng dãy liên tiếp N các từ có độ dài 32 bit:
M = M[0] M[1] …M[N – 1]

Đỗ Thị Xuân Thắm K31 B – Khóa luận tốt nghiệp – Chuyên ngành Tin học

25