Taessing

mod 연산, 필드, 항등원, 역원에 대해서 기본적으로 알고 있다고 생각하고 간다면


extended Euclid 알고리즘은 mod연산에 대한 finite filed에서 inverse를 구하는데 있어서 매우 유용한 알고리즘이다.
알고리즘은 보자.

우선 유클리드 알고리즘은 다음과 같다.

GCD(a,b)
{

Stream Cipher

LFSR sequences

LFSR(Linear feedback sequence register)
defined by a linearrecurrence. 선형적 반복에 의해 정의가 되었다.
implemented very easily,especially in hardware. 특히 하드웨어 쪽으로 구현이 매우 쉽다.
very fast (only the operating frequency is, not the throughput) 매우 빠르다.

이런 특징들이 있는 LFSR인데 어떻게 진행 되는지 한번 보도록 하자.

위 예제는 Xm+3 = Xm+1 XOR Xm 에 대해서 나타낸 것이다.
계속 반복적으로 진행되기 때문에 초기 상태가 필요하다. 위에서는 초기상태를 x1x2x3 = 010 으로 줬다.
Xm+3 = Xm+1 XOR Xm 의 식과 010의 초기 상태가 바로 sequence를 결정한다. 그림에서 보면 아주 간단하기 쉽게 알 수가 있다. 그리고 그값을 평문(plaintext)와 XOR연산을 하게 되면 바로 ciphertext가 나오게 되는 것이다.

그렇다면 sequence가 나오는 과정을 간단히 계산 해보도록 하자.
Xm+3 = Xm+1 XOR Xm 식을 이용하여
m=1, X4 = X2 + X1 = 1
m=2, X5 = X3 + X2 = 1
m=3, X6 = X4 + X3 = 1
m=4, X7 = X5 + X4 = 0
...........

정말 간단하다. 여기서 계속 더해 보면 한가지 특징을 발견 할 수 있는데 바로
키(초기상태)의 길이에 따라서 generate 되는 sequence의 길이 또한 결정이 된다는 것이다. 바로 아래와 같이 결정이 된다.

Key length = n 이면 sequence length = 2^n -1

위그림에서 key의 길이가 3인데 sequence가 7자리를 계속 반복한다는것을 알 수가 있다.


Attack

LFSR은 어떤식으로 위협을 받을 수 있을까??
불행이도 말이지
This encryption method succumbseasily to a known plaintext attack.
이 함호화 방법은 known plaintext attack에 굴복을 당한다.
This is because the constructionis linear.
왜냐하면 선형적(linear)하기 떄문이지.
If we know only a few consecutivebits of plaintext, along with the corresponding bits of ciphertext, an attack can determine the whole sequence.
우리가 ciphertext를 인지하고 있고 plaintext를 좀 알면 전체에 대해서 알 수 있다는 것이지.

그렇다면 Attack 과정을 한번 살펴 봅시다.

Ciphertext:10010100001110100100101010101011110010…

Plaintext : 11111111111…

Sequence: 01101011110…

다음과 같이 주어졌다고 했을때 어떻게 평문을 알 수 있을까 이상황에서 key length를 알 수가 없다 그러니까 key length를 어떤 임의의 값으로 지정해놓고 그것을 이용해서 방적식의 값을 구한다.

다시 말해서 length = 2, 3, 4 ... 일때를 예측해서.

Xn+length = C0Xn + C1n+1 + .... + Clength-1Xn+length-1

이용해서 방정식을 푼다는 것이다. 그렇게 어려운것은 아니니 패스 하자.

It is known that an attacker canrecover the linear recurrence if 2nconsecutive elements in the sequence is revealed. 2n의 연속되는 element가 sequence에 있다는게 드러난다면 attacker가 선형 반복을 알아내기는 쉽다.
This is much smaller than theperiod length of a sequence, i.e., 2n – 1. The problem is that therecurrence is linear,
이 문제는 반복이 선형적이라는 것이다.
and an attacker can make a matrix equation.
그리고 attacker가 행렬 방정식을 만들 수 있다.
So, we append some nonlinearelements.
그래서 우리는 이것을 해결하기 위해서 선형적이지 않은 것을 이용해야 된다.


Real Stream Cipher
실제 stream cipher에 대해서 알아보자.



사실 여기서는 별다른 그게 아니다. m = Majority(C1, C2, C3)는 바로 C1, C2, C3 중 많은 쪽이 Majority 가 된다.
EX1) EX2) 에서 잘 나와 있듯이 C1= 0, C2= 1, C3= 0 일떄는 0이 더 많으므로 C1, C3 쪽 즉 R1, R3가 clocking이 된다. clocking이란것이 위의 그림과 같이 XOR 연산을 하는것 같은 느낌인데.. 뭐 아님 말고



Block Cipher
일단 기본적인 개요에 대해 살펴 보자.

most symmetric block ciphers arebased on a Feistel Cipher Structure
대부분의 대칭되는 block cipher들은 Feistel Cipher Structure에 기반이다.
block ciphers look like anextremely large substitution
요것들은 극도로 큰 대입(치환) 같은 걸로 보인다.
would need table of 264 entries for a 64-bit block
64비트 블록을 위해서 2^64개의 엔트리의 테이블이 필요 할것이다.
instead create from smallerbuilding blocks
using idea of a product cipher
뭐 이런것들이 있다 본격적으로 한번 알아 보자.

기본 사항
우선 S-P networks 라고 있는데 이것은 substitution - permutation networks의 약자이네. 지금 할려는 block cipher의 basic이라고 할 수 있다. s-box p-box가 존재 한다고 한다. 아마 암호화를 하기 위한 어떤 아이템일 것이다. message의 confusion과 diffusion을 제공한다는데 이것이 무엇일까요? 알아보자.

Confusion 과 Diffusion
cipher needs to be completelyobscure statistical properties of original message
암호는 오리지널 메시지의 특징이 거의 없어야 한다.
a one-time pad does this
more practically Shannonsuggested combining elements to obtain
독해 생략

diffusion –dissipates statistical structure of plaintext over bulk of ciphertext
디퓨젼 - 암호문의 부피 크기에서 평문의 통계적 구조를 없앤다.
confusion –makes relationship between ciphertext and key as complex as possible
콘퓨젼 - 암호문과 키의 관계를 최대한 복잡하게 한다.

이렇게만 봐서는 잘모르겠다. 이제 본격적인 구조를 보자.

Feitel Cipher Structure
기본적인 것은 문장을 2 block으로 나눈다는 것이다.
암호화 할때는

평문을 (L0, R0)의 두개의 블록으로 나눈다.
round 1~n 까지
Li = R(i-1)
Ri = L(i-1) XOR f(Ri-1, Ki-1) f는 라운드 함수고 , k는 서브 키이다.
Ln, Rn이 암호문이 된다 정말 쉽구먼


복호화는 거꾸로 가면 된다.

Li-1 = Ri
Ri-1 = R(i-1) XOR f(Ri, Ki)
참 쉽죠잉.

이것을 그림으로 나타내면 다음과 같이


아주 쉽게 나타낼 수 있다.


DES
Data Encryption Standard
드디어 매우 매우 중요한게 나왔구나 DES이다.
이것은 세계에서 가장 널리 쓰이는 block cipher이다.
64비트 데이터를 56비트의 키를 이용해서 암 호화
그것의 보안성에 대해 논란이 일고 있긴한데. 뭐 우리는 일단 돌아가는것을 알아야 하니까 그게 더 중요하다.
아까 피스텔 사이퍼 디자인에서 간단히 봤듯이 일단 block cipher design에는 기본적인 구성 요소가 있다.
그것에 대해 살펴 본다면

number of rounds(라운드 수)
more is better, exhaustive searchbest attack

function f:(라운드한번에 펑션)
provides “confusion”, isnonlinear, avalanche
confusion을 주게 되고 선형적이지가 않다
key schedule
complex subkey creation, key avalanche
서브키 요런거지

이런것들을 어떻게 이용하는지는 다음과 같다.

우선 56bit의 key가 있고 64bit 평문 X가 있다면 암호화 함수 에 의해서 암호화가 되고 역시 반대로 복호화가 된다.

이것에 이용되는 기본적인 연산으로는
substitution 치환
trasposition  전치
linear operation(XOR)
정도가 있다.

그럼 이제 Encryption과 Decryption이 어떻게 이루어지는지 본격적으로 살펴 보자.

위그림으로는 뭐가 뭔지 잘 모르겠다 알 수 있는것이라고는 64비트의 평문이 들어가서 어떤 전치IP가 발생 하고 총 16라운드마다 키스케줄에 의해 나온 48비트 서브키가 관여한뒤 32비트 스왑이 발생하고 IP^-1(이게뭘까?)후에 암호문이 발생한다는 거다.

이건 각 라운드에서 일어나는 상황을 보여주는 것이다. 앞에서 배웠던 Feistel 암호화 방법에서 따온것과 같다.
L1 = R0
R1 = L0 + f(R0, K1) 이런식으로 되는거지. 이렇게 보니까 좀 반대이기는 하지만, 더 자세히 들여다 보자.



