У цій статті буде представлено принцип реалізації та масштабованість алгоритму цифрового підпису 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 (. Для еліптичної кривої нам потрібно лише знати, що на ній багато, багато точок, і додавання цих точок може отримати нові точки. нова точка все ще знаходиться на кривій. Ці точки та це додавання можуть утворювати групу. Зауважте, що додавання еліптичної кривої (спеціально визначено.
Ми погоджуємося на наступне позначення:
Це інтерактивний алгоритм, але це не має значення, існує трюк під назвою евристика Fiat-Shamir (вона може перетворити будь-який інтерактивний алгоритм на неінтерактивний алгоритм. Зрештою ми будемо використовувати неінтерактивний алгоритм.
Алгоритм цифрового підпису надасть нам такий API:
Реалізація KeyGen
Виведіть закритий та відкритий ключ:
- Випадково згенеруйте початкове число (це початкове число має 32 байти. Ми використовуємо криптографічно безпечний генератор випадкових чисел, який постачається разом із системою.
pub fn генерувати (csprng: &mut T) -> SecretKeywhere
T: CryptoRng + RngCore,
{
let mut sk: SecretKey = SecretKey([0u8; 32]);
csprng.fill_bytes(&mut sk.0);
ск
}
- Щойно розширте початкове значення до 64 байтів (тобто xseed на малюнку. Молодші 32 байти xseed є нашим закритим ключем (він же a). Старші 32 байти називаються одноразовими, які будуть використані пізніше. його функція подібна до доменного сператора.
pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a
pub(crate) nonce: [u8; 32], // nonce
}
fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
let mut h: Sha512 = Sha512::default();
let mut hash: [u8; 64] = [0u8; 64];
дозвольте знизити: [u8; 32] = [0u8; 32];
let mut upper: [u8; 32] = [0u8; 32];
h.update(secret_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(lower), nonce: upper, }
}
- Використовуйте закритий ключ для генерації відкритого ключа (відкритий ключ – це точка на еліптичній кривій. Зокрема, ми використовуємо базову точку еліптичної кривої для виконання множення еліптичної кривої для отримання відкритого ключа. Скаляр у множенні отримується шляхом об’єднання закритого ключа. Виконайте хешування, щоб отримати його.
pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a
pub(crate) nonce: [u8; 32], // nonce
}
fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
let mut h: Sha512 = Sha512::default();
let mut hash: [u8; 64] = [0u8; 64];
дозвольте знизити: [u8; 32] = [0u8; 32];
let mut upper: [u8; 32] = [0u8; 32];
h.update(secret_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(lower), nonce: upper, }
}
Реалізація знака
Тут можна згадати техніку Fiat Shamir, згадану раніше.Насправді вам потрібно лише замінити всі випадкові числа, надані Verifier, на результат хеш-функції. Перегляньте коментарі до коду, щоб дізнатися більше.
pub fn sign(&self, message: & [u8] , public_key: &PublicKey) -> ed25519::Signature {
let mut h: Sha512 = Sha512::new();
нехай R: CompressedEdwardsY;
нехай r: скаляр;
let s: скаляр;
нехай k: скаляр;
h.update(&self.nonce);
h.update(&message);
r = Scalar::from_hash(h); // r — це випадкове число в нашому інтерактивному алгоритмі, але тут ми використовуємо хеш.
R = (&r * &constants::ED25519_BASEPOINT_TABLE).compress(); // R = [r] Б
h = Sha512::new();
h.update(R.as_bytes());
h.update(public_key.as_bytes());
h.update(&message);
k = Scalar::from_hash(h); // h = Sha512(R || A || M)
s = &(&k * &self.key) + &r; // s = r + h * a, h спочатку є випадковим числом
InternalSignature { R, s }.into()
}
Реалізація Verify
Імпл Верифікаторed25519::Signature для публічного ключа {
#[allow(non_snake_case)]
fn verify(
&само,
повідомлення: & [u8] ,
підпис: &ed25519::Підпис
) -> Результат<(), SignatureError>
{
нехай підпис = InternalSignature::try_from(підпис)?;
let mut h: Sha512 = Sha512::new();
нехай R: EdwardsPoint;
нехай k: скаляр;
нехай мінус_A: EdwardsPoint = -self.1;
h.update(signature.R.as_bytes());
h.update(self.as_bytes());
h.update(&message);
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] B - [h] А
if R.compress() == signature.R { // Якщо R’==R, то результат перевірки вірний.
В порядку(())
} ще {
Err(InternalError::VerifyError.into())
}
}
}
код адреси (
Проблеми масштабованості
Є багато моментів, на які слід звернути увагу при реалізації та використанні криптографічних алгоритмів. Коли ми говоримо, що алгоритм цифрового підпису безпечний, це зазвичай означає, що навіть якщо зловмисник може отримати підпис будь-якого повідомлення (атака на вибране повідомлення), зловмисник все одно не може підробити підпис. Ed25519 відповідає цій властивості, але це не означає, що Ed25519 є абсолютно безпечним. В оригінальній статті також згадується, що проблема масштабованості є прийнятною, і оригінальний алгоритм має цю проблему.
Таким чином можна успішно перевірити як новий, так і старий підписи. Проблема податливості говорить нам, що підпис не є детермінованим щодо повідомлення та відкритого ключа.Коли алгоритм підпису має проблему податливості, а код припускає, що підпис є детермінованим, ймовірно, будуть лазівки.
Відповідно до стандарту (насправді немає проблеми з масштабованістю. Оскільки в процесі перевірки ми перевіримо, чи він менший, якщо результат перевірки невірний, перевірка не вдається. Але стандарт (з’являється пізніше, ніж папір) (тому в реальному середовищі все ще існують реалізації Ed25519, які мають проблеми з масштабованістю та потребують реалізацій, які ми перевіряємо.
Підсумувати
Дякую
- Дякуємо Safeheron, провідному постачальнику послуг із самостійного зберігання цифрових активів, за надання професійних технічних консультацій. *
Посилання
[1] .
[2] .
[3] .
[4] .
[5] . Дослідники використовують теорію груп для прискорення алгоритмів — Вступ до груп
