Anda pernah melihat kartu remi? Permainan kartu juga dapat disimulasikan dalam program komputer. Pernahkah anda berpikir bagaimanakah aturan yang adil untuk bermain kartu dalam program komputer? Terlebih lagi bermain kartu dengan orang yang belum pernah kita kenal dalam internet yang tidak mengenal jarak dan waktu?
Bayangkan apabila anda bermain kartu dengan teman anda yang anda kenal di facebook sehari yang lalu, kemudian mengajak bermain kartu “poker” di internet. Anda berada di Jakarta, teman anda berada di Surabaya sedangkan kartu yang digunakan adalah kartu digital yang anda kirim melalui email. Bagaimanakah caranya agar kartu yang dipilih tidak di”mainkan” terlebih dahulu oleh anda atau teman anda? Protokol mental poker memberikan salah satu solusinya.
Mental poker adalah nama umum untuk kumpulan masalah kriptografi yang berkonsentrasi pada pembagian informasi yang adil dan aman melalui jarak yang jauh tanpa diperlukan pihak ketiga yang terpercaya. Masalah mental poker hampir sama dengan melempar koin melalui jarak jauh.
1. Mengacak kartu menggunakan enkripsi komutatif
Salah satu cara yang paling mungkin dilakukan adalah dengan menggunakan skema enkripsi komutatif. Skema enkripsi komutatif maksudnya
Be(Ae(p)) == Ae(Be(p))
Ad(Be(Ae(p))) == Ad(Ae(Be(p)))
== Be(p)
Bd(Ae(Be(p))) == Bd(Be(Ae(p)))
== Ae(p)
dengan A dan B pihak yang mengenkripsi dan p adalah plain yang dienkripsi. Ae dan Be adalah kunci enkripsi A dan B. Sedangkan Ad dan Bd adalah kunci dekripsi A dan B.
Atau dengan kata lain, cipher teks yang dienkripsi A dapat dibuka oleh B setelah sebelumnya plain teks dienkripsi oleh B.
1.1 algoritma
1. A (Alice) dan B (Bob) menyetujui sekelompok informasi (disimbolkan dengan kartu).
2. Alice mengambil kunci enkripsi A dan menggunakannya untuk mengenkripsi setiap kartu pada dek [Ae(k1), Ae(k2)...Ae(kn)]
3. Alice mengacak
4. Alice memberikan kartu yang teracak dan terenkripsi pada Bob. Dengan enkripsi Alice, Bob tidak dapat mengetahui ciri-ciri setiap kartu.
5. Bob memilih kunci enkripsi B dan menggunakannya untuk mengenkripsi setiap kartu pada dek seperti yang dilakukan Alice [Be(Ae(k1)), Be(Ae(k2)),...Be(Ae(kn))]
6. Bob mengacak kartu yang dienkripsi tersebut
7. Bob mengembalikan kartu yang dienkripsi dua kali tersebut pada Alice.
8. Alice dekrip setiap kartu menggunakan kunci dekrip A. Kartu yang didekrip masih terenkripsi oleh kunci Bob [Be(k1), Be(k2),...Be(kn)]
9. Alice mengambil satu kunci enkripsi untuk setiap kartu (Ae1, Ae2, …, Aen) dan mengenkripnya masing-masing.
10. Alice mengembalikan dek pada Bob
11. Bob mendekripsi setiap kartu menggunakan kunci B. Kartu terdekripsi masih terenkripsi oleh kunci individual Ae1…Aen sehingga bob tidak akan tahu ciri-ciri kartu.
12. Bob mengambil satu kunci enkripsi untuk setiap kartu dan mengenkripsinya satu per satu.
13. Bob mengembalikan dek kembali pada Alice
14. Alice mengumumkan dek untuk setiap orang yang memainkan kartu.
Algoritma ini dapat diperluas untuk sejumlah pemain. Misalkan ada Carol, Dave dan yang lain cukup mengulang langkah 2-4 dan 8-10
Selama permainan, Alice dan Bob akan mengambil kartu dari deck, yang dicirikan berada pada dek. Ketika pemain ingin melihat kartunya, mereka akan meminta kunci yang berkaitan dengan pemain lainnya. Pemain tersebut, selama melihat kartu pemain benar-benar berkeinginan untuk melihat kartu, memberikan kunci individu kartu pada pemain lain. Pemeriksaan diperlukan untuk memastikan pemain tidak mencoba mendapatkan kunci beberapa kartu yang tidak dimiliki oleh pemain lain.
Contoh: Alice memilih kartu 1 hingga 5 pada dek. Bob mengambil kartu 6 hingga 10. Bob ingin melihat kartu yang dimilikinya. Alice setuju pada Bob untuk memeriksa kartu 6 hingga 10 dan memberikan kunci individu kartunya Ad6 hingga Ad10 untuk mendekripsi kartu. Bob mendekripsi kartunya dengan menggunakan kedua kunci Alice dan miliknya untuk kartu tersebut Bd6 hingga Bd10. Bob sekarang dapat melihat kartunya. Alice tidak dapat mengetahui kartu Bob karena dia tidak memiliki akses pada kunci Bob Bd6 hingga Bd10 yang diperlukan untuk mendekripsi kartu.
1.2 kelemahannya
Skema enkripsi ini harus aman terhadap known plaintext attack (serangan dengan diketahui plain teks): Bob harus tidak dapat menentukan kunci asli Ae Alice (untuk mendekripsi setiap kartu yang tidak dia ketahui) berdasarkan pengetahuannya terhadap bentuk kartu yang tidak terenkripsi yang dibuatnya. Hal ini menggagalkan beberapa skema enkripsi komutatif, dengan mudahnya seperti meng-XOR setiap kartu dengan kunci. (Menggunakan kunci yang terpisah untuk setiap kartu dimulai saat awal pertukaran kartu, menambah keamanan skema ini, tetapi tidak akan berguna jika kartu diacak sebelum kartu tersebut dikembalikan)
2. Protokol poker tanpa mengacak kartu terlebih dahulu
Pendekatan mental poker yang didasarkan pada protokol Alice-Bob diatas tidak memberikan performa yang cukup baik ketika digunakan pada permainan real-time online. Setiap pemain memerlukan waktu tertentu untuk mengenkrip setiap kartu. Sebuah paper menjelaskan sebuah protokol mental poker yang memberikan performa yang secara signifikan lebih tinggi dengan menggali aspek permainan poker tanpa model mengacak kartu. Daripada mengacak kartu dan mengambil yang diinginkan, dengan pendekatan paling baru, pemain membangkitkan (enkripsi) nomor random on the fly , yang digunakan untuk memilih kartu selanjutnya. Setiap kartu baru perlu diperiksa terhadap setiap kartu yang telah dipilih untuk mendeteksi duplikasi. Sebagai hasilnya, metode ini berguna pada permainan poker, dengan setiap nomor kartu yang dipilih jumlahnya sangat kecil dibandingkan dengan jumlah kartu keseluruhan di dek. Bagaimanapun juga, metode tersebut memerlukan kartu yang telah disetujui dan diketahui oleh semua pemain pada umumnya permainan poker.
Skema ini membutuhkan cryptosystem dengan dua kunci. Enkripsi E harus additive homomorphic, sehingga E(c1)E(c2) = E(c1+c2). Kedua, collition harus dapat dideteksi, tanpa mengetahui plaintextnya. Dengan kata lain, E(c1) dan E(c2), harus memenuhi c1 = c2, tanpa pemain dapat mempelajari informasi lain (khususnya mengidentifikasi c1 dan c2). Enkripsi Elgamal merupakan salah satu contoh sistem yang diketahui memiliki sifat tersebut. Algoritmanya berlangsung seperti berikut:
1. Pemain menginisialisasi sebuah daftar kosong L yang merekam kartu yang digunakan
2. Untuk menyetujui kartu, setiap pemain menghitung sebuah nomor random ri pada {0,…51}, menghitung E(ri), dan mengumumkan komitmen non-malleable pada E(ri)
3. Pemain kemudian mengumumkan E(ri) asli masing-masing dan dapat memverifikasi bahwa setiap pemain mentaati komitmennya
4. Pemain menghitung PHI E(ri) = E(sigma ri), yang menghasilkan kartu baru yang terenkripsi E(r*), dengan r* = sigma ri
5. Pemain memeriksa apakah E(r*) berada pada L. Jika tidak, E(r*) disetujui pada pemain yang sesuai, dan ditambahkan pada L. Ketika kartu perlu dibuka, semuanya dapat didekripsi.
Dengan cara ini, pemain hanya membutuhkan untuk menghitung enkripsi pada kartu-kartu yang digunakan pada permainan, ditambah beberapa tambahan untuk collision yang kecil selama jumlah kartu yang diperlukan jauh lebih sedikit daripada ukuran dek. Sebagai hasilnya, skema ini lebih cepat 2 hingga 4 kali (sebagaimana yang diukur dengan jumlah total modular exponentiation) daripada protokol terbaik yang dikenal yang melakukan pengacakan menggunakan mix-network.
Catat bahwa pembangkitan nomor random aman selama setiap pemain membangkitkan nomor random yang valid. Bahkan jika pemain k-1 sama-sama membangkitkan nomor r*, selama pemain ke-k benar-benar membangkitkan random r’, penjumlahan r = r* + r’ masih random pada {0,51}.
3. Meningkatkan performa protokol poker melalui pihak yang dipercaya
[tobecontinued]
