**Cryptography and Network Security

Cryptography**

암호화
• 송신자와 수신자 사이에서 안전하게 메시지를 전송하고 싶음

• 도청자가 메시지를 이해할 수 없음

암호화와 관련된 용어
• 평문(Plaintext): 암호화되기 전의 텍스트
• 암호문(Ciphertext): 암호화된 텍스트
• 암호화(Encryption): 텍스트를 알아볼 수 없도록 만드는 과정
• 복호화(Decryption): 알아볼 수 없는 텍스트를 다시 복원하여 읽을 수 있게 만드는 과정
• 키(Key)

• 텍스트를 암호화하는 데 사용되는 숫자(또는 숫자 집합)
• 암호문을 해독하기 위해 키가 필요함

암호화 알고리즘

• 대칭키 암호화 알고리즘(Symmetric-key algorithm)

• 암호화/복호화에 동일한 키 사용
  • 비대칭키 암호화 알고리즘(Asymmetric-key algorithm)
• 암호화/복호화에 서로 다른 키 사용

대칭키 암호화

• 앨리스(송신자)와 밥(수신자)이 비밀 키를 공유함
• 앨리스는 키를 사용하여 메시지를 암호화함
• 앨리스는 암호화된 메시지를 밥에게 전송함
• 밥은 키를 사용하여 메시지를 해독함
• 이브(도청자)는 키 없이는 메시지를 읽을 수 없음

비대칭키 암호화

• 밥은 공개/비밀 키 쌍을 가지고 있음
• 밥은 공개 키를 공개하고, 비밀 키는 비밀리에 보유함
• 앨리스는 밥의 공개 키를 사용하여 메시지를 암호화함
• 메시지는 밥의 비밀 키를 사용해서만 복호화할 수 있음 → 밥만이 이 메시지를 열 수 있음

대칭키 vs. 비대칭키

대칭키

• 암호화/복호화에 동일한 키 사용

비대칭키

• 암호화와 복호화에 서로 다른 키 사용

대칭키 vs. 비대칭키

Symmetric-key Cryptography

전통 암호화 방식
• 고전적인 방법

• Julius Caesar가 로마 제국 시대에도 사용한 방식

치환 암호(Substitution ciphers)

• 평문의 각 문자를 다른 문자로 대체하는 방식
• 단일 알파벳 치환

• 평문에서 두 문자가 같으면 암호문에서도 같음
  • 다중 알파벳 치환
• 평문에서 같은 문자라도 암호문에서는 다를 수 있음

치환 암호

• 시저 암호라고도 불리는 치환 암호의 기본 형태
• 알파벳을 좌우로 이동하여 암호문을 생성
• 예: 앞으로 3글자 이동
• A → D, B → E, ..., W → Z, X → A, Y → B, Z → C
• 예시: 평문이 "HELLO"이고 키가 15일 때 암호문을 생성하라
• 키가 15일 때, 암호문 "WTAAD"를 해독하라

전치 암호(Transposition ciphers)

• 문자의 위치를 변경하여 암호문을 생성
• 예시

• 메시지를 네 개의 블록으로 나눔
• 블록을 아래 상자에 나타난 순서로 재배열

• 평문 "HELLOMYDEAR"을 아래 전치 암호를 사용하여 암호문으로 만들어라
• 암호문이 "ELHLMDOYAZER"인 경우, 아래 전치 암호를 사용하여 평문은 무엇인가?

현대 암호화 방식

• 문자 기반에서 비트 기반으로
• 텍스트 데이터뿐만 아니라 멀티미디어도 암호화 필요

XOR 암호

• 평문과 키에 비트 단위 XOR 연산을 적용하여 암호문을 생성
• 평문: 01010111 01101101 01101011 01101011 - "Wiki"
• 키: 11110011
• 암호문: 10100100 10011010 10011000 10011010
• 복호화를 위해 암호문과 키에 XOR 연산을 적용

회전 암호

• 입력 비트를 좌우로 이동하여 암호문을 생성
• 전치 암호의 한 종류

S-박스

• S-박스(Substitution box): N비트를 입력으로 받아 M비트를 출력함

P-박스(Permutation box)

• 입력을 전치함
• 직접 치환, 확장 치환, 압축 치환 등

DES

• 데이터 암호화 표준(Data Encryption Standard)
• 대표적인 대칭키 암호화 알고리즘
• IBM에서 설계
• 키 = 56비트 (+ 8 패리티 비트)
• 라운드 암호의 한 종류

• 라운드 암호: 안전성을 향상시키기 위해 메시지를 여러 번 암호화
  • 라운드 키 생성기는 단일 64비트 문자열 (56비트 키 + 8 패리티 비트)로부터 16개의 48비트 하위 키를 생성

DES 흐름도

• 한 라운드 DES
• Feistel 함수 DES
  • 1977년에 미국의 표준 암호화 방식으로 선정
  • 56비트 키
  • DES에 대한 공격: 무차별 대입 공격
