Anggap Anda memiliki fungsi hash yang mengambil string dengan panjang dan mengembalikan string dengan panjang dan memiliki properti bagus yang tahan benturan , yaitu sulit untuk menemukan dua string berbeda dengan hash yang sama .
Anda sekarang ingin membangun fungsi hash baru yang membutuhkan string dengan panjang sewenang - wenang dan memetakannya ke string dengan panjang , sambil tetap tahan tabrakan.
Beruntung bagi Anda, sudah pada tahun 1979 sebuah metode yang sekarang dikenal sebagai konstruksi Merkle-Damgård diterbitkan yang mencapai hal ini.
Tugas dari tantangan ini adalah untuk mengimplementasikan algoritma ini, jadi pertama-tama kita akan melihat deskripsi formal dari konstruksi Merkle-Damgård, sebelum melalui contoh langkah-demi-langkah yang seharusnya menunjukkan bahwa pendekatannya lebih sederhana daripada mungkin muncul pada awalnya.
Diberikan bilangan bulat , fungsi hash seperti yang dijelaskan di atas dan string input panjang sewenang-wenang, fungsi hash baru melakukan hal berikut:
- Set, Panjang , dan perpecahan dalam potongan panjang , mengisi potongan terakhir dengan tertinggal nol jika diperlukan. Ini menghasilkan banyak potongan yang diberi label .
- Tambahkan terkemuka dan trailing sepotong dan , di mana adalah string yang terdiri dari angka nol dan adalah dalam biner, empuk dengan terkemuka nol dengan panjang .
- Sekarang secara iteratif terapkan ke chunk saat ini ditambahkan ke hasil sebelumnya : , di mana . (Langkah ini mungkin lebih jelas setelah melihat contoh di bawah ini.)
- Output dari adalah hasil akhir .
Tugas
Tulis program atau fungsi yang mengambil input bilangan bulat positif , fungsi hash sebagai kotak hitam dan string yang tidak kosong dan mengembalikan hasil yang sama dengan pada input yang sama.
Ini adalah kode-golf , jadi jawaban tersingkat di setiap bahasa menang.
Contoh
Katakanlah , jadi fungsi hash yang diberikan mengambil string dengan panjang 10 dan mengembalikan string dengan panjang 5.
- Diberikan masukan dari , kita mendapatkan potongan-potongan berikut: , , dan . Perhatikan bahwa harus diisi hingga panjang 5 dengan satu nol di belakangnya.
- hanyalah string dari lima nol dan adalah lima dalam biner ( ), diisi dengan dua nol di depan.
- Sekarang potongan digabungkan dengan :
- adalah output kami.
Mari kita lihat bagaimana output ini akan tergantung pada beberapa pilihan 1 untuk :
- Jika , yaitu hanya mengembalikan setiap karakter kedua, kita mendapatkan:
Jadi perlu menjadi output jika itu diberikan sebagai fungsi kotak hitam.
- Jika hanya mengembalikan 5 karakter pertama dari inputnya, output dari adalah . Demikian pula jika mengembalikan 5 karakter terakhir, hasilnya adalah .
- Jika mengalikan kode karakter dari inputnya dan mengembalikan lima digit pertama dari angka ini, misalnya , maka .
1 Untuk kesederhanaan, itu sebenarnya tidak tahan tabrakan, meskipun ini tidak masalah untuk menguji kiriman Anda.
omgPzzles0
. Contoh input yang dipilih dengan baik!Jawaban:
Haskell ,
919086 byteCobalah online!
Penjelasan
Hanya menetapkan stringn kali) ke
"00...0"
('0'
a
Fungsin ), n karakter pertama
?
mengimplementasikan aplikasi rekursif darih
:c
adalah hash yang telah kita peroleh sejauh ini (panjangz
adalah sisa dari string. Jikaz
kosong maka kita cukup kembalic
, jika tidak kita mengambilz
(mungkin diisi dengan nol daria
), tambahkanc
dan terapkanh
. Ini memberikan hash baru, dan kemudian kita memanggil?
secara berulang hash ini dan karakter yang tersisa dariz
.Fungsin .
!
adalah yang benar-benar menyelesaikan tantangan. Dibutuhkann
,h
dans
(tersirat) sebagai input. Kami menghitunga?s
, dan yang harus kami lakukan adalah menambahkann
dalam biner dan menerapkanh
sekali lagi.mapM(:"1")a!!n
mengembalikan representasi biner darisumber
let
di penjaga lebih pendek daripada menggunakanwhere
: Coba online!mapM(\_->"01")a
bisamapM(:"1")a
.R ,
159154 byteCobalah online!
Huek! Menjawab tantangan string dalam R tidak pernah cantik, tapi ini mengerikan. Ini adalah jawaban instruktif tentang bagaimana tidak menulis kode R "normal" ...
Terima kasih kepada nwellnhof karena telah memperbaiki bug, dengan biaya 0 byte!
Terima kasih kepada J.Doe untuk menukar operator alias untuk mengubah prioritas, bagus untuk -4 byte.
Penjelasan di bawah ini untuk versi kode sebelumnya, tetapi prinsip-prinsipnya tetap sama.
sumber
0*(n-(?s)%%n)
tidak berfungsi jika n membagi s secara merata. Tetapi0*-((?s)%%-n)
harus bekerja.seq
telah1
sebagaifrom
argumennya secara default.C (gcc) , 251 byte
Cobalah online!
Tidak sebersih solusi bash, dan sangat bisa diperbaiki.
Fungsi ini
f
mengambilH
sebagai fungsi yang menggantikan input string dengan hash string itu,n
seperti dalam deskripsi, danx
string input dan output buffer.Deskripsi:
sumber
Ruby , 78 byte
Cobalah online!
Bagaimana itu bekerja:
sumber
Jelly , 23 byte
Cobalah online!
TerimaH pada baris di atasnya, s sebagai argumen kiri, dan n sebagai argumen kanannya.
sumber
Bash , 127-ε byte
Cobalah online!
Ini berfungsi sebagai program / fungsi / skrip / cuplikan. H harus dapat diselesaikan ke program atau fungsi yang akan melakukan hashing. N adalah argumennya. Contoh panggilan:
Deskripsi:
Ini menciptakan string
$1
nol. Ini berfungsi dengan memanggil printf dan menyuruhnya mencetak bilangan bulat yang diisi dengan lebar argumen ekstra . Argumen tambahan yang kami sampaikan adalah$1
, argumen ke program / fungsi / skrip yang menyimpan n.Ini hanya menyalin Z, string nol kami, ke R, string hasil kami, dalam persiapan untuk loop hashing.
Ini loop atas input setiap
$1
(n) karakter memuat karakter yang telah dibaca ke dalam c. Jika input berakhir maka c hanya berakhir terlalu pendek. Ther
opsi memastikan bahwa setiap karakter khusus dalam input tidak mendapatkan bash ditafsirkan. Ini adalah-ε
judulnya - yangr
tidak sepenuhnya diperlukan, tetapi membuat fungsinya lebih akurat sesuai dengan input.Ini menyatukan n karakter yang dibaca dari input ke R bersama dengan nol untuk padding (terlalu banyak nol untuk saat ini).
Ini menggunakan string di sini sebagai input ke fungsi hash. Isi
${R::2*$1}
adalah substitusi parameter bash agak esoteris yang bertuliskan: R, mulai dari 0, hanya 2n karakter.Di sini loop berakhir dan kita selesai dengan:
Di sini trik format string yang sama digunakan untuk 0 pad nomor.
bc
digunakan untuk mengubahnya menjadi biner dengan mengatur basis output (obase) ke 2. Hasilnya dilewatkan ke fungsi / program hash yang outputnya tidak ditangkap dan dengan demikian ditampilkan kepada pengguna.sumber
r
bendera. Saya pikir 1 byte tidak terlalu penting, tetapi jika didorong saya bisa mencukurnya.read
perintah?Pyth , 24 byte
Karena Pyth tidak mengizinkan H digunakan untuk nama fungsi, saya menggunakan
y
sebagai gantinya.Cobalah online! Contoh adalah dengan versi "setiap karakter kedua" dari H.
sumber
Perl 6 ,
7968 byteCobalah online!
Penjelasan
sumber
Bersih , 143 byte
Cobalah online!
sumber
Python 2 ,
126113 byteCobalah online!
-13 terima kasih kepada Triggernometry .
Ya, ini adalah kekejian, mengapa saya tidak bisa hanya menggunakan built-in untuk membagi string menjadi potongan-potongan ...? :-(
sumber
while
lingkaran adalah yang terbaik builtin saya bisa berharap untuk. 104 byte'0'*~-n
bukannya'0'*(len(s)%n)
lebih pendek (dan sebenarnya mengoreksi input yang lebih pendek).Programming Puzz
(16 karakter). Mengganti'0'*(len(s)%n)
dengan'0'*~-n
perbaikan itu dan menyimpan 7 byte.Python 2 ,
106102 byteUntuk sekali ini, fungsinya mengalahkan lambda. -4 byte untuk manipulasi sintaksis sederhana, terima kasih kepada Jo King.
Cobalah online!
sumber
Japt , 27 byte
Cobalah!
Saya belum menemukan kemampuan untuk Japt untuk mengambil fungsi secara langsung sebagai input, jadi ini mengambil string yang ditafsirkan sebagai kode Japt dan mengharapkannya untuk mendefinisikan fungsi. Secara khusus,H yang mengambil karakter pada indeks ganjil, sedangkan yang ini adalah contoh "gandakan kode-kod dan ambil 5 angka tertinggi" contoh.
OvW
ambil input ketiga dan interpretasikan sebagai Japt, lalug
panggil. Mengganti itu denganOxW
memungkinkan input sebagai fungsi Javascript, atau jika fungsi itu (entah bagaimana) sudah disimpan di W itu bisa sajaW
dan menyimpan 2 byte. Tautan di atas memiliki contoh kerjaKarena cara Japt mengambil input,s akan menjadi n akan H akan
U
,V
, danW
Penjelasan:
sumber
GolfScript , 47 byte
Cobalah online!
sumber
OK , 41 byte
Cobalah online!
sumber