1.3. Asymmetrische Kryptographie

1. Kryptographie · 실제 시험 Abschnitt 1.3

RSA·ElGamal의 수학적 가정, 서명 공격, RSA 키 생성·암호화·서명을 1–5번 순서 그대로 풉니다.

이 페이지는 비슷한 주제를 임의로 다시 묶지 않고 실제 시험지의 Chapter → subsection → 소문제 순서를 그대로 따릅니다.

ACTUAL EXAM · VERBATIM TRANSCRIPT

시험지 원문 1:1 전사

아래 내용은 해설자가 바꿔 쓴 요약이 아닙니다. 실제 시험 전사본의 문장·순서·수치·배점·코드·표를 그대로 두고, Markdown 기호만 읽기 쉬운 제목·표·코드 모양으로 표시했습니다.

1.3. Asymmetrische Kryptographie (24 Punkte)

1. Auf welcher mathematischen Grundlage beruht die Sicherheit von RSA? Auf welcher mathematischen Grundlage beruht die Sicherheit von ElGamal? (2 Punkte)

2. Beschreiben Sie einen Selective-Forgery-Under-Chosen-Message-Angriff im Kontext von digitalen Signaturen. (4 Punkte)

3. Bestimmen Sie ein gültiges Schlüsselpaar ((e,n),(d,n)) für das RSA Kryptosystem mit den Parametern p = 7 und q = 7. Sie müssen keinen Rechenweg angeben sondern nur Ihre Ergebnisse für n, \varphi(n), e und d. Die Werte e = 1, d = 1 sind hierbei ausgeschlossen! (8 Punkte)

n = __________
φ(n) = ________
e = __________
d = __________

4. Verschlüsseln Sie die Nachricht m = 4 mit dem RSA Kryptosystem. Verwenden Sie dazu den öffentlichen Schlüssel (3,55). Geben Sie Ihren Rechenweg mit an! (4 Punkte)

5. Signieren Sie den Hash h = 3 mit dem RSA-Kryptosystem. Verwenden Sie dazu das Schlüsselpaar ((e,n),(d,n)) = ((11,15),(3,15)). Geben Sie Ihren Rechenweg mit an! (6 Punkte)

# 2. Netzwerksicherheit (62 Punkte)

근거: CSS_Altklausur_WiSe_2526.pdf 및 computersystemsicherheit_wise25-26_questions_only.md · Abschnitt 1.3

VISUAL MAP

공개키 문제의 두 갈래 왼쪽에서 오른쪽으로 읽은 뒤 아래 실제 소문제에서 같은 순서를 반복합니다.

01 목표 확인
02 키 방향
03 수학식 선택
04 mod 계산
05 검증

FIXED SOLVING METHOD

이 묶음의 고정 풀이 순서

문제가 암호화·서명·키 생성 중 무엇인지 표시합니다.
사용할 공개키 또는 개인키를 먼저 적습니다.
RSA 키 생성은 n, φ(n), e, d 순서로 계산합니다.
거듭제곱은 작은 중간값으로 나누어 매 단계 modulo를 취합니다.
마지막 값을 원래 식에 다시 대입해 검산합니다.

ZERO-BASE CONCEPT LESSONS

이 묶음을 풀기 전에 필요한 개념

카드를 열고 닫는 방식 대신 한 방향으로 이어지는 글로 구성했습니다. 비유 → 용어의 쉬운 뜻 → 실제 작동 → 시험에서의 경계 순서로 천천히 읽으세요.

기초 개념 01

공개키 암호와 RSA·ElGamal의 수학적 기반

먼저 장면으로 이해해 봅시다. 두 색의 물감을 섞기는 쉽지만 섞인 색에서 원래 정확한 두 물감을 분리하기는 어려운 것처럼, 한 방향 계산은 쉽고 역방향은 어렵게 만든다.

이제 전문 용어를 붙이면 다음과 같습니다. Public key은(는) 누구나 알아도 되는 key로, 보통 encryption 또는 signature verification에 사용됩니다. Private key은(는) 소유자만 비밀로 가져야 하는 key로, decryption 또는 signing에 사용됩니다. Hard problem은(는) 정상 사용자는 비밀정보로 쉽게 계산하지만 공격자는 현실적 시간에 풀기 어렵다고 가정하는 수학 문제입니다. Trapdoor은(는) 특별한 비밀정보를 알면 어려운 계산을 쉽게 뒤집을 수 있게 하는 정보입니다.

실제 시스템에서는 이렇게 작동합니다. 공개키 암호는 누구나 알 수 있는 public key와 소유자만 보관하는 private key를 사용한다. RSA에서는 두 큰 소수를 곱해 n을 만드는 것은 쉽지만 n만 보고 원래 소수들을 찾는 factorization이 어렵다는 점을 이용한다. ElGamal은 g^x mod p를 계산하기는 쉽지만 결과와 g, p만 보고 x를 찾는 discrete logarithm problem이 어렵다는 점을 이용한다.

Public key는 공개되어도 되고 private key는 비밀이어야 한다.
RSA의 대표 난제는 integer factorization이다.
ElGamal의 기반은 discrete logarithm과 관련 가정이다.
구체적인 parameter 크기와 padding까지 올바르게 써야 실제 시스템이 안전하다.

여기서 넘지 말아야 할 경계: ‘어려운 수학 문제 기반’이라는 말이 모든 작은 숫자 예제나 잘못 구성한 키까지 안전하게 만들지는 않는다.

07. Public key·RSA·ElGamal·Signature 독립 강의 →

기초 개념 02

RSA 계산에 필요한 소수·φ·서로소·역원

먼저 장면으로 이해해 봅시다. e로 자물쇠를 한 방향으로 돌린 뒤 d로 돌렸을 때 바퀴가 정확히 한 바퀴를 돌아 원위치에 오는 조합을 찾는다고 생각할 수 있다.

이제 전문 용어를 붙이면 다음과 같습니다. Prime number은(는) 1과 자기 자신으로만 나누어지는 1보다 큰 정수입니다. Euler φ function은(는) n 이하에서 n과 서로소인 수의 개수를 나타내며 RSA key 계산에 사용됩니다. Coprime은(는) 두 수의 최대공약수가 1인 관계입니다. Modular inverse은(는) `a·b ≡ 1 (mod n)`을 만족하는 b로, modulo 세계에서 나눗셈 역할을 합니다.

실제 시스템에서는 이렇게 작동합니다. 소수(prime)는 1과 자기 자신으로만 나누어지는 2 이상의 정수다. RSA는 보통 서로 다른 소수 p와 q를 골라 n=pq를 만든다. Euler의 φ(n)는 1부터 n까지 중 n과 서로소인 수의 개수다. p와 q가 서로 다른 소수라면 φ(n)=(p-1)(q-1)이다. 공개 지수 e는 φ(n)과 최대공약수가 1이어야 하고, 개인 지수 d는 ed≡1 mod φ(n)을 만족하는 modular inverse다.

n=pq를 계산하고 p와 q가 유효한 소수인지 확인한다.
p≠q이면 φ(n)=(p-1)(q-1)을 사용한다. p=q인 특수 입력은 φ(p²)=p²-p다.
gcd(e,φ(n))=1인 e를 고른다.
ed mod φ(n)=1이 되는 d를 찾는다.
암호화 c=m^e mod n, 복호화 m=c^d mod n을 목적에 맞게 적용한다.

여기서 넘지 말아야 할 경계: p=q인데 서로 다른 소수 공식 (p-1)(q-1)을 그대로 쓰거나, e와 d가 역원인지 확인하지 않고 숫자를 고르면 안 된다.

07. Public key·RSA·ElGamal·Signature 독립 강의 →

기초 개념 03

Digital signature는 무엇을 증명하는가

먼저 장면으로 이해해 봅시다. 편지 내용을 가리는 봉투가 encryption이라면 signature는 편지 내용에 연결된 위조하기 어려운 도장이다. 누구나 도장을 검사할 수 있지만 소유자만 새 도장을 만들 수 있어야 한다.

이제 전문 용어를 붙이면 다음과 같습니다. Digital signature은(는) private key 소유자가 특정 메시지에 서명했음을 검증하게 하는 값입니다. Signing은(는) 메시지와 private key로 signature를 만드는 과정입니다. Verification은(는) 메시지, signature, public key로 서명의 유효성을 검사하는 과정입니다. Authenticity / Integrity은(는) 서명은 서명자와 메시지의 진위를 확인하지만 메시지 내용을 숨기는 confidentiality 기능은 아닙니다.

실제 시스템에서는 이렇게 작동합니다. Digital signature는 메시지를 숨기는 기술이 아니라 메시지가 private key 소유자에게서 왔고 중간에 바뀌지 않았음을 검증하는 기술이다. 보통 긴 메시지 자체가 아니라 메시지의 hash에 서명한다. RSA의 단순 교재식 표현에서는 서명 s=h^d mod n을 만들고 검증자는 s^e mod n이 h와 같은지 확인한다.

메시지를 hash해 고정 길이 digest h를 만든다.
서명자는 private key로 h에 대한 signature를 만든다.
검증자는 public key와 원래 메시지로 signature를 확인한다.
Selective forgery에서는 공격 전에 정한 특정 새 메시지에 대한 유효 서명을 만드는 것이 목표다.

여기서 넘지 말아야 할 경계: 서명은 confidentiality를 제공하지 않는다. 또한 교재의 raw RSA 계산은 개념 연습이며 실제로는 안전한 signature encoding이 필요하다.

07. Public key·RSA·ElGamal·Signature 독립 강의 →

QUESTION-BY-QUESTION COMMENTARY

실제 시험 소문제별 해설

시험지의 번호와 순서를 그대로 유지했습니다. 각 항목을 열어 원문 → 쉬운 개념 설명 → 이번 문제의 단계별 풀이 → 답안 → 함정 순서로 읽으세요.

ACTUAL EXAM SUBSECTION 1.3

1.3. Asymmetrische Kryptographie

5개 학습 항목 · 24점

1.3.1 RSA의 보안은 어떤 수학적 Grundlage에 기반하는가? ElGamal의 보안은 어떤 수학적 Grundlage에 기반하는가? 기존 71문항 학습 번호 12 · 2점 단답형

1.3.1 · 실제 시험 원문

1. Auf welcher mathematischen Grundlage beruht die Sicherheit von RSA? Auf welcher mathematischen Grundlage beruht die Sicherheit von ElGamal? **(2 Punkte)**

한국어로 요구사항만 풀어 읽기

RSA의 보안은 어떤 수학적 Grundlage에 기반하는가? ElGamal의 보안은 어떤 수학적 Grundlage에 기반하는가?

공개키 암호와 RSA·ElGamal의 수학적 기반Modulo, 경우의 수, key space를 처음부터 계산하기

TERMS FOR 1.3.1

이 소문제의 중요한 용어부터 이해하기

전문 용어를 알고 있다고 가정하지 않습니다. 아래 정의의 굵은 용어를 문제 문장 속 같은 단어와 바꾸어 읽은 뒤 풀이로 넘어가세요.

01Public key: 누구나 알아도 되는 key로, 보통 encryption 또는 signature verification에 사용됩니다.
02Private key: 소유자만 비밀로 가져야 하는 key로, decryption 또는 signing에 사용됩니다.
03Hard problem: 정상 사용자는 비밀정보로 쉽게 계산하지만 공격자는 현실적 시간에 풀기 어렵다고 가정하는 수학 문제입니다.
04Trapdoor: 특별한 비밀정보를 알면 어려운 계산을 쉽게 뒤집을 수 있게 하는 정보입니다.
05Modulo: 어떤 수를 나눈 나머지만 보는 연산입니다. 시계가 12 다음 1로 돌아가는 것과 비슷합니다.
06Key space: 가능한 모든 key의 집합과 그 개수입니다.
07Entropy: 공격자가 key를 예측하기 어려운 정도를 bit 단위로 나타내는 관점입니다. 단순 길이와 항상 같지는 않습니다.
08Multiplication principle: 독립적으로 고르는 각 자리의 경우의 수를 곱해 전체 경우의 수를 계산하는 원리입니다.

ZERO-BASE MINI LESSON · 1.3.1

이 소문제만을 위한 0부터 시작하는 미니 강의

아래 설명은 이 과목의 선행 지식을 가정하지 않습니다. 개념 → 비유의 대응 → 눈으로 읽는 구조 → 작은 예제 순서로 읽은 뒤 실제 시험 풀이로 넘어가세요.

1 · 먼저 알아야 할 개념

비대칭 암호(asymmetrische Kryptographie)는 서로 연결된 public key와 private key를 쓴다. 누구나 public key로 암호화하거나 서명을 검증할 수 있지만, private key 없이는 복호화하거나 유효한 서명을 만들기 어려워야 한다.

이 설계는 정방향 계산은 빠르지만 결과에서 비밀을 되찾는 역문제는 큰 수에서 계산적으로 어렵다는 가정에 의존한다. ‘어렵다’는 것은 답이 없다는 뜻이 아니라 알려진 알고리즘과 현실적 자원으로 너무 오래 걸린다는 뜻이다.

RSA에서는 서로 다른 큰 소수 p,q를 곱해 n=pq를 공개한다. p,q를 알면 φ(n)=(p−1)(q−1)과 private exponent d=e^−1 mod φ(n)를 계산할 수 있으므로, 큰 n의 인수분해가 어렵다는 가정이 핵심 기반으로 가르쳐진다.

엄밀히 말해 일반적인 RSA 역산 문제가 인수분해와 완전히 동치라고 증명된 것은 아니다. 그러나 n을 factorization하면 개인키를 계산할 수 있으므로 시험의 기대 답은 Faktorisierungsproblem이며, textbook RSA가 IND-CPA 안전하려면 별도의 randomized padding도 필요하다.

ElGamal은 순환군에서 y=g^x를 공개하고 비밀 지수 x를 숨긴다. y에서 x를 찾는 Discrete Logarithm Problem(DLP)이 키 복구의 기반이고, 암호문의 indistinguishability/IND-CPA를 말할 때는 보통 DDH(Decisional Diffie-Hellman) 가정을 사용한다.

2 · 일상 장면으로 먼저 잡기

RSA는 아주 큰 두 톱니바퀴를 곱해 만든 제품 번호만 공개하고 원래 두 부품을 숨기는 금고, ElGamal은 미로에서 앞으로 여러 번 이동한 도착점만 공개하고 몇 번 이동했는지를 숨기는 금고로 생각한다.

두 톱니바퀴를 곱한 제품 번호 RSA modulus n=pq
제품 번호에서 원래 부품 둘 찾기 RSA의 integer factorization problem
시작점 g에서 x번 규칙 이동한 도착점 ElGamal public value y=g^x
도착점에서 이동 횟수 x 찾기 Discrete Logarithm Problem

비유의 경계 작은 숫자의 인수분해와 discrete log는 손으로 풀 수 있다. 비유의 ‘되돌릴 수 없음’은 절대 불가능이 아니라 적절한 군과 충분한 키 크기에서 계산적으로 어렵다는 뜻이다.

3 · 눈으로 관계 읽기 RSA와 ElGamal의 어려운 역문제

01 RSA 정방향
p,q → n=pq는 빠름
02 RSA 역방향
큰 n → p,q factorization이 어려움
03 ElGamal 정방향
x → y=g^x in group은 빠름
04 ElGamal 역방향
g,y → x discrete logarithm이 어려움
05 ElGamal IND-CPA
DH tuple을 구별하기 어렵다는 DDH 가정

각 알고리즘의 쉬운 공개키 생성 방향과 어려워야 하는 비밀 복구 방향을 한 쌍씩 읽는다.

4 · TOY EXAMPLE

작은 RSA와 ElGamal에서 역문제 보기

주어진 것과 목표 RSA에는 n=15, ElGamal 장난감 군에는 modulus 23, generator 후보 g=5, 공개값 y=8을 사용한다. 목표는 작은 수에서 두 역문제가 무엇인지 확인하는 것이다.

01

n=15를 작은 소수로 나눈다.

왜? RSA에서 공개 modulus를 factorization하는 역문제를 직접 보기 위해서다.

중간 결과 15=3×5이므로 p=3, q=5를 복구한다.
02

인수로 φ(15)를 계산한다.

왜? factorization이 private exponent 계산으로 어떻게 이어지는지 보기 위해서다.

중간 결과 φ(15)=(3−1)(5−1)=8; 공개 e가 3이면 inverse d도 3이다. 3×3=9≡1 mod 8이다.
03

ElGamal 쪽에서 5의 작은 거듭제곱을 modulo 23으로 계산한다.

왜? 공개값 y=8을 만든 비밀 지수를 작은 예제에서 찾기 위해서다.

중간 결과 5^2=2, 5^3=10, 5^4=4, 5^5=20, 5^6=8 (mod 23)이므로 x=6이다.
04

작은 예제와 실제 키 크기를 비교한다.

왜? 보안이 연산 불가능이 아니라 규모에 따른 계산 난이도라는 점을 확인하기 위해서다.

중간 결과 15와 23에서는 쉽게 풀리지만 실제 큰 n과 적절한 군에서는 알려진 최선 알고리즘으로 역문제가 어렵도록 매개변수를 고른다.

예제 결론 RSA는 공개된 곱에서 소인수를 되찾는 문제, ElGamal은 공개된 군 거듭제곱에서 비밀 지수를 되찾거나 DH 관계를 구별하는 문제에 기대어 비밀키를 숨긴다.

실제 시험으로 옮기기 2점 답안은 RSA: Faktorisierungsproblem, ElGamal: diskretes Logarithmusproblem을 정확히 짝짓고, 여유가 있으면 ElGamal IND-CPA에는 DDH를 덧붙인다.

이번 문제는 이 단계로 풀어야 했습니다

먼저 문제에서 직접 주어진 값과 최종적으로 구할 값을 분리합니다. 그다음 각 값·용어·경로를 왜 선택했는지 확인하며, 앞 단계의 중간 결과를 다음 단계의 입력으로 사용합니다.

START HERE

먼저 문제를 식과 조건으로 정리하기

계산을 시작하기 전에 주어진 것과 구할 것을 분리합니다. 그다음 아래 관계식을 위에서 아래로 사용하면, 숫자가 어디서 왔는지 놓치지 않을 수 있습니다.

강사가 문제의 요구사항을 쉬운 말로 바꾸면

시험 문장이 요구하는 것: RSA의 보안은 어떤 수학적 Grundlage에 기반하는가? ElGamal의 보안은 어떤 수학적 Grundlage에 기반하는가?

이 문제의 풀이 전략: 이 소문제에서는 RSA 구조 회상 → RSA 기반 명명 → ElGamal 구조 회상 → ElGamal 기반 명명 → 두 답 짝짓기 순서로 진행합니다. 마지막에는 ‘RSA는 `n=pq`의 factorization, ElGamal은 군에서 `g^x`의 discrete logarithm 및 IND-CPA 맥락의 DDH를 기반으로 한다.’라는 교정 기준으로 답을 다시 확인합니다.

문제에서 주어진 정보

실제 시험이 준 상황·문장
RSA의 보안은 어떤 수학적 Grundlage에 기반하는가? ElGamal의 보안은 어떤 수학적 Grundlage에 기반하는가?
이 문항의 첫 출발점
RSA 공개 modulus는 서로 다른 큰 소수의 곱 `n=pq`이고, p,q를 알면 φ(n)과 d를 계산할 수 있다.

RSA에 discrete logarithm을 배정하지 않는다.

최종적으로 구해야 하는 것

마지막에 도달할 답안
RSA→factorization, ElGamal→discrete logarithm(IND-CPA: DDH) 순서로 쓴다.
정답을 지탱하는 이유
RSA는 큰 `n=pq`를 인수분해해 p,q를 찾기 어렵다는 가정에 기반하며, 인수를 알면 φ(n)과 private exponent d를 계산할 수 있다. 시험 답안에서는 이를 `Faktorisierungsproblem`이라고 쓴다. ElGamal의 비밀키 복구는 사용한 군의 `diskretes Logarithmusproblem`이 어렵다는 데 기대고, 암호문의 IND-CPA 보안은 보통 DDH 가정으로 설명한다. 단, factorization hardness만으로 padding 없는 textbook RSA의 모든 보안 성질이 자동 보장되는 것은 아니다.

사용할 공식·판정 관계

이 소문제만의 풀이 사슬
RSA 구조 회상 → RSA 기반 명명 → ElGamal 구조 회상 → ElGamal 기반 명명 → 두 답 짝짓기

각 알고리즘의 쉬운 공개키 생성 방향과 어려워야 하는 비밀 복구 방향을 한 쌍씩 읽는다.

01

RSA 구조 회상

구체적으로 RSA 공개 modulus는 서로 다른 큰 소수의 곱 n=pq이고, p,q를 알면 φ(n)과 d를 계산할 수 있다.

여기서 검산 RSA에 discrete logarithm을 배정하지 않는다.

다음 단계로 여기서 확인한 내용을 다음 ‘RSA 기반 명명’ 단계의 출발점으로 사용합니다.
02

RSA 기반 명명

구체적으로 시험 기대 용어는 큰 합성수 n의 Faktorisierungsproblem이다.

여기서 검산 ‘큰 소수 찾기’가 아니라 이미 공개된 합성수의 소인수 찾기라고 쓴다.

다음 단계로 여기서 확인한 내용을 다음 ‘ElGamal 구조 회상’ 단계의 출발점으로 사용합니다.
03

ElGamal 구조 회상

구체적으로 ElGamal은 군에서 공개값 y=g^x와 비밀 지수 x를 사용한다.

여기서 검산 연산 공간이 일반 정수가 아니라 선택한 cyclic group임을 확인한다.

다음 단계로 여기서 확인한 내용을 다음 ‘ElGamal 기반 명명’ 단계의 출발점으로 사용합니다.
04

ElGamal 기반 명명

구체적으로 키 복구 관점은 diskretes Logarithmusproblem, semantic/IND-CPA 보안은 보통 DDH hardness에 기반한다.

여기서 검산 DLP와 DDH의 역할 차이를 과도하게 섞지 않는다.

다음 단계로 여기서 확인한 내용을 다음 ‘두 답 짝짓기’ 단계의 출발점으로 사용합니다.
05

두 답 짝짓기

구체적으로 RSA→factorization, ElGamal→discrete logarithm(IND-CPA: DDH) 순서로 쓴다.

여기서 검산 두 알고리즘의 근거를 서로 바꾸지 않았는지 마지막으로 확인한다.

다음 단계로 앞 단계의 결과를 모아 채점 가능한 최종 답안으로 정리합니다.

정답과 해설

RSA: Faktorisierungsproblem / φ(n) 계산 난이도. ElGamal: diskreter Logarithmus, semantic security는 DDH hardness.

정답이 이렇게 되는 이유

