특정 해시 함수의 실용성

Question

다음 해시 함수를 고려하십시오.

$$(V\cdot A + V\cdot B)^2 \bmod C$$

$A, B,$ 과 $C$ 큰 소수입니다. $V$ 해시 할 값이며 적어도 가장 큰 소수만큼의 비트를 포함하도록 보장됩니다.

표면적으로 이것은 우수한 수준의 충돌 저항을 제공해야합니다.

이제 문제의 소수가 충분히 크다고 가정하면 그 반대를 계산하는 것은 불가능합니다. 옳은?

Answer 1

사각형을 볼 때 명백한 약점은

$$(a)^{2} = (-a)^{2},$$가능한 4 명의 후보로부터 메시지를 해결하기 위해 추가 메커니즘이 필요하기 때문에 Rabin Cryptosystem 에서는 문제가되지 않습니다 . 그러나 여기에서는 직접 충돌이 발생할 수 있습니다.

또한 fgrieu가 언급했듯이 Tonelli-Shanks 의 주요 사례에서는 제곱근 계산이 어렵지 않습니다 . 이 알고리즘은 소수에 대해 작동합니다.$p$및 일반화 를 위해$p^k$, 너무.

이제 문제의 소수가 충분히 크다고 가정하면 그 반대를 계산하는 것은 불가능합니다. 옳은?

취하다 $$h = (V\cdot A + V \cdot B)^2 = V^2(A+B)^2 \bmod C $$ 그래서 이유가 없습니다 $A$ 과 $B$소수가되기 위해. 키가있는 해시가 아니기 때문에 모든 값을 알아야합니다.$A,B,C$ 그때

$$V^2 = \frac{h}{(A+B)^2} \bmod C$$ 이것은 범위에 두 가지 솔루션이 있습니다 $[0,C{-1}]$ 무한히 많은 솔루션을 $\mathbf{Z}$. 처음 두 개는 Tonelli-Shank로, 나머지는 모듈 식 산술로 찾을 수 있습니다.

따라서 하나는 사전 이미지, 보조 사전 이미지 및 충돌을 매우 쉽게 찾을 수 있습니다. 사전 이미지 공격에서는 실제 값을 찾을 필요가 없습니다.$V$및 모든 값 $V'$ 주어진 해시 값을 생성하는 $h$ 이 공격이 성공하기에 충분합니다.

보안 해시 함수에 가깝지도 않습니다.