Hashing Panjang Sewenang-wenang

16

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 .H2nnssH(s)=H(s)

Anda sekarang ingin membangun fungsi hash baru yang membutuhkan string dengan panjang sewenang - wenang dan memetakannya ke string dengan panjang , sambil tetap tahan tabrakan.Hn

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 n>0 , fungsi hash H seperti yang dijelaskan di atas dan string input s panjang sewenang-wenang, fungsi hash baru H 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 .l=|s|ssnm=lnc1,c2,,cm
  • 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 .c0cm+1c0ncm+1nn
  • 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.)Hciri1ri=H(ri1ci)r0=c0
  • Output dari adalah hasil akhir .Hrm+1

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.nHsH

Ini adalah , 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.n=5H

  • Diberikan masukan dari , kita mendapatkan potongan-potongan berikut: , , dan . Perhatikan bahwa harus diisi hingga panjang 5 dengan satu nol di belakangnya.s="Programming Puzzles"s1="Progr"s2="ammin"s3="g Puz"s4="zles0"s4
  • c0="00000" hanyalah string dari lima nol dan adalah lima dalam biner ( ), diisi dengan dua nol di depan.c5="00101"101
  • Sekarang potongan digabungkan dengan :H
    r0=c0="00000"
    r1=H(r0c1)=H("00000Progr")
    r2=H(r1c2)=H(H("00000Progr")"ammin") r3=H(r2c3)=H(H(H("00000Progr")"ammin")"g Puz")
    r4=H(r3c4)=H(H(H(H("00000Progr")"ammin")"g Puz")"zles0")
    r5=H(r4c5)=H(H(H(H(H("00000Progr")"ammin")"g Puz")"zles0")"00101")
  • r5 adalah output kami.

Mari kita lihat bagaimana output ini akan tergantung pada beberapa pilihan 1 untuk :H

  • Jika , yaitu hanya mengembalikan setiap karakter kedua, kita mendapatkan: Jadi perlu menjadi output jika itu diberikan sebagai fungsi kotak hitam.H("0123456789")="13579"H
    r1=H("00000Progr")="00Por"
    r2=H("00Porammin")="0oamn"
    r3=H("0oamng Puz")="omgPz"
    r4=H("omgPzzles0")="mPze0"
    r5=H("mPze000101")="Pe011"
    "Pe011"H
  • Jika hanya mengembalikan 5 karakter pertama dari inputnya, output dari adalah . Demikian pula jika mengembalikan 5 karakter terakhir, hasilnya adalah .HH"00000"H"00101"
  • Jika mengalikan kode karakter dari inputnya dan mengembalikan lima digit pertama dari angka ini, misalnya , maka .HH("PPCG123456")="56613"H("Programming Puzzles")="91579"

1 Untuk kesederhanaan, itu sebenarnya tidak tahan tabrakan, meskipun ini tidak masalah untuk menguji kiriman Anda.H

Laikoni
sumber
Saya harus mengatakan itu menyenangkan bahwa contoh yang diberikan memiliki hash 'penuh' terakhir dari "Teka-teki OMG!" secara efektif omgPzzles0. Contoh input yang dipilih dengan baik!
LambdaBeta
Bisakah kita mengasumsikan fleksibilitas pada format input untuk H (mis. Dibutuhkan dua string dengan panjang n, atau string yang lebih panjang yang hanya mempertimbangkan karakter 2n pertama)?
Delfad0r
Apakah karakter spasi, misalnya, antara "g P" output yang valid?
tamu271314
@ guest271314 Jika ruang tersebut adalah bagian dari hash yang dihasilkan, itu perlu dikeluarkan. Jika hash sebenarnya "gP", Anda mungkin tidak menampilkan ruang inbetween.
Laikoni

Jawaban:

7

Haskell , 91 90 86 byte

  • -1 byte terima kasih kepada Laikoni
  • -4 byte berkat xnor
n!h|let a='0'<$[1..n];c?""=c;c?z=h(c++take n(z++a))?drop n z=h.(++mapM(:"1")a!!n).(a?)

Cobalah online!

Penjelasan

a='0'<$[1..n]

Hanya menetapkan string "00...0"( '0' n kali) kea


c?""=c
c?z=h(c++take n(z++a))?drop n z

