Регистрация Войти
Рейтинг:2
avatar Crypto

Почему большую часть времени в закрытых ключах X25519 наблюдается небольшое несоответствие в зависимости от используемых функций, но открытые ключи всегда совпадают (одно и то же начальное число для обоих)?

флаг cn
mkl

Я пытаюсь обернуть голову вокруг перехода от семя к ключ подписи, а также получение Приватный ключ (ключ шифрования). Я использую NaCl/libsodium.

Я создал код ниже, и результаты интересны. Оказывается pk1.private_key и pk2.private_key совпадают примерно в 3% случаев. Однако открытый ключ соответствует 100%, все они генерируются, начиная с одного и того же семя. Что здесь происходит?

  • я получаю ПК1 используя PrivateKey.from_seed(начальное число)

  • я получаю ПК2 используя Ключ подписи (начальное число).to_curve25519_private_key()

Примеры несоответствия (они близки, но не равны):

# Несоответствие 1-го байта на 0x01
семя: f8d9e54a23971beebf2552c1a50ade6150cd051321398394f515e8d4b1ba0404
приват1: c1fd4612ee8ef24d295210a277e196e6bb4a9ae6b93f98d93f197860fe5dc048
priv2: c0fd4612ee8ef24d295210a277e196e6bb4a9ae6b93f98d93f197860fe5dc048

# Несоответствие 1-го байта на 0x03
семя: d612a66f92ee2f42ab1f7ea9a712a47c815843d21fc988b1d202459f235b6410
приват1: f33d5e80bb556333e2961c9868b1dc7e548836ee56808689ca022f1a19fe86bb
приват2: f03d5e80bb556333e2961c9868b1dc7e548836ee56808689ca022f1a19fe867b

# Несоответствие 1-го байта на 0x01, несоответствие последнего байта на 0x40
семя: 10b7e1c66cf08005a22289158a088e028160f892dc6c20d43025be4690aaed85
приват1: 194898f65d117579d50e80a9b7e07bd048bfd1300d55561dac9dfaed4ef02109
приват2: 184898f65d117579d50e80a9b7e07bd048bfd1300d55561dac9dfaed4ef02149

из nacl.signing импортировать SigningKey
из nacl.public импортировать PrivateKey, PublicKey, Box, SealedBox
из nacl.bindings импортировать crypto_sign_SEEDBYTES
из nacl.utils импортировать StringFixer, случайный

деф запустить (отладка = Ложь):
    семя = случайное (crypto_sign_SEEDBYTES)
    pk1 = PrivateKey.from_seed(seed)
    pk2 = Ключ подписи (начальное число).to_curve25519_private_key()
    если отладить:
        print('seed: ', seed.hex()) 
        print('priv1: ', pk1._private_key.hex())
        print('priv2: ', pk2._private_key.hex())
        print('pub1: ', байты(pk1.public_key).hex())
        print('pub2: ', байты(pk2.public_key).hex())
    возврат семян, pk1, pk2

пробеги = 10000
приватный_ключ_матч = 0
public_key_match = 0
оба_матча = 0

для i в диапазоне (работает):
    если я % 500 == 0:
        print(i, 'из', работает)
    семя, pk1, pk2 = запустить ()
    х = pk1._private_key == pk2._private_key
    y = байты (pk1.public_key) == байты (pk2.public_key)
    если х:
        private_key_match += 1
    если у:
        public_key_match += 1
    если х и у:
        оба_совпадения += 1

print('совпадение закрытого ключа:', private_key_match)
print('совпадение открытого ключа: ', public_key_match)
print('оба совпадают: ', Both_match)
99
0 + 0
Maarten Bodewes avatar
флаг in
Maarten Bodewes
Закрытый ключ должен иметь несколько битов, установленных на определенные значения, если они уже были установлены случайно, вы получите то, что получите.
0
Ответить
флаг cn
mkl
@MaartenBodewes, я не уверен, что понимаю, не представляет ли закрытый ключ целое число, используемое при вычислении открытого ключа, а также при расшифровке. Почему несколько битов не имеют значения? Есть ли спецификация, которую мне не хватает?
0
Ответить
Maarten Bodewes avatar
флаг in
Maarten Bodewes
Тьфу, мне нужно найти уравнения для этого, однако мне интересно, не заключается ли разница в том, когда применяются битовые маски. Я надеялся на помощь моих коллег-криптографов.
1
Ответить
Рейтинг:2
dave_thompson_085 avatar Crypto
флаг cn
dave_thompson_085

'curve25519' (как ее первоначально называл Бернштейн, теперь для ясности переименованный в X25519 или XDH25519, поскольку тот же изгиб в другой форме используется для Ed25519 [ph]) требует, чтобы закрытый ключ (множитель) был кратным 8, чтобы избежать атак с использованием малых подгрупп, и обычно представлен в формате с прямым порядком байтов, поэтому младшие 3 бита первого байта принудительно 0.

