고귀양이의 노트.

 DFS는 그래프나 트리에서 탐색하는 대표적인 두가지 방법(DFS, BFS)중 하나로, 하위 혹은 연결된 노드 중 하나를

우선적으로 방문하는 형태이다. 여기에서는 무방향 그래프를 사용하여 알아 보도록 한다.

인접 행렬, 인접 리스트

 먼저 그래프의 구현에 앞서 인접 행렬과 인접 리스트가 있다.

인접 행렬의 경우 NxN의 행렬로(N은 노드 개수)로 표시하는 것으로, 다음과 같이 표시한다.

0, 1의 노드가 연결되어 있는 경우, adjArray[0][1] = 1로 표시한다.

무방향 그래프의 경우 인접 행렬의 대각선(푸른선)을 기준으로 뒤집어진 대칭을 이루고 있다.

현재 행렬값이 모두 1로 되어 있지만 가중치 그래프의 경우 행렬의 숫자를 바꾸면 된다.

장점 : 

    구현이 비교적 간단하다.

    i, j노드의 연결을 확인할 경우 adjArray[i][j]로 바로 확인할 수 있어, O(1)의 시간복잡도를 가진다.

단점 :

    i 노드에 연결된 모든 노드를 확인하고자 할때 adjArray[i][0] ~ adjArray[i][N-1] 모두 확인해야해서

    O(N)의 시간복잡도를 가진다. 노드가 많고 간선(연결)이 적을때 비효율이다.

    공간복잡도도 O(N^2)로 메모리를 많이 차지한다.

 인접 리스트의 경우 연결된 노드들의 리스트로 다음과 같이 표현한다.

0, 1의 연결을 확인하고 싶은 경우 adjList[0] 리스트를 순회하여 1번이 있는 지 확인하면 된다.

무방향의 경우 인접 행렬과 동일하게 0, 1이 연결된다면 1, 0의 연결도 추가하여야 한다.

장점 :

    i와 연결된 모든 노드를 확인하고자 할때 최악의 경우(i가 모든 노드와 연결된 경우) O(N)이지만,

    대부분의 경우 항상 O(N)인 인접행렬보다 빠르다.

    공간복잡도도 간선의 개수를 E라 할때 최악의 경우를 제외하고 O(E) < O(N^2)이므로 낭비가 적다.

단점 :

    i, j의 연결을 확인하고 싶을때 adjList[i]를 순회하며 j가 있는지 봐야 하므로 O(N)으로 인접행렬보다 느리다.

DFS

dfs의 동작을 간단하게 보면 다음과 같다.

2번 노드 부터 시작하면 먼저 스택에 2를 푸쉬해 둔다.

  1. pop하여 스택 최상단 노드를 꺼내어 방문 표시를 하고 출력한다.

  2. 해당 노드의 인접 노드중 미방문 노드를 전부 push한다. 이때 스택에 중복 push는 없게 한다.

  2. 스택이 빌때까지 1, 2번을 계속한다.

예시 그래프의 노드를 위 순서대로 진행하면 2 1 0 3 4가 된다.

코드

함수 호출이 스택메모리를 사용하므로 재귀호출로도 구현할 수 있다.

이번 코드에서는 JAVA에서 지원하는 stack 컨테이너로 구현하였다.

스택에 중복 데이터에 대한 예외처리를 하지 않았기 때문에 탐색 순서가 다르게 나올 수 있다.

(스택에 들어있는지 확인하는 행렬 같은 거를 추가하면 쉽게 구현할 수 있다.)

import java.util.*;

public class graph {
	private int szVertex;
	private ArrayList<Integer> adjList[];
	private boolean visited[];
	private Stack<Integer> stack;				// for DFS
	
	public graph(int v) {
		szVertex = v;
		visited = new boolean[szVertex];		// default false
		adjList = new ArrayList[szVertex];
		for (int i = 0; i < szVertex; i++) {
			adjList[i] = new ArrayList();
		}
		stack = new Stack();
	}
	
	public void addEdge(int from, int to) {
		// 무방향 그래프이므로 반대의 경우도 추가
		adjList[from].add(to);
		adjList[to].add(from);
	}
	
	// 재귀 호출로 구현할 수 있지만 stack을 이용하여 구현하였다
	public void DFS(int start) {
		stack.push(start);
		
		// stack이 비어질때까지 게속
		while (!stack.isEmpty()) {
			// stack 최상단을 꺼내어 방문 행렬에 표시하고 출력
			int current = stack.pop();
			
			// 미방문 정점의 경우
			if (!visited[current]) {
				visited[current] = true;
				System.out.print(current + " ");
				
				// 인접 리스트에서 미방문 정점의 경우 스택에 추가
				for (int i : adjList[current])
					if (!visited[i])
						stack.push(i);
			}
		}
		System.out.println();
	}
	
	// 첫노드가 주어지지 않을 경우 0번 부터
	public void DFS() {
		DFS(0);
	}
}

public class dfs {

	public static void main(String[] args) {
		graph g = new graph(5);
		
		g.addEdge(0, 4);
		g.addEdge(1, 3);
		g.addEdge(2, 4);
		g.addEdge(2, 3);
		g.addEdge(1, 2);
		g.addEdge(1, 0);
		
		g.DFS(2);
	}
}

local outlier fator(이하 lof)는 각 점들의 밀도와 이웃점들의 밀도를 고려하여 해당 점의 스코어를 계산합니다.

lof를 구하기 앞서 먼저 reachability-distance를 구해야 한다.

reachability-distance(A,B)는  두 점 사이의 거리와 B에서 k번째 근접이웃까지의 거리중

큰 값이 reachability-distance의 값이 된다. 예를 들어,

위 그림에서 빨간선으로 이어진 점들을 B라고 볼때,

