현대 블록 암호

<Modern Block Ciphers>
- 현대 대칭키 블록 암호는
  - n비트 평문 블록을 암호화 하거나
  - n비트 암호문 블록을 복호화한다
- 암호화 혹은 복호화 알고리즘은 k비트 키를 사용한다


 ex) 만약 인코딩 과정에서 8비트 ASCII 코드가 사용되고 64비트 블록 암호를 이용하여 암호화하기를 원한다면,
  100개의 문자로 구성된 메시지는 몇 비트가 덧붙이기 되어야 하는가?

Solution)
100개의 문자를 8비트 ASCII 코드로 인코딩하면 800비트의 메시지가 된다
평문은 64로 나누어야만 한다
만약 |M|과 |Pad|를 각각 메시지 길이와 덧붙이기 길이라고 한다면
|M| + |Pad| = 0 mod 64 -> |Pad| = -800 mod 64 -> 32 mod 64



<Substitution or Transposition>
- 현대 블록 암호는 대치 암호 혹은 전치 암호로 동작하도록 설계되었다
- 현대 블록 암호는 전수조사 공격에 안전하기 위하여 대치암호로 설계되어야 한다


  ex) 64비트 블록 암호라 가정하자(n=64)
  만약 암호문에서 1의 개수가 10이라면, Eve가 중간에 가로챈 암호문으로부터 평문을 도출해내기 위해서
  필요한 시행착오(trial-and-error test)는 다음 두 가지 경우 각각 몇 번인가
 
  1) 암호가 대치암호로 설계된 경우
  - Eve는 평문의 1의 개수가 몇 개인지 알 수 없다 따라서 Eve는 암호문에 대응되는 평문을 찾기 위해서
    64비트 블록에 대하여 2^26번 시행착오(trial-and-error test)가 필요하다

  2) 암호가 전치암호로 설계된 경우
  - 전치 암호의 경우, 암호문의 1의 개수가 유지되기 때문에 Eve는 평문의 1이 개수가 정확히 10인 것을 알 수 있다
    따라서 64비트 블록에 대하여 Eve는 1의 개수가 10인 평문만을 전수조사하면 된다 -> 64!/(10!54!)



<전체 길이 키 암호(Full-Size Key Ciphers)>
- 입력 값을 출력 값으로 대응시키는 모든 가능한 경우를 키로 대응시킬 수 있을 만큼 충분히 긴 키 길이를 가지는 암호
- 전체 사이즈 키 대치 암호는 치환으로는 모델화 할 수 없다
- 하지만 입력 값을 디코딩하고 출력 값을 인코딩할 수 있다면 대치암호를 치환암호로 모델화 할 수 있다
- 즉, 전체 사이즈 키 n 비트 전치 암호 혹은 대치 블록 암호는 치환으로 모델화가 될 수 있지만, 그들의 키 사이즈는 서로 다르다
  - 전치암호의 경우 키 길이는 [log2n!] 비트
  - 대치암호의 경우 키 길이는 [log2(2^n)!] 비트
- 전체 길이의 키 암호의 부분 집합인 부분 키 암호가 부분근이라면 함수의 합성으로 정의된 군이 된다



<Block Ciphers as Permutation Groups>
- 전체 사이즈 키 전치 블록 암호(Full-Size Key Transposition Block Ciphers)
  - 각 비트의 값을 대체시키는 것이 아니라
    단지 비트의 위치를 재배열한다
  - 따라서 전체 길이 전치 블록의 암호는 n!개의 치환표로 구성된 집합으로 모델화할 수 있다
  - n!개의 각각의 치환표에 대하여 키를 대응시키기 위하여 n!개의 키가 필요하며, 효율적인 키 길이는 [log2 n!] 비트이다

  ex) 블록 길이가 3비트인 3비트 블록 전치 암호의 모델과 치환표의 집합을 보여라
  solution : 치환표의 집합은 3!=6의 원소를 가지며, 키 길이는 [log26]=3이다



<Components of a Modern Block Cipher>
- 일반적으로 현대 블록 암호는 '부분 키 대치 암호'이다
- 부분 키는 입력 값을 출력 값으로 대응시키는 가능한 모든 경우 중에서 '일부분의 대응'만을 정의한다



<P(permutation)-Boxes>
- P-박스(치환 박스)는 문자 단위로 암호화를 수행하였던 고전 전치 암호를 병렬적으로 수행한다
  - Straight P-box : 입력과 출력이 1:1 대응
  - Compression P-box : 입력값의 일부가 누락되고 출력에서는 입력의 일부에 대한 전치만 이루어진다
  - Expansion P-box : 입력보다 출력의 크기가 더 큰 P-box

- 확장 P-박스(Expansion P-Boxes)
  - 확장 P-박스는 n비트를 입력 받아 m 비트를 출력하는 P-박스로서 n>m을 만족한다

- P-Boxes : 역함수의 존재성(Invertibility)
  - 단순 P-박스는 역함수가 존재하지만 축소 P-박스와 확장 P-박스는 역함수가 존재하지 않는다



<S-Box>
- S-박스는 대치 암호의 축소모형으로 생각할 수 있다
- S-박스는 mxn 대치 단위이다
  단, m과 n이 같을 필요는 없다

- S-Boxes : 역함수의 존재성(Invertibility)
  - S-박스는 입력 값과 출력 값 사이의 관계가 테이블 혹은 수학적 관계로 정의되는 대치 암호
  - S-박스는 역함수가 존재할 수도 있고, 존재하지 않을 수도 있다
  - 역함수가 존재하는 S-박스는 입력 비트와 출력 비트의 개수가 동일하며 출력 비트 값은 모두 달라야 한다(1대1 대응)