Skip to content
Beside the Wheel

RSA 암호화 이해하기 with 백준

RSA
알고리즘

RSA는 대표적인 비대칭 암호화 방식 중 하나이다.

연산자, 조건문, 반복문 등 기본적인 프로그래밍을 이해하고 있다는 전제로, RSA의 동작 방식과 수학적 원리를 차근차근 배워보자. 그리고 백준 온라인 저지에 등록된 관련 문제를 실제로 구현해보자.

군

RSA에 대해 이해하기 위해선 우선 군(group)이 무엇인지 알아야한다.
오늘날 RSA를 비롯한 많은 암호화 방식이 군론을 기반으로 한다. 개념은 어렵지 않다.

군이란, 아래 규칙에 맞게 원소의 집합과 연산(덧셈, 곱셈)을 정의한 것이다.

  • 닫힘: 집합 안의 두 원소를 연산했을 때, 그 결과가 군 안에 속해야한다.
  • 결합법칙: 여러 원소에 대한 연상을 임의의 순서로 수행할 수 있다. (e.g. (a+b)+c = a+(b+c))
  • 항등원: 특정 원소와 피연산자를 연산한 결과가 동일할 수 있어야한다. 그 원소를 항등원이라 부른다. (e.g. a+0=a, 이 경우 항등원인 0이 군 내에 존재함)
  • 역원: 두 원소를 연산한 결과가 항등원인 특정 원소가 군 내에 존재한다. 그 원소를 역원이라 부른다. (e.g. a+(-a)=0, 이 경우 역원인 -a가 군에 존재함)

RSA에서 사용하는 군은 1, 2, 3, …, p-1과 같이 특정 수 이하의 양의 정수로 구성된 군이다.

양의 정수끼리 그냥 덧셈한 결과는 p-1보다 큰 수가 될 수 있으니, 군의 성질을 만족시키기 위해 덧셈 연산을 (a+b)%p로 정의한다. %는 모듈러 연산자이고 p로 나눈 나머지값을 결과로 한다.

순환부분군

여기서 어떤 수를 정하고 자신을 계속해서 곱하면 똑같은 패턴이 반복되는데, 이를 순환부분군이라 한다. 시작한 수는 생성원(generator)이나 베이스(base)로 부른다.

2 mod 5           = 2
2*2 mod 5         = 4
2*2*2 mod 5       = 3
2*2*2*2 mod 5     = 1
2*2*2*2*2 mod 5   = 2
2*2*2*2*2*2 mod 5 = 4
... (반복)

RSA로 암호화하는 방법이 이 부분군을 이용한다.

RSA로 암호화할 때, 메세지 m은

ciphertext = m^e mod p
ciphertext^d = (message^e)^d = message^{e*d} = message mod p

비밀지수 d 찾기: 오일러의 정리

이 비밀지수 d를 찾는 수학은 굉장히 까다롭다. 간단히 말하면 공개 지수의 역수와 그룹의 차우(원소 수), order를 mod 연산한 값을 계산한다.

d = e^-1 mod p

모듈러 역한수를 계산하는 효율적인 알고리즘이 있으므로 이는 문제가 되지 않는다. 하지만 또 다른 문제가 있다! 소수 p가 주어질 때 차수는 단순히 p-1이므로 누구나 비밀 지수를 계산하기 쉽다.

오일러의 정리

모듈러 역수 구하기

모듈러 역수를 쉽게 구하는 방법은 크게 페르마 소정리를 이용하는 방법과 확장 유클리드 호제법을 이용하는 방법이 있다. 페르마 소정리는 모듈로 하는 값이 소수일 때만 사용할 수 있다.

페르마 소정리

소수 m, 임의의 수 a에 대해 아래 식이 성립한다.

a^(m-1) = a*a^(m-2) = 1

