Kriptografi kunci asimetris

Di pelajaran ini kita akan melihat kriptografi kunci asimetris yang menjadi dasar banyak interaksi jaringan aman yang ada saat ini.

Di akhir pelajaran kita akan sudah membahas:

• Apa itu kriptografi kunci asimetris
• Penggunaan kriptografi kunci asimetris, termasuk pertukaran kunci dan tanda tangan digital
• Keamanan kriptografi kunci asimetris secara umum
• Detail lebih lanjut tentang algoritma RSA, DSA, dan Elliptic Curves serta keamanannya
• Beberapa contoh kode Python yang memperlihatkan cara kerja algoritma secara praktis
• Ancaman terhadap algoritma-algoritma ini dari komputer klasik maupun kuantum

Pengantar kriptografi kunci asimetris

Seperti yang kita pelajari di pelajaran sebelumnya, kriptografi kunci simetris sangat cepat dan efisien untuk melindungi informasi, tapi ada beberapa keterbatasannya:

1. Semakin banyak pihak yang ingin bertukar informasi secara aman, jumlah kunci yang dibutuhkan tumbuh secara kombinatorial. Tidak ada mekanisme untuk mendistribusikan kunci-kunci ini secara aman antara pengirim dan penerima.
2. Tidak ada ketentuan untuk non-repudiation. Semua pihak bisa mendekripsi atau mengenkripsi pesan tanpa cara untuk memastikan pesan telah diterima atau dari mana asalnya.

Solusi untuk kedua masalah ini disediakan oleh kriptografi kunci asimetris (AKC), yang juga dikenal sebagai kriptografi kunci publik (PKC), yang karenanya menjadi fondasi keamanan digital modern.

Kriptografi kunci asimetris (AKC) melibatkan penggunaan sepasang kunci — satu publik, satu privat. Kunci publik dan privat terhubung secara kriptografis dan biasanya dibuat secara bersamaan sebagai pasangan kunci menggunakan algoritma matematis khusus. Kunci publik, seperti namanya, dimaksudkan untuk didistribusikan secara bebas, sementara kunci privat dijaga kerahasiaannya oleh pihak yang membuat pasangan kunci tersebut. Keamanan komunikasi yang menggunakan pasangan kunci asimetris terjamin selama kunci privat tetap rahasia.

Gambar 1. Enkripsi Kunci Asimetris

AKC menawarkan beberapa fungsi berguna, seperti:

1. Enkripsi dan dekripsi untuk mengaktifkan kerahasiaan komunikasi.
2. Tanda tangan digital untuk memastikan keaslian, integritas, dan non-repudiation.
3. Pertukaran kunci yang aman untuk memfasilitasi penggunaan kriptosistem simetris berikutnya.

Dalam aplikasi modern, AKC terutama digunakan untuk tanda tangan digital dan pertukaran kunci yang aman. Di pelajaran ini, kita memperkenalkan dua fungsi kunci ini, lalu kita membahas beberapa variasi protokol kriptografi untuk fungsi-fungsi tersebut.

Pertukaran kunci dengan kriptografi kunci asimetris

Salah satu masalah mendasar dalam kriptografi adalah pertukaran kunci secara aman. Misalnya, jika dua pihak ingin menggunakan enkripsi simetris, keduanya membutuhkan kunci yang sama untuk mengenkripsi dan mendekripsi pesan. Tapi bagaimana mereka menukar kunci itu secara aman? Kriptografi kunci asimetris mengatasi ini melalui mekanisme pertukaran kunci interaktif dan non-interaktif.

Pertukaran kunci interaktif

Protokol pertukaran kunci interaktif mengacu pada metode di mana dua pihak bekerja sama untuk membuat kunci rahasia bersama melalui saluran komunikasi yang tidak aman. Kunci rahasia bersama ini kemudian bisa digunakan untuk tugas enkripsi dan dekripsi simetris.

Yang paling terkenal di antara protokol seperti itu adalah algoritma Diffie-Hellman (DH), yang dirancang khusus untuk memfasilitasi pertukaran kunci. Dalam protokol ini, setiap pihak menghasilkan sepasang kunci (publik dan privat) dan menyiarkan kunci publik mereka. Kemudian setiap pihak menggunakan kunci privat mereka sendiri dan kunci publik pihak lain untuk menghasilkan kunci rahasia bersama. DH menggunakan prinsip aritmatika modular untuk memastikan kedua pihak berakhir dengan rahasia bersama yang sama meskipun setiap pihak hanya memiliki akses ke kunci publik pihak lain.

Kriptosistem modern berbasis kriptografi kurva eliptik (ECC) memperluas konsep ini dengan pertukaran kunci elliptic curve Diffie-Hellman (ECDH). ECDH bekerja mirip dengan DH tapi memanfaatkan sifat-sifat kurva eliptik, menghasilkan sistem yang lebih aman dan efisien.

Gambar 2. Protokol Pertukaran Kunci

Pertukaran kunci non-interaktif

Tidak seperti protokol pertukaran kunci seperti DH dan ECDH, yang bersifat interaktif dan memerlukan komunikasi bolak-balik untuk menentukan kunci simetris, AKC juga menyediakan cara non-interaktif untuk menetapkan kunci rahasia bersama. Dalam skema tersebut, satu pihak menghasilkan sepasang kunci (publik dan privat) dan berbagi kunci publik dengan pihak lain. Pihak kedua ini kemudian menghasilkan kunci simetris acak, mengenkripsinya dengan kunci publik yang diterima, dan mengirimkannya kembali ke pihak pertama. Pihak pertama menggunakan kunci privat mereka untuk mendekripsi pesan yang diterima, sehingga mendapatkan kunci simetris bersama. Skema ini bersifat non-interaktif karena kunci simetris ditentukan oleh satu pihak dan hanya dikomunikasikan secara aman ke pihak lain dalam bentuk terenkripsi.

Pertimbangan penting dalam pertukaran kunci non-interaktif berkaitan dengan perbedaan panjang dalam bit antara kunci simetris yang ingin ditukar oleh para pihak dan ukuran pesan yang direkomendasikan dalam AKC. Biasanya, kunci simetris modern berkisar antara 128-256 bit, sementara kriptosistem kunci asimetris seperti RSA bekerja dengan ukuran pesan sekitar 1024-4096 bit. Oleh karena itu, saat menggunakan AKC untuk mengirimkan kunci simetris, demi keamanan kunci tersebut tetap harus dikodekan ke dalam pesan yang lebih panjang 1024-4096 bit. Ini bisa dicapai melalui dua pendekatan:

• Pertukaran kunci berbasis padding: Dalam pendekatan ini, kunci simetris yang lebih pendek (128-256 bit) dibuat terlebih dahulu lalu skema padding yang dapat dibalik yang telah disepakati seperti OAEP digunakan untuk menyematkannya ke dalam pesan yang lebih panjang (1024-4096 bit). Pesan yang lebih panjang ini dienkripsi menggunakan AKC dan disiarkan sebagai ciphertext. Penerima pertama mendekripsi ciphertext dan kemudian menghapus padding untuk mengekstrak kunci simetris yang lebih pendek.

• Mekanisme enkapsulasi kunci (KEM): Dengan pertukaran kunci berbasis KEM, pesan teks biasa yang panjang (1024-4096 bit) dibuat secara acak terlebih dahulu, dari mana kunci simetris yang lebih pendek (128-256 bit) bisa diekstrak menggunakan fungsi derivasi kunci (KDF) yang telah disepakati. Teks biasa yang lebih panjang dienkripsi menggunakan AKC dan disiarkan ke penerima sebagai ciphertext. Penerima mendekode ciphertext menggunakan kunci privat mereka lalu menggunakan KDF untuk mengekstrak kunci simetris yang lebih pendek (128-256 bit). Kriptosistem populer seperti RSA, dengan kemampuannya untuk mengenkripsi data secara langsung, bisa digunakan untuk mengimplementasikan KEM.

Gambar 3. Mekanisme Enkapsulasi Kunci

Tanda tangan digital dengan kriptografi kunci asimetris

Tanda tangan digital adalah aplikasi lain yang kuat dari kriptografi kunci asimetris. Mereka memberikan autentikasi, integritas, dan non-repudiation yang dimungkinkan oleh fakta bahwa dalam AKC, entitas memiliki kunci privat yang unik. Ide dasar yang mendasari protokol tanda tangan adalah bahwa pengirim pesan aman akan secara tambahan menandatangani secara digital pesan menggunakan kunci privat unik mereka. Penerima kemudian akan memverifikasi tanda tangan digital menggunakan kunci publik pengirim. Dalam AKC, tanda tangan digital bisa diimplementasikan dengan menggunakan algoritma yang dirancang khusus untuk tujuan tersebut atau dengan menggunakan kriptosistem generik.

Gambar 4. Tanda tangan digital dengan kriptografi kunci asimetris

Algoritma tanda tangan digital yang didedikasikan

Saat ini, Standar Pemrosesan Informasi Federal AS (FIPS) untuk tanda tangan digital adalah skema khusus yang secara sederhana disebut Algoritma Tanda Tangan Digital (DSA). Agak mirip dengan protokol Diffie-Hellman, DSA menggunakan sifat aljabar dari eksponensiasi modular dan invers multiplikatif untuk pembuatan dan verifikasi tanda tangan.

Algoritma tanda tangan digital kurva eliptik (ECDSA) adalah varian ECC dari DSA, menyediakan fungsionalitas yang sama tapi dengan kunci yang jauh lebih pendek. Ini menghasilkan peningkatan efisiensi, menjadikannya pilihan populer untuk sistem dengan kendala sumber daya.

DSA dan ECDSA akan diilustrasikan lebih rinci nanti.

Skema tanda tangan digital menggunakan kriptosistem generik

Selain algoritma yang didedikasikan, tanda tangan digital juga bisa dibuat menggunakan kriptosistem asimetris generik, seperti RSA.

RSA, yang akan dibahas secara rinci di bagian selanjutnya, juga memanfaatkan invers multiplikatif modular dan eksponensiasi modular sebagai operasi dasar tapi menggabungkannya dalam urutan yang berbeda dari DSA. Dalam RSA, penanda tangan biasanya membuat hash dari pesan lalu mengenkripsi hash dengan kunci privatnya, menciptakan tanda tangan digital. Pihak mana pun kemudian bisa memverifikasi tanda tangan ini dengan mendekripsinya menggunakan kunci publik penanda tangan dan membandingkannya dengan pesan yang di-hash.

Aplikasi kriptografi kunci asimetris

Kriptografi kunci asimetris bersifat ubiquitous dalam aplikasi teknologi digital modern. Fungsionalitas dasar AKC yang dijelaskan di atas membentuk blok bangunan banyak protokol aplikasi tingkat lebih tinggi, termasuk:

1. Komunikasi internet: Komunikasi aman melalui internet, seperti HTTPS, sangat bergantung pada kriptografi kunci asimetris. Transport Layer Security (TLS) dan pendahulunya, Secure Sockets Layer (SSL), menggunakan kriptografi kunci asimetris selama proses handshake awal untuk menetapkan kunci simetris, yang kemudian digunakan untuk sisa sesi komunikasi.

2. Autentikasi: Kriptografi kunci asimetris digunakan untuk membuat tanda tangan digital, memungkinkan suatu entitas mengautentikasi dokumen atau pesan digital sebagai berasal dari pengirim tertentu. Ini digunakan dalam banyak skenario, dari memverifikasi pembaruan perangkat lunak hingga kontrak digital yang mengikat secara hukum.

3. Enkripsi email: Protokol enkripsi email seperti PGP (Pretty Good Privacy) dan alternatif open-source-nya GPG (GNU Privacy Guard) menggunakan kriptografi kunci asimetris untuk memastikan bahwa hanya penerima yang dituju yang bisa membaca isi email.

4. Secure shell (SSH): SSH adalah protokol untuk login jarak jauh yang aman dan layanan jaringan aman lainnya melalui jaringan yang tidak aman. SSH menggunakan kriptografi kunci asimetris untuk mengautentikasi server ke klien dan, opsional, klien ke server.

5. VPN (virtual private network): Enkripsi kunci asimetris digunakan untuk menetapkan koneksi aman dalam VPN, memastikan komunikasi aman melalui jaringan publik.

6. Blockchain dan mata uang kripto: Teknologi blockchain, termasuk Bitcoin dan Ethereum, menggunakan kriptografi kunci asimetris. Misalnya, kepemilikan Bitcoin ditetapkan melalui tanda tangan digital menggunakan kriptografi kunci asimetris.

7. Otoritas sertifikat: Kriptografi kunci asimetris digunakan oleh otoritas sertifikat (CA) untuk menerbitkan dan menandatangani sertifikat digital, yang digunakan dalam komunikasi TLS, penandatanganan kode, enkripsi email, dan lainnya. Sertifikat digital mengikat kunci publik ke entitas tertentu (misalnya, seseorang atau server).

Gambar 5. Menerbitkan dan menandatangani sertifikat digital menggunakan kriptografi kunci asimetris

Keamanan kriptografi kunci asimetris

Beberapa konsep kriptografi bersatu untuk mengaktifkan kriptografi kunci asimetris yang aman, termasuk:

Kerahasiaan kunci privat: Persyaratan keamanan paling dasar dari AKC adalah bahwa kunci privat tetap rahasia. Namun, karena kunci privat harus terhubung secara matematis dengan kunci publik, kerahasiaan kunci privat juga mengharuskan bahwa tidak mungkin secara komputasi untuk menurunkan kunci privat dari pengetahuan kunci publik. Skema pembuatan kunci dalam AKC mengandalkan masalah matematis yang sulit secara komputasi untuk memfasilitasi persyaratan ini.

Fungsionalitas trapdoor Dalam AKC, operasi enkripsi dan dekripsi melibatkan kunci komplementer yang berbeda dari satu pasangan kunci. Ciphertext yang dihasilkan oleh enkripsi menggunakan salah satu kunci (misalnya kunci publik) harus tidak terbaca oleh pihak ketiga sementara mudah didekripsi oleh pemegang kunci komplementer (dalam hal ini kunci privat). Dengan kata lain, enkripsi harus menyerupai sebuah fungsi satu arah trapdoor sedemikian rupa sehingga pihak ketiga tidak bisa membalik operasi dan memulihkan teks biasa tapi kunci privat menyediakan trapdoor rahasia yang memungkinkan inversi yang mudah. Algoritma AKC populer menggunakan eksponensiasi modular untuk menyiapkan perilaku fungsi satu arah trapdoor.

Keacakan: Proses pembuatan kunci juga harus memanfaatkan keacakan untuk memastikan bahwa kunci tidak dapat diprediksi, karena pola atau prediktabilitas apa pun dalam pembuatan kunci bisa dieksploitasi oleh penyerang. Keacakan juga digunakan untuk padding selama enkripsi untuk menghasilkan ciphertext yang aman secara semantis dan dalam skema tanda tangan digital untuk menghasilkan tanda tangan unik bahkan ketika pesan yang sama ditandatangani beberapa kali. Untuk alasan ini, penggunaan generator angka acak yang kuat adalah bagian penting dari AKC.

Ukuran kunci besar: Seperti halnya SKC, ukuran kunci yang besar memastikan perlindungan terhadap serangan brute force. Namun, karena ukuran kunci yang besar juga meningkatkan biaya komputasi proses enkripsi dan dekripsi, solusi optimal perlu menyeimbangkan pertimbangan keamanan dan efisiensi. Tabel berikut menunjukkan ukuran kunci tipikal untuk berbagai protokol dan aplikasi kriptografi kunci asimetris:

Protokol	Ukuran Kunci Tipikal (dalam bit)	Aplikasi
RSA	1024 (usang), 2048, 3072, 4096	Enkripsi, tanda tangan digital
DSA	1024 (usang), 2048, 3072	Tanda tangan digital
DH	2048, 3072, 4096	Pertukaran kunci
ECDH	224, 256, 384, 521	Pertukaran kunci
ECDSA	224, 256, 384, 521	Tanda tangan digital

Infrastruktur kunci publik: Dalam AKC, kunci privat harus dijaga kerahasiaannya oleh pemilik sementara kunci publik dibagikan. Harus ada mekanisme aman untuk mengelola dan mendistribusikan kunci publik ini antar pengguna. Infrastruktur kunci publik (PKI) menyediakan cara untuk melakukan ini menggunakan sertifikat digital. Sertifikat digital memberikan bukti identitas pemilik kunci publik dan diterbitkan oleh otoritas tepercaya seperti otoritas sertifikat (yang merupakan bagian dari PKI). Karenanya, PKI memainkan peran integral dalam keamanan aplikasi modern yang menggunakan AKC dengan memungkinkan manajemen kunci berskala besar (dengan membuat, mengelola, mendistribusikan, dan mencabut sertifikat digital).

Risiko keamanan terhadap kriptografi kunci asimetris

Seperti yang diuraikan dalam tabel di atas, algoritma kunci asimetris modern seperti RSA biasanya menggunakan ukuran kunci yang jauh lebih besar daripada pasangan kunci simetris yang umum digunakan seperti AES-128. Bahkan protokol berbasis ECC (ECDH dan ECDSA) yang memiliki ukuran kunci lebih kecil menggunakan minimal setidaknya 224 bit untuk kunci. Ini pada gilirannya menyiratkan bahwa serangan brute force yang melibatkan pencarian menyeluruh di ruang kunci privat untuk mengidentifikasi kunci yang benar tidak dapat dilakukan secara komputasi di masa mendatang. Ini tetap berlaku bahkan jika komputer kuantum digunakan untuk tugas ini. Oleh karena itu, serangan terhadap AKC biasanya berfokus pada mengeksploitasi kelemahan potensial lain dari kriptosistem tertentu. Beberapa mode serangan yang terdokumentasi dengan baik menargetkan:

1. Kelemahan algoritmik dengan menggunakan sarana matematis dan komputasi yang canggih untuk melemahkan asumsi kekerasan yang digunakan untuk merumuskan algoritma kunci asimetris. Misalnya, keamanan RSA didasarkan pada kesulitan memfaktorkan bilangan prima besar, dan kemajuan komputasi terbaru telah memungkinkan faktorisasi kunci RSA 829-bit yang berhasil. Oleh karena itu, RSA 1024-bit saat ini sudah usang. Seperti yang akan dibahas nanti, risiko utama yang ditimbulkan komputer kuantum pada AKC juga masuk dalam kategori ini.

2. Keacakan yang tidak sempurna, yang dapat menyebabkan kelemahan dalam proses pembuatan kunci. Misalnya, jika generator angka acak yang digunakan untuk membuat kunci cacat dan menghasilkan kunci yang tidak benar-benar acak, penyerang mungkin bisa memprediksi kunci tersebut.

3. Cacat implementasi seperti kesalahan dalam implementasi algoritma kriptografi yang secara tidak sengaja mengungkapkan informasi tentang kunci. Misalnya, padding yang salah berpotensi mengungkapkan detail tentang kunci.

4. Side channel yang mengacu pada kebocoran informasi dari sistem fisik yang menjalankan kriptografi. Kebocoran seperti itu bisa berupa informasi waktu, konsumsi daya, atau bahkan suara, yang bisa dieksploitasi dalam apa yang disebut serangan side-channel. Misalnya, menganalisis berapa lama operasi kriptografi membutuhkan waktu untuk dijalankan dapat mengungkapkan jumlah '1' dalam kunci biner. Kebocoran yang tampaknya tidak berbahaya ini secara signifikan mempersempit ruang pencarian, mengungkap solusi potensial untuk masalah yang awalnya tampak tidak dapat diatasi.

5. Pertukaran kunci dengan mencegat kunci saat sedang dipertukarkan, seperti dalam serangan man-in-the-middle (MITM). Protokol DH rentan terhadap serangan MITM jika langkah autentikasi tambahan tidak disertakan.

6. Penyimpanan kunci dengan bertujuan mencuri kunci dari penyimpanan yang tidak aman. Ini termasuk serangan fisik seperti manipulasi atau pencurian perangkat penyimpanan.

Mengamankan kriptosistem kunci asimetris dari berbagai serangan yang mungkin terjadi adalah tugas yang signifikan yang melibatkan pertimbangan matematis, perangkat keras, perangkat lunak, logistis, dan hukum.

RSA

Algoritma RSA (Rivest-Shamir-Adleman) adalah salah satu kriptosistem kunci publik pertama dan banyak digunakan untuk transmisi data yang aman. Ini adalah kriptosistem serbaguna karena menyediakan operasi yang diperlukan untuk mengaktifkan enkripsi, dekripsi, tanda tangan digital, dan pertukaran kunci dalam satu kerangka kerja yang umum.

Di bagian ini, kita akan mengilustrasikan kriptografi kunci asimetris (AKC) menggunakan RSA melalui contoh-contoh sederhana.

Kita akan menggunakan skenario standar dua pihak, Alice dan Bob, yang ingin berkomunikasi secara aman menggunakan AKC.

Algoritma RSA

Algoritma RSA dasar melibatkan empat operasi: pembuatan kunci, distribusi kunci, enkripsi, dan dekripsi:

1. Pembuatan kunci:

   Kunci publik dan privat dibuat berdasarkan prinsip matematis seputar bilangan prima, di mana menghitungnya mudah, tapi kebalikannya sulit.

   Kita akan menyebut ini:

   • Kunci publik: $(e, n)$
   • Kunci privat: $(d, n)$

   Perhatikan bahwa $n$ umum untuk kunci publik dan kunci privat, dan dikenal sebagai modulus. Kita akan perlu menggunakan ini nanti.

Detail matematika

• Pilih dua bilangan prima yang berbeda, $p$ dan $q$.
  • dipilih secara acak (untuk keamanan).
  • Mereka harus berukuran serupa, tapi berbeda panjangnya beberapa digit, untuk mempersulit faktorisasi.
  • Bilangan prima bisa dipilih secara efisien menggunakan uji primalitas.
• Hitung $n = p*q$.
  • $n$ adalah modulus untuk kunci publik dan privat.
