Kriptografi : Protokol Secret Sharing

Protokol kriptografi lainnya adalah protokol secret sharing, yang memungkinkan pendistribusian satu rahasia di antara sekumpulan orang yang saling percaya yang selanjutnya disebut share holder (share receiver). Protokol secret sharing ini menerapkan (m,n)-threshold scheme, yaitu informasi tentang rahasia adalah didistribusikan sedemikian rupa sehingga sembarang m dari n orang (m ≤ n) memiliki informasi yang cukup untuk menentukan (mengetahui) rahasia tersebut, tetapi sembarang set m-1 orang tidak dapat melakukannya. Dalam sembarang secret sharing scheme, terdapat kumpulan orang yang terpilih yang informasi kumulatif mereka cukup untuk memecahkan rahasia.

Dalam beberapa implementasi secret sharing scheme, setiap partisipan menerima rahasia setelah rahasia yang dimaksud dihasilkan. Dalam implementasi lain, rahasia sebenarnya tidak pernah dibuat kelihatan kepada partisipan, walaupun akses diberikan untuk mendapatkan rahasia tersebut diberikan (misalnya dalam akses ke dalam ruangan atau izin untuk melakukan proses). Beberapa algoritma dari secret sharing scheme adalah LaGrange Interpolating Polynomial Scheme, Asmuth- Bloom Scheme, dan sebagainya.

Algoritma LaGrange Interpolating Polynomial ini menggunakan persamaan polinomial dalam memecahkan pesan yang ingin dirahasiakan tersebut. Sedangkan, untuk menyusun kembali pesan diperlukan bantuan metode pencarian solusi sistem persamaan linier.

Sedangkan, algoritma Asmuth-Bloom menggunakan sistem kongruen linier, aritmatika modulo, bilangan prima dan bilangan acak untuk meningkatkan keamanannya. Selain itu, algoritma ini juga memerlukan bantuan teorema Chinese Remainder pada saat penggabungan pesan kembali.

Kriptografi : Protokol Multiple-Key Public-Key Cryptography

Protokol ini dapat digunakan dalam proses enkripsi-dekripsi dan proses signature yang melibatkan dua orang signer. Berbeda dengan algoritma kriptografi pada umumnya yang hanya dapat diterapkan untuk komunikasi antara dua orang, protokol ini menggunakan algoritma kriptografi yang dapat diterapkan untuk lebih dari dua orang.

Kriptografi : Metode Kriptografi (MMB, LUC)

Berdasarkan pemakaian kunci maka sistem kriptografi (cryptosystems) dapat digolongkan atas 2 jenis sistem yakni sistem kriptografi kunci publik (public key cryptography) dan sistem kriptografi kunci rahasia (secret key cryptography).

Dalam sistem kriptografi kunci rahasia yang dikenal juga dengan symmetric cryptosystems, pihak pengirim dan penerima bersama-sama menyepakati sebuah kunci rahasia yang akan digunakan dalam proses enkripsi dan dekripsi tanpa diketahui oleh pihak lain.

Sedangkan dalam sistem kriptografi kunci publik atau dikenal dengan assymmetric cryptosystem, pihak pengirim maupun pihak penerima mendapatkan sepasang kunci yakni kunci publik (public key) dan kunci rahasia (private key) dimana kunci publik dipublikasikan dan kunci rahasia tetap dirahasiakan. Enkripsi dilakukan dengan menggunakan kunci publik sedangkan dekripsi dilakukan dengan menggunakan kunci rahasia.

Berikut diberikan penjelasan singkat mengenai algoritma simetris (contoh : MMB) dan algoritma asimetris (contoh : LUC).

Metode MMB

Kriptografi metode MMB menggunakan plaintext 128 bit dan algoritma iteratif yang terdiri dari langkah-langkah linier (seperti XOR dan aplikasi kunci) serta aplikasi paralel dari empat substitusi non linier besar yang dapat dibalik. Substitusi ini ditentukan oleh sebuah operasi perkalian modulo 2³² – 1 dengan faktor konstan, yang memiliki tingkat sekuritas lebih tinggi bila dibandingkan dengan metode IDEA yang hanya menggunakan operasi perkalian modulo 2¹⁶ + 1. MMB menggunakan 32 bit subblock text (x₀, x₁, x₂, x₃) dan 32 bit subblock kunci (k₀, k₁, k₂, k₃). Hal ini membuat algoritma tersebut sangat cocok diimplementasikan pada prosesor 32 bit. Sebuah fungsi non linier, f, diterapkan enam kali bersama dengan fungsi XOR.

