Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm
và ứng dụng trong giao
dịch điện tử
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
1
LỜI NÓI ĐẦU
Trong xu hướng phát triển của thế giới và Việt Nam hiện nay, mạng Internet đang
đem đến sự bùng nổ thông tin một cách mạnh mẽ. Nó được sử dụng để truyền thư điện
tử, truy cập các website, kết nối các công sở, liên lạc với các khách hàng và sử dụng
các dịch vụ ngân hàng, các giao dịch điện tử…
Tiềm năng của mạng Internet là rất lớn. Như ta đã biết các giao tiế
p, trao đổi thông
tin qua Internet đều sử dụng giao thức TCP/IP. Các gói tin truyền từ điểm nguồn tới
điểm đích sẽ đi qua rất nhiều máy tính trung gian, vì vậy độ an toàn thấp, nó rất dễ bị
xâm phạm, theo dõi và giả mạo trên đường truyền. Vấn đề không an toàn cho thông tin
trên đường truyền khiến nhiều người đắn đo trong việc sử dụng mạng Internet cho
những ứng dụng về tài chính, giao dịch ngân hàng, hoạt
động mua bán và khi truyền
các thông tin kinh tế, chính trị vv…
2
Chương I
CÁC KHÁI NIỆM CƠ BẢN
1.1 Cơ sở toán học
1.1.1. Ước số - Bội số
Định nghĩa : Ước số của a và b là c nếu c|a và c|b
Ước số chung lớn nhất : Là số lớn nhất mà a và b chia hết
Ký hiệu : c = gcd (a,b) ; (great common divisor)
Bội số chung nhỏ nhất : d là BCNN của a và b nếu
∀
c mà a|c , b|c → d|c
Ký hiệu : d = lcm (a,b) ; (least common multiple)
Tính chất: lcm (a,b) = a.b/gcd(a,b)
1.1.2. Số nguyên tố
Định nghĩa : Số nguyên tố là số chỉ chia hết cho 1 và chính nó, ngoài ra không còn
số nào nó có thể chia hết nữa. Hệ mật thường sử dụng số nguyên tố lớn cỡ 512bits và
thậm chí còn lớn hơn nữa.
Hai số m và n gọi là hai số nguyên tố cùng nhau khi ước số chung lớn nhất của
chúng bằng 1. Chúng ta có thể viết như sau:
UCLN(m,n) = 1
1.1.3. Khái niệm nhóm
Định nghĩa : Nhóm là b
ộ đôi (G,
∗
), trong đó G là tập
φ
≠
và
a * b = b * a
∀
a, b
∈
G
1.1.4. Nhóm hữu hạn
Định nghĩa : Nhóm (G,
∗
) hữu hạn nếu |G| là hữu hạn. Số các phần tử của nhóm G
được gọi là cấp của nhóm.
Ví dụ :
Tập các số nguyên Z với phép cộng sẽ tạo nên một nhóm. Phần tử đơn vị
của nhóm này được kí hiệu là 0, phần tử ngược của một số nguyên a là
số nguyên –a.
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
3
Tập Z
n
với phép cộng modulo tạo nên một nhóm cấp n. Tập Z
n
với phép
toán nhân theo modulo n không phải là một nhóm vì không phải mọi
phần tử của nhóm đều có nghịch đảo. Tuy nhiên tập Z
*
n
sẽ là một nhóm
cấp
φ
Phép toán Độ phức tạp bit
Cộng a + b
Trừ a – b
Nhân a * b
Chia a = qb + r
0(lg a + lg b) = 0 (lg n)
0(lg a + lg b) = 0 (lg n)
0
(
)
b) (lg*a) (lg
= 0
(
)
n)2 (lg
0
(
)
b) (lg*a) (lg
= 0
(
)
n)2 (lg
1.1.8. Thuật toán Euclide : Tính UCLN của 2 số nguyên
VÀO : Hai số nguyên không âm a và b với a > b
RA : UCLN của a và b
(1). while b
≠ 0 do
2
– qx
1
, y
← y
2
– qy
1
2. a
← b, b ← r, x
2
← x
1
, x
1
← x, y
2
← y
1
, y
1
← y
(4) Đặt d ← a, x ← x
2
, y ← y
2
và return (d, x, y)
1.1.10. Định nghĩa hàm Φ Euler
Định nghĩa : Với n≥1 chúng ta gọi
⎠
⎞
⎜
⎜
⎝
⎛
−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
k
ppp
1
1
1
≡
a
1
+b
1
(mod n)
a.b ≡ a
1
.b
1
(mod n)
1.1.12. Số nghịch đảo
Định nghĩa : Cho a ∈ Z
n
. Một số nguyên x ∈ Z
n
gọi là nghịch đảo của a theo mod n
nếu a.x ≡ 1mod n
Nếu có số x như vậy thì nó là duy nhất và ta nói a là khả nghịch. Ký hiệu là a
-1
. Có
thể suy ra rằng a khả nghịch theo mod n khi và chỉ khi gcd (a,n)=1.
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
5
1.1.13. Nhóm nhân Z*n
Định nghĩa : Nhóm nhân của Z
n
ký hiệu là Z
hai được kí hiệu là
n
Q
.
1.1.15. Phần dư China CRT ( Chinese Remainder Theorem)
Nếu các số nguyên n
1
, n
2
, …, n
k
là nguyên tố cùng nhau từng thì hệ các phương
trình đồng dư:
x ≡ a
1
(mod n
1
)
x ≡ a
2
(mod n
2
)
………………
x ≡ a
k
(mod n
k
)
sẽ có nghiệm duy nhất theo modulo n (n = n
(
)
)2n (lg
các phép toán trên bit.
Ví dụ :
Cặp phương trình đồng dư
x ≡ 5 (mod 9)
x ≡ 19 (mod 23) có nghiệm duy nhất x ≡ 203 (mod 207)
Tính chất
Nếu (n
1
, n
2
) = 1 thì cặp phương trình đồng dư
x ≡ a (mod n
1
), x ≡ a (mod n
2
)
có một nghiệm duy nhất x ≡ a (mod n
1
, n
2
)
1.1.16. Độ phức tạp tính toán
Lý thuyết thuật toán và các hàm số tính được ra đời từ những năm 30 của thế kỉ 20
đã đặt nền móng cho việc nghiên cứu các vấn đề “ tính được ”, “ giải được ” trong toán
học. Tuy nhiên từ các “ tính được ” đến việc tính toán thực tế là một khoảng cách rất
lớn. Có rất nhiều vấn đề chứng minh là có thể tính được nhưng không tính được trong
có thể được tính bằng cách dùng thuật toán Euclide mở rộng được
mô tả dưới đây:
1.1.18. Thuật toán ( Tính các nghịch đảo trong Zn )
VÀO : a ∈ Z
n
RA : a
-1
mod n (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 ax + ny = d trong đó d = (a, n)
2. Nếu d >1 thì a
-1
mod n không tồn tại. Ngược lại return (x)
Phép lũy thừa theo modulo có thể được thực hiện có hiệu quả bằng thuật toán nhân
và bình phương có lặp. Đây là một thuật toán rất quan trọng trong nhiều thủ tục mật
mã. Cho biểu diễn nhị phân của a là :
∑
=
t
i 0
k
i
2
i
trong đó mỗi k
i
∈ {0, 1} khi đó
a + b với a + b < n
a + b – r.n với a + b ≥ n
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
0
Thuật toán nhân và bình phương có lặp để lấy lũy thừa trong Z
n
VÀO : a ∈ Z
n
và số nguyên k, (0
≤
k < n) có biểu diễn nhị phân :
k =
i
t
i
i
k 2
0
∑
=
RA : a
k
mod n
1. Đặt b ← l. Nếu k = 0 thì return (b)
2. Đ
ặt A ← a
3. Nếu k
0
= 1 thì đặt b ← a
Lũy thừa modulo
0
(
)
3
)(lg n
Độ phức tạp bit của các phép toán cơ bản trong Z
n
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
8
1.1.19. Hàm một phía - Hàm một phía có cửa sập
Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhưng rất khó
để tính ngược lại.
Ví dụ :
Biết giả thiết x thì có thể dễ dàng tính ra f(x), nhưng nếu biết f(x) thì rất khó
tính ra được x. Trong trường hợp này khó có nghĩa là để tính ra được kết quả thì phải
mất rất nhiều thời gian để tính toán.
F(x) được gọi là hàm một phía có cửa sập nếu tính xuôi y = f(x) thì dễ nhưng tính
ngược x =f
1−
(y) thì khó tuy nhiên nếu có “ cửa sập ” thì vấn đề tính ngược trở nên dễ
dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính ngược.
Ví dụ :
y = f(x) = x
b
mod n tính xuôi thì dễ nhưng tính ngược x = y
a
9
Sơ đồ khối một hệ truyền tin mật
Định nghĩa : Một hệ mật mã là một bộ năm (P, C, K, E, D) thoả mãn các điều kiện
sau đây:
+ P là một tập hữu hạn các bản rõ.
+ C là một tập hữu hạn các bản mã.
+ K là một tập hữu hạn các khoá.
+ Với mỗi k ∈ K, có một hàm lập mã e
k
∈ E
e
k
: P
→ C
và một hàm giải mã d
k
∈ D
d
k
m
ã
K
D
K
E
B A
Bản rõ
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
10
Các đặc điểm của hệ mã cổ điển
1. Các phương pháp mã hóa cổ điển đòi hỏi người mã hóa và người giải mã phải
có cùng chung một khóa.
2. Khóa phải được giữ bí mật tuyệt đối, khóa phải được gửi đi trên kênh an toàn.
Vì dễ dàng xác định một khóa nếu biết khóa kia.
Nhược điểm chính của phương pháp này là khóa được truyền trên kênh an toàn nên
chi phí tốn kém và không kịp thời.
Ưu điểm là tốc độ mã hóa và giải mã rất nhanh.
Các hệ mật mã cổ điển cũng dùng chung một khoá cho việc lập mã và giải mã, các
bản rõ và bản mã thường dùng cơ sở là bảng chữ cái trong ngôn ngữ tự nhiên. Và
trong phần này ta sẽ dùng bảng chữ cái tiếng Anh làm ví dụ.
Nơi ứng dụng
Hệ mã cổ điển thường được sử dụng trong môi trường mà khóa có thể dễ dàng trao
chuy
ển bí mật. Nó cũng được dùng để mã hóa thông tin khi lưu trữ trên đĩa.
1.2.1.1. Mã dịch chuyển
Định nghĩa : Mã dịch chuyển: (P, C, K, E, D)
P = C = K = Z
2
để nhận được bản rõ.
Cách đây 2000 năm mã dịch chuyển đã được Julius Ceasar sử dụng, với khoá k=3
mã địch chuyển được gọi là mã Ceasar.
Tập khoá phụ thuộc vào Z
m
với m là số khoá có thể.
Trong tiếng Anh tập khoá chỉ có 26 khoá có thể, việc thám mã có thể được thực
hiện bằng cách duyệt tuần tự 26 khoá đó, vì vậy độ an toàn của mã dịch chuyển rất
thấp.
1.2.1.2. Mã thay thế
Định nghĩa Mã thay thế: (P, C, K, E, D)
P = C = Z
26
, K = S (Z
26
) Với mỗi π є K, tức là một hoán vị trên Z
26
, ta xác định
e
π
(x) = π (x)
d
π
(y) = π
-1
(y)
với x, y є Z
26
, π
1.2.1.3. Mã Affine
Định nghĩa Mã Affine: (P, C, K, E, D)
P = C = Z
26
, K = { (a, b) є Z
26
x Z
26
: (a, 26) = 1 }
với mỗi k = (a, b) є K ta định nghĩa:
e
k
(x) = ax + b mod 26
d
k
(y) = a
-1
(y – b) mod 26
trong đó x, y є Z
26
Ví dụ: Lấy k = (5, 6).
Bản rõ:
“maaffine”
m a a f f i n e
x 12 0 0 5 5 8 13 4
Y=5x + 6 mod 26
14 6 6 5 5 20 19 0
y o g g f f u t a
Bản mã:
) ∈ K có:
e
k
(x
1
, x
2
,…, x
m
) = (x
1
+ k
1
, x
2
+ k
2
,…, x
m
+ k
m
)
d
k
(y
1
, y
2
,…, y
m
Tập hợp các khoá trong mã Vingenere mới m ≥ 1 có tất cả là 26
m
khoá có thể có.
Với m = 6, số khoá đó là 308.915.776, duyệt toàn bộ chừng ấy khoá để thám mã bằng
tính tay thì khó, nhưng với máy tính thì vẫn là điều dễ dàng.
1.2.1.5. Mã Hill
Định nghĩa Mã Hill: (P, C, K, E, D)
Cho m là số nguyên dương.
P = C = (Z
26
)
m
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
14
K = { k ∈ (Z
26
)
mxm
mxm :
()
26 det(k),
= 1 }
với mỗi k ∈ K định nghĩa:
e
k
(x
1
, x
2
⎟
⎠
⎞
⎜
⎜
⎝
⎛
73
811
Với bộ 2 ký tự (x
1
, x
2
), ta có mã là (y
1
, y
2
) = (x
1
, x
2
). k được tính bởi
y
1
= 11.x
1
+ 3.x
2
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
dc
ba
Và được tính như sau
1−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
dc
ba
=
⎟
⎟
⎟
⎟
⎠
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
15
Khi đó: k
-1
.k = I là ma trận đơn vị (đường chéo chính bằng 1)
1−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
dc
ba
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
dc
ba
=
⎟
⎟
⎛
dc
ba
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
10
01
Định thức của
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
73
811
Là 11*7 – 8*3 = 1 ≡ 1 mod 26
Khi đó
⎜
⎜
⎝
⎛
1123
187
mod 26
1.2.1.6. Mã hoán vị
Định nghĩa Mã hoán vị: (P, C, K, E, D)
Cho m là số nguyên dương.
P = C = Z
26
, K = S
m
(
)
mk
xxxe ,,,
21
=
() ( ) ( )
(
)
m
xxx
πππ
,,,
21
-1
là:
1 2 3 4
2 3 4 1
1 2 3 4
4 1 2 3
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
16
Bản rõ:
“ mahoanvi ”
m a h o a n v i
vt 1 2 3 4 1 2 3 4
π
1
→2 2→3 3→4 4→1 1→2 2→3 3→4 4→1
vt 2 3 4 1 2 3 4 1
a h o m a h o m
Bản mã:
“ ahomahom ”
Dùng hoán vị nghịch đảo, từ bản mật mã ta lại thu được bản rõ.
Chú ý:
Mã hoán vị là một trường hợp riêng của mã Hill. Thực vậy, cho phép hoán vị π của
{1, 2,…, m}, ta có thể xác định ma trận K
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
17
Ý tưởng xây dựng một hệ mật khóa công khai là tìm một hệ mật không có khả
năng tính tóan để xác định d
k
khi biết e
k
. Nếu thực hiện được như vậy thì quy tắc mã e
k
có thể được công khai bằng cách công bố nó trong một danh bạ (bởi vậy nên có thuật
ngữ hệ mật khóa công khai).
Ưu điểm của hệ mật khóa công khai là ở chỗ A (hoặc bất kỳ A) có thể gửi một bản
tin đã mã hóa cho B (mà không cần thông tin trước về khóa mật) bằng cách dùng mật
mã công khai e
k
. Người nhận A sẽ là người duy nhất có thể giải mã được bản mã này
bằng việc sử dụng luật giải bí mật d
k
của mình. Có thể hình dung hệ mật này tương tự
như sau: A đặt một vật vào một hộp kim loại và rồi khóa nó lại bằng một khóa số do B
để lại. Chỉ có B là người duy nhất có thể mở được hộp vì chỉ có anh ta mới biết tổ hợp
mã của khóa số của mình.
Ý tưởng về một hệ mật khóa công khai được Diffie và Hellman đưa ra vào năm
1976. Còn việc hiện thực hóa nó thì do Riyesrt, Shamir và Ableman đưa ra lần
đầu vào
năm 1977, họ đã tạo nên hệ mật nổi tiếng RSA và một số hệ mật khác. Độ bảo mật của
hệ RSA dựa trên độ khó của việc phân tích ra thừa số nguyên lớn.
Nơi ứng dụng
Sử dụng chủ yếu trên các mạng công khai như Internet, khi mà việc trao chuyển
r
ị n và b được công khai và các giá t
r
ị p, q, a được giữ kín
Ví dụ:
Chọn p = 2, q = 5. Tính n = p.q = 2*5 = 10
φ(n)= (p – 1).(q – 1) = 1*4 = 4
Do UCLN(φ(n), b) = 1 nên chọn b = 3
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
18
a.b ≡ 1 mod φ(n) nên chọn a = 7
Giả sử G muốn gửi bản rõ x = 3 tới N, G phải tính:
y = e
K
(x)= x
b
mod n = 3
3
mod 10 = 7
Khi N nhận được bản mã y = 7, anh ta sử dụng số mũ a mật để tính:
x = d
K
(y) = y
a
mod n = 7
7
mod 10 = 3
Bài toán logarithm rời rạc trong Z
p
:
Đặc trưng của bài toán: I = (p,
α
,
β
) trong đó p là số nguyên tố, α ∈
p
Z
là
phần tử nguyên thuỷ (hay phần tử sinh), β ∈
*
p
Z
Mục tiêu: Hãy tìm một số nguyên duy nhất a, 0 ≤ a ≤ p – 2 sao cho:
α
a
≡ β (mod p)
Ta sẽ xác định số nguyên a bằng log
α
β.
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
19
1−p
Z
, ta xác định:
e
K
(x, k) = (y
1
, y
2
).
Trong đó: y
1
= α
k
mod p
y
2
= x. β
k
mod p
với y
1
, y
2
∈
*
p
Z ta xác định:
d
K
, chọn k =3
Giả sử G muốn gửi thông báo x = 3 cho N, G phải tính:
e
K
(x, k) = (y
1
, y
2
)
Trong đó:
y
1
= α
k
mod p = 3
3
mod 7 = 6
y
2
= x. β
k
mod p = 3*2
3
mod 7 = 3
Khi N thu được bản mã (y
1
, y
2
) = (6, 3), anh ta sẽ tính:
x = d
2.1.1. Khái quát về chữ ký điện tử ?
Về căn bản, khái niệm chữ ký điện tử (electronic signature) cũng giống như chữ
viết tay. Bạn dùng nó để xác nhận lời hứa hay cam kết của mình và sau đó không thể
rút lại được. Chữ ký điện tử không đòi hỏi phải sử dụng giấy mực, nó gắn
đặc điểm
nhận dạng của người ký vào một bản cam kết nào đó, nó là đoạn dữ liệu ngắn đính
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
tính toàn vẹn của nội dung văn bản gốc.
Con người đã sử dụng các hợp đồng dưới dạng điện tử từ
hơn 100 năm nay với
việc sử dụng mã Morse và điện tín. Vào năm 1889, tòa án tối cao bang New
Hampshire (Hoa kỳ) đã phê chuẩn tính hiệu lực của chữ ký điện tử. Tuy nhiên, chỉ với
những phát triển của khoa học kỹ thuật gần đây thì chữ ký điện tử mới đi vào cuộc
sống một cách rộng rãi. Vào thập kỷ 1980, các công ty và một số cá nhân bắt đầu sử
dụ
ng máy fax để truyền đi các tài liệu quan trọng. Mặc dù chữ ký trên các tài liệu này
vẫn thể hiện trên giấy nhưng quá trình truyền và nhận chúng hoàn toàn dựa trên tín
hiệu điện tử.
Hiện nay, chữ ký điện tử 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ằng bút điện tử với thiết bị màn hình
cảm ứng tại các quầy tính tiền, chấp nhận các đi
ều khoản người dùng (EULA) khi cài
đặt phần mềm máy tính, ký các hợp đồng điện tử online.
Chữ ký điện tử được tạo ra bằng cách áp dụng thuật toán Băm một chiều trên văn
bản gốc để tạo ra bản phân tích văn bản (message digest) hay còn gọi là fingerprint,
sau đó mã hóa bằng private key tạo ra chữ ký số đính kèm với văn bản gốc để gửi đi.
Khi nhận, văn bản đượ
c tách làm 2 phần, phần văn bản gốc được tính lại fingerprint để
so sánh với fingerprint cũ cũng được phục hồi từ việc giải mã chữ ký số.
giả mạo.
Bản copy thông điệp được ký bằng
chữ ký thông thường lại có thể khác với
bản gốc.
Bản copy thông điệp được ký bằng
chữ ký điện tử thì đồng nhất với bản
gốc, điều này có nghĩa là cần phải ngăn
chặn một bức thông điệp ký số không bị
dùng lại.
2.1.2. Định nghĩa về sơ đồ ký điện tử
Một sơ đồ chữ ký S là một bộ năm
S = (P , A , K , S , V)
Trong đó: P là một tập hữu hạn các thông báo có thể có,
A là một tập hữu hạn các chữ ký có thể có,
K là một tập hữu hạn các khoá, mỗi khoá K ∈ K gồm có hai phần
K=(K’,K''), K' là khoá bí mật dành cho việc ký, còn K'' là khoá
công khai dành cho việc kiểm thử chữ ký.
V
ới mỗi K =(K’,K''), trong S có một thuật toán ký sig
k’
: P → A , và trong V có
một thuật toán kiểm thử ver
k”
: PxA
→
{đúng,sai} thoả mãn điều kiện sau đây đối với
mọi thông báo x ∈ P và mọi chữ ký y ∈ A :
ver
k”
cầu đầu tiên này là những trở ngại chính trong giao dịch qua máy tính.
Hai tính chất bổ trợ sau là những tính chất mong muốn đối với giao dịch
được hoàn tất nhờ chữ ký số.
¾ Không thể thay đổi : sau khi được phát M không thể
thay đổi bởi
F.R hoặc bởi một kẻ thu trộm nào.
¾ Không thể sử dụng lại : một thông báo trước đó được đưa ra sẽ
ngay lập tức bị R phát hiện.
2.1.3. Sơ đồ chữ ký RSA
Sơ đồ chữ ký RSA được cho bởi bộ năm
S = (P , A , K , S , V)
Trong đó : P = A =Z
n
, với n =p.q là tích của hai số nguyên tố lớn p,q
K là tập các cặp khoá K =(K’,K''), với K’ = a và K'' = (n,b)
a và b là hai số thuộc Z
*
n
thoả mãn a.b ≡ 1(mod
φ
(n)).
Các hàm sig
k’
và ver
k”
được xác định như sau:
sig
k’
(x) = x
Sinh viên: Phạm Thị Hiểu Lớp CT702
23
truyền tin công cộng, ta có cả hai hệ mật mã khoá công khai S
1
và hệ xác nhận bằng
chữ ký S
2
. Giả sử B có bộ khoá mật mã K = (K', K'') với K' = (n, e) và
K'' = d trong hệ S
1
, và A có bộ khoá chữ ký K
s
= (K’
s
, K''
s
) với
K’
s
= a và K''
s
= (n,b) trong hệ S
2
. A có thể gửi đến B một thông báo vừa bảo mật vừa
có chữ ký để xác nhận như sau: A ký trên thông báo x trước, rồi thay cho việc gửi đến
B văn bản cùng chữ ký (x,sig
k’s
(x)) thì A sẽ gửi cho B bản mật mã của văn bản đó
được lập theo khoá công khai của B, tức là gửi cho B e
k’
*
p
là rất khó. Tập hợp K gồm các cặp khoá K=(K’,K''), với K’=a
là một số thuộc Z
*
p
, K'' =(p, α , β), α là một phần tử nguyên thuỷ của Z
*
p
, và
β=α
a
modp. K’ là khoá bí mật dùng để ký, và K'' là khoá công khai dùng để kiểm thử
chữ ký. Các thuật toán ký và kiểm thử chữ ký được xác định như sau: Với mỗi thông
báo x, để tạo chữ ký trên x ta chọn thêm môt số ngẫu nhiên k ∈ Z
*
p-1
, rồi tính :
sig
k’
(x,k ) = (γ , δ) với
γ = α
k
modp,
δ = (x – a.γ). k
-1
mod(p -1).
Thuật toán kiểm thử được định nghĩa bởi:
ver
k”
mod467=132. Cho x =100; ta
chọn ngẫu nhiên k =213 (∈ Z
*
466
) và được k
-1
mod466 = 431.
Chữ ký trên văn bản x=100 với số ngẫu nhiên k =213 là (γ , δ), trong đó
γ =2
213
mod467 = 29 và δ = (100 - 127.29).431mod466 =51.
Để kiểm thử ta tính :
β
γ
. γ
δ
= 132
29
.29
51
≡ 189 (mod467),
Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử
Sinh viên: Phạm Thị Hiểu Lớp CT702
24
α
x
= 2
100
≡ 189 (mod467),
hai giá trị đó đồng dư với nhau theo mod 467, chữ ký (β
,α = h
(p-1)/q
mod p ≠ 1 với 1<h<p-1
a là số ngẫu nhiên (0 < a < q )
β ≡ α
a
modp.
k là số ngẫu nhiên (0 < k < q )
K=(K’,K''), trong đó khoá bí mật K’ = a, và khoá công khai K'' = (p,q, α, β).
Hàm ký sig
k’
:
sig
k’
(x,k ) = (γ , δ)
Trong đó γ = (α
k
modp) modq,
δ = (x + a. γ).k
-1
modq.
Hàm kiểm thử ver
k”
:
ver
k”
(x,(γ , δ)) = đúng
↔ (
21
.
. α
a. γ.w
mod p) mod q
= (α
(x+a.γ).w
mod p) mod q (1)
Hơn nữa w = δ
-1
mod q
= (x + a.γ)
-1
.k mod q
→ (x + a. γ).w = k mod q (2)
Từ (1) và (″) → (
21
.
ee
βα
mod p)mod q = (α
k
mod p) mod q = γ
Như vậy ver
k”
(x,(γ ,δ)) = đúng
Ví dụ :
Copyright: Tài liệu đại học ©