NTRUEncrypt

NTRU 암호화 알고리즘으로도 알려진 NTRUncrypt 공용 키 암호 시스템은 RSA 및 타원 곡선 암호학(ECC)에 대한 NTRU 격자 기반 대안이며, 격자 내 최단 벡터 문제(양자 컴퓨터를 사용하여 파괴할 수 있는 것으로 알려져 있지 않음)에 기초한다.

잘린 다항식 링의 특정 다항식을 계수가 매우 작은 두 다항식의 인수로 인수하는 것은 추정된 어려움에 의존한다.암호체계를 깨는 것은 비록 등가는 아니지만, 특정 격자에서의 격자 감소라는 알고리즘 문제와 밀접한 관련이 있다.일부 공개된 공격을 좌절시키려면 매개 변수를 신중하게 선택해야 한다.

암호화와 암호 해독은 모두 단순한 다항식 곱셈만을 사용하기 때문에 이러한 작업은 RSA, ElGamal, 타원곡선 암호화와 같은 다른 비대칭 암호화 방식에 비해 매우 빠르다.그러나 NTRUEncrypt는 아직 전개된 형태로 비교 가능한 양의 암호 분석을 거치지 않았다.

관련 알고리즘은 NTRUSign 디지털 서명 알고리즘이다.

구체적으로 NTRU 연산은 잘린 다항 링 $\ R=\mathbb {Z} [X]/(X^{N}-1)$ = Z $\ R=\mathbb {Z} [X]/(X^{N}-1)$ [ $\ R=\mathbb {Z} [X]/(X^{N}-1)$ $\ R=\mathbb {Z} [X]/(X^{N}-1)$ / $\ R=\mathbb {Z} [X]/(X^{N}-1)$ ( $\ R=\mathbb {Z} [X]/(X^{N}-1)$ $\ R=\mathbb {Z} [X]/(X^{N}-1)$ - 1 $\ R=\mathbb {Z} [X]/(X^{N}-1)$ ) ${\displaystyle$ \ $R=\mathb {Z}[X]/(X^{N}-1)$ 에 있는 $\ R=\mathbb {Z} [X]/(X^{N}-1)$ 객체에 기초하며, 링에 있는 모든 다항은 최대 N-1:

{\textbf{a}}=a_{0}+a_{1}X^{1}X+a_{2}X^{2}+\cdots +a_{N-2}X^{N-2}A_{N-1}X^{N-1}}}}

NTRU는 실제로 암호 시스템의 매개 변수화된 제품군이며, 각 시스템은 잘린 링 R, 작은 계량 및 큰 계량에서 $\ N-1$ 도 N - $\ N-1$ ${\displaystyle$ \ $N-1}$ 을 $\ N-1$ 나타내는 세 개의 정수 매개변수(N, p, q)로 지정되며, N은 항상 primary라고 가정한다.p, and p and q are coprime; and four sets of polynomials $\ {\mathcal {L}}_{f},{\mathcal {L}}_{g},{\mathcal {L}}_{m}$ and $\ {\mathcal {L}}_{r}$ (a polynomial part of the private key, a polynomial for generation of the public key, the message and a블라인딩 값(각각), $\ N-1$ $\ N-1$ - 1 ${\displaystyle$ \ $N-1$

역사

NTRUEncrypt Public Key Crypt 시스템은 비교적 새로운 암호 시스템이다.단순히 NTRU라고 불렸던 이 시스템의 첫 번째 버전은 1996년경 세 명의 수학자(제프리 호프스타인, 질 피퍼, 조셉 H. 실버맨)에 의해 개발되었다.1996년 다니엘 리먼과 함께 이 수학자들은 NTRU 암호 시스템을 설립했고 암호 시스템에 대한 특허^[1](현재 만료됨)를 받았다.

지난 10년 동안 사람들은 암호체계를 향상시키기 위해 노력해왔다.암호 시스템의 첫 번째 제시 이후, 시스템의 성능과 보안 모두를 향상시키기 위해 몇 가지 변경이 이루어졌다.대부분의 성능 향상은 그 과정을 가속화하는 데 초점이 맞춰져 있었다.2005년까지 NTRUEncrypt의 암호 해독 실패를 설명하는 문헌을 찾을 수 있다.보안에 대해서는, NTRUEncrypt의 첫 번째 버전부터, 현재 알려진 모든 공격에 대해 안전해 보이는 새로운 파라미터가 도입되어, 연산력의 합리적인 증가가 이루어지고 있다.

이제 시스템은 격자 기반 공개키 암호화에 대한 규격(IEEE P1363.1)에 따라 IEEE P1363 표준에 완전히 수용된다.NTRUEncrypt Public Key 암호 시스템의 속도(벤치마킹 결과는 http://bench.cr.yp.to 참조)와 메모리 사용량이 적기 때문에 모바일 기기나 스마트 카드 등의 애플리케이션에서 사용할 수 있다.^{[dubious – discuss]}2011년 4월, NTRUEncrypt는 금융 서비스 산업에서 사용하기 위해 X9.98 표준으로 채택되었다.^[2]

공개키 생성

앨리스가 밥에게 비밀 메시지를 보내려면 공개 키와 비공개 키의 생성이 필요하다.공개 키는 앨리스와 밥 둘 다에 의해 알려지고 비공개 키는 밥에 의해서만 알려진다.키 쌍을 생성하려면 최대 $\ N-1$ - $\ N-1$ ${\displaystyle$ \ $N-1}$ 과 $\ N-1$ (와) {-1,0,1}의 계수를 가진 두 개의 다항식 f와 g가 필요하다.그것들은 R에서 $\ X^N-1$ 다항식 modulo $\ X^{N}-1$ $\ X^{N}-1$ - 1 ${\displaystyle$ \ $X^{N}-1}$ 의 잔여 등급의 표현으로 간주할 수 있다.The polynomial ${\textbf {f}}\in L_{f}$ must satisfy the additional requirement that the inverses modulo q and modulo p (computed using the Euclidean algorithm) exist, which means that $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ and $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ = $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ ( $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ ) ${\$ 1{\ $pmod{q$ }}}}}}은(는) 보류되어야 한다 $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ .그래서 선택된 f가 돌이킬 수 없을 때, 밥은 돌아가서 다른 f를 시도해야 한다.

