Contoh soal pembuktian Matematika Lanjut dengan Induksi

Berikut adalah contoh pembuktian beberapa soal matematika lanjut untuk Kriptografi yang pernah menjadi tugas dari kuliah Matematika Lanjut. Pembuktian dengan metode Induksi.

• Buktikan untuk setiap \(n\)  bilangan bulat positif berlaku \(1 +3+5+...+(2n-1)=n^{2}\)

Jawaban :

1.  Uji untuk nilai \(n\) terkecil, yaitu \(n=1\);  \((2n-1)=n^{2}\Rightarrow (2.1-1) =1^{2}\Rightarrow1=1\) ......(Benar)

2. Asumsikan untuk \(n=k\) , \(k\) bilangan bulat positif,  \(1+2+3+...+(2k-1)=k^{2}\) adalah benar.

3. Buktikan untuk \(n=k+1\) :
\(\Rightarrow 1+2+3+...+(2k-1)+(2(k+1)-1)=(k+1)^{2}\),
Dengan memasukkan persamaan pd no. 2  didapat :
\(\Rightarrow k^{2}+(2k+2-1)=k^{2}+2k+1\)
\(\Rightarrow k^{2}+2k+1 = k^{2}+2k+1\)
Jadi terbukti untuk setiap \(n\)  bilangan bulat positif berlaku \(1 +3+5+...+(2n-1)=n^{2}\)

• Buktikan untuk setiap \(n\) bilangan bulat positif dan \(n\geq2\) berlaku : \(5^{n}+9<6^{n}\)

Jawaban :

1. Uji untuk nilai \(n\) terkecil, yaitu \(n=2\),
\(5^{2}+9<6^{2}\Rightarrow 34 < 36\)......(Benar)

2. Asumsikan untuk \(n=k\), \(k\) bilangan bulat positif, \(5^{k}+9<6^{k}\) adalah benar.
\(6(5^{k}+9)<6.6^{k}\) ....(kedua ruas dikalikan 6) didapatkan :
\(6.5^{k}+54<6.6^{k}\)......(Berarti bisa diasumsikan jika ini juga benar).

3.  Buktikan untuk \(n=k+1\) :
\(\Rightarrow 5^{k+1}+9<6^{k+1}\)
\(\Rightarrow 5^{k+1}+9<6^{k}.6^{1}\)
\(\Rightarrow 5^{1}.5^{k}+9<6^{1}.6^{k}\)
\(5.5^{k}+9<6.6^{k}\)
Dari persamaan pada no.2 kita ketahui benar bahwa :
\(6.5^{k}+54<6.6^{k}\)
Berarti ini juga benar bahwa :
\(5.5^{k}+9<6.6^{k}\),
atau bisa dituliskan :
\(5.5^{k}+9<6.5^{k}+54\)
karena :
\(5.5^{k}<6.5^{k}\)  dan \(9<54\)

Jadi terbukti untuk setiap \(n\) bilangan bulat positif dan \(n\geq2\) berlaku \(5^{n}+9<6^{n}\)

Bezout Identity

<<Algoritama Eucledian
Sebelum kita sampai pada karakteristik ketiga dari gcd, kita harus bisa melakukan algoritma Euclidean ke belakang. Ini kadang dikenal sebagai identitas Bezout. Kalau di Indonesia dikenal dengan nama Kombinasi Lanjar (Linier Combination).

Teorema Bezout Identity.

Misalkan \(a\) dan \(b\) adalah dua buah bilangan bulat positif, maka terdapat bilangan bulat \(x\) dan \(y\) sedemikian sehingga \(GCD(a,b) = ax + by\).

Algoritma Euclidean

<<GCD
Di dalam Pembagi Persekutuan Terbesar telah diperlihatkan bahwa untuk mencari GCD dari dua buah bilangan bulat a dan b, mula-mula kita mendaftarkan semua pembagi dari masing-masing a dan b, lalu memilih pembagi persekutuan yang bernilai paling besar.

Pada bagian ini akan diberikan metode untuk menemukan GCD, yang dikenal dengan nama Algoritma Euclidean. Algoritma ini sudah dikenal sejak lama. Euclid, penemu algoritma ini adalah seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element.

Algoritma Euclidean didasarkan pada Teorema Algoritma Pembagian  secara berturut-turut sampai kita menemukan sisa pembagian bernilai 0. Secara formal algoritma Euclidean dirumuskan sebagai berikut:

Misalkan a dan b adalah bilangan bulat positif dengan \(a\geq b\). Misalkan \(r_{0}=a\) dan \(r_{1}=b\). Lakukan secara berturut-turut Teorema Algoritma Pembagian untuk memperoleh :

\(r_{0} = r_{1}q_{1}+r_{2}\)             \(0\leq r_{2}\leq r_{1} \)

\(r_{1} = r_{2}q_{2}+r_{3}\)             \(0\leq r_{3}\leq r_{2} \)

.

.

.

\(r_{n-2} = r_{n-1}q_{n-1}+r_{n}\)    \(0\leq r_{n}\leq r_{n-1} \)

\(r_{n-1} = r_{n}q_{n}+0\)

Menurut Teorema Algoritma Euclidean,

\(GCD(a,b)=GCD(r_{0},r_{1})=GCD(r_{1},r_{2})=...=GCD(r_{n-2},r_{n-1})=GCD(r_{n-1},r_{n})=GCD(r_{n},0)=r_{n}\)

Extended GCD.

Bezout Identity>>

Pembagi Persekutuan Terbesar

<<Algoritma Pembagian

Pembagi Persekutuan Terbesar (PBB) atau Faktor Persekutuan Terbesar (FPB) atau bisa juga disebut Pembagi Bersama Terbesar, dalam bahasa Inggris disebut The Greatest Common Divisor (GCD).

Dua buah bilangan bulat dapat memiliki faktor pembagi yang sama. Faktor pembagi bersama yang terpenting adalah GCD. Misalnya 45 memiliki faktor pembagi 1, 3, 5, 9, 15 dan 45 sendiri; sedangkan 36 memiliki faktor pembagi 1, 2, 3, 4, 9, 12, 18, dan 36 sendiri. Faktor pembagi bersama dari 45 dan 36 adalah 1, 3, dan 9. Yang terbesar adalah 9 sehingga disimpulkan GCD(45,36) = 9

Untuk mencari GCD pada Sagemath dapat dilakukan dengan cara di bawah ini.

Definisinya adalah sebagai berikut :

Misalkan \(a\) dan \(b\) adalah dua buah bilangan bulat tidak 0. GCD dari \(a\) dan \(b\) adalah bilangan bulat terbesar \(d\) sedemikian hingga \(d|a\) dan \(d|b\) . Dalam hal ini dinyatakan sebagai \(GCD(a,b) = d\).

Sifat-sifat dari GCD dinyatakan dalam Teorema di bawah ini:

Misalkan a, b, dan c adalah bilangan bulat.

Jika \(c\) adalah GCD dari \(a\) dan \(b\), maka \(c|a+b\). 

Jika \(c\) adalah GCD dari \(a\) dan \(b\), maka \(c|a-b\). 

Jika \(c|a\), maka \(c|ab\).

Algoritma Eucledian>>

Algoritma Pembagian

Jika kita membagi bilangan bulat a dengan b (bilangan bulat positif), Maka kita akan selalu mendapatkan bilangan bulat sisa r yang tidak negatif, namun kurang dari b. 

Teorema Algoritma Pembagian.   
Untuk  \(a,b \in Z\) dan \(b > 0\) kita dapat menulis \(a = kb + r\) dengan  \(0 \leq r < b\)

Sesuai Algoritma Pembagian di atas, sangat mudah untuk melakukan pembagian pada contoh bilangan yang tidak terlalu besar seperti contoh berikut  :
 \(a = 13\) dan \(b = 3\),
\[13 = 4.3 + 1\] sehingga \(q = 4\) dan \(r = 1\)
Untuk pembagian bilangan bulat yang lebih besar maka kita bisa menggunakan bantuan Sagemath sebagai berikut :

Jika ingin mengetahui tentang fungsi \(divmod\), ketik saja \(divmod?\) di dalam Sage Cell seperti di bawah ini.

GCD>>

Affine Cipher

<<Caesar Cipher

Metode Affine cipher adalah perluasan dari metode Caesar cipher, yang mengalikan plainteks dengan sebuah nilai P dan menambahkannya dengan sebuah pergeseran b menghasilkan cipherteks C dinyatakan dengan fungsi kongruen:

\[C\equiv mP+b(\bmod n) \]

Yang mana n adalah ukuran alphabet, m adalah bilangan bulat yang harus relatif prima dengan n (jika tidak relatif prima, maka dekripsi tidak bisa dilakukan) dan b adalah jumlah pergeseran (Caesar cipher adalah bentuk khusus dari Affine cipher dengan m=1). Untuk melakukan dekripsi, persamaan di atas harus dipecahkan untuk memperoleh P. Solusi kekongruenan tersebut hanya ada jika invers m (mod n), dinyatakan dengan \(m^{-1}\). Jika \(m^{-1}\) ada maka dekripsi dilakukan dengan persamaan sebagai berikut: (Munir, 2006)

