수학기호 및 용어

$$a, |, b$$ : 정수 $$b$$는 정수 $$a$$로 나누어 떨어진다. $$\in$$ : (왼쪽이 오른쪽의) 원소이다. $$\exist$$ : 존재한다. (exist) $$\mathbb{Z}$$ : 정수 집합

약수의 정의

$$a,b\in\mathbb{Z}; (a\ne0)$$ $$a$$가 $$b$$의 약수라는 말은 $$b=ak,, \exist k \in \mathbb{Z}$$ 라는 말과 동치이다.

0의 약수

$$x,|,0; \Rightarrow; x$$는 모든 정수 0의 약수는 모든 정수 (모든 정수는 0의 배수)$$\Rightarrow,x,|,0;\Rightarrow,0=x\times k, (k는, 0), ,,\exist k\in,\mathbb{Z}$$

공약수(최대 공약수)

$$\gcd(a,b)$$ 라고 나타낼 수 있으며 $$\gcd$$는 greatest common diviser (최대 공약수)의 약자이다. $${\sf ex})\gcd(12,3)=3\\quad;,\gcd(32,18)=2$$

유클리드 알고리즘(유클리드 호제법)

$$\gcd(A,B)=\gcd(B,r) $$

각 문자의 크기를 비교해보면 $$0\le r<B<A$$ 라고 나타낼 수 있는데 유클리드 호제법을 보면 $$A$$보다 작은 $$B,r$$의 최대공약수가 $$A,B$$의 최대공약수와 같다고 나와있다. 따라서 위의 식에서 = 의 의미는 같은 값 $$\gcd$$를 좀 더 작은 수로 축소해서 나타낸다는 말이 될 수 있다. 또한 이 말을 통해 $$\gcd(B,r)$$을 계속 축소할 수 있다는 것을 알 수 있다. $$\gcd(A,B)\quad (A>B,,,A\ne B)\ A=qB+r\B=q_1r+r_1 $$ 위의 $$B$$의 식은 $$\gcd(B,r)$$을 한번 더 축소했다고 가정했을 때의 식이다. 이때 $$q,q_1$$은 몫을 나타내고 $$r,r_1$$은 나머지를 나타낸다.

증명

$$\gcd(A,B)=\gcd(B,r)$$ $$($$단, $$A>B,,A\ne B,,A=qB+r,,0\le r<B)$$

$${\sf pf};\gcd(A,B)=g\Rightarrow \gcd(B,r)=g\\quad;$$이때 $$\gcd(B,r)=g$$ 가 우리가 증명할 명제이다. 공통인수인 $$g$$를 사용하여 $$A,B$$를 식으로 나타내면$$\quad ,A=ga\\quad ,B=gb$$ 와 같다. 단, $$a,b$$ 는 서로소이다.

서로소란?

: $$a,b$$가 서로소라는건, $$\gcd(a,b)=1\Leftrightarrow$$ 공통인수가 없다.(1을 제외하고)

$$a,b$$가 서로소가 아닐 경우

$$\gcd(a,b)\ne1,,,\gcd(a,b)=m\Rightarrow m,|,a,,,m,|,b$$ $$A=ga, ,,B=gb$$ 를 $$gm$$으로 나눌 수 있고 모두 약분된다. 그럼 $$A,B$$의 공통인수는 $$gm$$이 된다. 따라서 $$\gcd(A,B)=g\Rightarrow$$ 모순 이를 정리하자면 $$\gcd(A,B)=g\A=ga,,,B=gb;,$$ $$($$단, $$\gcd(a,b)=1)$$

다시 증명을 이어서 하면 $${\sf pf};A=qB+r$$ 은 $$ga=qgb+r$$ 과 같이 나타낼 수 있고 $$\quad ;r=ga-qgb=g(a-qb)=gr^\prime$$ 을 통해 $$g,|,r$$ 이 가능하다. $$\quad B=gb,,r=gr^\prime,\Rightarrow,g,|,b,,,g,|,r$$ $$\quad$$위 식을 통해 $$g$$가 $$B,r$$의 공약수임을 알 수 있지만 최대공약수인지는 알 수 없다. $$\quad$$따라서 $$\gcd=(B,r^\prime)=1$$임을 보여야한다.

$$\quad$$우리는 귀류법을 사용할 것인데 $$\gcd(b,r^\prime)=\alpha;,(a\ne1)$$ 라고 가정하고 식을 써보면 다음과 같다. $$\quad A=qB+r\Rightarrow ga=qgb+gr^\prime$$ $$\quad b=\alpha b^\prime$$ $$\quad r^\prime=\alpha r^{\prime\prime}$$ $$\quad$$이때 $$\gcd(b^\prime,r^{\prime\prime})=1$$ 이며 위 $$b,,,r^\prime$$ 에 대한 두 식을 $$ga=qgb+gr^\prime$$ 에 대입한다. $$\quad A=ga=qg\alpha b^\prime+g\alpha r^{\prime\prime}=ga(qb^\prime+r^{\prime\prime})\\quad\Rightarrow g\alpha,|,A\ \quad\quad;g\alpha,|,B=gb=g\alpha b^\prime$$ $$\quad$$위 식은 $$\gcd(A,B)=\gcd(B,r)$$ 에 모순이다. $$\quad$$즉, 최대공약수가 $$g\alpha$$ 이기 때문에 $$A,,,B$$의 최대공약수가 $$g$$라는 것에 모순이다.

$$\quad$$위 귀류법을 통해 $$\gcd(b,r^\prime)=1$$ 이 증명된다. $$\quad$$그럼 $$\gcd(B,r)=g$$ 또한 증명이 되고 따라서 $$\gcd(A,B),\gcd(B,r)$$의 값이 g로 같다. $$\quad$$결론적으로, $$\gcd(A,B)=\gcd(B,r)$$ 이라는 것을 알 수 있다.

예제

$${\sf ex}),\gcd(12345,123)=\gcd(123,45)\\quad\quad\quad\quad\quad\quad\quad\quad;;,=\gcd(45,33)\\quad\quad\quad\quad\quad\quad\quad\quad;;, =\gcd(33,12)\\quad\quad\quad\quad\quad\quad\quad\quad;;, =\gcd(12,9)\\quad\quad\quad\quad\quad\quad\quad\quad;;, =\gcd(9,3)\\quad\quad\quad\quad\quad\quad\quad\quad;;, =\gcd(3,0) =3$$

틀린부분이나 이상한 부분 있으면 알려주세요...!

1. pycryptodome

파이썬을 이용하여 암호화를 하기 위해서 난 pycryptodome을 사용할 것이다.

pip install PyCryptodome

위에 코드를 입력했더니

Raquirement already satisfied: PyCryptodome in /home/bassel/anaconda3/lib/python3.8/site-packages (3.9.9)

라고 나왔다. 그럼 이제 파이썬으로 코드를 입력하면 된다.

2. Python으로 코드 입력

from Crypto.Cipher import AES
from secrets import token_bytes

key = token_bytes(16)

def encrypt(msg):
    cipher = AES.new(key, AES.MODE_EAX)
    nonce = cipher.nonce
    ciphertext, tag = cipher.encrypt_and_digest(msg.encode('ascii'))
    return nonce, ciphertext, tag

def decrypt(nonce, ciphertext, tag):
    cipher = AES.new(key, AES.MODE_EAX, nonce=nonce)
    plaintext = cipher.decrypt(ciphertext)
    try:
        cipher.verify(tag)
        return plaintext.decode('ascii')
    except:
        return False

nonce, ciphertext, tag = encrypt(input('Enter a message: '))
plaintext = decrypt(nonce, ciphertext, tag)
print(f'Cipher text: {ciphertext}')
if not plaintext:
    print('Message is corrupted')
else:
    print(f'Plain text: {plaintext}')

이렇게 코드를 입력했다.

3. 결과

터미널에 파일명인

python aes_encryption.py

를 입력했더니

Enter a message:

라고 뜬다. 그리고 입력창에 아무 메세지나 입력해서 enter를 누르면 AES 알고리즘을 통해 Cipher text와 Plain text가 차례대로 나타난다.

Reference https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html?highlight=AES

: 대칭키 알고리즘으로 1997년 NIST(미국 국립기술표준원)에서 DES를 대체하기 위해 Advanced Encryption Standard(AES)로 불리는 암호 알고리즘을 공모하였다. 이후 레인달이 개발한 알고리즘이 AES로 채택되었고 높은 안전성과 효율성, 속도 등으로 인해 DES 대신 전 세계적으로 많이 사용되고 있다.

AES에는 3가지 종류가 있으며 각각 AES-128, AES-192, AES-256으로 불리며 이름 그대로 키 크기가 128, 192, 256 bit이다.

DES는 Feistel 네트워크라는 기본 구조를 사용하지만 AES에서는 SPN 이라는 구조를 사용하고 있다.

spn: Subsititution Layer과 Pernutation을 이용하여 Confusion과 Diffusion을 만족시켜주는 구조이다. 이 구조의 장점은 Feistal 구조와 반대로 병렬연산이 가능하여 속도가 빠르고 단점은 복호화시 별도의 복호화 모듈을 구현해줘야 한다는 것이다.

AES 알고리즘의 동작과정

1. SubBytes 과정 (바이트 대체)

: 암호문이 비 선형성을 갖도록 하기 위해 바이트 단위로 역 변환이 가능한 S-box라는 표를 이용하여 블록을 교환한다.

2. ShiftRows 과정 (행 이동)

: Shift 연산을 하여 단순히 행과 행을 치환하는데 4개의 행은 각각 왼쪽으로 Shift되지만 첫번째 행은 그 행의 맨 오른쪽 값으로 이동한다.

void ShiftRows()
{
    unsigned char temp;
    // Rotate first row 1 columns to left
    temp = state[1][0];
    state[1][0] = state[1][1];
    state[1][1] = state[1][2];
    state[1][2] = state[1][3];
    state[1][3] = temp;
    // Rotate second row 2 columns to left
    temp = state[2][0];
    state[2][0] = state[2][2];
    state[2][2] = temp;
    temp = state[2][1];
    state[2][1] = state[2][3];
    state[2][3] = temp;
    // Rotate third row 3 columns to left
    temp = state[3][0];
    state[3][0] = state[3][3];
    state[3][3] = state[3][2];
    state[3][2] = state[3][1];
    state[3][1] = temp;
}

3. Mixcolumn 과정 (열 섞기)

: 열 단위 연산을 수행한다. 열에 속한 모든 바이트를 순환 행렬을 사용해 함수로 열에 있는 각 바이트를 대체하여 변화시킨다. 참고로 마지막 라운드는 MixColumn을 하지 않는다

// xtime is a macro that finds the product of {02} and the argument to xtime modulo {1b}
#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0x1b))
// MixColumns function mixes the columns of the state matrix
// The method used may look complicated, but it is easy if you know the underlying theory.
// Refer the documents specified above.
void MixColumns()
{
    int i;
    unsigned char Tmp, Tm, t;
    for (i = 0; i<4; i++)
    {
        t = state[0][i];
        Tmp = state[0][i] ^ state[1][i] ^ state[2][i] ^ state[3][i];
        Tm = state[0][i] ^ state[1][i]; Tm = xtime(Tm); state[0][i] ^= Tm ^ Tmp;
        Tm = state[1][i] ^ state[2][i]; Tm = xtime(Tm); state[1][i] ^= Tm ^ Tmp;
        Tm = state[2][i] ^ state[3][i]; Tm = xtime(Tm); state[2][i] ^= Tm ^ Tmp;
        Tm = state[3][i] ^ t; Tm = xtime(Tm); state[3][i] ^= Tm ^ Tmp;
    }
}

4. AddRoundKey 과정 (라운드 키 더하기)

: 라운드 키와 현재 state 블록을 비트별로 XOR 한다.RoundKey는 key expansion schedule에 따라 key로부터 유도되어진다.

// This function adds the round key to state.
// The round key is added to the state by an XOR function.
void AddRoundKey(int round)
{
    int i, j;
    for (i = 0; i<4; i++)
        for (j = 0; j<4; j++)
            state[j][i] ^= RoundKey[round * Nb * 4 + i * Nb + j];
}

5. AES 암호화, 복호화 알고리즘

참고) 대칭형 알고리즘

:암호화 할 때의 key와 복호화 할 때의 key 값이 같으면 대칭키라고 한다. 대칭키를 사용하는 암호화를 '대칭형 암호 알고리즘'이라고 하고 대표적인 예로는 SEED, DES, DES3, AES 등이 있다.

대칭 암호화 방식

자신의 키로 메세지를 암호화라고 키를 수신자에게 보내면 키를 이용해 복호화하는 방식이다. 키를 공유해야하기 때문에 키가 공격자에게 노출되면 보안에 취약해지지만 비대칭 암호화 방식에 비해 키 사이즈가 작고 알고리즘 구조가 간단해서 속도가 빨라 효율적이다.

Reference https://developer-mac.tistory.com/59 https://www.crocus.co.kr/1230 https://gaeko-security-hack.tistory.com/106

올해 동계 해킹캠프는 토, 일 2일 동안 진행되었다. 처음에는 내용이 어려워서 내가 못 따라갈까봐 걱정했지만 발표자분들이 친절하게 질의응답을 해주시고 이해하기 쉽게 설명해주셔서 정말 재밌는 시간을 보낼 수 있었다.

2일 동안 9개의 발표를 들었는데 당시 한참 네트워크 공부를 하고 있었을 때라 노무승 발표자님께서 발표해주신 '와이파이(IEEE 802.11) 해킹에 대해 알아보자!' 라는 발표가 제일 재밌었고 인상깊었다. 이 외에도 웹해킹, 워게임, 취약점 분석 등 다양한 주제를 너무나도 열심히 발표해주셔서 평소 잘 접하지 못했던 내용들을 흥미롭게 들을 수 있었다. 또한 발표도 발표지만 캠프 중간에 SISS 분들이 준비해주신 퀴즈들 덕분에 더 재밌었다.

토요일 마지막 발표가 끝난 뒤에 새벽 1시인가 2시까지 팀원분들과 함께 ctf 문제를 풀었다. 솔직히 현재 해킹공부를 시작한지 얼마 안되었기에 ctf에 참가하기 전에 좀 겁이 났었는데 팀원분들이 너무나도 친절하셔서 긴장이 좀 풀릴 수 있었다. 🙏 약 6시간의 ctf가 끝나고 모두 열심히 문제를 푼 결과 운 좋게 1등을 할 수 있었다... 진짜 당시에 문제 푸느라 바빠서 아무것도 남기지 못했었는데 대신 라잇업 제출해주시고 어려운 문제 다 풀어주신 팀원분들께 넘 감사했다...ㅠ

ctf가 끝난 뒤에는 다음날 다시 발표를 듣고 Demon 팀원분들과 Q&A 시간을 가진 후, 시상식을 하고 2일 동안의 캠프가 끝났다. 처음 캠프를 시작하기 전에는 온라인이라 많은 기대를 하지 않았는데 2일 동안 해보니 기대 이상으로 너무 유익하고 재밌었다. 특히 Demon 팀원분들과의 Q&A 시간에 그동안 궁금했던 점들을 직접 답변해주셔셔 앞으로 해킹공부를 하는데 도움이 될 정보들을 얻을 수 있었다. 다음번에는 제발 코로나가 좀 완화되어서 오프라인으로 했으면 좋겠고 온라인으로 해도 꼭 다시 참가할 계획이다.