RSA는 큰 n=pq를 인수분해해 p,q를 찾기 어렵다는 가정에 기반하며, 인수를 알면 φ(n)과 private exponent d를 계산할 수 있다. 시험 답안에서는 이를 Faktorisierungsproblem이라고 쓴다. ElGamal의 비밀키 복구는 사용한 군의 diskretes Logarithmusproblem이 어렵다는 데 기대고, 암호문의 IND-CPA 보안은 보통 DDH 가정으로 설명한다. 단, factorization hardness만으로 padding 없는 textbook RSA의 모든 보안 성질이 자동 보장되는 것은 아니다.

초보자가 가장 자주 뒤집는 지점

잘못된 생각 RSA와 ElGamal은 둘 다 큰 소수를 사용하므로 둘 다 소인수분해 난이도에 기반한다.

왜 틀렸나 매개변수에 소수나 modulo가 등장한다는 표면만 보고 실제로 숨기는 역문제를 구분하지 않았다.

고쳐 말하면 RSA는 n=pq의 factorization, ElGamal은 군에서 g^x의 discrete logarithm 및 IND-CPA 맥락의 DDH를 기반으로 한다.

한 문제만 더: 개념이 정말 연결됐는지 확인

질문 공격자가 RSA modulus n의 소인수 p,q를 알아냈다. 공개 e로 private exponent d를 어떻게 이어서 구하는가?

정답 φ(n)=(p−1)(q−1)을 계산한 뒤 ed≡1 mod φ(n)을 만족하는 modular inverse d=e^−1 mod φ(n)을 구한다.

이 문제의 오답 함정

RSA를 discrete logarithm 기반이라고 쓰기
ElGamal의 probabilistic encryption과 hard problem을 분리하지 못하기

ACTIVE RECALL

이 소문제를 점수로 바꾸는 6개의 작은 훈련

해설을 닫은 상태에서 1번부터 수행하세요. 정답을 읽은 직후보다 직접 문제 지도를 만들고 답을 꺼낸 뒤 채점할 때 기억이 더 정확해집니다. 작성 내용과 복습 판정은 이 브라우저에 자동 저장됩니다.

01 · 30초 문제 지도
해설을 보지 말고 주어진 정보 → 구할 것 → 사용할 공식·판정 관계를 한 줄씩 복원하세요.

막힐 때만 첫 단서 열기

RSA public key의 n에서 숨겨진 값은 무엇이고, ElGamal public key A = g^a에서 숨겨진 값은 무엇인가?
02 · 90초 닫힌책 답안
RSA의 보안은 어떤 수학적 Grundlage에 기반하는가? ElGamal의 보안은 어떤 수학적 Grundlage에 기반하는가?

정답 문장만 말하지 말고 근거·중간값·메시지 흐름 중 이 문항에 필요한 것을 빈 종이에 남기세요.
03 · 부분점수 자가채점
작성한 뒤에만 아래 기준을 열고, 실제로 쓴 항목만 체크하세요.

답안 작성 후 채점 기준 열기

답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.

RSA는 factoring n 또는 φ(n) 계산 난이도에 기반한다고 쓴다. ElGamal은 discrete logarithm problem에 기반한다고 쓴다. semantic security를 묻는 맥락이면 DDH hardness도 언급한다. 두 scheme의 근거를 서로 바꾸지 않는다.

0/4 slots
04 · 문항별 후속 질문·조건 전이
- p, q, φ(n)을 알면 RSA private key d를 어떻게 구하는가?
- ElGamal에서 public key A = g^a를 보고 a를 찾는 문제의 이름은 무엇인가?
- 정답의 핵심 조건 하나를 일부러 빼고 생기는 잘못된 결론을 쓴 뒤, 그 조건을 다시 넣어 시험 답안 한 문장으로 복구하세요.
조건 변형: 원문의 핵심 조건 하나를 반대로 바꾸고, 기존 정답에서 어느 문장과 근거를 수정해야 하는지 두 문장으로 설명하세요.
05 · 대표 오답 복구
고칠 답안: RSA를 discrete logarithm 기반이라고 쓰기

복구 힌트: RSA public key의 n에서 숨겨진 값은 무엇이고, ElGamal public key A = g^a에서 숨겨진 값은 무엇인가?

오답의 첫 잘못된 전제를 한 줄로 지우고, 올바른 조건과 결론을 두 줄로 다시 쓰세요.
06 · 확신도 보정·다음 복습 결정
채점 전 예상과 실제 채점 결과가 달랐는지 확인한 뒤 상태를 남기세요. ‘숙달’은 근거와 중간 과정까지 무힌트로 재현했을 때만 선택합니다.

현재 확신도 낮음 보통 높음

아직 복습 판정을 남기지 않았습니다.

모든 훈련을 마친 뒤 핵심 정답 다시 확인

RSA: Faktorisierungsproblem / φ(n) 계산 난이도. ElGamal: diskreter Logarithmus, semantic security는 DDH hardness.

1.3.2 digital signatures 문맥에서 Selective-Forgery-Under-Chosen-Message-Angriff를 설명하라. 기존 71문항 학습 번호 13 · 4점 단답형

1.3.2 · 실제 시험 원문

2. Beschreiben Sie einen Selective-Forgery-Under-Chosen-Message-Angriff im Kontext von digitalen Signaturen. **(4 Punkte)**

한국어로 요구사항만 풀어 읽기

digital signatures 문맥에서 Selective-Forgery-Under-Chosen-Message-Angriff를 설명하라.

Digital signature는 무엇을 증명하는가공격자 모델과 oracle을 게임처럼 읽는 법Hash는 암호화가 아니라 고정 길이 지문이다

TERMS FOR 1.3.2

이 소문제의 중요한 용어부터 이해하기

전문 용어를 알고 있다고 가정하지 않습니다. 아래 정의의 굵은 용어를 문제 문장 속 같은 단어와 바꾸어 읽은 뒤 풀이로 넘어가세요.

01GET

HTTP request method 중 하나로 parameter가 흔히 URL query string에 들어갑니다.

작은 예: Login을 GET으로 보내면 ?user=alice&pw=secret이 history나 log에 남을 수 있습니다.

02Digital signature

private key 소유자가 특정 메시지에 서명했음을 검증하게 하는 값입니다.

03Signing

메시지와 private key로 signature를 만드는 과정입니다.

04Verification

메시지, signature, public key로 서명의 유효성을 검사하는 과정입니다.

05Authenticity / Integrity

서명은 서명자와 메시지의 진위를 확인하지만 메시지 내용을 숨기는 confidentiality 기능은 아닙니다.

06Attacker model

공격자가 무엇을 보고, 선택하고, 질문하고, 바꿀 수 있는지를 정확히 정한 가정입니다.

07Oracle

보안 게임에서 공격자가 정해진 형식으로 질의하고 답을 받을 수 있는 가상 인터페이스입니다.

08Challenge

공격자가 구별하거나 위조해야 하는 중심 시험값입니다.

ZERO-BASE MINI LESSON · 1.3.2

이 소문제만을 위한 0부터 시작하는 미니 강의

1 · 먼저 알아야 할 개념

디지털 서명은 메시지를 숨기는 암호화가 아니라 누가 승인했는지(authenticity)와 내용이 바뀌지 않았는지(integrity)를 검증하는 장치다. 서명자는 private signing key로 Sign(sk,m)을 계산하고 누구나 public verification key로 Verify(pk,m,σ)를 검사한다.

Signing oracle은 공격자가 선택한 메시지를 제출하면 정상 서명을 돌려주는 검은 상자다. 현실에서는 사용자가 지정한 문서에 서명하는 스마트카드나 서명 API가 이 권한과 비슷할 수 있다.

Chosen-Message Attack(CMA)은 공격자가 분석에 도움이 되도록 메시지들을 골라 그 서명을 얻을 수 있다는 뜻이다. 안전한 서명은 많은 정상 서명을 보여 줘도 질의하지 않은 메시지의 새 유효 서명을 만들기 어려워야 한다.

Selective Forgery에서는 공격자가 공격 시작 전에 특정 목표 메시지 m*를 정한다. oracle 답을 본 뒤 아무 쉬운 메시지로 목표를 바꾸는 existential forgery보다 목표 선택이 제한된 개념이다.

공격 성공은 target m*를 signing oracle에 질의하지 않았는데도 Verify(pk,m*,σ*)=accept인 서명 σ*를 출력하는 것이다. 이미 oracle에서 받은 동일한 (m*,σ*)를 재생하는 것은 위조가 아니다.

2 · 일상 장면으로 먼저 잡기

공격자가 ‘999유로 송금’이라는 위조 목표 문서를 미리 적어 두고, 공증인에게 다른 소액 문서들을 골라 진짜 도장을 받아 관찰한 뒤 목표 문서에 통과하는 가짜 도장을 만드는 장면을 생각한다.

공격 전 적어 둔 999유로 문서 사전에 고정한 selective target message m*
다른 문서에 진짜 도장을 요청 chosen-message signing oracle queries
목표 문서에 새로 만든 도장 forged signature σ*
공증 검사가 도장을 진짜로 인정 Verify(pk,m*,σ*)=accept

비유의 경계 물리 도장은 모양 복사로 설명되지만 안전한 디지털 서명은 단순 이미지 복제가 아니며 메시지 전체와 수학적으로 연결된다. 비유는 질의 권한과 성공 조건만 보여 준다.

3 · 눈으로 관계 읽기 Selective Forgery 게임

01 1. Target
공격 전에 m* 고정
02 2. 학습
다른 mi → signing oracle → σi
03 3. 금지
m* 자체의 서명을 oracle에서 받지 않음
04 4. 위조
새 σ* 출력
05 5. 승리
Verify(pk,m*,σ*)=accept

target 선택이 oracle 학습보다 앞에 있고, target이 query 목록에 없어야 마지막 accept가 위조 성공이 된다.

4 · TOY EXAMPLE

사전 목표 송금 지시 위조 게임

주어진 것과 목표 공격자가 시작 전에 m*='PAY BOB 999'를 목표로 정한다. signing oracle에는 다른 메시지를 물어볼 수 있으며 목표는 유효한 σ*를 만드는 것이다.

01

공격자가 oracle 사용 전에 목표 m*='PAY BOB 999'를 선언한다.

왜? Selective라는 제한은 목표가 학습 결과보다 먼저 고정됨을 요구하기 때문이다.

중간 결과 나중에 더 쉬운 메시지로 target을 바꿀 수 없다.
02

'PAY BOB 10'과 'PAY ALICE 20'의 서명을 oracle에 요청한다.

왜? Chosen-Message Attack은 공격자가 학습용 메시지를 직접 선택하도록 허용하기 때문이다.

중간 결과 두 정상 서명 σ1,σ2를 얻지만 target 자체의 서명은 얻지 않는다.
03

관찰한 자료로 target에 대한 새 값 σ*를 계산해 출력한다.

왜? 공격 목적은 private key를 반드시 출력하는 것이 아니라 유효한 위조 하나를 만드는 것이기 때문이다.

중간 결과 아직 성공 여부는 public verification으로 판정한다.
04

Verify(pk,'PAY BOB 999',σ*)를 실행하고 query 목록을 확인한다.

왜? 유효성뿐 아니라 target이 이전에 서명 요청되지 않았다는 비자명성도 필요하기 때문이다.

중간 결과 검증이 accept이고 target이 미질의였다면 selective forgery에 성공한다.

예제 결론 미리 정한 target에 대해, 다른 선택 메시지들의 정상 서명을 이용하고도 새 유효 서명을 만들면 위조 성공이다.

실제 시험으로 옮기기 4점 답안에는 ‘target 사전 고정’, ‘chosen messages의 signing oracle’, ‘target 미질의’, ‘Verify accept’를 순서대로 쓴다.

