# George Plotnikov

Personal site and blog. Please feel free to contact me via the social networks below.

# Elliptic curves smalltalk #2

Consider Diffie–Hellman key exchange.

DH uses final field. For example

user select in as a key

user select in as a key

int this case key exchange will looks: user send to user send to

their public key is = . How do they calculate it? user A takes and vice versa. there we see that for finding a key, cursed user should solve discrete logarithm task.

where here we can find an elliptic curve? we should replace exponentiation with multiplication. each participant selects some number and to summarize a point (on an elliptic curve) with itself times. the point is already known, also known that it produces big enough sub-group in elliptic curve points group. Each user sends his to the participant and keeps in secret. Consequently, a public key will be calculated as summarizing the point from the other participant with itself his times.

## Encryption

### El-Gamal system on EC

Suppose we have the pre-defined curve and a point. Curve, as known, is over some final field. User wants to send a message to user . Assume message is also a point on a curve.

• elliptic curve over ,
• - private key = - public key Assume
• message
• random number

Encrypted text from to will consists of the two parts:

1. =

It means anyone can encrypt and send a message, but the only receiver who has both keys can decrypt it. Real life example is the post office. You came to send a post to your aunt. You are able to put your envelope into the box, but you cannot open it.

### ECDSA

Elliptic curve digital sign algorithm

• - elliptic curve over , - point order
• - private key
• = - public key
• - random number

User wants to send message to user calculates hash and for the random

Sign:

,  ,  ,  ,

User checks the sign:

• ,
• then the sign is valid

## Elliptic cryptography pros and cons

pros:

• for the same security level, using elliptic curves algorithms require key with significantly less length. 4096 bit’s RSA’ key equal 313 bits in EC system. Performance improvement here takes place because despite each operation consumes more calculation, a key length much less.

cons:

• RSA has been analyzed much more times.

Common problems usually lay in the implementation:

• bad random numbers generator (true for the RSA as well)

Let’s consider another cases of using EC.

## Lenstra’s Factorization

Assume we have number which we want to factorize. This algorithm works fine if we suppose has not so big prime divider. In this algorithm, we consider not the EC over final field, but the set of points which are satisfied the same equitation as an EC (coordinates are ). We take some threshold number and declare that we will find any divider lesser or equals . Calculate point which is point -times summarized with itself. It means at the end of the loop we want to calculate . Why do we need this ? If we will try to calculate the following we can find the case with illegal summarize operation. It means we found some number immutable . Probably it’s multiplicator. If true, we should take a new random EC (point) and repeat algorithm. But if it is the lesser common divider - we found ’s divider (). might not be prime. The problem causes if is a multiplication of two big primes (~ ).

• take
• take random , ,
• take
• for j=2,3…treshold
• fail? means and divider
• - victory
• - should re-generate all and do it once again

Average working time: