Katman 1 Yayında

Asal Alanlar (Fp)

Modüler Aritmetik · Sonlu Alan Cebri ve Eliptik Eğri Temelleri

Modern şifreleme algoritmalarında ve özellikle Eliptik Eğri Kriptografisinde (ECC), matematiksel işlemler alışık olduğumuz gerçek sayılar ( $\mathbb{R}$ ) kümesi üzerinde gerçekleştirilmez. Lise veya üniversite matematik derslerinde gördüğümüz sürekli (continuous) eğriler, gerçek sayılar dünyasında pürüzsüz ve sonsuzdur. Ancak, bilgisayarların dijital dünyasında gerçek sayılarla kriptografi yapmak iki büyük probleme yol açar:

Yuvarlama Hataları (Hassasiyet Kaybı): Bilgisayarlar, ondalıklı sayıları (örneğin 0.1 veya 1.333...) sınırlı miktarda bit kullanarak saklar (floating-point). Bu durum, işlemler uzadıkça mikro düzeyde yuvarlama hatalarına (rounding errors) neden olur. Şifrelemede ise hassasiyet kaybına kesinlikle yer yoktur. Bir şifreli metin çözülürken tek bir bitin veya virgülden sonraki bir basamağın değişmesi, tüm mesajın yanlış çözülmesine veya güvenlik anahtarının bozulmasına yol açar.
Determinizm ve Sonsuzluk Problemi: Gerçek sayılar kümesi sonsuzdur ve sayılar sınırsız büyüklüğe ulaşabilir. Bilgisayar belleğinde sonsuz büyüklükte sayılarla işlem yapmak donanımsal taşmalara (overflow) sebep olur. Kriptografide her işlem girdisinin, her zaman aynı ve kesin çıktıyı ürettiği (deterministic) kapalı bir sistem kurulmalıdır.

Bu sorunları çözmek için matematikçiler, sürekli analiz yerine Soyut Cebir kurallarını devreye sokarak işlemleri Sonlu Alanlar (Finite Fields) üzerinde yürütürler. Sonlu alan, eleman sayısı sınırlı olan (örneğin sadece 17 elemanı olan veya 256 bitlik bir sayı kadar elemanı olan) ve kendi içinde kapalı bir matematiksel dünyadır. Bu dünyada yapılan toplama, çıkarma ve çarpma gibi tüm işlemler, kümenin sınırları dışına çıkamaz. Tıpkı saat aritmetiği gibi (saat 11'e 3 eklediğimizde 14 yerine tekrar 2'ye dönmesi gibi), işlemler belirli bir sınıra ulaştığında sıfırlanıp başa döner.

