# 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.