Vấn đề An toàn thông tin
TRONG ĐẤU GIÁ ĐIỆN TỬ
Đấu giá kín và chọn giá cao nhất
(First-price Sealed-bid Auction)
Trịnh Nhật Tiến


Chương 1. ĐẤU GIÁ ĐIỆN TỬ
1.1. ĐẤU GIÁ TRUYỀN THỐNG
1.2. ĐẤU GIÁ ĐIỆN TỬ
Chương 2. MÔ HÌNH ĐẤU GIÁ KÍN CHỌN GIÁ CAO NHẤT
2.1. GIỚI THIỆU
2.2. GIAO THỨC ĐẤU GIÁ
2.3. TÍNH AN TOÀN CỦA MÔ HÌNH ĐẤU GIÁ
2.4. CÁC YÊU CẦU CỦA MÔ HÌNH ĐẤU GIÁ
2.5. KỸ THUẬT ĐỂ THỰC HIỆN CÁC YÊU CẦU ĐẤU GIÁ

DANH MỤC CÁC TỪ VIẾT TẮT

ASCII
CA
RA
PIN
URL
DNS
AM
B
ID

American Standard Code for Information Interchange.
(Bộ ký tự chuẩn dùng trong máy tính)

khả năng mua được). Quá trình này sẽ diễn ra liên tục cho đến khi tất cả số
lượng hàng đã được bán. Và kết quả thu được là có các mức giá khác nhau
giành cho những người mua khác nhau và dĩ nhiên người mua đầu tiên sẽ phải
trả với mức giá cao nhất .
Đấu giá theo kiểu Hà Lan chỉ áp dụng đối với những mặt hàng có thời
gian tồn tại ngắn như hoa, rau… Đấu giá kiểu này thường diễn ra rất nhanh do
đó những người tham gia phải nhanh chóng có quyết định nếu họ thực sự
muốn mua món hàng.

3


1.1.3. Đấu giá kiểu Anh (English Auction)
Đấu giá kiểu Anh cũng được biết đến như là đấu giá với giá tăng
(Ascending - Price Auction). Giá khởi điểm của mô hình này là một giá rất
thấp sau đó người mua sẽ ra giá tăng dần một cách lần lượt cho món hàng.
Cuộc đấu giá vẫn tiếp tục cho đến khi không còn ai đưa ra giá cao hơn một
mức giá nào đó hoặc thời gian đã kết thúc. Vào thời điểm đó người chủ trì sẽ
gõ một cái búa xuống bàn và chỉ định người ra giá cao nhất là người thắng
cuộc.
Đấu giá kiểu Anh thường được áp dụng đối với các mặt hàng có giá trị
lớn như các tác phẩm nghệ thuật, rượu vang, hợp đồng và các mặt hàng khác
có thời gian tồn tại không giới hạn. Trong hình thức này người thắng cuộc
luôn luôn phải trả giá cao nhất để có thể sở hữu món hàng.
1.1.4. Đấu giá kín và chọn giá cao nhất (Sealed bid first price auction)
Hình thức đấu giá này là không phải là hình thức đấu giá mở (open bid
auction), nghĩa là giá đưa ra đấu được giấu, không cho những người khác
tham gia đấu giá biết. Quá trình tiến hành đấu giá trải qua hai giai đoạn: giai
đoạn đặt giá trong đó tất cả giá đưa ra được tập hợp lại, và giai đoạn quyết
định kết quả trong đó danh sách giá đưa ra sẽ được tiến hành kiểm tra và

