เหตุใดเส้นโค้งวงรีบนฟิลด์ไบนารีจึงใช้น้อยกว่าที่ใช้บนฟิลด์ไพรม์ï¼

ในการใช้งานจริง เส้นโค้งวงรีมากกว่า $F_p$ ดูจะเป็นที่นิยมกว่าที่อื่น $F_{2^n}$. เป็นเพราะการดำเนินการในฟิลด์สำคัญนั้นเร็วกว่า $F_{2^n}$ เพื่อความปลอดภัยระดับเดียวกัน?

อาจจะเป็นจินตนาการของฉัน ฉันเพิ่งเห็นโครงการเปิดอื่น ๆ อีกมากมายที่ใช้เส้นโค้งวงรี $F_p$ แต่ไม่มากเท่า $F_{2^n}$.

ความปลอดภัย: ฟิลด์ไบนารีมีเวกเตอร์การโจมตีมากกว่าฟิลด์ไพรม์

บันทึกไม่ต่อเนื่องบน ECCs กับเขตข้อมูลไบนารีจะไม่เสีย นั่นไม่ใช่เหตุผล เบิร์นสไตน์ กล่าว;

เรื่องราวความปลอดภัยสำหรับฟิลด์ที่ไม่ใช่ไพรม์ (เช่น ฟิลด์ส่วนขยายไบนารี) คือ ซับซ้อนกว่าและเสถียรน้อยกว่า กว่าเรื่องความปลอดภัยสำหรับเขตข้อมูลหลักดังที่แสดงโดย 1998 Frey, 2002 GaudryâHessâSmart, 2009 Gaudry และ 2012 PetitâQuisquater

ด้วยเหตุนี้ การเลือกฟิลด์หลักจึงช่วยลดเวกเตอร์การโจมตี ดังนั้นจึงมีความกังวลน้อยลงในเรื่องความปลอดภัย

• 2002 แง่มุมที่สร้างสรรค์และทำลายล้างของ Weil Descent บนเส้นโค้งวงรี

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

• 2004 แคลคูลัสดัชนีสำหรับพันธุ์อาเบเลียนและปัญหาลอการิทึมไม่ต่อเนื่องเส้นโค้งวงรี โดย Pierrick Gaudry

  เราได้แสดงให้เห็นว่าเส้นโค้งวงรีแบบไม่กำหนดเส้นกำกับเหนือฟิลด์ส่วนขยายระดับเล็กนั้นเป็นอย่างไร อ่อนแอ กว่าที่กำหนดไว้ในฟิลด์เฉพาะหรือฟิลด์ส่วนขยายระดับเฉพาะขนาดใหญ่

• 2012 เกี่ยวกับระบบพหุนามที่เกิดจาก Weil Descent โดย Christophe Petit และ Jean-Jacques Quisquater

  พวกเขาได้ดูที่ ECDLP ในฟิลด์ส่วนขยายไบนารีและแสดงว่าอัลกอริทึมของพวกเขามีประสิทธิภาพดีกว่าอัลกอริทึมลอการิทึมแบบแยกทั่วไปสำหรับ $N >2000$. ขนาดที่แนะนำยังไม่ได้รับผลกระทบ!

สิทธิบัตรของ Certicom ( และอื่นๆ)

ประเด็นสำคัญอีกประการหนึ่งคือ สิทธิบัตร ที่ Certicom ส่วนใหญ่มี/มี

อันดับแรก คำพูดของ Bruce Schneier

"Certicom สามารถอ้างสิทธิ์ความเป็นเจ้าของ ECC ได้อย่างแน่นอน" Schneier กล่าวกับเรา "อัลกอริธึมได้รับการพัฒนาและจดสิทธิบัตรโดยผู้ก่อตั้งบริษัท และสิทธิบัตรเขียนไว้อย่างดีและรัดกุม ฉันไม่ชอบ แต่พวกเขาสามารถอ้างความเป็นเจ้าของได้"

• หนึ่งในสิทธิบัตรของ Certicom มีประสิทธิภาพ $\operatorname{GF}(2^n)$ การคูณในรูปแบบปกติ สิทธิบัตรสหรัฐอเมริกา 5,787,028. สิทธิบัตรนี้ได้รับในปี 1998 และหมดอายุในปี 2016
• NSA มีสิทธิบัตรบางอย่างเกี่ยวกับ $\operatorname{GF}(2^n)$, ด้วย; [1] [2] [3] [4]อย่างไรก็ตาม หมดอายุเร็วมากเนื่องจาก NSA ไม่จ่ายค่าธรรมเนียม (ฉันคิดว่าจงใจ)

ขั้นตอนปัจจุบันของการโจมตีเพื่อเปรียบเทียบ

ถ้าเราดูที่ ความท้าทาย ECC ของ Certicom

• Koblitz โค้งกว่า $2^{108}$ แตกหักในปี 2543
• ก $109$ บิตไพรม์โค้งเสียในปี 2545
• โค้งกว่า $2^{109}$ พังในปี 2547
• ความท้าทายไบนารีหรือไพรม์ 131 บิตยังไม่ถูกทำลาย

