Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: BlackHatCoiner on May 22, 2021, 04:18:42 PM


Title: [C#] Trying to implement EC Multiplication in pure code
Post by: BlackHatCoiner on May 22, 2021, 04:18:42 PM
I want to perform EC multiplication, but with pure code. No libraries or anything outside my C# class. I've found a ruby script (https://learnmeabitcoin.com/technical/public-key) (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:
Code:
# 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:
Code:
 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:
Code:
# 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:
Code:
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:
Code:
# 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:

Code:
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:
Code:
# 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:
Code:
 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:
Code:
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:
Code:
EF235AACF90D9F4AADD8C92E4B2562E1D9EB97F0DF9BA3B508258739CB013DB2

and I get as a result this uncompressed public key:
Code:
04F16342D6F4B64CC9911166A922D5AE5A9074B6BB59F3B7F159E82DFBB1F2641080931651B4F05BB9DD93ED3DF9D708BC0A1AD03F478767C3FDE73AEE2739C9ED54

I know that something goes wrong in that process since I get a different result from gobittest.appspot.com:


Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: j2002ba2 on May 22, 2021, 05:14:17 PM
You are missing an important point - the one at infinity (0,0).

So three important cases are missing:
- doubling (0,0)
- adding to (0,0)
- adding (x,y) and (x,-y), which produces (0,0)


Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: BlackHatCoiner on May 22, 2021, 05:18:04 PM
Quote from: j2002ba2 on May 22, 2021, 05:14:17 PM
You are missing an important point - the one at infinity (0,0).
But I just “converted” the Ruby code to C#. If it's missing from me, then it should be missing from Ruby code too, but it doesn't. It works fine.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: j2002ba2 on May 22, 2021, 05:30:50 PM
When in ruby there are multiple assignments in one line, they are done in parallel, yes? Then your modinv is very wrong. If you need a forum post to find such mistake... maybe you should use a library.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: BlackHatCoiner on May 22, 2021, 06:57:13 PM
Quote from: j2002ba2 on May 22, 2021, 05:30:50 PM
maybe you should use a library.

For that particular function? For modinv only?

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: ignacioruiz23 on May 22, 2021, 07:15:23 PM
I'm working in something like at the university. Try to check if c# doesn't round any result.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: j2002ba2 on May 22, 2021, 07:45:25 PM
Quote from: BlackHatCoiner on May 22, 2021, 06:57:13 PM
Quote from: j2002ba2 on May 22, 2021, 05:30:50 PM
maybe you should use a library.

For that particular function? For modinv only?

Looks like for all. One more mistake is using ^2 for square. In C# (and C, C++, etc.) this is XOR with 2.

Do you really know C#? When translating code you should first understand what it does, both original and translated. Anyway, this must be a good learning experience for you. Maybe check what it does step by step and consult manuals more.


Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: archyone on May 22, 2021, 07:50:55 PM
Quote from: BlackHatCoiner on May 22, 2021, 06:57:13 PM
Quote from: j2002ba2 on May 22, 2021, 05:30:50 PM
maybe you should use a library.

For that particular function? For modinv only?

I use this one for modular multiplicative inverse.

Code:
int modInverse(int a, int n) 
{
    int i = n, v = 0, d = 1;
    while (a>0) {
        int t = i/a, x = a;
        a = i % x;
        i = x;
        x = d;
        d = v - t*x;
        v = x;
    }
    v %= n;
    if (v<0) v = (v+n)%n;
    return v;
}

On the other hand you would save your time using a library like Bouncy Castle for all your work on ecc calculation  :'(
You can find good source code to learn like Casascius one - https://github.com/casascius/Bitcoin-Address-Utility


Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: vjudeu on May 22, 2021, 07:56:36 PM
Follow this article: https://www.coindesk.com/math-behind-bitcoin

First, implement it using small numbers. After that, increase the numbers and make sure there is no brute force (like checking every number to find modulo inverse). Understanding the code is the most important part, so starting with small numbers should help.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: Coding Enthusiast on May 23, 2021, 03:54:02 AM
Quote from: BlackHatCoiner on May 22, 2021, 04:18:42 PM
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.
Unless this is just for educational purposes you shouldn't do it. Use a library like libsecp256k1 (https://github.com/bitcoin-core/secp256k1) with a wrapper in C#.

Quote from: BlackHatCoiner on May 22, 2021, 04:18:42 PM
That being said, it'd really satisfy me if there's an already written code (just like in learnmeabitcoin) in C#.
Bitcoin.Net has an EllipticCurve (https://github.com/Autarkysoft/Denovo/tree/master/Src/Autarkysoft.Bitcoin/Cryptography/Asymmetric/EllipticCurve) namespace which is a very simple implementation of ECC.
Private key to public key code would be MultiplyByG(BigInteger k) (https://github.com/Autarkysoft/Denovo/blob/8325f90a832bb5edd7062537ce3af3e3648723db/Src/Autarkysoft.Bitcoin/Cryptography/Asymmetric/EllipticCurve/EllipticCurveCalculator.cs#L262) method.
Keep in mind that this is minimally tested using NIST Cryptographic Algorithm Validation Program since I plan to completely replace it before releasing version 1.0.

If you want to see a more efficient implementation based on libsec256k1 check out the ECC (https://github.com/Coding-Enthusiast/FinderOuter/tree/master/Src/FinderOuter/Backend/ECC) namespace in FinderOuter.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: NotATether on May 23, 2021, 06:33:18 AM
Quote from: BlackHatCoiner on May 22, 2021, 04:18:42 PM
Into this:
Code:
 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;
        }

You're representing the points as an array which is unnecessary. You just need two variables to represent k and another two passed as reference for the return value.

Also why are you converting the BigInteger to a string and back again? It will cause a lot of unnecessary overhead and is probably the reason why you get a different result. You should be able to do this with just pure math, right?

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: BlackHatCoiner on May 23, 2021, 10:37:36 AM
Quote from: Coding Enthusiast on May 23, 2021, 03:54:02 AM
Private key to public key code would be MultiplyByG(BigInteger k) (https://github.com/Autarkysoft/Denovo/blob/8325f90a832bb5edd7062537ce3af3e3648723db/Src/Autarkysoft.Bitcoin/Cryptography/Asymmetric/EllipticCurve/EllipticCurveCalculator.cs#L262) method.
Thank you. I'm now trying it, because it seems simple. I've installed Bitcoin.net and copied this code:
Code:
        private readonly Autarkysoft.Bitcoin.Cryptography.Asymmetric.EllipticCurve.EllipticCurveCalculator calc = new Autarkysoft.Bitcoin.Cryptography.Asymmetric.EllipticCurve.EllipticCurveCalculator();

        public PublicKey ToPublicKey()
        {
            return new PublicKey(calc.MultiplyByG(BigInteger.Parse("1")));
        }

I don't know how to turn this PublicKey to string. Obviously, ToPublicKey().ToString() didn't work. Also, how do I get rid of Autarkysoft.Bitcoin.Cryptography.Asymmetric.EllipticCurve each time I want to include a part from EllipticCurveCalculator to my main c# script? I'm imported lots of usings, but it seems that it always needs the namespace:
Code:
using Autarkysoft.Bitcoin.Cryptography.Arithmetic;
using Autarkysoft.Bitcoin.Cryptography.Asymmetric.KeyPairs;
using Autarkysoft.Bitcoin.Cryptography.Hashing;
using Autarkysoft.Bitcoin.Blockchain.Scripts;
using Autarkysoft.Bitcoin.Blockchain.Transactions;
using Autarkysoft.Bitcoin.Cryptography.Asymmetric.EllipticCurve;

Quote from: Coding Enthusiast on May 23, 2021, 03:54:02 AM
Unless this is just for educational purposes you shouldn't do it.
It's not exactly educational purposes. I surely do this for exercise, but I just feel that I have to write it on a standalone c# script for one of my projects I have in mind.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: Coding Enthusiast on May 23, 2021, 11:01:00 AM
Quote from: BlackHatCoiner on May 23, 2021, 10:37:36 AM
I don't know how to turn this PublicKey to string. Obviously, ToPublicKey().ToString() didn't work.
Assuming you are using the PublicKey class provided here (https://github.com/Autarkysoft/Denovo/blob/master/Src/Autarkysoft.Bitcoin/Cryptography/Asymmetric/KeyPairs/PublicKey.cs) you have to call the ToByteArray() method and then encode the bytes however you want. byte[] has a special extension method to convert to hexadecimal called ToBase16().

BTW if you want to get public key of a private key it is best to use the PrivateKey (https://github.com/Autarkysoft/Denovo/blob/master/Src/Autarkysoft.Bitcoin/Cryptography/Asymmetric/KeyPairs/PrivateKey.cs) class directly since it makes sure you have a valid key.
Code:
var key = new PrivateKey(rng_or_wif_or_bytes_or_int);
string compPubHex = key.ToPublicKey().ToByteArray(true).ToBase16();
key.Dispose();

Quote from: BlackHatCoiner on May 23, 2021, 10:37:36 AM
Also, how do I get rid of Autarkysoft.Bitcoin.Cryptography.Asymmetric.EllipticCurve each time I want to include a part from EllipticCurveCalculator to my main c# script? I'm imported lots of usings, but it seems that it always needs the namespace:
I'm not sure what you are asking here. Each .cs file has to have the using directives before you can use the types in that namespace. This is not something you can get rid of.
https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/using-directive

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: HCP on May 24, 2021, 10:06:12 AM
Quote from: BlackHatCoiner on May 22, 2021, 04:18:42 PM
I turned this:
Quote
# 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:
Quote
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;
        }

Assuming these code snippets have all been copy/pasted here and not typed by hand... are you sure that your "a>0" check is correct? ??? Seems like it should be "a<0" as per the Ruby example.


Also, the your lines:
Code:
                y = prevy - q * y;
                prevy = y;
                a = m % a;
                m = a;

Won't work... because in Ruby the assignments/evaluation in the following code:
Code:
    y, prevy = prevy - q * y, y
    a, m = m % a, a
happens in parallel... so you'll need to use some temp variables to hold the "old" value of y and a...

ie.
Code:
                oldy = y
                y = prevy - q * y;
                prevy = oldy;
                olda = a
                a = m % a;
                m = olda;

Otherwise your final values of prevy and m will be the wrong values.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: BlackHatCoiner on June 30, 2021, 08:47:34 PM
Alright, so back to this thread five weeks later. Coding Enthusiast, your code works great; I'm just continuing this, because I now want to complete it straightly in my writing without using any external libraries. I've edited the modular inverse function, due to the assignments' parallelism as said by HCP. (I've also corrected the a>0 too)

modinv should be working properly:
Code:
public BigInteger modinv(BigInteger a, BigInteger m)
        {
            BigInteger prevy = 0;
            BigInteger y = 1;
            BigInteger q;
            BigInteger oldy;
            BigInteger olda;
            if (a < 0)
            {
                a = a % m;
            }
            while (a > 1)
            {
                q = m / a;
                oldy = y;
                y = prevy - q * y;
                prevy = oldy;
                olda = a;
                a = m % a;
                m = olda;
            }
            return y;
        }

If I haven't made any other mistakes in EC addition, multiplication and doubling, then it must be on the curve's variables:

Code:
string privatekey = "5"; // this is the private key in hex
BigInteger p = BigInteger.Parse("115792089237316195423570985008687907853269984665640564039457584007908834671663");
BigInteger[] g =
{
        BigInteger.Parse("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798", NumberStyles.AllowHexSpecifier),
        BigInteger.Parse("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", NumberStyles.AllowHexSpecifier)
};

This is what I run:
Code:
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;
ECDSApublic.Text = public_key_uncompressed;

And that's what I get:
Code:
0441721458CC97441B6C43006E2AE8050D55F8A200A22E067BA1D4F6C4E846B27AF5D0F2E457F91F826EC0412BEA2A13BADD81D5DB59009620EA2E56C927D6ED521

While I should be getting:
Code:
042F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4D8AC222636E5E3D6D4DBA9DDA6C9C426F788271BAB0D6840DCA87D3AA6AC62D6

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: BlackHatCoiner on July 27, 2021, 06:00:47 PM
Tuesday July 27th 2021 and I still face it.

My modular inverse function should be working fine.
Code:
public BigInteger inverse(BigInteger a, BigInteger m)
        {
            BigInteger m_orig = m;
            BigInteger prevy = 0;
            BigInteger y = 1;
            BigInteger q;
            BigInteger oldy = 0;
            BigInteger olda = 0;
            if (a < 0)
            {
                a = a % m;
            }
            while (a > 1)
            {
                q = m / a;
                oldy = y;
                y = prevy - q * y;
                prevy = oldy;
                olda = a;
                a = m % a;
                m = olda;
            }
            return y % m_orig;
        }

I rechecked the ECdouble & ECaddition and made a few corrections:
Code:
public BigInteger[] ECdouble(BigInteger[] point)
        {
            BigInteger slope = ((3 * point[0] ^ 2) * inverse((2 * point[1]), p)) % p;
            BigInteger x = (slope ^ 2 - (2 * point[0])) % p;
            BigInteger y = (slope * (point[0] - x) - point[1]) % p;
            BigInteger[] coord = { x, y };
            return coord;

        }

Code:
public BigInteger[] ECaddition(BigInteger[] point1, BigInteger[] point2)
        {
            if (point1[0] == point2[0] && point1[1] == point2[1])
            {
                return ECdouble(point1);
            }

            BigInteger slope = ((point1[1] - point2[1]) * inverse(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;
        }

The ECmultiplication was completely wrong and I'm curious why nobody noticed it. Not sure if it's now correct, but:
Code:
public BigInteger[] ECMultiplication(BigInteger k, BigInteger[] Gpoint)
        {
            BigInteger[] current = Gpoint;

            //private key to binary
            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);
           
            for (int i=0; i<binary.Length; i++)
            {
                current = ECdouble(current);
                if (binary[i] == '1')
                {
                    current = ECaddition(current, Gpoint);
                }
                    
                
            }
            
            return current;
        }

And finally, for k = 100 I should be getting:
Code:
048282263212C609D9EA2A6E3E172DE238D8C39CABD5AC1CA10646E23FD5F5150811F8A8098557DFE45E8256E830B60ACE62D613AC2F7B17BED31B6EAFF6E26CAF

But, my code has another opinion:
Code:
047D285CA13DEC25E44F435B6876601CC9042F8787AD8B7DCC1F6588FF50D5327FF21E17C179DFC3A565E3ECCD0EEF92D9A39D6B23FAB1F8093A72E3468C9A2A335


[My C# code (http://pastie.org/p/6zEnGxzOhDsYuLT8c4pkqQ)]

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: COBRAS on July 27, 2021, 07:14:28 PM
More about modern and fast point addiation. I think this will be more good then simple add or doubling points.

Try implement in yours code https://paulmillr.com/posts/noble-secp256k1-fast-ecc/#unsafe-multiplication-for-key-recovery

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: j2002ba2 on July 27, 2021, 11:24:20 PM
Marked with red are some grievous mistakes. Blue are some missing parts.
Since you managed to discard any feedback let me make it very clear:
^ 2 is not squaring a number: 2^2 = 0

Quote from: BlackHatCoiner on July 27, 2021, 06:00:47 PM
public BigInteger[] ECdouble(BigInteger[] point)
        {
           if (point[1] == 0) {
                BigInteger[] coord = {0,0};
                return coord;
            }
            BigInteger slope = ((3 * point[0] ^ 2) * inverse((2 * point[1]), p)) % p;
            BigInteger x = (slope ^ 2 - (2 * point[0])) % p;
            BigInteger y = (slope * (point[0] - x) - point[1]) % p;
            BigInteger[] coord = { x, y };
            return coord;

        }

public BigInteger[] ECaddition(BigInteger[] point1, BigInteger[] point2)
        {
            if (point1[0] == point2[0] && point1[1] == point2[1])
            {
                return ECdouble(point1);
            }
           if (point1[0] == point2[0])
            {
                BigInteger[] coord = {0,0};
                return coord;
            }
            BigInteger slope = ((point1[1] - point2[1]) * inverse(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;
        }


Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: BlackHatCoiner on July 28, 2021, 08:16:30 AM
Quote from: j2002ba2 on July 27, 2021, 11:24:20 PM
...
I could swear that ^n means raising to the power of n. But, it turns out that it doesn't. It actually means index from end operator (https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/member-access-operators#index-from-end-operator-). As for the missing parts, I didn't know them. I was only following the ruby scripts from learnmeabitcoin. Thanks for the time it took you to correct me.

I did make the changes, but still get false result. For k=100 I should be getting:
Code:
048282263212C609D9EA2A6E3E172DE238D8C39CABD5AC1CA10646E23FD5F5150811F8A8098557DFE45E8256E830B60ACE62D613AC2F7B17BED31B6EAFF6E26CAF

But, I get:
Code:
040F19435668D97C96E4AE99B4BC78EB71826D36F9B380E0B462FD3159F5D896642B2B297DED0525941A6BEBB8386979BDEFBC7DFC6707C6871E67983E0807E4523

So, I still have something wrong in my code (http://pastie.org/p/2qyfgFEfrnGVRsYJgtRQ1W). Just to catch you; I used n*n instead of Math.Pow(n, 2) just because they're BigInteger and the Math.Pow(n, 2) would require extra additions which would make the code even more complex. Both of them work fine.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: j2002ba2 on July 28, 2021, 10:58:11 AM
Quote from: BlackHatCoiner on July 28, 2021, 08:16:30 AM
Quote from: j2002ba2 on July 27, 2021, 11:24:20 PM
...
I could swear that ^n means raising to the power of n. But, it turns out that it doesn't. It actually means index from end operator (https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/member-access-operators#index-from-end-operator-). As for the missing parts, I didn't know them. I was only following the ruby scripts from learnmeabitcoin. Thanks for the time it took you to correct me.


I would say it is Logical exclusive OR operator ^ (https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/bitwise-and-shift-operators#logical-exclusive-or-operator-).

Quote
I did make the changes, but still get false result. For k=100 I should be getting:

Test it step by step:
Is ECdouble giving the correct result for G, 2G, O?
Is ECaddition doing it as well: G+G, G+(-G), G+2G, 2G+3G, 3G+4G?
Finally is ECMultiplication correct for small numbers (1-10), for big numbers (n-1), for numbers >=n ?


Your inverse function is still wrong. You could give up and use the simpler (but slower) version:
Code:
        public static BigInteger inverse(BigInteger a, BigInteger m)
        {
            return BigInteger.ModPow(a, m - 2, m);
        }

Looking at your struggle is just painful. Here is working code.
Code:
using System;
using System.Numerics;
					
public class Program
{
    static BigInteger p = BigInteger.Parse("115792089237316195423570985008687907853269984665640564039457584007908834671663");
    static BigInteger n = BigInteger.Parse("115792089237316195423570985008687907852837564279074904382605163141518161494337");
    static BigInteger[] zero = {0,0};
    static BigInteger[] g = {
        BigInteger.Parse("55066263022277343669578718895168534326250603453777594175500187360389116729240"),
        BigInteger.Parse("32670510020758816978083085130507043184471273380659243275938904335757337482424")
    };
    public static void Main()
    {
        BigInteger[] g0 = {0,0}, g2 = ECdouble(g), g4 = ECdouble(g2);
        BigInteger[] z = ECMultiplication(7, g);
        //z = ECaddition(z, g);
        //z = ECaddition(z, g2);
        //z = ECaddition(z, g4);
        Console.WriteLine(z[0].ToString());
        Console.WriteLine(z[1].ToString());
        Console.WriteLine(IsOnCurve(z));
        Console.WriteLine(IsOnCurve(zero));
    }
	
    public static BigInteger inverse(BigInteger a, BigInteger m) { return BigInteger.ModPow(a, m-2, m); }
    public static BigInteger[] ECdouble(BigInteger[] point)
        {
            if (point[1] == 0) return zero;
            BigInteger slope = (3 * BigInteger.ModPow(point[0], 2, p) * inverse((2 * point[1]), p)) % p;
            BigInteger x = (BigInteger.ModPow(slope, 2, p) - (2 * point[0])) % p;
            BigInteger y = (slope * (point[0] - x) - point[1]) % p;
            if (x < 0) x += p;
            if (y < 0) y += p;
            BigInteger[] coord = { x, y };
            return coord;

        }
    public static BigInteger[] ECaddition(BigInteger[] point1, BigInteger[] point2)
        {
            if (point1[1] == 0) return point2;
            if (point2[1] == 0) return point1;
            if (point1[0] == point2[0]) {
                if (point1[1] == point2[1]) return ECdouble(point1);
                return zero;
            }
            BigInteger slope = ((point2[1] - point1[1]) * inverse(point2[0] - point1[0], p)) % p;
            BigInteger x = (BigInteger.ModPow(slope, 2, p) - point1[0] - point2[0]) % p;
            BigInteger y = ((slope * (point1[0] - x)) - point1[1]) % p;
            if (x < 0) x += p;
            if (y < 0) y += p;
            BigInteger[] coord = { x, y };
            return coord;
        }

    public static BigInteger[] ECMultiplication(BigInteger k, BigInteger[] Gpoint)
        {
            BigInteger[] powerOfTwo = Gpoint;
            BigInteger[] result = zero;
            k %= n; if (k < 0) k += n;
            while (k > 0) {
                if ((k&1) == 1) result = ECaddition(result, powerOfTwo);
                k >>= 1;
                powerOfTwo = ECdouble(powerOfTwo);
            }
            return result;
        }
    public static bool IsOnCurve(BigInteger[] point)
        {
            BigInteger x = point[0] % p; if (x<0) x += p;
            BigInteger y = point[1] % p; if (y<0) y += p;
            return BigInteger.ModPow(y, 2, p) == (BigInteger.ModPow(x, 3, p) + 7) % p;
        }
}

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: BlackHatCoiner on July 28, 2021, 03:18:42 PM
Thank you!

Your code works fine, there's just one thing which slips (?) the process. It adds an additional zero sometimes in front of the x & y and I don't know what's responsible for that.  For example, if I run it with k=1, it returns it properly:
Code:
x: 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y: 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Trying it with k=2, you'll get:
Code:
x: 0C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
y: 1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A

That extra zero (0C60...) shouldn't exist, because obviously, once is hashed with SHA256 it'll give a different result.


Seriously now, I'll say this again; thank you. You wasted your time to write me code? The least I can do is merit you.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: j2002ba2 on July 28, 2021, 03:46:31 PM
Quote from: BlackHatCoiner on July 28, 2021, 03:18:42 PM
Thank you!

Your code works fine, there's just one thing which slips (?) the process. It adds an additional zero sometimes in front of the x & y and I don't know what's responsible for that.  For example, if I run it with k=1, it returns it properly:
Code:
x: 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y: 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Trying it with k=2, you'll get:
Code:
x: 0C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
y: 1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A

That extra zero (0C60...) shouldn't exist, because obviously, once is hashed with SHA256 it'll give a different result.

This is a C# thing, it adds a leading zero when MSB of the top byte is one, something to do with distinguishing between positive and negative numbers. You have to be careful when parsing hex numbers as well: BigInteger.Parse("ff") = -1.

Overall C# is a language with many such intricacies (or I would say stupid choices).

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: pooya87 on July 29, 2021, 03:37:04 AM
Quote from: j2002ba2 on July 28, 2021, 03:46:31 PM
This is a C# thing, it adds a leading zero when MSB of the top byte is one, something to do with distinguishing between positive and negative numbers. You have to be careful when parsing hex numbers as well: BigInteger.Parse("ff") = -1.

Overall C# is a language with many such intricacies (or I would say stupid choices).
This is not a C# thing at all. This is a popular way in computers to indicate positive/negative numbers which the BigInteger class also uses. In fact we are using a similar logic in bitcoin signatures that are encoded using DER encoding (use most significant bit of the most significant byte to indicate sign).

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: j2002ba2 on July 29, 2021, 06:44:08 AM
Quote from: pooya87 on July 29, 2021, 03:37:04 AM
Quote from: j2002ba2 on July 28, 2021, 03:46:31 PM
This is a C# thing, it adds a leading zero when MSB of the top byte is one, something to do with distinguishing between positive and negative numbers. You have to be careful when parsing hex numbers as well: BigInteger.Parse("ff") = -1.

Overall C# is a language with many such intricacies (or I would say stupid choices).
This is not a C# thing at all. This is a popular way in computers to indicate positive/negative numbers which the BigInteger class also uses. In fact we are using a similar logic in bitcoin signatures that are encoded using DER encoding (use most significant bit of the most significant byte to indicate sign).

The most popular way to indicate a negative number is with "-". They are doing a memory dump. Is there a way to print and parse the number properly? In DER encoding it is justified, we get a single long hex digit sequence, but when printing a single number it just looks wrong, and consequently increases the cognitive load. One could write in the source code -0xff, and all is good, but AFAIK there's no (easy) way to parse "-0xff" as a BigInteger.

Title: Re: [C#] Trying to implement EC Multiplication in pure code
Post by: pooya87 on July 29, 2021, 08:27:21 AM
Quote from: j2002ba2 on July 29, 2021, 06:44:08 AM
The most popular way to indicate a negative number is with "-". They are doing a memory dump. Is there a way to print and parse the number properly? In DER encoding it is justified, we get a single long hex digit sequence, but when printing a single number it just looks wrong, and consequently increases the cognitive load. One could write in the source code -0xff, and all is good, but AFAIK there's no (easy) way to parse "-0xff" as a BigInteger.
You are thinking as a "human" not a "computer". In computer there is no "-" there are only bits and when we are representing an arbitrary length octet string there has to be a certain way we represent the sign and that is the most significant bit.
0xff is 0b11111111 and since the most significant bit is set this number is negative.


Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines