HMAC 인증 방식은 해시 기반 메시지 인증 코드(HMAC)를 사용하여 메시지 무결성과 인증을 보장하는 보안 기술입니다.

목차

- 소개
- HMAC 인증의 기본 원리
- HMAC 인증 구현하기
- 보안 고려사항과 모범 사례
- HMAC vs 다른 인증 방식 비교
- 결론
- 참고 자료

소개

API 보안은 현대 웹 서비스에서 가장 중요한 요소 중 하나입니다. 다양한 인증 방식 중에서 HMAC(Hash-based Message Authentication Code) 인증 방식은 메시지의 무결성과 신원 확인을 동시에 보장하는 강력한 메커니즘을 제공합니다. 이 글에서는 HMAC 인증 방식의 원리부터 실제 구현까지 상세히 알아보겠습니다.

이 글에서 배울 내용:

  • HMAC 알고리즘의 작동 원리와 암호학적 기초
  • 다양한 프로그래밍 언어에서 HMAC 인증 구현 방법
  • HMAC 인증을 적용할 때의 보안 모범 사례

HMAC 인증의 기본 원리

HMAC이란 무엇인가?

HMAC(Hash-based Message Authentication Code)는 메시지 인증을 위한 암호화 기법으로, 비밀 키와 해시 함수를 조합하여 메시지의 무결성과 신원을 검증합니다. HMAC은 단순한 해시 함수와 달리 비밀 키를 사용하기 때문에, 중간자 공격(man-in-the-middle attack)이나 재전송 공격(replay attack)에 강한 보안성을 제공합니다.

wiki Hmac 이미지



HMAC 알고리즘은 다음과 같은 수식으로 표현됩니다:

HMAC(K,m) = H((K' ⊕ opad) || H((K' ⊕ ipad) || m))


여기서:

  • K는 비밀 키
  • m은 메시지
  • H는 해시 함수(SHA-256, SHA-512 등)
  • K'는 해시 함수의 블록 크기에 맞게 조정된 키
  • opad와 ipad는 내부 패딩과 외부 패딩 상수
  • ⊕는 XOR 연산, ||는 연결 연산자

java

// HMAC 계산의 기본 원리 (의사 코드)
public static byte[] hmac(byte[] key, byte[] message, MessageDigest hashFunction) throws Exception {
  int blockSize = 64; // SHA-256의 블록 크기
  
  // 키가 해시 함수의 블록 크기보다 크면 해싱하여 줄임
  if (key.length > blockSize) {
    key = hashFunction.digest(key);
  }
  
  // 키가 짧으면 패딩으로 블록 크기까지 늘림
  if (key.length < blockSize) {
    byte[] newKey = new byte[blockSize];
    System.arraycopy(key, 0, newKey, 0, key.length);
    key = newKey;
  }
  
  // 내부/외부 패딩 생성
  byte[] ipad = new byte[blockSize];
  byte[] opad = new byte[blockSize];
  
  for (int i = 0; i < blockSize; i++) {
    ipad[i] = 0x36;
    opad[i] = 0x5c;
  }
  
  // XOR 연산 및 해싱
  byte[] keyXorIpad = new byte[blockSize];
  byte[] keyXorOpad = new byte[blockSize];
  
  for (int i = 0; i < blockSize; i++) {
    keyXorIpad[i] = (byte) (key[i] ^ ipad[i]);
    keyXorOpad[i] = (byte) (key[i] ^ opad[i]);
  }
  
  // 내부 해싱
  hashFunction.reset();
  hashFunction.update(keyXorIpad);
  hashFunction.update(message);
  byte[] innerHash = hashFunction.digest();
  
  // 외부 해싱
  hashFunction.reset();
  hashFunction.update(keyXorOpad);
  hashFunction.update(innerHash);
  byte[] outerHash = hashFunction.digest();
  
  return outerHash;
}

 

HMAC 인증 프로세스

HMAC 기반 API 인증의 일반적인 흐름은 다음과 같습니다:

1. 클라이언트와 서버가 사전에 비밀 키를 공유합니다.
2. 클라이언트가 요청을 보낼 때:
   - 요청 데이터(URL, 메서드, 헤더, 본문 등)를 기반으로 메시지 문자열을 생성합니다.
   - 공유된 비밀 키를 사용하여 메시지의 HMAC을 계산합니다.
   - HMAC 서명을 요청 헤더에 포함시켜 서버로 전송합니다.
3. 서버가 요청을 받으면:
   - 동일한 방식으로 요청 데이터로부터 메시지 문자열을 생성합니다.
   - 동일한 비밀 키로 HMAC을 계산합니다.
   - 계산된 HMAC과 클라이언트가 보낸 서명을 비교합니다.
   - 일치하면 요청을 처리하고, 불일치하면 거부합니다.

HMAC 인증 절차 (출처 : https://cyberhoot.com/cybrary/hmac-authentication/)

💡 팁: 타임스탬프를 메시지에 포함시켜 재전송 공격을 방지할 수 있습니다. 서버는 일정 시간(보통 5-15분) 이상 지난 요청을 거부하는 방식으로 구현합니다.

HMAC 인증 구현하기

java

// 서버 측 HMAC 검증 필터 (Spring Framework)
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
import org.springframework.web.filter.OncePerRequestFilter;
import javax.servlet.FilterChain;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.util.Enumeration;
import java.util.stream.Collectors;
import org.apache.commons.codec.binary.Hex;
import java.nio.charset.StandardCharsets;
import java.time.Instant;

public class HmacAuthenticationFilter extends OncePerRequestFilter {
    
    @Override
    protected void doFilterInternal(HttpServletRequest request, HttpServletResponse response, FilterChain filterChain) 
            throws ServletException, IOException {
        try {
            // 요청에서 인증 헤더 가져오기
            String apiKey = request.getHeader("X-API-Key");
            String hmacSignature = request.getHeader("X-HMAC-Signature");
            String timestamp = request.getHeader("X-Timestamp");
            
            if (apiKey == null || hmacSignature == null || timestamp == null) {
                response.setStatus(HttpServletResponse.SC_UNAUTHORIZED);
                response.getWriter().write("{\"error\":\"Missing authentication headers\"}");
                return;
            }
            
            // API 키로 클라이언트 비밀 키 조회 (실제로는 DB에서 조회)
            String secretKey = getClientSecretKey(apiKey);
            
            if (secretKey == null) {
                response.setStatus(HttpServletResponse.SC_UNAUTHORIZED);
                response.getWriter().write("{\"error\":\"Invalid API Key\"}");
                return;
            }
            
            // 현재 시간과 타임스탬프의 차이 확인 (재전송 공격 방지)
            long currentTime = Instant.now().getEpochSecond();
            long requestTime = Long.parseLong(timestamp);
            
            if (Math.abs(currentTime - requestTime) > 300) { // 5분 허용
                response.setStatus(HttpServletResponse.SC_UNAUTHORIZED);
                response.getWriter().write("{\"error\":\"Timestamp expired\"}");
                return;
            }
            
            // 서명할 메시지 생성
            String method = request.getMethod();
            String path = request.getRequestURI();
            
            // 요청 본문 읽기
            String body = request.getReader().lines().collect(Collectors.joining());
            
            String message = method + path + timestamp + body;
            
            // HMAC 계산
            Mac sha256Hmac = Mac.getInstance("HmacSHA256");
            SecretKeySpec secretKeySpec = new SecretKeySpec(secretKey.getBytes(StandardCharsets.UTF_8), "HmacSHA256");
            sha256Hmac.init(secretKeySpec);
            
            byte[] hmacBytes = sha256Hmac.doFinal(message.getBytes(StandardCharsets.UTF_8));
            String calculatedSignature = Hex.encodeHexString(hmacBytes);
            
            // 서명 비교
            if (calculatedSignature.equals(hmacSignature)) {
                // 인증 성공, 요청 처리 계속
                filterChain.doFilter(request, response);
            } else {
                response.setStatus(HttpServletResponse.SC_UNAUTHORIZED);
                response.getWriter().write("{\"error\":\"Invalid signature\"}");
            }
        } catch (Exception e) {
            logger.error("HMAC 인증 중 오류 발생", e);
            response.setStatus(HttpServletResponse.SC_INTERNAL_SERVER_ERROR);
            response.getWriter().write("{\"error\":\"Authentication error\"}");
        }
    }
    
    private String getClientSecretKey(String apiKey) {
        // 실제 구현에서는 DB나 캐시에서 API 키에 해당하는 비밀 키를 조회
        // 여기서는 예시로 하드코딩
        if ("test-api-key".equals(apiKey)) {
            return "test-secret-key";
        }
        return null;
    }
}

 

클라이언트 측 구현 (JavaScript)

클라이언트에서는 요청을 보내기 전에 HMAC 서명을 계산하여 헤더에 포함시켜야 합니다.
java


// 클라이언트 측 HMAC 서명 생성 (Java)
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
import java.net.URI;
import java.net.http.HttpClient;
import java.net.http.HttpRequest;
import java.net.http.HttpResponse;
import java.nio.charset.StandardCharsets;
import java.time.Duration;
import org.apache.commons.codec.binary.Hex;

public class HmacClient {
    private final String apiKey;
    private final String secretKey;
    private final HttpClient httpClient;
    
    public HmacClient(String apiKey, String secretKey) {
        this.apiKey = apiKey;
        this.secretKey = secretKey;
        this.httpClient = HttpClient.newBuilder()
            .connectTimeout(Duration.ofSeconds(10))
            .build();
    }
    
    public HttpResponse<String> sendRequest(String method, String url, String body) throws Exception {
        // 타임스탬프 생성 (Unix 시간)
        String timestamp = String.valueOf(System.currentTimeMillis() / 1000);
        
        // 서명할 메시지 생성
        String message = method + url + timestamp + (body != null ? body : "");
        
        // HMAC 서명 계산
        Mac sha256Hmac = Mac.getInstance("HmacSHA256");
        SecretKeySpec secretKeySpec = new SecretKeySpec(
            secretKey.getBytes(StandardCharsets.UTF_8), "HmacSHA256");
        sha256Hmac.init(secretKeySpec);
        
        byte[] hmacBytes = sha256Hmac.doFinal(message.getBytes(StandardCharsets.UTF_8));
        String signature = Hex.encodeHexString(hmacBytes);
        
        // HTTP 요청 생성
        HttpRequest.Builder requestBuilder = HttpRequest.newBuilder()
            .uri(URI.create(url))
            .header("Content-Type", "application/json")
            .header("X-API-Key", apiKey)
            .header("X-HMAC-Signature", signature)
            .header("X-Timestamp", timestamp);
        
        HttpRequest request;
        
        switch (method.toUpperCase()) {
            case "GET":
                request = requestBuilder.GET().build();
                break;
            case "POST":
                request = requestBuilder.POST(HttpRequest.BodyPublishers.ofString(body != null ? body : ""))
                    .build();
                break;
            case "PUT":
                request = requestBuilder.PUT(HttpRequest.BodyPublishers.ofString(body != null ? body : ""))
                    .build();
                break;
            case "DELETE":
                request = requestBuilder.DELETE().build();
                break;
            default:
                throw new IllegalArgumentException("Unsupported HTTP method: " + method);
        }
        
        // 요청 전송 및 응답 반환
        return httpClient.send(request, HttpResponse.BodyHandlers.ofString());
    }
    
    // 사용 예시
    public static void main(String[] args) {
        try {
            HmacClient client = new HmacClient("test-api-key", "test-secret-key");
            HttpResponse<String> response = client.sendRequest(
                "GET", 
                "
https://api.example.com/data
", 
                null
            );
            
            System.out.println("Status code: " + response.statusCode());
            System.out.println("Response body: " + response.body());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

보안 고려사항과 모범 사례

키 관리 전략

HMAC 인증의 보안성은 비밀 키 관리에 크게 의존합니다. 효과적인 키 관리를 위한 모범 사례는 다음과 같습니다:
주요 장점:

  • 비밀 키는 충분히 길고 무작위적이어야 합니다 (최소 256비트 길이 권장).
  • 키는 안전한 저장소(HSM, KMS 등)에 보관하고, 평문으로 코드나 설정 파일에 저장하지 마세요.
  • 주기적인 키 교체 메커니즘을 구현하여 키 노출 시 피해를 최소화하세요.

타임스탬프와 논스(Nonce) 활용

재전송 공격을 방지하기 위한 추가적인 보안 조치로 타임스탬프와 논스를 활용할 수 있습니다.
java


// 타임스탬프와 논스를 포함한 HMAC 서명 생성
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
import java.nio.charset.StandardCharsets;
import java.security.SecureRandom;
import org.apache.commons.codec.binary.Hex;

public class HmacWithNonce {
    
    public static HmacSignature createHmacWithNonce(String method, String url, String body, String secretKey) 
            throws Exception {
        // 타임스탬프 생성
        String timestamp = String.valueOf(System.currentTimeMillis() / 1000);
        
        // 무작위 논스 생성 (16바이트)
        byte[] nonceBytes = new byte[16];
        SecureRandom secureRandom = new SecureRandom();
        secureRandom.nextBytes(nonceBytes);
        String nonce = Hex.encodeHexString(nonceBytes);
        
        // 메시지 생성
        String message = method + url + timestamp + nonce + (body != null ? body : "");
        
        // HMAC 계산
        Mac sha256Hmac = Mac.getInstance("HmacSHA256");
        SecretKeySpec secretKeySpec = new SecretKeySpec(
            secretKey.getBytes(StandardCharsets.UTF_8), "HmacSHA256");
        sha256Hmac.init(secretKeySpec);
        
        byte[] hmacBytes = sha256Hmac.doFinal(message.getBytes(StandardCharsets.UTF_8));
        String signature = Hex.encodeHexString(hmacBytes);
        
        return new HmacSignature(signature, timestamp, nonce);
    }
    
    // 서명 결과를 담는 클래스
    public static class HmacSignature {
        private final String signature;
        private final String timestamp;
        private final String nonce;
        
        public HmacSignature(String signature, String timestamp, String nonce) {
            this.signature = signature;
            this.timestamp = timestamp;
            this.nonce = nonce;
        }
        
        public String getSignature() {
            return signature;
        }
        
        public String getTimestamp() {
            return timestamp;
        }
        
        public String getNonce() {
            return nonce;
        }
    }
}

HMAC vs 다른 인증 방식 비교

인증 방식별 특징

다양한 API 인증 방식의 장단점을 비교해보겠습니다.

 

인증 방식 주요 기능 보안 수준 구현 복잡성
API 키 단일 토큰 기반 인증 낮음 매우 간단
HMAC 메시지 서명 기반 인증 높음 보통
OAuth 2.0 위임 액세스 프로토콜 높음 복잡함
JWT Self-contained 토큰 중간-높음 보통
mTLS 상호 TLS 인증 매우 높음 복잡함

 

HMAC의 장단점

HMAC 인증 방식의 주요 장단점은 다음과 같습니다:

장점:

  • 메시지 무결성과 신원 확인을 동시에 보장
  • 비밀 키가 네트워크로 전송되지 않음
  • 타임스탬프와 함께 사용 시 재전송 공격에 강함
  • 서버 측에서 세션 상태를 유지할 필요가 없음


단점:

  • 클라이언트와 서버 간 시간 동기화 필요
  • 구현이 OAuth나 API 키보다 복잡함
  • 비밀 키 관리에 주의가 필요함

HMAC 인증의 고급 적용 사례

캐노니컬 요청 형식

대규모 API 시스템에서는 요청의 모든 부분(쿼리 파라미터, 헤더 등)을 일관된 형식으로 정규화하여 서명하는 것이 중요합니다. AWS 서명 버전 4와 유사한 캐노니컬 형식의 예시입니다.
java


// 캐노니컬 요청 형식 생성 (AWS Signature V4 스타일)
import java.net.URI;
import java.net.URLEncoder;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;

public class CanonicalRequest {
    
    public static String createCanonicalRequest(String method, String url,
                                               Map<String, String> headers,
                                               Map<String, String> queryParams,
                                               String body) throws Exception {
        // URL 경로 추출
        URI uri = new URI(url);
        String path = uri.getPath();
        
        // 쿼리 파라미터 정렬 및 인코딩
        TreeMap<String, String> sortedQueryParams = new TreeMap<>(queryParams);
        String canonicalQueryString = sortedQueryParams.entrySet().stream()
            .map(entry -> {
                try {
                    return URLEncoder.encode(entry.getKey(), "UTF-8") + "=" +
                           URLEncoder.encode(entry.getValue(), "UTF-8");
                } catch (Exception e) {
                    throw new RuntimeException("URL 인코딩 실패", e);
                }
            })
            .collect(Collectors.joining("&"));
        
        // 헤더 정렬 및 소문자로 변환
        TreeMap<String, String> sortedHeaders = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        sortedHeaders.putAll(headers);
        
        StringBuilder canonicalHeaders = new StringBuilder();
        for (Map.Entry<String, String> header : sortedHeaders.entrySet()) {
            canonicalHeaders.append(header.getKey().toLowerCase())
                           .append(":")
                           .append(header.getValue().trim())
                           .append("\n");
        }
        
        // 서명에 포함된 헤더 이름들
        String signedHeaders = sortedHeaders.keySet().stream()
            .map(String::toLowerCase)
            .collect(Collectors.joining(";"));
        
        // 요청 본문 해시 생성
        MessageDigest sha256 = MessageDigest.getInstance("SHA-256");
        byte[] bodyHash = sha256.digest((body != null ? body : "").getBytes(StandardCharsets.UTF_8));
        String hexBodyHash = bytesToHex(bodyHash);
        
        // 캐노니컬 요청 형식 조합
        return method + "\n" +
               path + "\n" +
               canonicalQueryString + "\n" +
               canonicalHeaders + "\n" +
               signedHeaders + "\n" +
               hexBodyHash;
    }
    
    private static String bytesToHex(byte[] bytes) {
        StringBuilder result = new StringBuilder();
        for (byte b : bytes) {
            result.append(String.format("%02x", b));
        }
        return result.toString();
    }
    
    // 사용 예시
    public static void main(String[] args) {
        try {
            // 요청 정보
            String method = "POST";
            String url = "
https://api.example.com/resource/path?queryParam1=value1
";
            
            // 헤더 생성
            Map<String, String> headers = new HashMap<>();
            headers.put("Host", "api.example.com");
            headers.put("Content-Type", "application/json");
            headers.put("X-Amz-Date", "20250518T120000Z");
            
            // 쿼리 파라미터
            Map<String, String> queryParams = new HashMap<>();
            queryParams.put("queryParam1", "value1");
            
            // 요청 본문
            String body = "{\"key\":\"value\"}";
            
            String canonicalRequest = createCanonicalRequest(method, url, headers, queryParams, body);
            System.out.println("Canonical Request:");
            System.out.println(canonicalRequest);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}


다층 보안을 위한 HMAC 활용

HMAC은 다른 보안 메커니즘과 함께 사용하여 다층 방어(defense in depth)를 구현할 수 있습니다.

적용 예시

java

// JWT와 HMAC을 결합한 보안 강화 예시
import io.jsonwebtoken.Jwts;
import io.jsonwebtoken.SignatureAlgorithm;
import io.jsonwebtoken.security.Keys;
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
import java.nio.charset.StandardCharsets;
import java.security.Key;
import java.util.Date;
import java.util.Map;
import org.apache.commons.codec.binary.Hex;

public class SecureTokenGenerator {
    
    public static class SecureToken {
        private final String token;
        private final String signature;
        
        public SecureToken(String token, String signature) {
            this.token = token;
            this.signature = signature;
        }
        
        public String getToken() {
            return token;
        }
        
        public String getSignature() {
            return signature;
        }
    }
    
    public static SecureToken createSecureToken(Map<String, Object> payload, String jwtSecret, String hmacSecret) {
        // JWT 토큰 생성
        Key key = Keys.hmacShaKeyFor(jwtSecret.getBytes(StandardCharsets.UTF_8));
        
        String token = Jwts.builder()
            .setClaims(payload)
            .setIssuedAt(new Date())
            .setExpiration(new Date(System.currentTimeMillis() + 3600000)) // 1시간 유효
            .signWith(key, SignatureAlgorithm.HS256)
            .compact();
        
        // JWT 토큰에 대한 HMAC 서명 추가
        try {
            Mac sha256Hmac = Mac.getInstance("HmacSHA256");
            SecretKeySpec secretKeySpec = new SecretKeySpec(
                hmacSecret.getBytes(StandardCharsets.UTF_8), "HmacSHA256");
            sha256Hmac.init(secretKeySpec);
            
            byte[] hmacBytes = sha256Hmac.doFinal(token.getBytes(StandardCharsets.UTF_8));
            String signature = Hex.encodeHexString(hmacBytes);
            
            return new SecureToken(token, signature);
        } catch (Exception e) {
            throw new RuntimeException("HMAC 서명 생성 실패", e);
        }
    }
    
    // 서버 측 검증
    public static Map<String, Object> verifySecureToken(String token, String signature, 
                                                      String jwtSecret, String hmacSecret) {
        // HMAC 서명 검증
        try {
            Mac sha256Hmac = Mac.getInstance("HmacSHA256");
            SecretKeySpec secretKeySpec = new SecretKeySpec(
                hmacSecret.getBytes(StandardCharsets.UTF_8), "HmacSHA256");
            sha256Hmac.init(secretKeySpec);
            
            byte[] hmacBytes = sha256Hmac.doFinal(token.getBytes(StandardCharsets.UTF_8));
            String calculatedSignature = Hex.encodeHexString(hmacBytes);
            
            if (!calculatedSignature.equals(signature)) {
                throw new RuntimeException("유효하지 않은 HMAC 서명");
            }
            
            // JWT 토큰 검증
            Key key = Keys.hmacShaKeyFor(jwtSecret.getBytes(StandardCharsets.UTF_8));
            Map<String, Object> claims = Jwts.parserBuilder()
                .setSigningKey(key)
                .build()
                .parseClaimsJws(token)
                .getBody();
            
            return claims;
        } catch (Exception e) {
            throw new RuntimeException("토큰 검증 실패: " + e.getMessage(), e);
        }
    }
    
    // 사용 예시
    public static void main(String[] args) {
        try {
            // 페이로드 생성
            Map<String, Object> payload = new HashMap<>();
            payload.put("userId", 123);
            
            // 보안 토큰 생성
            SecureToken secureToken = createSecureToken(
                payload, "jwt-secret-key", "hmac-secret-key");
            
            System.out.println("Token: " + secureToken.getToken());
            System.out.println("HMAC Signature: " + secureToken.getSignature());
            
            // 토큰 검증
            Map<String, Object> claims = verifySecureToken(
                secureToken.getToken(), secureToken.getSignature(),
                "jwt-secret-key", "hmac-secret-key");
            
            System.out.println("Verified claims: " + claims);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

HMAC vs 다른 인증 방식 비교

실제 서비스에서의 선택 가이드

어떤 인증 방식을 선택해야 할지는 서비스의 특성과 보안 요구사항에 따라 달라집니다.

 

도구 주요 기능 링크
HMAC 인증 높은 보안성, 메시지 무결성 보장 https://tools.ietf.org/html/rfc2104
OAuth 2.0 사용자 인증 위임, 서드파티 접근 제어 https://oauth.net/2/
JWT Self-contained 토큰, 무상태 인증 https://jwt.io/

 

보안 강화를 위한 추가 조치

HMAC 인증과 함께 사용할 수 있는 추가적인 보안 조치들입니다:

  • TLS(HTTPS) 사용 강제
  • 속도 제한(Rate Limiting) 구현
  • IP 주소 기반 필터링 추가
  • 사용자별 API 키 권한 세분화

결론

HMAC 인증 방식은 API 보안을 위한 강력하고 효과적인 솔루션입니다. 비밀 키를 네트워크로 전송하지 않으면서도 메시지 무결성과 신원 확인을 동시에 보장할 수 있어, 다양한 보안 요구사항을 충족시킵니다. 올바르게 구현하고 모범 사례를 따른다면, HMAC은 중간자 공격이나 재전송 공격과 같은 일반적인 API 보안 위협으로부터 시스템을 보호하는 데 큰 도움이 됩니다.

핵심 요약:

  • HMAC은 해시 함수와 비밀 키를 조합한 메시지 인증 코드로, API 인증에 효과적입니다.
  • 올바른 구현을 위해서는 타임스탬프, 논스, 캐노니컬 요청 형식 등의 추가 요소가 중요합니다.
  • 비밀 키 관리는 HMAC 보안의 핵심이므로, 안전한 저장과 주기적인 교체가 필수적입니다.

참고 자료

 

 

 

 

'IT' 카테고리의 다른 글

[IT] SHA-1, SHA-2, SHA-256 해시 알고리즘의 차이점  (2) 2023.12.02

🔍문제

젤다



https://www.acmicpc.net/problem/4485
젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. \[0]\[0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 \[N-1]\[N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

🤔발상

0,0에서 n-1,n-1까지  최단거리를 탐색하는 문제입니다.
한 지점에서 다른 지점까지의 최단거리에서 다익스트라 알고리즘을 사용할 수 있을 것 같습니다.
또한 좌표 이동 시 1칸씩 이동 가능하다는 점에서 bfs탐색에 적합할 것으로 보입니다.

🔦입출력

동굴의 크기는 2~125이며 루피는 0~9 범위입니다.

📃의사코드

 

- 데이터 입력받기
- bfs탐색
- 결과 출력

👨‍💻코드

import java.util.*;
import java.lang.*;
import java.io.*;

/*
입력
동굴의 크기 정수 Number(2~125)
N줄 - 도둑 루피의 크기(0~9)
출력
가장 작은 최소 금액(최단 거리)
설계
2차원 배열을 0,0에서 n-1,n-1까지 최단 거리로 갈 때의 비용을 측정
상하좌우 1칸 이동 가능
dfs 탐색으로 누적 거리를 파라미터로 넘기며, 종료 지점의 값을 반환해서 최소값 찾기
*/

// The main method must be in a class named "Main".
public class Main {
    public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            StringBuilder sb = new StringBuilder();
            String problem = "Problem";

            int n = Integer.parseInt(br.readLine());
            int tc = 0;
            while (n != 0) {
                tc++;
                Map map = new Map(n);
                map.init(br);
                sb.append(problem).append(" ").append(tc).append(": ").append(map.getResult()).append("\n");
                n = Integer.parseInt(br.readLine());
            }
            bw.write(sb.toString());
        }
    }
}

class Map {

    private int[][] map;
    private int minResult;
    private int[][] dirs = {{0, 1}, {1, 0},{0, -1}, {-1, 0}};

    Map(int n) {
        map = new int[n][n];
    }

    public void init(BufferedReader br) throws IOException {
        int n = map.length;
        minResult = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
    }

    public int getStart(){
        return map[0][0];
    }

    public void dfs(int x, int y, int sum, boolean[][] visited) {
        visited[y][x] = true;
        int n = map.length;
        if (x == n - 1 && y == n - 1) {
            minResult = Math.min(minResult, sum);
            visited[y][x] = false;
            return;
        }
        for (int[] dir : dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                continue;
            }
            if (!visited[ny][nx]) {
                dfs(nx, ny, sum + map[ny][nx], visited);
            }
        }
        visited[y][x] = false;
    }

    public int getResult() {
        return bfs();
    }
    private int bfs() {
        int n = map.length;
        int[][] minCost = new int[n][n];
        for (int[] row : minCost) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        minCost[0][0] = map[0][0];
        Queue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(0, 0, map[0][0]));

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            int x = current.x;
            int y = current.y;
            int cost = current.cost;

            if (x == n - 1 && y == n - 1) {
                return cost;
            }

            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                    int newCost = cost + map[ny][nx];
                    if (newCost < minCost[ny][nx]) {
                        minCost[ny][nx] = newCost;
                        queue.offer(new Node(nx, ny, newCost));
                    }
                }
            }
        }
        return -1;
    }
}

class Node implements Comparable<Node> {
    int x, y, cost;

    Node(int x, int y, int cost) {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node other) {
        return this.cost - other.cost;
    }
}

 

🔍문제

https://www.acmicpc.net/problem/2458


1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

1번 학생의 키 < 5번 학생의 키
3번 학생의 키 < 4번 학생의 키
5번 학생의 키 < 4번 학생의 키
4번 학생의 키 < 2번 학생의 키
4번 학생의 키 < 6번 학생의 키
5번 학생의 키 < 2번 학생의 키
이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.



1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

🤔발상

자신의 키가 몇 번째인지 알 수 있는 학생이 누군지 고민을 했습니다.
문제에서 이미지로 주어진 그래프를 관찰하다보니, 한 학생이 다른 학생과 모든 학생과 직,간접적으로 연결 관계가 존재하면 자신의 키가 몇 번째 인지 알 수 있다고 보았고, 플로이드 워셜 알고리즘을 이용하여 연결 관계를 파악하고, 이 숫자를 세어 전체 인원수와 비교하면 될 것으로 보았습니다.

🔦입출력

다행이 학생 수가 500 이하로, 만약 10,000등 수가 많았으면 다른 그래프 탐색방법을 고민해보았어야 할 것 같은데 플로이드 워셜을 사용할 수 있을 것 같습니다.

📃의사코드

- 데이터 입력받기
- 플로이드 워셜 이용하여 연결관계 업데이트
- 각 학생의 연결된 인원 수 세기
- 모든 학생과 연결된 학생의 수 세기

👨‍💻코드

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            String[] nm = br.readLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            HeightUtil heightUtil = new HeightUtil(n, m);
            heightUtil.init(br);
            bw.write(String.valueOf(heightUtil.getResult()));
        }
    }
}

class HeightUtil {

    boolean[][] graph;
    int[] dist;
    int n;
    int m;

    public HeightUtil(int n, int m) {
        this.n = n;
        this.m = m;
        graph = new boolean[n + 1][n + 1];
        dist = new int[n + 1];
    }

    public void setGraph(int a, int b) {
        graph[a][b] = true;
    }

    public void floydWarshall() {
        for (int k = 1; k <= n; ++k) {
            for (int j = 1; j <= n; ++j) {
                for (int i = 1; i <= n; ++i) {
                    if (graph[i][k] && graph[k][j]) {
                        graph[i][j] = true;
                    }
                }
            }
        }
    }

    public void setDist() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] || graph[j][i]) {
                    dist[i]++;
                }
            }
        }
    }

    public int getResult() {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == n - 1) {
                result++;
            }
        }
        return result;
    }

    public void init(BufferedReader br) throws IOException {
        for (int i = 0; i < m; i++) {
            String[] ab = br.readLine().split(" ");
            int a = Integer.parseInt(ab[0]);
            int b = Integer.parseInt(ab[1]);
            setGraph(a, b);
        }
        floydWarshall();
        setDist();
    }
}

🚀TIL

  • 다른 탐색 방법도 한번 고민해보고 구현해보면 좋을 것 같습니다.

썸네일

🔍문제

정원


https://www.acmicpc.net/problem/2457
오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

🤔발상

꽃들을 시작 날짜와 종료 날짜로 정렬한 뒤에, 앞에서부터 조건에 맞는지 검사하면서 가장 종료 날짜가 긴 꽃을 선택하면 될 것 같았습니다.
주 키워드는 정렬과 그리디 알고리즘으로 보입니다.

🔦입출력

입력
꽃들의 총 개수 N(1~100,000)
꽃이 피는 날짜와 지는 날짜 x N
출력:  
선택한 꽃들의 최소 개수

📃의사코드

- 입력받은 꽃들을 정렬 가능한 클래스로 생성하여 배열에 담기
- 배열 정렬
- 시작날짜, 종료날짜 기준점 생성
- 시작날짜가 종료날짜 이전 동안 반복
	- 꽃들 배열 탐색
		- 탐색 대상의 시작날짜가 현재 시작날짜보다 늦으면 안됨
		- 탐색 대상의 종료날짜가 현재까지 찾은 마지막 날짜보다 뒤라면
			- 마지막날짜 업데이트
			- 인덱스 업데이트
			- 찾음 플래그 on

