1. Closure 

- 정의) A set S is closed with respect to a binary operator if, for every pair of elements of S, the binary operator specifies a rule for obtaining a unique elements of S

 

2. Associate law(결합법칙)

 - (x*y)*z=x*(y*z) for all x,y,z∈S

 

3. Commutative law(교환법칙)

 - x*y=y*x for all x,y∈S

 

4. Identity elements(항등원)

 - for all x∈S, e*x=x*e=x 

 

5. Inverse(역원)

 - for all x∈S , exists y∈S, such that x*y=e 

   이때의 y를 x의 inverse(역원)이라 한다. 

 

6. Distributive law(분배법칙) 

 - (a)  x(y+z) = xy+xz

  (b) x+yz=(x+y)(x+z)

- (b) 식이 와닿지 않아서 증명해보았다. 

(x+y)(x+z) = xx+xz+yx+yz

              = x+xz+yx+yz

              = x(1+z) + yx+yz

              = x+yx+yz            <1+z = 1>

              = x(1+y)+yz

              = x+yz

 

 

 

Minterms (최소항) 

- 정의) 모든 변수가 한 번씩 나타나 곱의 형태를 이루고, 그 변수들은 true 혹은 complement 된 형태를 취하게 되는것

- 쉽게 말해서 곱들의 합이라고 표현할 수 있다. 

- ex) F1 = x'y'z+xy'z'+xyz

- xy+xz+yz 의 경우는 해당하지 않는다 (why? 각 곱들에 모든 변수가 한번씩 나타나지 않았기 때문)

- 논리 회로는 AND gates만 사용한다. 

- variables 가 n개라면, 총 2^n개 이다. 

 

Maxterms(최대항)

- 정의) 모든 변수가 한 번씩 나타나 합의 형태를 이루고, 그 변수들은 true 혹은 complement 된 형태를 취하게 되는것

- 쉽게 말해서 합들의 곱이라고 표현할 수 있다. 

- 논리 회로는 AND gates만 사용한다.

- variables 가 n개라면, 총 2^n개 이다. 

 

Minterms & Maxterms for three variables(x,y,z)

 

 

Minterms 의 예시

F = A+B'C =∑(1,4,5,6,7)

풀이) F = A+B'C = A(B+B')+B'C

                      = AB+AB'+B'C

                      = AB(C+C')+AB'(C+C')+(A+A')B'C

                      = ABC+ABC'+AB'C+AB'C'+A'B'C

                      = m1+m4+m5+m6+m7 (위의 표 참고)

                      =∑(1,4,5,6,7) 

 

m1,m4,m5,m6,m7부분만 1이고 나머지는 다 0이므로 F에 대한 truth table을 그리면 다음과 같다.

 

Maxterms 의 예시

F1' = m0+m2+m3+m5+m6 이라는 minterms식이 있음. F1은 maxterms로 나타나게 되는데, 그때의 truth table은?

풀이) F1' = m0+m2+m3+m5+m6 

            = x'y'z' + x'yz' + x'yz + xy'z + xyz'

        F1 = (F1')' = (x+y+z)(x+y'+z)(x+y'+z')(x'+y+z')(x'+y'+z) <드모르간 법칙>

                      = M0M2M3M5M6

                      =∏(0,2,3,5,6)

M0,M2,M3,M5,M6부분만 0이고 나머지는 다 1이므로 F1에 대한 truth table을 그리면 다음과 같다.

 

Minterms 와 Maxterms의 관계

F = xy+x'z 로 Minterms와 Maxterms 비교

1. Minterms 구하기

F = xy+x'z = xy(z+z')+x'z(y+y') 

              = xyz+xyz'+x'yz+x'y'z

              = m7+m6+m3+m1

              = ∑(1,3,6,7) 

 

2. Maxterms 구하기

F = xy+x'z = (xy+x')(xy+z)

              = (x+x')(y+x')(x+z)(y+z) 

              = (y+x')(x+z)(y+z) 

              = (x'+y+z)(x'+y+z')(x+y+z)(x+y'+z)(x+y+z)(x'+y+z)     <cf1>

              = (x+y+z)(x'+y+z)(x'+y+z')(x+y'+z)     <cf2>

              = M0M4M5M2

              = ∏(0,2,4,5)

<cf1. x'+y = x'+y+zz' = (x'+y+z)(x'+y+z')>

<cf2. xx' = x>

 

따라서

F(x,y,z) = ∑(1,3,6,7)  = ∏(0,2,4,5)가 성립하고

드모르간 법칙에 의해,

F'(x,y,z) = (1,3,6,7)  = (0,2,4,5) 도 성립하는 것을 알 수 있다. 

MNIST database 

- 손으로 쓴 숫자들로 이루어진 대형 데이터 베이스이며, 다양한 화상 처리 시스템을 training하기 위해 일반적으로 사용됨

- 60,000개의 트레이닝 이미지와 10,000개의 테스트 이미지 포함

- NIST의 테스트 데이터셋으로부터 취합됨  

※NIST

더보기

NIST

28x28 픽셀의 바운딩 박스와 앤티엘리어싱 처리되어 그레이스케일 레벨이 들어가 있도록 평준화 되어 있음

KERAS(딥러닝 네트워크를 구축하기 위한 텐서플로의 고수준 API)

- 진입장벽이 낮고, 추상화가 잘 되어 있어 코드 가독성이 높기 때문에 주로 사용

- Backend인 Theano, TesorFlow, CNTK를 골라서 사용 가능

mnist model 구축 및 학습

1. import required modules

import numpy as np
import tensorflow as tf 
from tensorflow import keras
from keras.layers import Dense
from keras.models import Sequential
from keras.datasets import mnist

import mnist 모듈을 통해 data를 준비한다. 

2. load mnist data

(X_train, Y_train),(X_test,Y_test) = mnist.load_data()

(X_train, Y_train) : train dataset으로, 60000, 28*28 그레이스케일 이미지의 10digits인 dataset이다. 

(X_test, Y_test) : test dataset으로, trained model을 테스트하기 위한 10000, 28*28 그레이스케일 이미지이다. 

3. Reshape

X_train = X_train.reshape(60000,28*28).astype('float32')/255.0
X_test = X_test.reshape(10000,28*28).astype('float32')/255.0

Y_train = keras.utils.to_categorical(Y_train, 10)
Y_test = keras.utils.to_categorical(Y_test, 10)

60000은  x_train.shape[0]와 동일하고, 28*28은 784이므로 X_train = X_train.reshape(x_train.shape[0],784)라 작성하여도 무방하다. 

x_train.astype('float32'/255.0 : 그레이스케일 color 0~255.0을 0~1로 다시 스케일링 한다는 의미이다. 

keras.utils.to_categorical(Y_train,10) : 10개의 값을 one hot encoding한다는 의미이다. 

4. design model(Architecture) by using Keras Sequential model

model = Sequential()
model.add(Dense(units=4, input_dim=(28*28),activation='sigmoid'))
model.add(Dense(units=10,activation='softmax'))
model.summary() 

Sequential model : 뉴런의 각 레이어가 다음 레이어 위에 쌓이는 모델을 의미한다. 

model.add는 말그대로 model에 레이어를 추가한다는 의미이다. 

Dense는 "Dense 레이어"임을 나타내 주고, fully connected 레이어라고도 한다. 예측할 때 입력이 뉴런의 모든 단일 뉴런으로 전달됨을 의미한다. 

그런 다음 각 뉴런은 어느 정도 활성화(activated)되는데, 활성화 정도는 훈련 중 학습된 가중치, 편향과 활성화 함수(activation function)을 기준으로 한다. 첫번째 레이어에서의 활성화 함수는 "sigmoid"함수이고, 두번째 레이어의 경우 "softmax"이다. 

model.summary() 를 통해 작성한 model의 구조를 확인할 수 있다. 

네트워크 레이어, 출력형태, 파라미터 수를 확인할 수 있다. 네트워크 크기(메모리 용량)은 대부분의 파라미터 수에 따라 달라지며 총가중치와 편향 수를 의미한다. 

5. Compile model

model.compile(optimizer='sgd',loss='categorical_crossentropy',metrics=['accuracy'])

model을 compile하는 단계는, 학습 과정에서 사용되는 몇 가지 중요한 인수를 설정하고 훈련할 모델을 준비하는 과정이다. 

optimizer : 훈련 중에 네트워크가 입력을 모델링하도록 조정하는 알고리즘을 지정하고, 여기선 'sgd'를 사용

loss : 훈련 과정에서 네트워크 예측이 실제 값에서 얼마나 멀리 떨어져있는지 계산하기 위해 사용하는 방법을 지정하고, 여기서는 'categorical_crossentropy'함수를 사용, 이 함수를 보통 손실함수라 한다. 이 외에도 mse(Mean Squared Error 평균 제곱 오차법),등이 있다. 

metrics : 모델의 성능을 판단할 때 사용하는 함수를 지정하고, 여기선 'accuracy'함수 사용, 이 외에도 mae(Mean Absolute Error 평균 절대 오차법),등이 있다. 

6. Train designed model

history=model.fit(X_train, Y_train, batch_size=10, epochs=10, validation_split=0.3)

X_train, Y_train : 훈련데이터의 x,y값

batch_size : 배치크기는 정확도를 측정하고 가중치와 편향을 업데이트하기 전에 네트워크에 공급할 훈련 데이터 수를 지정해 주는 것이다. 위의 경우, 10으로 설정했으므로 각 에폭은 네트워크를 10번 업데이트할 것이다. 

epochs : 에폭은 전체 훈련 데이터셋이 훈련 중 네트워크를 통해 몇 번이나 실행될 것인지 지정한다. 따라서 에폭이 클 수록 학습을 더 많이한다. 

validation_split : 검증 데이터셋을 지정한다. 검증 데이터셋의 데이터는 전체 훈련 과정을 마친 네트워크에 투입되어 네트워크의 예측값과 기대 출력값을 비교한다. 

이렇게 Epoch이 10이 될 때까지 실행 후 출력한다. 

loss : loss함수의 출력값. 당연한 얘기지만, 작을수록 좋음. 첫번째 에폭의 loss값과 마지막 에폭의 loss값을 비교하여 개선이 되었는지 판단할 수 있다. 

accuracy : 훈련데이터의 정확도이다. 

val_loss : 검증 데이터에 대한 손실 함수 출력이다. 훈련손실이 검증 손실보다 낮을 경우, 네트워크가 과적합 될 수도 있음을 암시한다. 

val_accuracy : 마찬가지로 검증 데이터에대한 정확도이다. 

 

※ 에폭이 클수록 학습을 더 많이 하니까, 항상 네트워크가 더 좋아질까?

No, 일부 네트워크는 특정 수의 에폭 이후에 훈련 데이터에 과적합될 수도 있다. 과적합이 없는 경우에도 일부 네트워크는 일정량의 훈련 후에 네트워크 개선이 중단되는 경우도 있다. 

따라서, 네트워크가 개선되지 않을 시 훈련하지 않는 것이 좋다. 

7. Evaluate model

loss,accuracy=model.evaluate(X_test,Y_test)

테스트 데이터셋의 손실을 계산하고 출력한다. 정확히, 손실과 정확도를 계산하고 출력하여 모델 예측값이 실제값과 얼마나 차이나는지 계산한다. 

8. draw plot of accuracy

import matplotlib.pyplot as plt
plt.plot(history.history['accuracy'])
plt.plot(history.history['val_accuracy'])
plt.title('model accuracy')
plt.ylabel('accuracy')
plt.xlabel('epoch')
plt.legend(['training', 'validation'], loc='best')
plt.show()

 

9. draw plot of loss

plt.plot(history.history['loss'])
plt.plot(history.history['val_loss'])
plt.title('model loss')
plt.ylabel('loss')
plt.xlabel('epoch')
plt.legend(['training', 'validation'], loc='best')
plt.show()

 

 

 

1. 자신의 윈도우 bit에 맞는 최신버전 zip 파일 다운로드한다.

http://code.google.com/p/openssl-for-windows/downloads/list 

 

참고) 윈도우 비트 확인하는 방법

내 컴퓨터 (내 PC)에 오른쪽 클릭을 한 다음에 속성을 누르면 된다. 그러면 시스템 탭이 열리는데 시스템 종류란을 확인하면, 윈도우 bit를 확인 할 수 있다. 

 

2. 설치한 파일을 압축 해제 후에 해당 폴더를 (로컬디스크)C:\ 로 이동한다. 

 

3.  cmd창을 열어 ([Win]+[R] 클릭 후 cmd 입력) 다음과 같이 실행함으로써, 설치가 잘 되어있는지 확인한다. 

cd 명령어를 통해 해당 폴더 (bin)로 이동하고

openssl 명령어를 실행시키면

설치에 성공한 경우, OpenSSL> 이라는 글자가 뜬다. 

quit을 입력해 openssl을 종료시키면 된다. 

DES(Data Encryption Stadard)

- Block cipher

  plaintext를 64bit의 block으로 나눠 56bit의 key를 이용해 다시 64bit의 ciphertext를 만들어내는 알고리즘

Symmetric cipher

  암호문을 작성할 때 사용하는 암호키 = 암호문을 해독할 때 사용하는 해독키

 

DES 동작 과정

(1) 전반적인 DES 동작 과정

1. 64bit의 plaintext가 첫번째 round를 거치기 전에   Initial Permutation(초기 치환)을 통과한다.

 

2. IP를 통과한 후 나온 64bit32bitL0과 R0으로 분리된다.

 

3. R0에 해당하는 32bit는 각 key_schedule를 통해 나온 첫번째 48bit key와 함께 F-box에 들어간다. F-boxoutput32bit이다.

 

4. 32bitL032bitXOR operation 해준다.

 

5. 생성된 32bitR1에 보내주고, R0 32bit L1에 오도록 한다. (swapping)

이과정을 16 round 반복한다.

마지막 round의 경우, swapping하지 않고 그대로 실행시켜야 한다.

 

6. R16L16을 합쳐서 64bit로 만들고 FP(IP의 역)을 통과한다. output64bitciphertext이다.

 

 

 

 

(2) F-box

1. round마다 오른쪽 32bitExpansion(E)를 통과한 후 48bit로 확장된다.

2. 48bitkey_schedule에 따른 key 48bitXOR operation한 후에 F-box를 통과한다.

3. XOR operation 후에 얻은 48bit6bit씩 8부분으로 나누어 각각 S-Box를 통과한다.

4. S-Box를 통과한 output 4bit이고 8개를 모두 합치면 32bit가 된다.

5. Permutation(P)를 통과해 F-box output를 도출해 낸다.

 

(2) key schedule

처음 64bitkeyPC1을 거쳐 56bit가 되는데, 나머지 8bitParity bit로 사용된다.

    ☞ parity bit?

더보기

정보전달 과정에서 오류가 생겼는지를 검사하기 위한 bit

56bit28bit씩 왼쪽, 오른쪽 분리한 후 실행한다. round마다 shift_schedule(key 회전 스케줄)에 따라 왼쪽으로 1bit, 2bit 회전한다.

→ 1,2,9,16번째는 1shift, 나머지는 2shift한다.

각각 shift연산을 한 후에 왼쪽 오른쪽을 합쳐서 PC2를 통과시키면 output48bit이고 각각 subkey를 의미한다.

1. Enigma란?

Enigma는 독일의 Arthur Scherbius에 의해 고안된 암호화와 복호화를 수행하는 기계

Enigma는 고대 그리스어로 수수께끼를 뜻하는 아이니그마라는 말에서 따온 것

Enigma는 키보드, 램프, 플러그보드, 로터, 등으로 조합한 기계로 암호화와 복호화를 수행

송신자와 수신자는 enigma를 각각 1대씩

송신자는 enigma를 이용해 평문(메시지)을 암호화하고 완성된 암호문을 무선으로 수신자에게 보냄

수신자는 받은 암호문을 자신의 enigma로 복호화 해서 평문(메시지)을 얻음

 

2. Enigma의 암호통신 및 구성요소

(1) Codebook

송신자와 수신자는 같은 키를 사용해야 하므로 codebook이라고 하는 두꺼운 책자를 공유

codebook-  송신자와 수신자가 사용하는 날짜별 키(KEK) 기록 

※ KEK(Key Encrypting Key)

날짜별 키.

통신키의 암호화에 이용( 키를 암호하기 위한 키)

날짜에 해당하는 기어 종류, 기어 설정, 플러그 연결,등 기록되어 있음

 

(2) 키보드

Enigma의 키보드의 키를 누르게 되면 전기신호가 복잡한 회로를 거쳐 램프에 불이 들어오게 되는데, 이때 입력한 값과 출력한 값(램프에 들어오는 값)은 다름

 

(3) 플러그보드

플러그보드는 연결선을 바꿈으로써 문자의 대응을 다양하게 변화시키기 위한 부품

Codebook에 따른 날짜 별 키로 플러그보드의 연결선이 정해지며 설정한 뒤에는 하루동안 변경X

 

(4) 로터

로터는 앞과 뒤의 단자가 전선으로 연결되어 있는 원반 모양의 부품

회로의 중간에 3개 있음

로터 하나하나의 연결선은 변경할 수 없고 문자를 입력할 때마다 자동으로 회전

각 로터의 주변에는 표시 문자가 적혀 있고, 문자에 대응하는 설치 각도를 설정 가능

키보드의 글자를 하나씩 입력할 때마다 첫번째 로터가 하나씩 도는데 첫번째 로터가 한바퀴를 다 회전하면 두번째 로터가 하나 회전하고, 두번째 로터가 한바퀴 다 회전하면 세번째 로터가 하나 회전

 

3. Enigma의 암호화 과정 (1)~(5)

(1) Enigma의 설정

송신자는 codebook에 있는 해당 날의 날짜별 키를 찾아내고 그 키에 맞춰 enigma를 설정한다. 즉, 플러그보드의 연결선을 연결하고, codebook에 지정된 로터 3개를 선택한 뒤에 이를 enigma 기계에 끼워넣고 설정된 각도로 설정한다.

(2) 통신키 암호화 및 메모

송신자는 통신키 즉, 알파벳 3문자를 정하여 암호화

통신키도 enigma를 이용해서 암호화해야 함 -> 통신키를 2번 연속해서 입력하여 암호화

ex) “uat”가 통신키라면 “uatuat”를 입력

