picoCTF2025: EVEN RSA CAN BE BROKEN??? Writeup

EVEN RSA CAN BE BROKEN???

authored by Michael Crotty

This service provides you an encrypted flag. Can you decrypt it with just N & e?

from sys import exit
from Crypto.Util.number import bytes_to_long, inverse
from setup import get_primes

e = 65537

def gen_key(k):
    """
    Generates RSA key with k bits
    """
    p,q = get_primes(k//2)
    N = p*q
    d = inverse(e, (p-1)*(q-1))

    return ((N,e), d)

def encrypt(pubkey, m):
    N,e = pubkey
    return pow(bytes_to_long(m.encode('utf-8')), e, N)

def main(flag):
    pubkey, _privkey = gen_key(1024)
    encrypted = encrypt(pubkey, flag) 
    return (pubkey[0], encrypted)

if __name__ == "__main__":
    flag = open('flag.txt', 'r').read()
    flag = flag.strip()
    N, cypher  = main(flag)
    print("N:", N)
    print("e:", e)
    print("cyphertext:", cypher)
    exit()

$N, e, cyphertext$が与えられます。
コードからは脆弱性らしきところはわかりません。

解法

$N$を取得してみましょう。すると、17365606987476149264805069969051887986625813037004054842196043402472264712368895766353245683772546912515447974408464713690964796174463480992978049945216914が渡されますが、最後の1桁は4であり、Nの値は偶数になっています。一旦$N$を2で割り、素数になるか確認してみましょう。

print(isPrime(17365606987476149264805069969051887986625813037004054842196043402472264712368895766353245683772546912515447974408464713690964796174463480992978049945216914//2))
#True

Trueになりました。つまり、$p,q$のどちらかは2であることがわかります。
後は、いつも通り復元したらフラグが取得できます。

from pwn import *
from Crypto.Util.number import isPrime, long_to_bytes
HOST = "verbal-sleep.picoctf.net"
PORT = 50440

io = remote(HOST, PORT)

io.recvuntil(b"N:")
N = int(io.recvline().strip().decode())

io.recvuntil(b"e:")
e = int(io.recvline().strip().decode())

io.recvuntil(b"cyphertext:")
c = int(io.recvline().strip().decode())

p = N//2
q = 2
d = pow(e, -1, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, N)).decode())

Flag: picoCTF{tw0_1$_pr!m31c9046c4}

picoCTFに出ていた際に面白いなと思った問題で、実験も時には必要だなと感じた1問でした。
Writeup書いてないなと思ったので今書いてみました。