05. 정리 및 DES & AES

1. 대칭키 암호시스템 

대칭키는 송신자키와 수신자가 같은 키를 가지고 있고, 그 키를 통해 송신자가 평문을 암호화 해서 보면

수신자가 같은 키로 복호화

장점

1. 키 크기가 상대적으로 작음

2. 암호 알고리즘 내부 구조가 단순 : 시스템 개발환경에 용이,

    + 비대칭키에 비해 암/복호화 속도가 빠름

단점

1. 교환 당사자간에 동일한 키를 공유해야함 -> 키 관리의 어려움 (n 명 : n(n-1)/2 의 비밀키) 

   키 변경이 자주 있을경우 불편, 중재자가 필요함

종류

- DES, 3DES, blowfish, IDEA, RC4, RC5, RC6, AES, SEED, ARIA

B. 공개키 암호 시스템

- 비대칭키 암호 시스템

- 공개키를 통해 암호화, 비밀키(개인키)로 복호화

장점 

1. 대칭키 암호 시스템보다 더 좋은 확장 가능성 (왜?)

2. 인증과 부인방지 기능 제공

3. 범용적 사용 가능

단점 

1. 대칭키 시스템보다 더 큰 길이의 키 사용

2. 고도의 수학적 연산 

    -> 암호화 처리 시간 길고, 공개키 배포에 대한 신뢰성 문제 존재함 (PKI 와 같은 공개키 관리 구조가 필요함)

종류 

- RSA, Rabin, ECC, Schnorr, Diffie-Helman, EI Gamal, DSA, KCDSA, Knapsack

암호화에 적용되는 평문의 길이에 따라, 아래와 같이 나눔.

1. 스트림 암호 시스템

2. 블록 암호 시스템

스트림 암호 시스템 : 난수열을 생성하여 입력 평문 비트열을 한비트 또는 한문자(바이트) 단위로 xor 하여 암호화

블록 암호 시스템 : 입력 평문 비트열을 일정 크기의 블록으로 나누어 암호화

스트림 암호

- 한번에 한 바이트 or 한 비트씩 암호화 되는 형식, 초기값이 필요함

- 평문을 키 생성 알고리즘 비밀키로 xor 연산하여, 그 암호문을 기밀성과 무결성이 보장되는 채널을 통하여 받고

  비밀키로 복호화 한다.

- 암/복호화 과정에서 동일한 키 스트림

- 키 스트림은, 진 난수 스트림과 최대한 비슷해야 한다.

- 이동통신에서도 구현이 용이하여, 이동통신 등 무선 데이터 보호에 많이 사용됨.

1) 스트림 암호 특징 

- 원타임 패드를 실용적으로 구현할 목적으로 개발됨

- 다음에 출력 비트를 예측할 확률이 1/2 이어야 안전함. (왜?)

- 긴 주기와 선형 복잡도가 요구됨

- 블록 단위로 암호화 하는것에 비하여, 비트단위로 암호화하기때문에 더 빠르다.

- 주로 LFSR 을 이용하며, 블록암호의 CFB, OFB 모드와 같은 역할임

동기식 스트림 암호 

1. 동기식 스트림 암호에서 키 스트림은 평문 혹은 암호문 스트림과 독립적이다.

2. 키 스트림은 평문 혹은 암호문 비트와 키 비트 사이에 어떠한 관계도 없이 생성되고 사용된다.

2) 동기식 스트림 암호의 기술 

ㄱ. One time pad : 일회성 암호로 , 암호화를 수행할때마다 랜덤하게 선택된 키 스트림을 사용

ㄴ. FSR(feedback shift register)

     one-time pad의 절충안, sw,hw 구현 둘다 되지만, hw 구현이 더 용이함.

     귀환 shift register는 shift register 와 feedback 함수로 구성된다.

ㄷ. LFSR(Linear Feedback Shift Register) 

    많은 스트림암호가 LFSR 을 이용한다.

ㄹ. 비선형 귀환 시프트 레지스터 ( Non - Linear feedback shift register)

주로 LFSR 은 선형성 때문에 공격에 취약하다. 그러므로, NLFSR 을 이용하여, LFSR 보다 안전한 스트림 암호를 설계할수 있다.

비동기식 스트림 암호

