암호 (Cryptography)

암호개요

암호학 (Cryptology)

• 크립토스(비밀) + 로고스(학문:과학)의 합성어
• 여러가지 형태의 암호화와 복호화 방법을 만드는 암호와
  그것을 해석하고 분석하는 암호분석을 포함함
  

암호 (Cryptography)

• 비밀스럽게 작성한다는 뜻에서 유래되었다.

• 평문 (Plain Text)을 보호하기 위한 암호화 알고리즘을 연구함

• 평문을 해독 불가능한 형태로 변환하거나 또는 암호화된 통신문을
  해독 가능한 형태로 변환하기 위한 원리, 수단, 방법등을 취급하는 기술 또는 과학
  

• 정보보호 서비스 등을 제공하는 기술 (기밀성, 무결성, 인증 서비스 제공)

• 현대 암호학은 학문의 범위가 넓어짐
  (정보보호분야 전반에 걸쳐 비밀통신과 관련된 다양한 문제와 그 문제들의 해결방법에 대한 분야)
  

암호화 기술

• 비밀키 (대칭키) 암호 알고리즘

  • 블록 암호 알고리즘
  • 스트링 암호 알고리즘

• 공개키(비대칭키) 암호 알고리즘

  • RSA, ElGamal, ECC

암호 프로토콜 기술

• 기본 암호 프로토콜

  • 개인식별 및 인증
  • 전자서명

• 발전된 암호 프로토콜

  • 전자 화폐, 전자 결재, 전자 선거

암호해독 (Cryptanalysis)

• 암호문을 해독하기 위해 암호문 (Cipher Text)을 연구함

암호 복호화 과정(Cryptosystem)

• 암호화 및 복호화 과정 그리고 이때 사용되는 암,복호화 키와 키 관리 등을 포함해
  정보보호를 위한 일련의 과정 (프로세스)
  

평문 (M) => 암호화 (E(M) => C) => 암호문 (C) => 복호화 (D(C) => M) => 평문 (M)

암호 용어

암호시스템 설계요건

• 암호화 키(Key)에 의하여 암호화 및 복호화가 효과적으로 이루어져야 함
• 사용이 용이하여야 함
• 공개되어야 함 (AES, ARIIA, LFA)
• 암호화 안전성은 키에만 의존함

암호 방식 : 암호화, 복호화 키에 따라 분류됨

대칭키(비밀키) 암호

• 암호화/복호화 키가 같은 암호
• M => E(M) = C => C => D(C) = M => M
• 여기서 암호화 복호화 키가 같기에 E.key === D.key
• 양쪽에서 사용하고 민감하기에 비밀이 보장되어야 한다.
• 관용키, 비밀키, 대칭키 (DES, SKIPJACK, IDEA, AES, ARIA, KEA, SEED)

비대칭(공개키) 암호

• 암호화/복호화 키가 다른 암호
• M => E(M) = C => C => D(C) = M => M
• 여기서 암호화 복호화 키가 다르기에 E.key !== D.key
• 양쪽에서 다른 키를 사용하기에 암호화키를 알아도 괜찮다.
  (복호화 키를 알려주지 않는 이상 알아내기까지 엄척난 시간이 걸린다.)
  
• 비관용키, 공개키, 비대칭키 (RSA, ElGamal, ECC, DSA, ECDSA, DH)

암호의 역사

• 최초의 암호 (BC 480년 경)
  • 스파르타에서 추방되어 페르시아에 살던 데마라토스
  • 페르시아의 침략 계획 소식을 나무판에 조각하여 적은 후 밀납을 발라 스파르타에 보냄

고전 암호

• 전치 암호 (Transpositioin Chiper)

  • 메시지의 내용변경 없이 배열의 위치만을 바꾸는 방법
  • 평문에 나타난 문자 또는 기호의 형태는 바꾸지 않고 평문을 동일한 길이를 갖는
    몇 개의 블록으로 나눈 후 블록 안에서 일정한 규칙에 따라 문자 또는 기호를 재배열하는 방식
    
  • 순서를 바꾸어 재 배열하는 의미 (Permutation)
  • 대표적인 치환암호 : 스키테일 암호 (Scytale)

• 대치(환치, 대체) 암호 (Subsitution Cipher)

  • 평문에 나타만 문자 또는 기호의 순서는 바꾸지 않고 원래의 문자나 기호자체를 다른 문자나
    기호로 바꾸는 (대치하는) 방식임
    

  • 대표적인 대치암호 : 이동 암호 (Shift Cipher)

  • 시저 암호 (Caesar Cipher)

    • Marcus Cicern에게 군사적으로 중요한 메시지를 보낼 때, 적이 알아볼 수 없도록 문자를
      다른 문자로 대치시켜 메시지를 암호화하여 전달함
      

    • 영문 알파벳 A~Z까지 26자를 3자씩 (Key=3) 오른쪽으로 이동시킨 뒤
      해당되는 글자로 변환시켜 만드는 암호
      

