-
Attacking a Variant of the RSA Cryptosystem
서론 이번 글은 저번 달의 글에 이어서 pbctf 2021를 출제하면서 사용한 논문 하나를 리뷰하려고 합니다. 이 논문은 Yet Another RSA라는 문제로 작성하게 되었습니다. 해당 논문의 제목은 Classical Attacks on a Variant of the RSA Cryptosystem인데요, RSA의 변종에 대해 $d$가 작을 경우의 공격법을 다루는 논문입니다. 본론 RSA Variant 이 논문에서 소개하는 RSA의 변종은 정수가 아닌 group 위에서 정의됩니다. 해당 그룹에 대해서 정의하자면 다음과 같습니다. Field $(\mathbb{F}, +, \cdot)$에 대해서 non-cubic integer $r \in \mathbb{F}$를 하나 뽑읍시다....
-
Linear Suffix Array Construction
제가 최근에 작업을 하면서 큰 문자열에서 다른 작은 문자열을 많이 찾을 필요가 있었습니다. 정확히는, 이런 일을 해야 할 필요가 있었습니다. 문자열 $T$가 주어집니다. 문자열 $S_{1}$, $S_{2}$, $\cdots$, $S_{K}$가 $T$에서 등장하는 횟수를 구해야 합니다. 모든 정수 $1 \leq i < K$에 대해, $S_{1}$, $S_{2}$, $\cdots$, $S_{i}$에 대한 답을 구한 이후에야 $S_{i+1}$을 알 수 있습니다. 이 조건은 실제 문제 상황보다는 조금 빡빡한 제한이지만, 이렇게 가정해도 큰 무리는 없습니다. 이 상황이 다른 일반적인 상황과 크게 다른 점은 이렇습니다....
-
Cryptanalytic Extraction of Neural Network Models
1. Introduction 이번 글에서는 암호학 분야에서 탑 티어 컨퍼런스 중 하나인 CRYPTO 2020에 통과된 Cryptanalytic Extraction of Neural Network Models 논문에 대해 알아보고자 합니다. 보통 암호학에서 인공지능을 활용할 때나 반대로 인공지능에서 암호학을 활용할 때에는 해당 기술을 마치 블랙박스와 같이 두고 결과를 가져다 쓰는 방식으로 진행되기 마련인데 이 논문에서는 그게 아니고 Neural Network Model의 Extraction을 하는 상황이 곧 암호학에서 아주 유명한 공격인 차분 공격을 하는 상황과 유사하다는 것을 이용해 Neural Network Model에 대한 Extraction을 기존의 방법들보다...
-
알고리즘 문제 접근 과정 5
알고리즘 문제 접근 과정 5 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 두 배열의 합 - KOI 2001 고등부 1번 관찰 우리가 생각해볼 수 있는 가장 쉬운 방법은 무엇이 있을까요? 아마 문제에서 나온 방법을 그대로 사용하는 것이 가장 편한 방법일 것입니다. 우리가 만들 수 있는...
-
컴퓨터 과학의 미해결 문제들
개요 수학에는 많은 난제들이 있습니다. 전세계적으로 유명한 밀레니엄 문제가 대표적입니다. 인지도 있고 학술적 가치가 높은 난제는 하나를 해결하는 것이 평생의 업적이 되기도 합니다. 많은 난제들이 꾸준히 풀리고 있지만, 새로운 문제가 창조되는 것에도 역시 끝이 없습니다. 난제의 범위를 컴퓨터 과학으로 좁혀봅시다. 대표적인 것으로는 밀레니엄 문제의 일부이기도 한 P-NP 문제가 있습니다. P-NP 문제는 너무나 유명해서 이 글을 읽을 사람이라면 누구나 한 번쯤은 들어보았을 것입니다. 하지만 그 외에 다른 컴퓨터 과학 난제는 그다지 널리 알려진 것이 없는 것...