삼패스 프로토콜

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2018년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

암호학에서 메시지 전송을 위한 3패스 프로토콜은 암호화 키를 교환하거나 배포할 필요 없이 한 당사자가 제2자에게 안전하게 메시지를 보낼 수 있도록 하는 프레임워크다.이러한 메시지 패스를 사용하는 다양한 다른 알고리즘과 혼동해서는 안 된다 인증에 3개의 프로토콜은.

송신자와 수신자가 3개의 암호화된 메시지를 교환하기 때문에 3-통과 프로토콜이라고 불린다.최초의 3패스 프로토콜은 1980년경 Adi Shamir circa에 의해 개발되었으며, 이후 절에서 더 자세히 설명된다.3패스 프로토콜의 기본 개념은 각 당사자가 개인 암호키와 개인 암호 해독키를 갖는 것이다.양 당사자는 독자적으로 키를 사용하고, 먼저 메시지를 암호화한 다음, 메시지를 해독한다.

프로토콜은 암호화 함수 E와 암호 해독 함수 D를 사용한다.암호화 기능은 암호화 키 e를 사용하여 일반 텍스트 메시지 m을 암호화된 메시지 또는 암호문 E($e$,${\displaystyle m}$ ${\displaystyle )}$로 변경한다$.$ E( e , m ) ${\displaystyle$ E$(e,m)}.$ 각 암호화 키 e에 대응되는 암호 해독 키 d가 있어 암호 해독 기능을 $사용$하여 메시지를 복구할 수 있다. D${\displaystyle (}$ ${\displaystyle d}$, ${\displaystyle E}$ ( ${\displaystyle e}$ , E ${\displaystyle (,}$ m${\displaystyle }$)${\displaystyle }$= ${\displaystyle m}$ ${\displayst$.$yle D(d,E(e,m)=m$ 가끔 암호화 기능과 암호 해독 기능이 동일할 때도 있다.

암호화 기능과 암호 해독 기능이 3-통과 프로토콜에 적합하려면 메시지 m, 해당 암호 해독 키 d를 가진 암호화 키 e 및 모든 독립 암호화 키 k${\displaystyle (d,}$ E ${\displaystyle (}$ )${\displaystyle }$= ${\displaystyle E}$( , ${\displaystyle E}$ (${\displaystyle }$) = ${\displaystyle E}$ ( , ${\displaystyle m}$ ) = E ( k${\displaystyle }$, m${\displaystyle }$) ${\displaystyle D(d,$ E ($k, E, m)$를 가진 속성을 가져야 한다.$=E(k,m$ 다시 말해, 키 k를 사용한 두 번째 암호화가 수행되었음에도 불구하고 키 e로 첫 번째 암호화를 제거할 수 있어야 한다.이것은 항상 교환 암호화를 통해 가능할 것이다.정류형 암호화는 주문에 독립적인 암호화를 말하며, ${\displaystyle 즉}$ $E{\displaystyle (,}$ ${\displaystyle E(,}$ ${\displaystyle b,}$ m${\displaystyle }$)${\displaystyle }$= E${\displaystyle (,}$ ${\displaystyle E(,}$ ${\displaystyle m}$ )${\displaystyle E(a,E(b,m))$를 만족한다.$=E(b,E(a,m)}$ 모든 암호화 키 a 및 b와 모든 메시지 m에 대해$$동시 암호화로 $D{\displaystyle (d}$, E${\displaystyle }$( ,${\displaystyle E}$(${\displaystyle }$, ${\displaystyle m}$ ) )${\displaystyle }$= D${\displaystyle }$( ,${\displaystyle E}$( , ${\displaystyle E}$ (${\displaystyle }$,${\displaystyle m}$)${\displaystyle }$) ${\displaystyle D(d,$ E$(k,E(e,m)))$를 만족한다.$=D(d,E(e,E(k,m)))}}$.

3패스 프로토콜은 다음과 같이 동작한다.

1. 송신자는 개인 암호화 키 s와 해당 암호 해독 키 t를 선택한다.송신자는 키 s로 메시지 m을 암호화하고 암호화된 메시지 $E{\displaystyle (s}$, m$){\displaystyle E(s,m)}$를 수신기로$$ 송신한다.
2. 수신자는 개인 암호화 키 r과 해당 암호 해독 키 q를 선택하고 키 r과 함께$$ 첫 번째 $메시지{\displaystyle }$ E${\displaystyle (s}$ ${\displaystyle ,}$ $){\$$displaystyle$ $E($${\displaystyle s}$$,m)}$를 슈퍼암호화하여 이중 암호화된 $메시지$ E$r$ ${\displaystyle ,}$ $(, E,m)}$를 송신자에게 다시$$ 보낸다.
3. 송신자는 키 t로 두 번째 메시지를 해독한다.$D{\displaystyle (t,}$ ${\displaystyle E(}$ ${\displaystyle r,}$ ${\displaystyle E(}$ ${\displaystyle s,}$ ${\displaystyle m}$)${\displaystyle }$) =${\displaystyle E(}$ ${\displaystyle r}$,${\displaystyle m}$ )$${\$displaystyle D(t,$E$(r,E(s,m))))$ 위에 설명된 정류율 속성 때문에$=E(r,m)}$은(는) 수신자의 개인 키로만 암호화된 메시지 입니다.송신자는 이것을 수신자에게 보낸다.

수신자는 이제 키 q, ${\displaystyle 즉}$ ${\displaystyle D}$ (${\displaystyle q,}$ E${\displaystyle }$( ${\displaystyle r,}$ m${\displaystyle }$)${\displaystyle }$= m ${\displaystyle D(q,E(r,m)=m}$을(를) 사용하여 메시지를 해독할 수 있다.

송신자의 개인 키 s와 t와 관련된 모든 작업은 송신자에 의해 수행되며, 수신자의 개인 키 r과 q와 관련된 모든 작업은 수신자에 의해 수행되므로, 어느 쪽도 상대방의 키를 알 필요가 없다.

샤미르 3패스 프로토콜

최초의 3패스 프로토콜은 1980년에 개발된 샤미르 3패스 프로토콜이다.송신자와 수신자가 어떤 키도 교환하지 않기 때문에 샤미르 No-Key Protocol이라고도 부르지만, 프로토콜은 송신자와 수신자에게 메시지의 암호화 및 암호 해독을 위한 2개의 개인 키를 보유하도록 요구한다.샤미르 알고리즘은 암호화 기능과 암호 해독 기능 둘 다로 큰 프라이밍을 사용한다.즉, E(e,m) = m m^e mod p와 D(d,m) = m^d m mod p이고 여기서 p는 큰 prime이다.gcd(e,p-1) = 1 범위의 암호화 지수 e에 대해 de de 1(mod p-1)과 같은 해당 암호 해독 지수 d를 선택한다.D(d,E(e,m) = m모드^de p = m인 것은 페르마의 작은 정리에서 따온 것이다.

샤미르 프로토콜은 E(a,E(b,m) = m mod^ab p = m^ba m mod p = E(b,E(a,m)) 이후 원하는 공통성 속성을 가진다.

매시-오무라 암호체계

매시-오무라 암호 시스템은 제임스 매시와 짐 K에 의해 제안되었다. 1982년 샤미르 의정서에 대한 개선 가능성으로 오무라.Massey-Omura 방법은 암호화와 암호 해독 기능 모두 GF(2)의ⁿ 지수를 사용한다.그것은 갈루아 분야에서 계산이 이루어지는 E(e,m)=m과^e D(d,m)=m이다^d.0<e<2-1ⁿ 및 gcd(e,2-1ⁿ)=1을 가진 암호화 지수 e의 경우 해당 암호 해독 지수는 de de 1(mod 2-1)과 같은ⁿ d이다.갈루아장 GF(2ⁿ)의 승법군은 2-1ⁿ 라그랑주의 정리를 가지고 있으므로 GF(2ⁿ)^*의 모든 m에 대해^de m=m이라는 것을 암시한다.

갈루아장 GF(2ⁿ)의 각 원소는 각 기본 벡터가 앞의 원소의 제곱인 정상 기준에 걸쳐 이항 벡터로 표현된다.즉, 기본 벡터는 v¹, v², v⁴, v, ...이고⁸ 여기서 v는 최대 순서의 필드 요소다.이 표현을 사용함으로써, 2의 힘에 의한 지수를 주기적인 교대조에서 달성할 수 있다.이것은 m을 임의의 힘으로 끌어올릴 수 있다는 것을 의미하며, 최대 n교대 및 n의 배수로 달성할 수 있다.게다가 여러 가지 승수를 병행할 수 있다.이를 통해 여러 개의 승수를 구현해야 하는 비용을 들여 하드웨어 실현 속도를 높일 수 있다.

보안

A necessary condition for a three-pass algorithm to be secure is that an attacker cannot determine any information about the message m from the three transmitted messages ${\displaystyle E(s,m)}$, ${\displaystyle E(r,E(s,m))}$ and ${\displaystyle E(r,m)}$.

위에서 설명한 샤미르 알고리즘과 Massey-Omura 알고리즘에서 사용되는 암호화 기능의 경우, 보안은 유한한 분야에서 이산 로그의 계산의 어려움에 의존한다.공격자가 샤미르 방법의 경우 GF(p)로 이산 로그 또는 매시-오무라 방법의 경우 GFⁿ(2)로 계산할 수 있다면 프로토콜이 깨질 수 있다.키 s는 메시지^r m과^rs m으로 계산할 수 있다.s가 알려지면 암호 해독 지수 t를 계산하기 쉽다.그러면 공격자는 가로챈 메시지 m을^s t전원으로 올려 m을 계산할 수 있었다.K. 사쿠라이와 H.시즈야는 어떤 가정 하에서 Massey-Omura 암호체계를 깨는 것이 Diffie-와 동등하다는 것을 보여준다.지옥의 가정.

인증

위에서 설명한 3패스 프로토콜은 어떠한 인증도 제공하지 않는다.따라서, 추가적인 인증 없이, 프로토콜은 상대방이 거짓 메시지를 만들거나, 진짜 전송된 메시지를 가로채서 대체할 수 있는 능력이 있다면, 중간 공격에 취약하다.

참조

• 미국 특허 4,567,600, 매시-오무라 암호시스템에 대한 미국 특허
• Konheim, Alan G. (1981). Cryptography: A Primer. pp. 346–347.
• Menezes, A.; VanOorschot, P.; Vanstone, S. (1996). Handbook of Applied Cryptography. pp. 500, 642.
• Sakurai, K.; Shizuya, H. (1998). "A Structural Comparison of the Computational Difficulty of Breaking Discrete Log Cryptosystems". Journal of Cryptology. 11: 29–43. doi:10.1007/s001459900033.