• 모든 가능한 키를 시도함
• 2^56 = 72,057,594,037,927,936
  • 1998년, 슈퍼컴퓨터 "Deep Crack"이 키를 56시간만에 찾음
  • 6개월 후, Deep Crack과 distributed.net이 함께 작업하여 22시간 15분만에 키를 찾음
  • 1999년, DES는 여전히 표준 암호화 방식이지만 Triple DES (3DES)가 권장되는 방법이 됨

Triple DES (3DES)

• 56비트 키는 너무 짧기 때문에 키 크기를 늘리기 위해 세 번 암호화

• Key1 = Key3인 경우, 키 크기는 112비트
• 세 개의 다른 키를 사용하는 경우, 키 크기는 168비트
• 암호화 → 복호화 → 암호화 방식:
  • DES와의 호환성을 위해
  • Key1 = Key2 = Key3인 경우 DES와 동일

AES

• 고급 암호화 표준(Advanced Encryption Standard)
• 3DES의 짧은 키를 보완하기 위해 개발됨
• 2002년에 표준 암호화 방식으로 선정
• 키 크기: 128, 192 또는 256

• AES 흐름
• AES 라운드

Asymmetric-key Cryptography

RSA

• Rivest, Shamir, and Adleman에 의해 개발된 RSA 알고리즘
• 공개 키: e
• 개인 키: d

RSA: 키 생성

• Bob은 공개 키와 개인 키를 생성함
– 두 개의 소수인 p와 q를 선택함
– n=pxq
• n은 암호화와 복호화에 사용되는 "모듈러스"임
– Ф=(p-1)x(q-1)
– 무작위 수 e를 선택함
– d를 선택하여 dxe=1modФ이 되도록 함
• 예: Ф=60인 경우, 1modФ=1, 61, 121, 181,...
• Bob은 e와 n을 공개함: 공개 키
• Bob은 d와 Ф를 공개하지 않음: 개인 키

RSA: 암호화

• Alice가 Bob에게 메시지를 보내려면, Alice는 다음과 같이 암호문을 계산함
• C = Pe(mod n)

RSA: 복호화

• Bob은 d를 알고 있으므로 다음과 같이 암호문을 해독함
• P = Cd(mod n)
• d가 없으면 메시지를 해독할 수 없음. 따라서 Bob만이 이 메시지를 해독할 수 있음

RSA: 예시

• Bob은 키를 생성함 – p=7, q=11을 선택함
– n=7x11=77
– Ф=6x10=60
– e=13을 선택함
– d=37이라면 조건이 만족함(13x37=481, 481mod60=1)
– e와 n을 공개함

RSA: 예시

• Alice는 Bob에게 메시지를 보내려고 함
• 평문: 5라고 가정함
• 암호문은 다음과 같이 계산됨
• C=513 mod77=26
• 암호문: 26
• 이를 Bob에게 보냄

RSA: 예시

• Bob은 26을 받았습니다. 다음과 같이 암호문을 해독함
• P=2637 mod77=5
• 따라서 Alice가 보낸 메시지는 "5"입니다.

RSA: 실제 사용 예

• p와 q는 512비트 소수 중에서 선택됨 - 매우 큰 소수

RSA: 실제 사용 예

• p와 q에서 n과 Ф를 계산함

RSA: 실제 사용 예

• e를 선택하고 적절한 d를 찾음
• 평문이 P인 경우

RSA: 실제 사용 예

• 암호문을 생성함. C = Pe(mod n)
• Bob이 C를 받으면 다음과 같이 암호문을 해독함
• P = Cd(mod n)

RSA

• 장점
– 대칭 키 알고리즘을 사용하려면 송신자와 수신자가 비밀 키를 공유해야 함
– 비밀 키를 비밀리에 공유하기 어려움
– RSA는 키 공유 과정을 필요로하지 않음
• 단점
– 복잡하여 속도가 느림
• 사용 예시
– RSA를 사용하여 비밀 키를 전송한 후, 대칭 키 암호를 사용하여 통신함

Diffie-Hellman

• 비밀 키를 공유하기 위한 방법 - 포인트: x와 y는 직접 전송되지 않음
• Alice가 Bob에게 비밀 키를 보내려고 함
– Alice는 p와 g를 선택하고 Bob에게 보냄. p는 소수임
– Alice는 수 x를 선택하고 R1을 계산함
• R1=gxmodp
– Bob은 수 y를 선택하고 R2를 계산함
• R2=gymodp
– Alice는 R1을 Bob에게 보내고, Bob은 R2를 Alice에게 보냄
– Alice는 K를 계산함
• K=(R2)x modp
– Bob은 K를 계산함
• K=(R1)y modp

Diffie-Hellman: 예시

• g=7이고 p=23이라고 가정함
• Alice: x=3을 선택함. R1=73mod23=21.
• Bob: y=6을 선택함. R2=76 mod23=4.
• Alice는 21을 Bob에게 보냄
• Bob은 4를 Alice에게 보냄
• Alice는 K를 계산함: K=43 mod23=18
• Bob은 K를 계산함: K=216 mod23=18
• K는 공유된 비밀 키임

Diffie-Hellman

• Eve(도청자)가 R1과 R2를 가로챘다고 가정해봅시다.
• Eve는 비밀 키를 알아내기 위해 x와 y를 찾아야하지만, 이는 매우 어려움

Network Security

보안 서비스

• 메시지 기밀성: 도청자가 송신자에서 수신자로 전송된 메시지를 이해할 수 없음
  • 메시지 무결성: 메시지가 수신자에게 도달하기 전에 변경되지 않음
  • 메시지 인증: 메시지가 송신자로부터 실제로 전송된 것임을 확인함
  • 메시지 부인 방지: 송신자가 메시지를 보냈다고 부인할 수 없음
  • 개체 인증: 사용자의 신원을 확인함

메시지 기밀성

• 대칭 키를 사용하여 기밀성 보장
• 대칭 키는 일반적으로 비대칭 키 암호화를 사용하여 전송됨
• 비대칭 키를 사용하여 기밀성 보장
• 송신자와 수신자 모두 공개/비공개 키 쌍을 생성해야 함
• 복잡성 때문에 긴 메시지에는 적합하지 않음

메시지 무결성

• 암호화/복호화는 기밀성을 제공하지만 무결성은 제공하지 않음
• 때로는 문서에 기밀성이 필요하지 않지만 무결성이 필요함
• 메시지 다이제스트를 사용하여 메시지가 전송 중에 수정되지 않았음을 보장함
• 송신자는 해시 함수를 사용하여 메시지 다이제스트를 생성함
• 송신자는 메시지와 메시지 다이제스트를 수신자에게 전송함
• 수신자는 동일한 해시 함수를 사용하여 메시지 다이제스트를 생성하고 송신자로부터 받은 메시지 다이제스트와 비교함
• 메시지 다이제스트는 비밀리에(암호화를 사용하여) 전송되어야 함

해시 함수

• 메시지 무결성을 제공하기 위해 사용되는 해시 함수는 다음과 같은 특성을 가져야 함
• 일방성: 다이제스트로부터 메시지를 유추할 수 없음
• 약한 충돌 저항성: 메시지 x에 대해 동일한 해시 값이 나오는 다른 메시지 y를 찾을 수 없음
• 강한 충돌 저항성: 두 개의 메시지 x와 y를 찾을 수 없음, 그들의 해시 값이 동일함

해시 함수: SHA-1

• Secure Hash Algorithm-1
• 미국 국립표준기술연구소(NIST)에서 설계됨
• 160비트 메시지 다이제스트 생성
• 블록에서의 결과가 다음 블록 계산에 사용되기 때문에 메시지의 작은 변화도 완전히 다른 해시 값으로 이어짐
• SHA1("Thequickbrownfoxjumpsoverthelazydog") = 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
• SHA1("Thequickbrownfoxjumpsoverthelazydog.") = 408d94384216f890ff7a0c3528e8bed1e0b01621

메시지 인증

• 해시 함수는 메시지 무결성을 제공할 수 있지만 메시지가 실제로 송신자에 의해 전송되었음을 보장할 수 없음
• 메시지 인증을 위해 메시지 다이제스트를 생성하는 데 키를 사용해야 함

MAC (Message Authentication Code)

• 키가 포함된 해시 함수: 키를 포함한 해시 함수
• Alice와 Bob 사이의 공유 키를 사용하여 메시지 다이제스트 생성

HMAC

• HMAC(Hashed MAC): 메시지 인증을 위한 표준 방법

디지털 서명

• MAC를 사용하려면 공유 비밀 키가 필요함 - 키 공유가 어려움
• 디지털 서명은 송신자를 인증하기 위해 비대칭 키를 사용함
• Alice는 개인 키를 사용하여 문서를 암호화함
• Bob은 Alice의 공개 키를 사용하여 문서를 복호화함
• 복호화가 가능하면 Alice가 문서를 보냈다는 것이 확실함
• 비대칭 키 암호화는 시간이 많이 걸림
• 따라서 디지털 서명은 메시지 자체가 아닌 메시지 다이제스트에 대해 주로 사용됨

메시지 부인 방지

• 송신자가 메시지를 보낸 것을 부인하지 못하도록 함
• 이를 위해 신뢰할 수 있는 제3자가 필요함
• Alice의 키로 서명된 메시지 사본이 신뢰할 수 있는 센터에 저장됨
• 나중에 신뢰할 수 있는 센터는 메시지를 자체 비밀 키로 서명하여 Bob에게 보내고, Bob은 이를 받음
• Alice가 메시지를 보냈다는 것을 부인하면 Bob은 신뢰할 수 있는 센터에 저장된 메시지와 비교할 수 있음