Pertukaran kunci Diffie-Hellman dijelaskan

Selama ribuan tahun, mengirim pesan rahasia berarti terlebih dahulu berbagi kunci rahasia secara langsung atau melalui kurir. Pada tahun 1976 dua peneliti di Stanford menunjukkan bahwa dua pihak dapat menciptakan kunci bersama dari ketiadaan, dengan bertukar pesan di depan mata siapa pun. Gagasan ini membuka era kriptografi kunci publik dan masih bekerja setiap kali browser menampilkan ikon gembok.

Alice dan Bob di kedua sisi saluran publik, masing-masing mencampur cat kuning bersama dengan warna rahasia, keduanya berakhir dengan campuran yang sama sementara Eve mengamati
Alice dan Bob di kedua sisi saluran publik, masing-masing mencampur cat kuning bersama dengan warna rahasia, keduanya berakhir dengan campuran yang sama sementara Eve mengamati

Masalah distribusi kunci

Sandi seperti AES hanya seaman kuncinya, dan kedua pihak memerlukan kunci yang sama. Sebelum 1976 kunci harus diantarkan secara rahasia: lewat kantong diplomatik, kurir tepercaya, atau buku kode yang dicetak sebelumnya. Bagi dua orang asing yang ingin berbicara dengan aman saat ini juga, misalnya sebuah toko dan pelanggan di internet, hal itu mustahil. Makalah Whitfield Diffie dan Martin Hellman, New Directions in Cryptography, memecahkan masalah ini dengan metode yang sama sekali tidak memerlukan rahasia sebelumnya.

Aritmetika pada jam

Pertukaran ini menggunakan aritmetika modular: perhitungan pada jam dengan p jam, dengan p sebuah bilangan prima besar. Pangkat-pangkat pada jam ini berperilaku dengan cara yang luar biasa. Jika g adalah akar primitif, bilangan g, g², g³, … mod p melompat-lompat dan mengunjungi setiap jam dari 1 sampai p − 1 sebelum berulang, dalam urutan yang tampak acak. Menghitung gᵃ mod p itu cepat, dengan kira-kira sebanyak perkalian dengan jumlah digit biner a. Membaliknya tidak.

Pertukaran langkah demi langkah

Alice dan Bob secara terbuka menyepakati p dan g. Alice memilih rahasia a dan mengirim A = gᵃ mod p; Bob memilih rahasia b dan mengirim B = gᵇ mod p. Alice menghitung Bᵃ = (gᵇ)ᵃ dan Bob menghitung Aᵇ = (gᵃ)ᵇ, keduanya mod p. Karena urutan eksponen tidak penting, keduanya mendapat g^(ab) mod p. Dengan contoh kecil klasik p = 23, g = 5, a = 6, dan b = 15, Alice mengirim 8, Bob mengirim 19, dan keduanya sampai pada rahasia bersama 2.

Masalah logaritma diskret

Eve melihat p, g, A, dan B. Jika ia bisa menemukan a dari A = gᵃ mod p, ia bisa menghitung rahasianya persis seperti Alice. Inilah masalah logaritma diskret. Algoritma klasik terbaik yang diketahui, seperti saringan medan bilangan (number field sieve), jauh lebih cepat daripada mencoba setiap eksponen tetapi tetap memerlukan waktu yang tumbuh lebih cepat daripada pangkat berapa pun dari jumlah digit. Dengan bilangan prima 2048 bit, masalah ini di luar jangkauan komputer mana pun yang ada. Apakah ada cara yang lebih cepat tidak diketahui, dan keamanan pertukaran ini bertumpu pada keyakinan tersebut.

Man-in-the-middle

Diffie-Hellman melindungi dari penyadap, tetapi tidak dari penipu yang menyamar. Mallory, yang berada di antara Alice dan Bob, dapat menjalankan satu pertukaran dengan masing-masing dari mereka dan meneruskan pesan, sambil membaca semuanya. Pertahanannya adalah autentikasi: dalam HTTPS server menandatangani bagiannya dalam pertukaran dengan kunci yang disertifikasi oleh otoritas tepercaya, sehingga browser tahu bahwa ia benar-benar berbicara dengan situs yang tepat. Pertukaran kunci dan tanda tangan selalu berjalan bersama.

