mở đầu
Trong mật mã vấn đề bảo mật luôn đi đôi với vấn đề xác thực
thông tin, đặc biệt trong hệ thống mã khoá công khai vấn đề xác
thực là vô cùng quan trọng. Để giải quyết được vấn đề xác thực
người ta đưa ra một cách vừa đơn giản vừa hiệu quả là sử dụng
chữ kí số. Việc sử dụng chữ kí số ngày càng có nhiều ứng dụng
trong thực tế, không chỉ giới hạn trong Ngành Công Nghệ Thông
Tin , Ngành Mật Mã mà còn được áp dụng trong một số lĩnh vực
khác như trong lĩnh vực Ngân Hàng để xác thực người gửỉ, người
nhận, lĩnh vực Viễn thông để sử dụng các thẻ thông minh.
Với mật mã khoá công khai việc tạo ra chữ kí số và ứng dụng
vào các tài liệu, các văn bản điện tử là vô cùng quan trọng. Chữ kí
thường ( Chữ kí viết tay ) thì có thể giả mạo được , vậy thì chữ kí số
phải đảm bảo những yêu cầu gì để có thể tạo cơ sở pháp lý trong
thời đại Thông tin – Tin học hoá.
Chữ kí số phải có những tính năng sau :
1. Người nhận văn bản đã kí phải có thể xác minh được
bất kì chữ kí hợp lệ nào của người gửi.
2. Chữ kí không thể giả mạo được
3. Người đã kí thông báo thì không thể từ chối phủ nhận
nó về sau được
Bùi Lê Trung – Líp CT96B
1
Mục đích của luận văn là giới thiệu về “ Sơ đồ chữ kí số
Elgamal “ , đây là một trong những sơ đồ mạnh vào bậc nhất hiện
nay, và đã được nhiều nước trên thế giới ứng dụng , đặc biệt là tại
Mỹ đã có bản cải tiến của sơ đồ này và đã được Viện tiêu chuẩn và
Công nghệ quốc gia Mỹ (NIST) chấp nhận làm chuẩn chữ kí số .
Điểm mạnh và an toàn của sơ đồ chữ kí số Elgamal là dựa trên tính
khó giải của bài toán tìm Logarithm rời rạc trên trường hữu hạn
Z

p
.
CHƯƠNG I : GIỚI THIỆU SƠ ĐỒ CHỮ KÍ SỐ
Thông thường chữ kí viết tay trên các văn bản , trên các tài liệu
hay trên các hợp đồng kinh tế v.v thì được dùng để xác nhận
người kí nó .
Sơ đồ chữ kí ( hay còn gọi là chữ kí số ) là phương pháp kí một
bức điện lưu dưới dạng điện tử . Chẳng hạn một bức điện có chữ kí
được truyền trên mạng máy tính
Một sơ đồ chữ kí số thường chứa hai thành phần : Thuật toán kí
và thuật toán xác minh . Người A có thể kí bức điện x dùng thuật
Bùi Lê Trung – Líp CT96B
2
toán kí an toàn . Chữ kí Sig(x) nhận được có thể kiểm tra bằng thuật
toán xác minh công khai Ver . Khi cho trước cặp (x,y) thuật toán
xác minh cho giá trị TRUE hay FALSE tuỳ thuộc vào việc chữ kí
được xác thực như thế nào .
Định nghĩa hình thức của chữ kí số
Một sơ đồ chữ kí số là bộ 5 ( P,A,K,S,V) thoả mãn các điều
kiện sau :
1. P : là tập hữu hạn các bức điện có thể.
2. A : là tập hữu hạn các chữ kí có thể .
3. K : không gian khoá là tập hữu hạn các khoá có thể
4.Với mỗi K thuộc K tồn tại một thuật toán kí Sig
K

∈
S và một
thuật toán xác minh Ver
K


∈
V .
Mỗi Sig
K
: P -> A và Ver
K
:P x A -> { TRUE ,FALSE } là
những hàm sao cho mỗi bức điện x
∈
P và mỗi bức điện y
∈
A
thoả mãn phương trình sau đây
TRUE nếu y= Sig(x)
Ver (x,y) =
FALSE nếu y #Sig(x)
Với mỗi K
∈
K , hàm Sig
K
và Ver
K
là các hàm thời gian đa
thức . Ver
K
sẽ là hàm công khai còn Sig
K
là hàm mật . Ta gọi Alice
là người gửi còn Bob là người nhận . Không thể dễ dàng tính toán