👨‍💻코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.time.LocalDate;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

public static void main(String args[]) throws NumberFormatException, IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int n = Integer.parseInt(br.readLine());
            Flower[] flowers = new Flower[n];
            for (int i = 0; i < n; i++) {
                flowers[i] = new Flower(br.readLine());
            }
            Arrays.sort(flowers);
            final int BASE_YEAR = 2023;
            LocalDate start = LocalDate.of(BASE_YEAR, 3, 1);
            LocalDate end = LocalDate.of(BASE_YEAR, 12, 1);

            int count = 0;
            int idx = 0;
            LocalDate maxEnd = start;

            //1. [x]시작날짜, 종료날짜 비교
            //2. [x]선택한 값이 종료날짜 이전인 동안 반복
            //3. [x]탐색 대상의 시작일이 이전 꽃의 이전 꽃의 종료일보다 이후이면 선택 안함
            //4. [x]탐색 대상의 기간이 이전 최대값보다 크면 선택
            while (start.isBefore(end)) {
                boolean find = false;
                for (int i = idx; i < n; i++) {
                    if (flowers[i].getStart().isAfter(start)) {
                        break;
                    }
                    if (flowers[i].getEnd().isAfter(maxEnd)) {
                        maxEnd = flowers[i].getEnd();
                        idx = i;
                        find = true;
                    }
                }
                if (!find) {
                    count = 0;
                    break;
                }
                start = flowers[idx].getEnd();
                count++;
                idx++;
            }

            bw.write(String.valueOf(count));
        }
    }

}

