몽고메리 사다리

2025.11.18 15:14

몽고메리 사다리 알고리즘은 거듭제곱을 안전하고 효율적으로 계산하는 방법이다.

a^n을 계산하고 싶다면 가장 단순한 방법은 a를 n번 곱하는 것이다. 하지만 n이 크면 비효율적이다.

# 느린 방법
result = 1
for i in range(n):
    result = result * a

n = 1000이면 999번의 곱셈이 필요하다.

더 나은 방법은 분할 정복을 사용하는 것이다. 거듭제곱의 지수를 반으로 나눠가며 계산한다.

a^8 = a^4 × a^4
a^4 = a^2 × a^2
a^2 = a × a

이렇게 하면 8번 곱하는 대신 3번만 곱하면 된다.

a^n = (a^(n/2))^2           (n이 짝수)
a^n = a × (a^((n-1)/2))^2   (n이 홀수)

지수 n을 이진수로 표현하면 더 명확해진다. 예를 들어 a^13을 계산한다고 하자. 13을 이진수로 나타내면 1101₂이다.

13 = 8 + 4 + 1
   = 2^3 + 2^2 + 2^0

따라서:

a^13 = a^(2^3 + 2^2 + 2^0)
     = a^8 × a^4 × a^1

이다. a^1, a^2, a^4, a^8, …을 차례로 계산하면서, 지수의 이진 표현에서 1인 비트에 해당하는 항들만 곱하면 된다.

이진 표현을 이용한 거듭제곱 알고리즘은 이렇게 작동한다.

def binary_exponentiation(a, n):
    result = 1
    base = a

    while n > 0:
        if n % 2 == 1:  # n의 마지막 비트가 1이면
            result = result * base
        base = base * base  # 다음 비트를 위해 base를 제곱
        n = n // 2  # 다음 비트로 이동

    return result

예를 들어 a^13 (1101₂):

n = 13 (1101)
비트 확인: 1 → result = a^1, base = a^2
비트 확인: 0 → base = a^4
비트 확인: 1 → result = a^1 × a^4 = a^5, base = a^8
비트 확인: 1 → result = a^5 × a^8 = a^13

이 방법은 O(log n)번의 곱셈으로 거듭제곱을 계산한다. 매우 효율적이다.

사이드 채널 공격의 위협

하지만 암호학에서는 효율성만으로는 부족하다. 위의 알고리즘을 자세히 보면 보안적으로 문제가 생길 수 있다. 지수의 비트가 1일 때와 0일 때 다른 연산을 수행하기 때문이다.

비트가 1: result 갱신 + base 제곱 (2번 곱셈)
비트가 0: base 제곱만 (1번 곱셈)

만약 공격자가 계산 시간을 측정하거나, 전력 소비를 분석하거나, 전자기파 방출을 관찰할 수 있다면? 각 비트마다 연산 횟수가 다르므로 비밀 지수를 알아낼 수 있다.

이런 공격을 사이드 채널 공격이라고 한다. 암호 알고리즘 자체를 공격하는 게 아니라, 구현의 물리적 특성을 관찰해서 비밀 정보를 추출하는 것이다. RSA 개인키나 타원곡선 암호의 비밀 스칼라처럼 절대 노출되어선 안 되는 지수를 다룰 때, 큰 보안 문제가 될 수 있다.

몽고메리 사다리

몽고메리 사다리 알고리즘은 이 문제를 해결한다. 핵심 아이디어는 모든 비트에서 동일한 연산을 수행하는 것이다.

우선 두 개의 변수 R0과 R1을 유지한다.

R0: 현재까지 처리한 비트로 계산한 값
R1: R0의 다음 단계 값 (R0 × a)

각 비트마다:

비트가 0이면: R0 = R0^2, R1 = R0 × R1
비트가 1이면: R1 = R1^2, R0 = R0 × R1

이 방식을 사용하면 어떤 비트든 항상 정확히 2번의 곱셈을 수행하게 된다. 0일 때도, 1일 때도 마찬가지다. 연산 패턴이 일정하므로, 타이밍 분석이나 전력 분석으로는 비트 값을 알아낼 수 없다.

def montgomery_ladder(a, n):
    R0 = 1
    R1 = a

    # n의 최상위 비트부터 처리
    bits = bin(n)[2:]  # '0b' 제거

    for bit in bits:
        if bit == '0':
            R1 = R0 * R1
            R0 = R0 * R0
        else:
            R0 = R0 * R1
            R1 = R1 * R1

    return R0

이 방식이 올바른 결과를 얻는 이유는 각 단계에서 불변량이 유지되기 때문이다.

