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
- Molecular mechanisms of senescence response to transforming growth factor-beta in liver cancer
Karaciğer kanserinde başkalaştırıcı büyüme etmeni-beta?ya bağlı yaşlanma yanıtının moleküler mekanizmaları
ŞERİF ŞENTÜRK
Doktora
İngilizce
2010
Onkolojiİhsan Doğramacı Bilkent ÜniversitesiMoleküler Biyoloji ve Genetik Ana Bilim Dalı
PROF. DR. MEHMET ÖZTÜRK
- Bilgi transfer rotalarının ürün tasarım performansına etkisi
The effect of knowledge transfer routes on product design performance
OKŞAN İMAMOĞLU
Doktora
Türkçe
2017
İşletmeİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. SITKI GÖZLÜ
PROF. DR. MEHMET BÜLENT DURMUŞOĞLU
- Döviz kurunu belirleyen faktörler ve kur riski
Determination of foreign exchange rates and foreign exchange risk
MEHMET COŞKUN ÖZAVNİK
- Müşteri odaklılığın satış performansına etkisi ve bir araştırma
Impact of customer orientation on sales performance and a research
SEZİN CANAY ACAR
- Restorasyon uygulamalarında kullanılan çağdaş teknikler
Contemporary techniques in architectural restoration practice
LORY ZAKAR
Yüksek Lisans
Türkçe
2013
Mimarlıkİstanbul Teknik ÜniversitesiRestorasyon Ana Bilim Dalı
PROF. DR. KEMAL KUTGÜN EYÜPGİLLER