f와 $\ \mathbf {f} _{p}$ ${\$ {\ $displaystyle \mathbf {f} _{p}($ 및 $g$ ${\displaystyle g$ 모두 밥의 개인 키다.공개 키 h는 수량을 계산하여 생성된다.

{\textbf {h}=p{\textbf {f}_{q}\cdot {\textbf {g}{\pmod {q}}.

예:이 예에서 매개변수(N, p, q)는 N = 11, p = 3 및 q = 32의 값을 가지며, 따라서 다항식 f와 g는 최대 10의 도이다.시스템 매개변수(N, p, q)는 모든 사람에게 알려져 있다.다항식은 랜덤하게 선택되므로 다음과 같이 표현된다고 가정해 보십시오.

{\textbf{f}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}}}}

{\textbf{g}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}}}

유클리드 알고리즘을 사용하여 각각 f modulo p와 modulo q의 역이 계산된다.

{\textbf{f}_{p}=1+2X+2X^{3}+2X^{4}+X^{5}+2X^{7}+X^{8}+2X^{9}{\pmod{3}

{\textbf {f}}_{q}=5+9X+6X^{2}+16X^{3}+4X^{4}+15X^{5}+16X^{6}+22X^{7}+20X^{8}+18X^{9}+30X^{10}{\pmod {32}}

제품을 계산하는 공개 키 h(Alice와 Bob에게 모두 알려져 있음)가 생성됨

{\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {32}}=8-7X-10X^{2}-12X^{3}+12X^{4}-8X^{5}+15X^{6}-13X^{7}+12X^{8}-13X^{9}+16X^{10}{\pmod {32}}

암호화

밥에게 비밀 메시지를 보내고 싶은 앨리스는 자신의 $[-p/2,p/2]$ 를 $[-p/2,p/2]$ [ - p $[-p/2,p/2]$ / $[-p/2,p/2]$ , $[-p/2,p/2]$ / 2 $[-p/2,p/2]$ $[-p/2,p/2]$ 에 계수가 있는 다항식 m의 형태로 넣는다. $[-p/2,p/2]$ 암호화의 현대적 응용에서 다항식 메시지는 2진법이나 3진법으로 번역할 수 있다.다항식 메시지를 작성한 후 앨리스는 메시지를 모호하게 하기 위한 작은 계수({1,0,1} 집합으로 제한되지 않음)를 가진 다항식 r을 임의로 선택한다.

Bob의 공개 키 h로 암호화된 메시지 e를 계산한다.

{\textbf {e}={\textbf {r}\cdot {\textbf {h}+{\textbf {m}{\pmod{q}}}}

이 암호문은 앨리스의 메시지를 숨기고 밥에게 안전하게 보내질 수 있다.

예:앨리스가 다항식으로 쓸 수 있는 메시지를 보내고 싶어한다고 가정하자.

{\textbf{m}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}}}

그리고 무작위로 선택된 '블라인딩 값'은 다음과 같이 표현될 수 있다.

{\textbf {{r}=-1+X^{2}+X^{3}+X^{4}-X^{5}-X^{7}}

그녀의 암호화된 메시지를 나타내는 암호문이 밥에게 보내는 것처럼 보일 것이다.

{\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {32}}=14+11X+26X^{2}+24X^{3}+14X^{4}+16X^{5}+30X^{6}+7X^{7}+25X^{8}+6X^{9}+19X^{10}{\pmod {32}}

암호 해독

r을 아는 사람은 누구나 e - rh를 평가하여 메시지 m을 계산할 수 있으므로, r은 앨리스에 의해 밝혀져서는 안 된다.공개적으로 이용 가능한 정보 외에도, 밥은 자신의 개인 키를 알고 있다.그가 m을 얻는 방법은 다음과 같다: 첫째, 그는 암호화된 메시지 e와 그의 개인 키 f의 일부를 곱한다.

{\textbf {a}={\textbf {f}\cdot {\textbf {e}{\pmod{q}}}

다항식을 다시 쓰면서 이 방정식은 실제로 다음과 같은 계산을 나타낸다.

{\textbf {a}={\textbf {f}\cdot {\textbf {e}{\pmod{q}}}

{\textbf {a}={\textbf {f}\cdot({r}\textbf {h}+{\textbf {m}){\pmod {q}}}

{\textbf{a}}={\textbf {f}\cdot p{\textbf{f}_{q}\textbf{g}+{\textbf{m}}{\pmod{q}}}}}}}}

{\textbf {a}=p{\textbf {r}\cdot {\textbf {g}+{\textbf {m}{\pmod}}}}

0과 q – 1 사이의 계수를 선택하는 대신 [-q/2, q/2] 구간에 선택되어 앨리스가 메시지 m의 좌표를 [-p/2, p/2] 구간에 선택하므로 원본 메시지가 제대로 복구되지 않을 수 있다.This implies that all coefficients of $\ p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}$ already lie within the interval [-q/2, q/2] because the polynomials r, g, f and m and prime p all have coefficients that are small compared to q.이는 모든 계수가 modulo q를 줄이는 동안 변경되지 않고 그대로 남아 있고 원래의 메시지가 제대로 복구될 수 있다는 것을 의미한다.

다음 단계는 modulo p:

{\textbf{b}={\textbf {a}{\pmod}={\textbf {f}}\textbf {m}{\pmod}}}

$\ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0$ p $\ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0$ $\ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0$ g $\ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0$ ( $\ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0$ p $\ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0$ ) = 0 $\p{\textbf{r}\cdot{g}{\pmod}=0$ .

b Bob을 알면 개인 키의 다른 부분 $\ \left({\textbf {f}}_{p}\right)$ p $){\$ 을 $\ \left(\textbf{f}_p \right)$ 사용하여 $\ {\textbf {f}}_{p}$ 와 $\ {\textbf {f}}_{p}$ ${\$ {p $}}})$ 을 곱하여 앨리스의 메시지를 복구할 수 있다.

{\displaystyle{\textbf{c}={\textbf{f}_{p}}}}{\textbf{b}}}={\textbf{f}}\textbf{m}}}}}}}}}{\textbf {pmod{p}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}"

{\textbf{c}={\textbf {m}{\pmod{p}}

$\ {\textbf {f}}_{p}$ f $\ {\textbf {f}}_{p}$ $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ = $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ ( $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ ) ${\$ { $f}_{p}=1$ ${\pmod{p}}}}$ 이(가) 필요했기 $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ 때문이다 $\ {\textbf {f}}_{p}$

예:앨리스에서 Bob까지 암호화된 메시지 e에 다항식 f를 곱한다.

{\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {32}}=3-7X-10X^{2}-11X^{3}+10X^{4}+7X^{5}+6X^{6}+7X^{7}+5X^{8}-3X^{9}-7X^{10}{\pmod {32}},

여기서 밥은 다항식 a 계수에 대한 간격 [0, q – 1] 대신 [-q/2, q/2] 간격을 사용하여 원본 메시지가 올바르게 복구되지 않도록 한다.

mod p의 계수를 줄이면

{\displaystyle {\textbf{b}}={\pmod{3}=-X-X^{2}+X^{3}+X^{4}+X^{5}+X^{7}-X^{8}-X^{10}{\pmod{3}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}\pmod {\pmod {pmod {a

$\ {\textbf {b}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}$ = f $\ {\textbf {b}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}$ $\ {\textbf {b}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}$ ) ${\$

마지막 단계에서 결과는 $\ {\textbf {f}}_{p}$ 의 개인 키에서 $\ {\textbf {f}}_{p}$ $\ {\textbf {f}}_{p}$ ${\$ 로 곱하여 원래 메시지 m으로 끝난다.

{\displaystyle{\textbf{c}}={\textbf{f}_{p}}}{\textbf{f}}{p}}\textbf {f}}\textbf {m}}}{\pmod{3}}={\textbf{{m}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

{\textbf {{c}=-1+X^{3}-X^{4}-X^{8}+X^{9}+X^{10}}}

그게 바로 앨리스가 밥에게 보낸 원래의 메시지야!

공격

NTRU의 제안 이후 NTRUncrypt 공개 키 암호 시스템에 대한 공격이 여러 차례 도입되었다.대부분의 공격은 메시지 m을 단순히 복구하는 대신 비밀키 f를 찾아 총체적 돌파에 초점이 맞춰져 있다.만약 f가 0이 아닌 계수가 거의 없는 것으로 알려지면, 이브는 f에 대한 모든 값을 시도함으로써 성공적으로 짐승의 힘 공격을 할 수 있다.이브는 f'가 비밀키인지 알고 싶을 때 $\ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}$ ′ $\ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}$ $\ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}$ ( $\ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}$ $){\$ 단순히 f ′ \ \ \ \ \ \ \ \를 계산한다 $\ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}$ 또한 이브는 $\ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}$ 의 값을 시도하여 g $\ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}$ - 1 $\ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}$ $\ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}$ ) ${\$ { $h}}^{1}{\pmod{q}}}}}$ 의 값이 $\ {\textbf {g}}'\cdot {\textbf {h}}^{-1}{\pmod {q}}$ 작은지 여부를 테스트할 수 있다.

더 강력한 중전공격이 가능하다.제곱근으로 검색 시간을 단축할 수 있다.공격은 $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$ $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$ $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$ = $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$ $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$ ( $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$ $){\$ {q $}}}}}}}}}$ 라는 속성을 기반으로 한다 $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$

