加密散列元素樹

我正在一個項目中，我有一棵樹的對象。這個對象樹可能非常大，並且可能會受到更多用戶的頻繁修改（例如添加或刪除節點，更改節點的某些屬性等）。現在，每次用戶發佈更新時，我都需要能夠獲得該樹的散列，因爲它是在用戶修改它之後進行的，因此用戶可以使用他的私有RSA密鑰來簽署更新。所以我顯然需要哈希來保密。但是，每當用戶只更改一個節點時，一次又一次散列整棵樹的線性表示是不可行的。加密散列元素樹

我考慮這一策略，但我不知道是否會制定出正確：

我添加到一個新的領域的每一個節點，那就是它的所有子節點的SHA256哈希值。
節點的散列現在是節點的每個字段的散列，因此包括其子節點的散列。現在

，更新樹應該很容易：每次我更新節點的時候，我改變其父的哈希領域，那麼它的祖父母等，直至達到根，並使用根的哈希作爲散列值。這會將此操作的複雜度降低到O（ln（N））而不是O（N）。

但是，我知道信任自己對密碼學的直覺是不安全的。那麼這個過程是否安全？

來源

2015-07-20 Matteo Monti

就你的解釋而言，它似乎是相當可靠的。但是，您如何生成葉節點的散列？節點彼此之間是否充分「不同」，以致它們的哈希將分佈得很好？例如，如果您的節點是3D座標，並且大多數點趨於接近原點，則可能會遇到足夠分佈的問題。另外，你如何結合葉節點哈希來形成父節點哈希？ –

這聽起來像你已經深入實施完全自定義的加密，這是很可能以某種方式打破。爲什麼「顯而易見」你需要一個密碼安全的哈希值來加密簽名？爲什麼對樹進行哈希是不可行的？你確定你正在避免'延長'問題嗎？等等 – pvg

@EricJ。我必須考慮如何散列葉節點。但是，每個節點都是完全不同的。它們是永不重複的長序列字節。 –

這被稱爲hash tree or Merkle tree。這不是什麼新鮮事物，它是安全的。它通常用於並行散列，因爲散列方法本身在本質上是嚴格順序的。

不要連接數據和散列，除非明確包含數據的大小。最好只連接散列。

來源

2015-07-20 21:33:37

在我看來你的算法已經足夠好了。假設SHA-256是安全的（至少，其名稱是「安全哈希算法」），可以通過歸納樹的深度來證明您的算法也是安全的。

來源

2015-07-20 20:34:36 WhatsUp

我同意。數據是數據。 – erickson

加密散列元素樹

回答

相關問題