### Developers Club geek daily blog

1 year, 5 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);

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

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

UnlockForm();
ActivatePage(2);
}
``````

## 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 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");
{
sb.AppendLine(x + " " + y);
sb1.AppendLine(x + " " + y);
}

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

UnlockForm();
ActivatePage(2);
}
``````

### Result

As was to be shown

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