Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell

Sinh viên thực hiện: Trần Trung Hiếu 1 Lớp CT 702
LỜI GIỚI THIỆU

1. Bỏ phiếu điện tử - thực trạng

Trong suốt nhiều thế kỷ gần đây trong lịch sử thế giới, các cuộc bầu cử đã giữ một vai trò
quan trọng trong việc xác lập các thể chế chính trị của các quốc gia từ lớn đến nhỏ. Trong
thế giới hiện đại, việc bỏ phiếu bầu quốc hội (ở Anh, Mỹ là Hạ Nghị Viện, ở Nga là
Duma quốc gia ) là một trong số những s
ự kiện quan trọng nhất của đất nước. từ những
năm 1990, khi internet bùng nổ, một câu hỏi đã được quan tâm là: liệu một ngày nào đó,
có thể thực hiện việc bỏ phiếu qua internet? Nhiều nước ở châu Âu đã chuẩn bị nghiên
cứu với nhiều dự án cùng nhiều chiến lược khác nhau, dưới nhiều góc độ: Kỹ thuật, Luật,
Chính sách, Xã hội. Ngoài ra, bỏ phiếu điện t
ử cũng được nghiên cứu ở các nước khác
như Mỹ, Braxin, Mêhicô, Nga, Ấn Độ.
Người ta đã bỏ ra rất nhiều công sức vào việc cải tiến các phương thức bầu cử, khiến cho
các cuộc bầu cử ngày càng trở lên tốt hơn. Các phương thức này được thay đổi theo từng
thời kỳ, theo sự tiến bộ của xã hội. Trong xu thế thực hiện “chính phủ điện tử
” thì việc số
hóa cuộc bầu cử để thay thế cho phương thức truyền thống là điều sẽ phải diễn ra trong
tương lai gần.
Trong các ứng dụng an toàn thông tin, thì bỏ phiếu điện tử (E-Voting) là ứng dụng đòi hỏi
tính bảo mật cao nhất. Vì chính sự thành công hay thất bại của nó có ảnh hưởng nhiều
nhất đến bộ mặt chính trị, xã hội của tổ chứ
c, quốc gia đó.

2. Bỏ phiếu điện tử và sơ đồ chia sẻ bí mật


1.1.10.Nhóm Cylic
1.1.11.Không gian vectơ
1.1.1.12.Trường hữu hạn
1.1.1.13.Các thuật toán trong trường hữu hạn
1.1.1.14.Độ phức tạp của thuật toán
1.2. Các hệ mật mã Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell

Sinh viên thực hiện: Trần Trung Hiếu 3 Lớp CT 702
Sơ đồ khối một hệ truyền tin mật

(e
k
(x)) = x với mọi x
∈
P

1.2.1.Mã cổ điển

B A
Bản tin mật mã
Kênh công cộng
Kênh an toàn
Bản tin gốc
Bộ mã
hoá
Bộ giải
mã
Hinh 1.1 Sơ đồ truyền tin trong hệ mật
khoá đối xứn
g

Nguồn tin Bộ mã hóa
Kênh mở
(không an toàn)
Bộ giải mã Nhận tin
Thám mã
Kênh an toàn
Nguồn khóa
Bản rõ Bản mã Bản mã
K

26
với k ∈ K, định nghĩa e
k
(x) = (x + k) mod 26
d
k
(y) = (y – k) mod 26
(x, y ∈ Z
26
)
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
, π

