[C#] Trying to implement EC Multiplication in pure code

[BlackHatCoiner]

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:

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:

[1714009675]

1714009675

[1714009675]

1714009675

[1714009675]

1714009675

[1714009675]

1714009675

[1714009675]

1714009675

[j2002ba2]

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)

[BlackHatCoiner]

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.

[j2002ba2]

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.

[BlackHatCoiner]

maybe you should use a library.

For that particular function? For modinv only?

[ignacioruiz23]

I'm working in something like at the university. Try to check if c# doesn't round any result.

[j2002ba2]

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.

[archyone]

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

[vjudeu]

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.

[Coding Enthusiast]

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 with a wrapper in C#.

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 namespace which is a very simple implementation of ECC.
Private key to public key code would be MultiplyByG(BigInteger k) 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 namespace in FinderOuter.

[NotATether]

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?

[BlackHatCoiner]

Private key to public key code would be MultiplyByG(BigInteger k) 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;

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.

[Coding Enthusiast]

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 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 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();

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

[HCP]

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;
        }

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.

[BlackHatCoiner]

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

[BlackHatCoiner]

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]

[COBRAS]

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

[j2002ba2]

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

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;
        }

[BlackHatCoiner]

...

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. 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. 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.

[j2002ba2]

...

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. 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 ^.

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;
        }
}