class Flower implements Comparable<Flower> {

    private final LocalDate start;
    private final LocalDate end;

    Flower(String str) {
        StringTokenizer st = new StringTokenizer(str);
        start = LocalDate.of(2023, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        end = LocalDate.of(2023, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

    public LocalDate getStart() {
        return start;
    }

    public LocalDate getEnd() {
        return end;
    }


    //equals, hashCode, toString 생략
    @Override
    public int compareTo(Flower o) {
        if (this.start.equals(o.start)) {
            return o.end.compareTo(this.end);
        }
        return this.start.compareTo(o.start);
    }
}

🚀TIL

  • 처음엔 LocalDate를 좀 더 활용하고 싶어 CronoUtil.DAYS.between(start,end)로 period를 구해서 최적해를 찾아보려 했는데, 시작 날짜에 따라 문제의 최적해가 꽃의 period만으로 판단할 수 없어서 수정하였습니다.
  • 날짜를 다루는 알고리즘 문제가 꽤 자주 나오는데, 시간내서 java.time 복습을 해야겠습니다.

썸네일

🔍문제

https://www.acmicpc.net/problem/1865

 

웜홀

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

 

🤔발상

주어진 데이터는 노드와 간선이 주어지는 그래프 형태의 데이터이며 음의 가중치가 존재합니다.
그 중에 사이클이 존재하는지 검사하는 알고리즘으로 벨만포드 알고리즘으로 풀기에 적합한 문제라 판단하였습니다.
최단거리를 찾는 방법 중 자주 쓰이는 알고리즘 3개 중 하나이며 각각의 특징은 다음과 같습니다.

  • 다익스트라
    • 한 노드 사이의 최단거리를 계산
    • DP를 이용하여 빠름
    • 음의 가중치가 존재하면 사용 불가능
  • 플로이드 워셜
    • 모든 노드 사이의 최단거리를 계산
    • O(N ^ 3) 시간복잡도로 느림
    • 음의 가중치가 존재해도 사용 가능
  • 벨만포드
    • 모든 노드 사이의 최단거리를 계산
    • 음의 가중치가 존재해도 사용 가능
    • 음수 사이클을 감지 가능함

🔦입출력

음의 가중치가 주어진 간선은 입력 순서로 구분되며, 입력값을 전처리해주어야 합니다.


📃의사코드

- 데이터 입력
- 입력시 음의 가중치 별도 처리
- 벨만포드 알고리즘 이용, 거리 업데이트
- 사이클 검사 결과 출력

👨‍💻코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int tc = Integer.parseInt(br.readLine());
            for (int i = 0; i < tc; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int v = Integer.parseInt(st.nextToken());
                int undirected = Integer.parseInt(st.nextToken());
                int directed = Integer.parseInt(st.nextToken());
                Graph graph = new Graph(v, undirected * 2 + directed);
                graph.init(br, undirected, directed);
                graph.bellmanFord(1);
                bw.write(!graph.isCycle ? "NO" : "YES");
                bw.newLine();
            }
        }
    }
}

class Graph {

    boolean isCycle;

    class Edge {

        /**
         * source
         */
        int s;
        int dest;
        int weight;

        Edge() {
            s = dest = weight = 0;
        }

        Edge(int s, int dest, int weight) {
            this.s = s;
            this.dest = dest;
            this.weight = weight;
        }
    }

    int V, E;
    /**
     * edge
     */
    ArrayList<Edge> e;

    Graph(int v, int en) {
        V = v;
        E = en;
        e = new ArrayList<>();
        isCycle = false;
    }

    public void init(BufferedReader br, int undirected, int directed) throws IOException {
        StringTokenizer st;
        for (int i = 0; i < undirected; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            e.add(new Edge(src, dest, weight));
            e.add(new Edge(dest, src, weight));
        }
        for (int i = 0; i < directed; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            e.add(new Edge(src, dest, -weight));
        }
    }

    public void bellmanFord(int src) {
        Graph graph = this;
        int V = graph.V, E = graph.E;

        int[] dist = new int[V + 1];
        Arrays.fill(dist, 1000000000);
        dist[src] = 0;

        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < E; j++) {
                Edge edge = graph.e.get(j);
                if (dist[edge.dest] > dist[edge.s] + edge.weight) {
                    dist[edge.dest] = dist[edge.s] + edge.weight;
                }
            }
        }

        for (int i = 0; i < E; i++) {
            Edge edge = graph.e.get(i);
            if (dist[edge.dest] > dist[edge.s] + edge.weight) {
                isCycle = true;
            }
        }
    }
}