Fungsi ?mengimplementasikan aplikasi rekursif dari h: cadalah hash yang telah kita peroleh sejauh ini (panjang n ), zadalah sisa dari string. Jika zkosong maka kita cukup kembali c, jika tidak kita mengambil n karakter pertama z(mungkin diisi dengan nol dari a), tambahkan cdan terapkan h. Ini memberikan hash baru, dan kemudian kita memanggil ?secara berulang hash ini dan karakter yang tersisa dari z.


n!h=h.(++mapM(:"1")a!!n).(a?)

Fungsi !adalah yang benar-benar menyelesaikan tantangan. Dibutuhkan n, hdan s(tersirat) sebagai input. Kami menghitung a?s, dan yang harus kami lakukan adalah menambahkan ndalam biner dan menerapkan hsekali lagi. mapM(:"1")a!!nmengembalikan representasi biner dari n .

Delfad0r
sumber
1
letdi penjaga lebih pendek daripada menggunakan where: Coba online!
Laikoni
2
Sepertinya mapM(\_->"01")abisa mapM(:"1")a.
xnor
7

R , 159 154 byte

function(n,H,s,`?`=paste0,`*`=strrep,`/`=Reduce,`+`=nchar,S=0*n?s?0*-(+s%%-n)?"?"/n%/%2^(n:1-1)%%2)(function(x,y)H(x?y))/substring(S,s<-seq(,+S,n),s--n-1)

Cobalah online!

Huek! Menjawab tantangan 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.

function(n,H,s,               # harmless-looking function arguments with horrible default arguments 
                              # to prevent the use of {} and save two bytes
                              # then come the default arguments,
                              # replacing operators as aliases for commonly used functions:
 `+`=paste0,                  # paste0 with binary +
 `*`=strrep,                  # strrep for binary *
 `/`=Reduce,                  # Reduce with binary /
 `?`=nchar,                   # nchar with unary ?
 S=                           # final default argument S, the padded string:
  0*n+                        # rep 0 n times
  s+                          # the original string
  0*-((?s)%%-n)+              # 0 padding as a multiple of n
  "+"/n%/%2^(n:1-1)%%2)       # n as an n-bit number
                              # finally, the function body:
 (function(x,y)H(x+y)) /      # Reduce/Fold (/) by H operating on x + y
  substring(S,seq(1,?S,n),seq(n,?S,n))  # operating on the n-length substrings of S
Giuseppe
sumber
Saya pikir 0*(n-(?s)%%n)tidak berfungsi jika n membagi s secara merata. Tetapi 0*-((?s)%%-n)harus bekerja.
nwellnhof
@wellwell ah, tentu saja, terima kasih, sudah diperbaiki.
Giuseppe
Perubahan kecil, 155 byte
J.Doe
1
@ J.Apakah bagus! Saya menyimpan byte lain karena seqtelah 1sebagai fromargumennya secara default.
Giuseppe
3

C (gcc) , 251 byte

#define P sprintf(R,
b(_){_=_>1?10*b(_/2)+_%2:_;}f(H,n,x)void(*H)(char*);char*x;{char R[2*n+1],c[n+1],*X=x;P"%0*d",n,0);while(strlen(x)>n){strncpy(c,x,n);x+=n;strcat(R,c);H(R);}P"%s%s%0*d",R,x,n-strlen(x),0);H(R);P"%s%0*d",R,n,b(n));H(R);strcpy(X,R);}

Cobalah online!

Tidak sebersih solusi bash, dan sangat bisa diperbaiki.

Fungsi ini fmengambil Hsebagai fungsi yang menggantikan input string dengan hash string itu, nseperti dalam deskripsi, dan xstring input dan output buffer.

Deskripsi:

#define P sprintf(R,     // Replace P with sprintf(R, leading to unbalanced parenthesis
                         // This is replaced and expanded for the rest of the description
b(_){                    // Define b(x). It will return the integer binary expansion of _
                         // e.g. 5 -> 101 (still as integer)
  _=_>1?                 // If _ is greater than 1
    10*b(_/2)+_%2        // return 10*binary expansion of _/2 + last binary digit
    :_;}                 // otherwise just _
