루니프의 짤막보안강의 루니프의 짤막보안강의

[2021/07/22][짤막한 이야기 - 깊이 우선 탐색] “깊이 우선 탐색(Depth First Search, DFS)”이란 어떠한 그룹을 전체적으로 탐색할 때 깊이를 우선으로 하여 탐색하는 기법이다. 일반적으로 “트리(Tree)”를 탐색할 때에 우선시 하는 탐색 방법을 의미한다. 트리는 자료구조 중 하나로 다음에 소개할 주제이기도 하다. 트리의 깊이를 우선하여 탐색한다는 것은 갈림길이 나왔을 때 아래로 먼저 진행한다는 의미이기도 하다. 그리고 이것은 이전에 언급하였던 “우수법”과 동일한 알고리즘이다. 동굴에서 벽에 손을 짚고 걷는다는 것은 갈림길이 나올때마다 안으로 더 깊이 들어간다는 의미이기도 하다. 따라서 갈림길에서 잘못된 방향을 선택할 경우 동굴 출구로의 최단 거리를 구하는 것은 어려워진다. 이..

[2021/07/19][짤막한 이야기 - 알고리즘] “알고리즘(Algorithm)”은 수학, 컴퓨터 과학, 언어학 등에서 문제를 해결하기 위하여 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것이다. 즉, 문제 해결에 요구되는 계산 혹은 처리 순서를 의미한다. 고대 페르시아의 수학자 “알콰리즈미(Al-Khwarizmi)”에서 유래하였다고 알려져있으며, 이러한 알고리즘에는 몇가지 조건이 있다. 변하지 않는 명확한 작업 단계(정밀성)를 가지며, 각 단계마다 명확한 다음 단계(유일성)를 가진다. 정의된 입력을 받아들여서 출력을 내보낼 수 있어야 하며(입력 및 출력), 특정 횟수 이후 정지(유한성)해야한다. 그리고 마지막으로 일반적인 적용(일반성)이 가능하여야 한다. #이야기 #루니프 #알고리즘 #수학 #..

[2021/05/08][짤막한 이야기 - 영지식증명(한계)] “영지식증명”은 증명자가 지식을 보여주기 위한 최고의 수단이다. 왜냐하면 증명자의 지식을 제시하면서도 그 외의 정보는 아무것도 노출하지 않기 때문이다. 그러나 영지식증명에는 한계점이 있다. 앞선 예시(너무 오래전에 포스팅했지만..)를 다시 한번 생각해보자. (잘 기억나지 않는다면 이전 게시글을 확인하고 오는 것이 좋다.) 동굴의 마법의 주문을 알고 있음을 증명하기 위해서는 검증자가 원하는 방향으로 나와야 한다. 즉, 검증자와 한번은 대화를 해야하는 것이다. 그러나 한번만으로는 50% 확률로 검증에 통과할 수 있기 때문에 불충분하다. 그렇다고 검증자가 원했던 10번을 다 통과하면 증명자는 정말 비밀정보(마법의 주문)를 알고 있는 것일까? 즉, 대..

[2021/03/26][짤막한 이야기 - 영지식증명(개념)] “영지식증명”이란 증명자(Prover)가 검증자(Verifier)에게 어떠한 명제가 참이라는 것을 증명하기 위한 과정이다. 중요한 점은 “영지식”이라는 단어인데, 이는 증명 과정에서 “참”이라는 점 빼고 아무 지식도 노출되지 않는다는 의미이다. 예를 들어 검증자가 정말 증명자의 진위여부를 확인하고 싶을 때, 주민등록증을 확인할 수 있다. 이 과정에서 증명자가 맞는지(참) 이외에도 증명자의 주민등록번호가 노출될 수 있다. 이러한 정보 노출을 피하는 방법은 무엇일까? 증명자가 아니면 정확히 대답할 수 없는 질문을 여러번 던지는 것이다. 이의 구체적인 내용은 다음 포스트에서 제시한다. 개념적으로만 설명하자면 “양쪽으로 이동가능한 동굴에 마법의 문이 ..

