컴퓨터 네트워크 PART 02 프로토콜 (chapter 05 데이터 압축과 보안) 임효택 E-mail : htlim@dongseo.ac.kr Home page : http://kowon.dongseo.ac.kr/~htlim

Chapter 05 데이터 압축과 보안 데이터 압축 5.1.1 데이터 압축 허프만(Huffman) 코드 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 데이터 압축 5.1.1 데이터 압축 허프만(Huffman) 코드 허프만 코드는 가장 널리 쓰이는 압축 방법 문자가 나타나는 빈도수에 따라 그 크기를 다르게 하는 것 : 빈도수 의존 코드(frequency dependent code) 모음과 'L', 'R', 'S', 'N', 'T' 등과 같이 자주 나타나는 문자들은 더 작은 비트를 할당 예제 : 각각의 확률이 0.5, 0.3, 0.15, 0.05인 4개의 값 x1, ..., x4가 있다고 가정 만일 x1, ..., x4값 각각을 나타내기 위해 코드 값 00, 01, 10 11을 사용한다 면 X값을 전송하기 위해 2비트가 필요 그러나 만일 x1을 나타내기 위해 0, x2를 나타내기 위해 10, x3을 나타내기 위해 110, x4를 나타내기 위해 111을 사용한다면, 평균 0.5 x 1 + 0.3 x 2 + 0.15 x 3 + 0.05 x 3 = 1.7 비트가 필요

Chapter 05 데이터 압축과 보안 접두코드(prefix code) 허프만 알고리즘 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 접두코드(prefix code) 허프만 알고리즘 단 하나의 노드만을 가지고 있는 이진 트리와 각 문자를 매핑 각 트리에 문자들의 빈도수를 할당: 트리의 가중치(weight) 두개의 가장 작은 가중치를 가지고 있는 트리를 찾아 하나의 트리로 합치고 새로운 루트 노드를 만들어 낸다.(이 새 트리의 가중치는 합쳐진 두 트리의 가중치의 합) 마지막으로 하나의 트리가 남을 때까지 이 과정을 반복 이 과정이 끝났을 때 원래 노드들의 각각은 마지막 이진 트리의 말단 노드(leaf)가 된다. 이진 트리에서 루트로부터 말단 노드에 이르는 유일한 길(path)이 있게 되고 이 길이 허프만 코드가 된다. 그것은 각 왼쪽 자식 포인터에 0을 할당하고 오른쪽 자식 포인터 에 1을 할당해서 결정

PART 02 프로토콜 Chapter 05 데이터 압축과 보안 허프만 코드 생성 과정 [그림 5.2] 허프만 코드의 생성 과정

Chapter 05 데이터 압축과 보안 Run Length Encoding PART 02 프로토콜 Chapter 05 데이터 압축과 보안 Run Length Encoding 허프만 코드는 알려져 있는 문자의 빈도수를 알아야 함 팩스는 종이의 밝은 부분과 어두운 부분에 해당하는 비트를 전송 →직접적으로 문자를 전송하지 않음 Run Length Encoding 기법은 단순하지만 확실한 접근을 시도 → 0 또는 1이 계속 해서 나타나는 비트 문자열을 분석해서 모든 비트를 보내는 대신에 다만 0과 1이 몇 번 나타나는 횟수를 전송 팩시밀리 신호를 부호화하고 압축하는데 사용되는 간단하면서도 효율적인 데이터 압축 알고리즘

Chapter 05 데이터 압축과 보안 팩시밀리 전송을 위해 페이지를 줄단위로 주사하고 각 줄을 따라 일정 간격의 점들 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 팩시밀리 전송을 위해 페이지를 줄단위로 주사하고 각 줄을 따라 일정 간격의 점들 에 의해 반사되는 빛의 밝기를 측정 흰점을 0으로 나타내고 검은점을 1로 나타낸다고 가정하자. 만일 팩시밀리가 1인치당 200줄을 스캔하고, 각 줄마다 1인치당 200개의 점들의 밝기를 측정한다면 8.5인치×11인치 크기의 페이지를 200x200x8.5x11=3.74x10**6개의 비트로 표현 이 비트들을 9600bps 모뎀으로 전송한다면 6.5분이 걸림 팩시밀리는 긴 0들의 열을 전송하는 대신에 두 1사이의 연속적인 0의 개수를 보낸다. 예를 들어 0a가 a개의 연속적인 0을 나타낸다고 표기하면, 1 0a 1 0b 1 0c 1 0d와 같은 스트링(string)은 A B C D와 같이 부호화된다. 여기서 A는 a의 이진수 표현이고, B는 b의, C는 c의, D는 d의 이진수 표현이다. 따라서 만일 a = 600(3인치 길이의 흰점에 해당)이면 A=1001011000 이 되고 따라서 600개의 0을 전송하는 대신에 단지 10비트만 전송하면 된다.

Chapter 05 데이터 압축과 보안 상대적 인코딩(Relative Encoding) PART 02 프로토콜 Chapter 05 데이터 압축과 보안 상대적 인코딩(Relative Encoding) 비디오 전송에서 이미지들은 팩스의 어둡고 환한 이미지 전송과 텍스트 파일 전송에 비해 매우 복잡 전에 소개된 방법는 이미지 압축에 도움이 되지 않음 하나의 비디오 이미지는 거의 반복을 가지고 있지 않지만 여러 이미지들에 대해서는 많은 반복이 있음 상대적 인코딩은 각각의 프레임을 개별적인 단위로서 다루고 압축하려고 시도하지 않고 각 프레임이 전의 것보다 얼마나 다른지를 고려 정보를 압축하고 보내는 것은 프레임들간의 차이가 아주 작을 때 효과적이 된다.

Chapter 05 데이터 압축과 보안 상대적 인코딩의 원리 처음 프레임은 보내지고 수신기의 버퍼에 이것이 저장 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 상대적 인코딩의 원리 처음 프레임은 보내지고 수신기의 버퍼에 이것이 저장 송신기는 두 번째 프레임을 처음 것과 비교하고 그 차이를 인코드 그리고 그것을 프레임 포맷으로 보내게 된다 수신기는 그 프레임을 얻고 그 프레임이 가지고 있는 차이를 적용해서 송신 기가 가졌던 두 번째 프레임을 만들어 냄 두 번째 프레임을 버퍼에 저장하고 계속해서 새로운 프레임에 대해서 위의 과정을 반복

Chapter 05 데이터 압축과 보안 Lempel-Ziv 인코딩 최근에 데이터를 압축하는 또하나의 방법 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 Lempel-Ziv 인코딩 최근에 데이터를 압축하는 또하나의 방법 흔하게 되풀이되어지는 문자열을 찾아서 단지 한번만 저장 한번 저장된 동일한 단어나 문장은 원래의 것을 가리키는 포인터와 길이를 나타 내는 값으로 대치 UNIX 압축 명령(compress 명령어)와 MS-DOS의 ARC 유틸리티에서 이 알고리즘이 사용 이 알고리즘을 사용하면 긴 파일을 거의 1/2길이로 압축 "the other one is the oldest”을 Lempel-Ziv 알고리즘으로 압축 the o[1,3]r[4,2]is[3,1][1,5]ld[3,1][16,1][1,1] [1,3]에서 1은 문장의 첫 번째 문자를 의미하며 3은 길이가 3임을 의미한다.

Chapter 05 데이터 압축과 보안 반복되는 문자열의 길이가 길수록 이 알고리즘의 효율은 증가 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 반복되는 문자열의 길이가 길수록 이 알고리즘의 효율은 증가 Lempel-Ziv 알고리즘의 실제구현은 위에서 설명한 원래의 알고리즘과 약간 다르다. 즉 실제로는 구현이 쉽도록 수정된 알고리즘을 사용하게 되는데 대신에 압축율 이 조금 떨어진다.

Chapter 05 데이터 압축과 보안 보안 5.2.1 암호화 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 보안 5.2.1 암호화 일반적으로 컴퓨터 시스템에서 사용되는 정보 암호화는 특정한 키(key)값을 이용하여 평문(plain text)으로 된 정보를 암호문(cipher text)으로 바꾸는 작업.

Chapter 05 데이터 압축과 보안 고전적인 암호 방식 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 고전적인 암호 방식 고전적인 암호 방식 중 하나는 시져(Julius Caesar) 황제가 만든 것으로서 각 문자를 알파벳 순서상 세 자리 뒤의 문자로 대체하는 방법에 기초 예: 영어 문자 알파벳을 사용하여 이 방법에 의해서 대문자로 변환하면 평문 'Caesar'는 암호문 'FDHVDU'가 된다. 이 방법은 암호문을 세 자리 대신 k 자리만큼 문자를 이동시키는 것으로 일반화 이 방법은 k를 키로 한 순환이동 방법: 대체암호(substitution cipher) 치환암호(transposition cipher) : 대체암호 방식과 함께 고전적인 암호 방식의 한 부류 평문의 심볼들을 재배치하는 방법이다.(순서를 재배열)

