-
CryptoHack - Elliptic Curves : Double And Broken Writeup
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}$에서 이차방정식을 풀...
-
RSA Puzzles (1)
이전 글 - RSA 원리와 구현 이전 글에서는 RSA의 원리와 그 구현에 대해 간단히 소개하였으며, 이번 글에서는 ctf의 RSA Puzzle들에 적용할 수 있는 방법들을 몇가지 소개할 예정이다. (RSA Puzzle이라는 용어를 사용하는 이유에 관해서는 secmem - RSA Puzzles를 참고) Weak N RSA의 여러 인자 중 N은 RSA의 원리와 안전성 보장에 직결되어있는 요소이다. 이러한 N이 특정한 취약점을 지녀 쉽게 인수분해되거나 phi(N)이 쉽게 계산되어, RSA 암호화 전체를 파훼할 수 있게 되어버린다. 다음은 N에 발생할 수 있는 취약점 중...
-
RSA 원리와 구현
RSA란? 고전 암호와는 달리, RSA, ECC 등은 ‘어려운 문제’에 기반하여 암호화를 진행합니다. 이러한 ‘어려운 문제’는 컴퓨터를 이용하여도 정답(혹은 해)를 구하기 어려운 문제를 말하며, 소인수분해 문제, 이산 로그 문제 등이 대표적인 예시입니다. RSA는 그 중 소인수분해가 어려운 문제라는 점을 활용하는 암호화방식입니다. GNFS 등 빠른 소인수분해 알고리즘이 등장하였으나, 비트수에 대한 다항 시간 알고리즘은 알려져 있지 않아 큰 수를 소인수분해하는 것은 여전히 어려운 문제입니다. RSA는 1978년 로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)의 연구에 의해 체계화되어,...
-
Tonelli-Shanks 알고리즘 구현
Tonelli-Shanks 알고리즘은 mod p에서 Quadratic Residue에 대해 그 제곱근을 구하는 알고리즘이다. def tonelli_shanks(n,p): def isQR(x,p): return pow(x,(p-1)//2,p)==1 if not isQR(n,p): return -1 Q,S=p-1,0 while Q%2==0: S+=1 Q//=2 z=None for x in range(2,p): if not isQR(x,p): z=x break M,c,t,R=S,pow(z,Q,p),pow(n,Q,p),pow(n,(Q+1)//2,p) while True: if t==0: return 0 elif t==1: return R k=t*t%p ii=None for i in range(1,M): if k==1: ii=i break k*=k k%=p b=pow(c,2**(M-i-1),p)%p M=ii%p c=b*b%p t=t*c%p R=R*b%p if __name__=='__main__': n,p=map(int,input().split()) print("STARTED") print(tonelli_shanks(n,p))
-
Caesar Cipher(시저 암호)
Caesar Cipher은 고대 로마 황제였던 카이사르(시저)가 사용했던 간단한 암호로써, 알파벳을 특정한 개수만큼 shift하는 것으로 decode할 수 있다. shift된 문자열이 encode되기 전의 원본인지 판별하는 것을 자동화하는 것은 쉽지 않으며, decode 결과로 가능한 문자열의 수는 많지 않으므로(26개) 다음은 가능한 모든 결과를 출력하는 함수의 구현이다. def decode_caesar(t): def nxtAlpha(x): if x=='z': return 'a' elif x=='Z': return 'A' else: return chr(ord(x)+1) import copy s=copy.deepcopy(t) res=[] for x in range(26): res.append(copy.deepcopy(s)) for y in range(len(s)): if s[y].isalpha(): s=s[:y]+nxtAlpha(s[y])+s[y+1:] return tuple(res)...