[2021/03/16][짤막한 이야기 - 무결성(요약)] 앞선 포스트에서는 “무결성”과 관련된 암호프리미티브를 제시하였다. 각 프리미티브를 요약하면 다음과 같다. “변조 감지 코드”는 비밀 정보를 전혀 사용하지 않으며, “메시지 무결성”을 제공한다. “메시지 인증 코드”는 비밀 정보로 대칭키를 사용하며, “메시지 무결성”과 “메시지 인증”을 제공한다. “전자 서명”은 비밀 정보로 비대칭키를 사용하며, “메시지 무결성”과 “메시지 인증”, “부인 방지”를 제공한다. 생성 속도 측면에서는 “비대칭키 < 대칭키 < No-Key”에 해당하기 때문에 “전자 서명”이 가장 느리며 “변조 감지 코드”가 가장 빠르다. 안전성 측면에서는 “전자 서명”이 암호화 키만 공개하면 되기 때문에 가장 공유하기 안전하며, “메시지..

[2021/03/13][짤막한 이야기 - 전자 서명] “전자 서명(Digital Signature)”은 메시지 무결성, 메시지 인증, 부인 방지를 보장하기 위한 암호프리미티브이다. “전자 서명”은 “비대칭키”를 사용하여 부인 방지를 보장한다. 비대칭키 암호란 암호화 키(EK)와 복호화 키(DK)가 다른 경우이며, 암호화 키만이 대중(= “밥(Bob)”)에 공개한다고 언급하였다. 즉, 대중이 메시지를 암호화하여 “앨리스(Alice)”에게 암호문을 보내면 “앨리스”만이 복호화를 할 수 있는 방식이다. 전자 서명은 비대칭키 암호의 키 사용 방식을 반대로 적용하면 된다. 즉, “앨리스”가 먼저 메시지에 복호화 키를 적용한 후, 복호문을 대중에게 공개하면 대중은 공개된 암호화 키로 메시지를 복원할 수 있다. 전자..

[2021/03/03][짤막한 이야기 - 부인 방지] “부인 방지(Non-Repudiation)”는 어느 개체가 수행한 행위를 부정(거짓말)하는 것을 방지하는 속성이다. 기밀성, 무결성, 가용성 등과 같은 보안의 속성 중 하나에 해당하며, 부인 방지를 보장하지 못하였을 때 큰 문제가 될 수 있다. 부인 방지를 보장한다는 것의 의미는 간단히 이야기하면 특정 값의 생성은 특정 개체만이 할 수 있다는 것이다. 즉, 특정 값을 “밥(Bob)”이 가지고 있어도, 그 값을 “앨리스(Alice)”만이 생성할 수 있다면, 자연스럽게 “송신 부인 방지”를 보장한다. 즉 앨리스가 이 값을 (실제로 송신했지만) 송신한 적이 없다고 부인할 수 없는 것이다. 앞서 서술한 이야기에서 MAC은 메시지의 무결성과 인증을 동시에 보장..

[2021/03/02][짤막한 이야기 - 메시지 인증 코드] “메시지 인증 코드(Message Authentication Code, MAC)”는 “메시지 인증”을 위하여 사용되는 코드이다. “메시지 무결성”을 보호하기 위하여 “해쉬 함수”를 메시지에 적용한다고 하였는데, 이 때의 해쉬 값은 “변조 감지 코드(MDC, Modification Detection Code)”라고 소개한 바 있다. MDC는 기본적으로 안전한 채널로 전송되어야 한다고 했지만, 그것이 쉬운 일은 아니다. MAC도 MDC처럼 해쉬 함수를 사용하여 구성할 수도 있다. MDC와는 다르게 키를 함께 해쉬 함수에 넣는 것이다. 따라서 키를 모르는 개체는 동일한 MAC을 생성할 수 없다. 즉, MAC는 “메시지 무결성”과 “메시지 인증”을 동..