-
Forgery Attack on ElGamal Signatures
서론 최근에 한 문제에 대한 질문을 받았습니다. FuzzyLand라는 사이트의 WebShop 2.0 이라는 문제로, ElGamal signature 에 대한 공격을 요구하는 문제였습니다. 문제를 풀다보니 아이디어가 흥미로워서 공유하게 되었습니다. 본론 ElGamal Signatures ElGamal signature는 RSA signature와 비슷하게 discrete logarithm의 어려움에 바탕을 둔 signature scheme입니다. ElGamal signature는 다음과 같은 방식으로 돌아갑니다. 파라미터 및 생성 어떤 $N$-bit 소수 $p$를 고릅니다. 그리고 Hash function $H$를 고릅니다. 2부터 $p-1$ 사이의 어떤 수 $g$를 고릅니다. 이 수를 generator라고 부릅니다. 이 때 generator라고 불리는...
-
Digital Signature and Nonce Reuse
서론 Digital signature, 혹은 디지털 서명은 컴퓨터 네트워크에서 빠져서는 안 될 중요한 요소 중 하나이다. 수신자는 발신자로부터 메시지를 수신한 뒤, 메시지에 같이 붙어 온 digital signature를 검증해 해당 메시지가 정말로 발신자로부터 온 것인지 확인할 수 있다. 이를 보장할 수 있는 근간에는 다양한 수학 이론이 깔려있고, 이 중 중심이 되는 것은 정수론과 타원 곡선이라고 할 수 있다. 오늘 이 포스트에서는 이 중에서도 가장 쉽게 이해할 수 있고 널리 쓰이고 있는 DSA에 대해서 알아보고, nonce reuse가 왜...