-
Sadrazamv4
ig:sadrazam_v4 tg: Sadrazam.spy
🔐 RSA CTF Rehberi — RSA Zafiyetleri, Saldırı Türleri ve Challenge Analizi
RSA, CTF'lerde en sık karşılaşılan public-key cryptography algoritmalarından biridir.Ancak burada da temel mantık AES'e benzer:
CTF challenge'larında çoğunlukla RSA'nın kendisindeki bir matematiksel kırılma değil, yanlış parametre seçimi veya hatalı kullanım hedeflenir.
En sık karşılaşabileceğimiz alanlar:
Küçük p/q
Weak primes
Shared prime
Small e
Small plaintext
Common modulus
Broadcast attack
Wiener attack
Boneh-Durfee
Franklin-Reiter
Related-message attacks
Textbook RSA
RSA malleability
Padding oracle
Fault attacks
Poor randomness
Şimdi bunları tek tek inceleyelim.
🧩 1. Önce RSA'nın Temel Yapısını Bilmek
RSA'da:p, q → prime numbers
n = p × q
φ(n) = (p-1)(q-1)
e → public exponent
d → private exponent
Public key:
(n, e)
Private key:
(n, d)
Encryption:
c = m^e mod n
Decryption:
m = c^d mod n
CTF açısından en önemli değişkenler:
n
e
c
p
q
d
Challenge bunlardan bazılarını bize veriyorsa, hangisinin normalden farklı olduğuna bakmamız gerekir.
🔎 2. RSA Challenge'ında İlk Bakılacak Şeyler
Bir RSA challenge'ı gördüğümüzde ilk olarak:[ ] n kaç bit?
[ ] e kaç?
[ ] c verilmiş mi?
[ ] p veya q verilmiş mi?
[ ] p/q tahmin edilebilir mi?
[ ] Aynı n başka challenge'larda kullanılmış mı?
[ ] Aynı p/q başka key'lerde var mı?
[ ] Birden fazla ciphertext var mı?
[ ] Aynı e kullanılıyor mu?
[ ] e küçük mü?
[ ] Aynı message farklı public key'lerle şifrelenmiş mi?
[ ] Padding kullanılıyor mu?
[ ] Raw/textbook RSA mı?
[ ] Encryption oracle var mı?
[ ] Decryption oracle var mı?
[ ] Signature oracle var mı?
[ ] d küçük olabilir mi?
[ ] p ve q birbirine fazla yakın mı?
[ ] Randomness güvenli mi?
Bunları cevapladıktan sonra saldırı seçmek çok daha kolaydır.
🧱 3. RSA Modulus n Çok Küçükse
RSA'nın güvenliği büyük ölçüde:n = p × q
sayısını factor edebilmenin zorluğuna dayanır.
Normal RSA'da n yeterince büyük seçilir.
CTF'de ise:
n = 1024 bit
veya daha küçük değerler görebiliriz.
Özellikle:
512-bit
256-bit
128-bit
gibi çok küçük modulus'lar varsa factorization ilk kontrol edilmesi gereken şeylerden biridir.
🎯 CTF yaklaşımı
n↓
factorization
↓
p, q
↓
φ(n)
↓
d
↓
decrypt
Ancak modern, yeterince büyük ve düzgün oluşturulmuş bir RSA modulus'unu sırf public key elimizde diye factor etmeye çalışmak mantıklı değildir.
🔨 4. Fermat Factorization — p ve q Birbirine Yakınsa
RSA:n = p × q
ve p ile q birbirine çok yakınsa Fermat factorization etkili olabilir.
Çünkü:
n = a² - b²
şeklinde yazılabilir:
n = (a-b)(a+b)
Buradan:
p = a-b
q = a+b
elde edilebilir.
🎯 CTF'de ne zaman?
Şüpheli durum:p ≈ q
veya challenge açıklamasında:
close primes
gibi bir ipucu.
Bu durumda Fermat factorization düşünülmelidir.
🧮 5. Weak Prime Generation
RSA'nın p ve q değerleri güvenli şekilde üretilmelidir.CTF'de:
p = predictable
q = predictable
veya zayıf random generator kullanılıyorsa RSA'nın kendisini kırmaya gerek kalmaz.
Örneğin:
timestamp
↓
PRNG
↓
prime
gibi bir yapı varsa randomness incelenmelidir.
🔁 6. Shared Prime Attack
Bu RSA CTF'lerinde çok önemli.İki farklı public key düşünelim:
n1 = p × q1
n2 = p × q2
Burada aynı p yanlışlıkla iki key'de kullanılmış.
O zaman:
gcd(n1, n2) = p
olur.
💥 Böylece iki modulus'tan birini factor etmiş oluruz.
🎯 CTF'de ne yapmalıyız?
Birden fazla RSA public key veriliyorsa:gcd(n1, n2)
gcd(n1, n3)
gcd(n2, n3)
...
kontrol edilmelidir.
Eğer:
gcd(ni, nj) > 1
çıkarsa shared prime ihtimali vardır.
Bu yüzden birden fazla RSA modulus'u gördüğünüzde GCD kontrolü ilk işlemlerden biri olmalı.
📡 7. Small Public Exponent — Küçük e
RSA'da public exponent genellikle:e = 65537
gibi bir değer olur.
CTF'de ise:
e = 3
gibi küçük exponent'ler özellikle dikkat çekicidir.
Ancak:
Ek koşullar gerekir.
Örneğin plaintext küçükse ve:
m^e < n
ise modulo işlemi etkili olmayabilir.
Bu durumda:
c = m^e
olabilir.
Dolayısıyla:
m = integer_nth_root(c, e)
ile plaintext elde edilebilir.
🧮 8. Low Public Exponent Attack
Örneğin:e = 3
ve plaintext yeterince küçükse:
c = m³
olabilir.
Bu durumda doğrudan integer cube root alınabilir.
🎯 CTF'de:
e = 3+
küçük plaintext
+
no padding
görüyorsanız low exponent attack düşünülmelidir.
Burada RSA'yı factor etmiyoruz.
📡 9. Hastad / Broadcast Attack
Bir message:m
aynı küçük public exponent ile birden fazla farklı RSA modulus altında şifrelenmiş olsun:
c1 = m^e mod n1
c2 = m^e mod n2
c3 = m^e mod n3
Eğer:
e = 3
ve gerekli koşullar sağlanıyorsa CRT kullanılarak:
m^e
elde edilebilir.
Daha sonra:
e-th root
alınarak plaintext bulunabilir.
Bu saldırı genellikle:
olarak bilinir.
🎯 CTF işareti
same message+
different n
+
small e
görüyorsanız broadcast attack araştırılmalıdır.
🔗 10. Common Modulus Attack
İki farklı public exponent aynı modulus üzerinde kullanılıyorsa:n aynı
e1 farklı
e2 farklı
ve aynı plaintext şifrelenmişse:
c1 = m^e1 mod n
c2 = m^e2 mod n
common modulus attack gündeme gelebilir.
Özellikle:
gcd(e1, e2) = 1
ise Bézout identity kullanılabilir:
a·e1 + b·e2 = 1
ve buradan m elde edilebilir.
🎯 CTF işareti
same n+
different e
+
same plaintext
🧠 11. Wiener's Attack — Küçük d
RSA'da:d
private exponent'tir.
Normalde d yeterince büyük ve güvenli olmalıdır.
Eğer:
d
çok küçük seçilmişse Wiener attack uygulanabilir.
Temel olarak continued fractions kullanılır.
🎯 CTF işareti
Challenge:n
e
veriyor ama factorization çok zor görünüyorsa ve d'nin özellikle küçük seçildiğine dair bir ipucu varsa:
araştırılmalıdır.
🧠 12. Boneh-Durfee
Wiener attack'in daha ileri bir versiyonu olarak düşünülebilir.RSA private exponent d belirli sınırlar altında yeterince küçükse lattice-based yöntemlerle d recovery mümkün olabilir.
Bu:
Wiener
↓
d küçük
↓
Boneh-Durfee
↓
d daha büyük ama hâlâ tehlikeli
şeklinde düşünülebilir.
🎯 CTF seviyesi
Genellikle ileri seviye RSA challenge'larında karşımıza çıkar.🔗 13. Common Factor / GCD Kontrolü
RSA challenge'ında birden fazla modulus varsa:n1
n2
n3
n4
...
ilk yapılacak kontrollerden biri:
gcd(ni, nj)
olmalıdır.
Eğer:
gcd(ni,nj) = p
gibi non-trivial bir sonuç çıkarsa:
p bulundu
↓
q = n/p
↓
φ(n)
↓
d
şeklinde devam edilebilir.
Bu nedenle:
🧪 14. Textbook RSA
Padding olmadan doğrudan:c = m^e mod n
kullanılan RSA'ya textbook RSA denir.
Bu kullanım gerçek sistemlerde güvenli değildir.
RSA encryption için modern uygulamalarda uygun padding/encoding şemaları kullanılır.
CTF'de textbook RSA özellikle önemlidir çünkü:
- Deterministic'tir
- Malleable'dır
- Küçük plaintext saldırılarına açık olabilir
- Algebraic manipülasyonlara izin verebilir
🧩 15. RSA Malleability
Textbook RSA'nın önemli özelliklerinden biri multiplicative homomorphism'dir.Eğer:
c = m^e mod n
ise:
c' = c × s^e mod n
oluşturulduğunda:
c' = (m × s)^e mod n
olur.
Dolayısıyla decrypt edildiğinde:
m' = m × s mod n
elde edilir.
🎯 CTF'de ne zaman?
textbook RSA+
decryption oracle
görüyorsanız RSA malleability mutlaka düşünülmelidir.
🕵️ 16. RSA Decryption Oracle
Sunucu size:ciphertext gönder
↓
server decrypt eder
↓
sonucu döndürür
gibi bir oracle sağlıyorsa çok dikkatli analiz gerekir.
Özellikle:
textbook RSA
+
decryption oracle
kombinasyonu önemli bir saldırı yüzeyidir.
Challenge'ın davranışına göre ciphertext manipulation kullanılarak hedef plaintext hakkında bilgi elde edilebilir.
📦 17. RSA Padding Oracle
Modern RSA encryption genellikle uygun padding şemalarıyla kullanılmalıdır.Özellikle tarihsel olarak:
RSAES-OAEP
RSAES-PKCS1-v1_5
gibi şemalarla karşılaşılır.
PKCS#1 v1.5 encryption'ın yanlış uygulanması ve decryption oracle bulunması bazı oracle saldırılarına yol açabilir.
En ünlü örneklerden biri:
'tır.
🎯 CTF işareti
RSA+
PKCS#1 v1.5
+
decryption oracle
+
padding hakkında farklı cevaplar
görüyorsanız padding oracle araştırılmalıdır.
🧨 18. Bleichenbacher Attack
Bleichenbacher attack, RSA PKCS#1 v1.5 encryption'ın padding validation davranışından yararlanan klasik bir adaptive chosen-ciphertext attack'tır.Challenge size:
ciphertext
+
oracle
veriyorsa ve oracle ciphertext'in padding açısından geçerli olup olmadığını ayırt edebiliyorsa bu saldırı gündeme gelebilir.
Burada kritik nokta:
Oracle'ın verdiği bilgi kullanılarak plaintext hakkında giderek daha fazla bilgi elde ediliyor.
🔗 19. Franklin-Reiter Related Message Attack
Aynı RSA modulus ve public exponent altında iki plaintext arasında bilinen bir algebraic relationship varsa Franklin-Reiter attack gündeme gelebilir.Örneğin plaintext'ler:
m1
m2 = m1 + k
gibi ilişkiliyse ve textbook RSA kullanılıyorsa polynomial relationships kullanılabilir.
🎯 CTF işareti
same n+
same e
+
related plaintexts
+
no secure padding
görüyorsanız Franklin-Reiter attack araştırılabilir.
🧬 20. Related Message Attacks
Genel olarak RSA'da aynı veya ilişkili mesajların kötü şekilde şifrelenmesi problem oluşturabilir.Özellikle:
same n
same e
related messages
textbook RSA
kombinasyonu önemlidir.
Challenge source code'unda plaintext'lerin birbirleriyle nasıl ilişkili olduğuna bakmak gerekir.
🎲 21. Weak Randomness
RSA key generation güvenli random prime üretimine ihtiyaç duyar.Eğer:
p/q
tahmin edilebilir bir PRNG ile oluşturuluyorsa:
random seed
↓
predictable prime
↓
factor n
şeklinde ilerlenebilir.
Özellikle:
time-based seed
weak PRNG
predictable randomness
gibi ifadeler önemli kırmızı bayraklardır.
🧮 22. p ve q Arasındaki İlişki
Normal RSA'da p ve q rastgele ve uygun şekilde seçilmiş asal sayılardır.CTF'de ise:
p ≈ q
veya:
q = f(p)
gibi özel ilişkiler bulunabilir.
Bu durumda standart factorization yerine ilişkinin kendisini kullanmak mümkün olabilir.
Dolayısıyla source code varsa:
sorusu çok önemlidir.
💥 23. Fault Attack
RSA implementation'ına fiziksel veya hesaplama sırasında fault enjekte edilebilen senaryolarda private key hakkında bilgi çıkarılabilir.Özellikle CRT-based RSA implementation'larında fault saldırıları önemli olabilir.
Bu tarz challenge'lar:
RSA implementation
+
faulty signature/decryption
gibi bir yapı sunabilir.
Bu konu daha çok ileri seviye crypto/hardware challenge'larında karşımıza çıkar.
✍️ 24. RSA Signature Challenge'ları
RSA sadece encryption için kullanılmaz.Digital signature challenge'larında:
signature
public key
message
verification
gibi şeylerle karşılaşabiliriz.
Burada özellikle:
Textbook RSA signature
Weak padding
Signature malleability
Bad verification
gibi problemler araştırılmalıdır.
🧨 25. Textbook RSA Signature
Naive RSA signature kabaca:s = m^d mod n
şeklindedir.
Böyle bir sistem proper signature encoding/padding kullanmıyorsa algebraic özelliklerden yararlanılabilir.
Özellikle challenge:
sign(message)
verify(signature)
oracle'ı veriyorsa signature sisteminin nasıl tasarlandığını incelemek gerekir.
🔢 26. Small e Görünce Otomatik Saldırma
Çok önemli bir nokta:e = 3
gördünüz diye direkt:
demeyin.
Önce:
m^3 < n ?
kontrol edilmelidir.
Ayrıca:
padding var mı?
ve:
plaintext gerçekten küçük mü?
sorularına bakılmalıdır.
Küçük e sadece bir ipucudur, otomatik vulnerability değildir.
🧱 27. RSA Padding
RSA challenge'larında padding özellikle önemlidir.Örneğin encryption tarafında:
RSAES-OAEP
veya:
RSAES-PKCS1-v1_5
gibi yapılar kullanılabilir.
Eğer challenge:
textbook RSA
kullanıyorsa bu ayrıca dikkat edilmesi gereken bir durumdur.
🔍 28. Ciphertext'in Decimal/Hex/Binary Olması
CTF'lerde RSA ciphertext'i farklı formatlarda verilebilir:123456789...
veya:
0x...
veya:
hex(...)
gibi.
Bunları önce integer'a dönüştürmek gerekir.
RSA matematiği genellikle:
integer
üzerinde gerçekleştirilir.
🧮 29. RSA'da Modüler Ters
Birçok challenge'da:d = e⁻¹ mod φ(n)
hesaplamak gerekir.
Yani:
e × d ≡ 1 mod φ(n)
olmalıdır.
Eğer p ve q elimizdeyse:
φ(n) = (p-1)(q-1)
hesaplanabilir.
Sonrasında modular inverse ile d bulunabilir.
🧠 30. CRT — Chinese Remainder Theorem
RSA challenge'larında CRT ile sık sık karşılaşılır.Özellikle:
Broadcast attack
ve bazı RSA implementation'larında CRT önemlidir.
Broadcast attack'ta farklı modulus'lar üzerinden elde edilen congruence'ler CRT ile birleştirilebilir.
Dolayısıyla:
RSA
+
multiple ciphertext
+
different n
gördüğünüzde CRT aklınızda olsun.
🏆 31. RSA Challenge'larında En Önemli Saldırılar
Kısa bir özet:| Karşımıza çıkan | Düşünülecek saldırı |
|---|---|
| Küçük n | Factorization |
| p ≈ q | Fermat |
| Aynı p farklı n'lerde | Shared Prime / GCD |
| e = 3 | Low exponent |
| Aynı mesaj + farklı n + küçük e | Håstad Broadcast |
| Aynı n + farklı e | Common Modulus |
| Küçük d | Wiener |
| Daha geniş küçük-d durumu | Boneh-Durfee |
| Textbook RSA | Malleability / algebraic attacks |
| Decryption oracle | Oracle attacks |
| PKCS#1 v1.5 + oracle | Bleichenbacher |
| Related messages | Franklin-Reiter / related-message attacks |
| Weak PRNG | Key recovery / factorization |
| Birden fazla n | GCD kontrolü |
| RSA signature | Signature implementation analizi |
| Faulty RSA | Fault attacks |
🧭 32. RSA Challenge İçin Pratik Analiz Sırası
Bir challenge'da RSA gördüğümde şu sırayla ilerlemek oldukça mantıklıdır:RSA
↓
n, e, c değerlerini çıkar
↓
n boyutunu kontrol et
↓
e'yi kontrol et
↓
Birden fazla n var mı?
↓
GCD kontrolü
↓
p/q ilişkisi var mı?
↓
Factorization mümkün mü?
↓
Textbook RSA mı?
↓
Padding var mı?
↓
Aynı message tekrar kullanılmış mı?
↓
Aynı n tekrar kullanılmış mı?
↓
e küçük mü?
↓
d küçük olabilir mi?
↓
Oracle var mı?
↓
Related message var mı?
↓
Weak randomness var mı?
↓
Uygun saldırıyı seç
📋 33. RSA CTF Checklist
[ ] n değeri çıkarıldı[ ] e değeri çıkarıldı
[ ] c değeri çıkarıldı
[ ] n bit uzunluğu kontrol edildi
[ ] e küçük mü kontrol edildi
[ ] Birden fazla n var mı kontrol edildi
[ ] GCD saldırısı kontrol edildi
[ ] Shared prime kontrol edildi
[ ] p ≈ q kontrol edildi
[ ] Factorization denenmesi gerektiği değerlendirildi
[ ] Padding kontrol edildi
[ ] Textbook RSA olup olmadığı kontrol edildi
[ ] Aynı message farklı n'lerde kullanılmış mı kontrol edildi
[ ] Broadcast attack değerlendirildi
[ ] Common modulus değerlendirildi
[ ] Related message kontrol edildi
[ ] Küçük d ihtimali değerlendirildi
[ ] Wiener değerlendirildi
[ ] Boneh-Durfee ihtimali değerlendirildi
[ ] Encryption oracle kontrol edildi
[ ] Decryption oracle kontrol edildi
[ ] Signature oracle kontrol edildi
[ ] Padding oracle kontrol edildi
[ ] Weak randomness kontrol edildi
[ ] Source code varsa prime generation incelendi
[ ] Source code varsa padding/verification incelendi
🧠 34. RSA'da En Önemli Mental Model
RSA challenge'larında şunu ezberlemek yerine:"RSA = factorization"
şunu düşünmek çok daha faydalıdır:
RSA
│
┌───────────────┼────────────────┐
│ │ │
n e c
│ │ │
Factorization Small e Plaintext
│ │ │
Shared prime Broadcast Related msg
Fermat Low exponent Malleability
│
└──────────────┐
│
Private
key
│
Small d / RNG
Bunun üzerine bir de:
Padding
Oracle
Signature
Implementation
katmanlarını eklediğinizde RSA CTF'lerinin büyük kısmını sınıflandırabilirsiniz.
🔥 35. Sonuç
RSA challenge'larında en önemli şey hangi parametrenin normalden farklı olduğunu bulmaktır.Örneğin:
e küçük
→ Low exponent araştır
aynı p
→ GCD / Shared Prime
p ≈ q
→ Fermat
aynı message + farklı n
→ Broadcast
aynı n + farklı e
→ Common Modulus
küçük d
→ Wiener / Boneh-Durfee
textbook RSA
→ Malleability / algebraic attacks
PKCS#1 v1.5 + oracle
→ Bleichenbacher
related messages
→ Franklin-Reiter
weak randomness
→ Key generation saldırısı
birden fazla RSA key
→ GCD kontrolü
Ve en önemli prensip:
Önce:
n nasıl oluşturulmuş?
e neden böyle?
p/q nasıl üretilmiş?
aynı key tekrar kullanılmış mı?
padding var mı?
aynı mesaj tekrar kullanılmış mı?
oracle var mı?
sorularını sorun.
Çünkü CTF'lerde çoğu zaman problem:
