매우 부드러운 해시

매우 부드러운 해시(VSH)
일반
디자이너	스콧 콘티니, 아르젠 K 론 스타인
초판	2005
후계자	VSH*
세부 사항
다이제스트 사이즈	1024비트 이상

암호학에서 VSH(Very Smooth Hash)는 Scott Continue,^[1] Arjen Lenstra 및 Ron Steinfeld에 의해 2005년에 발명된 안전한 암호 해시 함수입니다.'확실히 안전하다'는 것은 충돌을 찾는 것이 알려진 어려운 수학 문제만큼이나 어렵다는 것을 의미합니다.다른 안전한 충돌 방지 해시와는 달리 VSH는 효율적이며 실제로 사용할 수 있습니다.점근적으로 로그(n) 메시지비트당 1배만 필요하며 RSA 타입의 산술이 사용됩니다.따라서 VSH는 코드 공간이 제한된 임베디드 환경에서 유용합니다.

VSH의 두 가지 주요 변형이 제안되었다.예를 들어, 충돌을 찾는 것은 매우 매끄러운 수 모듈로 n의 중요하지 않은 모듈러 제곱근을 찾는 것만큼 어렵지 않을 수 없다.다른 하나는 소수 계수 p(트랩도어 없음)를 사용하며, 보안 증명은 매우 부드러운 수의 이산 로그를 찾는 경도에 의존합니다.두 버전 모두 효율이 비슷합니다.

VSH는 랜덤오라클 대체로는 적합하지 않지만 안전한 랜덤화 트랩도어 해시 함수를 구축하기 위해 사용할 수 있습니다.이 함수는 크레이머에서 사용되는 트랩도어 함수를 대체할 수 있습니다.검증 시간을 약 50% 단축하면서 입증 가능한 보안을 유지하는 Shoup 서명 스킴

VSN 및 VSSR

현재 널리 사용되는 모든 암호화 해시 함수는 어려운 수학 문제에 기초하지 않습니다.어려운 수학 문제 위에 구축된 이러한 몇 가지 함수는 입증할 수 있는 안전함수라고 불립니다.충돌을 찾는 것은 어려운 수학 문제를 푸는 것만큼 어려운 것으로 알려져 있다.Very Smooth Hash 함수의 기본 버전에서 이 어려운 문제는 특정 특수 번호(VSN)^[1]의 Modular Square Root(VSSR; 모듈라 제곱근)를 찾는 것입니다.이것은 정수를 인수분해하는 것만큼 어렵다고 가정합니다.

고정 상수 c 및 n의 경우, 최대 소수인 m이 최대(log n)^c일 경우 정수 m은 매우 부드러운 수(VSN)이다.

정수 b는 bs 인수분해에서 최대 소수가 최대(^clog n)이고 b $b\equiv x^{2}\mod n$ x $b\equiv x^{2}\mod n$ $b\equiv x^{2}\mod n$ n $b\equiv x^{2}\mod n$ \ $display style$ b \ $equiv$ x $^{2}$ \ $mod$ n $b\equiv x^{2}\mod n$ 인 정수 x가 존재하는 경우 매우 부드러운 2차 잔차 n이다.정수 x는 b의 모듈러 제곱근이라고 합니다.

우리는 단순하지 않은 제곱근에만 관심이 있다. 여기서²² x n n이면, 루트는 실제 필드와 같은 특성 0의 필드의 알고리즘을 사용하여 쉽게 계산할 수 있다.따라서 암호화 프리미티브에는 적합하지 않습니다.

