Mục Lục

1


Mở đầu
Mật mã học là một trong những vấn đề quan trọng trong lĩnh vực bảo mật
và an toàn thông tin. Trên thế giới, mật mã học đã được ra đời từ thời La Mã cổ
đại và ngày càng nghiên cứu, phát triển đạt được những thành tựu to lớn. Trong
mật mã học, vấn đề bảo mật luôn đi đôi với vấn đề xá thực thông tin, đặc biệt
trong hệ thống mã hóa khóa công khai vấn đề xác thực là vô cùng quan trọng.
Để giải quyết vấn đề trên người ta đưa ra một cách giải quyết hiệu quả, đó là chữ
kí số.
Với sự bùng nổ của mạng Internet hiện nay, mạng máy tính đang ngày
càng đóng vai trò thiết yếu trong mọi lĩnh vực hoạt động của toàn xã hội, và khi
nó trở thành phương tiện điều hành các hệ thống thì nhu cầu bảo mật thông tin
được đặt lên hàng đầu. Việc sử dụng chữ kí số là một trong giải pháp hữu hiệu
hiện, ngày càng được ứng dụng nhiều trong thực tế, không chỉ giới hạn trong
ngành công nghệ thông tin, mật mã học mà còn được áp dụng nhiều trong những
lĩnh vực như ngân hàng, viễn thông, …
Mật mã học khóa công khai tạo ra chữ ký số và ứng dụng vào các tài liệu.
Hệ mã hóa ELGAMAL – hệ mã hóa điển hình của mật mã công khai cùng với
hàm băm mật mã học một chiều chính là một trong những công cụ chính trong
việc tạo ra chữ kí số điện tử.
Khi nói đến chữ ký số, chúng ta luôn lấy mục tiêu an toàn lên hàng đầu.
Một chữ ký số chỉ thực sự được áp dụng trong thực tế nếu như nó được chứng
minh là không thể giả mạo. Mục tiêu lớn nhất của kẻ tấn công các sơ đồ chữ ký
chính là giả mạo chữ ký, điều này có nghĩa kẻ tấn công sẽ sinh ra được chữ ký
của người ký lên thông điệp, mà chữ ký này sẽ được chấp nhận bởi người xác
nhận. Trong thực tế các hành vi tấn công chữ ký điện tử là hết sức đa dạng. Vì
vậy trong bài tiểu luận em xin phép nghiên cứu vấn đề: Phân tích xây dựng sơ

đồ chữ ký số Elgamal và các cách thám mã.

2


Nội Dung
1. Tổng quan về chữ ký số
1.1. Giới thiệu chung
Trong đời sống hàng ngày, chữ kí trên một văn bản là một minh chứng về
“bản quyền” hoặc ít nhất cũng là sự tán đồng, thừa nhận các nội dung trong văn
bản. Chẳng hạn như việc ký vào phiếu nhận tiền từ ngân hàng, hợp đồng mua
bán, chuyển nhượng, thừa kế, tố tụng, … Chữ ký viết tay được chính tay người
ký nên không thể sao chụp được. Thông thường chữ ký viết tay trên văn bản
được dùng để xác nhận người ký nó. Những yếu tố nào làm nên sức thuyết phục
của nó? Ta có thể xem xét các yếu tố sau:
- Chữ ký là bằng chứng thể hiện người ký có chủ định khi ký văn bản.
- Chữ ký thể hiện chủ quyền, nó làm cho người nhận văn bản biết rằng ai
đích thị là người đã ký văn bản.
- Văn bản đã ký không thể thay đổi được.
- Chữ ký không thể giả mạo và cũng là thứ không thể chối bỏ.
Trong đời sống bình thường, việc tạo một mô hình lý tưởng như trên là
không dễ vì việc ký trên văn bản giấy có thể giả mạo chữ ký, nhưng với khả
năng kiểm định sát sao thì việc làm thay đổi không phải là dễ. Tuy nhiên trong
thế giới máy tính thì vấn đề ký như trên thực tế gặp phải nhiều khó khăn: các
dòng thông tin trên máy tính có thể thay đổi dễ dàng, hình ảnh của chữ ký tay
của một người cũng dễ dàng sang truyền từ một văn bản này sang văn bản khác,
và việc thay đổi nội dung một văn bản điện tử cũng chẳng để lại dấu vết gì về
phương diện tẩy, xóa.
Để có được những đặc tính như trên, giao thức kí trong thế giới điện tử
cần phải có sự hỗ trợ của công nghệ mã hóa. Sơ đồ chữ ký số là phương pháp ký

một thông báo được lưu dưới dạng điện tử. Giao thức cơ bản của chữ ký số dựa
trên ý tưởng của Diffie và Hellman:
- Người gửi ký văn bản bằng cách mã hóa nó với khóa bí mật của mình.
- Người gửi chuyển văn bản cho người nhận.
- Người nhận văn bản kiểm tra chữ ký bằng việc sử dụng chìa khóa công
khai của người gửi để giải mã văn bản.
3


