When connecting to the server, we are presented with the following message:```$ nc challs.xmas.htsp.ro 1000Provide a hex string X such that sha256(unhexlify(X))[-5:] = 939e0
d444060eaed6dcfd33feGood, 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 message2. guess the secret message3. 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 sysfrom 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
# PoWp_o_w = inp().split(' ')[-1]inp()prnt(PoW(p_o_w))
# Read introinp(4)
NN = list()nn = Noneee = Nonepp = Noneqq = Nonephi = Nonedd = Nonecc = Nonefor 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 keyqq = nn // ppphi = (pp-1) * (qq-1)dd = inverse_mod(ee, phi)mi = pow(cc, dd, nn)ms = hex(mi)[2:]
# Read menuinp(5)
# Choose option 2prnt(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 message2. guess the secret message3. exit
1Here is the encrypted secret message: 2679e38b198f5815df86fbe2698697b9b0bba6636c2e63f7d5cc9ea6b9cabb48e853bf3996a596e3fb72062c850f701af770b21e142e8fb9ad2d048048640af188e82b2f4ca37c6c01ad01d5ef6298f684017eeb0ff887b68e499677451b4e03d35a7266ca399c96d1a7ed8f6be109fb0baaaeabc2e2d5a9e956cd832bd0bfc183ddc4c75c008922549cda8d6568eeae3d0fc2f16b78b7582ae6eddfbc994e48161c8b55c6543452c6d21eb51342605cb2386ba31e370e3c60aa9c683c56ef29f6cc4baa557c56866f030ded3a1d9232a1d657a6f22fd87f3cc09817582383c90a9992f59a41e7cec09974a2acd97d8c9cfe1c85c7dd64817d00c687be8aae4a.Ah, and also here's the public key with which it was encrypted:n: 8079251517893884153226649892767688917265798970329695047338595582369397621426984040735092129644587761986658412325473735342117658930106916201045793412035524834697233107715326664348717457272348743848500550196933670492059608094892880972168375355830986853543150055828544190611440233236154945300182931898129892215264804199753719949051893832823278584030431821712155150577369709586010756188562929222985412125872628891467616080282959116804180374051991807209531040073358199585846456864778416574824006160575786320593847318436460835228185950514059033856079349982539851820385356752470926237421794866513330303491283852793043087247e: 65537
[INFO] Duplicate factor found!Choose what you want to do:1. get encrypted secret message2. guess the secret message3. exit
2Let's see what you've got.
715e61411551edbcIt 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}```