Very Smooth Nontrival Modular Square Root(VSSR; 매우 스무스한 번호의 Nontrival Modular Square Root)는 다음 문제입니다.n을 거의 같은 크기의 알 수 없는 2개의 소수점 곱으로 하고 k $k\leq (\log n)^{c}$ ( $k\leq (\log n)^{c}$ n ) $k\leq (\log n)^{c}$ {\ $display$ $style$ k $\leq$ ( \ $log$ n )^{ $c$ $k\leq (\log n)^{c}$ $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ 1 $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ , $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ p $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ , $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ , { $display$ p $_$ {1} $= 2$ , $p_2$ } = $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ 3, $p_{$ 3 } = 3 $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ = 3 = 3 } , 5 $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ $}$ 5 } 5 、 5 。VSSR은 다음 문제입니다.n이 주어졌을 때 $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ $x\in \mathbb {Z} _{n}^{*}$ Z n $∗$ \ $displaystyle$ x \ $in$ $x\in \mathbb {Z} _{n}^{*}$ \ $mathbb$ { $Z } _$ { $n$ } { { n } such $x\in \mathbb {Z} _{n}^{*}$ x 2 $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ i $= 0$ $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ i i i $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ \ $displaystyle x^{2}$ \ $equiv$ \ $eqiv$ \ { $i$ } { i } { $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ i_k } { i at₀ } at $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ at at at at at at at at at at at at at at odd odd given given given x x x $given$ given $x\in \mathbb {Z} _{n}^{*}$

VSSR의 가정에서는 확률론적 다항식 $\log n$ 에 $)$ n\ $displaystyle\$ log $n$ 의 시간 알고리즘이 존재하지 않는 것이 전제입니다.이는 계산상 어려운 모듈리 VSSR의 크기를 알 수 없기 때문에 연습에 도움이 되지 않는 가정으로 간주됩니다.대신 계산 VSSR 가정이 사용됩니다.VSSR의 해결은 $s$ 가 어려운 s $(\displaystyle$ s $)$ 비트계수를 $s$ 고려하는 것만큼 어렵다고 가정합니다. $s$ 서 s $(\displaystyle$ s $)$ 는 $s$ $(\displaystyle$ n $n$ 크기보다 다소 작습니다.

VSN 및 VSSR의 예

$c=5$ 는 c $n=31$ $({displaystyle$ $n=31$ $=5})$ $n=31$ n = $31$ ({ $displaystyle$ n $=31$ 로 고정합니다.

$(\log 31)^{5}~{\dot {=}}~7.37$ 1 $m_{1}=35=5\cdot 7$ $m_{1}=35=5\cdot 7$ $=$ $m_{1}=35=5\cdot 7$ $m_{1}=35=5\cdot 7$ 7 { $displaystyle m_{1$ } = $35$ = 5 \ $cdot$ 7 $m_{1}=35=5\cdot 7$ } $(\log 31)^{5}~{\dot {=}}~7.37$ 、 5 $(\log 31)^{5}~{\dot {=}}~7.37$ 7. $(\log 31)^{5}~{\dot {=}}~7.37$ ${$ $display style$ ( \ $log$ 31 $(\log 31)^{5}~{\dot {=}}~7.37$ )^ $5$ 37 { \ dot { \ $dot$ { =} ~ $7$ } } $m_{1}$ 37 $(\log 31)^{5}~{\dot {=}}~7.37$ 1 $37$ 7 $37$ 7 37 7 37 7 37 7 37 7 37 7 37 7 377 371 $m_{1}$ 。한편, $m_{2}=55=5\cdot 11$ $m_{2}=55=5\cdot 11$ $m_{2}=55=5\cdot 11$ $m_{2}=55=5\cdot 11$ 5 $m_{2}=55=5\cdot 11$ 11 { $displaystyle m_{2$ } = $55$ = $m_{2}=55=5\cdot 11$ 5 \ $cdot$ 11 }은 $m_2 = 55 = 5\cdot 11$ $c=5$ c $=$ $c=5$ { $displaystyle$ c $= 5$ } 및 $n=31$ $n=31$ $n=31$ { $displaystyle$ n= $31$ 에서 VSN이 아닙니다.

$b_{1}=9$ $b_{1}=9$ $=$ $b_{1}=9$ { $style b_{1$ }= $9}$ 은 $b_1 = 9$ $n$ (는 $)$ 매우 부드러운 숫자 $($ $c$ , n {\ $displaystyle$ c $, n$ $아래$ )이며 x 1 $=$ $x_{1}=3$ { $display x_{1$ }= $3$ $($ $x_{1}^{2}=b_{1}$ $x_{1}^{2}=b_{1}$ $=$ $x_{1}^{2}=b_{1}$ 1 $display x_2)$ 이므로 매우 부드러운 2차 잔여 $n$ 입니다. $tyle$ n $}$ 입니다. $3^{2}\not \geq n$ µn \ $displaystyle$ 3 $^{2}\not \geq$ n이므로 $3^{2}\not \geq n$ 제곱 시 계수는 관여하지 않기 때문에 이것은 단순한 모듈러 제곱근입니다.

$b_{2}=15$ $b_{2}=15$ 2 $=$ $b_{2}=15$ ${$ $displaystyle$ b_ ${$ 2}= $15$ $20^{2}=400\equiv 15$ 도 $b_2 = 15$ 매우 부드러운 2차 잔차 $n$ 입니다 $.$ 모든 소인수는 7.37보다 작으며 모듈러 $x_{2}=20$ 은 $20^{2}=400\equiv 15$ $x_{2}=20$ $=$ $20^{2}=400\equiv 15$ 이므로 $x_2 = 20$ x 2 $x_{2}=20$ $20^{2}=400\equiv 15$ { $displaystyle$ $x_$ {2} $=$ $20$ $20^{2}=400\equiv 15$ ${\$ 15 $= 15 equiv$ $n$ 따라서 이것은 단순한 루트가 아닙니다.VSSR의 문제는 $({$ 와 $b_{2}$ n({ $displaystyle$ n $n$ 에서 $({$ })를 $x_{2}$ $x_{2}$ 것입니다.이 문제는 계산상으로는 n $({displaystyle$ n $n$ 을 $n$ 하는 것만큼 어렵다고 생각됩니다.

VSH 알고리즘, 기본 버전

$(\displaystyle$ n $)$ 을 $n$ 큰 RSA 복합체로 하고 $p_{1}=2,p_{2}=3,\ldots$ $p_{1}=2,p_{2}=3,\ldots$ , $p_{1}=2,p_{2}=3,\ldots$ $p_{1}=2,p_{2}=3,\ldots$ $...$ { displaystyle $p_{1$ } $= 2$ , $p_{2} =$ 3, \ldots $p_{1}=2,p_{2}=3,\ldots$ $}$ 을(를) 소수 시퀀스로 합니다.k{k\displaystyle}, 블록 길이, 가장 큰 정수자는 나는 나는 < 1kp/&n{\displaystyle\textstyle \prod_{i=1}^{k}p_{나는}<, n} 할게. m{m\displaystyle}ℓ{\displaystyle \ell}-bit 메시지비트로 구성된 데이터를 해시할 정도(m1,…, mℓ){\displaystyle(m_{1},\l ∏.점 $, m_$ $\ell <2^{k}$ < $\ell <2^{k}$ k \ $displaystyle \ell$ < $2$ ^ { $k$ $。$ m { \ $displaystyle$ m $m$ 의 해시를 계산하려면:

x₀ = 1
l $(\displaystyle$ l $/k$ $l/k$ 의 최소 정수인L(\ $displaystyle$ L $L$ 을 블록 수로 $합니다$ .l $l<i\leq Lk$ < $l<i\leq Lk$ $l<i\leq Lk$ $k$ 의 경우 $l<i\leq Lk$ $m_{i}=0$ $0$ { $displaystyle$ $m$ _ { $i$ $l<i\leq Lk$ } $l<i\leq Lk$ $= 0$ 으로 $m_{i}=0$ $m_{i}=0$ .
$\ell _{i}\in \{0,1\}$ $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ i $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ $i$ $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ - $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ 1 ( \ $displaystyle$ \ $textstyle$ \ ell = \ $sum$ _ { i $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ = $\ell _{i}\in \{0,1\}$ $}^{$ k $} l$ $\ell _{i}\in \{0,1\}$ { $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ $i$ - 1 $\ell _{i}\in \{0,1\}$ ^ { i - 1 } ^{ i - 1 } ^ { i - 1 $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ } ^ { i - 1 } } { $\ell$ 、 { i-1 $}$ { $displaystystyl$ _ displaystyl _ displaystyl _ $display$ $\ell _{i}\in \{0,1\}$ style } $the$ the $}$ the the the $the$ $1\leq i\leq k$ - $1\leq i\leq k$ - $1\leq i\leq k$ ( $displaystyle$ 1 \ $leq$ i \ $leq$ k $1\leq i\leq k$ )
j = 0, 1, ... L을 연속적으로 $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ j + $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ $=$ $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ j 2 $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ $=$ $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ i $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ + $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$ n { $display$ x _ ${$ j + 1 } = $x$ _ { $j$ }^{ $k } p _$ { $i$ }^{ $k$ + $i$ } \ $mod$ n
x를_{L + 1} 반환한다.

4단계의 함수를 압축함수라고 합니다.

VSH 속성

메시지 길이를 미리 알 필요는 없습니다.
VSH에서의 충돌 검출은 VSSR 해결만큼이나 어렵습니다.따라서 VSH는 (강력하게) 충돌에 대한 내성이며, 이는 두 번째 프리이미지 저항도 의미합니다.VSH는 초기 이미지에 대한 내성이 검증되지 않았습니다.
압축 기능은 충돌 방지 기능이 아닙니다.단, 해시함수 VSH는 VSSR의 가정에 따라 충돌에 대한 내성이 있습니다.VSH*라고 불리는 VSH의 변경된 버전은 충돌 방지 압축 기능을 사용하여 짧은 메시지를 해시할 때 약 5배 더 빠릅니다.
VSH의 출력 길이는 시큐어 RSA 계수의 길이이기 때문에 VSH는 실제로는 임의의 긴 메시지에 대해 "해시 후 서명" RSA 시그니처를 구축하는 데 매우 적합합니다.단, 이러한 시그니처는 보안을 확보하기 위해 신중하게 설계되어야 합니다.CPA(Chosen-Plaintext 공격)에서는 순진한 접근법이 쉽게 깨질 수 있습니다.
효율성:각 반복의 비용은 3개의 모듈식 곱셈 비용보다 작습니다.VSH의 기본 버전에서는 모두 D $\Omega (\log n/\log \log n)$ ( $\Omega (\log n/\log \log n)$ $\Omega (\log n/\log \log n)$ / $\Omega (\log n/\log \log n)$ " $\Omega (\log n/\log \log n)$ log $\Omega (\log n/\log \log n)$ " $\Omega (\log n/\log \log n)$ $)\displaystyle$ \Omega $(\log$ n $/\log \log$ n $)}$ 메시지 $\Omega (\log n/\log \log n)$ 비트당 단일 곱셈이 필요합니다.

VSH의 종류

몇 가지 개선점, 속도 향상 및 보다 효율적인 VSH 변형이 ^[1]제안되었습니다.그 중 어느 것도 함수의 기본 개념을 바꾸지 않습니다.이러한 개선을 다음과 같이 부릅니다.

큐빙 VSH(스쿼어링 대신)
작은 소수점 수가 증가한 VSH.
미리 계산된 소수점 제품이 포함된 VSH.
고속 VSH
블록 길이가 늘어난 고속 VSH

VSDL 및 VSH-DL 배리언트

VSH-DL은 트랩도어가 없는 VSH의 이산 로그 변종이며, 그 보안성은 이산 로그 모듈로 소수 ^[1]p를 찾는 것의 난이도에 따라 달라집니다.

VSDL(Very Smooth Number Discrete Loggm)은 매우 부드러운 숫자가 주어지면 어떤 숫자 n에 대한 이산 로그 모듈을 찾는 문제입니다.

이전 섹션과 마찬가지로 $(\$ })로 $p_{i}$ i $(\displaystyle$ i $)$ -번째 $i$ 소수를 $나타냅니다$ . $또한$ c $(\displaystyle$ c $)$ 가 $c$ 고정 $p$ 이고p(\ $displaystyle$ p $p$ p $(\displaystyle$ q $p=2q+1$ 가 $q$ $p=2q+1$ $=$ 2 $q$ + 1 $(\$ $displaystyle$ p $)$ $k\leq (\log p)^{c}$ c $display$ $p$ 인 $p = 2q + 1$ 소수점에서는 VSDL이 $e_{1},...,e_{k}$ 과 같습니다 $.$ ..., ek{\displaystyle e_{1},...,e_{k}} 같은 2e1≡ ∏ 나는 정도 2kp나는 에 들어간다면 나는 mod p{\displaystyle 2^{e_{1}}\equiv \prod _{i=2}^{k}p_{나는}^{e_{나는}}\mod p}과 ei<, q{\displaystyle e_{나는}<>q}에 i=1,..., k{\displaystyle i=1,...,k}과 적어도 한명의 e1.,. $e_{1},...,e_{k}$ $e_{1},...,e_{k}$ $(\$ 는 $e_1,...,e_k$ 0이 아닙니다 $e_{1},...,e_{k}$

VSDL의 가정은 VSDL을 비필수 확률로 해결하는 확률론적 다항식(로그 $\log p$ \ $displaystyle \log$ p $\log p$ 시간 알고리즘이 없다는 것입니다.VSDL의 경도와 이산 로그 모듈로 $p$ (\ $style$ p $p$ 계산의 경도 사이에는 강한 연관성이 있으며, 이는 VSSR과 정수 인수분해 사이의 연관성을 연상시키지만 다소 약합니다.

VSH 보안

강력한 충돌 저항성은 VSH에 대해 검증된 유일한 특성입니다.이는 preimage-resistance나 기타 중요한 해시함수 속성을 의미하는 것은 아니며, 작성자는 "VSH를 랜덤오라클 모델링에 사용해서는 안 된다"고 기술하고 있으며, 이에 의존하는 구성(RSA 시그니처, 일부 MAC)^[1]으로 대체할 수 없습니다.VSH는 보안 엔지니어링에서 일반적으로 이해되는 범용 해시 함수로 간주해서는 안 됩니다.

곱셈 특성

VSH는 곱셈입니다.x, y 및 z는 길이가 같은 3비트 문자열입니다.여기서 z는 0비트로만 구성되며 문자열은 x AND y = z를 만족합니다.H(z)H(x OR y) h H(x)H(y)(mod n)라는 것을 쉽게 알 수 있습니다.그 결과 VSH는 곱셈 해시 및 가산 해시에 적용되는 전형적인 타임메모리 트레이드오프 공격에 굴복합니다.

이 사실은 예상대로 2 $2^{\ell }$ {\(\ $displaystyle$ 2 $^{\ell})$ 가 $2^{\ell }$ $2^{\ell }$ $2^{\ell /2}$ $2^{\ell /2}$ / $2^{\ell /2}$ (\ $displaystyle$ 2 $^{\ell /2})$ 의 $\ell$ $2^{\ell/2}$ 복잡성을 갖는 ${\(\displaystyle \ell)$ 의 VSH에 대한 프리이미지 공격을 구성하기 위해 사용할 수 있습니다.

잘린 버전에 대한 공격

VSH는 매우 긴 해시(일반적으로 1024비트)를 생성합니다.잘린 VSH 해시가 해시 길이에 비례하는 보안을 제공한다는 징후는 없습니다.

최하위 l비트로 ^[2]잘린 VSH 부분 충돌 공격이 존재합니다.

VSH에 대한 이 공격의 복잡성은 다음과 같습니다.

테이블을 오프라인으로 사전 계산: $2^{\ell /3}$ / 3 $($ 2 $^{\ell /3})$ 시공간 $2^{\ell /3}$
$2^{\ell /3}$ 발견: $2^{\ell /3}$ / $($ 2 $^{\ell/3})$ 반복 $2^{\ell /3}$ .
총비용: 의사난수 특성이 양호한 해시함수에서 예상대로 2 $2^{\ell /2}$ 4 $/$ 가 $2^{\ell /2}$ $2^{\ell /3}$ 2/ $3({$ $displaystyle 2^{\ell$ / $3})$ 입니다 $2^{\ell/2}$ .

이로 인해 타원곡선 시그니처 방식 등 VSH 해시 결과보다 짧은 시그니처를 생성하는 디지털시그니처 방식에서의 VSH 적용 가능성은 배제될 수 있습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b ^c ^d ^e Contini, S.; Lenstra, A.; Steinfeld, R. (2005-06-23), VSH, an Efficient and Provable Collision-Resistant Hash Function.
^ Saarinen, M.-J. O. (2006), Security of VSH in the real world (PDF), doi:10.1007/11941378_8{{citation}}: CS1 maint :url-status (링크)

[main-1] Contini, S.; Lenstra, A.; Steinfeld, R. (2005-06-23), VSH, an Efficient and Provable Collision-Resistant Hash Function.

[attack-2] Saarinen, M.-J. O. (2006), Security of VSH in the real world (PDF), doi:10.1007/11941378_8{{citation}}: CS1 maint :url-status (링크)

[1]

[2]

Search

매우 부드러운 해시

네임스페이스

더

목차