암호화 및 해시함수
1. 대칭키 암호화
1) 대칭키 암호
- 암호화와 복호화에 하나의 동일한 비밀키를 사용하는 암호방식
( 대칭키 암호, 비밀키 암호, 단일키 암호, 관용암호 )
- 블록암호화 스트링 암호
2)블록암호
① 블록 암호의 방식
평문을 고정된 크기의 블록으로 나누어 각블록마다 암호화 과정을 수행하여 블록단위의
암호문을 얻는 대칭키 암호방식 (암호화된 블럭을 연결하면 평문에 대한 암호문 완성)
② 블록암호 알고리즘의 구조
- 출력 블록의 각 비트는 입력블록과 키의 모든 비트에 영향을 받음
- 단순한 함수를 반복적으로 적용함으로써 암호학적으로 강한 함수를 만듦
라운드 함수 : 반복되는 함수
라운드 키 : 라운드 함수에 작용하는 키 (키를 입력받아 라운별로 키를 별도 적용)
키 스케쥴 : 키를 입력하여 라운드 키를 발생시키는 과정
③ 라운드 함수의 구조
▣ 파일스텔 구조 (Feistel)
하나의 입력 블록을 분할하여 좌우 두개의 블록으로 구분 후 짝수번의 라운드 진행
각라운드의 출력이 다음 라운드의 입력블록 이 됨
- 입력의 오른쪽은 그대로 왼쪽 블럭으로 출력
- 입력의 오른쪽과 키의 라운드 함수에 입력의 왼쪽블록을 XOR연산, 오른쪽 블럭 출력
라운드 함수와 관계없이 역반환 가능
두번의 수행으로 블록간의 완전한 확산
DES, SEED등 많은 블록암호에 사용됨
▣ SPN 구조 (Substitution Permutation Network, 치환과 전치 활용)구조
하나의 입력블록을 여러개의 소블록으로 나눈 후 라운드 진행
각 라운드의 출력블록이 다음 라운드의 입력블록이 됨
- 각 소블록을 S-Box로 입력하여 치환
- S-Box의 출력을 P-Box로 전치
라운드 함수가 역변환 가능해야 함 (Pbox, Sbox 역함수 존재)
더 많은 병렬성을 제공 (속도)
AES, ARIA등 최근의 블록암호에 사용
④ 블록의 암호사용모드
각 블록에 블록암호를 사용방법에 따른 구분
▣ 전자코드북(ECB, Electronic Code Book) 모드
입력받은 평문을 블럭으로 나누어 각 블럭에 대해 키를 적용해 암호화
암·복호화(Encryption, Decryption)시 병렬처리가능
암호화 블록의 오류가 다른 블록에 영향을 미치지 않음
동일한 평문블록은 동일한 암호문 생성(패턴분석가능, 이미지 등 정보파악가능)
▣ 암호연결블록(CBC, Ciper Block Chaining) 모드
암호화시 병렬처리 불가능
- 암호문이 주어진 상태는 인접한 두개의 블록 XOR를 통해 복호화 병렬처리가능
암호화시 평문블록오류가 그 다음 암호문에 영향 → 메시지 인증에 사용
- 평문 비트값 변경시 암호화 결과에 영향 (CBC마지막 블록을 MAC이용가능)
▣ 암호피드백(CFB, Ciper Feedback) 모드
초깃값을 암호화해서 블록과 XOR, 특정 입력이 이후로 영향을 미침 → 메시지 인증에 사용
복호화 함수가 필요없음 (키 복호화한 값과 이전블록의 암호화값을 XOR)
▣ 출력피드백(OFB, Output Feedback) 모드
. 암호문 블록의 오류는 한 블록에만 영향을 미침, 초깃값을 암호화하여 연산에 사용(블럭마다 암호화 반복)
→ 영상이나 음성같은 디지털화된 아날로그 신호에 사용 (신호를 연속으로 보낼때)
복호화 함수 필요없음 (키 복호화한 값과, 암호문과 XOR로 복호화)
▣ 카운터(CTR)모드
초깃값을 수열로 생성하고 암호화하여 평문블록과 XOR로 암호화, 병렬처리가능
복호화시 병렬처리가능하고 복호화함수 불필요(복호화된 키와 암호문 XOR), 오류의 확산X
3)스트림 암호
평문과 같은 길이의 키 스트림을 생성하여 평문과 키를 비트단위로 XOR하여 암호문을 얻는 대칭키방식
임의의 길이의 평문이 주어져도 동일한 길이의 키스트림 생성가능(규칙성이 없어 예측불가능한 랜덤수열이 안전하나 복호화를 위해서는 저장 및 활용이 어려움)
의사랜덤(pseudorandom) 수열생성 (예측이 어려우면서도 자동화된 생성이 가능, LFSR-Linear Feedback Shift Register등 )
- LSFR 단독사용은 쉽게 해독이 되므로 다른 방식과 함께 키 스트림 생성에 활용
4) 대칭키 암호 알고리즘
DES, AES, IDEA, SEED, CRYPTON, RC5, FEAL, MISTY, Skipjack, ARIA, LEA, RC4
① DES (Data Encryption Standard)
1977년 미국에서 데이터 암호 알고리즘 표준으로 공표
블록 암호 알고리즘
- 블록크기 : 64bit ,키길이 : 56bit
- 파이스텔 구조 : 16라운드(1개 블럭), 키 길이 48bits(라운드키)
컴퓨터 속도개선과 암호해독기술의 발전으로 2001년 AES로 표준변경
② TDEA (Triple Data Encryption Standard)
DES를 3회 반복 (3DES : triple DES)
DES의 짧은 키 길이로 인한 안전성 문제 해결, DES보다 3배 정도 느림
③ AES (Advanced Encryption Standard)
DES를 대신하는 새로운 표준
- 2001년 미국 NIST에서 공표(공모를 통해 Rijndael을 AES로 선정)
블록암호알고리즘
- 블록크기 : 128bit
- 키길이 : 128bit, 192bits, 256bits중 택1 (각각 10라운드, 12라운드 14라운드)
- SPN 구조 (라운드 암호화 키 갯수 : Nr + 1 (Nr개의 라운드 + 평문과 라운드키 XOR연산 )
** 여러가지 대칭키 암호 알고리즘
2. 공개키 암호화
암호화와 복호화에 두개의 서로다른 키를 사용하는 암호방식
한쌍의 키
공개키 : 누구나 공개키를 이용하여 암호화 가능
개인키 : 오직 자신만 개인키를 이용하여 복호화 가능
1) 기반문제 (one way function)
공개키 암호알고리즘은 수학적으로 어려운 문제들에 기반
다양한 일방향 함수 - 소인수분해 문제, 이산대수 문제, 타원곡선 이산대수문제
① 소인수 분해문제
어떤 두 정수의 곱은 빠른 시간안에 구할수 있지만, 임의의 양의 정수의 소인수 분해는 매우 어려움
소인수분해 알고리즘 : RSA
안전한 암호로 사용하기 위한 키의 크기 : 2,048bits 이상
② 이산대수 문제
양의 정수 n, a, x에 대하여 aˣ (mod n)은 빠르게 구할수 있지만, 양의 정수 n,a,y에 대하여 y=aˣ (mod n)인 x를 구하는 것은 매우 어려움
이산대수 문제 기반 알고리즘 : Elgamal, DSA(Digital signature algorighm), KCDSA(한국에서 개발한 디지털 서명 알고리즘), DHKE(Diffie-Hellman Key Exhchange)프로토콜
안전한 암호로 사용하기 위한 키의 크기 : 2,048bits 이상
③ 타원곡선 이산대수 문제
타원 곡성상의 점과 타원곡선에서 정의되는 덧셈 연산을 이용하여 정의되는 이산대수의 문제
정수에서의 이산대수 문제처럼 일방향 함수의 성질을 가짐
타원곡선 이산대수 문제기반 알고리즘 : ECDSA(elliptic curve digita signature algorithm), EC-KCDSA
안전한 암호로 사용하기 위한 키의 크기 : 224bit (키가 작으면서도 안전)
2) RSA 암호 알고리즘
1978년 Rivest, Shamir, Adleman이 개발, 국제암호표준으로 활용
많은 응용분야에서 전세계적으로 활용(신용카드, 증건권래, 이메일) 및 암호키의 안전한 분배 및 관리
① 소인수분해 문제에 기반
자릿수는 비슷하지만 두수의 차가 큰 서로 다른 두 소수 p, q이용 (1024비트 내외)
키생성(수신자) : 공개키(e,n) 개인키(d, p, q)준비
암호화(송신자)
n보다 작은 숫자인 평문 M을 수신자의 공개키(e,n)이용하여 암호문 C계산
복호화(수신자)
암호문 C를 수신자의 개인키 (d,p,q) 이용하여 복호화
** p, q 선택시의 조건
서로다른 두 소수 p,q는 거의 같은 자리수이나 충분히 차이가 남
p-1과 q-1도 큰 소인수를 가지며, GCD(p-1, q-1)작은수
p+1과 q+1이 큰 소인수를 가지며 | p-q |도 충분히 커야 함
3) ElGamal 암호 알고리즘
1985년 ElGamal이 제안
유한체상에서의 이산대수 문제에 기반 (수신자의 공개키를 가지고 개인키를 계산하는 이산대수문제)
Diffie-Hellman 키교환과 같은 원리 이용
4) 타원곡선 암호 알고리즘 (Elliptic Curve Cryptosystem, ECC)
1985년 Miller와 Koblitz가 독립적으로 제안
유한체 상에서 정의된 타원곡선 군에서의 이산대수 문제에 기반 (정수가 아닌 타원곡선의 점을 사용)
RSA, ElGamal등과 동일한 수준의 보안성을 제공하면서도 키의 길이는 짧음
이산대수 문제에 기반을 둔 ElGamal암호 알고리즘등을 변환하여(지수 연산대신에 타원곡선 암호알고리즘으로) 적용
** 그외의 공개키 암호 알고리즘
3. 해시함수(hash)함수
임의의 길이의 입력 데이터를 고정된 길이의 해시코드로 대응시키는 함수
1) 일방향 함수
임의의 데이터에 대한 해시코드는 쉽게 생성, 해시코드에 대응되는 데이터를 역으로 찾는것 어려움
2) 응용분야
메시지인증(HMAC)
전자서명
의사 난수 생성기(PRNG: PseudoRandom Number Generator) - 스트림암호의 키스트림 생성
3) 해시함수 H의 요구조건
- H는 임의의 크기의 입력데이터 D에 적용가능, H는 일정한 크기의 해시코드 h출력
- H와 입력데이터 D가 주어졌을때 해시코드 h=H(D)계산하기 쉬움
- 약한 일방향성 : H와 해시코드 h가 주어졌을때 h=H(D)를 만족하는 입력데이터 D를 구하는
것이 계산상 실행 불가능 ex)사용자 패스워드를 해시코드로 저장할때 노출되는 것을 방지
- 강한 일방향성 : H와 해시코드 입력데이터 D'가 주어졌을때 H(D)=H(D')를 만족하는 다른
입력데이터 D를 구하는 것이 계산상 실행 불가 ex)메시지 인증코드를 탈취 후 새로운 M'생성
하여 속이는 것을 방지
- 충돌저항성 : 입력이 주어지지 않고, 함수만 존재
H가 주어졌을때 H(D)=H(D')을 만족하는 두 데이터 D와 D'를 구하는 것이
계산상 실행 불가능 ex) 생일 공격에 활용 (365명 이상의 사람이 모이면 중복되는 1개의 생일이
반드시 존재하나 실제로는 23명만 모여도 생일이 같은 사람이 존재할 확률 50%이상
4) 해시 알고리즘
① 블록암호 알고리즘에 기초한 해시 알고리즘 (블록암호보다 속도가 훨씬 떨어짐)
② 모듈러 연산을 이용한 해시 알고리즘 (속도가 느려 사용영역제한, 역방향 연산이 간단하여 안전X)
③ 전용해시 알고리즘
MD4 (Message Digest 4)
- 1990년 발표 (현재로는 사용X), 해시코드 크기 : 128비트
- MD5, RIPEMD, IPEMD-160, SHA-I등 많은 전용 해시알고리즘의 기본모델
MD5 (Message Digest 5)
- MD4보다 보수적으로 설계, 해시코드 크기 : 128비트
- 일방향성과 충돌저항성에 문제가 있음 (현재로는 사용X)
SHA-1 (Secure Hash Algorithm)
- 1995년 발표된 표준해시 알고리즘
- 2⁶⁴(10¹⁸)비트보다 작은 크기의 입력데이터에 적용가능, 해시코드 크기 : 160비트
- 18자리의 숫자에 가능, 조금씩 취약성이 드러나고 있음
SHA-2 (Secure Hash Algorithm)
- 2002년 표준해시 알고리즘에 추가 ( SHA-1과 유사한 방법으로 만들어짐)
- 해시코드의 크기에 따라 SHA-224, SHA-256, SHA-384, SHA-512 존재(비트수)
- SHA-224, SHA-256는 2⁶⁴보다 작은 크기의 입력 대응
- SHA-384, SHA-512는 2¹²⁸보다 작은 크기의 입력 데이터에 대응
SHA-3 (Secure Hash Algorithm)
- 2015년 표준해시 알고리즘에 추가
- SHA-1이나 SHA-2와는 다른 완전히 새로운 구조로 만들어짐 (스펀지 구조 : 입력데이터를 모두
흡수하는 단계를 거친후 스펀지를 짜내는 단계에서 원하는 크기만큼의 해시코드 생성)
- 입력 데이터의 크기제한 없음
- 해시코드의 크기 (출력의 크기도 다변화)
고정 : SHA3-224, SHA3-256, SHA3-384, SHA3-512 (고정된 비트수의 해시코드 생성)
가변 : SHAKE128, SHAKE256 (사용자가 원하는 크기의 해시코드 생성)
4. 전자서명 (Digital Signature)
- 메시지를 보낸 사람의 신원이 진짜임을 증명
- 전달된 메시지의 원래 내용이 변조되지 않았음을 보증
- 수기서명과 동일한 효력
- 메시지의 암호화 여부에 상관없이 사용
사용례) 인증서
1) 전자서명 사용의 부가적인 이득
전자서명이 쉽게 전송될수 있음
전자서명을 쉽게 부인할수 없음
전자 서명을 다름 사람이 흉내낼수 없음
타임스탬프가 자동으로 유지될수 있음
2) 전자서명의 요구조건
전자서명은 서명되는 메시지에 의존하는 비트값
전자서명은 서명자만의 고유정보를 사용해야 함
전자서명 생성 및 검증이 비교적 쉬워야 함
전자서명의 위조는 계산적으로 불가능해야 함
전자서명의 복사본을 저장소에 손쉽게 보관할수 있음
→ 해시함수와 공개키 암호사용
3) 전자서명의 동작원리
서명
해시함수 : 메시지에 의존하지만 작은 크기의 데이터 생성
개인키 : 오직 서명자 자신만 서명할수 있음
4) 검증
공개키 : 누구나 서명을 검증할수 있음
5) 전자서명 기법의 종류
ElGamal 전자서명 시법, Schnorr 전자서명 기법
- 이산대수 문제에 기반한 공개키 암호방식 이용
전자서명표준 (DSS: Digital Signature Standard)
- 세가지 기법으로 구성
DSA(Digital Signature Alrorithm) ElGamal과 Schnorr기법에 기반
RSA 전자서명 알고리즘 RSA알고리즘에 기반
ECDSA(Elliptic Curve Digital Signature Algorithm) 타원곡성 암호에 기반
→ RSA는 암호화/복호화 과정이 동일 (암호화 개인키, 복호화에 공개키 사용에 문제없음)
ElGamal 이나 ECDSA는 암호화 과정과 복호화 과정이 다름 (암호화 과정에 개인키를 적용시
전자서명이 되지 않으며, 암호화 알고리즘과 전자서명 알고리즘에 차이가 있음)
5. 키관리
1) 디피-헬먼 키교환(DHKE : Diffie-Hellman Key Exchange) 프로토콜
이산대수 문제에 기반하여 비밀키를 안전하게 공유하는 방법
예) p=13, g=2 송신자는 s=3, 수신자가 보낸 B는 6일때 공유키는 ?
송신자는 s=3, 2^3(mod13)의 결과인 5을 수신자에게 보냄, 수신은 5^3(mod 13)=8 이면 (인증완료)의 결과
수신자는 t=5, 2^5(mod13)=6의 결과인 6을 송신자에게 보냄, 송신자는 k=6^3(mod p) => 6^3(mod 13) = 8
받은 값 B^s(modp) = 8 , 5^3(mod13) = 8, 6^3(mod13)=8
중간자 공격 : 송수신자 사이에 제3자인 공격자가 존재해서 둘 사이의 통신을 바꾸어, 송수신자간
키 공유가 아닌 제3자와 키를 교환하게 됨 ( 키 교환시 상호인증 필요,공개키 암호필요 )
2) 공개키 암호의 키 관리
① 공개선언
자신의 홈페이지에 올려두거나 요청자에게 직접 보냄
홈페이지 또는 전달 도중에 공격을 받아 공개키가 바뀔 위험 존재
② 신뢰받는 센터
모든 사람의 공개키를 신뢰받는 센터가 관리
센터의 디렉터리에 사람들이 공개키를 올림 , 센터는 공개키에 대한 모든 질의에 응답
- 전달 도중 공개키가 바뀔 위험 존재
③ 통제된 신뢰받는 센터
공개키를 배분할때 센터의 서명을 붙임 (타임스탬프 위조의 우려)
공개키 요청시 타임스탬프를 같이 받음, 타임스탬프에 대한 센터의 서명을 공개키와 보냄
공개키에 대한 변조 가능성, 많은 요청에 대한 센터의 부하
④ 인증기관 (CA)
공개키를 인증서로 만들어 분배
인증서 : 개인의 공개키에 인증기관의 서명을 붙인것
사람들의 공개키를 인증서로 변환하여 디렉터리에 붙임
사용시 인증기관 공개키로 검증
3) 공개키 기반구조 (PKI, Public Key Infrastructure)
X.509에 기초해서 인증서를 생성하고 분배, 인증 및 폐지까지 관리하는 체계
공개키 암호를 통해 암호화 및 전자서명을 제공하는 복합적인 보안 시스템
제공서비스 : 기밀성, 무결성, 접근제어, 인증, 부인방지
응용분야 : 은행지불결제 시스템, 기관간 전자문서교환, 병원의무기록에 대한 서명 (공동인증서)
① X.509 (통일된 인증서 구조 정의)
공통 규격이 없으면 사용자들은 인증서마다 별도 프로그램을 사용해야 하므로 많은 불편초래
유효기간, 소유자, 공개키정보등에 인증기관 비밀키로 서명하여 인증서 형태 구성
② PKI 구성요소
사용자 : 다양한 응용에서 전자서명 생서 및 검증, 암·복호화 수행
인증기관(CA, Certification Authority) : 공개키에 대한 인증서 발급
등록기관(RA, Registration Authority) : 사용자들의 인증서 신청시 신분과 소속을 확인함 (은행이나 증권사)
디렉터리 : DAP 혹은 LDAP로 X-500서비스 제공
인증서, 사용자 관련보호, 상호인증서쌍, 인증서 취소목록등을 저장/검색하는 장소
(인증서와 상호인증서쌍은 유효기간 경과후에도 서명검증을 위해 일정 기간 저장)
③ PKI 동작원리
A가 서명한 문서와 인증서를 송신, B는 A가 보낸 인증서를 (CA의 공개키로) 검증
A는 CA에 Bd의 공개키를 요청하여 암호화해서 송신, B는 자신의 개인키로 복호화
④ PKI 관리대상
인증서
- 인증서 관리서비스는 PKI의 핵심(인증서 발행, 공표, 보관 및 관련 정책 수립 및 승인)
상호인증서쌍 (인증기관이 다양한 계층으로 존재하므로 기관간 인증)
- 한 도메인이나 다른 도메인의 인증기관 사이에 발행하는 인증서의 쌍
순방향 인증서 : 인증기관 X에 대해 다른 인증기관에서 생성 (인증받음)
역방향 인증서 : 인증기관 X가 다른 인증기관에 대해 생성 (인증해줌)
- 상호인증서를 사용하여 인증경로 단축가능
인증서 취소목록 (CRL : Certification Revocation List)
- 효력이 상실된 인증서에 대한 목록
- 유효기간 만기전에 인증서 효력이 상실된 경우(개인키 노출, 소유자가 도메인 옮김)
⑤ 인증서의 신뢰 구성
PKI에서 신뢰는 인증 경로를 통해 전달
전자서명 검증과정
검증자는 자신이 신뢰하는 인증기관의 공개키만 알고 있음
인증기관의 공개키를 이용하여 인증경로를 검증함으로써 서명자의 공개키를 획득함
획득한 공개키는 무결성이 보장되며, 이를 이용하여 서명을 검증
PKI의 구성형태 : 계층적구성과 네트워크 구성
- 계층적 구성 : 상위 CA가 하위 CA에 인증서발행, 루트CA는 모두에게 공개
(루트를 기준으로 자신의 경로를 알려주면 상호연결 가능)
- 네트워크 구성 : CA가 독립적으로 존재하며 서로를 상호인증 (국가간, 대등 기관간)
사용자는 자신의 인증서를 발행한 CA의 공개키만 인지