🚀TIL

  • 문제를 푸는 것보다 개선에서 굉장히 고생을 많이 하였습니다.
  • 최초 풀이는 평소 익숙한 방식인 2중연결리스트로 그래프 자료구조를 구현하여 일반적인 그래프 순환탐색을 이용하여 구현하였습니다.(노드마다 모든 간선을 탐색하는게 아닌, 연결 간선만 탐색)
  • 그 후 최적화 시도를 위해 연결관계를 표현하지 않고 간선만 입력받아 리스트로 저장한 뒤, 간선을 순회하는 벨만포드 알고리즘 의사코드를 작성하였는데 몇가지 오류가 발생하였습니다
    • 이전엔 발생하지 않던 오버플로 발생(Integer.MAX_VALUE로 초기화 하면 오류 발생)
    • 간선을 입력받으면서 생기는 사소한 반복문 인덱스 이슈
    • 시간제한 이슈(이는 오버플로 이슈를 우회하다 생긴 이슈)
      • 한번만 수행하면 되는 벨만포드지만 오버플로로 오답이 발생, 그런데 시작지점을 변경하여 여러번 반복수행하면 오버플로 오답이 놀랍게도 해결됨(??)
  • 몇일전부터 고민하던 1시작 반복문을 for(i=0; i<n; ++i)로 개선
    • 이를 통해 배열일 경우 선언문에서만 +1 해주고 입력값을 그대로 사용가능

 



🔍문제

https://www.acmicpc.net/problem/2660


월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

🤔발상

친구의 친구, 친구의 친구의 친구는 주어진 연결관계 내에서 경유를 통해 연결될 수 있는가를 물어보는 문제로 파악했습니다.
플로이드 워셜로 최단경로를 업데이트 하면 연결관계를 알 수 있고, 이를 이용해 가장 작은 점수, 그리고 그 점수에 해당하는 사람들을 찾으면 되며, 이를 위해 자료구조와 정렬이 필요합니다.

정렬 문제는 정렬이 문제의 핵심키워드일 경우엔 추가적인 시간복잡도, 공간복잡도 고려가 필요하지만 입력수가 50처럼 작은 경우에는 자바에서 기본적으로 제공하는 라이브러리나 스트림 등을 사용해도 큰 이슈 없이 해결되는 경우가 많습니다.

최적화를 위해선 다소 코드가 복잡해도 for문이나 배열을 이용해 직접 조작하는게 좋지만, 간단하게 해결할 수 있는 경우엔 쉬운 방법을 택하는 것도 괜찮은 전략입니다.

🔦입출력

최대 회원의 입력 수는 50이며 종료 입력을 받아 입력을 종료해야 합니다.
100 미만이므로 O(N ^ 3)에 적합합니다.

📃의사코드

- 데이터 입력받기
- 연결관계 업데이트(플로이드 워셜)
- 점수 계산
- 결과 출력(정렬된 결과)

👨‍💻코드

import java.util.*;
import java.util.stream.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int n = Integer.parseInt(br.readLine());
            Election election = new Election(n);

            while (true) {
                String[] input = br.readLine().split(" ");
                int a = Integer.parseInt(input[0]);
                int b = Integer.parseInt(input[1]);
                if (a == -1 && b == -1) {
                    break;
                }
                election.addConnection(a, b);
            }

            election.floydWarshall();
            election.calculateScore();
            bw.write(election.getResult() + "\n");      
        }
  }
}

class Election {

    static final int INF = 10000000;

    int[][] graph;
    Candidate[] candidates;
    int minScore;
    int n;

    public Election(int n) {
        this.n = n;
        this.graph = new int[n + 1][n + 1];
        this.candidates = new Candidate[n + 1];
        this.minScore = INF;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    graph[i][j] = INF;
                }
            }
        }
    }


    public void addConnection(int a, int b) {
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    public void floydWarshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }

    public void calculateScore() {
        for (int i = 1; i <= n; i++) {
            int max = 0;
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] < INF) {
                    max = Math.max(max, graph[i][j]);
                }
            }
            candidates[i] = new Candidate(max, i);
            minScore = Math.min(minScore, max);
        }
    }

    public String getResult() {
        StringBuilder sb = new StringBuilder();
        List<Candidate> list = Arrays.stream(candidates).filter(candidate -> {
            if (candidate == null) {
                return false;
            }
            return candidate.score == minScore;
        }).sorted().collect(Collectors.toList());

        sb.append(minScore).append(" ").append(list.size()).append("\n");
        for (Candidate candidate : list) {
            sb.append(candidate.number).append(" ");
        }
        return sb.toString().trim();
    }
}

class Candidate implements Comparable<Candidate> {

    int score;
    int number;

    public Candidate(int score, int number) {
        this.score = score;
        this.number = number;
    }

    @Override
    public int compareTo(Candidate o) {
        return this.number - o.number;
    }
}

🚀TIL

  • 최저 점수인 사람들을 찾고 정렬하는게 번거로워 보여 별도 클래스를 만들고 Comparable을 구현하여 필터링, 정렬을 동시에 해결을 시도했습니다.
  • 개인 IDE에선 java 17 을 사용하고 있는데, 문제 사이트는 java 11이다보니, 스트림 api의 toList() 메서드를 지원하지 않아(자바 16부터 지원) 컴파일 에러가 발생하는 이슈가 있었습니다.
  • Try-with-resource 문법은 꽤 괜찮았으며, 반복문의 변수를 의미변수로 명명하는 것은 IDE를 사용할 땐 편리하지만 IDE 도움 없이 라이브코딩하는 경우 코드작성이 번거롭고 오타의 위험이 있어 안쓰는게 더 좋을 것 같습니다.

 

썸네일

🔍문제

https://www.acmicpc.net/problem/1389

 

맛있는 베이컨(문제와 관련 없음)

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

🤔발상

문제의 핵심 아이디어는 모든 사람들의 연결 단계 수를 계산하고 그 합인 케빈 베이컨 수 중 최소 값을 출력하는 것입니다.
어제 풀었던 알고리즘인 플로이드 와셜 알고리즘을 활용하기 적절한 문제이며 약간의 후처리 과정으로 답을 얻을 수 있습니다.

🔦입출력

유저의 수가 100 이하이므로 플로이드 와셜 알고리즘의 제한사항 중 하나인 O(N ^ 3)으로 시간 내에 수행 가능할 것으로 생각됩니다.

 

📃의사코드

- 연결 관계 입력받기
- 플로이드 와셜 -> 연결 관계 업데이트
- 케빈 베이컨 수 계산
- 결과 출력

👨‍💻코드

import java.util.*;
import java.io.*;

public class Main {
    
    /*
    - 모든 사람의 최단경로 계산
    - 한 사람의 최단경로 합 계산
    - 가장 작은 최단경로(케빈 베이컨의 수) 출력
    
    - 입력제한 N (2 <= N <= 100)
    */
    
  public static void main(String args[]) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      KevinBacon kv = new KevinBacon();
      kv.init(br);
      bw.write(String.valueOf(kv.getResult()));
      bw.close();
  }
}

class KevinBacon {
    private int n;
    private int[][] graph;
    private final int INF = 1000000;

    public void init(BufferedReader br) throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        graph = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j){
                    graph[i][j] = INF;
                }
            }
        }

        for(int i=0;i<m;i++){
            updateGraph(br.readLine());
        }
    }

    private void updateGraph(String input) throws IOException{
        String[] inputs = input.split(" ");
        int a = Integer.parseInt(inputs[0]);
        int b = Integer.parseInt(inputs[1]);

        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    private void floydWarshall(){
        for(int k=1;k<= n;k++){
            for(int i=1;i<= n;i++){
                for(int j=1;j<= n;j++){
                    int newDistance = graph[i][k] + graph[k][j];
                    if(newDistance < graph[i][j]){
                        graph[i][j] = newDistance;
                    }
                }
            }
        }
    }

    public int getResult(){
        floydWarshall();
        int minSum = Integer.MAX_VALUE;
        int result = 0;
        for(int i=1;i<=n;i++){
            int sum = 0;
            for(int j=1;j<=n;j++){
                if (graph[i][j] < INF) {
                    sum += graph[i][j];
                }
            }
            if(sum < minSum){
                minSum = sum;
                result = i;
            }
        }
        return result;
    }

}

