Tag Archive

#rsa

이 태그가 포함된 글을 최신순으로 모아봤어요.

26
posts
BLOG2026-10-28
[🥇 Gold 3] 서명 두 개로 공개키를 되살려 HMAC 키로 쓴다 — DreamHack Simple Login 풀이
blog

[🥇 Gold 3] 서명 두 개로 공개키를 되살려 HMAC 키로 쓴다 — DreamHack Simple Login 풀이

verifyToken 이 토큰 헤더의 alg 를 먼저 읽고, HS256 이면 RSA 공개키 PEM 을 HMAC 비밀키로 넘긴다. 전형적인 알고리즘 혼동인데 공개키가 빌드할 때마다 새로 생성되고 어디에도 노출되지 않는다. guest 로 두 번 로그인해 받은 RS256 서명 두 개에서 모듈러스를 gcd 로 되살리고, openssl 과 바이트까지 같은 PEM 을 재조립해 그 451바이트를 HMAC 키로 username admin 토큰을 서명했다.
#dreamhack#ctf#web+5
 
BLOG2026-10-25
[🥈 Silver 3] 평문이 어느 1/4 구간인지만 흘려도 RSA 는 통째로 털린다 — DreamHack Supernova 풀이
blog

[🥈 Silver 3] 평문이 어느 1/4 구간인지만 흘려도 RSA 는 통째로 털린다 — DreamHack Supernova 풀이

서버는 복호한 평문이 0 부터 N 사이의 어느 1/4 구간에 있는지만 알려준다. 2비트짜리 정보인데, textbook RSA 의 곱셈 준동형으로 2의 k승을 곱해 가며 물어보면 그 응답이 곧 m/N 의 2진 전개가 된다. 520번 물어보고 1024비트 평문을 그대로 복원한 과정과, 그 전에 세 번 미끄러진 자리를 정리했다.
#dreamhack#ctf#crypto+5
 
BLOG2026-10-11
[💠 Platinum 4] 이진체 위의 RSA는 다항식 인수분해로 무너진다 — DreamHack Red-Black Christmas Tree 풀이
blog

[💠 Platinum 4] 이진체 위의 RSA는 다항식 인수분해로 무너진다 — DreamHack Red-Black Christmas Tree 풀이

정수가 아니라 GF(2) 위 4096차 다항식을 법으로 쓰는 RSA. "Red or Black, 0 or 1, binary fields"라는 힌트 그대로 곱셈은 carryless 다항식 곱이고 암호문은 flag^65537이다. 정수 인수분해는 어렵지만 유한체 위 다항식 인수분해는 다항시간이라, n을 0.16초 만에 8개 기약다항식으로 쪼개 유닛군 위수를 구하고 d=e⁻¹로 flag를 복원한다.
#dreamhack#ctf#crypto+6
 
BLOG2026-10-10
[🥇 Gold 3] 교과서 RSA 실수 9종 세트로 그림 퍼즐 풀기 — DreamHack EZ-RSA-PZ 풀이
blog

[🥇 Gold 3] 교과서 RSA 실수 9종 세트로 그림 퍼즐 풀기 — DreamHack EZ-RSA-PZ 풀이

오프라인 HTML 퍼즐 게임 하나에 RSA 공격 아홉 개가 숨어 있다. 개인키 노출·소수 노출·서명 악용·저지수·공통 소인수·공통 모듈러스·CRT 정수근·Coppersmith·Franklin-Reiter 로 아홉 서브플래그를 뽑고, 각각을 SHA256 해 AES-CBC 키로 직소 조각을 복호한 뒤 9장을 겹쳐 그림 속 최종 플래그를 읽는다.
#dreamhack#ctf#crypto+6
 
BLOG2026-08-22
[🥉 Bronze 4] RSA-2048 을 아홉 가지로 두들기고 돌아오니 답은 소스에 있었다 — DreamHack fakeday revenge 풀이
blog