f(H,n,x)                 // Define f(H,n,x)
  void(*H)(char*);       // H is a function taking a string
  char*x; {              // x is a string
  char R[2*n+1],c[n+1],  // Declare R as a 2n-length string and c as a n-length string
  *X=x;                  // save x so we can overwrite it later
  sprintf(R,"%0*d",n,0); // print 'n' 0's into R
  while(strlen(x)>n){    // while x has at least n characters
    strncpy(c,x,n);x+=n; // 'move' the first n characters of x into c
    strcat(R,c);         // concatenate c and R
    H(R);}               // Hash R
  sprintf(R,"%s%s%0*d"   // set R to two strings concatenated followed by some zeroes
    R,x,                 // the two strings being R and (what's left of) x
    n-strlen(x),0);      // and n-len(x) zeroes
  H(R);                  // Hash R
  sprintf(R,"%s%*d",R,n, // append to R the decimal number, 0 padded to width n
    b(n));               // The binary expansion of n as a decimal number
  H(R);strcpy(X,R);}     // Hash R and copy it into where x used to be
LambdaBeta
sumber
229 bytes
ceilingcat
Saya pikir: 227 byte (keluar dari komentar
ceilingcat
3

Ruby , 78 byte

->n,s,g{(([?0*n]*2*s).chop.scan(/.{#{n}}/)+["%0#{n}b"%n]).reduce{|s,x|g[s+x]}}

Cobalah online!

Bagaimana itu bekerja:

([?0*n]*2*s).chop    # Padding: add leading and trailing 
                     # zeros, then remove the last one
.scan(/.{#{n}}/)     # Split the string into chunks
                     # of length n
+["%0#{n}b"%n]       # Add the trailing block
.reduce{|s,x|g[s+x]} # Apply the hashing function
                     # repeatedly
GB
sumber
2

Jelly , 23 byte

0Ṿ;s;BṾ€ṚWƲ}z”0ZU0¦;Ç¥/

Cobalah online!

Terima H pada baris di atasnya, s sebagai argumen kiri, dan n sebagai argumen kanannya.

Erik the Outgolfer
sumber
2

Bash , 127-ε byte

Z=`printf %0*d $1` R=$Z
while IFS= read -rn$1 c;do R=$R$c$Z;R=`H<<<${R::2*$1}`;done
H< <(printf $R%0*d $1 `bc <<<"obase=2;$1"`)

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:

$ H() {
>   sed 's/.\(.\)/\1/g'
> }
$ ./wherever_you_put_the_script.sh 5 <<< "Programming Puzzles"  # if you add a shebang
Pe011

Deskripsi:

Z=`printf %0*d $1`

Ini menciptakan string $1nol. 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.

R=$Z

Ini hanya menyalin Z, string nol kami, ke R, string hasil kami, dalam persiapan untuk loop hashing.

while IFS= read -rn$1 c; do

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. The ropsi memastikan bahwa setiap karakter khusus dalam input tidak mendapatkan bash ditafsirkan. Ini adalah judulnya - yang rtidak sepenuhnya diperlukan, tetapi membuat fungsinya lebih akurat sesuai dengan input.

R=$R$c$Z

Ini menyatukan n karakter yang dibaca dari input ke R bersama dengan nol untuk padding (terlalu banyak nol untuk saat ini).

R=`H<<<${R::2*$1}`;done

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:

H< <(printf $R%0*d $1 `bc <<<"obase=2;$1"`)

Di sini trik format string yang sama digunakan untuk 0 pad nomor. bcdigunakan 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.

LambdaBeta
sumber
Kenapa "127-ε"? Kenapa tidak "127" saja?
Solomon Ucko
Saya tidak tahu Saya berada di pagar tentang perlunya rbendera. Saya pikir 1 byte tidak terlalu penting, tetapi jika didorong saya bisa mencukurnya.
LambdaBeta
Untuk readperintah?
Solomon Ucko
Karena tanpanya `` dalam input akan ditafsirkan alih-alih diabaikan, jadi mereka harus melarikan diri.
LambdaBeta
Mungkin menambahkan catatan tentang itu?
Solomon Ucko
2

Pyth , 24 byte

Karena Pyth tidak mengizinkan H digunakan untuk nama fungsi, saya menggunakan ysebagai gantinya.

uy+GH+c.[E=`ZQQ.[ZQ.BQ*Z

Cobalah online! Contoh adalah dengan versi "setiap karakter kedua" dari H.

Steven H.
sumber
2

Perl 6 , 79 68 byte

{reduce &^h o&[~],comb 0 x$^n~$^s~$n.fmt("%.{$n-$s.comb%-$n}b"): $n}

Cobalah online!

Penjelasan

{
  reduce         # Reduce with
    &^h o&[~],   # composition of string concat and hash function
    comb         # Split string
      0 x$^n     # Zero repeated n times
      ~$^s       # Append input string s
      ~$n.fmt("  # Append n formatted
        %.       # with leading zeroes,
        {$n             # field width n for final chunk
         -$s.comb%-$n}  # -(len(s)%-n) for padding,
        b")      # as binary number
      :          # Method call with colon syntax
      $n         # Split into substrings of length n
}
nwellnhof
sumber
1

Bersih , 143 byte

import StdEnv
r=['0':r]
$n h s=foldl(\a b=h(a++b))(r%(1,n))([(s++r)%(i,i+n-1)\\i<-[0,n..length s]]++[['0'+toChar((n>>(n-p))rem 2)\\p<-[1..n]]])

Cobalah online!

Suram
sumber
1

Python 2 , 126 113 byte

lambda n,H,s:reduce(lambda x,y:H(x+y),re.findall('.'*n,'0'*n+s+'0'*(n-len(s)%n))+[bin(n)[2:].zfill(n)])
import re

Cobalah online!

-13 terima kasih kepada Triggernometry .

Ya, ini adalah kekejian, mengapa saya tidak bisa hanya menggunakan built-in untuk membagi string menjadi potongan-potongan ...? :-(

Erik the Outgolfer
sumber
codegolf.stackexchange.com/a/173952/55696 Sebuah whilelingkaran adalah yang terbaik builtin saya bisa berharap untuk. 104 byte
Steven H.
@ SevenH. Ya, terutama jika Anda benar-benar fokus pada golf itu sendiri. > _>
Erik the Outgolfer
'0'*~-nbukannya '0'*(len(s)%n)lebih pendek (dan sebenarnya mengoreksi input yang lebih pendek).
nwellnhof
@wellwell Ya, tapi itu jelas bukan hal yang sama.
Erik the Outgolfer
Mungkin saya tidak cukup jelas. Solusi Anda memberikan jawaban yang salah untuk string seperti Programming Puzz(16 karakter). Mengganti '0'*(len(s)%n)dengan '0'*~-nperbaikan itu dan menyimpan 7 byte.
nwellnhof
1

Python 2 , 106 102 byte

Untuk sekali ini, fungsinya mengalahkan lambda. -4 byte untuk manipulasi sintaksis sederhana, terima kasih kepada Jo King.

def f(n,H,s):
 x='0'*n;s+='0'*(n-len(s)%n)+bin(n)[2:].zfill(n)
 while s:x=H(x+s[:n]);s=s[n:]
 return x

Cobalah online!

Steven H.
sumber
Bukankah seharusnya hasilnya 'Pe011', bukan 'e011'?
Triggernometri
Itu seharusnya. Tetap!
Steven H.
Gunakan semi-titik dua bukan baris baru. -4 byte
Jo King
Saya tidak menyadari bahwa itu bekerja untuk saat loop juga, terima kasih!
Steven H.
1

Japt , 27 byte

òV ú'0 pV¤ùTV)rÈ+Y gOvW}VçT

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, OvWambil input ketiga dan interpretasikan sebagai Japt, lalu gpanggil. Mengganti itu dengan OxWmemungkinkan input sebagai fungsi Javascript, atau jika fungsi itu (entah bagaimana) sudah disimpan di W itu bisa saja Wdan menyimpan 2 byte. Tautan di atas memiliki contoh kerjaHyang mengambil karakter pada indeks ganjil, sedangkan yang ini adalah contoh "gandakan kode-kod dan ambil 5 angka tertinggi" contoh.

Karena cara Japt mengambil input, sakan menjadi U,nakan V, danH akan W

Penjelasan:

òV                             Split U into segments of length V
   ú'0                         Right-pad the short segment with "0" to the same length as the others
       p     )                 Add an extra element:
        V¤                       V as a base-2 string
          ùTV                    Left-pad with "0" until it is V digits long
              r                Reduce...
                        VçT          ...Starting with "0" repeated V times...
               È       }                                                  ...By applying:
                +Y               Combine with the previous result
                   gOvW          And run W as Japt code

Kamil Drakari
sumber
0

OK , 41 byte

{(x#48)(y@,)/(0N,x)#z,,/$((x+x!-#z)#2)\x}

Cobalah online!

{                                       } /x is n, y is H, z is s.
                          (x+x!-#z)       /number of padding 0's needed + x
                         (         #2)\x  /binary(x) with this length
                      ,/$                 /to string
                    z,                    /append to z
             (0N,x)#                      /split into groups of length x
       (y@,)/                             /foldl of y(concat(left, right))...
 (x#48)                                   /...with "0"*x as the first left string
zgrep
sumber