để giả mạo chữ kí của Bob trên bức điện x . Nghĩa là với x cho
Bùi Lê Trung – Líp CT96B
3
trước , chỉ có Bob mới có thể tính được chữ kí y để Ver (x,y) = True
.
CHƯƠNG II : SƠ ĐỒ CHỮ KÍ ELGAMAL
Sơ đồ chữ kí Elgamal đã từng được giới thiệu vào năm 1985 ở
Mỹ. Bản cải tiến của sơ đồ này đã được Viện Tiêu Chuẩn và Công
Nghệ Quốc Gia Mỹ (NIST) chấp nhận làm chuẩn chữ kí số. Sơ đồ
chữ kí Elgamal dựa trên tính khó giải của bài toán tìm Logarithm
rời rạc trên trường hữu hạn .Trước hết ta hãy làm quen với bài toán
Logarithm rời rạc trên trường hữu hạn Z
p
I. Bài toán Logarithm rời rạc trong Z
p

Chóng ta sẽ bắt đầu bằng việc mô tả bài toán này khi thiết lập
một trường hữu hạn Z
p
, p là số nguyên tố (Nhóm nhân Z
p
* là nhóm
Cyclic và phần tử sinh của Z
p
* được gọi là phần tử nguyên thuỷ) .
Bài toán Logarithm rời rạc trong Z
p
là đối tượng trong nhiều
công trình nghiên cứu , và được xem là bài toán khó nếu p được
chọn cẩn thận. Cụ thể là không có một thuật toán thời gian đa thức

nào cho bài toán Logarithm rời rạc .
Để gây khó khăn cho các phương pháp tấn công đã biết , p
phải có Ýt nhất 150 chữ số thập phân ( ≈ 500 bít ) và (p -1) phải có
Ýt nhất một thừa số nguyên tố lớn , tốt nhất p có dạng p = 2q + 1
với q cũng là nguyên tố. Số nguyên tố p dạng này gọi là số nguyên
tố mạnh ( String – Prime ) đối với hệ Elgamal nói riêng và cho
Bùi Lê Trung – Líp CT96B
4
những hệ mà độ an toàn dựa vào tính khó giải của bài toán
Logarithm rời rạc nói chung . Lợi thế của bài toán Logarithm rời rạc
trong xây dựng sơ đồ chữ kí là khó tìm được các Logarithm rời rạc,
song bài toán ngược lấy luỹ thừa lại có thể tính toán hiệu quả theo
thuật toán bình phương và nhân . Nói cách khác , luỹ thừa theo
modulo p là hàm một chiều với các số nguyên tố p thích hợp.
Bài toán Logarithm rời rạc trên trường hữu hạn Zp
Đặc trưng của bài toán : I= ( p,
α
,
β
) trong đó p là số nguyên
tố lẻ ,
α

∈
Z
p
là phần tử nguyên thuỷ ,
β∈
Z
p

* , 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
α

β
( mod p) được gọi là
Logarit cơ số
α
của
β
.

II. Sơ đồ chữ kí số Elgamal .
Sơ đồ Elgamal được thiết kế với mục đích dành riêng cho chữ
kí số , điểm mạnh của nó là cùng số nguyên tố p trong cùng một sơ
đồ thì với k là ngẫu nhiên nên ta có thể có nhiều chữ kí số, không tất
định giống như hệ thống mã khoá công khai Elgamal, ở sơ đồ chữ kí

RSA ta chỉ thấy trên cùng một sơ đồ với cùng một số nguyên tố p
thì ta chỉ có một chữ kí số. Điều này có nghĩa là có nhiều chữ kí hợp
Bùi Lê Trung – Líp CT96B
5
lệ trên bức điện cho trước bất kì .Thuật toán xác minh phải có khả
năng chấp nhận bất kì chữ kí hợp lệ nào khi xác thực chữ kí đó.
Sơ đồ chữ kí Elgamal
Cho p là số nguyên tố sao cho bài toán Logarithm rời rạc trên Z
p
là
khó và giả sử
α

∈
Z
p
* là phần tử nguyên thuỷ
Cho p = Z
p
* , A=Z
p
*
×
Z
p-1
, và kí hiệu :
K={(p,
α
,a,
β

):
β

≡α
a
(mod p) }
Giá trị p,
α
,
β
là công khai ,còn a là mật
Với K=(p,
α
,a,
β
) và với mét số ngẫu nhiên (mật) k
∈
Z
p-1
*
Định nghĩa : Sig
k
(x,k) = (
γ
,
δ
) .
trong đó
γ
=

α
k
mod p
và
δ
= (x-a
γ
)k
-1
mod (p-1).
Với x,
γ

∈
Z
p
* và
δ

∈
Z
p-1
ta định nghĩa
Ver(x,y,
δ
) = True
↔

β
γ


γ
δ

≡α
x
(mod p).

Nếu chữ kí được thiết lập đúng thì xác minh sẽ thành công vì :
β
γ
γ
δ