1.2. ĐẤU GIÁ ĐIỆN TỬ
1.2.1. Giới thiệu về đấu giá điện tử
Ngày nay khoa học kỹ thuật phát triển mạnh mẽ trên nhiều phương diện
trong đó có công nghệ thông tin và viễn thông. Sự ra đời của internet đã làm
cho thương mại điện tử phát triển nhanh chóng và chi phối sâu sắc đến đời
sống con người trên nhiều lĩnh vực khác nhau. Một trong những lĩnh vực đạt
thành công rực rỡ nhất đó là đấu giá (auction). Điển hình cho những thành
công đó không thể không kể đến những sàn đấu giá nổi tiếng như ebay, ubid
v.v. Còn ở Việt Nam tuy thương mại điện tử còn mang tính trải nghiệm nhưng
đã xuất hiện các sàn đấu giá như chodientu.com, chodaugia.com, heya.com...
Không phải ngẫu nhiên mà thương mại điện tử lại thành công đến vậy,
điều này có thể giải thích bằng những lợi ích mà thương mại điện tử mang lại
nhờ sự kết hợp giữa đấu giá truyền thống và sức mạnh thương mại điện tử. Đó
là khả năng tạo ra môi trường cạnh tranh công bằng, người mua và người bán
có quyền bình đẳng như nhau. Người mua có thể tìm kiếm, tiếp cận với nhiều
mặt hàng và có cơ hội được ra giá. Còn người bán có cơ hội giới thiệu, quảng
cáo các mặt hàng của mình và bán được chúng với giá mong muốn. Như vậy
một lần nữa ta có thể khẳng định rằng sự kết hợp gữa đấu giá truyền thống và
thương mại điện tử là sự kết hợp đúng đắn nó đáp được nhu cầu của cả 2 bên
mua và bán đồng thời nó cũng phản ánh đúng quy luật cung cầu trên thị
trường một yếu tố cơ bản để tạo nên sự thành công rực rỡ. Do vậy nên việc
phổ biến hình thức đấu giá trên mạng hay còn gọi là đấu giá điện tử thực sự
được coi là cần thiết.
Đấu giá điện tử là hình thức đấu giá được tiến hành trực tuyến, giống
như đấu giá thông thường ngoại trừ nó được tiến hành trên máy tính. Chính vì
sự khác nhau này làm cho đấu giá điện tử phải tuân theo những quy tắc cũng
như những đặc tính của thương mại điện tử và có những đặc thù riêng.

3


tác thứ ba cung cấp dịch vụ này. Những mặt hàng được lựa chọn đem đấu giá
thường được đi kèm với các thông tin liên quan và tuân thủ những quy tắc
nhất định để có thể bán đấu giá được như số lượng, tính độc đáo, tính lịch sử,
văn hóa hay tính cá nhân của sản phẩm. Để mua hàng tại các trang web đấu
giá trước hết người mua sẽ chọn các mặt hàng mình muốn theo danh mục các
mặt hàng được trình bày rõ tại các trang web. Sau khi lựa chọn mặt hàng
muốn mua, người mua sẽ phải tham gia đấu giá với những người mua khác
bằng cách cung cấp một số thông tin như là đặt giá cho mặt hàng muốn mua
và số lượng muốn mua mặt hàng đó. Trang web sẽ tự động làm việc, và khi
thời hạn kết thúc, hệ thống sẽ thông báo kết quả đấu giá đến cho những người
liên quan.
1.2.4. Các luật trong đấu giá điện tử
Trong thương mại điện tử, cũng tùy vào từng sàn giao dịch mà có các
ràng buộc khác nhau, các nguyên tắc phải tuân thủ khác nhau, và mọi hoạt
động trong lĩnh vực này đều phải tuân theo pháp luật về thương mại điện tử.
Tuy nhiên có một số quy định mà hầu như các sàn giao dịch đấu giá điện tử
đều tuân thủ như sau:
Thời hạn kết thúc đấu giá với một mặt hàng: Để tránh tình trạng có quá
nhiều mặt hàng tồn đọng trên trang web, khi một mặt hàng được đưa lên bán
đấu giá, chủ hàng phải xác định thời hạn chấm dứt đấu giá. Thời hạn càng lưu
lên trang web lâu, mức phí chủ hàng phải trả cho chủ trang web càng lớn.

5


Ví dụ mặt hàng được đưa lên vào đầu tháng 04/2006 thì chủ hàng sẽ có
thông báo rằng mặt hàng đó chỉ được đấu giá đến ngày 01/05/2006 muốn để
mặt hàng đấu giá đến hết tháng 01/2006 chủ hàng phải trả thêm một chi phí
nữa cho website
Thắng lợi trong đấu giá điện tử: Không phải khi nào việc đấu giá cũng

Đối với giai đoạn đăng ký: cần xác thực những thông tin của hai bên
tham gia.
Đối với người mua, hệ thống phải xác thực những thông tin như: họ tên,
ngày tháng năm sinh, số CMT, email …đặc biệt là phải xác thực về tài khoản
của người mua, xem tài khoản đó có thực hay không? Nếu có thì tài khoản đó
có đủ để tham gia vào phiên đấu giá đó không?
Đối với người bán, hệ thống tập trung xác thực vào các sản phẩm người
chủ hàng cần đấu giá. Khi người bán đăng ký sản phẩm, sẽ có bộ phận xác
định xem sản phẩm đó có hay không, là hàng thật hay hàng giả, giá trị thực tế
là bao nhiêu.
Thông tin của người đấu giá sau khi đăng ký hoàn toàn được giữ kín
cho đến khi kết thúc phiên đấu giá. Nếu anh ta là người thắng cuộc thì danh
tính của anh ta mới được tiết lộ để mọi người có thể kiểm tra. Nếu không phải
là người thắng cuộc thì danh tính của anh ta sẽ khôgn bị lộ diện. Như vậy,
phiên đấu giá đảm bảo được tính ẩn danh người đấu giá.

7


Giai đoạn 2: Giới thiệu sản phẩm và thiết lập phiên đấu giá
Ở giai đoạn này, hệ thống và người bán một lần nữa thẩm định lại giá
trị của sản phẩm. Sau đó mô tả sản phẩm đấu giá một cách chi tiết nhất để làm
nổi bật giá trị của sản phẩm, nhằm thu hút những khách hàng tiềm năng. Đồng
thời đưa ra các quy tắc đấu giá đối với người tham gia như là giải thích các
quy luật đấu giá được sử dụng (đấu giá mở, đấu giá kín, đấu giá kiểu Hà Lan,
đấu giá kiểu Anh…), những con số được đưa ra đàm phán (giá khởi điểm,
ngày giao hàng, cách thanh toán…), thời gian bắt đầu cuộc đấu giá, điều kiện
để cuộc đấu giá kết thúc. Dựa vào quảng cáo và các quy tắc của cuộc đấu giá,
người mua có thể tìm kiếm để lựa chọn sản phẩm đấu giá và các kiểu đấu giá
phù hợp.

Có nhiều mô hình đấu giá, trong chương này chúng tôi tập trung nghiên
cứu tìm hiểu mô hình đấu giá kín chọn giá cao nhất.
Trong một cuộc đấu giá theo kiểu Anh, rất dễ đáp ứng thuộc tính xác
thực công khai vì các giá trong cuộc đấu giá đều được công khai. Tuy nhiên,
trong cuộc đấu giá kín thật khó có thể nhận ra tính xác thực công khai vì mỗi
giá đều được giữ bí mật.
Mô hình đấu giá kín và lấy giá cao nhất thỏa mãn tính xác thực công
khai. Điều quan trọng là chuyên gia phải đáp ứng được tính nặc danh nhằm
bảo mật thông tin cho người muốn mua món hàng và quá trình trả giá của
người tham gia đấu giá.
Theo mô hình này, tính nặc danh chỉ được nhận ra bởi người quản lý
cuộc đấu giá (AM), không trực tiếp để lộ trong quá trình đấu giá. Chúng tôi sử
dụng đặc tính khác biệt này để giúp người quản lý cuộc đấu giá nhận ra tính
nặc danh và không để lộ trực tiếp các thông tin về giá thua cuộc.
Cho đến nay hầu hết các cuộc đấu giá kín đều được đánh giá là đảm bảo
tính xác thực và đảm bảo tính bảo mật về cổ phiếu của những người có giá
thua cuộc.
Tính bảo mật của những giá thua cuộc:
Mô hình này nên được bảo mật cho tất cả những giá được đưa ra ngoại
trừ người chiến thắng. Về phía người quản lý cuộc đấu giá, thì thuộc tính
riêng của người thua cuộc phải được giữ bí mật.
Tính bảo mật của những giá thua cuộc không được yêu cầu trong hình
thức bán đấu giá theo kiểu Anh bởi vì tất cả những giá thua cuộc đều được
công khai. Chính vì vậy sự cần thiết của tính bảo mật cho giá thua cuộc phụ
thuộc vào mục tiêu của đấu giá điện tử.

10


Như sẽ trình bày dưới đây, chúng ta chú trọng đến cuộc bán đấu giá kín

