Konser: Pemalsu tiket | Teknologi –

Posted on

– Charles, Charles! Tunggu sebentar! – Paula berteriak dari jendela di lantai pertama institut – Pemberitahuan: kita akan pergi ke konser SUPERSTAR.

Carlos memandang Paula dengan skeptis.

Paula, maaf, konser telah dibatalkan. Beberapa tiket duplikat, atau melebihi kapasitas… Saya tidak tahu.

“Tepat!” seru Paula. Diundur sampai minggu depan. Dan di kelas teknologi, mereka memulai sebuah kontes. Anda harus menjawab tiga pertanyaan dan harganya adalah dua tiket!

Carlos menyukai SUPERSTAR, jadi dia duduk dengan sabar sementara Paula dengan bersemangat melepaskan semburan informasi.

Konser dihentikan karena mereka memiliki beberapa masalah dengan validasi tiket. Anda lihat, setiap input memiliki nomor, dan untuk memvalidasinya lebih cepat, nomor itu diringkas dengan transformasi yang disebut fungsi hash atau fungsi ringkasan. Di gerbang stadion mereka memiliki pembaca yang membandingkan ringkasan setiap entri dengan daftar ringkasan yang valid, untuk mengesahkan atau tidak bagian tersebut.

“Aku mulai malas…” Carlos memprotes. “Apa fungsi ringkasan ini?”

Paula melanjutkan tanpa henti. Fungsi hash adalah fungsi matematika yang mengambil nilai, seperti string angka dengan panjang berapa pun, seperti jumlah input, dan mengembalikan hash, yaitu urutan angka yang pendek. Proses ini tidak dapat diubah, yaitu jika mereka memberi Anda ringkasan, Anda tidak dapat kembali dan mendapatkan urutan aslinya kembali. Di sisi lain, dengan input yang sama, fungsi selalu mengembalikan output yang sama. Paula melukis dua lingkaran dengan titik dan panah di tanah korsel, mewakili apa yang dia jelaskan.

Ringkasan ini digunakan untuk banyak hal. Misalnya, untuk mendeteksi dan memperbaiki kesalahan saat menyalin angka besar; justru inilah peran surat DNI kita yang merupakan rangkuman dari angka-angka yang mendahuluinya. Mereka juga digunakan untuk mendeteksi jika seseorang menambahkan virus ke program yang Anda unduh dari Internet: Anda dapat memeriksa apakah ringkasan kode yang Anda unduh sesuai dengan yang dipublikasikan di situs orang yang menawarkan program tersebut kepada Anda. Jika tidak, seseorang memodifikasi file saat bepergian di jaringan.

“Dan itu tidak bagus…” Carlos menyela.

-Tidak. Sinyal buruk. Di lain waktu abstrak digunakan untuk, misalnya, mempercepat proses, bayangkan bahwa alih-alih memanggil kami di institut menggunakan nomor pendaftaran lengkap kami, mereka hanya menggunakan dua digit terakhir.

“Yah, betapa kacaunya mereka,” lompat Carlos, “karena aku yakin banyak dari kita memiliki nomor yang sama.”

“Itu benar!” Paula berkata: “Jika fungsi ringkasan buruk, ada kebetulan, yang disebut tabrakan, dan mereka tidak boleh digunakan … itulah yang terjadi pada mereka di konser!” Saya akan menjelaskannya kepada Anda, itu cukup sederhana. Setiap entri memiliki nomor ID, intisari yang ditentukan menggunakan fungsi CUTREHASH, yang membagi bilangan asli dengan 1024 dan mengambil sisa pembagian tersebut sebagai intisari.

“Dan mengapa hanya 1.024?”

“Hmmm. Tidak relevan untuk memecahkan masalah, tetapi akan menarik bagi mereka yang mengingat barisan biner. Karena validasi input harus cepat, kedua angka direpresentasikan dalam biner (dengan satu dan nol), sehingga mudah dibaca dengan pembaca optik. Karena 1024 adalah 2 dinaikkan menjadi 10, kami memastikan bahwa nomor ringkasan dapat diwakili dengan paling banyak 10 digit (10 bit).

“Saya tidak melihat masalahnya,” kata Carlos, “mereka telah memikirkan segalanya dengan sangat baik.”

Yah… tidak cukup… —Paula tersenyum— untuk memulai, kapasitas stadion adalah 10.900 orang, jadi ID awal yang benar harus berupa angka antara 1 dan 10.900. memiliki ringkasan yang jauh lebih sedikit daripada jumlah entri, jadi tidak bisa menjadi ringkasan yang berbeda untuk setiap ID! Apakah Anda ingat prinsip Pigeonhole yang kita lihat di kelas? Jika Anda memiliki lebih banyak merpati daripada loteng, beberapa harus berbagi tempat tidur…dan itulah yang terjadi pada mereka. Pada satu titik, orang-orang mulai berdatangan dengan tiket dan rekap yang valid yang sudah divalidasi oleh pembaca pintu, sehingga menolak akses mereka.

“Ya Tuhan, sungguh bencana,” Carlos tampak khawatir, “dan apakah mereka butuh waktu lama untuk mengetahuinya?”

“Tidak juga, Carlos, pikirkanlah… Ini adalah pertanyaan pertama dari kuis.. Berapa banyak orang paling banyak dan setidaknya telah memasuki stadion ketika orang pertama dengan ringkasan berulang tiba?

– Ayo, aku sedang memikirkannya. Tapi, jika tidak butuh waktu lama bagi mereka untuk menyadarinya, mereka bisa saja menggelar konser sedikit lebih lama, bukan?

“Mereka mencoba melakukannya. Memverifikasi bahwa hanya menggunakan ringkasan adalah metode yang buruk, mereka memutuskan untuk memvalidasi input dengan cara lain, memeriksa dua hal: bahwa pengidentifikasi belum pernah digunakan sebelumnya, dan ringkasannya dihitung dengan benar (menggunakan hash untuk memperbaiki kesalahan pencetakan). Tapi itu tidak berhasil juga. Beberapa scammer, yang mengetahui sistem validasi yang salah, telah merusak ribuan entri dengan abstrak yang sesuai, dari yang memiliki ID 10.901, hingga yang bernomor 99.999. Dan mereka baru menyadarinya ketika peserta jelas-jelas melebihi kapasitas!

Dan sekarang sampai pada pertanyaan tantangan lainnya. Kedua Sederhana saja: Bisakah Anda menemukan nomor entri yang valid yang ringkasannya memberikan nilai yang sama dengan entri dengan id 4410? Ya ketiga, lebih rumit: Berapa banyak tiket yang valid dan berapa banyak totalnya, dihitung yang palsu, apakah mereka memiliki 4.410 itu dalam ringkasan? Anda harus bergegas, harganya dua tiket bagus!

“Baiklah, ayo pergi! Sekarang Carlos yakin. “Kita akan pergi ke konser tetap SUPER STAR!”

Tantangan Crypto akan dirilis setiap 15 hari. Pembaca dapat meninggalkan solusi mereka dan mendiskusikan masalah ini di komentar di halaman ini. Jadi siapa pun yang ingin menyelesaikannya sendiri disarankan untuk tidak membacanya sampai mereka memecahkan teka-teki itu. Anda juga dapat mengirimkan jawaban Anda melalui email [email protected]. Di setiap tantangan baru, kami akan menerbitkan solusi dari tantangan sebelumnya, disertai dengan komentar dengan beberapa ide orisinal atau inspiratif yang telah kami terima.

Ana Isabel Gonzalez Tablas Ferreres@aigtf, adalah seorang doktor dalam ilmu komputer dan seorang profesor dan peneliti dari grup COSEC di Carlos III University of Madrid.

SOLUSI TANTANGAN SEBELUMNYA

dalam tantangan Cara mengelabui pemeriksa sudoku, hal utama dalam tantangan ini adalah untuk mengamati ini: jika tiga ubin yang sama ditumpuk di setiap sel, selama sudoku tidak diselesaikan dengan baik, pemeriksa akan selalu mendeteksi masalah. Oleh karena itu, satu-satunya kemungkinan untuk menipu pemeriksa adalah menumpuk ubin dengan nomor yang berbeda.

