> Bu makale, eliptik eğri tabanlı dijital imza algoritması Ed25519'un uygulama ilkesini ve ölçeklenebilirliğini tanıtacaktır.

Yazan: Ah Wei

Ed25519, verimli, güvenli ve yaygın olarak kullanılan, eliptik eğriye dayalı bir dijital imza algoritmasıdır. TLS 1.3, SSH, Tor, ZCash, WhatsApp ve Signal'de kullanılır. Bu makale temel olarak aşağıdaki noktaları açıklamaktadır:

1. Grup teorisi hakkında biraz bilgi verin, amaç herkesin Ed25519 ilkesi ve ölçeklenebilirlik sorunu hakkında bir sezgiye sahip olmasını sağlamaktır. Daha derin bir anlayış için başka materyallere başvurmanız gerekir;
2. ed25519-dalek rust kitaplığının 1.0.1 sürümü için ed25519'un uygulanmasını açıklayın;
3. Kütüphanenin genişletilebilirliğini açıklar.

Matematik Temelleri İncelemesi

Grupların tanımı ve özellikleri

Grup teorisi, soyut cebir araştırmasının içeriğidir, ancak soyut cebirin bazı fikirleri programcılara çok aşinadır. Nesne yönelimli kalıtım iyi bir örnektir.Alt sınıfların üst sınıfı miras aldıktan sonra üst sınıfta tanımlanan yöntemleri kullanabileceğini hepimiz biliyoruz. Soyut cebir, soyut bir veri yapısı için bazı özelliklerin tanımlanması olarak anlaşılabilir ve bu özelliklerden türetilen teoremler tüm alt sınıflar için geçerlidir.

Şimdi metaforu kullanarak grubun veri yapısının nasıl tanımlandığını görelim.

Bir grup, bir işlemden (herhangi bir ikili işlemle gösterilir) ve aşağıdaki özellikleri sağlayan bazı öğelerden oluşur:

Bundan birçok ilginç teorem türetilebilir:

Birkaç örnek vermek gerekirse:

• ..., −2, −1, 0, 1, 2, ... tamsayıları ve toplama bir gruptur çünkü yukarıdaki dört özelliği sağlarlar
• Tamsayılar ve çarpma, tersine çevrilebilirliği sağlamadıkları için grup değildir, 4 x 1/4 = 1, ancak 1/4 bir tam sayı değildir

Grup Teorisi Terminolojisi Kesildi

Lagrange Teoremi

Şimdi çok ilginç bir teorem tanıtalım, bu teoremin türetilmesi makalenin sonunda alıntılanan videoda.

** "Grubun sırası, alt grubun sırasına göre bölünür."**

Bu teorem neden ilginçtir, sadece kanıtlama süreci az önce tanıtılan pek çok bilgiyi birbirine bağladığı için değil, aynı zamanda aşağıdaki sonuçlar nedeniyle de:

**"Grubun mertebesi bir asal sayı ise, Lagrange teoremine göre alt grubun mertebesi veya olmalıdır. Gruptaki tüm elemanlar, hariç

Ed25519'un uygulanması

Şimdi EdDSA algoritmalarından biri olan Ed25519'dan bahsedelim. EdDSA'nın 11 parametresi vardır (bu parametrelerin özel olarak seçilmesi, algoritmanın güvenliği ve performansı üzerinde büyük bir etkiye sahiptir. Ed25519'un özel seçimi için lütfen bağlantıya bakın (

Ek olarak, bu algoritmanın Curve25519 () adında bir eliptik eğri kullandığını belirtmekte fayda var. yeni nokta hala eğri üzerindedir.Bu noktalar ve bu ekleme bir grup oluşturabilir.Eliptik eğri toplamanın (özel olarak tanımlandığına dikkat edin.

Aşağıdaki gösterimde hemfikiriz:

Bu etkileşimli bir algoritma ama önemli değil, Fiat - Shamir buluşsal yöntemi diye bir hile var (Her etkileşimli algoritmayı etkileşimsiz algoritmaya çevirebilir. Sonunda etkileşimsiz bir algoritma kullanacağız.

Dijital imza algoritması bize aşağıdaki API'yi verecektir:

KeyGen uygulaması

Bir özel anahtar ve bir ortak anahtar çıktısı alın:

1. Rastgele bir tohum oluşturun (bu tohum 32 bayta sahiptir. Sistemle birlikte gelen kriptografik olarak güvenli bir rasgele sayı üreteci kullanıyoruz.

pub fn oluşturmak (csprng: &mut T) -> SecretKeywhere

T: CryptoRng + RngCore,

{

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

csprng.fill_bytes(&mut sk.0);

sk

}

2. Tohumu şimdi 64 bayta genişletin (yani, şekildeki xseed. xseed'in düşük 32 baytı bizim özel anahtarımızdır (aka a). Yüksek 32 bayta nonce denir ve bu daha sonra kullanılacaktır. işlevi etki alanı operatörüne benzer.

pub struct ExpandedSecretKey { // xseed pub(crate) anahtarı: Skaler, // a

pub(sandık) nonce: [u8; 32], // yok

}

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

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

mut hash yapalım: [u8; 64] = [0u8; 64];

mut'u düşür: [u8; 32] = [0u8; 32];

mut üst olsun: [u8; 32] = [0u8; 32];

h.update(secret_key.as_bytes());

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

alt.kopya_from_slice(&hash[00..32]);

üst.kopya_from_slice(&hash[32..64]);

// Bu adım kelepçe

daha düşük [0] &= 248;

daha düşük [31] &= 63;

daha düşük [31] |= 64;

ExpandedSecretKey{ anahtar: Scalar::from_bits(alt), nonce: üst, }

}

3. Genel anahtarı oluşturmak için özel anahtarı kullanın (ortak anahtar, eliptik eğri üzerindeki bir noktadır. Özellikle, genel anahtarı elde etmek için eliptik eğri çarpmasını gerçekleştirmek için eliptik eğrinin taban noktasını kullanırız. Çarpmadaki skaler özel anahtarın eşleştirilmesiyle elde edilir. Bunu elde etmek için bir hash yapın.

pub struct ExpandedSecretKey { // xseed pub(crate) anahtarı: Skaler, // a

pub(sandık) nonce: [u8; 32], // yok

}

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

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

mut hash yapalım: [u8; 64] = [0u8; 64];

mut'u düşür: [u8; 32] = [0u8; 32];

mut üst olsun: [u8; 32] = [0u8; 32];

h.update(secret_key.as_bytes());

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

alt.kopya_from_slice(&hash[00..32]);

üst.kopya_from_slice(&hash[32..64]);

// Bu adım kelepçe

daha düşük [0] &= 248;

daha düşük [31] &= 63;

daha düşük [31] |= 64;

ExpandedSecretKey{ anahtar: Scalar::from_bits(alt), nonce: üst, }

}

İşaretin Uygulanması

Burada daha önce bahsedilen Fiat Shamir tekniğinden bahsedebiliriz.Aslında Verifier tarafından sağlanan tüm rasgele sayıları bir hash fonksiyonunun sonucuyla değiştirmeniz yeterlidir. Ayrıntılar için kod yorumlarına bakın.

pub fn işareti(&self, mesaj: & [u8] , public_key: &PublicKey) -> ed25519::İmza {

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

R: CompressedEdwardsY olsun;

r: skaler olsun;

s: skaler;

k: skaler olsun;

h.update(&self.nonce);

h.update(&mesaj);

r = Scalar::from_hash(h); // r, etkileşimli algoritmamızda rastgele bir sayıdır, ancak burada bir hash kullanıyoruz.

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

h = Sha512::new();

h.update(R.as_bytes());

h.update(public_key.as_bytes());

h.update(&mesaj);

k = Skaler::from_hash(h); // h = Sha512(R || A || M)

s = &(&k * &self.key) + &r; // s = r + h * a, h başlangıçta rasgele bir sayıdır

Dahili İmza { R, s }.into()

}

Doğrulamanın Uygulanması

impl Doğrulayıcı PublicKey için {

#[izin ver(non_snake_case)]

fn doğrulamak(

&kendi,

İleti: & [u8] ,

imza: &ed25519::İmza

) -> Sonuç<(), SignatureError>

{

imza = Dahili İmza::try_from(imza)?;

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

R: EdwardsPoint olsun;

k: skaler olsun;

eksi_A olsun: EdwardsPoint = -self.1;

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

h.update(self.as_bytes());

h.update(&mesaj);

k = Scalar::from_hash(h); // h'nin hesaplanması işaretteki ile aynıdır, h=Sha512(R||A||M)

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

if R.compress() == imza.R { // R'==R ise doğrulama sonucu doğrudur.

Tamam(())

} başka {

Err(InternalError::VerifyError.into())

}

}

}

kod adresi (

Ölçeklenebilirlik sorunları

Kriptografik algoritmaların uygulanmasında ve kullanımında dikkat edilmesi gereken birçok yer vardır. Bir dijital imza algoritmasının güvenli olduğunu söylediğimizde, genellikle saldırgan herhangi bir mesajın imzasını elde etse bile (Seçilmiş Mesaj Saldırısı), yine de imzayı taklit edemez demektir. Ed25519 bu özelliği karşılar, ancak Ed25519'un kesinlikle güvenli olduğu anlamına gelmez. Ölçeklenebilirlik sorununun kabul edilebilir olduğu ve orijinal algoritmanın bu soruna sahip olduğu orijinal makalede de belirtilmiştir.

Bu sayede hem yeni oluşturulan imza hem de eski imza başarıyla doğrulanabilir. Dövülebilirlik sorunu bize, imzanın mesaja ve genel anahtara göre deterministik olmadığını söyler.İmza algoritmasında bir işlenebilirlik sorunu olduğunda ve kod, imzanın deterministik olduğunu varsayarsa, muhtemelen boşluklar olacaktır.

Standarda göre (aslında ölçeklenebilirlik sorunu yok. Çünkü doğrulama sürecinde küçük olup olmadığını kontrol edeceğiz, kontrol sonucu doğru değilse doğrulama başarısız oluyor. Ancak standart (kağıttan sonra çıkıyor) (yani gerçek ortamda, hala ölçeklenebilirlik sorunları olan ve incelediğimiz uygulamaları gerektiren Ed25519 uygulamaları vardır.

Özetle

Teşekkürler

*Tek noktadan dijital varlık kendi kendine gözetim hizmeti sağlayıcısı olan Safeheron'a profesyonel teknik tavsiye sağladığı için teşekkür ederiz. *

> Referanslar

> [1] .

> [2] .

> [3] .

> [4] .

> [5] . Araştırmacılar Algoritmaları Hızlandırmak İçin Grup Teorisini Kullanıyor — Gruplara Giriş