hasz zwrotny?

Question

istnieje klasa algorytmów mieszających, czy teoretyczne i praktyczne, tak że algo do klasy może być uważane za „zwrotny”, według definicji poniżej:

• hash1 = algo1 („tekstu wejściowego 1”)
• hash1 = algo1 („tekstu wejściowego 1” + hash1)

operatora + może być konkatenacją lub inny określonej operacji łączenia wyjścia (hash1) z powrotem do wejścia („tekstu wejściowego 1”) tak, że algorytm (algo1) da dokładnie taki sam wynik. tj. kolizja na wejściu i wejściu + wyjściu. Operator + musi łączyć w całość oba wejścia, a algo nie może odrzucić części wejścia.

Algorytm musi wytworzyć 128 bitów entropii na wyjściu. Może, ale nie musi, być trudne do kryptografii, aby odwrócić wyjście z jednego lub obu możliwych wejść.

Nie jestem matematykiem, ale dobra odpowiedź może zawierać dowód na to, dlaczego taka klasa algorytmów nie może istnieć. To jednak nie jest pytanie abstrakcyjne. Jestem naprawdę zainteresowany wykorzystaniem takiego algorytmu w moim systemie, jeśli taki istnieje.

Answer 1

Cóż, mogę Ci powiedzieć, że nie dostaniesz dowodu na nieistnienie. Oto przykład:

operator + (a, b): oblicz 64-bitowy skrót hash, 64-bitowy skrót hash i łącz konkrenty łańcuchowe, zwracając 128-bitowy skrót.

algo1: dla pewnej wartości 128 bitów ignorować ostatnie 64 bitów i oblicz mieszania pierwszego 64.

nieformalnie dowolnego algo1 który daje pierwszego operatora o + w pierwszym etapie będzie. Może nie tak interesująca klasa, jak ci się wydawało, ale pasuje do rachunku. I nie jest bez przykładów w prawdziwym świecie. Wiele algorytmów haszowania hasłem obcina ich dane wejściowe.

Answer 2

Jestem prawie pewna, że ​​taka funkcja "reflektywnego skrótu" (jeśli istniałaby w większym niż trywialny sposób znaczeniu) nie byłaby użyteczną funkcją mieszającą w normalnym znaczeniu.

Na przykład funkcji mieszającej refleksyjnym "trywialny":

int hash(Object obj) { return 0; } 

Answer 3

Jasne, tu jest trywialne jeden:

def algo1(input): 
    sum = 0 
    for i in input: 
     sum += ord(i) 
    return chr(sum % 256) + chr(-sum % 256) 

złączyć wynik i "hash" nie ulega zmianie. Łatwo jest wymyślić coś podobnego, gdy można odwrócić hash.

Answer 4

Opierając się na ephemiat's answer, myślę, że można zrobić coś takiego:

Wybierz swój ulubiony klucz symetryczny szyfr blokowy (np .: AES). Dla konkretności, powiedzmy, że działa na blokach 128-bitowych. Dla danego klawisza K oznacz to funkcję szyfrowania i funkcję deszyfrującą odpowiednio przez Enc (K, blok) i Dec (K, blok), tak aby blok = Dec (K, Enc (K, blok)) = Enc (K, Dec (K, blok)).

Podziel dane wejściowe na tablicę bloków 128-bitowych (wypełnienie w razie potrzeby). Możesz wybrać stały klucz K lub uczynić go częścią wejścia do mieszania. W dalszej części zakładamy, że jest on poprawiony.

def hash(input): 
    state = arbitrary 128-bit initialization vector 
    for i = 1 to len(input) do 
     state = state^Enc(K, input[i]) 
    return concatenate(state, Dec(K, state)) 

Ta funkcja zwraca 256-bitowy skrót. Nie powinno być zbyt trudno zweryfikować, czy spełnia warunek "refleksyjności" z jednym zastrzeżeniem - dane wejściowe muszą być dopełnione do całej liczby 128-bitowych bloków przed połączeniem skrótu. Innymi słowy, zamiast hash (input) = hash (input + hash (input)) jak pierwotnie podano, mamy hash (input) = hash (input '+ hash (input)), gdzie input' jest po prostu wyściełanym wejściem. Mam nadzieję, że nie jest to zbyt uciążliwe.

Answer 5

Tak, można uzyskać ten efekt za pomocą CRC.

Co trzeba zrobić, to:

1. Wdrożenie algorytm, który znajdzie sekwencję bitów wejściowych N wiodących z danego państwa (z N-bit CRC akumulatora) do drugiego.
2. Obliczyć CRC sygnału wejściowego w normalny sposób. Zwróć uwagę na stan końcowy (nazwij go A):
3. Za pomocą funkcji zaimplementowanej w (1) znajdź sekwencję bitów, która prowadzi od A do A. Ta sekwencja jest twoim hashem. Możesz teraz dołączyć ją do wejścia.

[Initial state] >- input string -> [A] >- hash -> [A] ... 

Here is one way to find the hash. (Uwaga: wystąpił błąd w liczbach w przykładzie CRC32, ale algorytm działa.)

A oto implementacja w języku Java. Uwaga: Użyłem 32-bitowego CRC (mniejszego niż określone przez ciebie 64), ponieważ zostało to zaimplementowane w standardowej bibliotece, ale dzięki kodowi biblioteki innej firmy możesz z łatwością rozszerzyć go na większe skróty.

public static byte[] hash(byte[] input) { 
    CRC32 crc = new CRC32(); 
    crc.update(input); 
    int reg = ~ (int) crc.getValue(); 
    return delta(reg, reg); 
} 

public static void main(String[] args) { 
    byte[] prefix = "Hello, World!".getBytes(Charsets.UTF_8); 

    System.err.printf("%s => %s%n", Arrays.toString(prefix), Arrays.toString(hash(prefix))); 

    byte[] suffix = hash(prefix); 
    byte[] combined = ArrayUtils.addAll(prefix, suffix); 

    System.err.printf("%s => %s%n", Arrays.toString(combined), Arrays.toString(hash(combined))); 
} 

private static byte[] delta(int from, int to) { 
    ByteBuffer buf = ByteBuffer.allocate(8); 
    buf.order(ByteOrder.LITTLE_ENDIAN); 
    buf.putInt(from); 
    buf.putInt(to); 
    for (int i = 8; i-- > 4;) { 
     int e = CRCINVINDEX[buf.get(i) & 0xff]; 
     buf.putInt(i - 3, buf.getInt(i - 3)^CRC32TAB[e]); 
     buf.put(i - 4, (byte) (e^buf.get(i - 4))); 
    } 
    return Arrays.copyOfRange(buf.array(), 0, 4); 
} 
private static final int[] CRC32TAB = new int[0x100]; 
private static final int[] CRCINVINDEX = new int[0x100]; 
static { 
    CRC32 crc = new CRC32(); 
    for (int b = 0; b < 0x100; ++ b) { 
     crc.update(~b); 
     CRC32TAB[b] = 0xFF000000^(int) crc.getValue(); 
     CRCINVINDEX[CRC32TAB[b] >>> 24] = b; 
     crc.reset(); 
    } 
}