Παραληρήματα au lait

(Άσχετο, αλλά να πώς πλακώνουν τα μαύρα ελικόπτερα. Οι μη έχοντες κολλήματα προσπεράστε.)

Διάβαζα ξανά το “The Code Book”, και σκέφτηκα το ακόλουθο όσον αφορά public keys:

Έστω p, q οι (μεγάλοι) πρώτοι αριθμοί που αποτελούν το μυστικό μέρος του κλειδιού, και N το γινόμενό τους, που είναι ουσιαστικά το δημόσιο μέρος του κλειδιού.

Ενδιάμεσος υπολογισμός:

γ = ⌈√(Ν)⌉ : ο μικρότερος ακέραιος που είναι μεγαλύτερος από την τετραγωνική ρίζα του Ν (aka το γεωμετρικό μέσο όρο των p, q). Εξ ορισμού γ²>N

δ = γ²-N

Αν, λοιπόν, δ είναι τέλειο τετράγωνο, τα p, q είναι κακή επιλογή ζεύγους πρώτων αριθμών, αφού τότε p = γ+√δ, q = γ-√δ (θεωρώντας p > q). Ή τουλάχιστον έτσι λέω.

Παράδειγμα με μικρούς πρώτους (επειδή σε λίγο πρέπει να βγάλουμε βόλτα και τα παιδιά).

p = 71, q = 53, N = 3763, γ = 62, γ² = 3844, δ = 81 (p = 62+√81, q = 62-√81)

Ένα γρήγορο φύλλο που έκανα, δείχνει πως αυτό ισχύει γενικώς για πρώτους που δεν απέχουν πολύ μεταξύ τους (πάντα σε σχέση με τα μεγέθη τους), οπότε φαντάζομαι πως δεν είναι γενικότερο πρόβλημα, αλλά έκανα μια γρήγορη αναζήτηση και δεν κατάφερα να βρω κάτι σχετικό, ούτε θυμάμαι να έχω διαβάσει αυτό ακριβώς σε αναφορές vulnerability περί key creation.

Αν το δ δεν είναι τετράγωνο, τότε τα πράγματα περιπλέκονται καθησυχαστικά για την παγκόσμια ασφάλεια. Εγώ μπαίνω για μπάνιο τώρα, και αν έχω πετύχει κάποιο νεύρο εν αγνοία μου, τα παιδιά θα πάνε βόλτα με ελικόπτερο αντί με αυτοκίνητο. Ουδέν κακόν αμιγές καλού.