[정보보안] 디지털 서명 알고리즘과 RSA

 

목차

 

<디지털 서명>

디지털 서명은 디지털 형태의 데이터를 안전하게 전송하기 위한 방식 중 하나로, 전자 문서나 메시지 등이 발신자 본인에 의해 생성되었으며 전송 중에 변조되지 않았음을 보증하는 기술이다. 이는 전통적인 필적 기반의 서명과 유사한 법적 효력을 가지며, 디지털 환경에서의 인증, 무결성 보증, 부인 방지 등의 목적으로 사용된다.

 

디지털 서명의 기본 원리와 과정은 다음과 같다

 

해쉬 함수 공유

먼저 디지털 서명을 생성하고 검증하는 과정에서 양측이 해시 함수를 공유하게 된다. 디지털 서명 프로토콜을 사용하기 전, 사용할 해시 함수(예: SHA-256, SHA-3 등)에 대한 합의가 필요하다. 이는 보안 통신을 진행하는 양쪽 모두가 동일한 방식으로 메시지의 해시값을 계산하고, 이를 통해 무결성 검증 및 인증 과정을 수행할 수 있도록 보장하기 위함이다.

 

해시 함수의 선택은 다음과 같은 요소에 의해 영향을 받는다:

• 안전성: 해시 함수는 충돌 저항성(collision resistance), 선이미지 저항성(pre-image resistance), 그리고 제2선이미지 저항성(second pre-image resistance)과 같은 보안 속성을 만족해야 한다. 이는 해시 함수가 예측 불가능하게 해야 하며, 해시값을 바탕으로 원본 메시지를 찾아내거나, 동일한 해시값을 가지는 다른 메시지를 찾아내는 것이 실질적으로 불가능해야 함을 의미한다.
• 효율성: 해시 함수는 빠르게 계산될 수 있어야 하며, 다양한 길이의 메시지에 대해 일정한 길이의 해시값을 빠르게 생성할 수 있어야 한다.

통신의 양 당사자가 서명 프로세스에 사용할 해시 함수에 대해 사전에 합의하게 되면, 그 후의 모든 메시지에 대한 디지털 서명 생성 및 검증 과정에서 해당 해시 함수를 사용한다. 이렇게 해서, 메시지의 무결성과 발신자의 인증, 그리고 서명의 부인 방지 등을 보장하는 데 필수적인 역할을 하게 된다.

 

 

서명 생성

• 메시지 해시 생성: 전송할 메시지에 대해 해시 함수를 적용하여 고정된 길이의 해시값을 생성한다. 해시 함수는 입력값이 조금만 달라져도 완전히 다른 출력값을 생성하는 특성을 가진다.
• 해시값 암호화: 생성된 해시값을 발신자의 개인키로 암호화한다. 이 과정이 바로 '서명'을 생성하는 과정이다. 개인키는 발신자만 가지고 있으므로, 이 서명은 발신자만 생성할 수 있다.

서명 검증

• 해시값 복호화: 수신자는 공개키를 사용하여 서명된 해시값을 복호화한다. 공개키와 개인키는 일치하는 한 쌍이므로, 공개키로 복호화가 가능하다면 해당 서명은 실제로 발신자의 개인키로 생성된 것임을 의미한다.
• 메시지 해시값 재생성 및 비교: 수신자는 동일한 해시 함수로 수신된 메시지의 해시값을 다시 생성하고, 이를 복호화된 해시값과 비교한다. 두 해시값이 일치하면 메시지가 중간에 변조되지 않았음을 의미한다.

 

디지털 서명의 특징

• 무결성: 메시지가 변조되지 않았음을 보증한다.
• 인증: 메시지가 실제로 특정 개인이나 기관에 의해 생성되었음을 확인할 수 있다.
• 부인 방지: 발신자가 메시지 발송을 부인할 수 없게 한다.

 

사용 사례

디지털 서명은 다양한 분야에서 중요한 역할을 한다. 예를 들어, 소프트웨어 배포 시 개발자는 소프트웨어와 업데이트를 디지털 서명하여 사용자가 소스의 신뢰성을 확인할 수 있게 한다. 또한, 전자 상거래, 전자 메일, 온라인 문서 서명 등에서도 널리 사용된다.

디지털 서명은 공개키 기반 구조(PKI)를 사용하여 구현되며, RSA, ECDSA(타원 곡선 디지털 서명 알고리즘) 등 다양한 알고리즘이 사용된다. 각 알고리즘은 보안성, 연산 속도, 키 길이 등에서 차이를 보인다. 따라서 사용 목적에 따라 적합한 알고리즘을 선택하는 것이 중요하다.

 

 

 

