В настоящее время я пытаюсь сделать криптопалы вызов 62, разбивая ECDSA с помощью смещенных одноразовых номеров, с помощью этих двух ссылок (1 2), которые точно описывают атаку. Однако примерно через 15 часов я все еще не могу заставить его работать, и я совершенно не понимаю, где я допустил ошибку.
Вот как я это сделал (используя Python 3.6):
Во-первых, чтобы сгенерировать подписи с ошибочными одноразовыми номерами (я взял ту же модель, что и те, которые используют эти ссылки, поэтому 8 бит LSB равны нулю):
импорт ecdsa
из случайного импорта randint
gen = ecdsa.SECP256k1.generator
порядок = ген.порядок()
d = randint(1, порядок)
pub = ecdsa.ecdsa.Public_key(gen, gen*d)
priv = ecdsa.ecdsa.Private_key(pub, d)
Р = []
С = []
для i в диапазоне (100):
одноразовый номер = randint(1, порядок)
одноразовый номер ^= (одноразовый номер и 0xff)
подписанный = личный знак (h, одноразовый номер)
R.добавлять(подписано.r)
S.append(подписано.s)
затем собственно атака, которая довольно короткая: мы вычисляем несколько чисел, строим из них матрицу, вызываем алгоритм LLL и должны найти в приведенном базисе значение -д*кт прямо рядом с у.е. один, по ссылкам:
Построение матрицы:
ч = 1337
N_SIGNATURE = 100
M = [[0 для i в диапазоне (N_SIGNATURE + 2)] для j в диапазоне (N_SIGNATURE + 2)]
для i в диапазоне (N_SIGNATURE):
М [я] [я] = порядок
ct = gmpy2.invert(256, order) # 2**l где l = известные биты
у.е. = заказ * кт
М[-2][-2] = целое(кт)
M[-1][-1] = целое (у.е.)
для i в диапазоне (N_SIGNATURE):
M[-2][i] = int(R[i] * gmpy2.invert(S[i] * 256, порядок)) % порядок # t_i
M[-1][i] = int(-h * gmpy2.invert(S[i] * 256, порядок)) % порядок # u_i
С помощью очень эффективного полный lib (эта часть немного корявая и будет переписана с помощью Sage, но она работает. Здесь я в основном форматирую матрицу, чтобы ее можно было ввести для fplll, и конвертирую вывод обратно в матрицу):
str_M = str(M).replace(",", "")
os.system("echo" + str_M + " | fplll -a lll -m Verified -f mpfr > result.txt")
new_matrix = [[0 для i в диапазоне (N_SIGNATURE+2)] для j в диапазоне (N_SIGNATURE+2)]
с open("result.txt", "r") в качестве myfile:
содержимое = myfile.read()
содержимое = содержимое.replace("[", "").replace("]", "").replace("\n", "").split(" ")
contents =contents[:-1] # в конце есть одна пустая строка
утверждать (len (содержимое) == pow (N_SIGNATURE + 2, 2))
я = 0
j = 0
для v в содержании:
new_matrix[i][j] = int(v)
j += 1
если j == N_SIGNATURE + 2:
j = 0
я += 1
Получение д:
для строки в new_matrix:
если (строка [-1] == у.е.):
d2 = (-row[-2] * gmpy2.invert(ct, order)) % порядок
если (d2 == d):
print("Секретный ключ восстановлен")
Однако, сколько бы переменных я ни настраивал и ни пробовал, я не могу получить результат. Я также безуспешно пытался сканировать всю матрицу вместо последних элементов. Я сделал глупую ошибку, которую не заметил, или в моем коде что-то не так?
Примечание: следующая строка в ссылке 2:
Я забыл упомянуть: вам нужно написать свою реализацию для работы с векторами рациональных чисел. Если у вас есть поплавки с бесконечной точностью, они тоже будут работать.
привлек мое внимание, но mpfr аргумент fplll должен соответствовать тому, что здесь нужно.И в случае, если это не так, я также попытался использовать матрицу Sage, определенную над QQ, но это не работает лучше.