A까지의 거리가 각 점들에서 k-distance보다 크므로 빨간선이 reachability-distance값이 된다.

그 다음으로 lrd(local reachability density)를 구해야 한다.

여기서 Nk는 k-distance내 점들의 집합이다.

A가 밀도가 높지 않은 지역에 위치할 경우 A로부터 집합내의 점 B까지 거리가 길어지므로,

A의 lrd값은 작아진다.

최종적으로 lof는 주변 이웃 점들의 평균 lrd값을 구하고,

A의 lrd값을 나누어줌으로써 구해진다.

위에서 언급했듯,

A가 밀도가 높지 않은 지역에 위치할 경우 lrd값은 작아지므로 반대로 lof값은 커진다. (분모이므로)

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import LocalOutlierFactor

print(__doc__)

np.random.seed(42)

# Generate train data
X_inliers = 0.3 * np.random.randn(100, 2)
X_inliers = np.r_[X_inliers + 2, X_inliers - 2]

# Generate some outliers
X_outliers = np.random.uniform(low=-4, high=4, size=(20, 2))
X = np.r_[X_inliers, X_outliers]

n_outliers = len(X_outliers)
ground_truth = np.ones(len(X), dtype=int)
ground_truth[-n_outliers:] = -1

# fit the model for outlier detection (default)
clf = LocalOutlierFactor(n_neighbors=20, contamination=0.1)
# use fit_predict to compute the predicted labels of the training samples
# (when LOF is used for outlier detection, the estimator has no predict,
# decision_function and score_samples methods).
y_pred = clf.fit_predict(X)
X_scores = clf.negative_outlier_factor_

plt.title("Local Outlier Factor (LOF)")
plt.scatter(X[:, 0], X[:, 1], color='k', s=3., label='Data points')
# plot circles with radius proportional to the outlier scores
radius = (X_scores.max() - X_scores) / (X_scores.max() - X_scores.min())
plt.scatter(X[:, 0], X[:, 1], s=1000 * radius, edgecolors='r',
            facecolors='none', label='Outlier scores')
plt.axis('tight')
plt.xlim((-5, 5))
plt.ylim((-5, 5))
n=np.copy(X_scores*-1) # 스코어값이 음수로 나오므로
n[n<2]=np.nan          # 스코어값이 2보다 작으면 표시 안함
n=np.round(n,2)
for i, txt in enumerate(n):
    if np.isnan(txt):continue
    plt.annotate(txt, (X[i,0], X[i,1]))
legend = plt.legend(loc='upper left')  # 범례 위치
plt.show()

-----------------------------------------------------------------------------------------------------------------------------------

참고

https://scikit-learn.org/stable/auto_examples/neighbors/plot_lof_outlier_detection.html

https://jayhey.github.io/novelty%20detection/2017/11/10/Novelty_detection_LOF/

https://godongyoung.github.io/머신러닝/2019/03/11/Local-Outlier-Factor(LOF).html

ball tree도 kd tree와 마찬가지로 knn(k-nearest neighbor) search에 많이 쓰이는 트리이다.

kd tree보다는 초기 트리 구성에 비용이 크지만, kd tree의 경우 차수가 아주 크면

query했을때 검색이 매우 느려지는데, ball tree는 kd tree보다 훨씬 빠르게 결과를 도출한다.

a(1,1550), b(900,440), c(2500,330), d(4000,2), e(5000,1)

위와 같은 데이터가 주어졌을때의 트리의 구성은 그림과 같다.

먼저 가장 범위가 큰 차수로 정렬을 시키고 (위 데이터에서는 1번째 차원의 범위가 1~5000이므로 가장 크다)

중간값을 취하고 왼쪽, 오른쪽으로 나눈 뒤 다시 재귀적으로 트리를 구성하도록 한다.

검색에 활용하도록 반지름 값도 구하는데 자식 노드중 가장 멀리 떨어진 노드와의 거리가 반지름이 된다.

이때, leaf size가 1보다 큰 경우 중간값을 size만큼의 개수를 취한다.

(leaf size는 검색 결과에 영향은 없지만 검색 속도에 영향이 있을 수 있다.)

예시 데이터를 기반으로 'ball'을 그려보면 다음과 같을 것이다.

알고리즘 설명및 코드의 한글 자료는 거의 전무하여 (내 검색 능력이 모자른 것일 수도)

위키백과와 사이트의 내용을 참고하였다.

import numpy as np

class Node:
    def __init__(self, data, radius, depth, left_child=None, right_child=None):
        self.left_child = left_child
        self.right_child = right_child
        self.data = data
        self.radius = radius
        self.depth = depth

    def printALL(self):
        print(self.radius, self.data, self.depth)
        if self.left_child != None:
            self.left_child.printALL()
        if self.right_child != None:
            self.right_child.printALL()

def balltree(ndata, depth):
    if ndata.shape[0] < 1:
        return None

    # element가 한 개일 경우
    if ndata.shape[0] == 1:
        return Node(
            data=np.max(ndata, 0).tolist(),
            radius=0,
            depth=depth,
            left_child=None,
            right_child=None
        )
    else:
        # 범위가 가장 큰 dimension에 따라 정렬
        largest_dim = np.argmax(ndata.max(0) - ndata.min(0))
        i_sort = np.argsort(ndata[:, largest_dim])
        ndata[:] = ndata[i_sort, :]

        nHalf = int(ndata.shape[0] / 2)
        loc = ndata[nHalf, :]
        data = loc.tolist()

        # 중간 값(data)에서 가장 멀리 떨어진 값 까지의 거리
        radius = np.sqrt(np.max(np.sum((ndata - loc) ** 2, 1)))

        return Node(
            data=data,
            radius=radius,
            depth=depth,
            left_child=balltree(ndata[:nHalf], depth+1),
            right_child=balltree(ndata[nHalf+1:], depth+1)
        )