26
)
m
với mỗi khoá k = (k
1
, k
2
,…,k
m
) ∈ K có:
e
k
(x
1
, x
2
,…, x
m
) = (x
1
+ k
1
, x
2
+ k
2
,…, x
m
+ k
m

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
,…, x
m
) = (x
1
, x
2
,…, x
m
).k
d
k
(y
1
, y
2

21

( )
mk
yyyd ...,,,
21
=
() ( ) ( )
( )
m
yyy
111
...,,,
21
−−−
πππ

với mỗi k = π ∈ S
m
, ta có
Trong đó π
-1
là hoán vị nghịch đảo của π


Cho n = p.q trong đó p và q là các số nguyên tố. Đặt P = C = Z
n
và định nghĩa:
K = {(n, p, q, a, b): n = p.q, p, q là các số nguyên tố, a.b ≡ 1 mod φ(n)}
Với K = (n, p, q, a, b) ta xác định: e
K
(x) = x
b
mod n
và d
K
(y) = y
a
mod n
(x, y ∈ Z
n
) Các giá trị n và b được công khai và các giá trị p, q, a được giữ kín
1.2.2.2. Mã Elgamal
(1) Public key
(2) Bản mã
Kênh công cộng
Bản tin gốc
A

Bản tin gốc
Bộ lâp mã
(public key)
Bộ giải mã
(public key)
Hinh 1.2 Sơ đồ truyền tin trong hệ mật mã

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
α
β.
Định nghĩa mã hoá công khai Elgamal trong
*
p
Z
:
Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong
p
Z
là khó giải.
Cho α ∈
*
p
Z
là phần tử nguyên thuỷ. Giả sử P =
*
p
Z
, C =
*
p

mod p
với y
1
, y
2
∈
*
p
Z
ta xác định:
d
K
(y
1
, y
2
) = y
2
(y
1
a
)
– 1
mod p

Vấn đề về kiểm tra
Chữ ký được kiểm tra bằng cách so
sánh nó với chữ ký xác thực khác. Tuy
nhiên, đây không phải là một phương
pháp an toàn vì nó dễ bị giả mạo.
Vấn đề về kiểm tra
Chữ ký điện tử có thể kiểm tra nhờ
dùng một thuật toán “kiểm tra công
khai”. Như vậy, bất kì ai cũng có thể
kiểm tra được chữ ký điện tử. Việc dùng
chữ ký điện tử an toàn có thể chặn được
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.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)
Báo cáo tóm tắt Sơ đồ chia sẻ bí mật dựa trên không gian vectơ Brickell

Sinh viên thực hiện: Trần Trung Hiếu 9 Lớp CT 702
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ý.

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
a
modn ,
ver
k”
(x,y ) = đúng ↔ x ≡ y
b
(modn).
Dễ chứng minh được rằng sơ đồ được định nghĩa như vậy là hợp thức, tức là với
mọi x ∈ P và mọi chữ ký y ∈ A:
ver
k”
(x,y ) = đúng ↔ y = sig
k’
(x)
Chú ý rằng tuy hai vấn đề xác nhận và bảo mật theo sơ đồ RSA là có bề ngoài giống

, 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’
((x, sig
k’s

(x)). Nhận được văn bản mật mã đó B sẽ dùng thuật toán giải mã d
k’’
của mình để thu
được (x, sig
k’s
(x)), sau đó dùng thuật toán kiểm thử chữ ký công khai ver
k”s
của A để xác
nhận chữ ký sig
k’s
(x) đúng là của A trên x.
2.4.Sơ đồ chữ ký Elgamal

*
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”
(x,(γ , δ)) = đúng ↔ β
γ
. γ
δ
≡ α
x
(modp).
Dễ thấy rằng sơ đồ chữ ký được định nghĩa như trên là hợp thức. Thực vậy, nếu
sig
k’
(x,k ) = (γ , δ) thì ta có :
β
γ
. γ
δ

các tập con có khả năng khôi phục bí mật.
3.2 Một số sơ đồ chia sẻ bí mật:
3.2.1 Sơ đồ chia sẻ bí mật sơ khai:
Một s
ơ đồ chia sẻ bí mật đảm bảo tính bảo mật là sơ đồ trong đó bất kỳ người nào
có ít hơn t phần dữ liệu (là số lượng đủ để khôi phục bí mật) không có nhiều thông tin hơn
một người không có dữ liệu. Xem xét sơ đồ chia sẻ bí mật sơ khai trong đó cụm từ bí mật
“password” được chia thành các phần “pa…”,”ss…”,”wo…”và ”rd…”. Một người không
có một trong các phần bí mật đó chỉ biế
t mật khẩu có 8 chữ cái. Anh ta sẽ phải đoán mật
khẩu đó từ 2
26
=8 tỷ khả năng có thể xảy ra. Một người có một phần trong số 6 phần của
mật khẩu đó sẽ phải đoán 6 chữ cái tương đương với 2
26
khả năng. Hệ thống này không
phải là một sơ đồ chia sẻ bí mật bảo mật bởi vì một người tham gia có ít hơn t phần dữ
liệu thu được một phần đáng kể thông tin về bí mật.Trong một sơ đồ bảo mật, mặc dù một
người tham gia chỉ thiếu một phần dữ liệu cũng có thể sẽ đối mặt với 26
8
= 208 tỷ khả
năng.
3.2.2 Sơ đồ chia sẻ bí mật tầm thường
Có một vài sơ đồ chia sẻ bí mật trong đó yêu cầu tất cả những người tham gia phải
cùng nhau khôi phục lại bí mật :
• Mã hóa bí mật thành một số nguyên S. Đưa cho mỗi người tham gia i một số ngẫu
nhiên r
i
(trừ một người).
Đưa cho người cuối cùng một số (S- r