이번 문제는 이 단계로 풀어야 했습니다

START HERE

먼저 문제를 식과 조건으로 정리하기

강사가 문제의 요구사항을 쉬운 말로 바꾸면

시험 문장이 요구하는 것: digital signatures 문맥에서 Selective-Forgery-Under-Chosen-Message-Angriff를 설명하라.

이 문제의 풀이 전략: 이 소문제에서는 보안 대상 명시 → Selective 조건 → Chosen-Message 권한 → 비자명성 조건 → 승리 조건 순서로 진행합니다. 마지막에는 ‘target `m*`는 signing oracle에 질의하지 않아야 하며 공격자가 새로 만든 `σ*`가 검증을 통과해야 한다.’라는 교정 기준으로 답을 다시 확인합니다.

문제에서 주어진 정보

실제 시험이 준 상황·문장
digital signatures 문맥에서 Selective-Forgery-Under-Chosen-Message-Angriff를 설명하라.
이 문항의 첫 출발점
디지털 서명의 unforgeability를 공격하는 상황이며 메시지 기밀성을 묻는 문제가 아니다.

서명과 암호화를 같은 기능으로 설명하지 않는다.

최종적으로 구해야 하는 것

마지막에 도달할 답안
private key 없이 만든 `σ*`가 `Verify(pk,m*,σ*)=accept`이면 성공한다.
정답을 지탱하는 이유
Selective Forgery under Chosen-Message Attack에서 공격자는 먼저 목표 메시지 `m*`를 고정한다. 그는 다른 선택 메시지들에 대해서는 signing oracle에서 정상 서명을 받아 분석할 수 있다. 이후 `m*`를 oracle에 질의한 적 없이 `Verify(pk,m*,σ*)=accept`인 새 서명을 출력하면 성공한다. 이는 디지털 서명의 authenticity, integrity, unforgeability를 깨는 공격이다.

사용할 공식·판정 관계

이 소문제만의 풀이 사슬
보안 대상 명시 → Selective 조건 → Chosen-Message 권한 → 비자명성 조건 → 승리 조건

target 선택이 oracle 학습보다 앞에 있고, target이 query 목록에 없어야 마지막 accept가 위조 성공이 된다.

01

보안 대상 명시

구체적으로 디지털 서명의 unforgeability를 공격하는 상황이며 메시지 기밀성을 묻는 문제가 아니다.

여기서 검산 서명과 암호화를 같은 기능으로 설명하지 않는다.

다음 단계로 여기서 확인한 내용을 다음 ‘Selective 조건’ 단계의 출발점으로 사용합니다.
02

Selective 조건

구체적으로 공격자는 목표 메시지 m*를 공격 시작 전, oracle 답을 보기 전에 정한다.

여기서 검산 마지막에 아무 메시지나 고르는 existential forgery와 구분한다.

다음 단계로 여기서 확인한 내용을 다음 ‘Chosen-Message 권한’ 단계의 출발점으로 사용합니다.
03

Chosen-Message 권한

구체적으로 공격자는 자신이 고른 다른 메시지들의 정상 서명을 signing oracle에서 얻는다.

여기서 검산 oracle이 encryption이나 decryption oracle이 아니라 signing oracle인지 확인한다.

다음 단계로 여기서 확인한 내용을 다음 ‘비자명성 조건’ 단계의 출발점으로 사용합니다.
04

비자명성 조건

구체적으로 target m* 자체를 서명 질의해 받은 값을 그대로 제출하면 위조가 아니다.

여기서 검산 target이 query set에 없다고 명시한다.

다음 단계로 여기서 확인한 내용을 다음 ‘승리 조건’ 단계의 출발점으로 사용합니다.
05

승리 조건

구체적으로 private key 없이 만든 σ*가 Verify(pk,m*,σ*)=accept이면 성공한다.

여기서 검산 새 서명의 유효성 검사를 수식이나 문장으로 포함한다.

다음 단계로 앞 단계의 결과를 모아 채점 가능한 최종 답안으로 정리합니다.

정답과 해설

공격자는 chosen messages에 대한 signatures를 받을 수 있고, 사전에 정한 target message에 대해 새 valid signature를 위조하면 성공한다.

정답이 이렇게 되는 이유

Selective Forgery under Chosen-Message Attack에서 공격자는 먼저 목표 메시지 m*를 고정한다. 그는 다른 선택 메시지들에 대해서는 signing oracle에서 정상 서명을 받아 분석할 수 있다. 이후 m*를 oracle에 질의한 적 없이 Verify(pk,m*,σ*)=accept인 새 서명을 출력하면 성공한다. 이는 디지털 서명의 authenticity, integrity, unforgeability를 깨는 공격이다.

초보자가 가장 자주 뒤집는 지점

잘못된 생각 공격자가 목표 메시지의 정상 서명을 signing oracle에서 받은 뒤 그대로 다시 내도 selective forgery다.

왜 틀렸나 그 행동은 이미 받은 유효 서명의 replay일 뿐 새 메시지에 대한 서명 능력을 보여 주지 않는다.

고쳐 말하면 target m*는 signing oracle에 질의하지 않아야 하며 공격자가 새로 만든 σ*가 검증을 통과해야 한다.

한 문제만 더: 개념이 정말 연결됐는지 확인

질문 공격자가 oracle 답을 모두 본 뒤 그중 가장 위조하기 쉬운 새 메시지를 골랐다. target을 공격 전에 고정하지 않았다면 ‘selective’ 조건을 만족하는가?

정답 아니다. 이는 target을 사전에 고정하는 selective 조건과 다르며, 목표를 나중에 고를 수 있는 existential forgery 쪽의 능력이다.

이 문제의 오답 함정

Existential Forgery와 Selective Forgery를 구분하지 않기
이미 oracle에 요청한 target signature를 그대로 제출해도 된다고 쓰기

ACTIVE RECALL

이 소문제를 점수로 바꾸는 6개의 작은 훈련

01 · 30초 문제 지도
해설을 보지 말고 주어진 정보 → 구할 것 → 사용할 공식·판정 관계를 한 줄씩 복원하세요.

막힐 때만 첫 단서 열기

두 부분으로 나눠라: 공격자가 무엇을 받을 수 있는가, 무엇을 만들어야 성공인가?
02 · 90초 닫힌책 답안
digital signatures 문맥에서 Selective-Forgery-Under-Chosen-Message-Angriff를 설명하라.

정답 문장만 말하지 말고 근거·중간값·메시지 흐름 중 이 문항에 필요한 것을 빈 종이에 남기세요.
03 · 부분점수 자가채점
작성한 뒤에만 아래 기준을 열고, 실제로 쓴 항목만 체크하세요.

답안 작성 후 채점 기준 열기

답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.

Chosen Message Attack: 선택 메시지에 대한 signature를 받을 수 있음을 쓴다. Selective Forgery: target/new message가 공격 전에 정해져 있음을 쓴다. Forgery는 target에 대한 valid signature이며 trivial replay가 아니어야 한다. 위반되는 목표가 authenticity/integrity/unforgeability임을 언급한다.

0/4 slots
04 · 문항별 후속 질문·조건 전이
- Existential Forgery와 Selective Forgery의 target message 조건 차이는 무엇인가?
- Adaptive Chosen Message Attack은 ordinary Chosen Message Attack보다 무엇이 강한가?
- 정답의 핵심 조건 하나를 일부러 빼고 생기는 잘못된 결론을 쓴 뒤, 그 조건을 다시 넣어 시험 답안 한 문장으로 복구하세요.
조건 변형: 원문의 핵심 조건 하나를 반대로 바꾸고, 기존 정답에서 어느 문장과 근거를 수정해야 하는지 두 문장으로 설명하세요.
05 · 대표 오답 복구
고칠 답안: Existential Forgery와 Selective Forgery를 구분하지 않기

복구 힌트: 두 부분으로 나눠라: 공격자가 무엇을 받을 수 있는가, 무엇을 만들어야 성공인가?

오답의 첫 잘못된 전제를 한 줄로 지우고, 올바른 조건과 결론을 두 줄로 다시 쓰세요.
06 · 확신도 보정·다음 복습 결정
채점 전 예상과 실제 채점 결과가 달랐는지 확인한 뒤 상태를 남기세요. ‘숙달’은 근거와 중간 과정까지 무힌트로 재현했을 때만 선택합니다.

현재 확신도 낮음 보통 높음

아직 복습 판정을 남기지 않았습니다.

모든 훈련을 마친 뒤 핵심 정답 다시 확인

공격자는 chosen messages에 대한 signatures를 받을 수 있고, 사전에 정한 target message에 대해 새 valid signature를 위조하면 성공한다.

1.3.3 p = 7, q = 7인 RSA에서 gültiges Schlüsselpaar ((e,n),(d,n))를 구하라. 풀이 과정 없이 n, φ(n), e, d만 쓰며 e=1,d=1은 제외한다. 기존 71문항 학습 번호 14 · 8점 계산

1.3.3 · 실제 시험 원문

3. Bestimmen Sie ein gültiges Schlüsselpaar $((e,n),(d,n))$ für das RSA Kryptosystem mit den Parametern $p = 7$ und $q = 7$. Sie müssen keinen Rechenweg angeben sondern nur Ihre Ergebnisse für $n$, $\varphi(n)$, $e$ und $d$. Die Werte $e = 1$, $d = 1$ sind hierbei ausgeschlossen! **(8 Punkte)**

```text
n = __________
φ(n) = ________
e = __________
d = __________
```

한국어로 요구사항만 풀어 읽기

p = 7, q = 7인 RSA에서 gültiges Schlüsselpaar ((e,n),(d,n))를 구하라. 풀이 과정 없이 n, φ(n), e, d만 쓰며 e=1,d=1은 제외한다.

암호화의 가장 기본적인 등장인물RSA 계산에 필요한 소수·φ·서로소·역원Modulo, 경우의 수, key space를 처음부터 계산하기

TERMS FOR 1.3.3

이 소문제의 중요한 용어부터 이해하기

전문 용어를 알고 있다고 가정하지 않습니다. 아래 정의의 굵은 용어를 문제 문장 속 같은 단어와 바꾸어 읽은 뒤 풀이로 넘어가세요.

01Plaintext: 암호화하기 전의 원래 메시지입니다. 사람이 읽는 문장뿐 아니라 파일의 byte도 plaintext가 될 수 있습니다.
02Ciphertext: 암호화 결과입니다. 숨겨진 원문과 같은 말이 아니라, key 없이는 원문을 알아내기 어려워야 하는 출력입니다.
03Key: 암호 알고리즘의 동작을 결정하는 값입니다. 알고리즘 자체가 아니라 key를 비밀로 관리하는 것이 현대 암호의 기본입니다.
04Encryption / Decryption: Encryption은 plaintext를 ciphertext로, decryption은 올바른 key로 ciphertext를 다시 plaintext로 바꾸는 과정입니다.
05Prime number: 1과 자기 자신으로만 나누어지는 1보다 큰 정수입니다.
06Euler φ function: n 이하에서 n과 서로소인 수의 개수를 나타내며 RSA key 계산에 사용됩니다.
07Coprime: 두 수의 최대공약수가 1인 관계입니다.
08Modular inverse: `a·b ≡ 1 (mod n)`을 만족하는 b로, modulo 세계에서 나눗셈 역할을 합니다.

ZERO-BASE MINI LESSON · 1.3.3

이 소문제만을 위한 0부터 시작하는 미니 강의

1 · 먼저 알아야 할 개념

