Kriptografi kunci asimetrik

Dalam pelajaran ini kita akan melihat kriptografi kunci asimetrik yang menjadi asas kepada banyak interaksi rangkaian selamat pada hari ini.

Menjelang akhir pelajaran ini, kita akan telah membincangkan:

Apa itu kriptografi kunci asimetrik
Penggunaan kriptografi kunci asimetrik, termasuk pertukaran kunci dan tandatangan digital
Keselamatan kriptografi kunci asimetrik secara umum
Butiran lanjut tentang algoritma RSA, DSA dan Lengkung Eliptik serta keselamatannya
Beberapa contoh kod Python yang menunjukkan cara algoritma ini berfungsi dalam praktik
Ancaman kepada algoritma ini daripada komputer klasik mahupun komputer kuantum

Pengenalan kepada kriptografi kunci asimetrik

Seperti yang kita pelajari dalam pelajaran lepas, kriptografi kunci simetrik sangat pantas dan cekap untuk melindungi maklumat, tetapi ia mempunyai beberapa had:

Apabila bilangan pihak yang ingin bertukar maklumat selamat bertambah, bilangan kunci yang diperlukan meningkat secara kombinatorial. Ia tidak menyediakan mekanisme untuk mengedarkan kunci ini secara selamat antara penghantar dan penerima.
Tiada peruntukan untuk tanpa penolakan. Mana-mana pihak boleh menyahsulit atau menyulitkan mesej tanpa cara untuk menjamin bahawa mesej telah diterima atau daripada mana ia berasal

Penyelesaian kepada kedua-dua masalah ini disediakan oleh kriptografi kunci asimetrik (AKC), yang juga dikenali sebagai kriptografi kunci awam (PKC), yang oleh itu membentuk tonggak keselamatan digital moden.

Kriptografi kunci asimetrik (AKC) melibatkan penggunaan sepasang kunci — satu awam, satu peribadi. Kunci awam dan kunci peribadi dipautkan secara kriptografi dan biasanya dijana pada masa yang sama sebagai pasangan kunci menggunakan algoritma matematik khusus. Kunci awam, seperti yang dicadangkan oleh namanya, kemudiannya dimaksudkan untuk diedarkan secara bebas, manakala kunci peribadi disimpan secara rahsia oleh pihak yang menjana pasangan kunci. Keselamatan komunikasi yang menggunakan pasangan kunci asimetrik terjamin selagi kunci peribadi kekal sulit.

Rajah 1. Penyulitan Kunci Asimetrik

Rajah 1. Penyulitan Kunci Asimetrik

AKC menawarkan beberapa fungsi berguna, seperti:

Penyulitan dan penyahsulitan untuk membolehkan kerahsiaan komunikasi.
Tandatangan digital untuk memastikan kesahihan, integriti, dan tanpa penolakan.
Pertukaran kunci selamat untuk memudahkan penggunaan sistem kripto simetrik seterusnya.

Dalam aplikasi moden, AKC digunakan terutamanya untuk tandatangan digital dan pertukaran kunci selamat. Dalam pelajaran ini, kita memperkenalkan dua fungsi utama ini, kemudian kita membincangkan beberapa variasi protokol kriptografi untuk fungsi-fungsi ini.

Pertukaran kunci dengan kriptografi kunci asimetrik

Salah satu masalah asas dalam kriptografi ialah pertukaran kunci secara selamat. Sebagai contoh, jika dua pihak ingin menggunakan penyulitan simetrik, kedua-dua pihak memerlukan kunci yang sama untuk menyulitkan dan menyahsulit mesej. Tetapi bagaimana mereka boleh menukar kunci itu secara selamat? Kriptografi kunci asimetrik menangani perkara ini melalui mekanisme pertukaran kunci interaktif dan bukan interaktif.

Pertukaran kunci interaktif

Protokol pertukaran kunci interaktif merujuk kepada kaedah di mana dua pihak bekerjasama untuk mencipta kunci rahsia dikongsi melalui saluran komunikasi yang tidak selamat. Kunci rahsia dikongsi ini kemudiannya boleh digunakan untuk tugas penyulitan dan penyahsulitan simetrik.

Yang paling terkenal dalam kalangan protokol sedemikian ialah algoritma Diffie-Hellman (DH), yang direka khusus untuk memudahkan pertukaran kunci. Dalam protokol ini, setiap pihak menjana sepasang kunci (awam dan peribadi) dan menyiarkan kunci awam mereka. Kemudian setiap pihak menggunakan kunci peribadi mereka sendiri dan kunci awam pihak lain untuk menjana kunci rahsia dikongsi. DH menggunakan prinsip aritmetik modular untuk memastikan kedua-dua pihak akhirnya mendapat rahsia dikongsi yang sama walaupun setiap pihak hanya mempunyai akses kepada kunci awam pihak lain.

Sistem kripto moden berdasarkan kriptografi lengkung eliptik (ECC) memperluaskan konsep ini dengan pertukaran kunci Diffie-Hellman lengkung eliptik (ECDH). ECDH berfungsi serupa dengan DH tetapi menggunakan sifat-sifat lengkung eliptik, menghasilkan sistem yang lebih selamat dan cekap.

Rajah 2. Protokol Pertukaran Kunci

Rajah 2. Protokol Pertukaran Kunci

Pertukaran kunci bukan interaktif

Tidak seperti protokol pertukaran kunci seperti DH dan ECDH yang bersifat interaktif, memerlukan komunikasi berulang-alik untuk menentukan kunci simetrik, AKC juga menyediakan cara bukan interaktif untuk mewujudkan kunci rahsia dikongsi. Dalam skim sedemikian, satu pihak menjana sepasang kunci (awam dan peribadi) dan berkongsi kunci awam dengan pihak lain. Pihak kedua ini kemudiannya menjana kunci simetrik rawak, menyulitkannya dengan kunci awam yang diterima, dan menghantar semula kepada pihak pertama. Pihak pertama menggunakan kunci peribadi mereka untuk menyahsulit mesej yang diterima, dengan itu mendapatkan kunci simetrik dikongsi. Skim ini bersifat bukan interaktif dalam erti kata kunci simetrik ditentukan oleh satu pihak dan hanya dikomunikasikan secara selamat kepada pihak lain dalam bentuk tersulitkan.

Pertimbangan penting dalam pertukaran kunci bukan interaktif berkaitan dengan perbezaan panjang dalam bit antara kunci simetrik yang ingin ditukar oleh pihak-pihak dan saiz mesej yang disyorkan dalam AKC. Biasanya, kunci simetrik moden berada dalam julat 128-256 bit, manakala sistem kripto kunci asimetrik seperti RSA berfungsi dengan saiz mesej sekitar 1024-4096 bit. Oleh itu, apabila menggunakan AKC untuk menghantar kunci simetrik, demi keselamatan ia tetap perlu dikodkan ke dalam mesej 1024-4096 bit yang lebih panjang. Ini boleh dicapai melalui dua pendekatan:

Pertukaran kunci berasaskan padding: Dalam pendekatan ini, kunci simetrik yang lebih pendek (128-256 bit) dijana dahulu kemudian skim padding boleh-balik yang dipersetujui seperti OAEP digunakan untuk membenamkannya ke dalam mesej yang lebih panjang (1024-4096 bit). Mesej yang lebih panjang ini disulitkan menggunakan AKC dan disiarkan sebagai ciphertext. Penerima mula-mula menyahsulit ciphertext kemudian mengalihkan padding untuk mengekstrak kunci simetrik yang lebih pendek.
Mekanisme enkapsulasi kunci (KEM): Dengan pertukaran kunci berasaskan KEM, mesej teks biasa rawak yang panjang (1024-4096 bit) dijana terlebih dahulu, dari mana kunci simetrik yang lebih pendek (128-256 bit) boleh diekstrak menggunakan fungsi terbitan kunci (KDF) yang dipersetujui. Teks biasa yang lebih panjang disulitkan menggunakan AKC dan disiarkan kepada penerima sebagai ciphertext. Penerima menyahkod ciphertext menggunakan kunci peribadi mereka kemudian menggunakan KDF untuk mengekstrak kunci simetrik yang lebih pendek (128-256 bit). Sistem kripto popular seperti RSA, dengan keupayaannya untuk menyulitkan data secara langsung, boleh digunakan untuk melaksanakan KEM.

Rajah 3. Mekanisme Enkapsulasi Kunci

Rajah 3. Mekanisme Enkapsulasi Kunci

Tandatangan digital dengan kriptografi kunci asimetrik

Tandatangan digital ialah satu lagi aplikasi kriptografi kunci asimetrik yang berkuasa. Ia menyediakan pengesahan, integriti, dan tanpa penolakan yang didayakan oleh hakikat bahawa dalam AKC, entiti memiliki kunci peribadi yang unik. Idea asas yang mendasari protokol tandatangan ialah penghantar mesej selamat akan menandatangani secara digital mesej tersebut menggunakan kunci peribadi unik mereka. Penerima kemudiannya akan mengesahkan tandatangan digital menggunakan kunci awam penghantar. Dalam AKC, tandatangan digital boleh dilaksanakan dengan menggunakan algoritma yang direka khusus untuk tujuan itu atau dengan menggunakan sistem kripto generik.

Rajah 4. Tandatangan digital dengan kriptografi kunci asimetrik

Rajah 4. Tandatangan digital dengan kriptografi kunci asimetrik

Algoritma tandatangan digital khusus

Pada masa ini, Piawaian Pemprosesan Maklumat Persekutuan AS (FIPS) untuk tandatangan digital ialah skim khusus yang dinamakan mudah Algoritma Tandatangan Digital (DSA). Agak serupa dengan protokol Diffie-Hellman, DSA menggunakan sifat-sifat algebra daripada eksponen modular dan songsangan pendaraban untuk penjanaan dan pengesahan tandatangan.

Algoritma tandatangan digital lengkung eliptik (ECDSA) ialah varian ECC bagi DSA, menyediakan fungsi yang sama tetapi dengan kunci yang jauh lebih pendek. Ini menghasilkan kecekapan yang lebih baik, menjadikannya pilihan popular untuk sistem dengan kekangan sumber.

Kedua-dua DSA dan ECDSA akan diilustrasikan dengan lebih terperinci kemudian.

Skim tandatangan digital menggunakan sistem kripto generik

Selain daripada algoritma khusus, tandatangan digital juga boleh dijana menggunakan sistem kripto asimetrik generik, seperti RSA.

RSA, yang akan dibincangkan secara terperinci dalam bahagian kemudian, turut mengeksploitasi songsangan pendaraban modular dan pemangkatan modular sebagai operasi asas tetapi menggabungkannya dalam urutan yang berbeza daripada DSA. Dalam RSA, penandatangan biasanya mencipta hash mesej kemudian menyulitkan hash tersebut dengan kunci peribadi mereka, mencipta tandatangan digital. Mana-mana pihak kemudiannya boleh mengesahkan tandatangan ini dengan menyahsulitnya menggunakan kunci awam penandatangan dan membandingkannya dengan mesej yang di-hash.

Aplikasi kriptografi kunci asimetrik

Kriptografi kunci asimetrik adalah merata-rata dalam aplikasi teknologi digital moden. Fungsi asas AKC yang diterangkan di atas membentuk blok binaan banyak protokol aplikasi peringkat lebih tinggi, termasuk:

Komunikasi internet: Komunikasi selamat melalui internet, seperti HTTPS, sangat bergantung pada kriptografi kunci asimetrik. Transport Layer Security (TLS) dan pendahulunya, Secure Sockets Layer (SSL), menggunakan kriptografi kunci asimetrik semasa proses jabat tangan awal untuk mewujudkan kunci simetrik, yang kemudiannya digunakan untuk selebihnya sesi komunikasi.
Pengesahan: Kriptografi kunci asimetrik digunakan untuk mencipta tandatangan digital, membolehkan entiti mengesahkan dokumen atau mesej digital sebagai datang daripada penghantar tertentu. Ini digunakan dalam banyak senario, daripada mengesahkan kemas kini perisian kepada kontrak digital yang mengikat secara undang-undang.
Penyulitan e-mel: Protokol penyulitan e-mel seperti PGP (Pretty Good Privacy) dan alternatif sumber terbukanya GPG (GNU Privacy Guard) menggunakan kriptografi kunci asimetrik untuk memastikan hanya penerima yang dimaksudkan boleh membaca kandungan e-mel.
Secure shell (SSH): SSH ialah protokol untuk log masuk jauh yang selamat dan perkhidmatan rangkaian selamat lain melalui rangkaian yang tidak selamat. Ia menggunakan kriptografi kunci asimetrik untuk mengesahkan pelayan kepada klien dan, secara pilihan, klien kepada pelayan.
VPN (rangkaian peribadi maya): Penyulitan kunci asimetrik digunakan untuk mewujudkan sambungan selamat dalam VPN, memastikan komunikasi selamat melalui rangkaian awam.
Blokchain dan mata wang kripto: Teknologi blokchain, termasuk Bitcoin dan Ethereum, menggunakan kriptografi kunci asimetrik. Sebagai contoh, pemilikan Bitcoin diwujudkan melalui tandatangan digital menggunakan kriptografi kunci asimetrik.
Pihak berkuasa sijil: Kriptografi kunci asimetrik digunakan oleh pihak berkuasa sijil (CA) untuk mengeluarkan dan menandatangani sijil digital, yang digunakan dalam komunikasi TLS, penandatanganan kod, penyulitan e-mel, dan lain-lain. Sijil digital mengikat kunci awam kepada entiti tertentu (contohnya, seseorang atau pelayan).

Rajah 5. Mengeluarkan dan menandatangani sijil digital menggunakan kriptografi kunci asimetrik

Rajah 5. Mengeluarkan dan menandatangani sijil digital menggunakan kriptografi kunci asimetrik

Keselamatan kriptografi kunci asimetrik

Beberapa gagasan kriptografi bergabung untuk membolehkan kriptografi kunci asimetrik yang selamat, termasuk:

Kerahsiaan kunci peribadi: Keperluan keselamatan paling asas AKC ialah kunci peribadi kekal rahsia. Walau bagaimanapun, memandangkan kunci peribadi mesti dipautkan secara matematik kepada kunci awam, kerahsiaan kunci peribadi juga memerlukan bahawa adalah tidak mungkin secara pengiraan untuk mendapatkan kunci peribadi daripada pengetahuan tentang kunci awam. Skim penjanaan kunci dalam AKC bergantung kepada masalah matematik yang sukar secara pengiraan untuk memudahkan keperluan ini.

Fungsi perangkap Dalam AKC, operasi penyulitan dan penyahsulitan melibatkan kunci pelengkap berbeza daripada pasangan kunci tunggal. Ciphertext yang dijana oleh penyulitan menggunakan salah satu kunci (contohnya kunci awam) mesti tidak dapat difahami oleh pihak ketiga manakala mudah disahsulit oleh pemegang kunci pelengkap (dalam kes ini kunci peribadi). Dengan kata lain, penyulitan sepatutnya menyerupai fungsi sehala perangkap supaya pihak ketiga tidak boleh membalikkan operasi dan memulihkan teks biasa tetapi kunci peribadi menyediakan perangkap rahsia yang membolehkan penyongsangan mudah. Algoritma AKC popular menggunakan pemangkatan modular untuk mewujudkan tingkah laku fungsi sehala perangkap.

Kerawakan: Proses penjanaan kunci juga perlu mengeksploitasi kerawakan untuk memastikan kunci tidak dapat diramalkan, kerana sebarang corak atau kebolehramalan dalam penjanaan kunci boleh dieksploitasi oleh penyerang. Kerawakan juga digunakan untuk padding semasa penyulitan untuk menjana ciphertext yang selamat secara semantik dan dalam skim tandatangan digital untuk menghasilkan tandatangan unik walaupun mesej yang sama ditandatangani beberapa kali. Atas sebab ini, penggunaan penjana nombor rawak yang kuat adalah bahagian penting AKC.

Saiz kunci besar: Seperti dalam kes SKC, saiz kunci besar memastikan perlindungan terhadap serangan brute force. Walau bagaimanapun, memandangkan saiz kunci besar juga meningkatkan kos pengiraan proses penyulitan dan penyahsulitan, penyelesaian optimum perlu mengimbangi pertimbangan keselamatan dan kecekapan. Jadual berikut menunjukkan saiz kunci tipikal untuk pelbagai protokol dan aplikasi kriptografi kunci asimetrik:

Protokol	Saiz Kunci Tipikal (dalam bit)	Aplikasi
RSA	1024 (ditamatkan), 2048, 3072, 4096	Penyulitan, tandatangan digital
DSA	1024 (ditamatkan), 2048, 3072	Tandatangan digital
DH	2048, 3072, 4096	Pertukaran kunci
ECDH	224, 256, 384, 521	Pertukaran kunci
ECDSA	224, 256, 384, 521	Tandatangan digital

Infrastruktur kunci awam: Dalam AKC, kunci peribadi mesti disimpan secara rahsia oleh pemilik manakala kunci awam dikongsi. Perlu ada mekanisme selamat untuk mengurus dan mengedarkan kunci awam ini antara pengguna. Infrastruktur kunci awam (PKI) menyediakan cara untuk melakukan ini menggunakan sijil digital. Sijil digital menyediakan bukti identiti pemilik kunci awam dan dikeluarkan oleh pihak berkuasa yang dipercayai seperti pihak berkuasa sijil (yang merupakan sebahagian daripada PKI). Oleh itu, PKI memainkan peranan penting dalam keselamatan aplikasi moden menggunakan AKC dengan membolehkan pengurusan kunci berskala besar (dengan mencipta, mengurus, mengedarkan dan membatalkan sijil digital).

Risiko keselamatan kepada kriptografi kunci asimetrik

Seperti yang digariskan dalam jadual di atas, algoritma kunci asimetrik moden seperti RSA biasanya menggunakan saiz kunci yang jauh lebih besar daripada rakan sejawatan kunci simetrik yang biasa digunakan seperti AES-128. Malah protokol berasaskan ECC (ECDH dan ECDSA) yang mempunyai saiz kunci lebih kecil menggunakan sekurang-kurangnya 224 bit untuk kunci. Ini seterusnya bermakna bahawa serangan brute force yang melibatkan carian menyeluruh ruang kunci peribadi untuk mengenal pasti kunci yang betul adalah tidak dapat dilaksanakan secara pengiraan dalam masa terdekat. Ini tetap benar walaupun komputer kuantum digunakan untuk tugas ini. Oleh itu, serangan terhadap AKC biasanya menumpukan kepada mengeksploitasi kelemahan potensi lain sistem kripto tertentu. Beberapa mod serangan yang didokumentasikan dengan baik menyasarkan:

Kelemahan algoritma dengan menggunakan cara matematik dan pengiraan yang canggih untuk menjejaskan andaian kekerasan yang digunakan untuk merumuskan algoritma kunci asimetrik. Sebagai contoh, keselamatan RSA adalah bergantung kepada kesukaran memfaktorkan nombor perdana besar, dan kemajuan pengiraan terkini telah membolehkan pemfaktoran berjaya kunci RSA 829-bit. Oleh itu, RSA 1024-bit pada masa ini telah ditamatkan. Seperti yang akan dibincangkan kemudian, risiko utama yang ditimbulkan oleh komputer kuantum kepada AKC juga termasuk dalam kategori ini.
Kerawakan tidak sempurna, yang boleh membawa kepada kelemahan dalam proses penjanaan kunci. Sebagai contoh, jika penjana nombor rawak yang digunakan untuk mencipta kunci adalah cacat dan menjana kunci yang tidak benar-benar rawak, penyerang mungkin dapat meramalkan kunci tersebut.
Kelemahan pelaksanaan seperti ralat dalam pelaksanaan algoritma kriptografi yang secara tidak sengaja mendedahkan maklumat tentang kunci. Sebagai contoh, padding yang salah berpotensi mendedahkan butiran tentang kunci.
Saluran sisi yang merujuk kepada kebocoran maklumat daripada sistem fizikal yang menjalankan kriptografi. Kebocoran sedemikian boleh dalam bentuk maklumat masa, penggunaan kuasa, atau bahkan bunyi, yang boleh dieksploitasi dalam apa yang dipanggil serangan saluran sisi. Sebagai contoh, menganalisis berapa lama operasi kriptografi mengambil masa untuk dilaksanakan boleh mendedahkan bilangan '1' dalam kunci binari. Kebocoran yang kelihatan tidak berbahaya ini secara ketara mempersempitkan ruang carian, mendedahkan penyelesaian yang berpotensi kepada masalah yang pada mulanya kelihatan tidak dapat diatasi.
Pertukaran kunci dengan memintas kunci semasa pertukaran, seperti dalam serangan man-in-the-middle (MITM). Protokol DH terdedah kepada serangan MITM jika langkah pengesahan tambahan tidak dimasukkan.
Penyimpanan kunci dengan bertujuan mencuri kunci daripada storan yang tidak selamat. Ini termasuk serangan fizikal seperti manipulasi atau kecurian peranti storan.

Mengamankan sistem kripto kunci asimetrik terhadap pelbagai serangan yang mungkin adalah oleh itu satu tugas yang signifikan melibatkan pertimbangan matematik, perkakasan, perisian, logistik, dan perundangan.

RSA

Algoritma RSA (Rivest-Shamir-Adleman) ialah salah satu sistem kripto kunci awam yang pertama dan digunakan secara meluas untuk penghantaran data selamat. Ia adalah sistem kripto yang serba guna kerana ia menyediakan operasi yang diperlukan untuk membolehkan penyulitan, penyahsulitan, tandatangan digital, dan pertukaran kunci dalam kerangka yang sama.

Dalam bahagian ini, kita akan mengilustrasikan kriptografi kunci asimetrik (AKC) menggunakan RSA melalui contoh mudah.

Kita akan menggunakan senario standard dua pihak, Alice dan Bob, yang ingin berkomunikasi secara selamat menggunakan AKC.

Algoritma RSA

Algoritma RSA asas melibatkan empat operasi: penjanaan kunci, pengedaran kunci, penyulitan, dan penyahsulitan:

Penjanaan kunci:

Kunci awam dan peribadi dijana berdasarkan prinsip matematik sekitar nombor perdana, di mana mengira ia adalah mudah, tetapi sebaliknya adalah sukar.

Kita akan merujuk kepada ini:
- Kunci awam: $(e, n)$
- Kunci peribadi: $(d, n)$
Perhatikan bahawa $n$ adalah biasa kepada kedua-dua kunci awam dan kunci peribadi, dan dikenali sebagai modulus. Kita akan perlu menggunakannya kemudian.

Butiran matematik

