Chu Ky Elgamal | 9linux

CHỮ KÝ ELGAMAL

4.3.1. Sơ đồ chữ ký Elgamal

Sơ đồ (Elgamal đề xuất năm 1985)

1/. Tạo cặp khóa (bí mật, công khai) (a, h) :

Chọn số nguyên tố p sao cho bài toán logarit rời rạc trong Zp là “khó” giải.

Chọn phần tử nguyên thuỷ gZp* . Đặt P = Z p*, A = Z p* x Z p-1.

Chọn khóa bí mật là a Zp* . Tính khóa công khai hga mod p.

Định nghĩa tập khóa: = {(p, g, a, h): hga mod p}.

Các giá trị p, g, h được công khai, phải giữ bí mật a.

2/.Ký số: Dùng 2 khóa ký: khóa a và khóa ngẫu nhiên bí mật rZp-1* .

(Vì rZp-1* , nên nguyên tố cùng p -1, do đó tồn tại r-1 mod (p -1) ).

Chữ ký trên xPlà y = Sig a(x, r) = (, ), yA(E1)

Trong đó Z p*,  Zp-1:

 = gr mod p và  = (x – a *  ) * r-1 mod (p -1)

3/.Kiểm tra chữ ký:

Ver k (x, , ) = đúng h*gx mod p. (E2)

Chú ý: Nếu chữ ký được tính đúng, kiểm thử sẽ thành công vì

h*ga* gr* mod p g(a +r* ) mod p gx mod p.

Do  = (x – a *  ) * r-1 mod (p -1) nên (a *  + r *) x mod (p-1).

Ví dụChữ ký Elgamal trên dữ liệu x = 112.

1/. Tạo cặp khóa (bí mật, công khai) (a, h) :

Chọn số nguyên tố p = 463. Đặt P = Z p*, A = Z p* x Z p-1.

Chọn phần tử nguyên thuỷ g = 2Zp* .

Chọn khóa bí mật là a = 211Zp* .

Tính khóa công khai hga mod p = 2211 mod 463 = 249.

Định nghĩa tập khóa: = {(p, g, a, h): hga mod p}.

Các giá trị p, g, h được công khai, phải giữ bí mật a.

2/.Ký số: Chọn ngẫu nhiên bí mật r = 235 Zp-1* . Khóa ký là (a, r ).

Vì rZp-1* , nên nguyên tố cùng p -1, do đó tồn tại r-1 mod (p -1). Cụ thể:

UCLN(r, p-1) = UCLN(235, 462) = 1, nên r-1 mod (p-1) = 235 -1 mod 462 = 289.

Chữ ký trên dữ liệu x = 112 là ( ,  ) = (16, 108), trong đó:

 = gr mod p = 2235 mod 463 = 16

 = (x – a *  ) * r-1 mod (p -1) = (112– 211 * 16) * 289 mod 462 = 108

3/.Kiểm tra chữ ký: Ver k (x, , ) = đúng h*gx mod p.

h* = 24916* 16 108mod 463 = 132

gx mod p = 2112 mod 463 = 132.

Hai giá trị đó bằng nhau, như vậy chữ ký là đúng.

4.3.2. Độ an toàn của chữ ký Elgamal

* Bài toán căn bản bảo đảm độ an toàn của Sơ đồ chữ ký Elgamal:

Bài toán tính Logarit rời rạc:

Biết khóa công khai hga mod p.

Nên có thể xác định khóa bí mật a bằng cách tính Log gh.

4.3.2.1. Vấn đề giả mạo chữ ký Elgamal

1). Trường hợp 1: Giả mạo chữ ký khôngcùng với tài liệu được ký.

+ H cố gắng giả mạo chữ ký trên x, mà không biết khóa bí mật a.

Như vậy, H phải tính được  và .

* Nếu chọn trước , H phải tính  qua đẳng thức h*gx mod p (E2)

Tức là gxh–mod p hay  loggxh–mod p.

* Nếu chọn trước , H phải tính  qua phương trình: h*gx mod p.

Hiện nay chưa có cách hữu hiệu 2 trường hợp trên, nhưng phỏng đoán là khó hơn bài toán logarit rời rạc.

Có thể có cách tính ,  đồng thời với (, ) là chữ ký ? Chưa có trả lời rõ !

* Nếu chọn trước , , sau đó tính x, H phải đối đầu với bài toán logarit rời rạc.

Ta có h*gx mod p (E2).

Như vậy x logggx loggh*

2). Trường hợp 2: Giả mạo chữ ký cùng với tài liệu được ký.

H có thể ký trên tài liệu ngẫu nhiên bằng cách chọn trước đồng thời x,,.

Cách 1

* Chọn x,, thoả mãn điều kiện kiểm thử như sau:

Chọn các số nguyên i, j sao cho 0  i, j  p-2, (j, p-1) = 1 và tính:

 = g i h j mod p,  = –  j -1 mod (p -1), x = –  i j -1 mod (p -1).

Trong đó j -1 được tính theo mod (p -1) (nghĩa là j nguyên tố với p-1).

* Chứng minh (, ) là chữ ký trên x, bằng cách kiểm tra điều kiện kiểm thử:

hh (g ihj ) – . j -1mod p hg – i . .j-1h–mod p gx mod p

Ví dụ

* Chọn các tham số của sơ đồ chữ ký Elgamal:

Số nguyên tố p = 463, phần tử sinh g = 2, Khóa bí mật a = 135.

Khóa công khai h = ga mod p = 2 135 mod 463 = 272.

* Chọn x,, thoả mãn điều kiện kiểm thử như sau:

Chọn i = 89, j = 125, 0  i, j  p-2, (j, p-1) = 1. Tính j -1 mod (p-1) = 377.

 = gi * hj mod p = 289 * 272125 mod 463 = 218

 = –  * j -1 mod (p -1) = -218 * 377 mod 462 = 50

x = – * i * j -1 mod (p -1) = -218 * 89 * 377 mod 462 = 292

* (, ) = (218, 50) là chữ ký trên x = 292, vì thỏa mãn điều kiện kiểm thử:

h* = 272 218 * 218 50 322 (mod 463)

gx = 2 292322 (mod 467)

Cách 2

* Nếu (, ) là chữ ký trên tài liệu x có từ trước, thì có thể giả mạo chữ ký trên

tài liệu x’ khác.

+ Chọn số nguyên k, i, j thỏa mãn 0  k, i, j  p-2, (k  – j , p-1) = 1 và tính:

 = kgihj mod p,  =  (k  – j ) -1 mod (p -1),

x’ =  (k x + i ) (k  – j ) -1 mod (p -1)

* (, ) là chữ ký trên x’, vì thỏa mãn điều kiện kiểm thử:

hgx’ mod p.

Chú ý

Cả hai cách giả mạo nói trên đều cho chữ ký đúng trên tài liệu tương ứng, nhưng đó không phải là tài liệu được chọn theo ý của người giả mạo. Tài liệu đó đều được tính sau khi tính chữ ký, vì vậy giả mạo loại này trong thực tế cũng không có ý nghĩa nhiều.

Share this:

• Facebook
• X

Like Loading...

Related