Standalone

### Implementing Elliptic Curves

Part I

# Field Arithmetic

Download quests in Questplay

Completing this quest requires knowledge in elliptic curve operations. If you are not read, we recommend trying our theory campaign first!

Take a look at `contracts/ObsidianGates.sol`

, a contract that uses an elliptic curve signature scheme for access control. The contract itself requires no modification, but for it to work, we must implement the underlying elliptic curve (in `FieldElement.sol`

and `EllipticCurve.sol`

).

`ObsidianGates`

uses the NIST P-256 curve, rather than the EVM's secp256k1 curve. The curve is given by the equation:

${y}^{2}\equiv {x}^{3}+ax+b\phantom{\rule{0ex}{0ex}}\phantom{\rule{0.4444em}{0ex}}\left(mod\phantom{\rule{0.3333em}{0ex}}p\right)$

where:

$a=0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc$

$b=0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b$

$p=0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff$

The curve is restricted over a prime field ${F}_{p}$, which uses modulo arithmetic for all field calculations. Hence, before implementing this curve in Solidity, it would be useful to first create a user-defined type for the field element.

In `contracts/FieldElement.sol`

, we have defined a new type `Felt`

(aka field element), along with some user-defined operators for `+`

, `-`

, `*`

, and `==`

.

```
Felt is uint256;
using {
add as +,
sub as -,
mul as *,
equals as ==, inv
} for Felt global;
```

We want to define these operations to be modular operations under $p$. By doing so, we can later comfortably handle field arithmetic when implementing the NIST P-256 curve itself.

## Your Task

In `contracts/FieldElement.sol`

, implement the logic for `add`

, `sub`

, `mul`

, `equals`

, and `inv`

. These functions must be implemented efficiently.

You can safely assume that all `Felt`

inputs in functions will be within valid range (i.e., $\le p$).

Run tests in Questplay

The Obsidian Gates are imbued with elliptic curve magic. To restore them, we must first build from the ground up...