≡ α
a
γ
α
k
δ
(mod p) ≡ α
x
(mod p ).
Ở đây ta dùng hệ thức : a γ + k δ ≡ x (mod p-1).
Bob tính chữ kí bằng cách dùng cả giá trị mật a (là một phần
của khoá ) lẫn số ngẫu nhiên mật k ( dùng để kí lên bức điện x ).
Việc xác minh có thể thực hiện duy nhất bằng thông tin công khai.
Ta xét một ví dụ sau :
Bùi Lê Trung – Líp CT96B
6

Giả sử : Cho p =467 , α=2 , a=127 khi đó:
β = α
a
mod p = 2
127
mod 467 = 132.
Nếu Bob muốn kí lên bức điện x = 100 và chọn số ngẫu nhiên k =
213
( chó ý là USCLN(213,466) =1 và 213
-1
mod 466 =431 ). Khi đó :
γ = 2
213
mod 467 =29
và δ = (100 – 127 × 29 ) 431 mod 466 = 51
Bất kì ai cũng có thể xác minh chữ kí này bằng cách kiểm tra :
132
29
29
51
≡ 189 (mod 467 )
và 2
100
≡ 189 (mod 467 )
Vì thế chữ kí là hợp lệ .
Ta xét độ mật của sơ đồ chữ kí Elgamal.
Giả sử ,Oscar thử giả mạo chữ kí trên bức điện x cho trước mà
không biết a . Nếu Oscar chọn γ và sau đó thử tìm giá trị δ tương
ứng .Anh ta phải tính Logarithm rời rạc Log
γ

α
x
β
-
γ
.Mặt khác , nếu
đầu tiên anh ta chọn δ và sau đó thử tìm γ và thử giải phương trình :
β
γ
γ
δ
≡ α
x
( mod p ) .
Bùi Lê Trung – Líp CT96B
7
Để tìm γ . Đây là bài toán chưa có lời giải nào , tuy nhiên ,dường
như nó chưa được gắn với đến bài toán đã nghiên cứu kĩ nào nên
vẫn còn khả năng có cách nào đó để tính δ và γ đồng thời để (δ , γ )
là một 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 rằng nó không thể giải được
Nếu Oscar chọn γ và δ và sau đó thử giải tìm x , anh ta sẽ phải
đối mặt với bài toán Logarithm rời rạc , tức bài toán tính Log
α
β
γ
γ
δ
.
Vì thế Oscar không thể kí một bức điện ngẫu nhiên bằng biện pháp

này .
Cuối cùng , ta sẽ nêu cách có thể phá được sơ đồ này nếu
không áp dụng nó một cách cẩn thận. Trước hết , giá trị k ngẫu
nhiên được dùng để tính chữ kí phải được giữ kín không được để
lộ . Vì nếu k bị lộ , khá đơn giản để tính : a = (x-
k γ )δ
-1
mod ( p –1 ).
Dĩ nhiên , một khi a bị lộ thì hệ thống bị phá và Oscar có thể
dễ dàng giả mạo chữ kí .
Một kiểu dùng sai sơ đồ nữa là dùng cùng giá trị k để kí hai
bức điện khác nhau . Điều này cũng tạo thuận lợi cho Oscar tính a
và phá hệ thống. Sau đây là cách thực hiện . Giả sử ( γ,δ
1
) là chữ kí
trên x
1
và ( γ,δ2 ) là chữ kí trên x
2
. Khi đó ta có :
β
γ
γ
δ
1
≡ α
x1
(mod p )
và β
γ

γ
δ
2
≡ α
x2
( mod p )
Bùi Lê Trung – Líp CT96B
8
Như vậy : α
x1 x2
≡ γ
δ
1
δ
2
( mod p ).
Nếu viết γ = αk ta nhận được phương trình tìm k chưa biết sau:
α
x1 x2
≡ α
k(
δ
1-
δ
2 )
( mod p ).
tương đương với phương trình : x
1
- x
2

≡ k (δ
1
-δ
2
) (mod p-1).
Bây giờ giả sử d = USCLN(δ
1
-δ
2
,p –1). Vì d | ( p –1) và d | (δ
1
-δ
2
)
nên suy ra d | (x
1
-x
2
). Ta định nghĩa :
x’ = (x
1
-x
2
)/d ; δ’ = ( δ
1
-δ
2
) / d ; p’ = ( p-1 ) / d
Khi đó đồng dư thức trở thành : x’ ≡ k δ’ ( mod p’ )
Vì USCLN (δ’,p’ ) =1 , nên ta có thể tính : ε = ( δ’ )

