-
비밀글 기능을 추가했습니다! (비밀번호:1234)
LOCKED PAGE
-
How JWT RS256 works
서론 Json Web Token(이하 JWT)은 전자 서명을 통해 json의 변조를 방지하는 Claim 기반의 토큰입니다. 이번 글에서는 제가 RS256을 다루면서 한참을 헤맸던 부분을 조금 정리해보고자 합니다. 본 글에서는 Google Colab에서 Python 3.7.12 PyJWT 2.3.0을 사용하여 테스트하였습니다. 결과값이 다르다면 동일한 환경에서 시도해주세요. ### RS256이란 JWT는 크게 header, payload, signature의 세 부분으로 구성됩니다. header은 해당 json이 JWT이며 어떤 알고리즘으로 서명하였는지, payload는 JWT에 담고자 한 내용이, signature은 header와 payload의 정보를 서명한 결과가 URLsafe base64 인코딩되어 담겨있습니다. (마지막의 패딩인 =는...
-
CakeCTF Cryptography Probs Write-Up
서론 굉장한 버스를 탔던 대회이다. 그럼에도 뉴비 키워준다는 느낌으로 가이딩을 많이 해주셔서 혼자서라면 꽤 많이 삽질했을 법한 부분도 수월하게 넘길 수 있던 것 같다. 물론 내가 참가한 부분은 crypto이므로, 이에 해당하는 5가지 문제를 업솔빙하며 풀이를 적어보려고 한다. discrete-log 문제에서 주어진 코드와 실행 결과는 다음과 같다. from Crypto.Util.number import getPrime, isPrime, getRandomRange def getSafePrime(bits): while True: p = getPrime(bits - 1) q = 2*p + 1 if isPrime(q): return q with open("flag.txt", "rb") as f: flag...
-
Introduction and Proof of Baby-step Giant-step Algorithm
서론 시작하기에 앞서 이산 로그 문제(Discrete Logarithm Problem, 이하 DLP)가 무엇인지 알아봅시다. 소수 $p$와 $\mathbb{Z}/p\mathbb{Z}$의 원소 $b$, $n$이 주어질 때 다음 식을 만족하는 $0$ 이상 $p-1$ 미만의 정수 $x$를 찾는 문제가 DLP입니다. \(b^x\equiv n \text{ (mod }p\text{)}\) Baby-step Giant-step 알고리즘은 DLP을 $O(\sqrt{p}\lg{p})$에 해결할 수 있는 알고리즘입니다. 다양한 DLP 알고리즘 중 완전탐색을 제외한 가장 간단한 알고리즘에 해당합니다. 이 글에서는 Baby-step Giant-step 알고리즘이 DLP를 어떻게 해결하는지, 왜 $O(\sqrt{p}\lg{p})$라는 시간복잡도가 보장되는지에 관해 알아보겠습니다. Baby-step Giant-step Algorithm 이 알고리즘은다음과...
-
Introduction and Proof of Tonelli-Shanks Algorithm
서론 이 글은 이전에 작성한 Tonelli-Shanks 구현 포스팅에 Tonelli-Shanks에 대한 이론적 내용을 덧붙여 작성한 글입니다. 배우며 작성한 글이므로 틀린 내용이 있을 수 있으니, 발견하시면 댓글로 알려주시길 바랍니다. 본 글은 https://rkm0959.tistory.com/20를 토대로 학습하며 작성한 글입니다. 암호학을 공부하다 보면 $\mathbb{Z}/p\mathbb{Z}$에서 이차방정식을 풀어야 할 필요가 있다. CTF에서 RSA 문제를 풀 때 $m^2\mod p$를 구했다거나, Diffie-Hellman 프로토콜 문제를 풀며 $g^2 \mod p$로부터 $g$를 찾아야 한다거나… 여러 상황에서 이차방정식을 해결할 수 있다면 편리할 것이다. 우선 $\mathbb{Z}/p\mathbb{Z}$가 아니라 $\mathbb{R}$에서 이차방정식을 풀...