PAD Holiday Encryption Challenge

🎄 Merry Christmas from the PAD team ✨

Over the next week, we’ll be running an Xmas cryptographic puzzle 🔐

It consists of a 4-part challenge, with the challenges announced first on our Twitter: @PADtech_team.

If you manage to solve the four challenges correctly, the private key for a crypto wallet will be revealed; the first person to break the encryption is free to take the coins! Anyone who solves the puzzle can DM us on twitter for entry to our runner-up prize of 1:1 mentoring with experts (a choice of cryptography, privacy, venture funding or building start-ups).

Challenge 1 - Details

You have been given the encryption of a secret message M, using the ElGamal encryption system, and you have uncovered most of the decryption key. Recover the message M!

The ElGamal scheme has the following parameters:

  • Public parameters:

G = subgroup of multiplicative group of positive integers modulo p, where p = 81566989310791204912958106145305555115719958949728922727303163862148214358867 and where G is generated by g =


  • G has order q=(p−1)/2, and p and q are both prime.

  • Public key:

h = 80793392348996635802525441390281537983978395997501497563949031756925432102154

  • Private key (missing the first two digits):


The message M is written in ascii. We can consider it as an array of bytes x0,x1,…,xn−1, where 0≤xi≤255. Because ElGamal requires a message encoded as a long integer, we encode M as the integer


The encryption of M using the public key is the pair (c1, c2), where c1 = 44785258761373616031676979156741163241906288463412693477477111877289074374600 c2 = 18847655241697736948346855844525403433480137005221703577277568904143970421162