14. 암호학 계산 문제와 복습

암호 알고리즘을 이해하려면 정의를 읽는 것과 함께 직접 계산해 보는 과정이 필요하다. 키 재사용의 문제부터 AES의 바이트 연산, RSA와 전자서명까지 대표적인 문제로 확인해 보자.

1. 대칭키 암호와 RSA 연습

문제 1: CIA Triad

정보보호의 세 가지 목표는 무엇이며, 각각 무엇을 보호하는가?

기밀성(Confidentiality)은 허가되지 않은 정보 열람을 막고, 무결성(Integrity)은 허가되지 않은 변경을 막는다. 가용성(Availability)은 정당한 사용자가 필요한 자원을 제때 이용할 수 있게 하는 성질이다.

문제 2: One-Time Pad(OTP)

비밀키 KiK_i와 평문 MM을 XOR하여 암호문 CiC_i를 만드는 OTP에서 키스트림 재사용 시 메시지 관계가 드러나는지 분석한다.

C1=M1⊕K1,C2=M2⊕K2C_1=M_1\oplus K_1,\qquad C_2=M_2\oplus K_2

독립적인 한 번짜리 키라면 각각 완전비밀성 조건을 만족한다. 그러나 동일한 키를 공유하여 재사용했다면 C1⊕C2=M1⊕M2C_1\oplus C_2=M_1\oplus M_2이고, 알려진 한 평문에서 다른 평문을 복원할 수 있다. 세 메시지에 각각 K2K_2, K3K_3, K2⊕K3K_2\oplus K_3를 사용하면 다음과 같다.

C1=M1⊕K2,C2=M2⊕K3,C3=M3⊕K2⊕K3.C_1=M_1\oplus K_2,\quad C_2=M_2\oplus K_3,\quad C_3=M_3\oplus K_2\oplus K_3.

세 암호문을 XOR하면 키 항이 모두 소거된다.

C1⊕C2⊕C3=M1⊕M2⊕M3.C_1\oplus C_2\oplus C_3=M_1\oplus M_2\oplus M_3.

공격자는 암호문만으로 세 평문의 관계를 알 수 있으므로, 세 메시지를 함께 보았을 때 완전비밀성이 성립하지 않는다.

문제 3: Feistel Round

Feistel 구조의 한 라운드에서 왼쪽과 오른쪽 블록이 어떻게 바뀌는지 식으로 표현해 보자.

Li=Ri−1,Ri=Li−1⊕F(Ri−1,Ki).L_i=R_{i-1},\qquad R_i=L_{i-1}\oplus F(R_{i-1},K_i).

Feistel 구조에서 F는 역함수가 없어도 복호화할 수 있으며, 복호화는 역순 키를 적용한다.

문제 4: PRNG 기반 XOR 암복호화

PRNG(K)PRNG(K)로 생성한 난수열 R을 이용할 때

C=M⊕R,M=C⊕RC=M\oplus R,\qquad M=C\oplus R

을 도식화한다. 송수신자가 동일한 키스트림을 생성할 수 있어야 한다.

문제 5: Triple DES

DES의 암호화 EE와 복호화 DD로 EDE 암호화/복호화를 나타내고, 세 키가 같은 경우 DES와 같아지는지 확인한다.

C=EK3(DK2(EK1(M)))C=E_{K_3}(D_{K_2}(E_{K_1}(M))) M=DK1(EK2(DK3(C))).M=D_{K_1}(E_{K_2}(D_{K_3}(C))).

문제 6: DES와 AES 비교

요구 사항DESAES
Block size64비트128비트
Key size유효 56비트128/192/256비트
Rounds1610/12/14
Round structureFeistelSPN
Round key size48비트128비트

AES의 SubBytes, ShiftRows, MixColumns, AddRoundKey와 DES의 Expansion, XOR, Substitution, Permutation 절차도 설명할 수 있어야 한다.

문제 7: AES SubBytes와 ShiftRows

AES 계산 문제 7의 입력과 풀이 주어진 4x4 바이트 State에 S-box를 적용하고 ShiftRows를 적용하는 문제다.

풀이 원칙

  1. 각 바이트의 상위 16진수 한 자리는 S-box의 행, 하위 한 자리는 열

  2. 네 행을 각각 왼쪽으로 0, 1, 2, 3바이트 회전

  3. 바이트를 십진수로 읽지 않고 16진수 바이트 표기를 유지

문제 8: AES 유한체와 MixColumns

