ล้นใน Shamir Secret Sharing Scheme แบบคลาสสิก

ฉันใช้ Shamir Secret Sharing Scheme แบบคลาสสิกซึ่งมีลักษณะดังนี้:

• รับรหัสผ่านเป็นอินพุต (ความยาวเท่าใดก็ได้)
• แปลงข้อความรหัสผ่านเป็นจำนวนเต็มขนาดใหญ่
• สร้าง coefs พหุนาม (an ... a1)
• สร้างการแยก - คู่ (xi, yi) ด้วยเกณฑ์ที่กำหนด

มันใช้งานได้ดีและนี่คือวิธีสร้างส่วนแบ่งงานลับให้มากขึ้น:

• รับส่วนแบ่งและเกณฑ์เป็นอินพุต
• การหา coeffs ด้วยเกาส์ (ดังนั้นฉันจึงรู้พหุนามดั้งเดิม)
• การค้นหาค่าลับ <-- นี่คือปัญหา
• สร้างการแบ่งปันมากขึ้น - ใช้การประทับเวลาเป็น xi

ทุกอย่างทำงานได้ดี แต่เมื่อฉันใช้รหัสผ่านที่ยาว (10 ตัวอักษรขึ้นไป) เมื่อสร้างค่าลับใหม่ มันล้มเหลวอาจเป็นเพราะมันสูญเสียความแม่นยำสำหรับตัวเลขที่สูง

แล้วจะเอาชนะวิธีการแบบคลาสสิกนี้ได้อย่างไร? อะไรควรเปลี่ยนแปลงในรูปแบบที่ไม่ควรละเอียดอ่อนต่อข้อความลับที่มีความยาว

อะไรควรเปลี่ยนแปลงในรูปแบบที่ไม่ควรละเอียดอ่อนต่อข้อความลับที่มีความยาว

Vadym ได้กล่าวแล้วว่า Shamir Secret Sharing ควรทำใน Finite Field; แต่มันไม่ได้ตอบคำถามของคุณ

ด้วย Shamir's Scheme อินสแตนซ์เดียวสามารถแบ่งปันค่าระหว่าง $0$ และ $p^k - 1$ (ที่ไหน $p^k$ คือขนาดของเขตข้อมูลจำกัดที่คุณใช้ [1]) และด้วย Shamir นั้นไม่มีความแตกต่างด้านความปลอดภัยระหว่างฟิลด์จำกัดต่างๆ ดังนั้นเราสามารถเลือกหนึ่งตามข้อกังวลที่ใช้งานได้จริง (เช่น จำนวนความลับที่คุณต้องการให้ออกได้ ขนาดของความลับ ความสะดวกในการใช้งาน การดำเนินการภาคสนามที่หลากหลาย)

อย่างไรก็ตาม สิ่งที่คุณต้องการทำคือแบ่งปันรหัสผ่านเป็นความลับ รหัสผ่านนั้นค่อนข้างยาวและมีความยาวผันแปรได้ มีสองทางเลือกที่ชัดเจน:

• เลือก ก $p^k$ (หรือนายก $p$ ถ้าคุณไปด้วย $k-1$) ที่ใหญ่พอที่จะเก็บรหัสผ่านใดๆ ที่คุณต้องการแชร์ ตัวอย่างเช่น ถ้าคุณใช้ $p=2^{521}-1$ (ซึ่งเป็นรหัสเฉพาะ) คุณสามารถแบ่งปันรหัสผ่านที่มีความยาวสูงสุด 65 อักขระ ใช้งานได้ แต่ข้อเสียคือค่าขนาดใหญ่นี้จะต้องได้รับการจัดการด้วยไลบรารีขนาดใหญ่ หากคุณใช้ภาษาที่มีไลบรารี bignum ในตัว (เช่น Python) นี่ไม่ใช่ปัญหา หากไม่ใช่ แนวคิดที่สองน่าจะง่ายกว่า

ด้วยแนวคิดนี้ ถ้าเรามีรหัสผ่าน 'letmein' (0x6c 0x65 0x74 0x6d 0x65 0x69 0x6e ใน ASCII) เราอาจเข้ารหัสเป็นจำนวนเต็ม 0x6c65746d65696e = 30510848210725230

• แบ่งรหัสผ่านออกเป็นหลายๆ ความลับ และแบ่งปันแต่ละความลับแยกกัน ตัวอย่างเช่น สำหรับรหัสผ่าน 14 อักขระ เราสามารถแบ่งรหัสนั้นออกเป็น 14 รหัสลับแยกกัน (โดยแต่ละรหัสลับจะเป็นหนึ่งอักขระจากรหัสผ่าน) และแบ่งปันอักขระแต่ละตัวโดยใช้ $p=257$ และ $k=1$ (แต่ละฝ่ายจะได้ทั้งหมด 14 หุ้น หนึ่งหุ้นต่อตัวละครทั้ง 14 ตัว) ด้วยแนวคิดนี้ จึงปลอดภัยที่จะใช้ตัวระบุเดียวกันสำหรับหุ้นทั้งหมดที่ฝ่ายหนึ่งได้รับ อย่างไรก็ตาม สิ่งสำคัญคือแต่ละความลับจะต้องสร้างขึ้นโดยใช้การสุ่มอย่างอิสระ (นั่นคือ แต่ละโพลิโนเมียลแบบสุ่มจาก 14 ชื่อจะถูกสร้างขึ้นแยกกัน)

ด้วยแนวคิดนี้ เราจะเข้ารหัสรหัสผ่าน 'letmein' เป็น 8 ความลับอิสระ 0x6c 0x65 0x74 0x6d 0x65 0x69 0x6e

ด้วยแนวคิดที่สองนี้ หากคุณไม่ต้องการปล่อยให้ความยาวของความลับรั่วไหล สิ่งที่คุณทำได้คือแบ่งปันความลับในจำนวนคงที่เสมอ (ซึ่งจะเป็นความยาวสูงสุดของรหัสผ่านที่คุณสามารถแบ่งปันได้ เช่น 32) และ สำหรับรหัสผ่านที่สั้นกว่านั้น ให้กรอกอักขระลับเพิ่มเติมด้วยค่าที่ไม่สามารถเกิดขึ้นในรหัสผ่านจริง (สำหรับตัวอย่างของฉันคือ $p=257$ค่าที่ชัดเจนในการใช้จะเป็น $256$).

[1]: สำหรับจำนวนเฉพาะใดๆ $p$ และจำนวนเต็มใดๆ $k$มีขนาดฟิลด์จำกัด $p^k$. มันอาจจะง่ายกว่าสำหรับคุณที่จะเริ่มต้นด้วยการใช้ฟิลด์ด้วย $k=1$ และ $p$ ไพรม์ที่มีขนาดเหมาะสม - สิ่งนี้ทำให้การบวก การลบ และการคูณใกล้เคียงกับอัลกอริทึมมาตรฐานที่คุณคุ้นเคยมากขึ้น (การหารยังคงไม่แน่นอน)

จากคำอธิบายที่ให้มา อาจมีคนแนะนำว่าเลขทศนิยมและการใช้ทศนิยมจะเป็นวิธีแก้ปัญหาที่ตรงไปตรงมา ไม่มีปัญหาโอเวอร์โฟลว์และความแม่นยำกับฟิลด์จำกัด

โปรดพิจารณาโมดูโลเลขคณิตบางจำนวนเฉพาะ กำหนดมาตรฐาน c++ ใหม่ บวก ลบ คูณ หาร เลือกหนังสือเรียนที่คุณสามารถอ่านได้ มันเป็นถนนยาว ขอให้โชคดี.