Diffie-Hellman 개인 키 크기
저는 현재 Diffie-Hellma n 구현을 작성하고 있습니다 (실제 사용을위한 것이 아닙니다. 이것은 제가 직접 DH를 더 잘 이해하기위한 것입니다.)
프라임 및 생성기의 경우 RFC 3526 , 특히 4096 비트 프라임을 사용하고 있습니다.
제 질문은 Diffie-Hellman에 대한 특정 표준 비밀 정수 생성이 있습니까? 비밀 정수 (일반적으로 2 개이지만 DH는 1-1 이상의 통신을 지원함)의 보안은 키 교환의 보안에 매우 중요합니다.
답변
DHKE
DHKE로 표시되는 지수 Diffie-Hellman 에서 하나는 그룹을 취합니다.$G$ 발전기로 $g$ 순서대로 $n$.
키를 교환하는 동안 Alice와 Bob은 난수를 생성합니다. $a$ 과 $b$ 범위 안에 $a,b\in (1,n)$ 및 전송 $g^a$ 과 $g^b$ 마지막으로 키를 다음과 같이 설정합니다. $g^{ab}$ 그런 다음 KDF를 사용하여 대칭 키와 IV / nonce를 파생합니다.
DHKE의 Elliptic Curve 버전도 있으며 ECDH로 표시되며 기존 지수 버전보다 더 많이 사용됩니다.
초기
DHKE에서 우리는 프라임을 안전한 프라임으로 선택합니다. $p = 2 \cdot q + 1$ 와 $q$또한 소수입니다. 그만큼$q$소피 제르맹 프라임 이라고합니다 .
이 대책이다 Pohlig - 헬만 알고리즘 이의 작은 요소 혜택$p-1$. 요인보다 안전한 프라임이 사용되는 경우$2$ 과 $q$. 큰 요인을 갖는 것은 Pohlig-Hellman에 대한 대응책입니다.
또한이 Schnorr의 그룹 으로$p = r\,q + 1$. 이것은 세이지 프라임의 일반화로 간주 될 수 있습니다. 세이지 프라임이 최적입니다.
프라임 생성
순진한 접근 방식은 소수를 생성합니다. $q$ 그런 다음 $2 \, q +1$( Menezes : 알고리즘 4.86 ). 의사 코드에서;
do
p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)
더 빠른 방법이 있습니다
2003 년 David Naccache의 Double-Speed Safe Prime Generation
제목에서 알 수 있듯이 두 가지를 모두 테스트하여 약 2 배 정도 속도를 높일 수 있습니다. $2q + 1$ 과 $(q − 1)/2$ 원시성을 위해.
아이디어는 무작위 소수를 사용하는 것입니다. $p$ 안전한 프라임 또는 Sophie Germain 프라임으로;
do p = randomPrime(k-bit integer) while ((p − 1)/2 and 2p + 1 are composite)결합 체 를 사용한 안전한 프라임 생성 ( Michael J. Wiener, 2003).
그들은 작은 소수를 체질하는 것을 제안했습니다. $2^{16}$. 이것은 제공합니다$15x$ 순진한 알고리즘보다 속도가 빨라집니다.
아이디어는이 관찰에서 시작됩니다. 양자 모두$q$ 과 $q=2p+1$ 일치해야합니다 $2$ 모듈로 $3$. 따라서 다음과 같은 후보를 제거 할 수 있습니다.$0$ 모듈로 $3$ 과 $1$ 모듈로 $3$.
이것은 임의의 홀수 소수로 일반화 될 수 있습니다. $r$. 죽이다$q$의 일치하는 $(r-1)/2$ 모듈로 $r$ 이 경우부터 $p$ 나눌 수있다 $r$.
세트 가져가 $S$ 모든 홀수 소수 $<B$. 그때$\prod_{r\in S}(r-2)/r$ 후보자의 체가 살아남을 것입니다.
만약 $B=2^{16}$ 그것은 생산할 수있는 것으로 추정됩니다 $\approx \times 15$ 속력을 올리다.
충돌
이제 같은 난수에 도달 할 확률을 살펴 보겠습니다. $k$동일한 DHKE 계수를 사용하는 사람들. 우리는$k$동일한 보안 (예측할 수없는) 난수 생성기를 사용하여 임의 키를 생성하는 사람들. 이를 단순화하기 위해 난수를 생성하는 사람이 한 명이라고 가정 할 수 있습니다. 이 경우, 이것은 완전히 생일 패러독스 이고 Cryptography에서 우리는 50 % 충돌을 찾기위한 생일 공격 을 봅니다 . 이것은 해시 함수의 충돌을 보는 일반적인 방법입니다.
허락하다 $H$ 난수 생성기의 범위이고 $p$ 우리가 원하는 확률을 나타냅니다. $n(p; H)$ 우리가 선택해야하는 가장 적은 수의 값이어야합니다.
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
고전적인 해시 충돌 사례에서 우리는 $p=1/2$ 그리고이 접근
$$n(0.5;H) \approx 1.1774 \sqrt H$$ 그리고 우리는 일반적으로 $\mathcal{O}(\sqrt{H})$
이제 실제 숫자를 살펴 보겠습니다.
2048 비트 프라임
그것을 가정 $n$ 2048 비트 숫자입니다. $n$ 발전기의 순서였다 $g$. 그때
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
50 % 확률로 $$n(0.5;2^{2048})\approx 2^{1204}$$
결과적으로 다음을 생성해야합니다. $2^{1204}$난수를 50 %로 다시 맞 춥니 다. 가능하지 않다.
4096 비트 프라임
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
50 % 확률로 $$n(0.5;2^{4096})\approx 2^{2048}$$
결과적으로 다음을 생성해야합니다. $2^{2048}$난수를 50 %로 다시 맞 춥니 다. 가능하지 않다. dlog 테이블을 미리 계산합니다.
모듈러스는 표준에 의해 미리 결정되기 때문에 초강력을 가진 일부 조직은 모듈러스에 대해 일부 DLog 테이블을 구축했다고 주장 할 수 있습니다.
이것도 위험하지 않습니다. 그들이 테이블을 만들 수 있다고 가정합시다$2^{64}$ 그러면 무작위 히트의 확률은 $$\frac{\ell \, 2^{64}}{2^{2048}}$$ 와 $\ell$시험. 그룹의 가능한 키 생성 번호를$\ell$. 따라서 2048 비트는 처리해야 할 정말 큰 숫자입니다.