Techit 13th 1st

Huisu·2023년 7월 10일

JWT Token divide & conquer spring security

Techit

목록 보기

30/42

Divide & Conquer

주유소

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

서브태스크

번호	배점	제한
1	17	모든 주유소의 리터당 가격은 1원이다.
2	41	2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다.
3	42	원래의 제약조건 이외에 아무 제약조건이 없다.

예제 입력 1

4
2 3 1
5 2 4 1

예제 입력 2

4
3 3 4
1 1 1 1

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/13305
public class three13305 {
    public long solution () throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long cityCount = Integer.parseInt(reader.readLine());

        StringTokenizer cityDistToken = new StringTokenizer(reader.readLine());
        // 각 도시들 간의 거리기 때문에 크기는 n - 1
        long[] cityDistance = new long[(int) (cityCount - 1)];
        for (int i = 0; i < cityCount - 1; i++) {
            cityDistance[i] = Integer.parseInt(cityDistToken.nextToken());
        }

        StringTokenizer cityFuelToken = new StringTokenizer(reader.readLine());
        long[] cityFuel = new long[(int) cityCount];
        for (int i = 0; i < cityCount; i++) {
            cityFuel[i] = Integer.parseInt(cityFuelToken.nextToken());
        }

        // 여태까지 확인한 최소 기름값 저장할 변수
        long currentMin = Integer.MAX_VALUE;
        // 현재 도시에서 현재 도시보다 기름값이 싼 도시까지 걸린 거리
        long needToGo = 0;
        // 총 주유비
        long totalPrice = 0;
        // 이동하는 횟수 만큼만 반복
        for (int i = 0; i < cityCount - 1; i++) {
            // 현재 도시의 기름값이 여태까지 중 제일 싸다
            if (cityFuel[i] < currentMin) {
                // 이 도시까지 도달하는 데 걸린 거리 만큼은
                // 이전 최소값 도시에서 넣어야 한다
                totalPrice += currentMin * needToGo;
                // 기름값 최솟값 갱신
                currentMin = cityFuel[i];
                // 여기서부터 다음 도시까지의 거리
                needToGo = cityDistance[i];
            } else {
                // 주유 안 하고 지나치니까 거리 더해 주기
                needToGo += cityDistance[i];
            }
        }
        // 마지막 주유비를 계산한다
        return totalPrice + needToGo * currentMin;
    }
    public static void main(String[] args) throws IOException {
        System.out.println(new three13305().solution());
    }
}

분할 정복

분할 정복 알고리즘은 큰 문제를 나누어서 풀고 그 결과를 조합해서 문제를 해결하는 알고리즘 기법이다.

분할: 해결할 문제를 여러 개의 작은 문제로 나눈다.
정복: 작은 단위의 문제를 해결한다.
조합: 해결한 작은 단위 문제들을 합해 원래 문제의 답을 구한다.

하노이의 탑

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

예제 입력 1

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// https://www.acmicpc.net/problem/11729
public class one11729 {
    private StringBuilder towerBuilder;
    private int[] pillars = new int[] {1, 2, 3};
    public void solution() throws IOException {
        int n = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
        this.towerBuilder = new StringBuilder();
        this.towerBuilder.append((int) (Math.pow(2, n) - 1)).append('\n');
        hanoi(n, 1, 3, 2);
        System.out.println(this.towerBuilder);
    }

    public void hanoi(int height, int start, int end, int other) {
        // height: 옮기고자 하는 탑의 높이
        // start: 시작 위치
        // end: 목표 위치
        // other: 이동하지 않는 위치 -> 재귀 호출 시에는 end로 바로 가지 않고 other로 바로 보내야 하기 때문
        if (height == 1) {
            // 하나짜리 원반은 바로 이동
            this.towerBuilder.append(start + " " + end + "\n");
        }
        else {
            // 하나가 아니라면
            // N 보다 작은 원반들을 start에서 other로
            hanoi(height - 1, start, other, end);
            // n 번째 원반을 start에서 end로 이동
            this.towerBuilder.append(start + " " + end + "\n");
            // n보다 작은 원반들을 other에서 end로
            hanoi(height - 1, other, end, start);
        }
    }

    public static void main(String[] args) throws IOException {
        new one11729().solution();
    }
}

병합 정렬