ECC standartlarında ve blokzincir protokollerinde (örneğin Bitcoin ve Ethereum'un kullandığı secp256k1 eğrisinde) en yaygın olarak kullanılan sonlu alan türü Asal Alanlar (Prime Fields), diğer bir deyişle $\mathbb{F}_p$ veya Galois Alanı temsilcisi olan $GF(p)$ yapısıdır. Burada $p$ , devasa bir asal sayıdır. Asal alanların kriptografideki önemi şu temel detaylara dayanır:

Kümeyi Asal Sayı ile Sınırlandırmak: Bir sonlu alanın sınır değeri ( $p$ ) asal seçildiğinde, kümedeki sıfırdan farklı her elemanın modüler çarpımsal tersi (yani o sayıyla çarpıldığında modülde 1 sonucunu veren tersi) kesinlikle mevcuttur. Eğer sınır değeri asal olmasaydı (örneğin 12 gibi bir bileşik sayı olsaydı), bazı sayılar için bölme işlemi yapılamazdı. Asal sayı seçimi, tüm temel matematiksel işlemlerin (toplama, çıkarma, çarpma ve bölme/tersini alma) kusursuz bir cisim (field) yapısı içinde çalışmasını garanti eder.
256-Bit Güvenlik Duvarı: Kriptografik standartlarda $p$ asal sayısı öylesine büyüktür ki (secp256k1 eğrisinde yaklaşık $2^{256} - 2^{32} - 977$ ), kümenin elemanlarını tek tek denemek evrenin ömründen daha uzun sürer. Bu devasa sayı uzayı, eliptik eğriler üzerindeki nokta işlemlerinin tek yönlü fonksiyonlara dönüşmesini sağlayarak gizli anahtarlarımızın kırılmasını imkansız hale getirir.

ℤ_n

Modüler Aritmetik ve Cebirsel Cisim (Field) Yapısı

Asal alan $\mathbb{F}_p$ (veya $GF(p)$ ), elemanları yalnızca sıfır ile $p-1$ arasındaki tam sayılardan oluşan sonlu bir kümedir. Bu matematiksel dünyadaki tüm toplama, çıkarma ve çarpma işlemleri, $p$ asal sayısına bölünerek elde edilen kalanlar üzerinden (modüler aritmetik) yürütülür:

a + b \pmod p \quad \text{ve} \quad a \cdot b \pmod p

Basitçe Ne Anlama Gelir?
Eğer sınır asal sayımızı (modül) $p = 5$ seçersek, tüm evrenimiz yalnızca beş sayıdan ibarettir: $\{0, 1, 2, 3, 4\}$ . Bu dünyada negatif sayılar, kesirler veya 5'ten büyük sayılar doğrudan var olamaz. Yapılan her işlemin sonucu hemen 5'e bölünür ve sadece kalan kısmı yazılır. Örneğin:

Toplama: Normalde $3 + 4 = 7$ 'dir. Ancak bizim dünyamızda 7'nin 5 ile bölümünden kalan $2$ olduğu için: $3 + 4 \equiv 2 \pmod 5$ yazılır.
Çarpma: Normalde $3 \cdot 4 = 12$ 'dir. 12'nin 5 ile bölümünden kalan $2$ olduğu için: $3 \cdot 4 \equiv 2 \pmod 5$ olur.

Bir sayı kümesinin soyut cebirde bir Cisim (Field) (tüm dört temel aritmetik işlemin sorunsuz yapılabildiği güvenli bir oyun alanı) oluşturabilmesi için aşağıdaki üç temel kuralı sağlaması gerekir:

Toplama ve Çarpma Altında Kapalılık (Closure):
Matematiksel Karşılığı: İşlem sonucu her zaman kümenin bir elemanıdır.
Basitçe Anlamı: Bu dünyadaki hangi iki sayıyı toplarsanız toplayın veya çarparsanız çarpın, sonuç modülden geçtikten sonra yine bizim kümemizin ( $0$ ile $p-1$ arası) bir üyesi olur. Sistem dışına kaçamazsınız; evren kendi içine bükülmüştür.
Birim Elemanların Varlığı (Identity Elements):
Matematiksel Karşılığı: Toplama için birim eleman $0$ , çarpma için birim eleman $1$ 'dir.
Basitçe Anlamı: "Etkisiz elemanlar" normal matematikte olduğu gibi bu dünyada da mevcuttur. Bir sayıyı $0$ ile toplamak veya $1$ ile çarpmak sayının değerini değiştirmez. Aritmetiğin temel dengesi korunur.

Ters Elemanın Varlığı (Existence of Inverses):
Matematiksel Karşılığı: Toplamsal ters (

-a \equiv p - a

) ve çarpımsal ters (

a^{-1}

) mevcuttur.
Basitçe Anlamı: Her sayının bu dünyada onu "sıfırlayan" (toplamsal olarak sıfıra götüren) veya "birleyen" (çarpımsal olarak bire götüren) bir nötrleyici eşi bulunur. Bu yapılar çıkarma ve bölme işlemlerinin temelini oluşturur:

Ters Eleman Türü	Matematiksel Gösterim	Kriptografik Görevi	Basitçe Ne Anlama Gelir? (Örnek: mod 5)
Toplamsal Ters Çıkarma yerine geçer	`-a ≡ p - a (mod p)`	Nokta koordinatlarını ters çevirirken ve çıkarma işlemlerinde kullanılır.	Bir sayıyı sıfırlamak için ona ne eklemeliyiz? 3'ün tersi 2'dir; çünkü `3 + 2 = 5 ≡ 0 (mod 5)`. Negatif sayılar yerine pozitif modüler karşılıkları yazılır.
Çarpımsal Ters Bölme yerine geçer	`a • a⁻¹ ≡ 1 (mod p)`	Nokta toplamada eğim (slope) hesaplarken bölme yapmak yerine kullanılır.	Bir sayıyı bir yapmak için neyle çarpmalıyız? 2'nin tersi 3'tür; çünkü `2 • 3 = 6 ≡ 1 (mod 5)`. Bölmek yerine tersiyle çarparız (`2⁻¹ = 3`). Sınır sayımızın asal olması her sayının bir tersi bulunmasını sağlar.

a⁻¹

Çarpımsal Ters (Modular Inverse) Hesaplama

Kriptografik eliptik eğri işlemlerinde (örneğin eğri üzerindeki iki noktayı toplarken eğim hesaplama adımında) bir sayıyı diğer bir sayıya bölmemiz gerekir. Ancak sonlu alanlar dünyasında ondalıklı/kesirli sayılar yasak olduğu için doğrudan bölme işlemi yapılamaz. Bölme işlemi yerine, bölünen sayıyı bölen sayının çarpımsal tersi ( $b^{-1}$ ) ile çarparız:

\frac{a}{b} \equiv a \cdot b^{-1} \pmod p

Bir $b$ sayısının modüler tersini ( $b^{-1}$ ) hesaplamak, "Bu dünyada $b$ sayısını hangi tam sayı ile çarparsak sonuç modüle göre 1 olur?" sorusuna yanıt aramaktır. Bu ters değeri bulmak için bilgisayarlarda kullanılan iki temel algoritma vardır:

1. Genişletilmiş Öklid Algoritması (Extended Euclidean)

İki sayının en büyük ortak bölenini ( $\gcd$ ) bulurken geriye doğru adımları izleyen ve modüler tersi hızlıca hesaplayan klasik bir yöntemdir. $p$ sınır değerimiz asal sayı olduğundan, sıfır dışındaki her $b$ sayısı için en büyük ortak bölen her zaman 1'dir ( $\gcd(b, p) = 1$ ). Algoritma şu eşitliği çözerek modüler tersi bulur:

b \cdot x + p \cdot y = 1 \implies b \cdot x \equiv 1 \pmod p

Buradaki bilinmeyen $x$ katsayısı, doğrudan $b$ sayısının çarpımsal tersi olan $b^{-1}$ değerine eşit olur. Genişletilmiş Öklid oldukça hızlı çalışır, ancak işlem süresi girdinin büyüklüğüne göre değiştiği için zamanlama saldırısı (timing attack) riskleri barındırır.

2. Fermat'ın Küçük Teoremi (Fermat's Little Theorem)

