กลับไปหน้าบทความ

อ่าน 10 นาที

อัลกอริทึมลายเซ็นดิจิทัลเส้นโค้งวงรี

ในด้านการเข้ารหัสลับอั ลก อริทึมลายเซ็นดิจิทัลแบบเส้นโค้งวงรี ( ECDSA ) เป็นรูปแบบหนึ่งของอัลกอริทึมลายเซ็นดิจิทัล (DSA) ซึ่งใช้ การเข้ารหัส ลับ แบบเส้นโค้งวงรี

อัลกอริทึมลายเซ็นดิจิทัลเส้นโค้งวงรี

ในด้านการเข้ารหัสลับอั ลก อริทึมลายเซ็นดิจิทัลแบบเส้นโค้งวงรี ( ECDSA ) เป็นรูปแบบหนึ่งของอัลกอริทึมลายเซ็นดิจิทัล (DSA) ซึ่งใช้ การเข้ารหัส ลับ แบบเส้นโค้งวงรี

ขนาดกุญแจและลายเซ็น

เช่นเดียวกับการเข้ารหัสแบบวงรีโดยทั่วไปขนาด บิต ของคีย์ส่วนตัวที่เชื่อว่าจำเป็นสำหรับ ECDSA นั้นมีขนาดประมาณสองเท่าของระดับความปลอดภัยในหน่วยบิต[ 1 ]ตัวอย่างเช่น ที่ระดับความปลอดภัย 80 บิต ซึ่งหมายความว่าผู้โจมตีต้องใช้การดำเนินการสูงสุดประมาณเพื่อค้นหาคีย์ส่วนตัว ขนาดของคีย์ส่วนตัว ECDSA จะเป็น 160 บิต ในทางกลับกัน ขนาดลายเซ็นจะเท่ากันสำหรับทั้ง DSA และ ECDSA: ประมาณบิต โดยที่คือเลขชี้กำลังในสูตรนั่นคือประมาณ 320 บิตสำหรับระดับความปลอดภัย 80 บิต ซึ่งเทียบเท่ากับการดำเนินการ

อัลกอริทึมการสร้างลายเซ็น

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

พารามิเตอร์
เส้นโค้งสนามเส้นโค้งวงรีและสมการที่ใช้
จีจุดฐานของเส้นโค้งวงรี จุดบนเส้นโค้งที่สร้างกลุ่มย่อยที่มีอันดับจำนวนเฉพาะขนาดใหญ่ n
nอันดับจำนวนเต็มของGหมายความว่าโดยที่คือองค์ประกอบเอกลักษณ์
กุญแจส่วนตัว (เลือกแบบสุ่ม)
กุญแจสาธารณะ(คำนวณโดยใช้เส้นโค้งวงรี)
ข้อความที่จะส่ง

อันดับของจุดฐานต้องเป็นจำนวนเฉพาะอันที่จริง เราสมมติว่าสมาชิกที่ไม่เป็นศูนย์ทุกตัวในริง นั้น สามารถผกผันได้ ดังนั้น จึงต้องเป็นฟิลด์ซึ่งหมายความว่าต้องเป็นจำนวนเฉพาะ (ดูเอกลักษณ์ของเบซูต์ ประกอบ )

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

ในการลงนามข้อความ อลิซต้องทำตามขั้นตอนเหล่านี้:

  1. คำนวณ(ในที่นี้ HASH คือฟังก์ชันแฮชเข้ารหัสลับเช่นSHA-2โดยผลลัพธ์จะถูกแปลงเป็นจำนวนเต็ม)
  2. ให้เป็นบิตซ้ายสุดของโดยที่ คือความ ยาวบิตของลำดับกลุ่ม(โปรดทราบว่าอาจมากกว่าแต่ไม่ยาวกว่า[ 2 ] )
  3. เลือกจำนวนเต็มสุ่มที่มีความปลอดภัยทางด้านการเข้ารหัสจาก ตัวเลือกที่มี อยู่
  4. คำนวณจุดบนเส้นโค้ง
  5. คำนวณ. ถ้าให้กลับไปที่ขั้นตอนที่ 3
  6. คำนวณ. ถ้าให้กลับไปที่ขั้นตอนที่ 3
  7. ลายเซ็นนี้เป็นคู่(และเป็นลายเซ็นที่ถูกต้องตามกฎหมายด้วย)

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