분할 정복 기법을 이용한 대표적인 정렬 알고리즘이다. 정렬되지 않은 배열이 있을 때, 배열을 두 개의 동일한 크기의 배열로 나누고 각 배열의 원소가 하나씩 남을 때까지 반복한다. 이후 나눠진 배열을 2개씩 정렬하면서 하나의 배열로 병합하는 과정이다.

public class MergeSort {
    public void sort(int[] arr) {
        // 비웠거나 길이가 1 이하라면 정렬 필요 없음
        if (arr == null || arr.length <= 1) {
            return;
        }
        mergeSort(arr, 0, arr.length -1);
    }

    public void mergeSort(
            int[] arr,
            int left,
            int right
    ) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public void merge(int[] arr, int left, int mid, int right) {
        // 왼쪽 배열과 오른쪽 배열의 크기
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 배열을 복사한다
        int[] leftArr = Arrays.copyOfRange(arr, left, left + n1);
        int[] rightArr = Arrays.copyOfRange(arr, mid + 1, mid + 1 + n2);

        // 임시 배열 두 개를 앞쪽 원소부터 각각 비교하면서
        // 더 작은 원소를 원본 배열에 순서 대로 저장
        // 왼쪽 배열 index
        int i = 0;
        int j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            // 왼쪽 배열 값이 더 작거나 같을 때
            if(leftArr[i] <= rightArr[j]) {
                // 원본 배열에 저장 후
                arr[k] = leftArr[i];
                // 왼쪽 배열의 다음 원소 지정
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            // 원본 배열의 다음 저장 위치
            k++;
        }
        // 왼쪽 배열에 원소가 남았으면 마저 저장
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        // 오른쪽 배열에 원소가 남았으면 마저 저장
        while(j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 9, 2, 4, 7, 3, 6, 8};
        new MergeSort().sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Spring Security

Spring Security & Filter

Spring Security는 JAVA Servlet의 Filter를 이용해 그 기능을 제공한다. Spring에서 만든 Filter의 동작을 알아보자. 필터는 스프링의 범위 바깥에 있는 것이다. 스프링 부트를 사용하는 입장에서는 필터를 관리하는 톰캣마저도 한 프로젝트에 정의되어 있기 때문에 @Component 등의 어노테이션을 통해 어느 정도 자동화의 선상에 올려 둘 수 있다.

필터는 하나로 구성되어 있지 않다. JAVA Servlet이 요청을 실제로 처리하고, 요청을 거르는 역할을 필터가 한다. 필터는 한두 개로 만들어지는 것이 아니라 doFilter라는 메소드를 만들어 FilterChatin 객체를 통해 순차적으로 사용한다.

기본적인 Servlet Filter는 Spring Application과는 별도이기 때문에 Bean 객체를 찾지 못한다. 그래서 Spring에서는 DelegatingFilterProxy를 통해 Bean 객체 찾을 수 있는 Filter를 만들어 준다.

Spring Security에서는 이 DelagatingFilterProxy를 활용해 FilterChainProxy를 등록한다. FilterChainProxy에는 다시 우리가 구성한 SecurityFilterChain을 등록한다. 그리고 이 SecurityFilterChain에 우리가 만든 Filter를 등록하고 인증을 진행할 수 있다.

JWT를 이용한 인증

JWT는 저장해야 할 필요가 있다. 이후로 인증을 필요로 하는 기능들을 사용할 때 쿠키를 첨부하는 것처럼 이 토큰을 같이 붙여서 보내야 한다. 즉 클라이언트가 JWT만 보내면 서버는 해당 JWT만 해석해서 보내 주는 것이다.

일반적으로 JWT는 Header에 포함해서 보낸다. 중에 특히 자신의 인증 정볼르 증명할 때는 Authorization이라는 이름의 헤더를 사용한다. JWT의 경우 Bearer {JWT Token} 형태로 전송하는 경우가 많다. 이를 Bearer Authentication (Token Authentication)이라고 부른다. 클라이언트가 Header에 JWT를 능동적으로 추가해 줘야 한다. 토큰의 보관도 클라이언트가 직접 진행해야 한다. 서버는 클라이언트에 대한 데이터를 일절 저장하지 않는다.

JWT가 포함된 요청의 인증 방법

요청에 Authorization 헤더가 존재하는지 확인한다. 없다면 비인증 사용자이다.
Header에 Bearer로 시작하는지 확인한다. 아니라면 잘못된 인증 정보. 비인증 사용자이다.
Header의 값 중 JWT Token 값이 정상적인지 확인한다. 아니라면 비인증 사용자이다.
JWT에서 사용자 정보를 해석해 인증상태를 기록하고, 인증이 필요한 경로를 허가한다. JWT를 검증해 인증 상태를 기록하는 필터를 만들어서 사용한다.

JwtTokenUtils에서 JWT가 유효한지 판단하는 메소드를 만들면 다음과 같다.

@Slf4j
@Component
// JWT 생성, 인증 등의 기능을 가지고 있을 컴포넌트
public class JwtTokenUtils {
    // JWT는 암호화를 거쳐서 만들어지는데
    // 이를 위해서 암호키가 필요
    private final Key signingKey;
    **private final JwtParser jwtParser; // JWT 해석키**
    public JwtTokenUtils(
            @Value("${jwt.secret}")
            String jwtSecret) {
        this.signingKey = Keys.hmacShaKeyFor(jwtSecret.getBytes());
        **this.jwtParser = Jwts
                .parserBuilder()
                .setSigningKey(this.signingKey)
                .build();**
    }

    // 1. JWT가 유효한지 판단하는 메소드
    // jjwt 라이브러리에서는 JWT를 해석하는 과정에서
    // 유효하지 않으면 예외 발생
    public boolean validate(String token) {
        try {
            // 정당한 JWT면 true,
            // parseClaimsJws: 암호화된 JWT를 해석하기 위한 메소드
            jwtParser.parseClaimsJwt(token);
            // 정당하지 않은 JWT이면 false
            return true;
        } catch (Exception e) {
            log.warn("invalid jwt");
            return false;
        }
    }
}

OncePerRequestFilter

필터를 구현하기 위해 저희는 추상클래스 OncePerRequestFilter 를 사용한다. 이는 Spring에서 제공하는 클래스 중 하나로, 비동기 처리 또는 forward / redirect 등의 특정 상황에서 Filter의 기능이 복수 번 사용될 수 있을 경우, 실제로는 한번만 사용되도록 보장하는 Filter 객체이다.

이 클래스를 상속받으면 일반적인 doFilter 대신 doFilterInternal 을 구현한다.

public class JwtTokenFilter extends OncePerRequestFilter {
    private final JwtTokenUtils jwtTokenUtils;

    public JwtTokenFilter(JwtTokenUtils jwtTokenUtils) {
        this.jwtTokenUtils = jwtTokenUtils;
    }

    @Override
    protected void doFilterInternal(
            HttpServletRequest request,
            HttpServletResponse response,
            FilterChain filterChain)
            throws ServletException, IOException {
        filterChain.doFilter(request, response);
    }
}

이 클래스를 상속받으면 일반적인 doFilter 대신 doFilterInternal을 구현해야 한다. 먼저 Authorization 헤더가 존재하는지 확인하고, 존재한다면 이 헤더가 Bearer 로 시작하는지 확인하고, 이후 뒤의 JWT가 유효한지까지 검사한다.

public class JwtTokenFilter extends OncePerRequestFilter {
    private final JwtTokenUtils jwtTokenUtils;

    public JwtTokenFilter(JwtTokenUtils jwtTokenUtils) {
        this.jwtTokenUtils = jwtTokenUtils;
    }

    @Override
    protected void doFilterInternal(
            HttpServletRequest request,
            HttpServletResponse response,
            FilterChain filterChain)
            throws ServletException, IOException {
				String authHeader 
		            = request.getHeader(HttpHeaders.AUTHORIZATION);
		    if (authHeader != null && authHeader.startsWith("Bearer ")) {
		        String token = authHeader.split(" ")[1];
		        if (jwtTokenUtils.validate(token)){
		            // TODO
		        }
		        else {
		            log.warn("jwt validation failed");
		        }
		    }
        filterChain.doFilter(request, response);
    }
}

SecurityContext

이전에 인증이 된 사용자에 대해서 사용자 정보를 받아오기 위해 SecurityContextHolder를 사용했었다. 인증에 성공한 사용자를 똑같이 SecurityContextHolder에 저장하면, Spring Security가 사용자를 인증된 사용자로 판단한다. 이때 만들어서 저장하는 객체는 Authentication의 구현체이며. 일반적으로 UsernamePasswordAuthenticationToken을 구현체로 활용한다.

@Slf4j
@Component
// 사용자가 Header에 포함한 JWT를 해석하고
// 그에 따라 사용자가 인증된 상태인지를 확인하는 용도
public class JwtTokenFilter extends OncePerRequestFilter {
    private final JwtTokenUtils jwtTokenUtils;

    public JwtTokenFilter(JwtTokenUtils jwtTokenUtils) {
        this.jwtTokenUtils = jwtTokenUtils;
    }

    @Override
    protected void doFilterInternal(
            HttpServletRequest request,
            HttpServletResponse response,
            FilterChain filterChain)
            throws ServletException, IOException {
        // JWT가 포함되어 있으면 포함되어 있는 헤더를 요청
        String authHeader = request.getHeader(HttpHeaders.AUTHORIZATION);
        // authHeader가 null이 아니면서 Bearer로 구성되어 있어야
        // 정상적인 인증 정보다
        if (authHeader != null && authHeader.startsWith("Bearer ")) {
            // TODO JWT를 회수하여 JWT가 정상적인지 확인
            String jwtToken = authHeader.split(" ")[1];
            if(!jwtTokenUtils.validate(jwtToken)) {
                log.warn("jwt validation failed");
                // 웹상의 많은 예시
                // SecurityContextHolder.getContext().setAuthentication();
                // 이왕이면 emptyContext를 새로 만들어서 대입해
                // https://docs.spring.io/spring-security/reference/servlet/authentication/architecture.html
                // security 공식 문서 추천
                // 인증, 보안과 관련된 맥락을 새로 만들고 있음
                **SecurityContext context
                        = SecurityContextHolder.createEmptyContext();**
                // JWT에서 사용자 이름을 가져오기
                **String username = jwtTokenUtils
                        .parseClaims(jwtToken)
                        .getSubject();**
                // 인증 정보 생성
                **AbstractAuthenticationToken abstractAuthenticationToken
                        = new UsernamePasswordAuthenticationToken(
                        CustomUserDetails.builder()
                                .username(username)
                                .build(),
                        jwtToken, // 비밀번호 대신 토큰
                        new ArrayList<>() // 권한 관련
                );**
                // SecurityContext에 사용자 정보 설정
                context.setAuthentication(abstractAuthenticationToken);
                // SecurityContextHolder에 SecurityContext 설정
                SecurityContextHolder.setContext(context);
                log.info("set security context with jwt");
            }
            else {
                log.info("complete");
            }
        }
        filterChain.doFilter(request, response);
    }
}

마지막으로 이 필터를 WebSecurityConfig 를 통해 FilterChain에 등록한다.

@Configuration
public class WebSecurityConfig {
    **private final JwtTokenFilter jwtTokenFilter;

    public WebSecurityConfig(JwtTokenFilter jwtTokenFilter) {
        this.jwtTokenFilter = jwtTokenFilter;
    }**

    @Bean  // 메소드의 결과를 Bean 객체로 등록해주는 어노테이션
    public SecurityFilterChain securityFilterChain(
            // DI 자동으로 설정됨, 빌더 패턴 처럼 쓴다.
            HttpSecurity http
    )
            throws Exception {
        http
                // CSRF: Cross Site Request Forgery
                .csrf(AbstractHttpConfigurer::disable)
                // 1. requestMatchers를 통해 설정할 URL 지정
                // 2. permitAll(), authenticated() 등을 통해 어떤 사용자가
                //    접근 가능한지 설정
                .authorizeHttpRequests(
                        authHttp -> authHttp // HTTP 요청 허가 관련 설정을 하고 싶다.
                                // requestMatchers == 어떤 URL로 오는 요청에 대하여 설정하는지
                                // permitAll() == 누가 요청해도 허가한다.
                                .requestMatchers(
                                        "/no-auth",
                                        "/token/issue"
                                )
                                .permitAll()
                                .anyRequest()
                                .authenticated()
                )
                .sessionManagement(
                        sessionManagement -> sessionManagement
                                .sessionCreationPolicy(SessionCreationPolicy.STATELESS)
                )
                **.addFilterBefore(
                        jwtTokenFilter,
                        AuthorizationFilter.class
                )**
        ;

        return http.build();
    }