Partial key exposure attacks on multi-power RSA

Abstract

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.

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.