KRY-0x06-cli/Program.cs

using System;
using System.Numerics;
using Microsoft.Win32.SafeHandles;

namespace KRY_0x06_cli
{
    class Program
    {
        static void Main(string[] args)
        {
            /* elliptic curve: y^2 % 71 = (x^3 + x + 10) % (prime==71) */

            bool is_same(int[] P1, int[] P2)
            {
                if (P1[0] == P2[0] && P1[1] == P2[1])
                {
                    return true;
                }

                return false;
            }

            int mmi(int a, int nn)
            {
                int i = nn, 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 %= nn;
                if (v < 0) return (v + nn) % nn;
                return v;
            }

            int[] add_point(int[] P1, int[] P2)
            {
                int[] nupoint = new int[2];
                if (is_same(P1, P2))
                {
                    int a = 1;

                    int inverse = mmi((2 * P1[1]), 71);
                    if (inverse == 0)
                    {
                        Console.WriteLine("You have reached infinity!");
                        int[] infinity = P1;
                        return infinity;
                    }
                    else
                    {
                        double bs = Math.Pow(P1[0], 2);
                        int slope = ((3 * Convert.ToInt32(bs)+a) * inverse) % 71;
                        if (slope < 0)
                        {
                            slope = 71 + slope;
                        }
                        int x = (Convert.ToInt32(Math.Pow(slope,2)) - 2 * P1[0]) % 71;
                        if (x < 0)
                        {
                            x = 71 + x;
                        }
                        int y = (-P1[1] + slope * (P1[0] - x)) % 71;
                        if (y < 0)
                        {
                            y = 71 + y;
                        }
                        nupoint[0] = x;
                        nupoint[1] = y;
                        return nupoint;
                    }
                }
                else
                {
                    int bs = P2[0] - P1[0];
                    /*
                     * pre-computation needed here as later on a negative value could be passed to mmi(), which would result in incorrect further computations;
                     * learnt the hard way
                     */
                    if (bs < 0) bs += 71;
                    int inverse = mmi( bs, 71);
                    if (inverse == 0)
                    {
                        Console.WriteLine("You have reached infinity!");
                        int[] infinity = P1;
                        return infinity;
                    }
                    else
                    {
                        int slope = ((P2[1] - P1[1]) * inverse) % 71;
                        if (slope < 0)
                        {
                            slope = 71 + slope;
                        }
                        int x = (Convert.ToInt32(Math.Pow(slope,2)) - P1[0] - P2[0]) % 71;
                        if (x < 0)
                        {
                            x = (71 + x) % 71;
                        }
                        int y = (-P1[1] + slope * (P1[0] - x)) % 71;
                        if (y < 0)
                        {
                            y = 71 + y;
                        }
                        nupoint[0] = x;
                        nupoint[1] = y;
                        return nupoint;
                    }
                }
            }

            void gen_curve(int[] generator)
            {
                int counter = 0;
                int[] point = generator;
                while (add_point(point, generator) != point)
                {
                    Console.WriteLine($"[{counter}]\t{point[0]},{point[1]}");
                    counter++;
                    point = add_point(point, generator);
                }
            }

            int[] p1 = {3, 18};
            int[] p2 = {7, 17};

            Console.WriteLine($"P: [{p1[0]},{p1[1]}]\nQ: [{p2[0]},{p2[1]}]");
            Console.WriteLine("P + Q  = R");
            int[] R = add_point(p1, p2);
            Console.WriteLine($"R: [{R[0]},{R[1]}]");
            Console.WriteLine("P + P  = 2P");
            int[] twoP = add_point(p1, p1);
            Console.WriteLine($"R: [{twoP[0]},{twoP[1]}]");
            Console.WriteLine("Elliptic curve:");
            int[] generator = {3, 18};
            gen_curve(generator);

        }
    }
}