Tính hiệu quả của quá trình: chi phí cho việc sử dụng máy tính và việc
thông tin trong quá trình trả giá là có ích.

12


2.2. GIAO THỨC ĐẤU GIÁ
2.2.1. Các ký hiệu
n : số người tham gia đấu giá (bidder) Bi, (i = 1, ..., n)
k : số bit của L
L : số điểm giá L = 2 k
i : danh mục của khách hàng đấu giá Bi (i = 1, ..., n)
~

ri, ri , Ri : các số ngẫu nhiên (random) của Bi
xi : khóa bí mật của người đấu giá Bi
yi : khóa công khai của người đấu giá Bi
xC: khóa bí mật của người quản lý đấu giá (Auction Management) AM.
yC : khóa công khai của AM.
ENC(D, k): thuật toán mã hóa, DEC(D, k): thuật toán giải mã
(k là khóa, D là dữ liệu)
Mi : vector đấu giá của người đấu giá Bi
ƒ() : hàm một chiều (hàm băm) của AM.
2.2.2. Khởi tạo
AM thiết lập hàm một chiều ƒ() và chuyển cho tất cả các Bs.
Người bán hàng υ (Vendor) muốn bán một món hàng, sẽ gửi yêu cầu
của mình đến AM.
Trước khi bắt đầu một phiên đấu giá, Bi thực hiện các bước sau:
Tạo một cặp khóa (khóa bí mật xi , khóa công khai yi).
Sau đó gửi yi đến AM và nhận chứng chỉ công khai của mình từ AM.

21
22
23
24
25
26
27
28
29
30
31

Điểm ghi giá
00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000

14000 $
15000 $
16000 $
17000 $
18000 $
19000 $
20000 $
21000 $
22000 $
23000 $
24000 $
25000 $
26000 $
27000 $
28000 $
29000 $
30000 $
31000 $
32000 $

Hình 2.1: Các điểm ghi giá

14


Theo công thức có 2k (= L) điểm ghi giá cho k bits. Một giá được biểu
diễn bởi một vector đấu giá Mi. Theo ví dụ trên, điểm ghi giá là số nhị phân
tương ứng với thứ tự của 32 điểm ghi giá, theo thứ tự từ giá thấp đến cao. Vì
vậy, điểm ghi giá (dạng nhị phân) có giá trị lớn thì “giá thật” cũng lớn.



+ Với t = k+2, Mi, k+2 = ENC( ri , yC) (Định danh của Vector giá: Mi id)
Chú ý:
Kí hiệu

là toán hạng đại diện phép XOR.

Hàm một chiều f thỏa mãn f k (r) = f(f k-1(r))
(Để đảm bảo “mở” được các giá trị khi mở đấu giá).
Mi,t là cột thứ t của Vector giá Mi

(1

t

).

Vector giá Mi bao gồm những giá trị mã hóa của các bit 0 hoặc 1 bằng
hàm f theo công thức trên. ID của người Bi và ID của Mi được gắn vào cột thứ
(k+1) và cột thứ (k+2).
Mi, 1 là bản mã của bit1,

Mi, 2 là bản mã của bít2, ...

ID của vector Mi ở cột thứ (k+2) được sử dụng với mục đích so khớp
vector đấu giá Mi với khóa mở, và không tiết lộ việc khớp Mi với Bi.
Sự ẩn dấu của Mi chỉ bị lộ khi mở được ID của Bi. ID chỉ có thể được mở
nếu Bi là người chiến thắng. Vì vậy chỉ có người thắng mới biết được giá cao
nhất. Mi được mở từ giá trị đầu tiên tới từng IDi. Bằng cách kiểm tra IDi của
người thắng cuộc, thì mới biết ai là người thắng.


Bước 1: Bi tạo ra các số phát sinh ngẫu nhiên Ri,k-t, Ri,1, ri và ri
Bước 2: Bi tính các giá trị ƒ(ri),.., ƒk(ri) bằng cách sử dụng hàm một chiều ƒ()
và số phát sinh ngẫu nhiên ri.
~

~