Siapa penemunya?

Diffie dan Hellman menerbitkannya pada tahun 1976, dengan membangun di atas gagasan Ralph Merkle, yang kemudian diminta Hellman untuk ikut dicantumkan. Pada tahun 1997 badan intelijen Inggris GCHQ mengungkapkan bahwa para matematikawannya telah sampai di sana lebih dulu: James Ellis memiliki gagasan kriptografi kunci publik pada tahun 1970, Clifford Cocks menemukan sistem mirip RSA pada tahun 1973, dan Malcolm Williamson menemukan pertukaran kunci yang sama pada tahun 1974, semuanya dirahasiakan selama lebih dari dua puluh tahun.

Martin Hellman (kiri) dan Whitfield Diffie (kanan), 1977
Martin Hellman (kiri) dan Whitfield Diffie (kanan), 1977
Ralph Merkle di Singularity Summit tahun 2007.
Ralph Merkle di Singularity Summit tahun 2007.

Diffie-Hellman saat ini

Koneksi modern sebagian besar menggunakan Diffie-Hellman kurva eliptik, yang memberikan keamanan yang sama dengan bilangan yang jauh lebih pendek, misalnya kurva X25519 di TLS 1.3, Signal, dan WhatsApp. Menggunakan pasangan rahasia baru untuk setiap koneksi memberikan forward secrecy: meskipun kunci jangka panjang server dicuri kemudian, percakapan masa lalu tetap aman. Parameter yang lemah tetap berbahaya, seperti yang ditunjukkan serangan Logjam tahun 2015 untuk bilangan prima lama 512 bit, dan komputer kuantum besar yang menjalankan algoritma Shor akan membobol baik Diffie-Hellman klasik maupun kurva eliptik, itulah sebabnya pertukaran kunci pascakuantum kini mulai diterapkan berdampingan dengannya.

Jelajahi sendiri

Buka visualisasi Diffie-Hellman untuk mengikuti lima langkah pada papan yang menunjukkan apa yang diketahui Alice, saluran publik, dan Bob, sebagai cat dan sebagai angka. Pilih bilangan prima dari 23 hingga 2.147.483.647, tentukan sendiri rahasianya, dan biarkan Eve menyerang dengan mencoba setiap eksponen: saksikan ia langsung berhasil pada bilangan prima kecil dan lihat bagaimana perkiraan waktu pencarian bertambah seiring makin panjangnya bilangan prima.

Pertanyaan yang sering diajukan

Apakah Diffie-Hellman sama dengan RSA?

Tidak, meskipun keduanya adalah metode kunci publik dari tahun 1970-an. RSA, yang diterbitkan pada tahun 1977, dapat mengenkripsi dan menandatangani dengan kunci publik dan kunci privat serta bertumpu pada sulitnya memfaktorkan bilangan besar. Diffie-Hellman hanya menyepakati rahasia bersama dan bertumpu pada masalah logaritma diskret.

Seberapa besar bilangannya dalam praktik?

Diffie-Hellman klasik menggunakan bilangan prima minimal 2048 bit, sekitar 617 digit desimal, dan sering kali 3072 atau 4096 bit. Versi kurva eliptik menggunakan kunci sekitar 256 bit untuk keamanan yang sebanding.

Mengapa setiap bit tambahan menggandakan pekerjaan Eve?

Bilangan prima dengan satu bit lebih banyak kira-kira dua kali lebih besar, sehingga ada kira-kira dua kali lebih banyak eksponen yang harus dicoba. Serangan sungguhan lebih cerdik daripada mencoba setiap eksponen, tetapi biayanya tetap tumbuh sangat cepat seiring ukuran bilangan prima.

Mengapa Alice dan Bob memerlukan bilangan prima?

Dengan modulus prima, setiap bilangan dari 1 sampai p − 1 memiliki invers dan akar primitif ada, sehingga pangkat-pangkat g mencakup semua kemungkinan. Bilangan prima aman, yaitu yang (p − 1)/2-nya juga prima, sering dipilih untuk menutup jalan pintas yang memanfaatkan faktor kecil dari p − 1.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Buka visualisasi Diffie-Hellman