## 5/22/2016

### cryptography15

Cryptography 15

Elliptic Curve

Elliptic curve is an equation with two variables and coefficients and it is a cubic equation like the following form:
$y^{2}+axy+by=x^{3}+cx^{2}+dx+e$
$y^{2}=x^{3}$

Let's plot $y^{2}=x^{3}+ax+b$ with set of points E(a,b) = E(1,1)

First we have element called O (zero point or point of infinity) and we have a rule in geometric tearm "If 3 points on an elliptic curve lie on a straight line, their sum is O."
We can drive some rules from this rule :
1- For any point P on elliptic curve P+O=P.
2- The negative of point P with the same X coordinate, so if P=(x,y) then -P=(x,-y).
3- To add two points P and Q,draw a straight line between them and the third intersection point with curve is -R, then these three points P+Q=-R and the positive value of P+Q is the mirror image of the third point.
If the line between P and Q is tangent to the curve then R=P or R=Q.
4- To double point P,draw the tangent line and find the intersection point S then 2P=-S.

Algebraic addition over Elliptic curve :

1- To add two points $P({X}_{p},{Y}_{p}) \ Q({X}_{q},{Y}_{q})$, then the slope of the line that join them $\Delta = \frac{{Y}_{q}-{Y}_{p}} {{X}_{q}-{Y}_{p}}$
Then we can express R (which R= P+Q)

${X}_{r} = \Delta ^{2} - {X}_{p}-{X}_{q}$
${Y}_{r} = -{Y}_{p}+\Delta({X}_{p}-{X}_{r})$

2- To double point P P+P=2P = R
${X}_{r} =(\frac{3{X}_{p}^{2}+a}{2{Y}_{p}})^{2}-2{X}_{p}$
${Y}_{p} =(\frac{3{x}_{p}^{2}+a} {2{Y}_{p}})({X}_{p}-{X}{r})-{Y}_{p}$

Elliptic Curve over finite field :

Elliptic Curve over finite field is using elliptic curve in which variables and coefficients are all restricted to elements of finite field.

Prime Curve over Zp :

Prime Curve is using a cubic equation in which the variables and coefficients take value from 0 to P-1.
Equation of elliptic curve over Zp :
$y^{2} mod(p)=(x^{3}+ax+b) mod(p)$

The rules for addition over ${E}_{p}(a,b)$:

1- If $P({X}_{p},{Y}_{p}) \ then \ -P({X}_{p},{-Y}_{p})$.
2- To add two points $P({X}_{p},{Y}_{p}) \ and \ Q ({X}_{q},{Y}_{q}) \ R= P+Q$
Then R =
${X}_{r}=(\lambda^{2}-{X}_{p}-{X}_{q})mod(p)$
${Y}_{r}=(\lambda({X}_{p}-{X}_{r})-{Y}_{p})mod(p)$

$\lambda = \begin{cases}(\frac{{}{Y}_{q}-{Y}_{p}}{{X}_{q}-{X}_{p}})mod(p)) & if\ p\neq q \\ \\ (\frac{3{X}_{p}^{2}+a}{2{Y}_{p}})mod(p) & \text if \ p=q (double\ point\ p) \end{cases}$

For example :

Let P=(3,10) Q=(9,7) in ${E}_{23}(1,1)$
$\lambda=\frac{7-10}{9-3}mod(23)\ =\frac{-1}{2}mod(23)=11$
${X}_{r}=(11^{2}-3-9)mod(23=13$
${Y}_{r}=(11(3-17)-10)mod(23)=20$
Then P+Q = (17,20)

To double point P 2P

For example :

Let P =(3,10)
$\lambda=(\frac{3(3^{2})+1}{2*10})mod(23)=6$
${X}_{r}=(6^{2}-3-3)mod(23)=7$
${Y}_{r}=(6(3-7)-10)mod(23)=12$
Then 2P = (7,12)

Elliptic curve over $GF(2^{m})$ :

$GF(2^{m})$ consists of $2^{m}$ elements with addition and multiplication can be defined over polynomials, which variables and coefficients are elements of $GF(2^{m})$.
The cubic equation for cryptographic applications for elliptic curve can take the following form :

$y^{2}+xy= x^{3}+ax^{2}+b$
For Example :

For g = 0010
$y^{2}+xy=x^{3}+g^{4}x^{2}+1 \ \ \ where \ a=g^{4} ,b=g^{0}$
$a= g^{4}, b = 1$  and points that satisfies this equation $(g^{5},g^{3})$
$=(9^{3})^{2}+(9^{5})(9^{3})=(9^{5})^{3}+(9^{4})(9^{5})^{2}+1$
$=9^{6}+9^{8}=9^{15}+9^{14}+1$
1100+0101 = 0001+1001+0001
1001 = 1001

The rules of addition over $GF(2^{m})$ :

1- If $P({X}_{p},{Y}_{p}) and Q({X}_{q},{Y}_{q}) R = P+Q$
Then
${X}_{r}=\lambda^{2}+\lambda+{X}_{p}+{X}_{q}+a$
${Y}_{r}=\lambda({X}_{p}+{X}_{r})+{X}_{r}+{Y}_{p}$
$\lambda=(\frac{{Y}_{q}+{Y}_{p}}{{X}_{q}+{X}_{p}})$

2- If $P({X}_{p},{Y}_{p}) R = 2P$
${X}_{r}=\lambda^{2}+\lambda+a$
${Y}_{r}={X}_{p}^{2}+(\lambda+{X}_{p})$
$\lambda={X}_{p}+\frac{{Y}_{p}}{{X}_{p}}$

Key exchange using elliptic curve:

First choose a large integer q OR a prime number P or integer of form $2^{m}$
Then choose base point $G =({x}_{1},{x}_{2})$ in Ep(a,b) whose order is a very large value n, The order n of point G is the smallest positive integer n such that nG=0.
The Key exchange can be done by the following:
1- User A select an integer ${n}_{A}$ less than n , This is A's private key, then compute public key ${P}_{a}={n}_{A} * G$
2- User B select ${n}_{B}$ and compute the public key ${P}_{b}$
3- User A compute the secret key $K={n}_{A} * {P}_{b}$
4- User B compute the secret key $K={n}_{B} * {P}_{a}$
Note : The secret key is a pair of numbers.

For Example:
P=211 in Ep(0,-4)
The equation $y^{2} = x^{3} - 4$
G = (2,2)
A's private key ${n}_{A}=121$
B's private key ${n}_{B}=203$
Then
A's public key ${P}_{a}={n}_{A} * G = 121(2,2) = (115,48)$
B's public key ${P}_{b}={n}_{B} * G = 203(2,2) = (130,203)$
A's secret key $K={n}_{A} * {P}_{b} = 121(130,203) = (161,69)$
B's secret key $K={n}_{B} * {P}_{a} = 203(115,48) = (161,69)$
Then the shared key k = (161,69)

Elliptic Curve encryption algorithm :

First we have to encode the message to be sent as x and y coordinates, and it is not easy because not all points are in ${E}_{p}(a,b)$.
As with the key exchange
- Choose a point G
- User A select a private key ${n}_{A}$
- User A calculate the public key ${P}_{a}={n}_{A} * G$
To send a message Pm to User B, User A choose a random integer K and then produce the ciphertext Cm by the following:
${C}_{m} = (KG.{P}_{m} + K{P}_{b})$
Note : User A masked the message Pm by adding (K.Pb) and nobody but user A knows k value.

For Example :
P=751 in ${E}_{p}(-1,188)$
The equation $y^{2} = x^{3} -x + 188$
G=(0,376) Pm = (562,201)
User A choose k=386
${P}_{b} = (201,5)$
Then K.G = 386(0,376) = (676,558)
${P}_{m} + K,{P}_{b}$
(562,201) + 386(201,5) = (385,328)
Then the ciphertext Cm
Cm = {(676,558),(385,328)}

## 5/16/2016

### cryptography14

Cryptography 14

Elgamal Cryptographic System

Elgamal cryptographic system is a public-key algorithm based on discrete logarithm.
Elgamal cryptographic system is used in digital signature standard (DSS).

Elgamal Cryptographic algorithm:

There are prime number q and primitive root of q = a.
User A want to generate private and public keys as the following:

1- Generate a random integer ${X}_{a}$ such that 1 < ${X}_{a}$ < q-1.
2- Compute ${Y}_{a}=a^{{X}_{a}} mod(q)$.
${X}_{a}$ is A's private key and (q,a,${Y}_{a}$) is A's public key.

If user B Has A's public key then he can send him encrypted message as the following:
1- Represent the message as an integer M such that 0 <= M <= q-1, and longer messages are send as a sequence of blocks, each block has integer value less than q.
2- Choose a random number k such that 1 <= k <= q-1.
3- Calculate one-time key $K = ({Y}_{a})^{k} mod(q)$.
4- Encrypt the message M as a pair of integer(C1,C2)
${C}_{1} = a^{k} mod(q) \\\ {C}_{2} = KM mod(q)$.

User A can decrypt the message :

1- Recover the key by calculating $K ={C}_{1}^{{X}_{a}} mod(q)$.
2- Calculate $M = {C}_{2}*k^{-1} mod(q)$.

How user A can recover the K value to decrypt the message M?

K value is defined during the encryption process
$K = {Y}_{a}^{k} mod(q)$  ----> we can substitute ${Y}_{a}=a^{{X}_{a}} mod(q)$
Then $K = (a^{{X}_{a}} mod(q))^{k} mod(q)$
Then $K = a^{(k{X}_{a})} mod(q)$ ---> we substitute $a^{k} mod(q) = {C}_{1} ( {C}_{1} = a^{k} mod(q))$
Then $K = {C}_{1}^{{X}_{a}} mod(q)$.

Example :

In Elgamal public key scheme suppose prime number q = 19
and primitive root of 19 we choose a=10
User A generate private and public keys as the following :
1- User A choose ${X}_{a} = 5$.
2- ${Y}_{a} = a^{{X}_{a}} mod(q) = 10^{5} mod(19) = 13$

User A's public key = (19,10,3) and A's private key=5

User B want to send encrypted message M to user A with M value = 17

1- User B choose k=6.
2- $K = {Y}_{a}^{k} mod(q) = 3^{6} mod(19) = 7$.
Then ${C}_{1} = a^{k} mod(q) = 10^{6} mod(19) = 11$
${C}_{2} = KM\ mod(q) = 7*17 mod(19) = 5$

Then user B send${C}_{1} = 11 \ and \ {C}_{2} = 5$ to user A.
Then user A decrypt the message
1- User A calculate $K = {C}_{1}^{{X}_{a}} mod(q) = 11^{5} mod(19) = 7$
2- The $K^{-1}\ in \ GF(19) = K^{-1} mod(19) = 7^{-1} mod(19) = 11$
3- $M = ({C}_{2}K^{-1})mod(q) = (5*11) mod(19) = 17$ #.