Metode LUC

Metode LUC merupakan algoritma kriptografi kunci publik yang dikembangkan oleh Peter J. Smith dari New Zealand pada tahun 1993. Metode LUC ini dirancang oleh Peter J. Smith setelah ia berhasil meneliti dan melihat kelemahan dari metode RSA. Metode LUC ini menggunakan fungsi Lucas yang dapat menutupi kelemahan metode RSA yang menggunakan fungsi pangkat. Kemungkinan untuk menjebol RSA menjadi ada karena masalah pangkat tersebut. Fungsi Lucas ini dapat mencegah kemungkinan tersebut.

Metode LUC sendiri hampir sama dengan metode RSA hanya saja fungsi pangkat pada metode RSA diganti dengan fungsi Lucas pada metode LUC. Metode LUC ini menggunakan dua buah bilangan prima besar, p dan q untuk menghasilkan pasangan kunci publik, e dan n, dimana n = p * q, serta kunci privat, d. Sedangkan nilai p dan q sendiri tidak digunakan dalam algoritma ini. Algoritma ini juga menggunakan Extended Euclidean algorithm untuk menghasilkan nilai kunci dekripsi d dari kunci enkripsi e. Nilai kunci enkripsi e merupakan sebuah bilangan acak yang dibangkitkan sedemikian rupa sehingga harus relatif prima terhadap p – 1, q – 1, p + 1 dan q + 1. Sedangkan panjang plaintext harus lebih kecil daripada n.

Metode Hungarian

Harold W. Kuhn dalam karya ilmiahnya yang berjudul “The Hungarian Method for the assignment problem” mendeskripsikan sebuah algoritma untuk mengkonstruksikan sebuah graf berbobot maksimum. Dalam karya ilmiahnya tersebut, Kuhn menjelaskan bagaimana cara kerja algoritma yang ditemukan oleh dua orang ahli matematika berkebangsaan Hungaria yang bernama D. Konig dan E. Egervary pada tahun 1931 tersebut, telah berkontribusi terhadap algoritma yang ditemukannya tersebut. Hal ini juga yang dijadikan alasan baginya mengapa algoritma yang ditemukannya tersebut diberi nama metode Hungaria.

Sistem Persamaan Linier (SPL)

Sistem persamaan linier merupakan suatu sistem persamaan dimana pangkat semua besaran di dalamnya sama dengan satu dan semua koefisien dalam sistem persamaan adalah konstan. Beberapa metode penyelesaian praktis sistem persamaan linier adalah Metode Eliminasi Gauss dan variasinya, Metode Cramer, Metode LU Gauss, Metode Reduksi Crout, Metode Dekomposisi Cholesky.

Matriks

Matriks merupakan istilah dalam matematika untuk menyatakan sebuah susunan segi empat siku-siku dari bilangan-bilangan. Bilangan-bilangan dalam susunan tersebut dinamakan entri dalam matriks.

Huruf-huruf besar A, B, … menunjukkan suatu matriks, sedang huruf-huruf kecil a, b, … menunjukkan suatu bilangan, dan disebut scalar. Dua matriks A dan B dikatakan sama, ditulis A = B, jika keduanya mempunyai ukuran sama, yaitu banyaknya baris dan kolom sama, dan memenuhi unsur-unsur yang letaknya sama. Oleh karena itu kesamaan dua matriks m x n ekivalen dengan sistem persamaan yang terdiri atas mn buah persamaan, dengan masing-masing unsur yang letaknya sama memberikan suatu persamaan.

Banyak algoritma yang digunakan untuk melakukan operasi perkalian matriks, beberapa diantaranya yaitu algoritma Naïve, Winograd dan Strassen.

Chinese Remainder Theorem (CRT)

Pada abad pertama, seorang matematikawan Tiongkok yang bernama Sun Tzu mengajukan pertanyaan sebagai berikut:

“Tentukan sebuah bilangan bulat yang bila dibagi dengan 5 menyisakan 3, bila dibagi 7 menyisakan 5, dan bila dibagi 11 menyisakan 7”.

Teorema Chinese Remainder berikut akan digunakan untuk menemukan solusi sistem kongruen linier seperti di atas:

Misalkan m₁, m₂, …, m_n adalah bilangan bulat positif sedemikian sehingga GCD(m_i, m_j) = 1 untuk i ¹ j. Maka sistem kongruen linier:

x = a_k (mod m_k)

mempunyai sebuah solusi unik dalam modulo m = m₁ . m₂ . … . m_n.

Graph

Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Sebagai contoh, peta jaringan jalan kereta api yang menghubungkan sejumlah kota di pulau Jawa. Sesungguhnya peta tersebut adalah sebuah graph, yang dalam ini kota dinyatakan sebagai bulatan sedangkan jalan dinyatakan sebagai garis. Dengan diberikannya peta tersebut, maka dapat diketahui apakah ada lintasan jalan antara dua buah kota. Selain itu, bila panjang jalan kereta api antara dua buah kota bertetangga diketahui, maka juga dapat ditentukan rute perjalanan tersingkat dari kota A ke kota B.

Dalam pemrograman komputer, graph dapat direpresentasikan dengan menggunakan beberapa macam representasi graph, antara lain adjacency matrix, incidency matrix dan adjacency list. Namun, saya merekomendasikan untuk menggunakan adjacency list karena lebih efisien dan efektif dalam pengkodean dan lebih menghemat memori.

Pewarnaan Graph

Ada tiga macam persoalan pewarnaan graph (graph colouring), yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan wilayah (region). Pembahasan kali ini hanya dibatasi pada pewarnaan simpul saja.

Pewarnaan simpul adalah memberi warna pada simpul-simpul di dalam graph sedemikian sehingga setiap dua simpul bertetanga mempunyai warna yang berbeda. Salah satu terapan penting pewarnaan graph adalah mewarnai peta (colouring of map). Di dalam persoalan pewarnaan graph, tidak hanya sekedar mewarnai simpul-simpul dengan warna berbeda dari warna simpul tetangganya saja, namun juga menginginkan jumlah macam warna yang digunakan sesedikit mungkin.

Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik graph G.

Algoritma Welch Powell

Algoritma Welch-Powell dapat digunakan untuk mewarnai sebuah graf G secara efisien. Algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai G, namun algoritma ini cukup praktis untuk digunakan dalam pewarnaan simpul graph. Algoritma Welch-Powell dapat dinyatakan sebagai berikut:

1. Urutkan simpul-simpul dari G dalam derajat yang menurun.

2. Gunakan satu warna untuk mewarnai simpul pertama (yang mempunyai derajat tertinggi) dan simpul-simpul lain (dalam urutan yang berurut) yang tidak tertetangga dengan simpul pertama ini.

3. Mulai lagi dengan simpul derajat tertinggi berikutnya di dalam daftar terurut yang belum diwarnai dan ulangi proses pewarnaan simpul dengan menggunakan warna kedua.

4. Ulangi penambahan warna-warna sampai semua simpul telah diwarnai.

Algoritma Recursive Largest First

Langkah kerja dari algoritma Recursive Largest First secara singkat :
1. Buat daftar semua simpul yang belum diwarnai dengan derajat tetangga (jumlah node tetangga yang belum diwarnai) terurut secara descending.
2. Ambil simpul yang memiliki derajat tetangga tertinggi dan warnai dengan sebuah warna.
3. Buang simpul yang telah diwarnai pada langkah (2) dan semua simpul yang bertetangga dengan simpul tersebut dari daftar simpul.
4. Warnai semua simpul yang tersisa pada daftar simpul dengan warna yang sama dengan warna simpul tadi.
5. Ulangi langkah-langkah diatas hingga semua node pada graph terwarnai.

Tree

Pohon (tree) adalah graph yang khusus. Pohon dapat didefinisikan sebagai graph-tak-berarah terhubung yang tidak mengandung sirkuit. Menurut definisi ini, ada dua sifat penting pada pohon, yaitu terhubung dan tidak mengandung sirkuit.

