Jaringan Substitusi-Permutasi

Pada pembahasan kali ini, kita beralih dari penyandian teks menjadi penyandian untaian bita secara umum. Karena komputer melihat data sebagai untaian bita-bita, penyandian untaian bita secara umum memampukan kita untuk melakukan penyandian data apa pun, seperti gambar, suara, video, dan dokumen jenis apa pun.

Sandi substitusi dan sandi transposisi (khususnya permutasi) dapat digabungkan menjadi suatu jaringan yang disebut sebagai jaringan substitusi-permutasi (SP). Jaringan SP terdiri atas operasi substitusi (biasa disebut sebagai kotak-S) dan operasi permutasi (kotak-P) yang disusun secara bergantian dan diulang beberapa kali. Jumlah pengulangan SP biasa disebut sebagai jumlah ronde.

Seperti penyandian pada umumnya, jaringan SP mengubah teks pesan menjadi teks tersandi dengan kunci yang diberikan. Untuk mengembalikan teks pesan, teks tersandi dimasukkan ke dalam inversi jaringan SP, yaitu sama dengan jaringan SP, tetapi urutan operasinya dibalik. Sebagai contoh, jaringan K-S-P-K-S-P-K memiliki inversi sebagai berikut: K-P-S-K-P-S-K. K adalah operasi penambahan kunci ke dalam teks.

Komponen Jaringan SP

Kotak-S berisi daftar konversi dari satu bita ke bita lain atau satu untaian bit ke untaian bit lain. Hal ini seperti konversi A menjadi B, lalu B menjadi K, dan seterusnya. Hal ini menyebabkan nilai-nilai bita hasil konversi tidak lagi memiliki hubungan linear terhadap nilai-nilai bita masukan.

Kotak-P berisi cara memetakan suatu bit dalam suatu bita ke bit lain dalam bita lain. Sebagai contoh, dari masukan 8 bita, bit ke-5 dalam bita ke-2 dipetakan ke bit ke-7 dalam bita ke-5. Hal ini menyebabkan susunan bit tidak lagi sama dengan sebelumnya sehingga relasi antara teks pesan dan teks tersandi menjadi sulit dimengerti.

Sebelum, setelah, dan di antara operasi substitusi dan permutasi, terdapat operasi penambahan kunci ke dalam teks. Namun, kunci yang digunakan berbeda-beda untuk tiap ronde, padahal hanya ada satu kunci yang diberikan. Caranya adalah penjadwalan kunci.

Penjadwalan kunci adalah cara untuk mendapatkan nilai kunci yang berbeda-beda untuk tiap ronde berdasarkan satu kunci yang diberikan. Terdapat beberapa cara untuk melakukannya, misalnya TEA membagi kunci 128 bit menjadi empat kunci 32 bit yang digunakan bergantian atau AES memiliki prosedur yang lebih kompleks untuk menjadwalkan kunci.

Contoh Kasus

Sebagai contoh, kita akan menyandikan pesan C5 37 2B 9F dengan menggunakan struktur K-S-P-K-S-P-K dan ukuran masukan empat bita. Selain itu, kunci yang diberikan juga empat bita: 58 65 9F DD.

Spesifikasi Jaringan SP

Berikut adalah nilai kotak-S yang digunakan dalam AES:

	_0	_1	_2	_3	_4	_5	_6	_7	_8	_9	_A	_B	_C	_D	_E	_F
0_	63	7C	77	7B	F2	6B	6F	C5	30	01	67	2B	FE	D7	AB	76
1_	CA	82	C9	7D	FA	59	47	F0	AD	D4	A2	AF	9C	A4	72	C0
2_	B7	FD	93	26	36	3F	F7	CC	34	A5	E5	F1	71	D8	31	15
3_	04	C7	23	C3	18	96	05	9A	07	12	80	E2	EB	27	B2	75
4_	09	83	2C	1A	1B	6E	5A	A0	52	3B	D6	B3	29	E3	2F	84
5_	53	D1	00	ED	20	FC	B1	5B	6A	CB	BE	39	4A	4C	58	CF
6_	D0	EF	AA	FB	43	4D	33	85	45	F9	02	7F	50	3C	9F	A8
7_	51	A3	40	8F	92	9D	38	F5	BC	B6	DA	21	10	FF	F3	D2
8_	CD	0C	13	EC	5F	97	44	17	C4	A7	7E	3D	64	5D	19	73
9_	60	81	4F	DC	22	2A	90	88	46	EE	B8	14	DE	5E	0B	DB
A_	E0	32	3A	0A	49	06	24	5C	C2	D3	AC	62	91	95	E4	79
B_	E7	C8	37	6D	8D	D5	4E	A9	6C	56	F4	EA	65	7A	AE	08
C_	BA	78	25	2E	1C	A6	B4	C6	E8	DD	74	1F	4B	BD	8B	8A
D_	70	3E	B5	66	48	03	F6	0E	61	35	57	B9	86	C1	1D	9E
E_	E1	F8	98	11	69	D9	8E	94	9B	1E	87	E9	CE	55	28	DF
F_	8C	A1	89	0D	BF	E6	42	68	41	99	2D	0F	B0	54	BB	16

