코딩스타트

https://github.com/robert-bor/aho-corasick/tree/master/src/main/java/org/ahocorasick/trie

https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm

오늘 포스팅할 내용은 HMAC에 대한 설명이다. 우선 HMAC에 대해 설명하기 이전에 요즘 대부분이 사용하고 있는 토큰인증 방식에 이용되는 JWT(Json Web Token)이다. 그렇다면 JWT란 무엇일까?

JSON Web Token은 웹표준(RFC-7519)으로서 두 개체에서 JSON객체를 사용하여 가볍고 자가수용적인(self-contained)방식으로 인증정보를 안정성있게 주고 받기 위해 만들어진 토큰이다. 우선 JWT토큰은 수많은 프로그래밍 언어에서 공통적으로 사용할 수 있는 인증 토큰이다. 그리고 JWT는 자체적으로 필요한 모든 정보(in Claims)를 가지고 있다. JWT 시스템에서 발급된 토큰은, 토큰에 대한 기본정보,전달할 정보(ex. 유저정보,권한 등..) 그리고 토큰의 signature를 포함하고 있다. 그렇다면 왜 토큰 방식의 인증방법을 채택하는 것일까?

Stateless 서버

Stateless 서버를 설명하기 이전에 Stateful서버가 무엇인지 먼저 알아본다. Stateful 서버는 클라이언트에게서 요청을 받을 때마다, 클라이언트의 상태를 계속해서 유지하고, 이 정보를 이용하여 서비스제공을 한다. Stateful 서버의 예제로는 HttpSession을 서버에 유지하고 있는 WAS이다. 예를들어 사용자가 로그인하면 로그인한 사용자의 정보를 자체 메모리에 갖고 있는다. 그리고 매 사용자 요청에 자신의 메모리에 담긴 세션객체를 이용한다. 만약 사용자가 많아 진다면 메모리에 담긴 세션객체가 많아질 것이고, 그렇다면 서버의 램에 많은 부하가 갈것이다. 그렇기 때문에 Stateless서버로 아키텍쳐를 잡고 서비스를 운영하면 상태를 유지할 필요가 없기때문에 서버에 부담도 주는 것과 동시에 확장성 또한 매우 높아진다.

<서버기반 인증>

<토큰기반 인증>

그렇다면 토큰기반인증에 사용되는 JWT란 진짜 무엇인가?

JWT의 구성

JWT는 "."을 구분으로 3가지의 문자열로 구성되어 있다.

이렇게 3가지 부분으로 나뉘어있는 토큰을 하나하나 설명해본다.

헤더(Header)

헤더는 두가지의 정보를 가지고 있다.

• typ : 토큰의 타입을 지정한다. 여기서는 JWT.
• alg : 해싱 알고리즘을 지정한다. 해싱 알고리즘으로는 보통 HMAC SHA256 혹은 RSA가 사용된다. 오늘 설명할 부분이기도 하다.

이 JSON 형태의 헤더정보를 base64로 인코딩하게 되면 토큰의 첫번째 헤더부분에 위치하게 된다.

정보(Payload)

Payload 부분에는 토큰에 담을 정보가 들어있다. Payload에 담기는 정보의 한 조각을 'Claim'이라고 부르고, 이는 키-값형태의 한쌍을 의미한다. 그렇다면 Payload는 'Claim'들의 모임인 'Claims'가 된다. 이런 클레임에는 크게 세분류로 나뉘어져있다.

• 등록된(registered) 클레임
• 공개(public)클레임
• 비공개(private)클레임

등록된 클레임

• iss : 토큰 발급자(issuer)
• sub : 토큰 제목(subject)
• aud : 토큰 대상자(audience)
• exp : 토큰의 만료시간, 시간은 NumericDate 형식으로 되어있어야한다.(ex. 1241421414124141)
• iat : 토큰이 발급된 시간(issued at), 이 값을 이용하여 토큰의 age를 판단할 수 있다.
• jti : JWT의 고유 식별자로써, 주로 중복적인 처리를 방지하기 위하여 사용된다.

위에 설명된 것보다 등록된 클레임 종류는 더 있을 것이다.

공개 클레임

공개클레임들은 충돌이 방지된 이름을 가지고 있어야한다. 충돌을 방지하기 위해서는, 클레임 이름을 URI형식으로 짓는다.

비공개 클레임

등록된 클레임도 아니고, 공개된 클레임도 아니다. 양 측간에 협의하에 사용되는 클레임 이름들이다. 공개 클레임과는 달리 이름이 중복되어 충돌이 될 수 있다.

이러한 Payload가 base64로 인코딩되면 토큰의 두번째 자리에 위치하게 된다.

서명

사실 오늘 포스팅한 주제에 해당 되는 부분이다. 이부분은 헤더의 인코딩 값과, Payload의 인코딩 값을 합친 후 주어진 비밀키로 해쉬 값을 생성한다. 이렇게 만든 해쉬를 다시 base64로 인코딩하면 세번째 자리에 위치하게 되는 값이 된다. 그렇다면 서명은 왜 필요한 것일까?

JWT토큰 인증 방법의 큰 장점 중 하나는 토큰의 유효성을 검사하기 위하여 Resource Server(보호된 API를 가지고 있는 서버)가 인증서버(Authorization Server)로 토큰을 전송하지 않는 다는 점이다. JWT 토큰을 사용하지 않는 토큰 인증 방법은 Resource Server가 토큰값을 받으면 이 토큰값 검사를 위하여 인증 서버 혹은 토큰이 저장된 저장소에서 토큰을 꺼내와 토큰의 유효성을 검사하곤 했다. 사용자가 적으면 문제 없지만 사용자가 대고객이라면? 인증서버 혹은 토큰의 저장소(Redis,RDBMS)에 큰 무리가 갈것이다. 하지만 JWT 토큰은 자체적으로 토큰 유효성 검사가 가능하다 ! 그 이유는 오늘 설명할 HMAC이다.(물론 HMAC이 아니라 RSA도 있다.) Resource Server는 토큰 유효성을 검사하기 위해 인증서버 혹은 토큰이 저장된 저장소에서 토큰을 가져올 필요가 없다. 단순히 JWT토큰을 받아서 해당 토큰이 위변조되었는지만 확인하여 위변조가 되지 않으면 JWT토큰 내부에서 사용자 정보를 꺼내 사용할 수 있기 때문이다. 바로 이렇게 토큰의 위변조가 있었는지 혹은 위변조를 방지하는 기법 중 하나를 HMAC(Hash-based Message Authentication)이라고 한다.

해싱은 원문(Plain Text)을 일정 길이의 바이트로 변환하는데 그 결과가 유일하여 긴 문장의 빠른 검색을 위한 키 값으로 많이 쓰인다. 그리고 해시된 결과를 사용해서 거꾸로 원문을 복구할 수 없다는 것이 해시를 사용하는 고유한 가치라고 할 수 있다. 이러한 해시의 특성을 사용하여 데이터의 위변조 여부를 알아낼 수 있다.

출처 : http://blog.jakeymvc.com/sso-hmac/

