베날로 암호체계

베날로 크립토시스템(Benaloh Cryptosystem)은 1985년 조쉬(코헨) 베날로가 만든 골드와세르-미칼리 암호체계(GM)의 연장선이다.GM에 비해 Benaloh Cryptosystem의 주요 개선점은 긴 데이터 블록을 한 번에 암호화할 수 있는 반면 GM에서는 각 비트가 개별적으로 암호화된다는 것이다.^[1][2][3]

구성표 정의

다른 공용 키 암호 시스템과 마찬가지로 이 체계는 그룹$({\displaystyle Z\mathbb{}/n\mathbb{}}$ Z${\displaystyle {}^{}}$) ${\displaystyle {\ast }^{}}$ ${\$에서 작동하며 여기서$$ n은 두 개의 큰 프리임의 곱이다.이 계획은 동형이기 때문에 순응할 수 있다.

키 생성

블록 크기 r을 지정하면 다음과 같이 공용/개인 키 쌍이 생성된다.

1. Choose large primes p and q such that ${\displaystyle r\vert (p-1),\operatorname {gcd} (r,(p-1)/r)=1,}$ and ${\displaystyle \operatorname {gcd} (r,(q-1))=1}$
2. 설정 $n{\displaystyle }$= ${\displaystyle p}$ ${\displaystyle q}$ ,${\displaystyle \varphi }$=${\displaystyle }$( ${\displaystyle p}$-${\displaystyle 1}$) ${\displaystyle n=pq,\phi =(p-1)(q-1)}$
3. $y{\displaystyle {}^{}}$${\displaystyle }$${\displaystyle {\varphi }^{}}$ / ${\displaystyle r^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle 1}$ ${\displaystyle \mathrm{mod}}$ ${\displaystyle n}$$${\$displaystyle y\$in \$mathb {$Z$} _{$n}^{*}}을$$(를) ${\displaystyle {}_{}^{}}$하여$\$ / r 1 mod n ${\displaysty y^{\pi /r}\equiv 1\modn}$이(가 아님)를 선택하십시오$.$

참고: r이 복합적인 경우, 2011년^[4] Fousse 등에서는 위의 조건(즉, 원본 논문에 명시된 조건)이 정확한 암호 해독을 보장하기에 불충분하다는 점을 지적하였다. 즉, $D{\displaystyle }$(${\displaystyle E)(m)}$= ${\displaystyle m}$ ${\displaystyle D(E)(m)=m}$을 모든 경우에$$ 보장하기에 불충분하다는 점을 지적하였다.이를 다루기 위해 저자들은${\displaystyle }r{\displaystyle }$ = ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {p\mathrm{}}_{}}$2 … ${\displaystyle {}_{}}$ ${\displaystyle k_{}}${\$displaystyle r=p_{$1}$p_{2}\dots p_{k}}}$를 r의 주요 인자화(primary factorization)로$$ 하자고 제안한다.$각{\displaystyle }$ 요인 ${\displaystyle p_{}}$${\displaystyle {}_{}^{}}$$i{\displaystyle {}_{}}$ ${\$에$대해$ y ${\displaystyle {\varphi }^{}}$ / ${\displaystyle {p{}_{}}^{}}$ i 1 ${\displaystyle mod}$ n ${\$displaystyle y^{n$}^{n}}}$을$($를) 선택하면 y$$${\displaystyle {/}^{}}$ / p ${\displaystyle {i_{}}^{}1}$ / 1 mod n {\$displaystysty$ y$^{\p_{i}\neq 1mod$ n$\}.$

1. $x{\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {\varphi }^{}}$/ ${\displaystyle r^{}}$ ${\displaystyle \mathrm{mod}{}^{}}$ ${\displaystyle n}$ ${\displaystyle x=y^{\phi /r}\mod n}$ 설정

공용 키는 $y{\displaystyle ,}$ ${\displaystyle n}$ ${\displaystyle y,n$이고 개인 키는 $\varphi {\displaystyle ,}$ ${\displaystyle x}$ ${\displaystyle \phi,x}$ 입니다$.$

메시지 암호화

메시지 $m{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$:

1. 임의 $u{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$을(를) 선택하십시오.
2. 설정 $E{\displaystyle {}_{}}$ ${\displaystyle r_{}}$( ${\displaystyle m}$)${\displaystyle }$= y ${\displaystyle m^{}}$ ${\displaystyle u^{}}$ r ${\displaystyle \mathrm{mod}{}^{}}$ ${\displaystyle n}$ ${\displaystyle E_{r}(m)=y^{m^{r}\mod n}$

메시지 암호 해독

암호 텍스트 $c{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$의 암호를 해독하려면:

1. 계산 $a{\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {\varphi }^{}}$/ ${\displaystyle r^{}}$ ${\displaystyle mod}$ n ${\displaystyle a=c^{\phi /r}\mod n}$
2. 출력 $m{\displaystyle }$= ${\displaystyle \log }$ ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$(${\displaystyle }$) ${\displaystyle$ m$=\log _{x}(a$ 즉, $x{\displaystyle {}^{}}$ ${\displaystyle m^{}}$ ${\displaystyle {}^{}}$ a ${\displaystyle mod}$ n ${\displaystyle$ x$^{m}\equiv a\mod n}$과 같은 m을 찾으십시오.

암호 해독을 이해하려면 먼저 $m{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathbb{}}_{}}$ ${\$ 및$$ $u{\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ {$Z} _{n}^{*}}}$에 대해 다음 사항을$$ 확인하십시오.

${\displaystyle a=(c)^{\phi /r}\equiv (y^{m}u^{r})^{\phi /r}\equiv (y^{m})^{\phi /r}(u^{r})^{\phi /r}\equiv (y^{\phi /r})^{m}(u)^{\phi }\equiv (x)^{m}(u)^{0}\equiv x^{m}\mod n}$

To recover m from a, we take the discrete log of a base x. If r is small, we can recover m by an exhaustive search, i.e. checking if ${\displaystyle x^{i}\equiv a\mod n}$ for all ${\displaystyle 0\dots (r-1)}$. For larger values of r, the Baby-step giant-step algorithm can be used to recover m in ${\displaystyle }$${\displaystyle O}$( ${\displaystyle r}$) ${\displaystyle$ O$({\sqrt{r}}}$시간$$ 및 공간.

보안

이 계획의 보안성은 특히 n의 인자를 알 수 없는 z,r 및 n을 고려할 때, z가 r번째 잔류물 모드의 n인지, $즉{\displaystyle }$ z${\displaystyle x^{}}$ x r ${\displaystyle mod}$ n$${\$displaystyle z\equiv$ x$^{r}\mod$ n$}$과 같은 x가 존재하는지 여부를 계산적으로 확인할 수 없다$.$

참조