CS (21) 썸네일형 리스트형 [자료구조] Ⅰ-5,6,7. 알고리즘 성능 분석, 복잡도 5. 알고리즘 ● 알고리즘이란 문제를 풀기 위한 방식으로, 예시로는 10장의 카드가 무작위로 펼쳐져 있고 그 중 85를 찾기 위해 순서대로 찾기(Sequential Search - 순차탐색) , 반으로 나누어 중간과 먼저 비교하여 큰지 작은지를 통해 절반씩 탐색 범위를 줄여가며 찾기(Binary Search - 이진탐색), 가장 적은 수의 동전으로 거스름돈을 받기 위한 방법(그리디 알고리즘), 한붓 그리기 등이 있다. ● 알고리즘은 자료구조의 기본적 연산을 구현하기 위한 것으로, 같은 자료라고 해도 어떻게 저장, 표현되느냐에 따라 사용 가능한 알고리즘이 달라지며 알고리즘의 성능은 자료구조에 종속된다. ● 알고리즘의 표현 방식 ● 알고리즘의 조건 1) input: 외부에서 제공되는 자료 0개 이상 2) o.. [자료구조] Ⅰ-1,2,3,4. 용어, 자료구조 분류, 데이터 추상화 ** 시험: 용어 빈칸, 코드 빈칸, 구조 그리기 등의 형태 1. 용어 ● 원자데이터(Atomic data): single piece of information으로 구성되어 다른 의미있는 데이터로 분해 불가 ● 복합데이터(Composite data): 의미 있는 subfield로 분해 가능한 데이터 i.e. 전화번호 ● 자료형: 두 부분(data, operation)으로 구성. ● 자료구조: 원자데이터와 복합데이터를 defined relationships의 집합으로 묶어놓은 것으로, 데이터를 저장하는 일련의 규칙이다. 1) 데이터를 combine 하여 2) relating rules를 정의할 수 있는 structure로 맞출 수 있다면 자료 구조를 만들었다고 할 수 있다. 이러한 자료구조들은 nested.. [정보보호] Digital Signatures Digital Signature은 message authentication을 위한 보안 기술로, 메시지를 교환하는 2개의 parties를 third party로부터 보호해주지만, 메시지를 교환하는 당사자들 사이의 authentication은 보장하지 않는다. Digital signature은 1) signature의 author, date, time을 verify하고 2) 메시지 내용을 authenticate 하며 3) third party가 이를 검증하게 해 dispute resolution(분쟁 해결)을 할 수 있다. Attack and Forgeries Attacks 1) Key-only attack: signature이 attacked 당하는 A의 public key만 알고 있다. 2) Known.. [정보보호] Message Authentication Codes Message Authentication 1) 메시지의 integrity 보호 2) Originator의 identity validate (발신자의 신원 확인) 3) non-repudiation of origin(dispute resolution): 발신자가 메시지를 보냈다는 사실을 부인하지 못하도록 한다. 1) Hash function 2) Message Encryption: Encryption 자체가 authenticator로 사용될 수 있다. 3) Message Authentication Code(MAC) Symmetric Encryption for Message Authentication Symmetric Encryption은 동일한 키를 사용하여 메시지를 암호화, 복호화 하는 방식이다. Symm.. [정보보호] Cryptographic Hash Functions Hash Function 해시 함수는 arbitrary 메시지를 fixed size로 condense 하는 함수로, ( h = H(M) ) data integrity를 위해 사용되며 메시지에 변화가 생기면 이를 감지할 수 있다. 좋은 해시 함수란 1) 균등하게 distributed 되고 2) random 한 함수를 말하며, 이러한 해시 함수는 주로 public에 공개되어 있다. Cryptographic Hash Function 암호학적으로 해시 함수는 두 가지 중요한 특징을 갖는다. 1) One-way property: 이는 원본 데이터(preimage)에서 해시 값(image)을 찾기는 쉽지만, 주어진 해시 값에서 원래 데이터를 역으로 찾기는 어렵다는 것이다. 2) Collision-free prope.. [정보보호] PRNG(Pseudorandom Number Generator) Asymmetric Ciphers에 기반한 PRNG(Pseudorandom Number Generator) 비대칭 암호 알고리즘은 키 쌍(private key, public key)을 사용하여 데이터를 암호화 및 복호화한다. 이러한 알고리즘은 output이 키에 의존하기 때문에, 특정 input에 대해 동일한 output을 생성하지 않는다. 즉 암호화된 데이터는 외부에서 봤을 때 무작위로 보이게 된다. 이러한 무작위로 보이는 출력을 사용하여 난수를 생성하는 PRNG를 만들 수 있다. PRNGS란, deterministic 알고리즘을 사용해 pseudorandom number을 생성하는 프로그램이다. 이는 완전히 random 하지는 않지만, 많은 randomness tests를 통과할 수 있다. Asymm.. [정보보호] TLS(Transport Layer Secrecy)에서의 Forward Secrecy Forward Secrecy란 long-term private key가 향후에 노출(compromised) 되더라도 session key가 revealed 되지 않도록 하는 보안이다. TLS 1.2 이전의 보안은 1. RSA의 경우 서버가 private key를 protect 하는 동안까지만 secure하였고 forward secure 하지는 않았다. 2. DHE(Ephemeral DH), ECDHE(Elliptic Curve DH)의 경우에는 forward secure을 제공했다. 이는 임시로 생성된 Diffie - Hellman 키를 사용하다가, 이 키가 compromised 되면 해당 public key를 discard 하고 새로운 키를 생성하여 보안을 유지한다. TLS 1.3에서는 RSA-base.. [정보보호] Elliptic Curve Cryptography ECC는 타원 곡성의 특징을 기반으로 하는 public key crypto 기술(공개키, 개인키 두개 사용)로, 타원 곡선의 특성을 활용하여 작은 bit 크기의 키로도 효율적인 보안을 제공할 수 있다. 이는 비교적 최근 기술이므로 다른 암호화 기술에 비해 분석이 덜 되었지만 그럼에도 불구하고 효율성이 뛰어나다. 기본 개념 elliptic curve는 다음과 같은 식의 형태로, 위 식을 만족하는 모든 (x,y)가 집합 E(a,b)에 속한다. Finite Elliptic Curves Finite Elliptic Curves는 Zp(소수 p를 사용하여 정의된 정수 집합) 또는 GF(2^m) 상의 타원 곡선이다. ECC에서는 variable과 coefficient가 finite 한 값이어야 한다. 현재 fini.. 이전 1 2 3 다음