if __name__ == '__main__':
    X = [[1,1550], [900,440], [2500,330], [4000,2], [5000,1]]
    X = np.asarray(X)

    tree = balltree(X, 0)
    tree.printALL()

역시 파이썬 패키지중 sklearn에서 balltree의 생성 및 검색을 간편하게 할 수 있다.

결과로 가장 유사한 데이터의 인덱스 번호와 거리를 반환한다.

import numpy as np
from sklearn.neighbors import BallTree

X = [[1,1550], [900,440], [2500,330], [4000,2], [5000,1]]
X = np.asarray(X)

# 트리 생성
tree = BallTree(X)

# 테스트 데이터 쿼리
dist, ind = tree.query([[1, 1551]], 1)

print(dist, ind)

-----------------------------------------------------------------------------------------------------------------------------------

참고

https://en.wikipedia.org/wiki/Ball_tree

https://www.astroml.org/book_figures/chapter2/fig_balltree_example.html

kd 트리는 이진 트리로, 모든 트리의 노드가 k차원으로 이루어져 있다.

최근 30차원의 데이터를 다루며 검색 및 존재 하지 않을 경우 유사도(유클리디안 거리)를 구하기 위해

보게 되었는데, 아쉽게도 트리를 구성하는 데이터가 10만개가 넘다보니 오래 걸렸다. (내 컴퓨터가 구린 것일 수도...)

어쨌든 간단하게 살펴보면,

a(7,2), b(5,4), c(9,6), d(4,7), e(8,1) 이 순으로 데이터가 트리가 삽입된다 하자

먼저 k=2가 된다.

a는 트리가 비어 있으므로 루트노드가 된다.

a의 x좌표를 비교하여 작은 애들은 왼쪽으로 큰 애들은 오른쪽으로 분류한다.

따라서 b는 a의 왼쪽 노드, c는 오른쪽 노드가 된다.

d의 x좌표는 a의 x좌표보다 작으므로 왼쪽으로 가지만 이미 b가 있으므로 이번에는 y좌표를 비교한다.

b의 y좌표보다 d의 y좌표가 크므로 오른쪽에 위치한다. 동일하게 e도 배치하면 위 그림과 같이 트리가 구성된다.

데이터 순서에 따라 트리의 구성이 달라지고 그에 따라 검색 속도도 천차만별로 바뀌게 된다.

이것을 막고자 트리 구성시 정렬 후 중간값을 취하도록 하는 방법도 있다.

from operator import itemgetter

class Node:
    def __init__(self, data, depth, left_child=None, right_child=None):
        self.left_child = left_child
        self.right_child = right_child
        self.data = data
        self.depth = depth
    def printALL(self):
        print(self.depth, self.data)
        if self.left_child != None:
            self.left_child.printALL()
        if self.right_child != None:
            self.right_child.printALL()


def kdtree(point_list, depth=0):
    if not point_list:
        return None

    k = len(point_list[0])
    axis = depth % k

    point_list.sort(key=itemgetter(axis))
    median = len(point_list) // 2

    return Node(
        data=point_list[median],
        depth=depth,
        left_child=kdtree(point_list[:median], depth + 1),
        right_child=kdtree(point_list[median + 1:], depth + 1)
    )

if __name__ == '__main__':
    point_list = [(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)]
    tree = kdtree(point_list)
    tree.printALL()

위 코드는 위키백과의 것을 알기 쉽게 수정한 것이다.

트리 구성시 정렬하여 중간값을 취하고 재귀적으로 왼쪽과 오른쪽을 구하고 있다.

또한 python의 scipy라이브러리내 kdtree의 생성과 검색을 제공하고 있다.

from scipy import spatial

if __name__ == '__main__':
    point_list = [(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)]
    tree = spatial.KDTree(point_list)

    print(tree.query((2, 3)))
    print(tree.query((2, 3.5)))

트리의 인자값으로 넣을 컨테이너로써 튜플이나 리스트외에도

DataFrame과 ndarray도 넣을 수 있다. query메소드로 검색하면 결과로

유클리디안 거리와 가장 유사한 노드의 인덱스 번호를 반환한다.

"""
 keras를 이용한 x1*100 + x2*200 + 150 학습 모델
"""
from tensorflow import keras

import numpy as np
from random import randint
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

# 학습데이터 생성
x = [ randint(0, 100) for i in range(100000) ]
y = [ x[i*2]*100 + x[i*2+1]*200 + 150 for i in range(50000) ]
x = np.asarray(x).astype(np.float32)
x = x.reshape((50000, 2))
y = np.asarray(y).astype(np.float32)
y = y.reshape((50000, 1))

"""
# 학습 데이터 그래프 그리기
xs = x[:,0]
ys = x[:,1]
zs = y

fig = plt.figure(figsize=(12,12))
ax = fig.add_subplot(111, projection='3d')
ax.scatter(xs, ys, zs)
ax.view_init(15, 15)
plt.show()
"""

# 검증 데이터 생성
test_x = [ randint(0, 100) for i in range(100) ]
test_y = [ test_x[i*2]*100 + test_x[i*2+1]*200 + 150 for i in range(50) ]
test_x = np.asarray(test_x).astype(np.float32)
test_x = test_x.reshape((50, 2))
test_y = np.asarray(test_y).astype(np.float32)
test_y = test_y.reshape((50, 1))

# 모델 생성
model = keras.Sequential()
model.add(keras.layers.Dense(1, input_shape=(2,)))
rmsprop = keras.optimizers.RMSprop(lr=0.02)
model.compile(loss='mean_squared_error', optimizer=rmsprop, metrics=[keras.metrics.mse])
model.summary()

# 학습
model.fit(x, y, epochs=10)

