A new LSB attack on special-structured RSA primes
Asymmetric key cryptosystem is a vital element in securing our communication in cyberspace. It encrypts our transmitting data and authenticates the originality and integrity of the data. The Rivest–Shamir–Adleman (RSA) cryptosystem is highly regarded as one of the most deployed public-key cryptosyst...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI
2020
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/36978/1/36978.pdf |
| _version_ | 1796973051214036992 |
|---|---|
| author | Abd Ghafar, Amir Hamzah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf |
| author_facet | Abd Ghafar, Amir Hamzah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf |
| author_sort | Abd Ghafar, Amir Hamzah |
| collection | UPM |
| description | Asymmetric key cryptosystem is a vital element in securing our communication in cyberspace. It encrypts our transmitting data and authenticates the originality and integrity of the data. The Rivest–Shamir–Adleman (RSA) cryptosystem is highly regarded as one of the most deployed public-key cryptosystem today. Previous attacks on the cryptosystem focus on the effort to weaken the hardness of integer factorization problem, embedded in the RSA modulus, N=pq . The adversary used several assumptions to enable the attacks. For examples, p and q which satisfy Pollard’s weak primes structures and partial knowledge of least significant bits (LSBs) of p and q can cause N to be factored in polynomial time, thus breaking the security of RSA. In this paper, we heavily utilized both assumptions. First, we assume that p and q satisfy specific structures where p=am+rp and q=bm+rq for a,b are positive integers and m is a positive even number. Second, we assume that the bits of rp and rq are the known LSBs of p and q respectively. In our analysis, we have successfully factored N in polynomial time using both assumptions. We also counted the number of primes that are affected by our attack. Based on the result, it may poses a great danger to the users of RSA if no countermeasure being developed to resist our attack. |
| first_indexed | 2024-03-06T08:36:56Z |
| format | Article |
| id | upm.eprints-36978 |
| institution | Universiti Putra Malaysia |
| language | English |
| last_indexed | 2024-03-06T08:36:56Z |
| publishDate | 2020 |
| publisher | MDPI |
| record_format | dspace |
| spelling | upm.eprints-369782020-06-16T06:38:45Z http://psasir.upm.edu.my/id/eprint/36978/ A new LSB attack on special-structured RSA primes Abd Ghafar, Amir Hamzah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf Asymmetric key cryptosystem is a vital element in securing our communication in cyberspace. It encrypts our transmitting data and authenticates the originality and integrity of the data. The Rivest–Shamir–Adleman (RSA) cryptosystem is highly regarded as one of the most deployed public-key cryptosystem today. Previous attacks on the cryptosystem focus on the effort to weaken the hardness of integer factorization problem, embedded in the RSA modulus, N=pq . The adversary used several assumptions to enable the attacks. For examples, p and q which satisfy Pollard’s weak primes structures and partial knowledge of least significant bits (LSBs) of p and q can cause N to be factored in polynomial time, thus breaking the security of RSA. In this paper, we heavily utilized both assumptions. First, we assume that p and q satisfy specific structures where p=am+rp and q=bm+rq for a,b are positive integers and m is a positive even number. Second, we assume that the bits of rp and rq are the known LSBs of p and q respectively. In our analysis, we have successfully factored N in polynomial time using both assumptions. We also counted the number of primes that are affected by our attack. Based on the result, it may poses a great danger to the users of RSA if no countermeasure being developed to resist our attack. MDPI 2020 Article PeerReviewed text en http://psasir.upm.edu.my/id/eprint/36978/1/36978.pdf Abd Ghafar, Amir Hamzah and Kamel Ariffin, Muhammad Rezal and Asbullah, Muhammad Asyraf (2020) A new LSB attack on special-structured RSA primes. Symmetry, 12 (5). art. no. 838. pp. 1-13. ISSN 2073-8994 https://www.mdpi.com/2073-8994/12/5/838 10.3390/sym12050838 |
| spellingShingle | Abd Ghafar, Amir Hamzah Kamel Ariffin, Muhammad Rezal Asbullah, Muhammad Asyraf A new LSB attack on special-structured RSA primes |
| title | A new LSB attack on special-structured RSA primes |
| title_full | A new LSB attack on special-structured RSA primes |
| title_fullStr | A new LSB attack on special-structured RSA primes |
| title_full_unstemmed | A new LSB attack on special-structured RSA primes |
| title_short | A new LSB attack on special-structured RSA primes |
| title_sort | new lsb attack on special structured rsa primes |
| url | http://psasir.upm.edu.my/id/eprint/36978/1/36978.pdf |
| work_keys_str_mv | AT abdghafaramirhamzah anewlsbattackonspecialstructuredrsaprimes AT kamelariffinmuhammadrezal anewlsbattackonspecialstructuredrsaprimes AT asbullahmuhammadasyraf anewlsbattackonspecialstructuredrsaprimes AT abdghafaramirhamzah newlsbattackonspecialstructuredrsaprimes AT kamelariffinmuhammadrezal newlsbattackonspecialstructuredrsaprimes AT asbullahmuhammadasyraf newlsbattackonspecialstructuredrsaprimes |