Break the RSA

50

Flag is the decryption of the following:

PublicKey= (114869651319530967114595389434126892905129957446815070167640244711056341561089,113)

CipherText=102692755691755898230412269602025019920938225158332080093559205660414585058354


PublicKeyをfactordbで素因数分解します。素因数分解できますので次のPythonプログラムで復号できます。
def exgcd(m, n):
  if n>0:
    y,x,d = exgcd(n, m%n)
    return x, y-m/n*x, d
  else:
    return 1, 0, m

n = 114869651319530967114595389434126892905129957446815070167640244711056341561089
e = 113
c = 102692755691755898230412269602025019920938225158332080093559205660414585058354

p = 338924256021210389725168429375903627261
q = 338924256021210389725168429375903627349
d = exgcd(e, (p-1)*(q-1))[0] % ((p-1)*(q-1))
s = pow(c, d, n)
h = format(s, 'x')
f = ''
for i in range(0, len(h), 2):
f += chr(int(h[i:i+2], 16))
print(f)
フラグは、
UUTCTF{easy sH0Rt RSA!!!}
タグ ：
#Crypto