When connecting to the server, we are presented with the following message:
```
$ nc challs.xmas.htsp.ro 1000
Provide a hex string X such that sha256(unhexlify(X))[-5:] = 939e0

d444060eaed6dcfd33fe
Good, you can continue!
Welcome to Santa's public key factory, here we create the world's highest quality keys.
Since this is an annanounced visit you can look through at most 256 keys.
As a bonus, try to use those keys to find what Santa's secret message for you is.
Choose what you want to do:
1. get encrypted secret message
2. guess the secret message
3. exit

```

Inspecting the given source code reveals, that textbook RSA is used for encryption. We can get the ciphertext and corresponding public key of a secret message when choosing menu option 1. Our task is to decrypt the ciphertext and send the secret message to the server by choosing option 2.

Everytime we choose option 1, we get the secret message encrypted with a new secret key. So we are looking for an attack against RSA where we know many different public keys and the encryption of a message mith those keys. The source code shows that a custom algorithm is used for prime generation. First, a 1024 bit number is generated by setting bit 1024 and 16 randomly chosen bits. Then, the next bigger prime number is computed and returned.

This sounds like we can expect one prime being used for two distinct RSA keys if look through 256 keys. So we wrote a script gathering 256 keys from the server. The script then checks each pair of public moduli (N_i, N_j) for common primes by computing the greatest common divisor. If the result is not 1, we have a hit and can compute the private key. With the private key we can decrypt the secret message and get the flag. This is our script:

```python3
#!/usr/bin/sage

import sys
from pow import PoW

def inp(i=1):
for _ in range(i):
line = input()
print(line, file=sys.stderr)
return line

def prnt(line):
print(line, file=sys.stderr)
print(line)
pass

# PoW
p_o_w = inp().split(' ')[-1]
inp()
prnt(PoW(p_o_w))

# Read intro
inp(4)

NN = list()
nn = None
ee = None
pp = None
qq = None
phi = None
dd = None
cc = None
for i in range(256):
# Read menu
inp(5)

# Choose option 1
prnt(1)

cc = int(inp().split(': ')[1][:-1], 16)
inp()
nn = int(inp().split(': ')[1], 10)
ee = int(inp().split(': ')[1], 10)
inp()

for n in NN:
ggt = gcd(nn, n)
if ggt != 1:
print('[INFO] Duplicate factor found!', file=sys.stderr)
pp = ggt
break
pass
pass
if not pp == None:
break
pass
else:
NN.append(nn)
pass
pass

if pp == None:
prnt(3)
exit(0)
pass

# Compute secret key
qq = nn // pp
phi = (pp-1) * (qq-1)
dd = inverse_mod(ee, phi)
mi = pow(cc, dd, nn)
ms = hex(mi)[2:]

# Read menu
inp(5)

# Choose option 2
prnt(2)

inp(2)

prnt(ms)
inp(2)
```

And voila: When running the script, we indeed observed prime number reusage:
```
$ ncat -e ${PWD}/santas_public_key_factory.sage challs.xmas.htsp.ro 1000
[...]
Choose what you want to do:
1. get encrypted secret message
2. guess the secret message
3. exit

1
Here is the encrypted secret message: 2679e38b198f5815df86fbe2698697b9b0bba6636c2e63f7d5cc9ea6b9cabb48e853bf3996a596e3fb72062c850f701af770b21e142e8fb9ad2d048048640af188e82b2f4ca37c6c01ad01d5ef6298f684017eeb0ff887b68e499677451b4e03d35a7266ca399c96d1a7ed8f6be109fb0baaaeabc2e2d5a9e956cd832bd0bfc183ddc4c75c008922549cda8d6568eeae3d0fc2f16b78b7582ae6eddfbc994e48161c8b55c6543452c6d21eb51342605cb2386ba31e370e3c60aa9c683c56ef29f6cc4baa557c56866f030ded3a1d9232a1d657a6f22fd87f3cc09817582383c90a9992f59a41e7cec09974a2acd97d8c9cfe1c85c7dd64817d00c687be8aae4a.
Ah, and also here's the public key with which it was encrypted:
n: 8079251517893884153226649892767688917265798970329695047338595582369397621426984040735092129644587761986658412325473735342117658930106916201045793412035524834697233107715326664348717457272348743848500550196933670492059608094892880972168375355830986853543150055828544190611440233236154945300182931898129892215264804199753719949051893832823278584030431821712155150577369709586010756188562929222985412125872628891467616080282959116804180374051991807209531040073358199585846456864778416574824006160575786320593847318436460835228185950514059033856079349982539851820385356752470926237421794866513330303491283852793043087247
e: 65537

[INFO] Duplicate factor found!
Choose what you want to do:
1. get encrypted secret message
2. guess the secret message
3. exit

2
Let's see what you've got.

715e61411551edbc
It seems you are a genius, we can't understand how you did it, but you did.
Here's your flag: X-MAS{M4yb3_50m3__m0re_r4nd0mn3s5_w0u1d_b3_n1ce_eb0b0506}
```