1개의 문자를 칠 때마다 로터가 조금씩 회전하며 그 문자에 대응하는 문자 램프에 불이 들어오는 데 송신자는 불이 들어온 램프에 대응하는 문자를 메모

(3) Enigma의 재설정

송신자는 통신키에 따라 enigma를 재설정

(통신자의 알파벳 3문자 == 3개의 로터 설치 각도)

통신키 “uat”는 첫번째 로터를 u의 각도, 두번째 로터를 a의 각도, 세번째 로터를 t의 각도로 설정한다는 것을 의미

(4) 평문(메시지) 암호화

송신자는 평문을 1문자씩 키보드에 입력하고, 램프에 불이 들어오는 문자를 메모

(5) 결합

 송신자는 암호화된 통신키와 암호화된 메시지를 결합하여 무선으로 송신

 

4. Enigma의 복호화 과정 (1)~(5)

(1) 분리

수신자는 수신한 통신문을 앞부분 6자(통신키)와 나머지 문자로 분리

(2) Enigma의 설정

수신자는 codebook을 참조해서 해당 날의 날짜별 키를 조사하여, 그 날짜별 키대로 enigma를 설정

(수신자의 설정과 동일)

(3) 통신키 복호화 및 메모

수신자는 통신키 6자를 복호화

Enigma 키보드로 6자를 쳐서 불이 켜지는 각각의 문자를 메모

