A higher resolution is required to access the IDE

- 21

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

Elliptic-Curve Cryptography (ECC) is a recent approach to asymmetric cryptography. Its main benefit is an excellent ratio between the level of security and the key size. For example, the NSA recommends 384-bit keys for a top-secret level encryption using ECC, while achieving the same level of security using RSA requires 7680-bit keys. RSA is currently mostly used with 1024-bit keys, which is equivalent to 160-bit keys with ECC (Ref #1).**How it works**

Given a prime number

Let us define an addition operator on the curve points (see Ref #3 for a visual illustration).

To double a point C: Consider the tangent to the curve at point C. Let (X,Y) be its intersection with the curve, the point S = 2C is defined as (X,

**-**Y).

To add two distinct points C and D: Consider the line passing through both points. Let (X,Y) be its intersection with the curve, the point S = C+D is defined as (X,

**-**Y).

Let us consider a starting point

`k`*

`k`times) for some randomly chosen integer

`k`which will be the private key. This pair of public/private keys can be used to encrypt or sign messages (e.g. through ElGamal cryptosystem), yet this is out of the scope of this puzzle. The safety of the private key is not based on the public value

`k`given

`k`*

`k`is often above 2^200 to make sure not to be able to bruteforce it. As a result, to compute your key in an efficient way, you should use the

**double-and-add**method (Ref #4).

**Explicit formulas**

To compute S = (Xs,Ys) = C+D given two distinct points C = (Xc,Yc) and D = (Xd,Yd):

L = (Yd - Yc) / (Xd - Xc) mod PTo double a point, i.e. when C = D, L becomes (here

Xs = L² - Xc - Xd mod P

Ys = L * (Xc - Xs) - Yc mod P

L = (3*Xc^2 + A) / (2*Yc) mod PNote: You will have to compute a modular division, a division modulo

**Instructions**

Write an EC key generator: For each of the

`N`given

`k`values, you should provide the X-coordinate of the point

`k`*

**References**

ECC security level: https://www.ripublication.com/ijaer17/ijaerv12n19_140.pdf

List of EC: https://safecurves.cr.yp.to

Maths on EC: https://www.youtube.com/watch?v=NF1pwjL9-DE

Maths on EC: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Double-and-add

Input

**Line 1:**An integer

`N`, the number of keys to generate.

**Next**An hexadecimal integer

`N`lines:`k`.

Output

**An hexadecimal integer**

`N`lines:`X`corresponding to the generated point X-coordinate.

Constraints

1 <

`N`≤ 50

1 <

`k`< 0x3000000000000000

Example

Input

1 0x2

Output

0x2544b2250b8b1e1c

A higher resolution is required to access the IDE

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD Online Participants