ฉันเพิ่งเข้าสู่การเข้ารหัสและกำลังเรียนรู้โดยการพยายามใช้อัลกอริทึมการเข้ารหัสบางอย่าง
ขณะนี้กำลังใช้อัลกอริทึมการแบ่งปันความลับของ Shamir สิ่งที่ฉันสังเกตเห็นคือฟิลด์ที่ จำกัด ปรากฏขึ้นเรื่อย ๆ
ฉันแค่ไม่เข้าใจว่าทำไมพวกเขาถึงเกี่ยวข้องกัน
สิ่งหนึ่งที่ฉันเห็นคือพวกเขาสามารถทำให้แน่ใจว่าไม่มีผลลัพธ์ใดที่เป็นทศนิยม ดังนั้นจึงไม่มีข้อผิดพลาดในการปัดเศษ แต่ฉันสงสัยอย่างยิ่งว่านั่นเป็นเหตุผลที่ผลลัพธ์เหล่านี้มีความสำคัญมาก คงจะดีมากถ้ามีคนให้สัญชาตญาณแก่ฉันว่าทำไมพวกเขาถึงต้องการ
นอกจากนี้ ข้อเท็จจริงที่ว่าพวกเขาเป็นอันตรายอย่างจำกัดหรือไม่?
หัวข้อหนึ่งที่สำคัญอย่างยิ่งสำหรับคำถามนี้คือหัวข้อของ ขนาดการเข้ารหัส. สิ่งนี้มาจาก "ข้อเท็จจริงเล็กน้อย" ต่อไปนี้:
สำหรับเซตอนันต์ $A$, ไม่มีอยู่บาง $s\in \mathbb{N}$ เช่นนั้นทุกๆ $a\ใน A$ สามารถอธิบายได้ใน $s$ บิต
เราสามารถแก้ไขปัญหานี้ได้โดยหันไปใช้การเข้ารหัสที่มีความยาวผันแปรได้ แต่สิ่งนี้สามารถนำไปสู่ปัญหาด้านความปลอดภัยได้อย่างง่ายดาย การรับข้อมูลบางอย่างเกี่ยวกับขนาดขององค์ประกอบที่เข้ารหัสบางอย่างอาจทำได้ค่อนข้างง่าย หากสิ่งนี้บ่งชี้ว่าองค์ประกอบใดถูกเข้ารหัส สิ่งนี้จะไม่ดี ดังนั้นหากคุณต้องการให้อ็อบเจกต์ในระบบเข้ารหัสของคุณมีการเข้ารหัสที่มีขนาดเท่ากัน คุณก็ติดอยู่กับอ็อบเจกต์ที่มีขอบเขตจำกัด
ข้อดี (ที่เล็กกว่า) ของการทำงานในโครงสร้างจำกัดคือมีการแจกแจงแบบสม่ำเสมอ มันคือ:
คุณสมบัติเหล่านี้เพียงพอแล้วในการแสดงความปลอดภัยของแพดแบบใช้ครั้งเดียว ซึ่งค่อนข้างเป็นพื้นฐาน และมักมีผู้ต้องการอุทธรณ์ (บ่อยครั้งหลังจากแทนที่วัตถุ "ของจริง" ด้วยวัตถุในอุดมคติ เช่น แทนที่ PRG ด้วยฟังก์ชันสุ่ม)
สำหรับกลุ่มที่ไม่มีที่สิ้นสุดบางกลุ่มสามารถรับการแจกแจงที่มีคุณสมบัติคล้ายกันได้ โดยเฉพาะอย่างยิ่ง วัดฮาร์. แต่มันคือ มาก ซับซ้อนทางเทคนิคมากขึ้น ดังนั้นความจริงที่ว่าการกระจายแบบสม่ำเสมอนั้นง่ายมาก (ในขณะที่มีคุณสมบัติที่ยอดเยี่ยม) จึงเป็นประเด็นที่สนับสนุนพื้นที่จำกัดอย่างแน่นอน แม้ว่าจะมีความสำคัญน้อยกว่าจุดขนาดการเข้ารหัสคงที่ในสายตาของฉันก็ตาม
ไม่มีคำตอบใดว่าทำไมจึงสิ้นสุด เขตข้อมูลแทนที่จะเป็นโครงสร้างพีชคณิตที่มีขอบเขตจำกัด แต่บ่อยครั้งที่ฟิลด์จำกัดถูกใช้เป็นแหล่งของกลุ่มจำกัดเท่านั้น $\mathbb{F}_p^\times$. มีใครเถียงว่าทำไมเราถึงต้องการกลุ่มมากกว่าโครงสร้างพีชคณิตที่อ่อนแอกว่า แต่ฉันมีประเด็นที่คลุมเครือในหัวข้อนี้เท่านั้น
บางทีจุดสุดท้ายคือ "ทำไม ไม่ โครงสร้างจำกัด" --- อะไรทำนองนั้น $(\mathbb{Z}/pq\mathbb{Z})^\times$ สำหรับ $p, q$ ของ $\ประมาณ 1024$ บิตมีขนาดใหญ่มากจนน่าขันในขณะที่มันไม่เป็นเช่นนั้น ในทางเทคนิค ไม่มีที่สิ้นสุด มันเป็น "สาระสำคัญ" ดังนั้น --- เช่น มีคร่าวๆ $2^{270}$ อะตอมในจักรวาลซึ่งก็คือ มาก มีขนาดเล็กกว่า $2^{2048}$ดังนั้นในแง่หนึ่ง มันจึง "ใหญ่กว่าจักรวาลของเรา" (ในขณะที่ยังคงมีขอบเขตจำกัด) ในขณะที่บางอย่างเช่น $\mathbb{R}$ ไม่มีที่สิ้นสุด หากสิ่งหนึ่งทำให้เกิดข้อผิดพลาดในการปัดเศษ (ตามที่คุณพูดถึง) คุณน่าจะทำงานกับการประมาณค่าทศนิยม ซึ่งโดยทั่วไปจะใช้มากที่สุด $128$ บิต ดังนั้น จริง ๆ แล้ว (โดยปริยาย) ทำงานกับ a เล็กลง เซตจำกัดกว่าที่นักเข้ารหัสใช้
ฉันจะพยายามให้คำตอบทั่วไปกับสิ่งนี้
ฟิลด์ จำกัด แสดงโดย ${F_p}$โดยที่ p เป็นจำนวนเฉพาะ ทำงานได้ดีกับอัลกอริทึมการเข้ารหัส เช่น AES, RSA เป็นต้น เนื่องจากเหตุผลต่อไปนี้:
เราจำเป็นต้องถอดรหัสข้อความที่เข้ารหัส ซึ่งจะเป็นไปได้ก็ต่อเมื่อมีการกลับด้านของฟังก์ชัน (bijective) ที่ไม่ซ้ำใคร สิ่งนี้จะเป็นไปได้ก็ต่อเมื่อไม่มีตัวหารเป็นศูนย์ในฟังก์ชัน และยังเป็นอนุมานและอนุญัติด้วย
นอกจากนี้ยังให้การทำงานแบบปิด ซึ่งหมายความว่า การดำเนินการใด ๆ ที่คุณทำในฟิลด์ ผลลัพธ์จะยังคงอยู่ในฟิลด์ ทำให้ง่ายต่อการใช้อัลกอริทึมการเข้ารหัสที่หลากหลาย
ฟิลด์จำกัดที่สร้างโดยจำนวนเฉพาะ (จำนวนเฉพาะหรือพหุนามที่ลดทอนไม่ได้) มีลักษณะที่จำเป็นเหล่านี้
ไม่ได้ใช้เฉพาะในการเข้ารหัสเท่านั้น แต่ยังใช้ในการเข้ารหัสแชนเนล เช่น การเข้ารหัส BCH หรือ Reed-Solomon มันแพร่หลายในรหัสการแก้ไขข้อผิดพลาดในการสื่อสารส่วนใหญ่ ความปลอดภัยของข้อมูล/เนื้อหา นอกจากนี้ส่วนขยายเช่น Groups and Rings ยังใช้ในด้านเคมีและสาขาวิทยาศาสตร์อื่นๆ
ประเด็นที่ Mark และ SSA หยิบยกขึ้นมาคือสิ่งสำคัญ เรามีคลาสโครงสร้างที่ศึกษามาอย่างดีซึ่งมาพร้อมกับปัญหาที่เหมาะสมซึ่งปัจจุบันเชื่อว่าคำนวณได้ยาก (ทั้งๆที่มีการศึกษาอย่างดี) จริงๆ แล้ว การแมปเชิงเส้นตรงทั้งหมด $x\mapsto ขวาน+b$ เป็น bijections (ดูสิ่งที่ Mark พูดเกี่ยวกับเอนโทรปีสูงสุด) เมื่อใดก็ตามที่ $a$ เป็นองค์ประกอบที่ไม่ใช่ศูนย์ของเขตข้อมูล ถ้าเราไม่มีสนามโดยเฉพาะ สิ่งนี้จะไม่เกิดขึ้น
ฉันยังต้องการเพิ่มคุณสมบัติบางอย่างของเขตข้อมูลจำกัดของคุณลักษณะสองอย่างโดยเฉพาะ ($GF(2^n)$ หรือ $\Bbb{F}_{2^n}$):
อย่างไรก็ตาม ฟิลด์เหล่านี้ก็มีข้อเสียเช่นกัน
ทำไมต้องเป็นสนาม: แนวคิดเบื้องหลังการแบ่งปันความลับของ Shamir คือการสร้างความลับขึ้นมาใหม่ (การทำงาน) และพิสูจน์ว่าความลับใด ๆ ที่แบ่งปันนั้นเป็นไปได้ (ความปลอดภัย) โดยใช้การแก้ไขพหุนาม
ในขณะที่การแก้ไขพหุนามสามารถทำได้ในโครงสร้างเกี่ยวกับพีชคณิตจำนวนมาก แต่จะใช้ได้ผลกับฟิลด์เสมอ (ในฟิลด์ พหุนามที่ไม่ใช่ศูนย์จะมีเลขศูนย์มากเท่ากับดีกรีของมัน เหนือโครงสร้างพีชคณิตอื่นๆ ที่เกี่ยวข้อง มักไม่เป็นความจริง)
แม้ว่าการแบ่งปันความลับของ Shamir มักจะทำในฟิลด์ แต่ก็มีการทำในโครงสร้างพีชคณิตอื่น ๆ อีกมากมาย สิ่งนี้มักต้องการการดูแลที่ดีและซับซ้อน เว้นแต่คุณจะต้องทำจริง ๆ การทำผ่านฟิลด์นั้นง่ายกว่าและดีกว่ามาก
ทำไมถึงจำกัด: ความปลอดภัยที่ความลับที่แชร์จะเป็นไปได้นั้นไม่เพียงพอ ความลับที่แชร์ทุกรายการจะต้องมีโอกาส (เกือบ) เท่ากันด้วย การใช้เขตข้อมูลจำกัดทำให้เราสามารถเลือกการสุ่มจากการแจกแจงแบบสม่ำเสมอ ซึ่งกลายเป็นว่าให้สิ่งที่เราต้องการอย่างแท้จริง
เราสามารถทำงานในฟิลด์ที่ไม่มีที่สิ้นสุด เช่น จำนวนตรรกยะ แต่ในกรณีนี้ เป็นเรื่องยากมากที่จะให้ความลับที่ใช้ร่วมกันทั้งหมดมีโอกาสเกือบเท่าๆ กัน สิ่งนี้เกี่ยวข้องกับการไม่มีการกระจายแบบสม่ำเสมอในเซตที่ไม่มีที่สิ้นสุด วิธีมองอย่างคร่าว ๆ ก็คือ ขนาดของค่าจะสัมพันธ์กับขนาดของค่าสัมประสิทธิ์และตำแหน่งที่เราประเมิน ดังนั้น หากเราต้องการซ่อนค่าสัมประสิทธิ์ใดค่าหนึ่ง เราจะต้อง "กลบมันออกไป" โดยมี ค่าสัมประสิทธิ์อื่น ๆ จะใหญ่กว่ามาก
การทำผ่านจำนวนเต็ม (ไม่ใช่ฟิลด์!) สามารถทำได้ แต่การได้รับความปลอดภัยนั้นต้องใช้งานค่อนข้างมาก ผลข้างเคียง (อย่างน้อยสำหรับโครงการที่ฉันได้ดู) หุ้นจะใหญ่กว่ามาก คุณไม่ต้องการค่าใช้จ่ายเหล่านี้เว้นแต่คุณจะมีเหตุผลที่ดี (ซึ่งบางครั้งคุณทำ)
เราสามารถลองคำนวณค่าประมาณของเขตข้อมูลที่ไม่มีที่สิ้นสุด เช่น จำนวนจริงหรือจำนวนเชิงซ้อน แต่ในกรณีนี้ สิ่งต่างๆ จะซับซ้อนมากขึ้น เนื่องจากเราต้องจัดการกับเลขคณิตที่ไม่แน่นอนด้วย ฉันไม่เห็นใครพยายามทำเช่นนี้ยกเว้นโดยไม่ได้ตั้งใจ
พื้นที่อื่น ๆ ของการเข้ารหัส: เขตข้อมูลจำกัดถูกใช้ทั่วการเข้ารหัส โดยทั่วไปแล้ว สิ่งนี้เกี่ยวข้องกับองค์ประกอบที่ไม่ใช่ศูนย์ในฟิลด์ที่มีการคูณผกผัน ซึ่งเรามักจะต้องการ การดำเนินการยังมีคุณสมบัติที่ดีและพิสูจน์ได้อีกมากมาย
ส่วนที่มีขอบเขตมักจำเป็นสำหรับการใช้งานจริง และบางครั้งเนื่องจากคุณสมบัติเฉพาะของเขตข้อมูลจำกัด
เออีเอส: ตัวอย่างหนึ่งอยู่ใน AES sbox ซึ่งมีคุณสมบัติที่ต้องการมากมายตามมาจากคุณสมบัติเกี่ยวกับพีชคณิต คุณจะไม่ได้รับคุณสมบัติทางพีชคณิตเหมือนกันจากจำนวนเต็มโมดูโล 256 (วงแหวน) เป็นต้น
กลุ่มย่อยที่ทวีคูณ: อีกตัวอย่างหนึ่งคือกลุ่มย่อยแบบทวีคูณของเขตข้อมูลจำกัด (องค์ประกอบที่ไม่ใช่ศูนย์ของเขตข้อมูลจำกัดสร้างกลุ่มแบบวนรอบ) ซึ่งสำหรับเขตข้อมูลจำกัดที่เลือกอย่างระมัดระวังกลายเป็นกลุ่มที่เหมาะสมสำหรับการเข้ารหัสแบบ d.log. (ลอการิทึมแบบไม่ต่อเนื่องถูกกำหนดในลักษณะเดียวกันกับลอการิทึมทั่วไป แต่ปรากฎว่าในบางกลุ่ม ดูเหมือนว่าจะคำนวณได้ยากมากหากไม่มีคอมพิวเตอร์ควอนตัม)
ในกรณีนี้ เราสามารถใช้วงแหวนบางวงได้เช่นกัน แต่ปรากฎว่าในทางปฏิบัติแล้ว ฟิลด์จำกัดเฉพาะจะดีกว่าสำหรับแอปพลิเคชันประเภทนี้ ตัวอย่างเช่น ความปลอดภัยไม่ได้ขึ้นอยู่กับคำสั่งของกลุ่มลับ ซึ่งช่วยให้เราทำบางสิ่งที่คุณไม่สามารถทำได้หากไม่ทราบคำสั่งของกลุ่ม (RSA ทำงานบนวงแหวนดังกล่าว แต่มีคุณสมบัติและข้อกำหนดอื่น ๆ )
เส้นโค้งวงรี: อีกตัวอย่างหนึ่งคือเส้นโค้งวงรีซึ่งใช้กันอย่างแพร่หลายในการเข้ารหัส (แม้แต่การเข้ารหัสหลังควอนตัม) แม้ว่าบางอย่างที่คล้ายกับเส้นโค้งวงรีสามารถกำหนดได้เหนือโครงสร้างพีชคณิตอื่นๆ เช่น วงแหวน แต่ทฤษฎีที่สมบูรณ์ของเส้นโค้งวงรีจำเป็นต้องทำงานในฟิลด์ต่างๆ
การศึกษาเส้นโค้งวงรีเป็นส่วนสำคัญของทฤษฎีจำนวน แต่สำหรับวัตถุประสงค์ในการเข้ารหัส เส้นโค้งที่กำหนดไว้เหนือเขตข้อมูลที่ไม่มีที่สิ้นสุดนั้นใช้ไม่ได้จริงหรือไม่เหมาะสมสำหรับวัตถุประสงค์การใช้งาน และไม่มีคุณสมบัติด้านความปลอดภัยที่จำเป็น (ตัวอย่างเช่น บันทึกแบบไม่ต่อเนื่องโดยประมาณสามารถคำนวณได้โดยการดูที่ขนาดของพิกัด ซึ่งอาจทำให้ความปลอดภัยเสียหาย หากไม่ใช้งานจริงได้ไม่สมบูรณ์ในขั้นแรก) แม้ว่าเส้นโค้งวงรีที่กำหนดเหนือฟิลด์ที่ไม่มีที่สิ้นสุดจะไม่ถูกใช้ในการเข้ารหัส การศึกษาของพวกเขามีความสำคัญสำหรับการวิเคราะห์การเข้ารหัสเส้นโค้งวงรี
เส้นโค้งวงรีบนวงแหวนจำกัดบางวงได้รับการพิจารณาในบริบทการเข้ารหัส แต่ยกเว้นกรณีที่คลุมเครือไม่ได้นำเสนอสิ่งที่น่าสนใจ (เห็นได้ชัดว่ายกเว้นแฟคตอริ่งเส้นโค้งวงรี!)
ตัวอย่างเพิ่มเติม: การเข้ารหัสแบบ Lattice และการเข้ารหัสแบบใช้รหัส ซึ่งใช้โครงสร้างพีชคณิตที่กำหนดผ่านเขตข้อมูลจำกัด การเข้ารหัสแบบหลายตัวแปรซึ่งอิงตามระบบสมการพหุนามบนฟิลด์จำกัด
อีกครั้ง สิ่งเหล่านี้สามารถทำได้บนวงแหวนจำกัดบางวง แต่มีข้อเสียมากมายและไม่ได้อะไรมากมาย
สำหรับ Shamir's Secret Sharing โดยเฉพาะ บทความ Wikipedia พูดเกี่ยวกับ เหตุใดจึงใช้เขตข้อมูลจำกัด แทนวงแหวนอื่นในฟิลด์ที่จำกัด จะไม่มีการรั่วไหลของข้อมูลเกี่ยวกับความลับโดยการรู้จำนวนหุ้นที่ต่ำกว่าเกณฑ์ เหตุผลนี้คือทุกฟังก์ชันบนฟิลด์จำกัดมีการแทนค่าพหุนามเฉพาะ (ระดับสูงสุด q-1)
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
