proof of correctness of sorting (정렬에 대한 증명, 정렬이란 무엇인가)입력 : 정수 집합 {a[0], a[1], ... a[n-1]}sorting이 끝난 후 배열에 저장된 값들을 {b[0], b[1], ... b[n-1]}이라고 하자 (같은 배열이지만 구별하기 위함조건 1 : {a[0], a[1], ... a[n-1]} = {b[0], b[1], ... b[n-1]} 집합으로 같음조건 2 : b[0] Selection sort (선택 정렬) int sort(int a[], int n){ int i, j, m, t; for(i = 0; i a[j]) m = j; t = a[i]; a[i]=a[m]; a[m]=t; } return;}proof of..

Binary search (이진 탐색)#include int binary_search(int a[], int n, int x){ int l = 0; int r = n-1; while(l x) r = m-1; // 찾는 수가 더 작은 경우 else l = m+1; // 찾는 수가 더 큰 경우 } return -1; // ... (1)}int main(){ int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; printf("%d\n", binary_search(a, 10, 3)); return 0;}index가 있으면 index를 return 하고, 없으면 -1을 return l은 왼쪽 끝의 index, r은 오른쪽 끝의 인..

Array (배열)정의 : 연속된 주소, 동일한 타입장점 : n개 중 k번째 access가 상수 시간에 가능, Search가 빠름(경우에 따라 다를 수는 있음)단점 : 크기 변화 비용이 크다, Insert, Delete가 느릴 수 있다.사용 : 변화가 없거나 드문 자료에 사용함Linear Search (선형 검색)순서대로 전부 탐색하는 검색 방법 #include int linear_search(int a[], int n, int x){ for (int i = 0; i 찾지 못하면 -1을 return 하도록 약속함배열의 이름은 주소 : a[i] == *(a+i)O(n) Sorting이 되면 더 빨리 검색할 수 있음

수학적 귀납법수학적 귀납법의 기본형Base : P(1)이 참이다Step : P(n-1) → P(n)이 참이다 ( p→ q 형태 )Result : P(n)은 모든 자연수에 대해 참이다우리가 증명하려는 것은 전체가 참이라는 것을 보이는 것이다. 하나하나가 참인지 거짓인지는 알지 못해도 됨.그 이유는, P(n-1)이 거짓일 때는 무조건 T가 되기 때문에 P(n-1)이 참일때 전체가 참이면 무조건 P(n)은 참이다. * P : 무엇인지 모르는 것 > 이름, 명제 등* n : 자연수 ex) Prove that \(1 + 2 + 3 ... + n =  \frac{n(n+1)}{2}\) for all \(n \epsilon \mathbb{N}\)(1) Base : \(P(1) = 1 = \frac{1 \times 2..

PCB (Process Control Blocks)프로세스의 정보를 저장하고 있는 데이터 블럭 Linux Kernel > /include/linux/sched.h struct task_struct {...}> PCB 역할을 해주는 구조체 volatile long state;unsigned int __state;unsigned int saved_state;> 현재 프로세스의 상태를 나타내줌 running → TASK_RUNNINGready → TASK_RUNNING (X)bocked → TASK_INTERRUPIBLE 등 (blocked의 종류에 따라 달라짐)void *stack;> Pointer to the kernel-mode stack프로세스 마다 스택이 존재함 → user-mode stack / ..

문제 : https://dreamhack.io/wargame/challenges/131 Textbook-RSADescription 드림이가 비밀 플래그를 가지고 있는 RSA 서버를 운영하고 있습니다. 서버를 공격해 플래그를 탈취해주세요! 플래그 형식은 DH{...} 입니다. References https://dreamhack.io/lecture/courses/76dreamhack.ioCode AnalysisRSA : RSA 암호화 및 복호화 처리class RSA(object): def __init__(self): self.p = getStrongPrime(512) self.q = getStrongPrime(512) self.N = self.p * self.q ..

Public Key (공개키) : 모든 사용자에게 공개되며 평문을 암호화할 때 사용함Private Key (개인키) : 타인에게 노출되어서는 안되며, 공개키로 암호화된 암호문을 복호화 할 때 사용함오일러 정리n과 서로소인 양의 정수 m이 다음의 식을 성립함$$ m^{\varphi(n)} ≡ 1$$ \(\varphi(n)\) : Euler's phi function 오일러 파이 함수 > n이하의 양의 정수 중에서 n과 서로소인 수의 개수 * 소수 p의 경우 \(\varphi(p) = p-1\) RSA암호키 생성 서로 다른 소수 p, q를 선택 > 1024비트 이상에서 비트 길이가 같은 수로 생성함\(n = p \times q\)\(\varphi(n) = p \times q -p -q +q = (p-1)(q..

문제 : https://dreamhack.io/wargame/challenges/120 Textbook-DHDescription Alice와 Bob의 통신을 중간자 드림이가 엿보고 있습니다. 둘의 키교환 과정을 공격해 플래그를 획득해주세요 ! 플래그 형식은 DH{...} 입니다. References https://dreamhack.io/lecture/courses/75dreamhack.ioCode Analysis라이브러리from Crypto.Util.number import getPrime #소수 반환from Crypto.Util.Padding import pad, unpad #패딩from Crypto.Cipher import AES # AESimport hashlib #해시 함수 제공import ran..

대칭키 암호 > 수신자와 송신자가 같은 키를 공유하고 있다는 전제가 필요함 → Key Exchange (키 교환)이 이루어져야함 → 공개된 채널(ex. 네트워크)를 통해 키를 교환해도 외부인은 키를 알 수 없게 하는 공개 키 교환 알고리즘을 고안 Diffie-Hellman key exchange protocol 수학적 원리 ▶ square and multiply algorithm : 임의의 합동 항등식에 대해 양변에 동일한 값을 곱해도 식은 성립함 ▶ Fermat's Little Theorem (페르마 소정리) : 소수 \(p\)와 정수 \(a\)에 대해 \(a^{p-1} ≡ 1 (mod \ p)\)가 성립함 ▶ Discrete Logarithm Problem (이산 로그 문제) : 자연수 \(a, m\..

다양한 크기의 데이터를 처리할 수 있도록 고안된 블록 암호의 사용 방법Padding (패딩)평문에 데이터를 붙여서 평문의 크기가 블록 크기의 배수가 되도록 만드는 과정 Bit Padding (비트 패딩)마지막 블록에서 평문이 채우지 못하는 비트 중 최상위 비트를 1로 설정하고 나머지는 모두 0으로 채우는 패딩 기법수신자 : 평문의 마지막 비트부터 처음으로 값이 1인 비트가 나올때까지를 패딩으로 인식할 수 있음 > 제거하여 평문 복구 * 평문의 크기가블록 크기의 배수인 경우 : 수신자의 메세지 일부를 패딩으로 오인하게 되는 문제 발생→ 패딩으로 한 블록을 추가함 ex) 0101 1010 1000 0000Byte Padding (바이트 패딩) : ANSI X.923블록의 남는 바이트를 일반적으로 0으로 채우..