Taessing

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비트 서브키를 생성하는데 중요한 요소이지 않을까 예상을 하면 서 넘어 간다.

http://plucky.tistory.com/trackback/3

foxtab -> 3D 탭 전환하는 기능
mouseless browsing -> 마우스 없이 사용가능 
foxmark -> 즐겨찾기 동기화
firebug, web developer -> 디버깅 툴

setjmp 와 longjmp를 이용한 간단한 프로그램을 작성하라.

#include<setjmp.h>

int setjmp(jmp_buf env);
void longjum(jmp_buf env, int val);

setjmp
- setjmp를 호춯한 함수의 스택 환경과 레지스터 환경을 env에 저장
- 직접 호출된 경우에 0을, longjmp에 의해 호출된 경우에는 0 이외의 지정된 값을 리턴한다.

longjmp
- 현재의 스택 프레임을 setjmp에 의해 저장된 스택 환경과 레지스터 환경으로 복원, setjmp가 지정한 위치로 제어가 이동
- val 값은 setjmp의 리턴값, 여러개의 longjmp 함수도 함꼐 사용 가능
- env 변수는 전역 변수로 선언 한다.

위 두함수는 비지역적 분기로서 지역 분기 goto문과는 달리 스택 정보를 복원할 수 있어야 한다. 위 두함수는 비지역 분기로 서 중첩된 함수 호출에서의 인터럽트나 에러를 처리하는데 효과적이다.

비지역적 분기와 변수값의 변화

변수값의 변화
- 메모리에 저장된 변수들은 longjmp 호출시의 값을 유지
- CPU나 레지스터에 저장된 변수들은 setjmp 설정시의 값으로 복원

최적화 컴파일
- 최적화하지 않는 경우에는 레지스터 변수 이외의 변수는 메모리에 할당한다.
- 최적화 하는 경우에는 휘발성 변수만 메모리에 할당하고 나머지는 레지스터에 할당한다. 단, 레지스터에 저장된 값을 보장하지는 않는다.


예제 프로그램

#include<stdio.h>
#include<setjmp.h>

static void f1(int, int, int);
static void f2(void);

static jmp_buf jmpbuffer; //jump 버퍼 설정

int main(void)
{
    int count; //count 변수는 일반 변수
    register int val; //val 변수는 레지스터
    volatile int sum; //sum 변수는 휘발성
   
    count=2; val=3; sum=4;

    if(setjmp(jmpbuffer) ! = 0)//setjmp결과가 0이 아니면 longjmp에 의해서 호출된 경우
    {
        //setjmp는 jmpbuffer에 현재 스택환경과 레지스터를 저장한다.(그러니까 복귀할때 여기로 복귀가 된다는 말!)
        //만약 longjmp가 호출 되어서 jmpbuffer에 저장되 어있는 스택환경과 레지스터 환경이 복원 되면
        //이 경우 아래 문장이 실행이 된다.
        printf("롱점프를 하면 : count = %d, val = %d, sum = %d", count, val, sum);
        exit(0);   
    }
   
    count = 97; val = 98; sum = 99;
   
    f1(count, val, sum);
}

static void f1(int i, int j , int k)
{
    printf("f1() : count = %d, val = %d, sum = %d", i, j, k);
    f2();
}

static void f2(void)
{
    longjmp(jmpbuffer, 1);
    //longjmp 의 두번째 파라미터는 setjmp의
}


자세한 설명은 주석으로 처리하였고 실행 결과 컴파일 옵션을 넣을때와 아닐때가 다른것을 알 수있다.
위 그림은 컴파일 옵션을 넣지 않았을 때인데 이경우 모두 뒤의 결과를 따르게 된다.


위 그림은 컴파일 옵션에 -O를 넣었을때는 휘발성 변수 뺴고는 다 레지스터 영역에 저장하여 longjmp시 setjmp가 호출 되었던 영역으로 돌아가게 될때 레지스터 영역에 있는 변수가 복귀가 된다. count와 val은 레지스터 영역에 저장 sum은 메모리 영역이므로 count와 val은 2, 3으로 복귀가 되지만 sum은 99 그래로이다.

1. 인공지능 공부 -> 즉 포스팅을 통해 더 확고히.

2. 음악 공부 -> 다음주부터 당장 시작

3. 영어 -> 이건 계속하는 습관을 들여야 한다.

4. 사진 찍기 -> 할 수 있으면 될 수 있으면 하는 쪽으로

5. 블로그 열심히 활성화 시키기 -> 이왕 티스토리로 왔는데.

6. 졸업 과제 생각 -> 뭐 연구실에서 시키겠지?

7. 일단 할려고 하는건 뭐든지 꾸준히 매일 하는게 제일 중요하다.

이 포스팅은 부산대학교 정보컴퓨터 공학부의 인공지능 수업을 들은 학생이 수업을 듣고 문서를 참고해 만든 포스팅으로 절대 이 내용이 정답이라고 보장 할 수는 없다.
================================================================================================================
Searching 을 이용해서 문제를 해결 한다는 것이다. 인공지능이란 과목에서 이것이 뜻하는 바가 무엇인가??

일단, 컴퓨터 과목에서 많이 나오는 State들 즉 시작 state(initial state)와 state들 사이의 이동을 전이(이동) 통해서 목표한(Goal)State를 찾아가는 듯한 느낌이다.

Problem solving agent
요것은 어떤 문제를 해결하는 데 있어서 그과정을 formalize(형식화) , operationalize(조작가능화) 하는것인데.
Define 할것이 있다.

search 알고리즘의 input 들은
◎ initial state -> state space
◎ operator (succesor functions) -> 요놈 역시 state space
◎ goal test
◎ path cost functions : 요건 path에서 개별적인 action에 대한 cost의 총합이라고 볼 수 있다.

위와 같고
Solution 이란 단어가 있는데 이건 initial state 에서 goal state 까지의 path를 말하는 것이고 optimal solution은 코스트가 가장 적게드는 solution이다.
쉽게 말해 서울에서 부산까지 가는 길이 엄청나게 많은데 그중에서 거리가 가장 짤은 길이 바로 optimal solution이 되는 것이다. 여기서 cost는 거리가 될수도 있고 돈이 될 수 있겠지. 그것은 상황마다 달라진다.

슬라이드에는 8-puzzle, 8-queens problem 이 나와 있고 어떤 문제들인지 설명과 각각의 agent에 대해설명이 자세히 나와 있다. 하지만 별로 어려운 것은 아니고 agent를 더 좋게 형식화 하면 훨씬 적은 stae space만 사용한다는 이런 예가 나와 있다. 그러므로 8-puzzle, 8-queens problem에 대해 간략히 설명 하면

8-puzzle은
요런 initial(start) state를 가지고 어떤 숫자가 있는 사각형을 빈칸으로 요리조리 (up, down, right, left)로 옮기면서(요게 successor function) goal state로 가면 된다.


8-queenz는
체스에서 퀸은 대각선으로만 공격할 수 있다는데 서로 공격하지 않게 배치해보자 이런 문제 이다. 앞으로도 많이 나와서 간략히 언급을 하였다.

----------------------------------------------------------------------------------------------------------------
Searching for Solution

state space를 통한 서치... 이게 뭔가??
일단 내용을 보게 되면

● 서치 트리라는 게 만들어 진다. 이것은 initial state 와 successor function에 의해 발생 된다는데..

● 서치 트리라는게 요거는 자료구조에서 배웟던것 처럼 노드가 있는데 이것은 보통 initial state 이다 당연한 거겠지.

● 현재 state에 operator를 적용하므로서 새로운 set of state가 발생한다. (한마디로 확장이 된다는 것이다.)

● 어떤것을 먼저 확장 시킬 것인가는 => Search Strategy 요것에 의해

요런것들이 있는데 쉽게 그림으로 나타내면 아까 8 puzzle problem에서 서치 트리를 한번 나타내 보자.
그림으로 나타내니 훨씬 쉽다. initial state 에서 successor function에 의해 expand가 잘되어 가는것이 보여진다.
그렇다면 이제 본격적으로 알아보자. 다음그림을 보자.

위 그림은 길을 찾아가는 문제를 그림으로 나타낸 것이다. 여기서 처음 시작점(initial state)를 Arad라고 하자. 그 후
어떤 곳을 찾아가기 위해서 searching tree를 만든다고 하면 다음 그림과 같이 나타낼 수 있을 것이다.

이 그림은 처음 봐서는 무슨 뜻인지 잘 이해가 안갈 텐데 일단 Arad가 root node(initial state), 나머지 state들이 계속 나타난 다는것을 알 수 있는데 위의 지도 그래프에서 보면 Arad의 인접한 것이 Sibiu , Timisoara, Zerind 이렇게 있다는것을 알 수 있다. 이것을 (b)에 잘나와 있듯이 Arad에서 expand를 한것이라고 하는데 set of state가 나온거라고 할 수 있다. 거기서 어떤것을 선택해서 계속 반복해서 원하는 목적지에 달하면 solution을 찾는 것이라 할 수 있는데~

여기서 Arad밖에 없을 때는 당연히 Arad에서 expand를 하는것이겠지만 (b)에서 3가지 state에서는 어쩔것인가? 어디서 expand 하는 가를 선택하는 것이 바로 searching strategy 이다.

그리고 (c)에서 보면 Arad가 또 나오는데 요러면 Arad를 선택해버리면 무한 루프에 빠져 버릴 수 도 있지 않겠는가? 한마디로 이것은 자신의 Ancestor(선조)를 expand 하지 않는다라고 생각하면 편할 것이다.

위의 장황한 말을 용어로 정리 해보자

Componets of a search node -> 트리의 구성 요소 정도?
◆ State(node)

◆ Parent node

◆ Action(Operator)

◆ Depth(깊이 이것은 위그림에서는 길에 따른 노드의 갯수 정도가 될것이다.)

◆ Path cost

Fringe -> 요거 매우 중요하다.
한마디로 앞으로 expand 될 노드이다. 요건 일반적으로 queue로 구현이 된다.

 위의 말이 무엇인지 모르겠다면 그림으로 한방에!

한번에 이해가 가지 않는가?
그러면 이제 앞으로의 알고리즘은 문제에 의해서 한번 풀어 볼 수 있도록 하자.

~받아가세요