1. 비동기식 스트림 암호에서, 키 스트림의 각 비트는 이전의 평문이나 암호문에 종속적으로 결정된다.

2. 블록 암호에서 다른 운영 모드를 생성하기 위해 사용되는 한가지 방법인

    CFB(cipher feedback mode) 는 실제로 스트림 암호를 생성한다.

강력한 스트림 암호의 특징

- 키스트림 값 내부에서 장기간 동안 반복되는 패턴이 없음

- 통계적으로 예측 가능하지 않은 키 스트림

- 키 스트림은 키와 선형적인 관계에 있지 않다 -> 키스트림값을 알아냈다는 것이 키 값을 안다는것을 의미하지는 않음.

DES( Data Encryption Standard)

(1) 개요

1) 역사

- 미국 국립 기술 표준원(NIST) 는 1973년 국가적으로 사용할 대칭키 암호시스템의 제안 요청서를 발표.

- 이에 따라 루시퍼 프로젝트의 수정판인 IBM의 제안이 DES 로 채택되었으며, DES 는 연방정보처리기준(FIPS) 의 draft 로 공표

- DES 는 가장 널리 사용되는 대칭키 블록 암호가 되었음. 후에 미국 국립기술표준원(nist) 는 훗날 사용할 목적으로 

   3중 DES을 권고하는 새로운표준(FIPS 46-3) 역시 발표

- 최신 블록 암호 표준인 AES 는 오랫동안 사용된 DES 를 대체하기 위하여 표준으로 채택된 알고리즘

2) 개관

- 평문의 길이 64bit

- key 56bit

- 이보다 긴 평문은, 64bit 블록으로 나눈다.

- DES 구조는 Feistel 네트워크의 변형된 형태

  라운드횟수 : 16

  56비트 원래 키로부터 16개의 서브키 생성, 그 서브키를 각 라운드에서 사용함.

- 복호화과정 = 암호화과정

(2) DES 구조

1) 암호화과정

- 두개의 전치(P-박스) 와 16개의 Feistel 라운드 함수로 구성

  여기서 사용된 두개의 P-박스중 하나는 초기 전치(initial permutation) , 다른 하나는 final permutation) 이라고 한다.

- 각 라운드는 라운드 키 생성기에 의해 암호키로부터 생성된 48bit 라운드 키를 사용한다.

2) 라운드 함수

DES 는 16번의 라운드 함수 를 사용한다.

DES 의 키는 7bit 마다 오류 검출을 위한 정보가 1비트씩 들어가므로 실질적으로는 56비트임

각 라운드에는 2개의 암호요소 혼합기(mixer) 와 교환기 (swpper) 가 있다. 

이런 요소들은 명백히 역연산이 가능

DES 함수 

DES 의 핵심은 DES 함수임. DES 함수란, 라운드 함수에 사용된 f(Ri-1, Ki) 를 가리킨다.

DES 함수는 32비트 출력값을 산출하기 위하여 가장 오른쪽의 32비트(Ri-1) 에 48비트 키를 적용한다.

1. 라운드 키와 xor 하기 위해, expansion 

2. 48비트로 확장된 이전라운드키의 오른쪽 평문 블록과 라운드키 xor

3. 2단계 결과값에서 6비트씩 가지고와 8개의 S-box에 가지고와서 4비트의 데이터만 추출하여 32비트로 만듦

4. 3단계의 결과값을 P-box 에 치환한 후 반환 

64bit block cipher algorithm 

key length : 64bit (56bit 비밀키, 8bit parity bit)

안정선은 주로 비선형함수로 구성된 8개의 S-box에 의존

16라운드의 페이스텔 구조임

복호화는 암호화의 역순

3) 암호화 알고리즘과 복호화 알고리즘 

(가)혼합기와 교환기를 사용하여, 16라운드 암호화 알고리즘과, 복호화 알고리즘을 만들수 있다.

암호화 알고리즘은, 암호화 가정에서 사용되고, 복호화 알고리즘은 복호화에서 사용된다.(당연한 말을 길게 써놨네;;)

여기서 중요한 점은, 라운드 키(K1 에서 K16) 이 역순으로 적용되어야 한다는 사실

암호화과정에서 1라운드는 K1 을 사용, 16라운드는 K16을 사용

복호화과정에서 1라운드는 K16, 16 라운드에서 K1 을 사용

(3) DES 분석

1) 설계 기준

(가) S-박스

- S-box 는 각 라운드에서부터 그 다음 라운드까지 혼돈을 만족하도록 설계되었다. = 비선형적으로 설계

* 혼돈 :  암호문과 키의 상관관계를 숨김

                                           평문의 작은 변화가, 암호문에 어떠한 변화를 일으킬지 예측할수 없는 성질. 비선형 함수

- S-box 는 비선형 함수이다.

- 입력값의 한 비트를 바꾼다면, 출력값에서는 두 비트 이상이 바뀐다.

(나) P-박스

- 32비트에서 32비트로 가는 하나의 단순 P-박스와 

   32비트에서 48비트로 가는 하나의 확장 P-박스가 있다. 

   이런 2개의 P-박스는 비트들을 동시에 확산(diffusion) 시킨다.

DES의 취약점

- 비평가들은 DES이 가장 큰 취약점 == 키의 크기 (56비트) 

   암호문이 주어졌을 경우, 키에 대한 전수조사를 위해 공격자는 2^56개의 키를 조사해야 한다.

(4) 다중 DES 

1) 3중 DES

(가)

  - 두 개의 키를 갖는 3중 DES 

  - 세 개의 키를 갖는 3중 DES

    * 3DES 는 hw 에서는 매우 효율적이지만, sw에서는 효율적이지 않다.

       3DES는 전자 여권에서 바이오 정보를 보호+ 금융분야에서 많이 사용됨

(나) 3중 DES 현황

- 3DES 는 현재도 은행 등에서 사용하고 있으나, 처리속도는 빠르지 않다.

   과거에 DES 로 암호화했던 자료의 호환성을 중시하는 경우를 제외하고는, 새로운 용도로 사용하는 경우는 드물다.

- 현재 우리나라에서는 3DES를 표준으로 정하여 사용하지않는다. 

   1999/9 정보통신단체표준(TTA) 에서 블록암호 SEED를 국가표준으로 정하였고, 

   학계, 연구소, 정부기관으로 구성된 학연관 공동으로 개발한 블록암호 ARIA는 2004년에 산업자원부의 인증을 획득하여 현재 사용하고 있다.

(다) 두 개의 키를 갖는 3중 DES

- 두 개의 키를 갖는 3중 DES 에서는 두개의 키 k1, k2 만을 사용

  첫번째와 세번째 단계에서 k1 , 두번째 단계에서 k2 

- 하나의 DES로 3중 DES를 만들기 위하여, 암호화 과정의 중간단계에서는 복호화 알고리즘을 사용하고, 복호화 과정에서는 DES의 암호화 알고리즘을 사용

https://m.blog.naver.com/PostView.nhn?blogId=asd7979&logNo=30181627741&proxyReferer=https%3A%2F%2Fwww.google.com%2F

(라) 세개의 키를 갖는 3중 DES

- 두개의 키를 갖는 3중 DES에 대한 기지 평문공격의 가능성 때문에, 어떤 응용프로그램은 세개의 키를 갖는 3중 DES 를 사용한다.

- 세개의 키를 갖는 3중 DES 는 PGP 와 같은 많은 응용프로그램에서 사용되고 있다.

3DES의 복호화는 암호화의 역이 된다.

(마) DES와의 호환성

- 트리플 DES에서 모든 키를 동일하게 하면, 3DES는 보통의 DES와 같아진다, 최초의 암호화->복호화로 인해 평문으로 돌아가기 때문

  과거에 DES로 암호화된 암호문은 3DES를 사용하여 복호화할 수 있다. 즉 3DES는 DES에 대한 상호 호환성을 갖고 있다.

구분	DES	Tripple DES	AES
평문 블록 크기	64	64	128
암호문 블록 크기	64	64	128
Key length	56	112 or 168	128, 192 or 256

AES (Advanced Encryption Standard)

(1) 개요 

1) 역사 

- 1997. nist 는 des 를 대체하기 위해 AES로 불리는 암호 알고리즘 공모

- 1차 심사에서 15개 응모작, 2차 심사에서 5개(MARS, RC6, Rijndael, Serpent, Twofish) 로 줄였다. 

   11월에 최종 선택안을 공표

