단답형
문제
독일어 원문
Auf welcher mathematischen Grundlage beruht die Sicherheit von RSA? Auf welcher mathematischen Grundlage beruht die Sicherheit von ElGamal?
한국어 해석
RSA의 보안은 어떤 수학적 Grundlage에 기반하는가? ElGamal의 보안은 어떤 수학적 Grundlage에 기반하는가?
직접 답안 작성
답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.
0/4 slots
답안은 브라우저에만 임시 저장됩니다. 채점 프레임과 비교해 스스로 판정하세요.
단계별 힌트
막혔을 때만 한 단계씩 여세요. 정답을 바로 읽는 것보다 기억을 꺼내는 시간이 중요합니다.
- 첫 힌트: RSA public key의 n에서 숨겨진 값은 무엇이고, ElGamal public key A = g^a에서 숨겨진 값은 무엇인가?
- 계산형 문항이 아니다.
- RSA reasoning: n=pq -> factorization gives φ(n) -> d=e^-1 mod φ(n).
- ElGamal reasoning: A=g^a -> finding a is discrete logarithm; DDH supports indistinguishability.
- 함정: RSA를 discrete logarithm 기반이라고 쓰기
- 함정: ElGamal의 probabilistic encryption과 hard problem을 분리하지 못하기
- 후속 점검: p, q, φ(n)을 알면 RSA private key d를 어떻게 구하는가?
채점 기준으로 내 답안 점검하기
- RSA는 factoring n 또는 φ(n) 계산 난이도에 기반한다고 쓴다.
- ElGamal은 discrete logarithm problem에 기반한다고 쓴다.
- semantic security를 묻는 맥락이면 DDH hardness도 언급한다.
- 두 scheme의 근거를 서로 바꾸지 않는다.
답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.
0/4 slots
정답과 핵심 해설 확인하기
RSA: Faktorisierungsproblem / φ(n) 계산 난이도. ElGamal: diskreter Logarithmus, semantic security는 DDH hardness.
개념부터 다시 보는 상세 풀이
BEGINNER LESSON
3-(a) RSA와 ElGamal은 어떤 수학 문제가 어려워서 안전한가?
ZERO-BASE START
정말 아무것도 모른다고 가정하고 시작합니다
전문 용어를 알고 있다고 가정하지 않습니다. 먼저 일상적인 장면을 보고, 그 장면의 사람과 행동에 실제 보안 용어를 하나씩 붙인 뒤, 시스템에서 일어나는 순서를 따라갑니다.
기초 개념 01
공개키 암호와 RSA·ElGamal의 수학적 기반
1타 강사식 시작: 이름은 잠시 가리고 장면부터 봅시다
두 색의 물감을 섞기는 쉽지만 섞인 색에서 원래 정확한 두 물감을 분리하기는 어려운 것처럼, 한 방향 계산은 쉽고 역방향은 어렵게 만든다.
지금은 이 비유를 완벽히 외울 필요가 없습니다. 누가 무엇을 가지고 있고, 무엇을 하려 하며, 어느 지점에서 문제가 생기는지만 찾으면 됩니다.
이제 실제 용어를 하나씩 붙여 봅시다
공개키 암호는 누구나 알 수 있는 public key와 소유자만 보관하는 private key를 사용한다. RSA에서는 두 큰 소수를 곱해 n을 만드는 것은 쉽지만 n만 보고 원래 소수들을 찾는 factorization이 어렵다는 점을 이용한다. ElGamal은 g^x mod p를 계산하기는 쉽지만 결과와 g, p만 보고 x를 찾는 discrete logarithm problem이 어렵다는 점을 이용한다.
TERMS FROM ZERO
전문 용어를 한 단어씩 풀기
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Public key
누구나 알아도 되는 key로, 보통 encryption 또는 signature verification에 사용됩니다.
Private key
소유자만 비밀로 가져야 하는 key로, decryption 또는 signing에 사용됩니다.
Hard problem
정상 사용자는 비밀정보로 쉽게 계산하지만 공격자는 현실적 시간에 풀기 어렵다고 가정하는 수학 문제입니다.
Trapdoor
특별한 비밀정보를 알면 어려운 계산을 쉽게 뒤집을 수 있게 하는 정보입니다.
프로그램이나 프로토콜 안에서는 다음 순서로 움직입니다.
- Public key는 공개되어도 되고 private key는 비밀이어야 한다.
- RSA의 대표 난제는 integer factorization이다.
- ElGamal의 기반은 discrete logarithm과 관련 가정이다.
- 구체적인 parameter 크기와 padding까지 올바르게 써야 실제 시스템이 안전하다.
왜 여기서 많이 틀릴까요?
‘어려운 수학 문제 기반’이라는 말이 모든 작은 숫자 예제나 잘못 구성한 키까지 안전하게 만들지는 않는다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
기초 개념 02
Modulo, 경우의 수, key space를 처음부터 계산하기
1타 강사식 시작: 이름은 잠시 가리고 장면부터 봅시다
시계에서 15시는 3시로 돌아오는 것이 modulo다. 자물쇠 번호가 9칸이고 각 칸에 26개 문자를 넣을 수 있다면 첫 칸 26가지마다 둘째 칸도 26가지가 붙으므로 선택지가 계속 곱해진다.
지금은 이 비유를 완벽히 외울 필요가 없습니다. 누가 무엇을 가지고 있고, 무엇을 하려 하며, 어느 지점에서 문제가 생기는지만 찾으면 됩니다.
이제 실제 용어를 하나씩 붙여 봅시다
Modulo는 나눗셈의 나머지를 구해 값을 일정 범위 안으로 되돌리는 연산이다. 29 mod 26은 3이다. Key space는 공격자가 고려해야 하는 가능한 키 전체의 집합이다. 독립적인 자리마다 선택지가 여러 개 있으면 곱셈 원리를 사용한다. 예를 들어 9자리 각각에 26개 문자를 고를 수 있으면 26을 9번 곱한 26^9개다.
TERMS FROM ZERO
전문 용어를 한 단어씩 풀기
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Modulo
어떤 수를 나눈 나머지만 보는 연산입니다. 시계가 12 다음 1로 돌아가는 것과 비슷합니다.
Key space
가능한 모든 key의 집합과 그 개수입니다.
Entropy
공격자가 key를 예측하기 어려운 정도를 bit 단위로 나타내는 관점입니다. 단순 길이와 항상 같지는 않습니다.
Multiplication principle
독립적으로 고르는 각 자리의 경우의 수를 곱해 전체 경우의 수를 계산하는 원리입니다.
프로그램이나 프로토콜 안에서는 다음 순서로 움직입니다.
- mod n의 결과 범위가 0부터 n-1임을 확인한다.
- 각 자리가 독립적으로 선택되는지 확인한다.
- 선택지 수를 자리 수만큼 곱하고 거듭제곱으로 적는다.
- Modulo 산술과 block mode의 데이터 의존성은 별개의 문제임을 기억한다.
왜 여기서 많이 틀릴까요?
알파벳 26개와 키 길이 9를 26×9로 계산하면 안 된다. 9개 자리마다 26개 선택이 반복되므로 26^9다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
핵심부터 말하면 시험 답안은 RSA: 큰 합성수의 소인수분해 문제(Faktorisierungsproblem), ElGamal: 유한 순환군의 이산로그 문제(diskretes Logarithmusproblem)라고 쓰면 된다. 더 정확히는 ElGamal의 IND-CPA 보안은 보통 DDH 가정과 연결된다.
이 글에서 익힐 것
공개키와 개인키가 왜 서로 다른지 이해한다.
쉬운 정방향 계산과 어려운 역방향 계산이라는 one-way problem 직관을 익힌다.
RSA의 n=pq, φ(n), e, d가 소인수분해와 어떻게 연결되는지 설명한다.
ElGamal의 g^x와 이산로그 x 찾기를 구분한다.
DLP·CDH·DDH를 시험 수준에서 구분한다.
개념부터 차근차근
-
비대칭 암호의 핵심
비대칭 암호는 공개해도 되는 public key와 소유자만 아는 private key를 사용한다. 누구나 public key로 암호화하거나 서명을 검증할 수 있지만, private key 없이는 복호화하거나 서명을 만들기 어려워야 한다. 이 차이를 만드는 것이 정방향은 쉽고 역방향은 어렵다고 믿는 수학 문제다.
-
보안은 '수학적으로 절대 불가능'이 아니라 계산적으로 어렵다는 가정
RSA와 ElGamal의 역문제에는 답이 존재한다. 충분히 작은 숫자라면 손으로도 풀 수 있다. 실제 보안은 키 크기가 충분히 클 때 알려진 알고리즘과 현실적 자원으로 답을 찾는 데 너무 오래 걸린다는 computational hardness에 의존한다.
-
Modulo 산술
공개키 암호는 나머지 연산을 자주 쓴다. a mod n은 a를 n으로 나눈 나머지다. 값이 0부터 n−1 범위에서 순환하므로 거듭제곱은 빠르게 계산할 수 있지만, 그 결과에서 원래 비밀 지수를 되찾는 문제는 어려울 수 있다.
개념부터 차근차근
Construction
서로 다른 큰 소수 p와 q를 비밀로 고른다.
n=pq를 계산해 공개한다.
φ(n)=(p−1)(q−1)를 계산한다.
gcd(e,φ(n))=1인 공개 지수 e를 고른다.
ed≡1 mod φ(n)이 되는 private exponent d를 계산한다.
Easy direction
p와 q를 알면 n과 φ(n), 그리고 e의 modular inverse d를 효율적으로 계산할 수 있다.
Hard direction
공격자는 공개키 (e,n)를 안다. n을 다시 p와 q로 소인수분해하면 φ(n)을 계산하고 d를 구할 수 있다. 충분히 큰 두 소수의 곱 n을 효율적으로 분해하기 어렵다는 것이 교과서적 RSA 보안 기반이다.
Important precision
RSA 문제를 푸는 것과 정수 소인수분해가 완전히 동치라고 일반적으로 증명된 것은 아니다. 하지만 시험의 2점 답안에서는 Faktorisierungsproblem 또는 φ(n) 계산의 어려움이 기대되는 표현이다. 또한 padding 없는 textbook RSA는 결정적이고 malleable하므로 소인수분해가 어렵다는 사실만으로 현대적 IND-CPA/CCA 안전성이 자동 보장되지 않는다.
시험 답안으로 정리하기
작은 예로 p=5, q=11이면 n=55다.
n=55를 보고 5×11임을 찾는 것은 쉽다. 그러면 φ(55)=4×10=40도 바로 안다.
실제 RSA는 n이 매우 커서 이런 factorization을 어렵게 만든다.
양자컴퓨터에서 충분히 큰 fault-tolerant Shor algorithm이 가능해지면 factorization을 효율적으로 풀 수 있으므로 RSA는 post-quantum secure가 아니다.
개념부터 차근차근
Construction
순환군 G와 generator g를 정한다.
개인키 x를 무작위로 고른다.
공개키 y=g^x를 계산한다.
암호화 때마다 새로운 무작위 r을 골라 g^r과 메시지를 shared value y^r로 가린 값을 보낸다.
Easy direction
g와 x를 알면 modular exponentiation으로 y=g^x를 빠르게 계산할 수 있다.
Hard direction
g와 y=g^x가 주어졌을 때 지수 x를 찾는 것이 discrete logarithm problem(DLP)이다. 일반 숫자 로그처럼 계산하면 되는 것이 아니라 선택한 유한군에서 어려운 문제다.
Randomness role
같은 메시지를 암호화해도 매번 새로운 r을 써야 암호문이 달라진다. r 재사용이나 잘못된 군 선택은 수학 가정이 강해도 시스템을 깨뜨릴 수 있다.
Dlp cdh ddh
-
비밀 지수 a를 찾기
DLP
g와 g^a
ElGamal의 기본 수학 난제로 가장 짧게 답할 때 사용.
-
g^(ab)를 계산하기
CDH
g, g^a, g^b
Diffie-Hellman shared secret을 직접 계산하는 문제. 강의에서는 CDH가 ElGamal 기반과 연결됨.
-
T가 g^(ab)인지 무작위 군 원소인지 구별하기
DDH
g, g^a, g^b, T
표준 ElGamal의 semantic security/IND-CPA를 설명할 때 더 정확한 가정.
헷갈리는 개념 비교하기
System
RSA
Public values
n=pq, e
자주 틀리는 지점
p,q 또는 d
Hard problem
정수 소인수분해 및 φ(n) 획득의 어려움
Quantum note
Shor algorithm의 위협
System
ElGamal
Public values
군 G, g, y=g^x
자주 틀리는 지점
x
Hard problem
이산로그; 보안 성질에 따라 CDH/DDH 가정
Quantum note
역시 Shor 계열의 위협
문제를 푸는 순서
1단계: 문제는 계산이 아니라 각 시스템의 hard problem 이름을 묻는다고 파악한다.
2단계: RSA 옆에 Faktorisierungsproblem, n=pq를 쓴다.
3단계: ElGamal 옆에 diskretes Logarithmusproblem을 쓴다.
4단계: 여유가 있으면 RSA는 φ(n)/private exponent 계산과 연결하고, ElGamal IND-CPA는 DDH 가정과 연결한다고 보충한다.
5단계: '큰 수라서 안전'처럼 모호하게 쓰지 않는다.
시험장에서는 이렇게 쓰기
Two point german
RSA basiert auf der angenommenen Schwierigkeit, ein großes Modul n=pq zu faktorisieren und damit φ(n) beziehungsweise den privaten Exponenten zu bestimmen. ElGamal basiert auf der Schwierigkeit des diskreten Logarithmusproblems in der verwendeten zyklischen Gruppe; für die IND-CPA-Sicherheit wird typischerweise die DDH-Annahme verwendet.
Minimal german
RSA: Faktorisierungsproblem. ElGamal: diskretes Logarithmusproblem (für semantische Sicherheit typischerweise DDH).
자주 틀리는 지점
RSA는 큰 소수 찾기가 어려워서 안전하다고 쓰는 것. 소수 생성·검사는 효율적이며 핵심은 공개된 큰 합성수의 factorization이다.
RSA 기반을 discrete logarithm, ElGamal 기반을 factorization으로 뒤집는 것.
ElGamal에서 단순히 modulo가 어려운 연산이라고 쓰는 것. modulo exponentiation 자체는 효율적이고 역방향 discrete log가 어렵다.
수학 난제가 어렵기만 하면 구현도 자동으로 안전하다고 생각하는 것. padding, randomness, key size, side channel이 별도 중요하다.
RSA와 ElGamal이 양자컴퓨터에도 보장된다고 쓰는 것. 둘 다 충분한 규모의 Shor algorithm에 취약하다.
한 줄로 기억하기
RSA는 곱하기는 쉽고 다시 두 소수로 쪼개기는 어렵다. ElGamal은 g를 x번 거듭제곱하기는 쉽고 결과에서 x를 로그처럼 되찾기는 어렵다.
스스로 확인하기
-
RSA에서 p,q를 알아내면 어떤 값들을 이어서 계산할 수 있는가?
φ(n)를 계산하고 e의 modular inverse인 private exponent d를 구할 수 있다.
-
g와 g^x에서 x를 찾는 문제 이름은?
Discrete Logarithm Problem(DLP).
-
ElGamal의 IND-CPA 보안과 더 직접 연결되는 구별 문제는?
Decisional Diffie-Hellman(DDH) 문제.
-
factorization이 어렵다면 padding 없는 textbook RSA도 자동으로 IND-CPA 안전한가?
아니다. textbook RSA는 결정적이어서 안전한 randomized encoding/padding이 필요하다.
설명의 근거
Gedächtnisprotokoll Computersystemsicherheit WS2025_26.md, Krypto / Asymmetrische Kryptographie, 3-(a), 2 Punkte.
Vorlesung 04 Asymmetrische Kryptographie, p.11-18 — RSA key generation, φ(n), private exponent와 보안 논의.
Vorlesung 04 Asymmetrische Kryptographie, p.53-58 — DLP/CDH 및 Diffie-Hellman·ElGamal 기반 논의.
예제로 확인하기
-
공개키 암호와 RSA·ElGamal의 수학적 기반을 구체적인 순서로 보기
두 색의 물감을 섞기는 쉽지만 섞인 색에서 원래 정확한 두 물감을 분리하기는 어려운 것처럼, 한 방향 계산은 쉽고 역방향은 어렵게 만든다.
Public key는 공개되어도 되고 private key는 비밀이어야 한다.
RSA의 대표 난제는 integer factorization이다.
ElGamal의 기반은 discrete logarithm과 관련 가정이다.
구체적인 parameter 크기와 padding까지 올바르게 써야 실제 시스템이 안전하다.
각 단계에서 입력이나 message가 어떻게 달라지는지 확인한 뒤 현재 문제의 조건과 결론에 연결합니다.
-
Modulo, 경우의 수, key space를 처음부터 계산하기을 구체적인 순서로 보기
시계에서 15시는 3시로 돌아오는 것이 modulo다. 자물쇠 번호가 9칸이고 각 칸에 26개 문자를 넣을 수 있다면 첫 칸 26가지마다 둘째 칸도 26가지가 붙으므로 선택지가 계속 곱해진다.
mod n의 결과 범위가 0부터 n-1임을 확인한다.
각 자리가 독립적으로 선택되는지 확인한다.
선택지 수를 자리 수만큼 곱하고 거듭제곱으로 적는다.
Modulo 산술과 block mode의 데이터 의존성은 별개의 문제임을 기억한다.
각 단계에서 입력이나 message가 어떻게 달라지는지 확인한 뒤 현재 문제의 조건과 결론에 연결합니다.
이 문제가 어려운 이유
짧은 문제 문장 ‘RSA의 보안은 어떤 수학적 Grundlage에 기반하는가? ElGamal의 보안은 어떤 수학적 Grundlage에 기반하는가?’ 안에 정의, 조건, 처리 순서가 압축되어 있습니다. 아래 예시에서는 이를 한 단계씩 펼쳐 확인합니다.
AI 구두시험용 프롬프트
한 문항만 풀어라. 먼저 정답을 열지 말고 90초 안에 답안을 말한 뒤, css-ws2025-26-crypto-asym-001의 채점 프레임으로 스스로 채점하라. 문제: RSA의 보안은 어떤 수학적 Grundlage에 기반하는가? ElGamal의 보안은 어떤 수학적 Grundlage에 기반하는가?
학습 기록