RSA şifreleme: Asal sayılar internet bağlantılarını nasıl korur?

Bir alışveriş sitesine girdiğinizde tarayıcınız ile sitenin sunucusu, daha önce hiç karşılaşmamış olmalarına rağmen birbirine güvenmenin bir yolunu bulur. Bu güvenin arkasında bir dizi matematiksel işlem vardır. Bu işlemlerin en tanınmışlarından biri RSA’dır. Adını, yöntemi 1977’de tanımlayan Ron Rivest, Adi Shamir ve Leonard Adleman’ın soyadlarının baş harflerinden alır.

RSA’nın dayandığı fikir sade bir asimetridir: İki büyük asal sayıyı çarpmak bir bilgisayar için saniyenin küçük bir kesrinde biter. Oysa yalnızca çarpımı bilerek o iki asalı geri bulmak, bugün bilinen yöntemlerle pratikte yapılamayacak kadar uzun sürer. Bu yazıda RSA’yı elle izlenebilecek küçük sayılarla kuracak, gerçek anahtarların neden yüzlerce basamaklı olduğunu ve yöntemin sınırlarını konuşacağız.

Asal sayılar ve tek yönlü bir kapı

Asal sayı, 1’den büyük olan ve 1 ile kendisinden başka pozitif böleni bulunmayan doğal sayıdır: 2, 3, 5, 7, 11, 13 ve devamı. Aritmetiğin temel teoremi, 1’den büyük her doğal sayının sıralama dışında tek bir biçimde asalların çarpımı olarak yazılabileceğini söyler. Örneğin 91 = 7 × 13’tür ve 91’i başka asallarla yazmanın yolu yoktur. Asalların sonsuz sayıda olduğu ise Antik Çağ’da ispatlanmıştı. Bu ispatın geçtiği eseri Öklid’in Elemanlar’ı üzerine yazımızda bulabilirsiniz.

Çarpma ile çarpanlara ayırma arasında büyük bir fark vardır. 7 ile 13’ü çarpmak bir an sürer, 91’in çarpanlarını bulmak da birkaç denemeyle olur. Sayılar büyüdükçe durum değişir. Onluk tabanda 600 basamağı aşan bir sayının hangi iki asalın çarpımı olduğunu bulmak için bilinen hiçbir klasik algoritma makul bir sürede sonuç vermez.

Kriptografide bir yönde kolay, ters yönde zor işlemlere “tek yönlü” denir. RSA’nın kullandığı işlem bir adım daha ileri gider: Gizli bir bilgiyi, yani asalları bilen biri için ters yön de kolaylaşır. Bu gizli bilgiyi bir tür arka kapı gibi düşünebilirsiniz.

Saat aritmetiği: mod işlemi

RSA’nın dili modüler aritmetiktir. Duvar saatini düşünün. Saat 10’dan 5 saat sonra 15 değil, 3 olur; çünkü 12’ye ulaşınca başa döneriz. Bunu 15 ≡ 3 (mod 12) biçiminde yazar, “15, 12’ye göre 3’e denktir” diye okuruz. Uygulamada “a mod n”, a’nın n’ye bölümünden kalan demektir.

Birkaç örnek:

• 100 mod 91 = 9, çünkü 100 = 91 + 9.
• 29 mod 8 = 5, çünkü 29 = 3 × 8 + 5.
• 145 mod 72 = 1, çünkü 145 = 2 × 72 + 1.

Son örneği birazdan kullanacağız. Modüler aritmetikte büyük kuvvetleri hesaplamak da sanıldığı kadar ağır değildir, çünkü her adımda kalanı alarak sayıları küçük tutarız. Örneğin 10⁴ mod 91’i bulmak için önce 10² = 100 ≡ 9 hesaplanır, sonra 9² = 81 bulunur. Demek ki 10⁴ ≡ 81 (mod 91).

Oyuncak örnek: 7 ve 13 ile anahtar üretmek

Aşağıdaki örnek, gerçek kullanımdan çok uzak, basitleştirilmiş bir modeldir. Sayılar her adım elle izlenebilsin diye bilerek küçük seçildi.

1. İki asal seçelim: p = 7 ve q = 13.
2. Çarpımı hesaplayalım: n = p × q = 91. Bu sayı herkese açıklanacak.
3. Yardımcı sayıyı bulalım: φ(n) = (p − 1) × (q − 1) = 6 × 12 = 72. Bu sayı, 1’den 91’e kadar olup 91 ile ortak böleni bulunmayan sayıların adedidir ve Euler’in adıyla anılır. φ(n)’yi hesaplamak için p ile q’yu bilmek gerekir, bu yüzden gizli kalır.
4. Açık üssü seçelim: 72 ile ortak böleni olmayan bir e seçelim. 72 = 2³ × 3² olduğundan e = 5 uygundur.
5. Gizli üssü bulalım: e × d ≡ 1 (mod 72) koşulunu sağlayan d’yi arıyoruz. 5 × 29 = 145 ve 145 mod 72 = 1 olduğundan d = 29 olur.

Artık iki anahtarımız var:

• Açık anahtar: (n = 91, e = 5). Herkes görebilir.
• Gizli anahtar: d = 29. Yalnızca sahibinde kalır.

Şifrele, sonra çöz

Mesajımız bir sayı olsun: m = 10. Gerçek sistemlerde metin önce sayılara dönüştürülür ve özel dolgu kurallarıyla işlenir. Bu ayrıntıyı şimdilik bir kenara bırakıyoruz.

Şifreleme: c = m⁵ mod 91 = 10⁵ mod 91.

10⁵ = 100 000 ve 100 000 = 91 × 1098 + 82 olduğundan c = 82 çıkar.

Şifreli mesaj olan 82 herkesin gözü önünde gönderilebilir. Açık anahtarı bilen biri bile 82’den 10’a kolayca dönemez. Bunun için d gerekir; d’yi bulmak için φ(n), φ(n) için de 91’in çarpanları gerekir.

Çözme: m = 82²⁹ mod 91.

Bu hesap elle uzun sürer ama her adımda kalan alındığında bir bilgisayar onu anında yapar ve sonuç 10 çıkar. Mesaj geri gelmiştir.

Peki neden işe yarıyor? Euler’in bir teoremine göre, n ile ortak böleni olmayan her a sayısının φ(n). kuvveti, mod n’de 1’e denktir. Bizim örneğimizde e × d = 145 = 2 × 72 + 1 olduğundan şu zinciri kurabiliriz: (m⁵)²⁹ = m¹⁴⁵ = (m⁷²)² × m ≡ 1 × m = m (mod 91). Mesajın 91 ile ortak böleni olduğu nadir durumda da sonuç doğru çıkar, ancak bunun gösterimi biraz daha uzundur.

Aynı düzen, tersine çalıştırıldığında dijital imza üretir. Gizli anahtarla işlenen bir sayı açık anahtarla kontrol edilir. Böylece herkes imzayı doğrulayabilir ama yalnızca gizli anahtarın sahibi imza atabilir.

Gerçek anahtarlar ne kadar büyük?

Oyuncak örneğimizde bir saldırgan 91’i bir anda 7 × 13 diye ayırır. Bu yüzden gerçek RSA anahtarlarında n çok büyük bir sayıdır ve bit cinsinden ölçülür. Bugün yaygın öneri, en az 2048 bitlik bir n kullanmaktır. Bu, onluk tabanda yaklaşık 617 basamaklı bir sayı demektir. Yaygın kabul gören değerlendirmelerde 2048 bitlik RSA yaklaşık 112 bitlik, 3072 bitlik RSA ise 128 bitlik güvenlik düzeyine denk sayılır.

Çarpanlara ayırma alanındaki ilerlemeyi gösteren bir örnek: 2020’de 250 basamaklı, 829 bitlik RSA-250 adlı sayı, çok sayıda bilgisayarın aylar süren ortak çalışmasıyla çarpanlarına ayrıldı. Toplam hesap yükü yaklaşık 2700 işlemci yılı olarak açıklandı. Bu sonuç önemli bir başarıdır, ama günlük kullanımdaki 2048 bitlik anahtarların hâlâ çok gerisindedir.