ความล้มเหลวในการใช้งานนี้ถูกนำมาใช้ ตัวอย่างเช่น เพื่อแยกคีย์ลงนามที่ใช้สำหรับเครื่องเล่นเกมPlayStation 3 [ 3 ]

อีกวิธีหนึ่งที่ลายเซ็น ECDSA อาจทำให้คีย์ส่วนตัวรั่วไหลคือเมื่อมีการสร้างโดยตัวสร้างเลขสุ่มที่ ผิดพลาด ความล้มเหลวในการสร้างเลขสุ่มดังกล่าวทำให้ผู้ใช้ Android Bitcoin Wallet สูญเสียเงินในเดือนสิงหาคม 2556 [ 4 ]

เพื่อให้แน่ใจว่าเป็นเอกลักษณ์สำหรับแต่ละข้อความ อาจข้ามการสร้างหมายเลขสุ่มไปโดยสิ้นเชิงและสร้างลายเซ็นแบบกำหนดได้โดยการอนุมานจากทั้งข้อความและคีย์ส่วนตัว[ 5 ]

อัลกอริทึมการตรวจสอบลายเซ็น

เพื่อให้บ็อบตรวจสอบความถูกต้องของลายเซ็นของอลิซในข้อความได้เขาต้องมีสำเนาจุดโค้งกุญแจสาธารณะของเธอบ็อบสามารถตรวจสอบได้ว่าจุดโค้งนั้นถูกต้องหรือไม่ดังนี้:

  1. ตรวจสอบว่าไม่เท่ากับองค์ประกอบเอกลักษณ์Oและพิกัดของมันถูกต้องตามข้อกำหนดอื่นๆ
  2. ตรวจสอบว่าเส้นนั้นอยู่บนเส้นโค้งหรือไม่
  3. ตรวจสอบดูสิ

หลังจากนั้น บ็อบก็ทำตามขั้นตอนต่อไปนี้:

  1. ตรวจสอบว่าrและsเป็นจำนวนเต็มในถ้าไม่ใช่ ลายเซ็นจะไม่ถูกต้อง
  2. คำนวณโดยที่ HASH คือฟังก์ชันเดียวกันกับที่ใช้ในการสร้างลายเซ็น
  3. ให้เป็น บิต ซ้ายสุดของe
  4. คำนวณและ.
  5. คำนวณจุดบนเส้นโค้งถ้าเป็นเช่นนั้น ลายเซ็นจะไม่ถูกต้อง
  6. ลายเซ็นจะถูกต้องหาก... มิเช่นนั้นจะไม่ถูกต้อง

โปรดทราบว่าการใช้งานที่มีประสิทธิภาพจะคำนวณค่าผกผันเพียงครั้งเดียวเท่านั้น นอกจากนี้ การใช้เทคนิคของ Shamir ยังสามารถคำนวณผลรวมของการคูณสเกลาร์สองครั้งได้เร็วกว่าการคูณสเกลาร์สองครั้งที่ทำแยกกัน[ 6 ]

ความถูกต้องของอัลกอริทึม

อาจไม่ใช่เรื่องชัดเจนในทันทีว่าเหตุใดการตรวจสอบจึงทำงานได้อย่างถูกต้อง เพื่อให้เข้าใจเหตุผล ให้กำหนดให้C เป็น จุดบนเส้นโค้งที่คำนวณได้ในขั้นตอนที่ 5 ของการตรวจสอบ

จากนิยามของกุญแจสาธารณะดังนี้

เนื่องจากการคูณสเกลาร์บนเส้นโค้งวงรีสามารถกระจายได้เมื่อเทียบกับการบวก

ขยายความหมายของและจากขั้นตอนการตรวจสอบที่ 4

การรวบรวมคำศัพท์ทั่วไป

ขยายความหมายของsจากขั้นตอนการลงนามขั้นตอนที่ 6

เนื่องจากตัวผกผันของตัวผกผันคือตัวเดิม และผลคูณของตัวผกผันของตัวนั้นกับตัวเดิมคือเอกลักษณ์ ดังนั้นเราจึงเหลือเพียง

จากนิยามของrนี่คือขั้นตอนการตรวจสอบข้อที่ 6

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

การกู้คืนคีย์สาธารณะ

เมื่อได้รับข้อความmและลายเซ็นของอลิซในข้อความนั้น บ็อบสามารถ (อาจจะ) กู้คืนคีย์สาธารณะของอลิซได้: [ 7 ]

  1. ตรวจสอบว่าrและsเป็นจำนวนเต็มในถ้าไม่ใช่ ลายเซ็นจะไม่ถูกต้อง
  2. คำนวณจุดบนเส้นโค้งที่เป็นหนึ่งในค่า, , ฯลฯ (โดยที่ไม่ใหญ่เกินไปสำหรับขอบเขตของเส้นโค้ง) และเป็นค่าที่ทำให้สมการของเส้นโค้งเป็นจริง โปรดทราบว่าอาจมีจุดบนเส้นโค้งหลายจุดที่ตรงตามเงื่อนไขเหล่านี้ และ ค่า R ที่แตกต่างกันแต่ละค่าจะ ส่งผลให้ได้รหัสที่กู้คืนได้แตกต่างกัน
  3. คำนวณโดยที่ HASH คือฟังก์ชันเดียวกันกับที่ใช้ในการสร้างลายเซ็น
  4. ให้zเป็นบิตซ้ายสุดของe
  5. คำนวณและ.
  6. คำนวณจุดบนเส้นโค้ง
  7. ลายเซ็นจะถูกต้องก็ต่อเมื่อตรงกับกุญแจสาธารณะของอลิซ
  8. ลายเซ็นจะไม่ถูกต้องหากได้ลองใช้ค่าR ที่เป็นไปได้ทั้งหมดแล้ว และไม่มีค่าใดตรงกับกุญแจสาธารณะของอลิซ

โปรดทราบว่าลายเซ็นที่ไม่ถูกต้อง หรือลายเซ็นจากข้อความอื่น จะส่งผลให้ได้คีย์สาธารณะที่ไม่ถูกต้อง อัลกอริทึมการกู้คืนสามารถใช้ตรวจสอบความถูกต้องของลายเซ็นได้ก็ต่อเมื่อทราบคีย์สาธารณะของผู้ลงนาม (หรือแฮชของคีย์นั้น) ล่วงหน้าเท่านั้น

ความถูกต้องของอัลกอริทึมการกู้คืน

เริ่มต้นด้วยคำจำกัดความจากขั้นตอนการฟื้นฟูข้อที่ 6

จากคำจำกัดความในขั้นตอนการลงนามข้อที่ 4

เนื่องจากการคูณสเกลาร์บนเส้นโค้งวงรีสามารถกระจายได้เมื่อเทียบกับการบวก

ขยายความหมายของ ขั้น ตอนการฟื้นฟูขั้นที่ 5

ขยายความหมายของsจากขั้นตอนการลงนามขั้นตอนที่ 6

เนื่องจากผลคูณของตัวผกผันขององค์ประกอบและองค์ประกอบนั้นคือเอกลักษณ์ ดังนั้นเราจึงเหลือเพียง

พจน์แรกและพจน์ที่สองหักล้างกันเอง

จากนิยามนี้นี่คือคีย์สาธารณะของอลิซ

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

ความปลอดภัย

ในเดือนธันวาคม พ.ศ. 2553 กลุ่มที่เรียกตัวเองว่าfail0verflowได้ประกาศการกู้คืนคีย์ส่วนตัว ECDSA ที่Sony ใช้ ในการลงนามซอฟต์แวร์สำหรับ เครื่องเล่นเกม PlayStation 3อย่างไรก็ตาม การโจมตีนี้ได้ผลก็ต่อเมื่อ Sony ไม่ได้นำอัลกอริทึมไปใช้อย่างถูกต้อง เนื่องจากเป็นแบบคงที่แทนที่จะเป็นแบบสุ่ม ดังที่ได้ชี้ให้เห็นใน ส่วน อัลกอริทึมการสร้างลายเซ็นข้างต้น ทำให้สามารถแก้ไขได้ ส่งผลให้อัลกอริทึมทั้งหมดไร้ประโยชน์[ 8 ]