Sudoku yang diusulkan selesai sebagai berikut:

Oleh karena itu, jika kita tahu bahwa pemeriksa memeriksa terlebih dahulu berdasarkan baris, kemudian berdasarkan kolom, dan terakhir dengan kotak, salah satu dari banyak cara untuk mengelabuinya adalah:

Di mana kita berasumsi bahwa token ditumpuk dan di sebelah kiri muncul nomor token pertama (bawah), di tengahnya yang kedua dan di sebelah kanan itu dari lapisan atas. Kami telah menempatkan tiga ubin identik di ruang tetap, karena menghadap ke atas, sedangkan dengan ubin menghadap ke bawah, kami membatasi diri untuk menempatkan, secara korelatif, ubin terendah yang tersedia, pertama dalam baris, kemudian dengan kolom dan akhirnya dengan kotak (dari kiri ke kanan dan dari atas ke bawah). Beberapa pembaca (seperti Javier dan Héctor) telah menunjukkan kepada kami bahwa karena ada tiga pemeriksaan (baris, kolom, dan kotak) yang akan dilakukan secara berurutan dan karena itu sepele untuk menyelesaikan sudoku sehingga tidak ada pengulangan di masing-masing mereka, probabilitas memberikan solusi yang verifikator anggap valid ketika kami hanya memiliki proposal yang lulus tes (yang memiliki baris, yang memiliki kolom, dan yang memiliki kotak) bertepatan dengan probabilitas untuk mendapatkan urutan verifikasi. akan dilakukan dengan baik. Probabilitas ini adalah 1/6 (satu dibagi dengan jumlah permutasi dari tiga elemen).

Alat kriptografi di balik tantangan ini adalah apa yang disebut Zero Knowledge Proofs, yang dikenal dengan akronim ZKP (Zero Knowledge Proof), yang diperkenalkan pada tahun 1985 oleh Shafi Goldwasser, Silvio Micali dan Charles Rackoff (lihat Kompleksitas pengetahuan sistem bukti interaktif). Secara informal, Pembuktian Tanpa Pengetahuan adalah prosedur di mana “pembukti” meyakinkan “pemverifikasi” suatu fakta tanpa mengungkapkan lebih banyak informasi daripada kebenaran fakta tersebut. Jenis protokol ini sangat berguna dalam kriptografi, karena, misalnya, memungkinkan untuk menunjukkan kepemilikan kunci rahasia (sehingga mengidentifikasi pengguna sistem) tanpa membocorkan informasi tentang mereka. Saat ini, penelitian ZKP sedang booming karena perluasan cryptocurrency. Dalam konteks ini, ZKP sangat penting untuk memvalidasi transaksi guna mencegah penipuan tanpa mengungkapkan pergerakan akun, sehingga melindungi privasi pengguna sistem.

Contoh Sudoku kami terinspirasi oleh Gradwohl, Naor, Pikas dan Rothblum (2007), di mana, selain mengusulkan dan meninjau ZKP lain untuk menyelesaikan Sudokus, penulis menganalisis secara rinci varian metode yang diusulkan di mana pemeriksa secara acak memilih kartu dari setiap kotak setiap kali sel ini muncul dalam pemeriksaan berdasarkan baris, kolom, atau kotak . Dengan protokol verifikasi ini, yang muncul dalam solusi yang diusulkan oleh seorang pembaca (David), kita dapat menunjukkan bahwa kemungkinan menipu sebuah pemeriksa dengan solusi yang buruk, tidak boleh lebih besar dari 1/9.

kamu bisa mengikuti TEKNOLOGI NEGARA di Facebook Ya Twitter atau daftar di sini untuk menerima kami buletin mingguan.

– Artikel ditulis oleh @Ana Isabel González Tablas Ferreres dari https://elpais.com/tecnologia/2022-08-05/los-falsificadores-de-entradas.html

Leave a Reply

Your email address will not be published.