[🥉 Bronze 4] RSA-2048 을 아홉 가지로 두들기고 돌아오니 답은 소스에 있었다 — DreamHack fakeday revenge 풀이

만우절에 올라온 문제. 배포본 prob.py 가 2048비트 RSA 로 flag 를 암호화하고 N, e, c 만 남기는데 소스의 flag 자리에는 가짜로 보이는 리터럴이 박혀 있다. Fermat, Pollard p-1, rho, 저지수, factordb 까지 아홉 항목을 돌려도 흠집이 없고, 설명이 가리킨 Shor 는 4099 큐빗이 필요하다. 답은 그 리터럴 자체였다.
#dreamhack#ctf#crypto+7
 
BLOG2026-08-21
[🥇 Gold 3] 자릿수를 뒤집은 소수 두 개 — DreamHack Triple Combination 풀이
blog

[🥇 Gold 3] 자릿수를 뒤집은 소수 두 개 — DreamHack Triple Combination 풀이

256비트 소수 p, q, r 을 2의 256제곱 진법 자릿수로 늘어놓아 만든 768비트 소수 a 와 b 는 서로 자릿수를 뒤집은 쌍이다. 그러면 2의 512제곱 빼기 1 로 나눈 나머지에서 두 소수가 같은 값으로 접히고, N 은 그 값의 제곱이 된다. 2의 512제곱 빼기 1 은 서로 다른 소수 13개로 완전분해되니 제곱근 8192개를 전부 만들어 걸러내면 된다. 전체 0.1초.
#dreamhack#ctf#crypto+5
 
BLOG2026-08-21
[💠 Platinum 2] 플래그를 반으로 쪼개 세 번 암호화하면 — DreamHack fl and ag 풀이
blog

[💠 Platinum 2] 플래그를 반으로 쪼개 세 번 암호화하면 — DreamHack fl and ag 풀이

68바이트 플래그를 34바이트씩 fl과 ag로 자른 뒤 fl, ag, 그리고 원본 flag를 같은 RSA 키로 전부 암호화해 공개한 문제. 평문 사이에 남은 일차 관계를 비 하나로 접어 Franklin-Reiter 관련 메시지 공격을 태우고, 거기서 나온 비를 2차원 격자 축약으로 다시 두 조각으로 펴서 0.9초 만에 플래그를 복원한 과정을 정리했다.
#dreamhack#ctf#crypto+6
 
BLOG2026-08-06
[💠 Platinum 4] 35%만 남긴 RSA 소수를, 플래그가 문자열이라서 복원한다 — DreamHack pprintable 풀이
blog

[💠 Platinum 4] 35%만 남긴 RSA 소수를, 플래그가 문자열이라서 복원한다 — DreamHack pprintable 풀이

플래그 256자를 그대로 1024비트 소수 두 개로 쓴 RSA 문제다. p, q 의 비트 중 35.16%만 공개돼 있어 Heninger-Shacham 부분키 복원이 요구하는 57%에 한참 못 미친다. 모자란 22%를 메운 건 암호가 아니라 플래그 자체의 성질이었다 — 모든 바이트가 영문자와 밑줄, 중괄호뿐인 55종 안에 있어야 한다는 것.
#dreamhack#ctf#crypto+5
 
BLOG2026-07-23
[🥈 Silver 4] e 가 (p-1) 을 나누는 RSA — AMM 으로 e차근 구하기 — DreamHack special_rsa_parameter 풀이
blog

[🥈 Silver 4] e 가 (p-1) 을 나누는 RSA — AMM 으로 e차근 구하기 — DreamHack special_rsa_parameter 풀이