• Hitung totient $φ$$(n) = (p-1)*(q-1)$.
  • Totient dimaksudkan untuk dijaga kerahasiaannya dan biasanya dibuang setelah pembuatan kunci.
• Pilih bilangan bulat $e$ sedemikian sehingga $1 < e <$$φ$$(n)$ dan $gcd$$(e,$$φ$$(n)) = 1$.
  • yaitu, $e$ dan $φ$$(n)$ harus koprim.
  • Bilangan $e$ ini membentuk eksponen kunci publik dan biasanya dipilih sebagai bilangan kecil untuk efisiensi komputasi.
  • Bilangan prima $65537 = 2^{16} + 1$ sering digunakan.
  • Hitung $d$ untuk memenuhi relasi kongruensi $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • Yaitu, $d$ adalah invers multiplikatif dari $e$ modulo $φ$$(n)$.
    • Ini lebih efisien dihitung menggunakan algoritma Euclidean yang diperluas.
    • Bilangan $d$ ini adalah eksponen kunci privat.
• Kunci publik terdiri dari $(e, n)$, dan kunci privat adalah $(d, n)$.

2. Distribusi kunci:

   • Kunci publik $(e, n)$ dipublikasikan ke mereka yang mungkin ingin mengirim pesan
   • Kunci privat $(d, n)$ dijaga kerahasiaannya.

3. Enkripsi:

   • Alice ingin mengirim pesan $M$ ke Bob. Dalam hal ini bilangan bulat sederhana
   • Alice menggunakan kunci publik Bob $(e, n)$ untuk mengenkripsi pesan menjadi ciphertext $C$

   Detail matematika

   • $M$ adalah bilangan bulat $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, di mana $C$ adalah ciphertext.

4. Dekripsi:

   • Bob menerima ciphertext $C$
   • Bob menggunakan kunci privatnya $(d, n)$ untuk mendekripsi pesan kembali menjadi pesan $M$

   Detail matematika

   • $M ≡ C^d (mod n)$.

Ini adalah garis besar dasar RSA. Dalam praktiknya, skema padding yang lebih canggih diterapkan pada teks biasa $M$ sebelum enkripsi untuk memastikan bahwa teks biasa yang sama menghasilkan ciphertext yang berbeda. Ini mencegah berbagai kemungkinan serangan terhadap implementasi RSA yang naif dan memungkinkan keamanan semantis.

Ilustrasi RSA dalam Python

Dalam sel kode berikut, kita mengilustrasikan contoh sederhana algoritma RSA menggunakan bilangan bulat kecil dan kemudian mendemonstrasikan distribusi kunci praktis dan aplikasi tanda tangan digital menggunakan pustaka Python yang mengimplementasikan RSA.

catatan

Catatan: Di bagian ini kita akan menampilkan perhitungan matematika secara detail sebagai bagian dari kode Python

Pembuatan kunci RSA

Mari kita telusuri contoh sederhana algoritma RSA menggunakan bilangan prima kecil.

Kita perlu bisa menghitung pembagi bersama terbesar dari dua bilangan bulat, karena itu akan diperlukan untuk menguji apakah dua bilangan bulat bersifat koprim.

Kita akan menjelaskan satu cara sederhana untuk menghitung ini, tapi jauh lebih efisien dengan bilangan bulat yang lebih besar untuk menggunakan fungsi python math.gcd.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

Fase pertama alur kerja RSA adalah pembuatan kunci. Ini dimulai dengan memilih dua bilangan prima, yang dimaksudkan untuk dijaga kerahasiaannya oleh entitas yang membuat kunci.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Selanjutnya, modulus $n$, yang merupakan hasil kali dari dua prima yang dipilih, dihitung. Modulus ini akan dipublikasikan sebagai bagian dari kunci publik.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

Fungsi totient Euler $\varphi(n)$ dihitung berikutnya, karena diperlukan untuk operasi invers multiplikatif modular yang digunakan untuk menentukan kunci dalam RSA. $phi$ juga dijaga kerahasiaannya dan biasanya dibuang setelah pembuatan kunci.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Kita sekarang siap untuk menghitung kunci publik dan privat. Dalam RSA, masing-masing ditentukan oleh tuple dua bilangan bulat. Entri pertama dalam setiap tuple adalah bilangan bulat yang berbeda, dan entri kedua adalah modulus $n$ yang umum untuk kedua kunci.

Entri pertama dalam kunci publik bisa berupa bilangan bulat apa pun yang lebih besar dari 1 yang koprim dengan $phi$. Dua bilangan bulat bersifat koprim jika pembagi bersama terbesar mereka adalah 1. Jadi kita menggunakan fungsi math.gcd untuk menemukan bilangan bulat $e$ yang koprim dengan $phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

Kunci privat membutuhkan bilangan bulat $d$, yang merupakan invers multiplikatif dari $e$ modulo $phi$; yaitu, memenuhi relasi kongruensi $d*e\equiv 1 \pmod{\varphi(n)}$. Untuk ilustrasi sederhana ini di mana kita berurusan dengan bilangan bulat kecil, kita cukup mengulang bilangan bulat positif untuk menemukan $d$ yang sesuai. Dalam pengaturan realistis, algoritma Euclidean yang diperluas yang efisien secara komputasi digunakan untuk tujuan ini.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Kita sekarang membentuk tuple $(e, n), (d, n)$, yang masing-masing membentuk kunci publik dan privat. Kunci publik kemudian dipublikasikan, sementara kunci privat dijaga kerahasiaannya.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

Enkripsi dan dekripsi dalam RSA menggunakan operasi eksponensiasi modular. Selanjutnya, kunci publik dan privat saling melengkapi dalam hal salah satu bisa digunakan untuk mengenkripsi pesan yang kemudian bisa didekripsi oleh yang lain.

Di sini kita mengilustrasikan kasus di mana kunci publik $(e,n)$ digunakan untuk enkripsi dan kunci privat $(d, n)$ digunakan untuk dekripsi dengan mendefinisikan fungsi Python untuk setiap operasi.

Kita kemudian mengenkripsi dan mendekripsi pesan bilangan bulat $msg$.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Meskipun bilangan bulat kecil yang digunakan di atas berguna untuk dengan mudah menguraikan ide-ide inti dalam algoritma RSA, dalam aplikasi nyata RSA membutuhkan penggunaan bilangan bulat yang sangat besar. Misalnya, RSA 2048-bit melibatkan penggunaan modulus $n$ yang panjangnya 2048 bit, setara dengan bilangan bulat desimal yang sekitar 10$^616$. Angka-angka yang sangat besar ini diperlukan untuk keamanan praktis RSA.

Pertukaran kunci simetris dengan RSA

Seperti yang dibahas sebelumnya, AKC memungkinkan dua pihak yang ingin berkomunikasi untuk menetapkan secara aman sebuah rahasia bersama, yang bisa digunakan, misalnya, sebagai kunci rahasia untuk enkripsi simetris teks biasa dalam jumlah besar berikutnya.

Mari kita pertimbangkan skenario berikut. Alice dan Bob ingin menggunakan SKC untuk mengenkripsi dan mendekripsi pesan. Namun, sebelum proses ini bisa diinisialisasi, mereka perlu menyepakati kunci rahasia bersama. Salah satu opsi adalah satu pihak — katakanlah, Alice — menghasilkan kunci rahasia dan kemudian mengirimkannya secara aman ke Bob. Untuk mencapai transfer yang aman ini, Alice memutuskan untuk menggunakan RSA sebagai mekanisme enkapsulasi kunci (KEM).

Ini melibatkan langkah-langkah berikut:

• Pertama, Alice menghasilkan kunci simetris acak, yang ingin dia bagikan dengan Bob.
• Kemudian, Bob menghasilkan pasangan kunci asimetris dan membuat kunci publiknya tersedia di saluran yang sesuai.
• Selanjutnya, Alice menggunakan kunci publik Bob untuk mengenkripsi kunci simetris, sehingga mengenkapsulasi dalam sebuah ciphertext.
• Kemudian, Alice menyiarkan ciphertext melalui saluran yang dapat diandalkan tapi tidak harus aman.
• Akhirnya, Bob menerima ciphertext dan mendekripsinya menggunakan kunci privatnya. Dia sekarang memiliki akses ke kunci simetris yang dibuat oleh Alice.

Gambar 1. Pertukaran kunci simetris dengan RSA

Contoh pertukaran kunci berbasis padding dalam Python

Alur kerja praktis yang menggunakan RSA untuk pertukaran kunci non-interaktif berbasis padding kini diilustrasikan menggunakan pustaka Python cryptography.

Impor modul yang diperlukan dari pustaka Python cryptography. Jika diperlukan, pustaka ini bisa diinstal menggunakan perintah pip install cryptography.

Alice kemudian menghasilkan kunci rahasia acak, yang ingin dia kirimkan ke Bob.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Menggunakan modul rsa dari pustaka cryptography, Bob menghasilkan pasangan kunci lalu menyiarkan kunci publiknya. Siapa pun bisa mencegat kunci publik dan membaca bilangan publik $(e,n)$ yang membentuk kunci tersebut.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

Pada titik ini, kita asumsikan Alice telah menerima kunci publik yang disiarkan oleh Bob. symmetric_key Alice di atas sekarang bisa dienkripsi menggunakan kunci publik Bob untuk menghasilkan ciphertext. Dalam pengaturan realistis, Alice juga akan menggunakan metode padding tambahan seperti OAEP untuk memastikan keamanan semantis untuk komunikasinya dengan Bob.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice kemudian menyiarkan ciphertext melalui saluran terbuka, yakin bahwa hanya Bob dengan kunci privat yang sesuai yang bisa mendekripsinya. Kita asumsikan Bob telah menerima ciphertext dan sekarang bisa mendekripsinya menggunakan kunci privat rahasianya.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

Pada titik ini, Alice dan Bob keduanya memiliki akses ke kunci simetris rahasia, yang bisa mereka gunakan untuk aplikasi SKC.

Mensimulasikan Mekanisme Enkapsulasi Kunci dengan RSA dalam Python

Dalam alur kerja berikut, kita mengilustrasikan penggunaan RSA untuk mensimulasikan Mekanisme Enkapsulasi Kunci (KEM) di mana pesan rahasia acak yang cukup panjang dipertukarkan secara aman dan kemudian dikonversi menjadi rahasia bersama dengan panjang yang sesuai menggunakan KDF.

Sekali lagi Alice dan Bob ingin menetapkan rahasia bersama secara non-interaktif dan Alice adalah pihak yang menentukan rahasia mana yang digunakan.

Kita mulai dengan mengimpor beberapa pustaka Python yang diperlukan.

Bob kemudian menghasilkan pasangan kunci RSA-nya dan menyiarkan kunci publiknya.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice pertama-tama menghasilkan rahasia acak yang panjang dari mana rahasia bersama pada akhirnya akan diturunkan. Dalam KEM murni, rahasia yang panjang akan menjadi elemen acak dari struktur aljabar yang mendasari kriptosistem. Dalam kasus RSA 2048-bit, ini akan menjadi bilangan bulat acak modulo RSA modulus 2048-bit. Karena KEM murni seperti itu tidak memerlukan padding tambahan tapi dalam contoh ini kita hanya mensimulasikan KEM menggunakan RSA dan pustaka cryptography mengharuskan penggunaan padding saat mengenkripsi dengan RSA. Jadi kita akan menggunakan rahasia panjang yang agak lebih pendek yang tetap jauh lebih panjang dari kunci AES 256-bit standar.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Selanjutnya Alice mengenkripsi rahasia panjang menggunakan kunci publik Bob dan rahasia terenkripsi dikomunikasikan ke Bob.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob mendekripsi rahasia terenkripsi yang diterima dari Alice menggunakan kunci privatnya.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Akhirnya baik Alice maupun Bob secara terpisah menerapkan Fungsi Derivasi Kunci (KDF) yang telah disepakati pada rahasia panjang untuk menurunkan kunci simetris.

Perhatikan bahwa prosesnya melibatkan protokol hashing dan penggunaan salt acak yang memastikan keunikan dan ketidakpastian kunci simetris bersama jika rahasia panjang pernah digunakan kembali (tidak disarankan). Namun salt itu sendiri tidak harus rahasia dan setelah dibuat secara acak, katakanlah oleh Alice dalam contoh ini, bisa disiarkan ke Bob bersama rahasia panjang yang terenkripsi.

Kita akan mengasumsikan bahwa baik Alice maupun Bob memiliki akses ke salt acak yang sama.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Tanda tangan digital dengan RSA

Kita sekarang akan memperluas skenario komunikasi rahasia di atas antara Alice dan Bob ke skenario yang juga menyertakan validasi dengan bantuan tanda tangan digital.

Seperti sebelumnya, Alice akan secara rahasia mengirim pesan yang mengenkapsulasi kunci simetris ke Bob, tapi dia juga akan menandatangani pesan secara digital sehingga Bob, setelah menerima pesan, bisa memverifikasi bahwa itu Alice yang berasal darinya dan bahwa isi pesan tidak dirusak selama transmisi.

Secara lebih umum, diinginkan untuk memungkinkan validasi tanpa mengorbankan kerahasiaan di mana pihak mana pun bisa memverifikasi integritas, keaslian, dan menetapkan non-repudiation terkait komunikasi tertentu, bahkan jika pihak tersebut tidak memiliki akses ke pesan teks biasa yang sebenarnya.

Kita akan mempertimbangkan pengaturan umum ini yang kemudian melibatkan langkah-langkah berikut:

• Pertama, baik Bob maupun Alice membuat kunci publik mereka tersedia melalui saluran terbuka.
• Kemudian, Alice mengenkripsi teks biasa menggunakan kunci publik Bob, membuat ciphertext.
• Selanjutnya, Alice membuat hash dari ciphertext dengan sebuah fungsi hash dan lebih lanjut mengenkripsi ciphertext yang di-hash menggunakan kunci privatnya. Hash terenkripsi ini adalah tanda tangan.
• Kemudian, Alice kemudian mengirimkan ciphertext dan tanda tangan melalui saluran terbuka.
• Kemudian, Bob menggunakan kunci publik Alice untuk mendekripsi tanda tangan, mengungkapkan ciphertext yang di-hash.
• Selanjutnya, karena Bob juga memiliki akses ke ciphertext itu sendiri, dia menggunakan fungsi hash yang sama yang digunakan Alice untuk membuat instance kedua dari ciphertext yang di-hash. Jika yang terakhir cocok dengan yang diperoleh dengan mendekripsi tanda tangan Alice, maka pesan telah divalidasi, meskipun ciphertext itu sendiri belum didekripsi.
• Akhirnya, Bob, setelah memvalidasi pesan, mendekripsi ciphertext menggunakan kunci privatnya sendiri.

Gambar 2. Tanda tangan digital dengan RSA

Alur kerja untuk tanda tangan digital ini diilustrasikan berikutnya.

Kita sekali lagi mengimpor beberapa modul berguna dari pustaka cryptography. Seperti sebelumnya, Alice bermaksud untuk secara aman mengirim kunci simetris ke Bob, tapi dia juga ingin menandatanganinya secara digital. Dalam hal ini, kita membutuhkan kunci publik untuk baik Alice maupun Bob. Oleh karena itu, langkah pertama adalah baik Alice maupun Bob membuat pasangan kunci mereka sendiri menggunakan RSA dan menyiarkan kunci publik mereka sendiri ke dunia.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

Pada langkah berikutnya, seperti sebelumnya, Alice menggunakan kunci publik Bob untuk mengenkripsi kunci simetris dan menyiapkan ciphertext.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

Pada tahap ini, alih-alih hanya menyiarkan ciphertext, Alice bermaksud untuk melampirkan tanda tangan digital ke dalamnya sehingga dia bisa membuktikan kepada Bob bahwa dia adalah pengirim pesan. Ini dilakukan dalam dua langkah:

1. Buat hash dari ciphertext menggunakan algoritma hashing.
2. Enkripsi hash menggunakan kunci privat Alice, yang merupakan sebuah tanda tangan.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice kemudian menyiarkan ciphertext dan tanda tangan melalui jaringan sehingga Bob bisa mencegat keduanya.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Di sisi Bob, tugas pertama adalah memverifikasi integritas dan keaslian ciphertext. Untuk melakukan ini, Bob membuat hash dari ciphertext yang diterima menggunakan algoritma hashing yang sama yang digunakan Alice.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Kemudian, Bob mendekripsi tanda tangan yang diterima menggunakan kunci publik Alice. Karena Alice menggunakan kunci privatnya untuk membuat tanda tangan, Bob bisa mendekripsinya menggunakan kunci publik Alice. Tanda tangan yang didekripsi tidak lain adalah hash dari ciphertext yang dibuat di sisi Alice. Jika hash yang dibuat oleh Bob cocok dengan tanda tangan yang didekripsi, maka Bob telah memverifikasi bahwa ciphertext yang dia terima tidak dirusak dan bahwa itu Alice yang menandatangani ciphertext tersebut.

Dalam kode Python di bawah ini, operasi-operasi ini digabungkan ke dalam fungsi utilitas berguna yang disebut verify yang disediakan oleh objek yang terkait dengan kunci publik Alice.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Setelah memverifikasi integritas dan keaslian ciphertext yang diterima, Bob kemudian bisa mendekripsinya menggunakan kunci privatnya karena Alice membuat ciphertext menggunakan kunci publik Bob.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

Dalam skenario tanda tangan digital di atas, pihak mana pun — bukan hanya Bob — bisa memverifikasi bahwa Alice adalah pengirim ciphertext karena semua orang bisa mengakses kunci publik Alice, ciphertext, dan tanda tangan digital. Selanjutnya, setelah mengirim ciphertext dan tanda tangan, Alice tidak bisa kemudian menyangkal telah melakukannya karena tanda tangan bisa didekripsi menjadi hash yang bermakna hanya menggunakan kunci publiknya. Ini menetapkan non-repudiation.

Dengan memungkinkan distribusi kunci yang aman dan mendukung non-repudiation, kriptografi kunci publik menetapkan fondasi yang kuat untuk komunikasi digital yang aman.

Membobol RSA

Kegunaan dan keamanan algoritma RSA yang diuraikan di atas bertumpu pada dua asumsi matematis:

1. Mencari invers perkalian modular $d$ dengan hanya memiliki akses ke $(e, n)$ secara komputasi tidak layak dilakukan.

2. Dalam konteks RSA, operasi eksponen modular berperilaku seperti fungsi trapdoor satu arah. Ketika digunakan untuk enkripsi, fungsi ini menghasilkan ciphertext yang tidak terbaca, dan tanpa akses ke kunci privat, membalikkan operasi untuk memulihkan teks biasa dari ciphertext tidaklah layak. Namun, dengan akses ke kunci privat yang bertindak sebagai trapdoor, ciphertext dapat dengan mudah didekripsi.

Serangan paling menonjol terhadap algoritma RSA bertujuan merusak asumsi 1 dengan cara memulihkan nomor kunci privat $d$ secara efisien melalui pemfaktoran modulus $n$. Seperti yang akan diilustrasikan di bawah, mudah untuk memulihkan $d$ jika seseorang memiliki akses ke faktor prima $p$ dan $q$ dari $n$ atau totient $φ$$(n)$. Ingatlah bahwa $p$, $q$, dan $φ$$(n)$ disimpan sebagai rahasia selama pembuatan kunci dan dibuang setelahnya. Pihak ketiga yang memulihkan informasi ini menggunakan komputer klasik atau kuantum pada dasarnya mengungkap kunci privat, sehingga membobol RSA. Oleh karena itu, faktorisasi prima adalah primitif komputasi kunci yang diperlukan untuk membobol RSA.

Komputasi klasik dan RSA

Faktorisasi prima dari bilangan bulat besar diketahui memiliki skalabilitas super-polinomial atau subeksponensial pada komputer klasik. Algoritma klasik terbaik yang diketahui untuk memfaktorkan bilangan bulat lebih besar dari $10^{100}$ adalah general number field sieve (GNFS)

Detail matematika

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

sebagai fungsi dari bilangan bulat $n$ yang akan difaktorkan.

Skalabilitas ini bersifat super-polinomial dalam jumlah bit yang diperlukan untuk merepresentasikan $n$.

Oleh karena itu, faktorisasi prima dianggap tidak efisien pada komputer klasik.

Saat ini, bilangan bulat terbesar yang difaktorkan pada perangkat keras klasik berada dalam kisaran 829 bit atau 250 digit desimal. Mengingat pertumbuhan eksponensial dalam daya komputasi klasik yang telah diamati selama beberapa dekade terakhir, RSA 1024-bit tidak lagi dianggap aman dalam waktu dekat dan kini sudah tidak digunakan. Meskipun demikian, di masa mendatang yang dapat terlihat, memfaktorkan bilangan bulat 2048-bit yang besarnya berada dalam kisaran $10^{617}$ saat ini dianggap tidak layak pada sistem klasik, yang mengisyaratkan kelanjutan kegunaannya. Namun, hadirnya komputer kuantum membatalkan penilaian ini.

Algoritma kuantum Shor dan RSA

Algoritma kuantum yang mungkin paling terkenal saat ini adalah algoritma Shor untuk menemukan faktor prima dari bilangan bulat. Ketika diperkenalkan oleh Peter Shor pada tahun 1994, algoritma ini diakui sebagai algoritma kuantum pertama yang menawarkan percepatan super-polinomial relatif terhadap algoritma klasik pada masalah yang sangat penting secara praktis, yaitu faktorisasi prima.

Algoritma Shor dapat memfaktorkan prima dengan $O(n^2)$ di mana $n$ adalah jumlah bit.

Penjelasan matematis algoritma Shor

Dalam konteks RSA, algoritma Shor bekerja dengan memanfaatkan periodisitas dari fungsi eksponensial modular $f(x) = a^x (mod~n)$ dan menyediakan primitif pencarian periode kuantum yang memungkinkan faktorisasi prima yang efisien dari modulus $n$.

Gambaran garis besar tingkat tinggi yang disederhanakan dari skema Shor secara keseluruhan untuk membobol RSA adalah sebagai berikut:

