Writeup DGSE - CTF - Le discret Napier

This article describes my solution for the 150-point challenge called “Le discret Napier”.

Introduction

Stockos a encore choisi un code d'accès qui est solution d'une énigme mathématique !
Retrouvez x tel que : 17^x ≡ 183512102249711162422426526694763570228 [207419578609033051199924683129295125643]
Le flag est de la forme : DGSESIEE{x} avec x la solution

Start

Considering the name of this challenge and the description, it sounds to me like the discrete logarithm problem. Discrete logarithm is used for public key cryptography, typically in Diffie-Hellman key exchange and El Gamal encryption. The reason is that, for a number of groups, there is no known efficient algorithm for the computation of the discrete logarithm, whereas the reciprocal, exponentiation, are performed in a number of logarithmic multiplications in the size of the argument. This problem is also present in elliptic curve cryptography, but it is called Elliptic Curve Discrete Logarithm Problem (ECDLP).

Quick explanation

This problem is quite classical to solve and tools such as SageMath (yes again) make our task much easier. For a quick explanation, if you take all the \(17^x \bmod n\) for \(x\) ranging from \(0\) to \(n-2\), you will have all the numbers between \(1\) and \(n-1\), of course over a finite field.

Solve \(x\)

First of all, you have to define \(K\) with the Galois field of cardinal \(n\).

sage: K = GF(207419578609033051199924683129295125643)

Set \(g\), the seventh element of \(K\).

sage: g = K(17)

Determine the position of \(h\) in \(K\).

h = K(183512102249711162422426526694763570228)

Retrieve its position in the multiplicative group generated by \(17\).

sage: h.log(g)

Few seconds or minutes after (depends on your processor), the result is found.

697873717765

That’s it! We managed to solve this mathematical riddle. You should know that this type of problem is easy to solve with rather small numbers, here they are very small.