MỤC
LỤC
LỜI MỞ
Đ
Ầ
U
1
Chương 1. CÁC KHÁI NIỆM CƠ BẢN
2
1.1. KHÁI NIỆM TRONG SỐ
H
Ọ
C
2
1.1.1.
Ƣớc
chung lớn nhất và bội chung
nhỏ
nh
ấ
t
2
1.1.1.1. Khái niệm 2
1.1.1.2. Tính
chất
2
1.1.2. Quan
hệ đồng
dƣ
3
1.2.4. Không gian vector 11
1.3. KHÁI NIỆM TRONG MẬT
MÃ
12
1.3.1. Một
số
khái
niệm
12
1.3.1.1. Khái niệm Mã hóa dữ
liệu
12
1.3.1.2.
Lƣợc đồ
chữ ký
số
12
1.3.1.3.
Hàm
bă
m
13
1.3.2. Một
số
thuật ngữ liên quan 14
1.4. GIỚI THIỆU VỀ CHỮ KÝ
S
Ố
15
1.4.1. Quy trình tạo và
tra chữ
ký
21
2.1.4. Độ an toàn của
hệ
mã hóa
RSA
21
2.2. LƢỢC ĐỒ CHỮ
KÝ
CƠ SỞ DỰA TRÊN HỆ MẬT
RSA
21
2.2.1.
Lƣợc đồ
chữ ký
cơ sở
21
2.2.1.1. Hình thành tham
số hệ thống
và khóa 21
2.2.1.2 Tạo chữ ký và
kiểm
tra chữ ký 22
2.2.2. Tính
đúng đắn của lƣợc đồ
chữ ký
cơ
sở 23
2.2.3. Mức
Lƣợc đồ
chữ ký bội song song 28
2.3.2.1. Hình thành các tham
số
hệ thống và
khóa
28
2.3.2.2. Chứng nhận và
kiểm
tra tính hợp pháp
của các
đ
ố
i
tƣợng ký
28
2.3.2.3. Hình thành và
kiểm
tra chữ ký bội song song 28
Chương 3. CHỮ KÝ BỘI TRÊN
ĐƢỜNG
CONG
ELLIPTIC
30
3.1. CÁC KHÁI NIỆM VỀ
ĐƢỜNG
CONG
ELLIPTIC
30
“tựa”
Elgamal
35
3.2.2.2. Hệ mã hóa
Menezes-Vantone
35
3.2.3.
Trao đổi
khóa Diffie –
Hellman trên đƣờng
cong Elliptic 36
3.2.3.1.
Mô hình trao đổi
khóa Diffie –
Hellman.
36
3.2.3.2.
Mô hình trao đổi
khóa Elliptic Curve Diffie – Hellman 36
3.2.4. Lựa
chọn đƣờng
cong Elliptic phù
hợp
36
3.3. CHỮ KÝ BỘI MÙ TRÊN
ĐƢỜNG
CONG ELLIPTIC 40
3.3.1. Sơ
đồ
chữ ký
Lƣợc đồ
chữ ký bội tuần tự 47
3.3.4. Sơ
đồ
chứ ký bội mù Harn trên
ECC
50
3.3.4.1. Sinh khóa 50
3.3.4.2. Ký mù trên
m
50
3.3.4.3. Chứng minh 50
Chương 4. ỨNG DỤNG VÀ THỰC NGHIỆM 52
4.1. ỨNG DỤNG CHỮ KÝ BỘI TRONG KÝ KẾT HỢP ĐỒNG 52
4.1.1. Bài toán
bảo đảm
tính toàn vẹn thông tin
hợp đồng
(biên bản) 53
4.1.2.
Bảo đảm
tính xác
thực
55
4.1.3.
Chống
chối
bỏ hợp đồng
giao
d
TRÌNH.
62
4.2.4.1. Sinh tham
số hệ
thống 62
4.2.4.2. Tạo chữ ký
bội
62
4.2.4.3.
Kiểm
tra chữ ký
bội
62
KẾT LUẬN 63
TÀI LIỆU THAM KHẢO 64
BẢNG CHỮ VIẾT TẮT, KÝ
HI
Ệ
U
gcd(a, b)
Ƣớc số
chung lớn nhất của a và b
lmc(a, b) Bội
số
chung
nhỏ
nhất của a và b
H(.)
Sử dụng
hàm
Khóa công khai của thực
thể
cuối U
i
CA
Cơ
quan chứng
thực
#E
Số
phần tử
của đƣờng
cong Elliptic
ECC
Hệ
mật trên đƣờng
cong Elliptic
DLP
Bài toán Logarith rời rạc
ECDSA Thuật toán ký trên
đƣờng
cong Elliptic
ECDLP
Bài toán Logarith rời
rạc trên đƣờng
cong Elliptic
ECDH
Trao đổi
khóa Elliptic Curve Difie - Hellman
sig
cộng hai điểm
P + Q =
R
31
Hình 3.2 Phép
cộng
P với chình nó P+P = 2P = R 32
Hình 4.1 Mẫu biên bản thỏa thuận kinh
doanh
53
Hình 4.2 Mẫu phiếu xuất kho 54
Hình 4.3 Cấu trúc cặp khóa bí mật công khai (d, e) của CA 58
Hình 4.4 Khóa bí mật công khai của
những ngƣời ký
59
Hình 4.5 Sinh tham số
hệ
th
ố
ng
60
Hình 4.6 Giao diện tạo tham
số
hệ
th
ố
ng
61
Hình 4.7 Giao diện tạo chữ ký
bội
trong đó
có Việt Nam, thì chữ ký số không thể
thiếu
đƣợc
và ngày càng trở nên quan trọng. Các mô hình ứng dụng chữ ký số cho
phép
đáp ứng tốt các yêu cầu về chứng thực nguồn gốc hay hiệu lực của
thông
tin
đƣợc
tạo ra bởi những thực thể có
tính
độc lập.
Nhƣng trong trƣờng
hợp
thông
t
i
n
đƣợc
tạo ra từ các thành viên hay bộ phận của một tổ chức thì nguồn gốc hay hiệu lực
thông tin ở cấp độ thành viên hay bộ phận lại
không đƣợc
chứng thực, trong khi, các
yêu cầu chứng thực đó lại ngày càng trở nên thực tế và cần
thiết.
Tr
ƣ
ớ
c
chữ ký bội RSA , chữ ký bội
trên
đƣ
ờ
ng
cong Elliptic và ứng dụng
của chúng, sau đó
là
phần
thử
nghiệm
ch
ƣ
ơng
trình.
Cuối cùng
là phần kết luận và tài liệu tham khảo.
Mặc
dù đã
cố gắng hết sức,
nhƣng
vẫn không sao tránh khỏi sai sót, vì vậy rất mong
đƣợc
sự góp ý phê bình.
2
Chương 1. CÁC KHÁI NIỆM CƠ
B
Ả
N
đƣợc
gọi là bội chung của các số nguyên a
1
, a
2
,
…,
a
n
, nếu nó là bội
của tất cả các
số
đó.
Một
ƣ
ớ
c
chung d >0 của các số nguyên a
1
, a
2
,
…,
a
n
,
trong đó
mọi
ƣ
ớ
,
…,
a
n
) hay d = UCLN(a
1
, a
2
,
…,
a
n
).
Nếu gcd(a
1
, a
2
,
…,
a
n
) = 1, thì a
1
, a
2
,
…,
a
n
đƣợc
…,
a
n
.
Ký hiệu m = lcm(a
1
, a
2
,
…,
a
n
) hay m = BCNN(a
1
, a
2
,
…,
a
n
).
Ví dụ:
Cho a = 12, b = 15, gcd(12,15) = 3, lcm(12,15) = 60.
Hai
số
8 và 13 là nguyên tố cùng nhau, vì gcd(8,13) = 1.
1.1.1.2. Tính chất
1. d = gcd(a
1
, a
…,
a
n
nguyên t
ố
cùng
nhau
⇔
t
ồ
n
t
ạ
i x
1
, x
2
,
…,
x
n
sao cho:
1 = a
1
x
1
+ a
2
x
2
a
n
)
⇔
gcd(m/a
1
, m/ a
2
,
…,
m/a
n
)
= 1.
4. gcd(m a
1
, m a
2
,
…,
m a
n
) = m* gcd(a
1
, a
2
,
…,
a
n
số dƣ
là 2.
1.1.2.2. Tính chất
1/. Quan
hệ “đồng dƣ”
là
quan hệ tƣơng đƣơng trong
Z
:
Với mọi
số nguyên dƣơng m ta
có:
a (mod m) với mọi a ; (tính chất phản xạ)
a (mod m) thì b
(mod
m);
(tính chát đối
xứng)
a (mod m) và b (mod m) thì a (mod m); (tính chất bắc cầu)
2/.
Tổng
hay
hiệu các “đồng
dƣ
”:
(a+b) (mod n) [(a mod n) + (b mod n)] (mod n)
(a- b) (mod n) [(a mod n) - (b mod n)] (mod n)
Tổng quát:
Có thể cộng hoặc trừ từng vế
nhiều đồng dƣ theo cùng một
Có thể nhân từng về
nhiều đồng dƣ thức
theo cùng một modula m,
ta đƣợc một
đồng
dƣ thức
theo cùng modulo m, tức là:
N
ế
u a
i
b
i
(mod m) v
ới i
=
1…k,
th
ì
ta
có:
∏
=
∏
(mod m)
4
1.1.3.
Số
nguyên t
yê
n t ố l ớn đã
đ
ƣ
ợ
c
t ì m t
h
ấ
y
1/. Định lý:
về số nguyên dƣơng >
1
Mọi
số nguyên dƣơng
n
>
1
đều
có
thể
biểu
diễn đƣợc
duy nhất
dƣới
dạng:
n = = = ,
trong
Chứng minh
Bằng phản chứng, giả sử k không là
số
nguyên tố. Khi
đó
k
= a.b
với 1 < a,b < k.
Nhƣ
vậy: p = 2
k
- 1 = 2
ab
– 1 = (2
a
)
b
– 1 = (2
a
– 1).E
(Trong đó
E là
một
biểu thức nguyên – áp dụng công thức nhị thức Niu-tơn).
Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử sai, hay k là
số
nguyên
tố.
3/. Hàm Euler:
Cho số
*
=
{1, 2, 3, 4, 5, 6, 7}. Khi
đó
|Z| =
( )
= p-1 = 8
–
1 = 7.
Định lý hàm Euler:
N
ế
u n là tích c
ủ
a hai s
ố
nguyên t
ố
n = p.q, thì (n) =
( ) ( )
= (p
–
1).(q -1).
1.1. KHÁI NI
Ệ
M TRO
NG ĐẠ
I S
Ố
1.2.1. Nhóm
là nhóm giao
hoán, có phần tử
đơn
vị là số 0. Gọi là nhóm cộng các
số
nguyên.
- Tập Q
*
các số hữu tỷ khác 0 (hay tập R
*
các số thực khác 0), cùng với phép nhân
(*)
thông thƣờng
là nhóm giao hoán. Gọi là nhóm nhân các
số
hữu tỷ
(số
thực) khác 0.
-
Tập các vectơ trong không gian
với phép toán
cộng vectơ
là
nhóm giao
hoán.
Z
n
1.2.1.2. Nhóm Cyclic
Nhóm (G, *)
đƣợc
khác: G
đƣợc
gọi là Nhóm Cyclic nếu tồn tại g G sao cho mọi phần tử trong G
đều
là
một lũy thừa nguyên
nào đó
của g.
Nhóm (Z
+
, +)
gồm
các
số nguyên dƣơng
là Cyclic với phàn tử sinh g = 1.
Cho (G, *) là Nhóm Cyclic với phần tử sinh g và phần tử trung lập e.
Nếu tồn tại số tự nhiên nhỏ nhất n mà g
n
= e, thì G sẽ chỉ gồm có n phần tử
khác nhau: e, g, g
2
, g
3
,…,
g
n-1
.
Khi
đó
G
n
*
= {x Z
n
, x là
số
nguyên
tố
cùng nhau với n}. Tức là x phải 0.
*
Z
n
đƣợ
c
g
ọ
i là Tập thặng dư thu gọn theo mod n, có
s
ố
ph
ầ
n t
ử
(n).
*
với phép nhân mod n lập thành một nhóm (nhóm nhân), phần tử trung lập e = 1.
l
ẻ
.
Tổng
*
(tức b guyên tố với p),
thì
( )
(mod n), hay b
p
–
1
(mod n).
1.2.1.4. Phần tử nghịch đảo đối với phép nhân
* Định nghĩa
Cho a Z
n
, nếu tồn tại b Z
n
sao cho a b 1(mod n), ta nói b là phần tử nghịch
đảo của a trong Z
n
và kí hiệu a
-1
Một phần tử có phần nghịch
đảo,
gọi là khả nghịch.
* Định lý:
UCLN(a,n) = 1
⇔
Ph
ầ
n t
ử
có phần tử nghịch đảo.
1.2.2. Vành
Vành là một tập R với toán tử + và . với
các điều
kiện sau:
(R, +) là một nhóm Abel
a.(b.c) = (a.b).c với mọi a, b, c R.
a.(b+c) = a.b + a.c và (a+b).c = a.c + b.c với mọi a, b, c R.
Vành
tuyến
tính
F là một vành.
Một đa thức
bậc n trên F có dạng:
( ) ∑
= a
0
+ a
1
x
+
…
+
a
n
x
n
v
ớ
i n là
a
( )
và g(x) là
( ) ( )
∑
( )
Cho
2
đa thứ
c
( ) ∑
và g(x) =
∑
Ta định nghĩa
tích c
ủ
a
( )
và g(x) là
( ) ( )
∑
( )
v
ớ
i
c
k
=
∑
(0 )
Giả sử
( )
và
( )
,
-
có bậc
nguyên
dƣ
ơng
,
tồn
tại duy
nhất đa thức
q(x),
r(x)
,
-
thỏa mãn
( ) ( ) ( ) ( )
với bậc của
( )
nhỏ hơn bậc
c
ủ
a
(
)
Nếu
của
( )
,
-
nếu
( )
= 0.
Hệ quả
Một phần tử a là nghiệm
của đa
thức
( )
,
- khi và chỉ khi là
ƣ
ớ
c
của ( ) trong
,
-
Chứng minh
Vì là nghiệm nên ( ) = 0. Vì
(
)
( ) ( )
( ) nên bậc
của ( ) nhỏ hơn
1,
tức
ấ
t
nghi
ệ
m
trong
1.2.3.
Trƣờ
ng
Trƣờ
ng là m
ộ
t vành v
ớ
i ph
ầ
n t
ử
đơn
vị
sao cho
* |
+
là m
ộ
t
nhóm nhân.
Định lý
Vành là
một trƣờng
t nhóm nhân. N
ế
u thì
Điề
u
này
nghĩa
là
và t
ồ
n t
ạ
i
. Do
đó
nế
u
|
và thì
|
( )
V
ậ
y là
s
ố
nguyên t
ố
.
Ngƣợc
i ph
ầ
n t
ử
1
trong .
V
ậ
y m
ỗ
i luôn có ph
ầ
n t
ử
ngh
ịch đả
o.
Định nghĩa
là
một trƣờng.
Một tập con của
cũng
là
một trƣờng
với các toán t
ử
đƣợc
gọi là
trƣờng
con của . Hay
con.
Trƣờng
đƣợc
gọi là
có đặc
số p nếu .
Trƣờng
hữu
hạn
là
trƣờng
chứa hữu hạn các phần tử. mọi
trƣờng
hữu hạn có một số
nguyên tố là đặc số của
trƣờng. Một
tr
ƣ
ờ
ng
có đặc số thì với mọi
⏞
Định nghĩa
Trƣờ
ng v
ớ
i ph
ầ
n t
ử
c R,
s
ố
ph
ức C
có đặ
c s
ố
là 0)
Với là
số
nguyên
tố
thì GF(p
n
)
có đặc số
p.
Nếu
H là
trƣờng
con
của
K
thì
H và K
có cùng đặc
số.
F là
trƣờ
a . N
ếu F là
trƣờ
ng
h
ữ
u h
ạn đặ
c s
ố
p thì nhóm nhân F
*
=F\{0} là nhóm
cyclic và F = Z
p
( ) với là phần tử sinh của nhóm F
*
và
đƣợc
gọi là phần tử nguyên
thủy của F.
Với 2 toán tử nhị nguyên * và trên các tập A và B, một ánh xạ : A → B nếu với
m
ọ
i ta có:
( ) ( ) (
)
Gi
ả
s
F là
trƣờng
mở rộng bậc n
trên trƣờng
hữu hạn K. Nếu K có q phần tử thì F có q
n
phần tử.
Chứng minh
Giả sử { } là cơ sở của F
nhƣ
là
một
không gian vector trên K. Mọi
s
ẽ
có d
ạ
ng
trong
đó
( )
Vì m
ố
i c
i
có th
ể
là
m
ộ
dƣ
ơng.
Vì vậy, mọi
trƣờng
hữu hạn là một mở
rộng của trƣờng đẳng
cấu Z
p
với
p
là
đặc
số
của F. Định lý
Trƣờng
hữu hạn là
một trƣờng
mở rộng của Z
p
bậc n và mọi phần tử của
là một
nghiệm của đa thức
trên Z
p
.
Chứng minh
Đặc số của là p. Tập hợp F* = F \ {0} tạo thành nhóm nhân bậc p
n
– 1. Với
, bậc của trong nhóm chia hết cho bậc của F*, p
ng
c
ủ
a k F
2
và v F
2
.
Khi đó
đƣợ
c
xem là không gian vector trên F
2
v
ớ
i chi
ề
u r. Ký hi
ệ
u d là chi
ề
u c
ủ
a không gian
vector này. Có thể thực hiện ánh xạ 1 – 1 giữa các phần tử trong không gian vector d
chiều và các d-tuple của các phần tử trong F
2
. Vì vậy, có 2
d
phần tử trong không gian
a (không gian vector trên F
q
) c
ủ
a
{ }gồm và các liên hợp của nó với F
q
,
đƣợc
gọi là cơ sở
trực giao của trên F
q
. Mọi
trƣờng
mở rộng bậc hữu hạn của
một
tr
ƣ
ờ
ng
hữu hạn có
một cơ sở
trực giao.
Không gian
chi
ế
u
Xét L = K
n+1
\{0} với K là
=
0, 1,
…,
n).
Quan hệ ~ là quan hệ
tƣơng đƣơng
và
đ
ị
nh
nghĩa một
phân hoạch của L.
Tập
thƣ
ơng
số
là không gian chiếu ký hiệu là
P
n
(K).
Mặt phẳng chiếu là tập các lớp
tƣơng đƣơng
của bộ ba (X, Y, Z) với
( ) ( )( )
. M
ỗ
i l
ớp
tƣơng đƣơng
t th
ể
hi
ệ
n
của
lớp tƣơng đƣơng
với x = , y = . Mặt phẳng chiếu có thể
đƣợc
đ
ị
nh
nghĩa
là
tập
tất
cả
các điểm
(x, y) của mặt phẳng Affine
cộng
với
các điểm
Z = 0.
1.2.4. Không gian vector
K là
một trƣờng
và V là một nhóm
cộng
Abel. V
n t
ử
c
ủa
K
đƣợ
c
g
ọ
i là các vô
hƣớng.
V là
một không gian vector trên trƣờng
K và các v
1
,
…,
v
m
V. Vector trong V
có dạng với c
i
K (i
=
1,
…,
m) là
một
tổ hợp tuyến tính của
v
).
V là
không gian vector trên trƣờng
K. Các vector v
1
,
…,
v
m
V
đƣợc
gọi là
độc lập
tuyến
tính trên K
nếu không có các
vô
hƣớng
c
1
,
…,
c
m
K thỏa mãn:
Tập S = {u
1
, u
2
,…,u
một trƣờng
mở rộng của
trƣờng
K thì F là một không gian vector trên K.
Chiều của
F
trên
K
đƣợc
gọi là bậc mở
rộng
của F trên K.
1.3.
KHÁI NIỆM TRONG MẬT MÃ
1.3.1.
Một số
khái ni
ệ
m
1.3.1.1. Khái niệm Mã hóa dữ liệu
Để
đảm bảo
An
toàn thông
tin
(ATTT)
lƣu
trữ trong máy tính (giữ gìn thông tin
cố định) hay đảm bảo ATTT trên
đƣờng
D, d
k
: C → P thỏa mãn: d
k
(e
k
(x)) = x, x P.
1.3.1.2. Lược đồ chữ ký số
Lƣợc đồ
chữ ký
số
là
bộ năm
(M, S, K, A, V), thỏa
mãn:
M là một tập hữu
hạn các thông điệp
dữ liệu.
S là một tập hữu hạn các chữ ký.
K là tập hữu hạn các khóa bí mật.
A là tập hữu hạn các thuật toán ký.
V là tập hữu hạn các thuật toán xác minh.
Đối với mỗi k K có một thuật toán ký sig
k
A, sig
k
: M → S và một thuật toán
xác
minh tƣơng
ứng ver
cố định.
Miếng băm mới tạo
ra
thƣờng có
kích
thƣ
ớ
c
nhỏ hơn
rất nhiều so với
bản tin ban
đầu.
Một giá trị
miếng băm
h
đƣợc
sinh ra bởi
hàm băm
H có
d
ạ
ng
:
h
=
H(M)
trong đó:
M là bản tin có
chiều
dài tùy ý, h là giá trị
ị
nh
nhƣng
với h cho
trƣớc
thì việc tính x cực kỳ
khó
khăn.
- Với hai giá trị
đầu
vào thì H(x)
≠
H(
y
)
Hiện nay, một số kỹ
thuật
băm
đƣợc
sử dụng phổ biến
nhƣ
:
SHA-1, SHA-256,
SHA-384, SHA-512; MD-4, MD-5…Tuy
nhiên chƣơng
trình thử nghiệm sẽ tập trung
nghiên
cứu
và cài
một nhóm
đối
tƣợng)
nhằm chứng thực nguồn gốc hay hiệu lực của
thông điệp
dữ liệu của thực
thể
đó.
Chữ ký bội
đƣợc
tạo nên từ nhiều chữ ký đơn
cũng nhằm
chứng thực nguồn gốc
hay hiệu lực
của thông điệp
dữ liệu.
Cơ quan chứng thực – CA (Certification Authority) là một thực thể cung cấp chứng
chỉ số.
H
ì
n
h 1.1
C
ác chức
năng
c
ủa hệ
th
ố
ký điện tử
Bƣớc đầu
tiên của quá trình tạo chữ ký là tạo giá trị
băm
của
thông
điệp
dữ liệu
cần gửi. Các
hàm băm
có
thể
sử dụng là MD2, MD4, MD5, SHA-1, SHA-256…
K
ế
t quả
thu đƣợc
là một tóm
tắt thông
điệp dữ liệu (message digest) có chiều
dài cố định, nhỏ
hơn
rất nhiều
thông
điệp dữ liệu
ban đầu.
Theo tính chất của
hàm
băm, xác
suất để
điệp dữ liệu ban đầu (ký) và truyền đến
ngƣời
gửi trên
môi
trƣ
ờ
ng
mạng.
1.4.1.2. Quy trình kiểm tra một chữ ký
số:
H
ì
n
h 1.3
Q
u
y t
r
ì nh
k
i ểm t ra chữ số ký
s
ố
Tính toán giá trị
băm hiện
thời
Sau khi
nhận đƣợc thông điệp
đƣợc
gọi là giá trị
băm hiện
thời vì
nó đƣợc
tính từ
thông điệp
dữ liệu
hiện thời.
Tính toán giá trị
băm ban
đầu
Trong bƣớc
thứ hai của quá trình giải mã, chữ ký số
đính kèm đƣợc
giải mã bằng
khóa công
khai
(public
key)
tƣơng
ứng với khóa bí
mật (private
key)
dùng để
tạo
chữ ký ở bên gửi. Kết quả
thu đƣợc
giá trị
băm ban
dữ
liệu cũng không
bị
thay đổi
trong quá trình
truyền
đi.
• Nếu hai giá trị
băm không
trùng: quá trình xác thức thất bại,
có hai trƣờng
hợp mất
an toàn đã
xảy ra:
- Khóa bí mật
của ngƣời
gửi
không đƣợc
sử dụng khi tạo chữ ký.
-
Thông điệp
dữ
liệu đã thay đổi
trong quá trình
truyền
đi.
Copyright: Tài liệu đại học ©