1. Diberikan modulus $n$, yang dipublikasikan sebagai bagian dari kunci publik, pilih sebuah angka $a$ yang koprima terhadap $n$, yaitu, $gcd(a,n) = 1$. Karena kita tahu bahwa $n = p*q$ memiliki tepat dua faktor prima $(p, q)$, hampir semua angka lebih kecil dari $n$ yang kita pilih secara acak kemungkinan besar akan koprima terhadap $n$.

2. Setelah memilih $a$, temukan eksponen $r$ sehingga $a^r \equiv 1 (mod~n)$. Ini berarti $a^r - 1 \equiv 0 (mod~n)$. Keberadaan sebuah eksponen $r$ sehingga kongruensi di atas terpenuhi dijamin oleh sifat periodisitas dari eksponen modular.

3. Jika $r$ genap, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ untuk suatu bilangan bulat $\gamma$. Sisi kiri dari kesamaan tersebut harus mengandung $p$ dan $q$ sebagai dua faktor primanya karena sisi kanan juga demikian. Jika $r$ ganjil, kembali ke langkah 1 dan coba pilihan yang berbeda untuk $a$.

4. Gunakan algoritma Euclid yang diperluas untuk mencari $gcd((a^{r/2} - 1), n)$ atau $gcd((a^{r/2} + 1), n)$. GCD yang dihitung kemungkinan besar akan mengidentifikasi salah satu faktor prima $p$ atau $q$. Bagi $n$ dengan faktor prima ini untuk memulihkan yang lainnya.

5. Setelah $p, q$ diketahui, gunakan langkah-langkah dari algoritma RSA asli untuk merekonstruksi totient $\phi(n)$ dan menghasilkan nomor kunci privat $d$ sebagai invers modular dari nomor kunci publik $e$ yang diketahui.

Pada Agustus 2023, Oded Regev mempublikasikan peningkatan atas versi asli Shor menggunakan pendekatan multi-dimensi yang menghasilkan $O(n^{1.5})$. Penelitian lebih lanjut terus dilakukan, termasuk oleh Ragavan dan Vaikuntanathan di bidang ini yang mungkin meningkatkan waktu, biaya, atau jumlah qubit yang dibutuhkan. Meskipun kita tidak dapat mengatakan kapan menjalankan algoritma semacam itu terhadap enkripsi RSA dunia nyata benar-benar menjadi layak, hal tersebut semakin dekat dari waktu ke waktu.

Contoh Python yang mendemonstrasikan pembobol enkripsi RSA

Dalam sel kode berikut, kita mengilustrasikan contoh pencarian kunci privat hanya dengan diberikan kunci publik. Ini akan menggunakan komputasi klasik dengan brute-force, tetapi menunjukkan bagaimana algoritma Shor bisa digunakan — termasuk untuk kunci yang besar.

catatan

Di bagian ini kita akan menampilkan kalkulasi matematis secara detail sebagai bagian dari kode Python

Dalam contoh ini, kita memiliki kunci publik $(5, 247)$, dan kita akan memulihkan kunci privat.

Langkah 1: Langkah pertama adalah memilih angka yang koprima terhadap 247. Hampir semua angka yang kita tebak akan cocok. Mari pilih 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Langkah 2: Selanjutnya kita perlu menemukan periode $r$ sehingga $6^r \equiv 1 (mod~247)$. Dalam contoh ini, kita menghitung $r$ secara klasik menggunakan brute force, tetapi kita juga bisa menggunakan algoritma Shor pada komputer kuantum menggunakan Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Langkah 3: Karena periode $r = 36$ adalah genap, kita dapat menghitung $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Langkah 4: Temukan GCD dari salah satu faktor tersebut dengan $n$. Cukup bagi $n$ dengan faktor prima yang sudah ditemukan untuk mendapatkan faktor prima kedua.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Langkah 5: Setelah memulihkan faktor prima dari $n = 247$ sebagai $p_{found}=13$ dan $q_{found}=19$, kita menghitung totient $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

Kunci privat adalah invers modular dari nomor kunci publik $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

Dalam skema di atas, langkah 2 adalah operasi pencarian periode yang krusial, di mana algoritma Shor menggunakan dua primitif kuantum fundamental, yaitu transformasi Fourier kuantum dan estimasi fase kuantum. Untuk penjelasan terperinci tentang aspek kuantum dari algoritma Shor, lihat pelajaran Estimasi fase dan pemfaktoran dalam Fundamentals of Quantum Algorithms. Langkah 1 dan 3 hingga 5 melibatkan operasi yang relatif murah dan dapat dengan mudah dilakukan pada komputer klasik.

Sebagai opsional, berikut adalah panduan visual terperinci untuk mengimplementasikan algoritma Shor.

Pada komputer kuantum, algoritma Shor dapat menunjukkan skalabilitas polilogatritmik sebaik $O((log~n)^2 (log~log~n))$ dalam hal modulus $n$, atau skalabilitas polinomial dalam hal jumlah bit yang diperlukan untuk merepresentasikan $n$. Ini adalah percepatan super-polinomial dibandingkan dengan algoritma GNFS klasik.

Estimasi sumber daya terbaru menunjukkan bahwa berdasarkan asumsi tertentu mengenai konfigurasi perangkat keras, beberapa puluhan ribu hingga beberapa juta qubit akan diperlukan untuk membobol RSA 2048-bit menggunakan algoritma Shor. Tidak mustahil bahwa komputer kuantum dengan beberapa puluhan ribu qubit akan tersedia dalam beberapa tahun ke depan, membuat batas bawah estimasi sumber daya dapat dicapai.

Pertukaran kunci Diffie-Hellman dan Algoritma Tanda Tangan Digital

Pada bagian sebelumnya, kita membahas kriptosistem RSA, yang keamanannya didasarkan pada kesulitan komputasional dari faktorisasi prima. Di sini, kita akan membahas dua protokol kriptografi kunci asimetris yang populer, pertukaran kunci Diffie-Hellman (DH) dan Algoritma Tanda Tangan Digital (DSA), keduanya didasarkan pada masalah matematis yang berbeda, yaitu masalah logaritma diskret (DLP).

Masalah logaritma diskret

Dalam persamaan berikut kita perlu menemukan $a$ hanya dengan diberikan $e$,$M$,$c$

$a^e$ $mod$ $M = c$

Ini diyakini sulit dilakukan dengan komputer klasik karena penggunaan aritmetika modulo, dan oleh karena itu merupakan dasar matematis yang baik untuk algoritma enkripsi.

Ini dikenal sebagai masalah logaritma diskret (DLP).

Detail matematis dari masalah logaritma diskret

DLP biasanya dirumuskan dalam konteks grup siklik dan dinyatakan sebagai berikut.

Pertimbangkan sebuah grup siklik $G$ yang dibangkitkan oleh elemen grup $g \in G$ dan diberikan elemen sembarang $h \in G$, temukan bilangan bulat $k$ sehingga $h = g^{k}$.

Di sini bilangan bulat $k \equiv log_{g}h$ adalah logaritma diskret. Sifat siklik dari $G$ menjamin bahwa untuk setiap $h$, bilangan bulat $k$ yang valid ada.

Untuk kriptografi, DLP pada grup multiplikatif dari bilangan bulat modulo bilangan prima $p$ yang dilambangkan $(\mathbb{Z}_p)^{\times}$ ternyata berguna. Elemen dari $(\mathbb{Z}_p)^{\times}$ adalah kelas kongruensi yang diberi label dengan bilangan bulat modulo $p$ yang koprima terhadap $p$.

Misalnya:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

Operasi perkalian $(\times)$ pada grup-grup ini hanyalah perkalian bilangan bulat biasa diikuti dengan reduksi modulo $p$ dan eksponensiasi oleh bilangan bulat $k$ hanyalah perkalian berulang sebanyak $k$ kali dan reduksi modulo $p$.

Mari kita ilustrasikan sebuah contoh DLP pada $(\mathbb{Z}_7)^{\times}$.

Grup multiplikatif ini memiliki dua generator ${[3],[5]}$ yang juga dikenal sebagai akar primitif. Kita akan menggunakan $[5]$ sebagai generator; yaitu, membangkitkan setiap elemen dari $(\mathbb{Z}_7)^{\times}$ menggunakan pangkat bilangan bulat berturut-turut dari 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Kita melihat bahwa dalam aritmetika modulo 7, memangkatkan 5 dengan pangkat bilangan bulat berturut-turut menghasilkan setiap elemen dari $(\mathbb{Z}_7)^{\times}$ tepat sekali sebelum siklus berulang tanpa batas dengan periode $p-1 =6$.

Jadi DLP pada $(\mathbb{Z}_7)^{\times}$ dengan generator [5] adalah:

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$.

Dari output sel Python di atas kita melihat bahwa:

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

Dalam aritmetika bilangan real biasa, eksponensiasi adalah fungsi yang monoton dan menemukan logaritma dari bilangan apa pun ke basis apa pun secara komputasi mudah. Sebaliknya, seperti yang terlihat jelas dari contoh $(\mathbb{Z}_7)^{\times}$ sederhana di atas, eksponensiasi modular bersifat non-monoton, dan meskipun bersifat periodik dengan periode $p-1$, selebihnya sangat tidak trivial. Jadi menghitung inversnya, logaritma diskret, ternyata tidak efisien untuk $p$ yang besar pada komputer klasik.

Pengamatan ini menjadi dasar dari pertukaran kunci Diffie-Hellman (DH) dan Algoritma Tanda Tangan Digital (DSA), yang dibahas di bagian berikutnya.

DLP dapat diperluas ke subgrup siklik sebagai berikut:

• Pertimbangkan $(\mathbb{Z}_p)^{\times}$ yang didefinisikan di atas dan sebuah elemen $g \in (\mathbb{Z}_p)^{\times}$ berorde prima $r$ yaitu, $g^r \equiv 1 (~mod~p)$.
• Himpunan pangkat bilangan bulat dari $g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ adalah subgrup siklik dari $(\mathbb{Z}_p)^{\times}$ dengan orde grup $r$.
• Sebuah DLP dapat ditentukan pada $\langle g \rangle$ dengan memilih $h \in \\langle g \rangle$ dan meminta $1 \le a \le r$ sehingga $g^a~(mod~p) = h$

Pertukaran kunci Diffie-Hellman

Pada tahun 1976, Whitfield Diffie dan Martin Hellman mengusulkan protokol pertukaran kunci untuk memungkinkan pembuatan kunci rahasia bersama melalui saluran komunikasi yang tidak aman. Kunci rahasia tersebut kemudian dapat digunakan oleh pihak-pihak yang berbagi untuk enkripsi simetris. Algoritma ini bergantung pada DLP.

Gambar 1. Pertukaran kunci Diffie-Hellman

Detail matematis dari pertukaran kunci Diffie-Hellman

Dengan Alice dan Bob sebagai dua pihak yang berkomunikasi, protokolnya bekerja sebagai berikut:

• Pertama, Alice dan Bob sepakat tentang bilangan prima besar $p$ dan akar primitif atau generator $a$.
• Kemudian, Alice memilih eksponen rahasia $k_A$ secara acak dengan $1 \le k_A \le p-2$ dan menghitung $h_A = a^{k_A}~(mod~p)$. $k_A, h_A$ masing-masing adalah kunci privat dan publik Alice.
• Selanjutnya, Bob memilih eksponen rahasia $k_B$ secara acak dengan $1 \le k_B \le p-2$ dan menghitung $h_B = a^{k_B}~(mod~p)$. $k_B, h_B$ masing-masing adalah kunci privat dan publik Bob.
• Kemudian, Alice mengirim $h_A$ ke Bob dan Bob mengirim $h_B$ ke Alice melalui saluran yang andal namun tidak harus aman.
• Lalu, Alice menggunakan $h_B$ yang diterimanya untuk menghitung kunci rahasia bersama $\kappa = h_B^{k_A}~(mod~p)$.
• Terakhir, Bob sementara itu menggunakan $h_A$ yang diterimanya untuk menghitung kunci rahasia bersama $\kappa = h_A^{k_B}~(mod~p)$.

Dengan protokol ini,

• Alice dan Bob dijamin mendapatkan kunci rahasia yang sama $\kappa$ karena $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• Pihak ketiga yang mencegat $h_A$ atau $h_B$ tidak dapat membuat kunci rahasia $\kappa$ karena mereka tidak memiliki akses ke $k_B$ atau $k_A$ masing-masing.
• Mengekstrak $k_A$ atau $k_B$ menggunakan informasi publik $a$, $p$, $h_A$ dan $h_B$ secara komputasi sulit karena setara dengan memecahkan DLP pada $(\mathbb{Z}_p)^{\times}$.

Ilustrasi protokol Diffie-Hellman dalam Python

Mari kita lihat contoh sederhana protokol DH dalam Python menggunakan bilangan prima kecil:

catatan

Di bagian ini kita akan menampilkan kalkulasi matematis secara detail sebagai bagian dari kode Python

Langkah 1: Alice dan Bob sepakat tentang prima $p$ dan akar primitif $a$. Mari pilih $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Langkah 2, 3: Alice memilih eksponen rahasia $k_A$ dan menghitung $h_A = a^{k_A}~(mod~p)$. Demikian pula, Bob memilih eksponen rahasia $k_B$ dan menghitung $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Langkah 4: Kedua pihak menyiarkan kunci publik mereka $h_A$ dan $h_B$.

Langkah 5, 6: Setiap pihak menggabungkan kunci privatnya dengan kunci publik pihak lain untuk membuat kunci rahasia bersama.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice dan Bob sekarang dapat menggunakan kunci rahasia bersama untuk enkripsi simetris.

Keamanan pertukaran kunci Diffie-Hellman

Seperti yang disebutkan di atas, keamanan DH bergantung pada kesulitan komputasional dalam memecahkan DLP dengan prima besar $p$. Dalam aplikasi tipikal, NIST merekomendasikan bilangan prima 2048- atau 3072-bit untuk pertukaran kunci DH, yang dianggap cukup aman terhadap upaya memecahkan DLP menggunakan komputer klasik.

Serangan man-in-the-middle (MITM): Fakta bahwa DH adalah skema interaktif di mana rahasia bersama bergantung pada penggabungan kunci privat satu pihak dengan kunci publik pihak lain membuatnya rentan terhadap serangan yang disebut Man-in-the-middle (MITM).

Detail matematis keamanan DH dan serangan MITM

Dalam skenario ini, pihak ketiga — misalnya, Eve — mencegat kunci publik $h_A, h_B$ selama transmisi dan menggantikan kunci publiknya sendiri $h_E$ untuk masing-masing $h_A$ dan $h_B$ sebelum meneruskannya ke Bob dan Alice.

Kemudian, alih-alih menggunakan $h_B$ untuk membuat rahasia bersamanya, Alice akan menggunakan $h_E$ sambil berpikir bahwa dia menggunakan kunci publik Bob. Demikian pula, alih-alih menggunakan $h_A$ untuk membuat rahasia bersamanya, Bob akan menggunakan $h_E$ sambil berpikir bahwa dia menggunakan kunci publik Alice.

Karena $h_E$ digunakan untuk membuat rahasia bersama Alice (Bob), teks biasa yang dienkripsi oleh Alice (Bob) dapat didekripsi oleh Eve.

Dengan demikian, pertukaran kunci DH biasanya digunakan bersama dengan algoritma tanda tangan digital untuk memastikan bahwa setiap pihak menggunakan kunci publik yang telah diautentikasi untuk membuat rahasia bersamanya.

Algoritma Tanda Tangan Digital (DSA)

Meskipun sistem kriptografi generik seperti RSA menyediakan fungsionalitas tanda tangan digital, pada tahun 1994 NIST mengadopsi skema tanda tangan khusus berdasarkan eksponensiasi modular dan masalah logaritma diskret sebagai standar federal untuk tanda tangan digital. Skema ini, yang kemudian dikenal sederhana sebagai Algoritma Tanda Tangan Digital (DSA), melibatkan empat fase yang berbeda:

1. Pembuatan kunci:

   Kunci DSA dibuat dari:

   • 2 prima yang memenuhi aturan tertentu
     • $p$ - biasanya 256 bit (kita sebut panjang ini $N$)
     • $q$ - biasanya 3072 bit (kita sebut panjang ini $L$)
   • Fungsi hash kriptografi yang akan mengkonversi dari string dengan panjang $L$ ke $N$
   • Parameter tambahan $g$ (lihat detail di bawah)

   Dari ini kita memilih bilangan acak $x$ sebagai kunci privat, dan dapat menghitung kunci publik $y$

   Detail matematis pembuatan kunci

   • Pembuatan parameter: Secara matematis, DSA melibatkan subgrup siklik dari $(\mathbb{Z}_p)^{\times}$ yang dibangkitkan oleh elemen $g$ berorde prima q < p. Langkah pertama dalam DSA oleh karena itu adalah memilih dua prima p, q untuk menyiapkan struktur matematis yang diperlukan.

     • Pilih prima $q$ berukuran $N$-bit.
     • Pilih prima $p$ berukuran $L$-bit sedemikian sehingga $p-1$ adalah kelipatan dari $q$. Pilihan $p$ menentukan grup $(\mathbb{Z}_p)^{\times}$
     • Pilih bilangan bulat $1 < h < p-1$ secara acak dan hitung $g = h^{(p-1)/q}~mod~p$. Jika $g=1$ yang jarang terjadi, coba $h$ yang lain.
     • Verifikasi bahwa $g^q~mod~p = 1$. Dengan demikian g adalah generator dari subgrup siklik $\langle g \rangle$ dari $(\mathbb{Z}_p)^{\times}$ berorde prima q.

     Parameter $(q, p, g)$ menentukan sebuah contoh algoritma dan merupakan informasi publik. Biasanya, $N \sim 256$ dan $L \sim 3072$ dalam aplikasi nyata.

     Protokol ini juga memerlukan fungsi hash kriptografi $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ yang memetakan string biner $L$-bit ke string $N$-bit, misalnya, SHA-256.

   • Pembuatan pasangan kunci: Penanda tangan perlu membuat pasangan kunci di pihaknya.

     • Pilih bilangan bulat rahasia acak $x \in \{1,2...q-1\}$. $x$ adalah kunci privat.
     • Hasilkan $y = g^{x}~mod~p$. $y$ adalah kunci publik penanda tangan.

2. Distribusi kunci:

   Informasi berikut dibagikan kepada siapa pun yang ingin memvalidasi tanda tangan

   • Parameter yang digunakan $(p,q,g)$ yang mendeskripsikan algoritma
   • Fungsi hash $H$
   • Kunci publik $y$

3. Penandatanganan:

   • Penanda tangan sekarang dapat menandatangani pesan $m$. Tanda tangan yang dihasilkan adalah $(r,s)$
   • Pesan dan tanda tangan keduanya sekarang dikirim ke penerima

   Detail matematis penandatanganan pesan

   Penanda tangan menandatangani pesan $m$ sebagai berikut:

   • Pilih bilangan bulat rahasia k secara acak dari $\{1,2...q-1\}$
   • Hitung $r = (g^k~mod~p)~mod~q$. Dalam kasus langka ketika $r=0$, coba k acak yang lain.
   • Hitung $s = (k^{-1} (H(m) + xr))~mod~q$. Dalam kasus langka jika $s=0$, coba k acak yang lain.
   • Tanda tangan adalah tupel $(r, s)$.
   • Penanda tangan mentransmisikan pesan $m$ beserta tanda tangan $(r,s)$ ke verifikator.

   Karena $r, s$ keduanya adalah bilangan bulat, modulo $q$ ukuran tanda tangan berada dalam urutan $N$-bit dan bukan $L$-bit yang lebih panjang.

4. Verifikasi:

   Penerima sekarang ingin memverifikasi keaslian pengirim. Mereka memiliki akses ke informasi publik $(q, p, g, H, y, (r,s), m)$ Mereka dapat menjalankan kalkulasi yang membuktikan bahwa pengirim memiliki akses ke kunci privat $x$

   dan berupaya memastikan bahwa penanda tangan adalah seseorang dengan akses ke kunci privat $x$.

   Detail matematis skema verifikasi DSA

   • Verifikasi bahwa $0 \lt r \lt q$ dan $0 \lt s \lt q$, yaitu, $r, s$ adalah bilangan bulat modulo~q yang valid.
   • Hitung $w = s^{-1}~mod~q$.
   • Hitung $u_1 = H(m)w~mod~q$.
   • Hitung $u_2 = rw~mod~q$.
   • Hitung $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • Tanda tangan diverifikasi jika $v = r$.

   Untuk tanda tangan yang sah, kebenaran algoritma DSA mudah ditunjukkan sebagai berikut:

   • Di pihak penanda tangan: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • Mempertimbangkan sisi kanan dari kesamaan tersebut, verifikator dapat menghitung $s^{-1}, H(m)$ karena $s, q, m, H$ adalah informasi publik.
   • Dengan demikian, verifikator menghitung $w = s^{-1}~mod~q$ dan $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • Verifikator juga menghitung $u_2 = rw~mod~q = rs^{-1}~mod~q$ karena $r$ juga merupakan informasi publik.
   • Perhatikan bahwa $k = (u_1 + xu_2)~mod~q$.
   • Namun, verifikator tidak memiliki akses ke $x$ karena itu adalah kunci privat penanda tangan, sehingga $k$ sendiri tidak dapat dihitung secara langsung. - Skema ini mengandalkan fakta bahwa meskipun verifikator tidak dapat menghitung $k$, dengan penanda tangan yang sah, verifikator seharusnya bisa menghitung ulang $(g^k~mod~p)~mod~q = r$ dengan bantuan kunci publik penanda tangan $y = g^{x}~mod~p$.
   • Jadi, verifikator menghitung $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • Kesamaan terakhir mengikuti karena $g$ berorde $q$ dan menetapkan $v = r$ untuk tanda tangan yang valid.

Ilustrasi DSA dalam Python

