3장

블록암호와 DES

스트림 암호
	한번에 1bit 혹은 1 byte 의 디지털 데이터 스트림을 암호화
	키 스트림은 평문 비트 스트림 만큼의 길이를 가진다 (ki == pi)

블록 암호
	평문 블록 전체를 가지고 같은 크기의 암호문 블록 생성
	64 or 128 bit
	n bit - n bit 블록 치환 (n = 4) 인경우
		4 비트 입력으로 16개 값중 하나 선택하고 내부 치환에 의해 16개 출력값 중 하나
	치환과 순열이 번갈아 가며 수행
		치환: plain text 의 각 원소 또는 원소 그룹을 다른 원소에 사상
		순열: plain text 의 순서는 순열의 순서대로 재배치
	Shannon
		"이상적인 암호는 암호문에 대한 모든 통계적 정보가 사용된 키와 독립적"
	확산 
		평문의 통계적 구조가 암호문에 광범위하게 분산
	혼돈
		암호문의 통계적 구조와 암호 키값 사이의 관계 복잡
		키를 이용한 암호문 생성 방법 복잡 -> 키 추론 어려움

Feistel 암호 구조의 동기
	블록 암호는 n bit 암호문 블록을 생성하기 위해 n bit 평문 블록을 이용하여 연산
	2^n 가지의 서로 다른 평문 블록 존재
	처리구조 
		길이 2w bit 인 평문 블록 (L0 , R0 )분할 처리
		K (Key) 로부터 유도된 n개의 키 사용
		n회의 동일한 반복 구조 실행
	하나의 반복구조
		오른쪽 반 R0에 반복함수 F 적용
			반복 서브키 k1 적용 ( K != Ki)
		왼쪽  반 L0와 XOR 연산 --> 치환
		좌우 양쪽 결과를 교환 --> 순열

왼쪽은 Encryption 오른쪽은 Decryption

Feistel 암호 설계의 고려사항
	빠른 소프트웨어 En / Decryption
		어플리케이션 또는 유틸리티 함수에 내재
		알고리즘의 실행 속도가 중요
	분석의 용이성
		암호해독의 취약성에 대한 알고리즘의 분석이 쉬움
		고도의 신뢰성과 보안 강도를 위한 개발 용이

Feistel 암호의 설계 특성
	블록 크기 (64 bit)
		블록이 크다면 보안 up, en / decryption 속도 저하
	키 크기 (128 bit)
		키가 크다면 보안 up, en / decryption 속도 저하
	반복 수
		다중 반복과정은 보안성 강화
		일반적으로 16회
	서브키 생성 알고리즘
		복잡 -> 강력
	반복함수
		복잡 -> 강력

DES: Data Encryption Standard
	특징
		64bit 블럭 암호 알고리즘
		56bit 키를 사용 (나머지 8 bit 은 parity check)
	기본 구조
		16 round
		치환 / 전치 의 혼합
		최근에는 3개의 키로 3번 반복하는 Triple-DES 사용

DES 의 반복과정

함수 F 의 설계
	8개의 S-box 로 구성
	각 S-box는 6bit 입력, 4bit 출력 생성

예를 들어 다음과 같은 S-box 가 있다고 가정

해당 s-box 에 011011 6 bit 을 입력하면
	0  1101  1 로 나뉘고 양 끝은 몇행인지, 중간은 무슨 열인지
		즉, 1행 13열 = 5 에 해당하는 비트를 2진수로 출력한다
		0101

DES 의 전체 동작 과정
	64 bit 평문이 첫 라운드를 거치기 전 initial permutation을 거친다
	initial permutation 을 거친 후 나온 64 bit 값은 각 L0 와 R0 로 32 bit 씩 
	R0에 해당하는 32 bit 는 확장 후 함수 F에 들어간다
		함수 F의 입력은 48 , 출력은 32
	생성된 32 bit 을  R1에 보내준다
	이 과정을 16 라운드까지 반복
	마지막 라운드에 L 과 R 이 반대로 들어간다
	이후 initial permutation의 역에 들어가 64bit 암호문을 얻는다
F 함수:
	각 라운드마다 오른쪽의 32 bit 가 expansion을 거쳐 48 bit가 된다
	이렇게 얻은 48 bit와 키 스케줄을 거친 48bit 가 XOR을 거치고 F 함수로 들어간다
	XOR로 얻은 48 bit 는 8부분으로 나뉘어 각각 6bit 씩 S-Box에 들어간다
	S-Box에 들어갔다 나온 값들은 4bit 로 나오게 되고 결국 모두 합치면 32 bit
	이 32 bit은 permutation을 거쳐 F 함수 결과인 32 비트를 도출

DES 쇄도효과
	평문이나 키의 작은 변화 --> 암호문의 여러 비트가 변한다
DES 강점
	56 비트 키 사용
	usec당 하나의 암호를 수행하는 장치 1백만개로 구성된 병렬기계 구성 
	평균 탐색시간 10시간으로 축소
	수년간 S box 의 수많은 정규성과 예측 못한 동작이 발견
		but 치명적 약점 x
	Timing 공격
		암호문을 복호화 하는데 걸리는 시간을 관측하여 키 또는 평문의 정보를 획득
		아직까지 성공 사례 x

암호 해독
	차분 암호 해독
		2^55 미만의 복잡도로 DES 를 해독
		2^47의 선택 평문을 가지고 DES 해독
	선형 암호 해독
		2^47 가지 평문으로 해독 가능
		DES 공격으로서의 선형 암호 해독은 가능성 x

DES 설계 기준
	S-box
		출력 비트와 입력 비트가 유사해서는 안된다
		S-box의 각 행은 16개의 출력 비트 조합을 모두 포함
		S-box의 두 입력중 한 비트가 다르면 출력은 최소 2 bit 이 달라야함
		S-box 의 두 입력 중 첫번째 두 비트가 다르고 마지막 두 비트가 같으면 출력은 달라야함
		입력들 사이에 0 이 아닌 6bit 차이를 나타내는 입력은 32쌍중 8쌍은 같은 출력

	순열 P 설계 기준
		i 번째 반복에서 각 S 로부터 4개의 출력 비트가 분산되어 2bit 는 (i+1) 번째
		반복의 중간비트에 영향을 미치고 다른 2비트는 양끝 비트에 영향
		각 S 출력 4비트는 다음 반복에서 6개의 다른 S에 영향을 준다
		두개의 S j,k 에서 j = k 에대해 Sj 의 한 출력 비트는 Sk의 중간비트에 영향 x

	F 함수 설계
		치환 결과를 복구하기 난해해야 함
		엄격한 쇄도 기준
			모든 i 와 j에 대해 어떤 입력 비트 i 가 바뀌면 S 의 출력비트 j는 1/2확률로
			바뀌어야함
			라운드의 수가 많으면 F함수가 약하더라도 암호 해독은 어려움
			Brute Force 탐색 공격 이상의 노력이 요구되도록 라운드 수 선정