encryption - 时间戳哈希如何工作？

Question

假设您有一个现有的散列 g84t5tw73y487tb38wo4bq8o34q384o7nfw3q434hqa这是从原始字符串 dont downvote my stupid question 创建的

现在我像这样(在 JS/伪代码中)为这个散列加上时间戳:

var hash = 'g84t5tw73y487tb38wo4bq8o34q384o7nfw3q434hqa';
var today= new Date(); // 2017-10-19

var timestamped = hash + today; 

var new_hash = SHA256(timestamped); 

// new_hash is 34t346tf3847tr8qrot3r8q248rtbrq4brtqti4t

如果我想验证我的原始字符串，我可以这样做:

var verified = goodHash('dont downvote my stupid question',hash); // true

如果我想验证带时间戳的版本，我可以这样做:

var original_hash = 'g84t5tw73y487tb38wo4bq8o34q384o7nfw3q434hqa';
var today = '2017-10-19';
var verified = goodHash(original_hash+today, timestamped_hash); // true

但是如果我试图根据时间戳验证原始字符串，我不能这样做:

var today = '2017-10-19';
var verified = goodHash('dont downvote my stupid question'+today, timestamped_hash); // FALSE

现在假设这个原始字符串为 n 一遍又一遍地散列和加时间戳迭代。

我只能验证 n-1th时间戳，前提是我有 n-1th哈希。

但是如果我有原始字符串 dont downvote my stupid question 怎么办？并想验证任何 ith时间戳，其中 0 < i < n .

基本上，我想验证一个只有我应该知道的字符串是否已经用给定日期加了时间戳，而不管它可能已经加了多少次时间戳和而不增加长度字符串的长度(太多了 - 虽然 任何 长度的增加都会随着 n 的增长而接近无穷大)。

这可能吗？哈希甚至可以包含所有这些信息吗？

Answer 1

让我们看看这里涉及的数学:

首先，您有一个输入字符串 s 和一个时间戳序列 t。我将使用 t[i] 来表示第 ith<​​ 时间戳。您的重复散列是递归关系:

f(i) = hash(f(t[i-1]) + t[i])

其中 + 表示字符串连接。现在我们要确定是否存在一个闭合公式 F(x)，它将计算 ith<​​ 哈希，其时间复杂度低于评估递归关系 f( i).

实现此目的的一种方法是找到与 f(t[i-1]) + t[i] 具有相同散列的字符串 x(i) .对于一个好的散列算法，这些冲突是极其罕见的。我的直觉是找到这样的字符串(f(t[i-1]) + t[i] 本身除外)比直接从递归关系直接计算更困难。