정보보호 개론 Chapter 04 암호화 기술

암호의 개요 암호의 필요성 암호 방식의 이용 암호를 사용함으로 막을 수 있는 효과 정보 시스템이 요구하는 정보의 보안 수준에 따라 효율적이고, 계층적인 보안 대책을 제공 암호를 사용함으로 막을 수 있는 효과 외부 침입자(Other intruder)에 의해 당할 수 있는 보안위협으로는 메시지가 수신자에게 전달되는 것을 막는 행위(blocking) 메시지를 중간에 가로채서(intercept) 내용을 읽는 행위 메시지의 내용을 수정 및 첨가 하는 변조(modify)하는 행위 외부 침입자가 보내는 메시지를 마치 송신자가 보내는 것처럼 위장(fabricate) 하는 행위 정보보호 개론

암호의 개요 암호의 필요성 암호 기술 암호화 기술 암호 프로토콜 기술 암호화 키와 복호화 키가 같은지 여부에 따라 대칭키 암호 알고리즘과 공개키 알고리즘으로 분류 대칭키 암호의 변환하는 방법에 따라 블록암호 알고리즘, 스트림 암호 알고리즘으로 분류 공개키 암호 알고리즘의 수학적 개념 기반에 따라 인수분해, 인산대수, 타원곡선 문제 등 암호 프로토콜 기술 기본 암호 프로토콜과 보다 발전된 암호 프로토콜로써 전자상거래 암호 프로토콜로 분류 정보보호 개론

암호의 개요 암호의 역사 암호학 비밀 통신 가장 오래된 학문 중 하나 수학의 한 부분 암호 방식은 인류 역사가 시작되기 전부터 사용 비밀 통신 암호문(cipher text)이 아닌 보통 문장의 평문(plain text)인 통신문 내용을 알아보지 못하도록 숨겨서 통신하는 방법도 포함 예) 고대 그리스에서의 통신 방법 나뭇가지에 열매가 달린 유무에 따라 통신문을 표현 스테가노그래피(steganography) 암호라고 하기보다는 다른 사람이 인식하지 못하도록 통신문을 감춘다는 뜻 정보보호 개론

암호의 개요 암호의 역사 고대 봉건 사회의 암호 산업 사회의 발전과 전기 통신의 발달 20세기 황제나 왕, 군주 등이 지방 관리에게 보내는 문서나 비밀 정책의 통보, 국가 기밀문서 등에 이용 전쟁 중 작전지시나 군사 훈련 중 지휘관의 명령이나 보고 사항 등을 적으로부터 비밀을 유지하기 위해 주로 사용 산업 사회의 발전과 전기 통신의 발달 유통되는 정보의 양이 급증하면서 정보 보호를 위한 암호 사용이 급증 20세기 무선 통신의 개발로 암호 사용이 더욱 가속화 정보보호 개론

암호의 개요 암호의 역사 고대 암호 가장 오래된 암호 방식 고대 암호와 근대 암호 기원전 400년경 고대 희랍인들이 사용한 scytale(스키테일) 암호라고 불리는 전치 암호 전달하려는 평문을 재배열하는 방식 곤봉에 종이(papyrus)를 감아 평문을 횡으로 쓴 다음 종이를 풀면 평문의 각 문자는 재배치되어 평문의 내용을 인식할 수 없게 됨 암호문 수신자는 송신자가 사용한 곤봉과 직경이 같은 곤봉에 암호문이 적혀있는 종이를 감고 횡으로 읽으면 평문을 얻을 수 있음 고대 암호와 근대 암호 문자의 전이와 치환을 이용한 암호 방식을 사용 정보보호 개론

암호의 개요 암호의 역사 고대 암호 전이암호(Transposition cipher) 메시지의 내용변경 없이 배열의 위치만을 바꾸는 것 KEY를 이용하여 재배열 하는 방법 예 평문은 “TRANSPOSITION CIPHER” 키값은 “CANDY” 키의 ASKII 순서는 2열, 1열, 4열, 3열, 5열의 순서로 재배열 평문을 키값 “CANDY”의 5개 문자에 맞추어 TRANS, POSIT, IONCI, PHER로 나눈 다음 배열 정보보호 개론

