Developers Club geek daily blog

1 year, 2 months ago
The benefit of approach on the basis of elliptic curves in comparison with a problem of the factorization of number used in RSA, or the problem of integer logarithming applied in Diffie-Hellman's algorithm and in DSS is that in this case equivalent protection at smaller key length is provided.

Generally the equation of an elliptic curve E in the field of real numbers of R has an appearance:

— y^2+a1*x*y+a3*y = x^3+a2*x^2+a4*x+a6

or in case of a final ring of deductions of Z|n:

— y^2+a1*x*y+a3*y = x^3+a2*x^2+a4*x+a6 mod N

Let's set for ourselves the task of visualization of an elliptic curve.

Elliptic curve E in the field of real numbers of R


If the elliptic curve E is considered in the field of real numbers of R, then creation of the diagram can be described, using only knowledge of algebra and geometry of the senior classes of school

arguments of N a1 a2 a3 a4 a6 xmin xmax
  1. We select the range [xmin — xmax] of argument x
  2. We note on the selected range of argument x necessary number of x1 values..., xN
  3. Each of x1 values..., x^3+a2*x^2+a4*x+a6 is substituted xN in y^2+a1*x*y+a3*y equation = and we receive the normal square equation of argument of y
  4. We find roots of the square equation of argument of y
  5. If the square equation of argument of y has solutions, then we add two points on the diagram
  6. We connect lines all "upper" points on the diagram and all "lower" points on the diagram


— a=a(x)=1
— b=b(x) =a1*x+a3
— c=c (x)=-(x^3+a2*x^2+a4*x+a6)

— ayy+by+c=0
— D=bb-4ac
— y1=(-b-sqrt(D)) / (2a)
— y2= (-b+sqrt (D)) / (2a)

Implementation


        private void button1_Click(object sender, EventArgs e)
        {
            LockForm();

            // Параметры эллиптической кривой
            double a1 = GetA1();
            double a2 = GetA2();
            double a3 = GetA3();
            double a4 = GetA4();
            double a6 = GetA6();

            // Диапазон изменения переменной X и количество интервалов
            double xmin = GetXmin();
            double xmax = GetXmax();
            ulong n = GetN();

            // http://stackoverflow.com/questions/10622674/chart-creating-dynamically-in-net-c-sharp
            var series1 = new Series
            {
                Name = "Series1",
                Color = Color.Black,
                IsVisibleInLegend = false,
                IsXValueIndexed = true,
                ChartType = SeriesChartType.Line
            };

            var series2 = new Series
            {
                Name = "Series2",
                Color = Color.Black,
                IsVisibleInLegend = false,
                IsXValueIndexed = true,
                ChartType = SeriesChartType.Line
            };

            var sb = new StringBuilder();
            var sb1 = new StringBuilder();
            sb.AppendLine("y^2+a1*x*y+a3*y = x^3+a2*x^2+a4*x+a6");
            sb.AppendLine("a1=" + a1);
            sb.AppendLine("a2=" + a2);
            sb.AppendLine("a3=" + a3);
            sb.AppendLine("a4=" + a4);
            sb.AppendLine("a6=" + a6);
            sb.AppendLine();
            sb.AppendLine("# X Y1 Y2");
            sb1.AppendLine("# X Y1 Y2");
            for (ulong i = 0; i <= n; i++)
            {
                double x = (xmin*(n - i) + xmax*i)/n;

                // Рассчитываем параметры квадратичного уравнения для данного X
                const double a = 1;
                double b = a1*x + a3;
                double c = -(x*x*x + a2*x*x + a4*x + a6);

                // По формуле за шестой класс средней школы вычисляем решение квадратичного уравнения
                double d = b*b - 4*a*c;
                if (d < 0) continue;

                double y1 = (-b - Math.Sqrt(d))/(2*a);
                double y2 = (-b + Math.Sqrt(d))/(2*a);

                series1.Points.AddXY(x, y1);
                series2.Points.AddXY(x, y2);

                sb.AppendLine(x + " " + y1 + " " + y2);
                sb1.AppendLine(x + " " + y1 + " " + y2);
            }

            // Выдаём отчёт о проделанной работе
            SetChart(series1, series2);
            SetReport(sb.ToString());
            SetReport1(sb1.ToString());

            UnlockForm();
            ActivatePage(2);
        }

Result


Эллиптическая кривая Е в поле действительных чисел R

Elliptic curve E in a ring of deductions of Z|n


If the elliptic curve E is considered for a final ring of deductions of Z|n, then the problem of visualization of an elliptic curve is represented more complex challenge.
In this case it is possible to offer standard easily programmable algorithm of rendezvous of connection of values of the left and right members of equation of an elliptic curve E:

— arguments of N a1 a2 a3 a4 a6

  1. to cache in tables of value of the left and right members of equation
  2. to construct indexes for columns of tables
  3. to make consolidation of tables on calculated to values
  4. to represent the received points after consolidation of tables on the diagram.


For work with cached values of the left and right members of equation of an elliptic curve E, we will use DBMS which will allow to perform most optimum work on indexation of columns of tables and consolidation of these tables.

t1
x key1 = x^3+a2*x^2+a4*x+a6 mod N
1 …
2 …
3 …

N rN

t2
y key2 = y^2+a3*y mod N
1 …
2 …
3 …

N lN

t3
x y key3=a1*x*y mod N
1 1 …
1 2 …

N N …