1. 사전에 Sender와 Receiver는 별도 채널로 해시에 사용할 키(Share key)를 공유한다. 그리고, 양쪽에서 사용할 해시 알고리즘을 정한다.
2. Sender는 공유키를 사용해서 UserId를 해시한다.
3. Sender는 원본 UserId와 그 해시결과(HMAC)을 쿼리스트링 값으로 Receiver에게 전달한다.
4. Receiver는 받은 UserId를 공유키를 사용하여 같은 알고리즘으로 해시한 결과(Receiver's HMAC)를 만든다.
5. Receiver가 만든 HMAC과 쿼리스트링으로 받은 HMAC이 같다면 UserId는 변경되지 않았다고 신뢰할 수 있다.

UserId + Sharekey = HMAC 이라는 공식에서 UserId를 변경한다면 그 결과인 HMAC도 변경된다. 따라서, 위조한 UserId가 Receiver에서 인정 받으려면 똑같은 해싱 과정을 거쳐 HMAC을 제공해야하는데, 공유키와 해시 알고리즘을 알지 못하면 어려운 일인 것이다.

즉, JWT는 이러한 위변조 방지 방법을 이용하여 인증서버 없이도 Resource Server에서 안전한 토큰 유효성 검사가 가능한 것이다. 물론 우리가 인증에 사용하는 JWT는 위에서 설명한 HMAC 플로우랑은 조금 다를 수 있다. 하지만 이번 포스팅의 목적은 이러한 HMAC을 이용하여 토큰의 유효성을 검사한다라는 것을 알기 위한 포스팅이기에 직접 프로젝트에 JWT인증 방법을 도입하려면 적당한 플로우를 적용시켜야 할 것이다.

1. 그래프 다익스트라 - 네트워크 복구(백준 2211번)

2. 다익스트라 알고리즘을 이용한 문제풀이

다익스트라 알고리즘을 이용하여 최소 경로를 구하는 문제이다. 하지만 여기에서 최소경로만 구하는 것이 아니라 최소 경로에 해당하는 노드들의 연결까지 출력하는 문제이다.(최소 경로 값만 출력하면 쉬운문제이다. 앞에서 다루었던 최소경로,최소비용 문제를 참고하면 된다. 다익스트라 알고리즘 설명은 따로 하지 않는다.) 위의 코드는 조금은 비효율적인 코드라서 나중에 수정하기는 하겠지만, 이 코드를 설명하면 무한대 값으로 초기화되있는 노드들의 값을 최단 경로로 변경될때 마다 result라는 리스트 배열에 두 노드의 값을 넣어 준다. 하지만 값을 넣어주기 전에 이전에 같은 노드의 값이 들어와있는지 반복문을 통해 검사해 만약 이전에 이 노드 값이 들어오지 않았다면 그냥 result 리스트 배열에 값을 넣어주고 만약 이전에 같은 노드가 들어왔었다면 count--해주고 이전에 들어온 값을 제거한 후에 최단경로가 변경된 노드의 값을 리스트 배열에 넣어준다. 그리고 모든 알고리즘이 종료된 후에는 최단 경로에 해당하는 노드들의 연결이 배열 리스트에 저장이 되어 있게된다.

1. 다이나믹 프로그래밍 - 동전1 (백준 2293번)

2. 다이나믹 프로그래밍을 이용한 문제풀이

이 문제를 예를 들어 설명한다면, dp메소드에서 반복문에 들어가게 되면 우선 memo[0]=1 이라고 초기화를 한다. 이 것은 동전을 아무 것도 선택하지 않는 경우를 한 경우로 보고 1로 초기화하는 것이다.(확률에서 선택하지 않는 것도 하나를 1로 생각하는 것과 같다 보면된다.) 그리고 반복문을 들어가게 된다. 여기서 i=0 일때를 보면 j-coin[i]>=0 에서 j=1부터 성립을 하게 된다. 그래서 memo[1]=memo[1]+memo[0] 에서 memo[1]=1 이 되게 된다. 여기서는 coin[1]이 1이므로 k+1까지 모두 1가지 경우로 값이 대입되게 된다. 하지만 2,3 혹은 어느 값이 들어오더라도 그 값의 배수에만 경우의 수 1이 들어가게 된다. 예를 들어 coin[1]=2일때 j가 2부터 j-coin[i]>=0 이 성립하고 memo[j]=memo[j]+memo[j-coin[i]] 값은 2의 배수인 경우에만 1 값이 들어오게 된다. 여기서 보면 특이한 것이 coin[1]=2 이고 j=2면 memo[j-2=0] 의 경우를 더해주고 j=4 이면 memo[j-2=2]의 경우의 수를 더해주고 규칙이 보일 것이다. 그럼 문제의 조건으로 돌아와서 coin[2]일때를 보면 j=2 일경우부터 조건문이 성립하고 memo[2]=memo[2]+memo[2-2] 이 된다. 이 말은 1과 2를 이용해 2를 만드는 경우의 수는 1->2개(1을 2개이용) , 1->0 && 2->1(2를 1개이용) 두가지의 경우의 수가 나온다. 여기서 1->2는 i=0일때 1로 2를 만들수 있는 경우의 수(이전 경우의수,이값은 빨간색으로) 1->0 && 2->1은 1을 0개 선택하고 2를 하나 선택한 경우(파란색)이다. 이 경우의 수를 색으로 표현한다면 

memo[2]=memo[2]+memo[0] 이 된다. 여기서의 이해가 중요하다. 앞의 memo[2]는 현재의 동전이 아니라 이전의 동전으로 2를 만들수 있는 방법, memo[0]은 2라는 동전을 하나 선택해서 2라는 값을 만들었으므로 이전의 동전으로 0이라는 값을 만드는 경우의 수를 더하는 것이다. 그러면 더 나아가서 memo[6]=memo[6]+memo[4] 라는 값을 보자 앞의 memo[6]은 이전까지의 동전들로 6을 만드는 경우이다. 즉, 1 1 1 1 1 1, 그리고 나머지 경우를 보게되면 1 1 1 1 2, 1 1 2 2, 2 2 2 라는 경우가 남아있다. 여기서 맨위 2를 빼면 1 1 1 1, 1 1 2, 2 2라는 경우는 어느 경우인가? 2까지의 동전을 사용해 memo[4]를 만든 경우가 된다. 이런식으로 마지막 동전까지 반복을 하게 된다.

1. 문자열 처리 - 명령 프롬프트(백준 1032번)

2.문제 풀이

이 문제는 간단히 주어진 모든 문자열에서 같은 위치에 같은 문자를 갖는 다면 그 문자를 그대로, 만약 하나의 문자열이라도 그 위치의 문자가 다르다면 '?'를 출력하는 문제이다. 물론 위의 코드보다 더욱 효율적인 코드는 있겠지만 실행이 되는 코드이고 코드를 직관적으로 분석하기 편하다. 모든 문자열의 길이는 같으므로(문제풀기가 수월한 이유이다.) 첫번째 배열의 문자열을 기준으로 하여 그 외의 모든 문자열을 반복문으로 불러와서 각 위치의 문자가 같은지만 비교하면 된다. 만약 같다면 그 문자를 스트링에 넣고 만약 한 글자라도 다르다면 isSame에 false가 들어가 바로 반복문을 벗어나 str에 '?'를 넣게 된다. 이렇게 문자열의 길이만큼 반복문을 실행하면 되는 것이다.

1. 그래프 이론 - 섬의 개수 (백준 4963번)

2. 그래프 이론을 이용한 문제 풀이

문제의 풀이는 배열 안에 섬의 표시가 1로 표시가 되고 가로, 세로 및 대각선이 연결된 섬으로 인식이 되는 것이다. 1행부터 열을 탐색하여 1이 나오는 배열의 인덱스를 찾게 되면 그 배열의 좌표를 기준으로 countIsland 메소드를 호출하게 된다. 메소드 안에 좌표가 전달되면 전역 변수로 선언한 dx,dy 배열을 이용하여 연결된 섬을 찾게 된다. 좌표는 시작으로 부터 왼쪽, 왼쪽대각선위, 위, 오른쪽 대각선위, 오른쪽, 오른쪽 대각선 아래, 아래, 왼쪽대각선 아래를 뜻하게 된다. 그렇게 8방을 반복문으로 하나하나 따져봐서 인접한 1을 찾게 되는 것이다. 이 반복문 안에 첫번째 조건문이 뜻하는 바는 처음에 입력값으로 선언된 높이와 넓이의 직사각형을 벗어나는지를 따져보는 것이다. 만약 직사각형의 범위를 벗어나지 않으면서 팔방의 위치에 1이 존재한다면? 그 좌표를 방문했다는 표시로 모두 2로 배열의 값을 변경해준다.(그러면 더 이상 이섬은 탐색하지 않는다.)그리고 이섬은 연결된 섬으로 간주하고 그 섬의 좌표를 기준으로 countIsland 메소드를 다시 호출하게 된다. 즉, 그래프의 깊이우선 탐색을 실행하여 탐색하다가 더 이상 연결된 섬이 없을 때는 백트랙킹으로 이전의 좌표로 돌아가 이 좌표를 기준으로 다시 깊이 우선탐색을 실행하는 것이다. 그러다가 더 이상 탐색할 곳이 없게되면 함수를 종료하게 된다.(이 과정까지가 처음 발견된 1의 좌표를 기준으로 연결된 섬을 모두 탐색하고 난 후 종료하는 과정이다.) 

1.다이나믹 프로그래밍 - 다리 놓기 (백준 1010번)

2.다이나믹 프로그래밍 & 조합을 이용한 문제풀이

1)조합을 이용한 문제풀이

첫번째 풀이는 조합을 이용한 풀이입니다. 예제 입력에서 29개의 다리 중에서 13개의 다리를 겹치지 않고 놓을 경우의 수는 67863913개입니다. 겹치지 않는다? 단순히 그냥 29개의 다리중에 13개의 다리를 뽑는 경우의 수를 구하면 됩니다. 굳이 겹치는 경우를 고려하지 않아도 되는 것입니다. 13C29(13콤비네이션29) 의 값을 구해주는 로직만 짜주면 답은 쉽게 나오게 됩니다.

2)DP를 이용한 풀이

예를 들어 서쪽에는 3개의 사이트 동쪽에는 5개의 사이트가 있다고 가정한다면 bridge(3,5) 메소드를 호출하게 된다. 여기서 반복문이 뜻하는 바는 i==4부터 i==2까지 값을 감소시키며 bridge 함수를 호출시키는 것이다. 이것은? i==4라면 서쪽의 첫번째 사이트가 동쪽의 1번 사이트와 다리가 연결되어 남은 2개의 서쪽사이트와 4개의 동쪽사이트로 연결할 수 있는 다리의 경우를 구하면 되는 것이고, i==3이면 서쪽의 1번 사이트가 동쪽의 2번사이트와 연결되어 남은 2개의 서쪽사이트와 동쪽의 2번 밑의 3,4,5 3개의 사이트와 연결될 경우의 수를 구한다. 이렇게 쭉쭉가다가 서쪽과 동쪽의 남은 사이트 수가 같을 때까지 반복한다. 이런 것이 서쪽 사이트가 하나씩 줄어 가며 반복되는 것이다. 그리고 마지막 서쪽사이트가 함수에 들어 오게 된다면 초기화된 값을 바탕으로 memo[n][m]의 값을 구하게 되는 것이다. 