공개지수 e=257 이 (p-1) 을 딱 한 번 나눈다. gcd(e, φ(N)) 이 1 이 아니라 d=e⁻¹ mod φ 가 존재하지 않아 평범한 RSA 복호가 막힌다. p·q 가 이미 주어졌으니 CRT 로 mod p / mod q 로 쪼갠 뒤, e차근이 유일한 mod q 는 그대로 풀고, e차근이 257개인 mod p 는 AMM(Adleman-Manders-Miller) 으로 전부 구해 CRT 로 다시 합친다. 257개 후보 중 BISC 로 시작하는 평문이 flag.
#dreamhack#ctf#crypto+6
 
BLOG2026-07-23
[🥉 Bronze 3] 8827비트 RSA가 0.004초에 갈라지는 이유 — DreamHack many primes 풀이
blog

[🥉 Bronze 3] 8827비트 RSA가 0.004초에 갈라지는 이유 — DreamHack many primes 풀이

모듈러스 N 이 2658자리(8827비트)라 겁을 주지만, 실은 11부터 8293 사이의 자잘한 소수 777개를 곱해 만든 값이다. 소인수가 전부 8296 미만이라 8296까지 시행나눗셈만 돌려도 통째로 갈라진다. 서로 다른 소수의 곱이라 φ(N)=∏(pᵢ−1) 로 바로 구해지고, d=e⁻¹ mod φ 로 개인키를 복원해 복호한다.
#dreamhack#ctf#crypto+5
 
BLOG2026-07-22
[🥈 Silver 3] 2048비트 RSA가 0스텝에 갈라지는 이유 — DreamHack crt rsa 풀이
blog

[🥈 Silver 3] 2048비트 RSA가 0스텝에 갈라지는 이유 — DreamHack crt rsa 풀이

공개 지수 e 도 개인키 d 도 주지 않고 dp, dq, qinv 와 암호문만 주는 RSA-CRT 문제. 두 소수를 p = nextprime(q + 1) 로 만들어 사실상 연속 소수라, 2048비트 모듈러스인데도 Fermat 인수분해로 0스텝에 갈라진다. dp·dq·qinv 는 그 자체가 CRT 복호 파라미터라, 소인수만 알면 e·d 복원 없이 곧장 평문을 얻는다.
#dreamhack#ctf#crypto+4
 
BLOG2026-07-21
[🥈 Silver 4] 소수 두 개가 크기부터 다르면 RSA는 절반만 뚫려도 끝난다 — DreamHack babycrypto3 풀이
blog

[🥈 Silver 4] 소수 두 개가 크기부터 다르면 RSA는 절반만 뚫려도 끝난다 — DreamHack babycrypto3 풀이

공개키(pub.pem) 하나와 암호문(ciphertext.txt) 하나가 전부인 RSA 문제. 모듈러스가 394비트밖에 안 돼서 "소수 두 개가 가까운가?"부터 의심하고 Fermat 인수분해를 시도했는데 곧바로 실패했다. 실제 결함은 전혀 달랐다 — 두 소수가 138비트와 256비트로 아예 크기 자체가 달랐다. 이렇게 극단적으로 불균형한 RSA는 작은 소수 하나만 ECM으로 뚫려도 전체가 무너진다. factordb.com에 이미 같은 모듈러스의 인수분해가 공개돼 있어 교차검증까지 마치고, 개인키를 복원해 RSA 복호 후 PKCS#1v1.5 패딩과 base64를 벗겨 flag를 얻었다.
#dreamhack#ctf#crypto+4
 
BLOG2026-07-21
[🥈 Silver 3] n도, e도, 암호문도 없이 개인키 d 하나만 준다면 — DreamHack d 풀이
blog

[🥈 Silver 3] n도, e도, 암호문도 없이 개인키 d 하나만 준다면 — DreamHack d 풀이

RSA 문제인데 공개된 값이 딱 하나, 개인키 d뿐이다. 공개키 n도, 지수 e도, 암호문도 없다. 그런데 flag 자체가 RSA의 소수 p로 그대로 쓰였다는 걸 알면 이야기가 달라진다. e·d - 1 이 (p-1)(q-1)의 배수라는 사실 하나만으로, n을 몰라도 이 숫자 하나를 완전히 소인수분해해서 p와 q를 통째로 되감을 수 있다. SageMath로 410비트 숫자를 끝까지 쪼갠 뒤, 그 조각들을 어떻게 나누면 진짜 소수 두 개가 나오는지 전수탐색으로 찾아냈다.
#dreamhack#ctf#crypto+5
 
