이론113 순서가 있는 정렬 : 위상 정렬 (Topological sorting) 들어가며 오늘은 특정한 몇몇 요소끼리의 순서가 정해진 상황에서 사용할 수 있는 정렬 방법인 위상 정렬(Topological sorting)에 대하여 알아보겠습니다. 알고리즘 수학에서 위상(topology)이란 연속적인 힘에 의한 변형에도 유지되는 기하학적인 속성을 의미합니다. 이렇게만 말하면 와닿지 않으니 갓 나온 가래떡을 하나 떠올려봅시다. 길쭉한 원기둥 모양을 한 가래떡에 찢어지지 않을 정도로 적당한 힘을 가하면 원래 모양보다 늘어나거나 구부러집니다. 그러나 가래떡의 모양이 변했다고 해서 원래 가지고 있던 속성들이 모두 변하는 것은 아닙니다. 아래 그림을 한 번 보겠습니다. 예를 들어, 이렇게 가래떡을 구성하는 분자들끼리 연결된 상태들은 변하지 않죠. 여전히 서로를 꽉 붙잡고 있습니다. 이렇게 서로간.. 2023. 7. 9. 암호 키 (Encryption Key) 지금까지 올라온 각종 네트워크 이론 포스트들을 보면 공통적으로 등장했던 단어가 있습니다. 바로 키입니다. 이번 글에서는 포스트마다 빠지지 않고 등장했던 중요한 개념인 키에 대해서 조금 더 자세히 알아보겠습니다. 키 (key) 우리가 흔히 키라고 부르는 암호 키(Encryption Key)는 암/복호화 과정에 함께 사용되는 일련의 값을 의미합니다. 대개 사람이 직접 연산하기 어려울 정도로 대단히 큰 수이며, 키의 길이가 길어지면 길어질수록 암호 알고리즘의 보안 강도(안전성이 유지되는 기간) 또한 높아지게 됩니다. 세상에 다양한 암호 알고리즘이 있듯, 키 또한 어떤 암호 알고리즘에 사용되는지에 따라 다양한 종류의 암호 키가 존재합니다. 우리가 이전에 SSH 통신을 하기 위해 PuTTYGen을 통해 만들었던 .. 2023. 6. 11. 공개 키 인증서 (Public key certificate) 지난 포스트에서는 디지털 서명을 이용해 부인방지를 적용하는 과정에 대해 알아보았습니다. 이번 포스트에서는 네트워크 통신상에서 디지털 서명을 포함하고 있는, 인증서에 대해서 간단하게 알아보겠습니다. 인증서란? 인증서는 디지털 서명보다 비교적 친숙하게 들리는 용어입니다. 실제로 일상생활에서 마주치게 될 확률이 높기 때문인데, 예시로 사용자가 웹을 탐색할때 종종 아래와 같은 오류 페이지를 만나게 될 때가 있습니다. 이때 주소창 부분의 "주의 요함" 을 클릭해서 확인해보면, 이런 팝업이 표시됩니다. 두 번째 리스트의 '인증서가 올바르지 않음' 이라는 문구가 보이시나요? 우리가 오늘 알아 볼 인증서가 바로 이것입니다. 웹 서핑을 할때 암호화 프로토콜인 HTTPS 를 이용하면, 우리는 실시간으로 이 인증서를 사용하.. 2023. 5. 28. 최단 경로 찾기 : 플로이드 워셜(Floyd-Warshall) 알고리즘 들어가며 오늘 살펴볼 알고리즘은 지난번에 살펴봤던 다익스트라 알고리즘과 마찬가지로 최단경로를 찾는 알고리즘 중 하나인 플로이드 워셜(Floyd-Warshall) 알고리즘입니다. 같은 목적을 가진 알고리즘이라 그런지 익숙하게 느껴지는데, 플로이드 워셜은 어떤 방법을 통해서 최단경로를 구하는지 살펴보도록 하겠습니다. 알고리즘 플로이드 워셜 알고리즘은 동적 계획법을 활용한 길찾기 알고리즘입니다. 다익스트라가 지금까지 방문한 지점에서 가장 짧은 거리에 있는 지점을 차례로 선택하여 길을 찾아가는 반면, 플로이드 워셜은 지점들 중 하나를 선택해 두 지점을 연결하는 경로 중 해당 지점을 경유하는 가장 짧은 거리를 갱신하여 저장하는 과정을 반복해 길을 찾아가는 방법입니다. 로직으로 만들기 쉽게 단계별로 살펴보면, 경로.. 2023. 5. 21. 디지털 서명의 부인방지(Non-repudiation) 이전 포스트를 통해 일방향 해시함수가 어떻게 파일의 무결성을 확인할 수 있는지 알 수 있었습니다. 그러나 이런 일방향 해시함수를 사용한다고 해도, 송신자 측에서 통신이 이루어졌다는걸 부인해버리면 이 통신의 진위를 확인할 방법이 없다는 문제점이 남아 있었습니다. 따라서 보다 안전하고 확실한 통신을 위해 어떤 요청을 해당 송신자가 보낸 것이 확실하다는, 이른바 부인방지(Non-repudiation) 라고 하는 기술이 필요했는데요. 오늘 설명할 디지털 서명이 바로 통신간 부인방지를 적용하기 위해 등장한 기술입니다. 이번 글에서는 디지털 서명이란 어떤 것인지, 어떻게 디지털 서명이 이러한 문제를 해결할 수 있었는지에 대하여 알아보겠습니다. 디지털 서명이란? 디지털 서명(Digital Signature)이란 말 .. 2023. 5. 14. 파일의 무결성 검증하기 (일방향 해시 함수) 들어가며 지난 포스트에서는 데이터를 안전하게 암호화하여 보내는 방법에 대해 알아보았습니다. 통신 중간에 누군가가 민감한 정보를 열람하는 것을 방지하기 위해 원본 데이터를 제 3자가 알아볼 수 없게 만드는 암호화를 사용했고, 이러한 방법을 통해 기밀성을 지킬 수 있었습니다. 그러나 기밀성을 지키는 것만으로는 충분하지 않았습니다. 적절한 암호화는 중간자가 내용을 알아보지 못하게 만들수는 있었지만, 중간자가 내용을 바꿔서 보내거나 아예 엉뚱한 응답을 보내는걸 막을 수는 없었습니다. 이에 처음 보냈던 내용과 다른 내용을 수신하는 것을 방지할 필요가 있었고, 이는 곧 기밀성에 이어 또 다른 요소인 무결성(integrity)을 검증하는 여러 방법을 탄생시키는 배경이 되었습니다. 일방향 해시 함수 검증을 진행하는 개.. 2023. 4. 30. 이전 1 2 3 4 5 6 7 ··· 19 다음
