Apakah ada algoritma hash 'refleksif'?

Apakah ada kelas algoritma hash, apakah teoretis atau praktis, sehingga suatu algoritma di kelas dapat dianggap 'refleksif' sesuai dengan definisi yang diberikan di bawah ini:

hash1 = algo1 ("input teks 1")
hash1 = algo1 ("input teks 1" + hash1)

Operator + mungkin merupakan gabungan atau operasi tertentu lainnya untuk menggabungkan output (hash1) kembali ke input ("input text 1") sehingga algoritma (algo1) akan menghasilkan hasil yang persis sama. yaitu tabrakan pada input dan input + output. Operator + harus menggabungkan keseluruhan input dan algo tidak boleh membuang bagian dari input.

Algoritme harus menghasilkan entropi tinggi dalam output. Mungkin, tetapi tidak perlu, sulit secara kriptografi untuk membalikkan output kembali ke satu atau kedua input yang mungkin.

Saya bukan ahli matematika, tetapi jawaban yang baik mungkin termasuk bukti mengapa kelas algoritma seperti itu tidak ada. Namun, ini bukan pertanyaan abstrak. Saya benar-benar tertarik menggunakan algoritma seperti itu di sistem saya, jika ada.

Ini adalah duplikat dari pertanyaan yang pertama kali diposting di /programming/4823680/reflexive-hash

ds.algorithms hash-function Komunitas
sumber

Terkait: Pencampuran hash asosiatif

Tsuyoshi Ito

Apakah Anda tertarik pada properti ini yang menampung semua teks input atau untuk satu teks input? Jika Anda ingin menahan untuk semua input teks maka membangun collision adalah sepele oleh desain jadi saya tidak berpikir itu dapat dianggap sebagai fungsi hash yang baik.

Peter Taylor

Seseorang ingin file hash yang berisi hash mereka sendiri! ;)

Raphael

@ Peter Taylor - Saya mencari fungsi yang berfungsi seperti yang dijelaskan untuk teks input sewenang-wenang. Setiap input yang berbeda menghasilkan hash yang secara umum memiliki entropi timbal balik yang tinggi untuk setiap input lain yang mungkin. Sebanyak fungsi hash ireversibel yang baik bekerja. Namun, fungsi hash yang saya cari tidak perlu memiliki properti irreversibilitas. Entropi tinggi sudah cukup.

@ Raphael - Yap, itu cara ringkas untuk menggambarkannya.

Jawaban:

Saya memberikan konstruksi sepele yang memenuhi persyaratan. Saya menyediakannya hanya untuk menjawab keberadaan fungsi hash "refleksif".

Biarkan menjadi fungsi hash yang menghasilkan entropi tinggi dalam output. Asumsikan bahwa string biner panjang sewenang-wenang ke string biner bit, di mana adalah bilangan bulat positif. Biarkan menunjukkan operator gabungan , dan biarkan menunjukkan panjang string biner . $G$ $G$ $k$ $k$ $+$ $|x|$ $x$

Tentukan fungsi hash pada input sebagai berikut: $H$ $x$

Jika , maka . $|x| \le k$ $H(x) \overset{\text{def}}{=} G(x)$
Jika , misalkan dan menjadi awalan -bit dan akhiran -bit masing-masing . Yaitu, dan . Jika (di mana dihitung secara rekursif ), maka $|x| > k$ $L$ $R$ $(|x|-k)$ $k$ $x$ $x = L + R$ $|R|=k$ $R = H(L)$ $H(L)$ ; jika tidak,. $H(x) \overset{\text{def}}{=} R$ $H(x) \overset{\text{def}}{=} G(x)$

Seperti yang saya katakan, ini adalah konstruksi yang sepele. Ini dapat diterapkan pada fungsi hash, praktis (seperti MD5, SHA-1, ...) atau teoretis.

MS Dousti
sumber

Saya tidak begitu yakin di bidang pengkodean, tetapi apakah

masih memiliki entropi yang tinggi? Dengan konstruksi, itu tentu memiliki hash yang sama untuk menggandakan string sebanyak sebelumnya. Dan mereka datang berpasangan yang sangat dekat satu sama lain. (Oh, seharusnya

di baris kedua 2.)

H

$H$

| R | = k

$|R|=k$

Raphael

@ Raphael: Terima kasih telah menunjukkan kesalahan ketik (diperbaiki). H memiliki entropi yang sama dengan G, kecuali dalam kondisi di mana R = G (L). Dengan persyaratan, dalam kondisi ini, H (x) harus sama dengan R. Kami tidak dapat melakukan apa pun di sini untuk meningkatkan entropi; karena persyaratan "refleksivitas" mencegah kita mengubah output.

MS Dousti

@ Sadq: Apakah diperlukan fungsi hash untuk dihitung secara rekursif? Apakah algoritma mendapatkan manfaat dari fakta ini?

Yasser Sobhdel

H (M + H (M) + H (M) + \dots + H (M))

$H(M+H(M)+H(M)+\ldots+H(M))$

H (M)

$H(M)$

Sadeq, terima kasih. Saya percaya ini dapat menjawab pertanyaan saya, seperti yang ditanyakan. Anda telah menuliskan jawabannya dalam peringatan yang sesuai. Dari sudut pandang pragmatis, saya menyukai kenyataan bahwa ini merupakan overlay untuk algoritma terkenal seperti SHA-1. Jika saya mengerti dengan benar, algoritma Anda akan terus menghitung hash secara rekursif sampai hits tabrakan yang diperlukan dan kemudian berhenti. Dalam hal ini mungkin kita bisa menjuluki ini solusi naif. Kekhawatiran saya adalah tampaknya ada asumsi implisit bahwa algoritma tertanam (SHA-1 katakan) pada akhirnya akan mencapai hash tabrakan yang diperlukan, mengingat