전자 서명 알고리즘

DSS(Digital Signature Standard)

FIPS 186-4에 정의된 미국 표준 전자서명 알고리즘 표준이다. 이 문서에서는 DSA, RSA, ECDSA라는 세가지 전자서명 알고리즘을 명세한다. 다만, 표준의 다음 버전에서는 DSA 알고리즘이 제거될 예정이다.

ECDSA (Elliptic Curve Digital Signature Algorithm)

Modulus 연산으로 정의된 DSA에 Elliptic Curve 연산을 적용한 알고리즘이다. 근본적으로 ElGamal과 Schnorr Signatures의 변형 알고리즘이다. (자세한 알고리즘은 표준문서나 Wiki 등을 참고)

RSA와 ECDSA 비교

ECDSA의 키 길이가 짧아서 좋은 데이터 효율을 보인다. 128-bit 안전성을 가정하면 ECDSA는 256 비트의 비밀키 사용하지만 RSA는 2048 bit의 비밀키를 사용한다. (하지만 공인인증서는 아직 RSA 서명을 사용함)

ECDSA의 키생성 알고리즘이 훨씬 간단하다. ECDSA의 경우 256비트 난수를 비밀키로 정하고, ECC Scalar 곱 1회를 거쳐 공개키를 얻을 수 있다. 반면 RSA는 1024 비트의 Strong Random Prime 2개를 선택하고, 그 곱을 공개키로 정하고, 난수 1개를 추가로 생성하여 개인키로 정한다. 하지만 Safe Random Prime을 뽑는 과정(아래에서 설명)이 매우 연산량이 크기 때문에 키 생성 알고리즘도 ECDSA가 효율이 좋다.

서명 알고리즘의 효율성은 자세히 비교해봐야 하겠지만 ECDSA가 결코 RSA에 뒤지지 않는다. 알고리즘만 보면 RSA가 이해하기 쉽지만 실제 실제 구현 레벨로 들어가면 여간 생각할 것이 많은게 아니다. (RSA-OAEP 참고) 퍼포먼스 측면은 어느 한쪽이 월등히 빨라서 어느한쪽이 우월한 수준은 아닌 것으로 알고 있다. (자세한 조사나 실험 필요..)

ECDSA가 효율적인 측면에서 RSA 서명보다 우수하지만 ECDSA 등장 전에 공인인증서 도입처가 많아서 실제 구현체는 RSA가 더 많다.

Safe Random Prime과 소수판정 Complexity

확정적으로 소수를 출력하는 알고리즘은 없다. 따라서 난수를 생성하고 그 수가 소수인지 판정한다. 만약 소수이면 해당 수를 리턴하고 아니면 다시 난수를 뽑는다. 하지만 확정적으로 소수인지 판단하는 알고리즘도 없다. 다만 어떤 수가 75% 확률로 소수일 것이라는 판정을 하는 알고리즘(Miller-rabin)만을 활용할 수 있다. 소수 판정 알고리즘은 여러번 반복 수행하여 에러를 줄이는 방향으로 수행된다.

소수 판정 알고리즘

Miller-rabin 소수판정법(비소수판정법)은 "입력된 수가 합성수다" 또는 "입력된 수는 아마도 소수이다."라는 결과를 리턴한다. 합성수라는 판정 결과는 100% 참이지만 소수라는 판정 결과는 25%의 오류를 포함한다. 따라서 Target 정수에 대하여 Miller-rabin 테스트를 반복하여 오류확률을 줄여 나가며 소수 판정을 수행한다. 128비트 보안 레벨이라면 64회 테스트롤 통과한 정수를 소수라고 믿는다. 즉, 2의 128승 분의 1의 오류를 포함하긴 하지만 소수라고 그냥 믿는 것이다.

Safe Prime

자기 자신인 q가 소수이면서 (q-1)/2도 소수인 q를 Safe Prime이라고 한다. 따라서 운좋게 한번에 Safe Prime을 선택하더라도 확인을 위해 총 128번의 MR Test가 소요된다. (q가 소수? (q-1)/2도 소수?) 난수를 하나 뽑고, 그것이 Safe Prime인지 판단하는 과정은 최대 MR Test 128번이 소요되니... Safe Prime 하나를 생성하는 과정은 생각보다 어렵다. 소요 시간은 초 단위를 넘어선다.