Wireless Access Point

라즈베리파이에 Access Point를 만드는 방법(표현이 맞는지 모르겠지만)이 Routed와 Bridged 방식이 있는데

Bridged Wireless Access Point는 아래 그림과 같이 와이파이 확장기처럼 작동하고

                                         +- RPi -------+
                                     +---+ 10.10.0.2   |          +- Laptop ----+
                                     |   |     WLAN AP +-)))  (((-+ WLAN Client |
                                     |   |  Bridge     |          | 10.10.0.5   |
                                     |   +-------------+          +-------------+
                 +- Router ----+     |
                 | Firewall    |     |   +- PC#2 ------+
(Internet)---WAN-+ DHCP server +-LAN-+---+ 10.10.0.3   |
                 |   10.10.0.1 |     |   +-------------+
                 +-------------+     |
                                     |   +- PC#1 ------+
                                     +---+ 10.10.0.4   |
                                         +-------------+

Routed Wireless Access Point는 새로 내부망을 만드는 방식이다.

                                         +- RPi -------+
                                     +---+ 10.10.0.2   |          +- Laptop ----+
                                     |   |     WLAN AP +-)))  (((-+ WLAN Client |
                                     |   | 192.168.4.1 |          | 192.168.4.2 |
                                     |   +-------------+          +-------------+
                 +- Router ----+     |
                 | Firewall    |     |   +- PC#2 ------+
(Internet)---WAN-+ DHCP server +-LAN-+---+ 10.10.0.3   |
                 |   10.10.0.1 |     |   +-------------+
                 +-------------+     |
                                     |   +- PC#1 ------+
                                     +---+ 10.10.0.4   |
                                         +-------------+

Routed 방식은 Bridged 방식에서 몇가지 추가해야 하기 때문에 Bridged 방식으로 하였음

Bridged Wireless Access Point 라즈베리 파이 3 이상 또는 라즈베리 파이 제로 W의 내장 무선 기능을 사용하거나
Access Point Mode를 지원하는 적절한 USB 무선 동글을 사용하여 만들 수 있음

Install AP and Management Software

hostapd 패키지 설치가 필요함

sudo apt install hostapd

무선 액세스 지점 서비스를 활성화하고 Raspberry Pi가 부팅될 때 시작하도록 설정

sudo systemctl unmask hostapd
sudo systemctl enable hostapd

Setup the Network Bridge

다음 명령어로 파일을 생성하여 br0이라는 브리지 네트워크 장치를 추가

sudo nano /etc/systemd/network/bridge-br0.netdev

[NetDev]
Name=br0
Kind=bridge

다음 파일을 생성하여 이더넷 인터페이스(eth0)를 브리지 구성원으로 추가하여 이더넷 네트워크와 무선 네트워크를 연결

sudo nano /etc/systemd/network/br0-member-eth0.network

[Match]
Name=eth0

[Network]
Bridge=br0

systemd-networkd 서비스를 활성화하여 Raspberry Pi가 부팅될 때 브리지를 만들고 실행

sudo systemctl enable systemd-networkd

Define the bridge device IP configuration

Raspberry Pi의 DHCP 클라이언트인 dhcpcd는 모든 활성 인터페이스의 IP 주소를 자동으로 요청함
따라서 eth0 및 wlan0 인터페이스가 처리되지 않도록 차단하고 DHCP를 통해 dhcpcd가 br0만 구성하도록 해야 함

sudo nano /etc/dhcpcd.conf

시작 부분에 작성하기,"interface xxx line"가 있다면 그 위에 작성

denyinterfaces wlan0 eth0

파일의 마지막에 작성

interface br0

Ensure Wireless Operation

sudo nano /etc/hostapd/hostapd.conf

country_code=GB
interface=wlan0
bridge=br0
ssid=NameOfNetwork
hw_mode=g
channel=7
macaddr_acl=0
auth_algs=1
ignore_broadcast_ssid=0
wpa=2
wpa_passphrase=AardvarkBadgerHedgehog
wpa_key_mgmt=WPA-PSK
wpa_pairwise=TKIP
rsn_pairwise=CCMP

country_code는 위키백과 참조

ssid는 wifi 이름

hw_mode는 

• a = IEEE 802.11a (5 GHz) (Raspberry Pi 3B+ onwards)
• b = IEEE 802.11b (2.4 GHz)
• g = IEEE 802.11g (2.4 GHz)

wpa_passphrase는 비밀번호 설정

Rasberry Pi를 다시 시작하고 무선 액세스 지점을 자동으로 사용할 수 있는지 확인

sudo systemctl reboot

사실 이렇게 만들어 봤자 신호가 너무 약해서 공유기를 대체할 수는 없는 것 같음

방 안에서 거실에 있는 와이파이 신호가 약할 때나 사용할 수 있을 듯

사실 공식문서 번역한 수준이고 모든 명령어 하나하나 뜯어보지 않아서 포스팅하기에 좀 부끄럽지만

다른 포스팅을 보는 것 보다 공식문서 보는게 좋고 (다른 포스팅 따라해봤지만 안됨)

번역 된 포스팅을 본적이 없어서 포스팅 하게 되었음

참조문헌

라즈베리파이 공식 문서

Zigbee 소개

지그비는 IEEE 802.15.4-2003을 기반으로 한 작고, 저전력의 디지털 라디오를 사용하는 하이레벨 통신 프로토콜

IEEE 802.15.4-2003는 단거리 라디오 주파수를 사용하는 램프, 전자계량기, 소비자용 전자제품과 같은 근거리 개인 무선통신망의 기준이다.

보통 IoT기기끼리 통신을 위해 사용한다.

Zigbee 특징

1. 저전력 소모, 간단한 구현
2. 한번의 배터리 충전으로 수 개월, 또는 수년간 사용 가능
3. 활성 모드(수신, 송신), 슬립 모드를 가짐.
4. 디바이스, 설치, 유지 등 모두 상대적으로 낮은 비용으로 가능
5. 안전성(보안성)
6. 신뢰성
7. 유연성
8. 매우 작은 프로토콜 스택
9. 상호 호환가능 및 어느 곳에서나 사용 가능
10. 네트워크당 높은 노트 밀집(지그비의 IEEE 802.15.4 사용은 네트워크에서 많은 디바이스를 다루는 것을 가능케 함. 이러한 특징으로 방대한 센서 배열과 네트워크의 통제가 가능)
11. 간단한 프로토콜, 국제적으로 구현(지그비 프로토콜 스택 코드의 크기는 블루투스나 802.11의 사이즈에 비해 4분의 1 정도에 불과하다.)

통신 설정

CH : 통신 주파수 설정 - 통신하고 싶은 기기끼리 같아야 함 (범위 : B~1A)

ID : 통신하고 싶은 기기끼리 같아야 함 (범위  : 0000 ~ FFFF)

MY 값이 있는 경우

DH, DL은 각각 상대 zigbee의 MY 값과 같아야 한다.

MY 값이 없는 경우

DH와 SH, DL와 SL 값이 각각 상대 zigbee의 같아야한다

통신 거리 및 속도 실험

사용한 zigbee 모델은 digi사에서 만든 zbee (model : S2CTH / XB24CZPIT-004)

모든 테스트는 XCTU프로그램으로 테스트 함

통신 거리 테스트

실내 & 도심 : 3m ~ 5m

야외 : 70m ~ 80m

통신 속도 테스트

baud rate 9600으로 설정 시 (기본 설정인 듯) 3.61kbps

baud rate 230400으로 설정 시 7.33kbps

다른 설정들은 변경해도 유의미한 결과를 얻기 힘들었음

참고문헌

XBee Python Library

XBee-arduino

ZigBee 사용하기 - 코코아팹

지그비 무선 통신하기 - CreAmp

최단 경로 문제는 그래프 사이에서 두 노드 사이의 가장 짧은 경로를 찾는 문제이다. 최단 경로 알고리즘에는

1. 너비 우선 탐색 BFS

2. 다익스트라 알고리즘

3. 벨만-포드 알고리즘

4. 플로이드-워셜 알고리즘

이 있다

그래프

그래프는 상하위의 개념이 없이 각각의 노드와 노드들을 간선(edge)으로 연결한 자료구조이다.

지도 어플의 최단거리. 배송 최소이동거리, 지하철 노선도의 최단경로 등에서 활용되고 있다.

너비 우선 탐색

그래프에서 가까운 노드부터 탐색하는 알고리즘으로 간선의 길이가 없을 때 사용하는 알고리즘

a노드에서 인접한 노드 e, b, d, h로 이동하면서 탐색하는 알고리즘

def DFS(graph, root):
    open = [root]
    close = []

    while open:
        n = open.pop()
        close.append(n)
        if n not in close:
            close.append(n)
            open += graph[n] - set(close)
    return close

print(BFS(graph_list, root_node))

다익스트라

간선의 길이가 양수 일 때 사용하는 알고리즘이며 하나의 노드에서 다른 노드들까지 최단거리를 계산하는 알고리즘

1. 아직 선택되지 않은 노드 중에서 가장 간선의 길이가 짧은 노드를 선택한다.
2. 1번에서 선택된 노드와 연결된 다른 노드의 최단 거리를 갱신한다.
3. 탐색하지 않은 노드가 있으면 1번으로 돌아간다.

import heapq


def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    while queue:
        current_distance, current_destination = heapq.heappop(queue)

        if distances[current_destination] < current_distance:
            continue

        for new_destination, new_distance in graph[current_destination].items():
            distance = current_distance + new_distance
            if distance < distances[new_destination]:
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])

벨만-포드

간선의 길이가 음수일 때도 사용가능하다 사이클이 음의 값을 가지면 사용 불가능하다.

• 시작 노드에 대해서 거리를 0으로 초기화, 나머지 노드는 거리를 무한으로 설정
• 정점 수(n) -1 만큼 다음 과정을 반복
• 매 반복 마다 모든 간선 확인
• 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 거리 정보 갱신
• n-1번 반복 이후, n번째 반복에서도 거리 값이 갱신된다면 음수 순환이 존재

다익스트라는 방문하지 않는 노드 중에서 가장 가까운 노드를 방문했지만 벨만-포드는 매 반복마다 모든 간선을 확인한다는 것이 차이점이다.

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
INF = sys.maxsize

adj = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    adj[a].append((c, b))


def ford():
    ans = [INF] * (n + 1)
    ans[1] = 0
    for i in range(1, n):
        for j in range(1, n + 1):
            for c, b in adj[j]:
                if ans[j] == INF:
                    continue
                if ans[b] > c + ans[j]:
                    ans[b] = c + ans[j]
    for j in range(1, n + 1):
        for c, b in adj[j]:
            if ans[j] == INF:
                continue
            if ans[b] > ans[j] + c:
                print(-1)
                sys.exit()
    return ans


temp = ford()
for i in range(2, n + 1):
    if temp[i] == INF:
        print(-1)
    else:
        print(temp[i])

플로이드 와샬

모든 정점에서 다른 모든 정점으로의 최단거리를 계산할 때 사용하는 알고리즘

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

import math

def rhun(x, y, z):
    x_r = y_r = z_r = 0
    
    while True:
        max_num = max(x, y, z)
        min_num = min(x, y, z)
        
        if max_num < 18 or min_num < 6:
            break

        r = math.ceil((max_num - min_num) / 18)

        if max_num == x:
            if min_num == z:
                r = min(r, z // 6)
            else:
                r = min(r, (z - y) // 6)
            if r == 0:
                r = 1
            x -= r * 18
            z -= r * 6
            x_r += r
        elif max_num == y:
            if min_num == x:
                r = min(r, x // 6)
            else:
                r = min(r, (x - z) // 6)
            if r == 0:
                r = 1
            y -= r * 18
            x -= r * 6
            y_r += r
        elif max_num == z:
            if min_num == y:
                r = min(r, y // 6)
            else:
                r = min(r, (y - x) // 6)
            if r == 0:
                r = 1
            z -= r * 18
            y -= r * 6
            z_r += r

    print(x_r, y_r, z_r, "//", x, y, z)

# Example usage
rhun(60, 45, 30)

중국인의 나머지 정리

중국의 5세기 문헌인 손자산경(孫子算經)에 나오는 문제로, 내용은 다음과 같다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 중국인의 나머지 정리가 되었다고 한다.

\(m_1, m_2, \cdots, m_n\)이 쌍마다 서로소 즉, \(\gcd\left(m_i,m_j\right)=1,i\neq j\)이면, 다음 연립 합동식

$$x\equiv a_{i}\left ( \bmod\;m_{i} \right )\;\;\;\;\;\;\;\;i=1,2,3,4 \cdots n$$

를 만족하는 \(x\)는 \(\bmod \;(n_1 n_2 \cdots n_k)\)에서 유일하게 존재한다는 정리이다.

위의 경우를 만족하는 유일한 해 \(x\)는
\(x \equiv a_1M_1N_1 + a_2M_2N_2 + \cdots + a_kM_kN_k\;(\bmod \; M)\)

이렇게 구할수 있는데 여기서

\(M=n_1 n_2 \cdots n_k\)

\(M_i=M/n_i\)

\(N_i \equiv M_i ^ {-1} \; (\bmod \; n_i)\)이다.

예제로 \(x \equiv 2\;(\bmod \; 3),\;x \equiv 3\;(\bmod \; 5),\;x \equiv 2\;(\bmod \; 7)\)를 만족하는 \(x\)를 구해보자.
위의 공식에서 사용되는 변수 \(M, M_i, N_i\)를 먼저 구해보면
\(M = 3 \times 5 \times 7 = 105\)
\(M_1 = M / 3 = 35,\;M_2 = M / 5 = 21,\;M_3 = M / 7 = 15\)
\(N_1 \equiv M_1^{-1}\equiv 2\;(\bmod\;3)\)
\(N_2 \equiv M_2^{-1}\equiv 1\;(\bmod\;5)\)
\(N_3 \equiv M_3^{-1}\equiv 1\;(\bmod\;7)\)이다.
사용된 변수를 모두 계산했으니 위 공식대로 대입해보면
\(x \equiv 2M_1N_1 + 3M_2N_2 + 2M_3N_3\;(\bmod\;M)\)

\(\equiv 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1\;(\bmod\;105)\)

\(\equiv 23\;(\bmod\;105)\)

라는 해를 구할 수 있다.

증명

증명은 존재성과 유일성 두 가지로 나뉘는데 증명하기 앞서 알아두어야 할 정리부터 증명하고 시작하겠음

양의 정수 \(m\)과 \(a_1,a_2,\cdots,a_n\)에 대하여 \(m\)이 \(a1​,a2​,⋯,a_n​\)와 각각 서로소이면,
\(m\)과 \(a_1a_2\cdots a_n​\)은 서로소이다.

\(m\)과 \(a1​,a2​,⋯,a_n​\)이 서로소가 아니라고 가정하면 \(m\)과 \(a_1a_2\cdots a_n​\)의 공약수인 소수 \(p\)가 존재한다. \(p\mid a_1a_2\cdots a_n​\)이므로 \(p\mid a_i\)가 존재한다.

그러면 \(p\)는 \(a_i\)와 \(m\)를 모두 나누므로 가정에 모순된다.

양의 정수 \(m\)과 \(a_1,a_2,\cdots,a_n\)에 대하여 \(m\)이 \(a_1,a_2,\cdots,a_n\) 의 각각의 배수이면 \(m\)은 \(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)\)의 배수이다.

나눗셈 정리에 의하여 \(m=q\cdot\text{lcm}\left(a_1,a_2,\cdots,a_n\right)+r\)을 만족하는 정수 \(q,r\)이 유일하게 존재한다\((0\leq r<\text{lcm}\left(a_1,a_2,\cdots,a_n\right))\).

그런데 \(a_i\)가 \(m\)과 \(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)\)을 모두 나누므로 \(a_i\)는 \(r\)도 나눠야 한다.

이것은 모든 \(i\)에 대해 참이므로 \(r\)은 \(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)\)보다 작은 \(a_i\)​들의 공배수이다.

이걸 만족하는 값은 \(r=0\)밖에 없으며, 이는 곧 \(m\)이 \(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)\)의 배수이다.

​존재성

\(m=m _1m_2⋯m_n\)라고 하자. 또, \(n_k=\frac{m}{m_k}\)라고 놓자. 즉, \(n_k\)는 \(m_k\)를 제외한 나머지 \(m_i\)들의 곱을 의미한다.
도움정리 1로부터 \(\gcd\left(n_k,m_k\right)=1\)이다. 그럼 베주 항등식에 의해,
\(s_k n_k + t_k m_k =1\)을 만족하는 정수 \(s_k,t_k\)가 존재한다. 이를 합동식 형태로 고치면,
\(s_k n_k\equiv1\left(\bmod\,m_k\right)\)이다.

이제 \(x = a_1 n_1 s_1 + a_2 n_2 s_2 + \cdots + a_n n_n s_n\)라고 놓자. \(j \neq k\)이면 \(m_k\mid n_j\)이고, 따라서
\(x\equiv a_k n_k s_k \equiv a_k \cdot 1 = a_k\left(\bmod\,m_k\right)\)이다.(\(1<=k<=n\)인 임의의 자연수)
즉, \(x\)는 주어진 연립 합동식의 한 해이다.

유일성

\(x,\;y\)가 주어진 연립 합동식의 해라고 하자. 그러면,
\(x\equiv a_1\left(\text{mod}\,m_1\right),\;y\equiv a_1\left(\text{mod}\,m_1\right)\)
\(x\equiv a_2\left(\text{mod}\,m_2\right),\;y\equiv a_2\left(\text{mod}\,m_2\right)\)
\(x\equiv a_n\left(\text{mod}\,m_n\right),\;y\equiv a_n\left(\text{mod}\,m_n\right)\)이다.

그러므로, 임의의 \(k\,\left(1\leq k\leq n\right)\)에 대하여, \(x\equiv a_k\equiv y\left(\text{mod}\,m_k\right)\)이고, 그래서 \(x-y\equiv0\left(\text{mod}\,m_k\right)\)이다.

즉, \(x-y\)는 모든 \(m_k\)들의 배수이다. 따라서 도움정리 2에 의해, \(\text{lcm}\left(m_1,m_2,\cdots,m_n\right)\mid\left(x-y\right)\)이다.

그런데 \(m_1,m_2,\cdots,m_n\)들이 쌍마다 서로소이므로 \(m_1 m_2 \cdots m_n\mid\left(x-y\right)\)이다.

즉, \(x\equiv y\left(\text{mod}\,m_1 m_2 \cdots m_n\right)\)이고

이는 주어진 연립 합동식의 해가 유일함을 보인다.

RSA암호화 알고리즘에는 2개의 암호화 키가 사용됩니다. 하나는 모두에게 공개되는 공개키이고 하나는 공개하지 않는 개인만 알고 있는 개인키(비밀 키라고도 함)입니다. 공개키는 평문을 암호화할 때 사용되고 개인키는 암호문을 평문으로 복호화할 때 사용합니다.

RSA알고리즘의 안정성은 아주 큰 합성수는 인수분해하기 어렵다는 인수분해 문제의 어려움에 기반합니다.

오일러 정리

오일러 정리는 \(n\)과 서로소인 양의 정수 \(m\)이 다음 식을 만족한다는 정리입니다.

\( m^{\varphi \left ( n \right )}\equiv 1\left ( \textrm{mod}\,n \right ) \)

여기서 \( \varphi \left ( n \right ) \)는 오일러 파이 함수라고 불리며, \(n\) 이하의 양의 정수 중에서 \(n\)과 서로소인 수의 개수를 의미합니다.

예를 들어 6 이하의 양의 정수 중 6과 서로소인 수는 1,5로 두 개이기 때문에 \( \varphi \left ( 6 \right )=2\)입니다.

공개키 생성

1. 두 소수를 찾는다. \( p = 53, q = 59 \)

2. 두 소수를 곱한다. \( n = p*q = 53 * 59 = 3127\)    \(n\)이 첫 번째 공개키 재료

공개키 생성을 위한 재료(\(e\))가 하나 더 필요하고 \(e\)는 아래의 조건을 만족하는 숫자들 중 하나를 정하면 됩니다.

\( \varphi \left ( n \right ) \)와 서로소 관계이어야 한다.        \( \textrm{gcd}\,\left ( e,\varphi \left ( n \right ) \right ) = 1 \)

즉, \( e \)값은 \( \varphi \left ( n \right )=\left ( p-1 \right )\left ( q-1 \right )=3016\)와 서로소 관계인 3,5,7,9 중 하나를 선택하면 됩니다.

\( e=3 \)으로 정하겠습니다.

비밀키 생성

비밀키 생성에 필요한 \( d \)는 \( d \equiv e^{-1}\left ( \textrm{mod} \, \varphi \left ( n \right ) \right ) \)을 만족하는 수들 중 하나입니다. \( d=2011 \)로 정하겠습니다.

암호화

공개키 \((n,e)\)로 \(n\)보다 작은 평문 \(m\)을 암호화할 때, 암호문 \(c\)는 다음 식으로 구해집니다.

\( c≡m^{e} \left ( \textrm{mod}\, n \right ) \)

"melon"을 숫자로 변환했을 때 2033으로 가정하고 "melon"을 암호화 하면

\( c≡2033^{3} \left ( \textrm{mod}\, 3127 \right ) \)

암호문은 1983이 됩니다.

복호화

암호문 \(c\)를 개인키 \(d\)로 복호화할 때, 평문 \(m\)은 다음과 같이 구해질 수 있습니다.

\( m≡c^{d} \left ( \textrm{mod}\, n \right ) \)

\( c≡1983^{2011} \left ( \textrm{mod}\, 3127 \right ) \)

당연히 계산 결과는 2033입니다.

참고문헌

geeks for geeks - RSA Algorithm in Cryptography

DES

DES는 미국의 국가 안보국 NSA에서 IBM의 루시퍼 알고리즘을 개량하여 만든 대칭키 암호입니다.

DES는 루시퍼에서 128비트 키를 사용했던 것과 달리 키 길이를 56비트로 줄였고, 내부에서 사용하는 알고리즘도 일부 변경하였습니다.

미국 국립표준기술연구소 NIST는 DES를 1976년부터 2002년까지 표준 블록 암호로 인정했습니다만 현대에는 DES에 대한 공격 기법이 많이 연구되어 DES를 더이상 블록 암호의 표준으로 사용하지 않습니다.

DES는 혼돈 성질을 만족하기 위해 치환을, 확산 성질을 만족하기 위해 순열을 사용합니다.

치환과 순열을 매우 단순한 연산이므로 평문에 이들을 한 번 적용한다고 해서 암호학적 효과를 기대할 수는 없습니다. 그러나 이들을 여러 번 교차해서 반복 적용하면 혼돈과 확산의 성질을 모두 만족하게 된다고 알려져 있습니다.

이런 특성을 이용하여 치환이나 순열 같은 단순한 연산들로 한 라운드로 구성하고, 각 라운드를 여러 번 반복하여 암호학적 안전성을 확보하는 암호를 곱 암호(Product Cipher)라고 합니다.

DES는 8바이트(64비트)를 한 블록으로 하는 블록 암호이며, 전체 구조는 초기 순열, 최종 순열, 페이스텔 구조의 16 라운드, 그리고 각 라운드에 사용되는 48비트의 키를 생성하는 키 생성 함수(Key Generation)로 구성되어 있습니다.

DES 구조

페이스텔 구조

DES에서 라운드 함수를 적용하는 전체 과정은 페이스텔 구조를 이루고 있습니다.

페이스텔 구조는 데이터를 두부분으로 나누어 좌, 우 두부분에 교대로 비선형 변환을 적용시키는 구조를 말하며 이를 3단계로 나누면

입력으로 들어온 블록을 동일한 길이의 왼쪽 블록과 오른쪽 블록으로 나눕니다.

각 라운드마다 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 입력됩니다.

왼쪽 블록은 오른쪽 블록에 라운드 함수를 적용한 결과와 xor되어 다음 라운드의 오른쪽 블록으로 입력됩니다.

수식으로 표현하면

1. \( L_{0} = P[:len(P)/2], R_{0} = P[len(P)/2:] \)

2. \( L_{n+1} = R_{n} \)

3. \( R_{n+1}​=L_{n} ​\bigoplus F(R_{n}, K_{n}​) \)

블록 암호는 평문을 복호화 할 수 있어야 하므로, 일반적으로 암호화를 구성하는 각 함수들에 역함수가 존재합니다.

그러나 페이스텔 구조를 사용하면 \(​\bigoplus\)의 특성상 역함수가 존재하지 않아도 됩니다.

또한 암호화와 복호화의 구조가 동일하므로, 암호화에 사용한 라운드 키를 역순으로 입력하면 복호화가 이뤄집니다.

한편, 오른쪽 블록은 다음 라운드의 왼쪽 블록으로 어떠한 처리도 없이 입력됩니다.

이런 특성으로 인해 페이스텔 암호는 비페이스텔 암호와 같은 안전성을 갖기 위해 두 배 정도 라운드를 사용해야한다는 단점이 있습니다.

Step1 초기 순열 & Step 3 최종 순열

DES는 시작할 때 초기 순열을, 마지막에는 최종 순열을 수행하며 초기 순열과 최종 순열은 서로 역관계에 있습니다.
임의의 64비트 데이터에 초기 순열을 적용하고, 최종 순열을 적용하면 입력 값이 그대로 출력됩니다.
초기 순열과 최종 순열은 정해진 테이블을 이용하여 64비트 입력을 비트 단위로 전치합니다.
테이블의 n번째 값이 m일 때, 출력의 n번째 비트는 입력의 m번째 비트가 됩니다.
초기 순열과 최종 순열은 각각 초기 순열 테이블과 최종 순열 테이블을 이용합니다.

IPT = [58, 50, 42, 34, 26, 18, 10, 2,
       60, 52, 44, 36, 28, 20, 12, 4,
       62, 54, 46, 38, 30, 22, 14, 6,
       64, 56, 48, 40, 32, 24, 16, 8,
       57, 49, 41, 33, 25, 17, 9, 1,
       59, 51, 43, 35, 27, 19, 11, 3,
       61, 53, 45, 37, 29, 21, 13, 5,
       63, 55, 47, 39, 31, 23, 15, 7]
FPT = [40, 8, 48, 16, 56, 24, 64, 32,
       39, 7, 47, 15, 55, 23, 63, 31,
       38, 6, 46, 14, 54, 22, 62, 30,
       37, 5, 45, 13, 53, 21, 61, 29,
       36, 4, 44, 12, 52, 20, 60, 28,
       35, 3, 43, 11, 51, 19, 59, 27,
       34, 2, 42, 10, 50, 18, 58, 26,
       33, 1, 41, 9, 49, 17, 57, 25]

Step2. 라운드 함수

라운드 함수에는 오른쪽 블록만 입력되므로, 입력의 길이는 32비트입니다. 라운드 함수는 확장 순열, 라운드 키 결합, 치환 테이블 그리고 고정 순열로 이루어져 있습니다.

Step 2.1. 확장 순열과 라운드 키 결합

확장 순열은 입력을 비트 단위로 전치하는 동시에, 전체 길이를 48비트로 확장합니다.

이 과정에서 32비트의 입력값을 4비트씩 8개의 부분으로 나누고, 테이블을 참조하여 각각을 6비트로 확장합니다.
이 과정은 테이블만 다를 뿐, 초기 순열, 최종 순열과 같은 방식으로 이뤄집니다.

라운드 키 결합은 확장 순열로 나온 출력을 라운드 키와 \(​\bigoplus\) xor 하는 것입니다.

Step2.2. S-Box와 고정 순열

S-Box는 라운드 키 결합에서 출력된 48비트 결과 값을 32비트로 축소합니다.

S-Box는 4개의 행과 16개의 열로 이루어진 표를 사용하는데, 표의 각 값은 4비트로 표현되는 수입니다.

S-Box가 적용되는 과정은 다음과 같습니다.

먼저, 입력을 6비트씩 8개의 부분으로 나눕니다. 여섯 비트 중 첫 번째와 마지막 비트로 행을 결정하고, 나머지 네 개의 비트로 열을 결정합니다. 그 뒤, S-Box의 표에서 행과 열을 참조하여 값을 반환합니다. DES에서는 여섯 비트로 자른 부분마다 다른 S-Box를 사용합니다.

S-Box로 길이를 축소하고 나면, 고정 순열(Straight P-Box)로 다시 비트 단위 전치가 이뤄집니다.

키 생성 함수

키 생성 함수는 64비트의 입력을 받아 각 라운드에 필요한 48비트 라운드 키를 생성하는 함수입니다. 

이 함수는 패리티 비트 제거, 쉬프트, 압축 순열로 구성되어 있습니다.

패리티 비트 제거

패리티 비트 제거는 입력에서 패리티 비트를 제거하고, 남은 56비트에 순열을 적용하는 과정입니다.

DES의 비밀키에서 각 바이트의 가장 오른쪽 비트는 자신이 속한 바이트의 나머지 7비트에 대한 홀수 패리티 비트입니다. 홀수 패리티 비트란 한 바이트를 이진수로 표현했을 때, 1의 개수가 홀수가 되도록 덧붙인 비트를 말합니다. 예를 들어, 1010101에는 1이 4개 있습니다. 홀수 패리티 비트를 적용하면 끝에 비트 1을 덧붙여서, 10101011을 전송해야 합니다.

패리티 비트는 통신 중에 비트 반전이 일어나지 않았음을 보증하는 역할을 합니다. 홀수 패리티 비트를 사용하여 통신할 때, 수신한 바이트 중 1의 갯수가 짝수인 바이트가 있다면 그 바이트에서 임의의 비트에 반전이 일어났음을 수신자가 알 수 있습니다. 이를 확인한 수신자는 손상되지 않은 데이터를 얻기 위해 재전송을 요구할 수 있습니다.

쉬프트

쉬프트는 입력을 왼쪽 28비트와 오른쪽 28비트로 나누어 각각을 1비트나 2비트만큼 왼쪽으로 순환 쉬프트하는 과정입니다. 1, 2, 9, 16 라운드에서는 1비트, 나머지 라운드에서는 2비트만큼 쉬프트합니다.

10101111을 왼쪽으로 1비트 순환 쉬프트하면, 왼쪽 끝의 비트가 오른쪽 끝으로 이동하여 01011111이 됩니다. 마찬가지로 2비트를 왼쪽으로 순환 쉬프트하면 왼쪽 끝의 '10'이 오른쪽으로 이동하여 10111110이 됩니다.

압축 순열

압축 순열은 56비트의 입력을 48비트 길이로 압축하는 과정입니다. 수행 방법은 앞서 설명한 순열들과 같습니다.