암호학 정수론 입문: 모듈러 연산·역원·소수와 보안 강도

1장 개념과 보호 목표#

모듈러 연산은 정수를 나눈 나머지의 세계에서 계산하는 방식입니다. RSA와 Diffie-Hellman의 원리를 이해하려면 나머지 연산, 곱셈 역원, 소수와 어려운 수학 문제를 구분해야 합니다. 수학 예제를 이해하는 것과 안전한 구현을 직접 만드는 것은 별개의 일입니다.

2장 원리와 구분#

7×103을 120으로 나눈 나머지는 1이므로 103은 7의 모듈러 곱셈 역원입니다. 역원이 존재하려면 두 수가 서로소여야 합니다. 오일러 정리는 서로소인 a와 n에 대해 a^φ(n)≡1 mod n이라고 말하며, 소수 p에 대한 페르마의 소정리는 그 특수한 경우입니다. 소수 생성에는 안전한 난수와 적절한 판별 절차가 필요합니다.

모듈러 연산에서 a−b가 음수가 될 때 언어의 나머지 연산 결과가 수학적 대표값과 다를 수 있습니다. 또한 큰 정수 연산은 자료형 범위와 상수시간 조건을 고려해야 합니다. 교육용 계산에서 맞는 결과를 얻었다는 사실만으로 키 생성 코드의 안전성을 입증할 수 없습니다.

3장 합동은 같은 수라는 뜻이 아니다#

a≡b mod m은 a와 b의 차이가 m의 배수라는 관계입니다. 17≡5 mod 12이지만 일반 정수로 17과 5가 같은 것은 아닙니다. 같은 나머지를 갖는 값들을 묶어 계산한다는 뜻입니다. 암호 수식의 기호를 일반 등호와 섞으면 지수와 역원의 관계를 오해하기 쉽습니다.

17 = 1×12 + 5 → 나머지 5
29 = 2×12 + 5 → 나머지 5
따라서 17 ≡ 29 ≡ 5 (mod 12)

4장 중간에 나머지를 계산해도 되는 이유#

덧셈과 곱셈의 중간 결과에 나머지를 적용하면 큰 정수를 줄이며 계산할 수 있습니다. 모듈러 거듭제곱도 반복 제곱과 곱셈을 이용합니다. 지수가 커져도 모든 거듭제곱을 먼저 만든 뒤 마지막에 나누는 방식만 가능한 것은 아닙니다.

운영에서는 큰 정수 라이브러리의 검증된 연산을 사용합니다. 교육용 산술이 맞아도 비밀에 따라 실행시간이나 메모리 접근이 달라지는 구현은 별도의 위험을 가질 수 있습니다.

5장 최대공약수와 서로소#

서로소는 두 정수의 최대공약수가 1이라는 조건입니다. 소수인 두 값만 서로소가 되는 것은 아닙니다. 예를 들어 8과 15도 서로소입니다. 모듈러 역원과 RSA 지수 선택에서 이 조건이 등장합니다.

gcd(8,15)=1 → 서로소
gcd(6,15)=3 → 서로소가 아님
gcd(a,m)=1 → a의 mod m 곱셈 역원 존재

6장 유클리드 알고리즘을 작은 수로 따라가기#

gcd(120,7)를 구할 때 120=17×7+1, 7=7×1+0이므로 최대공약수는 1입니다. 나머지를 반복하는 과정은 큰 수에서도 적용됩니다. 확장 유클리드 알고리즘은 이런 관계에서 계수를 되짚어 역원을 구하는 데 사용할 수 있습니다.

120 = 17×7 + 1
1 = 120 − 17×7
따라서 −17×7 ≡ 1 (mod 120)
−17 mod 120 = 103 → 7의 역원은 103

7장 모듈러 나눗셈이 일반 나눗셈과 다른 이유#

일반적인 나눗셈처럼 아무 값으로나 나눌 수 없습니다. 역원이 있을 때 그 역원을 곱하는 방식으로 해석합니다. 2 mod 4는 역원이 없어 일반 정수 분수의 감각을 그대로 옮길 수 없습니다. 암호 구현에서 잘못된 파라미터를 거부하는 이유와 연결됩니다.

값 a와 모듈러스 m	최대공약수	역원 판단
a=3, m=11	1	존재: 4
a=7, m=120	1	존재: 103
a=2, m=4	2	존재하지 않음

8장 소수와 합성수의 연산 환경#

소수 p에 대한 나머지에서는 0이 아닌 값들이 곱셈 역원을 갖습니다. 합성수에서는 그렇지 않은 값이 있을 수 있습니다. RSA의 합성수 모듈러스와 DH의 그룹 파라미터를 같은 용도의 숫자로 생각하지 않습니다. 각 방식의 연산 구조와 보안 가정을 확인해야 합니다.

소수라는 사실만으로 실제 암호 파라미터가 적절한 것도 아닙니다. 크기·그룹 조건·난수·표준이 요구하는 검증을 함께 적용하고 직접 만든 작은 예제를 운영 값으로 사용하지 않습니다.

9장 거듭제곱을 반복 제곱으로 계산하기#

지수 7은 4+2+1이므로 5^7을 5^4·5^2·5로 표현합니다. 각 단계에서 mod 143을 적용하면 5^2→25, 5^4→53, 최종→47입니다. 교육에서는 계산 과정을 적고 코드의 결과와 비교하면 나머지·지수의 역할을 이해하기 쉽습니다.

flowchart LR
 A["5"] --> B["제곱 후 mod 143: 25"]
 B --> C["다시 제곱 후 mod 143: 53"]
 C --> D["지수 4·2·1의 결과 곱하기"]
 D --> E["5의 7승 mod 143: 47"]

10장 키 길이와 보안 강도의 비교#

대칭키의 전수조사, RSA의 소인수분해 관련 공격, ECC의 이산로그 관련 공격은 구조가 다릅니다. 같은 숫자의 비트 길이를 같은 강도로 순위를 매기지 않습니다. 해시의 충돌 비용과 원상 비용도 서로 다른 질문입니다.

키 사용 기간·데이터 보존기간·현재 공격 방법·규정 요구를 함께 고려해 파라미터를 선택합니다. 긴 키가 Nonce 재사용이나 개인키 로그 노출을 해결하지는 않습니다.

11장 프로그래밍 언어의 정수 표현을 확인한다#

고정 길이 정수의 오버플로우, 음수 나머지의 규칙, 큰 정수 인코딩·바이트 순서가 계산을 바꿀 수 있습니다. 수학적으로 같은 수라도 전송 형식이 다르면 프로토콜의 입력이 달라집니다. 검증된 큰 정수·암호 라이브러리를 사용하고 표준 테스트 벡터와 대조합니다.

정수론 학습의 목적은 알고리즘을 혼자 구현하는 것보다 수식과 파라미터의 조건을 정확히 읽는 데 있습니다. 역원이 존재하는지, 어떤 모듈러스인지, 어떤 비밀을 보호하는지를 따라가면 기술 설명과 점검 근거를 연결할 수 있습니다.

12장 적용 사례와 운영 방법#

키 길이와 보안 비트는 다릅니다. 고전적 공격 기준의 비교에서 RSA-3072와 256비트 타원곡선은 대략 128비트 보안 강도에 대응하지만 구체적인 곡선·스킴·구현을 확인해야 합니다. 역사적으로 DES에서 AES, 공개키 암호에서 PQC로 관심이 이동한 이유도 공격 기술과 운영 환경의 변화입니다.

13장 나머지 연산에서 역원이 존재하는 조건#

정수 a의 모듈러 m에 대한 역원은 a×x≡1 mod m을 만족하는 x입니다. gcd(a,m)=1일 때 역원이 존재합니다. 예를 들어 3×4=12≡1 mod 11이므로 3의 역원은 4입니다. 반면 2와 4는 최대공약수가 2여서 2의 mod 4 역원이 없습니다. 일반 나눗셈의 감각을 그대로 적용하면 계산을 틀리기 쉽습니다.

소수 mod p에서 0이 아닌 값들은 곱셈 역원을 갖지만 합성수의 경우 모든 값이 그런 것은 아닙니다. 유클리드 알고리즘은 최대공약수를, 확장 유클리드 알고리즘은 역원 계산에 필요한 계수를 구하는 데 활용합니다. RSA의 지수 관계와 DH의 거듭제곱을 같은 연산 언어로 읽을 수 있는 이유입니다.

14장 키 길이와 보안 강도를 나누어 읽기#

키 길이는 표현의 비트 수이고 보안 강도는 알려진 공격으로 비밀을 찾는 비용의 척도입니다. 대칭키·RSA·ECC는 공격 구조가 달라 같은 비트 수를 같은 안전성으로 볼 수 없습니다. 이상적 전수조사의 평균 비용과 실제 알고리즘의 최선 공격 비용도 구분해야 합니다.

학습에서는 작은 수로 역원과 거듭제곱을 계산하고, 운영에서는 표준의 보안 강도 대응과 키 사용 기간을 확인합니다. 큰 소수를 선택했다는 사실만으로 충분하지 않습니다. 안전한 난수·파라미터·프로토콜 인증과 구현 품질이 함께 맞아야 합니다.

15장 적용 전 확인할 사항#

수식 예제와 실제 라이브러리 사용을 구분한다
키 길이 비교에 공격 모델과 보안 비트를 명시한다
표준의 파라미터와 사용 조건을 함께 확인한다

16장 자주 묻는 질문#

타원곡선 키를 두 배로 늘리면 안전성도 두 배가 되나요?#

길이만으로 단정할 수 없습니다. 곡선의 구조와 공격 복잡도, 구현·프로토콜 조건을 포함해 표준이 제시하는 보안 강도를 확인해야 합니다.

나머지 연산은 음수에도 적용할 수 있나요?#

합동 관계는 음수에도 정의되지만 프로그래밍 언어의 나머지 연산 결과는 다를 수 있습니다. 구현에서는 사용하는 라이브러리의 정규화 규칙을 확인해야 합니다.

소인수분해가 어렵다는 사실만으로 RSA 구현이 안전한가요?#

안전한 패딩·키 생성·부채널 방어·오류 처리가 필요합니다. 수학적 문제의 어려움과 시스템 전체의 공격 경로를 함께 검토해야 합니다.