Рейтинг:0

Помогите взломать ECDSA с помощью предвзятых одноразовых номеров

флаг cn

В настоящее время я пытаюсь сделать криптопалы вызов 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, но это не работает лучше.

Рейтинг:3
флаг ph

Вы должны быть немного осторожны с несколькими вещами:

  1. дробное число $\frac{1}{2^l}$ не является обратным модальному порядку 2^l.

  2. после редукции решетки элементы базовой матрицы могут быть отрицательными, поэтому утверждение if(row[-1] == cu) может быть не совсем корректным.

  3. обратите внимание, что порядок - d также является решением неравенства HNP, поэтому может быть безопасно проверить оба. Обычно уменьшение решетки приводит к меньшему из d и порядка - d.

  4. вектор, который вам нужен, может не быть первым вектором сокращенного базиса, поэтому вы можете проверить все строки.

Думаю, для 256-битного ECDSA с 8-битной утечкой достаточно 50 (даже 40).

Katoptriss avatar
флаг cn
Большое спасибо за ответ. Просто исправив пункт 1, все сразу заработало. Я бы никогда не догадался, что здесь нужна правильная дробь, так как все по модулю порядка, а деления вычисляются с модульной инверсией.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.