Partial key exposure attacks on multi-power RSA
Çoklu kuvvet RSA'ya kısmi bilgi saldırıları
- Tez No: 413234
- Danışmanlar: DR. OSMANBEY UZUNKOL, DR. MEHMET SABIR KİRAZ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: İstanbul Şehir Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu tezde temel olarak bir RSA çeşidinin kriptoanalizi üzerine yoğunlaşıyoruz. Çoklu kuvvet RSA olarak adlandırılan bu çeşitte RSA modülü $N=p^rq$, $r\ge 2$, olacak şekilde seçilmektedir. Boneh ve Durfee standart RSA üzerinde Coppersmith'in polinomların küçük köklerini bulma yöntemini kullanarak çok önemli bir sonuç (bir küçük gizli üs saldırısı) göstermişlerdir. Bu çalışmaya göre $N=pq$ için $d<N^{0.292}$ sağlandığında $\log N$ üzerinden polinom zamanda $N$ sayısı çarpanlarına ayrılabilmektedir. 2014'te, Sarkar çoklu kuvvet RSA üzerinde var olan küçük gizli üs saldırılarını $r\le 5$ için geliştirmiştir. Burada $r=2$ için $d<N^{0.395}$ sağlanması durumunda $N$'nin $\log N$ üzerinden polinom zamanda çarpanlarının bulunabileceği gösterilmiştir. Biz, Sarkar'ın çalışmasındaki fikirleri genişleterek çoklu kuvvet RSA'ya yeni bir kısmi bilgi saldırısı geliştireceğiz. Saldırının gerçekleştirilebilmesi için gizli üs $d$'nin en önemsiz bitlerinin bir kısmının bilinmesi gerekmektedir. Bulduğumuz sonuç, Sarkar'ın sonucunun bir genelleştirmesi olup, Sarkar'ın sonucu bizim sonucumuzun bir yan sonucu olarak görülebilmektedir. Saldırımız şu özellikleri taşımaktadır: gerekli olan en önemsiz bit miktarı açık üs $e$ küçüldükçe azalmaktadır ve $d$'nin ($e$'nin) bit boyu $N$ ile aynı olsa dahi bütün üsler $e$ ($d$) için çalışmaktadır. Saldırımızın pratik olarak çalıştığını göstermek için bilgisayar üzerinde bazı cebirsel deneyler gösterilmiştir. Deneylerde LLL algoritması ve Gröbner bazı hesaplaması kullanılmaktadır. Bazı deneylerde teorik sonucumuzun belirttiğinden daha iyi deney sonuçları elde edilmiştir.
Özet (Çeviri)
In this thesis, our main focus is a type of cryptanalysis of a variant of RSA, namely multi-power RSA. In multi-power RSA, the modulus is chosen as $N=p^rq$, where $r\ge 2$. Building on Coppersmith's method of finding small roots of polynomials, Boneh and Durfee show a very crucial result (a small private exponent attack) for standard RSA. According to this study, $N=pq$ can be factored in polynomial time in $\log N$ when $d<N^{0.292}$. In 2014, Sarkar improve the existing small private exponent attacks on multi-power RSA for $r\le 5$. He shows that one can factor $N$ in polynomial time in $\log N$ if $d<N^{0.395}$ for $r=2$. Extending the ideas in Sarkar's work, we develop a new partial key exposure attack on multi-power RSA. Prior knowledge of least significant bits (LSBs) of the private exponent $d$ is required to realize this attack. Our result is a generalization of Sarkar's result, and his result can be seen as a corollary of our result. Our attack has the following properties: the required known part of LSBs becomes smaller in the size of the public exponent $e$ and it works for all exponents $e$ (resp. $d$) when the exponent $d$ (resp. $e$) has full-size bit length. For practical validation of our attack, we demonstrate several computer algebra experiments. In the experiments, we use the LLL algorithm and Gr\"obner basis computation. We achieve to obtain better experimental results than our theoretical result indicates for some cases.
Benzer Tezler
- Diesel motorları yakıt püskürtme sistemlerinin dinamik simülasyonu
Başlık çevirisi yok
İRFAN KARAGÖZ
Yüksek Lisans
Türkçe
1986
Makine MühendisliğiUludağ ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. OĞUZ BORAT
- Kemalpaşa etlik piliç işletmelerinin teknik ve ekonomik yönden incelenmesi
Başlık çevirisi yok
HAYRİ TUNA YÜKSELEN
- Çatışmacı toplum paradigması: Teorik ve meta-teorik düzeylerin ilişkisi
Conflict paradigm of society
ADNAN TÜREGİN
- Hayriye (Kayseri) nefelin-siyenit intrüzyonunun petrografik ve jeokimyasal incelenmesi
Petrographical and geochemical investigation of Hayriye (Kasyseri) nepheline-syenite intrusion
H.MUSTAFA ÖZKAN
Yüksek Lisans
Türkçe
1987
Jeoloji MühendisliğiAnkara ÜniversitesiJeoloji Mühendisliği Ana Bilim Dalı
PROF. DR. YAVUZ ERKAN
- Naproksenin postoperatif dentoolveoler ağrıya olan analjezik etkisinin klinik olarak araştırılması
Başlık çevirisi yok
FATMA BULAT
Doktora
Türkçe
1987
Diş HekimliğiAnkara ÜniversitesiAğız, Diş ve Çene Cerrahisi Ana Bilim Dalı
DOÇ. DR. SELAHATTİN OR