Pilih dua nombor perdana berbeza, $p$ $p$ dan $q$ $q$ .
- dipilih secara rawak (untuk keselamatan).
- Ia sepatutnya serupa dalam magnitud, tetapi berbeza dalam panjang beberapa digit, untuk menjadikan pemfaktoran lebih sukar.
- Nombor perdana boleh dipilih secara cekap menggunakan ujian keprimeaan.
Kira $n = p*q$ $n = p * q$ .
- $n$ ialah modulus untuk kedua-dua kunci awam dan peribadi.
Kira fungsi totient $φ$ $(n) = (p-1)*(q-1)$ $(n) = (p - 1) * (q - 1)$ .
- Totient dimaksudkan untuk disimpan secara rahsia dan biasanya dibuang selepas penjanaan kunci.
Pilih integer $e$ $e$ supaya $1 < e <$ $1 < e <$ $φ$ $(n)$ $(n)$ dan $gcd$ $(e,$ $(e,$ $φ$ $(n)) = 1$ $(n)) = 1$ .
- iaitu, $e$ dan $φ$ $(n)$ sepatutnya koprima.
- Nombor $e$ ini membentuk eksponen kunci awam dan biasanya dipilih sebagai nombor kecil untuk kecekapan pengiraan.
- Nombor perdana $65537 = 2^{16} + 1$ sering digunakan.
- Kira $d$ $d$ untuk memenuhi hubungan kekongruenan $d*e ≡ 1 ($ $d * e \equiv 1 ($ $mod$ $φ$ $(n))$ $(n))$ .
  - Iaitu, $d$ ialah songsangan pendaraban $e$ modulo $φ$ $(n)$ .
  - Ini dikira dengan lebih cekap menggunakan algoritma Euclidean lanjutan.
  - Nombor $d$ ini ialah eksponen kunci peribadi.
Kunci awam terdiri daripada $(e, n)$ , dan kunci peribadi ialah $(d, n)$ .

Pengedaran kunci:
- Kunci awam $(e, n)$ dijadikan awam kepada mereka yang mungkin ingin menghantar mesej
- Kunci peribadi $(d, n)$ disimpan secara rahsia.
Penyulitan:
- Alice ingin menghantar mesej $M$ kepada Bob. Dalam kes ini satu integer mudah
- Alice menggunakan kunci awam Bob $(e, n)$ untuk menyulitkan mesej menjadi ciphertext $C$
Butiran matematik
- $M$ ialah integer $0 ≤ M < n$ .
- $C ≡ M^e (mod n)$ , di mana $C$ ialah ciphertext.
Penyahsulitan:
- Bob menerima ciphertext $C$
- Bob menggunakan kunci peribadinya $(d, n)$ untuk menyahsulit mesej semula menjadi mesej $M$
Butiran matematik
- $M ≡ C^d (mod n)$ .

Ini adalah garis besar asas RSA. Dalam praktik, skim padding yang lebih canggih digunakan kepada teks biasa $M$ sebelum penyulitan untuk memastikan teks biasa yang sama menghasilkan ciphertext yang berbeza. Ini mencegah pelbagai serangan yang mungkin terhadap pelaksanaan naif RSA dan membolehkan keselamatan semantik.

Ilustrasi RSA dalam Python

Dalam sel kod berikut, kita mengilustrasikan contoh mudah algoritma RSA menggunakan integer kecil kemudian menunjukkan pengedaran kunci praktikal dan aplikasi tandatangan digital menggunakan pustaka Python yang melaksanakan RSA.

nota

Nota: Dalam bahagian ini kita akan menunjukkan pengiraan matematik secara terperinci sebagai sebahagian daripada kod Python

Penjanaan kunci RSA

Mari kita lalui contoh mudah algoritma RSA menggunakan nombor perdana kecil.

Kita perlu dapat mengira pembahagi sepunya terbesar dua integer, kerana ia diperlukan untuk menguji sama ada dua integer adalah koprima.

Kita akan menerangkan satu cara mudah untuk mengira ini, tetapi adalah lebih cekap dengan integer 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)

Fasa pertama aliran kerja RSA ialah penjanaan kunci. Ini dimulakan dengan memilih dua nombor perdana, yang dimaksudkan untuk disimpan secara rahsia oleh entiti yang menjana kunci.

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

Seterusnya, modulus $n$ , yang merupakan hasil darab dua perdana yang dipilih, dikira. Modulus ini akan diterbitkan sebagai sebahagian daripada kunci awam.

# 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)$ dikira seterusnya, kerana ia diperlukan untuk operasi songsangan pendaraban modular yang digunakan untuk menentukan kunci dalam RSA. $phi$ juga disimpan secara rahsia dan biasanya dibuang selepas penjanaan 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 kini bersedia untuk mengira kunci awam dan peribadi. Dalam RSA, setiap satunya ditentukan oleh tupel dua integer. Entri pertama dalam setiap tupel ialah integer yang berbeza, dan entri kedua ialah modulus $n$ yang biasa kepada kedua-dua kunci.

Entri pertama dalam kunci awam boleh menjadi mana-mana integer yang lebih besar daripada 1 yang koprima kepada $phi$ . Dua integer adalah koprima jika pembahagi sepunya terbesar mereka ialah 1. Jadi kita menggunakan fungsi math.gcd untuk mencari integer $e$ yang koprima kepada $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 peribadi memerlukan integer $d$ , yang merupakan songsangan pendaraban $e$ modulo $phi$ ; iaitu, ia memenuhi hubungan kekongruenan $d*e\equiv 1 \pmod{\varphi(n)}$ . Untuk ilustrasi mudah ini di mana kita berurusan dengan integer kecil, kita boleh hanya mengulang ke atas integer positif untuk mencari $d$ yang sesuai. Dalam tetapan sebenar, algoritma Euclidean lanjutan yang cekap secara pengiraan 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 kini membentuk tupel $(e, n), (d, n)$ , yang membentuk kunci awam dan peribadi masing-masing. Kunci awam kemudiannya diterbitkan, manakala kunci peribadi disimpan secara rahsia.

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

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

Penyulitan dan penyahsulitan dalam RSA menggunakan operasi pemangkatan modular. Selanjutnya, kunci awam dan peribadi adalah saling melengkapi dalam erti kata sama ada boleh digunakan untuk menyulitkan mesej yang satu lagi boleh menyahsulitnya.

Di sini kita mengilustrasikan kes di mana kunci awam $(e,n)$ digunakan untuk penyulitan dan kunci peribadi $(d, n)$ digunakan untuk penyahsulitan dengan mentakrifkan fungsi Python untuk setiap operasi.

Kita kemudiannya menyulitkan dan menyahsulit mesej integer $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)

Walaupun integer kecil yang digunakan di atas berguna untuk dengan mudah menggariskan idea teras dalam algoritma RSA, dalam aplikasi sebenar RSA memerlukan penggunaan integer yang sangat besar. Sebagai contoh, RSA 2048-bit melibatkan penggunaan modulus $n$ yang panjang 2048 bit, setara integer perpuluhan yang mana adalah sekitar 10 $^616$ . Nombor-nombor yang benar-benar luar biasa besar ini diperlukan untuk keselamatan praktikal RSA.

Pertukaran kunci simetrik dengan RSA

Seperti yang dibincangkan sebelumnya, AKC membolehkan dua pihak yang ingin berkomunikasi untuk mewujudkan secara selamat rahsia dikongsi, yang boleh digunakan, sebagai contoh, sebagai kunci rahsia untuk penyulitan simetrik teks biasa pukal yang seterusnya.

Mari kita pertimbangkan senario berikut. Alice dan Bob ingin menggunakan SKC untuk menyulitkan dan menyahsulit mesej. Walau bagaimanapun, sebelum proses ini boleh dimulakan, mereka perlu bersetuju dengan kunci rahsia yang sama. Satu pilihan ialah satu pihak — katakan Alice — menjana kunci rahsia kemudian menghantarnya secara selamat kepada Bob. Untuk mencapai pemindahan selamat ini, Alice memutuskan untuk menggunakan RSA sebagai mekanisme enkapsulasi kunci (KEM).

Ini melibatkan langkah-langkah berikut:

Pertama, Alice menjana kunci simetrik rawak, yang dia ingin kongsi dengan Bob.
Kemudian, Bob menjana pasangan kunci asimetrik dan menjadikan kunci awamnya tersedia pada saluran yang sesuai.
Seterusnya, Alice menggunakan kunci awam Bob untuk menyulitkan kunci simetrik, dengan itu mengenkapsulasikannya dalam ciphertext.
Kemudian, Alice menyiarkan ciphertext melalui saluran yang boleh dipercayai tetapi tidak semestinya selamat.
Akhirnya, Bob menerima ciphertext dan menyahsulitnya menggunakan kunci peribadinya. Dia kini mempunyai akses kepada kunci simetrik yang dijana oleh Alice.

Rajah 1. Pertukaran kunci simetrik dengan RSA

Rajah 1. Pertukaran kunci simetrik dengan RSA

Contoh pertukaran kunci berasaskan padding dalam Python

Aliran kerja praktikal menggunakan RSA untuk pertukaran kunci bukan interaktif berasaskan padding kini diilustrasikan menggunakan pustaka Python cryptography.

Import modul yang diperlukan daripada pustaka Python cryptography. Jika diperlukan, pustaka ini boleh dipasang menggunakan perintah pip install cryptography.

Alice kemudiannya menjana kunci rahsia rawak, yang dia ingin hantar kepada 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 daripada pustaka cryptography, Bob menjana pasangan kunci dan kemudiannya menyiarkan kunci awamnya. Sesiapa sahaja boleh memintas kunci awam dan membaca nombor awam $(e,n)$ yang membentuk kunci.

# 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 ketika ini, kita andaikan Alice telah menerima kunci awam yang disiarkan oleh Bob. symmetric_key Alice di atas kini boleh disulitkan menggunakan kunci awam Bob untuk menghasilkan ciphertext. Dalam tetapan sebenar, Alice juga akan menggunakan kaedah padding tambahan seperti OAEP untuk memastikan keselamatan semantik 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 kemudiannya menyiarkan ciphertext melalui saluran terbuka, yakin bahawa hanya Bob dengan kunci peribadi yang sepadan akan dapat menyahsulitnya. Kita andaikan Bob telah menerima ciphertext dan kini boleh menyahsulitnya menggunakan kunci peribadi sulit miliknya.

# 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 ketika ini, Alice dan Bob kedua-duanya mempunyai akses kepada kunci simetrik rahsia, yang boleh mereka gunakan untuk aplikasi SKC.

Simulasi Mekanisme Enkapsulasi Kunci dengan RSA dalam Python

Dalam aliran kerja berikut, kita menggambarkan penggunaan RSA untuk mensimulasikan Mekanisme Enkapsulasi Kunci (KEM) di mana rahsia rawak yang cukup panjang ditukar secara selamat dan kemudiannya ditukarkan kepada rahsia bersama yang sesuai panjangnya menggunakan KDF.

Sekali lagi Alice dan Bob ingin mewujudkan rahsia bersama secara tidak interaktif dan Alice adalah pihak yang memutuskan rahsia mana yang hendak digunakan.

Kita mulakan dengan mengimport beberapa perpustakaan Python yang diperlukan.

Bob kemudian menjana pasangan kunci RSA-nya dan menyiarkan kunci awamnya.

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 mula-mula menjana rahsia rawak yang panjang dari mana rahsia bersama akhirnya akan diterbitkan. Dalam KEM yang tulen, rahsia panjang itu akan menjadi elemen rawak daripada struktur algebra yang mendasari sistem kriptografi. Dalam kes RSA 2048-bit, ini akan menjadi integer rawak modulo modulus RSA 2048-bit. Oleh itu, KEM yang tulen tidak memerlukan pengisi tambahan, tetapi dalam contoh ini kita hanya mensimulasikan KEM menggunakan RSA dan perpustakaan cryptography memerlukan penggunaan pengisi semasa penyulitan dengan RSA. Jadi kita akan menggunakan rahsia panjang yang agak lebih pendek namun jauh lebih panjang daripada kunci AES 256-bit standard.

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

Seterusnya Alice menyulitkan rahsia panjang itu menggunakan kunci awam Bob dan rahsia yang disulitkan itu disampaikan kepada 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 menyahsulit rahsia yang disulitkan yang diterima daripada Alice menggunakan kunci peribadinya.

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")

Akhir sekali, Alice dan Bob masing-masing secara berasingan menggunakan Fungsi Penurunan Kunci (KDF) yang telah dipersetujui ke atas rahsia panjang untuk mendapatkan kunci simetri.

