Score:-1

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

ธง co

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

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

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

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

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

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

kelalaka avatar
in flag
https://math.stackexchange.com/q/4329986/338051 และกลายเป็นพารามิเตอร์และปัญหาการเข้ารหัสที่อาจเหมาะกับ [so] มากกว่า
Vadym Fedyukovych avatar
in flag
คุณใช้ฟิลด์จำกัดเพื่อแสดงรหัสผ่านของคุณหรือไม่
Macko avatar
co flag
@VadymFedyukovych ยังไม่มี โปรดให้ตัวเลือกวิธีการทำใช่ไหม วิธีเข้ารหัสรหัสผ่านในฟิลด์จำกัดตัวอย่าง
Score:1
ธง my

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

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$ ไพรม์ที่มีขนาดเหมาะสม - สิ่งนี้ทำให้การบวก การลบ และการคูณใกล้เคียงกับอัลกอริทึมมาตรฐานที่คุณคุ้นเคยมากขึ้น (การหารยังคงไม่แน่นอน)

Macko avatar
co flag
อืม แนวคิดที่สองดูแปลกสำหรับฉันเพราะแต่ละฝ่ายที่ได้รับส่วนแบ่งไม่ควรมีส่วนแบ่งมากพอที่จะสร้างรหัสผ่านที่ได้รับการป้องกัน (ความลับ) ใหม่ ประการที่สองฉันไม่เข้าใจว่าการแชร์รหัสผ่านชุดเดียวสามารถสร้างใหม่เป็นรหัสผ่านแบบยาวได้อย่างไร วิธีการนี้ดูยืดหยุ่นกว่า
Macko avatar
co flag
ดูเหมือนว่าแนวทางแรกจะเป็นตัวเลือกที่ดี แต่ต้องมีการลองผิดลองถูกเพื่อค้นหาจุดที่น่าสนใจของโครงสร้างที่ใช้ภายใน - เพื่อค้นหาว่ารหัสผ่านที่ยาวหรือซับซ้อนสามารถประมวลผลได้ด้วยอัลกอริทึมที่เขียน
poncho avatar
my flag
@Macko: หากคุณไม่เข้าใจแนวคิดที่สอง แสดงว่าคุณกำลังคิดมากเกินไป ด้วยวิธีนี้ คุณจะสร้างรูปแบบการแบ่งปันความลับสำหรับจดหมายฉบับแรก และแจกจ่ายการแบ่งปันเหล่านั้น ในแบบคู่ขนานกัน คุณสร้าง ss สำหรับตัวอักษรตัวที่สอง และแบ่งส่วนนั้นให้กับฝ่ายเดียวกัน และส่วนเดียวกันสำหรับกลุ่มที่สาม สี่ ฯลฯ เมื่อถึงเวลารวมเข้าด้วยกันใหม่ ให้นำหุ้นทั้งหมดที่มี และรวมเข้าด้วยกัน หุ้นตัวแรกของพวกเขาร่วมกัน (เพื่อ gen อักษรตัวแรก); เหมือนกันกับตัวที่สอง เป็นต้น เมื่อคุณมีตัวอักษรทั้งหมดแล้ว ให้เชื่อมมันเข้าด้วยกัน เท่านี้ก็เสร็จแล้ว
Macko avatar
co flag
ฉันคิดว่าตัวเลือกที่สองนั้นออกแบบมากเกินไปและฝ่ายต่างๆ จะลงเอยด้วยการแบ่งปันมากเกินไปซึ่งยากต่อการจัดการ ฉันจะยึดติดกับตัวเลือกคลาสสิก 1 ในตอนนี้...
Score:0
ธง in

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

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

Macko avatar
co flag
แน่นอนคุณพูดถูก แต่ฉันต้องการรายละเอียดเพิ่มเติมหรือการยืนยันวิธีการทำให้ถูกต้อง: ก่อนอื่นให้เข้ารหัสรหัสผ่านเป็นตัวเลขจำนวนมาก (ใน Java มันจะเป็น BigInteger) กว่าแปลงค่านี้เป็นตัวเลขในฟิลด์ที่ จำกัด ? จากนี้ไปการคำนวณทั้งหมดเช่น (การสร้าง coefs, interpolating) ควรทำเฉพาะในฟิลด์ที่กำหนด ?

โพสต์คำตอบ

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