นอกเหนือจากความท้าทายเหล่านี้

• ปัญหาลอการิทึมโค้งวงรี 117.35 บิตบนเส้นโค้งไบนารีเสียในปี 2559 โดย Bernstein et อัล

ข้อเท็จจริงแบบติดดินที่เปลี่ยนความสมดุลไปสู่ $\mathbb F_p$ คือซีพียูมาตรฐานของปี 1990 และต้นยุค 2000 มักจะมีคำสั่งหลายคำสั่ง แต่ไม่มีการสนับสนุนฮาร์ดแวร์สำหรับ สินค้าพกพาน้อย, พลิกกลับได้เปรียบ $\mathbb F_{2^k}$ มีในฮาร์ดแวร์ และเลขคณิตใน $\mathbb F_p$ ได้รับการศึกษาอย่างกว้างขวางสำหรับ RSA และ DSA เป็นที่เข้าใจกันว่าผู้คนเริ่มใช้ $\mathbb F_p$และจากนั้นก็ไม่มีเหตุผลอันควรที่จะต้องเปลี่ยนแปลง บางที (ต่อใน ความคิดเห็นนี้) สิทธิบัตรของ Certicom เกี่ยวกับ ECC ใน $\mathbb F_{2^k}$ ขับไล่ผู้ทำนายออกไป นอกจากนี้ ผู้คนจำนวนมากเข้าใจเลขคณิตใน $\mathbb F_p$, และ ไม่มีใครเคยถูกไล่ออกจากการเลือก.

จากมุมมองด้านความปลอดภัย ฉันคิดว่ามีความรู้สึกที่สมเหตุสมผลกับ $\log_2p\ประมาณ m$, ECC ในเขตไพรม์ $\mathbb F_p$ ปลอดภัยกว่าในสนามเลขฐานสอง $\mathbb F_{2^m}$. เหตุผลที่ฉันเข้าใจคือ:

• สำหรับที่กำหนด $m$, มีประมาณ $\ประมาณ0.69\cdot2^m/m$ ทางเลือกสำหรับ $p$. ฟิลด์จำกัดทั้งหมดของคำสั่งที่กำหนดเป็นแบบไอโซมอร์ฟิค ดังนั้น $\mathbb F_{2^m}$ เป็นกรณีพิเศษ และใน crypto กรณีพิเศษแทบจะไม่ปลอดภัย
• อย่างน้อยในฮาร์ดแวร์ การเพิ่มจุด ECC นั้นมีค่าใช้จ่ายสูงกว่ามากในภาคสนาม $\mathbb F_p$ มากกว่าในสนาม $\mathbb F_{2^m}$. บางทียากขึ้นแปลว่าปลอดภัยกว่า และยากกว่าแปลว่าปลอดภัยน้อยกว่าก็น่าแปลกใจทีเดียว
• การแก้ DLP ในกลุ่มย่อยแบบคูณของฟิลด์ $\mathbb F_p$ ยากกว่าสำหรับ $\mathbb F_{2^m}$ดังจะเห็นได้จากบันทึก ($795\text{-บิต }p$ ใน $\mathbb F_p$, $m=30750$ ใน $\mathbb F_{2^m}$ ). อีกครั้ง บางที DLP ที่ยากขึ้นในกลุ่มย่อยแบบทวีคูณบ่งชี้ว่า DLP ที่ยากขึ้นในกลุ่ม ECC และคงเป็นเรื่องที่น่าแปลกใจที่มันบอกเป็นนัยว่า DLP ง่ายกว่าในกลุ่ม ECC

มีเหตุผลด้านความปลอดภัยอื่นๆ ฉันอ้างถึงกระสุนสามนัดแรกของ คำตอบอื่น ๆ. ฉันเข้าใจว่าพวกเขาแทบจะไม่เพียงพอที่จะบอกว่าพวกเขาไม่ได้นำไปสู่การโจมตี ECC ทั่วไปใน $\mathbb F_{2^m}$, เช่น. บนทางโค้งเข้า ส่วนที่ 3 ของ sec2v2. แต่ถึงกระนั้นมันก็สมเหตุสมผลที่พวกเขาจะสร้างความไม่สบายใจ

ในท้ายที่สุดฉันก็ยอมรับเช่นเดียวกับคนส่วนใหญ่ ภูมิปัญญาของ Safecurve :

2549 เบิร์นสไตน์ ระบุว่าไพรม์ฟิลด์ "มีประโยชน์ในการลดจำนวนข้อกังวลด้านความปลอดภัยสำหรับการเข้ารหัสแบบวงรี-เส้นโค้ง" ในทำนองเดียวกัน มาตรฐาน Brainpool และมาตรฐาน Suite B ของ NSA จำเป็นต้องมีฟิลด์เฉพาะ มีข้อตกลงทั่วไปว่าช่องหลักเป็นตัวเลือกที่ปลอดภัยและอนุรักษ์นิยมสำหรับ ECC