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

[2021/08/20][짤막한 이야기 - 콜라츠 추측] “콜라츠 추측(Collatz Conjecture)”이란, 추측이라는 글자에서 알 수 있듯이 현재까지 풀리지 않은 난제이다. 개념은 간단하다. 1) 특정 수 N이 1이라면 이 알고리즘은 종료된다. (C(1) = Exit) 2) 특정 수 N이 (1이 아닌) 홀수라면 3을 곱한 후 1을 더한다. (C(N) = 3N + 1) 3) 특정 수 N이 짝수라면 2를 나눈다. (C(N) = N / 2) 이 과정을 반복하면 유한번의 재귀를 통하여 1에 도달한다는 것이 콜라츠 추측이다. 이 추측은 아직 1로 도달하지 않는 반례가 나오지 않았기 때문에 지속적으로 반례를 찾고있으며, 반대로 항상 이것이 성립한다는 증명도 되지 않았기 때문에 난제로 불리우고 있다. 암호학에서..

[2021/08/19][짤막한 이야기 - 소수판별법] 이번 포스트에서는 “알고리즘”에서도 “암호학”에서도 매우 중요한 “소수판별법”에 대한 이야기를 하고자 한다. 가장 간단한 소수판별법은 검사대상 X를 X 미만의 숫자로 모두 나누어 보는 것이다. 즉, 103719521이 소수인지 판별하기 위해서는 2 ~ 103719520 까지 나눠 보는 것으로 시간 복잡도는 O(X)이 될 것이다. “RSA 2048”이라는 단어를 들어본 적이 있는가? 대표적인 비대칭키 암호알고리즘으로 이 때 2048은 RSA 암호알고리즘에 사용되어야 하는 공개키 N이 2048비트라는 의미이다. 공개키 N은 비밀키 P와 Q의 곱이며, P와 Q는 각각 1024비트의 소수이다. 즉, X가 두 개의 2^1024이기 때문에 랜덤한 두 수의 소수판..

[2021/08/18][짤막한 이야기 - 메모이제이션] 당신이 “알고리즘”에 전혀 관심이 없더라도 “피보나치 수열”을 한번쯤은 들어본 적이 있을 것이다. 피보나치 수열은 첫째 및 둘째 항(F1 & F2)이 1이며 셋째 항(F3)부터는 앞의 두 항의 합(F2 + F1)으로 구성되는 수열이다. 이를 점화식으로 표현하면 “F(i) = F(i-1) + F(i-2)”가 될 것인데, 간단하게 생각하면 “재귀 함수(Recursive Function)”로 구현할 수 있을 것 같다. 그런데 피보나치 수열은 매우 비효율적이다. 왜냐하면 F(7)을 구하기 위하여 F(3)을 구하는 횟수가 5번이나 되기 때문이다. 즉, “중복되는 부분 문제(Overlapping Sub Problem)”가 너무 많기 때문에 F(N)을 단순하게 ..

[2021/08/17][짤막한 이야기 - 핀툴 적용] 이전 포스트에서 생성한 핀툴을 이용하면 프로그램의 구조를 분석할 수 있다. 핀툴을 적용하기 위해서는 직접 생성한 핀툴(DLL) 이외에도 몇가지 준비물이 더 필요하며, 이는 그림에서의 위치(bin 폴더)에서 획득할 수 있다. 핀툴과 준비물, 그리고 분석 대상 프로그램을 모두 동일한 폴더에 넣은 후, 커맨드라인을 이용하여 명령어를 입력한다. “pin.exe -t [PinTool.DLL] -- [TargetProgram.exe]” 위 명령어는 [PinTool.DLL]을 이용하여 [TargetProgram.exe]를 분석하는 가장 기본적인 명령어이다. “pin.exe”는 위에서 언급한 준비물 중 하나이며, Pin이라는 가상머신 내에서 TargetProgram..