Perhatikan bahawa proses ini melibatkan protokol pencincangan dan penggunaan garam rawak yang memastikan keunikan dan ketidakbolehramalan kunci simetri bersama sekiranya rahsia panjang itu digunakan semula (tidak disyorkan). Walau bagaimanapun, garam itu sendiri tidak perlu dirahasiakan dan setelah dijana secara rawak, katakanlah oleh Alice dalam contoh ini, ia boleh disiarkan kepada Bob bersama rahsia panjang yang disulitkan.

Oleh itu kita akan anggap bahawa Alice dan Bob mempunyai akses kepada garam rawak 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!"
)

Tandatangan digital dengan RSA

Kita kini akan meluaskan senario komunikasi sulit antara Alice dan Bob di atas kepada senario yang juga termasuk pengesahan dengan bantuan tandatangan digital.

Seperti sebelumnya, Alice akan menghantar mesej yang merangkumi kunci simetri kepada Bob secara sulit, tetapi dia juga akan menandatanganinya secara digital supaya Bob, setelah menerima mesej itu, boleh mengesahkan bahawa Alice yang menghantar mesej itu dan kandungan mesej tidak diganggu semasa penghantaran.

Secara lebih umum, adalah wajar untuk membolehkan pengesahan tanpa menjejaskan kerahsiaan di mana mana-mana pihak yang berminat dapat mengesahkan integriti, keaslian, dan mewujudkan penafian tidak boleh dilakukan terhadap sesuatu komunikasi, walaupun pihak itu tidak mempunyai akses kepada mesej teks biasa yang sebenar.

Kita akan mempertimbangkan tetapan umum ini yang kemudiannya melibatkan langkah-langkah berikut:

Pertama, Bob dan Alice sama-sama membuat kunci awam mereka tersedia melalui saluran terbuka.
Kemudian, Alice menyulitkan teks biasa menggunakan kunci awam Bob, mencipta teks sifir.
Seterusnya, Alice mencipta cincang teks sifir dengan fungsi cincang dan kemudian menyulitkan teks sifir yang telah dicincang itu menggunakan kunci peribadinya. Cincang yang disulitkan ini adalah tandatangan.
Kemudian, Alice menghantar kedua-dua teks sifir dan tandatangan melalui saluran terbuka.
Kemudian, Bob menggunakan kunci awam Alice untuk menyahsulit tandatangan, mendedahkan teks sifir yang telah dicincang.
Seterusnya, kerana Bob juga mempunyai akses kepada teks sifir itu sendiri, dia menggunakan fungsi cincang yang sama yang digunakan oleh Alice untuk mencipta semula contoh kedua teks sifir yang dicincang. Jika yang terakhir sepadan dengan yang diperoleh dengan menyahsulit tandatangan Alice, maka mesej itu disahkan, walaupun teks sifir itu sendiri belum lagi dinyahsulit.
Akhir sekali, Bob, setelah mengesahkan mesej itu, menyahsulit teks sifir menggunakan kunci peribadinya sendiri.

Figure 2. Digital signatures with RSA

Rajah 2. Tandatangan digital dengan RSA

Aliran kerja untuk tandatangan digital ini diilustrasikan seterusnya.

Kita sekali lagi mengimport beberapa modul berguna daripada perpustakaan cryptography. Seperti sebelumnya, Alice berhasrat menghantar kunci simetri kepada Bob secara selamat, tetapi dia juga ingin menandatanganinya secara digital. Dalam kes ini, kita memerlukan kunci awam untuk Alice dan Bob. Oleh itu, langkah pertama adalah bagi Alice dan Bob masing-masing mencipta pasangan kunci mereka sendiri menggunakan RSA dan menyiarkan kunci awam mereka sendiri kepada 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.")

Dalam langkah seterusnya, seperti sebelumnya, Alice menggunakan kunci awam Bob untuk menyulitkan kunci simetri dan menyediakan teks sifir.

# 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 peringkat ini, daripada hanya menyiarkan teks sifir, Alice berhasrat untuk melampirkan tandatangan digital padanya supaya dia boleh membuktikan kepada Bob bahawa dia adalah pengirim mesej itu. Ini dilakukan dalam dua langkah:

Cipta cincang teks sifir menggunakan algoritma pencincangan.
Sulitkan cincang menggunakan kunci peribadi Alice, yang merupakan tandatangan.

# 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 teks sifir dan tandatangan melalui rangkaian supaya Bob dapat menerima kedua-duanya.

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

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

Dari sisi Bob, tugas pertama adalah untuk mengesahkan integriti dan keaslian teks sifir. Untuk melakukan ini, Bob mencipta cincang teks sifir yang diterima menggunakan algoritma pencincangan yang sama yang digunakan oleh 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 menyahsulit tandatangan yang diterima menggunakan kunci awam Alice. Kerana Alice menggunakan kunci peribadinya untuk mencipta tandatangan, Bob dapat menyahsulitnya menggunakan kunci awam Alice. Tandatangan yang dinyahsulit tidak lain hanyalah cincang teks sifir yang dicipta di pihak Alice. Jika cincang yang dicipta oleh Bob sepadan dengan tandatangan yang dinyahsulit, maka Bob telah mengesahkan bahawa teks sifir yang diterimanya tidak diganggu dan bahawa Alice yang menandatangani teks sifir itu.

Dalam kod Python di bawah, operasi-operasi ini digabungkan ke dalam fungsi utiliti berguna yang dipanggil verify yang disediakan oleh objek yang dikaitkan dengan kunci awam 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 mengesahkan integriti dan keaslian teks sifir yang diterima, Bob kemudian boleh menyahsulitnya menggunakan kunci peribadinya kerana Alice mencipta teks sifir menggunakan kunci awam 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 senario tandatangan digital di atas, mana-mana pihak — bukan hanya Bob — boleh mengesahkan bahawa Alice adalah pengirim teks sifir kerana semua orang boleh mengakses kunci awam Alice, teks sifir, dan tandatangan digital. Tambahan pula, setelah menghantar teks sifir dan tandatangan, Alice tidak boleh kemudiannya menafikan telah berbuat demikian kerana tandatangan itu boleh dinyahsulit kepada cincang yang bermakna hanya menggunakan kunci awamnya. Ini mewujudkan penafian tidak boleh dilakukan.

Dengan membolehkan pengedaran kunci yang selamat dan menyokong penafian tidak boleh dilakukan, kriptografi kunci awam mewujudkan asas yang kukuh untuk komunikasi digital yang selamat.

Memecahkan RSA

Kegunaan dan keselamatan algoritma RSA yang digariskan di atas bersandarkan dua andaian matematik:

Mencari songsang pendaraban modular $d$ sedangkan hanya mempunyai akses kepada $(e, n)$ adalah tidak boleh dilaksanakan secara pengiraan.
Dalam tetapan RSA, operasi pendarapan modular berkelakuan seperti fungsi trapdoor sehala. Apabila digunakan untuk penyulitan, ia menghasilkan teks sifir yang sukar difahami, dan tanpa akses kepada kunci peribadi, membalikkan operasi untuk memulihkan teks biasa daripada teks sifir adalah tidak boleh dilaksanakan. Walau bagaimanapun, dengan akses kepada kunci peribadi, yang bertindak sebagai trapdoor, teks sifir boleh dengan mudah dinyahsulit.

Serangan paling menonjol terhadap algoritma RSA bertujuan untuk melemahkan andaian 1 dengan memulihkan nombor kunci peribadi $d$ secara cekap melalui pemfaktoran modulus $n$ . Seperti yang akan diilustrasikan di bawah, adalah mudah untuk memulihkan $d$ jika seseorang mempunyai akses kepada sama ada faktor perdana $p$ dan $q$ bagi $n$ atau totient $φ$ $(n)$ . Ingat bahawa $p$ , $q$ , dan $φ$ $(n)$ dirahsiakan semasa penjanaan kunci dan dibuang selepas itu. Pihak ketiga yang memulihkan maklumat ini menggunakan komputer klasik atau kuantum pada dasarnya mendedahkan kunci peribadi, memecahkan RSA. Oleh itu, pemfaktoran perdana adalah primitif pengiraan utama yang diperlukan untuk memecahkan RSA.

Pengkomputeran klasik dan RSA

Pemfaktoran perdana bagi integer besar diketahui menunjukkan penskalaan super-polinomial atau subeksponential pada komputer klasik. Algoritma klasik terbaik yang diketahui untuk memfaktorkan integer yang lebih besar daripada $10^{100}$ ialah penapis medan nombor umum (GNFS)

Perincian matematik

$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 integer $n$ yang hendak difaktorkan.

Penskalaan ini adalah super-polinomial dalam bilangan bit yang diperlukan untuk mewakili $n$ .

Oleh itu, pemfaktoran perdana dianggap tidak cekap pada komputer klasik.

Pada masa ini, integer terbesar yang difaktorkan pada perkakasan klasik adalah dalam julat 829 bit atau 250 digit perpuluhan. Memandangkan pertumbuhan eksponen dalam kuasa pengkomputeran klasik yang telah disaksikan dalam beberapa dekad yang lalu, RSA 1024-bit tidak lagi dianggap selamat dalam jangka pendek dan kini sudah tidak diguna pakai. Walau bagaimanapun, dalam masa terdekat, memfaktorkan integer 2048-bit yang magnitudnya berada dalam julat $10^{617}$ pada masa ini dianggap tidak boleh dilaksanakan pada sistem klasik, mencadangkan kebolehterusan berterusan. Kemunculan komputer kuantum, bagaimanapun, membatalkan penilaian ini.

Algoritma kuantum Shor dan RSA

Mungkin algoritma kuantum yang paling terkenal hari ini ialah algoritma Shor untuk mencari faktor perdana integer. Apabila diperkenalkan oleh Peter Shor pada tahun 1994, ia diiktiraf sebagai algoritma kuantum pertama yang menawarkan percepatan super-polinomial berbanding algoritma klasik dalam masalah yang sangat penting dari segi praktikal, iaitu pemfaktoran perdana.

Algoritma Shor boleh memfaktorkan perdana dengan $O(n^2)$ di mana $n$ ialah bilangan bit.

Penjelasan matematik algoritma Shor

Dalam konteks RSA, algoritma Shor berfungsi dengan mengeksploitasi keperiodikan fungsi eksponen modular $f(x) = a^x (mod~n)$ dan menyediakan primitif pencarian tempoh kuantum yang membolehkan pemfaktoran perdana yang cekap bagi modulus $n$ .

Garis besar ringkas peringkat tinggi skema keseluruhan Shor untuk memecahkan RSA adalah seperti berikut:

Diberi modulus $n$ , yang diterbitkan sebagai sebahagian daripada kunci awam, pilih nombor $a$ yang koprim kepada $n$ iaitu, $gcd(a,n) = 1$ . Oleh kerana kita tahu bahawa $n = p*q$ mempunyai tepat dua faktor perdana $(p, q)$ , hampir mana-mana nombor yang kurang daripada $n$ yang kita pilih secara rawak berkemungkinan besar koprim kepada $n$ .
Setelah memilih $a$ , cari eksponen $r$ supaya $a^r \equiv 1 (mod~n)$ . Ini bermaksud $a^r - 1 \equiv 0 (mod~n)$ . Kewujudan eksponen $r$ supaya kongruens di atas berlaku dijamin oleh sifat keperiodikan pendarapan modular.
Jika $r$ adalah genap, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ untuk sesetengah integer $\gamma$ . Sebelah kiri persamaan terakhir ini mesti mengandungi $p$ dan $q$ sebagai dua daripada faktor perdananya kerana sebelah kanan juga berbuat demikian. Jika $r$ adalah ganjil, kembali ke langkah 1 dan cuba pilihan berbeza untuk $a$ .
Gunakan algoritma Euclid yang diperluas untuk mencari $gcd((a^{r/2} - 1), n)$ atau $gcd((a^{r/2} + 1), n)$ . GCD yang dikira sangat berkemungkinan mengenal pasti salah satu faktor perdana $p$ atau $q$ . Bahagikan $n$ dengan faktor perdana ini untuk memulihkan yang satu lagi.
Setelah $p, q$ diketahui, gunakan langkah-langkah dari algoritma RSA asal untuk membina semula totient $\phi(n)$ dan menjana nombor kunci peribadi $d$ sebagai songsang modular bagi nombor kunci awam $e$ yang diketahui.

