31.03.2018 21:15
ChePeter 21 4300 Источник
О некоторых свойствах кривой secp256k1 и попытке предсказать ее поведение.

Как известно, задача дискретного логарифмирования является очень сложной и люди не знают способа вычислять его быстро. Более того, зная точку на кривой P = n*G очень трудно сделать суждение о величине n. Даже о приблизительной величине. Попробуем еще проще: попробуем делать суждения о последовательности $P(i) = i*G$, вернее о значениях $i$ зная значения $P(i)$.

Попробуем определить, насколько эта последовательность отличается от случайной последовательности. Если последовательность $P(i)$ сложная и ее трудно предугадать, то она не будет отличаться от случайной последовательности. А если будет отличаться, то это означает, что последовательность точек кривой secp256k1 не так уж и сложна.
Построим нейронную сеть, которую обучим на тренировочной последовательности отличать последовательности.

Если мы сможем различать случайную последовательность и последовательность точек, то это будет означать, что существует некий достаточно быстро вычисляемый алгоритм позволяющий делать суждения о логарифме.

Напомню, что вычисление дискретного логарифма на эллиптической кривой очень трудная задача.
Возьмем заранее вычисленную случайную последовательность для повторяемости эксперимента. Качество этой последовательности можно проверить 

dieharder -f PM_rand_600.bin -g 201 -a

можно и nist проверить, но результат будет почти тот же.

Составим программу, которая будем смешивать координату y последовательности точек кривой и случайную последовательность в соотношении 1:8 и записывать в файл x600_btc_32_LH.bin и одновременно записывая в y600_btc_32_LH.bin указатель на источник — кривая или случайная.

data_preparation.cpp
#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 %s\n  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. Это говорит о том, что сеть обнаруживает закономерности в последовательности, которая должна быть очень сложной.

На сегодняшний день, 01.04.18, это самая серьезная уязвимость кривой secp256k1 и рано или поздно победа будет за AI.

Все тексты и файлы выложены на GitHub и можно всё проверить, убедиться и усовершенствовать.

Комментарии (21)


  1. dkukushkin
    01.04.2018 00:29
    #10735106

    Мне приходила на ум эта же идея, но применительно к факторизации целых чисел.

    К слову, если таки найдете способ — кирдык будет не только биткойну, но и всей мировой банковской систем, где передача тех же SWIFT-сообщений основана на ЭЦП.

    Будем надеяться что при нашей жизни этого не произойдет.


  1. lair
    01.04.2018 01:18
    #10735144

    Эм, а разве эллиптическая кривая — это CSPRNG? А если нет — то какая уязвимость в том, что взятые с нее точки отличимы от случайной последовательности?


    1. ChePeter Автор
      01.04.2018 08:50
      #10735246

      Ну да. Если оперировать понятими сложности, а не вероятности, то последовательность точек кривой это более простой объект, чем случайная последовательность. И если случайную последовательность принципиально трудно вычислить, то последовательность точек более предсказуема. И, кстати, почти все генераторы псевдослучайных последовательностей основываются на вычислении точек.


      1. lair
        01.04.2018 11:43
        #10735404

        Ну да

        "Ну да" — что? Эллиптическая кривая — это CSPRNG?


        Если оперировать понятими сложности, а не вероятности, то последовательность точек кривой это более простой объект, чем случайная последовательность.

        Что за понятие "сложности", и как оно формулируется математически?


        1. ChePeter Автор
          01.04.2018 12:20
          #10735440
          -2

          Прочтите труды Колмогорова о сложности и определение случайной последовательности Мартина Лёфа.
          ru.m.wikipedia.org/wiki/Колмогоровская_сложность


          1. lair
            01.04.2018 12:40
            #10735476

            Окей, со сложностью разобрались. Вернемся к первому вопросу: эллиптическая кривая — это CSPRNG?


            1. ChePeter Автор
              01.04.2018 16:51
              #10735724

              Так кто ж проверял то? В основе многих CSPRNG лежит сложная задача и в том числе дискретного логафмирования на эллиптической кривой.
              Думаю, что такую последовательность никто не проверял на соответствие требованиям CSPRNG.


              1. lair
                01.04.2018 16:56
                #10735732

                Так кто ж проверял то?

                Для начала — а кто-то обещал?


                В основе многих CSPRNG лежит сложная задача и в том числе дискретного логафмирования на эллиптической кривой.

                Эм, не совсем так. Более того, есть мнение, что эллиптические кривые не надо использовать для CSPRNG.


                1. ChePeter Автор
                  01.04.2018 17:02
                  #10735738

                  Полностью с Вами согласен, для серьезного дела и secp256k1 и все из нее исходящие конструкции не годятся. И надежность btc под большим вопросом.


                  1. lair
                    01.04.2018 17:05
                    #10735748
                    +1

                    То есть вы "полностью согласны" с тем, что ваше исследование ничего не доказывает? Я ведь именно об этом говорю.


                    1. ChePeter Автор
                      01.04.2018 17:09
                      #10735750

                      А оно разве собиралось Вам что то доказывать? Первый раз слышу, что Вам это исследование, да и любому другому, что то должно доказать!
                      Попробуйте прочесть еще раз! Там нет ничего про что то доказывающее, передоказывающее или опровергающее, провозглашающее или символизирующее.


  1. ainu
    01.04.2018 10:16
    #10735314

    Это общая проблема, не только эллиптических кривых. Недавно баловался, скачал криптослучайные данные на основе грозовых облаков, и обучил нейронную сеть.
    В итоге в случайных данных, которые должны быть абсолютно непредсказуемы (!), можно в 50% случаях предсказывать данные. То есть вместо непредсказуемости, нейронная сеть уменьшает непредсказуемость в два раза.
    Как рассчитывал:
    Взял криптостойкую непредсказуемость равную x = 100%.
    Затем обработал случайные данные в нейронной сети (1 мегабайт), и получил в результате новые данные. И они совпадают с исходными в полумиллионе случаев! Таким образом, непредсказуемость сбросилась вдвое, 100%/50% = 2.
    Благодаря этому можно улучшить ИИ в играх, ведь как минимум в половине случаев (это доказано только что) действия игрока не будут для ИИ непредсказуемыми и он сможет использовать более правильную стратегию. Во второй половине игр действия будут непредсказуемыми, и человек победит. Таким образом игра подстраивается под любого человека — от чемпиона до новичка.


    1. lair
      01.04.2018 11:44
      #10735408
      +1

      Затем обработал случайные данные в нейронной сети (1 мегабайт), и получил в результате новые данные. И они совпадают с исходными в полумиллионе случаев! Таким образом, непредсказуемость сбросилась вдвое

      Пожалуйста, объясните ваш алгоритм и расчет.


      1. Karbas
        01.04.2018 21:07
        #10736020

        Ну логично что в случайных данных единиц и нулей примерно поровну :) Тогда нейросети достаточно генерить только все единицы или только все нули, и «половина» случайных данных будет предсказана!
        (Это сарказм если что)


    1. Goodkat
      01.04.2018 14:50
      #10735590

      В итоге в случайных данных, которые должны быть абсолютно непредсказуемы (!), можно в 50% случаях предсказывать данные.
      Я, когда монетку подкидываю, тоже в 50% случаев предсказываю результат!


      1. marsermd
        01.04.2018 15:18
        #10735628

        Мне кажется, это неспроста:)


      1. ChePeter Автор
        01.04.2018 19:11
        #10735860

        Сомневаюсь в монетке.
        1. Она может не упасть, совсем и никогда, после того как ее подбросили.
        2. Она может упасть на ребро
        3,4. Орел, решка
        Это дает 4 варианта, каждый из которых имеет ненулевую вероятность.
        Более того, если ее бросать так, чтобы падала на песок, то она может зафиксироваться в песке с любым углом наклона и считать все эти выпадения одинаковыми мне не кажется корректным.


        1. ainu
          02.04.2018 13:59
          #10737242

          Всё верно говорите, поэтому монетка не может быть криптостойким генератором случайных чисел, и обучать нейронную сеть на монетках не имеет смысла.


  1. ilynxy
    02.04.2018 10:21
    #10736770

    www.quora.com/Has-anyone-actually-tried-to-train-a-neural-network-to-find-prime-numbers-and-what-was-the-result


  1. Derivator
    02.04.2018 13:28
    #10737170

    Координата Y в этих кривых симметрична относительно оси X. Поэтому точки всегда имеют пару, что уже отличает указанную последовательность от случайной.


  1. gearbox
    02.04.2018 14:54
    #10737362

    Теория Рамсея

    Имхо Вам нужно привести рельеф полученной нейросети к какой то метрике (хз, что типа числа используемых нейронов), убедиться что эта метрика меньше чем число возможных точек, ДОКАЗАТЬ что нейросеть в каком то проценте оказывается права (да, согласен, будет хардкор) и тогда можно утверждать есть какая то закономерность. Но вообще интересная мысль.