블럼-골드와세르 암호체계

블럼-골드와서(BG) 암호체계는 1984년 마누엘 블럼과 샤피 골드와서가 제안한 비대칭 키 암호화 알고리즘이다.Blum-Goldwasser는 일정한 크기의 암호문을 확장한 확률론적이고 의미론적으로 안전한 암호체계다.암호화 알고리즘은 키스트림을 생성하기 위해 BBS(Blum-Blum-Shub) 사이비 무작위 숫자 생성기를 사용하여 XOR 기반 스트림 암호를 구현한다.암호 해독은 초기 시드를 찾아 키스트림을 재구성하기 위해 개인 키를 사용하여 BBS 발전기의 최종 상태를 조작함으로써 이루어진다.

BG 암호 체계는 정수 인자화의 가정된 난해성에 기초하여 의미론적으로 안전하다. 특히 복합 $값{\displaystyle }$N = ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle$N=$pq}$을(를$$) 인수하면 $p{\displaystyle }$ ,$$q {\$displaystyle p,q$}이(가$$) 큰 primes이다.BG는 Goldwasser-Mecali 암호체계와 같은 이전의 확률론적 암호화 체계보다 여러 가지 장점을 가지고 있다.첫째, 그것의 의미적 보안은 추가적인 가정(예: 2차 잔류성 문제의 경도 또는 RSA 문제)을 요구하지 않고 정수 인자화만으로 감소한다.둘째, BG는 저장 측면에서 효율적이어서 메시지 길이에 상관없이 일정한 크기의 암호문 확장을 유도한다.BG는 계산 측면에서도 비교적 효율적이며, RSA와 같은 암호 시스템과 비교해도 요금이 잘 나온다(메시지 길이와 지수 선택에 따라 다름).그러나 BG는 적응형 선택 암호문 공격에 매우 취약하다(아래 참조).

암호화는 확률론적 알고리즘을 사용하여 수행되기 때문에, 주어진 일반 텍스트는 암호화될 때마다 매우 다른 암호문을 생성할 수 있다.이것은 적수가 가로채는 메시지를 알려진 암호문자의 사전과 비교함으로써 인식하지 못하게 하기 때문에 상당한 이점을 가지고 있다.

작전

Blum-Goldwasser 암호 체계는 세 가지 알고리즘, 즉 공용 키와 개인 키를 생성하는 확률론적 키 생성 알고리즘, 확률론적 암호화 알고리즘, 결정론적 암호 해독 알고리즘으로 구성된다.

키 생성

공용 및 개인 키는 다음과 같이 생성된다.

