ไม่มีที่ฉันรู้ แต่คุณอาจสร้างได้ (ทำไมคุณต้องการหนึ่ง แต่เป็นคำถามอื่น ... )
คุณสามารถค้นหาคำถามที่เกี่ยวข้องและคำตอบที่ยอดเยี่ยมได้ ที่นี่แม้ว่าจะไม่เกี่ยวกับเส้นโค้งวงรีโดยเฉพาะ โดยพื้นฐานแล้ว TL;DR นั้นง่ายกว่าในการสร้างแผนที่ทวิเนียร์ในกลุ่มของคำสั่งผสม $N=pq$ กับ $p$ และ $คิว$ จำนวนเฉพาะ เนื่องจากสิ่งเหล่านี้จะมีกลุ่มย่อยสองกลุ่มย่อยของลำดับจำนวนเฉพาะขนาดใหญ่ตามธรรมชาติจากทฤษฎีบทของลากรองจ์
ตอนนี้สำหรับ Elliptic Curves นั้นแตกต่างกันเล็กน้อย เรากำลังสร้าง "กลุ่มเส้นโค้งวงรี" ที่กำหนดไว้ในฟิลด์ที่กำหนด "พิกัด" ของจุดโค้งวงรีนั้น "มีชีวิต" ในฟิลด์นั้น แต่จุดต่างๆ นั้น "มีชีวิต" ในกลุ่ม EC
ทั้งคู่มี คำสั่งซื้อที่แตกต่างกัน. เขตข้อมูลมีลำดับของตัวเองและกลุ่มเส้นโค้งวงรีมีลำดับของตัวเอง $n$ (ซึ่งสามารถเป็นคอมโพสิตหรือไพรม์) เมื่อเราพูดถึงเส้นโค้งลำดับเฉพาะ โดยทั่วไปเราจะพิจารณาลำดับของกลุ่มเส้นโค้งวงรี ไม่ใช่ลำดับของฟิลด์พื้นฐานที่กำหนดไว้
สิ่งหนึ่งที่ต้องรู้ในสาขานั้นคือมีสิ่งที่เรียกว่า การโจมตีแบบ MOV ที่ใช้การจับคู่แบบบิลิเนียร์จับคู่จุดสองจุดในเส้นโค้งวงรี $E(\mathbb{F}_q)$ ไปยังองค์ประกอบในฟิลด์ $\mathbb{F}_{q^k}$, สำหรับ $k$ ระดับการฝังของเส้นโค้งนั้น เรากำหนด $k$ เป็นค่าต่ำสุดเช่นนั้น $n | q^k-1$. การโจมตี MOV นั้นอันตรายเพราะหาก $k$ เป็น เล็กจากนั้นการแก้ DLP ในฟิลด์ส่วนขยายนั้นจะง่ายกว่าในกลุ่มเส้นโค้งวงรีเริ่มต้น และแมปกลับไปที่วิธีแก้ปัญหาบนเส้นโค้งวงรี ซึ่งทำลายความปลอดภัยได้อย่างมีประสิทธิภาพ
ดังนั้น Elliptic Curves ทั่วไปที่เราใช้สำหรับ ECDSA, ECDH และรูปแบบเส้นโค้งวงรีอื่นๆ (ที่ไม่ได้อิงตามการจับคู่) จึงมีข้อกำหนดว่าระดับการฝังมีขนาดใหญ่ ก.ล.ต. 1 v2 พูดว่า:
สุดท้าย แม้ว่าจะไม่ทราบถึงอัลกอริธึมซับเอ็กซ์โปเนนเชียลทั่วไปในการแก้ ECDLP แต่เส้นโค้งสามคลาสนั้นไวต่ออัลกอริทึมวัตถุประสงค์พิเศษ ประการแรก เส้นโค้งวงรี $E$ เกิน $F_q$ กับ $n$ การแบ่ง $q^B â1$ สำหรับขนาดเล็ก $B$ มีความอ่อนไหวต่อการโจมตีที่อธิบายโดย Menezes, Okamoto และ Vanstone [MOV93] และ Frey และ Rück [FR94] การโจมตีลด ECDLP ได้อย่างมีประสิทธิภาพ บนเส้นโค้งเหล่านี้กับปัญหาลอการิทึมแบบไม่ต่อเนื่องแบบดั้งเดิมในการขยายระดับเล็กน้อยของ $F_q$. ผูกพัน $B ⥠20$ ถูกปรับปรุงเป็น $B €100$ ใน [X9.62a] เพื่อให้มีขอบขนาดใหญ่เพื่อความปลอดภัย
ที่นี่ของพวกเขา $B$ คือคุณค่าของเรา $k$.
การเลือกระดับการฝังนั้น $k$ สำหรับการเข้ารหัสแบบจับคู่เป็นการประนีประนอมระหว่างความปลอดภัยและประสิทธิภาพ: ระดับการฝังที่มากขึ้นหมายถึงปัญหาลอการิทึมที่ไม่ต่อเนื่องนั้นยากต่อการแก้ปัญหาในกลุ่มการคูณที่เกิดขึ้น แต่ก็หมายความว่าการดำเนินการจะดำเนินการในฟิลด์ส่วนขยายระดับที่สูงขึ้น ซึ่งมีประสิทธิภาพน้อยกว่า...
ตอนนี้ เมื่อเราพูดถึงเส้นโค้ง "เป็นมิตรกับการจับคู่" สิ่งที่มักจะหมายถึงคือเรารู้วิธีสร้างการจับคู่ที่จะ "ง่าย" คำนวณ สำหรับเส้นโค้งวงรีนั้น นอกจากนี้ยังหมายความว่าโดยปกติแล้วเราคาดว่าจะมีค่าค่อนข้าง "ต่ำ" สำหรับ $k$, เวลาส่วนใหญ่ $k \leq 24$. (หากต้องการดูภาพรวมของเส้นโค้งวงรีของการฝังองศาที่ 1 แนะนำให้อ่าน กระดาษ 2016 นี้.)
การรักษาความปลอดภัยของ DLP หมายความว่าอย่างไร อนุญาต $G$ เป็นกลุ่มย่อยของคำสั่ง $คิว$ ใน $E(F_p)$. เดอะ อัลกอริทึมของพอลลาร์ด-โร ในกลุ่มย่อย $G$ ของเส้นโค้งวงรีของเราจะใช้เวลา $\sqrt{\frac{Ïq}{2}}$ ขั้นตอนและแต่ละขั้นตอนจะใช้เวลา ~$O(\log^2(p))$. ซึ่งหมายความว่าเราต้องการตรวจสอบลำดับกลุ่มย่อยของเรา $คิว$ มีขนาดใหญ่ที่สุดเท่าที่จะเป็นไปได้เพื่อให้อัลกอริทึม Pollard-Rho ใช้เวลานานที่สุด
ด้วยการโจมตี MOV ที่กล่าวถึงข้างต้น $e : G\times G' âF_{p^k}$ , ที่ไหน $k$ คือระดับการฝัง เปิด DLP $G$ จากนั้นสามารถแปลเป็น DLP บน $F_{p^k}$ และ Pollard-Rho ในฟิลด์ส่วนขยายของเรา $F_{p^k}$ ความต้องการด้วย $\sqrt{\frac{Ïq}{2}}$ ขั้นตอน แต่แต่ละขั้นตอนใช้เวลาเท่านั้น $O(k \log(p))$นี่เป็นความแตกต่างอย่างมากในความซับซ้อน
นี่คือเหตุผลที่เราต้องการให้มีระดับการฝังขนาดใหญ่ $k$ สำหรับเส้นโค้งวงรีที่ใช้สำหรับ ECC ปกติ ดังที่ฉันได้กล่าวไว้ข้างต้นแล้ว แต่ไม่จำเป็นในการเข้ารหัสแบบจับคู่
ในที่สุด สิ่งสำคัญคือต้องระลึกไว้เสมอว่าเหตุใด "คำสั่งเฉพาะ" จึงน่าสนใจสำหรับ DLP นั่นเป็นเพราะ อัลกอริทึม Pohlig-Hellmanซึ่งกรณีความซับซ้อนที่เลวร้ายที่สุดคืออัลกอริทึมขั้นตอนแบบเบบี้สเต็ปยักษ์เมื่อลำดับเป็นจำนวนเฉพาะ
โดยพื้นฐานแล้ว Pohlig-Hellman ก็เหมือนกับ CRT สำหรับ RSA ซึ่งช่วยให้เราทำงานในกลุ่มที่เล็กลงและง่ายขึ้น หากลำดับของกลุ่มเริ่มต้นของเราไม่ใช่ลำดับเฉพาะ
ในการตั้งค่าแบบนั้น การมีลำดับไพรม์จำนวนมากก็สมเหตุสมผลแล้ว เนื่องจากกลุ่มย่อยทั้งหมดในกลุ่มเริ่มต้นของเราต้องแบ่งลำดับ ดังนั้นเรามั่นใจว่า Pollard-Rho นั้นยากที่สุดเท่าที่จะทำได้
น่าสนใจ การโจมตี (ทั่วไป) ที่ดีที่สุด (ดู นี้) ในการเข้ารหัสแบบเส้นโค้งวงรีเป็นการรวมกันของทั้งอัลกอริธึม Pohlig-Hellman และ Pollard-Rho ถ้าคุณแสดงว่า $l$ ตัวหารเฉพาะที่ใหญ่ที่สุดของ $n$การโจมตีนี้สามารถจัดการกับ ECDLP ได้ในเท่านั้น $O(\sqrt{l})$ เวลา ด้วยเหตุนี้เราจึงต้องการให้มีตัวหารเฉพาะมากตามลำดับของเรา $n$...
โปรดสังเกตว่าสำหรับเส้นโค้งที่ผิดปกติ นั่นคือเส้นโค้งวงรีเหนือสนาม $F_p$ ซึ่งเป็นคำสั่งของ EC ด้วย $p$เรามีการโจมตีที่กำลังดำเนินการในเวลาพหุนาม! ดู Satoh และ Araki ที่นี่, หรือ Semaev หรือ ฉลาด:
ในทางปฏิบัติ วิธีการที่อธิบายหมายความว่าเมื่อเลือกเส้นโค้งวงรีเพื่อใช้ในการเข้ารหัส เราต้องกำจัดเส้นโค้งทั้งหมดที่มีคำสั่งกลุ่มเท่ากับลำดับของเขตข้อมูลจำกัด
(เน้นของฉัน)
สังเกตว่าโดยทั่วไปถ้า $nâ1$ เป็นผลคูณของจำนวนเฉพาะขนาดเล็ก จากนั้นอัลกอริทึม PohligâHellman สามารถแก้ปัญหาลอการิทึมแยกในกลุ่มนี้ได้อย่างมีประสิทธิภาพ ซึ่งโดยทั่วไปแล้วเป็นเหตุผลว่าทำไมเราถึงเลือกจำนวนเฉพาะที่ปลอดภัยเมื่อจัดการกับ DLP: ทำให้มั่นใจได้ว่าเรามี " ไพรม์ขนาดใหญ่" ในการสลายตัวของ $n-1$.
ขอให้สังเกตว่าลำดับของเส้นโค้งนั้นเป็นจำนวนจุดตรรกยะบนเส้นโค้งวงรีนั้น หากเราทำงานเกิน $F_p$แล้วเรารู้ว่าจำนวนจุดใน EC ของเราคือ $p+1-t$ ที่ไหน $t$ คือ Frobenius ร่องรอยของเส้นโค้ง. ด้วยทฤษฎีบทของ Hasse เราก็รู้เช่นกัน $t$ อยู่ระหว่าง $-2 \sqrt{p}$ และ $2 \sqrt{p}$.
แต่ใน ECC เรามักจะทำงานกับ กลุ่มย่อย ของเส้นโค้งวงรีที่กำหนดโดยจุดฐาน ลำดับของจุดฐานเป็นตัวหารสำคัญของ $p+1-t$ โดยทฤษฎีบทลากรองจ์
แล้วคุณล่ะอยากเป็นนายกที่ปลอดภัยคนไหน? ฉันจะถือว่ากลุ่มย่อยที่สร้างโดยจุดฐานที่กำหนด
สิ่งนี้เป็นจริงเช่นกันสำหรับการเข้ารหัสตามการจับคู่: การจับคู่ถูกกำหนดผ่านกลุ่มย่อยของกลุ่ม EC โดยทั่วไป จับคู่เท็ด ถือว่า $k>1$, $\#E(F_p) = hn$, สำหรับ $n$ ไพรม์และทำงานในกลุ่มย่อยของคำสั่ง $n$ ของเส้นโค้งวงรีนั้น
น่าเศร้า อย่างที่ฉันบอกคุณในตอนเริ่มต้น ฉันไม่รู้เกี่ยวกับเส้นโค้งที่เป็นมิตรต่อการจับคู่ ซึ่งลำดับของกลุ่มย่อยคือไพรม์ที่ปลอดภัย มันน่าจะสร้างได้ แต่ฉันไม่มีเวลา (ยัง) เขียนสคริปต์การค้นหาที่จะสร้างขึ้นมา เราจะทำอย่างไร? ฉันเกรงว่าวิธีที่ง่ายที่สุดคือ "ลองผิดลองถูก" นั่นเอง!
Barreto และ Naehrig ได้ให้วิธีการหาเส้นโค้งของลำดับเฉพาะด้วย $k = 12$ซึ่งได้รับการ "ขยาย" ให้มีความโค้งมนด้วย $k= 3, 4, 6$ โดย ฟรีแมน.
น่าเศร้าที่ฉันไม่ทราบเกี่ยวกับการใช้งานโอเพ่นซอร์สที่ช่วยให้คุณทำได้อย่างง่ายดาย ลองสร้างเส้นโค้งเหล่านี้
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