Pada Ogos 2023 Oded Regev menerbitkan penambahbaikan pada asli Shor menggunakan pendekatan berbilang dimensi yang menghasilkan $O(n^{1.5})$ . Penyelidikan lanjut terus berlangsung termasuk oleh Ragavan dan Vaikuntanathan dalam bidang ini yang mungkin meningkatkan masa, kos, atau bilangan qubit yang diperlukan. Walaupun kita tidak boleh mengatakan bila menjalankan algoritma sedemikian terhadap penyulitan RSA dunia nyata benar-benar menjadi boleh dilaksanakan, ia semakin hampir dari masa ke masa.

Contoh Python yang menunjukkan pemecahan penyulitan RSA

Dalam sel kod berikut, kita menggambarkan contoh mencari kunci peribadi berdasarkan kunci awam sahaja. Ini akan menggunakan pengiraan klasik kasar, tetapi menunjukkan bagaimana algoritma Shor boleh digunakan — termasuk kunci yang besar.

nota

Dalam bahagian ini kita akan menunjukkan pengiraan matematik secara terperinci sebagai sebahagian daripada kod Python

Dalam contoh ini, kita mempunyai kunci awam $(5, 247)$ , dan kita akan memulihkan kunci peribadi.

Langkah 1: Langkah pertama adalah untuk memilih nombor yang koprim kepada 247. Hampir mana-mana nombor yang kita teka akan melaksanakan tugas tersebut. Mari kita 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: Seterusnya kita perlu mencari tempoh $r$ supaya $6^r \equiv 1 (mod~247)$ . Dalam contoh ini, kita mengira $r$ secara klasik menggunakan kasar paksa, tetapi kita juga boleh 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: Oleh kerana tempoh $r = 36$ adalah genap, kita boleh mengira $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: Cari GCD bagi salah satu faktor tersebut dengan $n$ . Bahagikan sahaja $n$ dengan faktor perdana yang telah ditemui untuk mendapatkan faktor perdana 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 perdana $n = 247$ sebagai $p_{found}=13$ dan $q_{found}=19$ , kita mengira totient $\phi_{found} = (p_{found}-1)*(q_{found}-1)$ .

Kunci peribadi adalah songsang modular bagi nombor kunci awam $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 tempoh yang penting di mana algoritma Shor menggunakan dua primitif kuantum asas, iaitu jelmaan Fourier kuantum dan anggaran fasa kuantum. Untuk penjelasan terperinci tentang aspek kuantum algoritma Shor, lihat pelajaran Anggaran fasa dan pemfaktoran dalam Asas Algoritma Kuantum. Langkah 1 dan 3 hingga 5 melibatkan operasi yang agak murah yang boleh dilaksanakan dengan mudah pada komputer klasik.

Secara pilihan, inilah panduan visual terperinci tentang pelaksanaan algoritma Shor.

Pada komputer kuantum, algoritma Shor boleh menunjukkan penskalaan polilogaritmik sebaik $O((log~n)^2 (log~log~n))$ dari segi modulus $n$ , atau penskalaan polinomial dari segi bilangan bit yang diperlukan untuk mewakili $n$ . Ini adalah percepatan super-polinomial berbanding algoritma GNFS klasik.

Anggaran sumber terkini menunjukkan bahawa berdasarkan andaian tertentu yang dibuat mengenai konfigurasi perkakasan, beberapa puluh ribu hingga beberapa juta qubit akan diperlukan untuk memecahkan RSA 2048-bit menggunakan algoritma Shor. Tidak mustahil bahawa komputer kuantum dengan beberapa puluh ribu qubit akan tersedia dalam beberapa tahun akan datang, menjadikan hujung bawah anggaran sumber boleh dicapai.

Pertukaran kunci Diffie-Hellman dan Algoritma Tandatangan Digital

Dalam bahagian sebelumnya, kita membincangkan kriptosistem RSA yang keselamatannya bergantung pada kesukaran pengiraan pemfaktoran perdana. Di sini, kita akan membincangkan dua protokol kriptografi kunci asimetri yang popular, iaitu pertukaran kunci Diffie-Hellman (DH) dan Algoritma Tandatangan Digital (DSA), kedua-duanya berasaskan masalah matematik yang berbeza, iaitu masalah logaritma diskret (DLP).

Masalah logaritma diskret

Dalam persamaan berikut, kita perlu mencari $a$ dengan hanya diberi $e$ , $M$ , $c$

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

Ini dipercayai sukar dilakukan dengan komputer klasik kerana penggunaan aritmetik modulo, dan oleh itu menjadi asas matematik yang baik untuk algoritma penyulitan.

Ini dikenali sebagai masalah logaritma diskret (DLP).

Butiran matematik masalah logaritma diskret

DLP biasanya dibingkai dalam konteks kumpulan kitaran dan dinyatakan seperti berikut.

Pertimbangkan kumpulan kitaran $G$ yang dijana oleh elemen kumpulan $g \in G$ dan diberi elemen sembarangan $h \in G$ , cari integer $k$ supaya $h = g^{k}$ .

Di sini integer $k \equiv log_{g}h$ adalah logaritma diskret. Sifat kitaran $G$ menjamin bahawa untuk setiap $h$ , terdapat integer $k$ yang sah.

Untuk kriptografi, DLP pada kumpulan pendaraban integer modulo nombor perdana $p$ yang ditandakan $(\mathbb{Z}_p)^{\times}$ ternyata berguna. Elemen-elemen $(\mathbb{Z}_p)^{\times}$ ialah kelas kongruens yang dilabelkan dengan integer modulo $p$ yang coprime dengan $p$ .

Sebagai contoh:

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

Operasi pendaraban $(\times)$ pada kumpulan ini hanyalah pendaraban integer biasa diikuti dengan pengurangan modulo $p$ , dan pemangkatan dengan integer $k$ hanyalah pendaraban berulang sebanyak $k$ kali dan pengurangan modulo $p$ .

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

Kumpulan pendaraban ini mempunyai dua penjana ${[3],[5]}$ yang juga dikenali sebagai punca primitif. Kita akan menggunakan $[5]$ sebagai penjana; iaitu, jana setiap elemen $(\mathbb{Z}_7)^{\times}$ menggunakan kuasa integer berturutan bagi 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 lihat bahawa dalam aritmetik modulo 7, menaikkan 5 kepada kuasa integer berturutan menghasilkan setiap elemen $(\mathbb{Z}_7)^{\times}$ tepat sekali sebelum kitaran berulang tanpa had dengan tempoh $p-1 =6$ .

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

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

Daripada output sel Python di atas kita lihat bahawa:

$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 aritmetik nombor nyata biasa, pemangkatan adalah fungsi monoton dan mencari logaritma sebarang nombor kepada sebarang asas adalah mudah secara pengiraan. Sebaliknya, seperti yang jelas daripada contoh mudah $(\mathbb{Z}_7)^{\times}$ di atas, pemangkatan modular adalah bukan monoton, dan walaupun ia berkala dengan tempoh $p-1$ , ia sebaliknya sangat tidak trivial. Jadi mengira songsangannya, iaitu logaritma diskret, ternyata tidak cekap untuk $p$ yang besar pada komputer klasik.

Pemerhatian ini menyokong kedua-dua pertukaran kunci Diffie-Hellman (DH) dan Algoritma Tandatangan Digital (DSA), yang dibincangkan dalam bahagian seterusnya.

DLP boleh diperluaskan kepada subkumpulan kitaran seperti berikut:

Pertimbangkan $(\mathbb{Z}_p)^{\times}$ yang ditakrifkan di atas dan elemen $g \in (\mathbb{Z}_p)^{\times}$ bertertib perdana $r$ , iaitu $g^r \equiv 1 (~mod~p)$ .
Set kuasa integer bagi $g$ : $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ adalah subkumpulan kitaran $(\mathbb{Z}_p)^{\times}$ dengan tertib kumpulan $r$ .
Satu DLP boleh ditentukan pada $\langle g \rangle$ dengan memilih $h \in \\langle g \rangle$ dan meminta $1 \le a \le r$ supaya $g^a~(mod~p) = h$

Pertukaran kunci Diffie-Hellman

Pada tahun 1976, Whitfield Diffie dan Martin Hellman mencadangkan protokol pertukaran kunci untuk membolehkan penciptaan kunci rahsia dikongsi melalui saluran komunikasi yang tidak selamat. Kunci rahsia tersebut kemudian boleh digunakan oleh pihak-pihak yang berkongsinya untuk penyulitan simetri. Algoritma ini bergantung pada DLP.

Rajah 1. Pertukaran kunci Diffie-Hellman

Rajah 1. Pertukaran kunci Diffie-Hellman

Butiran matematik pertukaran kunci Diffie-Hellman

Dengan Alice dan Bob sebagai dua pihak yang berkomunikasi, protokol berfungsi seperti berikut:

Pertama, Alice dan Bob bersetuju pada nombor perdana besar $p$ dan punca primitif atau penjana $a$ .
Kemudian, Alice memilih eksponen rahsia $k_A$ secara rawak dengan $1 \le k_A \le p-2$ dan mengira $h_A = a^{k_A}~(mod~p)$ . $k_A, h_A$ masing-masing adalah kunci peribadi dan kunci awam Alice.
Seterusnya, Bob memilih eksponen rahsia $k_B$ secara rawak dengan $1 \le k_B \le p-2$ dan mengira $h_B = a^{k_B}~(mod~p)$ . $k_B, h_B$ masing-masing adalah kunci peribadi dan kunci awam Bob.
Kemudian, Alice menghantar $h_A$ kepada Bob dan Bob menghantar $h_B$ kepada Alice melalui saluran yang boleh dipercayai tetapi tidak semestinya selamat.
Selepas itu, Alice menggunakan $h_B$ yang diterimanya untuk mengira kunci rahsia dikongsi $\kappa = h_B^{k_A}~(mod~p)$ .
Akhirnya, Bob pula menggunakan $h_A$ yang diterimanya untuk mengira kunci rahsia dikongsi $\kappa = h_A^{k_B}~(mod~p)$ .

Dengan protokol ini,

Alice dan Bob dijamin berakhir dengan kunci rahsia yang sama $\kappa$ kerana $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 memintas $h_A$ atau $h_B$ tidak boleh membina kunci rahsia $\kappa$ kerana mereka tidak mempunyai akses kepada $k_B$ atau $k_A$ masing-masing.
Mengekstrak $k_A$ atau $k_B$ menggunakan maklumat awam $a$ , $p$ , $h_A$ dan $h_B$ adalah sukar secara pengiraan kerana ia bersamaan dengan menyelesaikan DLP pada $(\mathbb{Z}_p)^{\times}$ .

Ilustrasi protokol Diffie-Hellman dalam Python

Mari kita lihat contoh mudah protokol DH dalam Python menggunakan nombor perdana kecil:

nota

Dalam bahagian ini kita akan menunjukkan pengiraan matematik secara terperinci sebagai sebahagian daripada kod Python

Langkah 1: Alice dan Bob bersetuju pada perdana $p$ dan punca 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 rahsia $k_A$ dan mengira $h_A = a^{k_A}~(mod~p)$ . Begitu juga, Bob memilih eksponen rahsia $k_B$ dan mengira $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-dua pihak menyiarkan kunci awam mereka $h_A$ dan $h_B$ .