Dalam contoh ini, kita akan menggunakan prima kecil untuk mengilustrasikan proses DSA dalam skenario di mana Alice mengirimkan pesan bertanda tangan ke Bob. Kita akan menggunakan bilangan bulat kecil dalam contoh ini. Skenario dunia nyata akan menggunakan prima yang jauh lebih besar dalam urutan 2048-3072 bit.

catatan

Kamu bisa mencoba menjalankan ulang contoh ini dengan nilai yang berbeda untuk melihat bagaimana algoritma berperilaku, tetapi pastikan kamu mulai menjalankan dari sel pertama di bagian ini.

Kita mulai dengan mengimpor library yang diperlukan dan memilih parameter kita. Parameter bilangan bulat $p$, $q$, $g$ adalah informasi publik, dan memenuhi aturan berikut:

• $p$, $q$ keduanya prima
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Selanjutnya penanda tangan, Alice, membuat kunci privatnya.

Kunci privat, k (alice-private-key dalam kode Python) harus memenuhi:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice menyimpan kunci privatnya sebagai rahasia.

Selanjutnya, Alice menghitung kunci publiknya menggunakan eksponensiasi modular. Membalikkan langkah ini untuk memulihkan kunci privat adalah sebuah contoh DLP, jadi sulit dihitung pada komputer klasik ketika prima besar digunakan.

Dari penjelasan matematis di atas, kita tahu ini dapat dihitung menggunakan rumus:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Seperti biasa, Alice membuat kunci publiknya tersedia melalui saluran yang tidak harus bersifat rahasia.

Sekarang Alice dapat menandatangani sebuah pesan.

Untuk skema tanda tangan digital, kita perlu membuat hash $H(m)$ dari pesan $m$ yang akan ditandatangani.

Misalkan Alice dan Bob sepakat untuk menggunakan algoritma hashing tertentu dengan panjang hash $N$ sama dengan jumlah bit dalam $q$. Dalam contoh sederhana ini, kita akan membatasi output dari fungsi hash tiruan kita dengan $q$. Fungsi hash di sini sangat sederhana, hanya menghasilkan bilangan bulat acak.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Selanjutnya, Alice perlu membuat bilangan rahasia acak per-pesan $k$ beserta invers perkalian modulo $q$ untuk menghitung tanda tangan.

Algoritma brute-force sederhana dapat digunakan untuk menghitung invers modular. Namun lebih baik menggunakan salah satu fungsi bawaan Python pow seperti yang ditunjukkan di bawah ini

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alice sekarang dapat menghitung tanda tangan.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

Perhatikan bahwa ada beberapa kondisi tertentu yang akan mengharuskan kita memilih nilai $k$ yang berbeda dalam kasus di mana $r$ atau $s$ menghasilkan nilai $0$. Dalam kasus ini kita akan membuat nilai baru dan mengulangi.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice menyiarkan pesan dan tanda tangannya ke penerima atau verifikator, Bob.

Bob sebelumnya telah mendapatkan kunci publik Alice dan sekarang dapat memverifikasi tanda tangan untuk mengautentikasi pesannya.

Untuk melakukannya, ia melakukan beberapa pemeriksaan, kemudian membuat ulang hash dari pesan siaran Alice dan menghitung kuantitas tambahan $w, u_1, u_2$ dan $v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Akhirnya, Bob memeriksa apakah $v$ sama dengan $r$. Jika keduanya sama, maka tanda tangan diverifikasi.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Keamanan DSA

Dengan komputasi klasik, keamanan DSA dapat dipengaruhi oleh beberapa faktor:

1. Ukuran kunci: Seperti biasa, ukuran kunci memberikan perlindungan dasar terhadap serangan brute force. Aplikasi modern yang menggunakan DSA menggunakan ukuran kunci minimal 2048 bit.

2. Kualitas $k$: Dalam DSA, setiap tanda tangan memerlukan nilai $k$ yang unik, acak, dan rahasia (lihat di atas). Keunikan, entropi, dan kerahasiaan $k$ sangat penting, dan kelemahan dalam salah satu aspek ini dapat menyebabkan kunci privat $x$ dikompromikan. Generator bilangan acak yang digunakan untuk menghasilkan $k$ harus aman sendiri.

3. Kekuatan fungsi hash: Karena DSA menggunakan fungsi hash sebagai bagian dari proses pembuatan dan verifikasi tanda tangan, fungsi hash yang lemah dapat membahayakan keamanan tanda tangan digital. Misalnya, penggunaan SHA-1 dengan DSA sudah tidak digunakan lagi dan SHA-2 atau yang lebih tinggi direkomendasikan.

Selain itu, implementasi DSA yang kuat juga harus melindungi terhadap jenis serangan lain yang menargetkan kriptografi kunci asimetris seperti yang telah diuraikan sebelumnya.

Pertukaran kunci terotentikasi dengan Diffie-Hellman dan DSA

Protokol keamanan jaringan modern, seperti Transport Layer Security (TLS) dan banyak lainnya, melibatkan penggabungan fungsionalitas pertukaran kunci dan autentikasi. Dalam konteks Diffie-Hellman, autentikasi diperlukan untuk melindungi dari serangan MITM. Dalam sel kode berikut, kita mengilustrasikan contoh di mana Alice dan Bob melakukan pertukaran kunci terotentikasi dengan menggabungkan protokol Diffie-Hellman dan DSA. Untuk ini, kita akan menggunakan library Python cryptography.

Gambar 2. Pertukaran kunci terotentikasi dengan Diffie-Hellman dan DSA

Pertama, Alice dan Bob sepakat tentang satu set parameter DH dan membuat satu set pasangan kunci publik-privat DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Kunci publik DH disiarkan. Selanjutnya, Alice dan Bob masing-masing membuat pasangan kunci terpisah untuk digunakan dengan DSA. Kunci-kunci ini pada gilirannya akan digunakan untuk menandatangani kunci publik DH yang akan dipertukarkan.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice menandatangani kunci publik DH-nya menggunakan kunci privat DSA-nya.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Demikian pula, Bob menandatangani kunci publik DH-nya menggunakan kunci privat DSA-nya.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Kunci publik DH dan tanda tangan yang sesuai sekarang disiarkan oleh Alice dan Bob. Setelah menerima kunci publik dan tanda tangan dari pihak lawan, setiap pihak kemudian memverifikasi bahwa tanda tangan tersebut valid. Dengan cara ini, serangan MITM dapat dicegah, karena Alice, misalnya, tahu bahwa kunci publik DH Bob memang ditandatangani oleh Bob dan sebaliknya.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Setelah verifikasi tanda tangan, Alice dan Bob membuat rahasia bersama, yang menyelesaikan pertukaran kunci.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Sebagai opsional, untuk keamanan tambahan, Alice dan Bob dapat menggunakan fungsi derivasi kunci khusus seperti HKDF untuk menghasilkan kunci simetris yang lebih aman dari rahasia bersama mereka menggunakan teknik key stretching.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Membobol Diffie-Hellman dan DSA

Kedua protokol Diffie-Hellman (DH) dan DSA melibatkan pembuatan kunci publik dalam bentuk $y = g^{x}~mod~p$, di mana kunci privat $x$ adalah logaritma diskret.

Penyerang yang dapat memecahkan sebuah contoh DLP dapat mengekspos kunci privat salah satu dari dua pihak dan, dengan menggabungkannya dengan kunci publik pihak kedua, mendapatkan akses ke rahasia bersama. Dalam kasus DSA, penyerang yang dapat memecahkan DLP dapat memulihkan kunci privat penanda tangan, membatalkan premis dasar dari tanda tangan digital.

Pada sistem komputasi klasik, DLP diyakini tidak memiliki solusi waktu polinomial. Namun seperti yang ditunjukkan oleh Peter Shor dalam makalah aslinya tahun 1994, algoritma Shor juga memecahkan DLP dalam waktu polinomial pada komputer kuantum.

Algoritma Shor dan masalah logaritma diskret

Algoritma Shor mampu memecahkan masalah logaritma diskret dalam waktu polinomial. Efisiensinya terutama dicapai dengan menggunakan algoritma kuantum yang dapat menemukan periode dari sebuah fungsi yang bergantung pada input masalah — yang kemudian digabungkan dengan operasi yang lebih konvensional.

Detail matematis algoritma Shor

Algoritma Shor menyediakan solusi yang efisien untuk DLP dengan memetakannya ke masalah yang lebih umum dalam teori grup yang dikenal sebagai masalah subgrup tersembunyi (HSP).

Dalam HSP, seseorang diberikan grup aljabar $G$ dan fungsi $f: G \rightarrow X$ dari $G$ ke beberapa himpunan $X$ sedemikian sehingga $f$ konstan pada setiap koset dari beberapa subgrup $H$ dari $G$ (dan berbeda pada koset yang berbeda). Kemudian, tugasnya adalah menentukan $H$. Diketahui bahwa komputer kuantum dapat memecahkan HSP pada grup Abel hingga dalam waktu polinomial dalam $log~|G|$ di mana $|G|$ adalah orde grup.

Dalam kasus DLP integer yang dibahas dalam pelajaran ini, pemetaan ke HSP adalah sebagai berikut:

• Misalkan $p$ adalah sebuah prima dan pertimbangkan DLP yang diberikan oleh $y = g^r~mod~p$ di mana $g$ adalah generator dari $(\mathbb{Z}_p)^{\times}$. Karena $g^{p-1} \equiv 1~mod~p$, $g$ berorde $p-1$.
• Pilih $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ di mana $\mathbb{Z}_{p-1}$ adalah grup bilangan bulat modulo $(p-1)$.
• Pilih $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ yang diberikan sebagai $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ .
• Kernel dari $f$ kemudian merupakan subgrup $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ konstan pada koset $(\delta, 0) + H_0$ dan "menyembunyikan" subgrup $H_0$ yang membentuk HSP.

Mengingat hal di atas, algoritma kuantum Shor untuk DLP integer menggunakan oracle kuantum untuk mengevaluasi fungsi $f$ pada keadaan yang merepresentasikan superposisi seragam atas $G$, kemudian menggunakan transformasi Fourier kuantum dan pengukuran dengan estimasi fase untuk menghasilkan keadaan kuantum yang memungkinkan identifikasi generator $(r, 1)$ dari $H_0$. Dari sini, $r$, logaritma diskret yang menjadi perhatian, dapat diekstrak.

Makalah asli Shor memiliki deskripsi terperinci tentang algoritmanya.

Kriptografi kurva eliptik

Kriptografi kurva eliptik (ECC), yang didasarkan pada matematika kurva eliptik, menawarkan pendekatan yang kuat untuk kriptografi kunci asimetris. ECC dikenal bisa memberikan tingkat keamanan yang serupa dengan metode seperti RSA tetapi dengan kunci yang lebih pendek, sehingga lebih efisien dan sangat cocok untuk sistem dengan sumber daya terbatas, seperti sistem tertanam dan perangkat mobile, di mana penghematan penyimpanan dan komputasi dari ukuran kunci yang lebih kecil sangat diinginkan.

Prinsip dasar kriptografi kurva eliptik

Kurva eliptik umumnya berbentuk $y^2 = x^3 + ax + b$ dengan beberapa sifat menarik.

• Kurva ini simetris secara horizontal. Jadi untuk setiap titik $(x,y)$ pada kurva, refleksinya $(x,-y)$ juga ada pada kurva
• Setiap garis lurus non-vertikal hanya akan memotong kurva di maksimal tiga titik

Gambar 1. Operasi penjumlahan dan penggandaan titik pada kurva eliptik. Sisi 1 mendefinisikan P + Q = -R. Sisi 2 mengilustrasikan penggandaan titik 2Q = -P. Sisi 3 mendefinisikan invers aditif dari suatu titik sebagai refleksinya terhadap sumbu x, yaitu P = -Q

Kriptografi kurva eliptik memanfaatkan serangkaian operasi aritmatika pada titik-titik di kurva. Setiap operasi secara efektif menavigasi ke titik baru pada kurva. Ini adalah proses yang mudah diikuti dalam satu arah, dan dengan ukuran kunci yang lebih pendek lebih efisien dari algoritma lain seperti RSA, tetapi mencoba membalikkannya sangat sulit, sehingga bisa diaplikasikan untuk kriptografi.

Prinsip matematis kriptografi kurva eliptik

Sebuah kurva eliptik di atas medan aljabar $K$ didefinisikan oleh persamaan matematika, umumnya berbentuk $y^2 = x^3 + ax + b$ dengan koefisien $a, b \in K$ dan mendeskripsikan titik-titik $(x, y) \in K \otimes K$ dengan persyaratan tambahan bahwa kurva tidak memiliki kink atau perpotongan diri.

Sifat-sifat kurva eliptik memungkinkan operasi "penjumlahan" dan "perkalian skalar" didefinisikan melibatkan titik-titik pada kurva.

Penjumlahan: Jika $P$ dan $Q$ adalah dua titik pada kurva eliptik, maka $P + Q$ mendeskripsikan titik ketiga yang unik yang diidentifikasi sebagai berikut: Tarik garis yang memotong $P$ dan $Q$ dan temukan titik ketiga, $R$, di mana garis tersebut memotong kurva lagi. Kita kemudian mendefinisikan $P + Q = −R$, titik yang berlawanan dari $R$ yang dicerminkan melalui sumbu $x$ (lihat gambar di bawah). Ketika garis melalui $P, Q$ tidak memotong kurva di $(x, y)$ yang berhingga, kita katakan ia memotong kurva di titik tak hingga $\mathbf{O}$.

Penjumlahan kurva eliptik memenuhi sifat grup aljabar dengan titik tak hingga sebagai identitas aditif.

Penggandaan dan perkalian skalar: Operasi penggandaan titik yang bersesuaian dengan perkalian skalar oleh $2$ diperoleh dengan menetapkan $P = Q$ dalam operasi penjumlahan dan secara grafis melibatkan garis singgung di $P$. Perkalian skalar umum oleh bilangan bulat $n$ yang didefinisikan sebagai $nP = P + P + ...~n$ kali diperoleh dengan penggandaan dan penjumlahan berulang.

Masalah logaritma diskret kurva eliptik

Masalah logaritma diskret kurva eliptik (ECDLP) memiliki banyak kesamaan dengan masalah logaritma diskret yang dibahas sebelumnya, yang didasarkan pada tantangan menemukan faktor.

Operasi perkalian skalar pada kurva eliptik memungkinkan definisi dari masalah logaritma diskret kurva eliptik:

Diberikan titik $P, Q$ pada kurva eliptik sedemikian sehingga $Q = nP$, tentukan $n$.

Masalah ini diketahui tidak bisa diselesaikan pada komputer klasik untuk $n$ yang besar dan menjadi dasar keamanan kriptografi.

Deskripsi matematis ECDLP

Kriptografi kurva eliptik terutama didasarkan pada ECDLP yang dirumuskan pada medan hingga aljabar tertentu. Pada tahun 1999, NIST merekomendasikan sepuluh medan hingga untuk digunakan dalam ECC. Ini adalah:

• Lima medan prima $\mathbb {F} _{p}$ untuk prima $p$ berukuran $\{192, 224, 256, 384, 521\}$ bit.
• Lima medan biner $\mathbb {F} _{2^{n}}$ untuk $n \in \{163, 233, 283, 409, 571\}$.

Dengan pengaturan di atas, sistem kriptografi kunci asimetris berbasis ECC dalam kasus medan prima dapat ditentukan sebagai berikut:

• Pilih $p$ dari daftar nilai yang direkomendasikan NIST untuk menentukan $\mathbb {F} _{p}$.

• Pilih parameter $a, b$ dari kurva eliptik.

• Pilih titik basis $G$ yang "menghasilkan" subgrup siklik pada kurva dengan orde $n$; yaitu, bilangan bulat terkecil sedemikian sehingga $nG = \mathbf{O}$.

• Hitung kofaktor $h = |E(\mathbb {F} _{p})|/n$ di mana $|E(\mathbb {F} _{p})|$ adalah jumlah titik pada kurva. $h$ biasanya merupakan bilangan bulat kecil.

• Parameter domain $(p, a, b, G, n, h)$ memungkinkan spesifikasi kunci asimetris dengan cara ini:

  • Kunci privat adalah bilangan bulat yang dipilih secara acak $d$ dengan bit sebanyak prima $p$. Harus dijaga kerahasiaannya.
  • Kunci publik adalah hasil "mengalikan" titik basis $G$ dengan kunci privat $d$. Ini biasanya dinotasikan sebagai $Q = dG$.

Memulihkan $d$ setara dengan menyelesaikan ECDLP, yang diasumsikan tidak bisa diselesaikan untuk $d$ yang besar. ECDLP oleh karena itu membentuk dasar untuk pertukaran kunci dan skema tanda tangan digital secara analogi langsung dengan skema Diffie-Hellman dan DSA yang didefinisikan di atas $(\mathbb{Z}_p)^{\times}$ yang dibahas sebelumnya.

Pertukaran kunci dengan ECC

Salah satu penggunaan utama ECC adalah dalam protokol pertukaran kunci yang dikenal sebagai Diffie-Hellman kurva eliptik (ECDH). Dalam ECDH, setiap pihak menghasilkan pasangan kunci privat-publik dan kemudian menukar kunci publik. Setiap pihak kemudian menggunakan kunci privat mereka sendiri dan kunci publik pihak lain untuk menghitung rahasia bersama, yang dapat digunakan sebagai kunci untuk enkripsi simetris.

Meskipun relatif mudah untuk melakukan penjumlahan titik pada kurva eliptik dan mendapatkan kunci publik dari kunci privat, secara komputasional tidak memungkinkan untuk membalikkan proses dan mendapatkan kunci privat dari kunci publik. Perilaku "satu arah" ini memberikan keamanan pertukaran kunci ECDH.

Di sini, kita akan mengilustrasikan contoh bagaimana seseorang mungkin melakukan pertukaran kunci ECDH menggunakan Python dan library cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Tanda tangan digital dengan ECC

ECC juga bisa digunakan untuk menghasilkan tanda tangan digital menggunakan Algoritma Tanda Tangan Digital Kurva Eliptik (ECDSA). Dalam ECDSA, penandatangan membuat tanda tangan menggunakan kunci privat mereka, dan orang lain bisa memverifikasi tanda tangan menggunakan kunci publik penandatangan. Sama seperti dengan ECDH, keamanan ECDSA bergantung pada ECDLP. Secara komputasional tidak memungkinkan bagi seseorang untuk memalsukan tanda tangan tanpa akses ke kunci privat penandatangan.

Berikut adalah contoh transaksi tanda-dan-verifikasi sederhana menggunakan ECDSA dengan Python dan cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

Dalam kode di atas, jika seseorang memodifikasi pesan setelah ditandatangani, verifikasi akan gagal, memberikan jaminan keaslian dan integritas untuk pesan tersebut.

Membobol ECDH dan ECDSA

Dengan cara yang analog dengan masalah logaritma diskret bilangan bulat, ECDLP ternyata sulit pada komputer klasik tetapi memiliki solusi yang efisien pada komputer kuantum sekali lagi melalui algoritma Shor. Kami merujuk kamu ke literatur terbaru untuk diskusi terkait generalisasi algoritma Shor ke kasus ECDLP.

Ringkasan

Dalam pelajaran ini, kita mulai dengan melihat karakteristik utama kriptografi kunci asimetris (AKC) dan mendiskusikan pertimbangan keamanan dasar yang mendasari sistem kripto asimetris. Khususnya, kita memperkenalkan dua aplikasi utama AKC — yaitu, pertukaran kunci dan tanda tangan digital — yang keduanya merupakan komponen penting dalam komunikasi berbasis internet modern.

Kita kemudian melihat sistem kriptografi RSA, yang sejak tahun 1970-an, telah terbukti sangat berharga untuk mengamankan komunikasi digital modern dengan memungkinkan pertukaran kunci dan tanda tangan digital dalam kerangka yang sederhana dan serbaguna. Keamanan kriptografi RSA terhadap komputasi klasik didasarkan pada kesulitan memfaktorkan bilangan bulat besar dan membutuhkan ukuran kunci dalam kisaran 2048 bit untuk memastikan bilangan bulat yang digunakan dalam aplikasi praktis cukup besar untuk menahan faktorisasi.

Kita kemudian melihat pertukaran kunci Diffie-Hellman (DH) dan Algoritma Tanda Tangan Digital (DSA). Keamanan skema ini dipredikatkan pada masalah logaritma diskret bilangan bulat (DLP), kunci privat yang secara komputasional sulit diekstrak dari kunci publik, tanpa solusi waktu polinomial pada komputer klasik. Penggunaan kunci acak dan unik memberikan keamanan tambahan terhadap serangan. Baik varian medan hingga bilangan bulat maupun kurva eliptik dari protokol DH dan DSA saat ini banyak digunakan di berbagai protokol komunikasi digital modern seperti TLS, SSH, dan sebagainya.

Terakhir, kita melihat kriptografi kurva eliptik. Dengan ukuran kunci yang efisien dan sifat keamanan yang kuat, saat ini merupakan pilihan yang sangat baik untuk banyak aplikasi kriptografi, dari pertukaran kunci hingga tanda tangan digital.

Semua algoritma ini terpapar serangan dari algoritma kuantum, karena solusi dapat dikembangkan untuk menyelesaikan masalah matematika yang menjadi premis dalam desainnya. Salah satu contohnya adalah algoritma Shor. Oleh karena itu, algoritma-algoritma ini perlu digantikan oleh sistem kripto asimetris yang aman secara kuantum yang lebih tahan terhadap serangan dari kuantum — sekaligus tetap aman dengan algoritma klasik. Masalah matematika yang mereka andalkan dapat diselesaikan secara efisien oleh komputer kuantum, sehingga memerlukan pengembangan sistem kripto asimetris yang aman secara kuantum yang dapat menahan serangan kuantum sekaligus mempertahankan keamanan klasik.

Pelajaran mendatang akan melihat sistem kripto yang aman secara kuantum dan mendiskusikan pendekatan yang diperlukan untuk mempertahankan keamanan kriptografi.