대칭키 암호

블록 암호 (Block Cipher)

• 평문을 일정한 블록 단위로 나누어서 각 블록 마다 암호화 과정을 수행하여,
  고정된 크기의 블록 단위로 암호문을 얻는 방법
  

• Feistal 구조와 SPN 구조로 이루어짐

• 혼돈(Confusion)과 확산(Diffusion)에 기반을 둔 암호

• 혼돈 : 평문의 1비트 변화가 암호문에 어떤 변화를 초래할지를 예측할 수 없는 성질 (Subsitution)

• 확산 : 평문을 구성하는 각 비트들의 정보가 암호문의 여러 비트에 분산되는 성질 (Permutation)

고정된 크기 블록 평문 P   =>   [암호 알고리즘]   =>   고정된 크기 암호문 C

스트림 암호 (Stream Cipher)

• 평문과 같은 길이의 키 스트림을 생성하여 평문과 키 이진 수열을
  비트단위로 베타적 논리합(Bitwise Exclusive OR) 이진연산으로 결합하여 암호문을 얻는 방법
  

• 난수와 의사난수 사용

• 군사 및 외교용으로 널리 사용

• 이동통신 환경에서 구현 용이

• 안전성을 수학적으로 엄밀하게 분석 가능

• 이동통신 등의 무선 통신데이터 보호에 적합함

• 대표적 암호 : RC4, SEAL, BlueTooth, A5

초기값, 키 -> 암호 알고리즘 -> 키 스트림(이진수열) ->
평문(이진수열) XOR 키 스트림(이진수열) -> 암호문

블록 암호 알고리즘

DES (Data Encryption Standard)

• IBM에서 개발, Lucifer 암호시스템을 수정 보완한 대칭키 암호이며, 블록암호임

• 1977년 1월 NIST에 의해 FIPS PUB 46에 미연방 표준으로 채택되어 1997년까지 사용함

• 64bit 평문을 64bit 암호문으로 만들며 56bit 크기의 암호화 키로 암호화됨

• 암호화 과정 한 단계를 라운드(Round)라 표현하고, 혼돈이 이 과정에서 이루어짐

• 16라운드 Feistel 구조를 가짐

  • 입력 n비트를 두 개의 블록 (L0, R0)으로 나누어 한 블록을 라운드함수 F에 적용시킨 후 출력값을 다른 블록에 적용하는 과정을 반복적으로 수행함

• 8개의 S-box를 사용함 (S-box는 대치하는 방법)

• 복호화는 암호화 과정과 동일한 역순

• 블록 암호 연구의 시발점을 제공함

• 1999년에 4개월 동안 분산 환경에서 병렬 처리로 복호화하는데 성공

AES (Advanced Encryption Standard)

• 미국 연방 표준 차세대 암호 알고리즘

• 128bit, 192bit, 256bit의 블록 크기와 키의 크기를 갖는 블록 암호 알고리즘

• AES 후보들 중에 알려진 모든 공격에 안전함

• 여러 가지 platform에 빠르며 효율적임

• 디자인의 간결성 특성을 가짐

• SQUARE (FSE 97)가 Rijndael의 모체임

• AES는 Feistel 구조가 아니라 SPN 구조임

• S-box는 대수적인 방법으로 만들어졌으며 구축방법이 명확

• S-box는 GF(2^8)내에서 x -> x^-1인 함수에 기초한 강도 높은 비선형임
  (차분공격과 선형공격 뿐만 아니라 최근 연구되는 삽입공격에도 방어 효과가 있음)
  

• 라운드 수는 안전성을 고려하여 128비트의 경우 10라운드를 선택함
  (입력 비트에 따라 라운드 수는 쉽게 늘릴 수 있음)
  

• 라운드는 4단계의 레이어(Layer)로 형성됨

  1. ByteSub (바이트 대치) : 비선형 레이어로 차분공격과 선형 암호공격을 방어하기 위한 단계
  2. ShiftRow (행 쉬프트) : 선형 혼합 단계로 라운드를 거듭할 수록 비트를 산란시키는 단계
  3. MixColumn (열 조합) : 입격 블록의 각 열에 해당하는 볼록들이 서로 영향을 받도록 변환시키는 단계
  4. Key XOR (부분키 덧셈) : 각 입력블록에 부분키를 XOR하는 단계

• 마지막 라운드(10라운드)는 3단계의 레이어(Layer)로 형성됨
  (ByteSub, ShiftRow, Key XO)
  

SEED

• 1999년 KISA에서 국내 표준 블록 암호 알고리즘으로 개발
• 128Bit 블록, 128bit 키의 블록암호로 16RoundFeistelx 구조
• Round 함수 : 64Bit를 입력받아 64Bit 라운드 키로 변환하여 64Bit 출력하는데 G함수를 3번 사용함
• G 함수 : 차분공격과 선형공격에 대해 안전성이 우수한 8Bit 입력에 8Bit 출력의 S-box 2개를 사용함
• 차분해독법(DC)/선형해독법(LC)에 대하여 안전성 유지
• S/W로 구현시 3DES보다 고속임
• 라운드 키를 간단히 계산할 수 있도록 설계함
• 알고리즘의 라운드 동작과 동시에 암/복호화 라운드 키가 생성될 수 있도록 설계함
• 우리나라 표준이라 지금도 사용

ARIA

• 2004년 개발된 128Bit 국가 표준 블록암호알고리즘
• 경량 환경 및 하드웨어 구현을 위해 최적화된, Involutional SPN 구조를 갖는 범용 블록 암호 알고리즘
• 이름은 개발에 참여한 학계, 연구소, 관(정부)의 공동 노력을 뜻함
• 128Bit 블록크기와 128/192/256Bit 키 크기를 가짐 (AES와 동일)
• Involutional Subsitution-Permutation Network (SPN) 구조

공개키 암호

공개키 암호

• 암호화에 사용되는 키와 복호화에 사용되는 키가 서로 다른 암호 시스템
• 비대칭키 암호라고도 함
• 공개키를 공개해도 비밀키만 비밀유지하면 상관없음

대칭키 암호와 공개키 암호의 장단점

암호 방식

• 혼함암호방식 (Hybrid Cryptosystem) : 공개키 암호 알고리즘(키 분배 알고리즘) + 대칭키 암호 알고리즘

수학적 어려운 문제에 기반하여 구성

모듈러 연산 알아보기

공개키 암호 시스템

RSA 암호

• 1978년 미국의 Rivest, Shamir, Adleman 개발
• 커다란 두 소수의 곱 n = pq의 인수분해문제에 안전성을 둠
• 현재 보안강도 122Bit 기준: n이 2048Bit 이상 안전함

RSA 암호 - Setup

1. 큰 소수 p, q를 선택함
2. n = pq를 계산함 (φ(n) = φ(pq) = (p-1)(q-1)) : 오일러 함수 (서로소 갯수 구하는 공식)
3. 자연수 e를 선택함, Gcd(e, (p-1)(q-1)) = 1
4. 자연수 d를 선택함, (단 ed = 1 mod (p-1)(p-1))
5. 공개키 (n,e), 비밀키 (p,q,d)

타원 곡선 암호 (Elliptic Curve Cryptosystem)

• 1985년 N.Koblitz와 V.Miller가 타원곡선 상에 정의된 군(타원곡선군)에서의 이산대수 문제를 기반으로 제안
• RSA와 ElGamal 보다 키 사이즈가 작음
• 구현은 복잡하나 현재까지 알려진 다른 어떤 공개키 암호 시스템보다 효율적임 (속도가 빠름)
• 저장량, 대역폭, 계산복잡도가 비교적 적음
• 스마트 카드, 휴대통신기기, 핸드폰등 모바일 환경에 적합함
• 일반적인 타원곡선 이산대수문제를 해결하는 준지수알고리즘이 발견되지 않았음 (RSA 인수분해 문제, DSA 이산대수 문제)
• 암호기법은 타원곡선 군에서 ElGamal 암호기법처럼 구성됨

암호시스템을 설계할 때 고려해야할 사항이 아닌 것은

1. 암호시스템의 안전성은 키에만 의존해야 한다.
2. 암호시스템에 사용되는 알고리즘은 공개해야 한다.
3. 암호시스템을 손쉽게 사용해야 한다.
4. 암호화는 쉽게 복호화는 어렵게 계산되어야 한다.

정답 4, 암호 시스템 설계 시 암호화, 복호화 모두 효과적으로 이루어져야 한다.

다음 공개키 알고리즘 중에서 이산대수문제를 기반으로 설계된 것이 아닌 것은?

1. ElGamal
2. RSA
3. DSA
4. XTR

정답 2, Rabin과 RSA 암호는 인수분해의 어려움에 기반을 둔 공개키 암호이다.