เมื่อวันที่ 29 มีนาคม พ.ศ. 2554 นักวิจัยสองคนได้ตีพิมพ์เอกสารIACR [ 9 ]ซึ่งแสดงให้เห็นว่าสามารถดึงคีย์ส่วนตัว TLS ของเซิร์ฟเวอร์โดยใช้OpenSSLที่ตรวจสอบความถูกต้องด้วย Elliptic Curves DSA ผ่านฟิลด์ ไบนารี โดยใช้การโจมตีแบบจับเวลาได้ [ 10 ] ช่องโหว่นี้ได้รับการแก้ไขใน OpenSSL 1.0.0f [ 11 ]

ในเดือนสิงหาคม พ.ศ. 2556 มีการเปิดเผยว่าข้อบกพร่องในการใช้งานคลาสSecureRandom ของ Javaบางส่วนบางครั้งทำให้เกิดการชนกันของค่า ซึ่งทำให้แฮกเกอร์สามารถกู้คืนคีย์ส่วนตัวได้ ทำให้พวกเขามีอำนาจควบคุมธุรกรรม Bitcoin เช่นเดียวกับเจ้าของคีย์ที่ถูกต้อง โดยใช้ช่องโหว่เดียวกันกับที่ใช้ในการเปิดเผยคีย์ลงนาม PS3 ใน การใช้งานแอป Android บาง แอป ซึ่งใช้ Java และอาศัย ECDSA ในการตรวจสอบความถูกต้องของธุรกรรม[ 12 ]

ปัญหานี้สามารถป้องกันได้โดยการสร้างค่า k อย่างเป็นระบบตามที่อธิบายไว้ใน RFC 6979

ข้อกังวล

ข้อกังวลบางประการเกี่ยวกับ ECDSA:

  1. ข้อกังวลทางการเมือง : ความน่าเชื่อถือของ เส้นโค้งที่ผลิตโดย NISTถูกตั้งคำถามหลังจากมีการเปิดเผยว่าNSAจงใจแทรกช่องโหว่เข้าไปในซอฟต์แวร์ ส่วนประกอบฮาร์ดแวร์ และมาตรฐานที่เผยแพร่ นักเข้ารหัสลับที่มีชื่อเสียง[ 13 ]ได้แสดง[ 14 ] [ 15 ]ข้อสงสัยเกี่ยวกับวิธีการออกแบบเส้นโค้ง NIST และการปนเปื้อนโดยสมัครใจได้รับการพิสูจน์แล้วในอดีต[ 16 ] [ 17 ] (ดูบทนำ ของเส้นโค้ง libssh curve25519ด้วย[ 18 ] ) อย่างไรก็ตาม ยังไม่มีหลักฐานว่าเส้นโค้ง NIST ที่กล่าวถึงนั้นใช้ประโยชน์จากจุดอ่อนที่หายาก
  2. ข้อกังวลทางเทคนิค : ความยากลำบากในการนำมาตรฐานไปใช้อย่างถูกต้อง ความช้า และข้อบกพร่องในการออกแบบซึ่งลดความปลอดภัยในการนำไปใช้ที่ไม่ป้องกันเพียงพอ[ 19 ]

การนำไปใช้

ด้านล่างนี้คือรายชื่อไลบรารีการเข้ารหัสที่รองรับ ECDSA:

ดูเพิ่มเติม

