-
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...
-
재귀 함수에 대한 이해
개요 재귀 함수는 알고리즘 문제 풀이뿐만 아니라 프로그래밍 전반에 있어 매우 중요한 기법 중 하나입니다. 여러 복잡해 보이는 문제들을 재귀 함수 하나면 손쉽게 구현할 수 있는 경우가 많기 때문에 매우 ‘강력하다’는 표현을 자주 쓰게 됩니다. 문제 풀이에서는 DFS를 구현하는 가장 기본적인 방법으로 널리 사용되기 때문에 최근에 핫한 코딩 테스트들에서도 사용 빈도가 매우 높습니다. 그러나 재귀 함수는 알고리즘 초보가 쉽게 벽을 느끼게 될 수 있는 기법이기도 합니다. 순차적으로 그냥 실행 흐름을 따라가면 되는 다른 코드들과는 달리,...