계산
문제
독일어 원문
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, φ(n), e und d. Die Werte e = 1, d = 1 sind hierbei ausgeschlossen.
한국어 해석
p = 7, q = 7인 RSA에서 gültiges Schlüsselpaar ((e,n),(d,n))를 구하라. 풀이 과정 없이 n, φ(n), e, d만 쓰며 e=1,d=1은 제외한다.
RSA 계산 스테퍼
각 단계의 값을 직접 계산하세요.
단계별 힌트
막혔을 때만 한 단계씩 여세요. 정답을 바로 읽는 것보다 기억을 꺼내는 시간이 중요합니다.
- 첫 힌트: 여기서는 계산보다 먼저 p와 q가 같다는 점이 문제인지 확인하라.
- n=pq=7×7=49
- φ(7²)=7²-7=42
- 42=2×3×7이므로 2·3·7 중 어느 것으로도 나누어지지 않는 작은 수 e=5를 고른다: gcd(5,42)=1
- d는 5d=1+42k로 찾는다. k=1이면 43은 5로 나누어지지 않고, k=2이면 85÷5=17이므로 d=17
- 검산: 5×17=85=2×42+1, 따라서 5×17≡1 (mod 42)
- 함정: 복기를 p=7,q=11처럼 고쳐 풀기
- 함정: p=q인데도 φ(n)=(p-1)(q-1)=36으로 계산하기
- 함정: e=1 또는 d=1을 고르기
- 후속 점검: 왜 강의의 RSA Schlüsselgeneration은 p≠q를 요구하는가?
채점 기준으로 내 답안 점검하기
- n=49를 쓴다.
- p=q이므로 φ(49)=42를 쓴다.
- gcd(e,42)=1이고 e≠1인 값을 고른다.
- ed≡1 (mod 42)이고 d≠1인 역원을 쓴다.
답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.
0/4 slots
정답과 핵심 해설 확인하기
한 가지 유효한 답: n=49, φ(n)=42, e=5, d=17.
5×17=85=2×42+1이므로 5×17≡1 (mod 42).
개념부터 다시 보는 상세 풀이
BEGINNER LESSON
3-(c) p=q=7 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다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
핵심부터 말하면 표준 RSA key generation은 서로 다른 소수 p≠q를 요구하므로 p=q=7로는 문제의 의미에서 gültiges 표준 RSA 키 쌍을 만들 수 없다. 수론 계산만 강제로 하면 n=49, φ(49)=42이고 예를 들어 e=5,d=17은 ed≡1 mod42지만, 이는 단위군 Z*₄₉에서는 작동해도 7의 배수 같은 모든 메시지에는 RSA correctness를 만족하지 않는다.
문제를 읽기 전 주의
복기 원문은 공식 해설이 아닌 기억 기록이며 p=7,q=7을 명시한다. 이를 임의로 q=11 등으로 고치면 안 된다. 강의의 표준 RSA 조건과 충돌하므로 학습 콘텐츠는 '표준 답: 불가능'과 '출제자가 산술값만 기대했을 가능성: 조건부 계산'을 모두 분리해 제시한다.
이 글에서 익힐 것
RSA key generation의 각 공식을 이유와 함께 적용한다.
서로 다른 소수일 때만 φ(pq)=(p−1)(q−1)을 바로 쓸 수 있음을 이해한다.
φ(49)=42를 직접 계산한다.
gcd와 modular inverse로 e,d를 선택한다.
단위군에서의 역지수와 모든 RSA 메시지에 대한 correctness를 구분한다.
문항 자체가 비표준일 때 시험 답안을 안전하게 작성한다.
개념부터 차근차근
Step
1. 서로 다른 소수 선택
Formula
p,q prime and p≠q
Reason
표준 correctness 증명과 φ(n) 공식은 서로 다른 두 소수의 곱을 전제로 한다.
Step
2. modulus
Formula
n=pq
Reason
public key와 private key가 공유하는 modulus다.
Step
3. Euler totient
Formula
φ(n)=(p−1)(q−1), 단 p≠q인 소수
Reason
1≤a<n 중 gcd(a,n)=1인 residue의 개수다.
Step
4. public exponent
Formula
1<e<φ(n), gcd(e,φ(n))=1
Reason
e가 modulo φ(n)에서 inverse를 가져야 한다.
Step
5. private exponent
Formula
d≡e⁻¹ modφ(n), 즉 ed≡1 modφ(n)
Reason
암호화 지수와 복호화 지수가 서로 취소되도록 만든다.
First check parameters
주어진 p=7과 q=7은 각각 소수인 점은 맞다.
그러나 p≠q 조건을 위반한다. n은 서로 다른 두 prime factor의 곱이 아니라 prime square 7²이다.
따라서 표준 공식 (p−1)(q−1)=6×6=36을 사용하면 안 된다.
문제의 'gültiges Schlüsselpaar'를 표준 RSA 정의대로 엄격히 해석하면 이 단계에서 유효한 키 생성이 불가능하다고 지적해야 한다.
단계별로 따라가기
단계별로 따라가기
n=pq=7×7=49
Result
n=49
단계별로 따라가기
prime power의 totient: φ(p²)=p²−p=p(p−1)
Result
φ(49)=49−7=42
단계별로 따라가기
1부터 48 중 7의 배수 7,14,21,28,35,42는 6개
Result
49보다 작은 양의 정수 48개 중 6개를 제외해 42개가 49와 서로소
단계별로 따라가기
e=5 선택: gcd(5,42)=1
Result
mod42 inverse가 존재
단계별로 따라가기
Extended Euclid: 42=8·5+2, 5=2·2+1
Result
1=5−2·2=5−(42−8·5)·2=17·5−2·42
단계별로 따라가기
따라서 5·17=85=2·42+1
Result
d=17, ed≡1 mod42
왜 그런지 이해하기
Wrong reasoning
p와 q가 소수이니 무조건 (p−1)(q−1)=36이라고 대입한다.
Correction
φ(pq)=(p−1)(q−1)은 p와 q가 서로 다른 소수라서 p의 배수와 q의 배수 집합이 별개일 때의 공식이다. p=q이면 같은 배수를 중복 제외하게 되어 공식이 달라진다.
Direct count
1,...,48 중 49와 공약수 7을 갖는 수는 7의 배수 6개뿐이다. 48−6=42이므로 φ(49)=42다.
General formula
φ(p^k)=p^k−p^(k−1)=p^(k−1)(p−1). 따라서 φ(7²)=7(7−1)=42.
Unit group verification
m이 gcd(m,49)=1인 단위(unit)라면 e=5,d=17은 역지수로 동작한다.
ed=85=1+2·42다. Euler theorem에 따라 m^42≡1 mod49이므로 m^85=m·(m^42)²≡m mod49다.
m=2는 49와 서로소다. 암호화 c=2^5 mod49=32이고, 복호화는 32^17 mod49=2로 돌아온다.
이 증명은 gcd(m,49)=1인 m에만 적용된다. 표준 RSA가 모든 residue 메시지를 처리한다는 correctness와 같지 않다.
시험 답안으로 정리하기
m=7을 선택한다. 이는 0≤m<49이지만 gcd(7,49)=7이라 단위가 아니다.
e=5이면 c=7^5 mod49다. 7²=49≡0 mod49이므로 7^5도 0이다.
복호화하면 0^17 mod49=0이다.
원래 m=7이 아니라 0이 나오므로 Dec(Enc(7))≠7이다.
사실 e≥2이면 7^e≡0 mod49가 되어 어떤 d≥1로도 7을 되살릴 수 없다. 따라서 e=1이 제외된 상태에서 모든 Z₄₉ 메시지에 올바른 표준 RSA 쌍은 없다.
시험 답안으로 정리하기
Interpretation
표준 강의 정의를 엄격히 적용
해설
p=q이므로 valid RSA key pair가 존재하지 않는다고 답한다. 이것이 수학적으로 가장 정확하다.
Interpretation
출제자가 prime-square totient와 unit group 산술을 의도
해설
n=49, φ(n)=42, e=5, d=17을 쓰되 'nur für Z*₄₉ / nicht Standard-RSA'라고 조건을 단다.
Interpretation
출제자가 p≠q를 놓치고 기계적으로 공식 적용
해설
φ=36을 기대했을 가능성은 있으나 이는 p=q=7에 대해 수학적으로 틀리다. 학습 콘텐츠에서 오답을 정답처럼 가르치지 않는다.
Interpretation
복기 숫자 오기
해설
가능성은 있지만 공식 원문·해설 없이 q를 임의로 다른 값으로 바꾸지 않는다.
문제를 푸는 순서
1단계: 계산 전에 p와 q가 서로 다른지 검사한다.
2단계: p=q이므로 표준 RSA 조건 위반을 표시한다.
3단계: 보조 산술로 n=49를 계산한다.
4단계: prime-power 공식으로 φ(49)=42를 계산한다. 36을 쓰지 않는다.
5단계: 조건부 unit-group 예시가 필요하면 gcd(e,42)=1인 e=5와 inverse d=17을 고른다.
6단계: m=7 반례로 이것이 모든 메시지에 대한 valid textbook RSA가 아님을 확인한다.
7단계: 답안에 표준 불가능과 조건부 산술을 명확히 분리한다.
시험장에서는 이렇게 쓰기
Mathematically strict german
Mit p=q=7 lässt sich nach der in der Vorlesung verwendeten RSA-Schlüsselerzeugung kein gültiges Standard-RSA-Schlüsselpaar bestimmen, da zwei verschiedene Primzahlen p≠q erforderlich sind. Zwar gilt n=49 und φ(49)=42; beispielsweise erfüllen e=5 und d=17 die Kongruenz ed≡1 (mod 42), aber dieses Paar ist nur auf Z*₄₉ korrekt und nicht für alle Nachrichten modulo 49, etwa nicht für m=7.
Conditional values
Bedingte Rechenwerte: n=49, φ(n)=42, e=5, d=17; Hinweis: kein gültiges Standard-RSA für den vollständigen Nachrichtenraum.
If only boxes exist
n=49; φ(n)=42; e=5; d=17. Daneben unbedingt notieren: p=q verletzt die Standard-RSA-Bedingung p≠q.
채점 포인트
p=q라는 비표준 조건을 발견했는가?
n=49를 계산했는가?
φ(49)=42를 prime-power 공식으로 계산했는가?
e와 42가 서로소인지 확인했는가?
ed≡1 mod42를 확인했는가?
조건부 값과 표준 RSA 유효성을 혼동하지 않았는가?
자주 틀리는 지점
φ(n)=(7−1)(7−1)=36이라고 쓰는 것. 서로 다른 소수일 때의 공식을 잘못 적용한 것이다.
e=5,d=17이 congruence를 만족하므로 모든 m에 자동으로 올바른 RSA라고 결론 내리는 것.
Euler theorem을 gcd(m,n)≠1인 m=7에도 적용하는 것.
복기 오류 가능성을 이유로 q를 마음대로 11 등으로 바꾸는 것.
e와 d를 둘 다 아무 서로소 수로 고르는 것. d는 반드시 e의 modular inverse여야 한다.
문제가 풀이 과정 불필요라고 했으니 학습 과정에서도 이유를 생략하는 것. 실제 시험 제출은 값만이어도 학습 콘텐츠는 함정을 이해해야 한다.
한 줄로 기억하기
RSA 공식 전에 '두 소수가 서로 다른가?'를 먼저 본다. 7×7은 같은 배수를 두 번 세면 안 되므로 φ는 36이 아니라 42, 그러나 같은 소수라 표준 RSA 자체는 실패한다.
스스로 확인하기
-
φ(7²)의 일반 공식과 값은?
φ(p²)=p²−p이므로 φ(49)=49−7=42.
-
5의 modulo 42 inverse가 17인 이유는?
5·17=85=2·42+1이므로 5·17≡1 mod42.
-
m=7에서 e=5 암호화 결과는?
7^5 mod49=0. 따라서 복호화로 7을 복원하지 못한다.
-
n=49에서 e=5,d=17이 올바르게 작동하는 메시지 집합은?
적어도 Euler theorem이 적용되는 단위군 Z*₄₉, 즉 gcd(m,49)=1인 메시지들.
-
표준 RSA key generation의 첫 조건은?
서로 다른 큰 소수 p와 q를 고르는 것.
설명의 근거
Gedächtnisprotokoll Computersystemsicherheit WS2025_26.md, Krypto / Asymmetrische Kryptographie, 3-(c), 8 Punkte — p=7,q=7 복기 표현을 그대로 보존.
Vorlesung 04 Asymmetrische Kryptographie, p.11-14 — RSA key generation에서 p≠q, n, φ(n), e,d 조건.
CSS Exam SoSe22, p.9-10 — RSA key-generation 계산형 문항 형식.
e와 d를 가장 쉽게 고르는 방법
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 관계다.
Candidate
e=2
Result
42와 공약수 2가 있으므로 불가
Candidate
e=3
Result
42와 공약수 3이 있으므로 불가
Candidate
e=4
Result
42와 공약수 2가 있으므로 불가
Candidate
e=5
Result
gcd(5,42)=1이므로 선택
Candidate
k=1
Result
1+42=43, 5로 나누어지지 않음
Candidate
k=2
Result
1+84=85, 85÷5=17 → d=17
먼저 p≠q 확인. 조건부 계산에서는 e는 φ와 겹치지 않는 작은 수, d는 ‘φ의 배수 + 1’을 e로 나눈 값.
예제로 확인하기
-
암호화의 가장 기본적인 등장인물을 구체적인 순서로 보기
누구나 자물쇠의 설계도를 볼 수 있지만 실제 열쇠가 없으면 열지 못하는 자물쇠를 생각하면 된다. 설계도를 숨기는 것이 아니라 열쇠를 관리하는 것이 핵심이다.
누가 평문을 가지고 있는지 확인한다.
어떤 키로 암호화하고 누가 복호화 키를 가지는지 확인한다.
암호문이 노출되어도 공격자가 어떤 정보를 얻지 못해야 하는지 적는다.
각 단계에서 입력이나 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가 어떻게 달라지는지 확인한 뒤 현재 문제의 조건과 결론에 연결합니다.
이 문제가 어려운 이유
짧은 문제 문장 ‘p = 7, q = 7인 RSA에서 gültiges Schlüsselpaar ((e,n),(d,n))를 구하라. 풀이 과정 없이 n, φ(n), e, d만 쓰며 e=1,d=1은 제외한다.’ 안에 정의, 조건, 처리 순서가 압축되어 있습니다. 아래 예시에서는 이를 한 단계씩 펼쳐 확인합니다.
AI 구두시험용 프롬프트
한 문항만 풀어라. 먼저 정답을 열지 말고 90초 안에 답안을 말한 뒤, css-ws2025-26-crypto-asym-003의 채점 프레임으로 스스로 채점하라. 문제: p = 7, q = 7인 RSA에서 gültiges Schlüsselpaar ((e,n),(d,n))를 구하라. 풀이 과정 없이 n, φ(n), e, d만 쓰며 e=1,d=1은 제외한다.
학습 기록