Kriptografi Kurva Eliptik

Kriptografi kurva eliptik (ECC) mewujudkan skema kunci publik di atas grup titik-titik pada kurva eliptik, mencapai keamanan yang sama dengan RSA atau Diffie-Hellman medan hingga dengan kunci yang jauh lebih kecil.

Definition

Kriptografi kurva eliptik adalah kriptografi kunci publik yang grup dasarnya adalah himpunan titik-titik pada kurva eliptik di atas medan hingga, dengan keamanan berdasarkan kesulitan masalah logaritma diskrit kurva eliptik.

Scope

Topik ini mencakup hukum grup kurva eliptik di atas medan hingga, masalah logaritma diskrit kurva eliptik, dan skema yang dibangun di atasnya: Diffie-Hellman kurva eliptik (ECDH), skema tanda tangan ECDSA dan EdDSA, serta kurva modern seperti Curve25519. Ini membahas mengapa logaritma diskrit kurva eliptik lebih sulit daripada logaritma diskrit medan hingga (tidak ada kalkulus indeks subeksponensial) dan masalah implementasi seperti penggunaan kembali nonce di ECDSA. Ini tidak termasuk RSA dan skema logaritma diskrit medan hingga yang dibahas dalam topik terkait.

Core questions

• Bagaimana penjumlahan geometris titik-titik pada kurva eliptik membentuk grup kriptografi?
• Mengapa logaritma diskrit kurva eliptik lebih sulit daripada analog medan hingga, memungkinkan kunci yang lebih kecil?
• Bagaimana Diffie-Hellman dan tanda tangan digital diinstansiasi di atas kurva eliptik?
• Apa yang membuat kurva modern seperti Curve25519 lebih aman untuk diimplementasikan daripada kurva NIST yang lebih lama?
• Mengapa keunikan nonce per tanda tangan sangat penting dalam ECDSA?

Key concepts

• hukum grup kurva eliptik
• perkalian skalar
• masalah logaritma diskrit kurva eliptik
• ECDH
• ECDSA
• EdDSA dan Ed25519
• Curve25519
• kerentanan penggunaan kembali nonce
• ukuran kunci vs RSA

Key theories

Masalah logaritma diskrit kurva eliptik

Mengingat titik P dan Q = kP pada kurva, memulihkan skalar k diyakini membutuhkan upaya eksponensial penuh untuk kurva yang dipilih dengan baik, karena serangan kalkulus indeks yang melemahkan logaritma diskrit medan hingga tidak berlaku.

Kunci yang lebih kecil untuk keamanan yang setara

Karena serangan terbaik pada logaritma diskrit kurva eliptik adalah algoritma akar kuadrat generik, kurva eliptik 256-bit memberikan keamanan sekitar 128-bit — sebanding dengan RSA 3072-bit — menghasilkan operasi yang lebih cepat serta kunci dan tanda tangan yang lebih kecil.

Mechanisms

Titik-titik pada kurva eliptik di atas medan hingga membentuk grup abelian di bawah hukum penjumlahan geometris; berulang kali menambahkan titik dasar P ke dirinya sendiri k kali (perkalian skalar, kP) adalah efisien, tetapi memulihkan k dari kP adalah masalah yang sulit. ECDH melakukan Diffie-Hellman dengan menukar kelipatan skalar dari titik dasar; ECDSA dan EdDSA menghasilkan tanda tangan dari skalar per pesan (nonce) — yang, jika diulang atau dapat diprediksi, membocorkan kunci privat, seperti yang ditunjukkan oleh beberapa pelanggaran nyata.

Clinical relevance

ECC adalah pilihan kunci publik standar untuk sistem baru: ECDHE menyediakan pertukaran kunci rahasia ke depan di TLS 1.3, Ed25519 menandatangani kunci SSH, pembaruan perangkat lunak, dan sertifikat, dan Curve25519 mengamankan Signal, WireGuard, dan pesan modern. Kuncinya yang kecil dan operasi yang cepat membuatnya sangat cocok untuk perangkat seluler, kartu pintar, dan perangkat keras IoT yang terbatas.

Evidence & guidelines

ECDSA distandarisasi dalam FIPS 186, ECDH dalam NIST SP 800-56A, dan EdDSA/Ed25519 dalam RFC 8032; Curve25519/X25519 dalam RFC 7748. Praktik modern lebih menyukai kurva Edwards dan X25519 karena ketahanannya terhadap jebakan implementasi. Kegagalan ECDSA ketika nonce digunakan kembali (terutama ekstraksi kunci Sony PlayStation 3 tahun 2010) adalah contoh standar yang patut dicatat.

History

Neal Koblitz dan Victor Miller secara independen mengusulkan penggunaan kurva eliptik untuk kriptografi pada tahun 1985-1987. Adopsi awalnya lambat karena masalah paten dan kepercayaan serta kompleksitas kurva NIST, tetapi ECC menjadi dominan pada tahun 2010-an karena efisiensi ukuran kunci menjadi lebih penting dan Curve25519 (2006) dan Ed25519 dari Bernstein menawarkan desain yang cepat dan tahan penyalahgunaan yang kini banyak digunakan.

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

Mengapa kunci kurva eliptik 256-bit setara dengan kunci RSA 3072-bit?

Serangan terbaik yang diketahui pada logaritma diskrit kurva eliptik bersifat generik dan membutuhkan waktu sekitar akar kuadrat dari ukuran grup, sedangkan faktorisasi dan logaritma diskrit medan hingga memiliki algoritma subeksponensial yang lebih cepat. Jadi kurva eliptik membutuhkan bit yang jauh lebih sedikit untuk tingkat keamanan yang sama.

Apakah kurva eliptik NIST dapat dipercaya?

Kurva P-standar NIST banyak digunakan dan tidak diketahui telah rusak, tetapi pilihan konstanta yang tidak dijelaskan dan kesulitan implementasinya menyebabkan banyak orang lebih memilih Curve25519 dan Ed25519, yang memiliki dasar desain yang transparan dan lebih mudah diimplementasikan dengan aman dalam waktu konstan.