將48位密鑰散列成16位值

我正在處理接收非常小的數據包的設備。設備由48位密鑰唯一標識。當設備收到單個數據包時，它需要讀取數據包並確定數據包是否適用於該設備。聽起來很簡單，但數據包只有一個16位密鑰足夠的空間。將48位密鑰散列成16位值

通信協議無法更改。我無法使用數據包中的多個數據包或其他字段。基本上我需要將這個48位標識符存儲在一個16位的字段中。很明顯，任何解決方案都會發生衝突。

我正在考慮發送原始密鑰的低16位或散列它。最大限度地減少碰撞的方法是什麼？

PS：實際上它看起來像原來的密鑰的前三個字節總是相同的，所以這個問題已經減少到推出一個16位密鑰的24位密鑰，但仍然非常糟糕。

PPS：碰撞不是災難性的。該設備可以恢復，但價格昂貴。

來源

2013-11-27 vopilif

「*在最小化碰撞的情況下做到這一點的最佳方式是什麼？*」如果不知道所使用值的分配和分配情況，這是無法回答的。 – RBarryYoung

如果私鑰是隨機生成的，那麼對它們進行哈希處理將不會比獲取16位小節更少的衝突。如果問題很重要，最好不要弄錯鑰匙。 –

單個設備是否可編程？你可以配置設備來告訴它它的16位密鑰是什麼？如果您事先知道所有設備ID，則可以創建[最小完美散列]（http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function）。但是，如果沒有某種方法告訴設備尋找特定的數據包號碼，碰撞的可能性將不爲零。 –

向製造商詢問此號碼生成中的任何模式。這24位數據中的一部分很可能確定了生產批次或世界部分需要運送到哪個位置，這使得它們成爲裁剪的主要候選對象。

在請求中明確指出您知道並接受他們可以隨時更改編號政策，恕不另行通知。這應該使他們更有可能提供信息。

來源

2013-11-27 12:32:39

在這種情況下唯一可以幫助你的是如果你的設備小於或等於2^16。在這裏您需要有散列表，它將每個24-bit密鑰映射到獨特的密鑰16-bit。所以在發送數據包的同時發送16-bit密鑰，同時檢索散列表中的密鑰映射值檢查。您也可以硬編碼16-bit的關鍵值進行直接比較。但是，如果您有超過2^16個設備，那麼根據鴿子洞原則，您將擁有2個或更多具有相同16-bit密鑰的設備，那麼您無法確定該數據包適用於哪個設備。

的僞碼發送&接收數據包： -

Send(BigKey,Data) { 

    // get 16-bit key from 24-bit one 
    SmallKey = HashMap.getValue(BigKey); 
    Packet = SmallKey + Data ; 

} 

Receive(Packet) { 

    (Key,Data) = split(Packet); 

    // get devices 16-bit key 
    SmallKey = HashMap.getValue(MyKey); 

    if(SmallKey==Key) 
     Process(Data) 
    else Error("Invalid Packet"); 

}

注： - 哈希表可以使用紅黑樹，B樹等，這些都在O（LOGN）查找創建。這對您的應用程序來說已經足夠了。

來源

2013-11-27 05:51:03

將48位密鑰散列成16位值

回答

相關問題