증명

  1. a와 서로소인 소수 p에 대해 a, 2a, 3a, …, (p−1)a인 p−1개의 수를 p로 나눴을 때 나오는 나머지는 모두 다르다.

    귀류법으로 증명된다. 0<i<j<p인 정수에서 ia와 ja의 나머지가 같다고 하면

    ia != ja (mod p)
    ja - ia = 0 (mod p)
    • 위 식이 성립하기 위해선, (j-i)a가 p로 나눠떨어져야함. a는 p와 서로소이므로 j-i가 p로 나눠떨어져야한다.
    • 하지만 조건에 따라 i-j가 p보다 클 수 없음 (i-j < p-1). 성립하려면 i-j가 0, 즉 두 수가 같아야한다.
    • 모순이 발생하므로 어떤 수와 0보다 크고 p보다 작은 수의 곱셈에 대해 p로 나눈 나머지는 항상 다르다.

  2. 아래와 같은 집합 A, B에서 집합 B는 p와 서로소인 수를 p로 나눌 때 생기는 모든 나머지들의 집합이다.

    A = { x | x=ia, i∈B }
    B = { 1, 2, ..., p−1 }

  3. 즉

    a * 2a * 3a * ... * (p−1)a = 1 * 2 * ... * (p−1) (mod p)
    (p−1)! * a^(p-1) = (p-1)! (mod p)

    이므로, 양변을 (p−1)!로 나누면

    a^(m-1) = a*a^(m-2) = 1

알고리즘 분류: 페르마의 소정리

다만 바로 위에서 말했듯 m이 소수여야만 사용할 수 있음. 확장 유클리드 호제법은 m이 소수가 아닌 경우에도 사용할 수 있지만, 여기서 설명하기에는 여백이 모자라니 찾아보기를 바람. 확장 유클리드 호제법은 생각보다 유용한 도구니만큼, 정수론 관련 문제를 풀 때 종종 등장하니 알아둬서 나쁠 건 없음.

그런데, 맨 처음에 말했듯 a의 역원이 존재하지 않을 수 있음. a의 역원이 존재할 조건은 바로 a와 m이 서로소라는 것임. 2 * b % 4 = 1인

b가 존재하지 않는 것은 gcd(2, 4) = 2가 되어 서로소가 아니기 때문임.

여담: 알고리즘 문제에서 결과를 10^9+7로 나눈 나머지로 출력시키는 이유

우선 32비트 정수 오버플로우를 막기 위함이고, 하필 소수로 사용하는 이유는 소수여야 모듈러 곱셈 역원을 구할 수 있기 때문이다. 10^7+9는 10자리인 첫 번째 소수이기 때문에 자주 사용된다고 한다.

풀어 말하자면 실수에서 2를 나누는 것과 1/2를 곱하는 것 대신 군 안에서는 2를 나누는 대신 모듈러 했을 때의 곱셈 역원인 정수를 대신 곱해줄 수 있는데, 모듈러하는 값이 소수일 때만 곱셈 역원이 항상 존재한다. ( e.g. m=8, a=1, b=2에서 1/2 mod{8}을 구할 수 없음 )

팩토리얼, 조합 경우의 수와 같이 매우 큰 수를 계산할 때 곱셈 역원을 사용할 수 있다.

C(n, k) = n! x (k!)^-1 x ((n-k)!)^-1 (mod p)

참고

BOJ 14565 역원(Inverse) 구하기

번외: BOJ 조합(Composite)

13618 RSA: 해보자

해결하는 소수를 구하는 13618번 문제를 풀어보자.

여담

다른 비대칭 암호화 방식인 타원곡선 암호화는 군이 아닌 체(Field)라는 용어로 설명한다. Z/nZ는 n이 합성수일 때 체가 아닙니다 n = p×q일 때, 0이 아닌 원소가 곱셈 역원을 갖지 않을 수 있음 예: n=15일 때, 3×5 ≡ 0 (mod 15)이므로 영인자(zero divisor)가 존재

참고