Langkah 5, 6: Setiap pihak menggabungkan kunci peribadi mereka dengan kunci awam pihak lain untuk mencipta kunci rahsia dikongsi.

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 kini boleh menggunakan kunci rahsia dikongsi untuk penyulitan simetri.

Keselamatan pertukaran kunci Diffie-Hellman

Seperti yang dinyatakan di atas, keselamatan DH bergantung pada kesukaran pengiraan menyelesaikan DLP dengan perdana besar $p$ . Dalam aplikasi biasa, NIST mengesyorkan integer perdana 2048 atau 3072 bit untuk pertukaran kunci DH, yang dianggap cukup selamat terhadap percubaan menyelesaikan DLP menggunakan komputer klasik.

Serangan Man-in-the-middle (MITM): Hakikat bahawa DH adalah skim interaktif di mana rahsia dikongsi bergantung pada penggabungan kunci peribadi satu pihak dengan kunci awam pihak lain menjadikannya terdedah kepada serangan yang dipanggil Man-in-the-middle (MITM).

Butiran matematik keselamatan DH dan serangan MITM

Dalam senario ini, pihak ketiga — katakanlah, Eve — memintas kunci awam $h_A, h_B$ semasa penghantaran dan menggantikan kunci awamnya sendiri $h_E$ untuk setiap $h_A$ dan $h_B$ sebelum meneruskannya kepada Bob dan Alice masing-masing.

Kemudian, bukannya menggunakan $h_B$ untuk mencipta rahsia berkongsiannya, Alice akan menggunakan $h_E$ sambil menyangka bahawa dia menggunakan kunci awam Bob. Begitu juga, bukannya menggunakan $h_A$ untuk mencipta rahsia berkongsiannya, Bob akan menggunakan $h_E$ sambil menyangka bahawa dia menggunakan kunci awam Alice.

Kerana $h_E$ digunakan untuk mencipta rahsia dikongsi Alice (Bob), teks biasa yang disulitkan oleh Alice (Bob) boleh dinyahsulit oleh Eve.

Oleh itu, pertukaran kunci DH biasanya digunakan bersama algoritma tandatangan digital untuk memastikan setiap pihak menggunakan kunci awam yang telah disahkan untuk mencipta rahsia dikongsi mereka.

Algoritma Tandatangan Digital (DSA)

Walaupun kriptosistem generik seperti RSA menyediakan fungsi tandatangan digital, pada tahun 1994 NIST mengadopsi skim tandatangan khusus berdasarkan pemangkatan modular dan masalah logaritma diskret sebagai piawaian persekutuan untuk tandatangan digital. Skim ini, yang kemudian dikenali hanya sebagai Algoritma Tandatangan Digital (DSA), melibatkan empat fasa berbeza:

Penjanaan kunci:

Kunci DSA dijana daripada:
- 2 nombor perdana yang memenuhi peraturan tertentu
  - $p$ - biasanya 256 bit (kita panggil panjang ini $N$ )
  - $q$ - biasanya 3072 bit (kita panggil panjang ini $L$ )
- Fungsi cincang kriptografi yang akan menukar daripada rentetan panjang $L$ kepada $N$
- Parameter tambahan $g$ (lihat butiran di bawah)
Daripada ini kita memilih nombor rawak $x$ sebagai kunci peribadi, dan mampu mengira kunci awam $y$
Butiran matematik penjanaan kunci
- Penjanaan parameter: Secara matematik, DSA melibatkan subkumpulan kitaran $(\mathbb{Z}_p)^{\times}$ yang dijana oleh elemen $g$ bertertib perdana q < p. Langkah pertama dalam DSA adalah memilih dua nombor perdana p, q untuk menyediakan struktur matematik yang diperlukan.
  
  Pilih nombor perdana $q$ sebanyak $N$ bit.
  
  Pilih nombor perdana $p$ sebanyak $L$ bit supaya $p-1$ adalah gandaan $q$ . Pilihan $p$ menentukan kumpulan $(\mathbb{Z}_p)^{\times}$
  
  Ambil integer $1 < h < p-1$ secara rawak dan kira $g = h^{(p-1)/q}~mod~p$ . Jika $g=1$ yang jarang berlaku, cuba $h$ yang lain.
  
  Sahkan bahawa $g^q~mod~p = 1$ . g dengan itu adalah penjana subkumpulan kitaran $\langle g \rangle$ bagi $(\mathbb{Z}_p)^{\times}$ bertertib perdana q.
  
  Parameter $(q, p, g)$ menentukan contoh algoritma dan merupakan maklumat awam. Biasanya, $N \sim 256$ dan $L \sim 3072$ dalam aplikasi sebenar.
  
  Protokol ini juga memerlukan fungsi cincang kriptografi $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ yang memetakan rentetan binari $L$ bit kepada rentetan $N$ bit, contohnya, SHA-256.
- Penjanaan pasangan kunci: Penandatangan perlu menjana pasangan kunci di pihak mereka.
  
  Pilih integer rahsia rawak $x \in \{1,2...q-1\}$ . $x$ adalah kunci peribadi.
  
  Jana $y = g^{x}~mod~p$ . $y$ adalah kunci awam penandatangan.
Pengedaran kunci:

Maklumat berikut dikongsi dengan sesiapa yang ingin mengesahkan tandatangan
- Parameter yang digunakan $(p,q,g)$ yang menerangkan algoritma
- Fungsi cincang $H$
- Kunci awam $y$
Penandatanganan:
- Penandatangan kini boleh menandatangani mesej $m$ . Tandatangan yang dihasilkan adalah $(r,s)$
- Mesej dan tandatangan kedua-duanya kini dihantar kepada penerima
Butiran matematik menandatangani mesej
Penandatangan menandatangani mesej $m$ seperti berikut:
- Pilih integer rahsia k secara rawak daripada $\{1,2...q-1\}$
- Kira $r = (g^k~mod~p)~mod~q$ . Dalam kes yang jarang berlaku apabila $r=0$ , cuba k rawak yang lain.
- Kira $s = (k^{-1} (H(m) + xr))~mod~q$ . Dalam kes yang jarang berlaku jika $s=0$ , cuba k rawak yang lain.
- Tandatangan adalah tuple $(r, s)$ .
- Penandatangan menghantar mesej $m$ serta tandatangan $(r,s)$ kepada pengesah.
Kerana kedua-dua $r, s$ adalah integer, modulo $q$ saiz tandatangan adalah dalam tertib $N$ bit dan bukan $L$ bit yang lebih panjang.
Pengesahan:

Penerima kini ingin mengesahkan kesahihan penghantar. Mereka mempunyai akses kepada maklumat awam $(q, p, g, H, y, (r,s), m)$ Mereka boleh melaksanakan pengiraan yang membuktikan bahawa penghantar mempunyai akses kepada kunci peribadi $x$

dan berusaha memastikan bahawa penandatangan adalah seseorang yang mempunyai akses kepada kunci peribadi $x$ .
Butiran matematik skim pengesahan DSA
- Sahkan bahawa $0 \lt r \lt q$ dan $0 \lt s \lt q$ , iaitu, $r, s$ adalah integer modulo~q yang sah.
- Kira $w = s^{-1}~mod~q$ .
- Kira $u_1 = H(m)w~mod~q$ .
- Kira $u_2 = rw~mod~q$ .
- Kira $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$ .
- Tandatangan disahkan jika $v = r$ .
Untuk tandatangan yang sah, ketepatan algoritma DSA mudah ditunjukkan seperti berikut:
- Di pihak penandatangan: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
- Memandangkan bahagian kanan kesamaan yang terakhir, pengesah boleh mengira $s^{-1}, H(m)$ kerana $s, q, m, H$ adalah maklumat awam.
- Oleh itu, pengesah mengira $w = s^{-1}~mod~q$ dan $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$ .
- Pengesah juga mengira $u_2 = rw~mod~q = rs^{-1}~mod~q$ kerana $r$ juga awam.
- Perhatikan bahawa $k = (u_1 + xu_2)~mod~q$ .
- Walau bagaimanapun, pengesah tidak mempunyai akses kepada $x$ kerana ia adalah kunci peribadi penandatangan, jadi $k$ itu sendiri tidak boleh dikira secara langsung. - Skim ini sebaliknya bergantung pada hakikat bahawa walaupun pengesah tidak dapat mengira $k$ , dengan penandatangan yang sah, pengesah sepatutnya mampu mengira semula $(g^k~mod~p)~mod~q = r$ dengan bantuan kunci awam penandatangan $y = g^{x}~mod~p$ .
- Jadi, pengesah mengira $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 berikut kerana $g$ bertertib $q$ dan menetapkan $v = r$ untuk tandatangan yang sah.

Ilustrasi DSA dalam Python

Dalam contoh ini, kita akan menggunakan nombor perdana kecil untuk mengilustrasikan proses DSA dalam senario di mana Alice menghantar mesej bertandatangan kepada Bob. Kita akan menggunakan integer kecil dalam contoh ini. Senario dunia sebenar akan menggunakan nombor perdana yang jauh lebih besar dalam tertib 2048-3072 bit.

nota

Kamu boleh cuba jalankan semula contoh ini dengan nilai berbeza untuk melihat bagaimana algoritma berkelakuan, tetapi pastikan kamu mula menjalankan dari sel pertama dalam bahagian ini.

Kita mulakan dengan mengimport perpustakaan yang diperlukan dan memilih parameter kita. Parameter integer $p$ , $q$ , $g$ adalah maklumat awam, dan memenuhi peraturan berikut:

$p$ , $q$ kedua-duanya perdana
$(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}")

Seterusnya penandatangan, Alice, menjana kunci peribadinya.

Kunci peribadi, k (alice-private-key dalam kod python) mesti 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 peribadinya sebagai rahsia.

Seterusnya, Alice mengira kunci awamnya menggunakan pemangkatan modular. Membalikkan langkah ini untuk mendapatkan semula kunci peribadi adalah contoh DLP, jadi sukar untuk dikira pada komputer klasik apabila perdana besar digunakan.

Daripada penjelasan matematik di atas, kita tahu ini boleh dikira menggunakan formula:

$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 menjadikan kunci awamnya tersedia melalui saluran yang tidak semestinya rahsia.

Sekarang Alice boleh menandatangani mesej.

Untuk skim tandatangan digital, kita perlu menjana cincang $H(m)$ bagi mesej $m$ yang akan ditandatangani.

Katakan Alice dan Bob bersetuju untuk menggunakan algoritma pencincangan tertentu dengan panjang cincang $N$ sama dengan bilangan bit dalam $q$ . Dalam contoh mudah ini, kita akan membatasi output fungsi cincang tiruan kita dengan $q$ . Fungsi cincang di sini adalah trivial, hanya menjana integer rawak.

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}")

Seterusnya, Alice perlu menjana nombor rahsia rawak setiap mesej $k$ serta songsangan pendaraban modulonya $q$ untuk mengira tandatangan.

Algoritma kekerasan mudah boleh digunakan untuk mengira songsangan modular. Walau bagaimanapun, lebih baik menggunakan salah satu fungsi Python terbina dalam pow seperti yang ditunjukkan di bawah

# 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 kini boleh mengira tandatangan.

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

Perhatikan bahawa terdapat beberapa syarat tertentu yang akan memerlukan kita memilih nilai berbeza untuk $k$ dalam kes di mana sama ada $r$ atau $s$ mengira kepada $0$ . Dalam kes ini kita akan menjana nilai baru dan ulang.

# 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 mesej dan tandatangannya kepada penerima atau pengesah, Bob.

Bob sebelum ini telah memperoleh kunci awam Alice dan kini boleh mengesahkan tandatangan untuk mengesahkan mesejnya.

Untuk melakukannya, dia melakukan beberapa semakan, kemudian menjana semula cincang mesej siaran Alice dan mengira kuantiti 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 menyemak sama ada $v$ bersamaan $r$ . Jika ia sama, maka tandatangan disahkan.