$\ {\textbf {f}}_{1}$ 는 $\ \textbf{f}_2$ $\ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}$ = $\ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}$ $\ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}$ + f $\ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}$ ${\textbf$ ${f}$ $_$ ${1$ }, $\ {\textbf {f}}_{2}$ $\ {\textbf {f}}_{2}$ ${\$ $displaystyle \{\$ $textbf{f}}}{\$ textbf { $f}={\textbf{f}}}+{$ 1}{ $f}_$ }}}}}}}}}}}}}}}}}}}}}}}}}}}}}{{{{{{{{{{{{2 $}}:}}}}}$

\left\textbf {f}_{1}+{\textbf {f}_{2}\오른쪽)\cdot {\textbf {h}={\textbf{g}{\pmod{q}}}}}}

{\textbf{f}_{1}\cdot {\textbf {h}={\textbf {g}-{\textbf{f}}\cdot{\textbf{h}{\pmod}}}}}}}

If f has d one's and N-d zero's, then Eve creates all possible $\ {\textbf {f}}_{1}$ and $\ {\textbf {f}}_{2}$ in which they both have length $\ {\frac {1}{2}}N$ (e.g. $\ {\textbf {f}}_{1}$ covers the $\ {\frac {1}{2}}N$ $\ {\frac {1}{2}}N$ 1 $\ {\frac {1}{2}}N$ $\ {\frac {1}{2}}N$ $\{1}{2}}N$ d/2로 f 및 f $\ {\textbf {f}}_{2}$ 의 가장 낮은 $\ {\frac {1}{2}}N$ 계수 ${\$ 가장 $\ {\textbf {f}}_{2}$ 높음)그런 다음 ${\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}$ 는 ${\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}$ f $\ {\textbf {f}}_{1}$ ${\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}$ $⋅$ h ${\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}$ ( ${\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}$ $){\$ $displaystyle$ ${\textbf{f}_{1}\cdot {\textbf{$ $h}{\textbf{pmod{q}}}}$ 를 $\textbf{f}_1 \cdot \textbf{h} \pmod q$ 계산하고 $\ {\textbf {f}}_{1}$ 첫 번째 k 좌표를 기준으로 빈으로 주문한다.그 후 그녀는 모든 $\ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ - $\ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ $\ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ ⋅ h $\ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ ( $\ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ $\ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ ) ${\$ 을 계산하고 $\ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$ 첫 번째 k 좌표에 1을 추가하면 어떤 일이 일어나는지 기준으로 빈에 주문한다.Then you check the bins that contain both $\ {\textbf {f}}_{1}$ and $\ {\textbf {f}}_{2}$ and see if the property ${\displaystyle \ {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot$ ${\textbf{h}{\pmod{q}}}$ 이 $\ \textbf{f}_1 \cdot \textbf{h} = \textbf{g} -\textbf{f}_2 \cdot \textbf{h} \pmod q$ (가) 유지된다.

격자 감소 공격은 가장 잘 알려진 것 중 하나이며 NTRUEncrypt를 깨기 위한 가장 실용적인 방법 중 하나이다.어떻게 보면 RSA에서 계수의 인자화와 비교할 수 있다.격자 감소 공격에 가장 많이 사용되는 알고리즘은 Lenstra-Lenstra-Lovasz 알고리즘이다.왜냐하면 공개키 h는 f와 g를 모두 포함하고 있기 때문에 h로부터 그것들을 얻으려고 시도할 수 있다.그러나 NTRUEncrypt 매개변수가 충분히 안전한 것으로 선택되었을 때 비밀키를 찾는 것은 너무 어렵다.격자의 치수가 커지고 최단 벡터가 길어지면 격자 감소 공격은 더 어려워진다.

선택한 암호문 공격도 비밀키 f를 되찾아 완전 단절(total break)을 초래하는 방법이다.이 공격에서 이브는 암호문으로부터 그녀 자신의 메시지를 얻으려 하고 따라서 비밀키를 얻으려고 한다.이 공격에서 이브는 밥과 아무런 상호작용을 하지 않는다.

작동 방식:

첫번째 이브)암호화 텍스트 e를 만듭니다 ch+c{\displaystyle\와 같이{\textbf{e}}=c{\textbf{h}}+c}가 c)0(모드 p), c는<>q2{\displaystyle)c=0{\pmod{p}},c<,{\frac{q}{2}}}과 2c>q2{\displaystyle\와 같이 2c>,{\frac{q}{2}}}언제 이브를 쓰는 단계로 해독해 e(없이 actu.최대 calculaf를 모르기 때문에 값을 팅) $\ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$ 는 a $\ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$ = $\ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$ $\ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$ e $\ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$ ( $\ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$ $\ {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$ ) ${\$ :

{\textbf {a}={\textbf {f}\왼쪽(c{\textbf {h}+c\오른쪽){\pmod{q}}

{\textbf {a}=c{\textbf {g}+c{\textbf{f}{\pmod{q}}}

{\textbf {a}=c{\textbf {g}+c{\textbf {f}-qK

여기서 $\ K=\sum k_{i}x^{i}$ $\ K=\sum k_{i}x^{i}$ = $\ K=\sum k_{i}x^{i}$ $\ K=\sum k_{i}x^{i}$ $\ K=\sum k_{i}x^{i}$ $\ K=\sum k_{i}x^{i}$ ${\$ \ $K=\sum k_{i}x^{i}}}.$

k_{i}={\begin{cases}1\ \ \qquad {\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ 1\\-1\qquad {\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ -1\\0\ \ \qquad {\text{Otherwise}}\end{cases}}

예:

{\textbf{f}=-1+X+X^{2}-X^{4}+X^{6}+X^{9}-X^{10}}}}

{\textbf{g}=-1+X^{2}+X^{3}+X^{5}-X^{8}-X^{10}}}

그러면 K는 $\ K=-1+X^{2}-X^{10}$ = $\ K=-1+X^{2}-X^{10}$ - $\ K=-1+X^{2}-X^{10}$ + $\ K=-1+X^{2}-X^{10}$ 2 $\ K=-1+X^{2}-X^{10}$ - $\ K=-1+X^{2}-X^{10}$ $\ K=-1+X^{2}-X^{10}$ ${\$ \ $K=-1+X^{2}-X^{10}}$ 이 된다 $\ K=-1+X^{2}-X^{10}$

다항식의 계수를 줄이면 mod p는 $\ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}$ 로 c $\ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}$ + $\ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}$ - $\ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}$ K $\ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}$ ( $\ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}$ $){\$ ${\pmod{p}}}}$ 의 계수를 줄인다 $\ {\textbf {f}}_{p}$ $\ {\textbf {f}}_{p}$ {\ $displaystystystylee:$

{\displaystyle {\textbf{m}=c{\textbf {f}_{p}\cdot{g}+c{\textbf {f}{p}}\textbf {f}-q}{p}\textbf}\cdot K{\pmod{p}}}}}}}}}}}}}}}}}}}}"

