О некоторых свойствах кривой secp256k1 и попытке предсказать ее поведение.
Как известно, задача дискретного логарифмирования является очень сложной и люди не знают способа вычислять его быстро. Более того, зная точку на кривой P = n*G очень трудно сделать суждение о величине n. Даже о приблизительной величине. Попробуем еще проще: попробуем делать суждения о последовательности 
, вернее о значениях 
зная значения 
.
Попробуем определить, насколько эта последовательность отличается от случайной последовательности. Если последовательность 
сложная и ее трудно предугадать, то она не будет отличаться от случайной последовательности. А если будет отличаться, то это означает, что последовательность точек кривой secp256k1 не так уж и сложна.
Построим нейронную сеть, которую обучим на тренировочной последовательности отличать последовательности.
Если мы сможем различать случайную последовательность и последовательность точек, то это будет означать, что существует некий достаточно быстро вычисляемый алгоритм позволяющий делать суждения о логарифме.
Напомню, что вычисление дискретного логарифма на эллиптической кривой очень трудная задача.
Возьмем заранее вычисленную случайную последовательность для повторяемости эксперимента. Качество этой последовательности можно проверить
dieharder -f PM_rand_600.bin -g 201 -a можно и nist проверить, но результат будет почти тот же.
Составим программу, которая будем смешивать координату y последовательности точек кривой и случайную последовательность в соотношении 1:8 и записывать в файл x600_btc_32_LH.bin и одновременно записывая в y600_btc_32_LH.bin указатель на источник — кривая или случайная.
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <openssl/bn.h>
#include <openssl/ec.h>
#include <openssl/err.h>
#include <openssl/symhacks.h>
using namespace std;
int main() {
int bits = 256;
unsigned char buf[32];
char *pr;
EC_GROUP *group;
EC_KEY *eckey = EC_KEY_new();
EC_POINT *P;
BN_CTX *ctx = BN_CTX_new();
BIGNUM *x = BN_new();
BIGNUM *n = BN_new(); // начало последовательности точек кривой
BIGNUM *y = BN_new();
char e_buf[256];
FILE * xFile;
FILE * yFile;
FILE * rFile;
xFile = fopen("x600_btc_32_LH.bin", "wb");
yFile = fopen("y600_btc_32_LH.bin", "wb");
rFile = fopen("PM_rand_600_t.bin", "rb");
if (rFile==NULL)
{ cout<<" PM_rand.bin NOT FOUND"; return -1; }
srand(time(NULL));
// nid 714. curve secp256k1
int nid = 714;
if ((group = EC_GROUP_new_by_curve_name(nid)) == NULL) {
fprintf(stdout, "nEC_GROUP_new_curve_name() failed with"
" curve %sn nid %x", nid);
}
if (eckey == NULL) {
cout << "ABORT2 ";
ERR_error_string(ERR_get_error(), e_buf);
cout << "E_BUF " << e_buf << endl;
}
if (!EC_KEY_set_group(eckey, group)) {
cout << "ABORT3 ";
ERR_error_string(ERR_get_error(), e_buf);
cout << "E_BUF " << e_buf << endl;
}
EC_GROUP_precompute_mult(group, ctx);
P = EC_POINT_new(group);
BN_rand(n, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
// n - начало выборки
int NN = 60000;
for (int i = 0; i < NN; i++) {
if ((rand() % 128) < 16) {
pr = (char *) "1";
if (!EC_POINT_mul(group, P, n, NULL, NULL, ctx)) {
cout << "ABORT_10 ";
ERR_error_string(ERR_get_error(), e_buf);
cout << "E_BUF " << e_buf << endl;
}
if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) {
cout << "ABORT_11 ";
ERR_error_string(ERR_get_error(), e_buf);
cout << "E_BUF " << e_buf << endl;
}
BN_bn2bin(y, buf);
} else {
pr = (char *) "0";
int cind = fread(buf, 32, 1, rFile); // read 32 byte = 256 bit
}
fwrite(buf, 32, 1, xFile);
BN_add_word(n, 1L); // in P new point n+i
fwrite(pr, 1, 1, yFile);
}
fclose(xFile);
fclose (yFile);
BN_CTX_free(ctx);
EC_GROUP_free(group);
BN_free(x);
BN_free(y);
}
И два полученных файла x600_btc_32_LH.bin и y600_btc_32_LH.bin скормим сети.
from keras.models import Model
from keras.utils import np_utils
from keras.layers import Dense, Input
from keras.layers import Bidirectional, GRU
from keras.models import Model
from keras.optimizers import RMSprop
import numpy as np
import keras as ks
num_classes = 2
length = 32
length_8 = length<<3
num_train = 50000
num_test = 10000
X_train = np.zeros(shape=(num_train, length_8), dtype='uint8')
y_train = np.zeros(shape=(num_train), dtype='uint8')
X_test = np.zeros(shape=(num_test, length_8), dtype='uint8')
y_test = np.zeros(shape=(num_test), dtype='uint8')
bx_train = np.zeros(shape=(num_train, length), dtype='uint8')
bx_test = np.zeros(shape=(num_test, length), dtype='uint8')
f_x = open("./input/x600_btc_32_LH.bin", 'rb')
for k in xrange(num_train):
for i in xrange(32):
bx_train[k, i] = ord(f_x.read(1))
for k in xrange(num_test):
for i in xrange(32):
bx_test[k, i] = ord(f_x.read(1))
f_x.close()
f_y = open("./input/y600_btc_32_LH.bin", 'rb')
for i in xrange(num_train):
y_train[i] = ord(f_y.read(1))
for i in xrange(num_test):
y_test[i] = ord(f_y.read(1))
f_y.close()
y_train -= 48
y_test -= 48
Переведем в формат бит в байт. Т.е. один бит исходной последовательности переносим в байт.
tab = np.zeros((256,8),dtype='int8')
for i in xrange(256):
mask = 1
for j in xrange(8):
if i & mask == 0:
tab[i,j] = 0
else:
tab[i,j] = 1
mask<<1
for k in xrange(num_train):
for i in xrange(length):
for j in xrange(8):
X_train[k,i*8+j] = tab[bx_train[k,i],j]
for k in xrange(num_test):
for i in xrange(length):
for j in xrange(8):
X_test[k,i*8+j] = tab[bx_test[k,i],j]
Переведем в формат float и масштабируем до 0.004 и подготовим Y.
X_train = X_train.astype('float32')
X_test = X_test.astype('float32')
X_train /= 255.
X_test /= 255.
Y_train = np_utils.to_categorical(y_train, num_classes)
Y_test = np_utils.to_categorical(y_test, num_classes)
Сеть возьмем достаточно простую, только немного изменим функцию активации.
import math
from keras import backend as K
from keras.utils.generic_utils import get_custom_objects
from keras.layers import Activation
def gaussian(x):
mu = 64.
sigma = 10.
xx = -0.5*((x-mu)/sigma)**2 / sigma / math.sqrt(2*math.pi)
return K.exp(xx)
get_custom_objects().update({'gaussian': Activation(gaussian)})
batch_size = 32
num_epochs = 16
hidden_size_1 = 1024
hidden_size_2 = 1024
X_train = X_train.reshape(num_train,16,16)
X_test = X_test.reshape(num_test,16,16)
inp = Input(shape=(16,16,))
x = Bidirectional(GRU(1024, return_sequences=True))(inp)
x = Bidirectional(GRU(1024, return_sequences=False))(x)
x = Dense(hidden_size_1, activation='sigmoid')(x)
x = Dense(hidden_size_2, activation='gaussian')(x)
out = Dense(num_classes, activation='gaussian')(x)
model = Model(inputs=inp, outputs=out)
model.compile(loss='binary_crossentropy',
# optimizer='adam',
optimizer=RMSprop(lr=0.0001,clipvalue=1, clipnorm=1),
metrics=['accuracy'])
Результат вполне приемлем, сеть отличает последовательность точек кривой от случайной последовательности, не так точно как хотелось бы, но суждение о логарифме делает.
mod = model.fit(X_train, Y_train, # Train the model using the training set...
batch_size=batch_size, epochs=2,
verbose=1, validation_data=(X_test, Y_test))
Train on 50000 samples, validate on 10000 samples
Epoch 1/2
val_loss: 0.3706 - val_acc: 0.8783
Epoch 2/2
val_loss: 0.3703 - val_acc: 0.8783
Мы получили, что простая обычная нейронная сеть может различать случайную последовательность и последовательность точек кривой secp256k1. Это говорит о том, что сеть обнаруживает закономерности в последовательности, которая должна быть очень сложной.
На сегодняшний день это самая серьезная уязвимость кривой secp256k1 и рано или поздно победа будет за AI.
Все тексты и файлы выложены на GitHub и можно всё проверить, убедиться и усовершенствовать.
Автор: ChePeter
