Attacks on the RSA Cryptosystem

Abstract

Το κρυπτοσύστημα δημόσιου κλειδιού RSA αποτελεί εκ των πραγμάτων το πρότυπο για ισχυρή κρυπτογράφηση/αποκρυπτογράφηση και ψηφιακές υπογραφές στην παγκόσμια τεχνολογία. Εμβαθύνοντας στην υποκείμενη αλγεβρική δομή του συστήματος, εξετάζουμε την ιστορία του, τις επιθέσεις που έχουν γίνει έως σήμερα καθώς και διάφορους αλγόριθμους που μέλλονται να είναι η βάση για εκμετάλλευση τυχόν ευπαθειών του συστήματος, συμπεραίνοντας ότι από την δημιουργία του προστατεύεται επιτυχώς από οποιαδήποτε επίθεση έχει γίνει ενάντια του. Διάφορες έρευνες που έχουν γίνει αποκάλυψαν ευπάθειες στο μοντέλο υλοποίησης του κρυπτοσυστήματος, όπως αδύναμα δημόσια/ιδιωτικά κλειδιά, το πρόβλημα παραγοντοποίησης ακεραίων και επιθέσεις που βασίζονται στην επιλογή μη περίπλοκων παραμέτρων. Τέτοιες ευπάθειες δεν θα θέσουν σε κίνδυνο την ασφάλεια του κρυπτοσυστήματος RSA, αλλά θα επιτρέψουν στους ερευνητές να εμβαθύνουν στα υποκείμενα μαθηματικά και στις λανθασμένες επιλογές παραμέτρων. Παρέχουμε μια ανάλυση των προηγούμενων ευρημάτων καθώς και λεπτομερείς περιγραφές συγκεκριμένων επιθέσεων ξεκινώντας από στοιχειώδεις επιθέσεις, καθώς και επιθέσεις που βασίζονται σε προχωρημένη άλγεβρα ή στα επιμέρους εξαρτήματα των συσκευών που υλοποιούν το κρυπτοσύστημα, ενώ δεν παραβλέπουμε να παρουσιάσουμε το πώς η κβαντική υπολογιστική μπορεί να ανατρέψει το RSA στο εγγύς μέλλον. Μια ανασκόπηση των γνωστών επιθέσεων του RSA αποκαλύπτει ότι ένας καλά εφαρμοσμένος αλγόριθμος είναι άθραυστος, αφού έχει αντέξει όλες τις κρυπτοαναλυτικές επιθέσεις έως την παρούσα ημέρα.

The RSA public key cryptosystem is the most widely accepted practice for robust encryption/decryption and digital signatures in global technologies. Since its inception, RSA has successfully guarded against forty years of attacks. Accounting to the underlying algebraic structure, we examine its history, present, and potential issues that need concrete analysis and serve as a countermeasure against possible dangers. Previous research has revealed vulnerabilities in the RSA usage model, including weak public/private keys, the integer factorization problem, and low-limit selection attacks. These flaws will not jeopardize the security of the RSA cryptosystem, but they will allow researchers to dig further into the underlying mathematics and erroneous parameter choices. We provide a summation of previous findings as well as detailed descriptions of specific attacks, from elementary ones to side channel and algebraic-based ones, finishing off with how quantum computing may disrupt RSA soon. A review of known RSA cryptosystem assaults reveals that a well-implemented algorithm is unbreakable, having withstood several cryptanalytic attempts since the inception of RSA.