GrabCon CTF 2021 | NotRSA

#grabcon2021

from math import sqrt
import random
from Crypto.Util.number import bytes_to_long


N = 2433984714450860961589027518159810370561856716063956157321856705975948489337570445957833120668443867975490363019335530343179129689501017626817947777263721
c = 1378297008929492435762470180953416238081302819750327089183697281160938504327642742017058360280755400054663296904328307673692314945545918393502459480987913
a = int(sqrt(N) + 1)
b = random.randint(0,9999999999)

flag = b"REDACTED"
m = bytes_to_long(flag)

c = ((a**m)*(b**(a-1)))%((a-1)*(a-1))

Paillier暗号

import gmpy2
from math import sqrt
from Crypto.Util.number import bytes_to_long, long_to_bytes
import random

#https://en.wikipedia.org/wiki/Paillier_cryptosystem
N = 2433984714450860961589027518159810370561856716063956157321856705975948489337570445957833120668443867975490363019335530343179129689501017626817947777263721
c = 1378297008929492435762470180953416238081302819750327089183697281160938504327642742017058360280755400054663296904328307673692314945545918393502459480987913
#a = int(sqrt(N) + 1)
a = 194545307101606186694882845905355574989*253593527157826835431576067999755840801 + 1
assert (a - 1) * (a - 1) == N

lambdaa = (194545307101606186694882845905355574989 - 1) * (253593527157826835431576067999755840801 - 1)
mu = int(gmpy2.invert(lambdaa, a - 1))
tempp = pow(c, lambdaa, (a - 1) * (a - 1))

flag = (((tempp - 1) // (a - 1)) * mu) % (a - 1)
print("flag:", long_to_bytes(flag))