계산
문제
독일어 원문
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.
한국어 해석
RSA-Schlüsselpaar ((e,n),(d,n))=((11,15),(3,15))로 Hash h=3에 signieren하고 Rechenweg를 쓰라.
RSA 계산 스테퍼
각 단계의 값을 직접 계산하세요.
단계별 힌트
막혔을 때만 한 단계씩 여세요. 정답을 바로 읽는 것보다 기억을 꺼내는 시간이 중요합니다.
- 첫 힌트: Signieren은 공개키 e가 아니라 개인키 d 방향이다.
- 서명에는 private exponent d=3을 사용한다.
- s=h^d mod n=3^3 mod 15
- 27 mod 15=12
- 따라서 signature s=12
- 함정: 검증식 s^e mod n을 서명 계산에 사용하기
- 함정: h=3 대신 m을 새로 hash하려고 하기
- 함정: mod 15 계산을 빼먹기
- 후속 점검: 검증할 때는 어떤 식으로 h와 signature를 비교하는가?
채점 기준으로 내 답안 점검하기
- 서명에는 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
정답과 핵심 해설 확인하기
서명 s=h^d mod n=3^3 mod 15=27 mod 15=12.
검산: s^e mod n=12^11 mod 15=3=h.
개념부터 다시 보는 상세 풀이
BEGINNER LESSON
3-(e) RSA로 hash h=3에 서명하고 검증하기
ZERO-BASE START
정말 아무것도 모른다고 가정하고 시작합니다
전문 용어를 알고 있다고 가정하지 않습니다. 먼저 일상적인 장면을 보고, 그 장면의 사람과 행동에 실제 보안 용어를 하나씩 붙인 뒤, 시스템에서 일어나는 순서를 따라갑니다.
기초 개념 01
Digital signature는 무엇을 증명하는가
1타 강사식 시작: 이름은 잠시 가리고 장면부터 봅시다
편지 내용을 가리는 봉투가 encryption이라면 signature는 편지 내용에 연결된 위조하기 어려운 도장이다. 누구나 도장을 검사할 수 있지만 소유자만 새 도장을 만들 수 있어야 한다.
지금은 이 비유를 완벽히 외울 필요가 없습니다. 누가 무엇을 가지고 있고, 무엇을 하려 하며, 어느 지점에서 문제가 생기는지만 찾으면 됩니다.
이제 실제 용어를 하나씩 붙여 봅시다
Digital signature는 메시지를 숨기는 기술이 아니라 메시지가 private key 소유자에게서 왔고 중간에 바뀌지 않았음을 검증하는 기술이다. 보통 긴 메시지 자체가 아니라 메시지의 hash에 서명한다. RSA의 단순 교재식 표현에서는 서명 s=h^d mod n을 만들고 검증자는 s^e mod n이 h와 같은지 확인한다.
TERMS FROM ZERO
전문 용어를 한 단어씩 풀기
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Digital signature
private key 소유자가 특정 메시지에 서명했음을 검증하게 하는 값입니다.
Signing
메시지와 private key로 signature를 만드는 과정입니다.
Verification
메시지, signature, public key로 서명의 유효성을 검사하는 과정입니다.
Authenticity / Integrity
서명은 서명자와 메시지의 진위를 확인하지만 메시지 내용을 숨기는 confidentiality 기능은 아닙니다.
프로그램이나 프로토콜 안에서는 다음 순서로 움직입니다.
- 메시지를 hash해 고정 길이 digest h를 만든다.
- 서명자는 private key로 h에 대한 signature를 만든다.
- 검증자는 public key와 원래 메시지로 signature를 확인한다.
- Selective forgery에서는 공격 전에 정한 특정 새 메시지에 대한 유효 서명을 만드는 것이 목표다.
왜 여기서 많이 틀릴까요?
서명은 confidentiality를 제공하지 않는다. 또한 교재의 raw RSA 계산은 개념 연습이며 실제로는 안전한 signature encoding이 필요하다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
기초 개념 02
RSA 계산에 필요한 소수·φ·서로소·역원
1타 강사식 시작: 이름은 잠시 가리고 장면부터 봅시다
e로 자물쇠를 한 방향으로 돌린 뒤 d로 돌렸을 때 바퀴가 정확히 한 바퀴를 돌아 원위치에 오는 조합을 찾는다고 생각할 수 있다.
지금은 이 비유를 완벽히 외울 필요가 없습니다. 누가 무엇을 가지고 있고, 무엇을 하려 하며, 어느 지점에서 문제가 생기는지만 찾으면 됩니다.
이제 실제 용어를 하나씩 붙여 봅시다
소수(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다.
TERMS FROM ZERO
전문 용어를 한 단어씩 풀기
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Prime number
1과 자기 자신으로만 나누어지는 1보다 큰 정수입니다.
Euler φ function
n 이하에서 n과 서로소인 수의 개수를 나타내며 RSA key 계산에 사용됩니다.
Coprime
두 수의 최대공약수가 1인 관계입니다.
Modular inverse
`a·b ≡ 1 (mod n)`을 만족하는 b로, modulo 세계에서 나눗셈 역할을 합니다.
프로그램이나 프로토콜 안에서는 다음 순서로 움직입니다.
- 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가 역원인지 확인하지 않고 숫자를 고르면 안 된다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
기초 개념 03
Hash는 암호화가 아니라 고정 길이 지문이다
1타 강사식 시작: 이름은 잠시 가리고 장면부터 봅시다
수많은 책을 짧은 서가 번호로 압축해 표시하면 언젠가 같은 번호가 겹친다. 좋은 hash는 공격자가 원하는 겹침을 일부러 찾기 매우 어렵게 만든다.
지금은 이 비유를 완벽히 외울 필요가 없습니다. 누가 무엇을 가지고 있고, 무엇을 하려 하며, 어느 지점에서 문제가 생기는지만 찾으면 됩니다.
이제 실제 용어를 하나씩 붙여 봅시다
Cryptographic hash function은 길이가 제각각인 입력을 정해진 길이의 digest로 바꾼다. 같은 입력은 같은 digest를 만들지만 digest에서 원문을 되찾기는 어려워야 한다. 서로 다른 두 입력이 같은 digest를 만드는 상황을 collision이라고 한다. 입력 가능성은 사실상 무한하고 출력 종류는 유한하므로 collision은 수학적으로 반드시 존재하며, 보안 목표는 collision이 전혀 없게 하는 것이 아니라 현실적인 시간에 찾기 어렵게 하는 것이다.
TERMS FROM ZERO
전문 용어를 한 단어씩 풀기
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Hash function
임의 길이 입력을 고정 길이 digest로 바꾸는 단방향 함수입니다. 암호화처럼 복호화 key가 있는 기능이 아닙니다.
Digest
Hash function의 고정 길이 출력으로, 데이터의 짧은 지문처럼 사용됩니다.
Collision
서로 다른 두 입력이 같은 digest를 만드는 경우입니다. 출력 공간이 유한하므로 존재 자체는 피할 수 없습니다.
Preimage resistance
주어진 digest를 만드는 입력을 현실적인 시간에 찾기 어려워야 한다는 성질입니다.
프로그램이나 프로토콜 안에서는 다음 순서로 움직입니다.
- 출력 길이는 입력 문장 길이가 아니라 알고리즘이 정한 bit 수로 고정된다.
- Preimage resistance는 digest에서 원문을 찾기 어려운 성질이다.
- Collision resistance는 서로 다른 두 입력의 같은 digest를 찾기 어려운 성질이다.
- MD5처럼 실용적인 collision 공격이 알려진 알고리즘은 보안 용도로 사용하지 않는다.
왜 여기서 많이 틀릴까요?
collision-free라는 절대 표현과 collision-resistant라는 계산적으로 찾기 어렵다는 표현을 구분해야 한다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
핵심부터 말하면 서명에는 private exponent d=3을 사용한다. s=h^d mod n=3³ mod15=27 mod15=12이므로 signature는 s=12다.
이 글에서 익힐 것
RSA 암호화와 RSA 서명에서 사용하는 지수를 구분한다.
hash-then-sign 흐름을 이해한다.
서명 생성 s=h^d mod n을 단계별로 계산한다.
검증 h'=s^e mod n으로 결과를 역확인한다.
교육용 textbook RSA signature와 실제 RSA-PSS를 구분한다.
개념부터 차근차근
-
서명의 목적
디지털 서명은 메시지를 숨기는 암호화가 아니다. private key 보유자가 메시지에 동의했다는 authenticity와 메시지가 바뀌지 않았다는 integrity를 검증하게 한다. 검증용 public key는 누구나 가져도 된다.
-
왜 메시지 대신 hash에 서명하는가
메시지는 매우 길 수 있지만 hash는 고정 길이다. 먼저 h=H(m)을 계산하고 그 digest에 안전한 encoding을 적용해 서명하면 효율적이다. 메시지 한 비트가 바뀌면 hash가 달라져 기존 서명 검증이 실패해야 한다.
-
키 쌍 읽기
((e,n),(d,n))=((11,15),(3,15))에서 public key는 (e,n)=(11,15), private key는 (d,n)=(3,15)다. 즉 e=11, d=3, n=15다.
-
서명과 검증 공식
교육용 textbook RSA에서 서명은 s=h^d mod n이고 검증은 h'=s^e mod n이다. 정상 키라면 h'=h가 되어야 한다. 서명자는 비밀 d를 쓰고 검증자는 공개 e를 쓴다.
Given values
Symbol
h
Value
3
Meaning
이미 계산된 message hash
Symbol
d
Value
3
Meaning
private signing exponent
Symbol
n
Value
15
Meaning
modulus
Symbol
e
Value
11
Meaning
public verification exponent
Symbol
s
Value
구할 값
Meaning
signature
단계별로 따라가기
서명 공식을 쓴다: s=h^d mod n.
값을 대입한다: s=3³ mod15.
거듭제곱한다: 3³=3·3·3=27.
나머지를 구한다: 27=1·15+12이므로 27 mod15=12.
따라서 signature s=12다.
시험 답안으로 정리하기
Recommended lines
s = h^d mod n
= 3^3 mod 15
= 27 mod 15
= 12
Final sentence
Die Signatur ist s=12.
Point strategy
공식·대입·거듭제곱·modulo·최종 서명을 줄별로 보여 Rechenweg 점수를 확보한다.
단계별로 따라가기
검증자는 public key (e,n)=(11,15)를 사용한다.
h'=s^e mod n=12^11 mod15를 계산한다.
12²=144≡9 mod15이다.
12⁴≡9²=81≡6 mod15이다.
12⁸≡6²=36≡6 mod15이다.
11=8+2+1이므로 12^11=12⁸·12²·12≡6·9·12=648≡3 mod15이다.
복원된 h'=3이 주어진 h=3과 같으므로 서명 s=12는 검증된다.
왜 그런지 이해하기
n=15=3·5이고 φ(15)=(3−1)(5−1)=8이다.
e=11은 modulo8에서 3과 같고 gcd(11,8)=1이다.
ed=11·3=33=4·8+1이므로 ed≡1 mod8이다.
따라서 d=3은 e=11의 modulo φ(15) inverse다.
h=3은 n=15와 서로소가 아니지만 n이 서로 다른 두 소수의 곱인 표준 형태라 이 예에서는 CRT 관점의 RSA correctness가 성립하며 실제 검산도 3으로 돌아온다.
헷갈리는 개념 비교하기
-
confidentiality
Encryption
보내는 사람 누구나
수신자의 public e
c=m^e mod n
-
평문 복원
Decryption
private key 소유자
private d
m=c^d mod n
-
authenticity/integrity
Signing
서명자
private d
s=h^d mod n
-
서명 유효성 확인
Verification
누구나
public e
h'=s^e mod n
Security context
raw RSA에서 단순히 h^d mod n만 계산하는 방식은 textbook 설명이다.
실제 RSA signature는 hash를 정해진 안전한 encoding에 넣으며 현대 권장은 RSA-PSS다. 단순 raw RSA는 대수적(multiplicative) 구조 때문에 위조에 취약할 수 있다.
검증자는 단순히 숫자가 맞는지만 보지 않고 사용한 hash algorithm, PSS parameters, 인증서/public key 신뢰까지 확인해야 한다.
서명은 메시지를 숨기지 않는다. 메시지 기밀성이 필요하면 별도의 encryption을 결합한다.
문제를 푸는 순서
1단계: 문제 동사 signieren을 보고 private exponent d를 선택한다.
2단계: 키 쌍에서 d=3,n=15를 읽는다. e=11은 검증용이다.
3단계: s=h^d mod n을 쓴다.
4단계: 3³=27, 27 mod15=12를 계산한다.
5단계: s=12라고 명시한다.
6단계: 학습 시 s^e mod n=3으로 검증하지만 시험 답안에서는 요구된 Rechenweg 분량에 맞춘다.
시험장에서는 이렇게 쓰기
German
Für die RSA-Signatur wird der private Exponent d verwendet: s=h^d mod n=3^3 mod15=27 mod15=12. Die Signatur lautet s=12.
Verification optional
Kontrolle: s^e mod n=12^11 mod15=3=h.
자주 틀리는 지점
서명에 public exponent e=11을 사용해 3^11을 계산하는 것. e는 검증용이다.
암호화와 서명의 목적을 모두 confidentiality라고 쓰는 것.
s=d^h mod n 또는 s=h·d mod n처럼 밑·지수·곱셈을 뒤섞는 것.
3³=27까지만 쓰고 modulo15를 생략하는 것.
나머지 12 대신 몫 1을 답으로 쓰는 것.
검증에서 다시 d를 사용하는 것. 검증자는 공개된 e를 사용한다.
raw textbook 계산이 실무에서도 그대로 안전하다고 생각하는 것. RSA-PSS 같은 검증된 encoding이 필요하다.
한 줄로 기억하기
서명은 비밀 d로 도장을 찍고, 검증은 공개 e로 도장을 읽는다: Sign h^d, Verify s^e.
스스로 확인하기
-
주어진 키 쌍에서 서명에 쓰는 지수는?
private exponent d=3.
-
3³ mod15의 값은?
27 mod15=12.
-
서명 12를 검증할 때 계산하는 식은?
12^11 mod15이며 결과는 3이다.
-
검증 결과 3은 무엇과 비교하는가?
검증자가 메시지에서 다시 계산한 hash h=3과 비교한다.
-
실제 RSA signature의 대표적인 안전한 encoding은?
RSA-PSS.
설명의 근거
Gedächtnisprotokoll Computersystemsicherheit WS2025_26.md, Krypto / Asymmetrische Kryptographie, 3-(e), 6 Punkte.
Vorlesung 04 Asymmetrische Kryptographie, p.25-28 — RSA digital signature 생성·검증.
CSS Exam SoSe22, p.9-10 — RSA signature 계산과 Rechenweg 형식.
예제로 확인하기
-
Digital signature는 무엇을 증명하는가을 구체적인 순서로 보기
편지 내용을 가리는 봉투가 encryption이라면 signature는 편지 내용에 연결된 위조하기 어려운 도장이다. 누구나 도장을 검사할 수 있지만 소유자만 새 도장을 만들 수 있어야 한다.
메시지를 hash해 고정 길이 digest h를 만든다.
서명자는 private key로 h에 대한 signature를 만든다.
검증자는 public key와 원래 메시지로 signature를 확인한다.
Selective forgery에서는 공격 전에 정한 특정 새 메시지에 대한 유효 서명을 만드는 것이 목표다.
각 단계에서 입력이나 message가 어떻게 달라지는지 확인한 뒤 현재 문제의 조건과 결론에 연결합니다.
-
RSA 계산에 필요한 소수·φ·서로소·역원을 구체적인 순서로 보기
e로 자물쇠를 한 방향으로 돌린 뒤 d로 돌렸을 때 바퀴가 정확히 한 바퀴를 돌아 원위치에 오는 조합을 찾는다고 생각할 수 있다.
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을 목적에 맞게 적용한다.
각 단계에서 입력이나 message가 어떻게 달라지는지 확인한 뒤 현재 문제의 조건과 결론에 연결합니다.
-
Hash는 암호화가 아니라 고정 길이 지문이다을 구체적인 순서로 보기
수많은 책을 짧은 서가 번호로 압축해 표시하면 언젠가 같은 번호가 겹친다. 좋은 hash는 공격자가 원하는 겹침을 일부러 찾기 매우 어렵게 만든다.
출력 길이는 입력 문장 길이가 아니라 알고리즘이 정한 bit 수로 고정된다.
Preimage resistance는 digest에서 원문을 찾기 어려운 성질이다.
Collision resistance는 서로 다른 두 입력의 같은 digest를 찾기 어려운 성질이다.
MD5처럼 실용적인 collision 공격이 알려진 알고리즘은 보안 용도로 사용하지 않는다.
각 단계에서 입력이나 message가 어떻게 달라지는지 확인한 뒤 현재 문제의 조건과 결론에 연결합니다.
이 문제가 어려운 이유
짧은 문제 문장 ‘RSA-Schlüsselpaar ((e,n),(d,n))=((11,15),(3,15))로 Hash h=3에 signieren하고 Rechenweg를 쓰라.’ 안에 정의, 조건, 처리 순서가 압축되어 있습니다. 아래 예시에서는 이를 한 단계씩 펼쳐 확인합니다.
AI 구두시험용 프롬프트
한 문항만 풀어라. 먼저 정답을 열지 말고 90초 안에 답안을 말한 뒤, css-ws2025-26-crypto-asym-005의 채점 프레임으로 스스로 채점하라. 문제: RSA-Schlüsselpaar ((e,n),(d,n))=((11,15),(3,15))로 Hash h=3에 signieren하고 Rechenweg를 쓰라.
학습 기록