[2021/08/13][짤막한 이야기 - 구간합(응용)] 앞선 포스트에서 구간합에 대한 이야기를 했다. 구간합은 미리 합배열(SumA)을 생성하여 구간합 연산 속도를 O(N)에서 O(1)로 낮출 수 있다. 그러므로 기존에는 O(N*Q)(N은 데이터 개수, Q는 질문 개수)였던 시간복잡도가 O(Q) 수준으로 낮출 수 있었다. 그런데 만약 A 배열내의 숫자가 변경될 수 있다면 어떻게 될까? Q에 단순히 구간합을 묻는 질문의 개수가 아니라 A 배열내의 특정 위치의 숫자를 다른 값으로 바꾸는 연산도 포함되어 있다면 이야기가 달라진다. 예를 들어 A[1]의 값을 5에서 7로 바꾼다면 SumA를 모두 업데이트해야 하기 때문이다. A[1]을 업데이트하면 SumA는 1 ~ 9까지 모두 업데이트해야하기 때문에 최악의 경..

[2021/08/11][짤막한 이야기 - 구간합] “구간합(Prefix Sum)”이란 자료구조에 나열된 숫자들 중 일부 구간에 대하여 합을 구하는 방법이다. 예를 들어, 위 그림에서 A 배열의 2~4번째 구간합을 물어본다면 10(=7+2+1)을 답하면 되는 것이다. 최악의 경우에도 자료구조 내 모든 데이터를 1번씩만 확인하며 합을 더해나가면 되기 때문에 10의 시간을 초과하지 않는다. 그런데 질문의 개수가 많아지면 이야기는 달라진다. 자료구조의 데이터 개수(N)가 10개이지만 질문의 개수(Q)가 1억개가 주어진다면, 최악의 경우 10억(N*Q)만큼의 시간이 소요되는 것이다. 이 경우는 약 10초가 소요된다. 만약 데이터 개수가 최대 1만개이고 질문의 개수가 최대 10만개인 경우에도 10초보다 적게 소요될..

[2021/08/10][짤막한 이야기 - 영지식증명(응용)] “영지식증명”은 대화형(Interactive) 성질을 가지고 있으며, 이에 따라 많은 대화를 교환해야함을 한계점으로 지적한 바 있다(너무 오래전에 포스팅했지만..). 영지식증명에 "비대화형(Non-Interactive)" 성질을 추가하여야 한 쪽("증명자" 혹은 "검증자")의 연결이 끊어져도 증명 프로토콜의 수행이 가능하다. ”앨리스(Alice)”가 “밥(Bob)”에게 Y(=G^X)에서의 X값을 알고 있음을 증명하고 싶다. 1) 앨리스는 T (=G^V, V는 랜덤값)를 밥에게 송신한다. 2) 밥은 앨리스에게 랜덤값 C를 송신한다. 3) 앨리스는 C를 이용하여 R (=V-C*X)을 계산하여 밥에게 회신한다. 4) 밥은 T가 (G^R)*(Y^C)와..

[2021/08/09][짤막한 이야기 - 핀툴 생성] “핀툴(PinTool)”은 “핀(Pin)”을 이용하여 생성할 수 있는 DBI 도구이다. 핀은 구글에서 “Pin DBI”를 검색하여 공식 홈페이지에서 다운로드 받을 수 있다. 일부 핀툴과 관련된 블로그나 카페에서는 핀툴을 생성하기 위하여 “시그윈(CygWin)”을 설치하라는 안내가 많이 있지만, 실제로는 그럴 필요가 전혀 없다. 시그윈 자체가 10GB 이상이기 때문에 핀툴 생성을 위한 시그윈 설치는 매우 비추천하기 때문이다. 대신 “Microsoft Visual Studio 2019 Community(무료)”를 설치하여 핀툴을 생성하는 것을 추천한다. 다운로드 받은 핀 압축 파일을 압축해제한 후, “source/tools/MyPinTool”의 경로로 들..