Niklas Jang

Niklas Jang

뜻이 있는 곳에 길이 있다.

[정보보호이론] Chapter 2 현대암호

4 minute read

단순 DES

  1. 교육용 알고리즘
    • 8비트 평문 블럭과 10비트 키를 사용

bc-7

  1. 기본함수
    • IP : Initial Permutation : 초기 순열
    • f_{k} 함수
    • transposition permutation : 전치
    • substitution : 치환
    • 키 입력에 의존 - SW : swap : 데이터의 두 절반을 상호 교환하는 함수 - f_{k}^{-1} : 초기 순열의 역인 순열 함수
  2. 알고리즘
    • IP^{-1} * f_{k2} * SW * f_{k1} * IP
  3. 암호화
    • Ciphertext = IP^{-1}(f_{k2}(SW()))

bc-8

Key Generation

첫 번째 그림의 Key Generation을 자세히 보면 아래와 같습니다.

bc-9

위 그림의 LS는 LeftShit를 의미합니다. LS-1과 LS-2는 각각 LeftShift 1bit LeftShift 2bit를 의미합니다. 화살표의 /표시는 몇 bit인지를 나타냅니다.

//left shift 1 bit
int arr[10];
for(int i=0; i<10; i++){
  cin>> arr[i];
}
int save = arr[0];
for(int i=1; i<5; i++){
  arr[i-1] = arr[i];
}
arr[5] = save;
save = arr[5];
for(int i=6; i<10; i++){
  arr[i-1] = arr[i];
}
arr[10] = save;

그리고 P는 permutation을 의미합니다. S-DES는 10비트 키를 사용해서 두 개의 8비트 sub key를 만들어냅니다.

bc-10

위 그림을 코드로 나타내면 아래와 같습니다.

//permutation 10 to 8
int intput[11]; // plain text
int output[11]; // output permutation
int result[11];

for(int i=1; i<=10; i++){
  cin>> input[i]; //1010000010
}

for(int i=1; i<=10; i++){
  cin>> output[i]; //1010000010
}
for(int i=1; i<=10; i++){
  result[i] = input[output[i]];
}
  1. LS-1 : 1비트 좌로 순환 이동 연산
    • 10000 -> 00001, 01100 -> 11000

bc-11

  1. 1 0 0 1 0 0 1 1 1 0을 P10을 통해서 0 0 0 1 1 0 1 1 1 0으로 바꿉니다.
  2. 0 0 0 1 1 0 1 1 1 0을 LF-1을 해서 0 0 1 1 0 1 1 1 0 0으로 바꿉니다.
  3. 0 0 1 1 0 1 1 1 0 0을 P8해서 1 1 1 1 1 0 0 0 으로 바꿉니다. 10개에서 8로 바꾸는 permutation은 사전에 정해진 숫자(key)로 생각하면 됩니다.
  4. 1 1 1 1 1 0 0 0을 LF-2gotj 1 1 0 0 0 1 0 0 1 1로 바꿉니다.
  5. 이를 다시 P8해서 1 0 0 0 0 0 1 1로 바꿉니다.

이렇게 Key1과 Key2가 만들어졌습니다.

Encryption

key generation 과정 다음은 Encryption입니다.

bc-12

Swap을 기준으로 위 아래의 과정은 입력되는 key가 K1과 K2라는 것만 다르고 동일합니다.

bc-13

암호화 과정은 입력과 출력이 모두 8비트입니다. 그리고 Permutation과 Inverse Permutation을 둘 다 진행하는 것은 아무것도 진행하지 않은 것과 같습니다.

IP의 출력부터 SW입력까지의 부분을 자세히 보겠습니다.

bc-14

  1. E/P(Expansion/Permutation)
  2. 4비트 입력을 일정한 순서에 따라서 8비트로 늘려줍니다.
  3. key generator가 생성한 Key 1을 더해줍니다.
  4. 이를 2개씩 묶어서 S0와 S1를 만듭니다.
  5. bc-15
  6. S-BOX에 따라서 8비트를 4비트로 줄입니다.
  7. bc-16
  8. P4 순열은 임의의 permutation으로 치환 역할을 합니다.
  9. 마지막으로 XOR 연산을 진행하고 SWap에 넣어줍니다.
  10. SWAP은 그림에 나와있듯, 좌우 4비트의 순서를 바꿉니다.
  11. fK2의 과정은 fk와 같고, 마지막에 IP^{-1}을 통해서 다시 한 번 permutation합니다.

위와 같은 알고리즘을 통해서 plain text는 cypertext로 출력됩니다. 외부의 공격자는 미지의 키를 알 수 없습니다. 만약 키가 10비트라면 키는 총 2^10 = 1024개를 갖습니다. cypertext는 plaintext와 key의 다항식 함수로서, 암호 알고리즘은 10개의 미지수를 갖는 8개의 비선형 방정식입니다. 알고리즘에서 순열과 합연산은 선형 사상이고, S-BOX를 통해서 비선형성을 도출해서 해독하기 어렵게 만듭니다.

여기까지만 알고 S0,S1를 구하기 위한 연산식, 방정식은 넘어가겠습니다.

DES와의 관계

단순 DES는 8비트 블록 단위로 2단계 처리를 합니다.

bc-17

위 그림에서 SW를 기준으로 Fk가 두 번 적용된다는 뜻입니다. 정리하자면 10비트 키에서 8비트 서브키를 생성하고, Fk함수는 4비트 연산을 진행합니다. 그리고 4행 4열로 구성된 2개의 S박스를 사용합니다.

  1. S-DES
    • 10비트Key -> 2개의 8비트 서브키
    • Fk 함수는 4비트 연산
    • 4행 4열로 구성된 2개의 S 박스 사용
  2. DES
    • 56비트Key -> 16개의 48비트 서브키
    • Fk 함수는 32비트 연산
    • 4행 16열로 구성된 8개의 S 박스 사용

블록 암호기법

  1. 평문 블록 전체를 가지고 같은 크기의 암호문 블록을 생성합니다.
  2. 전형적으로 64비트를 사용합니다.
  3. 한 번에 1비트 혹은 1바이트씩 암호화하는 stream 암호방식보다 더 넓은 범위에 사용합니다.
  4. 대부분 네트워크 암호는 블록 암호방식을 따릅니다.
  5. Feistel 블록 암호 기법의 구조에 따릅니다. (뒤에서 학습합니다.)

n비트 블록 처리

n비트 블록 처리는 n비트 평문을 받아서 n비트 암호문을 출력하는 것을 말합니다. 역으로 n비트 암호문 입력에 대해서 n비트 평문을 출력해줍니다. 총 2^n가지의 서로 다른 {plaint,cyper}쌍이 존재합니다.

  1. 00 -> 11
  2. 01 -> 10
  3. 10 -> 00
  4. 11 -> 01

bc-18

n이 작으면 취약점이 존재합니다. 크면 클수록 암호화 강도는 높아집니다. 작으면 작을수록 구현과 성능면에서 좋습니다. 적당한 크기가 좋습니다.

Feistel 암호방식

  • 치환과 순열을 번갈아 수행하는 암보 방식의 사용을 제안
  • 현재 사용하고 있는 모든 중요한 대칭 블록 암호의 기본구조
  • “매우 이상적인 암호문에 대한 모든 통계적인 정보가 사용된 키와 독릭적이어야 한다.”
  • 혼돈 함수와 학산 함수를 번갈아 수행
  • diffusion확산
    • 평문의 통계적인 구조가 암호문에 광범위하기 분산(평문과 암호문의 관계가 복잡)
    • 각 평문 숫자가 다수의 암호문 숫자 값에 영향
    • 문자메시지 M = m1 m2 m3을 통하여 하나의 암호 문자 Yn을 생성하는 방식. 예를 들어서 Yn = Sigma(M_{n+i} mod 26)
  • confusion혼돈
    • 암호문의 통계적 구조와 암호 키 값 사이의 관계를 복잡하게 만드는 것
    • 키를 이용한 암홈누 생성 방법이 복잡(키 추론이 어려움)
    • 복잡한 치환 알고리즘 사용으로 가능
  • SDES와 비교 :
    • 공통점 : 치환과 순열을 사용하는 반복적인 방법입니다.(자세한 구조는 생략합니다.)
    • 차이점 : SDES는 시작과 끝 단계에서 순열 함수(P와 P^{-1})로 시작되고 종료되지만 Feistel은 아닙니다.

DES

  • 64비트 블럭 암호 알고리즘
  • 56비드 키를 사용
    • 64비트 중 8비트는 parity check로 사용
  • 기본 구조
    • round 수 : 16
    • 복호화는 암호화의 역순
  • 회근에는 EDS 암호화를 세 개의 키로 세 번 반복함으로써 암호의 강도를 높인 triple-DES를 사용

요구조건

  1. It must provide a hight level of security
  2. It must be completely specified and easy to understand.
  3. The security provieded by the algorithm must not be based on t he secrecy of the algorithm.
  4. It must be all users and suppliers.
  5. It must be adaptable for use in diverse applications.
  6. It must be economical to implement in electronic devices and be efficient to use.
  7. It must be amenable to validation
  8. It must be exportable.

bc-19

  • 처리단계
    1. 초기 순열 단계 IP
    2. 16라운드 반복
    3. 좌우 교환단계
    4. 역초기순열 단계 IP^-1

좀 더 자세히 보면 다음과 같습니다.

bc-20

초록색 부분에서 Input을 64비트의 블록으로 분할하고 블록 알고리즘이 적용됩니다. 64비트 중 오른쪽 32비트를 48비트로 expansion하고 permuation까지 진행합니다.

bc-21

그리고 아래의 S-Box를 적용합니다.

bc-22

적용 후에는 다시 permutation으로 섞어줍니다.

Avalanche Effect

이처럼 DES는 치환과 순열의 조합입니다. 이는 강한 쇄도 효과Avalanche Effect를 갖습니다. PlainText 1bit가 달라져도 결과가 엄청 많이 바뀌는 것을 의미합니다. 만약 PlainText와 CyperText의 변화량이 비례한다면 이는 보안의 취약점이 될 것입니다.

3중 DES

  • 2개의 키를 사용
  • 암호화 : 암호화 -> 복호화 -> 암호화
  • 복호화 : 복호화 -> 암호화 -> 복호화
  • brute force 공격 : 2^112의 경우의 수

bc-23

You May Also Enjoy

less than 1 minute read