Bu kadar büyük asalların nasıl bulunduğunu da merak edebilirsiniz. Bilgisayar rastgele büyük tek sayılar üretir ve onları hızlı asallık testlerinden geçirir. Asal sayılar büyük sayılar arasında da yeterince sık bulunduğu için bu arama kısa sürer.

İnternette RSA ne iş yapar?

Adres çubuğunda https gördüğünüz güvenli bağlantılarda iki ayrı iş vardır. Birincisi, karşıdaki sunucunun gerçekten iddia ettiği site olduğunu doğrulamaktır. İkincisi, konuşmayı şifreleyecek ortak bir gizli anahtar üzerinde anlaşmaktır. Asıl veri, çok daha hızlı çalışan simetrik şifrelerle korunur. RSA gibi açık anahtarlı yöntemler ise işlem yükü ağır olduğu için kimlik doğrulama ve anahtar anlaşması aşamalarında devreye girer.

Güvenli bağlantı protokolünün güncel sürümü olan TLS 1.3’te, RSA ile anahtarın doğrudan taşınması seçeneği kaldırıldı. Ortak anahtar Diffie–Hellman türü yöntemlerle oluşturulur. RSA ise sertifikalardaki dijital imzalarda kullanılabilmeye devam eder; protokol eliptik eğrilere dayanan imzalara da izin verir. Yani RSA, interneti tek başına koruyan bir sistem değildir. Büyük bir araç kutusunun önemli ve tarihsel olarak öncü parçalarından biridir.

Kısa tarihçe ve kuantum sorusu

1976’da Whitfield Diffie ve Martin Hellman, iki tarafın önceden gizli bir bilgi paylaşmadan açık bir kanal üzerinden ortak anahtar oluşturabileceğini gösterdi. Bu fikir, açık anahtarlı kriptografinin kapısını araladı. Bir yıl sonra Rivest, Shamir ve Adleman hem şifreleme hem imza için kullanılabilen RSA’yı tanımladı; ayrıntılı makale 1978’de yayımlandı.

Tarihin ilginç bir kıvrımı da var. İngiltere’nin haberleşme istihbarat kurumu GCHQ’da çalışan matematikçi Clifford Cocks, 1973’te esasen aynı yöntemi bulmuştu. Bu çalışma gizli tutuldu ve ancak 1997’de kamuoyuna açıklandı.

1994’te Peter Shor, yeterince büyük ve hataları düzeltilebilen bir kuantum bilgisayarın büyük sayıları verimli biçimde çarpanlarına ayırabileceğini gösteren bir algoritma yayımladı. Böyle bir makine bugün yok ve ne zaman yapılabileceği tartışmalıdır. Yine de risk ciddiye alındığı için kuantum saldırılarına dayanıklı olduğu düşünülen yöntemler geliştirildi. Bu yöntemlerin ilk resmî standartları 2024’te yayımlandı.

Neden önemli?

RSA, okulda öğrenilen konuların şaşırtıcı bir buluşma noktasıdır. Bölme ve bölünebilme, asal çarpanlara ayırma, EBOB ve üslü sayılar, TYT matematik konuları arasında yer alır; hangi konuların sınavda nasıl dağıldığını ne öğrettiğimizi anlattığımız sayfada görebilirsiniz. Aynı konular burada, milyonlarca kişinin her gün kullandığı bir güvenlik düzeninin temelini oluşturur.

RSA’nın bize öğrettiği bir şey daha var: Bir problemin çözülebilir olması ile makul sürede çözülebilir olması farklı şeylerdir. 617 basamaklı bir sayının çarpanları vardır ve ilke olarak bulunabilir. Güvenliği sağlayan, bu işin pratikte ne kadar süreceğidir. Hesaplamanın sınırlarını merak ediyorsanız Turing makinesi yazımız iyi bir devam olur.

Kapanış

Antik Çağ’dan beri merak edilen asal sayılar, bugün cebimizdeki telefonun güvenli bağlantılarında iş görüyor. RSA’nın gücü karmaşık bir sırdan değil, çarpmanın kolay, çarpanlara ayırmanın zor olmasından geliyor. 7 ve 13 ile kurduğumuz küçük oyuncak, 600 basamağı aşan gerçek anahtarlarla aynı mantıkla çalışır. Değişen tek şey, sayıların büyüklüğüdür.