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!

Sandi Transposisi: Scytale, Sandi Pagar, dan Transposisi Kolom

Selain sandi substitusi, bentuk dasar penyandian adalah sandi transposisi.

Sandi transposisi adalah penyandian yang mengubah susunan pesan sesuai aturan tertentu. Pengubahan susunan ini bisa diterapkan dengan cara yang sama untuk keseluruhan pesan atau berbeda-beda untuk tiap bagian/potongan pesan. Yang dimaksud potongan pesan adalah unit terkecil yang diperhatikan oleh sandi tertentu. Sebagai contoh, untuk pesan berupa teks, unit terkecilnya bisa berupa huruf/karakter/bita.

Sebagai contoh, pesan AKU​LELAKI​YANG​KEREN​BANGET disandikan menjadi UKGNE​KANEG​EYEAX​LIKBT​ALARN. Untuk membuka sandi, penyerang bisa mencoba kata atau frasa yang memiliki huruf-huruf yang sama, seperti GAYA, LAKU, dan LELANG, tetapi memerlukan waktu karena terdapat banyak kombinasi huruf dan kata. Sebaliknya, pihak yang memiliki kunci dapat membuka sandi dengan mudah.

Pada praktiknya, pesan sependek dan semudah diprediksi itu akan dipecahkan dalam waktu singkat. Namun, dalam keadaan yang tepat, seperti pesan yang cukup panjang (lebih dari 200 huruf), isi pesan yang tidak mudah diprediksi, dan kunci yang berbeda untuk tiap pesan, menebak kata yang tepat akan sangat sulit tanpa informasi lebih lanjut mengenai isi pesan.

Scytale

Scytale adalah salah satu alat untuk melakukan sandi transposisi. Scytale tersusun dari silinder dengan lembaran panjang yang melilitinya secara menyamping. Pesan ditulis secara menurun pada silinder, lalu lilitan lembaran dibuka. Hasilnya adalah teks tersandi.

Contohnya pesan MEREKAPUNYAPEMANAH dengan jumlah kolom = 3 berikut.

    | M | E | R | E | K | A |   |
 ___| P | U | N | Y | A | P |___|
|   | E | M | A | N | A | H |

Setelah lilitan lembaran dibuka, akan terbaca MPEEUM RNAEYN KAAAPH.

Sandi Pagar

Sandi rel pagar (rail fence) dinamai demikian karena cara penyusunannya yang naik-turun secara diagonal melintasi "rel". Setelah itu, teks dibaca per baris atau per "rel". Sandi rel pagar adalah pengembangan dari scytale.

Contohnya pesan KABAR​GEMBIRA​UNTUK​KITA​SEMUA dan jumlah rel = 3 berikut.

K-------R-------B-------U-------K-------A-------U--
--A---A---G---M---I---A---N---U---K---T---S---M---A
----B-------E-------R-------T-------I-------E------

Kemudian, baca per baris menjadi KRBUKAU, AAGMIANUKTSMA, dan BERTIE. Dengan pemisahan per empat huruf, teks tersandi menjadi KRBU KAUA AGMI ANUK TSMA BERT IE.

Transposisi Kolom

Transposisi kolom memerlukan sebuah kunci yang kemudian digunakan sebagai acuan dalam menyusun pesan, misalnya dengan mengurutkan kunci sesuai urutan alfabet. Bila panjang pesan bukan kelipatan panjang kunci, pesan diberi bantalan agar jumlahnya sesuai.

Contohnya pesan AKU​LELAKI​YANG​KEREN​BANGET dengan kunci RIFQI berikut.

R I F Q I    Kunci
5 2 1 4 3    Urutan sesuai alfabet
A K U L E    Teks yang disusun
L A K I Y    mendatar selebar
A N G K E    panjang kunci
R E N B A
N G E T X    Bantalan

Huruf yang sama diurutkan berdasarkan kemunculannya.

Kemudian, tulis secara menurun sesuai urutan kolom, yaitu (1) UKGNE, (2) KANEG, (3) EYEAX, (4) LIKBT, dan (5) ALARN. Setelah itu, gabungkan seluruhnya menjadi UKGNE​KANEG​EYEAX​LIKBT​ALARN. Biasanya, penulisan teks tesandi dipisah beberapa huruf agar mudah dibaca, misal UKGNE KANEG EYEAX LIKBT ALARN.

Penutup

Sekian dahulu yang bisa kutulis. Masih ada beberapa penyandian lain yang termasuk sandi transposisi. Namun, intinya tetap sama, yaitu mengubah susunan/urutan pesan. Semoga bermanfaat!

Sandi Substitusi: Sandi Geser, Tabel Substitusi, dan Sandi Vigenère

Sebelumnya, aku menulis tentang sandi geser. Namun, sandi geser hanyalah salah satu sandi dari kelompok sandi substitusi.

Sandi substitusi adalah penyandian yang mengganti (substitusi) satu nilai dengan nilai lain berdasarkan aturan tertentu. Penggantian ini bisa diterapkan dengan cara yang sama untuk keseluruhan pesan atau berbeda-beda untuk tiap bagian/potongan pesan. Yang dimaksud potongan pesan adalah unit terkecil yang diperhatikan oleh sandi tertentu. Sebagai contoh, untuk pesan berupa teks, unit terkecilnya bisa berupa huruf/karakter.

Sandi Geser

Sandi geser/sandi Caesar adalah penyandian yang dilakukan dengan cara "menggeser" nilai tiap potongan pesan. Penggeseran ini dilakukan ke arah tertentu dan sejumlah tertentu pula. Ini yang dipakai dalam contoh soal pada tulisanku sebelumnya. Sandi ini cukup kuno dan biasanya hanya untuk pembelajaran dan pesan yang diterapkan berbentuk teks.

Sebagai contoh, sandi geser dengan arah geser ke kiri (positif) dan jumlah geser 7 mengubah deretan ABCDE menjadi HIJKL.

Diagram pergeseran huruf-huruf dalam alfabet

Secara matematis, fungsi sandi geser didefinisikan sebagai berikut:
Misalkan potongan pesan dan potongan teks tersandi adalah gelanggang ${\mathbb{Z}}_{26}$,
$$e_K\left(x\right)=(x+K)mod26$$ dan
$$d_K\left(y\right)=(y-K)mod26$$ dengan $x,y\in {\mathbb{Z}}_{26}$.

Tabel Substitusi

Tabel substitusi adalah tabel yang berisi pemetaan dari suatu nilai ke nilai lain. Tabel substitusi digunakan dalam oleh substitusi untuk mengubah tiap potongan pesan menjadi nilai tertentu. Sandi geser adalah kasus khusus dari tabel substitusi (yang disusun agar nilai teks tersandi hanya berjarak sekian dari nilai teks asli).

Sebagai contoh, tabel substitusi berikut:

Nilai teks asli	Nilai teks tersandi
A	X
B	Y
C	Z

mengubah teks asli BACA menjadi teks tersandi YXZX.

Secara matematis, fungsi sandi substitusi didefinisikan sebagai berikut:
$$e_{\pi }\left(x\right)=\pi \left(x\right)$$ dan
$$d_{\pi }\left(y\right)={\pi }^{-1}\left(y\right)$$ dengan $\pi$ adalah tabel substitusi dan ${\pi }^{-1}$ adalah inversi tabel substitusi.

Sandi Vigenère

Bila sandi-sandi sebelumnya diterapkan dengan cara yang sama untuk tiap potongan pesan, sandi Vigenère menerapkan penyandian dengan cara yang berbeda-beda untuk tiap potongan pesan. Sandi Vigenère merupakan pengembangan dari sandi Caesar.

Sebagai contoh, untuk nilai geser (1, 2, 3), teks asli ABC disandikan menjadi BDF. Huruf A digeser sekali (A menjadi B); huruf B digeser dua kali (B menjadi D); huruf C digeser tiga kali (C menjadi F).

Secara matematis, sandi Vigenère didefinisikan sebagai berikut:
Misalkan potongan pesan dan potongan teks tersandi adalah ${\left({\mathbb{Z}}_{26}\right)}^m$,
$$e_K(x_1,x_2,\mathrm{...},x_m)=(x_1+k_1,x_2+k_2,\mathrm{...},x_m+k_m)$$ dan
$$d_K(y_1,y_2,\mathrm{...},y_m)=(y_1-k_1,y_2-k_2,\mathrm{...},y_m-k_m)$$ dengan keseluruhan perhitungan dilakukan dalam gelanggang ${\mathbb{Z}}_{26}$.

Penutup

Sekian dahulu yang bisa kutulis. Tulisan ini bisa dibilang cukup spontan. Jadi, tulisannya agak berantakan. Namun, isinya masih menarik buatku. Semoga bermanfaat!