อ่านเพิ่มเติม

  • คณะกรรมการมาตรฐานที่ได้รับการรับรองX9 ( ASC X9) ออกมาตรฐานใหม่สำหรับการเข้ารหัสแบบกุญแจสาธารณะ/ECDSAเมื่อวันที่ 6 ตุลาคม 2020 แหล่งที่มา
  • คณะกรรมการมาตรฐานที่ได้รับการรับรองX9 , มาตรฐานแห่งชาติอเมริกัน X9.62-2005, การเข้ารหัสแบบกุญแจสาธารณะสำหรับอุตสาหกรรมบริการทางการเงิน, อัลกอริทึมลายเซ็นดิจิทัลแบบเส้นโค้งวงรี (ECDSA) , 16 พฤศจิกายน 2005
  • Certicom Research, มาตรฐานสำหรับการเข้ารหัสที่มีประสิทธิภาพ, SEC 1: การเข้ารหัสด้วยเส้นโค้งวงรี , เวอร์ชัน 2.0, 21 พฤษภาคม 2552
  • López, J. และ Dahab, R. ภาพรวมของการเข้ารหัสด้วยเส้นโค้งวงรี , รายงานทางเทคนิค IC-00-10, มหาวิทยาลัยแห่งรัฐคัมปินาส, 2000.
  • Daniel J. Bernstein , อัลกอริทึมการยกกำลังของ Pippenger , 2002
  • Daniel RL Brown, Generic Groups, Collision Resistance, and ECDSA , Designs, Codes and Cryptography, 35 , 119–152, 2005. ePrint version
  • Ian F. Blake, Gadiel Seroussi และNigel Smartบรรณาธิการ, Advances in Elliptic Curve Cryptography , London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005
  • Hankerson, D.; Vanstone, S. ; Menezes, A. (2004). คู่มือการเข้ารหัสด้วยเส้นโค้งวงรี . Springer Professional Computing. นิวยอร์ก: Springer . doi : 10.1007/b97644 . ISBN 0-387-95273-XS2CID 720546 ​
  • มาตรฐานลายเซ็นดิจิทัล; รวมถึงข้อมูลเกี่ยวกับ ECDSA
  • อัลกอริทึมลายเซ็นดิจิทัลแบบเส้นโค้งวงรี (ECDSA); ให้คำแนะนำเชิงลึกเกี่ยวกับ ECDSAลิงก์Wayback
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Elliptic_Curve_Digital_Signature_Algorithm&oldid=1359160176 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ อัลกอริทึมลายเซ็นดิจิทัลเส้นโค้งวงรี

ในด้านการเข้ารหัสลับอั ลก อริทึมลายเซ็นดิจิทัลแบบเส้นโค้งวงรี ( ECDSA ) เป็นรูปแบบหนึ่งของอัลกอริทึมลายเซ็นดิจิทัล (DSA) ซึ่งใช้ การเข้ารหัส ลับ แบบเส้นโค้งวงรี

ขนาดกุญแจและลายเซ็น

เช่นเดียวกับการเข้ารหัสแบบวงรีโดยทั่วไป ขนาด บิต ของ คีย์ส่วนตัว ที่เชื่อว่าจำเป็นสำหรับ ECDSA นั้นมีขนาดประมาณสองเท่าของ ระดับความปลอดภัย ในหน่วยบิต [ 1 ] ตัวอย่างเช่น ที่ระดับความปลอดภัย 80 บิต...

อัลกอริทึมการสร้างลายเซ็น

สมมติว่า อลิซ ต้องการส่งข้อความที่ลงชื่อแล้วไปให้ บ็อบ ในขั้นต้น พวกเขาต้องตกลงกันเกี่ยวกับพารามิเตอร์ของเส้นโค้งนอกจาก ฟิลด์ และสมการของเส้นโค้งแล้ว เรายังต้องการจุดฐานที่มีอันดับเฉพาะบนเส้นโค้งด้วย โดยที่ คืออันดับการบวกของจุดนั้น ( เส้นโค้ง , จี , n )...

อัลกอริทึมการตรวจสอบลายเซ็น

เพื่อให้บ็อบตรวจสอบความถูกต้องของลายเซ็นของอลิซในข้อความได้เขาต้องมีสำเนาจุดโค้งกุญแจสาธารณะของเธอบ็อบสามารถตรวจสอบได้ว่าจุดโค้งนั้นถูกต้องหรือไม่ดังนี้: ร , ส {\displaystyle r,s} ม {\displaystyle m} คิว เอ {\displaystyle Q_{A}} คิว เอ {\displaystyle Q_{A}}