비확정암호법

비확정암호학은 암호 원점, 방법 및 시스템이 비확정적인 세미그룹, 그룹, 링과 같은 대수적 구조에 기초하는 암호학의 영역이다.암호 목적을 위한 비확정 대수 구조의 가장 초기 적용 중 하나는 암호 프로토콜을 개발하기 위해 브레이드 그룹을 사용하는 것이었다.후에 톰슨 그룹, 다순환 그룹, 그리고르추크 그룹, 매트릭스 그룹과 같은 몇 개의 다른 비협정적 구조가 암호 응용 프로그램의 잠재적 후보로 확인되었다.비확약적 암호체계와는 대조적으로, 현재 널리 사용되고 있는 RSA 암호체계인 Diffie–와 같은 공개키 암호체계.헬만 키 교환과 타원 곡선 암호화는 숫자 이론에 기초하므로 교호 대수 구조에 의존한다.

키 교환, 암호화 해독, 인증 등 다양한 암호 문제를 해결하기 위해 비암호화 프로토콜이 개발되었다.이 프로토콜들은 대응 사례의 해당 프로토콜과 매우 유사하다.

일부 비명령 암호 프로토콜

이러한 프로토콜에서 G는 비아벨라 그룹이라고 가정할 수 있을 것이다.w와 a가 G의 요소인 경우, 표기^a w는 원소가 기다리고⁻¹ 있음을 나타낼 것이다.

키 교환 프로토콜

고, 리, 기타 등등으로 인한 의전.

고씨, 리씨 등 때문에 다음과 같은 의전은 앨리스와 밥에게 공통된 비밀키 K를 확립한다.

1. G의 요소 w가 발표된다.
2. 모든 A in A와 B에 대해 ab = ba와 같은 G의 두 부분군 A와 B가 간행된다.
3. 앨리스는 A에서 원소 a를 선택하고 w를^a 밥에게 보낸다.앨리스는 일병이다.
4. 밥은 B에서 원소 b를 고르고 w를 앨리스에게^b 보낸다.밥은 b를 비밀로 한다.
5. 앨리스는 K = (w^b)^a = w를^ba 계산한다.
6. 밥은 K' = (w^a)=^bw를^ab 계산한다.
7. ab = ba, K = K'이기 때문이다.앨리스와 밥은 공통 비밀키 K를 공유한다.

안셀-안셀-골드펠트 프로토콜

이것은 비아벨리안 그룹 G를 이용한 키 교환 프로토콜이다.고씨, 이씨 등 때문에 의정서의 경우처럼 G의 통근 서브그룹 A와 B의 2개가 필요하지 않기 때문에 의미가 크다.

1. 원소 a₁, a₂, ..... a_k, b₁, b₂, g에서 b가_m 선택되어 간행된다.
2. 앨리스는 G에서 개인 x를 a₁, a₂, a, a_k;, 즉 x = x( a₁, a, a, a₂, . )의_k 단어로 선택한다.
3. 앨리스는 b₁^x, b₂^x, , b를 밥에게_m^x 보낸다.
4. 밥은 G에서₁ b, b₂, . . . b의_m 단어로 개인 y를 선택한다. 그것은 y = y(b₁, b₂, b_m, . . b )이다.
5. 밥은 앨리스에게 a₁^y₂^y, a, ., a를_k^y 보낸다.
6. 앨리스와 밥은 공통 비밀키 K = xyxy를⁻¹⁻¹ 공유한다.
7. 앨리스는 x ( a₁^y, a₂^y, . . . , a_k^y ) = y xy를⁻¹ 계산한다.그것을 x로⁻¹ 미리 멀티플을 하면 앨리스는 K를 얻게 된다.
8. 밥은 y(b₁^x, b₂^x, . . . b_m^x) = xyx를⁻¹ 계산한다.그것을 y로⁻¹ 미리 멀티핑한 다음 역수를 취하면 밥이 K를 받는다.

스틱엘의 키 교환 프로토콜

이 프로토콜의 원래 공식화에서 사용된 그룹은 유한한 영역에 걸친 변환 불가능한 행렬의 그룹이었다.

1. G를 공공의 비아벨리안 유한집단이 되게 하라.
2. a, b를 ab ≠ ba와 같은 G의 공공요소가 되게 하라.a와 b의 주문을 각각 N과 M으로 한다.
3. 앨리스는 n < N>과 m < M> 두 개의 난수를 선택하고 u = ab을^mn 밥에게 보낸다.
4. 밥은 r < N>과 s < M> 두 개의 난수를 골라 v = ab을^rs 앨리스에게 보낸다.
5. 앨리스와 밥이 공유하는 공통키는 K = ab이다^{m + rn + s}.
6. 앨리스는 K = avb로^mn 키를 계산한다.
7. 밥은 K = aub로^rs 키를 계산한다.

암호화 및 암호 해독 프로토콜

이 프로토콜은 비밀 메시지를 암호화한 다음 비명령 그룹을 사용하여 암호를 해독하는 방법을 설명한다.앨리스가 밥에게 비밀 메세지 m을 보내게 하라.

1. G를 비협조적인 그룹이 되게 하라.A와 B는 A와 B의 모든 A와 B에 대해 ab = ba와 같은 G의 공공 하위집단이 되도록 한다.
2. G에서 원소 x를 선택하고 발행한다.
3. 밥은 A에서 비밀키 b를 선택하고 z = x를^b 공개키로 발행한다.
4. 앨리스는 B에서 무작위 r을 선택하고 t = z를^r 계산한다.
5. 암호화된 메시지는 C = (x^r, H(t) $\oplus {\displaystyle }$ ${\displaystyle \oplus }$)이며, 여기서 H는 어떤 해시함수이고 $\oplus {\displaystyle }$ ${\displaysty \oplus }$은 XOR 작업을 나타낸다$$.앨리스는 밥에게 C를 보낸다.
6. C의 암호를 해독하기 위해 Bob은 다음과 같이 t를 복구한다: (x^r)^b = x^rb = x^br = (x^b)^r = z = t^r.앨리스가 보내는 일반 문자메시지는 P = (H(t) $\oplus {\displaystyle }$ ${\displaystyle \oplus }$ ) $\oplus {\displaystyle }$ ${\displaystyle \oplus }$(t) = m이다.

인증 프로토콜

밥이 메시지의 보낸 사람이 정말 앨리스인지 확인하고 싶도록 하자.

1. G를 비협정 집단이 되게 하고 A와 B를 모두 A와 B에 대해 ab = ba와 같이 G의 하위집단이 되게 한다.
2. G에서 w 요소를 선택하고 게시한다.
3. 앨리스는 A에서 개인 s를 선택하고 쌍(w, t )을 발표한다. 여기서 t = w .
4. 밥은 B에서 r을 선택하고 도전 w ' = w를^r 앨리스에게 보낸다.
5. 앨리스는 응답 w ' = (w ')^s를 밥에게 보낸다.
6. 밥은 w ' = t^r. 이것이 사실이라면 앨리스의 정체가 성립된다.

프로토콜의 보안 기반

위에서 제시된 다양한 프로토콜의 보안성과 강도에 대한 근거는 다음과 같은 두 가지 문제의 난이도에 있다.

• 결합 결정 문제(결합 문제라고도 함):그룹 G에서 u와 v의 두 요소에 따라 G에 v = u^x, 즉 v = x⁻¹ ux와 같은 요소 x가 존재하는지 여부를 결정한다.
• 결합 검색 문제:그룹 G에서 u와 v의 두 요소가 주어진 경우, v = u^x−1, 즉 v = x ux와 같은 요소 x를 G에서 찾는다.

만약 결합 검색 문제를 해결할 알고리즘이 알려져 있지 않다면, x → u^x 함수는 단방향 함수로 간주할 수 있다.

플랫폼 그룹

특정 암호 프로토콜에서 사용되는 비명령적 그룹을 그 프로토콜의 플랫폼 그룹이라고 한다.일정한 속성을 가지는 그룹만이 비 커밋 암호 프로토콜의 구현을 위한 플랫폼 그룹으로 사용할 수 있다.G는 특정 비협정 암호 시스템의 플랫폼 그룹으로 제안된 그룹이 되도록 하자.다음은 G에 기대되는 속성 목록이다.

1. G 그룹은 유명하고 학식이 많은 그룹이어야 한다.
2. G의 문제라는 단어는 결정론적 알고리즘에 의한 빠른 해법이 있어야 한다.G의 요소에 대해서는 효율적으로 계산할 수 있는 "정상 형태"가 있어야 한다.
3. G의 xy 제품에서 x와 y 인자를 회복하는 것은 불가능할 것이다.
4. G의 길이 n 요소의 수는 n의 어떤 다항식보다 더 빨리 증가해야 한다(여기서 "길이 n"은 그룹 요소를 나타내는 단어의 길이임).

플랫폼 그룹의 예

브레이드 그룹

n을 양의 정수가 되게 하라.브레이드 그룹 B는_n x₁, x₂, . . . . x에_n-1 의해 생성된 그룹이며, 다음과 같은 프레젠테이션을 가지고 있다.

${\displaystyle B_{n}=\left\langle x_{1},x_{2},\ldots ,x_{n-1}{\big }x_{i}x_{j}=x_{j}x_{i}{\text{ if }} i-j >1{\text{ and }}x_{i}x_{j}x_{i}=x_{j}x_{i}x_{j}{\text{ if }} i-j =1\right\rangle }$

톰프슨 그룹

톰슨의 그룹은 다음과 같은 무한 프레젠테이션을 가진 무한 그룹 F이다.

${\displaystyle F=\\좌측\langle x_{0}x_{1}x_{2},\ldots {\big }x_{k}x_{k}=x_{n+1}{n+1}{}}}{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}"에 대한 {\text:$

그리고르추크족

T는 무한 뿌리 이진 트리를 나타내도록 한다.정점의 V는 모든 유한 이진 시퀀스의 집합이다.렛 A(T)는 T의 모든 자동모형의 집합을 나타낸다(T의 자동모형은 연결성을 보존하는 정점을 허용한다).그리고르추크의 그룹 γ은 다음과 같이 정의된 자동형 a, b, c, d에 의해 생성되는 A(T)의 부분군이다.

• ${\displaystyle a(b_{1},b_{2},\ldots,b_{n}=(1-b_{1},b_{2},\ldots,b_{n})}$
• ${\displaystyle b(b_{1},b_{2},\ldots},b_{n}}={\\cHB}(b_{1},1-b_{2},\ldots,b_{n}},{n}, if }b_{1},c(b_{2},\ldots_{n})={n})={n}).&{\text{{}b_{1}=1\end{case}}}$
• ${\displaystyle c(b_{1},b_{2},\ldots},b_{n}}={\\cHB}(b_{1},1-b_{2},\ldots,b_{n}},{n}, if }b_{1}, d(b_{2},/ldots})={n}).&{\text{{}b_{1}=1\end{case}}}$
• ${\displaystyle d(b_{1},b_{2},\ldots,b_{n}}={\data}(b_{1}, b_{n},\dots, b_{n})={}{}}}{}}}}{},{},{},},}, {n},{},},{},},},},{},},},{},},},},},},},},}, {\text}=,}=,}=,}=,},&{\text{{}b_{1}=1\end{case}}}$

아르틴 그룹

A(Artin 그룹 A)는 다음과 같은 프레젠테이션을 가진 그룹이다.

${\displaystyle A(\Gamma )=\left\langle a_{1},a_{2},\ldots,a_{n} \mu_{ji}{\text{{{{}}}} \mu _{1}\leq i<j\leq n\rigregle }}}}}}}}}}}}}.$

여기서 ${\displaystyle {\mathrm{\mu ij}}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle a_{}}$… ${\displaystyle \mu _{ij}=a_{i}a_{$j}a_${j}a_{j}\ldots$}($$${\displaystyle {mi}_{}}$ j$${\$displaystym$ $m_{ij}}}$ 인수$$) $및{\displaystyle {}_{}}$ ${\displaystyle m_{}}$j = ${\displaystyle {}_{}}$ ${\displaystyle j_{}}${\$daysty$

행렬 그룹

F를 유한한 장으로 하자.F에 대한 행렬 그룹은 특정 비 커밋 암호 프로토콜의 플랫폼 그룹으로 사용되어 왔다.

반간접 제품

^[1]

참고 항목

• 그룹 기반 암호화

추가 읽기

1. Alexei Myasnikov; Vladimir Shpilrain; Alexander Ushakov (2008). Group-based Cryptography. Berlin: Birkhäuser Verlag.
2. Zhenfu Cao (2012). New Directions of Modern Cryptography. Boca Raton: CRC Press, Taylor & Francis Group. ISBN 978-1-4665-0140-9.
3. Benjamin Fine; et al. (2011). "Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems". arXiv:1103.4093 [cs.CR].
4. Alexei G. Myasnikov; Vladimir Shpilrain; Alexander Ushakov (2011). Non-commutative Cryptography and Complexity of Group-theoretic Problems. American Mathematical Society. ISBN 9780821853603.

참조