Khái niệm:
Chữ ký số là mô hình sử dụng các kỹ thuật mã hóa mật mã để gắn với mỗi
người sử dụng một cặp khóa công khai-bí mật và qua đó có thể ký các văn bản
điện tử cũng như trao đổi các thông tin mật. Khóa công khai thường được phân
phối thông qua chứng thực khóa công khai.
1.2. Vị trí, vai trò của chữ kí số
Xu hướng quốc tế hóa và toàn cầu hóa đã và đang ảnh hưởng đến sự phát
triển của thế giới. Việc trao đổi thông tin cũng từ đó yêu cầu nhanh gọn, chính
xác và đặc biệt là phải an toàn. Việc trao đổi thông tin, chứng thực thông tin theo
phong cách truyền thống làm giảm tốc độ, cũng như sự chính xác của thông tin.
Những công việc đó mang tính chất thủ công gây ra sự chậm chễ và thiếu chính
xác trong trao đổi.
Chính khó khăn đã nảy sinh sự phát triển mạnh mẽ của công nghệ thông
tin và công nghệ mã hóa. Hiện nay ở tất cả các nước phát triển cũng như đang
phát triển, mạng máy tính đang ngày càng đóng vai trò thiết yếu trong mọi lĩnh
vực hoạt động của toàn xã hội và nhu cầu bảo mật thông tin đặt lên hàng đầu.
Điển hình là việc mã hóa bảo mật các thông tin số của doanh nghiệp, dùng chữ
ký số xác thực email trao đổi thông tin, kiểm soát truy cập vào các sàn thương
mại điện tử và các đơn đặt hàng, ngân hàng điện tử, mua sắm trực tuyến… mà
vai trò chủ yếu là chữ kí số điện tử.
Trên thực tế chữ kí số không chỉ được thực hiện cho các giao dịch điện tử

trên mạng internet mà còn qua hệ thống mạng viễn thông di động. Đặc biệt, hiện
nay nhiều nước trên thế giới không chỉ triển khai ứng dụng chữ ký số trên mạng
máy tính mà còn áp dụng trên mạng điện thoại di động để thực hiện các giao
dịch điện tử. Hướng đi này giúp đẩy nhanh giao dịch, đơn giản hóa mua sắm
trực tuyến và giúp người dùng có thể truy cập mọi lúc mọi nơi.
Sự ra đời của chữ kí số khẳng định được lợi ích to lớn về chiến lược và
kinh tế, đồng thời các vấn đề liên quan đến chữ kí số cũng là những chủ đề quan
trọng nhất của mật mã học.

4


1.3. Sơ đồ tổng quan của chữ kí số
Chúng ta có thể hiểu nôm na về chữ ký số điện tử như sau: là những thông
tin đi kèm với dữ liệu nhằm xác định chủ của người gởi nó.
Chữ ký số điện tử bao gồm 3 thành phần: thuật toán tạo ra khóa, hàm tạo
chữ ký và hàm kiểm tra chữ ký.
Hàm tạo ra chữ ký là hàm tính toán chữ ký trên cơ sở khóa mật và dữ liệu
cần ký.
Hàm kiểm tra chữ ký là hàm kiểm tra xem chữ ký đã cho có đúng với
khóa công cộng không. Khóa này mọi người có quyền truy cập cho nên mọi
người đều có thể kiểm tra được chữ ký.
Định nghĩa: Sơ đồ chữ ký bao gồm các thành phần sau
1. Không gian bản rõ M.
2. Không gian chữ ký S.
3. Không gian khóa K để tạo nên chữ ký, không gian khóa K’ để kiểm tra
chữ ký.
N  K × K'

4. Thuật toán hiệu quả để tạo nên khóa Gen:

, ở đây K và K’
tương ứng với không gian khóa mật và khóa công cộng.
5. Thuật toán tạo chữ ký Sign:

M ×K  S

6. Thuật toán kiểm tra chữ ký Verify:
Đối với bất kỳ khóa tạo chữ ký
điện được ký hiệu:

sk ∈ K

.

M × K × K '

{True , False}

và bất kỳ bản tin

s ← Signsk (m)

m∈M

.

lệnh ký bức

.


Biểu thức này được đọc như sau: s-là chữ ký của bản tin m được tạo ra
nhờ thuật toán Sign và khóa mật sk.
Đối với bất kỳ khóa mật của chữ ký
cộng để kiểm tra chữ ký là
mãn điều kiện sau:

pk ∈ K '

sk ∈ K

, bất kỳ bản tin

, tương ứng với khóa công

m∈M

và chữ ký

s∈S

cần thỏa

5


True , if
Verify pk ( m, s ) = 
 False, if

s = Sign sk ( m )

s ≠ Signsk ( m )

