암호화
• 송신자와 수신자 사이에서 안전하게 메시지를 전송하고 싶음
암호화와 관련된 용어
• 평문(Plaintext): 암호화되기 전의 텍스트
• 암호문(Ciphertext): 암호화된 텍스트
• 암호화(Encryption): 텍스트를 알아볼 수 없도록 만드는 과정
• 복호화(Decryption): 알아볼 수 없는 텍스트를 다시 복원하여 읽을 수 있게 만드는 과정
• 키(Key)
• 대칭키 암호화 알고리즘(Symmetric-key algorithm)
• 앨리스(송신자)와 밥(수신자)이 비밀 키를 공유함
• 앨리스는 키를 사용하여 메시지를 암호화함
• 앨리스는 암호화된 메시지를 밥에게 전송함
• 밥은 키를 사용하여 메시지를 해독함
• 이브(도청자)는 키 없이는 메시지를 읽을 수 없음
• 밥은 공개/비밀 키 쌍을 가지고 있음
• 밥은 공개 키를 공개하고, 비밀 키는 비밀리에 보유함
• 앨리스는 밥의 공개 키를 사용하여 메시지를 암호화함
• 메시지는 밥의 비밀 키를 사용해서만 복호화할 수 있음 → 밥만이 이 메시지를 열 수 있음
암호화/복호화에 동일한 키 사용
암호화와 복호화에 서로 다른 키 사용
대칭키 vs. 비대칭키
전통 암호화 방식
• 고전적인 방법
• 평문의 각 문자를 다른 문자로 대체하는 방식
• 단일 알파벳 치환
• 시저 암호라고도 불리는 치환 암호의 기본 형태
• 알파벳을 좌우로 이동하여 암호문을 생성
• 예: 앞으로 3글자 이동
• A → D, B → E, ..., W → Z, X → A, Y → B, Z → C
• 예시: 평문이 "HELLO"이고 키가 15일 때 암호문을 생성하라
• 키가 15일 때, 암호문 "WTAAD"를 해독하라
• 문자의 위치를 변경하여 암호문을 생성
• 예시
• 평문 "HELLOMYDEAR"을 아래 전치 암호를 사용하여 암호문으로 만들어라
• 암호문이 "ELHLMDOYAZER"인 경우, 아래 전치 암호를 사용하여 평문은 무엇인가?
• 문자 기반에서 비트 기반으로
• 텍스트 데이터뿐만 아니라 멀티미디어도 암호화 필요
• 평문과 키에 비트 단위 XOR
연산을 적용하여 암호문을 생성
• 평문: 01010111 01101101 01101011 01101011 - "Wiki"
• 키: 11110011
• 암호문: 10100100 10011010 10011000 10011010
• 복호화를 위해 암호문과 키에 XOR 연산을 적용
• 입력 비트를 좌우로 이동하여 암호문을 생성
• 전치 암호의 한 종류
• S-박스(Substitution box): N비트를 입력으로 받아 M비트를 출력함
• 데이터 암호화 표준(Data Encryption Standard)
• 대표적인 대칭키 암호화 알고리즘
• IBM에서 설계
• 키 = 56비트 (+ 8 패리티 비트)
• 라운드 암호의 한 종류
• 56비트 키는 너무 짧기 때문에 키 크기를 늘리기 위해 세 번 암호화
• 고급 암호화 표준(Advanced Encryption Standard)
• 3DES의 짧은 키를 보완하기 위해 개발됨
• 2002년에 표준 암호화 방식으로 선정
• 키 크기: 128, 192 또는 256
• Rivest, Shamir, and Adleman에 의해 개발된 RSA 알고리즘
• 공개 키: e
• 개인 키: d
• Bob은 공개 키와 개인 키를 생성함
– 두 개의 소수인 p와 q를 선택함
– n=pxq
• n은 암호화와 복호화에 사용되는 "모듈러스"임
– Ф=(p-1)x(q-1)
– 무작위 수 e를 선택함
– d를 선택하여 dxe=1modФ이 되도록 함
• 예: Ф=60인 경우, 1modФ=1, 61, 121, 181,...
• Bob은 e와 n을 공개함: 공개 키
• Bob은 d와 Ф를 공개하지 않음: 개인 키
• Alice가 Bob에게 메시지를 보내려면, Alice는 다음과 같이 암호문을 계산함
• C = Pe(mod n)
• Bob은 d를 알고 있으므로 다음과 같이 암호문을 해독함
• P = Cd(mod n)
• d가 없으면 메시지를 해독할 수 없음. 따라서 Bob만이 이 메시지를 해독할 수 있음
• Bob은 키를 생성함 – p=7, q=11을 선택함
– n=7x11=77
– Ф=6x10=60
– e=13을 선택함
– d=37이라면 조건이 만족함(13x37=481, 481mod60=1)
– e와 n을 공개함
• Alice는 Bob에게 메시지를 보내려고 함
• 평문: 5라고 가정함
• 암호문은 다음과 같이 계산됨
• C=513 mod77=26
• 암호문: 26
• 이를 Bob에게 보냄
• Bob은 26을 받았습니다. 다음과 같이 암호문을 해독함
• P=2637 mod77=5
• 따라서 Alice가 보낸 메시지는 "5"입니다.
• p와 q는 512비트 소수 중에서 선택됨 - 매우 큰 소수
• p와 q에서 n과 Ф를 계산함
• e를 선택하고 적절한 d를 찾음
• 평문이 P인 경우
• 암호문을 생성함. C = Pe(mod n)
• Bob이 C를 받으면 다음과 같이 암호문을 해독함
• P = Cd(mod n)
• 장점
– 대칭 키 알고리즘을 사용하려면 송신자와 수신자가 비밀 키를 공유해야 함
– 비밀 키를 비밀리에 공유하기 어려움
– RSA는 키 공유 과정을 필요로하지 않음
• 단점
– 복잡하여 속도가 느림
• 사용 예시
– RSA를 사용하여 비밀 키를 전송한 후, 대칭 키 암호를 사용하여 통신함
• 비밀 키를 공유하기 위한 방법 - 포인트: x와 y는 직접 전송되지 않음
• Alice가 Bob에게 비밀 키를 보내려고 함
– Alice는 p와 g를 선택하고 Bob에게 보냄. p는 소수임
– Alice는 수 x를 선택하고 R1을 계산함
• R1=gxmodp
– Bob은 수 y를 선택하고 R2를 계산함
• R2=gymodp
– Alice는 R1을 Bob에게 보내고, Bob은 R2를 Alice에게 보냄
– Alice는 K를 계산함
• K=(R2)x modp
– Bob은 K를 계산함
• K=(R1)y modp
• g=7이고 p=23이라고 가정함
• Alice: x=3을 선택함. R1=73mod23=21.
• Bob: y=6을 선택함. R2=76 mod23=4.
• Alice는 21을 Bob에게 보냄
• Bob은 4를 Alice에게 보냄
• Alice는 K를 계산함: K=43 mod23=18
• Bob은 K를 계산함: K=216 mod23=18
• K는 공유된 비밀 키임
• Eve(도청자)가 R1과 R2를 가로챘다고 가정해봅시다.
• Eve는 비밀 키를 알아내기 위해 x와 y를 찾아야하지만, 이는 매우 어려움
• 대칭 키를 사용하여 기밀성 보장
• 대칭 키는 일반적으로 비대칭 키 암호화를 사용하여 전송됨
• 비대칭 키를 사용하여 기밀성 보장
• 송신자와 수신자 모두 공개/비공개 키 쌍을 생성해야 함
• 복잡성 때문에 긴 메시지에는 적합하지 않음
• 암호화/복호화는 기밀성을 제공하지만 무결성은 제공하지 않음
• 때로는 문서에 기밀성이 필요하지 않지만 무결성이 필요함
• 메시지 다이제스트를 사용하여 메시지가 전송 중에 수정되지 않았음을 보장함
• 송신자는 해시 함수를 사용하여 메시지 다이제스트를 생성함
• 송신자는 메시지와 메시지 다이제스트를 수신자에게 전송함
• 수신자는 동일한 해시 함수를 사용하여 메시지 다이제스트를 생성하고 송신자로부터 받은 메시지 다이제스트와 비교함
• 메시지 다이제스트는 비밀리에(암호화를 사용하여) 전송되어야 함
• 메시지 무결성을 제공하기 위해 사용되는 해시 함수는 다음과 같은 특성을 가져야 함
• 일방성: 다이제스트로부터 메시지를 유추할 수 없음
• 약한 충돌 저항성: 메시지 x에 대해 동일한 해시 값이 나오는 다른 메시지 y를 찾을 수 없음
• 강한 충돌 저항성: 두 개의 메시지 x와 y를 찾을 수 없음, 그들의 해시 값이 동일함
• Secure Hash Algorithm-1
• 미국 국립표준기술연구소(NIST)에서 설계됨
• 160비트 메시지 다이제스트 생성
• 블록에서의 결과가 다음 블록 계산에 사용되기 때문에 메시지의 작은 변화도 완전히 다른 해시 값으로 이어짐
• SHA1("Thequickbrownfoxjumpsoverthelazydog") = 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
• SHA1("Thequickbrownfoxjumpsoverthelazydog.") = 408d94384216f890ff7a0c3528e8bed1e0b01621
• 해시 함수는 메시지 무결성을 제공할 수 있지만 메시지가 실제로 송신자에 의해 전송되었음을 보장할 수 없음
• 메시지 인증을 위해 메시지 다이제스트를 생성하는 데 키를 사용해야 함
• 키가 포함된 해시 함수: 키를 포함한 해시 함수
• Alice와 Bob 사이의 공유 키를 사용하여 메시지 다이제스트 생성
• HMAC(Hashed MAC): 메시지 인증을 위한 표준 방법
• MAC를 사용하려면 공유 비밀 키가 필요함 - 키 공유가 어려움
• 디지털 서명은 송신자를 인증하기 위해 비대칭 키를 사용함
• Alice는 개인 키를 사용하여 문서를 암호화함
• Bob은 Alice의 공개 키를 사용하여 문서를 복호화함
• 복호화가 가능하면 Alice가 문서를 보냈다는 것이 확실함
• 비대칭 키 암호화는 시간이 많이 걸림
• 따라서 디지털 서명은 메시지 자체가 아닌 메시지 다이제스트에 대해 주로 사용됨
• 송신자가 메시지를 보낸 것을 부인하지 못하도록 함
• 이를 위해 신뢰할 수 있는 제3자가 필요함
• Alice의 키로 서명된 메시지 사본이 신뢰할 수 있는 센터에 저장됨
• 나중에 신뢰할 수 있는 센터는 메시지를 자체 비밀 키로 서명하여 Bob에게 보내고, Bob은 이를 받음
• Alice가 메시지를 보냈다는 것을 부인하면 Bob은 신뢰할 수 있는 센터에 저장된 메시지와 비교할 수 있음