-
트리를 활용한 새로운 효율적인 수열 쿼리 알고리즘
개요 그래프란 정점과 간선으로 구성된 자료구조로, 버스 노선 설계와 같은 생활속 문제부터 다양한 학술 분야의 이론까지 폭넓게 도입할 수 있다. 트리란 그래프의 일종으로 사이클이 없으며 연결성을 가진다는 강력한 조건을 가져 알고리즘 설계에 자주 사용된다. 본 글은 수열에서 특정 조건을 만족하는 순서쌍의 개수를 세는 복잡한 쿼리를, 트리를 활용하여 효율적으로 처리하는 새로운 알고리즘을 소개한다. 본문은 아래의 내용을 부가적인 설명 없이 서술한다. 각 항목에 대하여 자세하게 서술한 좋은 글을 링크해두었다. 세그먼트 트리 (Segment Tree) Heavy-Light Decomposition...
-
XOR 관련 문제를 푸는 접근법들
들어가기 전에 XOR (bitwise exclusive or)은 대표적인 bit 연산 중 하나입니다. 다른 bit 연산인 AND,OR,NOT이 갖지 못하는 특성 때문에, PS 및 CP에서도 관련 문제가 심심치 않게 출제되곤 합니다. 하지만 문제 제목이나 지문에 XOR이 있으면 일단 긴장하거나, 기피하시는 분들도 꽤 자주 본 것 같습니다. 그래서, 이번 글에서는 이런 XOR 관련 문제들에 접근하는 방법 몇 가지를 설명해 보려고 합니다. Basic Part 본격적으로 들어가기에 앞서, XOR 연산이 가지고 있는 성질 몇 가지에 대해서 간단하게 짚고 넘어가려고 합니다. 여러...
-
Differential Cryptanalysis on 4-round DES
서론 이번 글에서는 차분 분석 (Differential cryptanalysis)가 무엇인지 간략하게 살펴보고, 4-round DES에 대한 차분 공격을 예시로 알아보고자 합니다. 본론 차분 분석 차분 분석을 간단하게 말하자면, 어떤 함수 $f$가 주어져있을 때 $x, y$ 에 대해서 $(y - x, f(y) - f(x))$ 가 일정 확률로 특정 관계성을 만족하는 것을 이용하는 분석 방법 중 하나입니다. 이렇게만 이야기하면 쉽게 와닿지 않을 것 같아서 예시를 준비해봤습니다. S-box DES, AES와 같은 암호들을 살펴보면, 대부분의 연산이 선형 계산으로 이루어져 있습니다. 즉, 어떤...
-
Double dabble
안녕하세요? 이진법의 수를 BCD(binary-coded decimal)로 변환하는 알고리즘인 double dabble에 대해 알아보겠습니다. 십진수의 각 자리를 표시하는 데에는 4 bit가 필요하므로, 보통 이진수 네 자리를 묶어 십진수 한 자리를 표시하는 데에 사용할 수 있습니다. 예를 들어 53을 0101 0011과 같이 표시할 수 있습니다. 이를 BCD라고 합니다. 53을 이진수로 표시하면 110101이므로, 저희의 목표는 이를 BCD로 변환하는(또는 반대로), 다시 말해 110101를 0101 0011로 변환하는 것입니다. 위 작업 자체는 단순히 이진수를 십진수로 변환하기만 하면 되는 간단한 진법 변환이므로 매우 쉬운...
-
The Attacks on GEA-1 and GEA-2
Introduction 최근 한 논문이 암호학계에서 크게 주목을 받고 있습니다. 최고의 컨퍼런스 중 하나인 EUROCRYPT 2021에 수록된 논문인 “Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2”라는 논문입니다. 이 내용은 GEA-1, GEA-2라는 암호체계를 공격하는 알고리즘을 제시하는 논문입니다. 암호를 공격하는 논문은 많은데, 왜 하필 이 논문은 이렇게 주목을 많이 받고 있는 걸까요? 그 이유는 공격 과정에서 GEA-1에 백도어가 있다는 것이 사실상 확정적으로 밝혀졌기 때문입니다. 암호학적 백도어가 무엇인지는 barkingdong님의 http://www.secmem.org/blog/2020/09/20/Cryptographic-Backdoor/ 라는 글을 참고하시길 바랍니다. 이번 글에서는 GEA-1, GEA-2...