Chapter 05 데이터 압축과 보안 관용 암호 방식(conventional cryptosystem) PART 02 프로토콜 Chapter 05 데이터 압축과 보안 관용 암호 방식(conventional cryptosystem) 관용 암호 방식은 가장 널리 알려지고 또 일반적으로 사용되고 있는 암호 방식 컴퓨터 시스템과 통신망 등의 정보 암호화에 많이 이용 암호화 키와 복호화 키가 동일한 대칭 알고리즘을 사용 통신망에서 사용될 경우 일반적으로 세션키(session key) 또는 비밀키(secret key) 로 불리우는 이 대칭키를 암호화 이전에 서로 분배(distribution)해야하는 부담

Chapter 05 데이터 압축과 보안 키분배는 비용 증대와 시간 지연이라는 단점을 가진다. PART 02 프로토콜 Chapter 05 데이터 압축과 보안 키분배는 비용 증대와 시간 지연이라는 단점을 가진다. 그러나 암호화 작업과 복호화 작업에서 계산량이 적고 빠르다는 장점으로 인하여 현재 가장 많이 사용 사용 예 미국 IBM에서 개발한 DES: 56비트의 키를 사용 IDEA(International Data Encryption Standard) 128비트의 비교적 큰 키를 사용 PGP(Pretty Good Privacy)에서 사용 일본 NTT에서 개발한 FEAL(fast data encryption algorithm) 등 특히 DES는 가장 일반적으로 사용되는 암호 방식으로서 UNIX의 패스워드 처리 및 자료 저장에 응용 [정의 5-1] 관용 암호 방식의 조건: p 248

PART 02 프로토콜 Chapter 05 데이터 압축과 보안 [그림 5.4] 관용 암호 방식 개념도

Chapter 05 데이터 압축과 보안 공개키 암호 방식(public key cryptosystem) PART 02 프로토콜 Chapter 05 데이터 압축과 보안 공개키 암호 방식(public key cryptosystem) 관용 암호 방식의 가장 큰 문제점이었던 키분배 문제를 해결한 암호 방식 암호화 키와 복호화 키가 서로 다른 비대칭 알고리즘을 사용하고 암호화 키는 안전한 경로를 사용할 필요 없이 공개해도 무방하다는 특징을 갖는다.

Chapter 05 데이터 압축과 보안 키분배에 따르는 부담이 크게 줄어 듬 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 키분배에 따르는 부담이 크게 줄어 듬 통신망에서 사용하기에는 관용 암호화 방식보다 더 적합하다고 판단되어짐 암호화 및 복호화 작업에 필요한 계산량이 너무 크다는 치명적인 단점 효율적인 고속 하드웨어의 지원이 없이는 현실적으로 적용하기 어렵다. 대표적인 알고리즘은 최초의 공개키 방식으로 알려져 있는 RSA(Rivest, Shamir, Adleman) 알고리즘 [정의 5-2] 공개키 암호 방식의 조건 : p249

PART 02 프로토콜 Chapter 05 데이터 압축과 보안 [그림 5.5] 공개키 암호 방식 개념도

Chapter 05 데이터 압축과 보안 공개키 분배 방식(public key distribution cryptosystem) PART 02 프로토콜 Chapter 05 데이터 압축과 보안 공개키 분배 방식(public key distribution cryptosystem) 공개키 분배 방식은 관용 암호 방식의 키분배 부담을 해결한 대칭 알고리즘 방식이다. 이 방식의 기본적인 아이디어는 관용 암호 방식의 암호화 및 복호화 작업의 계산량이 적다는 장점과 공개키 암호 방식의 키를 공개할 수 있다는 장점을 결합하는 것이다. [그림 5.7] 공개키 분배 방식 개념도

Chapter 05 데이터 압축과 보안 디지털 서명(digital signature) PART 02 프로토콜 Chapter 05 데이터 압축과 보안 디지털 서명(digital signature) 디지털 서명은 일반적인 문서 서명의 개념을 컴퓨터에 도입한 것으로서, 하나의 전자적인 메세지가 유일한 것이며 또한 그 문서의 전송자가 누구라는 것을 추적하거나 증명할 수 있도록 하는 방법을 말한다. 디지털 서명은 메세지 송신자의 인증이 본래 손으로 쓰여진 서명과 같은 역할을 하는 것으로 생각한다. 디지털 서명은 전산화된 업무 및 회계 처리, 그리고 인터넷을 통한 전자 우편이나 정보의 전달에 주로 이용 보안 시스템의 중요성이 높아질수록 활용도가 매우 높아질 것으로 기대되는 기술 [정의 5-4] 디지털 서명의 조건

