AlpacaHack Round 3 : qrime

roaris commented 1 month ago

RSA暗号の問題

import os
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger, isPrime

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

def gen():
    while True:
        q = getRandomNBitInteger(256)
        r = getRandomNBitInteger(256)
        p = q * nextPrime(r) + nextPrime(q) * r
        if isPrime(p) and isPrime(q):
            return p, q, r

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q, r = gen()
n = p * q

phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")
print(f"{r=}")

roaris commented 1 month ago

この問題にはいくつか解き方があって、自分が思いついたのは二分探索を使う方法

$r, nextPrime(r)$ は分かっているので $q (qnextPrime(r)+nextPrime(q)*r) = n$を満たすような $q$ を二分探索で求めればよい

from Crypto.Util.number import isPrime, long_to_bytes

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

n=200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e=65537
c=77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r=30736331670163278077316573297195977299089049174626053101058657011068283335270
nr = nextPrime(r)

left = 0
right = n

while True:
    q = (left + right) // 2
    x = q * (q * nr + nextPrime(q) * r)

    if x == n:
        assert(n % q == 0)
        p = n // q
        phi = (p - 1) * (q - 1)
        d = pow(e, -1, phi)
        print(long_to_bytes(pow(c, d, n)).decode())
        exit()
    elif x < n:
        left = q
    else:
        right = q

roaris commented 1 month ago

他の解法として、二次方程式を解く解法がある

$q (q nextPrime(r) + nextPrime(q) * r) = n$ について $nextPrime(q) = q + d$ とすると、 $(r + nextPrime(r))q^2 + rdq - n = 0$ という二次方程式が出来る

$d$ は大体1000以下だろうというのが実験から分かり(素数定理からも分かるらしい)、 $d$ を全探索して、二次方程式を解けば $q$ が見つかる

math.sqrtだと誤差が出るので、math.isqrtを使っている https://docs.python.org/ja/3/library/math.html#math.isqrt

from Crypto.Util.number import isPrime, long_to_bytes
from math import isqrt

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

n=200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e=65537
cipher=77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r=30736331670163278077316573297195977299089049174626053101058657011068283335270
nr = nextPrime(r)

for d in range(1000):
    a = r + nr
    b = r * d
    c = -n
    D = b*b - 4*a*c
    rD = isqrt(D)

    if D >= 0 and rD ** 2 == D and (-b+rD) % (2*a) == 0:
        q = (-b+rD) // (2*a)
        p = n // q
        phi = (p - 1) * (q - 1)
        d = pow(e, -1, phi)
        print(long_to_bytes(pow(cipher, d, n)).decode())

roaris / ctf-log

AlpacaHack Round 3 : qrime #73