\[P\equiv m^{-1}(C-b)(\bmod n)\]

• ENKRIPSI & DEKRIPSI

Berikut adalah contoh ENKRIPSI dan DEKRIPSI dengan menggunakan library Affine Cryptosystem yang sudah tersedia di Sagemath. Author Affine Cipher adalah Minh Van Nguyen (Agustus 2009)

• ENKRIPSI dengan menggunakan KUNCI INVERS

Mengenkripsi Ciphertext di atas dengan menggunakan invers key akan menghasilkan Plaintext juga. Jadi selain dengan Dekripsi ciphertext menggunakan key aslinya, Plaintext-nya dapat dihasilkan juga dengan Enkripsi ciphertext dengan invers key-nya.

• BRUTE FORCE

Contoh berikut ini menunjukkan Brute Force terhadap Enkripsi di atas untuk menghasilkan plaintext tanpa menggunakan kuncinya :

Catatan :

• Jika dilihat di atas, nilai a memiliki batasan. Nilai a yang diijinkan adalah 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 dan  25 (jika alfabet yang digunakan adalah 26 karakter -- mod 26) karena sesuai dengan Teorema Bezout menunjukkan bahwa invers a (a') hanya ada jika a dan 26 (panjang alfabet) adalah coprime. Biasa saja kita melakukan Enkripsi dengan nilai a yang tidak coprime dengan 26 akan tetapi pada saat Dekripsi kita akan mendapatkan hasil dekripsi yang salah.
• Nilai b memiliki batasan dari 1 s.d. 25 jika modulo yang digunakan adalah mod 26. Sebenarnya bisa juga menggunakan nilai negatif seperti -1 akan tetapi hasilnya sama saja karena pada mod 16, nilai -1 sama dengan 25 (25 = -1 mod 26).
• Pada contoh Brute Force di atas, dicoba sebanyak 312 kombinasi key (a,b). Nilai key a yang mungkin sebanyak 12 key dan b sebanyak 26 sehingga 12 x 26 = 312.

Pada video di bawah ini diberikan contoh cara mencari invers pada modulo 26.

Berikut adalah Affine Cipher versi Buku William Stalling:

Contoh Enkripsi dan Dekripsi Affine Cipher dengan fungsi-fungsi di atas sbb:

Hill or Matrix Cipher>>

Contoh-contoh Soal Kriptografi Bagian I

CONTOH SOAL UTS RMKI 2015

1. Sebutkan kelemahan One Time Pad?
2. a. Jelaskan prinsip kerja Timing Attack! b. Jelaskan apa yang dimaksud dengan "bit independence criterion"!
3. Hitunglah inversi perkalian dari \(x^{5}+x^{4}+x^{2}+1\) pada \(GF(2^{8})\) dimana \(m(x)=x^{8}+x^{4}+x^{3}+x+1\).
4. Jelaskan mengapa Sbox pada AES membutuhkan inversi sedangkan pada DES tidak!
5. Manakah yang memiliki performa terbaik dalam bidang 'random access' dari mode berikut (ECB, CBC, CFB, OFB, CTR). Jelaskan!

Jawaban :

1. Dijawab di sini.

2. Belum dijawab

3. Invers perkalian dari \(x^{5}+x^{4}+x^{2}+1\) pada \(GF(2^{8})\) dengan modulus \(m(x)=x^{8}+x^{4}+x^{3}+x+1\) dapat dihitung dengan menggunakan Extended Euclidian sebagai berikut : 

Iterasi 1 : \(x^{8}+x^{4}+x^{3}+x+1\) dibagi \(x^{5}+x^{4}+x^{2}+1\) hasilnya adalah \(x^{3}+x^{2}+x\) dengan sisa hasil pembagian \(x^{3}+x^{2}+1\) 

Iterasi 2 : \(x^{5}+x^{4}+x^{2}+1\) dibagi dengan \(x^{3}+x^{2}+x\) hasilnya adalah \(x^{2}\) dengan sisa hasil pembagian 1, karena sisa hasil pembagian sudah 1 maka iterasi berhenti.
Jadi Invers-nya = 1 - (\(x^{2}\))*(\(x^{3}+x^{2}+x\)) =  \(x^{5}+x^{4}+x^{3}+1\).

Untuk detail rumusnya bisa dilihat pada gambar di samping kanan.

Bandingkan jawaban dengan Sage sebagai berikut :

4. Belum dijawab
5. Belum dijawab