타임 스탬프 해싱은 어떻게 작동합니까?

Question

는 dont downvote my stupid question

지금이 같은이 해시에 타임 스탬프를 원래 문자열에서 생성 된 기존 해시 g84t5tw73y487tb38wo4bq8o34q384o7nfw3q434hqa이 있다고 가정 (에서 JS/의사 코드) :

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

var timestamped = hash + today; 

var new_hash = SHA256(timestamped); 

// new_hash is 34t346tf3847tr8qrot3r8q248rtbrq4brtqti4t 

내가 확인하고 싶었다면 내 원래 문자열은 내가 할 수있는 :

,369 :

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 있습니다. ith 타임 스탬프를 나타내려면 t[i]을 사용합니다. +는 문자열 연결을 의미

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

: 귀하의 반복 해싱은 점화식이다. 이제는 닫는 수식 F(x)이 있는지 확인하여 반복 관계 f(i)을 평가하는 것보다 시간 복잡성이 적은 ith 해시를 계산합니다.

이 작업을 수행하는 한 가지 방법은 f(t[i-1]) + t[i]과 동일한 해시를 사용하는 x(i) 문자열을 찾는 것입니다. 좋은 해싱 알고리즘의 경우 이러한 충돌은 매우 드뭅니다. 내 직감은 본문 (예 : f(t[i-1]) + t[i] 제외)을 찾는 것이 단순히 반복 관계에서 직접 계산하는 것보다 어렵다는 것입니다.