> Artikel ini akan memperkenalkan prinsip implementasi dan skalabilitas algoritme tanda tangan digital berbasis kurva eliptik Ed25519.

Ditulis oleh: Ah Wei

Ed25519 adalah algoritma tanda tangan digital berdasarkan kurva eliptik, yang efisien, aman, dan banyak digunakan. Ini digunakan di TLS 1.3, SSH, Tor, ZCash, WhatsApp dan Signal. Artikel ini terutama menjelaskan hal-hal berikut:

1. Perkenalkan sedikit pengetahuan tentang teori grup, tujuannya adalah agar setiap orang memiliki intuisi tentang prinsip Ed25519 dan masalah skalabilitasnya. Untuk pemahaman yang lebih dalam, Anda perlu merujuk ke materi lain;
2. Jelaskan penerapan ed25519 untuk pustaka karat versi 1.0.1 ed25519-dalek;
3. Jelaskan ekstensibilitas perpustakaan.

Ulasan Penting Matematika

Definisi dan properti grup

Teori grup adalah isi dari penelitian aljabar abstrak, tetapi beberapa ide aljabar abstrak sangat familiar bagi programmer. Warisan dalam berorientasi objek adalah contoh yang baik Kita semua tahu bahwa setelah subclass mewarisi kelas induk, mereka dapat menggunakan metode yang didefinisikan dalam kelas induk. Aljabar abstrak dapat dipahami sebagai pendefinisian beberapa properti untuk struktur data abstrak, dan teorema yang diturunkan dari properti ini berlaku untuk semua subkelas.

Menggunakan metafora tadi, mari kita lihat bagaimana struktur data grup didefinisikan.

Grup terdiri dari operasi (dilambangkan dengan operasi biner) dan beberapa elemen, yang memenuhi sifat-sifat berikut:

Banyak teorema menarik dapat diturunkan dari ini:

Untuk memberikan beberapa contoh:

• Bilangan bulat ..., −2, −1, 0, 1, 2, ... dan penjumlahan merupakan grup karena memenuhi keempat sifat di atas
• Bilangan bulat dan perkalian bukan grup karena tidak memenuhi reversibilitas, 4 x 1/4 = 1, tetapi 1/4 bukan bilangan bulat

Terminologi Teori Kelompok Dipotong

Teorema Lagrange

Sekarang perkenalkan teorema yang sangat menarik, turunan dari teorema ini ada di video yang dikutip di akhir artikel.

** "Urutan grup dapat dibagi dengan urutan subgrup."**

Mengapa teorema ini menarik, bukan hanya karena proses pembuktiannya menghubungkan banyak pengetahuan yang baru saja diperkenalkan, tetapi juga karena kesimpulan berikut:

**“Jika orde suatu grup adalah bilangan prima, maka menurut teorema Lagrange, ordo subgrupnya harus atau. Semua elemen dalam grup adalah generator kecuali

Penerapan Ed25519