🚀TIL

  • 이전에 풀었던 문제로 개인적인 학습을 위해 클래스로 만들어 기능을 메서드 별로 분리하였습니다.(TDD 개발방법론 적용)
  • 리팩토링 후 결과 제출에 이슈가 있었는데, BufferdWriter의 write 메서드를 사용할 때, int  결과값을 그대로 반환하여 String을 인자로 받는 write 메서드와 파라미터 불일치로 이상값이 출력되어 수정하였습니다.
  • 코드 가독성 관련하여 몇가지 개선사항을 확인하여 다음부터 적용할 예정입니다.
    • 매직넘버 로직(graph\[i]\[j] < 10000000) -> INF 상수화 + boolean isConnect() 메서드 추출
    • 문제별로 다른 입출력 시작순서(0 시작 or 1 시작)을 구별하기 위한 1 시작일 경우 i j 관습변수가 아닌 personNumber 등의 의미변수 사용
  • BufferedReader와 BufferedWriter가 가독성 측면에서 분리하는게 좋을 것 같아 try-with-resources 문법으로 감싸주면 좋을 것 같습니다.

썸네일

아는 개발자 분이 알고리즘 스터디를 하신다는 이야기를 듣고 계획에 없었지만 신청하여 진행하게 되었습니다.

혼자 공부할때보단 동기부여도 생기고 다른 사람들과 교류하면서 더 좋은 성과를 얻을 것 같아 시작하였는데, 한동안 쓰지 않던 블로그를 TIL 기록을 해야해서(스터디 참가비를 환급해준다고 한다 😊) 1일 차부터 성과가 보이는 것 같습니다.

오늘의 학습 키워드

- 플로이드 워셜

내용

플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘입니다.

다익스트라와 비슷하지만, 다익스트라는 음의 가중치를 가진 경우 사용할 수 없지만 플로이드 워셜 알고리즘은 사용할 수 있다는 차이점이 있습니다.

이에 대해선 아래에서 좀 더 자세히 이야기 해보면 좋을 것 같습니다.

 

핵심 아이디어

플로이드 워셜 알고리즘의 핵심 아이디어는 

i 정점과 j정점 이 존재할 때, 경유지점 k를 고려하여 최단 거리를 업데이트 하는 것입니다.

수식으로 표현하면 다음과 같습니다.

D[i][j]=min(D[i][j],D[i][k]+D[k][j])

이를 코드로 표현하면 더 보기 쉬워지는데, 2차원 배열로 표현한 그래프를 전체순회하는 2중 반복문을 경유지점 k도 고려하도록 3중 반복문으로 감싸주면 됩니다.

 

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (distance[i][k] + distance[k][j] < distance[i][j]) {
                distance[i][j] = distance[i][k] + distance[k][j];
            }
        }
    }
}

3중 반복문이면 시간복잡도가 O(N^3)인데 사용해도 괜찮은가? 싶은 생각이 드는데, 전체 노드의 갯수가 크면 매우 느려집니다.

N의 수가 100 이하일 때 사용하는 것이 좋습니다.

 

연산 시간 예측

아래는 알고리즘 문제 풀이에 사용하는 대략적인 예측방법입니다.

제 pc의 cpu 클럭수는 3.3ghz인데 이는 초당 3,300,000,000 연산이 가능하다는 의미입니다.

 

이를 위 사례와 연결지어 생각하면 

100 ^ 3 = 1,000,000

1,000 ^ 3 = 1,000,000,000

10,000 ^ 3 = 1,000,000,000,000

으로 개인용 pc에서도 입력값이 10,000이 넘어가면 거의 300초(5분)이 걸린다고 에측할 수 있습니다.

문제 플랫폼에서 제공하는 연산리소스는 가정용 pc보다 낮을테니 100~1000 의 입력값 제한으로 보면 될 것 같습니다.

음의 가중치

위에서 이야기했던 다익스트라 알고리즘과의 차이점인 음의 가중치에 대해 좀 더 고민해보았습니다.

다익스트라 알고리즘은 그리디 알고리즘이 핵심 아이디어이며, 지금까지의 최선해에서 주어지는 정보로 다음 최선해를 계속 개선해 나가는 방식이라 다음 정보로 음의 가중치가 입력된다면 계속 결과값이 줄어들게 됩니다.

 

반면 플로이드 워셜 알고리즘의 경우 핵심 아이디어는 동적 프로그래밍으로 이전에 계산한 결과값을 바탕으로 다음 결과값을 계산하므로 이전 결과값을 변경하지 않습니다.

 

사실 말로 풀어쓰는 것보다 코드로 보면 훨씬 이해하기 쉬운데, 다익스트라Queue로 구현하며(다른 방법도 있지만 가장 효과적) 무한루프에 빠질 수 있지만 플로이드 워셜은 반복문으로 구현하여 무한루프에 빠지지 않습니다.

회고

알고리즘 공부를 오랫동안 쉬어서 이전에 공부했던 내용을 복습해 나가는게 스터디의 주 목적이 될 것 같습니다.

다른 레벨들의 문제들도 한번씩 보면서 복습 내용을 넓혀가면 좋을 것 같습니다.

안녕하세요. 다메카솔🐿️ 입니다.

지난 4.17일 PostgreSQL 100% 활용법 밋업에 참석하였습니다.

한동안 공부에 운동에 정신이 없어서 컨퍼런스 관련 정보를 찾아보지 못하고 있었는데, 갑자기 생각나서 찾아보니 평소에자주 사용하는 PostgreSQL 관련 밋업이 있어 바로 신청하였습니다.

신청하면서 개발자 입장에서 데이터베이스로 PostgreSQL와 mysql을 모두 사용해본 경험이 있지만, 둘의 차이가 뭘까? 생각했을 때 그냥 sql만 작성하고 제품 이름만 다르다, postgreSQL은 ORM에 친화적이다 정도로 아무것도 모르고 있다는 사실에 좀 충격받아서 기대를 가지고 참석하였습니다. 

 

https://www.meetup.com/pgmeetupseoul/events/300140824/

 

Login to Meetup | Meetup

Not a Meetup member yet? Log in and find groups that host online or in person events and meet people in your local community who share your interests.

www.meetup.com

아래는 밋업 정보입니다.

밋업 정보

[📣밋업 안내📣]

  • 일시
    2024년 4월 17일 수요일 18:30~20:30 (2시간)
  • 모집 일정
    2024년 4월 1일 ~ 4월 16일 (선착순)
  • 장소
    삼성역 섬유센터빌딩 2층 컨퍼런스홀 C3룸 (서울 강남구 테헤란로 518)
  • 식사
    샌드위치와 생수 제공
  • 후원
    비트나인
  • 참석비용
    무료

[🎁밋업 참석자 혜택🎁]

  • 참석자 혜택 1
    어디서도 들어볼 수 없는 생생한 PG 이야기를 실무자가 직접 들려드립니다.
  • 참석자 혜택 2
    현장 추첨을 통해 따뜻한 신상 도서를 선물로 드립니다.
    참석자 혜택 3
    추후 PostgreSQL Meetup Seoul 운영진으로 활동할 수 있는 기회를 드립니다.

[⏰밋업 시간표⏰]

  • 18:30 밋업 등록 및 식사
  • 18:50 환영인사
  • 18:55 보너스 세션: PostgreSQL Community 참여/기여 방법
  • 19:05 세션1: 실무에 적용하는 PostgreSQL 아키텍쳐 구성 방법
  • 19:35 세션2: PG Extension: 신개념 데이터 구조 저장: Apache AGE
  • 20:05 네트워킹
  • 20:30 마무리

아는 지인과 함께 세션을 등록하여 도착하였는데, 조금 일찍 도착하였음에도 사람들이 줄을 서 있었습니다.

대기 줄

앞에 계신 분은 함께 참석한 개발자분인데 초상권을 위해 모자이크 처리 하였습니다.

약간 사건 관계자 인터뷰 모자이크 느낌이 나긴 하지만 그림판으로 최선을 다했습니다...

 

줄을 서서 밋업 신청 확인을 하는데, 신청이 제대로 안되어있어 현장 신청을 하느라 조금 입장이 늦어졌습니다.

