ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
LÊ THỊ THU
NGHIÊN CỨU PHƯƠNG PHÁP BẢO VỆ THÔNG TIN
DÙNG TRÊN THIẾT BỊ CẦM TAY

LUẬN VĂN THẠC SĨ


NGHIÊN CỨU PHƯƠNG PHÁP BẢO VỆ THÔNG TIN
DÙNG TRÊN THIẾT BỊ CẦM TAY Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 604805 LUẬN VĂN THẠC SĨ

Người hướng dẫn khoa học: PGS TS TRỊNH NHẬT TIẾN Hà Nội – 2011
MỤC LỤC
BẢNG DANH MỤC CÁC TỪ VIẾT TẮT 5

1.4.2. Chữ ký số 36
1.4.2.1 Sơ đồ chữ ký số 36
1.4.2.2 Chữ ký số RSA 36
1.4.2.3 Chữ kỹ số Elgamal 37
Chƣơng 2. HỆ MẬT MÃ TRÊN ĐƢỜNG CONG ELLIPTIC 39
2.1. ĐƢỜNG CONG ELLIPTIC 39
2.1.1. Khái niệm đƣờng cong Elliptic 39
2.1.1.1 Đƣờng cong Elliptic theo công thức Weierstrass 39
2.1.1.2. Đƣờng cong Elliptic trên trƣờng Galois 40
2.1.1.3. Đƣờng cong Elliptic trên trƣờng hữu hạn 42
2.1.2. Các phép toán trên đƣờng cong ELLIPTIC 44
2.1.2.1 Phép cộng 44
2.1.2.2 Phép nhân 47
2.1.2.3. Số điểm trên đƣờng cong ELLIPTIC với trƣờng FQ 50
2.1.4. Chọn đƣờng cong ELLIPTIC phù hợp 51
2.1.4.1. Trƣờng K 51
2.1.4.2. Dạng của đƣờng cong elliptic 51
2.1.4.3. Phƣơng pháp lựa chọn 52
2.1.4.4. Bài toán LOGARIT rời rạc trên đƣờng cong ELLIPTIC 53
2.2 MỘT SỐ HỆ MẬT TRÊN ĐƢỜNG CONG ELLIPTIC 54
2.2.1. Hệ mã hoá 54
2.2.1.1. Nhúng bản rõ vào đƣờng cong Elliptic 54
2.2.1.2. Hệ mã hóa “tựa” Ellgamal 55
2.2.1.3. Hệ mã tƣơng tự mã mũ (Dạng tƣơng tự của Massey –Omura) 56
2.2.1.4. Hệ mã hóa trên đƣờng cong Elliptic của Menezes – Vanstore 58
2.2.1.5. Kết hợp ECES với thuật toán Rijndael và các thuật toán mở rộng 59
2.2.1.6. Một số chuẩn sử dụng hệ mật ECC 59

2.2.1.7. So sánh RSA và ECC 62
2.2.2. Chữ ký số 65

TÀI LIỆU THAM KHẢO 98
Elliptic Curve Key Agreement
Thỏa thuận khóa trên đƣờng
Elliptic
FSTC
Financial Services Technology
Consortium
Hệ thống thanh toán điện tử và
các dịch vụ tài chính
IETF
Internet Engineering Task Force
Giao thức thỏa thuận khóa
NIST
National Institue of Standards
Viện nghiên cứu chuẩn quốc tế
SET
Secure Electronic Transaction

WAP
Wireless Application Protocol

ECDLP
Elliptic Curve Discrete Logarithm
Problem

ECDH
Elliptic curve Diffie-Hellman DANH MỤC CÁC HÌNH VẼ


Hình 4.8
Giao diện chức năng quản lý tin nhắn SMS
Hình 4.9
Giao diện chức năng quản lý danh bạ LỜI MỞ ĐẦU
Hiện nay cùng với sự phát triển mạnh mẽ của các thiết bị cầm tay với ƣu điểm
tiện lợi, linh hoạt thì nhu cầu xây dựng những ứng dụng trên các thiết bị này ngày càng
lớn đặc biệt là các ứng dụng thƣơng mại điện tử. Do đó nhu cầu bảo mật thông tin
trong các giao dịch sử dụng thiết bị cầm tay càng lớn. Một trong những đặc điểm của
các thiết bị cầm tay là bộ nhớ nhỏ với tốc độ tính toán thấp.
Xuất phát từ thực tế đó, các thuật toán mã hóa trên đƣờng cong Elliptic với ƣu
điểm là tốc độ xử lý nhanh, không cần nhiều tài nguyên đã ra đời và rất thích hợp với
các thiết bị cầm tay này vì nó vừa đảm bảo độ an toàn và không yêu cầu nhiều tài
nguyên. Chính vì vậy em đã chọn đề tài:"Nghiên cứu phƣơng pháp bảo vệ thông tin
dùng trên thiết bị cầm tay" làm đề tài luận văn thạc sỹ của mình.
Nội dung của đề tài:
Chương 1: Các khái niệm cơ bản
Nêu lên một số khái niệm cơ bản về đại số, số học, các khái niệm về mã hóa,
chữ ký số cũng nhƣ độ phức tạp thuật toán.
Chương 2: Hệ mật mã trên đường cong Elliptic
Tìm hiểu về đƣờng cong Elliptic, một số hệ mật trên đƣờng cong Elliptic và các
tình huống xuất hiện khi sử dụng các hệ mật trên.
Chương 3: Sử dụng một số hệ mật mã khác trên thiết bị cầm tay
Nghiên cứu một số hệ mã khác dùng trên thiết bị cầm tay nhƣ: RC4, DES, 3DES.
Chương 4: Thử nghiệm chương trình:
Thử nghiệm chƣơng trình bảo mật tin nhắn trên điện thoại di động.
Em xin chân thành cảm ơn PGS. TS Trịnh Nhật Tiến đã tận tình giúp đỡ em
trong suốt quá trình viết luận văn này.


F nên m phải là hợp số. Khi đó có
hai số nguyên dƣơng q
1
, q
2
>1 để m = q
1
q
2
. Vì q
1
,q
2
< m nên q
1
,q
2


F. Nhƣ vậy ta có
phân tích: q
1
= t
1
t
2
t
h
và q

Điều này mâu thuẫn với giả thiết m

F. Nhƣ vậy F phải là tập rỗng. Do đó mọi
số tự nhiên lớn hơn 1 đều phân tích thành tích của hữu hạn thừa số nguyên tố.
Bây giờ giả sử một số đƣợc phân tích thành hai tích dạng A và B các thừa số
nguyên tố. Khi đó A = B. Bằng cách lƣợc bỏ tất cả các thừa số nguyên tố xuất hiện
trong cả A và B, ta nhận đƣợc đẳng thức tƣơng đƣơng C=D. Ta cần phải chứng minh
C=D=1.
Giả sử trái lại, C = D

1. Gọi p là thừa số nguyên tố xuất hiện trong C. Khi đó
p không thể là thừa số xuất hiện trong biểu thức tích của D. Có nghĩa là D không phải
là bội của p, và do đó C cũng không là bội của p (mâu thuẫn!). Vậy C = D = 1. Điều
này chứng tỏ rằng sự phân tích ra các thừa số nguyên tố của một số nguyên >1 là duy
nhất nếu không kể đến thứ tự các thừa số.

Định lý 1.2
Mọi hợp số n đều có ước nguyên tố nhỏ hơn
n

Chứng minh
Vì n là một hợp số nên ta có thể viết n = ab, trong đó a và b là các số nguyên
với 1<a, b

n. Rõ ràng ta phải có a hoặc b không vƣớt quá
n
, giả sử đó là a. Ƣớc
nguyên tố của a cũng đồng thời là ƣớc nguyên tố của n.
1.1.1.2. Phương pháp kiểm tra số nguyên tố
1/. Thuật toán Fermat

9-1
= 256 = 4 mod 9
Kết quả trên xác nhận khi p là số nguyên tố, thì 2
p-1
= 1 mod p, và cũng cho một
phỏng đoán rằng p không phải là số nguyên tố, thì 2
p-1


1 mod p. Tuy nhiên phỏng
đoán này lại không đúng, chẳng hạn nhƣ: n = 341 = 11 x 31 không phải là số nguyên
tố, nhƣng nó vẫn thoả mãn 2
341-1
= 1 mod 341. Do vậy định lý Fermat với a = 2 có thể
đƣợc sử dụng kiểm tra một số là hợp số nhƣng không thể dùng để kiểm tra một số chắc
chắn là số nguyên tố. Các số mà thoả mãn định lý Fermat mà không phải là số nguyên
tố gọi là số giả nguyên tố và đƣợc định nghĩa một cách nhƣ sau:

Định nghĩa 1.2
Một số giả nguyên tố cơ sở a là một hợp số nguyên n thoả mãn công thức a
n-1
= 1 mod n.

Nếu số giả nguyên tố cơ sở a không tồn tại, thì định lý Fermat cho một cách rất
đơn giản để kiểm tra số nguyên tố: một số n là số nguyên tố nếu và chỉ nếu
a
n-1
=1 mod n. Đáng tiếc số giả nguyên tố cơ sở a lại tồn tại với mọi cơ sở, vì
vậy định lý Fermat chỉ cho một cách kiểm tra thiên về hợp số. Thuật toán nhƣ sau:



như sau:
Định nghĩa 1.5 (Ký hiệu Jacobi)
Với n

1 lẻ và số ngun a

0. Giả sử n có triển khai chính tắc thành thừa số
ngun tố là n = p
1
x1
p
2
x2
p
k
xk
, thì ký hiệu Jacobi được định nghĩa như sau:









p
a
=

a









Khi n = p là số ngun tố, thì giá trị của ký hiệu Legendre và Jacobi là nhƣ nhau.
Định lý 1.4 (Tiêu chuẩn Euler)
Nếu n là số ngun tố khác 2, thì:






n
a
= a
(n-1)/2
mod n với a thoả mãn 1

a

n-1.
Định nghĩa 1.6
Với n là một hợp số ngun lẻ. Nếu gcd(a,n)>1hoặc a

1










Nếu
Nếu a là một thặng dư bậc 2 modp
Trường hợp khác

Sau đây là thuật toán xác định a là bằng chứng Euler(Euler witness) của n là
hợp số:

Bƣớc đầu tiên của thuật toán là tính r = a
(n-1)/2
mod n, giống nhƣ với thuật toán
Fermat. Nếu r =

1 mod n, thì r
2
= a
n-1
=1mod n, nên n là hợp số bằng thuật toán
Fermat. Bƣớc tiếp theo là tính Jacobi
a


(n)/2 giả mạo Euler (Euler liar)
cho n trong đoạn [2, n-1].
Chúng ta biết rằng

(n)<n, nên với mỗi hợp số n lẻ, ít hơn n/2 sự chọn lựa là
giả mạo Euler (Euler liars), và do đó có ít nhất n/2 chọn lựa là bằng chứng (Euler
witness). Điều này ngụ ý rằng nếu n là hợp số, thì có ít nhật 50% cơ hội cho mỗi giá trị
ngẫu nhiên của a trong thuật toán Solovay-Strassen sẽ là bằng chứng (witness). Nếu
kiểm tra phân loại một số là hợp số thì không có một sai sót nào. Nếu kiểm tra phân
loại một số là số nguyên tố thì có thể là không chính xác. Xác suất sai đƣợc cho bởi
một hệ quả sau đây:
Hệ quả
Nếu thuật toán Solovay-Strassen với tham số n và k phân loại n là số nguyên tố,
thì xác suất sai nhiều nhất là (1/2)
k
.
Vì vậy, chúng ta có thể đạt đƣợc xác suất n là số nguyên tố cao hơn đơn giản
bằng cách tăng k lên một giá trị cần thiết. Hơn nữa, thuật toán Solovay-Strassen bảo
đảo xác suất giống nhau của phân loại đúng bất chấp độ lớn của n. Điều này rất hữu
ích vì chúng ta muốn tìm kiếm số nguyên tố lớn.
Cách tính Jacobi:
Định lý 1.7: Với m, n >1 là số nguyên lẻ và với a, b là số nguyên bất kỳ. Thì ký
hiệu Jacobi có các tính chất sau:
(i)







n
a






n
b

(iii)






mn
a
=






m
a






n
1
=1
(vi)
( 1)/2
1 if 1mod4
1
( 1)
1if 3mod4
n
n
n
n





  







mn
m
mn
n
nm
mn
m






  





  





Các tính chất này cho phép chúng ta định nghĩa đệ quy ký hiệu Jacobi. Nếu n là
số lẻ, và a=2
k
a
1



Định nghĩa đệ quy này đƣợc diễn giải bởi thuật toán sau, thuật toán hiệu quả để
tính






n
a
mà không cần phải phân tích n thành thừa số nguyên tố:

Thời gian chạy của thuật toán tính Jacobi là O(log
2
n). Thuật toán Euler-witness
thực hiện với hai phép tính chính: a
(n-1)/2
mod n và






n
a
. Sử dụng phƣơng pháp bình
phƣơng liên tiếp, phép tính thứ nhất thực hiện trong thời gian O(log n), và phép tính

= 1 mod n và phân loại là số
giả nguyên tố nếu đƣợc. Cũng nhƣ vậy, tuy nhiên, nó cũng kiểm tra bất thặng dƣ bậc
hai (nontrivial square root) của 1 mod n bằng cách tính a
n-1
theo một cách riêng. Đầu
tiên, nó biểu diễn n-1 = u.2
t
, u là số lẻ. Sau đó viết a
n-1
= a
u.2t
= (a
u
)
2t
đƣợc tính bằng
cách bình phƣơng liên tiến a
u
tổng cộng t lần. Thuật toán đầu tiên tính a
u
sử dụng bình
phƣơng liên tiếp (ordinary binary exponentiation), sau đó bình phƣơng nó t lần, giữ lại
giá trị hiện tại(cur) và giá trị cuối cùng (last) ở mỗi bƣớc. Nếu cur = 1, thì last là thặng
dƣ bậc hai (square root) của 1 mod n. Nếu last khác 1, hoặc -1, thì nó là bất thặng dƣ
bậc hai (nontrivial square root) của 1 mod n, và do đó n là hợp số. Nếu mr-witness(a,
n) trả về đúng (true), thì a là cơ sở cho n là hợp số.

Kiểm tra Miller-Rabin chỉ đơn giản chạy thuật toán mr-witness với k lần ngẫu
nhiên chọn gia trị a. Nếu bất kỳ giá trị nào chứng tỏ n là hợp số thì n là hợp số, ngƣợc
lại n là số nguyên tố với xác suất nào đó:

k
với độ phức tạp O(k. log n).
Vì đây là thuật toán xác suất tìm số nguyên tố tốt nhất hiện này, nên trong luận
văn này xin trình bày một số ví dụ mình hoạ

Ví dụ 1: Lấy n = 91 = 7.13, n-1=90=2
1
.45, nên s=1. Chú ý 91 là hợp số
(a). Chọn ngẫu nhiên cơ sở a=10. Bắt đầu với b=10
45
mod 91 = 90. Do đó thuật
toán kết luận là số nguyên tố. Tuy nhiên , chúng ta biết rằng 91 không phải là số
nguyên tố, vậy 10 là một cơ sở cho kết luận sai.
(b). Chọn ngẫu nhiên cơ sở a=29. Bắt đầu với b=29
45
mod 91 = 1. Do đó thuật
toán lại trả về kết quả đúng (true), và 29 cũng là một cơ sở cho kết luận sai.
(c). Cuối cùng, chọn a=2 bắt đầu với b=2
45
mod 91 = 57. Ở đây thuật toán
không thể vào vòng lặp ( bởi vì s-1=0), thuật toán đến dòng 14, và từ đây cho kết quả
sai (false).
Vậy 91 đƣợc xác định là hợp số.
Ví dụ 2: Lấy n=101, n-1=100=2
2
.25, nên s=2. Chú ý 101 là số nguyên tố
(a). Giả sử a=17, có b=100, và thuật toán kết luận là số nguyên tố.
(b). Giả sử a=19, có b=1, và thuật toán kết luận là số nguyên tố.
(c). Giả sử a=29. Có b=91, nên vào vòng lặp. Tính b=91
2
7mod1711 
vì
7.41711 

Các tính chất:
Đối với
c,b,b,a,a
11
ta có:
(1)
 
nmodba 
nếu và chỉ nếu a và b cũng có phần dƣ khi chia cho n.
(2) Tính phản xạ :
 
nmodaa 
.
(3) Tính đối xứng : Nếu
 
nmodba 
thì
 
nmodab 

(4) Tính bắc cầu : Nếu
 
nmodba 
và

modulo n. Từ các tính chất (2), (3) và (5) ở trên ta có thể thấy rằng đối với n cố định,
quan hệ đồng dƣ theo modulo n sẽ phân hoạch Z thành các lớp tƣơng đƣơng.
Nếu
rqna 
với
nr0 
thì
 
nmodra 
.
Bởi vậy mỗi số nguyên a là đồng dƣ theo modulo n với một số nguyên duy nhất
nằm trong khoảng từ 0 tới
1n
, số này đƣợc gọi là thặng dƣ tối thiểu của
nmoda
.
Nhƣ vậy a và r có thể đƣợc dùng để biểu thị cho lớp tƣơng đƣơng này.
Định nghĩa 1.8
Không gian Z
n
(các số nguyên theo modulo n) là tập hợp các số nguyên
{0,1,2,…,n-1}. Các phép toán trong Z
n
nhƣ cộng, trừ, nhân, chia đều đƣợc thực hiện
theo module n.
Ví dụ:
Z
11
= {0,1,2,3,…,10}
Trong Z


= { p

Z
n
|1<= p <= n - 1}
Ví dụ:
Z
2
= {0,1} thì Z
2
*
= {1} vì gcd(1,2)=1.

1.1.2.2 Tính phần tử nghịch đảo trong Zn *
Thuật toán tính phần tử nghịch đảo trong Z
n
*

Vào :
n
Za

Ra :
nmoda
1
(nếu tồn tại).
(1) Dùng thuật toán Euclide mở rộng để tìm các số nguyên x và y sao cho
dnyax 
trong đó

t
i
kkk
t
i
i
k
k
aaaaa
222
0
2
1
1
0
0


1.1.2.3 Tính luỹ thừa trong Zn
Thuật toán nhân và bình phương có lặp để tính luỹ thừa trong Z
n
.
Vào :
n
Za
và số nguyên
 

thì đặt
ab 
.
(4)
dotto1fromiFor

4.1. Đặt
nmodAA
2

.
4.2. Nếu
1k
i

thì đặt
nmodb.Ab 

(5) Return (b)
Ví dụ: Bảng 2.2.1 sau chỉ ra các bƣớc tính toán
10131234mod5
596


i
0
1
2
3
4

1
1
625
625
67
67
1059
1059
1059
1013
Bảng 2.2.1: Tính
1234mod5
596Số các phép toán bit đối với phép toán cơ bản trong
n
Z
đƣợc tóm lƣợc trong
bảng 2.2.2.
Phép toán
Độ phức tạp bit
Cộng module
ba 

 
nlg0

Trừ modulo
ba 


Bảng 2.2.2: Độ phức tạp bit của các phép toán cơ bản trong
n
Z1.2. MỘT SỐ KHÁI NIỆM TRONG ĐẠI SỐ
1.2.1. Khái niệm: Nhóm, Vành, Trƣờng
1.2.1.1 Nhóm
Nhóm là cấu trúc bao gồm tập G và toán tử hai ngôi * trên G.
Với a, b

G, a * b

G đƣợc định nghĩa nhƣ sau:
(1) Tính chất kết hợp: a * (b * c) = (a * b) * c với mọi a, b, c

G
(2) Tồn tại phần tử trung hòa e

G thỏa mãn e * a = a * e = a với mọi a

G.
(3) Tồn tại phần tử nghịch đảo: Với mỗi a

G, tồn tại duy nhất phần tử b

G thỏa mãn
b * a = a * b = e
Ký hiệu


G là số
nguyên dƣơng nhỏ nhất m thỏa mãn a
m
= 1. Trong nhóm nhân, với mọi phần tử thuộc
nhóm, m luôn tồn tại.
Định lý 1.10
,*G
là nhóm nhân hữu hạn bậc n. Nếu bậc của phần tử a

G là m thì
a
k


1 khi và chỉ khi m|k
Chứng minh
Nếu k = mq, thì a
k
= (a
m
)
q
=1. Ngƣợc lại, k = mq + r,
mr 0
.
Khi đó a
r
= a
k


Ví dụ, tập hợp Z
n
= {0, 1, 2,…, n – 1} là một nhóm cylic bậc n với toán tử cộng
modulo n.
Định lý 1.11 (Euler)
Với a, m

Z thỏa mãn gcd(a, m) = 1,
1
)(

 m
a
mod m
Chứng minh
Theo định lý 1.1 G
m
= {a

Z
m
| gcd(a, m) = 1} tạo thành nhóm nhân bậc ф(m).
Định lý 1.12 (Fermat)
Cho p là số nguyên tố và a

Z. Khi đó, ta có:
(1) a
p-1


0 } là một nhóm nhân.
Định lý 1.13
Vành Z
p
là một trƣờng khi và chỉ khi p là số nguyên tố.
Chứng minh
Với a, b

Z, ta có: p là số nguyên tố

p|ab tức là p|a hoặc p|b
Nếu Z
p
là trƣờng thì
*
p
Z
tạo thành nhóm nhân. Nếu p a thì a

0 mod p.
Điều này nghĩa là a
*
p
Z
và tồn tại a
-1
. Do đó nếu p|ab và p a thì p|(ab)
-1
= b.
Vậy p là số nguyên tố.