Download presentation
Presentation is loading. Please wait.
Published byHartanti Wibowo Modified 5년 전
1
2009년 3월 30일 (5주차) 유 승 석(aviteria@gmail.com)
상용 관용 암호 방식 2009년 3월 30일 (5주차) 유 승
2
수업 내용 DES DES의 규칙성 DES의 안전성 문제 SEED AES 운용 모드 Questions & Answers
3
DES
4
DES 개요 DEA(Data Encryption Algorithm) 대칭키 암호 시스템, 암호화/복호화 키가 동일
IBM의 홀스트 파이스텔에 의해 개발됨, 루시퍼(1975, IBM) 알고리즘의 변형 ATM(Auto Teller Machines), POS(Point of Sale) 단말장치의 PIN 암호화 및 데이터 내용 변조 방지를 위해 사용됨 PIN : Personal Identification Number
5
DES (Data Encryption Standard)
1차 1973년 NBS(현 NIST의 전신) 공개 모집 NBS(National Bureau of Standards, 미국규격표준국) 2차 1974년 NBS 공개 모집 IBM Tuchman, Meyer 응모 1977년 미연방 표준 암호 알고리즘으로 선정(FIPS PUB 46) 참고사이트 NIST :
6
DES (계속) 공모 조건 높은 안전성 알고리즘 간단 안전성이 키에만 의존 응용이 다양 제작자 및 사용자 이용 가능
전자장치 간단 제작자의 알고리즘 타당성 검토 협력 수출 가능
7
DES의 특징 64비트 블록 단위로 암호화 56비트 키(Active Key) + 8비트 패리티체크(Parity Check) 비트 56 비트가 암호화 및 복호화에 사용된다. 16라운드의 치환(P-Box)과 대치(S-Box)를 사용 정보이론의 아버지 클로드 샤논이 제안했던 기술을 구현한 것 참고사이트
8
DES 암호화 진행 과정 Overview 1. 평문을 입력 64비트 2. 초기전치(재배열) 3. 좌우 분리 32비트씩
3. 좌우 분리 32비트씩 4. Feistel 연산 5. 원래의 키로부터 만들어 낸 키 6. 초기전치의 역전치(거꾸로) 7. 암호문 비트
9
DES 암호화 진행 과정 Overview
10
DES 암호화 과정 Overview - 초기전치 IP (initial permutation)
1) 평문을 64비트씩 자른다. 64비트 자른 평문을 이라고 하자. 평문 M은 초기치환 IP를 거쳐 으로 바뀐다. IP는 1번 자리에 58번째 비트를 놓고, 2번 자리에 50번째 비트를 놓고, 3번 자리에 42번째 비트를 놓는 방식으로 비트열의 자리를 바꾼다. IP 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
11
DES 암호화 과정 Overview - 16라운드의 함수계산(치환)
2) IP(M)은 좌우 각각 32비트씩 와 로 나누어 1라운드 암호화 과정에 들어간다. 와 를 가지고 다음 단계의 , 을 만든다. 이다. 3) 2라운드의 왼쪽 32비트 은 오른쪽 32비트 를 그대로 쓴다. 2라운드의 오른쪽 32비트 은 를 연산틀에 넣어서 처리한 다음 그 값과 을 XOR연산한다. 한 라운드를 넘기는 과정마다 암호키 열 이 차례대로 작용한다.
12
DES 암호화 과정 Overview -역전치IP–1(inverse of initial permutation)
역치환 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
13
DES의 f 함수 E : Expansion(확대전치E) XOR 연산 P-box(평형전치P) S-box
비트 확장표를 이용하여 32 비트를 48 비트로 확장 XOR 연산 키 스케줄러에서 생성된 라운드 별 Subkey와 XOR 연산 P-box(평형전치P) 선형전치표 S-box DES의 안전성에 중요한 역할 8 개의 비선형 함수로 구성됨 48 비트를 다시 32 비트로 변환
14
DES의 f 함수 확대전치 E
15
DES의 f 함수 평형전치 P
16
DES의 f 함수 S-Box
17
DES의 f 함수 S-Box 예
18
The Key-schedule of DES
키계열 생성 알고리즘 키 스케줄러라 불리움 Subkey 16 개 생성 K1, K2, K3, …, K16 과정 64비트 키 데이터 입력 선택치환 PC1 : Permuted Choice1 8bit 패리티 체크 비트 제거 56 bit 생성 28비트 씩 양분 라운드 별 지정된 수 만큼 좌측 시프트 PC2 : Permuted Choice2 48 비트의 라운드 키 생성됨 16라운드(회) 반복
19
The Key-schedule of DES
키 스케줄러에서 Subkey 16 개 생성( K1, K2, K3, …, K16 ) 64비트 키 데이터 입력 키전치 PC-1 Permuted Choice1 8bit 패리티 체크 비트 제거 56 bit 생성 28비트 씩 양분( C0, D0, … ) 라운드 별 지정된 수 만큼 좌측 시프트(LS1, LS2, …), 표4-8 축약전치 PC-2 PC2 : Permuted Choice2 48 비트의 라운드 키 생성됨 위의 과정들을 16라운드(회) 반복
20
The Key-schedule of DES
키전치 PC-1 제거
21
The Key-schedule of DES
축약전치 PC-2 제거
22
The Key-schedule of DES
키 스케쥴러 LS
23
DES 복호화 과정 암호문CIP역라운드IP–1평문M
24
DES 암호의 규칙성 보수 특성
25
취약 키 취약키로 평문을 암호화하고 다시 한 번 암호화하면 평문이 나타남
F E F E F E F E F E F E F E F E 1 F 1 F 1 F 1 F 0 E 0 E 0 E 0 E E 0 E 0 E 0 E 0 F 1 F 1 F 1 F 1
26
유사 취약 키 취약키와 상당히 비슷한 특성을 갖는 키 조합 0 1 F E 0 1 F E 0 1 F E 0 1 F E
1 F E 0 1 F E 0 0 E F 1 0 E F 1 E 0 1 F E 0 1 F F 1 0 E F 1 0 E 0 1 E E F F 1 E E F F 1 0 1 1 F F E 1 F F E 0 E F E 0 E F E F E 1 F F E 1 F F E 0 E F E 0 E 0 1 1 F F E E 1 F F E E 0 1 E 0 F E E 0 F E F 1 F E F 1 F E F E E 0 F E E 0 F E F 1 F E F 1 취약키와 상당히 비슷한 특성을 갖는 키 조합
27
DES의 안전성 문제 1975년 DES 알고리즘 발표 뒤 두가지 문제점이 제기됨 DES의 소모적 공격 키의 길이가 짧다
S-Box의 트랩도어나 의도적인 약점이 포함되어 있을 수 있다. DES의 소모적 공격 암호기에 평문을 입력시켜 모든 키를 차례로 사용하면서 원하는 암호문이 출력될 때 까지 반복 여러 개를 만들어 동시에 공격하면 시간 단축
28
DES의 안전성 문제 1998년 미국 RSA사에서 DES 해독
1997년 3-DES(Triple DES, 트리플 DES) 로 보완 DES를 사용하는 세 번의 암호화 2002년 AES(Advanced Encryption Standard)로 데체됨
29
DES (계속) 2중 DES 1비트 증가 효과
30
DES (계속) 3중 DES 강한 암호 가능 키의 길이가 2배 확대된 효과
31
참고자료 DES supplementary material
details the various tables referenced in the Data Encryption Standard (DES) block cipher.
32
SEED
33
SEED 개요 전자상거래, 금융, 무선통신 등에서 전송되는 개인정보와 같은 중요한 정보를 보호하기 위해 1999년 2월 한국정보보호진흥원과 국내 암호전문가들이 순수 국내기술로 개발 128비트 블록암호알고리즘 128비트 key 사용 1999년 9월 정보통신단체표준(TTA)으로 제정 2005년에는 국제 표준화 기구인 ISO/IEC 국제 블록암호알고리즘 표준으로 제정됨 참고사이트
34
SEED 암호화 과정
35
SEED의 f 함수 f 함수의 입력 값 64비트 REi 32비트 X, Y 로 분리
64비트 암호화 보조키 Ki+1 32비트 KK0, KK1 으로 분리
36
SEED의 G 함수 S-Box 치환 Bit-wise 연산 G함수의 입력 32비트를
4개의 8비트 블록 X3X2X1X0 으로 분할한 후 S-Box S2S1S2S1 에 입력 S2(X3), S1(X2), S2(X1), S1(X0) 를 출력함 Bit-wise 연산
37
SEED의 G 함수 & : bit-wise AND
38
SEED의 S–Box SEED의 안전성을 결정하는 중요한 요소 8비트가 입력, 8비트가 출력되는 치환과정
미분해독기법(differential cryptanalysis)및 선형해독기법(linear cryptanalysis) 특성이 가장 우수한 n=247, 251을 선택하여 전단사 함수 Xn 을 적용함 GF(28)을 이용 Z256 = { 0, 1, 2, … , 255 }
39
SEED의 S–Box
40
SEED의 S–Box S-Box
41
SEED – S1 Box 변환표
42
SEED – S2 Box 변환표
43
SEED – 보조키 생성 알고리즘 128비트의 키는 네 개의 32비트 블록으로 나누어져 키 생성 알고리즘에 입력됨(A,B,C,D)
44
SEED – 보조키 생성 알고리즘
45
SEED – 보조키 생성 알고리즘 키 생성 상수
46
SEED 참고자료 KISA SEED/ARIA 블록암호알고리즘 SEED 알고리즘 상세 명세서 SEED 개발 및 분석 보고서
SEED 알고리즘 상세 명세서 SEED 개발 및 분석 보고서
47
[참고] ARIA 블록암호알고리즘 ARIA는 경량 환경 및 하드웨어에서의 효율성 향상을 위해 개발된 블록 암호 알고리즘
블록 크기 : 128비트 키 크기 : 128/192/256비트 (AES와 동일 규격) 라운드 수 : 12/14/16 (키 크기에 따라 결정됨) ARIA가 사용하는 대부분의 연산은 XOR과 같은 단순한 바이트 단위 연산으로 구성됨 2004년에 국가표준기본법에 의거, 지식경제부에 의하여 국가표준(KS)으로 지정
48
[참고] ARIA 블록암호알고리즘 안정성과 효율성 ARIA 소스코드
국가정보원에서는 C와 JAVA로 작성된 ARIA 소스코드를 제공하고 있음
49
[참고] ARIA 블록암호알고리즘 참고사이트
KISA : IT보안인증사무국
50
Advanced Encryption Standard
AES Advanced Encryption Standard
51
AES의 공모 DES에 대한 여러 공격 방법들의 발표로 인해 새로운 표준암호 알고리즘의 필요성 대두
56-bit DES key : exhaustive key search feasible 64-bit DES block (and Triple DES) : MAC(Message Authentication Code) weakness 미국의 NIST는 1998년 AES 알고리즘을 공모 Round 1( – ) : CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish Round 2( – ): MARS, RC6, Rijndael, Serpent, Twofish 2000년 10월 2일 AES 알고리즘 선정 발표 Rijndael (Submitted by Joan Daeman and Vincent Rijman) 2001년 11월 FIPS-197로 등록
52
AES의 특징 입력 평문의 길이는 128비트로 고정 사용하는 암호화 키의 길이는 128, 192, 256비트 중 하나를 선택할 수 있음 참고) Rijndel 알고리즘은 키의 길이와 입력 평문의 길이를 128, 192, 256 비트 중 선택 가능 지금까지 알려진 모든 공격법에 대해 안전하도록 설계됨 모든 플랫폼에서 속도와 code compactness 면에서 효율적 Design simplicity Suited for Smart cards
53
AES의 개요 평문을 128비트 단위로 나누어 암호화, 복호화를 수행 각각의 128비트를 4x4 행렬로 표현하여 연산을 수행함
Input / output : sequence of 128 bits(block) 각각의 128비트를 4x4 행렬로 표현하여 연산을 수행함 암호화 키 Cipher key : sequence of 128, 192, 256 bits
54
AES의 개요 State 4x4행렬로 표현 암호화, 복호화 과정의 중간 단계 결과물 (4, Nb)의 이차원 행렬로 표현
55
AES의 개요 AES의 기본 연산은 Byte 단위로 수행
각 바이트를 유한체 GF(28)위의 다항식으로 표현하여 연산을 수행한다.
56
AES의 덧셈(Addition) GF(28)에서의 두 원소의 덧셈은 각 계수를 (mod 2)상에서 더한 결과
57
AES의 곱셈(Multiplication)
GF(28)에서의 곱셈은 mod 8차 기약다항식 상에서의 곱셈 기약 다항식(irreducible polynomial) : 1과 자기 자신만을 인수로 갖는 다항식 AES에서 사용하는 기약 다항식
58
[참고] 다항식의 연산 방법
59
AES 암호화 과정
60
AES 암호화 과정 KeyExpansion using Rijndael's key schedule Initial Round
AddRoundKey Rounds SubBytes : a non-linear substitution step where each byte is replaced with another according to a lookup table. ShiftRows : a transposition step where each row of the state is shifted cyclically a certain number of steps. MixColumns : a mixing operation which operates on the columns of the state, combining the four bytes in each column AddRoundKey : each byte of the state is combined with the round key; each round key is derived from the cipher key using a key schedule. Final Round (no MixColumns) SubBytes ShiftRows
61
The number of Rounds (Nr)
사용하는 암호화 키(Nk)의 길이에 따라 암호 및 복호화 과정에 필요한 라운드 수는 다르다.
62
AES의 암호화 과정
63
Round Transformation 4개의 다른 transformation으로 구성
※ 마지막 라운드에는 MixColumn 단계가 없음
64
Pseudo Code for the AES cipher
65
SubBytes step ShiftRows step MixColumns step AddRoundKey step
66
SubByte( ) Transformation
Non-linear byte substitution 바이트 단위로 invertible한 S-box에 적용 S-Box는 두 가지 변환으로 구성
67
SubByte( ) Transformation
S[02], 02 = x
68
SubByte( ) Transformation
69
SubByte( ) Transformation
70
SubByte( ) Transformation Example
71
SubBytes step ShiftRows step MixColumns step AddRoundKey step
72
ShiftRow( ) Transformation(1/2)
State의 각 행을 왼쪽으로 cyclic shift 0 행 : - 1 행 : 1 byte 2 행 : 2 byte 3 행 : 3 byte
73
ShiftRow() Transformation(2/2)
74
ShiftRow() Transformation Example
75
SubBytes step ShiftRows step MixColumns step AddRoundKey step
76
MixColumn() Transformation(1/2)
77
MixColumn() transformation(2/2)
78
MixColumn() transformation Example
79
SubBytes step ShiftRows step MixColumns step AddRoundKey step
80
AddRoundKey() Transformation
라운드 키는 각 state에 bitwise XOR로 적용 Cipher key로부터 키 스케줄러를 이용하여 라운드 키 생성 라운드 키의 길이 = 블록 길이 Nb
81
AddRoundKey() Transformation - Example
82
AES 복호화 과정
83
AES의 복호화 과정
84
Inverse Cipher
85
InvSubByte() Transformation(1/2)
86
InvSubByte() Transformation(2/2)
87
InvShiftRow() Transformation
88
InvMixColumn() Transformation
MixColumn에서 사용한 a(x)의 inverse를 곱한다.
89
KeyExpansion using Rijndael's key schedule
90
Key Expansion
91
Psedo code for Key Expansion
92
Key Expansion
93
Key Expansion – Example(1/4)
94
Key Expansion – Example(2/4)
95
Key Expansion – Example(3/4)
96
Key Expansion – Example(4/4)
97
Cipher – Example(1/4)
98
Cipher – Example(2/4)
99
Cipher – Example(3/4)
100
Cipher – Example(4/4)
101
참고 Advanced Encryption Standard Rijndael S-box Rijndael key schedule
Rijndael S-box Rijndael key schedule
102
운용 모드
103
블록 암호 방식의 운용 모드 ECB (Electronic Codebook Mode)
CBC (Cipher Block Chaining Mode) CFB (Cipher Feed Back Mode) OFB (Output Feed Back Mode)
104
ECB(Electronic Codebook) 모드
동일한 평문에 대해 동일한 암호문 출력 짧은 길이의 평문 암호화에 사용
105
CBC(Cipher Block Chaining) 모드
106
CBC(Cipher Block Chaining) 모드
107
CBC(Cipher Block Chaining) 모드
108
CFB(Cipher Feed Back) 모드
109
CFB(Cipher Feed Back) 모드
110
CFB(Cipher Feed Back) 모드
특징 동일한 평문 블록에 대해 동일한 암호문이 나 타나지 않도록 함 평문 블럭내에 한 비트 오류가 발생하면 모든 암호문에 영향을 미침 암호문 블럭내에 한 비트 오류가 발생하면 복 호화된 모든 평문에 영향을 미침
111
OFB(Output Feed Back) 모드
112
OFB(Output Feed Back) 모드
113
OFB(Output Feed Back) 모드
ECB 모드의 단점을 개선하고 CBC/CFB 모드의 오류 전파 특성을 제거한 방식 전송 중에 비트 손실이나 삽입에 유의해야 함
114
Questions & Answers
Similar presentations