if (a1! =0 mod N) select t1.x, t2.y from t1, t2, t3 where (key1=key2+key3 or key1+N=key2+key3) and t1.x=t3.x and t2.y=t3.y
if (a1 == 0 mod N) select t1.x, t2.y from t1, t2 where key1=key2

Implementation


— DBMS — SQLite
        private void button1_Click(object sender, EventArgs e)
        {
            LockForm();

            // Параметры кольца вычетов Z|n
            var n = GetN();

            // Параметры эллиптической кривой
            var a1 = GetA1();
            var a2 = GetA2();
            var a3 = GetA3();
            var a4 = GetA4();
            var a6 = GetA6();

            // http://stackoverflow.com/questions/9173485/how-can-i-create-an-in-memory-sqlite-database
            var connection = new SQLiteConnection("Data Source=:memory:");
            connection.Open();

            // Создаём таблицы
            string[] sqls1 =
            {
                "CREATE TABLE t1 (x INTEGER , key1 INTEGER )",
                "CREATE TABLE t2 (y INTEGER , key2 INTEGER )",
                "CREATE TABLE t3 (x INTEGER , y INTEGER , key3 INTEGER )"
            };

            foreach (var sql in sqls1)
                new SQLiteCommand(sql, connection).ExecuteNonQuery();

            // Заполняем таблицы начальными значениями
            for (ulong x = 0; x < n; x++)
            {
                var x2 = (x*x)%n;
                var x3 = (x2*x)%n;
                var a2X2 = (a2*x2)%n;
                var a4X = (a4*x)%n;
                var key1 = (x3 + a2X2 + a4X + a6)%n;
                var sql = string.Format("INSERT INTO t1 (x, key1) VALUES ({0},{1})", x, key1);
                new SQLiteCommand(sql, connection).ExecuteNonQuery();
            }

            for (ulong y = 0; y < n; y++)
            {
                var y2 = y*y%n;
                var a3Y = (a3*y)%n;
                var key2 = (y2 + a3Y)%n;
                var sql = string.Format("INSERT INTO t2 (y, key2) VALUES ({0},{1})", y, key2);
                new SQLiteCommand(sql, connection).ExecuteNonQuery();
            }

            if ((a1%n) != 0)
                for (ulong x = 0; x < n; x++)
                {
                    var a1X = (a1*x)%n;
                    for (ulong y = 0; y < n; y++)
                    {
                        var key3 = (a1X*y)%n;
                        var sql = string.Format("INSERT INTO t3 (x, y, key3) VALUES ({0},{1},{2})", x, y, key3);
                        new SQLiteCommand(sql, connection).ExecuteNonQuery();
                    }
                }

            // Создаём индексы для таблиц
            string[] sqls2 =
            {
                "CREATE INDEX t1key1 ON t1 (key1)",
                "CREATE INDEX t2key2 ON t2 (key2)",
                "CREATE INDEX t3key3 ON t3 (key3)",
                "CREATE UNIQUE INDEX t1x ON t1 (x)",
                "CREATE UNIQUE INDEX t2y ON t2 (y)",
                "CREATE INDEX t3x ON t3 (x)",
                "CREATE INDEX t3y ON t3 (y)"
            };

            foreach (var sql in sqls2)
                new SQLiteCommand(sql, connection).ExecuteNonQuery();

            // http://stackoverflow.com/questions/10622674/chart-creating-dynamically-in-net-c-sharp
            var series1 = new Series
            {
                Name = "Series1",
                Color = Color.Black,
                IsVisibleInLegend = false,
                IsXValueIndexed = true,
                ChartType = SeriesChartType.Point
            };

            // Выполняем JOIN запрос и получаем результаты
            // Чем дороже DBMS тем лучше алгоритмы она использует для оптимизации запросов
            var select = ((a1%n) == 0)
                ? "SELECT t1.x,t2.y FROM t1, t2 WHERE key1=key2"
                : "SELECT t1.x,t2.y FROM t1, t2, t3 WHERE (key1=key2+key3 or key1+" + n +
                  "=key2+key3) AND t1.x=t3.x AND t2.y=t3.y";
            var reader = new SQLiteCommand(select, connection).ExecuteReader();
            var sb = new StringBuilder();
            var sb1 = new StringBuilder();
            sb.AppendLine("y^2+a1*x*y+a3*y = x^3+a2*x^2+a4*x+a6 mod n");
            sb.AppendLine("n=" + n);
            sb.AppendLine("a1=" + a1);
            sb.AppendLine("a2=" + a2);
            sb.AppendLine("a3=" + a3);
            sb.AppendLine("a4=" + a4);
            sb.AppendLine("a6=" + a6);
            sb.AppendLine();
            sb.AppendLine("# X Y");
            sb1.AppendLine("# X Y");
            while (reader.Read())
            {
                var x = Convert.ToInt32(reader[0]);
                var y = Convert.ToInt32(reader[1]);
                series1.Points.AddXY(x, y);
                sb.AppendLine(x + " " + y);
                sb1.AppendLine(x + " " + y);
            }

            // Выдаём отчёт о проделанной работе
            SetChart(series1);
            SetReport(sb.ToString());
            SetReport1(sb1.ToString());
            connection.Close();

            UnlockForm();
            ActivatePage(2);
        }

Result


Эллиптическая кривая Е в кольце вычетов Z|n

As was to be shown

Source codes of programs are available to the address https://github.com/dprotopopov/mssove3

This article is a translation of the original post at habrahabr.ru/post/274473/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus