Question

hello everyone

can anybody provide me an light weight elliptic curve cryptography algorithm full coded in any programming language you want, that works with ns2(network simulator)

thanks

Answer 1

ANS :-

Pseudo code for elliptic cryptography algorithm.

1.MODULAR ADDITION:-

To find x + y (mod p) where x, y ∈ [0, p − 1]:
• Find z = x + y.
• If z ≥ p then let z = z − p.
• Return z. (Note z ∈ [0, p − 1].)

2.MODULAR SUBTRACTION:-

To find x − y (mod p) where x, y ∈ [0, p − 1]:
• If x < y let x = x + p.
• Find z = x − y.
• Return z. (Note z ∈ [0, p − 1].)

3.BARRETT REDUCTION:-

Input: Positive integers x = (x2k−1 · · · x1x0)b,
p = (pk−1 · · · p1p0)b (with pk−1 6= 0 and p > 3) and
µ = (b^2k/p) (upper bound)

Output: r ≡ x (mod p)

ALGORITHM:

q1 =(x/b^k-1) (upper bound)

q2 = q1 · µ

q3 =(q2/b^k+1) (upper bound)

r1 = x (mod b^k+1)
r2 = q3 · p (mod b^k+1)
r = r1 − r2
If r < 0 then r = r + b^k+1
While r ≥ p do: r = r − p
Return r.

4.MONTGOMERY REDUCTION:-

5MONTGOMERY MULTIPLICATION:-

6.EUCLIDEAN ALGORITHM:-

7.MODULAR SQUARE ROOT ALGORITHM:-

To find √
x (mod p) where p ≡ 3 (mod 4):
• Find r = x
(p+1)/4
(mod p).
• If r
2 6≡ x (mod p) return “No square root exists.”
• Else return (r, p − r).

8.ADDITION FOR POINTS IN AFFINE COORDINATES:-

• Let P and Q be the two points to be added together.
• If P is φ then return Q as the result.
• Else if Q is φ then return P as the result.
• Else:
– Let P = (x1, y1) and Q = (x2, y2).
– Let T1 = (y2 − y1)
– Let T2 = (x2 − x1)
– If T2 is zero then
∗ If T1 is zero then return Double(Q) as the re-
sult.
∗ Else return φ as the result.
– Let λ = T1 · T
−1
2
– Let x3 = λ
2 − x1 − x2
– Let y3 = λ (x1 − x3) − y1
– Return (x3, y3)

9.DOUBLING FOR POINTS IN AFFINE COORDINATES:-

• Let the point to be doubled be P.
• If P is φ, return φ as the result.
• Else
– Let P = (x1, y1).
– Let λ = (3x
2
1 + a) · (2y1)
−1
– Let x3 = λ
2 − 2x1
– Let y3 = λ (x1 − x3) − y1
– Return (x3, y3).

10.BINARY SCALE MULTIPLICATION:-

11.CONVERSION OF A SCALAR TO NAF FORMAT:-

To find the naf representation of k:
• Let hm−1hm−2 . . . h0 be the binary representation of 3k and
let km−1km−2 . . . k0 be the binary representation of k.
• For i from 1 to m − 1 do:
– Set gi−1 = hi − ki
.
• Return g = gm−2gm−3 . . . g0.

12.SIGNED BINARY SCALAR MULTIPLICATION:-

13.TWO-IN-ONE SCALAR MULTIPLICATION:-

To find R = [h]P + [k]Q:
• Let hm−1hm−2 . . . h0 be the binary representation of h and
let km−1km−2 . . . k0 be the binary representation of k.
• Set S0 = P
• Set S1 = Q
• Set S2 = P + Q
• Set S3 = P − Q
• Set R = φ
• For i from m − 1 to 0 do:
– Set R = [2]R.
– Set s = hi
.
– If hi
is the same as ki then set j = 2.
– Else if hi
is zero then set j = 1 and s = ki
.
– Else if ki
is zero then set j = 0.
– Else set j = 3.
– If s < 0 then set R = R − Sj
.
– Else if s > 0 then set R = R + Sj
.
• Return R..

14.GENERATION OF CURVE:-

• Take as input the prime p defining the Galois field over which the curve
will be defined, as well as a small positive integer c¯, which is an upper
limit on the value of the curve order cofactor.
• Do (until a secure curve is found and returned):
– Choose the curve parameters a and b modulo p.
– Find the order of the curve, #E(GF(p)) = η.
– Check the mov condition (the smallest value of l such that
p
l ≡ 1 (mod η) is “large”) and anomalous condition (η 6= p). If
either of these fail, go back to the beginning of the loop (choose a
new curve).
– If η is prime, proceed to the next step. Otherwise, attempt to
factor η. If the attempt is successful, proceed to the next step.
Otherwise, if the attempt has not succeeded within a “reasonable”
time, conclude that η does not have a large prime factor and the
curve is hence insecure. Go to the beginning of the loop.
– If η = c · n and c ≤ c¯ and n is prime, return the values defining
the (secure) curve, p, a and b, as well as the curve order and its
factorization, η = c · n.