비대칭 키 암호화

이 강의에서는 오늘날 많은 안전한 네트워크 상호작용의 기반을 이루는 비대칭 키 암호화에 대해 살펴봅니다.

이 강의가 끝나면 다음 내용을 다루게 됩니다:

• 비대칭 키 암호화란 무엇인가
• 키 교환 및 디지털 서명을 포함한 비대칭 키 암호화의 활용
• 비대칭 키 암호화의 일반적인 보안성
• RSA, DSA, 타원 곡선 알고리즘 및 그 보안에 대한 세부 사항
• 알고리즘이 실제로 어떻게 동작하는지 보여주는 Python 코드 예제
• 고전 컴퓨터와 양자 컴퓨터 모두로부터 이 알고리즘에 대한 위협

비대칭 키 암호화 소개

지난 강의에서 배운 것처럼, 대칭 키 암호화는 정보 보호에 매우 빠르고 효율적이지만 몇 가지 한계가 있습니다:

1. 안전한 정보를 교환하고자 하는 당사자의 수가 늘어날수록 필요한 키의 수도 기하급수적으로 증가합니다. 또한 송신자와 수신자 사이에서 이 키들을 안전하게 배포할 메커니즘이 없습니다.
2. 부인 방지에 대한 규정이 없습니다. 어떤 당사자도 메시지를 수신했는지 또는 어디서 발신되었는지 보장할 방법 없이 메시지를 복호화하거나 암호화할 수 있습니다

이 두 가지 문제에 대한 해결책은 비대칭 키 암호화(AKC), 즉 공개 키 암호화 (PKC)로 불리는 방식이 제공하며, 이는 현대 디지털 보안의 핵심 요소를 이룹니다.

비대칭 키 암호화(AKC)는 공개 키와 개인 키, 한 쌍의 키를 사용합니다. 공개 키와 개인 키는 암호학적으로 연결되어 있으며, 일반적으로 특수한 수학적 알고리즘을 사용하여 키 쌍으로 동시에 생성됩니다. 이름에서 알 수 있듯이, 공개 키는 자유롭게 배포되고, 개인 키는 키 쌍을 생성한 당사자가 비밀로 유지합니다. 비대칭 키 쌍을 사용하는 통신의 보안은 개인 키가 기밀로 유지되는 한 보장됩니다.

Figure 1. Asymmetric Key Encryption

AKC는 다음과 같은 여러 유용한 기능을 제공합니다:

1. 암호화 및 복호화를 통한 통신의 기밀성 보장.
2. 디지털 서명을 통한 인증, 무결성, 부인 방지 보장.
3. 후속 대칭 암호 시스템 사용을 위한 안전한 키 교환.

현대 응용 프로그램에서 AKC는 주로 디지털 서명과 안전한 키 교환에 사용됩니다. 이 강의에서는 이 두 가지 핵심 기능을 소개하고, 이러한 기능을 위한 여러 암호화 프로토콜 변형에 대해 논의합니다.

비대칭 키 암호화를 이용한 키 교환

암호학의 근본적인 문제 중 하나는 키를 안전하게 교환하는 것입니다. 예를 들어, 두 당사자가 대칭 암호화를 사용하려면 메시지를 암호화하고 복호화하기 위해 동일한 키가 필요합니다. 그런데 이 키를 어떻게 안전하게 교환할까요? 비대칭 키 암호화는 대화형 및 비대화형 키 교환 메커니즘을 통해 이 문제를 해결합니다.

대화형 키 교환

대화형 키 교환 프로토콜은 두 당사자가 안전하지 않은 통신 채널을 통해 협력하여 공유 비밀 키를 생성하는 방법을 말합니다. 이 공유 비밀 키는 이후 대칭 암호화 및 복호화 작업에 사용될 수 있습니다.

이러한 프로토콜 중 가장 잘 알려진 것은 키 교환을 용이하게 하기 위해 특별히 고안된 Diffie-Hellman 알고리즘 (DH)입니다. 이 프로토콜에서 각 당사자는 키 쌍(공개 키와 개인 키)을 생성하고 공개 키를 공개합니다. 그런 다음 각 당사자는 자신의 개인 키와 상대방의 공개 키를 사용하여 공유 비밀 키를 생성합니다. DH는 모듈러 연산의 원리를 활용하여 각 당사자가 상대방의 공개 키만 접근할 수 있어도 양측이 동일한 공유 비밀에 도달할 수 있도록 합니다.

타원 곡선 암호화 (ECC) 기반의 현대 암호 시스템은 타원 곡선 Diffie-Hellman (ECDH) 키 교환으로 이 개념을 확장합니다. ECDH는 DH와 유사하게 동작하지만 타원 곡선의 특성을 활용하여 더 안전하고 효율적인 시스템을 제공합니다.

Figure 2. Key Exchange Protocol

비대화형 키 교환

대화형 방식인 DH 및 ECDH 같은 키 교환 프로토콜과 달리, AKC는 공유 비밀 키를 설정하는 비대화형 방법도 제공합니다. 이러한 방식에서는 한 당사자가 키 쌍(공개 키와 개인 키)을 생성하고 공개 키를 상대방과 공유합니다. 두 번째 당사자는 임의의 대칭 키를 생성하고, 수신한 공개 키로 이를 암호화하여 첫 번째 당사자에게 전송합니다. 첫 번째 당사자는 개인 키를 사용하여 수신된 메시지를 복호화하여 공유 대칭 키를 얻습니다. 이 방식은 대칭 키가 한 당사자에 의해 결정되어 암호화된 형태로 상대방에게 안전하게 전달되기 때문에 비대화형입니다.

비대화형 키 교환에서 중요한 고려 사항은 교환하려는 대칭 키의 비트 길이와 AKC에서 권장하는 메시지 크기 사이의 차이입니다. 일반적으로 현대 대칭 키는 128-256비트 범위이지만, RSA와 같은 비대칭 키 암호 시스템은 약 1024-4096비트의 메시지 크기로 작동합니다. 따라서 AKC를 사용하여 대칭 키를 전송할 때, 보안을 위해 더 긴 1024-4096비트 메시지로 인코딩해야 합니다. 이는 두 가지 방법으로 달성할 수 있습니다:

• 패딩 기반 키 교환: 이 방식에서는 더 짧은 (128-256비트) 대칭 키가 먼저 생성된 후, 합의된 가역적 패딩 방식(예: OAEP)을 사용하여 더 긴 (1024-4096비트) 메시지에 삽입합니다. 이 더 긴 메시지는 AKC를 사용하여 암호화되고 암호문으로 공개됩니다. 수신자는 먼저 암호문을 복호화한 다음 패딩을 제거하여 더 짧은 대칭 키를 추출합니다.

• 키 캡슐화 메커니즘 (KEM): KEM 기반 키 교환에서는 임의의 긴 (1024-4096비트) 평문 메시지가 먼저 생성되고, 합의된 키 유도 함수 (KDF)를 사용하여 더 짧은 (128-256비트) 대칭 키를 추출할 수 있습니다. 더 긴 평문은 AKC를 사용하여 암호화되고 수신자에게 암호문으로 공개됩니다. 수신자는 개인 키로 암호문을 복호화한 다음 KDF를 사용하여 더 짧은 (128-256비트) 대칭 키를 추출합니다. 데이터를 직접 암호화할 수 있는 RSA와 같은 대중적인 암호 시스템을 사용하여 KEM을 구현할 수 있습니다.

Figure 3. Key Encapsulation Mechanism

비대칭 키 암호화를 이용한 디지털 서명

디지털 서명은 비대칭 키 암호화의 또 다른 강력한 응용입니다. 디지털 서명은 AKC 내에서 각 엔티티가 고유한 개인 키를 보유한다는 사실을 활용하여 인증, 무결성 및 부인 방지를 제공합니다. 서명 프로토콜의 기본 아이디어는 안전한 메시지의 발신자가 고유한 개인 키를 사용하여 메시지에 추가적으로 디지털 서명을 한다는 것입니다. 수신자는 발신자의 공개 키를 사용하여 디지털 서명을 확인합니다. AKC 내에서 디지털 서명은 특정 목적으로 설계된 알고리즘을 사용하거나 일반 암호 시스템을 사용하여 구현할 수 있습니다.

Figure 4. Digital signatures with asymmetric key cryptography

전용 디지털 서명 알고리즘

현재 디지털 서명에 대한 미국 연방 정보 처리 표준(FIPS)은 단순히 디지털 서명 알고리즘 (DSA)이라고 불리는 전용 방식입니다. Diffie-Hellman 프로토콜과 다소 유사하게, DSA는 서명 생성 및 검증을 위해 모듈러 지수 및 곱셈 역원의 대수적 특성을 활용합니다.

타원 곡선 디지털 서명 알고리즘 (ECDSA)은 DSA의 ECC 변형으로, 동일한 기능을 제공하지만 키 길이가 현저히 짧습니다. 이로 인해 효율성이 향상되어 자원이 제한된 시스템에서 인기 있는 선택이 됩니다.

DSA와 ECDSA 모두 나중에 더 자세히 설명됩니다.

일반 암호 시스템을 사용한 디지털 서명 방식

전용 알고리즘 외에도, 디지털 서명은 RSA와 같은 일반 비대칭 암호 시스템을 사용하여 생성할 수도 있습니다.

이후 섹션에서 자세히 논의될 RSA도 모듈러 곱셈 역원과 모듈러 지수를 기본 연산으로 활용하지만 DSA와는 다른 순서로 결합합니다. RSA에서 서명자는 일반적으로 메시지의 해시를 생성한 다음 개인 키로 해시를 암호화하여 디지털 서명을 만듭니다. 그런 다음 누구든지 서명자의 공개 키로 서명을 복호화하고 해시된 메시지와 비교하여 이 서명을 검증할 수 있습니다.

비대칭 키 암호화의 응용

비대칭 키 암호화는 현대 디지털 기술 응용 분야에서 어디에나 존재합니다. 위에서 설명한 AKC의 기본 기능들은 다음을 포함한 많은 상위 응용 프로토콜의 구성 요소를 이룹니다:

1. 인터넷 통신: HTTPS와 같은 인터넷을 통한 안전한 통신은 비대칭 키 암호화에 크게 의존합니다. 전송 계층 보안(TLS) 및 그 전신인 보안 소켓 계층(SSL)은 초기 핸드셰이크 과정에서 비대칭 키 암호화를 사용하여 대칭 키를 설정하고, 이후 통신 세션의 나머지 부분에 사용합니다.

2. 인증: 비대칭 키 암호화는 디지털 서명을 생성하는 데 사용되며, 이를 통해 엔티티가 특정 발신자로부터 온 디지털 문서 또는 메시지를 인증할 수 있습니다. 이는 소프트웨어 업데이트 검증부터 법적 구속력이 있는 디지털 계약까지 다양한 시나리오에서 활용됩니다.

3. 이메일 암호화: PGP(Pretty Good Privacy) 및 오픈 소스 대안인 GPG(GNU Privacy Guard)와 같은 이메일 암호화 프로토콜은 의도된 수신자만 이메일 내용을 읽을 수 있도록 비대칭 키 암호화를 사용합니다.