암호의 개요 암호의 역사 고대 암호 전이(치)암호(Transposition cipher) 예 키의 ASCII의 순서에 따라 암호문이 완성 암호문은 “ROOH TPIP NICR ASNE STI” 치환암호(Substitution cipher) 메시지의 각 문자의 위치 변화 없이 문자자체를 다른 형태의 요소로 대치시켜 암호화 하고 역 처리 시켜 이를 복원하는 방법 각 문자가 좌측으로 3자씩 이동시켜 사용한 줄리어스 시저(Julius Caesar) 암호가 대표적인 경우 예1) 원문과 암호문의 구성요소를 1:1로 대응시켜 좌우로 일정위치(n position)를 이동 원문과 암호문의 구성요소를 1:1로 대응시켜 key를 이용해 재배열하여 순서를 혼란 시킴 ② ① ④ ③ ⑤ 정보보호 개론

암호의 개요 암호의 역사 고대 암호 치환암호(Substitution cipher) 예 ) 예 ) 단순 대치암호를 보완하기 위하여 평문의 각 문자에 여러 개의 서로 다른 문자가 대응되는 암호방법 0부터 99까지의 2자리 숫자를 A-Z까지의 영문자에 배치한 후 평문의 각 문자를 각 문자에 해당수치로 순환하여 배치하는 방법 정보보호 개론

암호의 개요 암호의 역사 고대 암호 합성암호(Product cipher) 전이암호와 치환암호를 적당히 조합 시킨 것 1914년 제1차 세계대전 중 독일 육군에서 상용된 ADFGVX 암호 ADFGVX 암호 행렬이 각각 ADFGVX라는 행렬요소를 가진 6*6의 메트릭스에 영문자 26자 및 숫자 10자를 배열 평문의 각 문자를 좌표로 치환 시켜 1차 암호화 별도의 키를 이용하여 전이 시키므로 최종의 암호문 생성 정보보호 개론

암호의 개요 암호의 역사 근대 암호 17세기 20세기 두 차례의 세계대전을 거치며 근대 수학의 발전과 더불어 고급 암호가 발전하기 시작 20세기 본격적인 근대 수학을 도입한 과학적인 근대 암호가 발전하기 시작 불란서 외교관 Vigenere(비제네르)가 고안한 암호 방식 Playfair(플레이페어)가 만든 2문자 조합 암호 오스트리아 육군 대령 Fleissner의 grille(그릴) 암호 두 차례의 세계대전을 거치며 암호 방식 설계 및 해독에 관한 연구가 활발히 추진 정보보호 개론

암호의 개요 암호의 역사 근대 암호 근대 암호의 기초가 된 논문 근대 암호학의 연구를 촉진시킨 것 1920년 Freidman(프레드만)이 발표한 “일치 반복 률과 암호 응용” 제 2차 세계대전 중 독일군이 사용하던 에니그마(ENIGMA) 암호와 일본군이 사용하던 무라사끼 암호를 해독한 사람 유전자 구조 해석의 길을 개척한 선각자 C. E. Shannon이 발표한 “비밀 시스템의 통신이론” 확률론을 기초로 한 정보이론을 창시한 사람 원리적으로 해독 불가능한 암호 방식을 제안 안전성을 평균 정보량을 이용하여 수리적으로 증명 근대 암호학의 연구를 촉진시킨 것 두 차례의 세계 대전이 계기 기술적으로는 전신 기술의 발달과 세계대전 후의 전자계산기의 출현으로 암호화, 복호화 및 암호 해독의 속도가 향상됨으로써, 암호 실용화 연구가 활발해짐 정보보호 개론

암호의 개요 암호의 역사 현대 암호 1970년대 후반 스탠포드 대학과 MIT대학에서 시작 1976년 종래의 관용 암호 방식 스탠포드 대학의 디페(Diffie)와 헬만(Hellman)이 자신의 논문 “New Direction in Cryptography;암호화의 새로운 방향)”에서 처음 공개키 암호 방식의 개념을 발표 종래의 관용 암호 방식 암호화를 하기 위한 키와 복호화를 하기 위한 키를 동일한 키로 사용 Diffie와 Hellman이 제안한 공개키 암호 방식 암호화를 하기 위한 키와 복호화를 하기 위한 키를 분리 암호화 키는 공개하고 복호화 키는 비밀리에 보관 암호화 키를 사전에 전송할 필요가 없어 불특정 다수 비밀 통신 가입자 사이에 암호 통신망 구축이 쉬움 RSA MIT의 리베스트(Rivest), 샤미르(Shamir), 아델만(Adleman)에 의해 처음 실현 MH공개키 암호 방식 마클(Merkle), 헬만(Helman)의 의해 실현 라빈(Rabin)의 공개키 암호 방식 정보보호 개론

암호의 개요 암호의 역사 현대 암호 1977년 DES (Data Encryption Standard) 의 출현 미국 상무성 표준국 (NBS 현 NIST)은 전자계산기 데이터 보호를 위한 암호 알고리즘을 공개 모집, IBM사가 제안한 관용 암호 방식을 데이터 암호 규격(DES)으로 채택하여 상업용으로 사용 DES (Data Encryption Standard) 의 출현 상업용 암호 방식의 이용이 급격하게 증가 전자우편, 전자 문서 교환, 전자 현금 등을 실현하기 위한 암호 알고리즘, 디지털 서명 알고리즘 등 발표 이전의 암호 방식 키 뿐만 아니라 암호 알고리즘 역시 비밀로 함 현대 암호 방식 암호 알고리즘을 공개 공개적으로 암호 방식의 안전성을 검토하게 하여 그 안전성을 확인하도록 함 정보보호 개론

암호화 암호화의 개념 암호화(encryption)란 복호화(decryption)란 암호 해독 연구자들의 활동 암호 알고리즘 메시지의 내용을 확인하기 어렵도록 다른 형태로 바꾸는 것 복호화(decryption)란 암호화된 내용을 원래 내용으로 복원하는 것 암호 해독 연구자들의 활동 암호화된 메시지를 해독 암호화된 메시지에서 어떤 패턴을 찾아냄 복호화 알고리즘을 유추 암호화 알고리즘의 취약점을 연구 암호 알고리즘 해독 알고리즘을 찾는데 얼마의 시간이 필요한가의 문제를 갖고 있음 현재는 안전하다고 평가되는 암호 알고리즘이라도 컴퓨터의 처리 속도가 계속 향상되고, 병렬처리 및 분산처리 등의 기술적 발전으로 미래에는 안전하지 않을 수 있음 시간적 비용을 요구 안전한 알고리즘일수록 암호화, 복호화 시간이 길어지는 경향 정보보호 개론

암호화 암호화 방식 암호알고리즘 C = E (K, P) C : 암호문(Cipher) E : 암호화 K : 키 값(Key) P : 평문(Plane Text) 암호화와 복호화를 위해 서로 다른 키를 이용, C=E( KE,P ), P=D( KD, C ) KE는 암호화(Encryption)를 위한 키 KD는 복호화(Decryption)를 위한 키 정보보호 개론

암호화 암호화 방식       평문(plaintext) P 송신자가 수신자에게 전달하려는 정보 내용 누구나 그 의미를 알 수 있는 정보 송신자는 평문P를 암호화키 KE 와 암호(encryption) 알고리즘을 적용시켜 암호문(ciphertext) C를 생성하여 수신자에게 전달 암호문 C는 전송 상태에서 그 내용을 알 수 없는 데이터 수신자는 송신자가 전송한 암호문 C를 수신하여 복호화키 KD 와 복호화(decryption) 알고리즘을 적용시켜 송신자가 전송하려는 평문 P를 복원 가능       정보보호 개론

암호 알고리즘 간단한 치환 암호 알고리즘 시이저(Julius Caesar) 암호 평문의 각 문자를 우측으로 3문자씩 이동 그 위치에 대응하는 다른 문자를 치환함 예) TREATY IMPOSSIBLE(불가능한 협정) 는 WUHDWB LPSRVVLEOH 장점 단순 외우기 쉬운 규칙 암호화, 복호화를 쉽게 할 수 있음 단점 암호문을 복호화 하는 유추과정이 쉬움 정보보호 개론

암호 알고리즘 간단한 치환 암호 알고리즘 순열(permutation)을 이용한 암호화(전치암호) 키(key)를 이용한 암호화 예 π = 1, 3, 5, 7, 9, 10, 8, 6, 4, 2일 때, π(3) = 5 알파벳에 0부터 25의 숫자를 부여하고 정해진 순열을 이용 알파벳을 치환 π(λ) = 25 -λ를 적용, a → z, b → y, c → x … 키(key)를 이용한 암호화 송신자와 수신자만 아는 키를 설정 알파벳 치환의 첫 부분에 키 값을 배치하고 나머지 부분을 키 값이 아닌 알파벳으로 채움 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘의 개요 암호 이전 키 교환 비밀키 암호방식 메시지의 크기에 따라 안전한 채널(Secure Channel)을 이용하여 송신자와 수신자 간의 비밀키 교류 송신자는 비밀 키를 이용하여 평문을 암호 알고리즘에 따라 암호화 비밀키 암호방식 키 값은 송신자와 수신자가 비밀로 보관 메시지의 크기에 따라 블록암호 알고리즘과 스트림 암호 알고리즘으로 분류 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘의 개요 블록 암호 알고리즘 평문을 N 비트씩 나눈 블록 단위로 암호화를 수행 알고리즘의 구조에 따라 Feistel(파이스텔) 구조, SPN (Substitution Permutation Network) 구조 등으로 분류 대표적인 예 미국의 DES(Data Encryption Standard), Triple-DES 유럽의 IDEA(International Data Encryption Algorithm) 일본의 FEAL(Fast Data Encryption Algorithm) 한국의 SEED 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘의 개요 블록 암호 알고리즘 Feistel 구조 암호화 과정과 복호화 과정이 동일한 방식 복호화를 위해 암호화의 역 과정을 고려할 필요가 없음 구현이 비교적 쉬움 평문 전체를 블록 단위로 배열하고 블록을 동일한 크기로 분할 0번째 L0와 우측 0번째 R0는 n 라운드마다 위치를 교환하면서 함수 F와 XOR(exclusive OR) 연산을 통해 암호화 과정을 실행 Feistel 구조를 따르는 알고리즘 : DES, SEED 등 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘의 개요 블록 암호 알고리즘 SPN (Substitution Permutation Network) 구조 샤논(Shannon)의 혼동(confusion)과 확산(diffusion) 이론을 기반 암호화 과정과 복호화 과정이 달라 암호화의 역 과정을 고려해야 함 구현이 복잡함 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘의 개요 스트림 암호 알고리즘 대칭 키 암호화 알고리즘의 한 방식 1970년대 초반부터 주로 유럽에서 연구 발표된 쉬프트 레지스터를 이용한 이진 수열 발생기를 사용하여 입력되는 정보를 비트단위로 암호화하는 시스템 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘의 개요 스트림 암호 블록 암호보다 하드웨어로 구현하였을 때 수행속도가 빠르며 하드웨어 복잡도 역시 낮음 전송 오류가 매우 높거나, 메시지 버퍼링이 제한되어 있거나, 문자들이 수신 즉시 처리되어야 하는 상황에서 유용하게 사용 일회용 패드(One-time Pad)의 이론적 특성으로부터 연유됨 일회용 패드 Vernam(버넘) 암호로도 불림 완전히 임의로 생성된 키 열을 사용 키 열은 평문과 같은 길이를 가지며, 평문과 비트별 XOR 연산이 되어 암호문을 생성 Ci = Mi ⊕ Ki for I=1,2,3.... Ci : 암호문 문자의 비트열 Mi : 평문 문자의 비트열 Ki : 키열 ⊕ : XOR 연산자 전체 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘의 개요 스트림암호 RC4 일회용 패드 완벽한 비밀성 제공 완벽한 안전성을 제공하지만, 실용적이지는 못함 RC4 Rivest(라이베스트)가 설계한 바이트 단위로 연산을 하는 키 크기가 가변인 스트림 암호 알고리즘 임의 순열(Random Permutation)의 사용에 기반을 둠 암호의 주기가 10보다 큼 출력 바이트마다 8~16개 기계 연산이 수행 소프트웨어로 매우 빠르게 수행될 수 있음 SEA(Software-optimized Encrypton Algorithm) Rdgaway와 Coppersmith(카퍼스미스)에 의해 1993년 32비트 컴퓨터 고속 스트림 암호로 설계 초기화 단계 : 이 동안 SHA(Secure Hash Algorithm)를 이용하여 대량의 테이블 집합을 초기화 매우 빠른 성능을 얻을 수 있게 해 줌 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘의 개요 스트림 암호, 블록 암호화 알고리즘의 분류 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘 : DES DES DES의 역사 처음에는 DEA(Data En- cryption Algorithm)이라고도 불리었음 1976년 11월 23일 정부의 공식 암호화 알고리즘으로 채택 국제 표준화 기구(ISO)에 의해서도 표준으로 채택 1977년 1월, 연방정보처리규격 FIPS-46(Federal Information Processing Standard)에 등록되어 “Data Encryption Standard”로 공표되어 표준 알고리즘으로 선정 주로 민간용으로 사용되고 있으며 ANSI(American National Standards Institute) 표준으로도 지정되어 금융 기관 등에서 널리 사용되고 있음 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘 : DES DES DES의 구조 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘 : DES DES DES 알고리즘 64비트의 키(외부키)중 56비트는 실제의 키(내부 키)가 되고 나머지 8비트는 검사용 비트로 사용 64비트 단위 블록으로 구성된 평문 메시지를 16라운드(round)의 반복적인 암호화 과정을 실행 각 라운드마다 전치(transposition) 및 대치(substitution)의 과정을 거친 평문과 56비트의 내부 키에서 나온 48비트의 키를 이용하여 암호문을 만듦 DES 암호 알고리즘의 복호화 과정은 암호화 과정과 동일하지만, 키만 역순으로 사용 DES암호 알고리즘의 각 사이클(cycle)에서 사용되는 키는 이전 단계의 키를 1 비트(bit) 이동(shift)하여 사용 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘 : DES DES DES 알고리즘 DES 암호 알고리즘의 F함수는 8개의 S-box로 구성 S- box는 6비트의 입력을 4비트의 출력으로 변환하는 함수 S- box는 역방향으로 복원이 매우 어려운 강한 비선형성을 가지고 있음 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘 : DES DES DES 알고리즘 S-box는 한 비트 입력의 변화가 2비트 이상의 출력 변화를 나타내어야 하며, 확산 효과를 유발시키는 특징을 갖고 있어야 함 S 박스 내에 포함되는 수열 예시 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘 : DES DES가 전수 조사에 의한 브루트-포스((brute force;무차별 대입공격)) 공격에 취약한 것으로 알려지면서 DES의 안전성을 강화하려는 노력들이 진행 - 브루트-포스공격 : 보안 기술을 깨 나가는 크래킹 공격 예) 크렉 등 소프트웨어를 이용하여 password를 추측하는 방법 Double DES와 Triple DES 등이 발표 Double DES Double DES는 DES의 암호화 과정에 서로 다른 키를 사용하여 암호화를 2회 반복하는 방식 Double DES의 암호화 과정 예시 2개의 키에 의해 2회 암호화되므로 DES 보다 안전성이 상당히 향상 중간과정공격(Meet-in-the-Middle)에 취약 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 대칭키 암호 알고리즘 : DES Triple DES Double DES의 Meet-in-the-Middle 공격에 대한 취약점을 개선 2개의 키를 사용하여 DES의 암호화와 복호화를 3회 혼용 Triple DES의 암호화 과정 예시 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭 키 암호 알고리즘 IDEA(International Data Encryption Algorithm)- 유럽표준 블록 암호 알고리즘 64비트의 평문에 대하여 동작 키의 길이 : 128비트 8라운드의 암호 방식 적용 암호화와 복호화에 동일한 알고리즘이 사용 IDEA 알고리즘 상이한 대수 그룹으로부터의 세 가지 연산(Additional modular 216, Multiplication Modular 216+1)을 혼합하는 것 하드웨어나 소프트웨어로 쉽게 구현 16비트 단위 연산을 사용하여 16비트 프로세스에 구현이 쉬움 PGP(Pretty Good Privacy)의 메일 암호 시스템에 사용, 유럽 표준 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭키 암호 알고리즘 SEED SEED의 개요 1999년 한국정보보호진흥원(KISA)에 의해 개발된 국내 대칭키 기반 블록 암호 알고리즘 1999년 한국정보통신협회(TTA)에 의해 국내 표준으로 채택 현재 전자상거래, 전자 메일, 인터넷 뱅킹, 데이터베이스 암호화, 가상 사설망(VPN), 지적재산권 보호 등의 다양한 분야에서 사용 대칭 키 기반 블록 암호 알고리즘 128비트의 키를 사용하는 128비트 블록 단위로 메시지를 암호화 16라운드의 Feistel 구조로 구성 2개의 S 박스 사용 DES, MISTY와 비교하였을 때 우수한 내부 함수를 내장 차분 공격 및 선형 공격에 강함 블록암호공격 - 차분공격 : 암호문 블록의 비트 차이를 이용 - 선형공격 : 알고리즘 내부의 비선형 구조를 선형화시켜 열쇠를 찾음 - 전수공격법 : 모든 경우의 수를 조사 - 통계적분석 : 알려진 모든 통계적인 자료를 이용 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭키 암호 알고리즘 SEED SEED의 구조 128비트 단위 블록으로 구성된 평문 메시지를 16라운드의 Feistel 구조를 거쳐 암호화 128비트의 평문 메시지 블록은 두 개의 64비트 메시지 블록으로 분할 분할된 메시지 블록들은 F 함수, XOR(exclusive OR) 연산 등을 실행하는 16회 반복 16 라운드 이후 반복 메시지 블록들은 통합되어 128비트의 암호문 메시지 블록이 됨 각 라운드에 대해서는 서로 다른 64비트의 키가 적용 됨 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭키 암호 알고리즘 SEED SEED의 구조 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭키 암호 알고리즘 SEED F 함수 수정된 Feistel 구조로 구성 64비트 블록을 분할한 32비트 블록 2개(C, D)와 64비트 키에서 분할된 2개의 라운드 키 Ki, 0와 Ki,1을 입력받아 XOR 연산, MOD (modulation) 연산, G 함수 등을 거친 후 32비트 블록 2개를 출력 각 라운드 내에서 사용되는 F 함수의 구조 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭키 암호 알고리즘 SEED G 함수와 S 박스 F 함수 내에서 사용되는 G 함수는 4바이트 입력 데이터를 2개의 S-box 를 이용하여 전치하여 4바이트의 출력 값으로 만드는 기능을 제공 S-box는 DES의 경우와 마찬가지로 수열로 구성 G 함수의 구조 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭 키 암호 알고리즘 Skipjack(스킵잭) RC5 미국의 NSA(National Security Agency;미국 국가 안전보장국)에 의해 1985 ~ 1990 사이 개발 1993년 4월에 발표된 대칭 키 암호 알고리즘 64비트 블록을 사용하는 대칭 키 암호 알고리즘 80비트의 키 크기와 32라운드의 암호방식을 적용 비밀 키를 보관하기 위한 일종의 스마트카드인 클리퍼 칩(FORTEZZA PCMCIA 카드)에 적용이 쉬움 RC5 1994년 로널드 리베스트에 의해 개발 1997년 RSA 데이터 보안(Data Security)에 의해 특허를 받은 암호 알고리즘 여러 블록 크기의 블록 암호화 정수 덧셈, 비트방향(bit-wise) 논리적 배타 합 애플리케이션, 변수 회전을 통해 암호화 키 사이즈와 라운드 횟수는 가변적 전형적인 블록 사이즈 : 32, 64, 128비트 라운드 횟수 : 0 ~ 255까지 가능, 키 사이즈 : 0 ~ 2048비트까지 가능 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭 키 암호 알고리즘 차세대 암호 표준(AES) 차세대 암호 표준(AES : Advanced Encryption Standard) 1999년 미 국립 표준 기술 위원회(NIST : National Institute of Technology)에서 발표 후보 :MARS, RC6, 라인델(Rijndeal), 서펀트(Serpent), 투피쉬(Twofish) 2000년 10월 2일 NIST는 벨기에 암호학자인 조안 데멘 박사와 빈센트 라인멘 박사가 개발한 라인델(Rijndeal) 블록 암호화 알고리즘을 AES 알고리즘으로 선정 AES 키 확장(expension)과 라운드 키 선택으로 구성 라운드 키의 전체 비트 수 : 라운드에 1을 더한 수만큼 곱한 블록 길이와 동일 라운드 키들은 확장 키로부터 취해짐 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭 키 암호 알고리즘 차세대 암호 표준(AES) 라인델 블록암호화 알고리즘의 계층 구조 정보보호 개론