# 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!")

Keselamatan DSA

Dengan pengkomputeran klasik, keselamatan DSA boleh dipengaruhi oleh beberapa faktor:

Saiz kunci: Seperti biasa, saiz kunci memberikan perlindungan asas terhadap serangan kekerasan. Aplikasi moden yang menggunakan DSA menggunakan saiz kunci sekurang-kurangnya 2048 bit.
Kualiti $k$ : Dalam DSA, setiap tandatangan memerlukan nilai $k$ yang unik, rawak, dan rahsia (lihat di atas). Keunikan, entropi, dan kerahsiaan $k$ adalah kritikal, dan kelemahan dalam mana-mana aspek ini boleh menyebabkan kunci peribadi $x$ terkompromi. Penjana nombor rawak yang digunakan untuk menjana $k$ perlu selamat dengan sendirinya.
Kekuatan fungsi cincang: Memandangkan DSA menggunakan fungsi cincang sebagai sebahagian daripada proses penjanaan dan pengesahan tandatangan, fungsi cincang yang lemah boleh mengkompromi keselamatan tandatangan digital. Contohnya, penggunaan SHA-1 dengan DSA sudah lapuk dan SHA-2 atau lebih tinggi disyorkan.

Selain ini, implementasi DSA yang kukuh juga harus melindungi daripada jenis serangan lain yang menyasar kriptografi kunci asimetri seperti yang digariskan sebelumnya.

Pertukaran kunci disahkan dengan Diffie-Hellman dan DSA

Protokol keselamatan rangkaian moden, seperti Transport Layer Security (TLS) dan banyak lagi, melibatkan penggabungan fungsi pertukaran kunci dan pengesahan. Dalam konteks Diffie-Hellman, pengesahan diperlukan untuk melindungi daripada serangan MITM. Dalam sel kod berikut, kita mengilustrasikan contoh di mana Alice dan Bob melakukan pertukaran kunci yang disahkan dengan menggabungkan protokol Diffie-Hellman dan DSA. Untuk ini, kita akan menggunakan perpustakaan Python cryptography.

Rajah 2. Pertukaran kunci disahkan dengan Diffie-Hellman dan DSA

Rajah 2. Pertukaran kunci disahkan dengan Diffie-Hellman dan DSA Pertama, Alice dan Bob bersetuju pada set parameter DH dan menjana set pasangan kunci awam-peribadi 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 awam DH disiarkan. Seterusnya, Alice dan Bob masing-masing menjana pasangan kunci berasingan untuk digunakan dengan DSA. Kunci-kunci ini pula akan digunakan untuk menandatangani kunci awam DH yang akan ditukar.

# 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 awam DH-nya menggunakan kunci peribadi 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")

Begitu juga, Bob menandatangani kunci awam DH-nya menggunakan kunci peribadi 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 awam DH dan tandatangan yang sepadan kini disiarkan oleh Alice dan Bob. Setelah menerima kunci awam dan tandatangan rakan sejawat mereka, setiap pihak kemudian mengesahkan bahawa tandatangan adalah sah. Dengan cara ini, serangan MITM dapat dicegah, kerana Alice, misalnya, tahu bahawa kunci awam DH Bob memang telah ditandatangani oleh Bob dan begitu juga 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")

Selepas pengesahan tandatangan, Alice dan Bob menjana rahsia dikongsi, yang melengkapkan 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")

Secara pilihan, untuk keselamatan tambahan, Alice dan Bob boleh menggunakan fungsi derivasi kunci khusus seperti HKDF untuk menjana kunci simetri yang lebih selamat daripada rahsia dikongsi 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")

Memecahkan Diffie-Hellman dan DSA

Kedua-dua protokol Diffie-Hellman (DH) dan DSA melibatkan penjanaan kunci awam dalam bentuk $y = g^{x}~mod~p$ , di mana kunci peribadi $x$ ialah logaritma diskret.

Penyerang yang boleh menyelesaikan satu contoh DLP boleh mendedahkan kunci peribadi salah satu pihak dan, dengan menggabungkannya dengan kunci awam pihak kedua, mendapat akses kepada rahsia bersama. Dalam kes DSA, penyerang yang boleh menyelesaikan DLP boleh mendapatkan semula kunci peribadi penandatangan, menggugurkan premis asas tandatangan digital.

Pada sistem pengkomputeran klasik, DLP dipercayai tidak mempunyai penyelesaian masa-polinomial. Tetapi seperti yang ditunjukkan oleh Peter Shor dalam kertas asal 1994 beliau, algoritma Shor juga menyelesaikan DLP dalam masa-polinomial pada komputer kuantum.

Algoritma Shor dan masalah logaritma diskret

Algoritma Shor mampu menyelesaikan masalah logaritma diskret dalam masa polinomial. Ia mencapai kecekapannya terutamanya dengan menggunakan algoritma kuantum yang boleh mencari tempoh suatu fungsi yang bergantung pada input kepada masalah — yang kemudiannya digabungkan dengan operasi yang lebih konvensional.

Butiran matematik algoritma Shor

Algoritma Shor menyediakan penyelesaian cekap kepada DLP dengan memetakannya kepada masalah yang lebih umum dalam teori kumpulan yang dikenali sebagai masalah subkumpulan tersembunyi (HSP).

Dalam HSP, seseorang diberi kumpulan algebra $G$ dan fungsi $f: G \rightarrow X$ dari $G$ ke beberapa set $X$ sedemikian rupa hingga $f$ adalah malar pada setiap koset bagi suatu subkumpulan $H$ daripada $G$ (dan berbeza pada koset yang berlainan). Kemudian, tugasnya adalah untuk menentukan $H$ . Diketahui bahawa komputer kuantum boleh menyelesaikan HSP pada kumpulan Abelian terhingga dalam masa polinomial dalam $log~|G|$ di mana $|G|$ ialah peringkat kumpulan.

Dalam kes DLP integer yang dibincangkan dalam pelajaran ini, pemetaan kepada HSP adalah seperti berikut:

Biar $p$ ialah nombor perdana dan pertimbangkan DLP yang diberikan oleh $y = g^r~mod~p$ di mana $g$ ialah penjana $(\mathbb{Z}_p)^{\times}$ . Oleh kerana $g^{p-1} \equiv 1~mod~p$ , $g$ mempunyai peringkat $p-1$ .
Pilih $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ di mana $\mathbb{Z}_{p-1}$ ialah kumpulan integer 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 $f$ kemudiannya ialah subkumpulan $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$ adalah malar pada koset $(\delta, 0) + H_0$ dan "menyembunyikan" subkumpulan $H_0$ yang menyediakan satu HSP.

Berdasarkan perkara di atas, algoritma kuantum Shor untuk DLP integer menggunakan oracle kuantum untuk menilai fungsi $f$ pada suatu keadaan yang mewakili superposisi seragam merentasi $G$ , kemudian menggunakan transformasi Fourier kuantum dan pengukuran dengan anggaran fasa untuk menghasilkan keadaan kuantum yang membolehkan pengenalan penjana $(r, 1)$ bagi $H_0$ . Daripada ini, $r$ , iaitu logaritma diskret yang dikehendaki, boleh diekstrak.

Kertas asal Shor mempunyai penerangan terperinci tentang algoritma tersebut.

Kriptografi lengkung eliptik

Kriptografi lengkung eliptik (ECC), berdasarkan matematik lengkung eliptik, menawarkan pendekatan yang berkuasa kepada kriptografi kunci asimetri. ECC diketahui menyediakan tahap keselamatan yang serupa dengan kaedah seperti RSA tetapi dengan kunci yang lebih pendek, menjadikannya lebih cekap dan amat sesuai untuk sistem dengan sumber terhad, seperti sistem tertanam dan peranti mudah alih, di mana penjimatan storan dan pengiraan daripada saiz kunci yang lebih kecil sangat diingini.

Prinsip asas kriptografi lengkung eliptik

Lengkung eliptik biasanya berbentuk $y^2 = x^3 + ax + b$ dengan beberapa sifat yang menarik.

Ia simetri secara mendatar. Jadi untuk mana-mana titik $(x,y)$ pada lengkung, pantulannya $(x,-y)$ juga berada pada lengkung
Mana-mana garis lurus bukan tegak hanya akan bersilang dengan lengkung pada maksimum tiga titik

Figure 1. Operations of addition and point doubling on an elliptic curve. Facet 1 defines P + Q = -R. Facet 2 illustrates point doubling 2Q = -P. Facet 3 defines the additive inverse of a point as its reflection about the x-axis i.e, P = -Q

Rajah 1. Operasi penambahan dan penggandaan titik pada lengkung eliptik. Faset 1 mentakrifkan P + Q = -R. Faset 2 menggambarkan penggandaan titik 2Q = -P. Faset 3 mentakrifkan songsang aditif suatu titik sebagai pantulannya pada paksi-x, iaitu P = -Q

Kriptografi lengkung eliptik menggunakan siri operasi aritmetik yang dikenakan pada titik-titik pada lengkung. Setiap operasi secara berkesan menavigasi ke titik baru pada lengkung. Ini adalah proses yang mudah untuk diikuti dalam satu arah, dan dengan saiz kunci yang lebih pendek ia lebih cekap daripada algoritma lain seperti RSA, tetapi cuba membalikkan proses ini adalah sangat sukar, maka itulah sebabnya ia digunakan dalam kriptografi.

Prinsip matematik kriptografi lengkung eliptik

Lengkung eliptik merentasi medan algebra $K$ ditakrifkan oleh persamaan matematik, biasanya dalam bentuk $y^2 = x^3 + ax + b$ dengan pekali $a, b \in K$ dan menerangkan titik-titik $(x, y) \in K \otimes K$ dengan keperluan tambahan bahawa lengkung tidak mempunyai bengkokan atau persilangan sendiri.

Sifat lengkung eliptik membolehkan operasi "penambahan" dan "pendaraban skalar" ditakrifkan melibatkan titik-titik pada lengkung.

Penambahan: Jika $P$ dan $Q$ ialah dua titik pada lengkung eliptik, maka $P + Q$ menerangkan titik ketiga yang unik yang dikenalpasti seperti berikut: Lukis garis yang bersilang dengan $P$ dan $Q$ dan cari titik ketiga, $R$ , di mana garis itu bersilang dengan lengkung semula. Kita kemudiannya mentakrifkan $P + Q = −R$ , iaitu titik bertentangan dengan $R$ yang dipantulkan melalui paksi- $x$ (lihat rajah di bawah). Apabila garis melalui $P, Q$ tidak bersilang dengan lengkung pada mana-mana $(x, y)$ terhingga, kita katakan ia bersilang dengan lengkung pada titik di infiniti $\mathbf{O}$ .

Penambahan lengkung eliptik memenuhi sifat kumpulan algebra dengan titik di infiniti sebagai identiti aditif.

Penggandaan dan pendaraban skalar: Operasi penggandaan titik yang sepadan dengan pendaraban skalar sebanyak $2$ diperoleh dengan menetapkan $P = Q$ dalam operasi penambahan dan secara grafik melibatkan garis tangen pada $P$ . Pendaraban skalar umum dengan integer $n$ yang ditakrifkan sebagai $nP = P + P + ...~n$ kali diperoleh melalui penggandaan dan penambahan berulang.

Masalah logaritma diskret lengkung eliptik

Masalah logaritma diskret lengkung eliptik (ECDLP) mempunyai banyak persamaan dengan masalah logaritma diskret yang dibincangkan sebelum ini, kerana ia juga berasaskan cabaran mencari faktor.

Operasi pendaraban skalar pada lengkung eliptik membolehkan masalah logaritma diskret lengkung eliptik ditakrifkan:

Diberi titik $P, Q$ pada lengkung eliptik sedemikian rupa hingga $Q = nP$ , tentukan $n$ .

Masalah ini diketahui tidak boleh diselesaikan pada komputer klasik untuk $n$ yang besar dan menjadi asas kepada keselamatan kriptografi.

Penerangan matematik ECDLP

Kriptografi lengkung eliptik terutamanya berdasarkan ECDLP yang diformulasikan pada medan terhingga algebra tertentu. Pada tahun 1999, NIST mengesyorkan sepuluh medan terhingga untuk digunakan dalam ECC. Ini adalah:

Lima medan perdana $\mathbb {F} _{p}$ untuk nombor perdana $p$ bersaiz $\{192, 224, 256, 384, 521\}$ bit.
Lima medan binari $\mathbb {F} _{2^{n}}$ untuk $n \in \{163, 233, 283, 409, 571\}$ .

Dengan persediaan di atas, sistem kriptografi kunci asimetri berasaskan ECC dalam kes medan perdana boleh ditentukan seperti berikut:

Pilih $p$ daripada senarai nilai yang disyorkan NIST untuk menentukan $\mathbb {F} _{p}$ .
Pilih parameter $a, b$ bagi lengkung eliptik.
Pilih titik asas $G$ yang "menjana" subkumpulan kitaran pada lengkung dengan peringkat $n$ ; iaitu integer terkecil sedemikian rupa hingga $nG = \mathbf{O}$ .
Kira kofaktor $h = |E(\mathbb {F} _{p})|/n$ di mana $|E(\mathbb {F} _{p})|$ ialah bilangan titik pada lengkung. $h$ biasanya ialah integer kecil.
Parameter domain $(p, a, b, G, n, h)$ membolehkan spesifikasi kunci asimetri dengan cara ini:
- Kunci peribadi ialah integer rawak $d$ dengan bilangan bit yang sama dengan nombor perdana $p$ . Ia perlu dirahsiakan.
- Kunci awam ialah hasil "pendaraban" titik asas $G$ dengan kunci peribadi $d$ . Ini biasanya dinotasikan sebagai $Q = dG$ .

Mendapatkan semula $d$ bersamaan dengan menyelesaikan ECDLP, yang dianggap tidak boleh diselesaikan untuk $d$ yang besar. Oleh itu ECDLP menjadi asas kepada skema pertukaran kunci dan tandatangan digital secara analog langsung dengan skema Diffie-Hellman dan DSA yang ditakrifkan merentasi $(\mathbb{Z}_p)^{\times}$ yang dibincangkan sebelum ini.

Pertukaran kunci dengan ECC

Salah satu kegunaan utama ECC ialah dalam protokol pertukaran kunci yang dikenali sebagai Diffie-Hellman lengkung eliptik (ECDH). Dalam ECDH, setiap pihak menjana pasangan kunci peribadi-awam dan kemudian bertukar kunci awam. Setiap pihak kemudian menggunakan kunci peribadi mereka sendiri dan kunci awam pihak lain untuk mengira rahsia bersama, yang boleh digunakan sebagai kunci untuk penyulitan simetri.

Walaupun agak mudah untuk melakukan penambahan titik pada lengkung eliptik dan mendapatkan kunci awam daripada kunci peribadi, ia secara pengiraan tidak boleh dilaksanakan untuk membalikkan proses dan mendapatkan kunci peribadi daripada kunci awam. Tingkah laku "sehala" ini menyediakan keselamatan pertukaran kunci ECDH.

Di sini, kita akan menggambarkan contoh bagaimana seseorang boleh melakukan pertukaran kunci ECDH menggunakan Python dan pustaka 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")

Tandatangan digital dengan ECC

ECC juga boleh digunakan untuk menjana tandatangan digital menggunakan Algoritma Tandatangan Digital Lengkung Eliptik (ECDSA). Dalam ECDSA, penandatangan mencipta tandatangan menggunakan kunci peribadi mereka, dan orang lain boleh mengesahkan tandatangan menggunakan kunci awam penandatangan. Sama seperti ECDH, keselamatan ECDSA bergantung pada ECDLP. Adalah tidak boleh dilaksanakan secara pengiraan bagi seseorang untuk memalsukan tandatangan tanpa akses kepada kunci peribadi penandatangan.

Berikut ialah contoh transaksi tanda-dan-sahkan yang mudah 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 kod di atas, jika seseorang mengubah mesej selepas ia ditandatangani, pengesahan akan gagal, memberikan jaminan keaslian dan integriti untuk mesej tersebut.

Memecahkan ECDH dan ECDSA

Secara analog dengan masalah logaritma diskret integer, ECDLP ternyata sukar pada komputer klasik tetapi mempunyai penyelesaian cekap pada komputer kuantum sekali lagi melalui algoritma Shor. Kami merujuk anda kepada literatur terkini untuk perbincangan berkaitan pengitlakan algoritma Shor kepada kes ECDLP.

Ringkasan

Dalam pelajaran ini, kita mulakan dengan melihat ciri-ciri utama kriptografi kunci asimetri (AKC) dan membincangkan pertimbangan keselamatan asas yang menyokong sistem kriptografi asimetri. Khususnya, kita memperkenalkan dua aplikasi utama AKC — iaitu, pertukaran kunci dan tandatangan digital — yang kedua-duanya merupakan komponen penting komunikasi berasaskan internet moden.

Kita kemudian melihat sistem kriptografi RSA, yang sejak tahun 1970-an, telah terbukti amat bernilai dalam mengamankan komunikasi digital moden dengan membolehkan pertukaran kunci dan tandatangan digital dalam rangka kerja yang mudah dan serba boleh. Keselamatan kriptografi RSA berkenaan pengkomputeran klasik adalah berdasarkan kesukaran memfaktorkan integer besar dan memerlukan saiz kunci dalam julat 2048 bit untuk memastikan integer yang digunakan dalam aplikasi praktikal cukup besar untuk menahan pemfaktoran.

Kita kemudian melihat pertukaran kunci Diffie-Hellman (DH) dan Algoritma Tandatangan Digital (DSA). Keselamatan skema ini bersandar pada masalah logaritma diskret integer (DLP), di mana kunci peribadi sukar diekstrak secara pengiraan berdasarkan kunci awam, tanpa penyelesaian masa polinomial pada komputer klasik. Penggunaan kunci rawak dan unik memberikan keselamatan tambahan terhadap serangan. Kedua-dua varian medan terhingga integer dan lengkung eliptik bagi protokol DH dan DSA pada masa ini digunakan secara meluas merentasi banyak protokol komunikasi digital moden seperti TLS, SSH, dan lain-lain.

Akhirnya kita melihat kriptografi lengkung eliptik. Dengan saiz kunci yang cekap dan sifat keselamatan yang kukuh, ia kini mewakili pilihan yang cemerlang untuk banyak aplikasi kriptografi, daripada pertukaran kunci hingga tandatangan digital.

Semua algoritma ini terdedah kepada serangan daripada algoritma kuantum, kerana penyelesaian boleh dibangunkan untuk menyelesaikan masalah matematik yang menjadi premis dalam reka bentuk mereka. Salah satu contoh ialah algoritma Shor. Oleh itu, ia perlu digantikan oleh sistem kriptografi asimetri selamat-kuantum yang lebih tahan kepada serangan dari kuantum — sambil tetap selamat dengan algoritma klasik. Masalah matematik yang mereka bergantung padanya boleh diselesaikan dengan cekap oleh komputer kuantum, memerlukan pembangunan sistem kriptografi asimetri selamat-kuantum yang mampu menahan serangan kuantum sambil mengekalkan keselamatan klasik.

Pelajaran akan datang akan melihat sistem kriptografi selamat-kuantum dan membincangkan pendekatan yang diperlukan untuk mengekalkan keselamatan kriptografi.

Source: IBM Quantum docs — updated 4 Mei 2026

English version on doQumentation — updated 7 Mei 2026

This translation based on the English version of approx. 27 Mac 2026

Pengenalan kepada kriptografi kunci asimetrik​

Pertukaran kunci dengan kriptografi kunci asimetrik​

Pertukaran kunci interaktif​

Pertukaran kunci bukan interaktif​

Tandatangan digital dengan kriptografi kunci asimetrik​

Algoritma tandatangan digital khusus​

Skim tandatangan digital menggunakan sistem kripto generik​

Aplikasi kriptografi kunci asimetrik​

Keselamatan kriptografi kunci asimetrik​

Risiko keselamatan kepada kriptografi kunci asimetrik​

RSA​

Algoritma RSA​

Ilustrasi RSA dalam Python​

Penjanaan kunci RSA​

Pertukaran kunci simetrik dengan RSA​

Contoh pertukaran kunci berasaskan padding dalam Python​

Simulasi Mekanisme Enkapsulasi Kunci dengan RSA dalam Python​

Tandatangan digital dengan RSA​

Memecahkan RSA​

Pengkomputeran klasik dan RSA​

Algoritma kuantum Shor dan RSA​

Contoh Python yang menunjukkan pemecahan penyulitan RSA​

Pertukaran kunci Diffie-Hellman dan Algoritma Tandatangan Digital​

Masalah logaritma diskret​

Butiran matematik masalah logaritma diskret​

Pertukaran kunci Diffie-Hellman​

Ilustrasi protokol Diffie-Hellman dalam Python​

Keselamatan pertukaran kunci Diffie-Hellman​

Algoritma Tandatangan Digital (DSA)​

Ilustrasi DSA dalam Python​

Keselamatan DSA​

Pertukaran kunci disahkan dengan Diffie-Hellman dan DSA​

Memecahkan Diffie-Hellman dan DSA​

Algoritma Shor dan masalah logaritma diskret​

Kriptografi lengkung eliptik​

Prinsip asas kriptografi lengkung eliptik​

Masalah logaritma diskret lengkung eliptik​

Pertukaran kunci dengan ECC​

Tandatangan digital dengan ECC​

Memecahkan ECDH dan ECDSA​

Ringkasan​

Pengenalan kepada kriptografi kunci asimetrik

Pertukaran kunci dengan kriptografi kunci asimetrik

Pertukaran kunci interaktif

Pertukaran kunci bukan interaktif

Tandatangan digital dengan kriptografi kunci asimetrik

Algoritma tandatangan digital khusus

Skim tandatangan digital menggunakan sistem kripto generik

Aplikasi kriptografi kunci asimetrik

Keselamatan kriptografi kunci asimetrik

Risiko keselamatan kepada kriptografi kunci asimetrik

RSA

Algoritma RSA

Ilustrasi RSA dalam Python

Penjanaan kunci RSA

Pertukaran kunci simetrik dengan RSA

Contoh pertukaran kunci berasaskan padding dalam Python

Simulasi Mekanisme Enkapsulasi Kunci dengan RSA dalam Python

Tandatangan digital dengan RSA

Memecahkan RSA

Pengkomputeran klasik dan RSA

Algoritma kuantum Shor dan RSA

Contoh Python yang menunjukkan pemecahan penyulitan RSA

Pertukaran kunci Diffie-Hellman dan Algoritma Tandatangan Digital

Masalah logaritma diskret

Butiran matematik masalah logaritma diskret

Pertukaran kunci Diffie-Hellman

Ilustrasi protokol Diffie-Hellman dalam Python

Keselamatan pertukaran kunci Diffie-Hellman

Algoritma Tandatangan Digital (DSA)

Ilustrasi DSA dalam Python

Keselamatan DSA

Pertukaran kunci disahkan dengan Diffie-Hellman dan DSA

Memecahkan Diffie-Hellman dan DSA

Algoritma Shor dan masalah logaritma diskret

Kriptografi lengkung eliptik

Prinsip asas kriptografi lengkung eliptik

Masalah logaritma diskret lengkung eliptik

Pertukaran kunci dengan ECC

Tandatangan digital dengan ECC

Memecahkan ECDH dan ECDSA

Ringkasan