Untuk kasus ini, kita bisa membuat kotak-P agar menukar satu bita dengan bita sebelahnya. Sebagai contoh, empat bit pertama dari bita ke-1 ditukar dengan empat bit kedua dari bita ke-2, empat bit pertama dari bita ke-3 ditukar dengan empat bit kedua dari bita ke-4, dan seterusnya.

Operasi penambahan kunci hanya melakukan XOR dengan kunci. Selain itu, penjadwalan kunci yang akan kita gunakan sederhana, yaitu hanya melakukan geseran melingkar ke kiri (<<<) sebanyak satu bita untuk tiap ronde.

Perhitungan

Perhitungan dari kasus di atas ditunjukkan dalam tabel berikut:

Operasi	Teks				Kunci
Keadaan awal	C5	37	2B	9F	58	65	9F	DD
Penambahan kunci	9D	52	B4	42	58	65	9F	DD
Substitusi	5E	00	8D	2C	<<<
Permutasi	0E	05	CD	28
Penambahan kunci	6B	9A	10	70	65	9F	DD	58
Substitusi	7F	B8	CA	51	<<<
Permutasi	8F	B7	1A	5C
Penambahan kunci	10	6A	42	39	9F	DD	58	65

Hasil penyandiannya adalah 10 6A 42 39.

Bonus: Program C

Program C

#include <stdio.h>
#include <stdint.h>

#define UKURAN 4

void penambahanKunci(uint8_t *A, const uint8_t *kunci) { // K
	for (int i = 0; i < UKURAN; i ++)
		A[i] ^= kunci[i];
}

void substitusi(uint8_t *A, const uint8_t *kotakS) { // S
	for (int i = 0; i < UKURAN; i ++)
		A[i] = kotakS[A[i]];
}

void permutasi(uint8_t *A) { // P
	for (int i = 0; i < UKURAN; i += 2) {
		uint8_t lawas1 = A[i + 0];
		uint8_t lawas2 = A[i + 1];
		A[i + 0] = lawas1 & 0x0F | (lawas2 << 4) & 0xF0;
		A[i + 1] = lawas2 & 0xF0 | (lawas1 >> 4);
	}
}

void geserKunci(uint8_t *kunci) { // <<<
	uint8_t k = kunci[0];
	for (int i = 0; i < UKURAN - 1; i ++)
		kunci[i] = kunci[i + 1];
	kunci[UKURAN - 1] = k;
}

void jaringanSP(uint8_t *pesan, uint8_t *kunci, const uint8_t *kotakS) {
	penambahanKunci(pesan, kunci); // K
	substitusi(pesan, kotakS);     // S
	permutasi(pesan);              // P
	geserKunci(kunci);             // <<<
	penambahanKunci(pesan, kunci); // K
	substitusi(pesan, kotakS);     // S
	permutasi(pesan);              // P
	geserKunci(kunci);             // <<<
	penambahanKunci(pesan, kunci); // K
}

int main() {
	uint8_t pesan[] = {0xC5, 0x37, 0x2B, 0x9F};
	uint8_t kunci[] = {0x58, 0x65, 0x9F, 0xDD};
	uint8_t kotakS[256] = {};
	// https://id.wikipedia.org/wiki/Kotak-S_Rijndael
	initialize_aes_sbox(kotakS);
	jaringanSP(pesan, kunci, kotakS);
	printf("%X %X %X %X\n", pesan[0], pesan[1], pesan[2], pesan[3]);
	return 0;
}

Prinsip Shannon

Jaringan SP memenuhi prinsip pengacakan dan penghamburan Shannon.

• Pengacakan: Bila salah satu bit teks pesan diubah, hasil dari kotak-S akan jauh berbeda yang kemudian akan makin tersebar oleh kotak-P. Hal ini berulang dalam beberapa ronde. Hasilnya adalah teks tersandi sulit untuk ditebak hanya dengan perubahan kecil.
• Penghamburan: Bila salah satu bit kunci diubah, kunci ronde disebar ke seluruh/potongan teks sehingga perubahan teks tersandi sulit dilacak.

Penutup

Sekian dahulu tulisanku kali ini. Aku sudah ingin membahas ini sejak lama, terutama bagian menulis kode programnya, tetapi menunggu tulisan pembahasan sandi substitusi dan sandi transposisi selesai agar pembahasannya runtut. Semoga bermanfaat!