1.다이나믹 프로그래밍 - 계단 오르기 (백준 2579번)

2.다이나믹 프로그래밍을 이용한 풀이

이 문제 풀이의 핵심은 각 계단을 마지막 계단으로 보는 것입니다. 예를 들어 가장 마지막 계단을 오르는 경우의 수는 이전 계단을 밟는 경우와 전전계단을 밟는 경우 총 2가지입니다. 여기에서 이전 계단을 밟는 경우에서 upStair(n-3) 재귀호출까지 더해주는 이유는 3번 연속된 계단을 밟을 수 없기 때문입니다. 이 두가지 경우 중에서 큰수를 Math 클래스의 max 메소드를 이용해서 구합니다. 그래서 이 두가지의 경우로 재귀호출을 통해 다시 함수에 들어가게 되면 그 계단을 다시 마지막 계단으로 보고 다시 위의 두 가지 경우로 나뉘어서 재귀 호출을 반복하게 됩니다. 이 과정을 반복하다가 초기화된 값까지 다다르게 되면 모든 값이 메모된 값을 이용하여 총합을 구할 수 있게 됩니다. 여기에서 2번째 계단을 밟은 가장 큰 경우의 수는 1번째 계단을 밟는 경우이므로 stairArr[1]+stairArr[2] 를 통해 초기화를 해줍니다.