New World

1. 기본사항 X, Y : 집합 X에서 Y로의 함수 : ∀𝒙 ∈ 𝑿, ∃! 𝒚 ∈ 𝒀, 𝒙, 𝒚 ∈ 𝒇 를 만족하는 𝑿에서 𝒀로의 관계 [ 𝒇 ⊂ 𝑿 × 𝒀 ] X : f의 정의역, Y : f의 공역 y : x의 상 f(x), x : y의 역상 f(x) : f의 치역 상수함수 : 𝒇 ∶ 𝑿 → 𝒀, ∀𝒙 ∈ 𝑿, 𝒇 (𝒙) = 𝒄 (𝒄는 상수) 항등함수 : 𝒇 ∶ 𝑿 → 𝑿, ∀𝒙 ∈ 𝑿, 𝒇 (𝒙) = 𝒙 2. 전사함수, 단사함수, 역함수 전사함수 ∀𝒚 ∈ 𝒀, ∃𝒙 ∈ 𝑿, 𝒇 𝒙 = 𝒚 단사함수 ∀𝒙𝟏, ∀𝒙𝟐 ∈ 𝑿 𝒇 (𝒙𝟏) = 𝒇 (𝒙𝟐) ⇒ 𝒙𝟏 = 𝒙𝟐 𝒙𝟏 ≠ 𝒙𝟐 ⇒ 𝒇 (𝒙𝟏) ≠ 𝒇 (𝒙𝟐) 전단사함수 f 가 전사함수이자 단사함수 역함수 : 전단사함수인 경우 역관계의 함수 3. 함..

1. 기본사항 곱집합 : 모든 순서쌍들의 집합 𝑨 × 𝑩 = 𝒂, 𝒃 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩} 관계 : 𝒙는 𝒚와 𝑹의 관계 (𝒙, 𝒚) ∈ 𝑹 ⇒ ⇒ 𝒙𝑹𝒚로 표기 𝑿 = 𝒀이면 𝑹을 𝑿에서의 관계 2. 관계의 표현 화살표 도표 : 화살표를 그려 나타낸 관계 방향 그래프 ( G = (V, E) ) : 점과 선으로 이루어진 도형 | 방향 , 무향 , 일반 부울 행렬 3. 관계의 성질 반사적 대칭적 추이적 ∀𝒂 ∈ 𝑨 (𝒂, 𝒂) ∈ 𝑹 ∀𝒂, 𝒃 ∈ 𝑨 𝒂, 𝒃 ∈ 𝑹 ⇒ (𝒃, 𝒂) ∈ 𝑹 ∀𝒂, 𝒃, 𝒄 ∈ 𝑨 ((𝒂, 𝒃) ∈ 𝑹 ㅅ (𝒃, 𝒄) ∈ 𝑹) ⇒ (𝒂, 𝒄) ∈ 𝑹 자신의 집합으로 다시 돌아오는 관계 서로가 서로에게 관계 A -> B, B -> C => A -> C 관계 4. 관계의 종..

1. 기본사항 집합 표기법 - 원소 : 𝒂 ∈ 𝑺, 𝒃 ∉ 𝑺 - 집합 : 𝑺 = {1, 2, 3} / 𝑺 = { 𝒙｜𝟎 < 𝒙 < 𝟒 인 자연수} - 집합의 크기 : |𝑺| = 3 부분집합 : A의 모든 원소가 B의 원소라면 A는 B의 부분집합 (𝑨 ⊆ 𝑩 ⇔ ∀x 또는 𝐀 ⊂ 𝑩 ) 진부분집합 : 𝑨 ⊆ 𝑩, 𝑩 ⊆ 𝑨 ⇔ 𝑨 ⊆ 𝑩, 𝑨 ≠ 𝑩 상동 : 𝑨 = 𝑩 ⇔ 𝑨 ⊆ 𝑩 𝒂𝒏𝒅 𝑩 ⊆ 𝑨 서로소 : 서로 겹치는 원소가 없는 사이 분할 : 집합을 공집합이 아닌 부분집합들로 나눌 때 그 집합의 모든 원소들이 각각 나눠진 부분집합들 중 하나에만 포함될 경우 전체 집합을 그 집합의 분할이라고 함 멱집합 : 집합의 모든 부분집합들의 집합 ( P(A) 로 표기) 2. 집합연산 -합집합 : 전체 집합 |..

1. 기본사항 공리 : 명제들을 증명하기 위해 전제로 사용되는 가장 기본적인 가정, 별도의 증명 X 참으로 이용 증명 : 특정한 공리들을 가정, 제안된 명제가 참임을 입증 정리 : 공리로부터 증명된 명제 - 보조정리 : 정리를 증명하는 과정 중에 사용되는 증명된 명제 - 따름정리 : 정리로부터 쉽게 도출되는 부가적인 명제 2. 직접증명법 (연역법) 명제 변형 X 증명, 공리와 정의, 정리를 논리적으로 직접 연결하여 증명 ex) 파스칼 삼각형 3. 수학적 귀납법 자연수 n에 대한 명제의 성질을 증명 기본단계 => 귀납가정 => 귀납단계 기본단계 : n의 출발점에서 명제가 성립하는가 확인 귀납가정 : n = k 일 때, 명제가 성립한다고 가정 귀납단계 : n = k + 1 일 때도 명제가 성립함을 증명 4...

1. 명제 명제 : 참과 거짓을 구별할 수 있는 문장이나 수학적 식 명제 종류 : 합성명제, 조건명제, 쌍조건명제, 항진명제, 모순명제 2. 논리연산 2.1 논리연산 합성명제 : 하나 이상의 명제와 논리연산자 그리고 괄호로 이루어진 명제 논리합 : P v Q 논리곱 : P ㅅ Q 부정 : ~P 배타적 논리합 : XOR 사용, (P ㅅ~Q) v (~PㅅQ) 2.2 조건명제 - 조건의 역할을 수행하고 Q가 결론의 역할을 수행하는 경우 - 쌍조건명제 2.3 동치 - 두 명제 p와 q가 논리적으로 동등하면 논리적 동치 - 교환법칙, 결합법칙, 분배법칙, 항등법칙, 지배법칙, 부정법칙, 이중부적법칙, 멱등 법칙, 드모르간 법칙 흡수법칙, 함수법칙, 대우법칙 3. 술어논리 논리 : 명제 논리, 술어 논리

1. 해시함수 해시 함수의 개념 : 임의의 길이의 입력 데이터를 고정된 길이의 해시코드로 대응 약한 일방향성, 강한 일방향성, 충동 저항성 2. 전자서명 전자서명 : 메시지를 보낸 사람의 신원이 진짜임을 증명, 변조 X 개인키 이용, 해시함수 이용 1. 키 관리 공개키에서는 개인키는 감추고 공개키는 공개 2. 공개키 기반 구조의 개요 PKI : 공개키 암호에 기반을 둔 중요한 기반 기술의 집합체 인증서 발행, 갱신, 폐지 3. 공개키 기반 구조의 동작원리 4. 제공되는 서비스 기밀성 : 허락 X, 손님이나 객체가 내용을 알 수 없도록 무결성 : 전송 중에 변경되지 않았음을 보장 5. 공개키 기반 구조 모델 인증기관, 등록기관, 디렉터리, 사용자

1. 공개키 암호의 개념 암호화와 복호화에 두 개의 서로 다른 키를 사용 공개키 : 누구나 공개키를 이용할 수 있도록 공개 개인키 : 오직 자신만 이용하도록 아무에게도 공개X 2. 기반 문제 소인수분해 : RSA 알고리즘 이산대수 : ElGamal 알고리즘, DSA, KCDSA, Diffie-Hellman 키 교환 프로토콜 등 타원곡선 이산대수 : 타원곡선 상의 점과 타원곡선에서 정의되는 덧셈 연산을 이용, EC-DSA, EC-KCDSA 3. 공개키 암호 알고리즘들 RSA 알고리즘 : 소인수분해 문제 기반 ElGamal 알고리즘 : 유한체상에서의 이산대수 문제 기반 ECC : 타원곡선 군에서의 이산대수 문제 기반

1. 대칭키 암호의 개념 대칭키 암호 : 암호화와 복호화에 하나의 같은 비밀키를 사용 2. 블록 암호 평문을 고정된 크기의 블록으로 나눠 각 블록마다 암호화 과정을 수행하여 암호문을 얻는 방식 단순한 함수를 반복적으로 적용함으로 암호학적으로 강한 함수 라운드 함수 : 반복되는 함수 라운드 키 : 라운드 함수에 작용하는 키 키 스케줄 : 키를 입력하여 라운드 키를 발생 파이스텔 구조 -하나의 입력 블록을 분할하여 좌우 두개의 블록으로 구분하여 짝수 번의 라운드를 진행 - 라운드 함수와 관계없이 역변환 SPN 구조 - 하나의 입력 블록을 여러 개의 소블록으로 나눈 후 라운드를 진행 - 라운드 함수가 역변환 가능해야함 블록암호의 사용모드 전자코드북(ECB) : 독립적으로 암호화, 하나의 암호문에 오류가 발생해..