-
Understanding CRC
서론 작년 중순, 한 CTF에서 CRC와 관련된 문제가 하나 나왔습니다. 문제의 요지인 즉슨, flag{x}의 CRC 값이 다시 x가 나오게 하는 x를 구하는 것이었습니다. 이 과정에서 CRC의 특성에 대해서 이해하고 있는 사람이 별로 없다는 것을 알게 되었습니다. 또한 네트워크 수업에서도 Error code를 소개하는 자리에서 CRC가 나왔지만, CRC를 구하는 방법에 대해서만 알려줄 뿐 CRC가 어떠한 특성을 가지고 있는지는 알려주지 않았습니다. 최근에도 CRC에 대한 CTF 문제가 나오고 있고, 저도 CRC에 대해서 헷갈리던 부분이 있어서 이번에 한 번 정리하게...
-
A Generalized Birthday Problem
안녕하세요, 이번 글에서는 CRYPTO 2002에 소개된 David Wagner - A Generalized Birthday Problem 논문의 내용을 따라가며 논문에서 소개하는 Birthday Problem의 확장을 알아보겠습니다. Introduction Classic Birthday Problem Birthday Problem은 직관과 다르게 23명 이상만 있어도 그 중 두 명의 생일이 같을 확률이 1/2를 넘는다는 내용의 문제이고 별도의 설명이 필요한가 싶을 정도로 너무나 유명한 내용입니다. 암호학에서는 대표적으로 해쉬 함수가 N-bit이라고 할 때 해쉬값이 같은 두 입력을 찾기 위해서 $O(2^{N/2})$개의 입력에 대한 차분을 보면 된다는 정리가 Birthday Problem으로부터 도출되고...
-
General Matching and applications
General Matching and applications 유량(flow) 관련 알고리즘을 공부했다면 이분 그래프의 최대 매칭에 대해서는 익숙할 것이다. 이분 그래프에서 최대 매칭을 구하는 것은 크게 두 가지 의미에서 중요하다. 첫 번째는 문제 그 자체 에 대한 관심이다. 예를 들어, 택시 애플리케이션이 승객과 기사를 매칭하는 방법이나 결혼 중개업체가 남자와 여자를 짝짓는 방법 모두 이분 그래프의 매칭으로 표현할 수 있다. 두 번째는 이 문제가 다른 문제를 푸는데 어떻게 응용 될 수 있는지이다. 예를 들어, Konig’s theorem을 사용하면 이분 그래프의 최대...
-
Bixby Studio
Bixby Studio Contents 빅스비 스튜디오란? 내가 만든 예제 발전 방향 참고 빅스비 스튜디오란? 우선 빅스비는 삼성전자에서 개발된 음성인식 기반 개인 비서 어플리케이션으로 현재 스마트폰 외에도 여러가지 기기(대부분의 삼성 디바이스)에서 사용되고 있다. 보통 빅스비는 현재 삼성 페이와 연결되어 쇼핑으로 자주 활용된다. 빅스비는 어떤 발화가 주어지면, 그 발화를 해결할 수 있는 캡슐을 검색하게 된다. 예를들어 어떤 장소에 대해 질문을 하는 발화가 주어졌다면, 장소를 찾는 캡슐을 검색하고 그 캡슐안으로 이동해서, 여러 지정된 액션들을 수행하게 된다. 예전에 빅스비가 나왔던...
-
UCPC 2020 출제 후기
국내에서 가장 불꽃 튀는 알고리즘 대회 중 하나인 UCPC 2020 예선이 지난 7월 25일에, 본선이 8월 1일에 진행되었습니다. 저는 예선의 E번 감자 농장, H번 사과나무 그리고 본선의 G번 그건 망고가 아니라 고양이예요를 출제할 기회를 얻었습니다. 이 포스팅에서는 UCPC에서 문제를 제출한 순간부터 대회가 끝날 때까지 문제 개발이 어떻게 이루어졌는지를 다루어보고자 합니다. 테스트 케이스 제작에 초점을 두지만, 일반적인 검수 과정에 있어서도 길라잡이가 될 수 있으리라 생각합니다. 제가 만든 문제들을 해부하듯이 설명하기 때문에, 풀이도 서술되어 있음에 유의해주시길 바랍니다....