긴 글은 아니고, Coppersmith’s method에 대해서 공부하고 싶으신 분들을 위한 요약 글입니다.
기본
기본적인 Coppersmith’s method를 이해하는데 도움이 되는 글은 역시 Alexander May의 “New RSA Vulnerabilities Using Lattice Reduction Methods”라는 글이 아닐 수 없네요.
Coppersmith’s method의 근본이 되는 Lattice와 LLL theorem에 대해서 간략하게 설명하며, Coppersmith’s method의 univariate case와 multivariate case, 그리고 그 응용들에 대해서 자세히 설명합니다.
또한 sage를 통해서 간단한 경우에 대해서 Coppersmith’s method를 어떻게 사용할 수 있는지를 알아보는 일본어 글도 찾아볼 수 있습니다. (SageMathを使ってCoppersmith’s Attackをやってみる)
다만 해당 글의 코드는 엄밀하지 못하기 때문에, 아래 PPT도 한 번 읽어보시는 것을 추천합니다.
작년 겨울에 위의 문서들을 바탕으로 PLUS 동아리에서 세미나를 할 때 사용한 PPT를 첨부합니다. (퀄리티가 좋지 못한 점 양해 부탁드려요 ㅎㅎ)
심화
Boneh-Durfee Attack
Boneh-Durfee Attack의 기본에 대해서 이해하고 싶으시다면 ebmoon님의 “RSA Attack Using LLL – Understanding Boneh-Durfee Attack” 문서를 참고하시는 것을 추천합니다.
Sage로 작성한 Boneh-Durfee Attack 코드는 RSA-and-LLL-attacks repository에서 확인하실 수 있습니다.
On Factoring Given Any Bits
한 때 트위터에서 소개했던 코드입니다. (링크)
My code for the paper "Solving Linear Equations Modulo Divisors:
— RBTree (@RBTree_) November 15, 2019
On Factoring Given Any Bits"https://t.co/htzBJw0a0a
Random-bit coppersmith!
“Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits” 논문을 바탕으로 작성한 것으로, random한 위치의 bit를 모르는 경우 뿐만 아니라 multivariate linear equation을 푸는 코드입니다.
그 외
Partial information으로부터 key를 복구하는 방법에 대해서 다양하게 다룬 “How to recover cryptographic keys from partial information”라는 PPT도 참고하기 좋습니다.