<RSA>

 

RSA 서명은 공개키 암호 체계를 기반으로 한 디지털 서명 알고리즘이다. 이 알고리즘은 1977년에 로널드 리베스트, 아디 샤미르, 레너드 애들먼에 의해 고안되었다. RSA 암호화와 마찬가지로, RSA 서명도 공개키와 비밀키(개인키)를 사용한다. 메시지의 송신자는 자신의 비밀키로 메시지를 서명하고, 수신자는 송신자의 공개키를 사용하여 서명을 검증한다.

 

RSA 서명의 원리

 

키 생성

1. 두 개의 큰 소수 p와 q를 선택한다.
2. 이들의 곱 N = pq를 계산한다. N은 공개키와 비밀키 모두에 사용된다.
3. 오일러의 피 함수 phi(N) = (p-1)(q-1)을 계산한다.
4. 공개키 e를 선택한다. 이때, e는 1 < e < phi(N)이며 gcd(e, phi(N)) = 1인 값이어야 한다.
5. 비밀키 d를 계산한다. d는 e의 모듈로 phi(N)에 대한 역원이어야 하므로, ed ≡ 1 (mod phi(N))을 만족해야 한다.

메시지 서명

1. 메시지 M에 대해, 송신자는 해시 함수를 사용하여 메시지의 해시 값을 H(M)을 계산한다.
2. 송신자는 자신의 비밀키 d를 사용하여 서명 S를 생성한다: S = H(M)^d mod N.

서명 검증

1. 수신자는 송신자의 공개키 e와 N을 사용하여 S를 e제곱하여 모듈로 N을 취함으로써 H(M)을 재계산한다: S^e mod N.
2. 수신자는 메시지 M의 해시 값을 직접 계산하고, 이 값이 S^e mod N과 일치하는지 확인한다. 일치하면 서명이 유효함을 의미한다.

 

RSA 서명의 특징

• 비대칭 암호화: RSA는 비대칭 암호화 기법을 사용하므로, 서명 생성에 사용되는 비밀키와 서명 검증에 사용되는 공개키가 다르다.
• 인증과 무결성 제공: RSA 서명은 메시지의 발신자가 누구인지를 인증하고, 메시지가 전송 중에 변경되지 않았음을 보장한다.
• 부인 방지: 메시지에 대한 서명이 있으면, 송신자는 전송한 메시지에 대해 부인할 수 없다.
• 계산 복잡도: RSA 알고리즘은 큰 수의 소인수분해가 어려운 점을 기반으로 하므로, 안전성은 소인수분해의 어려움에 의존한다. 그러나 이로 인해 암호화 및 복호화 과정이 계산적으로 매우 복잡하고 시간이 많이 소요될 수 있다.
• 키 길이: 안전한 암호화를 위해서는 충분히 큰 키 길이가 필요하다. 현재는 최소 2048비트 이상의 키 길이를 권장한다.

RSA 서명은 이러한 원리와 특징을 바탕으로 디지털 서명, 인증서 발급, 안전한 통신 등 다양한 분야에서 널리 사용된다.

 

 

코드 예시

아래는 Python을 사용하여 간단한 RSA 디지털 서명 생성과 검증 과정을 구현한 예시다. 실제 응용에서는 보안성을 높이기 위해 표준 라이브러리나 검증된 암호화 도구를 사용하는 것이 좋다.

from Crypto.PublicKey import RSA
from Crypto.Signature import pkcs1_15
from Crypto.Hash import SHA256

# 키 생성
key = RSA.generate(2048)
private_key = key.export_key()
public_key = key.publickey().export_key()

# 메시지 정의
message = 'RSA 디지털 서명 테스트 메시지'.encode('utf-8')

# 메시지 해시 생성
hash_val = SHA256.new(message)

# 서명 생성
private_key_obj = RSA.import_key(private_key)
signature = pkcs1_15.new(private_key_obj).sign(hash_val)

# 서명 검증
public_key_obj = RSA.import_key(public_key)
try:
    pkcs1_15.new(public_key_obj).verify(hash_val, signature)
    print("서명 검증 성공")
except (ValueError, TypeError):
    print("서명 검증 실패")

 

 

이 코드는 pycryptodome 라이브러리를 사용한다.

실제 구현 전에 **pip install pycryptodome**를 실행하여 필요한 라이브러리를 설치해야 한다.