동형2

HTTP(Hypertext Transfer Protocol)은 이름에서도 알 수 있듯이 text를 전송하는 프로토콜이다.

최근에는 text 뿐만 아니라 정말 다양한 정보들이 HTTP 프로토콜을 이용하여 주고 받아진다. 

또한 동시에 HTTP 위에서 민감한 정보를 전송하는 수요도 증가하기 시작했는데, 

보안이 요구되기 시작함에 따라 SSL(Secure Socket Layer)같은 프로토콜이 디자인되었다.

HTTPS는 이러한 보안 레이어 위에서 HTTP를 이용하는 구조로, 따라서 HTTP에 담긴 평문 데이터를 암호화해서 주고받을 수 있다.

1. HTTP Over TLS

RFC2818은 HTTP Over TLS란 이름으로 말 그대로 TLS 레이어 위에서 HTTP를 전송하는지에 대해 담고 있다.

여기서 중요한 하위 레이어인 TLS은 두 가지 역할을 수행한다.

1. End Host 간 안전한 데이터 전송 및 무결성 확인

2. 인증서를 통해 통신 상대가 신뢰할 수 있는지 확인

데이터를 암호화하여 전송하고, 받는 측에서는 데이터를 복호화하여 HMAC 알고리즘을 이용해 무결성을 검증한다.

또한 통신 시작 전 상대의 Certificate(보통 서버의 Certificate)를 받아 통신 상대가 신뢰가능한지 검증한다.

2. TLS

위에서 말했던 2가지 역할은 모두 TLS Handshake로 부터 시작된다.

이 Handshake를 통해 서버와 클라이언트는 Cipher Suite라는 구조체를 정의하게 되고,

이 구조체를 이용하여 통신에 사용할 암호화 관련 알고리즘을 정의한다.

또한 Handshake 과정을 통해 인증서를 전송하고, 암호화에 사용할 Symmetric 키를 정의한다.

이제 Handshake 과정을 자세히 알아보자.

클라이언트-서버 구조로 먼저 처음엔 Client가 TLS 세션을 시작하는 ClientHello 메시지를 보내며 시작된다.

1) ClientHello

이 단계에서는 클라이언트가 사용 가능한 Cipher Suite 리스트와, 기타 메타데이터들을 전송하게 된다.

메타데이터 중 Session ID는 서버가 클라이언트 정보를 식별해, 최근에 연결되었던 세션이면 서버와 클라이언트는 이후 과정을 생략하여 Handshake를 끝내고 기존 Cipher Suite와 비밀키를 이용해 연결을 시작한다.

2) ServerHello

ClientHello를 받은 서버는 ServerHello 메시지로 클라이언트에 응답하게 된다.

이 메시지에는 클라이언트가 보낸 Cipher Suite 리스트 중 하나가 포함되고, 이 Cipher Suite를 이용하여 암호화를 진행한다

여기서 서버는 Cipher Suite로 TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 을 선택했는데, 이는

1. 대칭키 교환 방식은 ECDHE( Elliptic-Curve 디피헬만)

2. 인증서 서명 방식 RSA

3. 대칭키 암호화 알고리즘 AES128_GCM (Galois/Counter Mode)

4. HMAC 알고리즘 SHA256

을 사용한다는 의미이다.

3) Certificate

서버는 ServerHello 이외에도 여러 메시지를 전송하게 되는데, 첫번째로 Certificate이다.

이 Certificate에는 Root CA의 인증서부터 서버의 인증서까지 Certificate chains을 전송하게 된다.

필요에 따라 서버가 클라이언트의 신원이 필요할 경우 CertificateRequest를 클라이언트에 전송해

클라이언트 또한 서버에게 Certificate 메시지를 전송할 수 있다.

이 과정을 통해서 상대방의 서명된 인증서를 받고 이를 검증함으로써 통신상대가 신뢰할 수 있는지 검증하게 된다.

다음 링크에서는 Certificate chain 과정에 대해 자세히 설명해주고 있다.

https://support.dnsimple.com/articles/what-is-ssl-certificate-chain

4) ServerKeyExchange

Diffie Hellman을 키 교환 알고리즘을 사용할 경우 KeyExchange 과정을 통해 암호화에 사용할 키를 생성하기 위한 데이터를 주고받는다.

서버는 ServerKeyExchange, 클라이언트는 ClientKeyExchange 메시지를 통해 데이터들을 주고받는다.

5) ServerHelloDone

ServerHello 부터 시작해 필요한 메시지들을 모두 전송하면 서버는 ServerHelloDone을 통해 보낼 메시지는 다 보냈다고 알린다.

6) ChangeCipherSpec

데이터 전송 및 검증에 필요한 모든 데이터를 교환하고 암호화에 사용할 비밀키를 생성했다면 서버와 클라이언트는 각각 ChangeCipherSpec 메시지를 통해 이제 다음부터 보낼 데이터는 암호화 해서 보내겠다고 알린다.

7) Finished

Handshake 과정을 종료하고 이젠 Application Data를 암호화하여 전송하고, 받는 측에서는 복호화하여 무결성을 검증한다.

3. 참고

https://luavis.me/server/tls-101

https://rsec.kr/?p=455

1. Domain ? 

웹브라우저를 통해 네이버를 접속하기 위해서 우리는 naver.com 이란 도메인을 이용한다. 하지만 웹 브라우저가 서버와 통신하기 위해서는 naver.com 가 아닌 서버의 IP 주소를 알아야 하는데 이 때 도메인을 IP 주소로 변환하는데 도움을 주는 것이 DNS 이다. 이렇게 도메인을 IP로 변환한 이후에 웹브라우저는 본격적으로 서버에 요청을 보내게 된다.

2. DNS 질의

DNS 정보를 알기 위해 클라이언트는 DNS 질의(DNS Query)를 서버에 보내게 된다. 

이 때 매번 DNS 서버에 질의를 할 수 없으므로 브라우저와 운영체제는 DNS 레코드 정보를 캐싱하게 된다. 만약 도메인 정보가 캐싱되어 있으면 그대로 변환하고, 없으면 이제 IP를 얻기 위한 DNS Query가 시작된다.

먼저 가장 먼저 로컬에 등록된 DNS Resolver로 쿼리를 보낸다. DNS Resolver는 클라이언트에게 적절한 응답을 할 책임이 있다. 

먼저 DNS Resolver는 클라이언트의 쿼리를 받고 자신의 캐시를 확인한다. 이 때 캐싱되어 있으면 응답하고,

아니면 루트 네임 서버에 쿼리한다. 루트 네임 서버는 전 세계에 13대 밖에 없다고 한다.

루트 네임 서버는 쿼리를 받고 여기서 TLD(Top-Level-Domain) 서버의 주소를 응답한다.  naver.com 의 경우 TLD는 com 으로, 루트 네임 서버는 .com DNS 서버의 주소를 응답해 준다.

이제 DNS Resolver는 TLD DNS 서버에 Query를 보내고, TLD DNS 서버도 마찬가지로 캐싱되어 있으면 응답하고, 그렇지 않다면 해당 도메인의 네임서버의 주소를 응답해주게 된다. 

마지막으로 해당 도메인의 네임서버는 DNS 레코드를 갖고 있으며, DNS Resolver -> Client 순으로 응답하게 된다.

DNS Query를 빨리 해결하기 위해서 서버들은 다양한 정보를 캐싱해둔다. 이 때 DNS 레코드의 TTL(Time-To-Live)란 캐싱된 정보가 유효한 시간으로 이 시간 동안은 캐싱을 유지한다.

References

https://www.cloudflare.com/ko-kr/learning/dns/what-is-dns/

입력 N이 들어오면 N보다 큰 소수이면서 & 팰린드롬인 가장 작은 수를 출력하는 문제이다.

풀이

간단한 문제다. 일단 전처리로 모든 가능한 소수 & 팰린드롬들을 구하면 [2,3,...,1003001] 이 되고 입력에 따라 N보다 큰 최초의 수를 출력하면 된다.

전화번호 n개에 대해 서로 접두사 관계인게 존재하는지 찾는 문제이다.

전화번호의 길이는 O(1)이고 완전탐색을 통해 찾으면 O(n^2)이 되기 떄문에 더 빠른 알고리즘을 찾아야 한다.

문제를 풀고 검색을 해보니 트라이라는 자료구조, 또 문자열 배열 전체를 정렬해서 인접 문자열끼리만 확인하는 간단한 방법이 있었다. 

나는 문제를 풀긴 풀었는데 뭔가 빙빙(?) 돌아갔다.

풀이

나는 일단 가능한 케이스를 모두 뒤져보는 완전탐색으로 풀었다.

1. 문자열을 길이별로 나눈 후 정렬한다. ( O(nlogn) 소요 )

ex ) LIST[2] 에는 길이 2인 문자열들을 정렬하여 저장

2.  1<=i<j<=10 인 순서쌍 (i,j) 에 대해 

LIST[i]에 있는 문자열들을 순회하며 LIST[i]의 원소가 LIST[j]의 원소 중 접두사가 가능한 게 있는지 찾는다.

이 때 LIST[i]의 크기는 N이므로 LIST[i]의 문자열 순회는 O(n) 이 소요되고,

LIST[j]는 정렬되어있는 상태이므로 LIST[i]의 원소를 LIST[j]에서 찾는것은 O(logn)이 소요된다. 

따라서 (i,j)에 대해 수행하는 연산은 총 O(nlogn)이 소요된다.

또한 가능한 순서쌍 (i,j)는 문자열의 길이가 제한되어있기 때문에 O(1)이기 때문에 ( 최대 가능한 경우의 수는 55이다. )

모든 원소를 순회하며 탐색하는데 O(nlogn)이 소요된다.

정렬에 O(nlogn), 탐색에 O(nlogn)이 소요되므로 총 O(nlogn)에 문제를 풀 수 있다.

이렇게 풀긴 풀었는데 뭔가 엄청 간단한 풀이들이 있고,

트라이 라는 자료구조도 알게 되었음. 끝 !

또 파이썬에서 input()으로 받으니 시간초과가 뜬다. 메모메모

문제 바로가기

풀이

문제를 두 단계로 나눌 수 있다.

1. 모든 빙산에 대해 바다와 맞닿아있는 면적 갯수 계산
2. 빙산 업데이트 후 2개 이상으로 분리되었는지 확인

를 빙산이 없어지거나 빙산이 분리될 때 까지 반복해주면 된다.

주의할 점은 모든 빙산에 대해 계산 후 한번에 업데이트를 해줘야 한다.

1. 모든 빙산에 대해 바다와 맞닿아있는 면적 갯수 계산

상하좌우에 0의 갯수만큼 나중에 빙산을 업데이트 해주면 된다.
그래프 내의 빙산을 담고 있는 node 배열에 대해 똑같은 크기를 갖는 diff 배열에 값을 저장해서 계산했다.

2. 빙산 업데이트 후 2개 이상으로 분리되었는지 확인

node를 순회하며 diff값을 이용해 update 해주면 된다.

이후 빙산들에 대해 1) 빙산이 여러개로 분리 2) 아예 사라지는 경우

에 대해 체크해줘야 한다.

1)의 경우 빙산 하나에서 BFS를 했을 때 모든 node에 대해 방문이 되어야 한다. 그렇지 않으면 현재까지 진행한 값(year)를 출력하고 종료한다.
2)는 빙산이 분리되지 않고 다 녹는 경우이다. 0을 출력하고 종료한다.

1)과 2) 둘다 만족하지 않으면 year를 증가시키고 1을 다시 시작하면 된다.

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

풀이

파이썬으로 처음 풀어본(아마?) 알고리즘 문제이다. 알고리즘 자체도 정말 오랜만에 푼다..

일단 풀이자체는 쉽다. 파이썬에 익숙하지 않다보니 함수 뒤적뒤적하느라 좀 시간이 걸렸다..

주어진 연산은 처음 원소를 삭제하는 D와 리스트를 뒤집는 R연산이 존재한다.

원본 배열에서 D연산과 R연산을 사용해 결과를 출력하면 된다.

이 때 결과는 원본배열의 부분배열이거나(R연산을 짝수번 수행) , 원본배열의 부분배열을 뒤집은 것이다.(R연산을 홀수번 수행)

필요한 변수는

1) 배열의 방향을 의미하는 DIR 플래그 ( 0 = 정방, 1 = 역방향 )

2) 부분배열의 시작과 끝을 저장하는 FR, TO 변수  ( 초기 : FR = 0, TO = n-1 )

연산을 순회하며

1) R연산시에는 DIR 플래그만 바꾸어준다.

2) D연산시에는 DIR이 0이면 앞에서부터 삭제(FR++) 한다. 반대로 DIR이 1이면 뒤에서부터 삭제(TO--) 한다.

이때 배열이 비어있음을 의미하는 것은 TO-FR == 1인 상태이다.  1이상이 되면 error를 출력한다. ( 빈 배열에 대해 D 연산 수행 )

연산을 모두 순회한 뒤 DIR 플래그를 보고 원본배열의 FR~TO 부분 배열을 그대로 출력하거나 거꾸로 출력하면 된다.

문제 아이디어 자체는 쉬웠지만 파이썬에 익숙하지 못해서 리스트 조작에 시간이 좀 걸렸다. 파이썬 공부하자!

Fragmentation

메모리에 프로세스를 적재할 때 메모리의 빈 공간이 작은 조각들로 나누어져 사용이 불가능한 상태를 말한다.

Fragmentation에는 두가지 종류 : 내부(internal)과 외부(External)이 존재한다.

1. Internal Fragmentation

• 프로세스가 필요한 메모리 크기보다 더 큰 메모리를 할당해주어 생기는 문제이다. 세그먼트 단위로 프로그램을 분리해서 메모리를 할당하여 해결할 수 있다.

1. External Fragmentation

• 프로세스들을 메모리 파티션에 계속 할당하고 해제하다 보면 중간 중간에 사용가능하지만 작은 메모리공간들이 존재한다. 이를 External Fragmetation이라 한다. first-fit 방식을 사용하여 메모리를 할당하면 N개의 블록 중 0.5N개의 블록이 Fragmentation으로 사용불가능해진다. 이를 50%-rule이라 한다. 페이징 기법을 사용하거나 메모리 공간을Compaction(압축) 하여 해결할 수 있다.