케이리-퍼서 알고리즘

이 기사는 대체로 또는 전적으로 단일 출처에 의존한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 추가 출처에 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. 출처 찾기: "Cayley-Purser 알고리즘" – 뉴스 · 신문 · 책 · 학자 · JSTOR (1919년 10월)

케이리-퍼어 알고리즘은 더블린 데이터 보안 회사인 볼티모어 테크놀로지의 창업자 마이클 퍼서의 미발표 저작에 기초해 1999년 초 16세의 아일랜드 여성 사라 플래너리가 발표한 공개키 암호 알고리즘이다.플래너리는 수학자 아서 케이리를 위해 그것을 이름지었다.이후 공개키 알고리즘으로서 결함이 있는 것으로 밝혀졌지만, 상당한 언론의 관심의 대상이었다.

역사

볼티모어 테크놀로지스와의 업무 경험 배치 중에 Flannery는 마이클 퍼서(Michael Purser)에 의해 발표되지 않은 논문을 보여주었는데, 이 논문은 비확정적 곱셈을 사용한 새로운 공개키 암호 체계를 개략적으로 설명했다.그녀는 이 계획의 시행을 매카티카로 써 달라는 요청을 받았다.

이 배치 이전에 Flannery는 카이사르 암호에서 RSA에 이르는 이미 존재하는 암호기술을 설명하는 프로젝트로 1998년 ESAT 젊은 과학자 및 기술 전시회에 참석했었다.이것은 그녀가 1998년 미국에서 열린 인텔 국제 과학 및 엔지니어링 박람회에 참가할 기회를 포함한 인텔 학생상을 수상했다.자신의 전시 프로젝트에 추가할 어떤 독창적인 작품이 필요하다고 느낀 플래너리는 마이클 퍼서에게 그의 암호 체계를 바탕으로 한 작품을 포함시킬 수 있는 허가를 요청했다.

수학자 아버지의 조언에 따라 플란네리는 행렬을 이용하여 퍼서의 계획을 실행하기로 결정했다. 매트릭스 곱셈은 비확실성이라는 필수적인 속성을 가지고 있기 때문이다.결과 알고리즘은 곱셈에 의존하므로 지수 단계를 사용하는 RSA 알고리즘보다 훨씬 빠를 것이다.그녀의 Intel Science Fair 프로젝트를 위해 Flannery는 RSA와 그녀의 새로운 Cayley-Purser 알고리즘을 사용하여 동일한 일반 텍스트가 암호화된 데모를 준비했고, 그것은 실제로 상당한 시간 단축을 보여주었다.

1999년 ESAT 젊은 과학자와 기술 전시회로 돌아온 플래너리는 케이리-퍼서의 런타임을 공식화하고 알려진 다양한 공격들을 분석했는데, 그 중 어느 것도 효과적이라고 결정된 것은 없었다.

플래너리는 새로운 암호 시스템이 보안 시스템으로 인정되기 전에 시간의 테스트를 견뎌야 한다는 것을 알고 케이리-퍼서 알고리즘이 RSA를 대체할 것이라는 어떠한 주장도 하지 않았다.그러나 언론은 그다지 신중하지 않았고 그녀가 ESAT 전시회에서 1등을 했을 때, 전 세계의 신문들은 한 어린 소녀 천재가 암호학을 혁명적으로 발전시켰다는 이야기를 보도했다.

사실 그 직후 알고리즘에 대한 공격이 발견되었지만 그녀는 그것을 분석했고 그녀가 주요 상을 받은 유럽 전역의 대회를 포함한 후기 대회에서 부록으로 포함시켰다.

개요

이 논의에서 사용된 표기법은 플란네리의 원본 논문과 같다.

키 생성

Cayley-Purser는 RSA와 마찬가지로 두 개의 큰 primes p와 q와 그들의 제품 n인 semiprime을 생성하는 것으로 시작한다.다음으로, 정수 요소와 모듈식 산술 모드의 2×2 행렬의 일반 선형 그룹인 GL(2,n)을 고려한다.예를 들어, n=5일 경우 다음과 같이 쓸 수 있다.

${\displaystyle {\begin{bmatrix}0&1\\2&3\end{bmatrix}}+{\begin{bmatrix}1&2\\3&4\end{bmatrix}}={\begin{bmatrix}1&3\\5&7\end{bmatrix}}\equiv {\begin{bmatrix}1&3\\0&2\end{bmatrix}}}$

${\displaystyle {\begin{bmatrix}0&1\\2&3\end{bmatrix}}{\begin{bmatrix}1&2\\3&4\end{bmatrix}}={\begin{bmatrix}3&4\\11&16\end{bmatrix}}\equiv {\begin{bmatrix}3&4\\1&1\end{bmatrix}}}$

이 그룹은 (p-1²)(p-p²)(q-1²)(q-q²)와 같은 큰 순서(대규모 세미프라임 n의 경우)를 가지기 때문에 선택된다.

