Elliptic curves smalltalk #2

See the new version of this article here:https://www.georgeplotnikov.com/elliptic-curves-smalltalk-vol-2/

DH uses final field. For example $\{1,2,3...238\}=\{1,g,g^2,... g^{238}\;\}(mod\;239)$

user $A$ select $x$ in $\mathbb{Z}$ as a key

user $B$ select $y$ in $\mathbb{Z}$ as a key

int this case key exchange will looks: user $A$ send $g^x$ to $B$ user $B$ send $g^y$ to $A$

their public key is $g^{xy}$ = $g^{x^{y}}$ . How do they calculate it? user A takes $g^{x^{y}}$ and vice versa. there we see that for finding a key, cursed user $C$ should solve discrete logarithm task.

where here we can find an elliptic curve? we should replace exponentiation with multiplication. each participant selects some number $n$ and to summarize a point $p$ (on an elliptic curve) with itself $n$ times. the point is already known, also known that it produces big enough sub-group in elliptic curve points group. Each user sends his $n$ to the participant and keeps $p$ in secret. Consequently, a public key will be calculated as summarizing the point from the other participant with itself his $p$ 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 $A$ wants to send a message to user $B$ . Assume message is also a point on a curve.

$E$ elliptic curve over $F_p$ , $P\inE(F_p)$
$d_A$ - private key $A$ $Q_A$ = $d_aP$ - public key Assume
$M$ message
$k$ random number

Encrypted text from $B$ to $A$ will consists of the two parts:

$C_1$ = $kP$
$C_2$ = $M$ + $kQ_a$ receiver: $C_2-d_AC_1=(M+kd_aP)-d_AkP=M$

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

$E$ - elliptic curve over $F_p$ , $P\inE(F_p)$ - point order $n$
- private key
- $Q_A$ = $d_AP$ - public key $A$
$k$ - random number

User $A$ wants to send message $M$ to user $B$ $A$ calculates hash $e=H(m)$ and for the random $k$

$kP=(x_1,y_1)$ Sign:

$(r,s)$ , $r=x_1\;mod\;n$ , $s=k^{-1}(+d_Ar)\;mod\;n$ , $r$ , $s\neq0$

User $B$ checks the sign:

$u_1P+u_2Q_A=(x_2, y_2)$
$u_1=s^-1e\;mod\;n$ , $u_2=s^-1r\;mod\;n$
$if(\;x_2\;mod\;n)=r$ 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 curve
bad point
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 $N$ which we want to factorize. This algorithm works fine if we suppose $N$ 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 $mod\;n$ ). We take some threshold number $B$ and declare that we will find any $N$ divider lesser or equals $B$ . Calculate $mod\;N$ point $Q$ which is point $P$ $j$ -times summarized with itself. It means at the end of the loop we want to calculate $B!P$ . Why do we need this $Q$ ? If we will try to calculate the following $j((j-1)!P)$ we can find the case with illegal summarize operation. It means we found some number immutable $N$ . 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 $N$ ’s divider ( $j$ ). $j$ might not be prime. The problem causes if $N$ is a multiplication of two big primes (~ $\sqrt N$ ).

take $N$
take random $a$ , $b$ , $A\;mod\;N$
take $B\equiv b^2-a^3+Aa\;mod\;N$
$E:Y^2=X^3+AX+B$
- for j=2,3…treshold
- $Q=jP\;mod\;N$
- fail? means $d>1$ and divider $N$
- $d<N$ - victory
- $d=N$ - should re-generate all and do it once again

Average working time: $O(e^{\sqrt{2(log\;p)(log\;log\;p)}})$

Useful links: