암호학 정리

암호의 특성[Cryptographic Property]

Confidentiality

키를 모르는 제3자가 암호문을 올바르게 읽을 수 없음

Authentication

수신자에게 정당한 사용자/메시지임을 증명

상대방 인증, 메시지 인증

Integrity

전송도중 변화/수정되지 않았음을 증명

허락된 사용자만이 메시지 수정 가능

Non-repudiation

송/수신자가 메시지의 송/수신을 부인할 수 없음

암호 해독[Cryptanalysis]

Cryptanalytic attacks

암호문 단독 공격[Ciphertext-only attack]

암호화 키를 추측하는데 목적이 있음

암호문을 많이 수집하여 가능한한 많은 평문을 획득

기지 평문 공격[Known-plaintext attack]

공격자가 여러 암호문과 그에 대응하는 평문을 알고 있음

키 추측 또는 암호문을 복호하는 알고리즘 추측에 목적이 있음

선택 평문 공격[Chosen-plaintext attack]

평문을 선택하면 대응되는 암호문을 얻을 수 있는 상황에서 공격

선택 암호문 공격[Chosen-ciphertext attack]

암호문을 선택하면 대응되는 평문을 얻을 수 있는 상황에서 공격

암호 공격 성공

특정 암호문을 해독하여 평문 획득

암호문을 해동하는 알고리즘 회득/개발

암호화 키 획득[암호 공격의 최종 목표]

암호 알고리즘의 안정성[정보이론 내용 추가 필요]

얼마나 암호를 해독하기 어려운가?

공격에 어느 정도 견딜 수 있는지로 평가? 기준은?

암호를 공격하는데 필요한 비용, 시간, 필요 데이터량[암호문, 평문의 양]

Complexity

Data complexity

공격의 입력으로 필요한 데이터의 양

Processing complexity

공격 수행에 필요한 시간

Storage requirments

공격에 필요한 메모리의 양

Computational Security

사용 가능한 자원으로 알고리즘을 깰 수 있음

자원 : 시간, 데이터량, 계산량 등을 의미

복잡도이론의 관점에서의 안정성

**복잡도 이론

빅오 표기법 : 알고리즘의 복잡도가 얼마나 되는지를 알아내는 계산법 이다.

--> O(1), O(n) etc

복잡도의 분류

컴퓨터의 능력에 따라 결정됨

시간 복잡도 T, 공간 복잡도 S가 척도

T, S는 입력 크기 n의 함수로 나타냄

예 : 시간 복잡도가  〖4n〗^2+7n+12 인 알고리즘의 계산량적 복잡도 Ο(n^2)

알고리즘은 시간/공간 복잡도에 의해 분류

상수 :O(1)

선형 :O(n)

다항식 : Ο(n^m)  (단,m은 상수)

지수 : Ο(t^f(n) ) (단, t는 1보다 큰 정수, f(n)은 n의 다항식)

문제의 복잡도

튜링기계 : 인간과 비슷하게 사고 할 수있는 기계라고 정의

튜링기계의 2가지 종류

결정적 튜링머신

1 다음에 2

2 다음에 3 

--> 규칙적으로 사고하는 것이 가능한 기계

--> 하지만 무한루프나 오류가 발생하면 무한 루프 발생

--> 해결할 수 없는 머신

비결정 튜린머신

1 다음에 2

2 다음에 3

--> 사고를 하다가 오류, 무한루프를 스스로 발견

--> 문제를 해결하는 머신[상상속의 기계라고도 함.]

다항식 시간 알고리즘

현실적인 시간으로 해결 가능

지수 시간 알고리즘

유한 시간 내에서는 실행 불가능

복잡도의 분류

N < NP < NP-Complete < PSPACE < PSPACE-complete < EXPTIME

비결정적 튜링머신

사용 가능한 자원으로 알고리즘을 깰 수 있음

자원 : 시간, 데이터량, 계산량 등을 의미

복잡도이론의 관점에서의 안정성

ㄹ        

Unconditional Security

공격자가 아무리 많은 암호문을 가지더라도 평문을 회복하는데 필요한 정보가 부족

정보이론의 관점에서의 안정성 --> 정보이론 필기 확인 필요

Oerfect sercurity

대칭키 암호

암호화/복호 키가 동일한 암호

대칭키 암호 방식의 두가지 종류

Stream 암호

비트, 워드 단위로 평문을 암호화

1. one-time pad 암호

전사 공격에서 키공간을 모두 탐색하더라도 해독할 수 없는 암호

키 공간 전체를 순식간에 계산할 수 있는 무한대의 계산력을 갖는 컴퓨터로도 해독 불가능함

cuz 문자열이 복호화 되었다 하더라도, 그것이 바른 평문인지 아닌지 판정할 수 없음

But 지금은 사용되어 지지 않음

키의 길이 == 통신문의 길이 --> 비효율적임

키를 안전하게 보낼 수있는 방법이 존재 --> 평문을 안전하게 보낸다.

키를 실제 난수로 계속 생성해야 한다

통신 중 키에 약간의 손실 발생하면 복호화 X

키 재사용 불가능

Block 암호

평문을 특정 크기의 블록 단위로 나누어 암호화