- nist 에서 AES 알고리즘으로 선택한 것은, 레인달(Rindael) 

   레인달을 개발하고 제출한 두 연구자는 벨기에의 암호학자인 요안 대문과 빈슨트 레이믄

AES 의 응모조건

1. 알고리즘이 기밀이 아니어야 하고, 공개적으로 밝혀져야 함.

2. 키사이즈 : 128/192/256 비트중 선택가능

3. 국제적으로 자유로운 사용이 가능할 것 

4. triple des 보다 효율적이고 안전할것

2) 선정기준 (criteria)

- nist(미국 국립기술표준원) 에서 제시한 AES의 선정 기준은,

   1. 안정성 (security)

   2. 비용 (cost)

   3. 구현 효율성 (implementation)

    ->최종적으로 레인달이 세가지 조건에 가장 잘 부합하는것으로 결정됨

3) 라운드(Rounds)

- AES 는 128비트 평문을 128bit 암호문으로 출력하는 알고리즘

- AES 는 non-Feistel 알고리즘에 속한다. SPN 알고리즘

- 10, 12, 14 라운드를 사용

- 각 라운드에 대응하는 키 크기는 128, 192, 256 비트이다.

마스터 키 크기에 따라 AES의 세가지 버전이 존재하며, 

- AES-128

- AES-192

- AES-256 으로 불린다.

그러나, 어떤 경우라도, 키 확장 알고리즘으로부터 생성되는 

라운드 키 크기는  평문과 암호문 크기와 동일한 128 비트.   

(1) 한 블록 : 128 비트 
  (2) 128, 192, 256 비트의 비밀키 에 대해 라운드의 수는 각각 10, 12, 14 라운드가 실행
  (3) DES와 비교해보면, 먼저 키의 크기(56비트 -> 128/192/256비트)가 증가했다. 

      그리고 블록의 크기(64비트 -> 128비트)도 증가했다. 

      하지만 라운드 수(16라운드 -> 10/12/14라운드)는 감소했다. 

      즉, 한 라운드마다 절반씩 암호화되는 DES와는 다르다.

 2) 한 블록인 16 바이트(=128 비트)는 원소가 한 바이트 인 4x4 행렬로 변환됨
   - 이 행렬을 상태(state)라 부름

      (1byte, 1byte ,1byte ,1byte )

      (1byte, 1byte ,1byte ,1byte )

      (1byte, 1byte ,1byte ,1byte )

      (1byte, 1byte ,1byte ,1byte )  총 128bit

 3) 한 라운드는 네 가지 계층(Layer)으로 구성 
  (1) SubBytes
   - DES의 S-Box에 해당하며 한 바이트 단위로 치환 을 수행. 
   - 상태(state)의 한 바이트를 대응되는 S-Box의 한 바이트로 치환 한다. 이 계층은 혼돈의 원리를 구현한다. 
  (2) ShiftRows
   - 상태의 한 행안에서 바이트 단위로 자리바꿈이 수행  

      행 번호만큼 왼쪽으로 shift 수행(4bit), 가장 왼쪽에 있던 원래 아이는 가장 오른쪽으로 shift

  (3) MixColumns
   - 상태가 한 열안에서 혼합이 수행. ShiftRows와 함께 분산의 원리를 구현 

--> 다시 해볼것

  (4) AddRoundKey
   - 비밀키(128/192/256 비트)에서 생성된 128 비트의 라운드 키와 상태가 XOR됨

4) 암호화 마지막 라운드에서는 MixColumns()연산을 수행하지 않는다는 특징이 있다.

-> AES는 알려진 블록암호 알고리즘에 대한 모든 공격방법으로부터 안전하도록 설계되어있으며, hw,sw 구현시 속도나 코드 압축성 면에서

     효율적이므로, 스마트카드와 같은 응용에 적합하다는 장점

AES Encryption - Decryption

Encryption 시 S-box

	DES	AES
년도	1976	1999
block length	64bit	128bit
key length	56bit	128,192,256
encryption premitive	치환, 전치	치환, 시프트, 비트혼합
암호학적 premitive	혼돈, 확산	혼돈, 확산
설계	공개	공개
설계원칙	비공개	공개
선택과정	비밀	비밀,공모
출처	IBM, NSA	벨기에 암호학자

DES-AES 비교