Bởi vì tài liệu cần ký thường có chiều dài khá dài. Một biện pháp để ký là
chia tài liệu ra các đoạn nhỏ và sau đó ký lên từng đoạn và ghép lại. Nhưng
phương pháp có nhược điểm là chữ ký lớn, thứ hai là ký chậm vì hàm ký là các
hàm mũ, thứ ba là chữ ký có thể bị đảo loạn các vị trí không đảm tính nguyên
vẹn của tài liệu. Chính vì điều đó mà khi ký thì người ta ký lên giá trị hàm hash
của tài liệu, vì giá trị của hàm hash luôn cho chiều dài xác định. Hàm hash sẽ
được xem trong chương sau.
Có nhiều cách để tạo ra chữ kí. Ta có thể sử dụng một sơ đồ sau:

Chức năng của chữ ký số điện tử:
- Xác thực được nguồn gốc tài liệu: Tuy thuộc vào từng bản tin mà có thể
thêm các thông tin nhận dạng, như tên tác giả, nhản thời gian…vv.

6


- Tính toàn vẹn tài liệu. Vì khi có một sự thay bất kỳ vô tình hay cố ý lên
bức điện thì gía trị hàm hash sẽ bị thay đổi và kết quả kiểm tra bức điện sẽ
không đúng.
- Chống từ chối bức điện. Vì chỉ có chủ của bức điện mới có khóa mật để
ký bức điện.
Các khả năng tấn công đối với chữ ký điện tử:
1. Tội phạm có thể giả mã mạo chữ ký tương ứng với văn bản đã chọn.
2. Tội phạm thử chọn bức điện mà tương ứng với chữ ký đã cho.
3. Tội phạm có thể ăn trộm khóa mật và có thể ký bất kỳ một bức điện
nào nó muốn giống như chủ của khóa mật.
4. Tội phạm có thể dã mạo ông chủ ký một bức điện nào đó.
5. Tội phạm có thể đổi khóa công cộng bởi khóa của mình.

2. Sơ đồ chữ ký số Elgamal
2.1. Hệ mã Elgamal
Hệ mật Elgamal được xây dựng trên bài toán logarithm rời rạc.
Bài toán logarithm rời rạc trong Zp
Đặc trương của bài toán: I = (p,α,β).
Trong đó p là số nguyên tố, α ∈ Zp là phần tử nguyên thuỷ , β ∈ Zp*
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α β
Hệ mật khoá công khai Elgamal trong Zp*
Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó
giải. Cho α ∈ Zp* là phần tử nguyên thuỷ.Giả sử P = Zp* ,C = Zp* × Zp* . Ta
định nghĩa:
K = {(p, α,a,β): β ≡ αa (mod p)}
Các giá trị p, α,β được công khai, còn a giữ kín.
Với K = (p, α,a,β) và một số ngẫu nhiên bí mật k ∈ Zp-1, ta xác định:
7


ek (m,k) = (y1 ,y2 )
trong đó
y1 = αk mod p
y2 = mβk mod p
với y1 ,y2 ∈ Zp* ta xác định:
m=dk(y1 ,y2 ) = y2 (y1a )-1 mod p
2.2. Sơ đồ chữ ký số Elgamal
Sơ đồ chữ ký Elgamal được giới thiệu năm 1985. Sơ đồ này thiết kế dành
riêng cho chữ ký số khác với sơ đồ RSA dành chung cho cả hệ thống mã công

khai và chữ ký số. Tuy nhiên về tư tưởng thì cũng tương tự như hệ mã elgamal.
Sơ đồ chữ ký số Elgamal:
Tạo khóa:
Quá trình tạo khóa giống như qúa trình tạo khóa của hệ mật Elgamal, tức
là Alic chọn số nguyên tố p đủ lớn để bài toán logarith rời rạc trên Z p là khó giải,
và chọn

α ∈ Z *p

là phần tử nguyên thủy, chọn

mật và tính khóa công cộng yA=

α x A (mod p)

xA < p − 1

là số nguyên làm khóa

.

Tạo chữ ký:
∈ Z N*

k

Để ký lên bức điện m
Alice tạo ra số ngẫu nhiên thỏa mãn
và UCLN(k,p-1)=1 và hình thành nên chữ ký là cặp (r,s), ở đây


k < p −1

r ← α k (mod p ),
s ← k −1 (m − x A r )(mod p − 1).

Thẩm tra chữ ký:
Để thẩm tra chữ ký (r, s) Bob xem kết quả của hàm kiểm tra:

8


Verify (

α
,yA,p)

(m, (r, s)) = TRUE, nếu như r < p và

y Ar r s ≡ α m (mod p)

.

Chúng ta xem sự đúng đắn của phương trình thẩm tra chữ ký:

y Ar r s = α xA ⋅rα k ⋅k

−1

( m − x Ar )


(mod p) = α m (mod p)

.

Chúng ta thấy Alice hình thành chữ ký với khóa mật x A và cả số nguyên
ngẫu nhiên k. Việc thẩm tra chữ ký chỉ bằng thông tin công khai.
Sử dụng sơ đồ chữ kí số ở trên ta xây dựng lại cho sơ đồ chữ kí số
Elgamal

Ví dụ:
Giả sử Alice chọn p=467,

α =2

,xA=127. Alice đi tính khóa công khai yA

y A = α x A (mod p)

