Score:2

ความยากของปัญหาลอการิทึมไม่ต่อเนื่องเกี่ยวข้องกับการเข้ารหัสเส้นโค้งวงรีอย่างไร

ธง sr

ตามคำนิยาม ปัญหาลอการิทึมที่ไม่ต่อเนื่องคือการแก้ความสอดคล้องกันต่อไปนี้สำหรับ $x$ และเป็นที่ทราบกันดีว่าโดยทั่วไปแล้วไม่มีอัลกอริทึมที่มีประสิทธิภาพสำหรับสิ่งนั้น

$$\begin{จัด*} b^x\equiv r&\pmod p\quad(1)\end{align*}$$ คือการตามหา $x$ (ถ้ามี) สำหรับที่กำหนด $r,b$ เป็นจำนวนเต็มที่น้อยกว่าจำนวนเฉพาะ $p$.

ฉันถูกต้องแล้วหรือยัง? โปรดแก้ไขฉันหากฉันเข้าใจอะไรผิด

ในการเข้ารหัสแบบวงรี (elliptic curve cryptography) กล่าวกันว่าใน $P=a\คูณ G$ เราไม่สามารถคำนวณได้ $a$ โดยรู้ $พี$ และ $G$ เพราะปัญหาลอการิทึมไม่ต่อเนื่องแก้ยาก ฉันไม่เข้าใจว่าสิ่งนี้เกี่ยวข้องกับสมการ 1 อย่างไร ฉันหมายความว่ามีเพียงคำศัพท์ที่คล้ายกันในทั้งสองปัญหาหรือไม่

เพื่อชี้แจงคำถามของฉัน ลองจินตนาการว่าอัจฉริยะจากคนรุ่นหลังสามารถแนะนำวิธีแก้ปัญหาสมการ 1 ซึ่งทำได้ในเวลาที่เป็นไปได้โดยใช้การตั้งค่าฮาร์ดแวร์โดยเฉลี่ยของเวลานั้น อัลกอริทึมที่พวกเขาเสนอสามารถค้นหาได้ $x$ (ถ้ามี) สำหรับจำนวนเฉพาะที่กำหนด $p$ และใด ๆ ที่กำหนด $r, b$. ตอนนี้ ฉันต้องการทราบว่าสิ่งประดิษฐ์นี้เป็นภัยคุกคามต่อความปลอดภัยของการเข้ารหัสแบบ elliptic curve หรือไม่ กล่าวอีกนัยหนึ่ง ความรู้เกี่ยวกับอัลกอริทึมดังกล่าวจะช่วยในการดึงข้อมูลหรือไม่ $a$ จาก $พี$?

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

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