사진은 못찍었지만 맛있는 샌드위치랑 물을 주셔서 간단히 저녁 대용으로 먹고 세션을 기다렸습니다.

 

본격적으로 세션이 시작되기 전에, 오픈소스인 포스트그레 커뮤니티 대한 세션이 있었는데, 어떻게 기여할 수 있는지 절차를 설명해주시는 것을 보고, 항상 마음속으로만 있었던 많이 사용하는 오픈소스에 참여하여 개발자 생태계에 기여해보고 싶다는 생각이 다시 생기기 시작하였습니다.

항상 구체적인 방법이 너무 막막하였는데, 자세한 절차나 사례들을 설명해 주시니 한번 도전해볼까? 라는 생각이 들어 정보를 더 찾아봐야 될 것 같습니다.

 

세션에 관한 자세한 내용은 생략하고 두 세션 모두 열정적으로 발표해주셔서 시간가는 줄 모르고 들었습니다.

 

위 사진에 있는 좌석이 거의 만석이 될 정도로 많은 분들이 참석해주셨고, 세션 중간중간에 문답 시간에도 어려운 질문에도 상세하게 답변을 해주셔서 다음에 또 밋업이 있다면 참석할 예정입니다. 

안녕하세요. 다메카솔입니다. 🐿️

 

현재 회사에서 ISMS-P 인증을 준비하고 있습니다.

이를 위해서 데이터베이스에 저장되는 정보 중에 민감정보 암호화 작업이 어떻게 되는지 파악하고, 암호화 알고리즘이 얼마나 안전한지 점검하는 업무를 수행하였습니다.

 

이때 점검한 암호화 알고리즘의 종류에 따른 차이점에 대해 찾아보았습니다.

암호화에는 단방향 암호화와 양방향 암호화가 있는데, 이번 시간에는 단방향 암호화에 대해서만 살펴보도록 하겠습니다.

 

암호화 이미지 - 출처 KEYSIGHT

해시 알고리즘

해시 알고리즘은 고정된 크기의 고유한 값(해시 값 또는 해시 코드)을 생성하는 알고리즘입니다. 주어진 입력 데이터에 대해 항상 동일한 크기의 고정된 길이의 출력을 생성하며, 해시 함수라고도 불립니다. 해시 함수의 주요 특징은 다음과 같습니다:

  1. 고유성: 서로 다른 입력에 대해서는 고유한 해시 값을 생성합니다. 그러나 해시 함수의 출력 크기가 고정되어 있기 때문에 두 개 이상의 서로 다른 입력이 같은 해시 값을 갖을 수 있습니다. 이것을 '충돌'이라고 합니다.
  2. 고속성: 빠르게 계산될 수 있어야 합니다.
  3. 역전 불가능성: 해시 값으로는 원래 데이터를 역산하기 어렵습니다. 즉, 해시 값으로는 원래 데이터를 복원할 수 없어야 합니다.
  4. 비슷한 입력에 대한 다양한 출력: 입력의 작은 변화에 대해 큰 차이를 가져와야 합니다.

해시 알고리즘은 주로 데이터의 무결성을 검증하거나, 암호화된 비밀번호를 저장할 때 사용됩니다. 대표적인 해시 알고리즘에는 MD5, SHA-1, SHA-256, SHA-3 등이 있습니다.

 

우리에게 가장 중요한 것은 SHA 알고리즘입니다.

SHA (Secure Hashing Algorithm)는 암호화 보안에 사용됩니다. 이 알고리즘의 가장 중요한 전제는 해시의 비가역성과 고유성입니다. 비가역성-원본 데이터는 안전하고 알려지지 않은 상태로 유지됩니다. 고유성-두 개의 다른 데이터가 동일한 키를 생성 할 수 없습니다.

단방향 암호화 (One-way Encryption 또는 Hashing):

  • 특징:
    • 입력 데이터를 암호화한 결과를 역으로 해독할 수 없습니다.
    • 주로 암호화된 값을 저장하거나 전송할 때 사용됩니다.
    • 대표적으로 해시 함수 (예: SHA-256, MD5)가 사용됩니다.
    • 동일한 입력에 대해서는 항상 동일한 해시 값이 생성됩니다.
    • 주로 암호화된 비밀번호를 저장하고, 데이터 무결성을 검증하는 데 사용됩니다.
  • 예시:
    • 웹 사이트에서 사용자의 비밀번호를 해시하여 저장하고, 로그인 시에 입력된 비밀번호를 해시하여 저장된 해시 값과 비교합니다.

SHA-1 (Secure Hash Algorithm 1)

  • 길이: 160 비트
  • 출시 년도: 1993년
  • 특징: SHA-1은 빠른 속도와 간단한 구조를 가지고 있습니다. 그러나 현재는 충돌에 취약한 것으로 알려져 있어 보안 측면에서는 사용을 권장하지 않습니다. 실제로 SHA-1은 많은 곳에서 보안 요구 사항을 충족하지 못하게 되었고, 대부분의 보안 전문가들은 SHA-1을 피하고 SHA-2나 SHA-3으로 전환할 것을 권장합니다.

SHA-2 (Secure Hash Algorithm 2)

  • 길이: 다양한 길이를 가지고 있으며, 주로 224, 256, 384, 512 비트가 사용됩니다.
  • 출시 년도: 2001년
  • 특징: SHA-2는 SHA-1의 취약성을 보완하기 위해 개발되었습니다. 다양한 해시 길이를 지원하며, 길이가 길어질수록 더 강력한 보안을 제공합니다. 현재까지 안전하게 사용될 수 있는 해시 알고리즘 중 하나로 간주되고 있습니다.

SHA-256

  • 길이: 160 비트
  • 출시 년도: 1993년
  • 특징: SHA-1은 빠른 속도와 간단한 구조를 가지고 있습니다. 그러나 현재는 충돌에 취약한 것으로 알려져 있어 보안 측면에서는 사용을 권장하지 않습니다. 실제로 SHA-1은 많은 곳에서 보안 요구 사항을 충족하지 못하게 되었고, 대부분의 보안 전문가들은 SHA-1을 피하고 SHA-2나 SHA-3으로 전환할 것을 권장합니다.

비교 요약

  • 보안 수준: SHA-1 < SHA-256 < SHA-2 (다양한 길이)
  • 사용 권장 여부: SHA-1 (피하길 권장), SHA-256 및 SHA-2 (현재까지 안전한 보안 수준을 제공하므로 사용 가능)

결론

암호화 알고리즘은 SHA-2 이상을 사용하기를 권장하고 있습니다.

참고자료

NIST FIPS PUB 180-4

 

FIPS 180-4, Secure Hash Standard (SHS) | CSRC

Publications Secure Hash Standard (SHS)     Documentation     Topics Date Published: August 2015 Supersedes: FIPS 180-4 (03/06/2012) Planning Note (03/07/2023): After two rounds of public comment, NIST has decided to revise FIPS 180-4. Author(s) Nati

csrc.nist.gov

https://ko.wikipedia.org/wiki/SHA

 

SHA - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. SHA(Secure Hash Algorithm, 안전한 해시 알고리즘) 함수들은 서로 관련된 암호학적 해시 함수들의 모음이다. 이들 함수는 미국 국가안보국(NSA)이 1993년에 처음으로 설

ko.wikipedia.org

https://ko.wikipedia.org/wiki/SHA-2

 

SHA-2 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. SHA-2 (Secure Hash Algorithm 2)는 미국 국가안보국(NSA)이 설계한 암호화 해시 함수들의 집합이다.[1] 암호 해시 함수는 디지털 데이터 상에서 수학적으로 동작하며 알

ko.wikipedia.org

 

문의 사항이나 도움이 필요하신 분은 댓글 달아주세요!

'IT' 카테고리의 다른 글

[IT/보안] HMAC 인증 방식  (2) 2025.05.18

+ Recent posts