Sekarang mari kita bicara tentang Ed25519, yang merupakan salah satu algoritma EdDSA. EdDSA memiliki 11 parameter (pemilihan spesifik dari parameter ini berdampak besar pada keamanan dan kinerja algoritme. Untuk pemilihan spesifik Ed25519, silakan merujuk ke tautan (

Selain itu, perlu disebutkan bahwa algoritma ini menggunakan kurva eliptik yang disebut Curve25519 (. Untuk kurva eliptik, kita hanya perlu mengetahui bahwa ada banyak sekali titik di atasnya, dan penambahan titik-titik ini bisa mendapatkan titik baru. The titik baru masih pada kurva. Titik-titik ini dan penambahan ini dapat membentuk grup. Perhatikan bahwa penambahan kurva eliptik (didefinisikan secara khusus.

Kami menyetujui notasi berikut:

Ini adalah algoritme interaktif, tetapi tidak masalah, ada trik yang disebut heuristik Fiat - Shamir (Ini dapat mengubah algoritme interaktif apa pun menjadi algoritme non-interaktif. Nantinya kita akan menggunakan algoritme non-interaktif.

Algoritme tanda tangan digital akan memberi kita API berikut:

Implementasi KeyGen

Keluarkan kunci pribadi dan kunci publik:

1. Menghasilkan seed secara acak (seed ini memiliki 32 byte. Kami menggunakan generator angka acak yang aman secara kriptografis yang disertakan dengan sistem.

pub fn menghasilkan (csprng: &mut T) -> SecretKeywhere

T: CryptoRng + RngCore,

{

biarkan mut sk: SecretKey = SecretKey([0u8; 32]);

csprng.fill_bytes(&mut sk.0);

sk

}

2. Perluas seed sekarang menjadi 64 byte (yaitu, xseed pada gambar. 32 byte rendah dari xseed adalah kunci pribadi kita (alias a). 32 byte tinggi disebut nonce, yang akan digunakan nanti Di dalamnya, fungsinya mirip dengan domain sperator.

pub struct ExpandedSecretKey { // xseed kunci pub(peti): Skalar, // a

pub(peti) nonce: [u8; 32], // nonce

}

fn from(rahasia_key: &'a SecretKey) -> ExpandedSecretKey {

biarkan mut h: Sha512 = Sha512::default();

biarkan mut hash: [u8; 64] = [0u8; 64];

biarkan mut lebih rendah: [u8; 32] = [0u8; 32];

biarkan mut atas: [u8; 32] = [0u8; 32];

h.update(secret_key.as_bytes());

hash.copy_from_slice(h.finalize().as_slice());

lebih rendah.copy_from_slice(&hash[00..32]);

atas.copy_from_slice(&hash[32..64]);

// Langkah ini adalah penjepit

lebih rendah [0] &= 248;

lebih rendah [31] &= 63;

lebih rendah [31] |= 64;

ExpandedSecretKey{ key: Scalar::from_bits(lower), nonce: upper, }

}

3. Gunakan kunci pribadi untuk menghasilkan kunci publik (kunci publik adalah titik pada kurva eliptik. Secara khusus, kami menggunakan titik dasar kurva eliptik untuk melakukan perkalian kurva eliptik untuk mendapatkan kunci publik. Skalar dalam perkalian diperoleh dengan memasangkan kunci privat Lakukan hash untuk mendapatkannya.

pub struct ExpandedSecretKey { // xseed kunci pub(peti): Skalar, // a

pub(peti) nonce: [u8; 32], // nonce

}

fn from(rahasia_key: &'a SecretKey) -> ExpandedSecretKey {

biarkan mut h: Sha512 = Sha512::default();

biarkan mut hash: [u8; 64] = [0u8; 64];

biarkan mut lebih rendah: [u8; 32] = [0u8; 32];

biarkan mut atas: [u8; 32] = [0u8; 32];

h.update(secret_key.as_bytes());

hash.copy_from_slice(h.finalize().as_slice());

lebih rendah.copy_from_slice(&hash[00..32]);

atas.copy_from_slice(&hash[32..64]);

// Langkah ini adalah penjepit

lebih rendah [0] &= 248;

lebih rendah [31] &= 63;

lebih rendah [31] |= 64;

ExpandedSecretKey{ key: Scalar::from_bits(lower), nonce: upper, }

}

Implementasi Tanda

Di sini Anda dapat menyebutkan teknik Fiat Shamir yang disebutkan sebelumnya, sebenarnya Anda hanya perlu mengganti semua angka acak yang disediakan oleh Verifier dengan hasil dari fungsi hash. Lihat komentar kode untuk detailnya.

pub fn sign(&self, pesan: & [u8] , public_key: &PublicKey) -> ed25519::Signature {

biarkan mut h: Sha512 = Sha512::new();

biarkan R: CompressedEdwardsY;

biarkan r: Skalar;

mari s: Skalar;

misalkan k: Skalar;

h.update(&self.nonce);

h.update(&pesan);

r = Scalar::from_hash(h); // r adalah bilangan acak dalam algoritme interaktif kami, tetapi di sini kami menggunakan hash.

R = (&r * &constants::ED25519_BASEPOINT_TABLE).compress(); // R = [r] B

h = Sha512::baru();

h.update(R.as_bytes());

h.update(public_key.as_bytes());

h.update(&pesan);

k = Skalar::dari_hash(h); // h = Sha512(R || A || M)

s = &(&k * &self.key) + &r; // s = r + h * a, h aslinya bilangan acak

InternalSignature { R, s }.into()

}

Penerapan Verifikasi

Pemverifikasi impl untuk PublicKey {

#[izinkan(bukan_ular_kotak)]

fn verifikasi(

&diri sendiri,

pesan: & [u8] ,

tanda tangan: &ed25519::Tanda tangan

) -> Hasil<(), SignatureError>

{

biarkan tanda tangan = Tanda Tangan Internal::coba_dari(tanda tangan)?;

biarkan mut h: Sha512 = Sha512::new();

biarkan R: EdwardsPoint;

misalkan k: Skalar;

biarkan minus_A: EdwardsPoint = -self.1;

h.update(signature.R.as_bytes());

h.update(self.as_bytes());

h.update(&pesan);

k = Scalar::from_hash(h); // Perhitungan h sama dengan tanda, h=Sha512(R||A||M)

R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(minus_A), &signature.s); // R' = [s] B - [h] A

if R.compress() == signature.R { // Jika R'==R, maka hasil verifikasi benar.

Oke(())

} kalau tidak {

Err(InternalError::VerifyError.into())

}

}

}

kode alamat (

Masalah skalabilitas

Ada banyak tempat yang harus diperhatikan dalam implementasi dan penggunaan algoritma kriptografi. Ketika kami mengatakan bahwa algoritme tanda tangan digital itu aman, umumnya berarti bahwa meskipun penyerang dapat memperoleh tanda tangan dari pesan apa pun (Chosen Message Attack), penyerang tetap tidak dapat memalsukan tanda tangannya. Ed25519 memenuhi sifat ini, tetapi bukan berarti Ed25519 benar-benar aman. Juga disebutkan dalam makalah asli bahwa masalah skalabilitas dapat diterima, dan algoritme asli memiliki masalah ini.

Dengan cara ini, baik tanda tangan yang baru dibuat maupun tanda tangan lama dapat berhasil diverifikasi. Masalah kelenturan memberi tahu kita bahwa tanda tangan tidak deterministik relatif terhadap pesan dan kunci publik.Ketika algoritme tanda tangan memiliki masalah kelenturan dan kode mengasumsikan bahwa tanda tangan bersifat deterministik, kemungkinan ada celah.

Menurut standar (sebenarnya tidak ada masalah skalabilitas. Karena dalam proses verifikasi, kami akan memeriksa apakah kurang dari, jika hasil pemeriksaan tidak benar, verifikasi gagal. Tetapi standar (muncul lebih lambat dari kertas (jadi di lingkungan sebenarnya, Masih ada implementasi Ed25519 yang memiliki masalah skalabilitas dan memerlukan implementasi yang kami periksa.

Ringkas

Terima kasih

*Terima kasih kepada Safeheron, penyedia layanan penyimpanan mandiri aset digital satu atap terkemuka, karena telah memberikan saran teknis profesional. *

> Referensi

> [1] .

> [2] .

> [3] .

> [4] .

> [5] . Peneliti Menggunakan Teori Grup untuk Mempercepat Algoritma — Pengantar Grup