=2127 mod 467=132
9


Alice muốn ký lên bức điện m=100, thì Alice chọn số ngẫu nhiên k, ví dụ
Alice chọn k=213 (UCLN(213,467)=1) và tính 213-1(mod 466)=431. Khi đó:
r=2213 mod 467=29
s=431(100-127.29) mod 466=51
Bob hay bất kỳ ai cũng có thể thẩm tra được chữ ký này bằng cách:
132292951 ≡ 189(mod 467)
2100 ≡ 189(mod 467)


Vậy chữ ký là hợp lệ.
Code:
a, Sinh khóa
import random,math
def gcd(a,b):
r=0
while (b>0):
r=a%b
a=b;b=r
return a
def pt(a):
kq=[];
m=math.ceil(pow(a,0.5));
i=2;
if (prime(a)==1):i=m+1;
while (i<=m):
if (a%i==0):kq.append(i);
while (a%i==0):a=int(a/i)
if (kq[len(kq)-1]==i):
if (prime(a)==1):break;
i=i+1;
if (a>1):kq.append((int)(a));
return kq;
def prime(p):
if (p==2)|(p==3): return 1
if (p<2)|(p%2==0): return 0
for i in range(1,11):
a=random.randint(2,p-1)
if (pow(a,p-1,p)!=1): return 0
return 1

def ptnt(p):
m=pt(p-1)
while (1):
g=random.randint(2,p-2);
ok=1;

10


for i in m:
mu=(int)((p-1)/i)
if (pow(g,mu,p)==1):
ok=0;
break;
if (ok==1):return g;
return -1;
def chuyen(so):
x=[];
while (so>0):
x.insert(0,so%2);
so=(int)(so/2);
while (len(x)<64):x.insert(0,0);
return x;
def sinhp():
a=random.randint(10000000000,99999999990);
while (prime(a)==0):a=a+1;
return a;
#sinh khoa
m=123;
p=sinhp();

print("p:",p);
ap=ptnt(p);
print("ap:",ap);
a=random.randint(1,p-2);
print("a:",a);
bt=pow(ap,a,p);
print("bt:",bt);
k=random.randint(1,p-2);
while (gcd(k,p-1)!=1):k=random.randint(1,p-2)
print("k:",k);
#ma hoa
c1=pow(ap,k,p);
c2=(m*pow(bt,k,p))%p;
#giai ma
m=(c2*pow(c1,p-1-a,p))%p

b, Tạo chữ ký
import hashlib,math
base=['0','1','2','3',
'4','5','6','7','8','9','a','b','c','d','e','f']
def inv_mod(a,b):
a1=a;
y0=0;
y1=1;
while (b>0):
r=a%b;

11



q=(int)(a/b);
a=b;b=r;
if (r==0) :break;
y=y0-y1*q;
y0=y1;y1=y;
if (y1 < 0): y1 = y1 % a1;
return y1;
def md5(fname):
hash_md5 = hashlib.md5()
with open(fname, "rb") as f:
for chunk in iter(lambda: f.read(4096), b""):
hash_md5.update(chunk)
return hash_md5.hexdigest()
def sign(p,ap,bt,a,k,m):
r=pow(ap,k,p);
s=(inv_mod(p-1,k)*(m-a*r)+(p-1))%(p-1)
kq=[r,s]
return kq
def tinh(m):
kq=0;
for i in range(11,18):
for j in range(0,16):
if (m[i]==base[j]):kq=kq*16+j;
return kq;
#tao chu ky cho file ("file.txt")
# ta can biet cac tham so khoa cong khai (p,ap,bt) van ban
(m) , va cac khoa bi mat(a,k)
p=39935660561
a=34438456399
ap=20679859372

bt=11141505714
k=311680831
m=md5("file.txt");
m=list(m);
m=tinh(m);
kq=sign(p,ap,bt,a,k,m);
print("Chu ky:",kq)

c, Kiểm tra chữ ký
import hashlib,math
base=['0','1','2','3',
'4','5','6','7','8','9','a','b','c','d','e','f']
def inv_mod(a,b):
a1=a;
y0=0;
y1=1;
while (b>0):
r=a%b;
q=(int)(a/b);

12


a=b;b=r;
if (r==0) :break;
y=y0-y1*q;
y0=y1;y1=y;
if (y1 < 0): y1 = y1 % a1;
return y1;
def md5(fname):

hash_md5 = hashlib.md5()
with open(fname, "rb") as f:
for chunk in iter(lambda: f.read(4096), b""):
hash_md5.update(chunk)
return hash_md5.hexdigest()
def verify(p,ap,bt,m,s,r):
kq1=(pow(bt,r,p)*pow(r,s,p))%p
kq2=pow(ap,m,p)
if (kq1==kq2):print("CHU KY PHU HOP")
else: print("CHU KY KHONG PHU HOP")
def tinh(m):
kq=0;
for i in range(11,18):
for j in range(0,16):
if (m[i]==base[j]):kq=kq*16+j;
return kq;
#kiem tra file
# ta can biet cac tham so: khoa cong khai (p,ap,bt), van ban
(m) va chu ky (s,r)
m=md5("file.txt");
m=list(m);
m=tinh(m);
r=12313954204
s=36414863081
p=39935660561
ap=20679859372
bt=11141505714
verify(p,ap,bt,m,s,r);

