Kontes ini sudah berakhir.
Karena sifat tantangan polisi dan perampok , tantangan polisi menjadi jauh lebih mudah ketika minat terhadap tantangan perampok terkait berkurang. Karena itu, selagi Anda masih dapat memposting fungsi hash, jawaban Anda tidak akan diterima atau menjadi bagian dari papan peringkat.
Tantangan ini adalah pencarian implementasi terpendek dari fungsi hash yang tahan benturan , yaitu, tidak mungkin menemukan dua pesan berbeda dengan hash yang sama.
Sebagai seorang polisi, Anda mencoba untuk menciptakan dan mengimplementasikan fungsi hash menemukan kompromi terbaik antara ukuran kode dan resistensi tabrakan. Gunakan terlalu banyak byte dan polisi lain akan mengalahkan Anda!
Sebagai seorang perampok, Anda mencoba menggagalkan upaya polisi dengan merusak fungsinya, membuktikan bahwa itu tidak sesuai. Ini akan memaksa mereka menggunakan lebih banyak byte untuk memperkuat algoritme mereka!
Tantangan polisi
Tugas
Menerapkan fungsi hash kriptografis H: I -> O pilihan Anda, di mana saya adalah himpunan semua bilangan bulat non-negatif di bawah 2 2 30 dan O adalah himpunan semua bilangan bulat non-negatif di bawah 2 128 .
Anda dapat mengimplementasikan H sebagai fungsi aktual yang menerima dan mengembalikan integer tunggal, representasi string integer atau array integer atau program lengkap yang membaca dari STDIN dan mencetak ke STDOUT di basis 10 atau 16.
Mencetak gol
H bahwa ia harus menolak tantangan perampok yang didefinisikan di bawah ini.
Jika seorang perampok mengalahkan kiriman Anda dalam 168 jam pertama setelah mempostingnya, itu dianggap retak .
Implementasi H harus sesingkat mungkin. Pengajuan terputus terpendek akan menjadi pemenang dari tantangan polisi.
Aturan tambahan
Jika Anda menerapkan H sebagai fungsi, berikan pembungkus untuk menjalankan fungsi dari dalam program yang berperilaku seperti dijelaskan di atas.
Harap berikan setidaknya tiga vektor uji untuk program atau pembungkus Anda (misalnya input dan output yang sesuai).
H dapat berupa desain novel Anda (lebih disukai) atau algoritma yang terkenal, selama Anda menerapkannya sendiri. Dilarang menggunakan fungsi hash bawaan apa pun, fungsi kompresi, sandi, PRNG, dll.
Setiap built-in yang biasa digunakan untuk mengimplementasikan fungsi hashing (misalnya, konversi basis) adalah permainan yang wajar.
Output dari program atau fungsi Anda harus bersifat deterministik.
Seharusnya ada kompiler / juru bahasa gratis (seperti dalam bir) yang dapat dijalankan pada platform x86 atau x64 atau dari dalam browser web.
Program atau fungsi Anda harus cukup efisien dan harus mem-hash pesan apa pun di I di bawah 2 2 19 dalam waktu kurang dari satu detik.
Untuk kasus tepi, waktu (dinding) yang diambil pada komputer saya (Intel Core i7-3770, 16 GiB RAM) akan menentukan.
Mengingat sifat tantangan ini, dilarang mengubah kode jawaban Anda dengan cara apa pun, apakah itu mengubah hasilnya atau tidak.
Jika kiriman Anda telah dipecahkan (atau bahkan jika belum), Anda dapat memposting jawaban tambahan.
Jika jawaban Anda tidak valid (mis. Tidak sesuai dengan spesifikasi I / O), harap hapus.
Contoh
Python 2.7, 22 byte
def H(M): return M%17
Pembungkus
print H(int(input()))
Perampok menantang
Tugas
Crack salah satu polisi kiriman dengan posting berikut di perampok benang : dua pesan M dan N di saya sehingga H (M) = H (N) dan M ≠ N .
Mencetak gol
Memecahkan setiap pengiriman polisi memberi Anda satu poin. Perampok dengan poin terbanyak menang.
Dalam kasus dasi, perampok terikat yang memecahkan pengajuan menang paling lama.
Aturan tambahan
Setiap pengajuan polisi hanya dapat dibobol sekali.
Jika pengiriman polisi bergantung pada perilaku yang ditentukan atau tidak ditentukan implementasi, Anda hanya perlu menemukan celah yang berfungsi (dapat diverifikasi) pada mesin Anda.
Setiap celah milik jawaban terpisah di utas perampok.
Memposting upaya cracking yang tidak valid membuat Anda tidak bisa memecahkan submission tertentu selama 30 menit.
Anda tidak boleh merusak kiriman Anda sendiri.
Contoh
Python 2.7, 22 bytes oleh user8675309
1
dan
18
Papan peringkat
Pengajuan yang aman
Kiriman tidak terputus
Anda dapat menggunakan Cuplikan Stack ini untuk mendapatkan daftar jawaban yang belum retak.
function g(p){$.getJSON('//api.stackexchange.com/2.2/questions/51068/answers?page='+p+'&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!.Fjs-H6J36w0DtV5A_ZMzR7bRqt1e',function(s){s.items.map(function(a){var h=$('<div/>').html(a.body).children().first().text();if(!/cracked/i.test(h)&&(typeof a.comments=='undefined'||a.comments.filter(function(b){var c=$('<div/>').html(b.body);return /^cracked/i.test(c.text())||c.find('a').filter(function(){return /cracked/i.test($(this).text())}).length>0}).length==0)){var m=/^\s*((?:[^,(\s]|\s+[^-,(\s])+)\s*(?:[,(]|\s-).*?([0-9]+)/.exec(h);$('<tr/>').append($('<td/>').append($('<a/>').text(m?m[1]:h).attr('href',a.link)),$('<td class="score"/>').text(m?m[2]:'?'),$('<td/>').append($('<a/>').text(a.owner.display_name).attr('href',a.owner.link))).appendTo('#listcontent');}});if(s.length==100)g(p+1);});}g(1);
table th, table td {padding: 5px} th {text-align: left} .score {text-align: right} table a {display:block}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><table><tr><th>Language</th><th class="score">Length</th><th>User</th></tr><tbody id="listcontent"></tbody></table>
Jawaban:
CJam, 21 byte
Mengambil string byte sebagai input.
Dalam pseudocode:
Contoh hash:
"" (string kosong) -> 1
"Uji" -> 2607833638733409808360080023081587841
"test" -> 363640467424586895504738713637444713
Mungkin sedikit di sisi sederhana, kisaran output hanya sedikit lebih dari 122 bit, penguatan iterasi tiga sudah agak rusak karena melakukan hal yang persis sama setiap waktu, jadi input yang hash ke 1 di pertama iterasi akan menjadi istirahat penuh. Tetapi ini singkat, dan tidak menyenangkan untuk menjadi terlalu aman.
sumber
Python, 109 byte [ retak , dan lagi ]
Saya mencoba menerapkan fungsi Jenkins satu per satu waktu apa adanya, dengan satu-satunya perbedaan adalah benih dan jumlah bit.
Fakta menyenangkan: Rupanya Perl menggunakan hash Jenkins di beberapa titik .
Pembungkus
Contohnya
sumber
C ++, 148 byte
__uint128_t adalah ekstensi GCC, dan berfungsi seperti yang diharapkan. Hash didasarkan pada iterasi FNV hash (saya telah meminjam prime mereka, meskipun
a
merupakan digit pertama dari Pi dalam hex) dengan rotasi seperti sha1 pada awal setiap iterasi. Mengkompilasi dengan-O3
, hashing file 10MB membutuhkan waktu kurang dari 2 detik, jadi masih ada margin untuk meningkatkan iterasi di loop dalam - tapi saya merasa murah hati hari ini.De-uglified (mengubah nama variabel, menambahkan komentar, spasi putih dan sepasang kawat gigi) untuk kesenangan Anda:
Saran golf dipersilahkan (bahkan jika saya tidak bisa memperbaiki kode berdasarkan pada mereka).
sunting: memperbaiki kesalahan ketik dalam kode yang tidak ditandai (versi golf tetap tidak berubah).
sumber
o
tampaknya tidak diinisialisasi. Di manaoutput
dinyatakan? Atau mungkino
adalahoutput
?n
. Sudahkah Anda benar-benar memeriksa kode "de-uglified" untuk dijalankan?U i=81;i-=3
bisa lebih keji, tanpa biaya runtime yang signifikan.CJam, 44 byte [ retak ]
Input ada di basis 10.
CJam lambat. Saya harap ini berjalan dalam 1 detik di beberapa komputer ...
Penjelasan
Nah, dua hal dimensi tampaknya menjadi kelemahan ... Itu dimaksudkan untuk membuat beberapa perhitungan lambat lebih cepat di awal. Tapi itu tidak bisa berjalan dalam hitungan detik apa pun yang saya lakukan, jadi saya akhirnya menghapus kode yang lambat.
Seharusnya juga lebih baik jika saya telah menggunakan bit biner dan basis yang lebih tinggi.
Versi C.
sumber
C ++, 182 karakter (+ sekitar 51 karakter boilerplate)
Pelat boiler:
Program runnable dengan fungsi golf
sumber
__uint128_t
setelah menerapkan ini.Pyth, 8 Retak
Cobalah online
Sedikit jawaban konyol, saya akan menjelaskan cara kerjanya karena kebanyakan orang tidak dapat membaca Pyth. Ini mengambil log natural dari satu ditambah input, dan kemudian mengubahnya menjadi string. String itu dibalik, kemudian dievaluasi dan kemudian dikonversi ke integer.
Terjemahan python akan terlihat seperti:
sumber
Python 3, 216 byte [ retak ]
Karena ketidakcocokan dengan spesifikasi saya bisa memikirkan setidaknya satu kerentanan sedikit , tetapi selain itu saya pikir ini setidaknya bukti kuat. Saya sudah memeriksa 10 juta hash pertama, antara lain.
Dalam hal golf, ini akan lebih pendek di Python 2, tapi saya sudah mengorbankan beberapa byte untuk efisiensi (karena mungkin tidak akan menang lagi).
Sunting: Ini adalah upaya saya untuk mengimplementasikan Very Smooth Hash , tapi sayangnya 128-bit terlalu kecil.
Pembungkus
Contohnya
Penjelasan kode
Contoh padding untuk
f(6)
:sumber
C, 87 byte [ retak ]
Ini adalah program lengkap; tidak diperlukan pembungkus. Menerima input biner melalui stdin, dan menampilkan hash heksadesimal ke stdout.
Ini hanya menghitung hash 64-bit, jadi saya akan bertaruh di sini.
Jika ada yang bertanya-tanya, dua konstanta
'foo+'
dan'bar/'
adalah bilangan prima 1718578987 dan 1650553391.Contoh:
Abaikan nol terkemuka:
Input byte tunggal:
Input multi-byte:
sumber
foo|
(d5c9bef71d4f5d1b) danfoo\
(d5c9bef71d4f5d1b) menghasilkan hash yang SANGAT mirip.\x00
dan\x00\x00
!J - 39 byte - retak
Berfungsi mengambil string sebagai input dan mengembalikan integer <2 128 . Saya berasumsi kita harus menamai fungsi kita agar valid, jadi hilangkan 3 karakter lagi dari hitungan jika kita bisa mengirimkan fungsi anonim.
Bagi Anda yang tidak membaca hieroglif, berikut adalah ringkasan dari apa yang saya lakukan.
a=.(2^128x)&|@^/@
Ini adalah subrutin * yang mengambil array angka, dan kemudian memperlakukannya sebagai menara listrik, di mana eksponensial diambil mod 2 128 . Dengan "menara listrik", maksud saya jika Anda memberikan input3 4 5 6
, itu akan menghitung3 ^ (4 ^ (5 ^ 6))
.(".p:@+5,9:)a
Fungsi ini mengambil string, mengubahnya menjadi angka N , dan kemudian menghitung bilangan prima ( n +5) -th dan ( n +9) -th, dan kemudian melempara
dari sebelumnya. Yaitu, kita menemukanp(n+5) ^ p(n+9)
mod 2 128 di manap(k)
adalahk
prime -th.H=:_8...\(a...)]
Lakukan fungsi di atas pada sub-blok 8-karakter dari input, dan kemudiana
semua hasil bersama-sama dan panggil fungsi hash yang dihasilkanH
. Saya menggunakan 8 karakter karenak
fungsi " -th prime" J gagal ketikap(k)
> 31 , yaituk=105097564
aman terbesark
.Memiliki beberapa output sampel. Anda dapat mencobanya sendiri secara online di tryj.tk , tetapi saya sangat merekomendasikan melakukan ini di rumah dengan mengunduh juru bahasa dari Jsoftware .
* Secara teknis, ini bukan fungsi di dalam dan dari dirinya sendiri, itu melampirkan ke fungsi lain dan bertindak pada output mereka. Tapi ini adalah masalah semantik J, bukan perbedaan konseptual: aliran program seperti yang saya jelaskan di atas.
sumber
Python 3, 118 byte [ retak ]
Lekukan adalah satu tab. Hash sederhana, belum benar-benar diuji secara menyeluruh.
Panggil sebagai berikut:
hasil:
73117705077050518159191803746489514685
sumber
ord(c)
, jadi benar-benar, string apa pun akan melakukan :) (kecuali hal-hal seperti nul chars, saya pikir itu membuat tabrakan hash sangat mudah. Jadi tetap dengan string 0-9.)C ++, 239 byte
Golf kode pertama saya! [ Mohon lembut ]
Versi tidak disatukan:
Bukan hash terbaik, dan jelas bukan kode terpendek yang ada. Menerima tips bermain golf dan berharap untuk meningkat!
Pembungkus
Mungkin bukan yang terbaik di dunia, tapi bungkusnya
sumber
printf '33333333\x40\xF3\x32\xD6\x56\x91\xCA\x66' | ./hash7_
->a4baea17243177fd
;printf '33333333\x77\x39\xF3\x82\x93\xDE\xA7\x2F' | ./hash7_
->a4baea17243177fd
. Bruteforcer menemukan tabrakan di sini jauh lebih cepat dibandingkan dengan hash 64-bit lainnya di sini.Java,
299291282 byte, retak.Apakah beberapa operasi di BigIntegers, kemudian mengambil modulo 2 128 hasil .
sumber
public
sendiri dulu , menyimpan 7 karakter?C, 128 byte [ retak ]
Algoritma ini kurang lebih sama dengan upaya terakhir saya (di-crack oleh Vi.) , Tetapi sekarang memiliki roda hamster yang cukup untuk menghasilkan hash 128-bit yang tepat.
Empat konstanta utama dalam kode adalah sebagai berikut:
Seperti sebelumnya, ini adalah program lengkap tanpa perlu pembungkus. Integer I adalah input via stdin sebagai data biner mentah (big-endian), dan hash O dicetak dalam hex to stdout. Memimpin nol di I diabaikan.
Contoh:
sumber
C, 122 byte [ retak ]
Loop bersarang, LCG setengah-setengah, dan swapping variabel. Apa yang tidak untuk dicintai?
Berikut ini adalah versi yang tidak disenangi untuk dimainkan:
Ini adalah program mandiri yang membaca dari STDIN dan mencetak ke STDOUT.
Contoh:
Dalam beberapa tolok ukur sederhana, hash sekitar 3MB / s data teks. Kecepatan hash tergantung pada input data itu sendiri, sehingga mungkin harus dipertimbangkan.
sumber
PHP 4.1, 66 byte [ retak ]
Saya hanya pemanasan.
Saya harap Anda menemukan insteresting ini.
Saya sudah mencobanya dengan angka sebesar 999999999999999999999999999.
Outputnya sepertinya berada dalam kisaran 2 128 .
PHP 4.1 diperlukan karena
register_globals
arahan.Ini bekerja dengan secara otomatis membuat variabel lokal dari sesi, POST, DAPATKAN, PERMINTAAN dan cookie.
Itu menggunakan kunci
a
. (EG: akses selesaihttp://localhost/file.php?a=<number>
).Jika Anda ingin mengujinya dengan PHP 4.2 dan yang lebih baru, coba ini:
Versi ini hanya berfungsi dengan POST dan GET.
Contoh output:
(Saya yakinkan Anda bahwa ada angka yang menghasilkan hash yang sama).
sumber
C, 134 byte, Retak
Ini adalah program C yang lengkap.
Kegunaannya: Idenya adalah untuk mengambil input sebagai array byte dan menambahkan byte pseudo acak (tetapi deterministik) pada akhirnya untuk membuat panjangnya sama dengan sekitar 2 2 30 (sedikit lebih). Implementasinya membaca input byte demi byte dan mulai menggunakan data acak semu ketika menemukan karakter pertama yang bukan digit.
Karena PRNG bawaan tidak diizinkan, saya menerapkannya sendiri.
Ada perilaku tidak terdefinisi / implementasi didefinisikan yang membuat kode lebih pendek (nilai akhir harus tidak ditandatangani, dan saya harus menggunakan berbagai jenis untuk nilai yang berbeda). Dan saya tidak bisa menggunakan nilai 128 bit dalam C. Versi yang kurang jelas:
sumber
Python 2.X - 139 bytes [[ Retak ]]
Ini sangat mirip dengan semua hash lainnya (LOOP, XOR, SHIFT, ADD) di sini. Ayo ambil perampok poin Anda;) Saya akan membuat yang lebih sulit setelah ini diselesaikan.
Wrapper (mengharapkan satu argumen dalam basis-16 yang juga dikenal sebagai heksadesimal):
sumber
H(2**(2**10))
butuh sekitar 8 atau 9 detik, sementaraH(2**(2**12))
butuh sekitar 29 detik danH(2**(2**14))
lebih dari dua menit.Python 2.7 - 161 byte [[ Cracked ]]
Yah karena saya berhasil mengubah fungsi hash pertama saya menjadi versi yang tidak berguna sebelum mempostingnya, saya pikir saya akan memposting versi lain dari struktur yang sama. Kali ini saya mengujinya terhadap tabrakan sepele dan saya menguji sebagian besar kemungkinan input untuk kecepatan.
Wrapper (tidak dihitung dalam bytecount)
Jalankan contoh (input selalu berupa angka heksadesimal):
sumber
Ruby, 90 Bytes
Algoritma hash yang sangat acak saya buat tanpa melihat hash nyata ... tidak tahu apakah itu baik. dibutuhkan string sebagai input.
Pembungkus:
sumber
comparison of String with 255 failed (ArgumentError)
.gets.to_i
di bungkusnya.Mathematica, 89 byte, retak
Bukan yang terpendek.
sumber
PHP, 79 Bytes (retak. Dengan komentar):
Ini banyak hal-hal yang menakutkan melalui konversi tipe di php, yang membuatnya sulit untuk diprediksi;) (atau setidaknya saya harap begitu). Namun, itu bukan jawaban terpendek atau paling tidak terbaca.
Untuk menjalankannya, Anda dapat menggunakan PHP4 dan mendaftar global (dengan? I = 123) atau menggunakan baris perintah:
sumber
C # - 393 bytes retak
Tidak Disatukan:
Saya belum pernah menyentuh kriptografi atau hashing dalam hidup saya, jadi lembutlah :)
Ini adalah implementasi sederhana hash FNV-1a dengan beberapa array berputar pada input. Saya yakin ada cara yang lebih baik untuk melakukan ini tetapi ini adalah yang terbaik yang bisa saya lakukan.
Mungkin menggunakan sedikit memori pada input panjang.
sumber
Python 2, 115 byte [ Sudah retak! ]
Oke, ini usaha terakhir saya. Hanya 115 byte karena baris baru final tidak diperlukan.
Ini adalah program lengkap yang memasukkan bilangan bulat desimal pada stdin dan mencetak nilai hash desimal pada stdout. Nol memimpin ekstra akan menghasilkan nilai hash yang berbeda, jadi saya hanya akan berasumsi bahwa input tidak memilikinya.
Ini bekerja dengan memasukkan 197-digit potongan nomor input melalui eksponensial modular. Tidak seperti beberapa bahasa,
int()
fungsi selalu default ke basis 10, jadiint('077')
juga 77, bukan 63.Output sampel:
sumber