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 =

42601667111078634237251057071000498123000139127388458396732577437783457730731

• 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):

??157062320179074418841310204956762570062357594285157543214069332211552941115

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

x0+256x1+2562x2+…+256n−1xn−1.

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