2.3. Họ sơ đồ chữ kí Elgamal

Sau khi đăng sơ đồ chữ ký Elgamal, thì sau đó một số cải tiến của sơ đồ
này xuất hiện. Quan trọng nhất trong số đó là sơ đồ chữ ký Schnorr và chuẩn
chữ ký DSS (Digital Signature Standard).
2.3.1.

Sơ đồ chữ ký Schnorr

Đây là sơ đồ chữ ký thuộc họ của Elgamal nhưng có những tính chất tốt
hơn so với sơ đồ Elgamal.
13


Sơ đồ chữ ký được cho ở dưới
Thiết lập tham số hệ thống:
1.

Chọn hai số nguyên tố p và q, thỏa mãn điều kiện q|p-1. Và các số này
được chọn sao cho kích thước

2.

g ∈Z

Lựa chọn phần tử
phần tử

f ∈ Z *p

g ≠1


và

q = 160

.

có bậc là q (Để làm điều này thì cần phải lấy

và thực hiện lệnh

lặp lại lệnh đên khi
3.

*
p

p = 1024

g ← f ( p−1) / q (mod p)

. Nếu như g=1 thì

).

{ 0,1} * 

Zq

Lựa chọn hàm hash H:
(Ví dụ có thể chọn SHA-1).

Các tham số (p,q,g,H) sẽ phân bố giữa các người dùng hệ thống.
Hình thành khóa mật và khóa công cộng:
Alice tạo ra số ngẫu nhiên

x ∈ Z *p

và thực hiện lệnh:

y ← g − x (mod p)

.

Các tham số công cộng là (p,q,g,y,H) còn x là khóa mật.
Tạo chữ ký:
Để ký lên bức điện
thành cặp (e, s), ở đây:

m ∈ { 0,1}

*

, thì Alice tạo ra số ngẫu nhiên

l ∈ Zq

và hình

r ← g l (mod p),
e ← H (m || r ),
s ← l + xe(mod q).


Thẩm tra chữ ký:
Để thẩm tra chữ ký, Bob thực hiện các bước sau:
r ' ← g s y e (mod p),
e' ← H (m || r ' ),

14


Verify(p,q,g,y,h)(m,(s,e))=TRUE, nếu như e’=e.

Chú ý rằng khi tạo ra các tham số hệ thống, việc tạo phần tử sinh g có thể
được xác định rất nhanh bởi vì q|p-1.
Việc thẩm tra chữ ký đúng nếu như cặp (m,(s,e)) đúng là cặp “bức điệnchữ ký”, được tạo ra bởi Alice. Nghĩa là:

r ' ≡ g s y e ≡ g xe + l y e ≡ y − e g l y e ≡ g l ≡ r (mod p)

.

Zp

Như chúng ta thấy việc ứng dụng nhóm con bậc q của nhóm cho phép
quá trình ký của sơ đồ Schonorr nhanh hơn nhiều so với sơ đồ Elgamal: Để
chuyển chữ ký của Schonorr cần 2|q| bít, trong khi đó để chuyển chữ ký Elgamal
cần 2|p| bít. Chữ ký ngắn hơn rất nhiều cho phép giảm số lệnh cần thiết để hình
thành chữ ký và thẩm định chữ ký: trong sơ đồ Schonorr tốn O(
trong sơ đồ Elgamal cần O(
2.3.2.

log3 p


log2 q log2 p)

, còn

).

Chuẩn chữ ký DSS

Đây cũng là phiên bản cải tiến của Elgamal. Nó được để xuất năm 1991,
tuy nhiên nó được chấp nhận làm chuẩn từ 01/12/1994. Giống như sơ đồ chữ ký
Schnorr, chuẩn chữ ký DSS cũng có những ưu điểm so với Elgamal.
Sơ đồ chữ ký được miêu tả như sau:
Thiết lập tham số hệ thống:
Các tham số hệ thống giống như sơ đồ chữ ký Schnorr. Và chuẩn DSS
chọn hàm hash là SHA-1. Các tham số của hệ thống là (p,q,g,H) xem sơ đồ
Schnorr.
Tạo khóa:
Alice tạo ra số ngẫu nhiên

x∈Zp

là khóa mật và tính khóa công cộng:

y ← g x (mod p)

.

15



Tham số công khai của Alice bao gồm (p,q,g,y,H) còn x là tham số mật.
Hình thành chữ ký
Để ký lên bức điện m
nên cặp (r,s), với

∈ { 0,1}

*

, Alice tạo số ngẫu nhiên

l ∈Zp

và hình thành

r ← ( g l (mod p))(mod q ),
s ← l −1 ( H ( m) + xr )(mod q).

Thẩm tra chữ ký
Để thẩm tra chữ ký, Bob dùng cặp (m,(r,s)) cho tính toán sau
w ← s −1 (mod q),
u1 ← H (m) w(mod q),
u2 ← rw(mod q),

Verify(p,q,g,y,h)(m,(r,s))=TRUE, nếu như

r = ( g u1 y u 2 (mod p))(mod q)

.


Chúng ta xem việc kiểm tra chữ ký là hợp lý:
Đặt

v = ( g u1 y u 2 (mod p))(mod q) = [ g H ( m ) s

v = [( g s

−1

( H ( m ) + xr )(mod q )

−1

(mod q )

g xrs

−1

(mod q )

)(mod p)](mod q)

)(mod p)](mod q) = [ g l (mod p)](mod q ) = r

Nhứng ưu điểm, những chú ý tương tự sơ đồ chữ ký Schnorr.
2.3.3.

Chuẩn chữ ký của Liên Xô Gost 34-10.94


Sơ đồ này ra đời sau chuẩn DSS của Mỹ nên nó được kề thừa và bổ sung
những ưu việt của mình.
Sơ đồ chuẩn chữ ký GOST 3410.94
Hình thành tham số hệ thống:
Cho p là số nguyên tố, kích thước từ 509 đến 512 bít, q là số nguyên tố
sao cho q|p-1. Số g < p-1 có bậc là q, nghĩa là

g q ≡ 1(mod p )

.
16


Hình thành khóa:
Alice chọn x < q là khóa mật, và Alice đi tính khóa công khai:

y = g x (mod p)

. Các tham số (p,q,g,y) là tham số công khai.

Quá trình ký:
Alice muốn ký lên bức điện M, thì Alice thực hiện các bước sau:
1. Lựa chọn số ngẫu nhiên k.
2. Tính
3. Tính

r = [ g k (mod p)](mod q)
s = ( Mk + xr )(mod q)


.

.

Chữ ký của bản tin M là cặp (r,s).
Quá trình thẩm tra chữ ký:

Bob muốn kiểm tra chữ ký (r,s) có tương ứng với bản tin M và các tham
số mở (p,q,g,y) không, thì Bob thực hiện các bước tính sau:
1. Tính v
2. Tính
3. Tính
4. Tính

v = M q−2 (mod q)

.