Dalam kehidupan sehari-hari, orang telah lama menggunakan pohon untuk menggambarkan hirarkhi. Misalnya, pohon silsilah keluarga, struktur organisasi, organisasi pertandingan, dan lain-lain. Para ahli bahasa menggunakan pohon untuk menguraikan kalimat, yang disebut pohon parsing (parse tree).

Spanning Tree

Misalkan G = (V, E) adalah graph-tak-berarah terhubung yang bukan pohon, yang berarti di G terdapat beberapa sirkuit. G dapat diubah menjadi pohon T = (V₁, E₁) dengan cara memutuskan sirkuit-sirkuit yang ada. Caranya, mula-mula dipilih sebuah sirkuit, lalu hapus satu buah sisi dari sirkuit ini. G akan tetap terhubung dan jumlah sirkuitnya berkurang satu. Bila proses ini dilakukan berulang-ulang sampai semua sirkuit di G hilang, maka G menjadi sebuah pohon T, yang dinamakan pohon merentang (spanning tree).

Contoh aplikasi pohon merentang misalnya pada pemeliharaan jalan raya.

Minimum Spanning Tree

Jika G adalah graph berbobot, maka bobot pohon merentang T dari G didefinisikan sebagai jumlah bobot semua sisi di T. Pohon merentang yang berbeda mempunyai bobot yang berbeda pula. Di antara semua pohon merentang di G, pohon merentang yang berbobot minimum dinamakan pohon merentang minimum (minimum spanning tree). Pohon merentang minimum merupakan pohon merentang yang paling penting. Pohon merentang minimum mempunyai terapan yang luas dalam praktek.

Misalkan pemerintah akan membangun jalur rel kereta api yang menghubungkan sejumlah kota. Membangun jalur rel kereta api biayanya mahal, karena itu pembangunan jalur ini tidak perlu menghubungkan langsung dua buah kota, tetapi cukup membangun jalur kereta seperti pohon merentang. Karena di dalam sebuah graph mungkin saja terdapat lebih dari satu pohon merentang, harus dicari pohon merentang yang mempunyai jumlah jarak terpendek, dengan kata lain harus dicari pohon merentang minimum.

Algoritma yang dapat digunakan untuk membangun pohon merentang minimum ada dua buah, yaitu algoritma Prim dan algoritma Kruskal.

Algoritma Prim

Langkah kerja dari algoritma Prim dapat dinyatakan sebagai berikut: (G = graph input, T = graph hasil)

a. Ambil sisi dari graph G yang berbobot minimum, masukkan ke dalam T.

b. Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e tidak membentuk sirkuit di T. Masukkan e ke dalam T.

c. Ulangi langkah (b) sebanyak n – 2 kali.

Algoritma Kruskal

Pada algoritma Kruskal, sisi-sisi di dalam graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Setelah itu, baru dilakukan langkah kerja berikut ini:

a. T masih kosong.

b. Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T. Masukkan e ke dalam T.

c. Ulangi langkah (b) sebanyak n – 1 kali.

N.B. : Suatu graph dapat memiliki lebih dari satu buah minimum spanning tree.

Referensi Skripsi Teknik Informatika GRATIS !!!

Hello, teman mahasiswa sekalian, perkenalkan nama saya Paitan. Saya berprofesi sebagai programmer di salah satu software house di Surabaya dan juga berprofesi sebagai staf pengajar di salah satu kursus komputer.

Akhir-akhir ini, saya sering mendapat banyak keluhan dari teman-teman satu kampus terutama adik-adik kelas saya pada jurusan Teknik Informatika bahwa pembuatan tugas akhir (skripsi) mereka sering terbengkalai gara-gara tidak tahu ingin mengambil judul apa dan banyak yang terhambat di tengah jalan karena tidak dapat melanjutkan pembuatan program tugas akhir-nya.

Oleh karena itu, saya bermaksud untuk membantu teman-teman mahasiswa sekalian terutama mahasiswa pada jurusan Teknik Informatika dengan cara memberikan contoh-contoh program tugas akhir yang dapat dijadikan sebagai referensi dalam pembuatan tugas akhir pada jurusan Teknik Informatika.

Referensi-referensi yang diberikan berupa contoh program executable (berekstensi *.exe) dan contoh proposal. Semuanya ini akan diberikan secara GRATIS !!!

Untuk informasi lebih lanjut silahkan email saya di Paitan.28@gmail.com