AES 계산 문제 8의 입력과 풀이 먼저 GF(28)GF(2^8)의 법 다항식에 대응하는 비트열을 쓰고, 그 체 위에서 MixColumns 행렬 곱셈 일부를 계산한다.

P(X)=X8+X4+X3+X+1,02⊗x=xtime⁡(x).P(X)=X^8+X^4+X^3+X+1,\quad 02\otimes x=\operatorname{xtime}(x). (02030101010203010101020303010102)\begin{pmatrix} 02&03&01&01\\ 01&02&03&01\\ 01&01&02&03\\ 03&01&01&02 \end{pmatrix}

계산은 다항식 곱셈 후 P(X)P(X)에 대한 나머지를 취한다. 자리올림 없는 XOR 연산과 기약다항식에 의한 환원 과정을 차례로 적는 방식으로 풀이한다.

문제 9: Left-to-Right Modular Exponentiation

g117 mod pg^{117}\bmod p를 Left-to-Right 방법으로 계산하기 위한 경로를 쓰고 모듈러 곱셈 횟수를 구하는 문제.

117=(1110101)2=64+32+16+4+1.117=(1110101)_2=64+32+16+4+1.

첫 1비트에서 초기화하는 left-to-right 방식에서는 제곱 6회와 일반 곱셈 4회, 총 10회가 필요하다. ‘전체 7비트의 각 반복에서 1번씩 곱한다’는 구현과는 연산 횟수 계산 관례가 다를 수 있으니 초기화 방식과 연산 횟수의 기준을 명시해야 한다.

문제 10: OFB Mode

OFB의 암호화/복호화 그림과 수식을 직접 그리는 문제.

Z0=IV,Zi=EK(Zi−1),Ci=Pi⊕Zi,Pi=Ci⊕Zi.Z_0=IV,\quad Z_i=E_K(Z_{i-1}),\quad C_i=P_i\oplus Z_i,\quad P_i=C_i\oplus Z_i.

OFB의 피드백은 CFB와 달리 암호문이 아니라 이전 암호화 함수 출력이다.

문제 11: Public Key Encryption과 IND-CPA

PKE를 구성하는 세 알고리즘을 정의하고, 결정적 공개키 암호가 IND-CPA 안전성을 만족할 수 없는 이유를 설명해 보자.

(pk,sk)=KeyGen(λ),C=Enc(pk,M),M=Dec(sk,C).(pk,sk)=KeyGen(\lambda),\quad C=Enc(pk,M),\quad M=Dec(sk,C).

공격자가 공개키로 후보 M0,M1M_0,M_1을 직접 암호화할 수 있으므로 결정적 암호화에서는 challenge ciphertext와 비교해서 어느 메시지인지 맞힐 수 있다.

문제 12: RSA 계산 전체

p=11,q=13,N=143,e=37,C=2p=11,q=13,N=143,e=37,C=2에 대해 φ(N)\varphi(N), d, 평문 M을 계산한다.

φ(143)=(11−1)(13−1)=120.\varphi(143)=(11-1)(13-1)=120.

확장 유클리드:

120=3⋅37+9,37=4⋅9+1.120=3\cdot37+9,\quad37=4\cdot9+1. 1=37−4(120−3⋅37)=13⋅37−4⋅120.1=37-4(120-3\cdot37)=13\cdot37-4\cdot120. d=13,M=213 mod 143=41.d=13,\qquad M=2^{13}\bmod143=41.

검산: 37⋅13=481≡1(mod120)37\cdot13=481\equiv1\pmod{120}, 213=8192≡41(mod143)2^{13}=8192\equiv41\pmod{143}.

2. 공개키 암호, 서명과 인증 연습

문제 1: RSA-OAEP Decoding

RSA 개인키 d로 암호문 CTCT에서 인코딩된 메시지 EMEM을 얻은 후, 두 단계 mask 제거를 통해 원래 Message를 복원해야 한다.

  1. EM=CTd mod NEM=CT^d\bmod N 계산

  2. EMEM에서 maskedSeed, maskedDB를 위치에 따라 분리

  3. seedMask=MGF(maskedDB)seedMask=MGF(maskedDB)

  4. Seed=maskedSeed⊕seedMaskSeed=maskedSeed\oplus seedMask

  5. dbMask=MGF(Seed)dbMask=MGF(Seed)

  6. DB=maskedDB⊕dbMaskDB=maskedDB\oplus dbMask

  7. Label 해시, padding, 0x01 구분자를 검증해 메시지 M 추출

주의: MGF의 입력과 출력 길이를 구분하고, 디코딩 후 패딩 구조와 해시를 모두 검증해야 한다.

문제 2: Diffie-Hellman, MITM, Authentication

DH 공개값과 공유 비밀, 중간자 공격, 방어 방법까지 단계별로 묻는다.

A=ga mod p,B=gb mod pA=g^a\bmod p,\qquad B=g^b\bmod p K=Ba=Ab=gab mod p.K=B^a=A^b=g^{ab}\bmod p.

MITM 공격에서는 Eve가 Alice와 Bob에게 자신의 공개값을 대신 전달하므로 Alice, Bob은 서로가 아닌 Eve와 각각 다른 키를 공유한다. 방어 예시는 서명과 공개키 검증을 이용한 당사자 인증이다.

문제 3: ElGamal 암호와 Additive Notation

(a) 암호문 복호화의 실제 계산: p=23,g=5,h=17,x=7,C=(2,7)p=23,g=5,h=17,x=7,C=(2,7)라고 주어진다.

M=C2/(C1x) mod p=7/(27) mod 23.M=C_2/(C_1^x)\bmod p =7/(2^7)\bmod23. 27=128≡13(mod23),13−1≡16(mod23).2^7=128\equiv13\pmod{23},\quad13^{-1}\equiv16\pmod{23}. M=7⋅16=112≡20(mod23).M=7\cdot16=112\equiv20\pmod{23}.

(b) 임의 길이 비트 메시지로 확장: M∈{0,1}∗M\in\{0,1\}^*일 때 해시 함수 H:G→{0,1}∣M∣H:G\to\{0,1\}^{|M|}를 쓰는 구성은

C1=gr,C2=M⊕H(hr)C_1=g^r,\quad C_2=M\oplus H(h^r) M=C2⊕H(C1x).M=C_2\oplus H(C_1^x).

(c) ECC 등 Additive Group에서도 구성 가능: 표현을 곱셈에서 덧셈으로 바꾸면 표기 grg^r 대신 rGrG, hrh^r 대신 rHrH를 이용한다. 유한체 크기 대비 키와 암호문 길이가 작아질 수 있다는 장점이 있다.

문제 4: RSA Signature, Forgery, PSS

RSA Sign 및 Verify, textbook RSA Signature existential forgery, EMSA-PSS의 인코딩 및 서명 검증 절차까지 묻는다.

σ=Md mod N,Verify(pk,M,σ)=[σe≡M(modN)].\sigma=M^d\bmod N,\quad Verify(pk,M,\sigma)=[\sigma^e\equiv M\pmod N].

Existential forgery: 임의 σ\sigma를 고르고 M=σe mod NM=\sigma^e\bmod N이라 하면 검증에 성공한다. 즉 raw RSA 서명은 안전하지 않다. PSS에서는 Salt, Hash, MGF, DB, maskedDB, trailer를 구분해야 한다. 서명 생성 결과로부터 EMEM을 추출하고 인코딩 구조 및 해시 일치성을 검증한다.

문제 5: Elliptic Curve에서 실제 점 계산

유한체 F7\mathbb F_7 위 곡선 E:y2=x3+2E:y^2=x^3+2에 대해 점들을 나열하고 P+QP+Q, 2P2P를 구한다. 곡선 점:

E(F7)={O,(0,3),(0,4),(3,1),(3,6),(5,1),(5,6),(6,1),(6,6)}.E(\mathbb F_7)=\{\mathcal O,(0,3),(0,4),(3,1),(3,6),(5,1),(5,6),(6,1),(6,6)\}.

(b) P=(3,1),Q=(5,6)P=(3,1),Q=(5,6)

s=(6−1)/(5−3)=5⋅2−1≡5⋅4≡6(mod7)s=(6-1)/(5-3)=5\cdot2^{-1}\equiv5\cdot4\equiv6\pmod7 x3=s2−3−5=28≡0,y3=s(3−0)−1=17≡3(mod7).x_3=s^2-3-5=28\equiv0,\quad y_3=s(3-0)-1=17\equiv3\pmod7.

따라서 P+Q=(0,3)P+Q=(0,3).

(c) 2P2P

s=(3xP2)/(2yP)=27/2≡6⋅4=3(mod7)s=(3x_P^2)/(2y_P)=27/2\equiv6\cdot4=3\pmod7 x3=32−2⋅3=3,y3=3(3−3)−1≡6(mod7).x_3=3^2-2\cdot3=3,\quad y_3=3(3-3)-1\equiv6\pmod7.

따라서 2P=(3,6)2P=(3,6)이다.

문제 6: Cryptographic Hash Properties

(a) Collision Resistance: 서로 다른 두 메시지로

x≠x′,h(x)=h(x′)x\ne x',\quad h(x)=h(x')

를 찾기 어려워야 한다.

(b) 반례: h:{0,1}∗→{0,1}8h:\{0,1\}^*\to\{0,1\}^8가 입력의 마지막 비트만 출력하고 나머지는 0으로 패딩한다고 하자. 이 함수가 충돌 저항성을 갖지 않는 이유는 입력이 달라도 마지막 비트가 같으면 결과가 동일하기 때문이다. 예를 들어 마지막 비트가 모두 0인 두 입력을 쉽게 찾을 수 있다.

문제 7: CBC-MAC

CBC Mode를 이용하여 마지막 암호문 블록을 태그로 만드는 CBC-MAC 생성 알고리즘과 검증 과정을 묻는다.

Y0=IV,Yi=EK(Mi⊕Yi−1),tag=Yn.Y_0=IV,\qquad Y_i=E_K(M_i\oplus Y_{i-1}),\qquad tag=Y_n.

검증자는 공유키로 같은 연산을 다시 수행하고 전달받은 태그와 비교한다. 일반 IV 표기를 사용하지만, 안전한 기본 CBC-MAC에서는 고정 IV(보통 0), 고정 길이 메시지 가정 등이 중요하다.

3. 추가 복습

문제출제 주제핵심 풀이 또는 확인사항
1컴퓨터 보안 및 DES/AES/RC4의 T/F기밀성 vs 무결성, DES와 AES 구조, ECB/CBC/CFB/OFB
2Permutation 및 Substitution Cipher문자 값 치환과 위치 순열을 구별
3Affine Cipher의 키 a,b 복원두 평문/암호문 쌍의 연립합동식
4OTP의 Perfect Secrecy균등 무작위, 키 1회 사용, 메시지 길이의 키
5Symmetric vs Public-Key키 종류, 키 공유, 속도, 키 개수
6Block Cipher vs Stream Cipher블록 단위와 요소 단위 처리
7Feistel Round의 도식과 복호화좌우 교환, XOR, 라운드 키 역순
8DES S-box 입력에서 4비트 출력바깥 2비트 = row, 가운데 4비트 = col
9Right-to-Left Modular Exponentiation지수의 이진 비트, 제곱 및 곱셈 횟수
10AES SubBytes 및 ShiftRows4x4 State 처리, S-box lookup
11AES GF(28)GF(2^8)와 MixColumns모듈러 다항식, Shift/XOR와 reduction
12LFSR 키스트림과 XOR 복호화점화식으로 12비트 생성, 암호문 XOR
13CTR Mode 암복호화 및 장점Counter 블록 암호화, 병렬/사전 계산
14RSA 비밀 지수와 인수분해N=pqN=pq, Euler 함수, 모듈러 역원

문제 1: 참과 거짓 판별

주장판정과 이유
암호화만으로 데이터 무결성을 보장한다.거짓. 기밀성과 무결성은 별개의 목표다.
DES의 각 라운드는 같은 구조를 사용한다.참. 같은 Feistel 라운드 구조에 서로 다른 라운드 키를 넣는다.
AES의 모든 라운드는 같은 구조다.거짓. 마지막 라운드에는 MixColumns가 없다.
RC4와 ChaCha는 스트림 암호다.참. 다만 암호의 분류와 실제 사용 시의 안전성은 구별해야 한다.
ECB, CBC, OFB는 모두 키스트림을 XOR하는 방식이다.거짓. OFB는 키스트림을 생성하지만 ECB와 CBC는 평문 블록을 블록암호에 입력한다.

문제 2: 위치 순열과 문자 치환

알파벳 집합을 A={1,2,3,4,5}A=\{1,2,3,4,5\}로 두고 순열을 다음처럼 정의하자.

π(1)=2,π(2)=4,π(3)=5,π(4)=3,π(5)=1.\pi(1)=2,\quad\pi(2)=4,\quad\pi(3)=5,\quad\pi(4)=3,\quad\pi(5)=1.

위치 순열 암호에서 yi=xπ(i)y_i=x_{\pi(i)}라는 규칙을 사용하면 평문 24531은 x2x4x5x3x1x_2x_4x_5x_3x_1, 즉 43152가 된다. 반면 문자 치환은 각 문자에 π\pi를 적용하므로 평문 12345가 24531이 된다. 순열의 표가 같아도 위치를 바꾸는지, 문자 값을 바꾸는지에 따라 계산이 달라진다.

문제 3: Affine Cipher 복습 예시

선택 평문 N과 O가 각각 T와 Y에 대응한다면

13a+b≡19(mod26),14a+b≡24(mod26).13a+b\equiv19\pmod{26},\qquad14a+b\equiv24\pmod{26}.

빼면 a≡5(mod26)a\equiv5\pmod{26}, 따라서 b≡19−13⋅5≡6(mod26)b\equiv19-13\cdot5\equiv6\pmod{26}. **키는 (5,6)**이다. 정합성: gcd⁡(5,26)=1\gcd(5,26)=1.

문제 8: DES S-box의 행과 열

입력 비트의 첫 비트와 마지막 비트로 행을 정하고, 가운데 네 비트로 열을 정한다. 행과 열은 0부터 센다. S-box S4S_4는 다음과 같다.

행\열  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
0      7 13 14  3  0  6  9 10  1  2  8  5 11 12  4 15
1     13  8 11  5  6 15  0  3  4  7  2 12  1 10 14  9
2     10  6  9  0 12 11  7 13 15  1  3 14  5  2  8  4
3      3 15  0  6 10  1 13  8  9  4  5 11 12  7  2 14
  • 입력 101000: 행은 102=210_2=2, 열은 01002=40100_2=4. 출력은 12=1100212=1100_2다.
  • 입력 001110: 행은 002=000_2=0, 열은 01112=70111_2=7. 출력은 10=1010210=1010_2다.

문제 9: Right-to-Left 거듭제곱

g213 mod pg^{213}\bmod p를 계산해 보자. 지수를 이진수로 쓰면 213=110101012=128+64+16+4+1213=11010101_2=128+64+16+4+1이다. 낮은 비트부터 처리할 때 누적값은 다음처럼 바뀐다. 모든 연산은 pp로 나눈 나머지로 수행한다.

1→g→g5→g21→g85→g213.1\to g\to g^5\to g^{21}\to g^{85}\to g^{213}.

처음의 1×g1\times g를 대입으로 처리하고 마지막 비트 이후의 불필요한 제곱을 생략하면, 제곱 7회와 누적 곱셈 4회로 총 11회의 모듈러 곱셈이 필요하다. 초기값과 반복문의 범위가 다른 구현에서는 연산 횟수도 달라질 수 있다.

문제 10: AES SubBytes와 ShiftRows

다음 State에 SubBytes와 ShiftRows를 차례로 적용하자. 행렬의 모든 값은 16진수 바이트다.

[D2600DE7157ABC686339E901C3031EFB]→SubBytes[B5D0D79459DA6545FB121E7C2E7B720F].\begin{bmatrix} \text{D2}&\text{60}&\text{0D}&\text{E7}\\ \text{15}&\text{7A}&\text{BC}&\text{68}\\ \text{63}&\text{39}&\text{E9}&\text{01}\\ \text{C3}&\text{03}&\text{1E}&\text{FB} \end{bmatrix} \xrightarrow{\mathrm{SubBytes}} \begin{bmatrix} \text{B5}&\text{D0}&\text{D7}&\text{94}\\ \text{59}&\text{DA}&\text{65}&\text{45}\\ \text{FB}&\text{12}&\text{1E}&\text{7C}\\ \text{2E}&\text{7B}&\text{72}&\text{0F} \end{bmatrix}.

ShiftRows는 첫 번째 행을 그대로 두고 나머지 행을 각각 왼쪽으로 1, 2, 3바이트 순환 이동한다.

[B5D0D794DA6545591E7CFB120F2E7B72].\begin{bmatrix} \text{B5}&\text{D0}&\text{D7}&\text{94}\\ \text{DA}&\text{65}&\text{45}&\text{59}\\ \text{1E}&\text{7C}&\text{FB}&\text{12}\\ \text{0F}&\text{2E}&\text{7B}&\text{72} \end{bmatrix}.

문제 11: 유한체 환원과 MixColumns

AES의 기약다항식은 P(X)=X8+X4+X3+X+1P(X)=X^8+X^4+X^3+X+1이다. 따라서 X8X^8의 나머지는 X4+X3+X+1X^4+X^3+X+1이며, 바이트 표현은 00011011, 즉 1B다.

다음 State에 MixColumns를 적용한 결과의 (2,2)(2,2) 성분을 구하자. 여기서는 행과 열을 1부터 센다.

[D6D3A39764E89204082EB5DD2B8ED576].\begin{bmatrix} \text{D6}&\text{D3}&\text{A3}&\text{97}\\ \text{64}&\text{E8}&\text{92}&\text{04}\\ \text{08}&\text{2E}&\text{B5}&\text{DD}\\ \text{2B}&\text{8E}&\text{D5}&\text{76} \end{bmatrix}.

두 번째 행의 계수는 (01,02,03,01)(01,02,03,01)이므로 두 번째 열과 곱하면 다음과 같다. 곱셈은 GF(28)GF(2^8)의 연산이다.

D3⊕(02⋅E8)⊕(03⋅2E)⊕8E=D3⊕CB⊕72⊕8E=E4.\text{D3}\oplus(02\cdot\text{E8})\oplus(03\cdot\text{2E})\oplus\text{8E} =\text{D3}\oplus\text{CB}\oplus\text{72}\oplus\text{8E} =\boxed{\text{E4}}.

02⋅E802\cdot\text{E8}에서는 왼쪽 이동으로 넘친 최고 비트를 제거한 뒤 1B를 XOR해 CB를 얻는다. 03⋅2E=(02⋅2E)⊕2E=5C⊕2E=7203\cdot\text{2E}=(02\cdot\text{2E})\oplus\text{2E}=\text{5C}\oplus\text{2E}=\text{72}다.

문제 12: LFSR 키스트림과 복호화

점화식과 초기 비트가 다음과 같다고 하자.

si+4=si+1⊕si,(s0,s1,s2,s3)=(1,0,0,0).s_{i+4}=s_{i+1}\oplus s_i,\qquad(s_0,s_1,s_2,s_3)=(1,0,0,0).

초기 비트를 포함해 12비트를 생성하면 1000 1001 1010이다. 암호문이 1110 0011 1100이면 같은 길이의 키스트림을 XOR한다.

암호문    1110 0011 1100
키스트림  1000 1001 1010
평문      0110 1010 0110

문제 14: RSA 비밀 지수 계산

N=667=23⋅29N=667=23\cdot29이고 공개 지수가 e=59e=59라면 φ(N)=22⋅28=616\varphi(N)=22\cdot28=616이다. 비밀 지수 dd는 59d≡1(mod616)59d\equiv1\pmod{616}을 만족해야 한다.

확장 유클리드 알고리즘으로 1=25⋅616−261⋅591=25\cdot616-261\cdot59를 얻으므로

d≡−261≡355(mod616).d\equiv-261\equiv\boxed{355}\pmod{616}.

실제로 59⋅355=20945=34⋅616+159\cdot355=20945=34\cdot616+1이다.

확장: RSA에서 φ(N)\varphi(N)과 소인수분해

서로 다른 두 소수의 곱인 RSA 모듈러스 N과 φ(N)\varphi(N)이 함께 주어졌다고 하자. 이 두 값으로 p와 q를 구할 수 있다.

p+q=N−φ(N)+1p+q=N-\varphi(N)+1

왜냐하면 φ(N)=(p−1)(q−1)=pq−p−q+1\varphi(N)=(p-1)(q-1)=pq-p-q+1이기 때문이다. 따라서 p,q는 다음 이차방정식의 근이다.

t2−(N−φ(N)+1)t+N=0.t^2-(N-\varphi(N)+1)t+N=0.

판별식이 제곱수가 되어야 하며, 두 근이 소수인지 검산한다.

4. 연습할 계산 유형

  1. Affine/Shift/Permutation: 숫자와 문자의 치환 및 알려진 평문 공격.

  2. DES/Feistel: 라운드 식과 S-box row/column 선택.

  3. AES: SubBytes, ShiftRows, MixColumns의 중간 행렬과 비트 계산.

  4. GF(28)GF(2^8): 기약다항식 환원 및 역원.

  5. Modular Exponentiation: Left-to-Right/Right-to-Left 알고리즘의 곱셈 횟수.

  6. RSA: Euler, Euclidean, modular inverse, KeyGen, Enc/Dec, OAEP.

  7. DH/ElGamal: 공유 비밀, MITM, 인증, 모듈러 역원 복호화.

  8. ECDSA/ECC: Point Addition, Doubling, x좌표와 mod.

  9. Hash/MAC: collision resistance와 MAC 검증 알고리즘.

Discussion

Comments