# 검증 데이터로 모델 평가 (verbose = 1 출력 모드)
model.evaluate(test_x, test_y, verbose=1)

ret = model.predict(test_x[:3])
print("예측 데이터 : ", ret)
print("실제 데이터 : ", test_y[:3])

tensorflow에 keras가 들어오면서 훨씬 더 간단하게 모델을 만들고 돌려볼 수 있게 되었다.

과정은 인증서를 설정해주는 것 외에는 보통의 hHttpURLConnection을 이요한 통신과 흡사하다.

private HttpsURLConnection urlConnection;
    private String method;
    private SSLContext sslContext;

    public static int BUFFER_SIZE = 1024;

    public HttpsURLConnection getConnection(Context context, String url, String requestMethod) {
        try {
            setCertification(context);

            // URL 설정
            URL request_url = new URL(url);
            method = requestMethod;

            urlConnection = (HttpsURLConnection) request_url.openConnection();
            urlConnection.setRequestMethod(method);
            urlConnection.setReadTimeout(95 * 1000);
            urlConnection.setConnectTimeout(95 * 1000);
            urlConnection.setDoInput(true);

            if (requestMethod.equals("GET"))
            {
                urlConnection.setRequestProperty("Accept", "application/json");
                urlConnection.setRequestProperty("X-Environment", "android");
            } else {
                urlConnection.setRequestProperty("Content-Type", "application/json; charset=UTF-8");
                urlConnection.setRequestProperty("X-Environment", "android");
            }

            urlConnection.setHostnameVerifier(new HostnameVerifier() {
                @Override
                public boolean verify(String hostname, SSLSession session) {
                    return true;
                }
            });
            // 위에서 설정한 인증서 사용
            urlConnection.setSSLSocketFactory(sslContext.getSocketFactory());

            urlConnection.connect();

        } catch(ConnectException ce) {
            // 커넥션 오류
            ce.printStackTrace();
            return null;
        } catch (Exception e) {
            e.printStackTrace();
        }

        return urlConnection;
    }

주의점은 HttpURLConnection이 아닌 HttpsURLConnection이다. 's'가 붙어있다.

메소드는 HttpURLConnection을 상속하고 있어서 비슷하다.

    private void setCertification(Context context) throws Exception {
        CertificateFactory cf = CertificateFactory.getInstance("X.509");

        InputStream caInput = context.getResources().openRawResource(R.raw.nive_crt);
        Certificate ca;
        try {
            ca = cf.generateCertificate(caInput);
            System.out.println("ca=" + ((X509Certificate) ca).getSubjectDN());
        } finally {
            caInput.close();
        }

        // Create a KeyStore containing our trusted CAs
        String keyStoreType = KeyStore.getDefaultType();
        KeyStore keyStore = KeyStore.getInstance(keyStoreType);
        keyStore.load(null, null);
        keyStore.setCertificateEntry("ca", ca);

        // Create a TrustManager that trusts the CAs in our KeyStore
        String tmfAlgorithm = TrustManagerFactory.getDefaultAlgorithm();
        TrustManagerFactory tmf = TrustManagerFactory.getInstance(tmfAlgorithm);
        tmf.init(keyStore);

        // Create an SSLContext that uses our TrustManager
        sslContext = SSLContext.getInstance("TLS");
        sslContext.init(null, tmf.getTrustManagers(), null);
    }

코드 원본 : https://developer.android.com/training/articles/security-ssl?hl=ko

구글 문서에서 제공하는 코드이다. 인증서 데이터는 /res/raw/ 에 두고 openRawResource()메소드로 가져오고 있다.

    public String request(String content) {
        try {
            if(method.equals("POST")) {
                // POST 일때만 실행
                OutputStream outputStream = urlConnection.getOutputStream();
                BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(outputStream, "UTF-8"));
                bufferedWriter.write(content);
                bufferedWriter.flush();
                bufferedWriter.close();
                outputStream.close();
            }

            String response = null;
            if (urlConnection.getResponseCode() == HttpURLConnection.HTTP_OK) {
                response = readStream();
            }

            urlConnection.disconnect();

            return response;
        }
        catch (Exception ex) {
            ex.printStackTrace();
        }

        return null;
    }

    private String readStream() throws Exception {
        StringBuilder responseStringBuilder = new StringBuilder();

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(urlConnection.getInputStream()));
        for (; ; ) {
            String stringLine = bufferedReader.readLine();
            if (stringLine == null) break;
            responseStringBuilder.append(stringLine + '\n');
        }
        bufferedReader.close();

        return responseStringBuilder.toString();
    }

    public void disconnect() {
        urlConnection.disconnect();
    }

요청, 응답 코드

SHA는 Secure Hash Algorithm의 줄임말로 1993년 미국 국가안보국(NSA)에 의해 설계되고 표준으로 지정되었다.

이때 출간된 SHA는 구분상 SHA-0이라하고 2년 뒤인 1995년에 개정된 SHA-1을 발표했고 현재 널리 쓰이는 해쉬 알고리즘이다.

이후 변형 버전인 SHA-2라 불리는 SHA-224, 256, 384, 512가 나왔으며 보통은 SHA-1을 사용하고 더 암호학적 안전을 요하는 곳에는

SHA-2를 사용한다.

SHA-1은 메시지 길이에 상관없이 512비트씩 잘라서 메시지 다이제스트 함수를 돌린 뒤 160비트의 출력을 낸다.

원본 메시지 + 패딩 + 원본 메시지 길이(64비트) 가 512비트의 배수가 되도록 만든다. (메시지가 없어도 한다.)

패딩은 맨 뒤 64비트에는 메시지 전체 길이를 넣고 나머지 비트는 최상위 비트 1을 제외하고 0으로 채운다.

메시지가 512비트보다 길 경우 다음 번 메시지 다이제스트 함수의 입력으로 전 함수의 출력을 받는다.

