BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
------------------------------------------

LUẬN VĂN THẠC SĨ KHOA HỌC

NGHIÊN CỨU CÁC PHƯƠNG PHÁP THẨM ĐỊNH XÁC THỰC CHỮ
KÝ VIẾT TAY ỨNG DỤNG TRONG THƯƠNG MẠI ĐIỆN TỬ
NGÀNH: CÔNG NGHỆ THÔNG TIN
NGUYỄN ANH TÀI

HÀ NỘI 2006

1


LỜI CAM ĐOAN

Tôi tên là : Nguyễn Anh Tài
Học viên lớp Cao học Công nghệ thông tin 2004
Tôi đã làm đồ án tốt nghiệp cao học CNTT với tên đề tài: Nghiên cứu các
phương pháp thẩm định xác thực chữ ký viết tay ứng dụng trong thương
mại điện tử, do PGS,TS Nguyễn Thị Hồng Lan hướng dẫn.
Tơi xin cam đoan nội dung trong đồ án tốt nghiệp này là do tơi tìm hiểu,
nghiên cứu và thực hiện. Nếu sai tơi hoàn toàn chịu trách nhiệm trước trường và
pháp luật
Hà Nội, ngày

tháng

năm 2006

Người cam đoan

Nguyễn Anh Tài

2


M ỤC L ỤC
LỜI CAM ĐOAN .............................................................................................2

23T

23T

Mục lục ....................................................................................................3

23T

Danh mục các ký hiệu, các chữ viêt tắt..................................................... 6

23T

Danh mục các bảng .................................................................................. 7

23T

Danh mục các hình vẽ, đồ thị ................................................................... 8

23T


Mở đầu ................................................................................................... 10

23T

CHƯƠNG I: TỔNG QUAN SINH TRẮC HỌC .......................................... 13

23T

23T

1.1 Khái niệm sinh trắc học .................................................................... 13

23T

2 3T

1.2 Hệ bảo mật sinh trắc học .................................................................. 13

23T

23 T

1.3 Chữ ký sinh trắc học ......................................................................... 14

23T

2 3T

1.4 Các khó khăn khi thực hiện ............................................................... 14


23T

23T

1.5 Vấn đề bảo mật bằng phương pháp sinh trắc học dựa trên chữ ký viết

23T

tay ................................................................................................................. 15
23 T

CHƯƠNG II: NGHIÊN CỨU, TÌM HIỂU PHƯƠNG PHÁP THẨM ĐỊNH

23T

CHỮ KÝ VIẾT TAY BẰNG PHƯƠNG PHÁP SINH TRẮC HỌC ............ 16
23T

2.1 Hệ thống mã hóa bảo mật sinh trắc học BioPKI ............................... 16

23T

23 T

2.2 Giai đoạn đối sánh mẫu .................................................................... 17

23T

23T


2.2.1 Đặc điểm của phương pháp DTW .............................................. 17

23T

23T

2.3 Kỹ thuật làm méo mới EPW ............................................................. 20

23T

2 3T

2.3.3 Làm méo đoan. ........................................................................... 27

23T

23T

2.3.4 Kiểm chứng bằng thực nghiệm. .................................................. 29

23T

23T

2.3.5 Cơ sở dữ liệu. ............................................................................. 29

23T

23T


2.3.6 Thực hành với các kết quả. ......................................................... 30

23T

23T

3


2.3.7 Kết luận ...................................................................................... 34

23T

23 T

2.4 Mã hóa các đặc trưng sinh trắc học ................................................... 34

23T

23 T

2.5 Tạo khóa riêng .................................................................................. 36

23T

23 T

2.6 Tính hiệu quả của hệ thống ............................................................... 37


23T

23T

CHƯƠNG 3: NGHIÊN CỨU, TÌM HIỂU PHƯƠNG PHÁP THẨM ĐỊNH

23T

CHỮ KÝ VIẾT TAY BẰNG MƠ HÌNH MARKOV ẨN ............................. 38
23T

3.1 Giới thiệu mơ hình MARKOV ẩn cho thẩm định chữ ký viết tay ..... 38

23T

23 T

3.1.1 Mơ hình HMM rời rạc và các tham số của mơ hình .................... 39

23T

23 T

3.1.2 Quá trình Markov trạng thái mở rộng ......................................... 39

23T

23 T

3.1.3 Các mơ hình Markov ẩn mở rộng từ các quá trình Markov trạng


23T

thái rời rạc ........................................................................................... 41
23T

3.1.4 Ba bài toán HMM cơ sở ............................................................. 43

23T

23T

3.1.5 Lời giải cho bài toán đánh giá thuật toán chuyển tiếp (Forwarding

23T

Algorithm) ........................................................................................... 44
23T

3.1.6 Lời giải cho bài toán giải mã- thuật toán Viterbi (Viterbi

23T

Algorithm) ................................................................................................. 46
23T

3.1.7 Lời giải cho bài toán huấn lyuện- thuật tốn Baum- Welch (Baum-

23T


Welch) ................................................................................................. 48
23T

3.2 Tìm hiểu hệ thống xác thực chữ ký viết tay off-line sử dụng mơ hình

23T

Markov ẩn. .............................................................................................. 51
23 T

3.2.1 Giai đoạn tiền xử lý .................................................................... 52

23T

23T

3.2.2 Mơ hình hóa chữ ký sử dụng HMM. ........................................... 65