Chapter 05 데이터 압축과 보안 인터넷에서의 보안 공개 네트워크(public Network) PART 02 프로토콜 Chapter 05 데이터 압축과 보안 인터넷에서의 보안 공개 네트워크(public Network) 전화망이나 인터넷처럼 네트워크 상의 개체들이 상호 자유롭게 정보를 주고받을 수 있도록 기반구조가 되는 네트워크 사설 네트워크(Private Network) 한 조직이나 개인이 소유한 네트워크, 해당 조직에 관련된 사용자만 사용 가능 가상 사설망, Virtual Private Network 인터넷과 같은 Public Network를 사용하여 private network를 구축하게 해주는 기술 혹은 네트워크

Chapter 05 데이터 압축과 보안 5.3.1 IPSec (IP Security Protocol) PART 02 프로토콜 Chapter 05 데이터 압축과 보안 5.3.1 IPSec (IP Security Protocol) IPSec은 전송모드(Transport mode)와 터널모드(Tunnel mode)를 제공 전송 모드 IP 페이로드만 암호화 되며, 원래의 IP Header는 그대로 둔다. 원본 패킷에 대하여 최소의 바이트 수만 추가된다는 장점 공개 네트워크 상에서의 모든 장비가 해당 패킷에 대한 최종 목적지를 부가적인 작업 없이 알 수 있다. [그림5.9]와 [그림 5.10]은 터널모드를 적용하기 전과 후의 패킷 형태이다. [그림 5.9] IPSec 전송모드를 적용하기 전의 패킷 [그림 5.10] IPSec 전송모드를 적용한 후의 패킷

PART 02 프로토콜 Chapter 05 데이터 압축과 보안 터널 모드 모든 초기의 IP Datagram이 암호화 되며, 기존의 원본 패킷을 기초로 안호화된 새로운 IP 패킷이 만들어진다. 라우터와 같은 네트워크 장비가 IPSec 프로토콜 상에서의 Proxy로 동작할 수 있다. 전체 패킷을 암호화 하므로, 실질적인 전송 호스트와 목적지는 노출되지 않으므로 침입을 위한 분석을 하기가 어렵다. 가상의 터널이 존재 [그림 5.11]과 [그림 5.12]는 터널 모드를 위하여 암호화된 패킷의 형태를 각각의 IPv4와 IPv6로 나타낸 것이다. [그림 5.11] IPSec 터널 모드 적용 전 패킷 [그림 5.12] IPSec 터널 모드 적용 후 패킷

Chapter 05 데이터 압축과 보안 5.3.2 SSL (Secure Socket Layer) PART 02 프로토콜 Chapter 05 데이터 압축과 보안 5.3.2 SSL (Secure Socket Layer) 양방향 프로토콜, Netscape Communications Corporation이 인터넷 상의 보안과 기밀을 보장하기 위해 개발한 규약 SSL 규약은 서버와 클라이언트의 진위 확인을 하도록 해준다. 암호화와 인증, 메시지 확인 규칙 등의 방법을 통해 송수신 경로의 보안과 안정성을 유지시켜 줄 수 있다. 양방향 핸드쉐이크 방식을 띄는 프로토콜 완전 핸드쉐이크 방식, 지속적 세션 수행 방식

PART 02 프로토콜 Chapter 05 데이터 압축과 보안 Full handshake 방식

PART 02 프로토콜 Chapter 05 데이터 압축과 보안 Resume Session

Chapter 05 데이터 압축과 보안 5.3.3 VPN에서의 IPSec과 SSL의 비교 PART 02 프로토콜 Chapter 05 데이터 압축과 보안 5.3.3 VPN에서의 IPSec과 SSL의 비교 Virtual Private Networks(VPNs)는 그들의 내부적인 Private Network를 사용하여, 외부 인터넷으로의 확장성을 제공한다. VPN은 외부에 대하여 폐쇄적인 환경을 구축하고자 하는 분야에서 널리 사용 IPSec과 SSL을 VPN에 적용함으로 인한 장단점. 장점 : 응용 계층 프로토콜에 독립적인 보안 연결을 제공 단점 : 세 가지의 관점에서 단점을 분석 관점 1 : 제한성 관점 2 : 확장성 및 호환성 관점 3 : 플랫폼에 대한 제한