Сегодня мы попытаемся сделать еще один шаг в сторону криптографии, но уже не в попытке сокрытия данных под видом «случайного шума» из байтов, генерируемого современными алгоритмами шифрования, а в несколько ином направлении. В этой статье мы прикоснемся к таким понятиям как доверие и подтверждение подлинности, познакомившись (впервые в этом блоге) с асимметричной криптографией и эллиптическими кривыми.
Эллиптические кривые — это очень привлекательный, интересный и сложный математический объект, поэтому сами механизмы на основании, которых будут работать механизмы подписания и проверки, мы объясним с необходимым минимализмом, подробности вы сможете найти в предложенных ссылках в конце статьи.
Для того, чтобы погрузиться в основы асимметричной криптографии, и прежде чем начать рассмотрение того, что было описаны выше, нам необходимо сделать небольшой экскурс в теорию. Прежде всего, стоит понять, что дальнейшие операции будут производиться на очень больших числах, числах сравнимых по порядку или даже больше, чем 2 ^^ 256, связано это как с определенными требованиями, которые накладываются на размеры электронной подписи, так и с некоторыми соображениями относительно сложности поиска ключей, а также их общего количества.
Мы с вами будем рассматривать такое понятие, как электронная подпись, и частично затронем некоторые из понятий асимметричной криптографии, т.е. криптографии с двумя ключами — открытым и закрытым ключом, и для этого мы введем ряд понятий.
Открытый ключ — это ключ, который условно говоря известен всем, и может быть использован как для проверки корректности подписи, так и для шифрования чего-либо в адрес владельца закрытого ключа. Закрытый ключ — это ключ, известный только владельцу, с помощью которого производиться подписание или расшифровка чего-либо, направленного в адрес владельца. В настоящий момент существует несколько схем, а отсюда также появляется и множество реализаций асимметричного шифрования, но в этой статье мы сфокусируемся на самом простом (и наиболее понятном из них) — это криптография на эллиптических кривых.
Поэтому помимо первых двух понятий, нам потребуется и набор определений для эллиптической криптографии.
Эллиптическая кривая — это некая кривая, которая в общем случае задается следующим уравнением:
y ^^ 2 = x ^^ 3 + a * x + b
где a и b — это коэффициенты кривой, причем такие, чтобы выполнялось соотношение:
4 * (a ^^ 3) + 27 * (b ^^ 2) != 0
Данное требование должно соблюдаться для исключения особых кривых и обеспечения криптостойкости используемой системы.
Также стоит учесть то, что используются очень большие числа для представления точек эллиптической кривой и то, что для всех операций с числами вместо чисел с плавающей точкой применяется арифметика по модулю. Но сама арифметика по модулю, это только малая часть хорошо проработанного математически ландшафта теории эллиптических кривых, фактически все вычисления протекают здесь в определенных конечных полях.
Чтобы не забивать статью математическими нюансами, а также чтобы не дезориентировать в вопросах математики, мы только коротко упомянем конечные поля и те операции, которые будут использоваться — а за деталями можно обратиться в интернет или в работы упомянутые в ссылках.
На самом деле, в реализации нам не потребуется каких-либо операций, кроме сложения, умноженияи иногда сравнения, но данные операции будут проходит по некоторому модулю (т.е. все операции осуществляются с учетом остатка от деления на некоторое число) и на них накладываются некоторые требования. В частности, остатки от деления на некоторое очень большое число (называется оно p или модуль конечного поля) образовывали группу, для которой обязательно наличие единичного элемента (т.е. начальной точки отсчета), обратного элемента (это мы рассмотрим чуть далее), а также выполняется свойство ассоциативности(т.е. когда для некоторых a, b и c выполняется (a + b) + c = a + (b + c)) и замыкания(если a и b принадлежат к конечному полю, то и a + bтакже к нему принадлежит).
Обычно, число p — это некоторое большое число, которое еще обычно является простым или числом Мерсенна (т.е. такое число, которое имеет некоторое представление, подробнее о числах Мерсенна тут), и это число также является одним из параметров используемой эллиптической кривой. Так как вычисления идут по модулю p(т.е. внутри конечного поля размерностью p), то у такой кривой количество точек, которые можно использовать, ограничено и это число называют порядком кривой и обозначают как n.
По сути, это все параметры которые необходимы для описания самой эллиптической кривой, которое можно сделать следующим образом, поскольку с самой кривой какие-либо операции не производятся:
/// псевдоним
alias BigInteger = BigInt;
/// Используемая эллиптическая кривая
class EllipticCurve
{
private {
BigInt _a, _b, _p, _n;
}
this(BigInteger a, BigInteger b, BigInteger p, BigInteger n)
{
_a = a;
_b = b;
_p = p;
_n = n;
}
@property {
BigInteger a()
{
return _a;
}
BigInteger b()
{
return _b;
}
BigInteger p()
{
return _p;
}
BigInteger n()
{
return _n;
}
}
override string toString()
{
return format(
`EllipticCurve(a = %s, b = %s, p = %s, n = %s)`,
_a,
_b,
_p,
_n
);
}
}Данный код не содержит ничего нового, и содержит то, что можно назвать дата-классом: т.е. классом, который только содержит данные, но не меняет их никак.
Кроме того, стоит повторно обратится к понятию конечного поля, и хоть мы его раскрывать не будем (это достаточно сложный математический объект) и упомянем тот факт, что сами точки эллиптической кривой являются элементами такого поля, если ввести расчеты в модулярной (модульной) арифметике. Стоит заметить, что именно модули (т.е. остатки от деления) приводят к формированию конечного поля, благодаря тем свойствам, что были описаны ранее, но именно одно из них является особенно важным — наличие обратного элемента. Именно это свойство важно из-за того, что в подписании и проверке электронной подписи применяется замена деления на умножение на обратный элемент.
Обратный элемент или мультипликативно обратный элемент в поле вычетов m — это некое число q. Пусть это число q обратно некому числу p, которое выбрано нами, если для любого x, принадлежащего полю вычетов (остатков), выполнимо следующее условие:
y = x × p (mod m) <=> x = y × q (mod m) <=> p × q = 1 (mod m)
где <=> — знак эквивалентности (или равносильности), т.е. здесь одно и то же условие, только записано по разному. И еще один момент, буквенные обозначения, использованные при определении этого понятия являются локальными для данного определения и не имеют отношения к ранее введенными обозначениями, которые будут по прежнему применяться далее.
Для поиска обратного элемента, есть замечательный и хорошо изученный метод, который называется расширенным алгоритмом Евклида, и в стандартной библиотеке D, он к сожалению, не реализован. Однако, благодаря RosettaCode и небольшим усилиям по доработке реализовать алгоритм Евклида можно в несколько строк:
/// обратный элемент в конечном поле по модулю b
T modInverse(T)(T a, T b) pure nothrow
{
if (b == 1)
{
return cast(T) 1;
}
T b0 = b, x0 = 0, x1 = 1;
while (a > 1)
{
immutable q = a / b;
auto t = b;
b = a % b;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
return (x1 < 0) ? (x1 + b0) : x1;
}Эта скромная функция потребуется для реализации нескольких базовых операций над точками эллиптической кривой, поскольку она неплохо работает с разными типами, в том числе и с BigInt.
Точкой на эллиптической кривой мы будем называть пару чисел (x; y), которые отражают координаты некоторой точки на эллиптической кривой. Помимо этого, существуют две «специальные» точки: бесконечно удаленная точка, т.е. точка почти буквально находящаяся в бесконечности (обозначается как O); и «генерирующая точка» кривой (обозначается как G) — такая точка, при умножении чисел на которую гарантировано получаются точки, лежащие на заданной кривой. В основном, нас будет интересовать генерирующая точка, так как она позволяет осуществить обмен секретным ключом двум сторонам при наличии канала с подслушиванием или для генерации публичного (открытого) ключа из приватного (закрытого).
Для создания электронной подписи на эллиптических кривых требуется реализовать следующие операции над точками эллиптической кривой: сложение точки с точкой, скалярное умножение точки на число, а также проверка равенства двух точек друг другу. Сложение двух точек, назовем их P и Q, и обозначим их координаты (xp; yp) и (xq; yq), тогда сложение двух точек кривой можно выразить следующими формулами:
P + Q = -R (точка -R, поскольку ответ симметричен относительно оси Y) alpha = (yq - yp) / (xq - xp) xr = -(alpha ^^ 2) - xp - xq yr = -yp - alpha(xp - xr)
а умножение точки на скаляр (число) можно выразить через повторяющееся сложение. Но умножение реализовать не так то просто, поскольку используемые нами числа очень велики, то представление сложения через простое повторение сложение в цикле приведет к значительному увеличению срока вычислений, и поэтому реализацию умножения проще всего сделать через известный вариант под названием «сложение-удвоение».
Вся суть этого способа в том, что используются преимущества компьютеров и двоичного представления того множителя, на который производится умножение.
Допустим, мы умножаем на некоторое число A и умножаем его на некоторое число B. Распишем их произведение C следующим образом, предположив что Aможно удобно и быстро представить в виде суммы степеней двойки от 0 до n:
C = A * B = (2 ^^ n) * B + (2 ^^ (n - 1)) * B + (2 ^^ (n - 2)) * B + ... + (2 ^^ 0) * B
т.е. для эффективного умножения по данному алгоритму, нам нужно выполнить примерно такую цепочку операций:
Вычисляем B; Удваиваем его, для того чтобы вычислить 2 * B; Складываем B и 2 * B для того, чтобы получить (2 ^^ 1) * B + (2 ^^ 0) * B; Удваиваем 2 * B, чтобы получить (2 ^^ 2) * B; Складываем с результатом, чтобы получить (2 ^^ 2) * B + (2 ^^ 1) * B + (2 ^^ 0) * B; Повторяем "размотку алгоритма" дальше по аналогии, до достижения (2 ^^ n) * B.
Похожий алгоритм для умножения на некое число точки эллиптической кривой будет использоваться в коде для описания точки кривой в данной статье, который мы приведем чуть позднее.
В принципе, изложенной теории уже достаточно для того, чтобы реализовать одну из необходимых для этого скромного проекта сущностей, а именно точку эллиптической кривой.
Для представления точки на заданной эллиптической кривой реализуем класс под названием EllipticPoint, внутри которого в качестве полей будут храниться: координаты точки — x и y, «конфигурация эллиптической кривой» — ее коэффициенты (aи b), а также ее порядок — nи модуль конечного поля p(или FG). Исходя из этого, у класса будет два конструктора: один принимает координаты точки и эллиптическую кривую, а второй — принимает уже существующую точку и на ее основе конструирует новую. Также, в целях отладки, сделано удобное отображение точки через перегруженный метод toString. Данный класс применяется не только для хранения данных о некоторой произвольной точке эллиптической кривой, но может быть использован для операций над точками: сложение точки с точкой (метод add), удвоение точки (метод multiplyByTwo, который нужен для реализации алгоритма «удвоения-сложения») и также умножение точки на некооторое произвольное число (метод multiply).
Реализация использует упомянутые выше формулы для работы с точками, механизм удвоения-сложения, а также расширенный метод Евклида в замене деления умножением на мультипликативно обратный элемент:
class EllipticPoint
{
public {
// координаты точки на кривой
BigInteger x, y;
// параметры кривой - a, b; а также FG (он же - p) - модуль конечного поля
BigInteger a, b, FG;
// порядок кривой
BigInteger n;
}
this(EllipticPoint lhs)
{
x = lhs.x;
y = lhs.y;
a = lhs.a;
b = lhs.b;
FG = lhs.FG;
n = lhs.n;
}
this(BigInteger x, BigInteger y, EllipticCurve curve)
{
this.x = x;
this.y = y;
a = curve.a;
b = curve.b;
FG = curve.p;
n = curve.n;
}
this()
{
x = 0;
y = 0;
a = 0;
b = 0;
FG = 0;
n = 0;
}
static
{
/// сложение двух точек lhs и rhs
EllipticPoint add(EllipticPoint lhs, EllipticPoint rhs)
{
EllipticPoint p3 = new EllipticPoint;
p3.a = lhs.a;
p3.b = lhs.b;
p3.FG = lhs.FG;
p3.n = lhs.n;
BigInteger dy = rhs.y - lhs.y;
BigInteger dx = rhs.x - lhs.x;
if (dx < 0)
{
dx += lhs.FG;
}
if (dy < 0)
{
dy += lhs.FG;
}
BigInteger m = (dy * dx.modInverse(lhs.FG)) % lhs.FG;
if (m < 0)
{
m += lhs.FG;
}
p3.x = (m * m - lhs.x - rhs.x) % lhs.FG;
p3.y = (m * (lhs.x - p3.x) - lhs.y) % lhs.FG;
if (p3.x < 0)
{
p3.x += lhs.FG;
}
if (p3.y < 0)
{
p3.y += lhs.FG;
}
return p3;
}
/// сложение точки c собой же (иными словами, умножение ее на два)
static EllipticPoint multiplyByTwo(EllipticPoint lhs)
{
EllipticPoint rhs = new EllipticPoint;
rhs.a = lhs.a;
rhs.b = lhs.b;
rhs.FG = lhs.FG;
rhs.n = lhs.n;
BigInteger dy = 3 * lhs.x * lhs.x + lhs.a;
BigInteger dx = 2 * lhs.y;
if (dx < 0)
{
dx += lhs.FG;
}
if (dy < 0)
{
dy += lhs.FG;
}
BigInteger m = (dy * dx.modInverse(lhs.FG)) % lhs.FG;
rhs.x = (m * m - lhs.x - lhs.x) % lhs.FG;
rhs.y = (m * (lhs.x - rhs.x) - lhs.y) % lhs.FG;
if (rhs.x < 0)
{
rhs.x += lhs.FG;
}
if (rhs.y < 0)
{
rhs.y += lhs.FG;
}
return rhs;
}
/// умножение точки на число x, по сути своей представляет x сложений точки самой с собой
EllipticPoint multiply(BigInteger x, EllipticPoint lhs)
{
EllipticPoint temp = lhs;
x = x - 1;
while (x != 0)
{
if ((x % 2) != 0)
{
if ((temp.x == lhs.x) || (temp.y == lhs.y))
{
temp = multiplyByTwo(temp);
}
else
{
temp = EllipticPoint.add(temp, lhs);
}
x = x - 1;
}
x = x / 2;
lhs = multiplyByTwo(lhs);
}
return temp;
}
}
/// Строковое представление точки на кривой
override string toString()
{
return format("Point(x = %s, y = %s)", x, y);
}
}Все операции выполняются по модулю p (FG).
При наличии такого «мощного» класса, минимальный комплект операций необходимый для реализации алгоритмов цифровой подписи практически готов. Однако, прежде чем переходить к реализации данных алгоритмов и их теоретической основе, стоит сделать важное дополнение, которое неявно будет присутствовать во всех остальных понятиях и коде. Для асимметричной криптографии, к которой относится в частности, цифровая подпись, важны два понятия — открытый (публичный) и закрытый (приватный ключ), и оба этих ключа это просто ОЧЕНЬ БОЛЬШИЕ ЧИСЛА, так же как и результат подписания чего-либо электронной подписью. Именно из-за того, что ключи и подпись — это просто числа, вытекают механизмы подписания, а также достоинства/недостатки алгоритмов электронной цифровой подписи (ЭЦП) на эллиптических кривых.
Поскольку, мы решили сосредоточить свое внимание на подписи на эллиптических кривых, то в качестве публичного ключа будет некоторая точка на эллиптической кривой (ее координаты выступают в роли открытого ключа), которую можно получить из приватного ключа (в роли которого обычно выступает случайно сгенерированное большое число, которое держится в секрете) простым умножением на генерирующую точку:
/// Генерирующая точка кривой
alias GeneratingPoint = EllipticPoint;
/// Генерация публичного ключа из приватного
auto fromPrivateKey(BigInteger privateKey, GeneratingPoint gp)
{
return GeneratingPoint.multiply(privateKey, gp);
}Предполагается, что приватный ключ известен только владельцу, а генерирующая точка (далее — GP) и параметры используемой кривой известны всем, кто применяет схему подписания на эллиптических кривых. И при таком подходе, если считать что есть некоторое сообщение M (которое также представляет собой ОЧЕНЬ БОЛЬШОЕ ЧИСЛО), можно заверить электронной цифровой подписью при помощи такого алгоритма:
1. Для создания одной подписи генерируем некоторое случайное число k, которое обязательно должно принадлежать диапазону [1; n-1] (n - это порядок кривой) 2. Вычисляем точку R: R = GP * k 3. Вычисляем число r: r = Rx mod n где Rx - x координата точки R и если r = 0, то повторяем шаги с 1 по 3. 4. Вычисляем число s: s = (M + r * privateKey) * inverse_k mod n где privateKey - закрытый ключ, а inverse_k mod n - это обратное для k число по модулю n. 5. Объединяем числа r и s
Объединение чисел полученное на последнем шаге — и есть цифровая подпись для сообщения M.
Для представления ЭЦП введем класс EllipticCurveDigitalSign, который будет содержать в себе оба числа r и s, а также позволит вывести «более наглядное» шестнадцатеричное представление подписи, которое просто «склеивает» (конкатенирует) оба числа:
/// Цифровая подпись
class EllipticCurveDigitalSign
{
private {
BigInteger _r, _s;
}
this(BigInteger r, BigInteger s)
{
_r = r;
_s = s;
}
@property {
BigInteger r()
{
return _r;
}
BigInteger s()
{
return _s;
}
}
override string toString()
{
return (r.toHex ~ s.toHex)
.replace("_", "")
.toLower;
}
}И при наличии удобного дата-класса для подписи функция подписания signWithEllipticCurve, которая принимает сообщение — message, приватный ключ — privateKey, и генерирующую точку — g:
/// Проставить подпись
auto signWithEllipticCurve(BigInteger message, BigInteger privateKey, GeneratingPoint g)
{
BigInteger k = randomBigInteger(g.n);
EllipticPoint rPoint = EllipticPoint.multiply(k, g);
BigInteger r = rPoint.x % g.n;
while (r == 0)
{
k = randomBigInteger(g.n);
rPoint = EllipticPoint.multiply(k, g);
r = rPoint.x % g.n;
}
auto s = modInverse(k, g.n) * (message + r * privateKey) % g.n;
return new EllipticCurveDigitalSign(r, s);
}Таким образом, можно подписать любое сообщение с помощью простой функции, однако, просто подписания в большинстве случаев недостаточно. Порой необходимо убедиться в том, что некоторая подпись, которой было подписано сообщение, является верной и не была подделана.
Предположим тогда, что у нас есть некое сообщение M, а также подпись (r, s), которой оно было подписано и публичный ключ, на основе которого была выполнена подпись, тогда алгоритм проверки подписи выглядит так:
1. Вычисляем число U: U = M * inverse_s mod n где inverse_s mod n - число обратное для s по модулю n, n - порядок кривой 2. Вычисляем число V: V = r * inverse_s mod n 3. Вычисляем точку C: C = U * GP + V * publicKey где GP - генерирующая точка, publicKey - открытый ключ 4. Проверяем равенство: Cx mod n = r где Cx - x координата точки C 5. Если равенство выполнено, то подпись корректна; иначе подпись некорректна или подделана.
Реализация такого алгоритма выражена функцией verifyWithEllipticCurve, которая принимает подпись — signature, сообщение — message, публичный ключ — publicKeyи генерирующую точку — g:
/// Проверить подпись
auto verifyWithEllipticCurve(EllipticCurveDigitalSign signature, BigInteger message, EllipticPoint publicKey, GeneratingPoint g)
{
BigInteger r = signature.r;
BigInteger s = signature.s;
BigInteger sInverse = modInverse(s, g.n);
auto c0 = EllipticPoint.multiply(message * sInverse % g.n, g);
auto c1 = EllipticPoint.multiply(r * sInverse % g.n, publicKey);
return EllipticPoint.add(c0, c1).x == r;
}И это весь необходимый минимум для подписания/проверки на эллиптических кривых.
Однако, подписание сообщения и его же проверка в таком виде являются бесполезными и годятся разве что в качестве учебных примеров. На деле же приходится проверять подписи не у отдельно полученных чисел, которыми представлены сообщения, а у достаточно больших объемов данных, размерность которых исчисляется миллионами (и более) таких чисел. Из-за применения длинной арифметики (она же числа BigInt) даже простое подписание файла — это вычислительно затратная процедура и поэтому, для подписания/проверки придуман замечательный трюк, который сводит вычислительную сложность практически на нет. Трюк состоит в том, чтобы всегда в качестве источника данных использовать нечто что всегда дает результат примерно одного и того же размера и при этом «влезает» в одно сообщение. Таким источником служит обычная хэш-функция, выход которой генерирует сообщение, которое можно использовать в рассмотренных алгоритмах подписания и верификации подписи.
Поступим точно также, а в качестве хэш-функции возьмем уже хорошо известный нам вариант — SHA-256:
Схема проста: тут две функции, первая создает подпись, а вторая — ее проверяет. Берется хэш SHA-256 от файлового буфера, перегоняется в массив байтов, и в качестве массива байтов передается в конструктор для структуры BigInt. Данная структура содержит в себе представление очень больших чисел и находится в модуле std.bigint, и используется в качестве одного из аргументов в уже знакомых нам функциях для подписи/проверки сообщения.
Но… В силу сложности математического аппарата, а также наличия специфических требований к эллиптическим кривым, необходимо как-то найти параметры конфигурации для кривой, а также значения координат для генерирующей точки. И тут, мы приходим к довольно спорному моменту относительно криптостойкости и потенциальных проблемах в схемах эллиптической криптографии. А дело все в том, что надежных кривых известно не так много, и почти все они стандартизированы Американским Институтом Стандартов (NIST), который печально прославился с некоторыми одобренными стандартами в области криптографии.
Поэтому в качестве кривой мы решили проэкспериментировать с кривой известной под названием sec256k1, которая применяется в Bitcoin. Ее «конфигурационные параметры» и сама кривая выглядят так:
/// коэффициент a
auto a = BigInt(0);
/// коэффициент b
auto b = BigInt(7);
/// модуль конечного поля
auto p = BigInt("115792089237316195423570985008687907853269984665640564039457584007908834671663");
/// координата x генерирующей точки
auto x = BigInt("55066263022277343669578718895168534326250603453777594175500187360389116729240");
/// координата y генерирующей точки
auto y = BigInt("32670510020758816978083085130507043184471273380659243275938904335757337482424");
/// порядок кривой (т.е количество ее точек)
auto n = BigInt("115792089237316195423570985008687907852837564279074904382605163141518161494337");
/// кривая
auto sec256k1 = new EllipticCurve(a, b, p, n);
/// генерирующая точка
auto g = new EllipticPoint(x, y, sec256k1);Прежде чем, мы покажем вам весь код экспериментального примера, в качестве бонуса мы вам расскажем одну историю…
Жили-были на свете два обычных сознательных гражданина, одного из них звали Алиса, а другого гражданина — Боб. И был у этих двоих канал связи, хороший такой канал, с высокой пропускной способностью, и все было замечательно. Однажды заметили два этих гражданина, что их канал активно прослушивается и небезопасно стало по нему что-либо передавать. Был у Боба и Алисы надежный алгоритм шифрования симметричный, и ключи надежные были, да встретится для того, чтобы обменяться ими возможности не было.
Да и канала надежного, что бы ключи передать тоже не было, однако, была у них одна общая эллиптическая кривая sec256k1 и одна генерирующая точка…
Взяла Алиса и сгенерировала случайное большое dA, умножила его на генерирующую точку g, и результат Ha, отправила Бобу по их каналу. А Боб, разгадав замысел Алисы, создал свое случайное большое число dB, умножил его на генерирующую точку g, и отправил результат Hb Алисе. Далее, каждый из них умножил полученные от партнера значения на свое случайное число (dA * Hb — для Алисы и dB * Ha для Боба), которое было создано ранее — и каждый из них получил один и тот же общий ключ, а взломщик остался с носом, так как получил только сами числа Ha и Hb, знание которых не приводит к получению общего ключа…
История, конечно так себе, но в ней есть реальная идея: dA * Hb = dB * Ha, и так действительно можно совместными усилиями создать ключ в условиях прослушивания или разделить общий секрет…
Мы рассказали вам эту историю, поскольку включили эту схему в протокол эксперимента с криптографией на эллиптических кривых, который содержит помимо кривой Bitcoin описание еще одной кривой, которая применяется в протоколе SSH:
private{ import std.bigint; import std.conv : to; import std.digest; import std.digest.sha; import std.format; import std.random : Random, uniform, unpredictableSeed; import std.stdio; import std.string : replace, strip, toLower; // псевдоним alias BigInteger = BigInt; // обратный элемент в конечном поле по модулю b T modInverse(T)(T a, T b) pure nothrow { if (b == 1) { return cast(T) 1; } T b0 = b, x0 = 0, x1 = 1; while (a > 1) { immutable q = a / b; auto t = b; b = a % b; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } return (x1 < 0) ? (x1 + b0) : x1; } auto randomBigInteger(BigInteger b) { BigInteger result = "0"; auto countOfBytes(BigInteger number) { ulong count = 0; while (number != 0) { number >>= 8; count++; } return count; } auto generateRandomBytes(ulong number) { auto rng = Random(unpredictableSeed); ubyte[] r; foreach (e; 0..uniform(0, number)) { r ~= cast(ubyte) uniform(0, 256, rng); } return r; } auto numberOfBytes = countOfBytes(b); auto isInRange(BigInteger number) { return ((number < b) && (number > 0)); } while (!isInRange(result)) { ubyte[] magnitude = generateRandomBytes(numberOfBytes); result = BigInteger(false, magnitude); } return result; } } class EllipticPoint { public { // координаты точки на кривой BigInteger x, y; // параметры кривой - a, b; а также FG (он же - p) - модуль конечного поля BigInteger a, b, FG; // порядок кривой BigInteger n; } this(EllipticPoint lhs) { x = lhs.x; y = lhs.y; a = lhs.a; b = lhs.b; FG = lhs.FG; n = lhs.n; } this(BigInteger x, BigInteger y, EllipticCurve curve) { this.x = x; this.y = y; a = curve.a; b = curve.b; FG = curve.p; n = curve.n; } this() { x = 0; y = 0; a = 0; b = 0; FG = 0; n = 0; } static { /// сложение двух точек lhs и rhs EllipticPoint add(EllipticPoint lhs, EllipticPoint rhs) { EllipticPoint p3 = new EllipticPoint; p3.a = lhs.a; p3.b = lhs.b; p3.FG = lhs.FG; p3.n = lhs.n; BigInteger dy = rhs.y - lhs.y; BigInteger dx = rhs.x - lhs.x; if (dx < 0) { dx += lhs.FG; } if (dy < 0) { dy += lhs.FG; } BigInteger m = (dy * dx.modInverse(lhs.FG)) % lhs.FG; if (m < 0) { m += lhs.FG; } p3.x = (m * m - lhs.x - rhs.x) % lhs.FG; p3.y = (m * (lhs.x - p3.x) - lhs.y) % lhs.FG; if (p3.x < 0) { p3.x += lhs.FG; } if (p3.y < 0) { p3.y += lhs.FG; } return p3; } /// сложение точки c собой же (иными словами, умножение ее на два) static EllipticPoint multiplyByTwo(EllipticPoint lhs) { EllipticPoint rhs = new EllipticPoint; rhs.a = lhs.a; rhs.b = lhs.b; rhs.FG = lhs.FG; rhs.n = lhs.n; BigInteger dy = 3 * lhs.x * lhs.x + lhs.a; BigInteger dx = 2 * lhs.y; if (dx < 0) { dx += lhs.FG; } if (dy < 0) { dy += lhs.FG; } BigInteger m = (dy * dx.modInverse(lhs.FG)) % lhs.FG; rhs.x = (m * m - lhs.x - lhs.x) % lhs.FG; rhs.y = (m * (lhs.x - rhs.x) - lhs.y) % lhs.FG; if (rhs.x < 0) { rhs.x += lhs.FG; } if (rhs.y < 0) { rhs.y += lhs.FG; } return rhs; } /// умножение точки на число x, по сути своей представляет x сложений точки самой с собой EllipticPoint multiply(BigInteger x, EllipticPoint lhs) { EllipticPoint temp = lhs; x = x - 1; while (x != 0) { if ((x % 2) != 0) { if ((temp.x == lhs.x) || (temp.y == lhs.y)) { temp = multiplyByTwo(temp); } else { temp = EllipticPoint.add(temp, lhs); } x = x - 1; } x = x / 2; lhs = multiplyByTwo(lhs); } return temp; } } /// Строковое представление точки на кривой override string toString() { return format("Point(x = %s, y = %s)", x, y); } } /// Генерирующая точка кривой alias GeneratingPoint = EllipticPoint; /// Генерация публичного ключа из приватного auto fromPrivateKey(BigInteger privateKey, GeneratingPoint gp) { return GeneratingPoint.multiply(privateKey, gp); } /// Цифровая подпись class EllipticCurveDigitalSign { private { BigInteger _r, _s; } this(BigInteger r, BigInteger s) { _r = r; _s = s; } @property { BigInteger r() { return _r; } BigInteger s() { return _s; } } override string toString() { return (r.toHex ~ s.toHex) .replace("_", "") .toLower; } } /// Используемая эллиптическая кривая class EllipticCurve { private { BigInt _a, _b, _p, _n; } this(BigInteger a, BigInteger b, BigInteger p, BigInteger n) { _a = a; _b = b; _p = p; _n = n; } @property { BigInteger a() { return _a; } BigInteger b() { return _b; } BigInteger p() { return _p; } BigInteger n() { return _n; } } override string toString() { return format( `EllipticCurve(a = %s, b = %s, p = %s, n = %s)`, _a, _b, _p, _n ); } } /// Проставить подпись auto signWithEllipticCurve(BigInteger message, BigInteger privateKey, GeneratingPoint g) { BigInteger k = randomBigInteger(g.n); EllipticPoint rPoint = EllipticPoint.multiply(k, g); BigInteger r = rPoint.x % g.n; while (r == 0) { k = randomBigInteger(g.n); rPoint = EllipticPoint.multiply(k, g); r = rPoint.x % g.n; } auto s = modInverse(k, g.n) * (message + r * privateKey) % g.n; return new EllipticCurveDigitalSign(r, s); } /// Проверить подпись auto verifyWithEllipticCurve(EllipticCurveDigitalSign signature, BigInteger message, EllipticPoint publicKey, GeneratingPoint g) { BigInteger r = signature.r; BigInteger s = signature.s; BigInteger sInverse = modInverse(s, g.n); auto c0 = EllipticPoint.multiply(message * sInverse % g.n, g); auto c1 = EllipticPoint.multiply(r * sInverse % g.n, publicKey); return EllipticPoint.add(c0, c1).x == r; } auto signFileWithEllipticCurve(string filepath, BigInteger privateKey, GeneratingPoint g) { File file = File(filepath); auto hash = BigInteger(false, cast(ubyte[]) digest!SHA256(file.byChunk(4096))); return signWithEllipticCurve(hash, privateKey, g); } auto verifyFileWithEllipticCurve(EllipticCurveDigitalSign signature, string filepath, EllipticPoint publicKey, GeneratingPoint g) { File file = File(filepath); auto hash = BigInteger(false, cast(ubyte[]) digest!SHA256(file.byChunk(4096))); return verifyWithEllipticCurve(signature, hash, publicKey, g); } void main() { /// коэффициент a auto a = BigInt(0); /// коэффициент b auto b = BigInt(7); /// модуль конечного поля auto p = BigInt("115792089237316195423570985008687907853269984665640564039457584007908834671663"); /// координата x генерирующей точки auto x = BigInt("55066263022277343669578718895168534326250603453777594175500187360389116729240"); /// координата y генерирующей точки auto y = BigInt("32670510020758816978083085130507043184471273380659243275938904335757337482424"); /// порядок кривой (т.е количество ее точек) auto n = BigInt("115792089237316195423570985008687907852837564279074904382605163141518161494337"); auto k = BigInt("2625326321425176125342621412651725155246868475"); auto privateKey = BigInt("123456789012345"); auto message = BigInt("12345"); auto sec256k1 = new EllipticCurve(a, b, p, n); auto g = new EllipticPoint(x, y, sec256k1); auto publicKey = fromPrivateKey(privateKey, g); auto signature = signWithEllipticCurve(message, privateKey, g); auto isValid = verifyWithEllipticCurve(signature, message, publicKey, g); writeln("Signature: ", signature); writeln("Signature length: ", signature.to!string.length / 2); writeln("Is valid: ", isValid); enum TEST_FILE = `/home/altakvajxo/workspace/data/images/Lenna0.png`; auto signature1 = signFileWithEllipticCurve(TEST_FILE, privateKey, g); auto isValid1 = verifyFileWithEllipticCurve(signature1, TEST_FILE, publicKey, g); writeln("File " ~ TEST_FILE ~ " signed to ", signature1); writeln("Signature of " ~ TEST_FILE ~ " is valid: ", isValid); // ключ Алисы auto dA = randomBigInteger(n); auto Ha = EllipticPoint.multiply(dA, g); // ключ Боба auto dB = randomBigInteger(n); auto Hb = EllipticPoint.multiply(dB, g); // Общий секрет auto S1 = EllipticPoint.multiply(dA, Hb); auto S2 = EllipticPoint.multiply(dB, Ha); writeln(`Alice private key = `, dA); writeln(`Bob private key = `, dB); writeln(`Secret 1 = `, S1); writeln(`Secret 2 = `, S2); /// Curve25519 /// коэффициент a auto a0 = BigInt("486662"); /// коэффициент b auto b0 = BigInt(1); /// модуль конечного поля auto p0 = (BigInt("2") ^^ 255) - BigInt("19"); /// координата x генерирующей точки auto x0 = BigInt("9"); /// координата y генерирующей точки auto y0 = BigInt("6278"); /// порядок кривой (т.е количество ее точек) auto n0 = (BigInt("2") ^^ 252) - BigInt("27742317777372353535851937790883648493"); auto curve25519 = new EllipticCurve(a0, b0, p0, n0); auto g0 = new EllipticPoint(x, y, curve25519); g0.writeln; }Этот тестовый модуль каждый раз создает разную подпись, а также генерирует общий ключ Алисы и Боба (он же S1, и он же S2) — что смотрится достаточно наглядно.
Мы настоятельно рекомендуем вам по возможности повторить этот эксперимент, а для энтузиастов рекомендуем как-нибудь проверить его на практике, передав ключ через описанные величины между разными участниками и полученные значения сериализовать в массив байтов и использовать как ключ в симметричном алгоритме шифрования. Это было бы очень показательно, однако, данный код категорически не рекомендуем применять в реальном коде, поскольку реализация криптографии своими руками — это почти всегда плохая идея, лучше использовать проверенное решение, вроде openSSL или других криптографических библиотек.
Надеемся вам понравилось столь краткое и местами поспешное введение в криптографию на эллиптических кривых, для интересующихся подробностями, советуем обратить внимание на следующую литературу: