Mã nén lecture7 -ElGamal

1
Lecture 7: Hệ mật mã ElGamal

1. Nhóm nhân modulo N

2. Tính lũy thừa theo module

3. Logarit rời rạc

4. Hệ mật mã ElGamal
2
Nhóm nhân modulo N

Nhóm nhân (phép nhân ) của tậpZ
n
được định nghĩa
như sau:

Trong trường hợp đặcbiệtnếun làsố nguyên tố thì:
{ }
1),(|
*
=∈= naUSCLNZaZ
nn
{ }
11
*
−≤≤= naZ
n
3
Nhóm nhân modulo N
4
Nhóm nhân modulo N

Định nghĩa: Cho a thuộc Z
n
*
, nếu cấp của a là φ(n),
khi đó a được gọi là phần tử sinh hay phần tử nguyên
thủy của Z
*
n
.
5
Tính chất phần tử sinh của Z
*
n

Nếu a là phần tử sinh của Z
*
n
thì
Z
*
n
={a
i
mod n| 0=<i<=φ(n) -1}

Giả sử a là một phần tử sinh của Z
*
n
, khi đób=a
i
mod
n cũng là phần tử sinh của Z
*
n
khi và chỉ khi gcd(i,
φ(n) )=1
6
Phần tử sinh của Z
*
n

Xét Z*
13
, kiểm tra a=2 có phải là phần tử sinh hay
không:

Như vậy a=2 là phần tử sinh, khi đó2
i
cũng là phần
tử sinh khi và chỉ khi gdc(i,12)=1 nghĩa là i=1, 5, 7.
Vậy 2, 6, 11 là các phần tử sinh của Z*
13
7
Tính lũy thừa theo module

Áp dụng định lý Euler (a
ø(n)
= 1 (mod n) - với mọi a,
n trong đó gcd(a,n)=1) để tính lũy thừa theo module:

Ví dụ : Tính 7
222
(mod 10)
Ta có 7 và 10 là 2 số nguyên tố cùng nhau.
Và φ(10) = 4. =>Do đó7
4
≡ 1 mod 10.
Phân tích: 7
222
= 7
4.45+2
≡ 7
2
= 49 ≡ 9 (mod 10)
8
Logarit rời rạc

Vấn đề logarit rời rạc: cho p là một số nguyên tố, a là phần tử
sinh của . Tìm x (0≤x≤p−2) sao cho a
x
≡ b (mod p).

Hiệnnay chưacóthuậttoánhiệuquả nào để tính logarit rờirạc
tổng quát. Có nhiềuthuậttoánchạy nhanh hơncácthuậttoán
thô sơ, nhưng vẫncònchậmhơn so vớithờigianđathức.

Thuật toán Baby-step/giant-step

Thuật toán Pohlig-Hellman

Thuật toán tính chỉ số
**
,
pp
ZbZ ∈
9
Thuật toán BABY-STEP/GIANT-STEP

Ýtưởng

ThuậttoánBaby-step/giant-step dựatrêncơ sở x =
im + j vớim làmộthằng số, 0 ≤ i, j < m.

Khi đóa
x
= a
im+j
≡ b (mod p) ⇔ a
j
≡ b.a
-im
(mod p)

Giảithuậttínhtrướca
j
vớimộtvàigiátrị j.
Cốđịnh m và thử các giá trị i có thể cho đếnkhithỏa
mãn.
10
Thuật toán BABY-STEP/GIANT-STEP

m=Ceiling( )

Tính a
j
mod p (0 ≤ j ≤ m-1), lưucặp(j, a
j
mod p)
được danh sách L1

Tính b.a
-im
mod p (0 ≤ i ≤ m-1), lưucặp (i, b.a
-im
mod
p) đượcdanhsáchL2

Tìm trong danh sách L1 mộtcặp (j, y) và L2 mộtcặp
(i, y). Có phầntử thứ 2 bằng nhau.

Đặt x = im + j
1−p
11
Thuật toán BABY-STEP/GIANT-STEP

ví dụ

Cho p = 113, a = 3, b =57. Tìm x = log
3
57 mod 113.
1/ Ta có m=Ceiling( ) = 11.
2/ Xây dựng bảng (j, a
j
), danh sách L1

Sắpxếpbảng L1 theo thành phầnthứ 2
j 0123 45678910
3
j
mod 113 1 3 9 27 81 17 51 40 7 21 63
j 0182 5 9376104
3
j
mod 113 1 3 7 9 17 21 27 40 51 63 81
112
12
Thuật toán BABY-STEP/GIANT-STEP

a
-1
= 3
-1
mod 113 = 38, a
-m
= 38
11
mod 113 = 58
3/ Xây dựng bảng (i, b.a
-im
), danh sách L2

Sắpxếpbảng L2 theo thứ tự thành phầnthứ 2

Ta thấyb.a
-9m
= 3 = a
1
. i = 9, j = 1, m = 11.
x = mi+j = 11*9 + 1 = 100

Kiểmtra3
100
mod 113 = 57
i 01 2 3 4 56789
b.(a
-m
)
i
57 29 100 37 112 55 26 39 2 3
i 012 3 4 56789
b.(a
-m
)
i
57 29 100 37 112 55 26 39 2 3
13
Hệ mật mã ELGAMAL

Hệ mật mã ElGamal là hệ mậtmãbất đốixứng (hệ
mật khóa công khai) dựatrênvấn đề logarit rờirạc
được Taher ElGamal đưaranăm 1984.
14
Hệ mật mã ELGAMAL

Thựcthể A thựchiện các bướcsauđể tạo ra khóa
công khai và khóa bí mậttương ứng:

1. Sinh ra mộtsố nguyên tố lớn p và a là mộtphần
tử sinh thuộc nhóm nhân modulo p

2. Chọnngẫunhiênx, 1≤x≤p−2, tính giá trị b = a
x
(mod p).

3. Khóa công khai là bộ 3 (p, a, b), khóa bí mậtlà
x

Thựcthể B mã mậtbản tin (gửitớiA) như sau:

1. Nhận khóa công khai từ thựcthể A (p, a, b).
*
p
Z

Xem chi tiết: Mã nén lecture7 -ElGamal