**불변량(invariant)**이란 알고리즘의 모든 단계에서 항상 참이 되는 조건을 의미한다. 루프를 반복하거나 상태가 변할 때도 이 조건은 절대 깨지지 않는다. 불변량이 올바르게 유지되면, 알고리즘이 끝났을 때 원하는 결과를 얻었음을 보장할 수 있다.

몽고메리 사다리 알고리즘의 불변량은 다음과 같다.

R1 = R0 × a

즉, 어떤 비트를 처리하든 항상 “R1은 R0에 a를 곱한 값”이라는 관계가 유지된다. 이 관계가 유지되는 한, R0이 올바른 거듭제곱 값을 가지면 알고리즘이 정확하게 작동한다는 것을 수학적으로 증명할 수 있다.

초기값:

R0 = 1 = a^0
R1 = a = a^1
불변량: a^1 = a^0 × a ✓

비트가 0일 때:

R0_new = R0^2
R1_new = R0 × R1
불변량 확인: R1_new = R0 × R1 = R0 × (R0 × a) = R0^2 × a = R0_new × a ✓

비트가 1일 때:

R0_new = R0 × R1
R1_new = R1^2
불변량 확인: R1_new = R1^2 = (R0 × a)^2 = R0^2 × a^2 = (R0 × R1) × a = R0_new × a ✓

더 직관적으로 이해하려면, R0이 표현하는 지수를 추적해보자.

예를 들어 a^13 (1101₂):

초기: R0 = a^0, R1 = a^1

비트 1: R0 = a^1, R1 = a^2
비트 1: R0 = a^3, R1 = a^4  (R0 지수: 1×2+1 = 3)
비트 0: R0 = a^6, R1 = a^7  (R0 지수: 3×2+0 = 6)
비트 1: R0 = a^13, R1 = a^14 (R0 지수: 6×2+1 = 13)

각 비트마다 현재 지수를 2배하고, 비트가 1이면 +1을 한다. 정확히 이진수를 왼쪽에서 오른쪽으로 읽으며 만드는 과정이다.

타원곡선 암호에서의 응용

몽고메리 사다리는 타원곡선 암호학에서 특히 중요하다.

타원곡선 위의 점 P에 대해 스칼라 곱셈 nP를 계산할 때, 거듭제곱과 같은 원리를 사용한다.

곱셈 대신 점 덧셈
제곱 대신 점 배가(doubling)

def montgomery_ladder_ec(P, n):
    R0 = O  # 무한원점 (항등원)
    R1 = P

    bits = bin(n)[2:]

    for bit in bits:
        if bit == '0':
            R1 = R0 + R1  # 점 덧셈
            R0 = R0 + R0  # 점 배가
        else:
            R0 = R0 + R1
            R1 = R1 + R1

    return R0

실제 타원곡선 암호 구현에서는 몽고메리 곡선이라는 특수한 형태의 곡선을 사용하면 연산이 더 효율적이다.

실제 구현 시 주의사항

진짜 암호학적으로 안전한 구현을 만들려면 추가 고려사항이 더 있다.

조건 분기 제거

위의 코드에는 if bit == '0' 같은 조건문이 있다. 일부 컴파일러나 CPU는 분기 예측을 사용하는데, 이것도 사이드 채널이 될 수 있다.

완전히 안전하게 만들려면 조건부 실행 대신 비트 마스킹을 사용한다.

def montgomery_ladder_ct(a, n, mod):
    R0 = 1
    R1 = a

    bits = bin(n)[2:]

    for bit in bits:
        b = int(bit)  # 0 or 1

        # 조건 없이 계산
        temp0 = (R0 * R1) % mod
        temp1_0 = (R0 * R0) % mod
        temp1_1 = (R1 * R1) % mod

        # 비트 값에 따라 선택 (constant-time select)
        R0 = temp1_0 if b == 0 else temp0
        R1 = temp0 if b == 0 else temp1_1

    return R0

실제로는 constant-time select 함수를 비트 연산으로 구현한다.

def ct_select(a, b, bit):
    """bit가 0이면 a, 1이면 b를 반환 (constant-time)"""
    mask = -bit  # bit=0이면 0x000..., bit=1이면 0xFFF...
    return (a & ~mask) | (b & mask)

메모리 접근 패턴
- 배열 인덱스도 비밀에 의존하면 안 된다. 캐시 타이밍 공격으로 패턴을 추출할 수 있다.
곱셈 자체의 타이밍
- 큰 수의 곱셈 알고리즘 자체도 입력 값에 따라 시간이 달라질 수 있다. 암호학 라이브러리는 이를 고려한 특수 연산을 제공한다.

참고

알고리즘Range GCD 알고리즘가장 가까운 두 점 알고리즘담금질 기법 알고리즘볼록 껍질과 회전하는 캘리퍼스 알고리즘오일러 경로 테크닉 알고리즘왜판원순회