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

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

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

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

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

วิธีการแบ่งปันความลับ

Adi Shamir คิดแผนการจัดการคีย์ประเภทนี้ในปี 1979 เมื่อเขาตีพิมพ์ผลงานของเขา “วิธีแบ่งปันความลับ”. บทความนี้อธิบายสั้น ๆ เกี่ยวกับสิ่งที่เรียกว่า รูปแบบเกณฑ์สำหรับการแบ่งค่าความลับ (เช่น คีย์การเข้ารหัส) ออกเป็นอย่างมีประสิทธิภาพ ชิ้นส่วน จากนั้นเมื่อใดและเมื่อใดอย่างน้อยที่สุด ของ ประกอบชิ้นส่วนแล้วคุณสามารถคืนความลับได้อย่างง่ายดาย .

จากมุมมองด้านความปลอดภัย คุณสมบัติที่สำคัญของโครงการนี้คือผู้โจมตีไม่ควรรู้สิ่งใดเลยเว้นแต่ว่าเขาจะมีข้อมูลอย่างน้อย ชิ้นส่วน แม้กระทั่งการปรากฏตัว ชิ้นส่วนไม่ควรให้ข้อมูลใดๆ เราเรียกทรัพย์สินนี้ว่า ความปลอดภัยทางความหมาย.

การประมาณค่าพหุนาม

โครงการเกณฑ์ Shamir สร้างขึ้นตามแนวคิด การประมาณค่าพหุนาม. หากคุณไม่คุ้นเคยกับแนวคิดนี้ จริงๆ แล้วมันก็ค่อนข้างง่าย ที่จริงแล้ว หากคุณเคยวาดจุดบนกราฟแล้วเชื่อมต่อมันด้วยเส้นหรือเส้นโค้ง แสดงว่าคุณใช้มันไปแล้ว!

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

พิจารณาพหุนามที่มีดีกรี XNUMX . หากคุณต้องการพล็อตฟังก์ชันนี้บนกราฟ คุณต้องการกี่จุด? เรารู้ว่านี่คือฟังก์ชันเชิงเส้นที่สร้างเส้นตรง และมันต้องมีจุดอย่างน้อย XNUMX จุด ต่อไป ให้พิจารณาฟังก์ชันพหุนามที่มีดีกรี XNUMX . นี่คือฟังก์ชันกำลังสอง ดังนั้นต้องมีจุดอย่างน้อย XNUMX จุดในการพล็อตกราฟ แล้วพหุนามที่มีดีกรี XNUMX ล่ะ? อย่างน้อยสี่คะแนน และอื่น ๆ และอื่น ๆ.

สิ่งเจ๋งจริงๆ เกี่ยวกับคุณสมบัตินี้คือ เมื่อพิจารณาจากดีกรีของฟังก์ชันพหุนาม และอย่างน้อย จุด เราสามารถหาจุดเพิ่มเติมสำหรับฟังก์ชันพหุนามนี้ได้ เราเรียกการคาดการณ์ประเด็นเพิ่มเติมเหล่านี้ การประมาณค่าพหุนาม.

กำลังสร้างความลับ

คุณอาจรู้แล้วว่านี่คือจุดที่แผนการอันชาญฉลาดของ Shamir เข้ามามีบทบาท เอาเป็นว่าความลับของเรา - เป็น . เราเลี้ยวได้ จนถึงจุดหนึ่งบนกราฟ และได้ฟังก์ชันพหุนามพร้อมดีกรีขึ้นมา ซึ่งตรงใจประเด็นนี้ ให้เรานึกถึงสิ่งนั้น จะเป็นค่าขีดจำกัดของแฟรกเมนต์ที่ต้องการ ดังนั้นหากเราตั้งค่าขีดจำกัดเป็นสามแฟรกเมนต์ เราจะต้องเลือกฟังก์ชันพหุนามที่มีดีกรี XNUMX

พหุนามของเราจะมีรูปแบบ ที่ไหน и — จำนวนเต็มบวกที่เลือกแบบสุ่ม เราแค่สร้างพหุนามด้วยดีกรี โดยที่ค่าสัมประสิทธิ์อิสระ  - นี่คือความลับของเรา และสำหรับแต่ละรายการที่ตามมา เทอม จะมีการสุ่มเลือกสัมประสิทธิ์บวก ถ้าเรากลับมาที่ตัวอย่างเดิมแล้วสมมุติว่า แล้วเราจะได้ฟังก์ชัน .

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

การกู้คืนความลับ

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

ที่ เราสามารถแก้มันได้แบบนี้และคืนค่าฟังก์ชันพหุนามดั้งเดิมของเรา:

เพราะเรารู้ว่า , การกู้คืน ทำได้ง่ายๆ:

การใช้เลขคณิตจำนวนเต็มที่ไม่ปลอดภัย

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

เพื่อแสดงให้เห็นว่าวงจรเลขคณิตจำนวนเต็มอ่อนแอเพียงใด ให้พิจารณาสถานการณ์ที่ผู้โจมตีได้รับสองคะแนน และทราบข้อมูลสาธารณะว่า . จากข้อมูลนี้เขาสามารถอนุมานได้ เท่ากับสองแล้วแทนค่าที่ทราบลงในสูตร и .

ผู้โจมตีสามารถค้นหาได้ , การนับ :

เนื่องจากเราได้กำหนดไว้แล้ว จากการสุ่มเลือกจำนวนเต็มบวก มีจำนวนจำกัดที่เป็นไปได้ . ผู้โจมตีสามารถอนุมานข้อมูลนี้ได้โดยใช้ข้อมูลนี้ เนื่องจากอะไรก็ตามที่มากกว่า 5 จะทำ เชิงลบ. สิ่งนี้กลายเป็นจริงตั้งแต่เราตัดสินใจแล้ว

ผู้โจมตีสามารถคำนวณค่าที่เป็นไปได้ แทนที่ в :

ด้วยตัวเลือกที่จำกัดสำหรับ จะเห็นได้ชัดว่าการเลือกและตรวจสอบค่านั้นง่ายเพียงใด . มีเพียงห้าตัวเลือกที่นี่

การแก้ปัญหาด้วยเลขคณิตจำนวนเต็มที่ไม่ปลอดภัย

เพื่อกำจัดช่องโหว่นี้ Shamir แนะนำให้ใช้เลขคณิตแบบโมดูลาร์แทนที่ บน ที่ไหน и - เซตของจำนวนเฉพาะทั้งหมด

มาจำกันอย่างรวดเร็วว่าเลขคณิตแบบแยกส่วนทำงานอย่างไร นาฬิกาที่มีเข็มเป็นแนวคิดที่คุ้นเคย เธอใช้นาฬิกานั่นคือ . ทันทีที่เข็มชั่วโมงผ่านไปเลขสิบสอง เข็มจะกลับไปเป็นเลขหนึ่ง คุณสมบัติที่น่าสนใจของระบบนี้คือเพียงแค่ดูที่นาฬิกา เราไม่สามารถอนุมานได้ว่าเข็มชั่วโมงได้หมุนไปแล้วกี่รอบ อย่างไรก็ตาม หากเรารู้ว่าเข็มชั่วโมงผ่านไป 12 สี่ครั้ง เราก็สามารถกำหนดจำนวนชั่วโมงที่ผ่านไปได้อย่างสมบูรณ์โดยใช้สูตรง่ายๆ ที่ไหน  คือตัวหารของเรา (ในที่นี้ ),  คือค่าสัมประสิทธิ์ (จำนวนครั้งที่ตัวหารหารจำนวนเดิมโดยไม่มีเศษเหลืออยู่ตรงนี้ ) และ  คือส่วนที่เหลือ ซึ่งมักจะส่งคืนการเรียกตัวดำเนินการแบบโมดูโล (ที่นี่ ). การรู้ค่าเหล่านี้ทั้งหมดทำให้เราสามารถแก้สมการได้ แต่ถ้าเราพลาดสัมประสิทธิ์ เราจะไม่สามารถคืนค่าเดิมได้

เราสามารถแสดงให้เห็นว่าสิ่งนี้ปรับปรุงความปลอดภัยของโครงการของเราได้อย่างไรโดยการนำโครงการไปใช้กับตัวอย่างก่อนหน้าและการใช้งาน . ฟังก์ชันพหุนามใหม่ของเรา และจุดใหม่ . ตอนนี้ผู้รักษาหลักสามารถใช้การประมาณค่าพหุนามเพื่อสร้างฟังก์ชันของเราขึ้นมาใหม่ได้อีกครั้ง แต่คราวนี้การดำเนินการบวกและการคูณจะต้องมาพร้อมกับการลดแบบโมดูโล (เช่น ).

จากตัวอย่างใหม่นี้ สมมติว่าผู้โจมตีได้เรียนรู้ประเด็นใหม่สองประเด็นนี้ และข้อมูลสาธารณะ . คราวนี้ผู้โจมตีจะส่งออกฟังก์ชันต่อไปนี้ตามข้อมูลทั้งหมดที่เขามี  คือเซตของจำนวนเต็มบวกทั้งหมด และ แสดงถึงค่าสัมประสิทธิ์โมดูลัส .

ตอนนี้ผู้โจมตีของเราพบอีกครั้ง , กำลังคำนวณ :

จากนั้นเขาก็ลองอีกครั้ง แทนที่ в :

คราวนี้เขามีปัญหาร้ายแรง สูตรไม่มีค่า , и . เนื่องจากตัวแปรเหล่านี้มีจำนวนไม่สิ้นสุด เขาจึงไม่สามารถรับข้อมูลเพิ่มเติมใดๆ ได้

ข้อควรพิจารณาด้านความปลอดภัย

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

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

ปัญหาอีกประการหนึ่งคือความยาวของส่วนใดๆ เท่ากับความยาวของส่วนลับที่เกี่ยวข้อง ดังนั้นความยาวของส่วนลับจึงง่ายต่อการระบุ ปัญหานี้สามารถแก้ไขได้ด้วยเรื่องเล็กน้อย การขยายความ ความลับที่มีตัวเลขที่กำหนดเองจนถึงความยาวคงที่

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

การสาธิต

На หน้านี้ มีการสาธิตแบบโต้ตอบเกี่ยวกับแผนการแบ่งปันความลับของ Shamir การสาธิตตามห้องสมุด ssss-jsซึ่งตัวเองเป็นพอร์ต JavaScript ของโปรแกรมยอดนิยม ssss. โปรดทราบว่าการคำนวณค่าจำนวนมาก , и อาจใช้เวลาสักครู่

ที่มา: will.com