표준 RSA 키 생성은 서로 다른 두 소수 p≠q를 고르고 n=pq를 만든다. 공개키는 (e,n), 개인키는 (d,n)이며 e와 d는 정해진 modulo 공간에서 서로 역원이어야 한다.

Euler의 φ 함수 φ(n)은 1부터 n−1 중 n과 서로소인 수의 개수다. 서로 다른 소수의 곱이면 φ(pq)=(p−1)(q−1)이지만, 같은 소수가 반복된 p^2이면 φ(p^2)=p^2−p=p(p−1)이다.

공개 지수 e는 gcd(e,φ(n))=1을 만족해야 modular inverse가 존재한다. 개인 지수 d는 ed≡1 mod φ(n)을 만족하는 e^−1이며, ed=1+kφ(n) 형태로 작은 k를 시험해 찾을 수 있다.

이 시험은 비표준적으로 p=q=7을 준다. 조건부 산술값은 n=49, φ(49)=42이며 e=5를 고르면 d=17이지만, p와 q가 같으면 textbook RSA 변환이 전체 메시지 공간에서 올바른 permutation이 되지 않는다.

따라서 초보자는 두 층을 함께 알아야 한다. 답안 칸의 의도된 계산값은 (49,42,5,17)이고 5×17=85≡1 mod 42이지만, 엄밀한 표준 RSA의 ‘gültiges Schlüsselpaar’은 p≠q 위반 때문에 존재하지 않는다는 경고를 옆에 적는 것이 정확하다.

2 · 일상 장면으로 먼저 잡기

서로 다른 두 자물쇠 톱니를 맞물리도록 설계된 기계에 같은 톱니를 두 번 복제해 넣은 장면을 생각한다. 숫자표의 역원 조건은 맞출 수 있어도 특정 물건은 기계 안에서 뭉개져 원상복구되지 않는다.

서로 다른 두 톱니 표준 RSA가 요구하는 distinct primes p와 q
같은 톱니 두 개를 복제 시험의 비표준 조건 p=q=7
숫자표에서 맞는 회전 횟수 ed≡1 mod φ(49)을 만족하는 e=5,d=17
특정 물건이 0 모양으로 뭉개짐 7의 배수 같은 non-unit 메시지가 암호화 후 0이 되어 복구 실패

비유의 경계 RSA의 실제 correctness는 기계 톱니보다 modular arithmetic과 중국인의 나머지 정리에 따른다. 비유는 역원 식 하나를 맞춘 것만으로 비표준 p=q가 완전한 RSA가 되지는 않음을 보여 준다.

3 · 눈으로 관계 읽기 p=q=7 조건부 계산과 엄밀한 경고

01 Modulus
n=7^2=49
02 Totient
φ(7^2)=49−7=42, 36이 아님
03 지수
e=5, d=17, 5×17=85=2×42+1
04 표준 조건
p≠q 위반
05 반례
m=7 → 7^5 mod49=0 → 0^17=0≠7

위 세 행은 시험 칸의 산술값이고, 아래 두 행은 그 값을 표준 RSA 전체에 그대로 ‘유효’라고 부를 수 없는 이유다.

4 · TOY EXAMPLE

시험과 다른 `p=q=5`로 같은 함정 확인

주어진 것과 목표 장난감 조건 p=q=5에서 조건부로 n, φ(n), e, d를 구하고 메시지 m=5가 복구되는지 검사한다.

01

n=5×5와 prime-power totient를 계산한다.

왜? 같은 소수가 반복될 때 (p−1)(q−1) 공식을 그대로 쓰면 안 되기 때문이다.

중간 결과 n=25, φ(25)=25−5=20이다.
02

20과 서로소인 작은 e=3을 고르고 inverse d를 찾는다.

왜? 공개 지수와 개인 지수의 조건부 산술 관계를 만들기 위해서다.

중간 결과 3×7=21≡1 mod 20이므로 d=7이다.
03

메시지 m=5를 e=3으로 암호화한다.

왜? φ 역원 조건이 전체 메시지 공간의 correctness를 보장하는지 검증하기 위해서다.

중간 결과 c=5^3 mod 25=125 mod 25=0이다.
04

c=0을 d=7로 복호화한다.

왜? 원래 메시지로 돌아오는지 확인해야 ‘유효한 RSA’라고 할 수 있기 때문이다.

중간 결과 0^7 mod 25=0≠5; p=q 때문에 전체 공간에서 복구가 실패한다.

예제 결론 p=q에서도 φ와 역원 숫자는 계산할 수 있지만, 그것만으로 표준 RSA 전체 메시지 공간의 유효한 키 쌍이 되지는 않는다.

실제 시험으로 옮기기 실제 p=q=7에서는 의도된 칸을 n=49, φ=42, e=5, d=17로 채우고 가능하면 p=q violates standard RSA; valid only conditionally/on units라고 덧붙인다.

BEGINNER SHORTCUT · RSA KEY SELECTION

e와 d를 시험장에서 쉽게 고르는 방법

주의: 표준 RSA는 서로 다른 소수 p≠q를 요구하므로 p=q=7은 비표준 조건이다. 아래 방법은 시험 칸에 요구된 조건부 산술값 e와 d를 쉽게 고르는 방법이다. e와 d를 무작정 추측하지 말고, e는 φ(n)과 공약수가 없는 작은 수로 고른 뒤 d는 1+φ(n)·k를 e로 나누어 찾으면 된다.

1. φ(n)의 소인수만 표시한다

φ(n)=42=2×3×7이다. 따라서 e가 2, 3, 7 중 하나로 나누어지면 gcd(e,42)≠1이므로 사용할 수 없다.
2. 작은 후보부터 e를 고른다

e=2,3,4는 42와 공약수가 있다. e=5는 2·3·7 어느 것으로도 나누어지지 않으므로 gcd(5,42)=1이다. 따라서 e=5가 빠르고 안전한 선택이다.
3. d를 1+42k 방식으로 찾는다

ed≡1 (mod 42)는 ed=1+42k라는 뜻이다. e=5를 넣으면 d=(1+42k)/5이다. k=1이면 43/5라서 정수가 아니고, k=2이면 85/5=17이므로 d=17이다.
4. 곱셈 한 번으로 검산한다

5×17=85이고 85를 42로 나누면 나머지가 1이다. 따라서 e=5와 d=17은 올바른 inverse 관계다.

e 후보를 작은 수부터 검사

e=2	42와 공약수 2가 있으므로 불가
e=3	42와 공약수 3이 있으므로 불가
e=4	42와 공약수 2가 있으므로 불가
e=5	gcd(5,42)=1이므로 선택

d를 찾는 k 대입

k=1	1+42=43, 5로 나누어지지 않음
k=2	1+84=85, 85÷5=17 → d=17

암기 문장: 먼저 p≠q 확인. 조건부 계산에서는 e는 φ와 겹치지 않는 작은 수, d는 ‘φ의 배수 + 1’을 e로 나눈 값.

이번 문제는 이 단계로 풀어야 했습니다

START HERE

먼저 문제를 식과 조건으로 정리하기

강사가 문제의 요구사항을 쉬운 말로 바꾸면

시험 문장이 요구하는 것: p = 7, q = 7인 RSA에서 gültiges Schlüsselpaar ((e,n),(d,n))를 구하라. 풀이 과정 없이 n, φ(n), e, d만 쓰며 e=1,d=1은 제외한다.

이 문제의 풀이 전략: 이 소문제에서는 중복 소수 확인 → n 계산 → φ 계산 → e 선택 → d 계산 → 유효성 한계 명시 순서로 진행합니다. 마지막에는 ‘`φ(7^2)=7^2−7=42`; e=5,d=17은 modulo 42 역원이지만 p=q라서 표준 RSA 유효성에는 별도 문제가 있다.’라는 교정 기준으로 답을 다시 확인합니다.

문제에서 주어진 정보

Prime 입력 $p=7,\quad q=7$
제외 조건 $e\neq1,\quad d\neq1$
주의
표준 RSA는 p≠q를 요구한다. 아래 값은 시험 칸에 맞춘 prime-square 조건부 산술이다.

최종적으로 구해야 하는 것

먼저 구할 값 $n,\quad \varphi(n)$
그다음 구할 값 $e,\quad d$
최종 검산 $ed\equiv1\pmod{\varphi(n)}$

사용할 공식·판정 관계

Modulus $\[n=pq\]$
Prime square의 totient $\varphi(p^2)=p^2-p=p(p-1)$
e의 조건 $\gcd(e,\varphi(n))=1$
d의 조건 $d\equiv e^{-1}\pmod{\varphi(n)}$
쉬운 역원 탐색 $d=\frac{1+k\varphi(n)}{e}$
분자가 e로 나누어지는 가장 작은 k를 찾는다.

01

중복 소수 확인

구체적으로 문제는 p=7, q=7로 같은 소수를 두 번 주므로 표준 RSA의 p≠q 조건을 위반한다.

여기서 검산 숫자가 우연히 같은지 먼저 표시하고 기계적으로 공식에 넣지 않는다.

다음 단계로 여기서 확인한 내용을 다음 ‘n 계산’ 단계의 출발점으로 사용합니다.
02

n 계산

구체적으로 n=pq=7×7=49다.

여기서 검산 합 14가 아니라 곱 49인지 확인한다.

다음 단계로 여기서 확인한 내용을 다음 ‘φ 계산’ 단계의 출발점으로 사용합니다.
03

φ 계산

구체적으로 49는 7^2이므로 φ(49)=7^2−7=42다.

여기서 검산 서로 다른 소수일 때만 쓰는 (7−1)(7−1)=36을 적용하지 않는다.

다음 단계로 여기서 확인한 내용을 다음 ‘e 선택’ 단계의 출발점으로 사용합니다.
04

e 선택

구체적으로 42=2×3×7이므로 이 인수들과 겹치지 않고 1이 아닌 작은 e=5를 고른다.

여기서 검산 gcd(5,42)=1을 Euclid 또는 소인수로 확인한다.

다음 단계로 여기서 확인한 내용을 다음 ‘d 계산’ 단계의 출발점으로 사용합니다.
05

d 계산

구체적으로 5d=1+42k에서 k=2를 쓰면 d=85÷5=17이다.

여기서 검산 5×17=85, 85 mod42=1, d≠1을 모두 확인한다.

다음 단계로 여기서 확인한 내용을 다음 ‘유효성 한계 명시’ 단계의 출발점으로 사용합니다.
06

유효성 한계 명시

구체적으로 값 (n,φ,e,d)=(49,42,5,17)은 조건부 역원 계산의 답이지만 m=7에서 복구가 실패하므로 전체 메시지 공간의 표준 RSA 키 쌍은 아니다.

여기서 검산 시험 의도 값과 수학적 엄밀성을 둘 중 하나 지우지 말고 함께 제시한다.

다음 단계로 앞 단계의 결과를 모아 채점 가능한 최종 답안으로 정리합니다.

정답과 해설

한 가지 유효한 답: n=49, φ(n)=42, e=5, d=17.

정답이 이렇게 되는 이유

시험 입력칸의 의도된 조건부 값 한 가지는 n=49, φ(n)=42, e=5, d=17이다. gcd(5,42)=1이고 5×17=85≡1 mod 42이므로 e와 d의 역원 조건은 맞는다. 그러나 표준 RSA는 서로 다른 소수 p≠q를 요구하며, 이 조건에서는 m=7이 암호화 후 0이 되어 복구되지 않는다. 따라서 엄밀히는 전체 메시지 공간에 대한 유효한 표준 RSA 키 쌍이 없고, 위 숫자는 시험이 요구한 조건부 산술값이라는 주석이 필요하다.