Matematikçi Pierre de Fermat'ın bulduğu ve asal sayılar dünyasında her zaman geçerli olan sihirli bir kuraldır. Eğer sınır değerimiz olan $p$ bir asal sayı ise ve elimizdeki $b$ sayısı bu asala bölünmüyorsa, teorem bize şu eşitliği garanti eder:

b^{p-1} \equiv 1 \pmod p

Bu eşitliğin her iki tarafını da matematiksel olarak $b^{-1}$ ile çarparsak, şifrelemede sıklıkla kullanılan pratik modüler ters formülünü elde ederiz:

b^{-1} \equiv b^{p-2} \pmod p

Basitçe Anlamı: Bir sayının modüler tersini bulmak için o sayının $p-2$ . kuvvetini alıp modüle göre kalanını hesaplamamız yeterlidir. Bu yöntem sabit adımlı üs alma algoritmalarıyla çalıştırılabildiğinden, işlem süresi sayıların büyüklüğüne göre değişmez.

Kriptografik Güvenlik (Zamanlama Saldırılarına Karşı Koruma): Genişletilmiş Öklid algoritması hızlı olsa da girdi sayılarına göre değişken zamanlarda sonuçlanır. Saldırganlar bu süre farklarını ölçerek gizli anahtarı ele geçirebilir (Timing Attack). Fermat'ın Küçük Teoremi ise sabit zamanda (constant-time) çalıştığı için modern güvenli şifreleme kütüphanelerinde (örneğin OpenSSL veya Rust tabanlı kripto paketlerinde) side-channel saldırılarını engellemek adına öncelikli olarak tercih edilir.

F_p

Asal Alanların Eliptik Eğriler İçin Önemi

Normalde gerçek sayılar ( $\mathbb{R}$ ) üzerinde çizilen bir eliptik eğri grafiği pürüzsüz, dalgalı ve sürekli bir çizgi oluşturur. Ancak koordinatları asal alan $\mathbb{F}_p$ ile sınırlandırdığımızda, sürekli çizgi yapısı tamamen kaybolur. Eğri üzerindeki noktalar, sadece tam sayı koordinatlarına oturabilen ve 2D düzlem üzerinde rastgele dağılmış gibi görünen kesikli bir nokta bulutuna (discrete scatter plot) dönüşür.

Bu kesikli yapı, eliptik eğri üzerindeki matematiksel işlemleri tek yönlü bir geçiş kapısı haline getirir:

Tek Yönlü Nokta Çarpımı: Bir başlangıç noktasını ( $P$ ) kendisiyle $k$ defa toplamak (nokta çarpımı: $Q = k \cdot P$ ) hızlı ve kolaydır.
Ayrık Logaritma Engeli (ECDLP): Sadece başlangıç noktası $P$ ve sonuç noktası $Q$ verileri bilindiğinde, aradaki $k$ çarpanını (yani gizli anahtarı) bulmak matematiksel olarak imkansız düzeyde zordur. Nokta bulutundaki dağınıklık nedeniyle geriye dönük arama yapmanın hiçbir düzenli formülü yoktur. Bu zorluğa Eliptik Eğri Ayrık Logaritma Problemi (ECDLP) denir ve blokzincir ağlarındaki cüzdan adreslerimizin ve imzalarımızın güvenliğini sağlayan ana korumadır.

🦀

Rust ile Fp Modüler Aritmetik ve Ters Eleman Doğrulaması

Aşağıdaki Rust kodu, $\mathbb{F}_p$ asal alanı üzerinde iki temel kriptografik işlemi sıfırdan uygular: hızlı modüler üs alma ve Fermat'ın Küçük Teoremi ile çarpımsal ters bulma. Kod aynı zamanda hesaplanan tersin doğruluğunu yerinde doğrular. Her yapısal bileşen aşağıda açıklanmaktadır.

PrimeField Yapısı

PrimeField yapısı, tek bir alan parametresi tutar: asal modül p. Tüm diğer metotlar bu yapıya bağlı olduğundan, aynı kod tabanıyla farklı asal sayılar için farklı alanlar oluşturmak mümkündür. Gerçek dünya kütüphanelerinde $p$ değeri 256-bit veya daha büyük bir asal sayıdır; simülasyonda sadelik için küçük bir asal kullanılmaktadır.

mod_pow: Kare-ve-Çarp ile Hızlı Üs Alma

Kriptografide en sık gerçekleştirilen işlem, büyük taban ve üslerin modüler üs almasıdır: $\text{base}^{\text{exp}} \bmod p$. Bunu naif yöntemle — tabanı ardarda çarparak — yapmak $O(\text{exp})$ işlem gerektirir; 256-bit üsler için bu pratik değildir.

mod_pow, kare-ve-çarp (square-and-multiply) yöntemini uygular. Üssün her biti soldan sağa taranır: her adımda sonuç karelenerek mod alınır; eğer mevcut bit 1 ise ayrıca tabanla çarpılır. Bu sayede 256-bit bir üs için yalnızca $\sim\!256$ işlemle sonuca ulaşılır — $O(\log \text{exp})$ karmaşıklık. Aradaki ara çarpımlar her adımda mod alındığından sayılar hiçbir zaman $p^2$ sınırını aşmaz, taşma riski yoktur.

mod_inverse: Fermat Teoremi ile Modüler Ters

Bölme işleminin yasak olduğu sonlu alanlarda $a / b$ yerine $a \cdot b^{-1} \bmod p$ yazılır. mod_inverse, $b^{-1}$'i bulmak için Fermat'ın Küçük Teoremi'nden doğrudan türetilen formülü kullanır: \[ b^{-1} \equiv b^{p-2} \pmod p \] Yani ters alma işlemi, mod_pow(b, p - 2) çağrısına indirgenir. Girdi olarak $b = 0$ gelirse — sıfırın modüler tersi tanımsız olduğundan — fonksiyon hata döndürür ya da None üretir. Bu yaklaşım sabit zamanda ($\text{constant-time}$) çalışır: hesaplama süresi $b$'nin değerine bağlı değil, yalnızca $\log p$'ye bağlıdır. Zamanlama saldırıları bu nedenle etkisiz kalır.

verify_inverse: Yerinde Doğrulama

Hesaplanan ters elemanın gerçekten doğru olduğunu kanıtlamak için kod, $b \cdot b^{-1} \bmod p$ çarpımını hesaplar ve sonucun $1$'e eşit olup olmadığını kontrol eder. Bu adım matematiksel bir sanity check'tir: çarpımsal tersinin tanımı gereği $b \cdot b^{-1} \equiv 1 \pmod p$ olmalıdır. Gerçek üretim kütüphanelerinde bu doğrulama tür sistemi veya birim testlerle yapılır; burada görünür biçimde yer alması algoritmanın ne yaptığını somutlaştırır.

                  
                  
                  
                

                    
                      
                      
                    
                    prime_field.rs
                    RUST
                  

                    
                    ● Constant-Time Arithmetic
                  

                /// Sonlu Asal Alan işlemlerini yöneten yapı
pub struct PrimeField {
    pub p: u128, // Büyük asal modül değeri
}

impl PrimeField {
    /// Modüler toplama: (a + b) mod p
    pub fn add(&self, a: u128, b: u128) -> u128 {
        ((a % self.p) + (b % self.p)) % self.p
    }

    /// Modüler çarpma: (a * b) mod p
    pub fn mul(&self, a: u128, b: u128) -> u128 {
        ((a % self.p) * (b % self.p)) % self.p
    }

    /// Modüler üs alma: (base^exp) mod p (Square-and-Multiply)
    pub fn pow(&self, mut base: u128, mut exp: u128) -> u128 {
        let mut result = 1;
        base = base % self.p;
        while exp > 0 {
            if exp % 2 == 1 {
                result = (result * base) % self.p;
            }
            base = (base * base) % self.p;
            exp /= 2;
        }
        result
    }

    /// Fermat'ın Küçük Teoremi ile çarpımsal ters bulma: a^(p-2) mod p
    pub fn invert(&self, a: u128) -> Option<u128> {
        if a % self.p == 0 {
            return None; // Sıfırın çarpımsal tersi yoktur
        }
        Some(self.pow(a, self.p - 2))
    }
}

fn main() {
    // 256-bit benzeri küçük bir asal sayı seçelim
    let field = PrimeField { p: 1000000007 }; // Asal sayı

    let val = 123456789;
    
    // Çarpımsal tersini hesaplayalım
    if let Some(inv) = field.invert(val) {
        println!("Sayi: {}", val);
        println!("Moduler Ters (val^-1): {}", inv);
        
        // Doğrulayalım: (val * val^-1) mod p == 1 olmalı
        let proof = field.mul(val, inv);
        println!("Dogrulama (val * val^-1) mod p = {}", proof);
        assert_eq!(proof, 1, "Hata: Modüler ters doğrulanamadı!");
    } else {
        println!("Sıfırın tersi yoktur.");
    }
}
              