cn flag
"เป็นที่ทราบกันดีว่าไม่มีอัลกอริธึมที่มีประสิทธิภาพสำหรับสิ่งนั้น โดยทั่วไป" นั่นไม่เป็นที่รู้จัก หากทราบ เราก็จะรู้ว่า $P \neq NP$
kelalaka avatar
in flag
[ลอการิทึมไม่ต่อเนื่อง: ให้ a p การหาลอการิทึมแยกของ x เป็นฐาน y หมายความว่าอย่างไร](https://crypto.stackexchange.com/q/76230/18298) [สรุปปัญหาทางคณิตศาสตร์ที่เป็นหัวใจของการทำลายคีย์สาธารณะของ Curve25519](https://crypto.stackexchange.com/q/50405/18298) [ทำไมต้องเป็น Elliptic Curves](https://crypto.stackexchange.com/q /26873/18298)
kelalaka avatar
in flag
นอกจากนี้ หากไม่มีโครงสร้างพิเศษในเส้นโค้ง ทฤษฎีกลุ่มทั่วไปจะบอกเราว่าดีที่สุดที่คุณสามารถดำเนินการ $\sqrt{n/2}$-time สำหรับ dlog ใน ECC
PouJa avatar
sr flag
@Maeher ขออภัยสำหรับภาษาอังกฤษที่ไม่ดีของฉัน ฉันหมายความว่าเรารู้ว่าไม่มีอัลกอริทึมที่รู้จัก ไม่ใช่ว่าเรามั่นใจว่าไม่มีอัลกอริทึมใดที่จะมีอยู่จริง
kelalaka avatar
in flag
Quantum on ECC Dlog คำตอบที่ยอมรับได้: [การคำนวณควอนตัมมีประสิทธิภาพเพียงใดเมื่อเทียบกับการเข้ารหัสเส้นโค้งวงรี] (https://crypto.stackexchange.com/q/59770/18298)
Score:6
ธง ru

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

กลุ่มสามารถเขียนด้วยสัญกรณ์การคูณ (เช่นเดียวกับโมดูโลกลุ่มการคูณ $p$) เพื่อให้การทำงานของกลุ่มถูกเขียนเป็น $*$, $\times$, $\cdot$ หรือโดยปริยาย ในกรณีทั้งหมดเหล่านี้ เราจะใช้สัญกรณ์ธรรมชาติสำหรับการใช้ซ้ำๆ ของการดำเนินการกลุ่มด้วยองค์ประกอบเดียว เช่น $b^2:=b*b$ และภาพรวมที่คล้ายคลึงกัน ดังนั้นปัญหาลอการิทึมแบบไม่ต่อเนื่องทั่วไปสำหรับกลุ่มวัฏจักร $C$ เขียนด้วยสัญกรณ์การคูณที่สร้างโดย $ข$ จะได้รับ $r\ ใน C$ หาจำนวนเต็ม $x$ ดังนั้น $b^x=r$.

กลุ่มอื่นเขียนด้วยสัญกรณ์เพิ่มเติม (โดยปกติจะสงวนไว้สำหรับกลุ่มอาเบเลียน รวมทั้งกลุ่มเส้นโค้งวงรี) ในกรณีนี้การดำเนินการกลุ่มจะแสดงแทน $+$ (แต่ไม่ควรอ่านเป็นการเพิ่มเติมในความหมายปกติ) และอีกครั้ง มีสัญกรณ์ธรรมชาติสำหรับการใช้ซ้ำๆ ของการดำเนินการกลุ่มด้วยองค์ประกอบเดียว เช่น $2G=G+G$ และอื่น ๆ เมื่อเขียนด้วยวิธีนี้ ปัญหาลอการิทึมที่ไม่ต่อเนื่องสำหรับกลุ่มวัฏจักร $C$ ที่สร้างขึ้นโดย $G$ กลายเป็น: ให้ $P\ใน C$ หาจำนวนเต็ม $x$ ดังนั้น $xG=P$.

ไม่เชื่อว่าจะเป็นการแปลที่ชัดเจนระหว่างปัญหาลอการิทึมที่ไม่ต่อเนื่องในกลุ่มต่างๆ มีบางกลุ่มที่ปัญหาลอการิทึมไม่ต่อเนื่องเป็นเรื่องง่าย (เช่น โมดูโลกลุ่มบวก $p$, โมดูโลกลุ่มคูณ $2^n$ และแม้กระทั่ง (ในความหมายกึ่งพหุนาม) กลุ่มการคูณของ $GF(2^n)$).

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

โปรดทราบว่าปัญหาลอการิทึมที่ไม่ต่อเนื่องทั้งหมดสามารถแก้ไขได้ในเวลาพหุนาม (ควอนตัม) โดย อัลกอริทึมของชอร์.

PouJa avatar
sr flag
ขอบคุณสำหรับคำตอบ. โปรดเจาะจงมากขึ้นเกี่ยวกับคำถามสุดท้าย คำตอบคือใช่หรือไม่ใช่ ฉันยังคงสับสน
Daniel S avatar
ru flag
ไม่ ไม่มีทางทราบวิธีการถ่ายโอนปัญหา
Myria avatar
in flag
โปรดทราบว่ากลุ่มวัฏจักรทั้งหมดจะเป็นไอโซมอร์ฟิกสำหรับกลุ่มวัฏจักรอื่น ๆ ในลำดับเดียวกัน ดังนั้น $(\mathbb{Z}/{(p-1)}\mathbb{Z})^+$ และ $(\mathbb{Z}/p\mathbb{Z})^\times$ จึงเป็นไอโซมอร์ฟิคสำหรับไพรม์ $ p$ และลอการิทึมแบบไม่ต่อเนื่องใน $(\mathbb{Z}/{(p-1)}\mathbb{Z})^+$ นั้นง่ายและเป็นลอการิทึมแบบไม่ต่อเนื่องใน $(\mathbb{Z}/p\mathbb{ Z})^\times$ ยาก
Score:0
ธง tl

อนุญาต $E$ เป็นเส้นโค้งวงรีที่กำหนดบนเขตข้อมูลจำกัด $\mathbb{F}_p$:

$$E : y^2 = x^3 + Ax + B \text{ กับ } A, B \in \mathbb{F}_p$$

อนุญาต $พี$ และ $T$ เป็นจุดใน $E(\mathbb{F}_p)$. ค้นหาจำนวนเต็ม $a$ ดังนั้น นั่น

$$P =aG$$

นี่คือปัญหาสำหรับเส้นโค้งวงรี ปัญหาสามารถเขียนใหม่ได้โดยใช้ลอการิทึม:

$$a = log_G (P)$$

คุณสามารถเปรียบเทียบกับลอการิทึมแยก "มาตรฐาน":

$$ b^x \equiv r \mod p \ลูกศรขวา x = log_b(r)$$

ตอนนี้คุณเห็นความคล้ายคลึงกันหรือไม่?

บันทึก: อัจฉริยะของคุณควรมีวิธีที่มีประสิทธิภาพในการทำลายมัน ไม่ใช่เพราะเขามีทรัพยากรไม่จำกัด และใช่ ถ้าคุณมีวิธีที่มีประสิทธิภาพในการแยกลอการิทึม คุณสามารถใช้รูปแบบนี้เพื่อทำลายเส้นโค้งวงรี ประเด็นหลักของการเข้ารหัสลับเส้นโค้งวงรีคือการคำนวณนั้นเร็วกว่าระบบลอการิทึมแบบแยก "มาตรฐาน" (มีข้อดีอื่น ๆ มากมายสำหรับ ecc)

PouJa avatar
sr flag
อะไรคือประเด็นในการเขียน $P=a\times G$ เป็น $a = log_G (P)$ ทำไมเราไม่สามารถพูดว่า $a=P\times G^-1$ ได้ เมื่อพูดถึงลอการิทึม ควรมีฐานและกำลัง ในที่นี้ $G$ ไม่ได้ยกกำลัง $a$ ใช่ไหม? @ไททันลอร์ด
PouJa avatar
sr flag
ทำไมคุณถึงบอกว่าการคำนวณในเส้นโค้งวงรีนั้นเร็วกว่าในขณะที่การคำนวณ $r$ จาก $b$ และ $x$ นั้นดูตรงไปตรงมามากกว่าเมื่อเปรียบเทียบกับการคำนวณ $P$ จาก $a$ และ $G$ ด้วยการเพิ่มและ ฟังก์ชันทวีคูณที่เกี่ยวข้องกับการคำนวณค่าผกผันโมดูลาร์หลายครั้งในระหว่าง? @ไททันลอร์ด
Titanlord avatar
tl flag
ใน $\mathbb{F}$ เราสามารถเขียนปัญหาใหม่ได้เหมือนที่ฉันทำ นี่ควรแสดงให้คุณเห็นความคล้ายคลึงกันของปัญหา การโจมตีที่รู้จักในปัญหาบันทึกแยกเป็นพื้นฐานสำหรับการโจมตีบนเส้นโค้งวงรี เช่น. Baby-Step-ยักษ์-Step.
Titanlord avatar
tl flag
คุณอาจคำนวณได้เร็วขึ้นบนกระดาษ แต่คอมพิวเตอร์ที่มีการทำงานแบบมาตรฐานต้องการเวลานานในการคำนวณเลขชี้กำลังใน $\mathbb{F}$ ซึ่งในความเป็นจริงแล้วสิ่งนี้ส่งผลให้มีการดำเนินการมากกว่าที่จำเป็นสำหรับวิธีบวกและวิธีสองเท่า

โพสต์คำตอบ

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