เหตุใดฟิลด์ส่วนขยายไบนารีจึงเป็นที่ต้องการสำหรับการแบ่งปันความลับของ Shamir

เพียงเพื่อเพิ่มรายละเอียดเพิ่มเติม คำตอบที่ยอดเยี่ยมของ kodlu:

เพื่อแบ่งปันข้อมูลลับบางอย่างโดยใช้ การแบ่งปันความลับของ Shamir เหนือสนามที่ จำกัด $\mathrm{GF}(k)$ก่อนอื่นคุณต้องเข้ารหัสข้อมูลนั้นเป็น $m ⥠1$ องค์ประกอบของเขตข้อมูล (ซึ่งแสดงโดยธรรมชาติเป็นจำนวนเต็มตั้งแต่ $0$ ถึง $k-1$) และยังกำหนดแต่ละการแบ่งปันที่คุณต้องการสร้างองค์ประกอบที่ไม่ใช่ศูนย์ที่แตกต่างกันของฟิลด์เป็นรหัสการแบ่งปัน (เช่น $x$ ประสานงานที่พหุนามสร้างหุ้นได้รับการประเมินเพื่อสร้างส่วนแบ่งนั้น)

จากนั้นคุณใช้กระบวนการสร้างหุ้น ซึ่งจะให้หุ้นหลายตัวแก่คุณ แต่ละตัวประกอบด้วย $m$ องค์ประกอบของสนาม $\mathrm{GF}(k)$ (บวกรหัสหุ้น) โดยการก่อสร้าง หุ้นเหล่านี้มีการกระจายอย่างสม่ำเสมอและ $t-1$ ฉลาดอิสระที่ไหน $t$ เป็นพารามิเตอร์เกณฑ์การสร้างใหม่ของโครงร่าง หมายความว่าชุดย่อยใดๆ ของ $s < t$ ของหุ้นนั้นแยกไม่ออกจาก $s$ ลำดับของ $m$ องค์ประกอบฟิลด์ที่เลือกอย่างอิสระโดยสุ่ม โดยเฉพาะอย่างยิ่ง ในฐานะที่เป็นข้อพิสูจน์ที่อ่อนแอของสิ่งนี้ องค์ประกอบฟิลด์ทั้งหมดที่ประกอบด้วยส่วนแบ่งจำเป็นต้องกระจายอย่างเท่าเทียมกันระหว่างกัน $0$ และ $k-1$รวม

ตอนนี้ สมมติว่าข้อมูลลับที่คุณต้องการแชร์เป็นแบบไบนารี และเข้ารหัสเป็นสตริง $n$ บิต หากคุณบังเอิญใช้ฟิลด์ไบนารี่ $k = 2^b$ (และถ้า $n$ เป็นทวีคูณของ $ข$) จากนั้นการแมปความลับลงในลำดับขององค์ประกอบฟิลด์นั้นง่ายมาก เพียงแค่ตัด $n$- บิตสตริงเข้า $m = \fracnb$ ชิ้นของ $ข$ บิต ซึ่งแต่ละบิตจับคู่กับองค์ประกอบฟิลด์โดยธรรมชาติ และเนื่องจากทุกองค์ประกอบของ $\mathrm{GF}(2^b)$ ยังแมปอย่างชัดเจนกับสตริงของ $ข$ บิต หุ้นของคุณสามารถแสดงเป็น $n$-bit bitstrings (บวก ID ที่ใช้ร่วมกัน) เพียงแค่เชื่อมต่อ (ตัวแทนไบนารีของ) องค์ประกอบฟิลด์ในแต่ละการแบ่งปัน

(ถ้าข้อมูลยาว $n$ เป็นตัวแปรและไม่จำเป็นต้องเป็นจำนวนเต็มคูณด้วย $ข$คุณอาจต้องใช้บางอย่าง การขยายความ เพื่อระบุความยาวอย่างชัดเจนก่อนที่จะแชร์ แต่นั่นยังเป็นปัญหาเล็กน้อยเท่านั้น และถ้าข้อมูลของคุณถูกเข้ารหัสเป็นไบต์แปดบิต และคุณไม่ต้องการการแบ่งปันมากกว่า 255 ครั้ง คุณก็สามารถใช้ $\mathrm{GF}(2^8)$ และข้ามช่องว่างภายใน)

เกิดอะไรขึ้นถ้าคุณ อย่า ต้องการใช้ฟิลด์ไบนารีหรือไม่ จากนั้นคุณมีสองตัวเลือก:

1. เลือกที่ใหญ่ที่สุด $ข$ ดังนั้น $2^b < k$, แยกข้อมูลออกเป็น $ข$- ชิ้นส่วนบิต แมปสิ่งเหล่านั้นลงในองค์ประกอบฟิลด์และแบ่งปัน ข้อเสียหลักของสิ่งนี้คือองค์ประกอบฟิลด์แบบสุ่มในการแบ่งปันจะ ไม่ พอดี $ข$ บิต (ตั้งแต่ $2^b < k$) ดังนั้นคุณจะต้องเข้ารหัสโดยใช้ $ข+1$ ทีละบิต เสียอย่างน้อย $m$ บิตต่อหุ้น (การเข้ารหัสความยาวผันแปรหลังการแชร์จะไม่ช่วยในส่วนนี้ เนื่องจากคุณไม่สามารถบีบอัดข้อมูลแบบสุ่มอย่างสม่ำเสมอได้ การเข้ารหัสความยาวแปรผัน ก่อน การแบ่งปันนั้นไม่ปลอดภัย เนื่องจากระยะเวลาการแบ่งปันของคุณอาจทำให้ข้อมูลเกี่ยวกับความลับรั่วไหลได้)

   คุณไม่สามารถจัดทั้งสองอย่างได้ $ข$ และ $ข+1$ ให้เป็นค่า "กลม" ที่สะดวก เช่น 8, 16, 32, 64, 128 หรือ 256 ซึ่งหมายความว่าชิ้นส่วนข้อมูลหรือชิ้นส่วนที่ใช้ร่วมกันจะมีความยาวที่น่าอึดอัดใจอย่างเลี่ยงไม่ได้ ตัวอย่างเช่น สมมติว่าคุณต้องการแบ่งปันคีย์เข้ารหัส 256 บิต; คุณสามารถเลือกได้ $b = 256$ซึ่งในกรณีนี้การแชร์ของคุณจะมีความยาว 257 บิต (และหากคุณต้องการใช้ฟิลด์ไพรม์ คุณต้องทำการคำนวณโมดูโลเป็นไพรม์ 257 บิต) หรือ $b = 255$ซึ่งในกรณีนี้ คุณจะต้องแยกคีย์ของคุณออกจากสององค์ประกอบฟิลด์ ส่งผลให้มีการใช้ร่วมกัน 512 บิต หรือคุณสามารถใช้พูดว่า $b = 32$ (และพูดว่าฟิลด์สำคัญ $\mathrm{GF}(2^{32}+15)$ซึ่งค่อนข้างยุ่งยากเล็กน้อยในการทำงานโดยใช้เลขคณิต 64 บิต แต่ก็ใช่ว่าจะเป็นไปไม่ได้ โดยเฉพาะอย่างยิ่งถ้าคุณไม่ต้องการการดำเนินการตามเวลาคงที่) และจบลงด้วย $33 \คูณ 8 = 264$ หุ้นบิตหลังจากการสับบิตซึ่งอาจเป็นพื้นกลางที่เหมาะสม

2. ใช้การแปลงฐานทั่วไปจากฐานสองเป็นฐาน $k$ เพื่อเข้ารหัสข้อมูลของคุณอย่างเหมาะสมที่สุด (เช่น ตีความไฟล์ $n$บิตข้อมูลไบนารีเป็นตัวเลขจาก $0$ ถึง $2^n-1$แล้วแสดงตัวเลขนั้นเป็นฐาน $k$) และการแปลงฐานผกผันจากฐาน $k$ เพื่อแปลงหุ้นกลับเป็นไบนารี่ คุณจะยังคงเสียบิตบางส่วน ดังนั้นการแบ่งปันของคุณจะยาวกว่าข้อมูล แต่จะเป็นจำนวนคงที่เท่านั้น ข้อเสียคือการแปลง radix ทำได้ช้ากว่าและซับซ้อนกว่าการสับบิตธรรมดา นอกจากนี้ คุณจะต้องมีแผนการขยายบางอย่างอย่างแน่นอน หากความยาวความลับของคุณไม่ได้รับการแก้ไข (และอย่าลืมใช้เสมอ $m = \lceil n \log_k 2 \rceil$แม้ว่าค่าลับของคุณจะพอดีกับฐานที่น้อยกว่าก็ตาม $k$ หลักเพื่อหลีกเลี่ยงการแชร์ข้อมูลความลับรั่วไหล)

ตอนนี้ไม่มีภาวะแทรกซ้อนใดที่ผ่านไม่ได้ แต่พวกเขา ทำ ทำให้การใช้งานซับซ้อนและทำให้การเข้ารหัสที่ใช้ร่วมกันมีประสิทธิภาพน้อยลง ในการเปรียบเทียบ แม้ว่าคุณจะต้องดำเนินการ $\mathrm{GF}(2^b)$ เลขคณิตจากศูนย์ด้วยตัวคุณเอง การใช้เขตข้อมูลไบนารียังง่ายกว่า