การแบ่งปันความลับของ Shamir: คณิตศาสตร์พหุนาม

การแบ่งปันคีย์ลับของ Shamir (1979) เข้ารหัสคีย์ลับเป็นจุดตัดแกน y (f(0)) ของพหุนามสุ่มดีกรี (k-1) บนฟิลด์จำกัด จุด k จุดใด ๆ จะกำหนดพหุนามได้เพียงหนึ่งเดียว (การอินเตอร์โพเลชันของ Lagrange) ส่วนจำนวนน้อยกว่า k จุดจะไม่เปิดเผยข้อมูลใด ๆ

หากต้องการแบ่งปันคีย์ลับ S ด้วยเกณฑ์ k ให้แก่ฝ่ายจำนวน n ฝ่าย ให้เลือกจำนวนเฉพาะ p ที่มากกว่า S และ n สุ่มสัมประสิทธิ์ a_1, ..., a_{k-1} กำหนด f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p) ฝ่ายที่ i จะได้รับส่วนแบ่ง (i, f(i))

คีย์ลับ S=7, p=17, k=2 (พหุนามเชิงเส้น) เลือก a_1=3 กำหนด f(x)=7+3x mod 17 ส่วนแบ่ง: (1,10), (2,13), (3,16) จุดสองจุดใด ๆ จะกำหนดเส้นตรงได้ f(0)=7 จุดเดียวมีเส้นตรงที่เป็นไปได้ไม่จำกัด จึงไม่เปิดเผยข้อมูลเกี่ยวกับ S เลย

เมื่อกำหนดจุด k จุด (x_1,y_1),...,(x_k,y_k) ให้กู้คืน f(0) ด้วยวิธี Lagrange: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p การคำนวณทั้งหมดเป็นแบบมอดูลาร์ ไม่มีเลขทศนิยมลอยตัว — กู้คืนได้อย่างแม่นยำบนฟิลด์จำกัด

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

สำหรับส่วนแบ่ง k-1 ส่วน จะมีพหุนามดีกรี k-1 เพียงหนึ่งเดียวที่ลากผ่านจุดทั้ง k-1 จุดนั้น สำหรับค่าความลับ S ที่เป็นไปได้ทุกค่า ดังนั้นเมื่อทราบส่วนแบ่ง k-1 ส่วน ค่าทุกค่าใน S ในช่วง [0, p-1] จึงมีโอกาสเท่ากัน — ไม่มีการเปิดเผยข้อมูลใด ๆ

p ต้องมีค่ามากกว่าความลับและ n ตัวเลือกที่ใช้กันทั่วไปคือ p = 2^127-1 (จำนวนเฉพาะเมอร์แซน) สำหรับความลับขนาด 128 บิต วิธีนี้ทำให้ส่วนแบ่งทั้งหมดมีขนาดไม่เกิน 128 บิตและคำนวณได้อย่างมีประสิทธิภาพ อีกทางเลือกหนึ่งคือใช้ p=2^521-1 สำหรับความลับขนาด 512 บิต

SSS พื้นฐานไม่มีการรับประกันความสมบูรณ์ของส่วนแบ่ง ผู้ถือส่วนแบ่งที่ประสงค์ร้ายสามารถส่งส่วนแบ่งปลอม ทำให้การกู้คืนความลับผิดพลาดได้ Feldman VSS (การแบ่งปันความลับที่ตรวจสอบได้) เผยแพร่ค่าให้คำมั่น g^{a_i} mod p ทำให้ตรวจสอบส่วนแบ่งได้โดยไม่เปิดเผยพหุนาม

สามารถปรับปรุงส่วนแบ่งเป็นระยะ ๆ ได้ โดยสร้างพหุนามใหม่ที่มีความลับ S เดิม แล้วแจกจ่ายส่วนแบ่งใหม่ ส่วนแบ่งเก่าจะใช้การไม่ได้ ผู้โจมตีที่เจาะระบบผู้ถือส่วนแบ่งได้หลังการปรับปรุงจะได้เพียงส่วนแบ่งเก่าที่ไร้ประโยชน์ วิธีนี้ใช้ในระบบจัดการกุญแจที่มีอายุการใช้งานยาวนาน

ssss (บรรทัดคำสั่งของ Linux), python-secret-sharing, hashicorp/vault ใช้ SSS สำหรับกลไกการผนึกข้อมูล และกระเป๋าเงินฮาร์ดแวร์ Trezor ใช้ SSS เพื่อสำรองข้อมูลค่าเริ่มต้นของกระเป๋าเงิน (SLIP-39) ทั้งหมดทำงานบนฟิลด์จำนวนเฉพาะขนาดใหญ่

SSS ต้องมีผู้แจกจ่ายที่เชื่อถือได้เพื่อสร้างและแจกจ่ายส่วนแบ่ง โดยผู้แจกจ่ายจะทราบความลับด้วย กรณีที่ไม่มีผู้แจกจ่ายต้องใช้ DKG (การสร้างกุญแจแบบกระจาย) การกู้คืนจะเปิดเผยความลับแก่ผู้ใดก็ตามที่ถือส่วนแบ่ง k ส่วน ซึ่งสามารถหลีกเลี่ยงได้ด้วย MPC หรือลายเซ็นตามเกณฑ์

ในการแบ่งปันความลับของ Shamir แบบ (3,5) ต้องใช้ส่วนแบ่งอย่างน้อยกี่ส่วนเพื่อกู้คืนความลับ

SSS ของ Shamir เข้ารหัสความลับเป็นจุดตัดแกน y ของพหุนาม การอินเตอร์โพเลชันของ Lagrange กู้คืนความลับได้จากส่วนแบ่ง k ส่วน มีความปลอดภัยเชิงทฤษฎีสารสนเทศอย่างสมบูรณ์เมื่อมีส่วนแบ่งน้อยกว่า k ส่วน ต่อไป: การแบ่งปันความลับด้วยภาพและการแบ่งปันแบบบวก