SIDH dan SIKE: Reka Bentuk dan Kriptanalisis

Supersingular Isogeni Diffie-Hellman (SIDH), yang dicadangkan oleh Jao dan De Feo pada tahun 2011, ialah protokol pertukaran kunci awam yang seumpama Diffie-Hellman tetapi menggunakan isogeni pada lengkung eliptik supersingular. Kedua-dua pihak bermula dengan lengkung supersingular E yang sama di atas Fp2. Alice mengira isogeni rahsia phi_A: E -> E_A (teras rawak dalam 2^a-kilasan), menerbitkan E_A dan imej penjana kilasan Bob di bawah phi_A. Bob mengira phi_B: E -> E_B (teras rawak dalam 3^b-kilasan), menerbitkan E_B dan imej penjana kilasan Alice di bawah phi_B. Alice menggunakan data terbitan Bob untuk mengira phi_A': E_B -> E_AB; Bob mengira phi_B': E_A -> E_AB. Kedua-duanya memperoleh j(E_AB) sebagai rahsia bersama.

Bentuk perdana khas SIDH p = 2^a * 3^b * f - 1 (f ialah faktor bersama kecil untuk keprimaan) memastikan lengkung E di atas Fp2 mempunyai struktur kilasan yang diperlukan. Bagi SIKEp434 (NIST Tahap 1, keselamatan pascakuantum 128 bit): p = 2^216 * 3^137 - 1, a = 216, b = 137. Ini bermaksud Alice menempuh 216 langkah isogeni-2, manakala Bob menempuh 137 langkah isogeni-3. Saiz kunci: kunci awam Alice ialah E_A ditambah dua titik Fp2 (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 bait. SIKEp751 menyasarkan keselamatan klasik 192 bit / kuantum 128 bit dan mempunyai kunci awam berukuran 564 bait. Ini ialah kunci awam paling kecil antara semua calon NIST PQC — dengan kos kelajuan 100 hingga 1000 kali lebih perlahan.

SIKE (Pengkapsulan Kunci Isogeni Supersingular) ialah KEM selamat IND-CCA2 yang dibina daripada SIDH menggunakan transformasi Fujisaki-Okamoto. SIKE.Encaps: memilih mesej rawak m, mengira (c0 = kunci awam SIDH dengan benih m, c1 = H2(m) XOR pk), kemudian menghantar (c0, c1). SIKE.Decaps: memulihkan m daripada c0 menggunakan kunci rahsia, mengesahkan c1, mengira semula (c0, c1) untuk menyemak ketekalan, kemudian mengeluarkan K = H3(m, c0). Transformasi FO menukarkan pertukaran SIDH yang selamat terhadap CPA kepada KEM selamat CCA2. SIKE menyertai kesemua empat pusingan NIST PQC (2017-2022) dan bertahan daripada analisis kriptografi yang meluas — sehingga serangan klasik yang dahsyat muncul pada Julai 2022.

Dari tahun 2011 hingga 2022, SIDH bertahan daripada usaha kriptanalisis yang besar. Serangan terbaik yang diketahui terhadap SIDH ialah: (1) Algoritma SSIP generik: O(p^{1/4}) secara klasik, O(p^{1/6}) secara kuantum menggunakan algoritma Tani. (2) Kaedah temu di tengah pada laluan isogeni: O(p^{1/4}) secara klasik, sama seperti SSIP. (3) Algoritma masa polinomial untuk serangan struktur khusus (van Oorschot-Wiener): tidak terpakai pada SIDH. Berpuluh-puluh makalah menganalisis keselamatan SIDH, dan tiada serangan klasik atau kuantum masa polinomial ditemui selama 11 tahun. Rekod ini menjadikan SIKE finalis NIST yang boleh dipercayai. Pemecahan akhirnya bukan datang daripada serangan langsung terhadap SSIP, sebaliknya daripada eksploitasi maklumat titik kilasan tambahan SIDH.

Pada 30 Julai 2022, Wouter Castryck dan Thomas Decru menerbitkan pracetak yang menunjukkan serangan klasik masa polinomial terhadap SIDH. Serangan itu menggunakan maklumat tambahan dalam titik kilasan tambahan SIDH phi_A(P_B), phi_A(Q_B): maklumat ini pada asasnya mendedahkan tindakan phi_A pada subkumpulan kilasan 3^b. Bersama-sama lengkung imej E_A, hal ini membolehkan pembinaan semula teras phi_A (dan seterusnya phi_A itu sendiri) menggunakan teknik daripada teori lengkung eliptik dengan pendaraban kompleks dan isogeni Richelot. Serangan itu dilaksanakan dalam masa 62 minit pada komputer riba untuk SIKEp434 — satu set parameter yang sepatutnya menyediakan keselamatan pascakuantum 128 bit. Dalam beberapa hari, penyelidik bebas mengesahkan dan mengembangkan serangan itu kepada semua parameter SIDH.

Reka bentuk SIDH memerlukan kedua-dua pihak menerbitkan imej titik asas kilasan pihak lain di bawah isogeni rahsia mereka. Hal ini diperlukan supaya protokol dapat berfungsi: tanpa phi_A(P_B) dan phi_A(Q_B), Bob tidak dapat memindahkan isogeninya ke lengkung Alice untuk mengira rahsia bersama. Namun, maklumat tambahan ini — yang mendedahkan tindakan phi_A yang dihadkan kepada kilasan 3^b — ternyata memberikan jauh lebih banyak maklumat daripada yang dijangkakan, dengan akibat yang amat buruk. Serangan Castryck-Decru menggunakan lengkung genus-2 (isogeni Richelot) untuk mengangkat masalah itu kepada objek bergenus lebih tinggi, yang tindakannya selepas dihadkan menentukan phi_A sepenuhnya. Kebocoran ini merupakan ciri struktur SIDH dan tidak dapat dibaiki tanpa mengubah reka bentuk asas protokol.

Pada 5 Julai 2022 (sebelum Castryck-Decru), NIST telah mengumumkan pilihan penstandardan PQC awalnya: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+), dan FN-DSA (Falcon) — SIKE tidak termasuk dalamnya (ia berada dalam pusingan pertimbangan kedua). Serangan Castryck-Decru pada Julai 2022 menyebabkan NIST menyingkirkan SIKE secara rasmi daripada pertimbangan sepenuhnya. NIST menyatakan: "SIKE tidak lagi dipertimbangkan untuk penstandardan." Ini merupakan perkembangan kriptanalisis paling dramatik dalam pertandingan PQC NIST, yang menunjukkan bahawa skim yang bertahan daripada analisis selama 11 tahun pun boleh dipecahkan melalui wawasan matematik yang benar-benar baharu.