Bước 3: Bi mã hóa ri với khóa công khai yC của AM bằng hàm Enc( ri ,yC).
Bước 4: Bi tạo vector đấu giá Mi tương ứng với vbi .
Bước 5: Bi giữ bí mật “bộ khóa mở” là {ƒk(ri), ƒk-t(ri), ƒ(ri)}.
~

Bước 6: Bi gửi Mi và Enc( ri ,yC) đến AM.

17


~

~

Bước 7: AM nhận được Enc( ri ,yC), sẽ giải mã ra ri bằng cách sử dụng khóa
~

bí mật của họ là xC. AM giữ bí mật ri với mục đích để đối chiếu với Mi.

18




27000 $

vb2

1

0

1

0

1

22000 $

vb3

1

1

1

0

1

30000 $


4

5

Bi id

Mi id

f5(r1) ⊕
f4(r1)
f5(r2) ⊕
f4(r2)
f5(r3) ⊕
f4(r3)
f5(r4) ⊕
f4(r4)

f4(r1) ⊕
f3(r1)

f3(r1) ⊕ R1,2

f2(r1) ⊕
f(r1)

f1(r1) ⊕
R1,0

r1 ⊕ x1

f3(r3) ⊕
f2(r3)
f3(r4) ⊕ R4,2

f1(r4) ⊕ r4

~

~

~

~

Hình 2.3: Mô tả vector giá của một phiên đấu giá

19


2.2.7. Mở đấu giá của người thắng
Đầu tiên AM đưa tất cả các Mi và khóa công khai yi lên internet, tuy
nhiên không ai có thể biết được Mj nào của yj nào cả.
Class
Mi

1

2

3


f3(r2) ⊕ f2(r2)

f2(r2) ⊕ R2,1

f(r2) ⊕ r2

r2 ⊕ x2

Enc( r2 ,yC)

M3

1

1

1

0

f(r3) ⊕ r3

r3 ⊕ x3

Enc( r3 ,yC)

M4

1

Bi chuyển tới AM lần lượt các khóa mở f k(ri), f k-t(ri), f 1(ri).
~

Bước 1: Bi gửi khóa đầu tiên của nó là ƒk(ri) cùng với Enc( ri ,yC) đến AM.
~

~

~

AM giải mã Enc( ri ,yC) để lấy ra ri và đối chiếu ri trong giai đoạn đấu giá nó
nhận được, để xác định ƒk(ri) dùng để mở Mi nào.
AM mở Mi từng giá trị đến khi gặp bit “0” thì tạm dừng, theo công thức sau:
Mi, t = f k-t+1(ri) ⊕ f k-t(ri)

Ta có:

Mi, t ⊕ f k-t+1(ri) = f k-t+1(ri) ⊕ f k-t(ri) ⊕ f k-t+1(ri) = f k-t(ri)
f(Mi, t ⊕ f k-t+1(ri)) = f(f k-t(ri)) = f k-t+1(ri)
(hàm f thỏa mãn tính chất fk(r) = f(fk-1(r) (xem mục 3.2.4))
Vì vậy:

Nếu f(Mi, t ⊕ f t(ri)) = f t(ri) thì bitt = 1.

Nếu f(Mi, t ⊕ f t(ri)) ≠ f t(ri) thì bitt = 0.
~

Bước 2: Bi gửi khóa kế tiếp của mình là ƒk-t(ri) cùng với Enc( ri ,yC) cho AM.
Giống như bước 1, AM sẽ mở tiếp được các giá trị tiếp theo sau bitt = 0.
b). Xác định người thắng cuộc

M1

1

1

0

1

0

r1 ⊕ x1

Enc( r1 ,yC)

M2

1

0

1

0

1

r2 ⊕ x2


~

~

~

~

Enc( r4 ,yC)

Hình 2.5: Vector giá không hợp lệ trường hợp 1
Trường hợp 2: Một người biết được khóa bí mật của Bi, nhưng không biết
được bộ khóa mở của Bi, nên không thể “mở” được các giá trị trong vector giá
của Bi (trong hình dưới là M4). Trường hợp này Mi cũng được coi là không
hợp lệ.
Class
Mi

1

2

3

4

5

Bi id


r2 ⊕ x2

Enc( r2 ,yC)

M3

1

1

1

0

1

r3 ⊕ x3

Enc( r3 ,yC)

M4

#

#

#

#