{\textbf {m}=c{\textbf {h}+c-q{\textbf {f}{p}\cdot K{\pmod {p}}}

c는 p의 배수로 선택되었기 때문에 m은 다음과 같이 쓸 수 있다.

{\textbf{m}=-q{\textbf {f}_{p}\cdot K{\pmod{p}}}

즉 $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$ = - $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$ $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$ ⋅ $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$ - $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$ ( $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$ $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$ ) ${\$ displaystyle $\{\textbf$ { $f}=-qK\cdot {\textbf{m}^{-1}{\pmod {p$

이제 f와 g가 동일한 요인에 동일한 계수가 거의 없는 경우, K는 0이 아닌 계수가 거의 없으므로 크기가 작다.K의 다른 값을 시도함으로써 공격자는 f를 복구할 수 있다.

NTRUEncrypt에 따라 메시지를 암호화하고 해독함으로써 공격자는 f 함수가 올바른 비밀키인지 아닌지 확인할 수 있다.

보안 및 성능 향상

NTRUEncrypt 공개 키 암호 시스템은 최신 제안 매개변수(아래 참조)를 사용하여 대부분의 공격에 안전하게 보호된다.그러나 성과와 보안 사이에는 계속 분쟁이 있다.속도를 늦추지 않고서는 보안이 개선되기 어렵고, 그 반대의 경우도 마찬가지다.

알고리즘의 유효성을 손상시키지 않고 공정 속도를 높이는 한 가지 방법은 비밀키 f를 일부 변경하는 것이다.먼저 f $\ {\textbf {f}}=1+p{\textbf {F}}$ = $\ {\textbf {f}}=1+p{\textbf {F}}$ + $\ {\textbf {f}}=1+p{\textbf {F}}$ F ${\$ 이 $\ {\textbf {f}}=1+p{\textbf {F}}$ 가) 작은 다항식(예: 계수 {-1,0, 1)인 f를 생성하십시오.f를 이런 식으로 구성함으로써 f는 불변형 mod p가 된다.사실 $\ {\textbf {f}}^{-1}=1{\pmod {p}}$ - $\ {\textbf {f}}^{-1}=1{\pmod {p}}$ = $\ {\textbf {f}}^{-1}=1{\pmod {p}}$ ( $\ {\textbf {f}}^{-1}=1{\pmod {p}}$ p $\ {\textbf {f}}^{-1}=1{\pmod {p}}$ ) ${\$ 이것은 밥이 실제로 역수를 계산할 필요가 없고, 밥이 두 번째 단계의 암호 해독을 수행할 필요가 없다는 것을 의미한다.따라서 이러한 방식으로 f를 구성하면 시간이 많이 절약되지만, F $\ {\textbf {f}}_{p}$ ${\$ 를 $\ \textbf{f}_p$ 찾는 것이 더 쉬울 뿐, F는 여전히 복구하기 어렵기 때문에 NTRUEncrypt의 보안에는 영향을 미치지 않는다.이 경우 f는 p에 의한 곱셈으로 인해 -1, 0 또는 1과 다른 계수를 가진다.그러나 밥은 p를 곱하여 공개키 h를 생성하고, 나중에 암호문 modulo p를 감소시키기 때문에, 이것은 암호화 방법에 영향을 미치지 않을 것이다.

둘째, f는 여러 다항식의 산물로 쓸 수 있는데, 다항식은 계수가 0이 많다.이렇게 하면 더 적은 계산을 수행해야 한다.

2020 NTRU NIST 제출에 따라 다음과 같은 매개변수가 안전한 것으로 간주된다.

표 1: 매개변수

	N	q	p
128비트 보안 여유(NTRU-HPS)	509	2048	3
192비트 보안 여유(NTRU-HPS)	677	2048	3
256비트 보안 여유(NTRU-HPS)	821	4096	3
256비트 보안 여유(NTRU-HRSS)	701	8192	3

참조

Jaulmes, E. and Joux, A. NTRU에 대한 선택-시퍼텍스트 공격. 컴퓨터 과학 강의 노트; Vol 1880.제20회 국제암호학회의의 암호학 발전 과정. 페이지 20–35, 2000.
Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman.NTRU: 링 기반 공개 키 암호 시스템.알고리즘 번호 이론(ANTIII), 포틀랜드, OR, 1998년 6월 J.P. Buhler (ed.), 컴퓨터 과학 1423, 스프링거-베를라크, 1998, 267–288.
Howgrave-Graham, N, Silverman, J.H & Whyte, W, Meet-in-The-Middle Attack on NTRU Private Key.
J. 호프스타인, J. 실버맨.NTRU. 공용 키 암호화와 계산 번호 이론(Warsaw, 2000년 9월 11일–15일), DeGruyter가 나타나기 위한 최적화.
A. C. 아티치, L. 바티나, J. 팬 & I. 부바우웨데.보급형 보안을 위한 NTRU의 저비용 구현.

외부 링크

[1] "US Patent 6081597 – Public key cryptosystem method and apparatus" – via Google Patents.

[2] "Security Innovation's NTRUEncrypt Adopted as X9 Standard for Data Protection". April 11, 2011.

[3] ttps://ntru.org/release/NIST-PQ-Submission-NTRU-20201016.tar.gz

[1]

[2]

Search