Dalam masa seminggu selepas Castryck-Decru, Thomas Decru dan Luciano Maino secara bebas, kemudian Damien Robert, menerbitkan penambahbaikan selanjutnya. Varian serangan Robert menggunakan wawasan yang sama tetapi mengira gelanggang endomorfisme E_A, bukannya mengira teras isogeni secara langsung, dan secara matematik mungkin lebih mudah untuk dihuraikan. Penemuan semula secara bebas yang pantas ini mengesahkan bahawa serangan Castryck-Decru mengenal pasti kelemahan struktur asas, bukannya helah yang kabur. Kepantasan makalah-makalah berikutnya juga mencerminkan bilangan penyelidik yang telah mengkaji kebocoran titik kilasan SIDH sebagai vektor serangan yang berpotensi; mereka menyedari bahawa pendedahan maklumat itu luar biasa tetapi tidak dapat mengeksploitasinya sehingga Castryck dan Decru menemui penghubung genus-2.

FESTA (Penyulitan Pantas daripada Serangan Kilasan Supersingular, 2023) ialah reka bentuk KEM yang mengambil ilham daripada SIDH tetapi mengelakkan data titik kilasan tambahan. FESTA menggunakan struktur protokol yang berbeza: kunci awam tidak mengandungi imej asas kilasan pihak satu lagi — sebaliknya, isogeni rahsia diikat melalui lengkung imej sahaja (tanpa titik tambahan). FESTA melakukan penyulitan menggunakan isogeni dengan cara yang mendedahkan kurang maklumat struktur. Analisis keselamatan awal menunjukkan bahawa FESTA mengelakkan struktur serangan Castryck-Decru. Walau bagaimanapun, FESTA lebih baharu dan menerima penelitian yang lebih sedikit berbanding rekod analisis SIKE selama 11 tahun, lalu komuniti isogeni berhati-hati untuk menggunakan skim baharu sebelum analisis yang meluas dijalankan.

Pemecahan SIKE memberikan pengajaran penting. (1) Pendedahan maklumat tambahan adalah berbahaya: data titik kilasan tambahan SIDH diperlukan untuk protokol, tetapi membocorkan maklumat secara membawa padah. Pereka bentuk protokol mesti menganalisis setiap cebisan data awam, bukan hanya nilai utama. (2) Rekod prestasi bukan bukti keselamatan: 11 tahun tanpa serangan yang diketahui memang meyakinkan, tetapi bukan jaminan. Bukti kriptografi (pengurangan kepada masalah sukar yang ditakrifkan dengan jelas) lebih boleh dipercayai berbanding hujah berdasarkan kewibawaan atau hakikat bahawa sesuatu skim telah bertahan daripada penelitian. (3) Alat matematik baharu mencipta risiko: serangan Castryck-Decru menggunakan isogeni Richelot genus-2 — alat daripada matematik yang belum pernah digunakan sebelum ini dalam kriptanalisis isogeni. Kriptanalisis terhadap primitif baharu mesti mengambil kira bidang matematik yang baharu.

Walaupun SIKE telah dipecahkan, kriptografi berasaskan isogeni terus berkembang sebagai bidang penyelidikan. Tandatangan SQISign (177 bait pada Tahap 1) kekal sebagai tandatangan PQC paling padat yang diketahui dan menggunakan andaian kesukaran yang berbeza (masalah gelanggang endomorfisme) yang tidak terjejas oleh serangan SIDH. Protokol berasaskan CSIDH menggunakan struktur tindakan kumpulan kelas (isogeni komutatif) tanpa kebocoran titik kilasan, walaupun CSIDH menghadapi cabarannya sendiri (lebih perlahan berbanding SIDH dahulu, dengan analisis keselamatan kuantum yang masih berjalan). Komuniti isogeni melihat pemecahan SIKE sebagai pengalaman pembelajaran yang memperjelas maklumat yang mesti disembunyikan dalam protokol isogeni — pengetahuan bernilai untuk mereka bentuk skim masa hadapan.

SIDH menggunakan rantaian isogeni 2^a dan 3^b yang berselang-seli antara dua pihak, dengan berkongsi imej titik kilasan tambahan untuk membolehkan pertukaran kunci. SIKE menggabungkan SIDH dengan Fujisaki-Okamoto untuk keselamatan CCA2. SIKE mempunyai kunci paling kecil antara semua calon NIST PQC (374 bait), tetapi 100 hingga 1000 kali lebih perlahan. Selepas 11 tahun analisis keselamatan, Castryck-Decru memecahkan SIKE pada Julai 2022 menggunakan isogeni Richelot genus-2 untuk mengeksploitasi kebocoran titik kilasan. NIST menyingkirkan SIKE. FESTA mengelakkan pendedahan titik kilasan. SQISign terus menggunakan kesukaran gelanggang endomorfisme. Pemecahan SIKE menunjukkan bahawa data awam tambahan mesti dianalisis dengan ketelitian yang sama seperti nilai protokol utama.