전자 서명 알고리즘 - 해시, 공개키 기반 구조

앞에서 전자 서명을 만들 때 해시 알고리즘을 언급했었습니다.

어떻게 구성되 있는지는 모르지만 결과는 항상 160bit가 나오는 함수라고 소개를 했었습니다.

이 해시라는 것은 전자 서명 뿐만아니라 서버에 암호를 저장할 때도 사용이 됩니다.

따라서 해시 과정을 한 번 자세히 살펴보겠습니다.

 

● Hash

목적 : 메세지의 사이즈를 줄이는 것입니다. (one-way)

해시 알고리즘은 다 open되어 있기 때문에 원문만 알면 누구나 해시를 시킬 수 있습니다.

하지만 해시된 값을 가지고 원문으로 복원하는 것은 절대 불가능 합니다.

 

▶ 암호학적 해시 함수

- Collision - Resistant (충돌방지)

서로 다른 메세지가 똑같은 해시 값을 가질 수 밖에 없습니다. 왜냐하면 큰 사이즈를 한정된 160bit로 줄이는 것이기 때문이죠. 이론상 충돌이 생길 수 밖에 없지만 그럼에도 불구하고 충돌이 너무 자주 생기면 안됩니다. 따라서 최대한 충돌이 생기지 않도록 해시 함수를 만드는 것이 중요한 요건 중 하나입니다.

- One-Wayness (일방향성)

해시값으로 부터 원문을 추측 불가능 해야 합니다.

 

☞ SHA(Secure Hash Algorithm)

입력문의 길이 : 0 < |M| <

이 안에 들어가는 길이의 메세지는 무조건 160bit짜리로 만들어 냅니다.

어떤 길이의 메세지가 들어오더라도 512bit짜리 블럭으로 쪼개서 해쉬를 시킵니다. 그렇다면 원래 들어온 평문이 512bit의 배수가 아니면 Padding을 해서 맞춰주어야 합니다.

 

- Message Padding

원래 메세지 + 1+0....0+원 메세지의 길이(64bits)

패딩시킨 후에 512bit로 짜른 것을

 

개의 블럭으로 표기를 합니다.

 

- 하나의 블럭

32bits로 쪼개면 16개의 word로 구성되게 됩니다.

결국 이 16개의 word를 가지고 해시를 시키는데 이 word가 메세지에 대한 key값으로 사용하게 됩니다.

SHA-1에서 정의된 함수(f)와 keyword(상수)를 이용하여서 한 블럭에 대해서 160bit짜리 해시값을 만들기 위해서는 80회 연산을 수행해서 메세지 다이제스트를 만들게 됩니다.

몇 번의 메세지 블록에 대해서 연산을 수행한다 하더라도 최종적으로 나오는 것은 160bit 메세지 다이제스트가 나옵니다.

 

 

- 각 회전에 사용되는 word 값

까지는 원래 메세지가 가지고 있는 값을 그대로 사용하고 총 80번 회전을 한다고 했기 때문에 총 80번 회전하는 동안 매번 사용되는 값이 다릅니다. 첫번째 회전에서는 , 두번째 회전에서는 ...~까지는 그림에 있는 식을 써줍니다. 예를 들어 16번째 word를 만든다면 13번째, 8번째, 2번째, 0번째 word값을 가지고 XOR을 취한 다음 1bit shift를 시킵니다. 따라서 15까지의 word값만 있으면 이걸 가지고 80개에 해당하는 word값을 다 만들어 낼 수 있습니다.

 

 

 

 

SHA 입니다. 무엇인지 모르겠지만 블록이 5개가 있습니다.

이 과정을 총 80번 수행합니다.

이것으로부터 최종 5개의 다른 블록이 생성이 되고 이걸 쭉 연결하면 최종 160bit 해시값이 생기는 것입니다.

과정이 복잡해보이지만 하나하나 따라가보면 간단합니다.

 

최초에 아무것도 없을 때 메세지 다이제스트를 할때는 A,B,C,D,E는 어떻게 형성이 될까요? 초기값이 있습니다.

 

E블록의 수행과정이 매우 복잡해 보입니다. B,C,D블록이 어떤 f함수를 수행한 뒤 E와 더해지고, A의 값을 5bit shift시킨 값과 더해줍니다.  그리고 이때 W라는 것을 더해줍니다. 이 W가 메세지에서 온 값입니다. 첫번째 round에서는  가 더해지는 것이죠. 두번째 round에서는 가 더해지고요...반복을 수행할 때마다 이 값이 바뀌게 됩니다. 그 다음 K값이 있습니다. 이 값은 상수입니다. 이것도 주어집니다.

 

초기 20번 회전 시에는 K값을 사용을 하고, 그 다음 20번 동안에는 두번째 K값을 사용합니다.

따라서 몇 번째 round이냐에 따라서 사용되는 K값도 고정입니다.

지금까지 H값도 고정, K값도 고정이고 달라지는 건 W값입니다.

 

 

 

f라는 함수도 이미 고정이 되어 있습니다. B,C,D의 값으로 논리연산을 하는 함수입니다.

 

20번씩 round를 나누어서  t값이 뭐가 되느냐에 따라 4가지 f함수를 수행합니다.

 

 

 

각 round마다 이 계산을 하고 나면 결국 W의 값이 매번 바뀌게 되고 원본에서 오는 값이기 때문에 계속 값을 변화시킵니다. 이 과정을 80번 다 수행하고 나면 첫번째 블록에 대한 해시값 160bit가 만들어 집니다. 그 다음 두번째 블록에 대해서 또 이 과정을 합니다. 하기 전에 H값에 이전 블록의 결과가 영향을 주게 됩니다.

 

에 이전 80번 회전해서 나온 A값을 더해줘서 갱신하고 나머지도 마찬가지로 순서대로 H값을 갱신합니다.

 

SHA-1은 이런식으로 동작하고 누구라도 원본이 주어지면 똑같은 해시값을 만들 수 있지만 해시로 부터 몇배에 달하는 원본은 만들어 낼 수 없습니다.

 

 

● 공개키 기반 구조(PKI)

공개키는 데이터의 기밀성도 제공하고 인증도 제공하기 때문에 내용을 감출 수도 있으면서 사용자 인증까지 같이 할 수 있으므로 좋긴 하지만 가장 큰 문제점은 공개키가 공개되다보니 누구나 이 공개키를 위변조 할 수 있다는 것입니다.

공격자가 중간에서 양 쪽 사용자의 공개키를 가로채서 공격자의 공개키를 보내도 양 쪽의 사용자들은 이 것이 상대의 공개키가 맞는지 알 수 없습니다. 왜냐하면 공개키는 랜던값입니다. 이 랜덤값이 사용자와 아무런 관련이 없죠.

따라서 공개키의 인증 또는 증명이 필요해집니다.  

이때부터 정책적인 부분과 인프라가 필요해집니다. 전나라가 통용되어야 사용될 수 있기 때문입니다. 우리나라는 90년대 부터 잘 구축이 되어져서 사용이 20년동안 잘 사용이 되어왔습니다. 이제와서 공개키 기반 구조를 대체할만한 무언가를 찾고 있는 상황입니다.

 

- 인증서(Certificate)

사용자와 공개키를 공식적으로 법적 효력을 갖도록 매칭해주는 증명서입니다. 누구나 공인해주는 인증서이기 때문에 인증 기관에서 발행해주어야만 유효하다고 봐야합니다.

 

- 인증 기관(CA : Certificate Authority)

우리나라에 대표적으로 yessign이 있습니다.

 

- PKI(Public - key infrastructure)

공개키를 사용할 수 있는 모든 재반 환경(공개키+사용자+인증서+인증기관)이 갖추어진 상태

사용자와 공개키에 대한 인증서를 발행하고 이 인증서를 검증할 수 있는 과정이 돌아가는 형태

 

 

- 우리나라 인증 기관 계층 구조

- PAA(정책승인기관)

하위 기관의 정책을 승인하고 공인인증서에 대한 정책을 결정

 

- PCA(정책인증기관)

KISA, yessign같은 기관이 공인인증기관이 맞다는 것을 인증해주는 기관

 

- CA(인증 기관)

yessign,NCA와 같은 기관,기업용 등의 인증서를 직접 발행하는 기관

 

- RA(등록기관)

은행같은 기관, 사용자의 신분을 확인해주고 인증서 발행할 수 있도록 도움

 

 

다음 글에서 공인인증서에 관련해서 더 깊게 공부해 보겠습니다~