1. ${\displaystyle \mathrm{큰}}$ 고유 소수 $p{\displaystyle }$ ${\displaystyle p}$과($와{\displaystyle }$$)$$$q {\$displaystyle p\equiv$ 3${\bmod}$과(와) ${\displaystyle \mathrm{q}}$3 ${\displaystyle mod}$ ${\displaystyle 4\mathrm{}}$ ${\$과(와) 같은 두$$ 개의 큰 고유 소수 p {\$displaystystylease q}$을 선택하십시오$.$
2. 계산 $n{\displaystyle }$= ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle n=pq}$^[1].

그런 $다음{\displaystyle }$ n$${\$displaystyle n$}이(가) 공개 키이고$$ 쌍${\displaystyle (p}$ ,${\displaystyle q}$ )$${\$displaystyle(p,q)}$이(가) 개인 키입니다.

암호화

메시지 $M{\displaystyle }$ ${\displaystyle M}$은(는) 다음과 같이$$ 공개 키 $n{\displaystyle }$ ${\displaystyle n}$을(를) 사용하여 암호화된다$$.

1. 블록 크기를 비트로 $계산$한다. h${\displaystyle }$=${\displaystyle o}$ ${\displaystyle {}_{}}$ ${\displaystyle {o\mathrm{}}_{}}$ ${\displaystyle g}$ ${\displaystyle 2}$ ( ${\displaystyle {}_{}{o\mathrm{}}_{}}$ ${\displaystyle g}$2 (n )${\displaystyle \rfloor }$⌋ {\$displaystyle$ h$=\lfloor log_{2}(n$)\rfloor $\}.$
2. $M{\displaystyle }$ ${\$$displaystyle$ $M}$을(를) $일련$의 t ${\$$displaystyle t}$$블록$ m ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{m\mathrm{}}_{}}$2${\displaystyle }$, ${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle t_{}}${\$displaystyle m_{1}, m_{2$$$$},\dots,$$m_$${$t$}}}$로 변환하십시오$.$
3. 임의 정수 < ${\displaystyle r<n}$을(를) 선택하십시오
4. 계산 $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle mod}$ ${\displaystyle n}$ ${\$
5. $i{\displaystyle }$ ${\displaystyle i}$의 경우 1 ~ t ${\displaystyle t}$
   1. 계산 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}mod}$ ${\displaystyle n}$ ${\$
   2. 계산 $p{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle p_{i}=}$ $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 $최하위$ h ${\displaystyle h}$비트$$$.$
   3. 계산 $c{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$
6. 마지막으로 $x{\displaystyle {}_{}}$ ${\displaystyle t_{}}$+ ${\displaystyle 1_{}}$= x ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle 2_{}^{}}$ ${\displaystyle mod}$ ${\displaystyle n}$ ${\$을(를) 계산하십시오$.$

The encryption of the message ${\displaystyle M}$ is then all the ${\displaystyle c_{i}}$ values plus the final ${\displaystyle x_{t+1}}$ value: ${\displaystyle (c_{1},c_{2},\dots ,c_{t},x_{t+1})}$.

암호 해독

암호화된 메시지$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{c\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle c}$ ${\displaystyle t_{}}$, x${\displaystyle }$) ${\displaystyle(c_{1},c_{2},\dots,c_{t},x)}$은(는) 개인$$ 키$({\displaystyle p}$, ${\displaystyle q}$) ${\displaystyle(p,q)}$을(으)로 해독할 수 있다$$.

1. $계산{\displaystyle {}_{}}$ d ${\displaystyle p_{}}$=${\displaystyle }$(${\displaystyle }$( ${\displaystyle \mathrm{p}}$+ 1${\displaystyle }$)${\displaystyle }$/ ${\displaystyle 4\mathrm{}{}^{}}$) t${\displaystyle {}^{}}$+ ${\displaystyle 1^{}}$ ${\displaystyle mod}$ (${\displaystyle }$p${\displaystyle }$- ${\displaystyle 1}$) ${\$$4$)$^{t+1}{\bmod {(p-1)}}}$.
2. 계산 $d{\displaystyle {}_{}}$ ${\displaystyle q_{}}$=${\displaystyle }$( (${\displaystyle q\mathrm{}}$+ ${\displaystyle 1}$)${\displaystyle }$/ 4${\displaystyle {}^{}}$) ${\displaystyle t^{}}$+ ${\displaystyle 1^{}}$ ${\displaystyle mod}$(${\displaystyle q}$- ${\displaystyle 1}$) ${\$$4$)$^{t+1}{\bmod {(q-1$
3. 계산 ${\displaystyle u_{}}$ p${\displaystyle {}_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {d{}_{}}^{}}$ ${\displaystyle {p_{}}^{}}$ ${\displaystyle mod{{}_{}}^{}}$ ${\displaystyle p}$ ${\$
4. 계산 $u{\displaystyle {}_{}}$ ${\displaystyle q_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {d{}_{}}^{}}$ ${\displaystyle {q_{}}^{}}$ ${\displaystyle mod{{}_{}}^{}}$ ${\displaystyle q}$ ${\$
5. ${\displaystyle {}_{}}$ 유클리드 알고리즘을 사용하여 $r{\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle p_{}}$${\$ 및 r q ${\$$displaystyle$ ${$p}$+r_{q}}:{q$$=$$1}$을(를) 계산하십시오$.$
6. 계산 $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle q_{}}$ ${\displaystyle {}_{}}$+ ${\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle mod}$ ${\displaystyle n}$ ${\$이 값은 암호화에 사용된 값과 동일하다(아래 증명 참조).${\displaystyle {\mathrm{그런}}_{}}$ ${\displaystyle {다음\mathrm{}}_{}}$ x$$0 {\$displaystyle x_{$0}}을(를) 사용하여 암호화에 사용된 것과 동일한 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 값을$$ 다음과 같이 계산할$$ 수 있다.
7. $i{\displaystyle }$ ${\displaystyle i}$의 경우 1 ~ t ${\displaystyle t}$
   1. 계산 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}mod}$ ${\displaystyle n}$ ${\$
   2. 계산 $p{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle p_{i}=}$ $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$의 $최하위$ h ${\displaystyle h}$비트$$$.$
   3. 계산 $m{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle p_{}}$ i ${\$
8. 마지막으로 값$($ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{m\mathrm{}}_{}}$ 2${\displaystyle ,}$ …, m t )${\displaystyle {}_{}}${\$displaystyle($m_{1$},m_{2$},\$dots,m_{t}})$을(를) $메시지{\displaystyle }$ M {\$displaystyle M}$에 다시 조립하십시오$.$

예

Let ${\displaystyle p=19}$ and ${\displaystyle q=7}$. Then ${\displaystyle n=133}$ and ${\displaystyle h=\lfloor log_{2}(log_{2}(133))\rfloor =3}$. To encrypt the six-bit message ${\displaystyle 101001_{2}}$, we break it into two 3-bit blocks ${\displaystyle m_{1}=101_{2},m_{2}=001_{2}}$, so ${\displaystyle t=2}$. We select a random ${\displaystyle r=36}$ and compute ${\displaystyle x_{0}=36^{2}{\bmod {1}}33=99}$.이제 c ${\displaystyle i_{}}$ ${\$ 값을$$ 다음과 같이 계산한다.

${\displaystyle {\begin{aligned}x_{1}&=99^{2}{\bmod {1}}33=92=1011100_{2};\quad p_{1}=100_{2};\quad c_{1}=101_{2}\oplus 100_{2}=001_{2}\\x_{2}&=92^{2}{\bmod {1}}33=85=1010101_{2};\quad p_{2}=101_{2};\quad c_{2}=001_{2}\oplus 101_{2}=100_{2}\\x_{3}&=85^{2}{\bmod {1}}33=43\end{aligned}}}$

따라서 암호화는${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle {001\mathrm{}}_{}}$ 2,${\displaystyle {}_{}}$c ${\displaystyle {2\mathrm{}}_{}}$= ${\displaystyle {100}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ x ${\displaystyle {3\mathrm{}}_{}}$= ${\displaystyle 43}$) ${\displaystyle (c_{1}=001_{2},c_{2}=100_{2},x_{3}=43)}$ 입니다$.$

암호를 해독하기 위해 우리는 계산한다.

${\displaystyle {\begin{aligned}d_{p}&=5^{3}{\bmod {1}}8=17\\d_{q}&=2^{3}{\bmod {6}}=2\\u_{p}&=43^{17}{\bmod {1}}9=4\\u_{q}&=43^{2}{\bmod {7}}=1\\(r_{p},r_{q})&=(3,-8){\text{ since }}3\cdot 19+(-8)\cdot 7=1\\x_{0}&=1\cdot 3\cdot 19+4\cdot (-8)\cdot 7{\bmod {1}}33=99\\\end{aligned}}}$

$x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$이(가) 암호화 알고리즘과 동일한 값을 가지고 있음을$$ 알 수 있다.따라서 암호 해독은 암호화와 동일하게 진행된다.

${\displaystyle {\begin{aligned}x_{1}&=99^{2}{\bmod {1}}33=92=1011100_{2};\quad p_{1}=100_{2};\quad m_{1}=001_{2}\oplus 100_{2}=101_{2}\\x_{2}&=92^{2}{\bmod {1}}33=85=1010101_{2};\quad p_{2}=101_{2};\quad m_{2}=100_{2}\oplus 101_{2}=001_{2}\end{aligned}}}$

정확성 증명

암호 해독 알고리즘의 6단계에서 계산한$$ 값 ${\displaystyle {x\mathrm{}}_{}}$ 0 ${\$이 암호화 알고리즘의 4단계에서 계산한 값과 같다는 것을 보여줘야 한다.

암호화 알고리즘에서, $construction{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 0$${\$displaystyle x_{0}$에 의한$$ 2차 잔류물 $modulo{\displaystyle }$ n$${\$displaystyle$ $n$ 따라서 다른 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}${\$displaystyle x_{i}$ 값도$$ 모두 스퀴어링에 의해 얻어진 2차 잔류 modulo p ${\$dulo p$}$이다$.$따라서 오일러의 기준으로 $x{\displaystyle {}_{}^{}}$ ${\displaystyle i_{}^{}}$ ${\displaystyle p_{}^{}}$- ${\displaystyle 1_{}^{}}$)${\displaystyle {}_{}^{}}$/ ${\displaystyle {2\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle 1}$ ${\displaystyle \mathrm{mod}}$ ${\displaystyle p}$ ${\displaystyle x_{i}^{\p-1)/2}\equiv 1\mod{p$그러면

${\displaystyle x_{t+1}^{(p+1)/4}\equiv(x_{t}^{2}^{(p+1)/4)}\equiv x_{t}^{(p+1)/2}\equiv x_{t}^{x_{t}^{(p-1)/2}\equiv x_{t}\mod{p}}}}$

마찬가지로

${\displaystyle x_{t}^{(p+1)/4}\equiv x_{t-1}\mod{p}}$

첫$$ 번째 방정식을 검정력으로${\displaystyle \mathrm{올리면}}$($p$+ 1${\displaystyle }$) /${\displaystyle 4\mathrm{}}$ ${\displaystyle ($p+1$)/4}$

${\displaystyle x_{t+1}^{(p+1)/4)^{2}}\equiv x_{t}^{(p+1)/4}\equiv x_{t-1}\mod{p}}}$

$이{\displaystyle }$ t ${\displaystyle t}$번$$ 반복하면

${\displaystyle x_{t+1}^{(p+1)/4)^{t+1}}\equiv x_{0}\mod{p}}}$

${\displaystyle x_{t+1}^{d_{p}\equiv u_{p}\equiv x_{0}\mod{p}}}$

${\displaystyle {그리고}_{}^{}}$ 비슷한 논거로 $x{\displaystyle {}_{}^{}}$ t${\displaystyle {}_{}^{}}$+ ${\displaystyle 1_{}^{}}$ ${\displaystyle {{}_{}}_{}^{}}$ ${\displaystyle {q_{}}_{}^{}}$u${\displaystyle {}_{}{q}_{}}$ ≡ ${\displaystyle {u\mathrm{}}_{}}$ q x 0 ${\displaystyle \mathrm{mod}{}_{}}$ ${\displaystyle q}$ ${\d$ 스타일 $x_{t+1}^{d_{$q}}\$equiv u_{$0}\$equiv x_{0}\mod{q}}}}$라는 것을 알 수 있다$.$

마지막으로 ${\displaystyle \mathrm{r}}$ ${\displaystyle {}_{}}$ + ${\displaystyle {}_{}{}_{}}$= 1 ${\displaystyle r_{p}p+r_{q}q=1}$이므로 x ${\$을 곱하여 얻을$$ 수 있다$.$

${\displaystyle x_{0}r_{p}p+x_{0}r_{q}q=x_{0}}}}$

from which ${\displaystyle u_{q}r_{p}p+u_{p}r_{q}q\equiv x_{0}}$, modulo both ${\displaystyle p}$ and ${\displaystyle q}$, and therefore ${\displaystyle u_{q}r_{p}p+u_{p}r_{q}q\equiv x_{0}\mod {n}}$.

보안 및 효율성

Blum-Goldwasser 체계는 최종 BBS 상태 $y{\displaystyle }$ ${\displaystyle y}$과(와) $공용{\displaystyle }$키 N {\$displaystyle N}$만 주어진 키스트림 비트를 예측하는 경도에 기초하여 의미론적으로 $안전$하지만, $→,$ {\$displaystyle{\vec},y}$ 형식의 암호문자는 적응형 선택한 암호문서에 취약하다$.$k: 적수가 선택한 암호문 $a{\displaystyle \stackrel{}{}}$→ ,${\displaystyle y}$ ${\displaystyle {\vec},y}$의 암호 해독 m${\$을(를) 요청하는 경우$.$원본 암호문의 암호$$ 해독 $m{\displaystyle }$ ${\displaystyle m}$은(는) $a{\displaystyle \stackrel{}{}}$→ ${\displaystyle \oplus }$ ${\displaystyle m\stackrel{}{}}$ ${\displaystyle {}^{}}$ c${\displaystyle \stackrel{}{}}$→ ${\$ }\oplus ${\vec}}}$로 계산할 수 있다$.$

일반 텍스트 크기에 따라 BG는 RSA보다 계산적으로 다소 비쌀 수 있다.대부분의 RSA 배포는 암호화 시간을 최소화하도록 최적화된 고정 암호화 지수를 사용하기 때문에 일반적으로 RSA 암호화는 가장 짧은 메시지를 제외한 모든 메시지에서 BG를 능가한다.그러나 RSA 암호 해독 지수가 무작위로 분포하기 때문에 모듈형 지수화는 동일한 길이의 암호문에 대해 BG 암호 해독에 대해 비슷한 수의 스쿼링/다중화가 필요할 수 있다.BG는 RSA가 여러 개의 개별 암호화를 필요로 하는 긴 암호문까지 보다 효율적으로 확장할 수 있다는 장점이 있다.이 경우 BG는 훨씬 더 효율적일 수 있다.

참조

1. M. Blum, S. Goldwasser, "모든 부분 정보를 숨기는 효율적인 확률론적 공개 키 암호화 체계", CRIPTO '84, 페이지 289–299, Springer Verlag, 1985.
2. 메네제스, 알프레드, 반 우르쇼트, 폴 C, 그리고 반스톤, 스콧 A.응용 암호학 핸드북.1996년 10월 CRC 프레스.ISBN 0-8493-8523-7

외부 링크

• 메네제스, 우르쇼트, 밴스톤, 스콧: 응용 암호화 핸드북(무료 PDF 다운로드) 8장 참조