4. 보안 셸(SSH): SSH는 안전하지 않은 네트워크를 통한 안전한 원격 로그인 및 기타 안전한 네트워크 서비스를 위한 프로토콜입니다. 비대칭 키 암호화를 사용하여 클라이언트에 서버를 인증하고, 선택적으로 서버에 클라이언트를 인증합니다.

5. VPN(가상 사설망): 비대칭 키 암호화는 VPN에서 안전한 연결을 설정하는 데 사용되어 공용 네트워크를 통한 안전한 통신을 보장합니다.

6. 블록체인과 암호화폐: 비트코인과 이더리움을 포함한 블록체인 기술은 비대칭 키 암호화를 사용합니다. 예를 들어, 비트코인의 소유권은 비대칭 키 암호화를 사용한 디지털 서명을 통해 확립됩니다.

7. 인증 기관: 비대칭 키 암호화는 인증 기관(CA)이 디지털 인증서를 발급하고 서명하는 데 사용되며, 이는 TLS 통신, 코드 서명, 이메일 암호화 등에 활용됩니다. 디지털 인증서는 공개 키를 특정 엔티티(예: 개인 또는 서버)에 바인딩합니다.

Figure 5. Issuing and signing digital certificates using asymmetric key cryptography

비대칭 키 암호화의 보안

다음을 포함한 여러 암호화 개념들이 결합되어 안전한 비대칭 키 암호화를 가능하게 합니다:

개인 키 기밀성: AKC의 가장 기본적인 보안 요구 사항은 개인 키가 비밀로 유지되어야 한다는 것입니다. 그러나 개인 키는 공개 키와 수학적으로 연결되어야 하므로, 개인 키 기밀성은 또한 공개 키에 대한 지식으로부터 개인 키를 도출하는 것이 계산적으로 불가능해야 한다는 요구도 포함합니다. AKC 내의 키 생성 방식은 이 요구 사항을 충족하기 위해 계산적으로 어려운 수학적 문제에 의존합니다.

트랩도어 기능 AKC에서 암호화 및 복호화 작업은 단일 키 쌍의 서로 다른 보완 키를 포함합니다. 키 중 하나(예: 공개 키)를 사용한 암호화로 생성된 암호문은 제3자에게 불가해해야 하며, 보완 키(이 경우 개인 키)의 보유자는 쉽게 복호화할 수 있어야 합니다. 즉, 암호화는 제3자가 작업을 역전시켜 평문을 복구할 수 없지만 개인 키가 쉬운 역전을 가능하게 하는 비밀 트랩도어를 제공하는 트랩도어 일방향 함수와 유사해야 합니다. 대중적인 AKC 알고리즘은 모듈러 지수를 사용하여 트랩도어 일방향 함수 동작을 설정합니다.

무작위성: 키 생성 과정은 또한 무작위성을 활용하여 키를 예측 불가능하게 해야 합니다. 키 생성의 패턴이나 예측 가능성은 공격자에 의해 악용될 수 있기 때문입니다. 무작위성은 의미론적으로 안전한 암호문을 생성하기 위한 암호화 중 패딩에도 사용되며, 동일한 메시지가 여러 번 서명될 때에도 고유한 서명을 생성하기 위해 디지털 서명 방식 내에서도 사용됩니다. 이러한 이유로 강력한 난수 생성기의 사용은 AKC의 중요한 부분입니다.

큰 키 크기: SKC의 경우와 마찬가지로, 큰 키 크기는 무차별 대입 공격에 대한 보호를 보장합니다. 그러나 큰 키 크기는 또한 암호화 및 복호화 과정의 계산 비용을 증가시키므로, 최적의 솔루션은 보안과 효율성 고려 사항의 균형을 맞춰야 합니다. 다음 표는 다양한 비대칭 키 암호화 프로토콜 및 응용의 일반적인 키 크기를 보여줍니다:

프로토콜	일반적인 키 크기(비트)	응용
RSA	1024 (deprecated), 2048, 3072, 4096	Encryption, digital signatures
DSA	1024 (deprecated), 2048, 3072	Digital signatures
DH	2048, 3072, 4096	Key exchange
ECDH	224, 256, 384, 521	Key exchange
ECDSA	224, 256, 384, 521	Digital signatures

공개 키 인프라: AKC에서 개인 키는 소유자가 비밀로 유지해야 하며 공개 키는 공유됩니다. 사용자 간에 이 공개 키를 관리하고 배포하기 위한 안전한 메커니즘이 필요합니다. 공개 키 인프라(PKI)는 디지털 인증서를 사용하여 이를 수행하는 방법을 제공합니다. 디지털 인증서는 공개 키 소유자의 신원 증명을 제공하며 인증 기관(PKI의 일부)과 같은 신뢰할 수 있는 기관에 의해 발급됩니다. 따라서 PKI는 디지털 인증서를 생성, 관리, 배포 및 폐기함으로써 대규모 키 관리를 가능하게 하여 AKC를 사용하는 현대 응용 프로그램의 보안에 필수적인 역할을 합니다.

비대칭 키 암호화에 대한 보안 위험

위의 표에서 알 수 있듯이, RSA와 같은 현대 비대칭 키 알고리즘은 일반적으로 AES-128과 같이 일반적으로 사용되는 대칭 키 대응물보다 훨씬 큰 키 크기를 사용합니다. 더 작은 키 크기를 사용하는 ECC 기반 프로토콜(ECDH 및 ECDSA)조차도 키에 최소 224비트를 사용합니다. 이는 올바른 키를 식별하기 위해 개인 키 공간을 완전히 탐색하는 무차별 대입 공격이 가까운 미래에 계산적으로 불가능함을 의미합니다. 이는 양자 컴퓨터가 이 작업에 배치되더라도 마찬가지입니다. 따라서 AKC에 대한 공격은 보통 특정 암호 시스템의 다른 잠재적 약점을 악용하는 데 집중됩니다. 잘 알려진 공격 방식들은 다음을 목표로 합니다:

1. 알고리즘 약점: 비대칭 키 알고리즘을 구성하는 데 사용된 경도 가정을 약화시키기 위한 정교한 수학적, 계산적 수단을 사용합니다. 예를 들어, RSA의 보안은 큰 소수를 인수분해하는 어려움에 기초하며, 최근 계산 발전으로 829비트 RSA 키의 성공적인 인수분해가 가능하게 되었습니다. 따라서 1024비트 RSA는 현재 폐기되었습니다. 나중에 논의될 것처럼, AKC에 대한 양자 컴퓨터가 제기하는 주요 위험도 이 범주에 해당합니다.

2. 불완전한 무작위성: 키 생성 과정에서 약점이 발생할 수 있습니다. 예를 들어, 키를 생성하는 데 사용된 난수 생성기가 결함이 있어 진정으로 무작위적이지 않은 키를 생성하면 공격자가 키를 예측할 수 있습니다.

3. 구현 결함: 개인 키에 대한 정보를 의도치 않게 노출시키는 암호화 알고리즘 구현의 오류입니다. 예를 들어, 잘못된 패딩은 잠재적으로 키에 대한 세부 정보를 노출할 수 있습니다.

4. 사이드 채널: 암호화를 수행하는 물리적 시스템으로부터 정보가 누출되는 것을 말합니다. 이러한 누출은 타이밍 정보, 전력 소비, 심지어 소리의 형태일 수 있으며, 소위 사이드 채널 공격에서 악용될 수 있습니다. 예를 들어, 암호화 작업 실행에 걸리는 시간을 분석하면 이진 키에서 '1'의 수를 알 수 있습니다. 이 겉보기에 무해한 누출은 처음에는 극복할 수 없어 보이는 문제에 대한 잠재적 해결책을 드러내며 탐색 공간을 크게 좁힙니다.

5. 키 교환: 중간자 공격 (MITM)과 같이 키가 교환되는 동안 가로채는 방식입니다. DH 프로토콜은 추가적인 인증 단계가 포함되지 않으면 MITM 공격에 취약합니다.

6. 키 저장: 보안이 취약한 저장소에서 키를 훔치는 것을 목표로 합니다. 이는 저장 장치의 조작 또는 도난과 같은 물리적 공격을 포함합니다.

따라서 다양한 가능한 공격에 대해 비대칭 키 암호 시스템을 보호하는 것은 수학적, 하드웨어, 소프트웨어, 물류 및 법적 고려 사항을 포함하는 중요한 작업입니다.

RSA

RSA (Rivest-Shamir-Adleman) 알고리즘은 최초의 공개 키 암호 시스템 중 하나로, 안전한 데이터 전송에 널리 사용됩니다. RSA는 단일 프레임워크 내에서 암호화, 복호화, 디지털 서명, 키 교환에 필요한 연산을 모두 제공하는 다목적 암호 시스템입니다.

이 섹션에서는 간단한 예제를 통해 RSA를 이용한 비대칭 키 암호화(AKC)를 설명합니다.

안전한 통신을 원하는 두 당사자, 앨리스(Alice)와 밥(Bob)이라는 표준 시나리오를 사용하겠습니다.

RSA 알고리즘

기본 RSA 알고리즘은 키 생성, 키 배포, 암호화, 복호화의 네 가지 연산으로 구성됩니다:

1. 키 생성:

   공개 키와 개인 키는 소수(prime number)와 관련된 수학적 원리에 따라 생성됩니다. 소수를 계산하는 것은 쉽지만, 역방향 연산은 어렵습니다.

   여기서는 다음과 같이 표기합니다:

   • 공개 키: $(e, n)$
   • 개인 키: $(d, n)$

   $n$은 공개 키와 개인 키 모두에 공통으로 사용되며, 모듈러스(modulus)라고 합니다. 이후에 사용해야 하므로 기억해 두세요.

수학적 세부 사항

• 서로 다른 두 소수 $p$와 $q$를 선택합니다.
  • 보안을 위해 무작위로 선택합니다.
  • 인수 분해를 더 어렵게 만들기 위해 크기는 비슷하되 자릿수는 몇 자리 차이가 나야 합니다.
  • 소수는 소수 판정법(primality test)을 사용하여 효율적으로 선택할 수 있습니다.
• $n = p*q$를 계산합니다.
  • $n$은 공개 키와 개인 키 모두의 모듈러스입니다.
• 토티엔트(totient) $φ$$(n) = (p-1)*(q-1)$을 계산합니다.
  • 토티엔트는 비밀로 유지되어야 하며, 일반적으로 키 생성 후 폐기됩니다.
• $1 < e <$$φ$$(n)$이고 $gcd$$(e,$$φ$$(n)) = 1$을 만족하는 정수 $e$를 선택합니다.
  • 즉, $e$와 $φ$$(n)$는 서로소(coprime)여야 합니다.
  • 이 수 $e$는 공개 키 지수(exponent)를 구성하며, 계산 효율성을 위해 일반적으로 작은 수로 선택합니다.
  • 소수 $65537 = 2^{16} + 1$이 자주 사용됩니다.
  • 합동 관계(congruence relation) $d*e ≡ 1 ($$mod$$φ$$(n))$을 만족하는 $d$를 계산합니다.
    • 즉, $d$는 $φ$$(n)$에 대한 $e$의 곱셈 역원(multiplicative inverse)입니다.
    • 이는 확장 유클리드 알고리즘(extended Euclidean algorithm)을 사용하면 더 효율적으로 계산할 수 있습니다.
    • 이 수 $d$가 개인 키 지수(exponent)입니다.
• 공개 키는 $(e, n)$으로, 개인 키는 $(d, n)$으로 구성됩니다.

2. 키 배포:

   • 공개 키 $(e, n)$은 메시지를 보내고자 하는 사람들에게 공개됩니다.
   • 개인 키 $(d, n)$은 비밀로 유지됩니다.

3. 암호화:

   • 앨리스는 밥에게 메시지 $M$을 보내고자 합니다. 여기서는 간단한 정수를 예로 사용합니다.
   • 앨리스는 밥의 공개 키 $(e, n)$을 사용하여 메시지를 암호문 $C$로 암호화합니다.

   수학적 세부 사항

   • $M$은 $0 ≤ M < n$을 만족하는 정수(integer)입니다.
   • $C ≡ M^e (mod n)$, 여기서 $C$가 암호문입니다.

4. 복호화:

   • 밥은 암호문 $C$를 수신합니다.
   • 밥은 자신의 개인 키 $(d, n)$을 사용하여 암호문을 원래 메시지 $M$으로 복호화합니다.

   수학적 세부 사항

   • $M ≡ C^d (mod n)$.

이것이 RSA의 기본 개요입니다. 실제로는 동일한 평문이 서로 다른 암호문을 생성하도록 암호화 전에 평문 $M$에 더 정교한 패딩 기법이 적용됩니다. 이는 RSA의 단순 구현에 대한 다양한 공격을 방지하고 의미론적 보안(semantic security)을 가능하게 합니다.

Python으로 RSA 구현 예제

다음 코드 셀에서는 작은 정수를 사용하여 RSA 알고리즘의 간단한 예제를 보여주고, Python 라이브러리를 사용한 실용적인 키 배포 및 디지털 서명 응용을 시연합니다.

참고

참고: 이 섹션에서는 Python 코드의 일부로 수학 계산을 자세히 보여줍니다.

RSA 키 생성

작은 소수를 사용하는 RSA 알고리즘의 간단한 예를 단계별로 살펴보겠습니다.

두 정수의 최대공약수(greatest common divisor)를 계산할 수 있어야 합니다. 이는 두 정수가 서로소(coprime)인지 검사하는 데 필요합니다.

간단한 계산 방법 하나를 설명하겠지만, 큰 정수를 다룰 때는 Python의 math.gcd 함수를 사용하는 것이 훨씬 효율적입니다.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

RSA 워크플로의 첫 번째 단계는 키 생성입니다. 이는 두 개의 소수를 선택하는 것으로 시작하며, 이 소수들은 키를 생성하는 주체가 비밀로 유지해야 합니다.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

다음으로, 선택한 두 소수의 곱인 모듈러스(modulus) $n$을 계산합니다. 이 모듈러스는 공개 키의 일부로 공개됩니다.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

다음으로 오일러 토티엔트(totient) 함수 $\varphi(n)$를 계산합니다. 이는 RSA에서 키를 결정하는 데 사용되는 모듈러 곱셈 역원(modular multiplicative inverse) 연산에 필요합니다. $phi$ 역시 비밀로 유지되며, 일반적으로 키 생성 후 폐기됩니다.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

이제 공개 키와 개인 키를 계산할 준비가 되었습니다. RSA에서 각 키는 두 정수의 튜플로 지정됩니다. 각 튜플의 첫 번째 항목은 고유한 정수이며, 두 번째 항목은 두 키에 공통으로 사용되는 모듈러스 $n$입니다.

공개 키의 첫 번째 항목은 1보다 크고 $phi$와 서로소인 임의의 정수가 될 수 있습니다. 두 정수의 최대공약수(greatest common divisor)가 1이면 서로소입니다. 따라서 math.gcd 함수를 사용하여 $phi$와 서로소인 정수 $e$를 찾습니다.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

개인 키에는 정수 $d$가 필요한데, 이는 $phi$에 대한 $e$의 곱셈 역원(multiplicative inverse)입니다. 즉, 합동 관계(congruency relation) $d*e\equiv 1 \pmod{\varphi(n)}$을 만족해야 합니다. 소수가 작은 이 간단한 예제에서는 양의 정수를 순회하여 적절한 $d$를 찾을 수 있습니다. 실제 환경에서는 계산 효율이 높은 확장 유클리드 알고리즘(extended Euclidean algorithm)이 이 목적에 사용됩니다.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

이제 튜플 $(e, n), (d, n)$을 구성합니다. 이것이 각각 공개 키와 개인 키가 됩니다. 공개 키는 공개되고, 개인 키는 비밀로 유지됩니다.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

RSA에서의 암호화와 복호화는 모듈러 지수 연산(modular exponentiation operation)을 사용합니다. 또한 공개 키와 개인 키는 상호 보완적이어서, 어느 쪽으로 암호화한 메시지도 나머지 키로 복호화할 수 있습니다.

여기서는 공개 키 $(e,n)$으로 암호화하고 개인 키 $(d, n)$으로 복호화하는 경우를 각 연산에 대한 Python 함수를 정의하여 예시합니다.

그런 다음 정수 메시지 $msg$를 암호화하고 복호화합니다.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

위에서 사용한 작은 정수들은 RSA 알고리즘의 핵심 아이디어를 쉽게 설명하는 데 유용하지만, 실제 애플리케이션에서 RSA는 매우 큰 정수를 사용해야 합니다. 예를 들어, 2048비트 RSA는 2048비트 길이의 모듈러스(modulus) $n$을 사용하며, 이에 해당하는 십진수 정수는 약 10$^616$ 수준입니다. 이처럼 거대한 숫자들이 RSA의 실용적인 보안을 위해 반드시 필요합니다.

RSA를 이용한 대칭 키 교환

앞서 논의한 바와 같이, AKC를 사용하면 통신하려는 두 당사자가 공유 비밀을 안전하게 설정할 수 있으며, 이는 예를 들어 대량 평문의 이후 대칭 암호화를 위한 비밀 키로 활용될 수 있습니다.

다음 시나리오를 고려해 봅시다. Alice와 Bob은 SKC를 사용하여 메시지를 암호화하고 복호화하려 합니다. 그러나 이 과정을 시작하기 전에, 두 사람은 공통 비밀 키에 합의해야 합니다. 한 가지 방법은 한 쪽 당사자 — 예를 들어 Alice — 가 비밀 키를 생성한 후 Bob에게 안전하게 전달하는 것입니다. 이 안전한 전송을 위해 Alice는 RSA를 키 캡슐화 메커니즘(KEM)으로 사용하기로 결정합니다.

이 과정은 다음 단계로 이루어집니다:

• 먼저, Alice는 Bob과 공유하려는 임의의 대칭 키를 생성합니다.
• 그런 다음, Bob은 비대칭 키 쌍을 생성하고 자신의 공개 키를 적절한 채널에 공개합니다.
• 다음으로, Alice는 Bob의 공개 키를 사용하여 대칭 키를 암호화하여 암호문에 캡슐화합니다.
• 그런 다음, Alice는 신뢰할 수 있지만 반드시 안전하지 않아도 되는 채널을 통해 암호문을 전송합니다.
• 마지막으로, Bob은 암호문을 수신하고 자신의 개인 키로 복호화합니다. 이제 Bob은 Alice가 생성한 대칭 키에 접근할 수 있습니다.

그림 1. RSA를 이용한 대칭 키 교환

Python에서 패딩 기반 키 교환 예시

이제 cryptography Python 라이브러리를 사용하여 RSA를 활용한 패딩 기반 비대화형 키 교환의 실용적인 워크플로를 설명합니다.

cryptography Python 라이브러리에서 필요한 모듈을 가져옵니다. 필요한 경우 이 라이브러리는 pip install cryptography 명령으로 설치할 수 있습니다.

그런 다음 Alice는 Bob에게 전달하려는 임의의 비밀 키를 생성합니다.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

cryptography 라이브러리의 rsa 모듈을 사용하여 Bob은 키 쌍을 생성한 후 자신의 공개 키를 전송합니다. 누구든 이 공개 키를 가로채서 키를 구성하는 공개 숫자 $(e,n)$을 읽을 수 있습니다.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

이 시점에서 Alice가 Bob이 전송한 공개 키를 수신했다고 가정합니다. 위의 Alice의 symmetric_key는 이제 Bob의 공개 키를 사용하여 암호화되어 암호문으로 생성될 수 있습니다. 현실적인 환경에서 Alice는 Bob과의 통신에서 의미론적 보안을 보장하기 위해 OAEP와 같은 추가 패딩 방법도 사용합니다.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice는 대응하는 개인 키를 가진 Bob만이 복호화할 수 있다는 확신을 가지고 공개 채널을 통해 암호문을 전송합니다. Bob이 암호문을 수신하여 자신의 기밀 개인 키를 사용해 복호화할 수 있다고 가정합니다.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

이 시점에서 Alice와 Bob 모두 비밀 대칭 키에 접근할 수 있으며, 이를 SKC 애플리케이션에 활용할 수 있습니다.

Python에서 RSA를 이용한 키 캡슐화 메커니즘 시뮬레이션

다음 워크플로에서는 충분히 긴 임의의 비밀 메시지를 안전하게 교환하고, 이후 KDF를 사용하여 적절한 길이의 공유 비밀로 변환하는 키 캡슐화 메커니즘(KEM)을 RSA로 시뮬레이션하는 방법을 설명합니다.

다시 한번 Alice와 Bob은 비대화형으로 공유 비밀을 설정하려 하며, 사용할 비밀을 결정하는 당사자는 Alice입니다.

필요한 Python 라이브러리를 가져오는 것으로 시작합니다.

Bob은 RSA 키 쌍을 생성하고 자신의 공개 키를 전송합니다.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice는 먼저 공유 비밀이 최종적으로 도출될 긴 임의의 비밀을 생성합니다. 순수한 KEM에서 긴 비밀은 암호 시스템의 기반이 되는 대수적 구조에서 가져온 임의의 원소입니다. 2048비트 RSA의 경우, 이는 2048비트 RSA 모듈러스에 대한 임의의 정수가 됩니다. 이러한 순수 KEM은 추가 패딩이 필요하지 않지만, 이 예시에서는 RSA를 사용하여 KEM을 시뮬레이션하고 있으며, cryptography 라이브러리는 RSA로 암호화할 때 패딩 사용을 요구합니다. 따라서 표준 256비트 AES 키보다는 훨씬 길지만 다소 짧은 긴 비밀을 사용합니다.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

다음으로 Alice는 Bob의 공개 키를 사용하여 긴 비밀을 암호화하고, 암호화된 비밀을 Bob에게 전달합니다.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob은 자신의 개인 키를 사용하여 Alice로부터 수신한 암호화된 비밀을 복호화합니다.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

마지막으로 Alice와 Bob 모두 합의된 키 도출 함수(KDF)를 긴 비밀에 각자 적용하여 대칭 키를 도출합니다.

이 과정에는 해싱 프로토콜과 임의의 솔트 사용이 포함되며, 긴 비밀이 재사용되는 경우(권장하지 않음) 공유 대칭 키의 고유성과 예측 불가능성을 보장합니다. 그러나 솔트 자체는 비밀일 필요가 없으며, 예를 들어 이 예시에서 Alice가 임의로 생성한 후 암호화된 긴 비밀과 함께 Bob에게 전송할 수 있습니다.

따라서 Alice와 Bob 모두 동일한 임의의 솔트에 접근할 수 있다고 가정합니다.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

RSA를 이용한 디지털 서명

이제 위의 앨리스와 밥의 기밀 통신 시나리오를 디지털 서명을 통해 검증 기능까지 포함하도록 확장하겠습니다.

이전과 마찬가지로 앨리스는 대칭 키를 담은 메시지를 밥에게 기밀로 전송하지만, 이번에는 메시지에 디지털 서명도 첨부합니다. 이를 통해 밥은 메시지를 수신한 후, 그 메시지가 앨리스로부터 발신된 것이며 전송 과정에서 내용이 변조되지 않았음을 검증할 수 있습니다.

보다 일반적으로, 기밀성을 훼손하지 않으면서도 검증을 가능하게 하는 것이 바람직합니다. 이를 통해 실제 평문 메시지에 접근할 수 없는 경우에도 모든 이해 관계자가 특정 통신의 무결성, 진정성을 검증하고 부인 방지를 확립할 수 있습니다.

이 일반적인 설정은 다음 단계들로 구성됩니다:

• 먼저, 밥과 앨리스 모두 자신의 공개 키를 공개 채널을 통해 공개합니다.
• 그런 다음, 앨리스는 밥의 공개 키를 사용하여 평문을 암호화하고 암호문을 만듭니다.
• 다음으로, 앨리스는 해시 함수를 사용하여 암호문의 해시를 생성하고, 생성된 해시된 암호문을 자신의 개인 키로 추가 암호화합니다. 이 암호화된 해시가 바로 서명입니다.
• 그런 다음, 앨리스는 암호문과 서명 모두를 공개 채널을 통해 전송합니다.
• 그런 다음, 밥은 앨리스의 공개 키를 사용하여 서명을 복호화하고 해시된 암호문을 얻습니다.
• 다음으로, 밥은 암호문 자체에도 접근할 수 있으므로, 앨리스가 사용한 것과 동일한 해시 함수를 사용하여 해시된 암호문의 두 번째 인스턴스를 재생성합니다. 후자가 앨리스의 서명을 복호화하여 얻은 것과 일치하면, 암호문 자체가 아직 복호화되지 않았더라도 메시지가 검증됩니다.
• 마지막으로, 밥은 메시지를 검증한 후 자신의 개인 키를 사용하여 암호문을 복호화합니다.

그림 2. RSA를 이용한 디지털 서명

디지털 서명의 이 워크플로는 다음과 같이 설명됩니다.

cryptography 라이브러리에서 유용한 모듈들을 다시 한번 가져옵니다. 이전과 마찬가지로 앨리스는 밥에게 대칭 키를 안전하게 전송하려 하지만, 이번에는 디지털 서명도 첨부하고자 합니다. 이 경우 앨리스와 밥 모두의 공개 키가 필요합니다. 따라서 첫 번째 단계는 앨리스와 밥 모두 RSA를 사용하여 자신의 키 쌍을 생성하고 자신의 공개 키를 공개하는 것입니다.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

다음 단계에서는 이전과 마찬가지로 앨리스가 밥의 공개 키를 사용하여 대칭 키를 암호화하고 암호문을 준비합니다.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

이 단계에서 앨리스는 단순히 암호문을 공개하는 대신, 자신이 메시지의 발신자임을 밥에게 증명할 수 있도록 디지털 서명을 첨부하려 합니다. 이는 두 단계로 수행됩니다:

1. 해싱 알고리즘을 사용하여 암호문의 해시를 생성합니다.
2. 앨리스의 개인 키를 사용하여 해시를 암호화하면 서명이 됩니다.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

그런 다음 앨리스는 밥이 두 가지를 모두 받을 수 있도록 암호문과 서명을 네트워크를 통해 공개합니다.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

밥의 측에서는 먼저 수신한 암호문의 무결성과 진정성을 검증하는 것이 첫 번째 작업입니다. 이를 위해 밥은 앨리스가 사용한 것과 동일한 해싱 알고리즘을 사용하여 수신된 암호문의 해시를 생성합니다.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

그런 다음 밥은 앨리스의 공개 키를 사용하여 수신된 서명을 복호화합니다. 앨리스가 자신의 개인 키를 사용하여 서명을 생성했기 때문에, 밥은 앨리스의 공개 키를 사용하여 이를 복호화할 수 있습니다. 복호화된 서명은 앨리스 측에서 생성된 암호문의 해시에 불과합니다. 밥이 생성한 해시가 복호화된 서명과 일치하면, 밥은 수신한 암호문이 변조되지 않았으며 앨리스가 암호문에 서명했음을 검증한 것입니다.

아래 Python 코드에서 이러한 작업들은 앨리스의 공개 키와 관련된 객체가 제공하는 verify라는 유용한 유틸리티 함수로 결합됩니다.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

수신된 암호문의 무결성과 진정성을 검증한 후, 밥은 앨리스가 밥의 공개 키를 사용하여 암호문을 생성했기 때문에 자신의 개인 키를 사용하여 복호화할 수 있습니다.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

위의 디지털 서명 시나리오에서, 밥뿐만 아니라 모든 당사자가 앨리스가 암호문의 발신자임을 검증할 수 있습니다. 왜냐하면 누구나 앨리스의 공개 키, 암호문, 그리고 디지털 서명에 접근할 수 있기 때문입니다. 또한, 암호문과 서명을 전송한 후에는 앨리스가 그 사실을 나중에 부인할 수 없습니다. 왜냐하면 서명은 오직 그녀의 공개 키를 사용해야만 의미 있는 해시로 복호화될 수 있기 때문입니다. 이것이 바로 부인 방지를 확립합니다.

안전한 키 배포를 가능하게 하고 부인 방지를 지원함으로써, 공개 키 암호화는 안전한 디지털 통신을 위한 강력한 기반을 마련합니다.

RSA 해독

위에서 설명한 RSA 알고리즘의 유용성과 보안성은 두 가지 수학적 가정에 기반합니다.

1. $(e, n)$에만 접근 가능한 상황에서 모듈러 곱셈 역원 $d$를 구하는 것은 계산적으로 불가능합니다.

2. RSA 설정에서, 모듈러 지수 연산은 단방향 트랩도어 함수처럼 작동합니다. 암호화에 사용될 때, 이 연산은 해독할 수 없는 암호문을 생성하며, 개인 키에 접근하지 않고는 암호문에서 평문을 복구하기 위해 연산을 역으로 수행하는 것이 불가능합니다. 그러나 트랩도어 역할을 하는 개인 키에 접근할 수 있다면 암호문을 쉽게 복호화할 수 있습니다.

RSA 알고리즘에 대한 가장 대표적인 공격은 모듈러스 $n$을 인수분해하여 개인 키 숫자 $d$를 효율적으로 복구함으로써 가정 1을 무너뜨리는 것을 목표로 합니다. 아래에서 설명하겠지만, $n$의 소인수 $p$와 $q$ 또는 토티엔트 $φ$$(n)$에 접근할 수 있다면 $d$를 쉽게 복구할 수 있습니다. $p$, $q$, 그리고 $φ$$(n)$은 키 생성 과정에서 비밀로 유지되다가 이후에 폐기된다는 점을 상기하세요. 고전 컴퓨터나 양자 컴퓨터를 사용하여 이 정보를 복구한 제3자는 사실상 개인 키를 발견하게 되어 RSA를 해독할 수 있습니다. 따라서 소인수분해는 RSA를 해독하는 데 필요한 핵심 계산 기본 요소입니다.

고전 컴퓨팅과 RSA

대형 정수의 소인수분해는 고전 컴퓨터에서 초다항식 또는 지수 미만의 확장성을 보이는 것으로 알려져 있습니다. $10^{100}$보다 큰 정수를 인수분해하기 위한 가장 잘 알려진 고전 알고리즘은 일반 수체 체 (GNFS)입니다.

수학적 세부 사항

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

인수분해할 정수 $n$의 함수로서의 확장성입니다.

이 확장성은 $n$을 표현하는 데 필요한 비트 수에 대해 초다항식입니다.

따라서, 소인수분해는 고전 컴퓨터에서 비효율적인 것으로 간주됩니다.

현재, 고전 하드웨어에서 인수분해된 가장 큰 정수는 829비트 또는 250자리 10진수 범위에 있습니다. 지난 수십 년간 목격된 고전 컴퓨팅 성능의 기하급수적 성장을 고려할 때, 1024비트 RSA는 더 이상 단기적으로 안전하다고 여겨지지 않으며 이제는 사용이 중단되었습니다. 그럼에도 불구하고, 예측 가능한 미래에는 $10^{617}$ 범위의 2048비트 정수를 인수분해하는 것이 현재로서는 고전 시스템에서 불가능하다고 여겨지므로, 지속적인 실행 가능성이 있습니다. 그러나 양자 컴퓨터의 등장은 이 평가를 무효화합니다.

쇼어의 양자 알고리즘과 RSA

오늘날 아마도 가장 잘 알려진 양자 알고리즘은 정수의 소인수를 찾기 위한 쇼어의 알고리즘입니다. 1994년 피터 쇼어에 의해 소개되었을 때, 이 알고리즘은 소인수분해라는 실용적으로 매우 중요한 문제에서 고전 알고리즘보다 초다항식 속도 향상을 제공하는 최초의 양자 알고리즘으로 인정받았습니다.

쇼어의 알고리즘은 $n$을 비트 수라 할 때 $O(n^2)$으로 소수를 인수분해할 수 있습니다.

쇼어의 알고리즘에 대한 수학적 설명

RSA의 맥락에서, 쇼어의 알고리즘은 모듈러 지수 함수 $f(x) = a^x (mod~n)$의 주기성을 활용하며, 모듈러스 $n$의 효율적인 소인수분해를 가능하게 하는 양자 주기 탐색 기본 요소를 제공합니다.

RSA를 해독하기 위한 쇼어의 전반적인 방식을 단순화한 고수준 개요는 다음과 같습니다:

1. 공개 키의 일부로 공개된 모듈러스 $n$이 주어지면, $n$과 서로소인 수 $a$를 선택합니다. 즉, $gcd(a,n) = 1$이어야 합니다. $n = p*q$가 정확히 두 개의 소인수 $(p, q)$를 가진다는 것을 알고 있으므로, 임의로 선택한 $n$보다 작은 거의 모든 수는 $n$과 서로소일 가능성이 높습니다.

2. $a$를 선택했다면, $a^r \equiv 1 (mod~n)$이 되는 지수 $r$을 찾습니다. 이는 $a^r - 1 \equiv 0 (mod~n)$을 의미합니다. 위의 합동이 성립하는 지수 $r$의 존재는 모듈러 지수의 주기성에 의해 보장됩니다.

3. $r$이 짝수라면, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$이 어떤 정수 $\gamma$에 대해 성립합니다. 우변이 $p$와 $q$를 소인수로 갖기 때문에, 이 후자 등식의 좌변도 $p$와 $q$를 두 소인수로 포함해야 합니다. $r$이 홀수라면, 1단계로 돌아가서 $a$에 대해 다른 값을 시도합니다.

4. $gcd((a^{r/2} - 1), n)$ 또는 $gcd((a^{r/2} + 1), n)$을 구하기 위해 확장 유클리드 알고리즘을 사용합니다. 계산된 GCD는 소인수 $p$ 또는 $q$ 중 하나를 매우 높은 확률로 식별합니다. $n$을 이 소인수로 나누어 다른 소인수를 복구합니다.

5. $p, q$를 알게 되면, 원래 RSA 알고리즘의 단계를 사용하여 토티엔트 $\phi(n)$을 재구성하고, 알려진 공개 키 숫자 $e$의 모듈러 역원으로서 개인 키 숫자 $d$를 생성합니다.

2023년 8월, Oded Regev는 다차원 접근법을 사용하여 $O(n^{1.5})$의 결과를 얻는 쇼어의 원래 알고리즘에 대한 개선안을 발표했습니다. 시간, 비용 또는 필요한 큐비트 수를 개선할 수 있는 Ragavan and Vaikuntanathan의 연구를 포함하여 이 분야에서 추가적인 연구가 계속되고 있습니다. 이러한 알고리즘을 실제 RSA 암호화에 적용하는 것이 언제 진정으로 실현 가능해질지는 말할 수 없지만, 점점 가까워지고 있습니다.

RSA 암호화 해독을 보여주는 Python 예제

다음 코드 셀에서는 공개 키만 주어진 상황에서 개인 키를 찾는 예제를 보여줍니다. 이것은 무차별 대입 고전 계산을 사용하지만, 쇼어의 알고리즘이 어떻게 사용될 수 있는지—대형 키를 포함하여—를 보여줍니다.

참고

이 섹션에서는 Python 코드의 일부로 수학적 계산을 상세히 보여줄 것입니다.

이 예제에서, 공개 키는 $(5, 247)$이며, 개인 키를 복구할 것입니다.

1단계: 첫 번째 단계는 247과 서로소인 숫자를 선택하는 것입니다. 우리가 추측하는 거의 모든 숫자가 가능합니다. 6을 선택해 보겠습니다.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

2단계: 다음으로 $6^r \equiv 1 (mod~247)$이 되는 주기 $r$을 찾아야 합니다. 이 예제에서는 무차별 대입으로 $r$을 고전적으로 계산하지만, Qiskit을 사용하여 양자 컴퓨터에서 쇼어의 알고리즘을 사용할 수도 있습니다.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

3단계: 주기 $r = 36$이 짝수이므로, $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$을 계산할 수 있습니다.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

4단계: 그 인수들 중 하나와 $n$의 GCD를 찾습니다. 이미 찾은 소인수로 $n$을 나누어 두 번째 소인수를 구합니다.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

5단계: $n = 247$의 소인수를 $p_{found}=13$과 $q_{found}=19$로 복구했으므로, 토티엔트 $\phi_{found} = (p_{found}-1)*(q_{found}-1)$를 계산합니다.

개인 키는 공개 키 숫자 $e=5$의 모듈러 역원입니다.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

위의 방식에서, 2단계는 쇼어의 알고리즘이 두 가지 기본적인 양자 기본 요소, 즉 양자 푸리에 변환과 양자 위상 추정을 사용하는 핵심 주기 탐색 연산입니다. 쇼어의 알고리즘의 양자적 측면에 대한 자세한 설명은 양자 알고리즘의 기초의 위상 추정 및 인수분해 레슨을 참조하세요. 1단계와 3~5단계는 고전 컴퓨터에서 쉽게 수행할 수 있는 비교적 간단한 연산들입니다.

선택 사항으로, 쇼어의 알고리즘 구현에 대한 상세한 시각적 안내도 있습니다.

양자 컴퓨터에서, 쇼어의 알고리즘은 모듈러스 $n$에 대해 $O((log~n)^2 (log~log~n))$만큼 유리한 다중로그 확장성을 보이거나, $n$을 표현하는 데 필요한 비트 수에 대해 다항식 확장성을 보일 수 있습니다. 이는 고전적인 GNFS 알고리즘에 비해 초다항식 속도 향상입니다.

최근의 자원 추정에 따르면, 하드웨어 구성에 관한 특정 가정을 기반으로, 쇼어의 알고리즘을 사용하여 2048비트 RSA를 해독하는 데 수만 개에서 수백만 개의 큐비트가 필요할 것으로 보입니다. 향후 수년 내에 수만 개의 큐비트를 갖춘 양자 컴퓨터가 등장할 가능성이 전혀 없지 않으므로, 자원 추정의 하한값은 접근 가능해질 수 있습니다.

Diffie-Hellman 키 교환과 디지털 서명 알고리즘

이전 섹션에서는 소인수분해의 계산적 어려움에 기반한 RSA 암호 시스템을 다루었습니다. 여기서는 두 가지 널리 사용되는 비대칭 키 암호화 프로토콜인 Diffie-Hellman 키 교환(DH)과 디지털 서명 알고리즘(DSA)을 살펴보겠습니다. 두 프로토콜 모두 이산 로그 문제(DLP)라는 서로 다른 수학적 문제에 기반합니다.

이산 로그 문제

다음 방정식에서 $e$, $M$, $c$만 주어졌을 때 $a$를 구해야 합니다.

$a^e$ $mod$ $M = c$

모듈러 산술을 사용하기 때문에 고전 컴퓨터로는 이를 풀기 어렵다고 알려져 있으며, 따라서 암호화 알고리즘의 좋은 수학적 기반이 됩니다.

이것이 바로 이산 로그 문제(DLP)로 알려진 것입니다.

이산 로그 문제의 수학적 세부 사항

DLP는 일반적으로 순환 군의 맥락에서 다음과 같이 정의됩니다.

군 원소 $g \in G$에 의해 생성되는 순환 군 $G$를 고려하고, 임의의 원소 $h \in G$가 주어졌을 때 $h = g^{k}$를 만족하는 정수 $k$를 구합니다.

여기서 정수 $k \equiv log_{g}h$가 이산 로그입니다. $G$의 순환 성질은 모든 $h$에 대해 유효한 정수 $k$가 존재함을 보장합니다.

암호학에서는 소수 $p$를 법으로 하는 정수의 곱셈군, 즉 $(\mathbb{Z}_p)^{\times}$로 표기되는 군에서의 DLP가 유용합니다. $(\mathbb{Z}_p)^{\times}$의 원소는 $p$와 서로소인 정수를 법 $p$로 나타낸 합동류입니다.

예를 들면:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

이 군들에서의 곱셈 연산 $(\times)$은 단순히 정수 곱셈 후 $p$로 나눈 나머지를 취하는 것이며, 정수 $k$에 의한 거듭제곱은 $k$번 반복 곱셈 후 $p$로 나눈 나머지를 취하는 것입니다.

$(\mathbb{Z}_7)^{\times}$에서 DLP의 예시를 살펴보겠습니다.

이 곱셈군은 두 개의 생성원 ${[3],[5]}$(원시근이라고도 함)를 가집니다. 생성원으로 $[5]$를 사용하겠습니다. 즉, 5의 연속적인 정수 거듭제곱을 사용하여 $(\mathbb{Z}_7)^{\times}$의 모든 원소를 생성합니다.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

mod 7 산술에서 5를 연속적인 정수 거듭제곱으로 올리면 $(\mathbb{Z}_7)^{\times}$의 모든 원소가 정확히 한 번씩 나타나고, 그 후 주기 $p-1 =6$으로 무한 반복됨을 알 수 있습니다.

따라서 생성원 [5]를 사용한 $(\mathbb{Z}_7)^{\times}$에서의 DLP는 다음과 같습니다:

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$.

위 Python 셀 출력에서 다음을 알 수 있습니다:

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

일반 실수 산술에서 거듭제곱은 단조 함수이며, 임의의 밑수에 대한 로그 계산은 계산적으로 쉽습니다. 반면, 위의 간단한 $(\mathbb{Z}_7)^{\times}$ 예시에서 볼 수 있듯이, 모듈러 거듭제곱은 비단조적이며, 주기 $p-1$을 가지기는 하지만 그 외에는 매우 복잡합니다. 따라서 그 역연산인 이산 로그는 고전 컴퓨터에서 큰 $p$에 대해 비효율적입니다.

이 관찰이 다음 섹션에서 다루는 Diffie-Hellman(DH) 키 교환과 디지털 서명 알고리즘(DSA) 모두의 기반이 됩니다.

DLP는 다음과 같이 순환 부분군으로 확장될 수 있습니다:

• 위에서 정의한 $(\mathbb{Z}_p)^{\times}$와 소수 위수 $r$을 갖는 원소 $g \in (\mathbb{Z}_p)^{\times}$, 즉 $g^r \equiv 1 (~mod~p)$를 고려합니다.
• $g$의 정수 거듭제곱의 집합: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$은 군 위수 $r$을 갖는 $(\mathbb{Z}_p)^{\times}$의 순환 부분군입니다.
• $h \in \\langle g \rangle$를 선택하고 $g^a~(mod~p) = h$를 만족하는 $1 \le a \le r$을 구함으로써 $\langle g \rangle$에 대한 DLP를 정의할 수 있습니다.

Diffie-Hellman 키 교환

1976년, Whitfield Diffie와 Martin Hellman은 안전하지 않은 통신 채널을 통해 공유 비밀 키를 생성할 수 있는 키 교환 프로토콜을 제안했습니다. 이 비밀 키는 이를 공유하는 당사자들이 대칭 암호화에 사용할 수 있습니다. 이 알고리즘은 DLP에 의존합니다.

Figure 1. Diffie-Hellman 키 교환

Diffie-Hellman 키 교환의 수학적 세부 사항

통신하는 두 당사자를 Alice와 Bob이라 할 때, 프로토콜은 다음과 같이 동작합니다:

• 먼저, Alice와 Bob은 큰 소수 $p$와 원시근 또는 생성원 $a$에 합의합니다.
• 그런 다음, Alice는 $1 \le k_A \le p-2$를 만족하는 비밀 지수 $k_A$를 무작위로 선택하고 $h_A = a^{k_A}~(mod~p)$를 계산합니다. $k_A, h_A$는 각각 Alice의 개인 키와 공개 키입니다.
• 다음으로, Bob은 $1 \le k_B \le p-2$를 만족하는 비밀 지수 $k_B$를 무작위로 선택하고 $h_B = a^{k_B}~(mod~p)$를 계산합니다. $k_B, h_B$는 각각 Bob의 개인 키와 공개 키입니다.
• 그런 다음, Alice는 Bob에게 $h_A$를, Bob은 Alice에게 $h_B$를 신뢰할 수 있지만 반드시 안전할 필요는 없는 채널을 통해 전송합니다.
• 그런 다음, Alice는 수신한 $h_B$를 사용하여 공유 비밀 키 $\kappa = h_B^{k_A}~(mod~p)$를 계산합니다.
• 마지막으로, Bob은 수신한 $h_A$를 사용하여 공유 비밀 키 $\kappa = h_A^{k_B}~(mod~p)$를 계산합니다.

이 프로토콜을 통해,

• Alice와 Bob은 $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$이기 때문에 동일한 비밀 키 $\kappa$를 갖게 됩니다.
• $h_A$ 또는 $h_B$를 가로챈 제3자는 $k_B$ 또는 $k_A$에 각각 접근할 수 없으므로 비밀 키 $\kappa$를 구성할 수 없습니다.
• 공개 정보 $a$, $p$, $h_A$, $h_B$를 사용하여 $k_A$ 또는 $k_B$를 추출하는 것은 $(\mathbb{Z}_p)^{\times}$에서 DLP를 푸는 것과 동일하므로 계산적으로 어렵습니다.

Python으로 구현한 Diffie-Hellman 프로토콜 예시

작은 소수를 사용하여 Python으로 DH 프로토콜의 간단한 예시를 살펴보겠습니다:

참고

이 섹션에서는 Python 코드의 일부로 수학적 계산을 자세히 보여주겠습니다.

1단계: Alice와 Bob이 소수 $p$와 원시근 $a$에 합의합니다. $p=11, a=7$로 선택하겠습니다.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

2, 3단계: Alice는 비밀 지수 $k_A$를 선택하고 $h_A = a^{k_A}~(mod~p)$를 계산합니다. 마찬가지로, Bob은 비밀 지수 $k_B$를 선택하고 $h_B = a^{k_B}~(mod~p)$를 계산합니다.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

4단계: 두 당사자가 공개 키 $h_A$와 $h_B$를 공개합니다.

5, 6단계: 각 당사자는 자신의 개인 키와 상대방의 공개 키를 결합하여 공유 비밀 키를 생성합니다.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice와 Bob은 이제 공유 비밀 키를 대칭 암호화에 사용할 수 있습니다.

Diffie-Hellman 키 교환의 보안

앞서 언급했듯이, DH의 보안은 큰 소수 $p$를 사용한 DLP 풀기의 계산적 어려움에 기반합니다. 일반적인 응용에서 NIST는 DH 키 교환에 2048비트 또는 3072비트 소수 정수를 권장하며, 이는 고전 컴퓨터로 DLP를 풀려는 시도에 대해 충분히 안전한 것으로 간주됩니다.

중간자(MITM) 공격: DH는 공유 비밀이 한 당사자의 개인 키와 상대방의 공개 키를 결합하는 대화형 방식이기 때문에 소위 중간자(MITM) 공격에 취약합니다.

DH 보안과 MITM 공격의 수학적 세부 사항

이 시나리오에서, Eve라는 제3자가 전송 중인 공개 키 $h_A, h_B$를 가로채고 $h_A$와 $h_B$ 각각을 자신의 공개 키 $h_E$로 대체한 후 각각 Bob과 Alice에게 전달합니다.

그러면 Alice는 Bob의 공개 키를 사용하고 있다고 생각하면서 $h_B$ 대신 $h_E$를 사용하여 공유 비밀을 생성하게 됩니다. 마찬가지로, Bob은 Alice의 공개 키를 사용하고 있다고 생각하면서 $h_A$ 대신 $h_E$를 사용하여 공유 비밀을 생성하게 됩니다.

$h_E$가 Alice(Bob)의 공유 비밀 생성에 사용되었기 때문에, Alice(Bob)가 암호화한 평문을 Eve가 복호화할 수 있습니다.

따라서 DH 키 교환은 일반적으로 각 당사자가 공유 비밀 생성에 인증된 공개 키를 사용하도록 보장하기 위해 디지털 서명 알고리즘과 함께 사용됩니다.

디지털 서명 알고리즘(DSA)

RSA와 같은 일반적인 암호 시스템이 디지털 서명 기능을 제공하기는 하지만, 1994년 NIST는 모듈러 거듭제곱과 이산 로그 문제에 기반한 전문화된 서명 방식을 디지털 서명의 연방 표준으로 채택했습니다. 디지털 서명 알고리즘(DSA)으로 알려진 이 방식은 네 가지 뚜렷한 단계로 구성됩니다:

1. 키 생성:

   DSA 키는 다음으로부터 생성됩니다:

   • 특정 규칙을 충족하는 2개의 소수
     • $p$ - 일반적으로 256비트 (이 길이를 $N$이라 부릅니다)
     • $q$ - 일반적으로 3072비트 (이 길이를 $L$이라 부릅니다)
   • 길이 $L$의 문자열을 $N$으로 변환하는 암호화 해시 함수
   • 추가 매개변수 $g$ (아래 세부 사항 참조)

   이로부터 임의의 수 $x$를 개인 키로 선택하고, 공개 키 $y$를 계산할 수 있습니다.

   키 생성의 수학적 세부 사항

   • 매개변수 생성: 수학적으로, DSA는 소수 위수 q < p를 갖는 원소 $g$에 의해 생성되는 $(\mathbb{Z}_p)^{\times}$의 순환 부분군을 다룹니다. 따라서 DSA의 첫 번째 단계는 필요한 수학적 구조를 설정하기 위해 두 소수 p, q를 선택하는 것입니다.

     • $N$비트 소수 $q$를 선택합니다.
     • $p-1$이 $q$의 배수가 되는 $L$비트 소수 $p$를 선택합니다. $p$의 선택은 군 $(\mathbb{Z}_p)^{\times}$를 결정합니다.
     • 정수 $1 < h < p-1$을 무작위로 선택하고 $g = h^{(p-1)/q}~mod~p$를 계산합니다. 드물게 $g=1$이 되면 다른 h를 시도합니다.
     • $g^q~mod~p = 1$을 확인합니다. 따라서 g는 소수 위수 q를 갖는 $(\mathbb{Z}_p)^{\times}$의 순환 부분군 $\langle g \rangle$의 생성원입니다.

     매개변수 $(q, p, g)$는 알고리즘의 인스턴스를 지정하며 공개 정보입니다. 실제 응용에서는 일반적으로 $N \sim 256$이고 $L \sim 3072$입니다.

     또한 이 프로토콜은 이진 $L$비트 문자열을 $N$비트 문자열로 매핑하는 암호화 해시 함수 $H : \{0,1\}^L \rightarrow \{0, 1\}^N$(예: SHA-256)이 필요합니다.

   • 키 쌍 생성: 서명자는 자신의 측에서 키 쌍을 생성해야 합니다.

     • 임의의 비밀 정수 $x \in \{1,2...q-1\}$을 선택합니다. $x$가 개인 키입니다.
     • $y = g^{x}~mod~p$를 생성합니다. $y$가 서명자의 공개 키입니다.

2. 키 배포:

   서명을 검증하고자 하는 모든 사람과 다음 정보를 공유합니다.

   • 알고리즘을 설명하는 사용된 매개변수 $(p,q,g)$
   • 해시 함수 $H$
   • 공개 키 $y$

3. 서명:

   • 서명자는 이제 메시지 $m$에 서명할 수 있습니다. 결과 서명은 $(r,s)$입니다.
   • 메시지와 서명 모두 수신자에게 전송됩니다.

   메시지 서명의 수학적 세부 사항

   서명자는 다음과 같이 메시지 $m$에 서명합니다:

   • $\{1,2...q-1\}$에서 비밀 정수 k를 무작위로 선택합니다.
   • $r = (g^k~mod~p)~mod~q$를 계산합니다. 드물게 $r=0$이 되면 다른 무작위 k를 시도합니다.
   • $s = (k^{-1} (H(m) + xr))~mod~q$를 계산합니다. 드물게 $s=0$이 되면 다른 무작위 k를 시도합니다.
   • 서명은 튜플 $(r, s)$입니다.
   • 서명자는 메시지 $m$과 서명 $(r,s)$를 검증자에게 전송합니다.

   $r, s$ 모두 정수이므로, 법 $q$에서 서명 크기는 더 긴 $L$비트가 아닌 $N$비트 수준입니다.

4. 검증:

   수신자는 이제 발신자의 진위를 확인하고자 합니다. 수신자는 공개 정보 $(q, p, g, H, y, (r,s), m)$에 접근할 수 있습니다. 수신자는 발신자가 개인 키 $x$에 접근했음을 증명하는 계산을 실행할 수 있습니다.

   수신자는 서명자가 개인 키 $x$에 접근할 수 있는 사람인지 확인하고자 합니다.

   DSA 검증 방식의 수학적 세부 사항

   • $0 \lt r \lt q$이고 $0 \lt s \lt q$임을 확인합니다. 즉, $r, s$가 유효한 법 $q$ 정수인지 확인합니다.
   • $w = s^{-1}~mod~q$를 계산합니다.
   • $u_1 = H(m)w~mod~q$를 계산합니다.
   • $u_2 = rw~mod~q$를 계산합니다.
   • $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$를 계산합니다.
   • $v = r$이면 서명이 검증됩니다.

   정당한 서명에 대해 DSA 알고리즘의 정확성은 다음과 같이 쉽게 증명됩니다:

   • 서명자 측에서: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • 후자 등식의 우변을 고려하면, 검증자는 $s, q, m, H$가 공개 정보이므로 $s^{-1}, H(m)$을 계산할 수 있습니다.
   • 따라서 검증자는 $w = s^{-1}~mod~q$와 $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$를 계산합니다.
   • 검증자는 $r$도 공개이므로 $u_2 = rw~mod~q = rs^{-1}~mod~q$도 계산합니다.
   • $k = (u_1 + xu_2)~mod~q$임에 주목합니다.
   • 그러나 검증자는 $x$가 서명자의 개인 키이므로 이에 접근할 수 없고, $k$ 자체를 직접 계산할 수 없습니다. - 대신 이 방식은 검증자가 $k$를 계산할 수 없더라도, 정당한 서명자의 경우 검증자가 서명자의 공개 키 $y = g^{x}~mod~p$의 도움으로 $(g^k~mod~p)~mod~q = r$을 재계산할 수 있어야 한다는 사실에 의존합니다.
   • 따라서 검증자는 $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$를 계산합니다.
   • 마지막 등식은 $g$가 위수 $q$를 가지기 때문에 성립하며, 유효한 서명에 대해 $v = r$임을 확인합니다.

Python으로 DSA 예시 살펴보기

이 예시에서는 작은 소수를 사용하여 Alice가 Bob에게 서명된 메시지를 보내는 시나리오로 DSA 과정을 설명합니다. 이 예시에서는 작은 정수를 사용합니다. 실제 환경에서는 2048~3072비트 규모의 훨씬 큰 소수를 사용합니다.

참고

다른 값으로 이 예시를 다시 실행해 알고리즘이 어떻게 동작하는지 확인해 볼 수 있습니다. 단, 이 섹션의 첫 번째 셀부터 실행해야 합니다.

먼저 필요한 라이브러리를 가져오고 매개변수를 선택합니다. 정수 매개변수 $p$, $q$, $g$는 공개 정보이며, 다음 규칙을 만족해야 합니다:

• $p$, $q$ 는 모두 소수입니다
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

다음으로 서명자인 Alice가 자신의 개인 키를 생성합니다.

개인 키 k (파이썬 코드의 alice-private-key)는 다음 조건을 만족해야 합니다:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice는 자신의 개인 키를 비밀로 유지합니다.

다음으로 Alice는 모듈러 지수 연산을 사용하여 공개 키를 계산합니다. 이 단계를 역으로 계산하여 개인 키를 복원하는 것은 DLP의 한 사례에 해당하므로, 큰 소수를 사용하는 경우 고전 컴퓨터에서는 계산하기 어렵습니다.

위의 수학적 설명에서 알 수 있듯이, 이는 다음 공식으로 계산할 수 있습니다:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

평소와 마찬가지로 Alice는 반드시 비밀일 필요가 없는 채널을 통해 자신의 공개 키를 공개합니다.

이제 Alice는 메시지에 서명할 수 있습니다.

디지털 서명 방식에서는 서명할 메시지 $m$의 해시 $H(m)$을 생성해야 합니다.

Alice와 Bob이 해시 길이 $N$이 $q$의 비트 수와 같은 특정 해싱 알고리즘을 사용하기로 합의했다고 가정합니다. 이 간단한 예시에서는 모의 해시 함수의 출력값을 $q$로 제한합니다. 여기서의 해시 함수는 단순히 무작위 정수를 생성하는 간단한 형태입니다.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

다음으로 Alice는 서명을 계산하기 위해 메시지별 무작위 비밀 숫자 $k$와 $q$에 대한 그 곱셈 역원을 생성해야 합니다.

모듈러 역원을 계산하는 데 간단한 브루트 포스 알고리즘을 사용할 수 있습니다. 그러나 아래에 나와 있는 파이썬 내장 함수 pow를 사용하는 것이 더 좋습니다.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

이제 Alice는 서명을 계산할 수 있습니다.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

$r$ 또는 $s$가 $0$으로 계산되는 경우에는 $k$의 값을 다시 선택해야 하는 특별한 조건이 있습니다. 이 경우 새로운 값을 생성하고 반복합니다.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice는 메시지와 서명을 수신자 또는 검증자인 Bob에게 공개합니다.

Bob은 이전에 Alice의 공개 키를 입수했으며, 이제 서명을 검증하여 그녀의 메시지를 인증할 수 있습니다.

이를 위해 Bob은 몇 가지 검사를 수행한 다음, Alice가 공개한 메시지의 해시를 다시 생성하고 보조량 $w, u_1, u_2$ 및 $v$를 계산합니다.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

마지막으로 Bob은 $v$가 $r$과 같은지 확인합니다. 두 값이 같으면 서명이 검증됩니다.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

DSA의 보안

고전 컴퓨팅 환경에서 DSA의 보안은 여러 요소에 의해 영향을 받을 수 있습니다.

1. 키 크기: 항상 그렇듯이, 키 크기는 무차별 대입 공격에 대한 기본적인 보호를 제공합니다. DSA를 사용하는 현대 애플리케이션은 최소 2048비트의 키 크기를 사용합니다.

2. $k$의 품질: DSA에서 각 서명은 고유하고 무작위이며 비밀인 $k$ 값이 필요합니다(위 참조). $k$의 고유성, 엔트로피, 그리고 비밀성은 매우 중요하며, 이러한 측면 중 어느 하나라도 취약하면 개인 키 $x$가 노출될 수 있습니다. $k$ 생성에 사용되는 난수 생성기 자체도 안전해야 합니다.

3. 해시 함수의 강도: DSA는 서명 생성 및 검증 과정에서 해시 함수를 사용하기 때문에, 취약한 해시 함수는 디지털 서명의 보안을 손상시킬 수 있습니다. 예를 들어, DSA와 함께 SHA-1을 사용하는 것은 더 이상 권장되지 않으며 SHA-2 이상을 사용하는 것이 권장됩니다.

이 외에도, 견고한 DSA 구현은 앞서 설명한 비대칭 키 암호화를 대상으로 하는 다른 유형의 공격에도 대비해야 합니다.

Diffie-Hellman과 DSA를 이용한 인증된 키 교환

전송 계층 보안(TLS)과 같은 현대 네트워크 보안 프로토콜은 키 교환과 인증 기능을 결합하는 방식을 사용합니다. Diffie-Hellman의 맥락에서, 인증은 중간자(MITM) 공격을 방어하기 위해 필요합니다. 다음 코드 셀에서는 Alice와 Bob이 Diffie-Hellman과 DSA 프로토콜을 결합하여 인증된 키 교환을 수행하는 예시를 살펴봐요. 이를 위해 Python의 cryptography 라이브러리를 사용합니다.

Figure 2. Authenticated key exchange with Diffie-Hellman and DSA

먼저, Alice와 Bob은 DH 파라미터 세트에 합의하고 DH 공개-개인 키 쌍을 생성합니다.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

DH 공개 키는 브로드캐스트됩니다. 다음으로, Alice와 Bob은 각각 DSA에서 사용할 별도의 키 쌍을 생성합니다. 이 키들은 교환될 DH 공개 키에 서명하는 데 사용됩니다.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice는 자신의 DSA 개인 키를 사용하여 DH 공개 키에 서명합니다.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

마찬가지로, Bob도 자신의 DSA 개인 키를 사용하여 DH 공개 키에 서명합니다.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

이제 DH 공개 키와 해당 서명이 Alice와 Bob 모두에 의해 브로드캐스트됩니다. 상대방의 공개 키와 서명을 받은 각 당사자는 서명이 유효한지 검증합니다. 이 방식으로, 예를 들어 Alice는 Bob의 DH 공개 키가 실제로 Bob에 의해 서명되었다는 것을 알 수 있으므로 MITM 공격을 방지할 수 있습니다.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

서명 검증 후, Alice와 Bob은 공유 비밀을 생성하여 키 교환을 완료합니다.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

선택적으로, 추가 보안을 위해 Alice와 Bob은 키 스트레칭 기법을 사용하여 공유 비밀로부터 더 안전한 대칭 키를 생성하는 HKDF와 같은 전용 키 유도 함수를 사용할 수 있습니다.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Diffie-Hellman과 DSA 깨기

Diffie-Hellman (DH)과 DSA 프로토콜 모두 $y = g^{x}~mod~p$ 형태의 공개 키 생성을 포함하며, 여기서 개인 키 $x$는 이산 로그입니다.

DLP의 인스턴스를 풀 수 있는 공격자는 두 당사자 중 한 명의 개인 키를 노출시킬 수 있으며, 이를 두 번째 당사자의 공개 키와 결합하면 공유 비밀에 접근할 수 있습니다. DSA의 경우, DLP를 풀 수 있는 공격자는 서명자의 개인 키를 복구하여 디지털 서명의 기본 전제를 무효화할 수 있습니다.

고전 컴퓨팅 시스템에서 DLP는 다항 시간 해법이 없는 것으로 알려져 있습니다. 그러나 Peter Shor가 그의 1994년 원본 논문에서 보여주었듯이, Shor의 알고리즘은 양자 컴퓨터에서 다항 시간으로 DLP도 풀 수 있습니다.

Shor의 알고리즘과 이산 로그 문제

Shor의 알고리즘은 이산 로그 문제를 다항 시간 내에 풀 수 있습니다. 주로 문제의 입력에 의존하는 함수의 주기를 찾는 양자 알고리즘을 활용하여 효율성을 달성하며, 이를 더 일반적인 연산과 결합합니다.

Shor의 알고리즘의 수학적 세부 사항

Shor의 알고리즘은 DLP를 숨겨진 부분군 문제 (HSP)라고 알려진 군론의 더 일반적인 문제로 매핑함으로써 효율적인 해법을 제공합니다.

HSP에서는 대수적 군 $G$와 $G$에서 어떤 집합 $X$로의 함수 $f: G \rightarrow X$가 주어지는데, 이 함수는 $G$의 부분군 $H$의 각 잉여류에서 상수이고(다른 잉여류에서는 구별됩니다). 그러면 $H$를 결정하는 것이 과제입니다. 양자 컴퓨터는 유한 아벨 군에서의 HSP를 $log~|G|$의 다항 시간으로 풀 수 있다고 알려져 있으며, 여기서 $|G|$는 군의 위수입니다.

이 수업에서 다룬 정수 DLP의 경우, HSP로의 매핑은 다음과 같습니다:

• $p$를 소수라 하고 $y = g^r~mod~p$로 주어진 DLP를 고려합니다. 여기서 $g$는 $(\mathbb{Z}_p)^{\times}$의 생성원입니다. $g^{p-1} \equiv 1~mod~p$이므로, $g$의 위수는 $p-1$입니다.
• $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$을 선택합니다. 여기서 $\mathbb{Z}_{p-1}$은 $(p-1)$을 법으로 하는 정수 군입니다.
• $f : G \rightarrow (\mathbb{Z}_p)^{\times}$를 $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$로 선택합니다.
• $f$의 핵은 부분군 $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$입니다.
• $f$는 잉여류 $(\delta, 0) + H_0$에서 상수이며 부분군 $H_0$를 "숨겨" HSP를 설정합니다.

위의 내용을 바탕으로, 정수 DLP에 대한 Shor의 양자 알고리즘은 양자 오라클을 사용하여 $G$ 위의 균일 중첩을 나타내는 상태에서 함수 $f$를 평가하고, 양자 푸리에 변환과 위상 추정을 이용한 측정을 통해 $H_0$의 생성원 $(r, 1)$을 식별할 수 있는 양자 상태를 생성합니다. 이로부터 관심 있는 이산 로그인 $r$을 추출할 수 있습니다.

Shor의 원본 논문에는 알고리즘에 대한 자세한 설명이 나와 있습니다.

타원 곡선 암호화

타원 곡선 암호화(ECC)는 타원 곡선의 수학에 기반하며 비대칭 키 암호화에 강력한 접근 방식을 제공합니다. ECC는 RSA와 같은 방법과 유사한 수준의 보안을 제공하지만 더 짧은 키를 사용하여 더 효율적이고, 임베디드 시스템과 모바일 장치 같이 더 작은 키 크기의 저장 및 계산 절약이 매우 바람직한 자원이 제한된 시스템에 특히 적합합니다.

타원 곡선 암호화의 기본 원리

타원 곡선은 일반적으로 $y^2 = x^3 + ax + b$ 형태이며 몇 가지 흥미로운 특성을 가집니다.

• 수평으로 대칭입니다. 따라서 곡선 위의 임의의 점 $(x,y)$에 대해, 그 반사점 $(x,-y)$도 곡선 위에 있습니다.
• 비수직 직선은 곡선과 최대 세 점에서만 교차합니다.

그림 1. 타원 곡선 위에서의 덧셈과 점의 배증 연산. 면 1은 P + Q = -R을 정의합니다. 면 2는 점의 배증 2Q = -P를 나타냅니다. 면 3은 점의 덧셈 역원을 x축에 대한 반사로 정의합니다, 즉 P = -Q

타원 곡선 암호화는 곡선 위의 점들에 일련의 산술 연산을 적용하는 방식을 사용합니다. 각 연산은 곡선 위의 새로운 점으로 이동합니다. 이는 한 방향으로는 따라가기 쉬운 과정이며, 더 짧은 키 크기로 RSA와 같은 다른 알고리즘보다 효율적이지만, 이를 역으로 되돌리는 것은 매우 어렵기 때문에 암호화에 적용됩니다.

타원 곡선 암호화의 수학적 원리

대수적 체 $K$ 위의 타원 곡선은 수학 방정식으로 정의되며, 일반적으로 계수 $a, b \in K$를 가진 $y^2 = x^3 + ax + b$ 형태로 점 $(x, y) \in K \otimes K$를 설명하고, 곡선에 꼭짓점이나 자기 교차점이 없어야 한다는 추가 요건이 있습니다.

타원 곡선의 특성은 곡선 위의 점들을 포함하는 "덧셈"과 "스칼라 곱셈" 연산을 정의할 수 있게 해줍니다.

덧셈: $P$와 $Q$가 타원 곡선 위의 두 점이라면, $P + Q$는 다음과 같이 식별된 고유한 세 번째 점을 설명합니다: $P$와 $Q$를 교차하는 직선을 그리고 그 직선이 곡선과 다시 교차하는 세 번째 점 $R$을 찾습니다. 그런 다음 $P + Q = −R$을 $x$축을 통해 반사된 $R$의 반사점으로 정의합니다(아래 그림 참조). $P, Q$를 지나는 직선이 유한한 $(x, y)$에서 곡선과 교차하지 않으면, 무한점 $\mathbf{O}$에서 교차한다고 말합니다.

타원 곡선 덧셈은 무한점을 덧셈 항등원으로 하는 대수적 군 특성을 만족합니다.

배증과 스칼라 곱셈: $2$에 의한 스칼라 곱셈에 해당하는 점 배증 연산은 덧셈 연산에서 $P = Q$로 설정하여 얻어지며, 그래프적으로는 $P$에서의 접선을 포함합니다. 정수 $n$에 의한 일반 스칼라 곱셈은 $nP = P + P + ...~n$번으로 정의되며, 반복적인 배증과 덧셈에 의해 얻어집니다.

타원 곡선 이산 로그 문제

타원 곡선 이산 로그 문제(ECDLP)는 인수 찾기의 어려움을 기반으로 한다는 점에서 앞서 논의한 이산 로그 문제와 많은 유사점을 가집니다.

타원 곡선에서의 스칼라 곱셈 연산은 타원 곡선 이산 로그 문제의 정의를 가능하게 합니다:

$Q = nP$가 되도록 타원 곡선 위의 점 $P, Q$가 주어졌을 때, $n$을 결정하세요.

이 문제는 큰 $n$에 대해 고전 컴퓨터에서 계산이 불가능한 것으로 알려져 있으며, 이것이 암호화 보안의 기반을 제공합니다.

ECDLP의 수학적 설명

타원 곡선 암호화는 주로 특정 대수적 유한체 위에 공식화된 ECDLP에 기반합니다. 1999년에 NIST는 ECC에 사용할 10개의 유한체를 권장했습니다. 이것들은:

• 크기가 $\{192, 224, 256, 384, 521\}$ 비트인 소수 $p$에 대한 다섯 개의 소수체 $\mathbb {F} _{p}$.
• $n \in \{163, 233, 283, 409, 571\}$에 대한 다섯 개의 이진체 $\mathbb {F} _{2^{n}}$.

위의 설정으로, 소수체의 경우 ECC 기반 비대칭 키 암호 시스템은 다음과 같이 명시될 수 있습니다:

• NIST 권장 값 목록에서 $p$를 선택하여 $\mathbb {F} _{p}$를 지정합니다.

• 타원 곡선의 파라미터 $a, b$를 선택합니다.

• 위수 $n$으로 곡선 위에서 순환 부분군을 "생성"하는 기저점 $G$를 선택합니다. 즉, $nG = \mathbf{O}$가 되는 가장 작은 정수입니다.

• 보조인수 $h = |E(\mathbb {F} _{p})|/n$을 계산합니다. 여기서 $|E(\mathbb {F} _{p})|$는 곡선 위의 점의 수입니다. $h$는 일반적으로 작은 정수입니다.

• 도메인 파라미터 $(p, a, b, G, n, h)$는 다음 방식으로 비대칭 키의 명시를 가능하게 합니다:

  • 개인 키는 소수 $p$와 같은 수의 비트를 가진 무작위로 선택된 정수 $d$입니다. 비밀로 유지되어야 합니다.
  • 공개 키는 기저점 $G$를 개인 키 $d$로 "곱한" 결과입니다. 이것은 일반적으로 $Q = dG$로 표기됩니다.

$d$를 복구하는 것은 ECDLP를 푸는 것과 동일하며, 이는 큰 $d$에 대해 계산이 불가능하다고 가정합니다. ECDLP는 따라서 이전에 논의된 $(\mathbb{Z}_p)^{\times}$ 위에서 정의된 Diffie-Hellman 및 DSA 체계와 직접적인 유사성으로 키 교환 및 디지털 서명 체계의 기반을 형성합니다.

ECC를 이용한 키 교환

ECC의 주요 용도 중 하나는 타원 곡선 Diffie-Hellman (ECDH)이라고 알려진 키 교환 프로토콜입니다. ECDH에서 각 당사자는 개인-공개 키 쌍을 생성한 다음 공개 키를 교환합니다. 각 당사자는 자신의 개인 키와 상대방의 공개 키를 사용하여 공유 비밀을 계산하며, 이것은 대칭 암호화의 키로 사용될 수 있습니다.

타원 곡선에서 점 덧셈을 수행하고 개인 키에서 공개 키를 유도하는 것은 비교적 쉽지만, 역과정으로 공개 키에서 개인 키를 유도하는 것은 계산적으로 불가능합니다. 이 "단방향" 동작이 ECDH 키 교환의 보안을 제공합니다.

여기서는 Python과 cryptography 라이브러리를 사용하여 ECDH 키 교환을 수행하는 방법의 예시를 살펴봐요.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

ECC를 이용한 디지털 서명

ECC는 타원 곡선 디지털 서명 알고리즘 (ECDSA)을 사용하여 디지털 서명을 생성하는 데도 사용될 수 있습니다. ECDSA에서 서명자는 개인 키를 사용하여 서명을 생성하고, 다른 사람들은 서명자의 공개 키를 사용하여 서명을 검증할 수 있습니다. ECDH와 마찬가지로, ECDSA의 보안도 ECDLP에 의존합니다. 서명자의 개인 키에 접근하지 않고 서명을 위조하는 것은 계산적으로 불가능합니다.

다음은 Python과 cryptography를 사용하여 ECDSA로 간단한 서명-검증 트랜잭션을 수행하는 예시입니다.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

위 코드에서, 서명 후 메시지를 수정하면 검증이 실패하여 메시지의 진위성과 무결성에 대한 보장을 제공합니다.

ECDH와 ECDSA 깨기

정수 이산 로그 문제와 유사한 방식으로, ECDLP는 고전 컴퓨터에서는 어렵지만 Shor의 알고리즘을 통해 양자 컴퓨터에서 다시 한번 효율적인 해법을 갖는 것으로 밝혀졌습니다. Shor의 알고리즘을 ECDLP 경우로 일반화하는 것에 관한 논의는 최근 문헌을 참조해 주세요.

요약

이 수업에서 우리는 비대칭 키 암호화(AKC)의 주요 특성을 살펴보고, 비대칭 암호 시스템의 기반이 되는 기본 보안 고려사항을 논의하는 것으로 시작했습니다. 특히, AKC의 두 가지 주요 응용 — 즉, 키 교환과 디지털 서명 — 을 소개했으며, 이 두 가지 모두 현대 인터넷 기반 통신의 필수 구성 요소입니다.

그런 다음 RSA 암호 시스템을 살펴보았습니다. RSA는 1970년대부터 간단하고 다목적적인 프레임워크 내에서 키 교환과 디지털 서명을 가능하게 함으로써 현대 디지털 통신을 보호하는 데 엄청난 가치가 있음이 입증되었습니다. 고전 컴퓨팅에 관한 RSA의 암호화 보안은 큰 정수의 인수 분해의 어려움을 기반으로 하며, 실용적인 응용에 사용되는 정수가 인수 분해에 저항할 만큼 충분히 크도록 2048비트 범위의 키 크기를 필요로 합니다.

그런 다음 Diffie-Hellman (DH) 키 교환과 디지털 서명 알고리즘(DSA)을 살펴보았습니다. 이 체계들의 보안은 정수 이산 로그(DLP) 문제에 기반하며, 개인 키는 공개 키가 주어졌을 때 계산적으로 추출하기 어렵고 고전 컴퓨터에서 다항 시간 해법이 없습니다. 무작위하고 고유한 키를 사용하면 공격에 대한 추가 보안을 제공합니다. 정수 유한체와 타원 곡선 변형의 DH 및 DSA 프로토콜은 현재 TLS, SSH 등과 같은 많은 현대 디지털 통신 프로토콜에서 광범위하게 사용됩니다.

마지막으로 타원 곡선 암호화를 살펴보았습니다. 효율적인 키 크기와 강력한 보안 특성을 갖춘 ECC는 현재 키 교환에서 디지털 서명에 이르기까지 많은 암호화 응용에 있어 훌륭한 선택입니다.

이 모든 알고리즘은 설계의 전제로 작용했던 수학적 문제들에 대한 해법이 개발될 수 있기 때문에 양자 알고리즘의 공격에 노출되어 있습니다. 그러한 예 중 하나가 Shor의 알고리즘입니다. 따라서 이것들은 양자 공격에 더 강하고 동시에 고전 알고리즘에도 안전한 양자 안전 비대칭 암호 시스템으로 교체될 필요가 있습니다. 이들이 의존하는 수학적 문제들은 양자 컴퓨터에 의해 효율적으로 풀릴 수 있으므로, 양자 공격에 견디면서 고전적 보안을 유지할 수 있는 양자 안전 비대칭 암호 시스템의 개발이 필요합니다.