> В этой статье будут представлены принцип реализации и масштабируемость алгоритма цифровой подписи на основе эллиптических кривых Ed25519.
Сценарист: А Вэй
Ed25519 — алгоритм цифровой подписи на основе эллиптической кривой, эффективный, безопасный и широко используемый. Он используется в TLS 1.3, SSH, Tor, ZCash, WhatsApp и Signal. В этой статье в основном объясняются следующие моменты:
Немного познакомьтесь с теорией групп. Цель состоит в том, чтобы дать каждому интуитивное представление о принципе Ed25519 и его проблеме масштабируемости. Для более глубокого понимания необходимо обратиться к другим материалам;
Объяснить реализацию ed25519 для версии 1.0.1 библиотеки rust ed25519-dalek;
Объясните расширяемость библиотеки.
Обзор основ математики
Определение и свойства групп
Теория групп является предметом исследования абстрактной алгебры, но некоторые идеи абстрактной алгебры хорошо знакомы программистам. Хорошим примером является наследование в объектно-ориентированном подходе: все мы знаем, что после того, как подклассы наследуют родительский класс, они могут использовать методы, определенные в родительском классе. Абстрактную алгебру можно понимать как определение некоторых свойств абстрактной структуры данных, и теоремы, полученные из этих свойств, справедливы для всех подклассов.
Используя только что метафору, давайте посмотрим, как определяется структура данных группы.
Группа состоит из операции (обозначаемой любой бинарной операцией) и некоторых элементов, удовлетворяющих следующим свойствам:
Отсюда можно вывести много интересных теорем:
Приведу несколько примеров:
Целые числа ..., −2, −1, 0, 1, 2, ... и сложение являются группой, поскольку они удовлетворяют четырем указанным выше свойствам.
Целые числа и умножение не являются группами, потому что они не удовлетворяют обратимости, 4 x 1/4 = 1, но 1/4 не является целым числом
Терминология теории групп урезана
Теорема Лагранжа
Теперь представим очень интересную теорему, вывод этой теоремы есть в видео, приведенном в конце статьи.
** «Порядок группы делится на порядок подгруппы».**
Почему эта теорема интересна не только тем, что процесс ее доказательства связывает множество только что введенных знаний, но и следующими выводами:
**"Если порядок группы - простое число, то по теореме Лагранжа порядок подгруппы должен быть или. Все элементы в группе являются образующими, кроме
Реализация Ed25519
Теперь поговорим об Ed25519, одном из алгоритмов EdDSA. EdDSA имеет 11 параметров (конкретный выбор этих параметров сильно влияет на безопасность и производительность алгоритма. Конкретный выбор Ed25519 можно посмотреть по ссылке (
Кроме того, стоит упомянуть, что этот алгоритм использует эллиптическую кривую под названием Curve25519 (. Для эллиптической кривой нам нужно только знать, что на ней много-много точек, и добавление этих точек может получить новые точки. новые точки все еще находятся на кривой.Эти точки и это добавление могут образовывать группу.Обратите внимание, что добавление эллиптической кривой (определено специально.
Мы договорились о следующих обозначениях:
Это интерактивный алгоритм, но это не имеет значения, есть трюк, называемый эвристикой Фиата — Шамира (он может преобразовать любой интерактивный алгоритм в неинтерактивный алгоритм. В конце концов мы будем использовать неинтерактивный алгоритм.
Алгоритм цифровой подписи даст нам следующий API:
Реализация KeyGen
Выведите закрытый ключ и открытый ключ:
Случайным образом сгенерируйте начальное число (это начальное число имеет 32 байта. Мы используем криптографически безопасный генератор случайных чисел, который поставляется с системой.
Расширить начальное значение только сейчас до 64 байт (то есть xseed на рисунке. Младшие 32 байта xseed — это наш закрытый ключ (он же a). Старшие 32 байта называются nonce, которые будут использоваться позже. В нем, его функция аналогична доменному диспетчеру.
Используйте закрытый ключ для генерации открытого ключа (открытый ключ — это точка на эллиптической кривой. В частности, мы используем базовую точку эллиптической кривой для выполнения умножения на эллиптическую кривую для получения открытого ключа. Скаляр в умножении получается путем сопряжения закрытого ключа. Сделайте хэш, чтобы получить его.
Здесь можно упомянуть технику Fiat Shamir, упомянутую ранее: по сути, вам нужно всего лишь заменить все случайные числа, предоставленные Verifier, на результат хэш-функции. Подробности смотрите в комментариях к коду.
k = Scalar::from_hash(h); // Вычисление h такое же, как и в sign, h=Sha512(R||A||M)
R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(минус_A), &signature.s); // R' = [s] Б - [h] А
if R.compress() == signal.R { // Если R'==R, то результат проверки верен.
Хорошо(())
} еще {
Err(InternalError::VerifyError.into())
}
}
}
кодовый адрес (
Проблемы с масштабируемостью
Есть много моментов, на которые следует обратить внимание при реализации и использовании криптографических алгоритмов. Когда мы говорим, что алгоритм цифровой подписи безопасен, обычно это означает, что даже если злоумышленник может получить подпись любого сообщения (атака выбранного сообщения), он все равно не сможет подделать подпись. Ed25519 удовлетворяет этому свойству, но это не означает, что Ed25519 абсолютно безопасен. В оригинальной статье также упоминается, что проблема масштабируемости является приемлемой, и исходный алгоритм имеет эту проблему.
Таким образом, как вновь созданная подпись, так и старая подпись могут быть успешно проверены. Проблема податливости говорит нам, что подпись не является детерминированной по отношению к сообщению и открытому ключу.Когда алгоритм подписи имеет проблему податливости, а код предполагает, что подпись является детерминированной, вероятны лазейки.
По стандарту (на самом деле проблемы масштабируемости нет. Потому что в процессе проверки мы будем проверять меньше ли, если результат проверки не соответствует действительности, проверка не проходит. Но стандарт (появляется позже бумажного (поэтому в реальной среде все еще существуют реализации Ed25519, которые имеют проблемы с масштабируемостью и требуют реализаций, которые мы изучаем.
Подведем итог
Спасибо
*Благодарим Safeheron, ведущего универсального поставщика услуг самообслуживания цифровых активов, за предоставление профессиональных технических консультаций. *
> Ссылки
> [1] .
> [2] .
> [3] .
> [4] .
> [5] . Исследователи используют теорию групп для ускорения алгоритмов — введение в группы
Посмотреть Оригинал
Содержание носит исключительно справочный характер и не является предложением или офертой. Консультации по инвестициям, налогообложению или юридическим вопросам не предоставляются. Более подробную информацию о рисках см. в разделе «Дисклеймер».
Обсудить принцип реализации и масштабируемость Ed25519
> В этой статье будут представлены принцип реализации и масштабируемость алгоритма цифровой подписи на основе эллиптических кривых Ed25519.
Сценарист: А Вэй
Ed25519 — алгоритм цифровой подписи на основе эллиптической кривой, эффективный, безопасный и широко используемый. Он используется в TLS 1.3, SSH, Tor, ZCash, WhatsApp и Signal. В этой статье в основном объясняются следующие моменты:
Обзор основ математики
Определение и свойства групп
Теория групп является предметом исследования абстрактной алгебры, но некоторые идеи абстрактной алгебры хорошо знакомы программистам. Хорошим примером является наследование в объектно-ориентированном подходе: все мы знаем, что после того, как подклассы наследуют родительский класс, они могут использовать методы, определенные в родительском классе. Абстрактную алгебру можно понимать как определение некоторых свойств абстрактной структуры данных, и теоремы, полученные из этих свойств, справедливы для всех подклассов.
Используя только что метафору, давайте посмотрим, как определяется структура данных группы.
Группа состоит из операции (обозначаемой любой бинарной операцией) и некоторых элементов, удовлетворяющих следующим свойствам:
Отсюда можно вывести много интересных теорем:
Приведу несколько примеров:
Терминология теории групп урезана
Теорема Лагранжа
Теперь представим очень интересную теорему, вывод этой теоремы есть в видео, приведенном в конце статьи.
** «Порядок группы делится на порядок подгруппы».**
Почему эта теорема интересна не только тем, что процесс ее доказательства связывает множество только что введенных знаний, но и следующими выводами:
**"Если порядок группы - простое число, то по теореме Лагранжа порядок подгруппы должен быть или. Все элементы в группе являются образующими, кроме
Реализация Ed25519
Теперь поговорим об Ed25519, одном из алгоритмов EdDSA. EdDSA имеет 11 параметров (конкретный выбор этих параметров сильно влияет на безопасность и производительность алгоритма. Конкретный выбор Ed25519 можно посмотреть по ссылке (
Кроме того, стоит упомянуть, что этот алгоритм использует эллиптическую кривую под названием Curve25519 (. Для эллиптической кривой нам нужно только знать, что на ней много-много точек, и добавление этих точек может получить новые точки. новые точки все еще находятся на кривой.Эти точки и это добавление могут образовывать группу.Обратите внимание, что добавление эллиптической кривой (определено специально.
Мы договорились о следующих обозначениях:
Это интерактивный алгоритм, но это не имеет значения, есть трюк, называемый эвристикой Фиата — Шамира (он может преобразовать любой интерактивный алгоритм в неинтерактивный алгоритм. В конце концов мы будем использовать неинтерактивный алгоритм.
Алгоритм цифровой подписи даст нам следующий API:
Реализация KeyGen
Выведите закрытый ключ и открытый ключ:
паб fn генерировать (csprng: &mut T) -> SecretKeywhere
Т: CryptoRng + RngCore,
{
пусть mut sk: SecretKey = SecretKey([0u8; 32]);
csprng.fill_bytes(&mut sk.0);
ск
}
pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a
pub(crate) одноразовый номер: [u8; 32], // одноразовый номер
}
fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
let mut h: Sha512 = Sha512::default();
пусть мут хэш: [u8; 64] = [0u8; 64];
пусть мут ниже: [u8; 32] = [0u8; 32];
пусть мут выше: [u8; 32] = [0u8; 32];
h.update(секрет_key.as_bytes());
hash.copy_from_slice(h.finalize().as_slice());
lower.copy_from_slice(&hash[00..32]);
upper.copy_from_slice(&hash[32..64]);
// Этот шаг является зажимом
ниже [0] &= 248;
ниже [31] &= 63;
ниже [31] |= 64;
ExpandedSecretKey{ключ: Scalar::from_bits(нижний), nonce: верхний, }
}
pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a
pub(crate) одноразовый номер: [u8; 32], // одноразовый номер
}
fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
let mut h: Sha512 = Sha512::default();
пусть мут хэш: [u8; 64] = [0u8; 64];
пусть мут ниже: [u8; 32] = [0u8; 32];
пусть мут выше: [u8; 32] = [0u8; 32];
h.update(секрет_key.as_bytes());
hash.copy_from_slice(h.finalize().as_slice());
lower.copy_from_slice(&hash[00..32]);
upper.copy_from_slice(&hash[32..64]);
// Этот шаг является зажимом
ниже [0] &= 248;
ниже [31] &= 63;
ниже [31] |= 64;
ExpandedSecretKey{ключ: Scalar::from_bits(нижний), nonce: верхний, }
}
Реализация знака
Здесь можно упомянуть технику Fiat Shamir, упомянутую ранее: по сути, вам нужно всего лишь заменить все случайные числа, предоставленные Verifier, на результат хэш-функции. Подробности смотрите в комментариях к коду.
pub fn sign(&self, message: & [u8] , public_key: &PublicKey) -> ed25519::Signature {
пусть mut h: Sha512 = Sha512::new();
пусть R: CompressedEdwardsY;
пусть r: скаляр;
let s: скаляр;
пусть k: скаляр;
h.update(&self.nonce);
h.update(&сообщение);
r = Scalar::from_hash(h); // r — это случайное число в нашем интерактивном алгоритме, но здесь мы используем хэш.
R = (&r * &constants::ED25519_BASEPOINT_TABLE).compress(); // Р = [r] Б
h = Sha512::new();
h.update(R.as_bytes());
h.update(public_key.as_bytes());
h.update(&сообщение);
k = скаляр::from_hash(h); // h = Sha512(R || A || M)
s = &(&k * &self.key) + &r; // s = r + h * a, h изначально случайное число
InternalSignature { R, s }.into()
}
Реализация проверки
внедрить верификатор для открытого ключа {
#[разрешить(не_snake_case)]
фн проверить(
&себя,
сообщение: & [u8] ,
подпись: &ed25519::Подпись
) -> Результат<(), SignatureError>
{
пусть подпись = InternalSignature::try_from(подпись)?;
пусть mut h: Sha512 = Sha512::new();
пусть R: ЭдвардсПойнт;
пусть k: скаляр;
пусть минус_A: EdwardsPoint = -self.1;
h.update(signature.R.as_bytes());
h.update(self.as_bytes());
h.update(&сообщение);
k = Scalar::from_hash(h); // Вычисление h такое же, как и в sign, h=Sha512(R||A||M)
R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(минус_A), &signature.s); // R' = [s] Б - [h] А
if R.compress() == signal.R { // Если R'==R, то результат проверки верен.
Хорошо(())
} еще {
Err(InternalError::VerifyError.into())
}
}
}
кодовый адрес (
Проблемы с масштабируемостью
Есть много моментов, на которые следует обратить внимание при реализации и использовании криптографических алгоритмов. Когда мы говорим, что алгоритм цифровой подписи безопасен, обычно это означает, что даже если злоумышленник может получить подпись любого сообщения (атака выбранного сообщения), он все равно не сможет подделать подпись. Ed25519 удовлетворяет этому свойству, но это не означает, что Ed25519 абсолютно безопасен. В оригинальной статье также упоминается, что проблема масштабируемости является приемлемой, и исходный алгоритм имеет эту проблему.
Таким образом, как вновь созданная подпись, так и старая подпись могут быть успешно проверены. Проблема податливости говорит нам, что подпись не является детерминированной по отношению к сообщению и открытому ключу.Когда алгоритм подписи имеет проблему податливости, а код предполагает, что подпись является детерминированной, вероятны лазейки.
По стандарту (на самом деле проблемы масштабируемости нет. Потому что в процессе проверки мы будем проверять меньше ли, если результат проверки не соответствует действительности, проверка не проходит. Но стандарт (появляется позже бумажного (поэтому в реальной среде все еще существуют реализации Ed25519, которые имеют проблемы с масштабируемостью и требуют реализаций, которые мы изучаем.
Подведем итог
Спасибо
*Благодарим Safeheron, ведущего универсального поставщика услуг самообслуживания цифровых активов, за предоставление профессиональных технических консультаций. *
> Ссылки
> [1] .
> [2] .
> [3] .
> [4] .
> [5] . Исследователи используют теорию групп для ускорения алгоритмов — введение в группы