f가 대체 어떤 f 인지 여기서 잘 나와 있다. R1을 구할 때 식이 R1 = L0 + f(R0, K1) 이었지 않는가.
 1. 32비트 였단 R0 블록이 48비트로 확장되어 K1과 XOR 연산
 2. 이것을 8개로 나누니 하나에 6비트가 나오고
 3. S1~S8을 거쳐서 4개로 줄게 되는데????
 4. 그후 순열을 거쳐 32비트의 f(R0, K1)이 나온다는 것이다.

3번에서 S-box 거치는데  이것은 블록 사이퍼에서 기본적인 내용인 S-box, P-box아닌가 Substitution은 치환이란 뜻인데.. 6비트가 4비트로 치환이 되는가 보다. 그리고 순열 box인 P-box도 보인다. 이런 구조를 알고 전체적인 그림을 보자.


한결 이해가 쉽지 않은가? S-box P-box IP, IP^-1 의 기능은 이제 한번 살펴보자. 요게 더 핵심이다.
 
우선 IP!!
이거는 Initial Permutaion/Inverse Permutation의 약자이네. 순열을 이용해서 석는거 같다.
X= IP(M) , M= IP^-1(M)이다. 우선 두개의 테이블을 보자.
분홍색 주석으로 아주 잘 달려있다.
위의 예에서 보면 M7(M의 7번째 비트) -> (IP) -> x64
인데 7번째 비트이기때문에 IP 테이블에서 7이라는 숫자를 찾아야 한다. 그러면 다음과 같이 64번째 7이 있다는 것을 알 수 있고 이것은 X에 64째 비트가 바로 M의 7번째 비트가 된다는 것이다.
IP^-1은 이것의 물론 반대다. 이런 2개의 테이블을 만들어서 DES의 처음과 끝의 IP, IP^-1연산을 하는 것이다.
어쨋든 중요한 것은 IP라는 연산이 Permutation 테이블에 의해 비트가 섞여서 순서가 달라진다는 것을 알면 된다.
정말 이렇게 나타내면 빡시구나 비트가 64니까.


그리고 16개의 라운드동안 계속 적용되는 Feistel 시스템에서 펑션에서 R0가 32비트에서 48비트로 Expansion(확장) 되는것을 알 수가 있는데, 이것은 원래 있던 비트를 그대로 좀더 반복시켜서 쓰는것이다. 물론 테이블은 아까 IP와 같은 형식이다.
이런식으로 확장은 한다는 말이다 . 1, 2 열의 각2비트는  바로 이전 2비트를 따온것이다. 요거또한 그림으로 크게 나타내면
32비트를 48비트로 확장시키는거지만 순서를 뒤섞지는 않기 때문에 비교적 좀 단순하구먼.

요까지는 이해가 잘 되었는가? 32비트를 48로 확장시키는 건 매우 간단하다. 아까 라운드 함수에서 보면 그확장된 48비트를 다시 6비트 8개로 나누어서 S1~S8 까지 넣는것을 보았을 것이다. 각 S-box의 그림들을 한번 보도록 하자.

이렇게 8개의 S-box 가 있는데 대체 이게 뭔가??
아까 각라운드에서 Feistel 연산(?)으로 넘어갈때 R1 = L0 + f(R0,K1) 이렇게 되는것을 보았다. (기억을 위해서 L1 = R0가 그대로 내려온다.) f에서 R0가 48비트로 expansion이 되고 그값이  K1(서브키) 가 XOR 연산을 하고 거기서 6비트 8개로 나누어 진뒤에 S-box에 들어가서 6비트가 4비트로 줄고 그후 P-box에 들어가서 R1 32비트 값이 나오는 것이었다. 
 
우선 S-box로 6비트가 들어가면 일단 양끝의 2비트는 S-box의 행, 중간의 4비트는 열을 나타낸다. 양끝의 2비트이니 4개의 행이 나오고 중간의 4비트는 16(0~15)개의 열을 나타낸다. 각 행은 0~15의 수로 이루어져있고 이수들은 4비트로 변환되어서 S-box에서 나온다.
 위 그림의 예에서 011011이 나왔다면 양끝의 2비트는 01이므로 2번째 행, 중간의 1101는 10진수로 13이고 14번째 열을 나타낸다. 그래서 그대로 찾으면 9이고 이것은 1001이다. 그러니까 결론적으로 나오는 4비트는 1001이다. 그래서 각S-box를 거친 32비트가 나오는 것이다. 

그리고 P-box(permutaion box)는 다음과 같다. 그냥 앞에와 비슷하다.
그냥 32비트를 적어주는 것이다. 으 정말 DES 복잡하구나.

이제 Key Schedule에 대해 알아보자. 이것은 56비트 키에서 48비트 서브키를 생성하는데 중요한 요소이지 않을까 예상을 하면 서 넘어 간다.