I want to perform EC multiplication, but with
pure code. No libraries or anything outside my C# class. I've found a
ruby script (from learnmeabitcoin) that performs this procedure in pure ruby, but I am not sure that I understand these terms. I do have understood theoretically how ECC works, but in its maths, it seems impossible to make any sense. In other words, I may be able to “convert” the ruby code to C# line-by-line, but I won't have acknowledged the importance of each line. (which is what
takes the cake, but anyway)
That being said, it'd really satisfy me if there's an already written code (just like in learnmeabitcoin) in C#. I've searched for it, but I only found complicated scripts that require libraries. I only want the “private key to public key” part. Not anything extra.
If there isn't one, please be my guide and tell me what I'm doing wrong.
Alright, so to implement EC multiplication, I'll have to also write the modular inverse, EC addition and EC doubling.
I turned this:
# Modular Inverse - Ruby doesn't have a built-in function for finding modular inverses, so here's one using the extended Euclidean algorithm.
def modinv(a, m = $p)
a = a % m if a < 0 # make sure a is positive
prevy, y = 0, 1
while a > 1
q = m / a
y, prevy = prevy - q * y, y
a, m = m % a, a
end
return y
end
Into this:
public BigInteger modinv(BigInteger a, BigInteger m)
{
BigInteger prevy = 0;
BigInteger y = 1;
BigInteger q;
if(a > 0)
{
a = a % m;
}
while(a > 1)
{
q = m / a;
y = prevy - q * y;
prevy = y;
a = m % a;
m = a;
}
return y;
}
This:
# Double - Add a point on the curve to itself.
def double(point)
# slope = (3x^2 + a) / 2y
slope = ((3 * point[:x] ** 2) * modinv((2 * point[:y]))) % $p # using modular inverse to perform "division"
# new x = slope^2 - 2x
x = (slope ** 2 - (2 * point[:x])) % $p
# new y = slope * (x - new x) * y
y = (slope * (point[:x] - x) - point[:y]) % $p
# return x, y coordinates of point
return { x: x, y: y }
end
Into this:
public BigInteger[] ECdouble(BigInteger[] point){
BigInteger slope = (3 * point[0] ^ 2) * modinv((2 * point[1]), p);
BigInteger x = (slope ^ 2 - (2 * point[0])) % p;
BigInteger y = (slope * (point[0] - x) - point[1]) % p;
BigInteger[] coord = { x, y };
return coord;
}This:
# Add - Add two points together.
def add(point1, point2)
# double if both points are the same
return double(point1) if point1 == point2
# slope = (y1 - y2) / (x1 - x2)
slope = ((point1[:y] - point2[:y]) * modinv(point1[:x] - point2[:x])) % $p
# new x = slope^2 - x1 - x2
x = (slope ** 2 - point1[:x] - point2[:x]) % $p
# new y = slope * (x1 - new x) - y1
y = ((slope * (point1[:x] - x)) - point1[:y]) % $p
# return x, y coordinates of point
return { x: x, y: y }
end
Into this:
public BigInteger[] ECaddition(BigInteger[] point1, BigInteger[] point2)
{
if(point1 == point2)
{
return ECdouble(point1);
}
BigInteger slope = ((point1[1] - point2[1]) * modinv(point1[0] - point2[0], p)) % p;
BigInteger x = (slope ^ 2 - point1[0] - point2[0]) % p;
BigInteger y = ((slope * (point1[0] - x)) - point1[1]) % p;
BigInteger[] coord = { x, y };
return coord;
}
And finally, this:
# Multiply - Use the double and add operations to quickly multiply a point by an integer (e.g. a private key).
def multiply(k, point = $g) # multiply the generator point by default
# create a copy the initial starting point (for use in addition later on)
current = point
# convert integer to binary representation (for use in the double and add algorithm)
binary = k.to_s(2)
# double and add algorithm for fast multiplication
binary.split("").drop(1).each do |char| # ignore first binary character
# 0 = double
current = double(current)
# 1 = double and add
if char == "1"
current = add(current, point)
end
end
# return the final point
return current
end
Into this:
public BigInteger[] ECMultiplication(BigInteger k, BigInteger[] Gpoint)
{
BigInteger[] current = g;
string binary = String.Join(String.Empty,
privatekey.Select(
c => Convert.ToString(Convert.ToInt32(c.ToString(), 16), 2).PadLeft(4, '0')
)
);
// ignoring the first binary character
binary = binary.Substring(1);
current = ECdouble(current);
if (binary[0] == '1') {
current = ECaddition(current, Gpoint);
}
return current;
}
I run this:
BigInteger k = BigInteger.Parse(privatekey, NumberStyles.AllowHexSpecifier);
BigInteger[] point = ECMultiplication(k, g);
string x = point[0].ToString("X");
string y = point[1].ToString("X");
string public_key_uncompressed = "04" + x + y;
MessageBox.Show(public_key_uncompressed);
with this private key:
EF235AACF90D9F4AADD8C92E4B2562E1D9EB97F0DF9BA3B508258739CB013DB2
and I get as a result this uncompressed public key:
04F16342D6F4B64CC9911166A922D5AE5A9074B6BB59F3B7F159E82DFBB1F2641080931651B4F05BB9DD93ED3DF9D708BC0A1AD03F478767C3FDE73AEE2739C9ED54
I know that something goes wrong in that process since I get a different result from gobittest.appspot.com:
Seems like it should be "a<0" as per the Ruby example.