초보자가 가장 자주 뒤집는 지점

잘못된 생각 φ(n)=(p−1)(q−1)이므로 p=q=7에서도 φ=36이고, 그 값으로 e,d를 고르면 된다.

왜 틀렸나 이 곱 공식은 서로 다른 소수의 곱에서 사용한다. n=49는 prime square이므로 7의 배수 7개를 제외한 49−7=42가 totient다.

고쳐 말하면 φ(7^2)=7^2−7=42; e=5,d=17은 modulo 42 역원이지만 p=q라서 표준 RSA 유효성에는 별도 문제가 있다.

한 문제만 더: 개념이 정말 연결됐는지 확인

질문 조건부 값 e=5,d=17로 메시지 m=7을 modulo 49에서 암호화·복호화하면 원래 7로 돌아오는가?

정답 아니다. 7^5 mod49=0이고 이후 0^17 mod49=0이므로 7을 복구하지 못한다. 이것이 p=q 조건의 엄밀한 결함을 보여 준다.

이 문제의 오답 함정

복기를 p=7,q=11처럼 고쳐 풀기
p=q인데도 φ(n)=(p-1)(q-1)=36으로 계산하기
e=1 또는 d=1을 고르기

ACTIVE RECALL

이 소문제를 점수로 바꾸는 6개의 작은 훈련

01 · 30초 문제 지도
해설을 보지 말고 주어진 정보 → 구할 것 → 사용할 공식·판정 관계를 한 줄씩 복원하세요.

막힐 때만 첫 단서 열기

여기서는 계산보다 먼저 p와 q가 같다는 점이 문제인지 확인하라.
02 · 90초 닫힌책 답안
p = 7, q = 7인 RSA에서 gültiges Schlüsselpaar ((e,n),(d,n))를 구하라. 풀이 과정 없이 n, φ(n), e, d만 쓰며 e=1,d=1은 제외한다.

정답 문장만 말하지 말고 근거·중간값·메시지 흐름 중 이 문항에 필요한 것을 빈 종이에 남기세요.
03 · 부분점수 자가채점
작성한 뒤에만 아래 기준을 열고, 실제로 쓴 항목만 체크하세요.

답안 작성 후 채점 기준 열기

답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.

n=49를 쓴다. p=q이므로 φ(49)=42를 쓴다. gcd(e,42)=1이고 e≠1인 값을 고른다. ed≡1 (mod 42)이고 d≠1인 역원을 쓴다.

0/4 slots
04 · 문항별 후속 질문·조건 전이
- 왜 강의의 RSA Schlüsselgeneration은 p≠q를 요구하는가?
- p=q일 때 φ(p^2)는 왜 p(p-1)인가?
- e=5의 inverse modulo 42를 확장 유클리드 없이 어떻게 확인할 수 있는가?
조건 변형: 문제의 숫자 하나가 달라졌다고 가정하세요. 어느 중간값부터 다시 계산해야 하는지 표시하고, 마지막 검산식까지 순서만 빈 종이에 재구성하세요.
05 · 대표 오답 복구
고칠 답안: 복기를 p=7,q=11처럼 고쳐 풀기

복구 힌트: 여기서는 계산보다 먼저 p와 q가 같다는 점이 문제인지 확인하라.

오답의 첫 잘못된 전제를 한 줄로 지우고, 올바른 조건과 결론을 두 줄로 다시 쓰세요.
06 · 확신도 보정·다음 복습 결정
채점 전 예상과 실제 채점 결과가 달랐는지 확인한 뒤 상태를 남기세요. ‘숙달’은 근거와 중간 과정까지 무힌트로 재현했을 때만 선택합니다.

현재 확신도 낮음 보통 높음

아직 복습 판정을 남기지 않았습니다.

모든 훈련을 마친 뒤 핵심 정답 다시 확인

한 가지 유효한 답: n=49, φ(n)=42, e=5, d=17.

1.3.4 öffentlicher Schlüssel (3,55)를 사용해 RSA로 Nachricht m=4를 verschlüsseln하고 Rechenweg를 쓰라. 기존 71문항 학습 번호 15 · 4점 계산

1.3.4 · 실제 시험 원문

4. Verschlüsseln Sie die Nachricht $m = 4$ mit dem RSA Kryptosystem. Verwenden Sie dazu den öffentlichen Schlüssel $(3,55)$. Geben Sie Ihren Rechenweg mit an! **(4 Punkte)**

한국어로 요구사항만 풀어 읽기

öffentlicher Schlüssel (3,55)를 사용해 RSA로 Nachricht m=4를 verschlüsseln하고 Rechenweg를 쓰라.

암호화의 가장 기본적인 등장인물RSA 계산에 필요한 소수·φ·서로소·역원Modulo, 경우의 수, key space를 처음부터 계산하기

TERMS FOR 1.3.4

이 소문제의 중요한 용어부터 이해하기

전문 용어를 알고 있다고 가정하지 않습니다. 아래 정의의 굵은 용어를 문제 문장 속 같은 단어와 바꾸어 읽은 뒤 풀이로 넘어가세요.

01Plaintext: 암호화하기 전의 원래 메시지입니다. 사람이 읽는 문장뿐 아니라 파일의 byte도 plaintext가 될 수 있습니다.
02Ciphertext: 암호화 결과입니다. 숨겨진 원문과 같은 말이 아니라, key 없이는 원문을 알아내기 어려워야 하는 출력입니다.
03Key: 암호 알고리즘의 동작을 결정하는 값입니다. 알고리즘 자체가 아니라 key를 비밀로 관리하는 것이 현대 암호의 기본입니다.
04Encryption / Decryption: Encryption은 plaintext를 ciphertext로, decryption은 올바른 key로 ciphertext를 다시 plaintext로 바꾸는 과정입니다.
05Prime number: 1과 자기 자신으로만 나누어지는 1보다 큰 정수입니다.
06Euler φ function: n 이하에서 n과 서로소인 수의 개수를 나타내며 RSA key 계산에 사용됩니다.
07Coprime: 두 수의 최대공약수가 1인 관계입니다.
08Modular inverse: `a·b ≡ 1 (mod n)`을 만족하는 b로, modulo 세계에서 나눗셈 역할을 합니다.

ZERO-BASE MINI LESSON · 1.3.4

이 소문제만을 위한 0부터 시작하는 미니 강의

1 · 먼저 알아야 할 개념

RSA 공개키는 (e,n)으로 쓰며 e는 public exponent, n은 modulus다. 문제의 (3,55)는 e=3, n=55라는 뜻이지 p=3, q=55라는 뜻이 아니다.

RSA는 정수에 대한 연산이므로 실제 텍스트는 encoding과 안전한 padding을 거쳐 0≤m<n인 정수 블록으로 표현된다. 이 시험에서는 이미 숫자 메시지 m=4가 주어져 encoding 단계는 끝났다.

교육용 textbook RSA의 암호화 공식은 c=m^e mod n이다. 공개 지수로 거듭제곱한 뒤 n으로 나눈 나머지를 ciphertext로 사용한다.

Modulo a mod n은 a를 n으로 나눈 나머지다. 실제 큰 수는 square-and-multiply로 중간마다 modulo를 취하지만, 이 문항의 4^3=64는 작아서 직접 계산할 수 있다.

Textbook RSA는 randomness가 없어 같은 (e,n)과 같은 m에서 항상 같은 c가 나오는 deterministic 방식이다. 실제 RSA 암호화에는 RSA-OAEP 같은 randomized encoding을 사용해야 하며, 이 시험 계산은 원리 학습용이다.

2 · 일상 장면으로 먼저 잡기

공개된 계산 레시피에 숫자 재료를 넣고, 결과가 원형 숫자판 0~54를 넘으면 55칸마다 한 바퀴를 버리고 남은 칸만 기록하는 장면을 생각한다.

공개된 레시피의 세제곱 지시 public exponent e=3
55칸 원형 숫자판 modulus n=55
입력 숫자 4 encoded message m=4
한 바퀴를 버리고 남은 9 ciphertext 64 mod55=9

비유의 경계 원형 숫자판만으로 RSA 보안이 생기는 것은 아니다. 실제 보안은 큰 수, 적절한 키 생성과 OAEP 같은 encoding에 의존하며 이 작은 deterministic 계산은 공격에 안전하지 않다.

3 · 눈으로 관계 읽기 RSA 암호화 한 줄

01 주어진 것
m=4, (e,n)=(3,55)
02 공식
c=m^e mod n
03 거듭제곱
4^3=64
04 나머지
64=1×55+9
05 암호문
c=9

각 행을 위에서 아래로 옮겨 적으면 시험이 요구하는 Rechenweg가 완성된다.

4 · TOY EXAMPLE

다른 공개키 `(3,33)`으로 m=3 암호화

주어진 것과 목표 장난감 공개키 (e,n)=(3,33)과 메시지 m=3을 사용한다. 목표는 공개키 읽기부터 modulo 결과까지 같은 절차를 연습하는 것이다.

01

튜플의 위치를 읽어 e=3, n=33으로 표시한다.

왜? 공식의 지수와 modulus 자리를 바꾸지 않기 위해서다.

중간 결과 사용할 공식은 c=3^3 mod33이다.
02

3^3=3×3×3을 계산한다.

왜? 먼저 거듭제곱 값을 구해야 나머지를 취할 수 있기 때문이다.

중간 결과 3^3=27이다.
03

27 mod33을 계산한다.

왜? RSA ciphertext는 0부터 n−1 범위에 있어야 하기 때문이다.

중간 결과 27이 33보다 작으므로 나머지는 그대로 27이다.
04

결과 범위를 검사한다.

왜? modulo 계산의 간단한 오류를 잡기 위해서다.

중간 결과 0≤27<33이므로 ciphertext c=27이 범위에 맞는다.

예제 결론 공개키 (e,n)을 읽고 m^e를 계산한 뒤 modulo n의 나머지를 취하면 된다.

실제 시험으로 옮기기 실제 값은 (e,n)=(3,55), m=4이므로 같은 틀에 넣어 4^3 mod55=9를 계산한다.

이번 문제는 이 단계로 풀어야 했습니다

START HERE

먼저 문제를 식과 조건으로 정리하기

강사가 문제의 요구사항을 쉬운 말로 바꾸면

시험 문장이 요구하는 것: öffentlicher Schlüssel (3,55)를 사용해 RSA로 Nachricht m=4를 verschlüsseln하고 Rechenweg를 쓰라.

이 문제의 풀이 전략: 이 소문제에서는 공개키 읽기 → 공식과 대입 → 거듭제곱 → Modulo → 최종 표기 순서로 진행합니다. 마지막에는 ‘`(3,55)`는 바로 `e=3,n=55`이므로 `c=4^3 mod55=9`만 계산한다.’라는 교정 기준으로 답을 다시 확인합니다.

문제에서 주어진 정보

Plaintext $\[m=4\]$
Public key $\[(e,n)=(3,55)\]$

최종적으로 구해야 하는 것

최종 출력 $\[c\]$
요구 과정
RSA encryption 식에 m, e, n을 대입하고 modulo 결과를 계산한다.

사용할 공식·판정 관계

RSA encryption $c\equiv m^e\pmod n$
값 대입 $c\equiv4^3\pmod{55}$
나머지 계산 $4^3=64=55+9\Rightarrow c=9$

01

공개키 읽기

구체적으로 (3,55)는 (e,n)이므로 e=3, n=55다.

여기서 검산 e와 n을 뒤집거나 개인 지수 d로 오해하지 않는다.

다음 단계로 여기서 확인한 내용을 다음 ‘공식과 대입’ 단계의 출발점으로 사용합니다.
02

공식과 대입

구체적으로 RSA 암호화 공식 c=m^e mod n에 넣어 c=4^3 mod55를 쓴다.

여기서 검산 암호화에는 public exponent e를 사용했는지 본다.

다음 단계로 여기서 확인한 내용을 다음 ‘거듭제곱’ 단계의 출발점으로 사용합니다.
03

거듭제곱

구체적으로 4^3=4×4×4=64다.

여기서 검산 4×3=12로 계산하지 않는다.

다음 단계로 여기서 확인한 내용을 다음 ‘Modulo’ 단계의 출발점으로 사용합니다.
04

Modulo

구체적으로 64=1×55+9이므로 64 mod55=9다.

여기서 검산 결과 9가 0≤9<55 범위인지 확인한다.

다음 단계로 여기서 확인한 내용을 다음 ‘최종 표기’ 단계의 출발점으로 사용합니다.
05

최종 표기

구체적으로 ciphertext는 c=9라고 단위를 명확히 적는다.

여기서 검산 중간값 64를 최종 암호문으로 제출하지 않는다.

다음 단계로 앞 단계의 결과를 모아 채점 가능한 최종 답안으로 정리합니다.

정답과 해설

c=m^e mod n=4^3 mod 55=64 mod 55=9.

정답이 이렇게 되는 이유

RSA 암호화에는 공개키 (e,n)과 공식 c=m^e mod n을 사용한다. 여기서는 e=3, n=55, m=4이므로 c=4^3 mod55다. 4^3=64이고 64=55+9이므로 나머지는 9다. 따라서 최종 ciphertext는 c=9다.

초보자가 가장 자주 뒤집는 지점

잘못된 생각 공개키 (3,55)의 두 수를 소수 p와 q로 보고 n을 다시 3×55로 계산한다.

왜 틀렸나 문제가 공개키의 표기 (e,n)를 이미 줬다는 사실을 놓쳤다.

고쳐 말하면 (3,55)는 바로 e=3,n=55이므로 c=4^3 mod55=9만 계산한다.

한 문제만 더: 개념이 정말 연결됐는지 확인

질문 공개키 (e,n)=(5,21)로 메시지 m=2를 textbook RSA 암호화하면 c는 얼마인가?

정답 c=2^5 mod21=32 mod21=11이다.

이 문제의 오답 함정

mod 55를 빼먹기
3^4로 계산하기
signature formula와 encryption formula를 섞기

ACTIVE RECALL

이 소문제를 점수로 바꾸는 6개의 작은 훈련

01 · 30초 문제 지도
해설을 보지 말고 주어진 정보 → 구할 것 → 사용할 공식·판정 관계를 한 줄씩 복원하세요.

막힐 때만 첫 단서 열기

암호화는 public exponent e를 쓴다. private exponent d가 아니다.
02 · 90초 닫힌책 답안
öffentlicher Schlüssel (3,55)를 사용해 RSA로 Nachricht m=4를 verschlüsseln하고 Rechenweg를 쓰라.

정답 문장만 말하지 말고 근거·중간값·메시지 흐름 중 이 문항에 필요한 것을 빈 종이에 남기세요.
03 · 부분점수 자가채점
작성한 뒤에만 아래 기준을 열고, 실제로 쓴 항목만 체크하세요.

답안 작성 후 채점 기준 열기

답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.

공식 c = m^e mod n을 쓴다. m=4, e=3, n=55를 대입한다. 4^3 = 64 중간 계산을 보인다. 64 mod 55 = 9로 최종 ciphertext를 제시한다.

0/4 slots
04 · 문항별 후속 질문·조건 전이
- 같은 key로 m=5를 암호화하면 어떤 식을 써야 하는가?
- RSA encryption과 RSA signing에서 public/private exponent 사용 방향은 어떻게 다른가?
- 최종값에서 출발해 각 중간값을 역순으로 검산하고, public/private key, modulus, exponent 중 하나라도 뒤바뀌면 어디서 처음 오류가 나는지 지적하세요.
조건 변형: 문제의 숫자 하나가 달라졌다고 가정하세요. 어느 중간값부터 다시 계산해야 하는지 표시하고, 마지막 검산식까지 순서만 빈 종이에 재구성하세요.
05 · 대표 오답 복구
고칠 답안: mod 55를 빼먹기

복구 힌트: 암호화는 public exponent e를 쓴다. private exponent d가 아니다.

오답의 첫 잘못된 전제를 한 줄로 지우고, 올바른 조건과 결론을 두 줄로 다시 쓰세요.
06 · 확신도 보정·다음 복습 결정
채점 전 예상과 실제 채점 결과가 달랐는지 확인한 뒤 상태를 남기세요. ‘숙달’은 근거와 중간 과정까지 무힌트로 재현했을 때만 선택합니다.

현재 확신도 낮음 보통 높음

아직 복습 판정을 남기지 않았습니다.

모든 훈련을 마친 뒤 핵심 정답 다시 확인

c=m^e mod n=4^3 mod 55=64 mod 55=9.

1.3.5 RSA-Schlüsselpaar ((e,n),(d,n))=((11,15),(3,15))로 Hash h=3에 signieren하고 Rechenweg를 쓰라. 기존 71문항 학습 번호 16 · 6점 계산

1.3.5 · 실제 시험 원문

5. Signieren Sie den Hash $h = 3$ mit dem RSA-Kryptosystem. Verwenden Sie dazu das Schlüsselpaar $((e,n),(d,n)) = ((11,15),(3,15))$. Geben Sie Ihren Rechenweg mit an! **(6 Punkte)**

# 2. Netzwerksicherheit (62 Punkte)

한국어로 요구사항만 풀어 읽기

RSA-Schlüsselpaar ((e,n),(d,n))=((11,15),(3,15))로 Hash h=3에 signieren하고 Rechenweg를 쓰라.

Digital signature는 무엇을 증명하는가RSA 계산에 필요한 소수·φ·서로소·역원Hash는 암호화가 아니라 고정 길이 지문이다

TERMS FOR 1.3.5

이 소문제의 중요한 용어부터 이해하기

전문 용어를 알고 있다고 가정하지 않습니다. 아래 정의의 굵은 용어를 문제 문장 속 같은 단어와 바꾸어 읽은 뒤 풀이로 넘어가세요.

01Cryptographic Hash

입력 데이터에서 고정 길이 digest를 계산하는 함수입니다. 수집 전후 hash가 같으면 그 사이 byte가 바뀌지 않았다는 강한 근거가 됩니다.

작은 예: 원본과 forensic image의 SHA-256을 기록하고 비교합니다.

02Digital signature

private key 소유자가 특정 메시지에 서명했음을 검증하게 하는 값입니다.

03Signing

메시지와 private key로 signature를 만드는 과정입니다.

04Verification

메시지, signature, public key로 서명의 유효성을 검사하는 과정입니다.

05Authenticity / Integrity

서명은 서명자와 메시지의 진위를 확인하지만 메시지 내용을 숨기는 confidentiality 기능은 아닙니다.

06Prime number

1과 자기 자신으로만 나누어지는 1보다 큰 정수입니다.

07Euler φ function

n 이하에서 n과 서로소인 수의 개수를 나타내며 RSA key 계산에 사용됩니다.

08Coprime

두 수의 최대공약수가 1인 관계입니다.

ZERO-BASE MINI LESSON · 1.3.5

이 소문제만을 위한 0부터 시작하는 미니 강의

1 · 먼저 알아야 할 개념

디지털 서명의 목적은 메시지를 숨기는 것이 아니라 private key 소유자가 승인했다는 authenticity와 메시지가 바뀌지 않았다는 integrity를 검증하는 것이다. 누구나 public key로 검증할 수 있다.

긴 메시지를 그대로 서명하기보다 먼저 h=H(m)으로 고정 길이 hash를 계산한다. 검증자는 받은 메시지를 다시 해시하고 서명이 복원하는 값과 비교하므로 메시지가 바뀌면 검증이 실패해야 한다.

주어진 키 쌍 ((e,n),(d,n))=((11,15),(3,15))에서 public key는 (11,15), private key는 (3,15)다. 즉 e=11, d=3, n=15이며 서명자는 비밀 지수 d를 사용한다.

교육용 textbook RSA 서명은 s=h^d mod n, 검증은 h'=s^e mod n이다. 정상 키와 허용된 representative에서는 h'=h가 되어야 한다.

실제 시스템은 raw hash를 그대로 지수승하지 않고 RSA-PSS 같은 안전한 randomized encoding을 사용한다. 이 시험의 작은 수 계산은 공개 지수와 개인 지수의 방향을 익히기 위한 장난감 예제다.

2 · 일상 장면으로 먼저 잡기

문서 전체를 거대한 도장판에 새기는 대신 문서의 짧은 지문 카드를 만들고, 소유자만 가진 비밀 압인기로 그 카드에 표시한다. 누구나 공개 검사틀로 압인이 그 지문 카드와 맞는지 확인한다.

문서의 짧은 지문 카드 메시지 hash h
소유자만 가진 비밀 압인기 private exponent d를 쓰는 서명 계산
공개 검사틀 public exponent e를 쓰는 검증
압인과 지문 카드가 일치 s^e mod n = h

비유의 경계 실제 디지털 서명은 물리 도장 이미지를 복사하는 것과 다르고 메시지·encoding에 수학적으로 결합된다. 또한 hash만 서명한다고 말할 때는 RSA-PSS 같은 안전한 encoding 단계가 생략된 교육용 설명임을 기억해야 한다.

3 · 눈으로 관계 읽기 RSA 서명과 검증의 방향

01 Hash
h=3
02 서명자
private d=3: s=3^3 mod15=12
03 전송
메시지와 signature s=12
04 검증자
public e=11: 12^11 mod15=3
05 판정
복원 3 = 다시 계산한 h → accept

왼쪽에서 private d로 서명하고 오른쪽에서 public e로 되돌려 hash를 비교하는 방향을 읽는다.

4 · TOY EXAMPLE

다른 RSA 키로 h=2 서명과 검증

주어진 것과 목표 장난감 키 쌍 ((e,n),(d,n))=((7,33),(3,33))와 hash h=2를 사용한다. 7×3=21≡1 mod20이므로 p=3,q=11인 n=33에서 지수 관계가 맞는다.

01

private exponent d=3을 골라 서명 식에 넣는다.

왜? 서명 생성은 비밀키 소유자만 할 수 있어야 하기 때문이다.

중간 결과 s=2^3 mod33이 된다.
02

서명값을 계산한다.

왜? 작은 거듭제곱이라 직접 계산할 수 있기 때문이다.

중간 결과 2^3=8, 따라서 s=8이다.
03

public exponent e=7로 8^7 mod33을 계산한다.

왜? 누구나 공개키로 서명이 원래 hash에 대응하는지 검증하기 위해서다.

중간 결과 8^2≡31, 8^4≡4, 따라서 8^7≡4×31×8=992≡2 mod33이다.
04

복원값과 원래 hash를 비교한다.

왜? 검증의 accept/reject 조건이 equality이기 때문이다.

중간 결과 복원값 2가 h=2와 같으므로 서명이 accept된다.

예제 결론 서명은 d로 만들고 e로 검증하며, 검증 결과가 서명 대상 hash와 같아야 한다.

실제 시험으로 옮기기 실제 문항에서는 h=3,d=3,n=15를 넣어 s=12를 구하고, 선택적으로 e=11 검산을 붙인다.

이번 문제는 이 단계로 풀어야 했습니다

START HERE