23T

23T

3.2.3 Xử lý học. ................................................................................... 65

23T

23T

3.2.4 Quyết định .................................................................................. 68


23T

23T

4


3.3 Tìm hiểu hệ thống xác thực chữ ký viết tay on-line sử dụng mơ hình

23T

Markov ẩn ............................................................................................... 69
23 T

3.3.1 Mô đun thu nhận chữ ký trực tuyến. ........................................... 69

23T

23T

3.3.2 Cơ sở dữ liệu chữ ký trực tuyến .................................................. 69

23T

23 T

3.3.3 Tiền xử lý chữ ký ....................................................................... 69

23T


23 T

3.3.4 Mô hình huấn luyện. ................................................................... 71

23T

23 T

3.3.5 Phát triển mơ hình. ..................................................................... 73

23T

23 T

3.3.6 Kiểm chứng kết quả [Juan J, I gazar] .......................................... 73

23T

23T

CHƯƠNG 4: CHƯƠNG TRÌNH KIỂM THỬ ................................................. 76

23T

2 3T

4.1 Giới thiệu chương trình kiểm thử ...................................................... 76

23T


23T

4.2 Giới thiệu các FORM ........................................................................ 76

23T

23 T

4.3 Chi tiết các form ............................................................................... 77

23T

23T

4.3.1 Thông tin người dùng (Form 1) .................................................. 77

23T

23T

4.3.2 Thêm người dùng (Form 2) ........................................................ 78

23T

23 T

4.3.3 Cập nhật thông tin người dùng (Form 3) .................................... 79

23T


23T

4.3.4 Thẩm định chữ ký (Form 4) ........................................................ 80

23T

23 T

4.3.5 Hiển thị kết quả thẩm định chữ ký (Form 5) ............................... 81

23T

23 T

4.4 Chi tiết các thành phần trên form ...................................................... 82

23T

23 T

4.5 Cơ sở dữ liệu ..................................................................................... 90

23T

23T

23T

23T


4.6 Các thí nghiệm ................................................................................. 91
KẾT LUẬN ...................................................................................................... 92
23T

TÀI LIỆU THAM KHẢO ................................................................................ 94

23T

23T

5


DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TĂT
Chữ viết tắt
Bio
BioPKI

Tiếng Anh
Biometric
Biometric Public Key
Infrastructure

DTW
EPW

Dynamic time warp
Extreme point warp

EPS

MHM
PKI

Extreme point
Hidden Markov Model
Public Key Infrastructure

FAR
FRR

False Accept Rate
False Reject Rate

6

Tiếng việt
Sinh trắc học
Hệ thống mã hóa
cơng khai sinh trắc
học
Làm méo động
Làm méo các điểm
cực
Điểm cực
Mơ hình Markov ẩn
Cơ sở hạ tầng khóa
cơng khai
Tỷ lệ chấp nhận sai
Tỷ lệ loại bỏ sai



DANH MỤC CÁC BẢNG

23TU

23TU

23TU

23TU

23TU

23TU

23TU

23TU

23TU

23TU

23TU

23TU

23TU

23TU


Bảng 2.1. Ảnh hưởng của hệ số bỏ qua ..................................................... 31
U23 T

Bảng 2.2 Tốc độ lỗi với DTW và EPW ...................................................... 32
U23 T

Bảng 3.1 Thể hiên FAR ............................................................................. 63
U23T

Bảng 3.2 Thể hiên FRR .............................................................................. 64
U2 3T

Bảng 3.3 Kết quả ....................................................................................... 74
U23 T

Bảng 3.4 Kết quả phương pháp tiền xử lý .................................................. 75
U23 T

Bảng 4.1 Các thành phần trên form thông tin người dùng .......................... 83
U23 T

Bảng 4.2 Phím tắt trên form thơng tin người dùng ..................................... 83
U 23T

Bảng 4.3 Các thành phần trên form thêm người dùng ................................ 85
U23 T

Bảng 4.4 Các phím tắt trên form thêm người dùng ..................................... 86
U23 T


Bảng 4.5 Các phím tắt trên form cập nhật thông tin người dùng ................ 88
U23T

Bảng 4.6 Các phím tắt trên form cập nhật thơng tin người dùng ................ 88
U23T

Bảng 4.7 Các thành phần trên form thẩm định chữ ký người dùng ............. 90
U23 T

Bảng 4.8 Các phím tắt form thẩm định chữ ký người dùng ........................ 90
U23T

7


DANH MỤC CÁC HÌNH VẼ ĐỒ THỊ

23TU

23TU

23TU

23TU

23TU

23TU


23TU

23TU

23TU

23TU

23TU

Hinh 2.1 Sơ đồ hệ thống BioPKI .............................................................. 16
U23T

Hinh 2.2 Hình sóng trước và sau DTW ..................................................... 19
U23T

Hình 2.3 EPs và các gợn sóng nhỏ ............................................................ 21
U23T

Hình 2.4 EPs từ hai tín hiệu ...................................................................... 23
U23T

Hình 2.6 Một ví dụ về so sánh các điểm EPs ............................................ 26
U23T

Hình 2.7 Kết quả sau khi so sánh EPs ....................................................... 27
U23 T

Hình 2.8 Làm méo đoạn (a) làm méo đoạn tín hiệu tham chiếu ................ 27
U23T


(b) làm méo tín hiệu mẫu .......................................................................... 27
U23 T

Hình 2.9 Kết quả làm méo đoạn (a) trước khi làm méo đoạn .................... 28
U2 3T

(b) sau khi làm méo đoạn ......................................................................... 28
U23 T

Hình 2.10 Một số ví dụ chữ ký (a,b) là chữ ký thật (c,d) là chữ ký giả mạo

U23T

.................................................................................................................. 30
23TU

23TU

Hình 2.11 Mã thuộc tính của thời gian bút viết ......................................... 36
U 23T

Hình 3.1 Sự minh hoạ của một chuỗi Markov với 3 trạng thái (ký hiệu S1,

S2, và S3.) ................................................................................................. 40
U23 T

23TU

23TU


Hình 3.2 Sự minh hoạ của một mơ hình Markov với 3 trạng thái ............. 42
U23 T

Hình 3.3 (a) là chữ ký ngẫu nhiên (b) là chữ ký đơn giãn (c) là chữ ký nguy

hiểm (d) là chữ ký gốc .............................................................................. 52
U23 T

23TU

Hình 3.4 (a) là chữ ký trước khi dịch chuyển (b) là chữ ký sau khi được

dịch chuyển vào giữa ảnh. ......................................................................... 53
U23 T

23TU

Hình 3.5 Điểm thuộc tính dựa trên phân chia theo chiều dọc .................... 54
U23T

8


23TU

U23T

23TU


23TU

Hình 3.6 Các điểm thuộc tính được tính theo sự phân chia theo chiều ngang
.................................................................................................................. 55
Hình 3.7 Khoảng cách trung bình (d avg ) và độ lệch chuẩn ( σ ) ............... 58
URU

URU

U2 3T

23T

23 T

Hình 3.8 Các điểm thuộc tính dựa trên sự phân chia theo chiều dọc với độ

sâu 2. ......................................................................................................... 64
U23T

23TU

Hình 3.9 Các điểm thuộc tính dựa trên sự phân chia theo chiều ngang với

độ sâu ........................................................................................................ 65
U23T

23TU

23TU


23TU

Hình 3.10 Mơ hình trái-phải của q xử lý trình học ............................... 66
U23T

Hình 3.11Học và kiểm tra chéo cho đường cong với một số trang thái ..... 67
U2 3T

Hình 3.12 Đường viền phân chia vùng chấp nhận và loại bỏ trong q trình

kiểm tra ..................................................................................................... 67
U23T

23TU

23TU

23TU

23TU

23TU

23TU

23TU

23TU


Hình 3.13 Thuật tốn chuẩn hóa ............................................................... 70
U23 T

Hình 3.14 Mơ hình HMH cho chữ ký online ............................................ 73
U23T

Hình 3.15 Biểu đồ DET ............................................................................ 74
U23T

Hình 4.1 Form thơng tin người dùng ........................................................ 77
U23 T

Hình 4.2 Form thêm người dùng .............................................................. 78
U23 T

Hình 4.3 Form Cập nhật người dùng ........................................................ 79
U23 T

Hình 4.4 Form thẩm định chữ ký .............................................................. 80
U 23T

Hình 4.5 Form hiển thị kết quả thẩm định ................................................ 82
U23 T

9


MỞ ĐẦU
Trong những năm gần đây, cơ sở hạ tầng của khố cơng khai đã được phát
triển cùng với nhu cầu ngày càng tăng về bảo mật dữ liệu số. Chữ ký số được tạo

ra bằng cách sử dụng công nghệ mã hố cơng khai. Cơng nghệ này sẽ được sử
dụng trong các giao dịch về thương mại được thực hiện trong mạng bảo mật kém
mà không sợ bị giả mạo chữ ký. Điểm mạnh của các chữ ký số dựa trên truy cập
điều khiển thơng qua các khố cá nhân. Việc lưu trữ khoá cá nhân bảo vệ bằng
phương pháp mật khẩu từ lâu đã là một mắt xích yếu trong hệ thống bảo mật.
Đối với chữ ký điện tử quản lý khoá riêng là điểm dễ bị tấn cơng nhất trong
hệ thống bảo mật. Mặt khác tính bảo mật của chữ ký điện tử lại dựa vào phương
pháp mã hố bất đối xứng vì phải sử dụng các truy cập thơng qua khố riêng.
Đối với giải thuật mã hố cơng khai khố riêng là một số rất lớn thường là một
số 1024 bit. Nhưng khi nó được lưu trữ thì sức mạnh của khố riêng giảm một
cách trầm trọng xuống chỉ còn là 6 đến 8 ký tự mật khẩu. Mọi người thường
không nhớ nhiều mật khẩu trong một thời gian dài nên họ thường sử dụng mậu
khẩu giống với mật khẩu của email hoặc mậu khẩu vào mạng, hoặc là mật khẩu
trực tuyến của ngân hàng, mật khẩu vào cơng ty …,người ta có thể ghi mật khẩu
vào các mảnh giấy và bị nhìn trộm. Họ có thể chọn biệt danh, ngày sinh làm mật
khẩu do đó mật khẩu của họ có thể bị những người gần gũi với họ đoán được.
Tất cả những vấn đề được đề cập ở trên thì sử dụng mật khẩu là một phương
pháp không tốt trong việc sử dụng chữ ký điện tử. Một người truy cập vào khoá
riêng là người biết được mật khẩu vào khố riêng nhưng khơng có nghĩa đó đúng
là người đấy.

10


Trước yêu cầu chống đánh cắp mật khẩu, quên mật khẩu, giả mạo chữ ký và
đảm bảo sự an toàn trong thực hiện các giao dịch điện tử nên luận văn này tôi sẽ
giới thiệu hai phương pháp thẩm định chữ ký viết tay tiên tiến ứng dụng trong
thực hiện các giao dịch điện tử thay vì thực hiện các giao dịch bằng phương pháp
sử dụng mật khẩu thông thường. Luận văn tập trung vào các nội dung sau:
U


Về lý thuyết
- Nghiên cứu, tìm hiểu phương pháp thẩm định chữ ký viết tay bằng
sinh trắc học
- Nghiêu cứu, tìm hiểu phương pháp thẩm đinh chữ ký viết tay bằng mơ
hình Markov ẩn

U

Về thử nghiệm
- Cài đặt một chương trình kiểm thử thẩm định chữ ký viết tay bằng mơ
hình Markov ẩn
Luận văn bao gồm các chương sau:

U

Chương 1: Tổng quan về sinh trắc học
U

- Trình bày về khái niệm của sinh trắc học, đặc điểm của hệ sinh trắc học
U

Chương 2: Phương pháp thẩm định chữ ký viết tay bằng sinh trắc học
U

- Trình bày phương pháp thẩm định chữ k ý viết tay bằng phương pháp sinh
trắc học.
U

Chương 3: Phương pháp thẩm định chữ ký viết tay bằng mô hình MarKov ẩn

U

- Trình bày tổng quan về lý thuyết mơ hình Markov ẩn
- Trình bày phương pháp thẩm định chữ ký viết tay bằng phương pháp mơ
hình MarKov ẩn cho hệ thống online và off-line
U

Chương 4: Xây dựng hệ thống thẩm định chữ ký viết tay bằng phương pháp mơ
U

hình Markov ẩn.

11


U

Chương 5: Đánh giá và nhận xét những kết quả đạt được.
U

Để hoàn thành bản đồ án tốt nghiệp này, ngồi sự cố gắng của cá nhân em
cịn có sự giúp đỡ tận tình của PGS.TS. Nguyễn Thị Hồng Lan – giảng viên khoa
Công nghệ thông tin Trường đại học Bách khoa Hà Nội. Cô đã định hướng, cung
cấp tài liệu, hướng dẫn chi tiết và sửa chữa các sai sót em mắc phải trong q trình
thực hiện.
Em xin chân thành cảm ơn các thầy cô giáo trong khoa “Công nghệ thông
tin” Trường đại học Bách khoa Hà Nội đã tận tình dạy dỗ em trong thời gian em
học tập tại trường.
Hà nôi, ngày 15 tháng 11 năm 2006.
Học viên

Nguyễn Anh Tài

12


CHƯƠNG I: TỔNG QUAN SINH TRẮC HỌC
1.1 KHÁI NIỆM SINH TRẮC HỌC
Sinh trắc hoc là khả năng tự động nhận dạng người dựa trên hình dáng của
thân thể hoặc tính cách của người đó. Phương pháp nhận dạng này được ưa
chuộng hơn phương pháp nhận dạng truyền thống dựa trên số PIN và mật khẩu.
Sinh trắc hoc miêu tả tính duy nhất về hình dáng vật lý và cách ứng xử của một
người. Các hình dạng vật lý bao gồm dấu vân tay, mu bàn tay, tròng đen của mắt
…Các cách ứng xử bao gồm chữ ký tay, cách ấn phím, giọng nói…Tổng hợp tất
cả những yếu tố trên tạo nên tính duy nhất của một người. Sinh trắc hoc là cách
duy nhất để nhận dạng ra một người với các căn cứ hợp lý.
1.2 HỆ BẢO MẬT SINH TRẮC HỌC
Hệ thống sinh trắc học (biometric system) hoạt động dựa trên hai chức năng
chính:
1. Thẩm định (verification): thực hiện đối sánh 1-1 giữa mẫu sinh trắc học
thu nhận được (biometric sample) với mẫu khn dạng sinh trắc học
(biometric template) có trong hệ thống từ trước . Kết quả trả lời câu hỏi
mẫu sinh trắc có liên quan tới mẫu khn dạng sinh trắc hay không.
2. Nhận dạng (identification): chức năng này thực hiện tìm kiếm (1-n), tìm
một mẫu sinh trắc cụ thể trong một cơ sở dữ liệu các mẫu khuôn dạng sinh
trắc thu thập từ trước.
Trong đồ án này chúng ta chỉ nghiên cứu hệ thống sinh trắc học thẩm định
cho chữ ký tay.

13



Có hai hướng tiếp cận để kết hợp sinh trắc học và mật mã học như sau
Hướng thứ nhât:
- Sử dụng sinh trắc học quản lý khóa (biometric-based key release)
Hướng thứ hai:
- Sử dụng sinh trắc học để tạo khóa riêng (biometric-based private key
generation)
1.3 CHỮ KÝ SINH TRẮC HỌC
Khái niệm chữ ký sinh trắc học lần đầu tiên được đề cập trên bài báo của
Pawan và Siyal vào năm 2001 họ định nghĩa chữ ký sinh trắc học là quá trình tạo
ra một khố riêng từ một mẫu sinh trắc học và dùng khố đó để ký vào tài liệu
điện tử. Sự thuận lợi của phương pháp mới là điều hiển nhiên, một khoá riêng
duy nhất được tạo ra từ một mẫu sinh trắc học của người nào đó hiển nhiên
chúng ta khơng cần phải lưu trữ khố riêng do đó chúng ta loại trừ được các lỗ
hổng bảo mật về quản lý khoá riêng. Việc tạo động khoá riêng sẽ thuận tiện cho
chúng ta rất nhiều trong việc ký các tài liệu một người có thể ký vào tài liệu bất
cứ khi nào và ở đâu mà không cần phải theo đĩa hoặc thẻ thơng minh.
1.4 CÁC KHĨ KHĂN KHI THỰC HIỆN
Việc thực hiện chữ ký sinh trắc học trong ứng dụng bao gồm 2 phần
1. Lấy được chính xác các mẫu dữ liệu sinh trắc học
3. Tạo ra khố riêng từ dữ liệu mẫu.
Khó khăn trong cơng việc thứ nhất là tất cả các bít trong mẫu phải chính
xác bài báo của Pawan và Siyal chỉ đề cập đến vấn đề thứ 2. Họ đưa ra một ví dụ
giả thiết về sinh trắc học tròng đen mắt trong đó 512 bít của trịng mắt khơng tồn
tại một bít nào lỗi. Dựa trên mẫu này sử dụng thuật toán khố cơng khai để tạo ra

14


một khố riêng ví dụ RSA và DSA. Tuy nhiên khi chụp trịng đen mắt thì sẽ tồn

tại các bít lỗi. Trong luận văn này sẽ đề cập nghiên cứu cả hai nội dung trên
nhằm đạt được một giải pháp tin cậy , hợp lý và có chi phí thấp dựa trên các chữ
ký trực tuyến một định dạng thông dụng của sinh trắc học về ứng xử.
1.5 VẤN ĐỀ BẢO MẬT BẰNG PHƯƠNG PHÁP SINH TRẮC HỌC DỰA
TRÊN KÝ VIẾT TAY
Bảo mật bằng phương pháp sinh trắc học dựa trên chữ ký viêt tay đã được một
số bài báo đề cập [Hao Feng, Chan Choong Wah]. Tuy nhiên vẫn chưa đưa ra
được một giải pháp có tính khả thi cịn có nhiều hạn chế do đó luận văn này trình
bày trình các giải pháp mang tính khả thi, giải quyết những vấn đề còn tồn tại để
xây dựng được một hệ thống bảo mật bằng phương pháp sinh trắc học dựa trên
chữ ký viết tay hoàn thiện với các tính năng bảo mật tốt hơn và hiệu quả hơn

15


CHƯƠNG II: NGHIÊN CỨU, TÌM HIỂU PHƯƠNG PHÁP THẨM ĐỊNH
CHỮ KÝ VIẾT TAY BẰNG PHƯƠNG PHÁP SINH TRẮC HỌC
2.1 HỆ THỐNG MÃ HOÁ BẢO MẬT SINH TRẮC HỌC BioPKI
Hiện nay có hai hướng tiếp cận của hệ thống bảo mật sinh trắc học dựa trên
sự kết hợp công nghệ sinh trắc học với hạ tầng mã hóa cơng khai PKI. Trong
luận văn này tập trung vào hướng tiếp cận thứ hai là sử dụng sinh trắc học để tạo
khóa riêng
Hệ thống mã hoá BioPKI là một giải pháp kết hợp hai cơng nghệ sinh trắc
học và khố cơng khai.

Hinh 2.1 Sơ đồ hệ thống BioPKI [Hao Feng]
Hình vẽ thể hiện sơ đồ khối của hệ bảo mật sinh trắc học BioPKI. Hệ thống bảo
mật sinh trắc học BioPKI bao gồm ba giai đoạn [Hao feng]
1. Thu nhận dấu hiệu sinh trắc học và đối sánh mẫu
2. Mã hoá đặc trưng sinh trắc học

3. Tạo khoá riêng bằng mã sinh trắc học
Giai đoạn thu nhận dấu hiệu sinh trắc học và đối sánh mẫu là giai đoạn thu
nhận các dấu hiệu sinh trắc học và đơi sánh mẫu nhằm mục đích loại bỏ các mẫu

16


giả đơn giản. Giai đoạn mã hoá đặc trưng sinh trắc học sẽ tìm ra một số thuộc
tính đặc trưng trong các thuộc tính đã được định nghĩa trước và nối các mã thuộc
tính thành một chuỗi mã cuối cùng là giai đoạn tạo khoá riêng bằng mã sinh trắc
học sử dụng chuỗi mã làm đầu vào để tạo ra khoá riêng cho từng người ký. Hoạt
động của hệ thống bao gồm hai giai đoạn đó là ký và thẩm định xác thực. Một
người đưa 10 mẫu chữ ký từ các mẫu này người ta một chữ ký mẫu và một cặp
khố trong đó họ sẽ loại bỏ khố riêng và giữ khố cơng khai. Trong q trình
xác minh một người đưa ra một mẫu chữ ký. Sau khi xử lý qua ba giai đoạn trên
một khoá riêng được tạo ra nếu khố riêng này tương ứng với khố cơng khai đã
được lưu trữ thì mẫu chữ ký trên đã được thẩm định và khóa riêng kia là chữ ký
điện tử dùng để ký trên các tài liệu điện tử.
2.2 GIAI ĐOẠN ĐỐI SÁNH MẪU.
Giai đoạn so sánh hình dạng bao gồm q trình kiểm tra các thuộc tính tĩnh
của chữ ký với chữ ký mẫu chỉ có các chữ ký có hình dạng giống với chữ ký
mẫu sẽ được xử lý trong giai đoạn tiếp theo. Giai đoạn này sẽ loại bỏ những chữ
ký giả mạo đơn giản. Các thuộc tính tĩnh của chữ ký mẫu khơng liên quan tới
gian đoạn tạo ra khoá riêng sau này. Trong để thực hiện giai đoạn này chúng ta
áp dụng thuật toán làm méo theo thời gian động (DTW) của Sankoff và Kruskal
để đối sánh hình dạng. DTW căn hình dạng sóng của x,y của một mẫu thử với
tham chiếu của nó. [Chang choong Wah
2.2.1 Đặc điểm của phương pháp DTW
Kỹ thuật DTW dựa trên giải thuật so sánh quy hoạch động để tìm ra hướng đi
so sánh tốt nhất với chi phí thấp nhất giữa một tín hiệu vào và một tín hiệu mẫu.

DTW đưa vào một tín hiệu nó sẽ được chỉnh sửa một cách phi tuyến tính với với

17


tín hiệu tham chiếu của nó. Q trính xử lý sẻ thay đổi sóng của tín hiệu đầu vào
hai khía cạnh
Điểm kết thúc hình sóng của đầu vào sẽ được căn thẳng với tham chiếu.
Đỉnh và đáy sẽ được căn thẳng với đỉnh và đáy của các tham chiếu. Để hiểu rõ
hơn về hình dạng sóng trước và sau khi DTW được thể hiện trong hình 2.2 Hình
(a) và (b) được vẽ từ tín hiệu tham chiếu, ở giữa hình (c) và (d) được vẽ từ tín
hiệu trước khi DTW và hai hình cuối cùng (e) và (f). là tín hiệu mẫu đã được làm
méo. Cả x và y độc lập với nhau được làm méo bằng DTW. Từ các hình (b), (d)
và (f) ta có thể nhận thấy các đỉnh và đáy của hình sóng được dịch chuyển cho
căn thẳng với các tham chiếu của nó. Một vài sự dịch chuyển của đỉnh và đáy
được tơ đậm trong hình (b), (d) và (f).

18


Hinh 2.2 Hình sóng trước và sau DTW [Hao feng]
19 T

19 T

Thơng thường DTW có hai nhược điểm chính khi ứng dụng vào xác nhận
chữ ký: (i) khối lượng tính toán lớn, (ii) sự méo của các chữ ký giả mạo. Nhược
điểm đầu tiên đã được biết đến trong nhận dạng tiếng nói. Nguyên nhân do DTW
làm méo phi tuyến trên tồn bộ tín hiệu. Thời gian thực hiện tỷ lệ với hình bao
kích thước tín hiệu. Để giảm thời gian tính tốn [Hangai] đã định nghĩa các điều

kiện biên trong ma trận so sánh DTW. Tuy nhiên kết quả của thời gian tính tốn
vẫn khá lâu, trung bình là 0.4 s, sẽ được đề cập đến trong phần sau. Vấn đề về
khối lượng tính tốn lớn sẽ khơng phù hợp với hệ thống xác nhận chữ ký trực
tuyến với nhiều yêu cầu với nhiều người tại cùng một thời điểm.

19


Tuy nhiên nhược điểm thứ hai không được đề cập nhiều bằng các tài liệu
trước đây. Khi được sử nhận trong dạng tiếng nói. DTW đã tìm ra cách tốt nhất
để cắt tín hiệu đầu vào để nhận dạng tơt hơn. Tuy nhiên trong xác nhận chữ ký
khi có các chữ ký giả mạo thì các tín hiệu giả mạo cũng được cắt do đó dễ bị xác
nhận sai. Vì vậy ta cần phải thay sửa lại một số điểm trong thuật toán được áp
dụng trong xác nhận chữ ký. Vân đề này được giải quyết một cách triệt để bằng
cách sử dụng một phép đo chuyển động phụ được định nghĩa bởi Sato và Kogure
(1982). Phép đo chuyển động có tính đến các nét bị làm méo. Đối với các tín
hiệu giả mạo thì các nét méo khơng cịn thẳng nếu như nó bị cắt nhiều trong q
trình xử lý DTW. Tuy nhiên trong phép đo chuyển động sẽ tạo thêm sự phức tạp
của phân lớp dữ liệu và tạo sự quyết định. Do đó nó khơng được sử dụng trong
những nghiên cứu gần đây.
Trong khuôn khổ luận văn tốt nghiệp tơi nghiên cứu và tìm hiểu một giải
pháp đơn giản được đề nghị bởi [Hao feng, Chang Choong Wah] khơng cần sử
dụng phép đo chuyển động thích hợp với việc giải quyết hai hạn chế trên. Nếu
như quá trình xử lý DTW làm méo tồn bộ điểm của tín hiệu thì chúng ta sẽ sử
dụng một kỹ thuật làm méo mới chỉ làm méo những điểm quan trọng của tín hiệu
2.3 KỸ THUẬT LÀM MÉO MỚI EPW
Chúng ta gọi kỹ thuật này là làm méo những điểm cần thiết(Extreme points
warping, EPW). Giống như tên của nó gợi ý kỹ thuật này chỉ làm méo những
điểm quan trọng (Eps) của tín hiệu. Q trình xử lý của EPW bao gồm 3 bước (i)
Đánh dấu các điểm EPs, (ii) so sánh các điểm Eps, (iii) các đoạn làm méo.

2.3.1 Đánh dấu các điểm làm méo.
EPs được định nghĩa như các đỉnh và đáy của tín hiệu. Đầu tiên chúng ta
định nghĩa một khoảng đi lên ký hiệu là ‘r’ là độ lớn của khoảng cách từ một đáy

20


tới một đỉnh và một khoảng đi xuống ký hiệu là ‘d’ là độ lớn khoảng cách giữa
một đỉnh với một đáy. Đối với bất kỳ một đỉnh hoặc một đáy nào khoảng đi lên
có thể được tính với bất cứ đoạn cong nào và khoảng đi xuống cũng có thể được
tính với các đường cong ngược lại. Các đỉnh và các đáy được đánh dấu là EP nếu
như thoả mãn điều kiện sau.
r ≥ h0 , d ≥ h0
R

R

R

Trong dó h 0 được định nghĩa là ngưỡng, Các gợn sóng nhỏ sẽ khơng được
R

R

tính là các điểm Eps. Bởi vì trong mọi trường hợp các gợn sóng nhỏ cho ta độ tin
cậy sẽ không cao. Ngưỡng h 0 thường được chọn là 1 điểm (pixel). Do đó các
R

R


gợn sóng nhở với khoảng cách đi lên và khoảng cách đi xuống bé hơn h0 sẽ
khơng được tính là các điểm Eps. Giải thuật đánh dấu điểm EPs của chúng ta
đơn giản chỉ nhận các đỉnh và các đáy loại trừ các gợn sóng nhỏ dọc theo tín
hiệu.

19T

Hình 2.3 EPs và các gợn sóng nhỏ
19 T

Sau khi đánh dấu được các đỉnh và đáy quan trọng đồng nghĩa với đánh dấu
được các điểm EPs, chúng ta sẽ so sánh các điểm EPs của tín hiệu vào với tín
hiệu tham chiếu tương ứng của nó.
2.3.2 So sánh các điểm EPs

21


Do có nhiều cách ký nên, hai tập hợp các điểm EPs của tín hiệu mẫu và tín
hiệu tham chiếu nếu so sánh 1-1 thì sẽ khơng khớp với nhau. Vì có thể thiếu
hoặc thừa các điểm EPs trong cả hai tín hiệu. Hình 2.3(a) và(b) vẽ sơ đồ (torque)
của tín hiệu tham chiếu và tín hiệu mẫu. Định nghĩa của Torque sẽ được giải
thích trong phần sau. các điểm EPs được đánh dấu ‘*’ dọc theo hai tín hiệu.
Bằng cách thống kê sự khác biệt tự nhiên từ việc thu thập dữ liệu từ cơ sở
dữ liệu bao gồm 25 người dùng và 1000 chữ ký. Chúng ta có thể tóm lược ba
loại khác nhau
Khơng đồng bộ điểm bắt đầu, điểm bắt đầu của cả hai tín hiệu khơng đồng
bộ bắt đầu từ một đỉnh hoặc bắt đầu từ một đáy.
Tồn tại các gợn sóng nhỏ, một gợn sóng có thể tìm thấy ở điểm bắt đầu hoặc
điểm kêt thúc của tín hiệu nó nằm ở giữa một cặp đỉnh và đáy, tuy nhiên sự xuất

hiện của hai hoặc nhiều gợn sóng giữa một tín hiệu đúng và tham chiếu của nó là
rất hiếm.
Khơng đồng bộ ở điểm kết thúc, điểm cuối cùng của cả hai tín hiệu khơng
đồng bộ có thể kết thúc bởi một đỉnh hoặc một đáy.
Chúng ta sẽ định nghĩa một giải thuật so sánh để nhận ra các cặp so sánh
tương ứng mặc dù có nhiều vấn đề đã được đề cập ở phía trên. Giải thuật so sánh
các điểm EPs của chúng ta dựa trên kỹ thuật so sánh quy hoạch động (Sankoff và
Kruskal, 1983). Thơng thường q trình so sánh quy hoạch động, một điểm của
một tín hiệu có thể được so sánh với bất cứ điểm nào ở tín hiệu kia. Tuy nhiên
trong trường hợp của chúng ta các điểm EPs là các đỉnh và các đáy do đó các cặp
so sánh sẽ là so sánh giữa các đỉnh của tín hiệu này với tín hiệu kia và giữa các
đáy của tín hiệu này với đáy của tín hiệu kia. Chúng ta sẽ giới thiệu một số quy
luật mới trong giải thuật quy hoạch động để phù hợp với ứng dụng.

22


Hình 2.4 EPs từ hai tín hiệu
Trong q trình xử lý so sánh các điểm EPs một ma trận EP-EP được thiết
lập
Trong ma trận các điểm EPs của tín hiệu tham chiếu nằm ở hàng ngang còn
các điểm EPs của các tín hiệu mẫu nằm ở hàng dọc. Chú ý trong ma trận các
điểm hai tập hợp các điểm EPs phải đồng bộ với nhau nghĩa là bắt đầu với đỉnh
hoặc đáy. Tổng các chi phí của các phần tử ở trong vùng trắng ở hình 2.4(a)
được tính tốn. Đường thẳng làm méo là đường chịu ít chi phí nhất từ (1,1) tới
(I,J).

23



Hình 2.5 Giải thuật so sánh các điểm EPs (a) đường làm méo tồn bộ
(b) đường làm méo bộ phận.
Hình 2.5(b) biểu diễn ba loại đường làm méo cục bộ từ vị trí (m,n) với giả
thuyết rằng (m,n) là một cặp so sánh nghĩa là vị trí thứ m của EPs trong tín hiệu
tham chiếu được so sánh với vị trí thư n của tín hiệu mẫu), cặp so sánh tiếp theo
có thể là một trong ba loại sau (m+1,n+1),(m+1,n+3),(m+3,n+1), (m+1,n+3)
nghĩa là giữa hai điểm EPs sau điểm thứ n của tín hiệu mẫu là một cặp gợn sóng
nên nó có thể được bỏ qua trong so sánh hồn tồn tương tự với so sánh
(m+3,n+1) nghĩa là hai điểm EPs sau điểm thứ m của tín hiệu tham chiếu là một
cặp gợn sóng. Do đó nó được bỏ qua trong quá trình so sánh. Khi một cặp của
EPs bỏ qua, chí phí bỏ qua là S(k,k+1). Nó được định nghĩa giống như khoảng
cách giữa các khối thứ k và thứ k+1 của các điểm EPs trong tín hiệu.
Các điểm EPs trong các tín hiệu tham chiếu có thể được biểu diễn thành
hai thành phần (xi,yi). Trong đó xi là vị trí theo chiều ngang của EP và yi là độ
lớn theo chiều dọc của EP. Hoàn toàn tương tự đối với tín hiệu mẫu các điểm
EPs của tín hiệu mẫu cũng được biểu diễn bởi (x j ,y j ) chúng ta định nghĩa khoảng
R

R

R

R

cách cục bộ giữa phần tử (i,j) trong ma trận là.
d(i,j) = |x i – x j | + |y i – y j |
R

R


R

R

R

R

R

R

Để tránh trường hợp khi có một số lượng lớn sự khác nhau trong vị trí hoặc
độ lớn có thể vượt q ngưỡng tác dụng của quyết định so sánh. Chúng ta định
nghĩa D(i,j) là độ dài tổng quát tại phần tử thứ (i,j) trong ma trận. Điều kiện khởi
tạo ban đầu là.
D(1,1) = d(1,1), D(1,3) = d(1,3), D(3,1) = d(3,1)
Chúng ta sẽ tính chi phí tổng qt của tồn bộ các phần tử theo công thức

24


D(i - 1, j - 3) + d(i, j) + ρ s * S(j - 2, j - 1)

D(i,j) = min D(i - 1, j - 1) + 1/2d(i, j)
D(i - 3, j - 1) + d(i, j) + ρ * S(i - 2, i - 1)
s


(2.1)

Trong đó ρ s là hệ số bỏ qua khác với DTW bình thường. Chúng ta đã giới
R

R

thiệu chi phí bỏ qua trong cơng thức 4. chi phí bỏ qua thường rất nhỏ đối với bỏ
qua các gợn sóng. Tuy nhiên nó sẽ lớn hơn rất nhiều nếu như bỏ qua một cặp
quan trọng đỉnh và đáy nếu như chúng ta nhầm lẫn giữa một cặp đỉnh và đáy
thực sự với một cặp gợn sóng. Hệ số bỏ qua ρ s nhằm điều chỉnh ảnh hưởng của
R

R

chi phí bỏ qua trong quyết định của so sánh. Qua khảo sát thì người ta thấy
rằng ρ s = 2 là giá trị thích hợp, điều này sẽ được giải thích trong sau
R

R

Ví dụ, chúng ta áp dụng giải thuật này để so sánh hai tập hợp điểm EPs.
Đầu tiên chúng ta thiết lập ma trận EP-EP (hình 2.5), trong đó các điểm EP của
tín hiệu tham chiếu nằm trên trục ngang, còn các điểm EP của tín hiệu mẫu nằm
trên trục dọc. Như chúng đã giải thích từ trước ma trận sẽ được đồng bộ giữa hai
tập EPs. Do đó điểm đầu tiên EP ( giả sử là điểm đáy) của tín hiệu tham chiếu bị
xố đi để cho hai tập hợp các điểm EPs được đồng bộ với điểm xuất phát là một
đỉnh( nhìn hình 2.3). Hồn tồn tương tự chúng ta có thể xố điểm đầu tiên EP(
giả sử là điểm đỉnh) của tín hiệu mẫu nhằm đồng bộ hoá tập hợp các điểm EPs
được bắt đầu từ một đáy, mặc dù nó khơng đúng với sự kiểm tra trực quan nhưng
nó vẫn là một ma trận EP-EP đúng. Nhưng phải chịu một tổng chí phí sẽ rất lớn
tại các phần tử trong ma trận thứ hai này nhằm mục đích chỉ ra rằng nó khơng

phải là một ma trận chính xác.

25