Skip to content

Files

Latest commit

96238cf · Jun 6, 2023

History

History

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Feb 2, 2023
Jun 6, 2023
Feb 2, 2023

Power RSA

  • Round: 30 (2023/01)
  • Category: Crypto
  • Points: 75
  • Solves: 25

Description

Another boring RSA challenge

Solution

p=x^2+1 and q=x^2+1 so isqrt(n,2) is a good approximation of x*y, then you get phi(n)=x^2*y^2 so you can compute d to decrypt the flag.

from Crypto.Util.number import long_to_bytes
import gmpy2

with open('output.txt') as f:
    exec(f.read())

xy = gmpy2.iroot(n, 2)[0] - 1
phi = xy**2
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

@sahuang found that there is a generalization of this challenge: A New Attack on Special-Structured RSA Primes (Paper)

Found with keyword: near-square RSA primes

Proof

Proving n > ( x y + 1 ) 2 :

n = ( x 2 + 1 ) ( y 2 + 1 ) = x 2 y 2 + x 2 + y 2 + 1 x 2 y 2 + 2 x y + 1 (AM-GM Inequality) = ( x y + 1 ) 2

On the other way, I can't prove that ( x y + 2 ) 2 n always hold in general:

n = ( x 2 + 1 ) ( y 2 + 1 ) = x 2 y 2 + x 2 + y 2 + 1 ? x 2 y 2 + 4 x y + 4 = ( x y + 2 ) 2

But assuming x , y both being a 128-bit integer, it is easy to see x 2 + y 2 < 4 x y always hold by experimenting with random x , y .

So we know ( x y + 1 ) 2 n ( x y + 2 ) 2 , therefore n = x y + 1 .