z1 = (( sv )(mod q )

z2 = (( q − r )v )(mod q )

.

.

u = [( g z1 y z 2 )(mod p)](mod q)

.


5. Và Bob kiểm tra đẳng thức sau:
Verify(p,q,g,y)(m,(r,s)=TRUE, nếu u=r.
Chúng ta xem hàm kiểm tra chữ ký là hợp lý bằng dãy biến đổi sau:

u = [( g z1 y z 2 )(mod p)](mod q)

=

[( g ( xr + kM ) M

q−2

=

(mod q ) + x ( q − r ) M q − 2 (mod q )

)(mod p)](mod q) =
17


[( g xrM

q−2

(mod q ) + k − xrM q−2 (mod q )

=

)(mod p)](mod q ) =


= [ g k (mod p)](mod q) = r

3. Độ an toàn và thám mã
3.1. Đánh giá độ an toàn
Như trên ta đã nói tội phạm có thể giả mạo chữ kí, giả mạo bức điện hay
có thể đánh cắp khóa mật, đánh cắp chữ kí,…
• Giả sử ta thử giả mạo chữ kí trên bức điện m cho trước mà không biết x a
thì ta có thể chọn r và tìm s tương ứng. Tức ta phải tính logarithm rời rạc
Logrαmya-r.
• Hoặc ngược lại nếu ta chọn s thì ta phải giải phương trình Y arrs=αm(mod
p). Phương trình này còn khó hơn và hiện nay nó chưa có lời giải hoặc
chưa được nghiên cứu.
• Nếu ta chọn (r,s) và thử tìm bức điện m thì ta phải tính Logαyarrs.
• Mặt khác nếu ta tấn công đánh cắp khóa mật xa bằng cách tính Logαya, ta
có thể kí lên bất kì bức điện nào để mạo danh người gửi.
Chúng ta đánh giá độ an toàn của sơ đồ chữ ký Elgamal qua một số cảnh
báo sau.
Cánh báo 1:
Đầu tiên để kiểm tra chữ ký thì cần phải kiểm tra bất đẳng thức r < p. Nếu
như r > p thì có khả năng bị tấn công, cách này đề xuất bởi Bleichenbacher. Giả
sử (r,s) là chữ ký của bức điện m. Tội phạm có thể giã mạo chữ ký với một bức
điện bất kỳ m’ bằng cách hình thành như sau:
1.
2.

u ← m' m −1 (mod p − 1)
s ' = su (mod p − 1)

.
r ' ≡ ru (mod p − 1)


3. Tính r’, thỏa mãn điều kiện
và
thể làm được nhờ áp dụng định lý phần dư Trung Hoa.

r ' ≡ r (mod p )

. Điều này có
18


Chúng ta thấy bức điện m’ với chữ ký (r’,s’) thỏa mãn điều kiện:

y Ar 'r 's ' = y Aru r su ≡ ( y Ar r s )u ≡ α mu ≡ α m ' (mod p)
Tấn công kiểu như thế này là không thể nếu như r < p, bởi vì trong trường
hợp này giá trị r’ được tính toán theo bước 3 ứng dụng định lý phần dư Trung
Hoa theo modulo p(p-1).
Cảnh báo 2:
Cảnh báo này cũng hình thành bởi Bleichenbacher. Alice cần phải lựa
Z *p

α

chọn phần tử ngẫu nhiên từ nhóm . Nếu như tham số này không được lựa
chọn bởi Alice (điều này là có thể, khi hệ thống người sử dụng có một tham số

α

α


mở và p), thì cần phải kiểm tra một số lần rằng
có thể áp dụng hàm tạo số giả ngẫu nhiên).

là số ngẫu nhiên (điều này

α

Giả sử rằng các tham số mở và p được lựa chọn bởi tội phạm Oscar.
Tham số p hình thành trên cơ sở phương pháp chuẩn: Giả sử p-1=bq, với q là số
nguyên tố đủ lớn, nhưng b có thể có thừa số nguyên tố nhỏ, và tính toán
logarithm trong nhóm bậc b không khó).
Oscar hình thành tham số

α

theo cách sau:

α = β t (mod p)
Với

β = cq

,

và c < b.

Chúng ta biết rằng việc tính toán logarith rời rạc của khóa mở y A là bài
toán khó. Thế nhưng tính toán logarith của độ lớn

y Aq


một sự khó khoăn nào. Logarith rời rạc này bằng
mãn đồng dư thức sau:

theo cơ số

αq

z ≡ x A (mod b)

không tạo nên

, có nghĩa thỏa

y Aq = (α q ) z (mod p)

19


Khi tính được giá trị z thì Oscar có thể giả mạo chữ ký của Alice bằng các
lệnh sau đây:
r ← β = cq,
s ← t (m − cqz )(mod p − 1).

Chúng ta xem việc thẩm tra chữ ký:

y Ar r s ≡ y Acq ( β t )( m − cqz ) ≡ α cqzα m − cqz ≡ α m (mod p )
Rõ ràng chúng ta thấy cặp (r,s) là chữ ký của bức điện m, nhưng việc tạo
thành chữ ký này không có sự tham gia của khóa mật x A (mà có sự tham gia của
số xA (mod b)).

Chú ý rằng trong quá trình hình thành chữ ký giả mạo thì số q là ước số
của r. Dẫn đên cách tấn công của Bleichenbacher có thể ngăn chặn nếu như
trong lúc kiểm tra Bob kiểm tra điều kiện q không là ước số của r (giả sử rằng
quá trình lựa chon p thì q là tham số mở).
Cảnh báo 3:
Trong cảnh báo này thì liên quan đến chiều dài của tham số k. Tạo ra chữ
ký theo sơ đồ Elgamal là thuật toán ngâu nhiên bởi vì tham số k được hình thành
ngẫu nhiên.
Alice không bao giờ dùng khóa để ký các bức điện khác nhau là có thời
gian sống ngắn. Nếu như tham số k sử dụng trở lại đối với chữ ký của hai bức
điện m1 và m2, mà hai bức điện thỏa mãn
tính s của sơ đồ chữ ký chúng ta có:

m1 ≠ m2 (mod p − 1)

l ( s1 − s2 ) ≡ m1 − m2 (mod p − 1)

Bởi vì

l −1 (mod p − 1)

, thì từ phương trình

.

tồn tại, và từ bất đẳng thức

m1 ≠ m2 (mod p − 1)

dẫn


đến:

l −1 ≡ ( s1 − s2 ) /( m1 − m2 )(mod p − 1)

,

20


l −1

Có nghĩa bị lộ. Nhưng quan trọng nhất là khóa mật Alice x A có thể tính
toán từ công thức hình thành s, và suy ra xA theo công thức:
x A ≡ ( m1 − ls1 ) / r (mod p − 1)

.

Điều này cho chúng ta thấy chỉ được sử dụng tham số k một lần duy nhất.
3.2. Thám mã
Để thám mã tấn công chữ kí số thực chất là ta đi giải bài toán logarithm
rời rạc tính logab(mod p). Ta sử dụng một số thuật toán sau:
3.2.1.

Thuật toán Shank

a, Thuật toán
Ta tìm a thỏa mãn beta=alphaa (mod p)
Đặt


[ ]

m := p1 / 2 + 1

Bước 1: Tính alphamj mod p với 0<=j<=m-1.
Bước 2: Sắp xếp các cặp (j, alphamj mod p) theo alphamj mod p và lưu vào
danh sách L1
Bước 3: Tính beta*alpha-i mod p với 0<=i<=m-1.
Bước 4: Sắp xếp các cặp (i, beta*alpha-i mod p) theo beta*alpha-i mod p
và lưu vào danh sách L2
Bước 5: Tìm trong hai danh sách L1 và L2 xem có tồn tại cặp ( j, alpha mj
mod p ) và ( i, beta*alpha-i mod p ) nào mà alphamj mod p = beta*alpha-i mod p
(tọa độ thứ hai của hai cặp bằng nhau ).
Bước 6: Tính a= ( mj + i ) mod ( p - 1 ).
b, Code

21


import random,math
def shank(p,ap,bt):
m=round(pow(p-1,0.5));
l1=[];
l2=[];
for i in range (0,m):
l1.append([pow(ap,m*i,p),i])
l2.append([(bt*pow(ap,i,p))%p,i])
l1.sort()
l2.sort()
i=0;j=0;

while (l1[j][0]!=l2[i][0]):
if (l1[j][0]>l2[i][0]):
i=i+1
else:
j=j+1;
a=(m*l1[j][1]-l2[i][1])%(p-1);
return a;

3.2.2.

Thuật toán Pohlig-Hellman

a, Thuật toán
Bài toán: tìm x thỏa mãn
Để tìm

a x ≡ b(mod p)

log a b(mod p − 1)

ta đi thực hiện giải các bài toán con tìm

loga b(mod qα )
với qα là các ước của (p-1). Sau đó sử dụng đinh lí phần dư trung hoa để
tìm

x = log a b(mod p)
Bước 1: Ta phân tích (p-1) ra thừa số nguyên tố
s


p − 1 = ∏ qiα i
i =1

22


Bước 2. Đối với từng số nguyên tố q,

qα || p − 1

, chúng ta tìm

loga b(mod qα )

Đặt
x ≡ log a b(mod q α ) ≡ x0 + x1q + ... + xα −1q α −1 (mod q α )

, với

0 ≤ xi ≤ q − 1

.
Ta có b=aα (mod p) nên:

b( p −1) / q ≡ a ( x0 + x1q +... + xα −1q


α −1

)( p −1) / q


(mod p)

b ( p −1) / q ≡ a x0 ( p −1) / q (mod p )

.

Để tìm x0 ta sử dụng thuật toán shank hoặc thuật toán khác. Tiếp tục với
x1
2

(ba − x0 )( p −1) / q ≡ a x1 ( p −1) / q (mod p )

.

xi

Ta tiếp tục tìm giá trị của x 1 dựa vào x0 đã biêt. Giá trị của
thấy từ phương trình
i −1

(ba − x0 − x1q −... − xi −1q ) ( p −1) / q

Bước 3. Khi tìm đươc

loga b(mod p − 1)

i +1

≡ a xi ( p −1) / q (mod p)


loga b(mod qiα i ), i = 1,..., s

được tìm

.

, chúng ta tìm

theo định lý phần dư trung hoa.

Định lí phần dư trung hoa

23


Như vậy độ phức tạp của thuật toán phục thuộc vào các phần tử q α. Nếu qα
càng lớn thì độ phức tạp của thuật toán càng gần với thuật toán Shank.
b, Code
import random,math
def prime(p):
if (p==2)|(p==3): return 1
if (p<2)|(p%2==0): return 0
for i in range(1,11):
a=random.randint(2,p-1)
if (pow(a,p-1,p)!=1): return 0
return 1
def pt(a):
kq=[];
m=math.ceil(pow(a,0.5));

i=2;
if (prime(a)==1):i=m+1;
while (i<=m):
if (a%i==0):kq.append(i);
while (a%i==0):a=int(a/i)
if (kq[len(kq)-1]==i):
if (prime(a)==1):break;
i=i+1;
if (a>1):kq.append((int)(a));
return kq;
def inv_mod(a,b):
a1=a;
y0=0;
y1=1;
while (b>0):

24


r=a%b;
q=(int)(a/b);
a=b;b=r;
if (r==0) :break;
y=y0-y1*q;
y0=y1;y1=y;
if (y1 < 0): y1 = y1 % a1;
return y1;
def tim(p,ap,bt,q): #shank
m=math.ceil(pow(q,0.5))+1;
l1=[];

l2=[];
for i in range (0,m+1):
l1.append([pow(ap,m*i,p),i])
l2.append([(bt*pow(ap,i,p))%p,i])
l1.sort()
l2.sort()
i=0;j=0;
while (l1[j][0]!=l2[i][0]):
if (l1[j][0]>l2[i][0]):
i=i+1
else:
j=j+1;
a=(m*l1[j][1]-l2[i][1])%q;
return a;
#thuat toan pohlig-hellman
def pohlig(p,ap,bt):
kx=[];
nt=pt(p-1);
for q in nt:
kl=[]
p1=p-1;
e=0;
while (p1%q==0):
e=e+1;
p1=p1/q;
y=1;
a=pow(ap,(int)((p-1)/q),p);
b=pow(bt,(int)((p-1)/q),p);
l=tim(p,a,b,q)
kl.append(l)

x=l;
qj=1;
for j in range(1,e):
qj = qj * q;
y=(y*pow(ap,l*(int)(qj/q),p))%p
b=pow(bt*pow(y,p-2,p),(int)((p1)/qj/q),p)

25