전자 서명 알고리즘 - RSA

개인키,공개키를 생성하는 방법은 전의 RSA 암호 알고리즘때의 설명과 동일합니다.

 

● 사용자 public key(n,e)

임의의 두 소수 p,q의 곱으로 이루어진 합성수 n만 공개를 하고 어떤 p,q로 곱해져있는지 절대로 공개하면 안됩니다.

(p-1)(q-1)의 서로소인 아무거나 e를 공개키로 합니다.

 

● 사용자 private key(n,d)

d를 구하려면 e는 공개된 값이고 은 multiplicative group이기 때문에 역원이 존재합니다. d는 mod (p-1)(q-1)상에서 역원만 구하면 되는데 p,q를 알아야 구할 수 있습니다. p,q만 알면 이미 알려진 e의 역원 구하는 것은 쉽습니다. 따라서 n에 대한 p,q를 아는 사람만 비밀키를 구할 수가 있습니다.

 

● Signature

사용자가 어떤 메세지에 대해서 자신의 서명을 생성하는 겁니다. 그래서 메세지 M에 사용자의 개인키(d)를 사용합니다.

 

● Verification

검증은 누구나 할 수 있어야 합니다. e를 아는 사람은 이 서명이 e의 공개키를 갖는 사람이 만든 것이다라는 걸 누구나 다 검증 가능합니다. 왜냐하면 원본 메세지가 나오게 됩니다.

 

현재 이 알고리즘에는 문제가 있습니다.

 

공격자가 동일한 사용자로 부터 서명 두개를 수집했습니다.

두개의 서로 다른 메세지에 대한 서명입니다.

이걸로 부터 공격자가 에 대한 새로운 서명 S'를 생성 가능하다는 겁니다.(이 유효하든 말든 상관이 없습니다. 서명자가 직접 생성하지 않은 문서에 대한 서명을 생성할 수 있다는 거 자체가 문제이기 때문이죠.)

서명 두개를 곱해 봤더니 에 대해서 서명이 만들어지게 됩니다.

 

어떻게 해결할 수 있을까요?

해시를 사용하는 겁니다.

 

 

이 되겠죠.

이것은 실제 메세지 두개를 곱해서 서명을 생성한 것과 값이 다릅니다.

최종적으로 서명은 이렇습니다. 이는 d(개인키)를 아는 사람만 생성할 수 있게 되죠.

노출된 값으로 이렇게 저렇게 해서 만들 수 없다는 게 중요합니다. 따라서 해시를 사용하면 무결성과 재사용을 방지할 수 있습니다.

다음에는 DSA 알고리즘에 대해서 살펴보겠습니다~