BLOG2026-07-20
[🥈 Silver 3] 값을 바꾸면 검사를 피해간다 — DreamHack Textbook-RSA 풀이
blog

[🥈 Silver 3] 값을 바꾸면 검사를 피해간다 — DreamHack Textbook-RSA 풀이

암호화된 플래그를 그대로 서버에 되돌려 복호화를 요청하는 뻔한 시도는 "Do not cheat !"로 바로 막힌다. 하지만 그 검사는 딱 숫자 하나만 비교할 뿐이다. RSA는 곱셈에 대해 준동형(homomorphic)이라는 성질이 있어서, 암호문에 알려진 값을 곱해 완전히 다른 숫자로 둔갑시키면 검사를 통과하면서도 원래 값을 복원할 수 있는 정보를 그대로 얻어낼 수 있다.
#dreamhack#ctf#crypto+3
 
BLOG2026-07-20
[🥉 Bronze 2] 공유 소수가 GCD로 새는 1000개의 RSA — DreamHack Common things between us 풀이
blog

[🥉 Bronze 2] 공유 소수가 GCD로 새는 1000개의 RSA — DreamHack Common things between us 풀이

1000개의 RSA 암호문과 모듈러를 주는 문제. 각 모듈러는 네 소수의 곱이고, 각 소수는 정확히 네 개의 모듈러에 공유된다. 두 모듈러의 최대공약수로 공유 소수를 캐내 전부 인수분해하고, 모든 평문을 복호해 XOR하면 플래그가 나온다. 단, 모든 쌍을 O(n²)으로 대조하면 1000개 기준으로 실제 20초 넘게 걸린다 — 실무에서 대규모 키 집합을 감사할 때는 이 방식이 그대로는 안 통한다.
#dreamhack#ctf#crypto+3
 
BLOG2026-07-20
[🥉 Bronze 2] 두 모듈러의 소수 차이로 여는 인수분해 — DreamHack Is it CRT-RSA? 풀이
blog

[🥉 Bronze 2] 두 모듈러의 소수 차이로 여는 인수분해 — DreamHack Is it CRT-RSA? 풀이

플래그를 두 벌의 RSA로 절반씩 암호화하고, 두 모듈러의 소수 차이 dp·dq를 힌트로 주는 문제. 두 모듈러 관계식을 전개하면 한 소수에 대한 2차방정식이 되고, 근의 공식으로 소인수를 구하면 두 모듈러를 모두 인수분해해 복호할 수 있다. dp·dq는 소수 자체와 맞먹는 크기라 두 소수가 실제로 가깝지도 않은데도 정확한 차이값 하나만으로 인수분해가 그대로 뚫린다.
#dreamhack#ctf#crypto+3
 
BLOG2026-07-20
[🥉 Bronze 2] 코드에 박혀 버린 소인수 — DreamHack safeprime 풀이
blog

[🥉 Bronze 2] 코드에 박혀 버린 소인수 — DreamHack safeprime 풀이

안전소수(safe prime)를 쓴다며 RSA 두 벌로 플래그를 절반씩 암호화한 문제. 그런데 소수 생성 함수가 p1을 매 반복마다 고정 상수로 덮어써, 사실상 한 소인수가 소스에 공개돼 있다. N을 그 소수로 나누면 나머지 소인수가 나와 두 RSA를 모두 복호할 수 있다. sympy로 확인해보면 이 상수는 진짜 안전소수 조건(p, 2p+1 모두 소수)을 만족한다 — 문제는 성질이 아니라 그 값이 절대 바뀌지 않는다는 것이다.
#dreamhack#ctf#crypto+3