컴퓨터보안#3

LeeMir, 10 March 2021

고전암호화

관용암호 모델
  • 평문 : 이해하기 쉬운 일반 메시지
  • 암호문 : 이해할 수 없도록 변형된 메시지
  • 암호화 과정 : 특정한 방식의 알고리즘에 비밀 유지되는 키를 적용하여 알기 쉬운 평문을 알 수 없는 암호문으로 변환
    • 동일한 메시지도 키에 따라 알고리즘의 변환 결과가 다르게 출현
  • 관용암호방식의 안정성 특징
    • 암호 알고리즘은 키 없이 암호문 자체만으로 해독 불가하도록 강도 유지
    • 안전성은 알고리즘 자체의 비밀성이 아니라 키의 비밀성에 의존
    • 암호문과 암복호 알고리즘이 알려져도 메시지 해독은 불가
    • 키만을 비밀 유지 필요
암호화 / 복호화
  • 평문 => 암호알고리즘(암호화) => 암호문 => 복호알고리즘(복호화) => 평문
  • 공개키 알고리즘
    • 암호할 때 사용하는 키와 복호할 때 사용하는 키가 다른 알고리즘
암호의 역사
  • 수동 암호시대(고대 ~ 1920)
    • 치환, 전치
  • 기계 암호시대(1920 ~ 1950)
    • 복잡한 기계 이용(에니그마 등)
  • 컴퓨터 암호시대 : 현대 암호시대 (1950 ~ 현재)
    • 컴퓨터 이용
치환 기법
  • 시이저(Caesar, 카이사르) 치환법 : 최초의 치환 암호, 쥴리어스 시이저에 의해 개발
    • 예제(Key : 3)
      • 평문 : meet me after the toga party
      • 암호문 : PHHW PH DIWHU WKH WRJD SDUWD
    • 암호화(문자 p를 암호화)
      • s = E(p) = (p+3) mod (26)
      • 일반화 : C = E(p) = (p+k) mod (26)
    • 복호화
      • p = D(s) = (s-3) mod (26)
      • 일반화 : p = D(C) = (C-k) mod (26)
    • 단점
      • 가능한 키가 25개 뿐
        • Brute-force attack이 가능
  • 단일문자 치환 암호법
    • 각 문자에 임의의 26자 치환
      • 카이사르 암호의 키 공간을 급격히 증가
        • 카이사르 암호 : 25
        • 단일 치환 암호법 : 26!
    • 단점
      • 출현 빈도수를 이용해 평문 유추 가능
        • 영어 문장에는 t, e, a 등이 많이 나타남, 암호문에서도 그에 상응하는 문자가 같은 빈도로 나타남
    • 과제?
      • https://math.bab2min.pe.kr/substt
      • F : e (가장 빈도수 높음)
      • PB : th(가장 빈도수 높음)
      • Q : a (두번째로 빈도수 높음, th?t에 해당)
      • E : w (?hat을 검색)
      • H : r (whetheH에서 유추)
      • The Walrus and the Carpenter(바다코끼리와 목수)라는 시의 시구
  • 다중 단일문자 치환 암호 : 분석가에 의한 빈도분석을 어렵게 만들기 위하여 암호문에 나타나는 문자들의 빈도를 거의 균등하게 만드는 암호
    • 다중 대체암호에서는 다중 대체를 통해 문자들의 발생빈도를 균등하게 분산
    • 대부분의 다중 대체암호는 주기(period)를 가진 대체암호
    • Vigenere Cipher
      • Key 문자열을 만들어 카이사르 암호처럼 평문에 Key를 더해 암호문을 만듦
        • Key는 한 단어가 평문의 길이만큼 반복되는 형식
      • 한 문자가 다른 문자로 치환될 수 있어 암호문에 나타나는 문자들의 발생빈도를 균등하게 분산
      • 그러나 적용된 주기를 유추해낼 수 있다면 동일한 키가 적용된 암호문들을 선별해 집합을 구성한 다음에 그 집합별로 빈도분석을 수행하면 암호공격이 성공
    • 키워드의 변형사용
      • 키워드와 평문을 연결하여 키로 사용(Key 문자열이 평문 문자열과 길이가 같거나 더 긺)
      • Key와 평문이 동일한 문자 빈도분포를 갖기 때문에 통계적 기법을 해독에 사용 가능
  • 다중문자 치환 기법
    • 한번에 2자 이상씩 암호화
    • Playfair 알고리즘 : 5x5 행렬에 기초
      • Keyword를 5x5에 채워넣은 후, A~Z까지 채워넣되 I와 J는 한 칸에 집어넣는다.
        • 이 때, 우하향으로 채워넣어야하고, A~Z중 Keyword에 포함되는 문자는 다시 적지 않는다.
      • 암호화
        • 반복되는 평문은 X와 같은 채움문자로 분리(balloon = ba lx lo on)
        • 같은 행에 두문자가 있을 경우 우측에 있는 문자와 치환
        • 같은 열에 두문자가 있을 경우 바로 밑에 문자와 치환
        • 그 외에 평문자쌍은 대각선에 위치한 문자와 치환
      • 2중자의 빈도수 분석은 어려움
      • 1,2차 대전중 미국, 영국 육군에서 사용
      • 수백자의 암호문자로 구조를 알 수 있음
      • 평문보다 평평한 분포를 가지지만, 여전히 해용한 구조를 가짐
    • Hill Cipher
      • 1929년 미국 수학교수 Laster Hill이 제안
      • 3x3행렬(Key)과 3x1행렬(평문) 곱으로 암호문 생성
      • 복호화는 역행렬을 만들어 계산
  • 일회용 암호
    • 통계적 해독을 방지하기 위해 키워드를 평문과 같은 길이로 사용
    • 문자 대신 문자를 2진 자료로 작동
      • Ci = pi XOR ki
    • 복호문은 XOR의 속성상 같은 비트 방식으로 연산
      • pi = Ci XOR ki
    • 이 방식의 본체는 키 생성 방법인데, 워낙 난해하기 때문에 실질적으로 사용하기 어려움