26008 해시 해킹 - 골드4

Posted Jan 18, 2024

By KimHyungkeun 6 min read

문제 출처 : https://www.acmicpc.net/problem/26008

1. 문제

그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하는 과오를 뒤로하고, 이제부터 암호에 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수라고는 알고리즘 문제 풀이에 많이 사용되는 롤링 해시 함수밖에 없기 때문에 이것을 응용하여 사용하기로 했다.

그린닷컴의 비밀번호 규칙은 꽤 특이한데, 길이가 정확히 N이어야 하며, 비밀번호를 이루는 문자는 지정된 M개의 문자 중 하나여야 한다. 따라서, 사용 가능한 각 문자를 0부터 차례대로 정수에 대응시키면, 비밀번호를 길이가 N이고 모든 원소가 0 이상 M-1 이하인 배열 P = [P0, P1, …, P{N-1} ]로 나타낼 수 있다.

이렇게 비밀번호를 배열 P로 나타낸 후, 미리 정해진 정수 A를 이용하여 다음과 같은 해시 함수 h를 적용한다.

h(P) = (P0 * A^0 + P1 * A^1 + … + P{N-1} * A^{N-1}) mod M

예를 들어 배열 P = [10, 30, 20], A = 7, M = 55 인 경우를 생각해보자. 이 경우, h(P) = (10 * 7^0 + 30 * 7^1 + 20 * 7^2) mod 55 = (10 + 210 + 980) mod 55 = 45 이다. 여기서 mod 는 나머지 연산으로 1200 = 21 * 55 + 45 이므로 1200 mod 55 = 45 이다. 따라서 해시값은 항상 0 이상 M-1 이하의 정수이다.

그린닷컴 관리자 계정의 비밀번호 해시값을 해킹한 재현이는, 이 해시값으로 실제 비밀번호가 뭐였는지 역추적해보려고 한다. 하지만 그린닷컴에서 사용 가능한 비밀번호는 M^N 개나 있고, 이 중 과연 알아낸 해시값과 일치하는 비밀번호는 몇 개나 될지 궁금해졌다. 여러분이 이것을 대신 구해주자.

입력 첫째 줄에 비밀번호의 길이 N과 문자 종류의 개수 M, 정수 A가 주어진다. (1 <= N, M, A M= 5,000,000)

둘째 줄에 재현이가 알아낸 해시값 정수 H가 주어진다. (0 <= H < M)

출력 주어진 해시값을 갖는 비밀번호의 개수를 출력한다. 출력하는 값이 너무 커질 수 있으므로, 이것을 1,000,000,007 ( = 10^9 + 7)로 나눈 나머지를 출력한다.

예제 1

3 2 1
1 => 4

예제 2

5000000 5000000 5000000
1 => 73352076

2. 정답 소스코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);
        int a = Integer.parseInt(inputs[2]);
        int h = Integer.parseInt(br.readLine());
        long answer = 1;

        int idx = 0;
        while (idx < n-1) {
            answer = (answer * m) % 1000000007;
            idx++;
        }

        System.out.println(answer);

    }
}

3. 풀이 방법

비번 길이 N, 문자종류 갯수 M, 정수 A가 주어질때, P의 범위는 (0 <= P <= M-1)
해쉬 함수 h(p) = (P0 * A^0 + P1 * A^1 + … P{N-1} * A^{N-1}) mod M 일때, 이는 다음과 같이 정리 가능하다.

h(p) = (P0 * A^0 + P1 * A^1 + ... P{N-1} * A^{N-1}) mod M 
 = (P0 * A^0 + (P1 * A^1 + ... P{N-1} * A^{N-1})) mod M
 = (P0 + C) mod M 
설명 : (P1 * A^1 + ... P{N-1} * A^{N-1})를 계산한 값을 임의의 C라는 변수로 치환

요점은 mod 연산 이다. 즉, C값과 상관 없이 결국은 M에 대한 나머지 연산을 진행하기 때문에, h(p)는 P0의 값에 의해 결정된다. (0 <= P <= M-1)

예시) C = 629, M = 5
P0 = 1일 경우, h(p) = (1 + 629) mod 5 = 0
P0 = 2일 경우, h(p) = (2 + 629) mod 5 = 1
P0 = 3일 경우, h(p) = (3 + 629) mod 5 = 2
P0 = 4일 경우, h(p) = (4 + 629) mod 5 = 3
P0 = 5일 경우, h(p) = (5 + 629) mod 5 = 4
P0 = 6일 경우, h(p) = (6 + 629) mod 5 = 0
...

따라서, 위 문제에서 사용 가능한 전체 비밀번호가 M^N개 있을 경우, 각 해시값에 해당하는 비밀번호 가짓수는 아래와 같다
1 M^N / M = M^(N-1)
=> 코딩테스트 답변 시에는, mod 1000000007까지 진행하여 답변할 것

PS, Baekjoon

PS Baekjoon MathMatics Hash

This post is licensed under CC BY 4.0 by the author.

1. 문제

2. 정답 소스코드

3. 풀이 방법

Trending Tags