Cryptology Academy · บทเรียน

การคูณสเกลาร์และ ECDLP

ทำความเข้าใจการบวกจุดซ้ำและเหตุผลที่การย้อนกระบวนการทำได้ยาก

บทเรียน 2 จาก 413 ขั้นตอน

การคูณสเกลาร์และ ECDLP เป็นบทเรียน Cryptology Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Cryptology Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Cryptology Academy มีบทเรียนทั้งหมด 4 บทเรียน

ยินดีต้อนรับ

การคูณสเกลาร์เป็นการดำเนินการหลักของ EC: คำนวณ k×P ด้วยการใช้กฎของกรุปซ้ำ ๆ ECDLP — การหา k เมื่อกำหนด k×P — เป็นปัญหายากที่รักษาความปลอดภัยให้การเข้ารหัสเส้นโค้งวงรีทั้งหมด

นิยามการคูณสเกลาร์

k×P = P + P + ... + P (k ครั้ง) สำหรับ k=4: 4P = P+P = 2P; 2P+2P = 4P สำหรับ k=2^256 การวนซ้ำโดยตรงไม่สามารถทำได้จริง เราจึงต้องใช้อัลกอริทึมที่มีประสิทธิภาพ

อัลกอริทึมดับเบิลแอนด์แอด

คล้ายกับการยกกำลังสองและคูณ: สำหรับแต่ละบิตของ k จาก MSB ถึง LSB: R = 2R (ทวี) ถ้าบิตเป็น 1: R = R + P (บวก) การดำเนินการของกรุป O(log k) ครั้ง ≈ O(256) ครั้งสำหรับ P-256

ตัวอย่าง: 13×P

13 = 1101 ในระบบเลขฐานสอง เริ่มต้น: R = P 1: R = 2P+P = 3P (สำหรับบิต 1) 0: R = 6P 1: R = 12P+P = 13P ✓ ทวี 4 ครั้ง + บวก 2 ครั้งสำหรับ k=13

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

กำหนดจุด G และ Q = k×G บนเส้นโค้ง จงหา k ไปข้างหน้า: ทำได้ง่าย (การดำเนินการ O(log k) ครั้ง) ย้อนกลับ: ยังไม่มีอัลกอริทึมพหุนามที่รู้จักสำหรับเส้นโค้งที่ใช้ในการเข้ารหัส อัลกอริทึมทั่วไปที่ดีที่สุด: โรของ Pollard ในเวลา O(√n) ≈ 2^128 สำหรับ P-256

เหตุใด ECDLP จึงยากกว่า DLP

DLP แบบดั้งเดิม (g^k mod p): อัลกอริทึมแคลคูลัสของดัชนีทำงานในเวลาย่อยเลขชี้กำลัง ส่วน ECDLP: ยังไม่มีสิ่งเทียบเท่าแคลคูลัสของดัชนีที่รู้จักสำหรับเส้นโค้งวงรีทั่วไป ความยาวกุญแจเท่ากัน แต่เป็นปัญหาที่แก้ได้ยากกว่ามาก

การโจมตีแบบ Pohlig-Hellman

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

การโจมตีแบบ MOV

การโจมตีแบบ MOV แปลง ECDLP เป็น DLP ในฟิลด์จำกัดผ่านการจับคู่ Weil ใช้ได้เฉพาะกับเส้นโค้งซูเปอร์ซิงกูลาร์ (ดีกรีการฝัง k=1,2) เส้นโค้งของ NIST ทั้งหมดต้านทาน MOV ได้

การคูณสเกลาร์แบบใช้เวลาคงที่

ดับเบิลแอนด์แอดแบบพื้นฐานเปิดเผย k ผ่านเวลาในการทำงาน (ขั้นตอนการบวกแบบมีเงื่อนไข) ให้ใช้บันไดมอนต์โกเมอรีหรืออัลกอริทึมแบบหวี ซึ่งดำเนินการเหมือนกันโดยไม่ขึ้นกับบิตของกุญแจ สิ่งนี้จำเป็นต่อการใช้งานที่ปลอดภัย

ระดับความปลอดภัยของ ECDLP

P-192: ความปลอดภัย 96 บิต (NIST เลิกแนะนำแล้ว) P-224: ความปลอดภัย 112 บิต P-256: ความปลอดภัย 128 บิต (มาตรฐานปัจจุบัน) P-384: ความปลอดภัย 192 บิต P-521: ความปลอดภัย 260 บิต Curve25519: ความปลอดภัย 128 บิต

จากความปลอดภัยของ ECDLP สู่ความปลอดภัยของ ECDH

ความปลอดภัยของ ECDH ลดรูปได้เป็น ECDLP: หากคุณแก้ ECDLP ได้ (หา a จาก A=a×G) คุณก็จะคำนวณความลับร่วมได้ สมมติฐาน Diffie-Hellman เชิงคำนวณ (CDH) ถือว่าปัญหานี้แก้ได้ยาก

ตรวจสอบอย่างรวดเร็ว

ความซับซ้อนด้านเวลาของอัลกอริทึมทั่วไปที่ดีที่สุด (โรของ Pollard) สำหรับ ECDLP ที่มีอันดับกรุป n คือเท่าใด

ตอบคำถามในบทเรียนแบบโต้ตอบ

สรุปทบทวน

เข้าใจการคูณสเกลาร์และ ECDLP แล้ว ต่อไปเราจะเปรียบเทียบเส้นโค้งมาตรฐาน ได้แก่ P-256, Curve25519 และ secp256k1

เริ่มต้นได้ฟรี

เรียนรู้ Cryptology Academy ด้วย AI tutor — ฟรี

เขียนและเรียกใช้โค้ดจริงในเบราว์เซอร์ของคุณ รับความช่วยเหลือทันทีจาก AI tutor 24/7 และเรียนรู้ต่อจากที่คุณหยุดบนเว็บหรือในแอป

คอร์ส: 67
บทเรียน: 261

เริ่มเรียนฟรี ดูหลักสูตรเต็ม

คำถามที่พบบ่อย

บทเรียน “การคูณสเกลาร์และ ECDLP” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การคูณสเกลาร์และ ECDLP” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Cryptology Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Cryptology Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การคูณสเกลาร์และ ECDLP”

ทำความเข้าใจการบวกจุดซ้ำและเหตุผลที่การย้อนกระบวนการทำได้ยาก คุณปฏิบัติ Cryptology Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Cryptology Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Cryptology Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน

บทเรียน “การคูณสเกลาร์และ ECDLP” ใช้เวลานานแค่ไหน

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

ฉันเขียนและรันโค้ดในบทเรียน Cryptology Academy นี้ได้ไหม

ได้ บทเรียน Cryptology Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

กฎกรุปของเส้นโค้งวงรี
การคูณสเกลาร์และ ECDLP
เส้นโค้งมาตรฐาน: P-256, Curve25519, secp256k1
ECC กับ RSA: ความสมดุลระหว่างความปลอดภัยและประสิทธิภาพ

← กลับไปที่ Cryptology Academy