암호 알고리즘 대칭키 암호 알고리즘 기타 대칭키 암호 알고리즘 차세대 암호 표준(AES) 라인델 블록 암호화 알고리즘 기타 대칭키 암호 알고리즘 차세대 암호 표준(AES) 라인델 블록 암호화 알고리즘 모든 알려진 공격에 대한 대응이 가능 간단한 설계, 코드 압축 및 다양한 종류의 플랫폼에서의 빠른 속도 제공 비선형 계층(Non-Liner Layer)은 최적과 최악의 경우를 고려한 비선형 특성을 갖는 S-box 들의 병렬 메트릭스의 응용(Application) 다음 단계인 선형 혼합 계층(Liner Mixing Layer)은 여러 라운드의 높은 확산에 대한 보장을 제공하는 계층 키 추가 계층(Key Addition Layer)은 중간상태(intermediate state)에 대한 라운드 키의 논리적 배타합을 이룸 다양한 블록크기인 128, 192, 256 비트 등 독립적으로 선택 가능한 키 길이를 가지고 각 단계의 암호화 과정이 반복되는 블록 암호화 중 하나로 분류 안전성을 검증 받은 차세대 암호 표준(AES) 라인델 블록 암호화는 제한된 영역이 없는 고속 칩, 스마트카드 등의 컴팩트 보조 프로세서 들을 구현할 때 적합 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 공개키 암호 알고리즘의 개요 1976년 W. Diffie와 M. E. Hellman이 “New Directions in Crytography”이란 논문을 발표하면서 최초로 공개키 개념을 소개 키 분배 문제, 키 관리 문제 및 서명 문제를 해결 1978년 Rivest, Shamir, Adleman(애들먼)에 의해 소인수분해의 어려움에 기반을 둔 공개키 암호 알고리즘(RSA)이 개발 공개키 암호 시스템 키 생성 알고리즘을 통해 두 개의 키를 생성 공개키(public key), 개인키(private key) 비대칭 키(Asymmetric key) 암호화 방식 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 공개키 암호 알고리즘의 개요 장점 단점 공개키 암호알고리즘 분류 키의 안전한 분배문제와 키 관리 문제가 쉬움 단점 암호화 및 복호화를 위한 처리 속도가 대칭키 암호 방식보다 느린편 공개키 암호알고리즘 분류 배경이 되는 수학 이론에 따라 인수분해(integer factoriza- tion)문제 기반 알고리즘 이산대수(discrete logarithm) 문제 기반 알고리즘 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 공개키 암호 알고리즘의 개요 인수분해 문제 기반 공개키 암호 알고리즘 합성수의 소인수 분해의 어려움을 이용하여 암호화 및 복호화를 수행 백 자리 크기 이상의 두 개의 소수 p, q가 존재, p, q의 곱 n을 계산할 경우 p와 q를 알고 있는 사람은 n을 계산하기 쉬움 n만 알고 있는 사람은 n으로부터 p와 q를 인수분해 하여 찾아내기는 매우 어려움 대표적인 인수분해 문제 기반 암호 알고리즘 RSA, Rabin 등 이산대수 문제 기반 공개키 암호 알고리즘 이산대수(discrete logarithm) 문제 큰 소수 p와 주어진 정수 g(0과 p-1사이), g에 대한 mod p 연산의 결과 y y=gx(mod p) g, y, p에서 x를 구하는 것 대표적인 이산대수 문제 기반 알고리즘 ElGamal(엘가말), 타원곡선 (ECC : Elliptic Curve Cryptography) 등 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 인수분해 문제 기반 공개키 암호 알고리즘 RSA(Rivest-Shamir-Adlman) 암호화와 복호화를 위한 키를 생성하기 위해서 두 개의 매우 큰 소수(pime mumber) p와 q를 임의로 선택하여 n = p X q (p, q는 소수)를 계산 d와 (p-1)·(q-1)에 대해 소인수 분해결과가 1이 되도록 d를 구함 gcd(d, (p-1)·(q-1)) = 1 여기서, 만족하는 d값을 복호화 키로 함 암호화 키 e·d = 1 mod ((p-1) ·(q-1))을 만족 e를 구함 mod(modular) 연산은 1과 ((p-1) ·(q-1))을 나눈 나머지 값을 취함 암호화 평문 M을 암호화 하기 위해서는 두 개의 양의 정수인 공개키 (e, n)을 이용하여 Me을 계산한 후, n으로 나눈 나머지를 암호문 C로 만듦 복호화 비밀키 (d, n)을 이용하여 암호문 C를 d번 곱한 후 n으로 나눔 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 인수분해 문제 기반 공개키 암호 알고리즘 RSA(Rivest-Shamir-Adlman) 암호문 C는 평문 M보다 결코 증가하지 않음 RSA 암호화의 안전성을 위해서 킷값은 적어도 512비트의 n을 사용 암호화/복호화 과정 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 이산대수 문제 기반 공개키 암호 알고리즘 ElGamal 이산대수(discrete logarithm) 문제를 근간으로 만들어진 공개키 암호 알고리즘 방식 이산 대수 문제 큰 소수 p로 만들어진 집합 Zp상에서의 원시 원소를 g라 할 때 gx ≡ y mod p의 g와 y값을 알고 있어도 loggy ≡ x를 구하는 것이 어려움 g를 알고 있는 사용자가 y를 계산하는 것은 간단 사용자는 큰 소수 p를 선정하여 Zp상의 원시 원소 g와 함께 p를 공개 송신자 A Zp상의 임의의 원소 xA를 비밀 정보로 선택하여 yA ≡ gxA mod p의 공개 정보 yA을 계산함 송신자 B Zp 상의 임의의 원소 xB를 비밀 정보로 선택하여 yB ≡ gxB mod p의 공개 정보 yB를 계산함 송신자 A와 수신자 B의 yA, yB, p, q를 공개 목록에 등록함 yA 와 yB가 송신자 A와 수신자 B의 공개 암호화 키 Ke이고 xA와 xB가 송신자 A와 수신자 B의 비밀 복호화 키 Kd가 됨 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 이산대수 문제 기반 공개키 암호 알고리즘 ElGamal 송신자 A가 평문 M을 암호화하여 암호문 C를 수신자 B에게 전송하기 위해서, Zp상에서 임의의 난수 r∈Zp-1을 선정하여 수신자 B의 공개 암호화 키 yB로 K ≡ yr mod pB를 계산 암호문 C C1 ≡ yr mod p와 C2 ≡ KM mod p을 계산한 다음 C = ( C1, C2 )가 됨 수신자 B의 평문 복호화 과정은 암호문 C1에 수신자 B자신의 비밀 복호화 키xB를 누승하여 K≡ Cxbmodp1를 구한 다음 M ≡ C2/Kmodp로 평문을 구함 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 이산대수 문제 기반 공개키 암호 알고리즘 타원곡선(EC) 대개 실수와 유리수와 같은 유한대 영역에 대해 정의되고 이산대수 문제에 대한 아날로그를 구현 나의 곡선 무한한 싱글 포인트 O를 갖는 y2 = x3 + ax + b 타원곡선의 공간들 덧셈은 모듈러 곱셈의 카운터 파트 곱셈은 모듈러 멱승 연산의 카운터파트 하나의 타원 곡선 상에 주어진 두 지점 P와 R에 대해 K=PR을 만족하는 K를 찾아낸다는 것은 타원곡선 이산 대수 문제로 알려진 어려운 문제임 작은 키 값을 갖고도 높은 보안 수준을 이룰 수 있음 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 이산대수 문제 기반 공개키 암호 알고리즘 공개키 암호화 방식의 예 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 대칭키와 공개키 암호 방식의 비교 공개키(public key) 암호의 주요한 장점 강화된 보안성과 편리함 전자서명 기법을 제공 부인방지(Non- Reputation) 공개키 인증에서는 사용자가 스스로 자신의 개인키 보호에 대한 전적인 책임을 짐 공개키 암호법의 단점 암호화 속도 전자 봉투(Digital Envelope) 공개키 시스템은 대형 파일이나 메시지를 암호화하는데 사용되는 비밀키의 암호화에 사용 가장공격(Impersonation)에 취약 침입자는 인증기관(Certification Authority)을 공격하여 획득한 공개키 인증서를 사용해 다른 사용자인 척 함 정보보호 개론

암호 알고리즘 공개키 암호 알고리즘 대칭키와 공개키 암호 방식의 비교 대칭키 암호방식과 공개키 암호방식 비교 정보보호 개론