계산
문제
독일어 원문
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.
한국어 해석
öffentlicher Schlüssel (3,55)를 사용해 RSA로 Nachricht m=4를 verschlüsseln하고 Rechenweg를 쓰라.
RSA 계산 스테퍼
각 단계의 값을 직접 계산하세요.
단계별 힌트
막혔을 때만 한 단계씩 여세요. 정답을 바로 읽는 것보다 기억을 꺼내는 시간이 중요합니다.
- 첫 힌트: 암호화는 public exponent e를 쓴다. private exponent d가 아니다.
- 공개키 (e,n)=(3,55)를 식 c=m^e mod n에 넣는다.
- 4^3=64
- 64 mod 55=9
- 따라서 ciphertext c=9
- 함정: mod 55를 빼먹기
- 함정: 3^4로 계산하기
- 함정: signature formula와 encryption formula를 섞기
- 후속 점검: 같은 key로 m=5를 암호화하면 어떤 식을 써야 하는가?
채점 기준으로 내 답안 점검하기
- 공식 c = m^e mod n을 쓴다.
- m=4, e=3, n=55를 대입한다.
- 4^3 = 64 중간 계산을 보인다.
- 64 mod 55 = 9로 최종 ciphertext를 제시한다.
답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.
0/4 slots
정답과 핵심 해설 확인하기
c=m^e mod n=4^3 mod 55=64 mod 55=9.
개념부터 다시 보는 상세 풀이
BEGINNER LESSON
3-(d) 공개키 (3,55)로 m=4를 RSA 암호화하기
ZERO-BASE START
정말 아무것도 모른다고 가정하고 시작합니다
전문 용어를 알고 있다고 가정하지 않습니다. 먼저 일상적인 장면을 보고, 그 장면의 사람과 행동에 실제 보안 용어를 하나씩 붙인 뒤, 시스템에서 일어나는 순서를 따라갑니다.
기초 개념 01
암호화의 가장 기본적인 등장인물
1타 강사식 시작: 이름은 잠시 가리고 장면부터 봅시다
누구나 자물쇠의 설계도를 볼 수 있지만 실제 열쇠가 없으면 열지 못하는 자물쇠를 생각하면 된다. 설계도를 숨기는 것이 아니라 열쇠를 관리하는 것이 핵심이다.
지금은 이 비유를 완벽히 외울 필요가 없습니다. 누가 무엇을 가지고 있고, 무엇을 하려 하며, 어느 지점에서 문제가 생기는지만 찾으면 됩니다.
이제 실제 용어를 하나씩 붙여 봅시다
평문(plaintext)은 보호하기 전의 원래 데이터이고 암호문(ciphertext)은 암호화 후 읽기 어렵게 바뀐 데이터다. 암호화(encryption)는 평문과 키(key)를 알고리즘에 넣어 암호문을 만드는 과정이고 복호화(decryption)는 올바른 키를 이용해 평문을 되찾는 과정이다. 키는 문을 여는 실제 열쇠에 해당하며, 현대 암호에서는 알고리즘 자체가 공개되어도 키가 비밀이면 안전해야 한다고 본다.
TERMS FROM ZERO
전문 용어를 한 단어씩 풀기
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Plaintext
암호화하기 전의 원래 메시지입니다. 사람이 읽는 문장뿐 아니라 파일의 byte도 plaintext가 될 수 있습니다.
Ciphertext
암호화 결과입니다. 숨겨진 원문과 같은 말이 아니라, key 없이는 원문을 알아내기 어려워야 하는 출력입니다.
Key
암호 알고리즘의 동작을 결정하는 값입니다. 알고리즘 자체가 아니라 key를 비밀로 관리하는 것이 현대 암호의 기본입니다.
Encryption / Decryption
Encryption은 plaintext를 ciphertext로, decryption은 올바른 key로 ciphertext를 다시 plaintext로 바꾸는 과정입니다.
프로그램이나 프로토콜 안에서는 다음 순서로 움직입니다.
- 누가 평문을 가지고 있는지 확인한다.
- 어떤 키로 암호화하고 누가 복호화 키를 가지는지 확인한다.
- 암호문이 노출되어도 공격자가 어떤 정보를 얻지 못해야 하는지 적는다.
왜 여기서 많이 틀릴까요?
암호화는 기본적으로 내용을 숨긴다. 누가 보냈는지, 내용이 바뀌지 않았는지, 서비스가 계속 동작하는지까지 저절로 보장하지는 않는다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
기초 개념 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
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다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
핵심부터 말하면 공개키 (e,n)=(3,55)를 RSA 암호화식 c=m^e mod n에 대입하면 c=4³ mod55=64 mod55=9다.
이 글에서 익힐 것
RSA 공개키 튜플에서 e와 n의 위치를 읽는다.
평문 m, 암호문 c, public exponent e, modulus n을 구분한다.
modular exponentiation을 단계별로 계산한다.
나머지 계산을 검산한다.
시험의 textbook RSA 계산과 실제 안전한 RSA 사용을 구분한다.
개념부터 차근차근
-
공개키 (e,n)
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 단계는 끝난 상태다.
-
암호화 공식
public key로 c=m^e mod n을 계산한다. 거듭제곱을 먼저 생각하고 n으로 나눈 나머지만 남긴다. 그 결과 c도 0부터 n−1 범위의 정수다.
-
Modulo는 몫을 버리고 나머지를 취함
64 mod55에서 64=1·55+9이므로 나머지는 9다. 64−55=9처럼 modulus를 한 번 빼도 계산할 수 있다.
Given values
Symbol
m
Value
4
Meaning
Nachricht/Klartext
Symbol
e
Value
3
Meaning
공개 암호화 지수
Symbol
n
Value
55
Meaning
RSA modulus
Symbol
c
Value
구할 값
Meaning
Ciphertext
단계별로 따라가기
RSA 암호화식을 쓴다: c=m^e mod n.
값을 대입한다: c=4³ mod55.
거듭제곱을 계산한다: 4³=4·4·4=16·4=64.
64를 55로 나눈 나머지를 계산한다: 64=1·55+9.
따라서 c=9다.
시험 답안으로 정리하기
Recommended lines
c = m^e mod n
= 4^3 mod 55
= 64 mod 55
= 9
왜 그런지 이해하기
공식, 대입, 거듭제곱, modulo 결과가 모두 보여 Rechenweg 점수를 잃지 않는다. 답만 9라고 쓰면 결과가 맞아도 과정 점수를 놓칠 수 있다.
Optional reverse check
n=55=5·11이고 φ(55)=(5−1)(11−1)=40이다.
e=3의 modulo40 inverse는 d=27이다. 3·27=81≡1 mod40이다.
복호화 검산은 m'=c^d mod n=9^27 mod55다.
반복 제곱으로 9²=81≡26, 9⁴≡26²=676≡16, 9⁸≡16²=256≡36, 9¹⁶≡36²=1296≡31 mod55다.
9²⁷=9^(16+8+2+1)≡31·36·26·9 mod55=4가 되어 원래 m=4로 돌아온다.
이 역검산은 문제 답안에 필수는 아니지만 학습 시 public/private exponent 관계를 확인하는 데 좋다.
Efficient modular exponentiation
이번에는 e=3이라 직접 4·4·4를 계산하면 된다.
지수가 크면 전체 거듭제곱을 만든 뒤 나누지 않고 square-and-multiply를 쓴다.
중간 단계마다 mod n을 취해도 최종 나머지는 같다: (ab mod n)=((a mod n)(b mod n)) mod n.
예: m^13은 13=8+4+1로 분해해 m,m²,m⁴,m⁸을 반복 제곱하고 필요한 것만 곱한다.
Security context
문제의 계산은 deterministic textbook RSA다. 같은 public key로 같은 m=4를 암호화하면 항상 c=9가 나온다.
따라서 공격자가 두 후보를 직접 암호화해 challenge와 비교할 수 있어 textbook RSA는 IND-CPA secure가 아니다.
실제 RSA encryption은 OAEP 같은 randomized padding/encoding을 사용한다. 여기서 padding은 단순 길이 채우기뿐 아니라 구조와 randomness를 제공한다.
작은 n=55는 교육용이라 즉시 factorization된다. 실제 키는 훨씬 큰 modulus를 쓴다.
문제를 푸는 순서
1단계: (3,55)를 (e,n)으로 표시한다.
2단계: m=4가 0≤m<n인지 확인한다.
3단계: c=m^e mod n 공식을 쓴다.
4단계: 4³=64를 계산한다.
5단계: 64 mod55=9를 계산하고 Ciphertext c=9라고 단위를 붙인다.
시험장에서는 이렇게 쓰기
German
Für RSA gilt c=m^e mod n. Also c=4^3 mod55=64 mod55=9. Der Ciphertext ist c=9.
Minimal with work
c=4³ mod55=64 mod55=9.
자주 틀리는 지점
공개키 (3,55)를 p=3,q=55로 해석하는 것.
private exponent d를 사용해 암호화하는 것. 이 문제의 암호화는 public exponent e=3을 쓴다.
c=e^m mod n=3⁴ mod55로 지수와 밑을 바꾸는 것.
4·3=12를 계산하는 것. m^e는 곱셈이 아니라 거듭제곱이다.
4³=64까지만 쓰고 modulo55를 하지 않는 것.
64/55의 몫 1을 답으로 쓰는 것. mod는 나머지 9다.
시험용 계산을 보고 실제 RSA도 raw integer를 그대로 암호화한다고 생각하는 것. 실제로는 OAEP 같은 안전한 encoding이 필요하다.
한 줄로 기억하기
RSA 암호화는 '메시지를 공개 지수만큼 올리고, n 울타리를 넘어간 만큼 modulo로 접는다': c=m^e mod n.
스스로 확인하기
-
공개키 (3,55)에서 e와 n은 각각?
e=3, n=55.
-
4³은 얼마인가?
64.
-
64 mod55는 왜 9인가?
64=1·55+9이므로 나머지가 9다.
-
이 계산이 매번 같은 c를 내는 이유는?
textbook RSA 식이 randomness 없는 deterministic 함수이기 때문이다.
-
실제 RSA encryption에서 사용하는 대표적 randomized encoding은?
RSA-OAEP.
설명의 근거
Gedächtnisprotokoll Computersystemsicherheit WS2025_26.md, Krypto / Asymmetrische Kryptographie, 3-(d), 4 Punkte.
Vorlesung 04 Asymmetrische Kryptographie, p.11-16 — RSA encryption/decryption 공식.
CSS Exam SoSe22, p.9-10 — RSA 암호화 계산과 Rechenweg 형식.
예제로 확인하기
-
암호화의 가장 기본적인 등장인물을 구체적인 순서로 보기
누구나 자물쇠의 설계도를 볼 수 있지만 실제 열쇠가 없으면 열지 못하는 자물쇠를 생각하면 된다. 설계도를 숨기는 것이 아니라 열쇠를 관리하는 것이 핵심이다.
누가 평문을 가지고 있는지 확인한다.
어떤 키로 암호화하고 누가 복호화 키를 가지는지 확인한다.
암호문이 노출되어도 공격자가 어떤 정보를 얻지 못해야 하는지 적는다.
각 단계에서 입력이나 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가 어떻게 달라지는지 확인한 뒤 현재 문제의 조건과 결론에 연결합니다.
-
Modulo, 경우의 수, key space를 처음부터 계산하기을 구체적인 순서로 보기
시계에서 15시는 3시로 돌아오는 것이 modulo다. 자물쇠 번호가 9칸이고 각 칸에 26개 문자를 넣을 수 있다면 첫 칸 26가지마다 둘째 칸도 26가지가 붙으므로 선택지가 계속 곱해진다.
mod n의 결과 범위가 0부터 n-1임을 확인한다.
각 자리가 독립적으로 선택되는지 확인한다.
선택지 수를 자리 수만큼 곱하고 거듭제곱으로 적는다.
Modulo 산술과 block mode의 데이터 의존성은 별개의 문제임을 기억한다.
각 단계에서 입력이나 message가 어떻게 달라지는지 확인한 뒤 현재 문제의 조건과 결론에 연결합니다.
이 문제가 어려운 이유
짧은 문제 문장 ‘öffentlicher Schlüssel (3,55)를 사용해 RSA로 Nachricht m=4를 verschlüsseln하고 Rechenweg를 쓰라.’ 안에 정의, 조건, 처리 순서가 압축되어 있습니다. 아래 예시에서는 이를 한 단계씩 펼쳐 확인합니다.
AI 구두시험용 프롬프트
한 문항만 풀어라. 먼저 정답을 열지 말고 90초 안에 답안을 말한 뒤, css-ws2025-26-crypto-asym-004의 채점 프레임으로 스스로 채점하라. 문제: öffentlicher Schlüssel (3,55)를 사용해 RSA로 Nachricht m=4를 verschlüsseln하고 Rechenweg를 쓰라.
학습 기록