X25519 также требует, чтобы старший бит был равен 0 (поскольку его базовое поле составляет всего около $2^{255}$), а Бернштейн указывает, что бит, следующий за старшим, равен 1 (чтобы заблокировать «оптимизацию», которая позволила бы проводить атаки по времени); это влияет на прошлой byte в форме с прямым порядком байтов, которую вы, видимо, не заметили в своих примерах, также меняют bb - 7b и 09 - 49.

Эти два (или три) ограничения, взятые вместе, изменят случайно выбранное значение во всех случаях, кроме (100/32)%, что достаточно близко к 3% для работы правительства.

У Ed25519 на самом деле такая же потребность в том, чтобы его частный множитель был кратен 8, но он не использует закрытый ключ напрямую для множителя; вместо этого он пропускает закрытый ключ через хеш для расширения и использования как для множителя, так и для секретного значения, которое скрывает сообщение, и внутренне ограничивает только часть множителя, не изменяя то, что пользователь видит как закрытый ключ.

Дуп Почему младшие 3 бита секретных ключей curve25519/ed25519 очищаются во время создания?
и Ключевая структура Curve25519
и посмотреть/сравнить https://datatracker.ietf.org/doc/html/rfc7748#page-8
против https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.5 .

0 + 0
knaccc avatar
флаг es
knaccc
Обратите внимание, что нет необходимости, чтобы закрытые ключи в любом варианте кривой 25519 были кратны 8. Некоторые реализации подписи или DH могут сделать это, но это только один способ предотвратить атаку небольшой подгруппы. Вы также можете предотвратить атаку, умножив точку EC на групповой порядок и проверив, что результатом является точка в бесконечности. Это также подтвердит, что точка EC находится в правильной более крупной подгруппе, что предотвращает другие типы атак, такие как атака уникальности изображения ключа кольцевой подписи с возможностью связывания.
0
Ответить
флаг cn
mkl
@dave_thompson_085, очень полезно, спасибо.Значит, похоже, что одна из функций реализована не полностью? Несмотря на то, что любой закрытый ключ создает один и тот же открытый ключ (я полагаю, что при генерации публичного ключа происходит некоторая проверка/очистка)
0
Ответить
dave_thompson_085 avatar
флаг cn
dave_thompson_085
@miketery Нет ничего незавершенного. Как я уже сказал, схемы определяются по-разному; X25519 требует фиксации закрытого ключа, который виден снаружи, в то время как Ed25519 применяет его внутри, поэтому видимый закрытый ключ не фиксируется, а умножение на эллиптическую кривую внутренне.
0
Ответить
Рейтинг:2
Gilles 'SO- stop being evil' avatar Crypto
флаг cn
Gilles 'SO- stop being evil'

Математически Кривая25519 закрытый ключ является элементом $\mathbb{F}_{2^{255}-19}$, т. е. целое по модулю $2^{255}-19$. Это может быть естественно представлено как целое число между $0$ и $2^{255}-19-1$, который сам может быть представлен с использованием 255 бит. Поскольку практические компьютеры работают с 8-битными байтами, наименьшим практическим представлением является 32-байтовая строка.

Существует стандартный формат представления закрытых ключей Curve25519, который описан в RFC 7748 §5. Этот формат кодирует целое число между $0$ и $2^{255}-19-1$ как 32-байтовая (256-битная) строка с прямым порядком байтов.

32-байтовая строка может представлять числа в диапазоне $[0,2^{256}-1]$, что больше, чем $[0,2^{255}-19-1]$. Также по разным причинам не все числа в диапазоне $[0,2^{255}-19-1]$ хороши (см. Ключевая структура Curve25519 и «Да пребудет с вами четвертый: микроархитектурная атака по побочному каналу на несколько реальных приложений Curve25519», автор Genkin et al.). Ограничения:

  • Число должно быть между $2^{254}$ и $2^{255}-19$, поэтому старшие два бита 256-битного числа должны быть равны 0 и 1.
  • Число должно быть кратно 8, поэтому три младших бита должны быть равны 0.

В RFC 7748 §5 указывается, что при генерации закрытого ключа необходимо взять случайную (или псевдослучайную, в зависимости от случая) 32-байтовую строку и принудительно установить для пяти упомянутых выше битов их обязательное значение. Реализация Curve25519, принимающая в качестве входных данных закрытый ключ в виде 32-байтовой строки, должна применить эту маскировку, прежде чем она начнет выполнять вычисления над числом, которое представляет ключ.

nacl.public.PrivateKey.from_seed возвращает необработанную 32-байтовую строку. nacl.signing.SigningKey(seed) выполняет маскировку, поэтому to_curve25519_private_key экспортирует значение в его канонической, замаскированной форме.

Маскировка относится к 5 битам, поэтому, учитывая случайное начальное число, существует $1/2^5 = 1/32 \приблизительно 3\%$ шанс, что он уже имеет правильное значение для этих 5 бит.

0 + 0
флаг cn
mkl
Отличный ответ, спасибо!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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