맨 앞 초기값 ABCDE는 정해진 상수값이다.

void SHA_1(FILE* fptr, BYTE* result) {
	int i, size = 0;

	BYTE msg[HASH_BLOCK * 2] = { 0, };
	UINT64 f_size = 0;

	SHA_1_init();

	while ((size = fread(msg, sizeof(BYTE), HASH_BLOCK, fptr))) {
		f_size += size;

		if (size < HASH_BLOCK)
			padding(msg, f_size);

		SHA_1_digest(msg);
		if (isAddpad) SHA_1_digest(msg + HASH_BLOCK);
		memset(msg, 0, HASH_BLOCK * 2);
	}

	for (i = 0; i < HASH_DATA; i++)
		result[i] = digest[i];
}

void padding(BYTE* in, UINT64 msg_len)
{
	int i;
	BYTE* ptr = (BYTE*)&msg_len;

	in[msg_len % HASH_BLOCK] = 0x80;
	msg_len *= 8;

	// 메시지가 448비트 보다 작은 경우와 448비트 보다 큰 경우로 나누어 처리
	// 448비트보다 큰 경우에는 512비트의 블록을 추가하여 패딩을 수행한다
	if ((msg_len % HASH_BLOCK) < 56)
	{
		for (i = 0; i<8; i++)
			in[HASH_BLOCK - i - 1] = *(ptr + i);
	}
	else
	{
		isAddpad = 1;
		for (i = 0; i<8; i++)
			in[HASH_BLOCK * 2 - i - 1] = *(ptr + i);
	}
}

파일을 읽고 크기가 64바이트(512비트)보다 작으면 패딩을 한다. 패딩에서 메시지가 448비트보다 커서 문자열 길이를 담을 수 없는 경우

블록을 하나 더 늘리고 메시지 다이제스트 함수도 한번 더 한다.

메시지 다이제스트 함수는 총 80라운드를 돌며 초기 입력 160비트와 마지막 80번째 라운드의 출력 160비트를 32비트씩 법 2^32상에서의 덧셈을 한다.

그 값이 메시지 다이제스트 함수의 최종 출력값이 된다.

각 라운드는 위 그림과 같이 구성되는데 32비트씩 나누어 A->B', B->C', C->D', D->E'로 간단한데 (B->C'일때 좌측 순환쉬프트 30비트를 해준다.)

E->A'로 할때에는 A의 좌측 순환쉬프트를 5비트해준 값과 B,C,D를 F함수에 넣은 출력값과 E값과 Wt와 라운드 상수 Kt를 법 2^32상에서 덧셈을 하여

구한다. F함수는 오른쪽 그림과 같으며 F2와 F4는 같은 동작을 한다.

Wt는 입력블록을 32비트씩 잘라 16개의 W0~W15를 만들고 이를 이용하여 W79까지 생성할 수 있다.

void SHA_1_digest(BYTE* in) {
	int i;
	UINT M[16] = { 0, };
	UINT W[80] = { 0, };
	UINT reg[5] = { 0, };
	UINT temp;

	reg[0] = init_reg[0];
	reg[1] = init_reg[1];
	reg[2] = init_reg[2];
	reg[3] = init_reg[3];
	reg[4] = init_reg[4];

	for (i = 0; i < 64; i += 4) {
		M[i / 4] = BTOW(in[i], in[i + 1], in[i + 2], in[i + 3]);
	}

	for (i = 0; i < 80; i++) {
		if (i < 16)
			W[i] = M[i];
		else
			W[i] = CIR_SHIFT((W[i - 16] ^ W[i - 14] ^ W[i - 8] ^ W[i - 3]), 1);
	}

	for (i = 0; i < 80; i++) {

		if (i < 20) {
			temp = CIR_SHIFT(reg[0], 5) + F1(reg[1], reg[2], reg[3]) + reg[4] + W[i] + K0;
		}
		else if (i < 40) {
			temp = CIR_SHIFT(reg[0], 5) + F2(reg[1], reg[2], reg[3]) + reg[4] + W[i] + K1;
		}
		else if (i < 60) {
			temp = CIR_SHIFT(reg[0], 5) + F3(reg[1], reg[2], reg[3]) + reg[4] + W[i] + K2;
		}
		else {
			temp = CIR_SHIFT(reg[0], 5) + F2(reg[1], reg[2], reg[3]) + reg[4] + W[i] + K3;
		}

		reg[4] = reg[3];
		reg[3] = reg[2];
		reg[2] = CIR_SHIFT(reg[1], 30);
		reg[1] = reg[0];
		reg[0] = temp;
	}

	init_reg[0] += reg[0];
	init_reg[1] += reg[1];
	init_reg[2] += reg[2];
	init_reg[3] += reg[3];
	init_reg[4] += reg[4];

	make_Bit160(init_reg[0], init_reg[1], init_reg[2], init_reg[3], init_reg[4]);
}

AES 구조

AES(Advanced Ecryption Standard)는 1997년 DES를 대체할 목적으로 NIST 암호 표준 공모를 하여 2001년에 채택된 암호 표준이다.

feistel 구조인 DES와 달리 SPN구조로 되어있어서 복호화시 역연산의 알고리즘을 따로 구현해야 하지만 병렬 처리를 하기 용이하다..

확장성을 고려하여 설계되어서 키 길이는 128/192/256 bit를 가지고 키 길이에 상관없이 블록 길이는 128 bit이며 라운드 수는 10/12/14를 가진다.

대략 적인 순서는

1. 라운드키와 xor한다. (AddRoundKey)

2. 바이트를 치환한다. (SubBytes)

3. 행별로 바이트를 옮긴다. (ShiftRows)

4. 열 별로 바이트를 섞는다. (MixColumns)

5. 라운키와 xor한다. (AddRoundKey)

6. (라운드 수 - 1) 만큼 2~5를 반복한다.

7. 마지막 라운드는 MixColumns를 제외하고 수행한다.

복호화는 각 단계의 역연산을 거꾸로 수행하면 된다.

이제 각 단계를 살펴보자.

aes는 입력 블럭을 위 그림과 같은 행렬로 구성하여 처린한다. 최 상위 한바이트씩 총 16바이트 가 들어가는데 주의할 점은

S00 , S01, S02, ......., S33 순이 아닌 S00, S10, S20, ......, S33순으로 즉 열 우선으로 넣어야 한다.

void AddRoundKey(BYTE state[][4], WORD* rKey) {
	int i, j;
	WORD mask, shift;

	for (i = 0; i < 4; i++) {
		shift = 24;
		mask = 0xff000000;

		for (j = 0; j < 4; j++) {
			state[j][i] = ((rKey[i] & mask) >> shift) ^ state[j][i];
			mask >>= 8;
			shift -= 8;
		}
	}
}

단순하게 state행렬의 각 바이트와 라운드 키 각 바이트와 xor한다.

Subbytes

SubBytes는 위 행렬식을 곱하여 바이트를 치환한다. X0 ~ X7순으로 바이트의 최상위 비트를 위치하여 계산한다.

메모리가 부족한 시스템이라면 직접 계산을 하여 구하지만 보통은 미리 모든 바이트가 계산된 치환표를 사용한다.

SubBytes 치환표

가령 0x37을 치환하면 0xb2로 바뀐다. 복호화시에는 동일하게 역 치환표도 있다.

치환표를 사용하지 않고 계산할 때에는 해당 바이트에 [1 0 1 0 0 0 0 0]을 빼고 위 8x8행렬의 역행렬을 곱해주면 된다.

void SubBytes(BYTE state[][4]) {
	int i, j;

	for (i = 0; i < 4; i++)
		for (j = 0; j < 4; j++)
			state[i][j] = S_box[HIHEX(state[i][j])][LOWHEX(state[i][j])];
}

* HIHEX(), LOWHEX()는 각각 상위4비트 하위4비트를 반환하는 함수.

각각의 바이트에 대하여 구해준다.

ShiftRows

첫행은 움직이지 않고 둘째행은 1번, 셋째행은 2번, 넷째행은 3번 바이트단위로 왼쪽순환쉬프트를 한다.

void ShiftRow(BYTE state[][4]) {
	int i, j;

	for (i = 1; i < 4; i++)
		for (j = 0; j < i; j++)
			CirshiftRows(state[i]);
}

void CirshiftRows(BYTE state[]) {
	BYTE temp = state[0];

	state[0] = state[1];
	state[1] = state[2];
	state[2] = state[3];
	state[3] = temp;
}

코드도 간단하다.

MixColumns 행렬식

MixColumns는 배열의 각 열에 대하여 위 그림과 같은 연산을 수행하는데 기약다항식 x^8 + x^4 + x^3 + x + 1 = 0 상에서 하게 되며 따라서

캐리 발생시 0001 1011을 xor한다.

void MixColumns(BYTE state[][4]) {
	int i, j, k;
	BYTE a[4][4] = { 0x2, 0x3 , 0x1, 0x1,
		0x1, 0x2, 0x3, 0x1,
		0x1, 0x1, 0x2, 0x3,
		0x3, 0x1, 0x1, 0x2 };

	for (i = 0; i < 4; i++) {
		BYTE temp[4] = { 0, };

		for (j = 0; j < 4; j++)
			for (k = 0; k < 4; k++)
				temp[j] ^= x_time(state[k][i], a[j][k]);

		state[0][i] = temp[0];
		state[1][i] = temp[1];
		state[2][i] = temp[2];
		state[3][i] = temp[3];
	}
}

BYTE x_time(BYTE b, BYTE n) {
	int i;
	BYTE temp = 0, mask = 0x01;

	for (i = 0; i < 8; i++) {
		if (n & mask)
			temp ^= b;

		if (b & 0x80)
			b = (b << 1) ^ 0x1B;
		else
			b <<= 1;

		mask <<= 1;
	}

	return temp;
}

x_time() 함수는 곱하려는 행렬 값에 따라 기약다항식 상에서 값을 배수해주는 함수이다.

역 MixColumns함수의 경우 4x4행렬의 역행렬을 사용한다.

키 확장

라운드 키는 128비트 기준 총 11개(첫 Addroundkey포함)이고 각 키는 4개의 의 워드로 구성되기때문에 총 44개의 워드가 필요하다.

키 확장의 순서는 이렇다.

1. 키를 4바이트씩 나누어 4개의 워드로 만든다.

2. 이전 번의 워드와 4번째전 워드를 xor하여 새 워드를 생성한다. ( 4의 배수 번째의 경우 이전 워드를 g함수에 통과시킨다.)

    2-1. 입력의 워드를 1바이트만큼 왼쪽 순환시프트를 한다.

    2-2. Subbytes에 썼던 치환을 여기서도 사용한다.

    2-3. 상수값 R과 xor하여 결과를 반환한다.

3. 워드가 44개 생성될때까지 2를 반복한다.

R상수

void KeyExpansion(BYTE key[], WORD w[]) {
	int i = 0;
	WORD temp;

	while (i < Nk) {
		w[i] = BTOW(key[4 * i], key[4 * i + 1], key[4 * i + 2], key[4 * i + 3]);
		i = i + 1;
	}

	i = Nk;

	while (i < (Nb * (Nr + 1))) {
		temp = w[i - 1];
		if (i%Nk == 0)
			temp = SubWord(RotWord(temp)) ^ Rcon[i / Nk - 1];
		else if ((Nk > 6) && (i%Nk == 4))
			temp = SubWord(temp);

		w[i] = w[i - Nk] ^ temp;
		i += 1;
	}
}

* Nk : 키 바이트수(4), Nb : 블럭 수(4), Nr : 라운드수(10)

이상 AES의 알고리즘에 대해 알아보았다...

DES 메카니즘

현대암호(하이브리드 암호)의 조상님인 DES( Data Encryption Standard )이다.

DES는 feistel 구조로 되어있으며 라운드수는 16이고 64비트 입력(블럭)에 64비트키(사실상 56비트 키)를 가진다.

대략적인 순서는

1. 64비트 입력을 초기 전치한다.

2. 32비트씩 쪼갠다.

3. 오른쪽32비트는 다음 라운드의 왼쪽32비트가 된다.

4. 오른쪽32비트를 라운드 키와함께 F함수에 통과한 후 왼쪽32비트와 xor하여 다음 라운드의 오른쪽32비트가 된다.

5. 3, 4를 16번 반복한다. 단, 마지막 16라운드에는 왼쪽 오른쪽을 교차하지 않는다.

6. 최종 전치( 초기 전치의 역전치 )를 하면 끝.

feistel구조는 원래 des이전부터 있던 구조이며 따라서 feistel구조의 블럭암호들은 보통 F함수를 설계한다.

DES F함수

DES의 F함수의 대략적 순서는

1. 32비트 입력을 48비트로 확장전치한다.

2. 48비트 라운드키와 xor한다.

3. 6비트씩 S박스에 통과시킨다. 이때 박스당 6비트의 입력은 4비트의 출력을 내며 S박스 통과 후 32비트가 된다.

4. 한번 더 전치 끝.

키는 입력 64비트키에서 확장시켜서 라운드키를 생성하는데

대략적 순서는

1. 전치한다. 이때 8의 배수 번째(8, 16, ... , 64)가 없어지며 56비트가 된다.

(이때문에 DES의 키공간은 2^56이다.)

2. 28비트씩 쪼갠다.

3. 라운드별 쉬프트 횟수만큼 왼쪽순환쉬프트를 왼쪽28비트 오른쪽28비트 각각 해준다.

4. 합쳐서 전치하여 라운드키 생성. 이때 48비트가 된다.

5. 3, 4번을 16라운드 반복한다.

코드를 보자

void DES_Encryption(BYTE *p_text, BYTE *result, BYTE *key) {
	int i;
	BYTE data[BLOCK_SIZE] = { 0, };

	BYTE round_key[16][6] = { 0, };
	UINT left = 0, right = 0;

	key_expansion(key, round_key);    // 키 확장
	IP(p_text, data);                        // 초기 전치

	BtoW(data, &left, &right);           // 32비트씩 쪼갬

	for (i = 0;i < DES_ROUND; i++) { 
		left = left ^ f(right, round_key[i]);
		if (i != DES_ROUND - 1)
			swap(&left, &right);
	}

	WtoB(left, right, data);
	In_IP(data, result);                    // 마지막 전치
}

암호화 코드이다. 

복호화 코드는 라운드 키를 역순으로 넣어주는 것 빼고 다른건 없다.( Feistel 구조의 특성 )

void IP(BYTE *in, BYTE *out)
{
	int i;
	BYTE index, bit, mask = 0x80;

	for (i = 0;i<64;i++)
	{
		index = (ip[i] - 1) / 8;
		bit = (ip[i] - 1) % 8;

		if (in[index] & (mask >> bit))
			out[i / 8] |= mask >> (i % 8);
	}
}

초기 전치 코드이다.

마스크값과 &연산을 하여 해당 비트가 1인지 확인하고 1이면 out의 비트 1로 한다.

0으로 초기화되어 있기때문에 0일때는 처리하지 않는다.

UINT f(UINT r, BYTE* rkey)
{
	int i;
	BYTE data[6] = { 0, };
	UINT out;

	EP(r, data);

	for (i = 0;i<6;i++)                                 // 라운드 키와 xor
		data[i] = data[i] ^ rkey[i];

	out = Permutation(S_box_Transfer(data));   // S박스 통과하여 전치함

	return out;
}

F함수 코드이다.

void EP(UINT r, BYTE* out)
{
	int i;
	UINT mask = 0x80000000;

	for (i = 0;i<48;i++)
	{
		if (r & (mask >> (E[i] - 1)))
		{
			out[i / 8] |= (BYTE)(0x80 >> (i % 8));
		}
	}
}

F함수 내 확장 전치 코드이다.

IP코드와 유사하다.

이 외의 전치코드들도 거의 흡사하므로 담지 않았다.

UINT S_box_Transfer(BYTE* in)
{
	int i, row, column, shift = 28;
	UINT temp = 0, result = 0, mask = 0x80;

	for (i = 0;i<48;i++)
	{
		if (in[i / 8] & (BYTE)(mask >> (i % 8)))  // 마스크를 씌워 확인 후 temp에 해당 비트 1로 함
                        temp |= 0x20 >> (i % 6);

		if ((i + 1) % 6 == 0)                        // 6비트마다
		{
			row = ((temp & 0x20) >> 4) + (temp & 0x01);           // 행 값
			column = (temp & 0x1E) >> 1;                               // 열 값

			result += ((UINT)s_box[i / 6][row][column] << shift);    // 값 더하고 쉬프트(4비트씩)

			shift -= 4;
			temp = 0;
		}
	}

	return result;
}

S-box의 코드이다.

C언어에서 최소 데이터형이 8비트이기 때문에 temp에 6비트씩 담아서 처리한다.

비트필드로도 처리해도 되겠지만 귀찮아서 패스.

6비트중 상위 1번째비트와 6번째 비트는 S-box의 행값( 따라서 총 4행 )을 나타내고

중간 4비트는 열값을 나타내며 해당 행, 열에 위치한 값으로 치환된다.

S1 box

void key_expansion(BYTE *key, BYTE round_key[16][6])
{
	int i;
	BYTE pc1_result[7] = { 0, };
	UINT c = 0, d = 0;

	PC1(key, pc1_result);                // 축소 전치(64 -> 56)

	makeBit28(&c, &d, pc1_result);  // 28비트씩 쪼갬

	for (i = 0;i<16;i++)
	{
		c = cir_shift(c, i);             // 순환왼쪽쉬프트
		d = cir_shift(d, i);

		PC2(c, d, round_key[i]);     // 축소 전치(56 -> 48)
	}
}

키 확장 코드이다.

UINT cir_shift(UINT n, int r)
{
	int n_shift[16] = { 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1 };

	n = (n << n_shift[r]) + (n >> (28 - n_shift[r]));

	return n & 0xFFFFFFF;      // 쓰레기값 제거
}

왼쪽 순환 쉬프트 코드이다.

n_shift 배열에 각 라운드별 순환 횟수가 있다.

그 횟수 만큼 왼쪽 쉬프트를 해주고 순환쉬프트이므로 28비트에서 밀려난 상위비트를 밀려난 만큼 최하위로 밀어준다.

UINT는 32비트이므로 n을 왼쪽으로 밀때 32비트 상위 4비트에 쓰레기값이 생긴다. 따라서 하위 28비트만 취할 수 있게

0xFFFFFFF의 마스크를 씌워 반환한다.

이상 DES의 구조와 핵심 코드들을 살펴 보았다.

이 코드는 이 코드를 위해 작성하였습니다.

java에서 smartcardio라이브러리를 이용하면 nfc제어를 쉽게 구현할 수 있다.

nfc리더기가 연결되어 있으면 터미널 초기화가 가능하다. 현재 사용중인 acr 1251 리더기는 PICC, SAM 두개의 터미널이 있는데

기본적으로 PICC를 사용한다. (SAM은 태그에 보호기술이 들어간 것에 사용)

IsCardPresent() 메소드는 리더기 위에 카드가 있는지 검사하며 있을 경우 터미널에 대한 채널을 GetCardAndOpenChannel() 메소드로 오픈한다.

SendCommand() 메소드를 통해 올려진 카드(혹은 핸드폰)에 데이터를 보낸다.

위 안드로이드 어플리케이션과 통신하기 위해 Select AID과정을 거치는데 그에 해당하는 바이트열이 selectCardAID()메소드에 있는 것이다.

NFCMain.java

package nfc_simple;

import javax.smartcardio.*;

import java.nio.ByteBuffer;
import java.util.*;

public class NFCMain {
    private static final String UNKNOWN_CMD_SW = "0000";
    private static final String SELECT_OK_SW = "9000";
    
    public void run() {
        CardTerminal terminal;
        CardChannel channel;
        
        while (true) {
            // 터미널 초기화
            try {
                terminal = InitializeTerminal();
                
                if(IsCardPresent(terminal)) {                                   // 리더기 위에 카드(핸드폰)가 있을 경우
                    channel = GetCardAndOpenChannel(terminal);
                    
                    String response = selectCardAID(channel);
                    
                    System.out.println(response);
                }
                
                Thread.sleep(2000);
                
            } catch (CardException e) {
                e.printStackTrace();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    
    public CardTerminal InitializeTerminal() throws CardException { 
        // Get terminal 
        System.out.println("Searching for terminals..."); 
        CardTerminal terminal = null; 
        TerminalFactory factory = TerminalFactory.getDefault(); 
        List<CardTerminal> terminals = factory.terminals().list(); 
      
        //Print list of terminals 
        for(CardTerminal ter:terminals) { 
            System.out.println("Found: "  +ter.getName().toString()); 
            terminal = terminals.get(0);// We assume just one is connected 
        } 
     
        return terminal; 
    }
    
    public boolean IsCardPresent(CardTerminal terminal) throws CardException {
        System.out.println("Waiting for card...");
        
        boolean isCard = false;
        
        while (!isCard) {
            isCard = terminal.waitForCardPresent(0);
            if(isCard)
                System.out.println("Card was found! :-)");
        }
        
        return true;
    }
    
    public CardChannel GetCardAndOpenChannel(CardTerminal terminal) throws CardException {
        Card card = terminal.connect("*");
        CardChannel channel = card.getBasicChannel();
        
        byte[] baReadUID = new byte[5];
        baReadUID = new byte[]{(byte) 0xFF, (byte) 0xCA, (byte) 0x00, (byte) 0x00, (byte) 0x00};
        
        // tag의 uid (unique ID)를 얻은 후 출력
        System.out.println("UID : " + SendCommand(baReadUID, channel));
        
        return channel;
    }
    
    public String selectCardAID(CardChannel channel) {
        
        byte[] baSelectCardAID = new byte[11];
        baSelectCardAID = new byte[]{(byte) 0x00, (byte) 0xA4, (byte) 0x04, (byte) 0x00, (byte)0x05,(byte) 0xF2, (byte) 0x22, (byte) 0x22, (byte) 0x22, (byte) 0x22};
        
        return SendCommand(baSelectCardAID, channel);
    }
    
    public static String SendCommand(byte[] cmd, CardChannel channel) { 
        String response = "";
        byte[] baResp = new byte[258];
         
        ByteBuffer bufCmd = ByteBuffer.wrap(cmd);
        ByteBuffer bufResp = ByteBuffer.wrap(baResp);
         
        int output = 0;
         
        try { 
            output = channel.transmit(bufCmd, bufResp); 
        } catch(CardException ex){ 
            ex.printStackTrace(); 
        } 

        for (int i = 0; i < output; i++) {
            response += String.format("%02X", baResp[i]); 
        }
          
        return response;  
    }
}