알파벳 3문자의 패턴이 2회 반복되면, 통신 오류가 발생하지 않았음을 알 수 있음

(4) Enigma의 재설정

 수신자는 구한 통신키를 이용하여 enigma를 재설정

(5) 암호문의 복호화 및 메모

 수신자는 통신키 6자를 제외한 통신문의 나머지 문자들을 1 문자씩 키보드에 입력하고 램프에 불이 들어오는 문자를 메모

Caesar cipher(시저 암호) : plaintext를 일정한 문자수(key space)만큼 평행이동 시킴으로써 암호화

 

a b c -> d e f  의 경우 더 길게 써보면

x y z a b c d e f ... w -> a b c d e f g h i ... z

오른쪽에 있는 알파벳은 cipher text에 속한다.

-> 를 mapping function이라고 하는데 위의 경우 Shift R3 charachers 의 역할을 한다. 

<- 은 mapping(-1) function = inverse mapping function으로 decrypt function을 의미한다. 

위의 경우 <-는 Shift L3 charachters = Shift R23 characters의 역할을 한다.

(Shift L3와 R23가 같은 이유는 알파벳의 전체 개수는 26이고 (xyzabcdef...w/xyz...)이렇게 반복을 하기 때문)

 

Shift 13 characters가 의미하는 것은?

"13"은 specific하고 strange한 number

why? 

"원래함수(암호화) = 역함수(복호화) " 가 되기 때문

-- 알파벳이 총 26개니까 Shift left right 모두 동일하다

 

stronger function? 

key space가 클수록!

 

brute-force attack

- 모든 케이스를 다 확인하는 공격

- 25!를 시도해야 얻을 수 있다

 

frequency analysis possible?

mapping table (fixed mapping) 

Original Encrypt
A L
B O
C F
D M
E Q
F Z

simple substitution cipher, You can find some patterns/frequency in the cypertext

 

복잡도가 충분히 높고, how can you improve it? 

실제로는 25!보다 훨씬 더 높은 확률로  break가능 (이유 :  fixed mapping)

how stronger?

(Enigma idea) codebook을 여러개 사용하는 것

+ Recent posts