–1
mod p’
Khi đó giá trị k xác định theo modulo p’ sẽ là : k = x’ ε mod p’
Phương trình này cho d giá trị có thể của k : k = x’ ε + i p’ mod p
với i nào đó , 0 ≤ i ≤ d-1 . Trong đó d giá trị có thể này có thể xác
định được một giá trị đúng duy nhất qua việc kiểm tra điều kiện :
γ ≡ α
k
( mod p )
Bùi Lê Trung – Líp CT96B
9
Chương III : mô phỏng chương trình chữ kí số
ELGAMAL TRÊN VĂN BẢN ĐIỆN TỬ
Như ta đã biết một sơ đồ chữ kí số thường chứa 2 thành phần
đó là thuật toán ký và thuật toán xác minh . Trong chương này em
xin trình bày về hàm Hash đơn giản là hàm tóm lược văn bản và ký
số lên file văn bản , nhằm bảo toàn tính nguyên vẹn của văn bản .
I. Hàm HASH và việc tóm lược thông báo.
Một vấn đề đặt ra là ta không nên áp sơ đồ ký số vào một thông
báo dài . Nhưng thông báo thì phải được kí , mâu thuẫn này có thể
giải quyết được bằng cách sử dụng hàm Hash , vì hàm Hash là một
công cụ tóm lược đặc trưng của thông báo rất an toàn và hữu hiệu .
Với một thông báo có độ dài M bất kỳ . Hàm Hash cho ra giá trị
tóm lược thông báo có độ dài không đổi, nói chung giá trị tóm lược
thông báo có độ dài nhỏ hơn thông báo M rất nhiều . Chẳng hạn |
H(M) | = 128 bít hoặc | H(M) | =160 bít trong khi đó thông báo
có độ dài cỡ Mega byte hay lớn hơn. Do vậy đặc tính cơ bản của
hàm Hash là đưa ra một giá trị đại diện của thông báo M rất ngắn so
với thông báo .
Sau khi đã tóm lược thông báo M được một tóm lược H(M)

người ta dùng chữ ký số áp vào H(M) . Thông báo M cùng với tóm
H(M) đã được ký sẽ được gói trọn trong một thông báo và được mã
hoá theo cách thông thường để truyền đi. Người nhận được thông
Bùi Lê Trung – Líp CT96B
10
báo có thể chứng thực chữ ký tóm lược H(M) sau đó dùng hàm
Hash tính lại tóm lược với thông báo vừa nhận được và so sánh kết
quả. Khi đó cùng một lúc có thể xác thực được người gửi và cả sự
nguyên vẹn của thông báo M .
II. Mô tả chương trình chữ kí số Elgamal trên một file văn bản
bất kỳ M.
-Đầu tiên ta mở file văn bản (M) cần kí , sau đó dùng hàm Hash
để tóm lược lại văn bản ta được H(M). Hàm Hash sau đây sẽ sử
dụng là ta sẽ chia văn bản M ra làm nhiều khối , mỗi khối là 40 byte
. Sau đó ta sẽ đọc từng 40 byte văn bản của từng khối gán bằng 1
byte mã. Nếu khối văn bản cuối cùng không đủ 40 byte thì ta sẽ cho
đọc riêng số lượng byte đó thành 1 byte mã. Đoạn chương trình sau
được viết bằng Pascal mô tả một trong những cách tóm lược văn
bản qua hàm Hash.
procedure tom_luoc(st:ten_file);
var
l,m,n,i,j:longint;
kq:word;
dem:sl;
begin
fillchar(hash,max_sl,0);
assign(f,st);
reset(f,1);
Bùi Lê Trung – Líp CT96B
11

l:=filesize(f);
m:=l div 40;
n:=l mod 40;
for i:=1 to m do
begin
blockread(f,dem,40,kq);
for j:=0 to 39 do hash[j]:=hash[j] xor dem[j];
end;
if (n>0) then
begin
blockread(f,dem,n,kq);
for j:=0 to n-1 do hash[j]:=hash[j] xor dem[j];
end;
close(f);
end;
-Sau khi tóm lược được, ta dùng chương trình ký cùng với phần
tóm lược để ký lên văn bản đã nhập . Cuối cùng sẽ ghi toàn bộ văn
bản và chữ kí số lên file ký .
-Đầu tiên ta mở file văn bản cần kiểm tra chữ ký sè , sau đó ta
lại dùng hàm Hash để tóm lược lại văn bản, sau đó đưa kết quả vào
để kiểm tra chữ kí trên văn bản
Bùi Lê Trung – Líp CT96B
12
M
C«ng Khai
Ch÷ Ký 1
Ch÷ Ký 2
Ch ¬ng
tr×nh
KiÓm Tra

Tãm l îc M
-Quá trình kí và kiểm tra chữ kí thể hiện qua 2 sơ đồ sau:
Sơ đồ quá trình kí lên văn bản M:
Sơ đồ quá trình kiểm tra chữ ký trên văn bản M:
Bùi Lê Trung – Líp CT96B
13
M
M
C«ng Khai
Ch÷ ký 1
Ch÷ ký 2
Ch ¬ng
Tr×nh
ký sè
Tãm l îc M