自反散列？

Question

是否有一個類的散列算法，無論是理論上或實用的，使得在類的算法中可能被認爲「反身」根據下面給出的定義：

• HASH1 = algo1（「輸入文本1」）
• HASH1 = algo1（ 「輸入文本1」 + HASH1）

+運算可能是級聯或任何其他指定的操作時的輸出（HASH1）合併回輸入（ 「輸入文本1」）這樣算法（algo1）將產生完全相同的結果。即在輸入和輸入+輸出上發生衝突。 +運算符必須組合兩個輸入的全部，並且算法可能不會丟棄部分輸入。

該算法必須在輸出中產生128位的熵。 它可能但不一定是加密難以將輸出反轉回一個或兩個可能的輸入。

我不是一個數學家，但一個好的答案可能包括證明爲什麼這樣一類算法不能存在。然而，這不是一個抽象的問題。如果真的存在，我真的很感興趣在我的系統中使用這樣的算法。

Answer 1

嗯，我可以告訴你，你不會得到一個不存在的證明。這裏有一個例子：

運算符+（a，b）：計算a的64位散列，b的64位散列，並連接位串，返回128位散列。

algo1：對於某些128位的值，忽略後64位，並計算第一64.

非正式的一些散列，其產生所述第一操作員+作爲它的第一個步驟將做任何algo1。也許不像你想找的那樣有趣，但它符合法案。而且它也不是沒有真實世界的實例。許多密碼散列算法會截斷其輸入。

Answer 2

我敢肯定，這種「自反散列」函數（如果確實存在的不僅僅是微不足道的意義）在正常意義上不是一個有用的散列函數。

對於「微不足道的」反身性的散列函數的例子：

int hash(Object obj) { return 0; } 

Answer 3

好的，這是一個很普通：

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

拼接的結果和「散列」不會改變。當你可以反轉散列時，想出類似的東西很容易。

Answer 4

大廈ephemiat's answer，我覺得你可以做這樣的事情：

挑選自己喜歡的對稱密鑰塊密碼（例如：AES）。具體來說，假設它在128位塊上運行。對於給定的密鑰K，分別用Enc（K，block）和Dec（K，block）表示加密函數和解密函數，使得block = Dec（K，Enc（K，block））= Enc（K， Dec（K，塊））。

將您的輸入劃分爲128位塊的數組（根據需要填充）。您可以選擇一個固定的密鑰K或將其作爲散列輸入的一部分。在下面，我們假設它是固定的。

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)) 

該函數返回一個256位散列。應該不難驗證它是否滿足「反射性」條件，只有一個警告 - 在散列被連接之前，必須將輸入填充到整個128位塊。換句話說，我們有hash（input）= hash（input'+ hash（input）），而不是輸入''就是填充的輸入，而不是散列（輸入）=散列（輸入+散列（輸入））。我希望這不是太繁重。

Answer 5

是的，你可以用CRC得到這個效果。

你需要做的是：

1. 實現的算法，將找到一個給定的狀態（N位CRC累加器）到另一家領先的N個輸入比特序列。
2. 以正常方式計算輸入的CRC。注意最後的狀態（稱之爲A）
3. 使用（1）中實現的函數，找出從A到A的位的序列。這個序列就是你的哈希碼。您現在可以將其附加到輸入。

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

Here is one way to find the hash。 （注意：CRC32示例中的數字存在錯誤，但該算法有效。）

這裏是Java中的一個實現。注意：我使用了32位的CRC（小於你指定的64），因爲它是在標準庫中實現的，但是通過第三方庫代碼，你可以輕鬆地將它擴展到更大的散列值。

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(); 
    } 
}