42 / 62
42
นิตยสาร สสวท.
ตัวอย่าง : ระบบแบ่งปันความลับแบบ 3–ใน–5
ในที่นี้ เราแบ่งข้อมูลที่เกี่ยวกับความลับให้แก่คน 5 คน และ
เมื่อนำ
�ส่วนความลับของ 3 คนใด ๆ ในจำ
�นวน 5 คนนี้มาประกอบ
กันแล้ว ทำ
�ให้คำ
�นวณหาความลับ K ได้
1. เลือก a
0
= 3 เป็นความลับ K
2. เลือก y = 3 – 2x + x
2
เป็นสมการของพาราโบลาที่ตัด
แกน y ที่จุด (0, 3)
3. เลือกจุด (1, 2), (–2, 11), (3, 6), (–4, 27) และ (7, 38)
เป็นจุด 5 จุด บนพาราโบลา
y = 3 – 2x + x
2
มอบแต่ละจุดให้เจ้าหน้าที่ 5 คน เจ้าหน้าที่แต่ละคนต้องเก็บ
จุดที่ได้รับแบ่งปันไว้เป็นความลับ
4. ในการคำ
�นวณหาความลับ K เมื่อคนสามคนนำ
�จุด 3 จุด
ที่แต่ละคนได้รับแบ่งปัน สมมุติว่าเป็นจุด (1, 2), (–2, 11) และ
(3, 6) เนื่องจากจุดทั้งสามนี้อยู่บนพาราโบลา เราสามารถคำ
�นวณ
หาสมการของพาราโบลาที่ผ่านจุดทั้งสามนี้ โดยการแทนค่า x
และ y ที่เป็นพิกัดของแต่ละจุดในสมการ (2) ดังนี้
จากจุด (1, 2) : a
0
+ a
1
+ a
2
= 2 แทน x = 1, y = 2
จากจุด (–2, 11) : a
0
– 2a
1
+ 4a
2
= 11 แทน x = –2,
y = 11
จากจุด (3, 6) : a
0
+ 3a
1
+ 9a
2
= 6 แทน x = 3, y = 6
เราได้ระบบสมการเชิงเส้นที่มี 3 สมการ และมี 3 ตัวแปร
จากความรู้เรื่องการหาผลเฉลยของระบบสมการ เราได้
a
0
= 3, a
1
= – 2 และ a
2
= 1
ดังนั้น สมการของพาราโบลาที่ผ่านจุด (1, 2), (–2, 11) และ
(3, 6) คือ y = 3 – 2x + x
2
นั่นคือ K = 3
ระบบแบ่งปันความลับแบบ t–ใน–n
ในการสร้างระบบ t–ใน–n เราเลือกจุด a
0
บนแกน y ให้
เป็นความลับ K และเลือกจุด n จุดที่อยู่บนเส้นโค้ง
y = a
0
+ a
1
x + a
2
x
2
+ … + a
t -1
x
t –1
..........(3)
มอบจุดเหล่านี้ให้แก่ผู้ที่เกี่ยวข้องเก็บไว้เป็นความลับ จะ
เห็นว่าดีกรีของพหุนาม (3) คือ t – 1 ซึ่งน้อยกว่าจำ
�นวนจุดที่
เลือกอยู่ 1 แทนจุด t จุดเหล่านี้ใน (3) จะได้สมการ t สมการที่
มีตัวไม่รู้ค่า t ตัว คือ a
0
, a
1
, …, a
t – 1
สมมุติว่าจุด t จุดนั้นคือ
(x
1
, y
1
), (x
2
, y
2
), …, และ (x
t
, y
t
) เนื่องจากจุดเหล่านี้อยู่บนเส้น
โค้ง (3) แทนค่า x และ y ใน (3) ดังนี้
จากจุด (x
1
, y
1
) :
y
1
= a
0
+ a
1
x
1
+ a
2
(x
1
)
2
+ …+
a
t – 1
(x
1
)
t – 1
จากจุด (x
2
, y
2
) :
y
2
= a
0
+ a
1
x
2
+ a
2
(x
2
)
2
+ … +
a
t – 1
(x
2
)
t – 1
จากจุด (x
t
, y
t
) :
y
t
= a
0
+ a
1
x
t
+ a
2
(x
t
)
2
+ … +
a
t
– 1
(x
t
)
t – 1
เราได้ระบบสมการที่ประกอบด้วย t สมการและมีตัวแปร t
ตัว ซึ่งสามารถเขียนในรูปเมทริกซ์ได้ดังนี้
เมทริกซ์ที่อยู่ซ้ายสุดเป็นเมทริกซ์ที่รู้จักกันในชื่อ
Vandermonde Matrix เป็นเมทริกซ์ซึ่งรู้กันว่ามีดีเทอร์
มิแนนต์ไม่เป็นศูนย์ และจากความรู้ในเรื่องพีชคณิตเชิงเส้น
สรุปได้ว่าระบบสมการข้างบนนี้มีผลเฉลยเพียงชุดเดียว นั่น
คือ มีพหุนามเดียวที่ผ่านจุด (x
1
, y
1
), (x
2
, y
2
), …, (x
t
, y
t
)
บรรณานุกรม
Trappe, Wade, & Washington, Lawrence C. (2006).
Introduction to Crypto-
graphy : with Coding Theory
. (2
nd
edition). New Jersey, Prentice-Hall.
...
...
...
...
...
=
...
...
...
1
x
1
x
1
...
x
1
a
0
y
1
1
x
2
x
2
...
x
2
a
1
y
2
1
x
t
x
t
...
x
t
a
t-1
y
t
2
2
2
t-1
t-1
t-1