[RCTF 2022] easyrsa

$p, q$ can be recovered from a continued fraction.

Then I just implement based on the paper without understanding the logic.

from Crypto.Util.number import *
import hashlib
import math
from sage.all import *

def function_v(r, k):
  r = int(r)
  k = int(k)
  if k == 0:
    return 2
  if k == 1:
    return r

  m = matrix(Zmod(N*N), [[r,-1],[1,0]])

  mk = m^(k-1)
  vec = vector(Zmod(N*N), [r, 2])

  res = mk * vec

  return res[0]


def function_d(p, i):
  return int(inverse(e, p-i))

#print(PoW(b'hrgqXfrgSNlb4eeT', 27))

e = 3121363059746835628022404544403822724460605553641332612055010587129451973002475126644668174294955070747985002800863652917895939538596303356113483509581841527286351537287500304267975061675901109982875778527827742120878835367386538561039072391997357702421691095861694681707017921391244519593945584755632901987840338065879901115934561426583008838453244051629340056867760923894623105542463500022221236457852502822707466528439969484890601953615303609725566617126458934095119670087068752543521167517461730977044465374505011791902510131823556603316457085145886999220426746234986984619161299098173535371540923264898459106461
c = 3023313363629909506923927199426293187583112749147539699346723655095868214179291222441307436555352537055690155418715652987685459938250844145450675418187664719327350488160722838989675928696633353180233455017609936874014883975932740217672705286265535646106053294507962613498142617741362730709360885118905440314573392981528077265110441270212385951070591696827167771592664502652520790612367259434545169836933571343480057141790292296952743986731389468760364416344837575740236416472589700581583016227273449673820568427641136163703116276104550877191839851640920430919278802098196408637904780725723268371465670950321881886863
N = 101946888552605033726177837709738163930032970477361664394564134626639467843553634920510447339985842689387519517553714582991506722045078696771986052246306068257957261478416093188640437503481862825381241480405463985516598520453211217206308826779669980833596066677262549841524134539729279446910817169620871929289


f = continued_fraction(e/(N-1)/(N-1))
#print(f)
conv = f.convergents()
#print(conv[:4])

for x in conv[6:]:
  d = x.denominator()
  k = x.numerator()
  if float(log(d) / log(N)) > 0.9: break

  v1 = e*d - (N-1)*(N-1)*k - 1
  if v1 % k != 0:
    continue

  #print("!!! k, d recovered")
  #print(k,d)
  break

### recover p, q
assert (e*d-1)%k == 0
v = N^2 + 1 - (e*d-1) // k   # p^2 + q^2
sq = v + 2*N # (p+q)^2
b = sq.isqrt() # p+q
assert b*b == sq
p = (b - (b^2 - 4*N).isqrt()) // 2
assert N % p == 0
q = N // p
assert p*q == N

# https://www.math.u-bordeaux.fr/~gcastagn/publi/crypto_quad.pdf

p = int(p)
q = int(q)

def v(k):
    if k == 0:
        return 2
    if k == 1:
        return r
    return (r * v(k - 1) - v(k - 2)) % (N * N)


def encrypt(m, e, N):
    c = (1 + m * N) * function_v(r, e) % (N * N)
    return c


# p = getPrime(512)
# q = getPrime(512)
# N = p * q
# d = getPrime(512)
# r = getPrime(512)
# e = inverse(d, (p * p - 1) * (q * q - 1))
# c = encrypt(235235235, e, N)
# # print(f"e = {e}")
# # print(f"c = {c}")
# print(f"N = {N}")
# # print(f"r = {r}")
# # print(f"p = {p}")
# # print(f"q = {q}")


invq = inverse(p,q)
invp = inverse(q,p)

precrt = invq

i = kronecker(c^2-4, Integer(p))
#i = 1
print("i ", i)
rp = int(function_v(c, function_d(p, i))) % p


i = kronecker(c^2-4, Integer(q))
#i = 1
print("i ", i)

rq = int(function_v(c, function_d(q, i))) % q

r = (rp + p*(rq-rp)*precrt) % N
print("r? ", r)
#print(r.is_prime())
N2 = N*N
V = int(function_v(r, e))
print("V", V)
print(gcd(V, N2))
tt = int(c * inverse_mod(V, N2) % N2)
print((tt-1)%N == 0) 

m = int(tt-1)//N
print(long_to_bytes(int(m)))

#tmp = int(function)

# tmp_p = int(c * function_v(r, e) % p^2)
# tmp_p = (tmp_p - 1) // p
# tmp_p = int(tmp_p)
# mp = tmp_p * invp % p

# tmp_q = int(c * function_v(r, e) % q^2)
# tmp_q = (tmp_q - 1) // q
# tmp_q = int(tmp_q)
# mq = tmp_q * invq % q

# mp = int(mp)
# mq = int(mq)

# m = (mp + p*(mq - mp) * precrt) % N

# print(long_to_bytes(int(m)))
# #print(m)