$\chi {\displaystyle }$ ${\displaystyle \chi }$ 및 $\alpha {\displaystyle }$ ${\displaystyle \alpha$ }을$($를) ${\displaystyle {}^{}}$- 1 α ${\displaystyle \alpha {}^{}}$α α ${\displaystyle \chi }$ ${\displaystyle \chi \-$1}$not =\not$ =\alpha $\chi$ $\}$과 같이 선택한 GL(2,n)의 행렬 두 개로$$ 두 개를 두 개로 두 개로 두 개로 두 개로 한다.

${\displaystyle \cHI ^{-1}\cHI ^{-1}$

$\displaystyle \cHI ^{r}.}$

공개 키는 $n{\displaystyle }$ ${\displaystyle n$ $\alpha {\displaystyle }$ ${\displaystyle \alpha },$$\beta {\displaystyle }$ ${\displaystyle \beta },$$\gamma {\displaystyle }$ ${\displaystyle \gamma }$이다$.$ 개인 키는 $\chi {\displaystyle }$ ${\displaystysty$ sty $\chy$ \chychi $\backslash \}$이다.

암호화

전송자는 무작위 자연수 s를 생성하고 다음과 같은 계산으로 시작한다.

${\displaystyle \cHB =\cHB^{s}}$

$\displaystyle \epsilon =\cHB ^{-1}\cHB \cHB \cHB }$

$\displaystyle \kappa =\properties ^{-1}\put \properties }$

그런 다음 메시지를 암호화하기 위해 각 메시지 블록은 숫자로 암호화되며(RSA와 같이) 한 번에 4개씩 일반 텍스트 매트릭스 $\mu {\displaystyle }$ ${\displaystyle \mu }$의 요소로 배치된다$.$ 각 $\mu {\displaystyle }$ ${\displaystyle \mu }$은(는) 다음을 사용하여 암호화된다$$.

$\displaystyle \mu '=\kappa \mu \kappa.}$

그런 다음 $\mu {\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$과($와{\displaystyle }$) ${\displaystyle \epsilon$}이(가) 수신기로 전송된다$$.

암호 해독

수신기는 다음을 통해$$ 원래 일반 텍스트 매트릭스 $\mu {\displaystyle }$ ${\displaystyle \mu }$을(를) 복구한다.

$\displaystyle \lambda =\chi ^{-1}\epsilon \chi ,}$

$\displaystyle \mu =\da \mu '\da.}$

보안

개인$$ 키 $\chi {\displaystyle }$ ${\displaystyle \gamma}$에서 개인 키 χ ${\displaystyle$ \$chi}$을(를) 복구하는 것은 계산상 불가능하며 최소한$$ 제곱근 mod n을 찾는 것만큼 어렵다(이차적 잔류물 참조).$\alpha {\displaystyle }$ ${\displaystyle \alpha }$ 및$$ $\beta {\displaystyle }$ ${\displaystyle \beta }$ 시스템$$ ${\displaystyle \beta }$-${\displaystyle 1^{}}$ ${\displaystyle {}^{}}$ - 1 ${\displaystyle {}^{}}$ ${\displaystyle \chi \beta =\lapa ^{-1} }$을(를)에서 복구할 수 있지만, 그룹 내 요소들의 순서가 큰 한 이 시스템에 대한 해결책 수는 크다.에멘트

그러나 다음과 같은 조합에서$$ $d{\displaystyle }$ ${\displaystyle$ d$}$을(를) 해결하여$$ $\chi {\displaystyle }$ ${\displaystyle \chi }$의 다중 $\chi$을 찾으면 시스템이 깨질 수 있다.

${\displaystyle d\left(\displaystyle d\lift(\reft -\reft ^{-1}\right)\equiv \left(\pmod {n}})}$

일부 $i{\displaystyle }$, ${\displaystyle j}$ ${\displaystyle \in }$ ${\displaystyle \gamma }$ ${\$ 및$$ $x{\displaystyle }$, ${\displaystyle y}$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$ x$,y\in \mathb {Z} _{n}}}}$에 대해 해결책이 존재하는지 확인하십시오.

${\displaystyle x\left(\displaystyle x\pmod {n})^{-1-\laim_{ij}\pmod {n}.}$

If ${\displaystyle d}$ is known, ${\displaystyle d\mathrm {I} +\gamma =\chi '}$ — a multiple of ${\displaystyle \chi }$. Any multiple of ${\displaystyle \chi }$ yields ${\displaystyle \lambda =\kappa ^{-1}=v^{-1}\chi ^{-1}\epsilon v\chi }$. This present아직 조정되지 않은 체제에 치명적인 약점이다.

이 결함은 송신자가 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$을(를) 비밀리에$$ 전송하는 경우, 알고리즘이 개인키/공용키 혼합 알고리즘으로 사용하는 것을 배제하지 않지만, 이 접근방식은 공개키 암호화 방식을 사용하여 대칭 암호화 키를 전송한 다음 대칭 암호화로 전환하는 일반적인 접근방식에 비해 이점이 없다.Cayley-Purser보다 빠른.

참고 항목

• 비확정암호법

참조

• 사라 플래너리와 데이비드 플래너리.코드: 수학 여행. ISBN0-7611-2384-9