BY KEYHUNTER 13.03.2025
우리는 타원 곡선에서 무효 곡선 공격의 개념을 genus 2 초타원 곡선으로 확장합니다. 또한 무효한 특이 (초)타원 곡선이 (초)타원 곡선 암호 시스템에 무효 곡선 공격을 마운트하는 데 사용될 수 있음을 보여주고 이러한 공격의 실용성에 대한 정량적 추정을 합니다. 이를 통해 초타원 곡선을 기반으로 하는 암호 시스템에서도 적절한 키 검증이 필요함을 보여줍니다. 부산물로, 이전 방법보다 더 간단한 새로운 계산 논증으로 유한체에 대한 genus (g) 초타원 곡선의 동형 클래스를 열거합니다.
- 소개
공개 키 검증의 목적은 공개 키가 특정 산술적 속성을 가지고 있는지 확인하는 것입니다.공개 키 검증은 특히 당사자( \hat{B} )가 자신의 개인 키와 다른 당사자( \hat{A} )로부터 받은 공개 키를 결합하여 그룹 요소( \sigma )를 형성하는 이산 대수 프로토콜에서 중요합니다.부정직한 당사자( \hat{A} )가 잘못된 공개 키를 선택하여 프로토콜에서 ( \sigma )를 사용한 후 ( \hat{B} )의 개인 키에 대한 정보가 유출될 수 있습니다.Lim 및 Lee[18]는 그룹 요소의 수신자가 해당 요소가 원하는 고차 그룹(예: ( \mathbb{F}_p^* )의 소수차 DSA 유형 하위 그룹)에 속하는지 확인하지 못하는 경우 효과적인 일부 이산 대수 키 합의 프로토콜에 대한 소그룹 공격을 제시하여 공개 키 검증의 중요성을 입증했습니다. [3, 1]에서, 수신자가 해당 지점이 실제로 선택된 타원 곡선에 있는지 확인하지 않는 경우 타원 곡선 프로토콜에 효과적인 무효 곡선 공격이 설계되었습니다. 또한 [20, 22, 21]을 참조하세요. Chen, Cheng 및 Smart [6]는 쌍선형 쌍을 사용하는 ID 기반 키 계약 프로토콜에서 공개 키 검증의 중요성을 설명했습니다.
저속 초타원 곡선의 성능은 타원 곡선의 성능과 경쟁력이 있는 것으로 나타났습니다(^*). 최근 연구 요약은 [2]를 참조하세요. 우리는 잘못된 곡선 공격이 프로토콜에 성공적으로 마운트될 수 있음을 보여줍니다.
2000 수학 과목 분류: 94A60. 핵심 단어 및 구문: 무효 곡선 공격, 초타원 곡선. (^*)타원 곡선은 1종 초타원 곡선입니다.
적절한 공개 키 검증이 수행되지 않으면 2세대 초타원 곡선을 기반으로 합니다. 또한 특이 곡선을 사용하여 (초)타원 곡선 프로토콜에 대한 무효 곡선 공격을 마운팅할 수 있음을 보여줍니다. 최근 제안된 두 가지 이산 대수 프로토콜(Twin Diffie-Hellman 키 합의 체계[5] 및 XCR 서명 체계[14])에 대한 공격을 설명합니다.
초타원 곡선 암호 시스템에 대한 무효 곡선 공격을 분석하기 위해서는 유한체( \mathbb{F}_q ) 위의 속(g ) 초타원 곡선의 동형 클래스 수( N_g(q) )를 아는 것이 유용합니다. 대수적으로 닫힌 체( K ) 위의 속(g ) 초타원 곡선의 동형 클래스는 ( K ) 위의 모듈리 공간( M_g )의 ((2g-1))차원 기약 부분 다양체( H_g )의 원소와 1대 1 대응합니다(참조 [11, p.347]). 이는 ( N_g(q) )에 대한 닫힌 공식을 제시한 Nart [23]에 의해 확인되었습니다. 우리는 ( N_g(q) = 2q^{2g-1} + O(q^{2g-2}) )라는 기본적인 계산 논거를 제시합니다.
논문의 나머지 부분은 다음과 같이 구성되어 있습니다. §2에서 수학적 기초를 마련한 후, §3에서 유한체 위의 속(g) 초타원 곡선의 수를 도출했습니다. §4에서 타원 곡선에서 속 2 곡선으로 무효 곡선의 개념을 확장했습니다. 또한 무효 특이 곡선의 개념을 제시하고 무효 타원 및 속 2 특이 곡선을 열거했습니다. 무효 곡선 공격은 §5에서 시연 및 분석했으며, §6에서 결론을 내렸습니다.
- 수학적 예비 지식
표기법. 연산자 ( [x^i] )는 ( x )가 불확정수일 때 계수 추출 연산자를 나타냅니다. 불확정수 ( x )와 다항식 ( f(x) )의 경우 규칙 ( [x^i]f(x) = f_i )를 채택합니다. 유한체 ( \mathbb{F} q )에 대한 차수 ( d )의 모닉 다항식 집합은 ( \mathcal{P}^d )로 표시됩니다. 반복되는 근이 하나 이상 있는 다항식의 부분 집합은 ( \mathcal{P}d^{\geq 2} )로 표시됩니다. ( \tilde{f} = \tilde{f}{d-1}, \tilde{f} {d-2}, \ldots, \tilde{f}_{di} )가 각각 ( \tilde{f}_j \in \mathbb{F}_q )인 순서 있는 시퀀스라고 합시다. 그러면
[ \mathcal{P} d := { x^d + f} {d-1}x^{d-1} + 점 + f} {di}x^{di} + f {di-1}x^{di-1} + 점 + f_0 \mid \tilde{f}_{di-1}, \ldots, f_0 \in \mathbb{F}_q }.]
예를 들어, ( \mathcal{P}^2_{2,3} )은 ( x^2 – 3x + f_0 ) 형태의 다항식 집합을 나타냅니다. 여기서 ( f_0 \in \mathbb{F}_q )입니다.
유한체( \mathbb{F}_q ) 위의 유형( g )의 초타원 곡선( \mathcal{H} )은 비특이 바이어슈트라스 방정식에 의해 정의됩니다.
[ \mathcal{H} : y^2 + H(x)y = F(x), ]
여기서 ( F, H \in \mathbb{F} q[x] ), ( F )는 단일적이고 ( \deg(F) = 2g + 1 ), ( \deg(H) \leq g )입니다. ( \mathcal{H} )의 ( \mathbb{F}_q )에 대한 야코비안 ( J {\mathcal{H}}(\mathbb{F}_q) )은 ( \mathbb{F}_q )에 대해 정의된 0차 약수의 몫군으로 ( \mathbb{F} q )에 대해 정의된 주 약수의 군입니다. 약수 클래스 ( \bar{D} \in J {\mathcal{H}}(\mathbb{F}_q) )는 ( u, v \in \mathbb{F}_q[x] ), ( \deg(v) < \deg(u) \leq g ), ( u ) 단일, ( u \mid (v^2 + Hv – F) )를 갖는 다항식 쌍 ((u, v))과 일대일 대응합니다. ( \bar{D} = [u, v] )로 씁니다.
( J_{\mathcal{H}}(\mathbb{F} q) )는 ( |J {\mathcal{H}}(\mathbb{F}_q)| \in [(\sqrt{q} – 1)^{2g}, (\sqrt{q} + 1)^{2g}] ) [25]를 갖는 유한 아벨 군입니다. 두 개의 약수 클래스( \bar{D}_1 = [v_1, v_1] )와 ( \bar{D} 2 = [v_2, v_2] \in J {\mathcal{H}}(\mathbb{F}_q) )가 주어지면 칸토어 알고리즘[4]을 사용하여 고유한 약수( \bar{D} = [u, v] )를 찾을 수 있으며, 이때 ( \bar{D} = \bar{D}_1 + \bar{D}_2 )가 됩니다.
( \text{char}(\mathbb{F}_q) \not\in {2, 2g + 1} )이면 동일한 곡선 ( \mathcal{H} )(동형까지)은 다음 방정식으로 주어질 수 있습니다.
[ (1) \quad \mathcal{H} : y^2 = f(x) = x^{2g+1} + \sum_{i=0}^{2g-1} f_i x^i. ]
( \mathcal{H} ) 방정식의 비특이점 요구 사항은 ( f )에 반복된 근이 없다는 것을 의미하며, 이 경우 ( \mathcal{H} )를 비특이 곡선이라고 합니다. ( f )에 반복된 근이 ( x_0 )인 경우 ( \mathcal{H} )를 특이 곡선이라고 하며, ( (x_0, y_0) )(여기서 ( y_0^2 = f(x_0) ))은 ( \mathcal{H} )의 특이점입니다.
이 작업의 나머지 부분에서는 유한체( \mathbb{F}_q ) 위의 종(g )의 초타원 곡선( \mathcal{H} )이 (1)을 통해 주어진다고 가정합니다. ( \mathbb{F}_q ) 위의 모든 (비특이) 종(g ) 초타원 곡선의 집합은 ( \mathcal{H}^* )로 표시됩니다. 초타원 곡선( \mathcal{H} )이 ( \mathbb{F} q ) 위에 정의되면 ( J {\mathcal{H}}(\mathbb{F} q) )를 ( J {\mathcal{H}} ) 로 축약합니다 .
3. 초타원곡선의 수
이 섹션에서 우리는 (1)에 의해 주어진 비동형 속(g) 초타원 곡선의 수를 추정합니다. 먼저 반복되는 근이 없고 고정된 2차 선행 계수를 갖는 모닉 다항식의 수에 대한 다음 공식이 필요합니다.
정리 1. ( g \geq 1 )이 정수이고 ( \mathbb{F}_q )가 유한체이고 ( f_2 \in \mathbb{F}_q )가 유한체라고 하자. 그러면
[ \lvert \mathbb{P} {f_2}^{2g+1} \setminus \mathbb{P}} {f_2}^{2g+1} \rvert = q^{2g} – q^{2g-1}.]
증명. ( \bar{\mathbb{F}}_q )가 ( \mathbb{F}_q )의 폐쇄를 나타낸다고 하자. 논증은 ( g )에 대한 귀납법으로 진행된다.
( g = 1 )에 대해 ( f(x) = x^3 + f_2 x^2 + f_1 x + f_0 \in \mathbb{P} {f_2}^{3} )을 고려합니다. ( f )는 3차이므로 최대 하나의 반복 근을 가질 수 있습니다(예: ( \alpha ). ( \alpha \in \mathbb{F}q \setminus \bar{\mathbb{F}}q )이면 ( \alpha )의 켤레도 ( f )의 반복 근이므로 ( f )가 최대 하나의 반복 근을 갖는다는 사실과 모순됩니다. 따라서 ( \alpha \in \bar{\mathbb{F}}q )입니다. ( f )를 인수분해하면 ( f(x) = (x – \alpha)^2 (x – \beta) )가 되고, 여기서 ( \beta = -f_2 – 2\alpha )입니다. 따라서 유일한 자유도는 ( \alpha )이고 따라서 ( \lvert \tilde{\mathbb{P}}{f_2}^{3} \rvert = q )입니다. 그리고 ( \lvert \mathbb{P}{f_2}^{1} \rvert = q^2 )이므로 ( \lvert \mathbb{P}{f_2}^{1} \setminus \tilde{\mathbb{P}} {f_2}^{1} \rvert = q^2 – q )가 됩니다.
모든 정수 ( 1, 2, \ldots, (g – 1) )에 대해 결과가 성립한다고 가정합니다. 여기서 ( g \geq 2 ). 결과가 ( g )에 대해서도 성립하는 것을 보일 것입니다. ( f(x) = x^{2g+1} + \sum_{j=0}^{2g} f_j x^j \in \mathbb{P}_{f_2}^{2g+1} )이라고 합니다. 중복도가 ( k \geq 2 )인 ( f )의 각 반복 근 ( \alpha )에 대해 ( \lfloor k/2 \rfloor ) 쌍 ((\alpha, \beta))을 연결합니다. 이러한 각 쌍을 ( \alpha )에 해당하는 ( f )의 쌍 반복 근이라고 합니다. ( f )는 최대 ( g )개의 쌍 반복 근을 가질 수 있습니다. ( f \in \mathbb{F}_q[x] )에서 ( f )가 정확히 ( i ) 쌍의 반복 근을 가지고 있다면 ( f = a^2 b )로 작성할 수 있습니다. 여기서 ( a, b \in \mathbb{F}_q[x] )
[ a(x) = x^i + a_i x^{i-1} + \cdots + a_0, \ b(x) = x^{2(gi)+1} + \beta x^{2(gi)} + b_{2(gi)-1} x^{2(gi)-1} + \cdots + b_0, ]
그리고 (b)는 ( \bar{\mathbb{F}}_q )에서 반복되는 근이 없습니다. (b(x))의 계수 ( \beta )는 ( \beta + [x^{2i-1}]a(x)^2 = f_2g )를 만족하므로 ( \beta )는 (a)와 (f_2g )에 의해 결정됩니다. 고정된 ( i \in [1, g – 1] )에 대해 반복되는 근이 없고 고정된 ( \beta )를 갖는 차수 ( 2(gi)+1 )의 다항식 (b)의 수는 ( q^{2(gi)} – q^{2(gi)-1} 입니다. 따라서 정확히 ( i ) 쌍의 반복 근을 갖는 다항식 ( f )의 수는 ( q^i \cdot (q^{2(gi)} – q^{2(gi)-1}) = q^{2g-i} – q^{2g-i-1} )입니다. ( i = g )의 경우 다항식 ( f )는 ( a^2 (x – \beta) )로 인수분해되고 이전과 마찬가지로 ( \beta )는 ( a )와 ( f_2g )에 의해 결정됩니다. 그러면 정확히 ( g ) 쌍의 반복 근을 갖는 다항식 ( f )의 수는 ( a )에 대한 선택 수인 ( q^g )와 같습니다.
따라서 적어도 하나의 쌍을 이루는 반복근을 갖는 다항식(f)의 수는 다음과 같습니다.
[ \lvert \tilde{\mathbb{P}} {f_2}^{2g+1} \rvert = q^g + \sum {i=1}^{g-1} (q^{2g-i} – q^{2g-i-1}) ]
[ = q^g + q^{2g-1} + \sum_{i=2}^{g-1} q^{2g-i} – \sum_{i=1}^{g-1} q^{2g-i-1} = q^{2g-1}. ]
마지막으로 (|P_{f_{2g}}^{2g+1}| = q^{2g})이므로 [|P_{f_{2g}}^{2g+1} \setminus \tilde{P} {f {2g}}^{2g+1}| = |P_{f_{2g}}^{2g+1}| – |\tilde{P} {f {2g}}^{2g+1}| = q^{2g} – q^{2g-1}]이 성립하여 인수가 완료됩니다.
정리 1의 설정(f_{2g} = 0)은 (\mathbb{F}_q) 위의 속(g) 초타원 곡선을 정의하는 다항식의 수를 결정합니다. 여기서 (\text{char}(\mathbb{F}_q) \notin {2, 2g + 1})입니다. 그러나 이러한 곡선은 두 개 이상의 표현을 가질 수 있으며 동형 곡선을 구별하고 싶지 않습니다. Lockhart [19]에 따른 다음 결과는 곡선의 동형 클래스와 Weierstrass 방정식의 동치 클래스 간에 일대일 대응 관계를 제공합니다.
정리 2. [19, 명제 1.2] (H_1)과 (H_2)가 (\mathbb{F}_q) 위에서 정의된 두 개의 종 (g) 초타원 곡선이면 (H_1)과 (H_2)가 (\mathbb{F}_q) 위에서 동형인 것은 오직 (\alpha \in \mathbb{F}_q^*, \beta \in \mathbb{F}_q,)와 (t \in \mathbb{F}_q[x])가 존재하고 (\deg(t) \leq g)인 경우이고, 이때 좌표 ((x, y) \to (\alpha^2 x + \beta, \alpha^{2g+1} y + t(x)))의 변화는 (H_1)의 방정식을 (H_2)의 방정식으로 변환합니다.
무효 곡선 공격은 곡선 표현(및 명시적 군 법칙)에 기반합니다. 따라서 우리는 곡선 표현을 보존하는 동형 사상에 관심이 있습니다. 록하트의 정리는 다음과 같이 우리의 필요에 맞게 특수화될 수 있습니다.
(\text{char}(\mathbb{F}_q))가 홀수이고 (\text{char}(\mathbb{F}_q) \nmid (2g + 1))이라고 가정합니다. (H)가 (\mathbb{F}_q) 위의 속(g) 초타원 곡선이고, (\tau : (x, y) \to (\alpha^2 x + \beta, \alpha^{2g+1} y + t(x)))가 (\mathbb{F}_q) 위의 다른 속(g) 초타원 곡선과 동형이라고 합니다. (\tau)가 방정식(1)의 형태를 유지한다면 (\beta = 0)이고 (t(x) = 0)이어야 한다고 주장합니다. 실제로 (t(x) \neq 0)이면 (\tau)를 (H)에 적용하면 (y)에 선형 항이 생기지만 (1)에는 없습니다. 이제 변환 ((x, y) \to (\alpha^2 x + \beta, \alpha^{2g+1} y))를 (1)에 적용하면 (x^{2g})의 계수는 ((2g + 1)\beta \alpha^{4g})이고 (1)과 같이 0이어야 합니다. (\alpha \neq 0)이고 (\text{char}(\mathbb{F}_q) \nmid (2g + 1))이므로 (\beta = 0)이어야 합니다. 따라서 (1)을 보존하는 초타원 곡선의 동형 사상에 대응하는 변환 클래스는 ((x, y) \to (\alpha^2 x, \alpha^{2g+1} y)) 형태이며, 여기서 (\alpha \in \mathbb{F}_q^*)입니다. 이제부터 동형 사상에 대해 이야기할 때 우리는 그것을 원소 (\alpha)와 동일시할 것입니다.
정리 3에서 우리는 (2g + 1)을 나누지 않는 홀수 특성의 유한체 (\mathbb{F}_q)에 대한 속 (g) 초타원 곡선의 동형 클래스 수를 추정합니다. 정리 1에 의해 속 (g) 초타원 곡선을 발생시키는 다항식 (f \in \mathbb{F}_q[x])의 수는 (q^{2g} – q^{2g-1}이고 동형 사상(0이 아닌 체 요소)의 수가 (q – 1)이므로 비동형 곡선의 수는 약 (q^{2g-1}일 것으로 예상합니다. 논문이 제출된 후에 나온 [23, 정리 3.3]에서 약간 더 강력한 결과가 증명되었습니다. 여기에 제시된 증명은 더 간단하고 독자의 편의를 위해 제시됩니다.
정리 3. (g)가 고정되어 있다고 하자. (\mathbb{F}_q)가 홀수 특성(p)을 갖는 유한체이고, (p \nmid (2g + 1))이고 (q > 4g + 2)라고 가정하자. 그러면 (\mathbb{F}_q) 위의 비동형 종(g) 초타원 곡선의 수는 [N_g(q) = 2q^{2g-1} + \mathcal{O}(gq^{2g-2})]이다.
증명. (f \in \tilde{P} {0}^{2g+1} \setminus P {0}^{2g+1})이라고 하자. (z_i(f) = 0)이면 (f_i = 0)이고, 그렇지 않으면 (z_i(f) = 1)로 정의한다. (f)가 문맥상 명확한 경우 (z_i(f))를 (z_i)로 줄인다. 시퀀스 (z(f) = (z_0, z_1, \ldots, z_{2g-1}))를 (f)의 특성 시퀀스라고 한다. (ab)를 사용하여 시퀀스 (z)를 표시하는데, 여기서 (z_0 = a, z_1 = b)이고 나머지 항목은 (\tilde{z}로 주어진다. (H_{ab}^z)를 특성 시퀀스 (z)를 갖는 다항식 (f)의 집합이라 하자. ( |z| )가 시퀀스 (z)에 있는 0이 아닌 항목의 개수를 나타낸다고 하자. 그러면 (|H_{10}^z| \leq (q-1)^{|z|})와 (|H_{11}^z| \leq (q-1)^{|z|})입니다.
곡선( y^2 = f(x) )에 작용하는 동형사상( \alpha )은 특성 시퀀스( z )를 보존합니다. 실제로, 동형 사상 ( \alpha : (x, y) \rightarrow (\alpha^2 x, \alpha^2 + y) )을 (1)에 적용하면 [ \alpha^{4g+2} y^2 = \alpha^{4g+2} x^{2g+1} + \alpha^{4g-2} f_{2g-1} x^{2g-1} + \cdots + \alpha^2 f_1 x + f_0, ]이 되며, 이는 [ y^2 = x^{2g+1} + \alpha^{-4} f_{2g-1} x^{2g-1} + \cdots + \alpha^{-4} f_1 x + \alpha^{-4g+2} f_0. ]로 다시 쓸 수 있습니다.
따라서 ( f \in H_{ab}^z )에 대한 곡선 ( y^2 = f(x) )은 동일한 자기 동형 군을 갖는다. 이 군을 ( \text{Aut} H_{ab}^z )로 표시한다. 또한 매핑 ( \alpha )이 자기 동형인 경우 ( \mathbb{F} q )에서 ( \alpha )의 차수는 ( 4g+2 )를 나누어야 함을 관찰한다. ( q > 4g+2 )이므로 ( |\text{Aut} H {ab}^z| )는 ( 4g+2 )보다 크지 않으며, 이는 [ \sum_z |H_{01}^z| (|\text{Aut} H_{11}^z| – 2) \leq 4g \sum_z |H_{01}^z| \leq 4g \sum_z (q-1)^{|z|} = 4g \sum_{|z|=1}^{2g-1} \left( \frac{2g-2}{|z|-1} \right) (q-1)^{i-1} = 4g(q-1) \sum_{i=1}^{2g-1} \frac{2g-2}{i} (q-1)^{i-1} = 4g(q-1)q^{2g-2} = O(q^{2g-1}). ]
위 방정식에서 시퀀스(z)의 처음 두 좌표가 고정되어 있으므로 나머지(|z| – 1)개의 0이 아닌 항목은 (2g-2)개의 가능한 인덱스에서 선택됩니다. 마찬가지로 [ \sum_z (|H_{11}^z| + |H_{01}^z| + |H_{10}^z|) = q^{2g} – q^{2g-1}.]가 있습니다.
( z_0 )과 ( z_1 )이 모두 0이면 ( 0 )은 ( f )의 반복근입니다. 따라서 ( f )에 반복근이 없으면 ( z_0 ) 또는 ( z_1 ) 중 적어도 하나는 0이 아닙니다. 정리 1에 따르면 [ \sum_{z \in 0z} (|H_{11}^z| + |H_{01}^z| + |H_{10}^z|) = q^{2g} – q^{2g-1}.]
(f_1)과 (f_0)이 동시에 0이 아닐 때 (f)를 고정하는 자기 동형 사상 ( \alpha )은 ( \alpha^2 = 1 )을 만족해야 합니다. 이러한 자기 동형 사상은 두 가지가 있으므로 ( |\text{Aut} H_{11}^z| = 2 )입니다. 따라서, [ N_g(q) = \sum_{z \in 0z} \frac{|H_{10}^z||\text{Aut} H_{ab}^z|}{q-1} = \sum_{z \in 0z} \frac{|H_{10}^z||\text{Aut} H_{ab}^z|}{q-1} = \sum_{z \in 0z} \frac{|H_{10}^z||\text{Aut} H_{ab}^z|}{q-1} = \sum_{z \in 0z} \frac{|H_{10}^z||\text{Aut} H_{ab}^z|}{q-1}.]
= \frac{1}{q-1} \left( \sum_{01\tilde{z}} |H_{01}\tilde{z}| | \text{자동} H_{01}\tilde{z} | + \sum_{10\tilde{z}} |H_{10}\tilde{z}| | \text{자동} H_{10}\tilde{z} | + 2|H_{11}\tilde{z}| \right)
= \frac{1}{q-1} \left( \sum_{01\tilde{z}} |H_{01}\tilde{z}| | \text{Aut} H_{01}\tilde{z} | + \sum_{10\tilde{z}} |H_{10}\tilde{z}| | \text{Aut} H_{10}\tilde{z} | + 2 \left( q^{2g} – q^{2g-1} – \sum_{01\tilde{z}} |H_{01}\tilde{z}| – \sum_{10\tilde{z}} |H_{10}\tilde{z}| \오른쪽) \오른쪽)
= \frac{1}{q-1} \left( \sum_{01\tilde{z}} |H_{01}\tilde{z}| \left( | \text{자동} H_{01}\tilde{z} | – 2 \오른쪽) + \sum_{10\tilde{z}} |H_{10}\tilde{z}| \left( | \text{자동} H_{10}\tilde{z} | – 2 \오른쪽) + 2 \left( q^{2g} – q^{2g-1} \오른쪽) \오른쪽)
= \frac{1}{q-1} \left( O(gq^{2g-1}) + O(gq^{2g-1}) + 2q^{2g} – 2q^{2g-1} \right)
= \frac{1}{q-1} \left( 2q^{2g} + O(gq^{2g-1}) \right)
= 2q^{2g-1} + O(gq^{2g-2}),
필요에 따라.
- 무효곡선 및 특이곡선
이제 Antipa et al. [1]이 제안한 무효 타원 곡선의 개념을 genus 2 곡선으로 확장합니다. 무효 곡선은 특정 곡선 표현과 군 법칙에 대한 명시적 공식에 대해 정의된다는 점을 강조합니다. 즉, 곡선 표현과 선택된 곡선 표현에서 특정 계수를 사용하지 않는 군 연산에 대한 공식이 주어지면 해당 표현-공식 쌍에 대해 무효 곡선을 정의할 수 있습니다. 명시적 공식이 곡선 표현의 모든 계수를 사용하는 경우 이 맥락에서 무효 곡선은 존재하지 않습니다. 그러나 암호화 응용 프로그램에서 널리 고려되는 genus 1 및 genus 2 곡선의 경우 무효 곡선의 개념은 실제로 관련성이 있고 중요합니다.
1세대 설정에서 우리는 [2, §13.2.1]에 기술된 군 법칙에 대한 아핀 공식을 사용하고 이 논문 전체에서 이 공식을 $F_{1a}$라고 합니다. $F_{1a}$의 명시적 계산에는 계수 $f_1$만 필요합니다. 잘못된 타원 곡선의 정의에서 우리는 특이 타원 곡선도 포함합니다.
정의 1. $E$가 방정식을 갖는 $\mathbb{F}_q$에 대해 정의된 타원 곡선이라고 하자.
$$E : y^2 = x^3 + f_1x + f_0.$$
$E$ 및 $F_{1a}$에 대한 잘못된 곡선은 방정식이 있는 $\mathbb{F}_q$ 위의 타원 곡선입니다.
$$IE : y^2 = x^3 + f_1x + \tilde{f}_0,$$
여기서 $\tilde{f}_0 \neq f_0$이고 $IE$는 $E$와 동형이 아닙니다. 또한 다항식 $\tilde{f}(x) = x^3 + f_1x + \tilde{f} 0$에 반복된 근이 있으면 $IE$는 $E$와 $F {1a}$에 대해 잘못된 특이 곡선이라고 합니다 .
2세대 설정에서 우리는 [2, §14.3.2]에 기술된 군 법칙에 대한 아핀 공식을 사용하고 이 논문 전체에서 이 공식을 $F_{2a}$라고 합니다. 공식 $F_{2a}$는 $f_2$와 $f_3$에만 의존합니다. 우리는 잘못된 초타원 곡선을 정의할 때 특이 초타원 곡선도 포함합니다.
정의 2. $H$가 방정식을 갖는 $\mathbb{F}_q$에 대해 정의된 종 2 초타원 곡선이 되도록 하세요.
$$H : y^2 = x^5 + f_3x^3 + f_2x^2 + f_1x + f_0.$$
$H$ 및 $F_{2a}$에 대한 잘못된 곡선은 방정식이 있는 $\mathbb{F}_q$ 위의 초타원 곡선입니다.
$$IH : y^2 = x^5 + f_3x^3 + f_2x^2 + \tilde{f}_1x + \tilde{f}_0, $$
여기서 $(f_1, f_0) \neq (f_1, f_0)$이고 $IH$는 $H$와 동형이 아닙니다. 또한 다항식 $f(x) = x^5 + f_3x^3 + f_2x^2 + \tilde{f}_1x + \tilde{f} 0$에 반복된 근이 있으면 $IH$는 $H$와 $F {2a}$ 에 대해 잘못된 특이 곡선이라고 합니다 .
잘못된 특이 곡선은 genus 1의 경우 매우 흥미롭습니다. $SE$가 $\mathbb{F}_q$와 $F_1a$ 위의 타원 곡선 $E$에 비해 $\mathbb{F}_q$ 위의 잘못된 특이 곡선이면 $SE$는 정확히 하나의 특이점 $P = (x_0, y_0)$을 갖습니다. 동형 사상 $(x, y) \rightarrow (x + x_0, y + y_0)$을 $SE$에 적용하면 $SE$가 다음 방정식으로 주어진다고 가정할 수 있습니다.
$$SE : y^2 = x^3 + a_2x^2, \quad a_2 \in \mathbb{F}_q, $$
그리고 $P = (0, 0)$은 $SE$의 특이점입니다. 이제 $y^2 – a_2x^2 = (y – \alpha x)(y – \beta x)$라 하자. 여기서 $\alpha, \beta \in \mathbb{F}_q$. 만약 $a_2 = 0$이면 $\alpha = \beta = 0$이고, $P$를 $SE$의 첨단 특이점이라고 합니다. 만약 $a_2 \neq 0$이면 $\alpha = -\beta$이고, $a_2 = a_2′; P$를 $SE$의 노드 특이점이라고 합니다. 이 경우, $a_2$가 $\mathbb{F}_q$의 이차 잔류물이라면 $\alpha, \beta \in \mathbb{F}_q$입니다. 그리고 $\alpha, \beta \in \mathbb{F}_q \setminus \mathbb{F} q^*$, 그렇지 않으면. $SE$ 위의 비특이 $\mathbb{F} q$-점들의 집합 $SE {ns}(\mathbb{F}_q)$와 무한대의 점은 군을 형성하고, 사실 $E$에 대한 군 법칙 $F_1a$는 $SE$에 대한 군 법칙이기도 하다는 것은 잘 알려진 사실이다. 게다가 $P$가 $SE$의 첨단 특이점이라면 $SE {ns}(\mathbb{F}_q)$는 $\mathbb{F}_q$의 덧셈 군과 동형이다. $P$가 $SE$의 노드 특이점이고 $a \in \mathbb{F} q$이면 $SE {ns}(\mathbb{F}_q)$는 $\mathbb{F}_q^*$의 순서-$(q + 1)$ 곱셈 부분군과 동형입니다. 모든 경우에서 동형 사상은 효율적으로 계산할 수 있습니다(자세한 내용은 [12, §7.2] 참조). 특이 무효 곡선 공격을 적용하는 핵심 요점은 특이하지 않은 타원 곡선에 대한 군 법칙을 특이하지 않은 타원 곡선의 특이하지 않은 부분에 쉽게 사용할 수 있다는 것입니다.
다음 정리는 정의 1의 설정을 가정하고 유효하지 않은 특이 타원 곡선의 존재와 개수를 확립합니다.
정리 4. $\gcd(q, 6) = 1인 $\mathbb{F}_q$에 대해 $y^2 = x^3 + f_1x + f_0$ 및 $F_1a$에 대한 잘못된 특이 곡선의 수는 다음과 같습니다.
(i) $f_1 = 0$이면 1입니다.
(ii) 2, 만약 $-\frac{f_1}{f_0} \in \mathbb{F}_q$이면;
(iii) $-\frac{f_1}{f_0}$가 $\mathbb{F}_q$의 이차 비잔류이면 0입니다.
증명. $f_1 \in \mathbb{F}_q$가 고정되어 있고 다항식 집합을 고려합니다.
$$P_{0, f_1}^3 = { P_{f_0}^3(x) = x^3 + f_1x + f_0′ : f_0′ \in \mathbb{F}_q }.$$
$P_{f_0}^3(x)$가 $\bar{\mathbb{F}}_q$에서 반복되는 근을 갖는 경우 우리는 다음을 가져야 합니다.
$$P_{f_0}^3(x) = x^3 + f_1x + f_0′ = (x + a)^2(x + k_0), \quad a, k_0 \in \mathbb{F}_q.$$
또는 동등하게,
\begin{align} (2) & \quad k_0 = -2a \ (3) & \quad f_1 = -3a^2 \ (4) & \quad f’_0 = -2a^3. \end{align}
고정된 ( f_1 )에 대해 우리는 (2)–(4)에 대한 솔루션 ((a, k_0, f’_0))을 고려합니다.
사례 (i). ( f_1 = 0 )이면 ((0, 0, 0))이 (2)–(4)에 대한 유일한 해이고 따라서 ( P_{0, f_1}^3 )은 반복된 근을 갖는 정확히 하나의 다항식, 즉 ( P(x) = x^3 )을 갖습니다. 이 경우 ( y^2 = P(x) )로 정의된 곡선은 ( S = (0, 0) )에서 정점 특이점을 갖습니다.
사례 (ii). ( -f_1/3 = a_1^2 )가 일부 ( a_1 \in \mathbb{F} q^* )에 대해 성립하는 경우 ((a_1, -2a_1, -2a_1^3))와 ((-a_1, 2a_1, 2a_1^3))은 (2)–(4)에 대한 유일한 두 해입니다. 따라서 ( P {0, f_1}^3 )에는 반복되는 근을 갖는 정확히 두 개의 다항식이 있습니다. ( P(x) = x^3 + f_1x – 2a_1^3 ) 이 경우 ( y^2 = P(x) )로 정의된 곡선은 ( S = (-a_1, 0)에서 노드 특이점을 갖습니다. 그리고 ( P(x) = x^3 + f_1x + 2a_1^3 )인 경우 ( y^2 = P(x) )로 정의된 곡선은 ( S = (a_1, 0) )에서 노드 특이점을 갖습니다.
사례 (iii). ( -f_1/3 )이 ( \mathbb{F} q )의 이차 비잔류이면 (2)–(4)로 정의된 시스템에는 해가 없으므로 ( P {0, f_1}^3 )에는 반복되는 근을 갖는 다항식이 포함되지 않습니다.
§5에 설명된 공격에서 적대자는 소순서 하위 그룹이 있는 곡선이 필요합니다. genus 1 사례에서 적대자는 ( f_0 )을 선택할 수 있는 능력이 있으며, [1, §4.4]에서 적대자가 본질적으로 무작위로 곡선을 선택하여 적합한 무효 곡선을 효율적으로 찾을 수 있다고 이미 주장했습니다. 이 주장을 genus 2에 확장하려면 다음과 같은 결과가 필요합니다.
정리 5. ( \gcd(q, 30) = 1 )이라고 가정합니다. ( y^2 = x^5 + f_3x^3 + f_2x^2 + f_1x + f_0 )와 ( \mathcal{F}_{2a} ) 위의 ( \mathbb{F}_q )에 대한 잘못된 특이 곡선의 수는 ( q – 3 )과 ( q + 3 ) 사이에 있습니다.
증명. ( f_2, f_3 \in \mathbb{F}_q )가 고정되어 있고 다항식 집합을 고려합니다.
[ P_{f_1, f’_0 }^5(x) = { P {f_1, f’_0}(x) = x^5 + f_3x^3 + f_2x^2 + f_1x + f’_0 : f’_1, f’_0 \in \mathbb{F}_q }. ]
( P_{f_1, f’_0}^5(x) )가 ( \bar{\mathbb{F}}_q )에서 반복되는 근을 갖는 경우 두 가지(상호 배타적이지 않음) 가능성이 있습니다.
사례 1. 다음과 같은 ( a, b, k_0 \in \mathbb{F}_q )가 존재합니다.
\begin{align} (5) & \quad P_{f_1, f’_0}^5(x) = x^5 + f_3x^3 + f_2x^2 + f_1’x + f’_0 = (x^2 + ax + b)^2(x + k_0). \end{align}
같은 차수 항의 계수를 비교하면 다음과 같습니다.
\begin{align} (6) & \quad k_0 = -2a \ (7) & \quad f_3 = 2b – 3a^2 \ (8) & \quad f_2 = -2a^3 + 2ab \ (9) & \quad f’_1 = b^2 – 4a^2b \ (10) & \quad f’_0 = -2b^2a. \end{align}
(7)과 (8)로부터 (a)는 (5a^3 + f_3a + f_2 = 0)을 만족해야 함을 알 수 있습니다. 더욱이 (f_2)와 (f_3)은 이미 고정되어 있으므로 (a)의 어떤 선택도 (6)과 (7)에 의해 (k_0)과 (b)를 고정합니다. 따라서 (5) 형태의 다항식 (P_{f_1, f’_0}^5(x))의 개수는 최대 3개입니다.
사례 2. 다음과 같은 (a, k_0, k_1, k_2 \in \mathbb{F}_q)가 존재합니다.
[ P_{f_1′, f_0′}(x) = x^5 + f_3x^3 + f_2x^2 + f_1’x + f_0′ = (x + a)^2(x^3 + k_2x^2 + k_1x + k_0).]
같은 차수 항의 계수를 비교하면 다음과 같습니다.
[ \begin{align*} (11) & \quad k_2 = -2a \ (12) & \quad k_1 = f_3 + 3a^2 \ (13) & \quad k_0 = f_2 – 2a(f_3 + 2a^2) \ (14) & \quad f_1′ = 2af_2 – 3a^2f_3 – 5a^4 \ (15) & \quad f_0′ = a^2f_2 – 2a^3f_3 – 4a^5. \end{align*} ]
고정된 쌍 ((f_2, f_3) \in \mathbb{F}_q \times \mathbb{F}_q)에 대해 먼저 (11)–(15)에 대한 해 ((a, k_0, k_1, k_2, f_0′, f_1′))의 개수를 센다. (a = 0)이면 (k_0 = f_2, k_1 = f_3, k_2 = f_0 = f_1′ = 0)이 되어야 한다는 점에 유의한다. 반면 (a \neq 0)이면 (k_1 \neq f_3)이 되고 ((k_1 – f_3)/3)은 (\mathbb{F}_q)에서 정확히 ((q – 1)/2)개의 원소 (k_1 \in \mathbb{F}_q)에 대한 이차 잉여이다.
이러한 각 (k_1)에 대해 (a)를 ((k_1 – f_3)/3의 제곱근과 같게 설정하여 결정되는 두 개의 솔루션을 얻습니다. 즉, 총 1 + 2(((q – 1)/2)) = (q)개의 솔루션이 있으며 각 솔루션 ((a, k_0, k_1, k_2, f_0′, f_1′))은 (\mathbb{F} q에서 하나 또는 두 개의 쌍을 이루는 반복된 근을 갖는 다항식 (P_{f_1′, f_0′}(x))으로 이어집니다 . 서로 다른 솔루션이 동일한 다항식 (P {f_1′, f_0′}(x)) 으로 이어질 수 있음을 유의하십시오 . 영어: 이는 (P_{f_1′, f_0′}(x))가 (\mathbb{F} q)에서 정확히 두 쌍의 반복 근을 갖는 경우에만 발생한다는 것을 쉽게 알 수 있으며, 이 경우 고정된 (P {f_1′, f_0′}(x))에 대해 이 다항식을 생성하는 최대 두 개의 서로 다른 솔루션이 존재할 수 있음을 보입니다. 증명은 다음과 같습니다. 세 개의 서로 다른 솔루션 (S := (a, k_0, k_1, k_2, f_0′, f_1′))과 (\tilde{S} := (\tilde{a}, \tilde{k}_0, \tilde{k}_1, \tilde{k} 2, f_0′, f_1′))이 있고, 다항식 (P {f_1′, f_0′}(x))이 생성된다고 가정합니다. (a = \tilde{a})이면 (11), (12) 및 (13)에 의해 (S = \tilde{S})입니다.
따라서 (a, \tilde{a})와 (\tilde{a})가 쌍으로 다르다고 가정할 것입니다. 이 경우 ((x + a)(x + \tilde{a})^2 | (x^3 + k_2x^2 + k_1x + k_0))이 성립하는 것을 볼 수 있는데, 이는 불가능합니다.
이제 정리를 증명할 준비가 되었습니다. 두 쌍의 반복 근이 모두 (\mathbb{F} q)에 있는 정확히 두 개의 쌍을 이루는 다항식 (P_{f_1′, f_0′}(x))의 수가 (\beta)이고, 두 쌍의 반복 근이 모두 (\mathbb{F}_q) (\backslash \mathbb{F} q)에 있는 정확히 두 개의 쌍을 이루는 다항식 (P {f_1′, f_0′}(x))의 수가 (\gamma)라고 가정합니다. 그러면 위의 논거에 따라 (11)–(15)에 대한 해 ((a, k_0, k_1, k_2, f_0′, f_1′))의 수는 각 해가 정확히 두 쌍의 반복 근을 갖고 두 근이 모두 (\mathbb{F} q에 있는 다항식 (P {f_1′, f_0′}(x))로 이어지는데 , 이 때 두 근이 모두 (\mathbb{F} q)에 있는 경우 최대 (2\beta)입니다. 따라서 (\mathbb{F} q에 정확히 한 쌍의 반복 근을 갖는 다항식 (P {f_1′, f_0′}(x)) 이 적어도 (q – 2\beta) 있고, (\mathbb{F}_q) 에 적어도 하나의 반복 근을 갖는 다항식 (P {f_1′, f_0′}(x))이 적어도 ((q – 2\beta) + \beta + \gamma) 있습니다. 사례 1에 따르면 (\beta + \gamma \leq 3)이고 (q – \beta + \gamma \geq q – 3)임을 알 수 있습니다.
사례 1과 사례 2에서 (\mathbb{F}_q)에 반복되는 근이 하나 이상 있는 다항식(P_{f_1′, f_0′}(x))은 최대 (q + 3)개입니다.
비고 1. (H : y^2 = x^5 + f_3x^3 + f_2x^2 + f_1x + f_0)을 (\mathbb{F} q) 위에 정의된 종 2 초타원 곡선이라고 하자. 정리 5에 따르면 (H)와 (\mathbb{F} {q^2}에 대해 적어도 (\chi = q^2 – q – 3)개의 유효하지 않은 곡선이 있다 . 이제 (f_2 \neq 0) 또는 (f_3 \neq 0)이면 이 곡선 중 적어도 (\chi/2)개가 쌍으로 비동형이라고 주장한다. (H’)와 (H”)가 (\mathbb{F}_q) 위에 있는 두 개의 종 2 초타원 곡선이라고 하자.
[ \begin{align*} H’ : & \quad y^2 = x^5 + f_3x^3 + f_2x^2 + f_1’x + f_0′ \ H” : & \quad y^2 = x^5 + f_3x^3 + f_2x^2 + f_1”x + f_0”. \end{align*} ]
곡선 $\mathcal{H}’$와 $\mathcal{H}”$는 동형사상 $\alpha$가 있는 경우 동형입니다.
$$\alpha : (x, y) \rightarrow (\alpha^2 x, \alpha^5 y)$$
$\mathcal{H}’$에 적용하면 $\mathcal{H}”$의 방정식이 됩니다. $\alpha$를 $\mathcal{H}’$에 적용하면
$$\alpha \mathcal{H}’ : y^2 = x^5 + \alpha^{-4} f_3 x^3 + \alpha^{-6} f_2 x^2 + \alpha^{-8} f_1 x + \alpha^{-10} f_0′.$$
$f_2 \neq 0$ 또는 $f_3 \neq 0$이면 $\mathcal{H}’$는 $\mathcal{H}”$와 동형인데, 이는 $\alpha^4 = 1$ 또는 $\alpha^6 = 1$일 때에만 가능합니다. 이는 적어도 $\mathcal{H}$와 $\mathcal{F} {2a}$에 대한 유효하지 않은 곡선의 동형 클래스가 쌍으로 비동형임을 증명합니다. 따라서 $f_2 \neq 0$ 또는 $f_3 \neq 0$일 때 적어도 $\mathcal{H}$와 $\mathcal{F} {2a}$에 대한 유효하지 않은 곡선의 동형 클래스가 $\left(\frac{\chi}{3} – 1\right)$개 있습니다. 최대 10개의 이러한 종 2 초타원 곡선의 동형 클래스가 $\mathbb{F}_q$에 대해 정의되기 때문에 우리는 논거에서 $f_2 = f_3 = 0$의 경우를 생략하는 것이 정당합니다(참조 [7]).
- 무효 곡선 공격
이산 대수 암호화 프로토콜에서 당사자 $\hat{B}$가 정적(장기) 개인 키 $b$를 사용하도록 요구하는 경우를 가정해 보겠습니다. 여기서 $\mathcal{H}$는 1세대 또는 2세대 초타원 곡선이고 P는 n차입니다. $\hat{B}$가 $P \in J_\mathcal{H}$임을 확인하지 못하면 적대자 $\mathcal{M}$가 $P \in J_\mathcal{H}$에 대한 유효하지 않은 곡선 또는 유효하지 않은 특이 곡선인 $P \in J_\mathcal{I}$를 선택하여 유효하지 않은 곡선 공격을 시작할 수 있습니다(그리고 $\mathcal{F} {1a}$ 또는 $\mathcal{F} {2a}$). 무효 곡선 공격에는 두 가지 유형이 있습니다.
소규모 부분군 공격[18]에서 $\mathcal{M}$은 $J_\mathcal{I}$가 작은 차수 $r$의 원소 $P$를 갖도록 $\mathcal{I}$를 선택합니다. 차수 $r$은 충분히 작아서 철저한 검색을 통해 $\langle P \rangle$의 이산대수 문제가 가능합니다. 일반적으로 $r$은 작은 소수입니다. 소규모 부분군 공격은 $\mathcal{M}$이 $bP$에서 파생된 양을 얻을 수 있는 상황(예: $k = H(bP)$, 여기서 $H$는 암호화 해시 함수)에서 사용할 수 있습니다. 이 경우 $\mathcal{M}$은 $k’ = k$가 될 때까지 모든 $i \in [0, r – 1]$에 대해 $k’ = H(iP)$를 계산한 후 $\mathcal{M}$이 $b \equiv i \pmod{r}$이라고 결론 내립니다. 다양한 곡선 $\mathcal{I}$(및 다양한 소수 $r$)에 대해 이 과정을 반복하면 중국 나머지 정리를 통해 $b$ 값을 복구할 수 있습니다.
대규모 하위 그룹 공격[20, p.58]에서 $\mathcal{M}$은 잘못된 곡선 $\mathcal{I}$를 선택하여 $J_\mathcal{I}$가 대차수 $t \approx n$의 원소 $P$를 갖고 $\langle P \rangle$의 이산대수 문제를 효율적으로 풀 수 있도록 합니다. 이는 $t$가 매끄럽거나 효율적인 DLP 알고리즘이 알려진 다른 그룹으로 $\langle P \rangle$에서 효율적으로 계산 가능한 매핑이 존재하는 경우입니다. 대규모 하위 그룹 공격은 $\mathcal{M}$이 그룹 원소 $bP$ 자체를 얻을 수 있는 상황에서 사용할 수 있습니다. 이 경우 $\mathcal{M}$은 $b \mod t$를 계산한 다음 효율적으로 $b$를 결정합니다.
위의 설정에서 $\mathcal{M}$이 무효 곡선 공격을 사용할 수 있는 데에는 두 가지 주요 이유가 있습니다. 첫째, 유효 그룹 $J_\mathcal{H}$의 요소 표현은 무효 그룹 $J_\mathcal{I}$의 요소 표현과 동일합니다. 둘째, 유효 그룹 $J_\mathcal{H}$에서 그룹 연산을 구현하면 수정 없이 무효 그룹 $J_\mathcal{I}$에 적용할 수 있습니다. 우리는 공개 키 검증을 수행하지 않아도 성공적인 두 가지 최근 제안된 이산 대수 프로토콜(Twin Diffie-Hellman 키 합의 체계와 XCR 서명 체계)에 대한 무효 곡선 공격을 설명합니다. 우리는 우리의 공격이 이러한 프로토콜의 약점을 보여주는 것이 아니라 공개 키 검증의 중요성을 강조하는 역할을 한다는 점을 강조합니다. 더 정확하게 말해서, 우리가 설명하는 공격은 공격자가 하드웨어를 조작하거나 레지스터를 수정할 것을 요구하지 않습니다. 공격은…