Written by virchau13
I've discovered a more efficient way to do RSA! There are no downsides to this approach, right?
Attachment:
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
def nextPrime(k):
while not isPrime(k):
k += 1
return k
p = getPrime(512)
q = nextPrime(2*p)
N = p*q
e = 65537
pt = bytes_to_long(open('flag.txt', 'rb').read())
ct = pow(pt, e, N)
print(f'N = {N}')
print(f'e = {e}')
print(f'ct = {ct}')
The coefficients are monotonic: when p gets larger, q becomes larger as well. we can find a lower/upper bound of p and use binary search to find p and q:
from Cryptodome.Util.number import isPrime, long_to_bytes
import math
N = 331952857868366988663932945877951080549278582595446041827767968625349664658283914707688360079014486835580798093875473318398665440196327017511963073666394378115620522693620625071360763670651867749935306771611365203669632958229266010553458203000895499490278056591308718235818336550276558946434347335414409026661
e = 65537
ct = 27392982072168505918328498224512439143304951239197916179225339049412270594576024668071218892690652612353376666973045187430259051892719839059780552668922042760370020764362839523844795479477997719361780814250593853162333527993824104731684172908271583213365558182307524519318252505075812038979585427505321346605
def nextPrime(k):
while not isPrime(k):
k += 1
return k
# N = p*q >= 2*p*p
lo_p = int(math.sqrt(N // 2))
q = nextPrime(2 * lo_p)
print(N - lo_p * q)
hi_p = nextPrime(lo_p + 2**480)
q = nextPrime(2 * hi_p)
print(N - hi_p * q)
# binary search
while lo_p < hi_p:
print(hi_p - lo_p)
mi_p = (lo_p + hi_p) // 2
p = nextPrime(mi_p)
q = nextPrime(2 * p)
if N - p * q > 0:
lo_p = mi_p
elif N - p * q < 0:
hi_p = mi_p
else:
print(p, q)
pt = pow(ct, pow(e, -1, (p - 1) * (q - 1)), N)
print(long_to_bytes(pt))
break
Flag: watctf{qu4dr4t1c_3qu4t10ns_l0ve_c0rr3l4t10n}.
Another solution by DeepSeek that enumerates the gap between 2*p and q:
To solve this CTF challenge, we need to decrypt the ciphertext `ct` given the public key `N` and `e`. The key insight is that the prime `q` is generated as the next prime after `2*p`, which means `q` is very close to `2*p`. This allows us to express `N` as `p * q ≈ 2 * p^2`, so `p` is approximately `sqrt(N/2)`. We can use this relationship to derive `p` and `q` by solving the equation `N = p * (2*p + k)` for small values of `k`, where `k` is the difference between `q` and `2*p`. Once `p` and `q` are found, we can compute the private key `d` and decrypt the ciphertext.
Here is the Python code to achieve this:
from math import isqrt
from Crypto.Util.number import isPrime, long_to_bytes
# Given values from the challenge output
N = # Insert the value of N here
e = 65537
ct = # Insert the value of ct here
# Iterate over possible values of k (prime gap)
for k in range(1, 2000):
D = k*k + 8*N
root = isqrt(D)
if root * root == D:
if (-k + root) % 4 == 0:
p = (-k + root) // 4
if isPrime(p):
q = N // p
if isPrime(q):
# Check if q is the next prime after 2*p
current = 2 * p
while True:
current += 1
if isPrime(current):
break
if current == q:
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
pt = pow(ct, d, N)
flag = long_to_bytes(pt)
print(flag)
exit(0)
print("Failed to find p and q")
### Explanation:
1. **Import Libraries**: We use `isqrt` from the `math` module to compute integer square roots, and `isPrime` and `long_to_bytes` from `Crypto.Util.number` for primality testing and conversion.
2. **Given Values**: Replace the placeholders for `N` and `ct` with the values provided from the challenge output.
3. **Iterate Over `k`**: For each `k` from 1 to 2000, compute the discriminant `D = k^2 + 8*N` and check if it is a perfect square.
4. **Check `p`**: If `D` is a perfect square, check if `(-k + root)` is divisible by 4 to ensure `p` is an integer. Then, check if `p` is prime.
5. **Check `q`**: Compute `q = N // p` and check if it is prime. Then, verify that `q` is indeed the next prime after `2*p` by finding the next prime after `2*p` and comparing it to `q`.
6. **Decrypt**: Once valid `p` and `q` are found, compute the private key `d` using the totient `phi = (p-1)*(q-1)`, decrypt the ciphertext `ct` to get the plaintext `pt`, and convert it to bytes to reveal the flag.
This approach efficiently exploits the proximity of `q` to `2*p` to factor `N` and decrypt the flag. The range for `k` (1 to 2000) is chosen based on typical prime gaps for numbers of size `2^513`, ensuring the solution is both correct and efficient.
Attack code:
from math import isqrt
from Cryptodome.Util.number import isPrime, long_to_bytes
# Given values from the challenge output
N = 331952857868366988663932945877951080549278582595446041827767968625349664658283914707688360079014486835580798093875473318398665440196327017511963073666394378115620522693620625071360763670651867749935306771611365203669632958229266010553458203000895499490278056591308718235818336550276558946434347335414409026661
e = 65537
ct = 27392982072168505918328498224512439143304951239197916179225339049412270594576024668071218892690652612353376666973045187430259051892719839059780552668922042760370020764362839523844795479477997719361780814250593853162333527993824104731684172908271583213365558182307524519318252505075812038979585427505321346605
# Iterate over possible values of k (prime gap)
for k in range(1, 2000):
D = k*k + 8*N
root = isqrt(D)
if root * root == D:
if (-k + root) % 4 == 0:
p = (-k + root) // 4
if isPrime(p):
q = N // p
if isPrime(q):
# Check if q is the next prime after 2*p
current = 2 * p
while True:
current += 1
if isPrime(current):
break
if current == q:
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
pt = pow(ct, d, N)
flag = long_to_bytes(pt)
print(flag)
exit(0)
print("Failed to find p and q")
It also works.