먼저 문제를 식과 조건으로 정리하기

강사가 문제의 요구사항을 쉬운 말로 바꾸면

시험 문장이 요구하는 것: RSA-Schlüsselpaar ((e,n),(d,n))=((11,15),(3,15))로 Hash h=3에 signieren하고 Rechenweg를 쓰라.

이 문제의 풀이 전략: 이 소문제에서는 키 쌍 분해 → 서명 지수 선택 → 공식 대입 → Modulo 계산 → 선택 검산 순서로 진행합니다. 마지막에는 ‘서명은 비밀 d로 `s=h^d mod n`, 검증은 공개 e로 `s^e mod n`을 계산한다.’라는 교정 기준으로 답을 다시 확인합니다.

문제에서 주어진 정보

Hash $\[h=3\]$
Key pair $\[((e,n),(d,n))=((11,15),(3,15))\]$
Signing에 사용할 값 $d=3,\quad n=15$

최종적으로 구해야 하는 것

최종 출력 $\[s\]$
선택 이유
Signature 생성에는 private exponent d를 사용한다. e는 verification에 사용한다.

사용할 공식·판정 관계

RSA signature $s\equiv h^d\pmod n$
값 대입 $s\equiv3^3\pmod{15}$
나머지 계산 $27=15+12\Rightarrow s=12$
검증 $s^e\equiv h\pmod n$

01

키 쌍 분해

구체적으로 ((11,15),(3,15))에서 e=11, d=3, n=15를 표시한다.

여기서 검산 첫 튜플은 public, 둘째 튜플은 private인지 확인한다.

다음 단계로 여기서 확인한 내용을 다음 ‘서명 지수 선택’ 단계의 출발점으로 사용합니다.
02

서명 지수 선택

구체적으로 서명 생성에는 private exponent d=3을 사용한다.

여기서 검산 암호화 공식처럼 e=11을 지수로 쓰지 않는다.

다음 단계로 여기서 확인한 내용을 다음 ‘공식 대입’ 단계의 출발점으로 사용합니다.
03

공식 대입

구체적으로 s=h^d mod n=3^3 mod15를 쓴다.

여기서 검산 h, d, n의 각 자리에 3,3,15가 들어갔는지 본다.

다음 단계로 여기서 확인한 내용을 다음 ‘Modulo 계산’ 단계의 출발점으로 사용합니다.
04

Modulo 계산

구체적으로 3^3=27이고 27=1×15+12이므로 s=12다.

여기서 검산 나머지 12가 0 이상 15 미만인지 확인한다.

다음 단계로 여기서 확인한 내용을 다음 ‘선택 검산’ 단계의 출발점으로 사용합니다.
05

선택 검산

구체적으로 12^2≡9, 12^4≡6, 12^8≡6 (mod15)이므로 12^11=12^8·12^2·12≡6·9·12≡3 mod15다.

여기서 검산 검증 결과 3이 원래 hash h=3과 같은지 비교한다.

다음 단계로 앞 단계의 결과를 모아 채점 가능한 최종 답안으로 정리합니다.

정답과 해설

서명 s=h^d mod n=3^3 mod 15=27 mod 15=12.

정답이 이렇게 되는 이유

RSA 서명에는 공개 지수 e가 아니라 private exponent d를 사용한다. 주어진 값에서 h=3, d=3, n=15이므로 s=h^d mod n=3^3 mod15다. 27 mod15=12이므로 signature는 s=12다. 공개 지수 e=11로 검산하면 12^11 mod15=3=h가 되어 검증을 통과한다.

초보자가 가장 자주 뒤집는 지점

잘못된 생각 공개키의 e=11로 3^11 mod15를 계산해야 서명이다.

왜 틀렸나 RSA 암호화와 서명 생성의 키 방향을 혼동했다. 누구나 아는 e로 서명을 만들 수 있다면 서명자 인증이 성립하지 않는다.

고쳐 말하면 서명은 비밀 d로 s=h^d mod n, 검증은 공개 e로 s^e mod n을 계산한다.

한 문제만 더: 개념이 정말 연결됐는지 확인

질문 메시지가 바뀌어 검증자가 다시 계산한 hash가 4가 되었지만 받은 signature 12는 여전히 12^11 mod15=3을 만든다. 검증 결과는?

정답 reject다. 서명에서 복원한 3과 새 메시지의 hash 4가 다르므로 무결성 검사가 실패한다.

이 문제의 오답 함정

검증식 s^e mod n을 서명 계산에 사용하기
h=3 대신 m을 새로 hash하려고 하기
mod 15 계산을 빼먹기

ACTIVE RECALL

이 소문제를 점수로 바꾸는 6개의 작은 훈련

01 · 30초 문제 지도
해설을 보지 말고 주어진 정보 → 구할 것 → 사용할 공식·판정 관계를 한 줄씩 복원하세요.

막힐 때만 첫 단서 열기

Signieren은 공개키 e가 아니라 개인키 d 방향이다.
02 · 90초 닫힌책 답안
RSA-Schlüsselpaar ((e,n),(d,n))=((11,15),(3,15))로 Hash h=3에 signieren하고 Rechenweg를 쓰라.

정답 문장만 말하지 말고 근거·중간값·메시지 흐름 중 이 문항에 필요한 것을 빈 종이에 남기세요.
03 · 부분점수 자가채점
작성한 뒤에만 아래 기준을 열고, 실제로 쓴 항목만 체크하세요.

답안 작성 후 채점 기준 열기

답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.

서명에는 private key exponent d를 쓴다고 명시한다. 공식 s = h^d mod n을 쓴다. h=3, d=3, n=15를 대입한다. 3^3 = 27, 27 mod 15 = 12를 보인다.

0/4 slots
04 · 문항별 후속 질문·조건 전이
- 검증할 때는 어떤 식으로 h와 signature를 비교하는가?
- RSA signature에서 hash function이 필요한 이유는 무엇인가?
- 최종값에서 출발해 각 중간값을 역순으로 검산하고, public/private key, modulus, exponent 중 하나라도 뒤바뀌면 어디서 처음 오류가 나는지 지적하세요.
조건 변형: 문제의 숫자 하나가 달라졌다고 가정하세요. 어느 중간값부터 다시 계산해야 하는지 표시하고, 마지막 검산식까지 순서만 빈 종이에 재구성하세요.
05 · 대표 오답 복구
고칠 답안: 검증식 s^e mod n을 서명 계산에 사용하기

복구 힌트: Signieren은 공개키 e가 아니라 개인키 d 방향이다.

오답의 첫 잘못된 전제를 한 줄로 지우고, 올바른 조건과 결론을 두 줄로 다시 쓰세요.
06 · 확신도 보정·다음 복습 결정
채점 전 예상과 실제 채점 결과가 달랐는지 확인한 뒤 상태를 남기세요. ‘숙달’은 근거와 중간 과정까지 무힌트로 재현했을 때만 선택합니다.

현재 확신도 낮음 보통 높음

아직 복습 판정을 남기지 않았습니다.

모든 훈련을 마친 뒤 핵심 정답 다시 확인

서명 s=h^d mod n=3^3 mod 15=27 mod 15=12.

ACTIVE RECALL

이 페이지를 닫기 전 확인

RSA의 어려운 문제와 ElGamal의 어려운 문제는 각각 무엇인가요?
d는 어떤 congruence를 만족하나요?
서명은 왜 기밀성을 제공하지 않나요?

1.3. Asymmetrische Kryptographie (24 Punkte)

이 묶음의 고정 풀이 순서

공개키 암호와 RSA·ElGamal의 수학적 기반

RSA 계산에 필요한 소수·φ·서로소·역원

Digital signature는 무엇을 증명하는가

1.3.1 · 실제 시험 원문

한국어로 요구사항만 풀어 읽기

이 소문제의 중요한 용어부터 이해하기

1 · 먼저 알아야 할 개념

2 · 일상 장면으로 먼저 잡기

n=15를 작은 소수로 나눈다.

인수로 φ(15)를 계산한다.

ElGamal 쪽에서 5의 작은 거듭제곱을 modulo 23으로 계산한다.

작은 예제와 실제 키 크기를 비교한다.

이번 문제는 이 단계로 풀어야 했습니다

강사가 문제의 요구사항을 쉬운 말로 바꾸면

문제에서 주어진 정보

최종적으로 구해야 하는 것

사용할 공식·판정 관계

RSA 구조 회상

RSA 기반 명명

ElGamal 구조 회상

ElGamal 기반 명명

두 답 짝짓기

정답과 해설

정답이 이렇게 되는 이유

초보자가 가장 자주 뒤집는 지점

이 문제의 오답 함정

1.3.2 · 실제 시험 원문

한국어로 요구사항만 풀어 읽기

이 소문제의 중요한 용어부터 이해하기

1 · 먼저 알아야 할 개념

2 · 일상 장면으로 먼저 잡기

공격자가 oracle 사용 전에 목표 m*='PAY BOB 999'를 선언한다.

'PAY BOB 10'과 'PAY ALICE 20'의 서명을 oracle에 요청한다.

관찰한 자료로 target에 대한 새 값 σ*를 계산해 출력한다.

Verify(pk,'PAY BOB 999',σ*)를 실행하고 query 목록을 확인한다.

이번 문제는 이 단계로 풀어야 했습니다

강사가 문제의 요구사항을 쉬운 말로 바꾸면

문제에서 주어진 정보

최종적으로 구해야 하는 것

사용할 공식·판정 관계

보안 대상 명시

Selective 조건

Chosen-Message 권한

비자명성 조건

승리 조건

정답과 해설

정답이 이렇게 되는 이유

초보자가 가장 자주 뒤집는 지점

이 문제의 오답 함정

1.3.3 · 실제 시험 원문

한국어로 요구사항만 풀어 읽기

이 소문제의 중요한 용어부터 이해하기

1 · 먼저 알아야 할 개념

2 · 일상 장면으로 먼저 잡기

n=5×5와 prime-power totient를 계산한다.

20과 서로소인 작은 e=3을 고르고 inverse d를 찾는다.

메시지 m=5를 e=3으로 암호화한다.

c=0을 d=7로 복호화한다.

e와 d를 시험장에서 쉽게 고르는 방법

1. φ(n)의 소인수만 표시한다

2. 작은 후보부터 e를 고른다

3. d를 1+42k 방식으로 찾는다

4. 곱셈 한 번으로 검산한다

e 후보를 작은 수부터 검사

d를 찾는 k 대입

이번 문제는 이 단계로 풀어야 했습니다

강사가 문제의 요구사항을 쉬운 말로 바꾸면

문제에서 주어진 정보

최종적으로 구해야 하는 것

사용할 공식·판정 관계

중복 소수 확인

n 계산

φ 계산

e 선택

d 계산

유효성 한계 명시

정답과 해설

정답이 이렇게 되는 이유

`n=15`를 작은 소수로 나눈다.

인수로 `φ(15)`를 계산한다.

공격자가 oracle 사용 전에 목표 `m*='PAY BOB 999'`를 선언한다.

`'PAY BOB 10'`과 `'PAY ALICE 20'`의 서명을 oracle에 요청한다.

관찰한 자료로 target에 대한 새 값 `σ*`를 계산해 출력한다.

`Verify(pk,'PAY BOB 999',σ*)`를 실행하고 query 목록을 확인한다.

`n=5×5`와 prime-power totient를 계산한다.

메시지 `m=5`를 e=3으로 암호화한다.

`3^3=3×3×3`을 계산한다.

`27 mod33`을 계산한다.

public exponent e=7로 `8^7 mod33`을 계산한다.