Jaringan substitusi–permutasi

Dalam kriptografi, jaringan substitusi–permutasi (jaringan SP, bahasa Inggris: substitution–permutation network, disingkat SPN) adalah rangkaian operasi matematis yang terhubung berturut-turut dan dipakai dalam penyandian blok, seperti AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, dan Square.

Sketsa jaringan substitusi–permutasi dengan tiga ronde yang mengenkripsi blok 16 bit. Kotak-S dinamai S_i, kotak-P dinamai P_i, dan kunci ronde dinamai K_i.

Jaringan ini mengambil seblok teks asal dan kunci sebagai masukan, lalu menerapkan substitusi (kotak-S) dan permutasi (kotak-P) secara bergantian untuk membuat blok teks tersandi. Kotak-S dan kotak-P mengubah bit-bit subblok menjadi bit-bit lain. Umumnya, transformasi ini adalah operasi yang efisien dilakukan dalam perangkat keras, seperti XOR dan rotasi bit demi bit. Tiap kunci diterapkan untuk tiap ronde dalam bentuk kunci ronde yang dibuat darinya. Pada beberapa desain jaringan, kotak-S yang dipakai bergantung pada kunci tersebut.

Dekripsi dapat dilakukan hanya dengan membalik prosesnya dengan menggunakan inversi kotak-S dan inversi kotak-P serta menerapkan kunci ronde dalam urutan yang dibalik.

Komponen pendukung

Kotak-S menukar (substitusi) blok bit kecil dengan blok bit lainnya sesuai tabel yang telah ditentukan. Substitusi ini harus korespondensi satu-satu untuk menjamin proses dekripsi. Selanjutnya, panjang bit penukar harus sama dengan panjang bit asal. Hal ini berbeda dengan kotak-S pada umumnya yang dapat berbeda panjangnya, seperti yang dipakai dalam Standar Enkripsi Data (DES). Kotak-S bukan sekadar permutasi bit-bitnya. Kotak-S yang baik akan memiliki sifat bahwa mengganti satu bit pada masukan akan mengubah paling tidak setengah bit pada keluaran (efek salju longsor). Kotak ini juga memiliki sifat bahwa tiap bit keluaran bergantung pada tiap bit masukan.

Kotak-P adalah permutasi seluruh bit. Kotak-P menerima keluaran kotak-S dan menyebarkan tiap bit ke kotak-S yang lain. Kotak-P yang baik memiliki sifat bahwa bit hasil kotak-S disebar merata ke sebanyak mungkin kotak-S lain.

Untuk tiap ronde, kunci ronde (diambil dari kunci utama dengan operasi tertentu) digabungkan dalam operasi pengelompokkan tertentu, misal operasi XOR.

Sifat-sifat

Kotak-S dan kotak-P tidak dapat memberikan kekuatan kriptografis sendirian. Kotak-S dapat diibaratkan sebagai sandi substitusi; kotak-P dapat diibaratkan sebagai sandi transposisi. Namun, jaringan SP yang baik dengan beberapa ronde kotak-S dan kotak-P telah memenuhi prinsip pengacakan dan penghamburan Shannon:

• Bila salah satu bit teks asli diubah, lalu dimasukkan ke dalam kotak-S yang mengubah beberapa bit, lalu bit-bit tersebut disebar oleh kotak-P ke beberapa kotak-S, lalu diulang beberapa ronde, hasil keluarannya akan berubah total. Dengan kata lain, untuk blok teks asal acak, bila bit kesekian diganti, setengah hasil akan berubah. Begitu pula sebaliknya. Jaringan SP tidak mudah ditebak hanya dari perubahan yang kecil. Inilah yang menyebabkan jaringan ini memenuhi prinsip pengacakan Shannon.
• Pengubahan salah satu bit pada kunci akan mengubah seluruh kunci ronde yang akan disebar ke seluruh blok sehingga teks hasil berubah dengan perubahan yang sulit dilacak. Inilah yang menyebabkan jaringan ini memenuhi prinsip penghamburan Shannon.
• Meski penyerang dapat mengetahui teks asli dan hasil penyandiannya, pengacakan dan penghamburannya menyulitkan penyerang untuk mencari kuncinya.

Kinerja

Meski sandi Feistel yang menggunakan kotak-S (seperti DES) mirip dengan jaringan SP, ada beberapa perbedaan yang membuat keduanya hanya cocok untuk keadaan tertentu. Untuk sejumlah pengacakan dan penghamburan, jaringan SP memiliki paralelisme bawaan sehingga dapat dihitung lebih cepat daripada sandi Feistel untuk prosesor dengan banyak unit eksekusi. Prosesor dengan unit eksekusi yang sedikit (seperti kartu pintar) tidak dapat memanfaatkan paralelisme bawaan. Terlebih lagi, jaringan SP membutuhkan inversi kotak-S sehingga memerlukan penyimpanan lebih besar daripada sandi Feistel yang dapat disusun dari fungsi satu arah.

Lihat pula

• Sandi Feistel
• Standar Enkripsi Lanjutan, contoh algoritme yang menerapkan jaringan SP

Referensi

1. Bart Preneel, Vincent Rijmen, dan Antoon Bosselaers. "Principles and Performance of Cryptographic Algorithms". Pemeliharaan CS1: Menggunakan parameter penulis (link)
2. Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, dan Jesse Walker (2008). (PDF). Diarsipkan dari versi asli (PDF) tanggal 2009-01-15. Diakses tanggal 2020-10-10. Pemeliharaan CS1: Menggunakan parameter penulis (link)

Bacaan lebih lanjut

• Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography. CRC Press. ISBN 978-1-5848-8551-1. 
• Stinson, Douglas R. (2006). Cryptography. Theory and Practice (edisi ke-3). Chapman & Hall/CRC. ISBN 1584885084.