Κρυπτογραφία και πρώτοι αριθμοί

[Spiros252]

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

Όλη η σύγχρονη κρυπτογραφία στηρίζεται στην υπόθεση ότι κανείς δεν μπορεί να υπολογίσει με εύκολο τρόπο (όχι δοκιμάζοντας όλους τους συνδυασμούς) από ποιους δυο πρώτους αριθμούς έχει προκύψει ένα γινόμενο. Δηλαδή αν έχεις τους πρώτους Α και Β και τους πολλαπλασιάσεις και πάρεις Γ, τότε αν δώσεις σε κάποιον μόνο το Γ είναι πρακτικά αδύνατο να βρει από ποιους Α και Β προήλθε. Μιλάμε φυσικά για πολλά ψηφία. Δεν λέμε το Α και το Β να είναι 3 και 5.

Ξέρεις τί τάξης μεγέθους πρώτοι χρησιμοποιούνται στη σύγχρονη κρυπτογραφία , πώς παράγονται, αν παραμένουν κρυφοί από το κοινό και ποιοι τους διαχειρίζονται?

[break]

Ξέρεις τί τάξης μεγέθους πρώτοι χρησιμοποιούνται στη σύγχρονη κρυπτογραφία , πώς παράγονται, αν παραμένουν κρυφοί από το κοινό και ποιοι τους διαχειρίζονται?

Ναι. Αυτό είναι το κρυπτογραφία τόσων bit που ακούς να λένε αναφορικά με το πόσο δυνατή είναι. Ας πούμε 2048 bit που τώρα θεωρείται καλή σημαίνει αριθμούς με 2048 ψηφία στο δυαδικό. Δηλαδή στο δεκαδικό γύρω στα 600 ψηφία. Όπως καταλαβαίνεις αν σου δώσουν ένα αριθμό 600 ψηφίων και σου πουν ότι είναι γινόμενο δύο πρώτων το να κάτσεις να κάνεις όλες τις πιθανές διαιρέσεις να βρεις ποιοι είναι αυτοί είναι πρακτικά αδύνατον.

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

Με απλά λόγια αυτό που κάνει είναι ότι κρατάς κάποιους αριθμούς, δίνεις κάποιους άλλους και υπάρχουν κάποιος πράξεις που μόνο εσύ μπορείς να κάνεις και κάποιες που όλοι μπορούν να κάνουν.

[Spiros252]

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

Αν όμως έχεις λίστες με πολλούς πρώτους αυτής της τάξης δεν χρειάζεται να κάνεις υπολογισμούς.

Αν κάποιος αριθμός χρησιμοποιηθεί "καίγεται"?

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

[nick]

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

Αν όμως έχεις λίστες με πολλούς πρώτους αυτής της τάξης δεν χρειάζεται να κάνεις υπολογισμούς.

Αν κάποιος αριθμός χρησιμοποιηθεί "καίγεται"?

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

Γενικα δεν ειναι τοσο αραιοι,
Ας πουμε θες να βρεις εναν 60-ψηφιο πρωτο.
Ξεκινα απο 10^60 +1 και δοκίμαζε των καθε επόμενο, το πολυ σε περίπου 1000 αριθμους μάλλον θα πετύχεις εναν.
Ο ελεγχος για τον αν ειναι πρωτος ειναι πολυ γρήγορος.
https://en.wikipedia.org/wiki/Fermat_primality_test

Επισης ας πουμε πως απο 10^60 μεχρι 2*10^60 υπαρχουν 10^40 πρωτοι, ποσο γρηγορα θα τεσταρεις 10^40 πρωτους !!!

[break]

Αν όμως έχεις λίστες με πολλούς πρώτους αυτής της τάξης δεν χρειάζεται να κάνεις υπολογισμούς.[

Αν κάποιος αριθμός χρησιμοποιηθεί "καίγεται"?

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

Οι πρώτοι αριθμοί με 600 ψηφία είναι αμέτρητοι. Άπειροι. Και οι αριθμοί διαλέγονται στην τύχη. Δεν είναι σαν passwords. Κάθε φορά που χρειάζεται να γίνει κρυπτογράφηση οι υπολογιστές κάθονται και βρίσκουν στην τύχη ένα τέτοιο τεράστιο αριθμό. Η πιθανότητα να χρησιμοποιηθεί ο ίδιος αριθμός είναι μηδέν. Μιλάμε το ξαναλέω για αριθμούς με 600 ψηφία. Δεν γίνεται να πέσεις ποτέ στον ίδιο.

Μεγάλη σημασία έχει φυσικά η τυχαιότητα. Αναπόσπαστο κομμάτι της κρυπτογραφίας είναι να έχεις καλή τυχαιότητα. Συστήματα έχουν χακευθεί επειδή ναι μεν οι αλγόριθμοι ήσαν μπετόν αρμέ αλλά η γεννήτρια που παρήγαγε τους τυχαίους δεν ήταν τελικά και τόσο τυχαία όσο νόμιζαν αυτοί που την χρησιμοποιούσαν και κάποιος μπόρεσε να προβλέψει τι αριθμούς παρήγαγε.

Σε συστήματα που η τυχαιότητα είναι πρωτίστης σημασία τους τυχαίους αριθμούς τους παίρνουν με φυσικές γεννήτριες. Πχ από το θόρυβο διαστημικής ακτινοβολίας. Ή από ραδιενεργή μετάπτωση. Έτσι ώστε το να προβλέψεις τον αριθμό που θα βγάλει να είναι 100% αδύνατο.

[Αρχέλαος]

Αν όμως έχεις λίστες με πολλούς πρώτους αυτής της τάξης δεν χρειάζεται να κάνεις υπολογισμούς.[

Αν κάποιος αριθμός χρησιμοποιηθεί "καίγεται"?

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

Οι πρώτοι αριθμοί με 600 ψηφία είναι αμέτρητοι. Άπειροι. Και οι αριθμοί διαλέγονται στην τύχη. Δεν είναι σαν passwords. Κάθε φορά που χρειάζεται να γίνει κρυπτογράφηση οι υπολογιστές κάθονται και βρίσκουν στην τύχη ένα τέτοιο τεράστιο αριθμό. Η πιθανότητα να χρησιμοποιηθεί ο ίδιος αριθμός είναι μηδέν. Μιλάμε το ξαναλέω για αριθμούς με 600 ψηφία. Δεν γίνεται να πέσεις ποτέ στον ίδιο.

Μεγάλη σημασία έχει φυσικά η τυχαιότητα. Αναπόσπαστο κομμάτι της κρυπτογραφίας είναι να έχεις καλή τυχαιότητα. Συστήματα έχουν χακευθεί επειδή ναι μεν οι αλγόριθμοι ήσαν μπετόν αρμέ αλλά η γεννήτρια που παρήγαγε τους τυχαίους δεν ήταν τελικά και τόσο τυχαία όσο νόμιζαν αυτοί που την χρησιμοποιούσαν και κάποιος μπόρεσε να προβλέψει τι αριθμούς παρήγαγε.

Σε συστήματα που η τυχαιότητα είναι πρωτίστης σημασία τους τυχαίους αριθμούς τους παίρνουν με φυσικές γεννήτριες. Πχ από το θόρυβο διαστημικής ακτινοβολίας. Ή από ραδιενεργή μετάπτωση. Έτσι ώστε το να προβλέψεις τον αριθμό που θα βγάλει να είναι 100% αδύνατο.

[wooded glade]

Γιατί γίνεται με τυχαίους αριθμούς η κρυπτογράφηση ;
Θέλω εγώ ας πούμε να φτιάξω τον χάρτη των λουλουδιών, με τα θωρηκτά της τσέπης.
Αν γράψω f(x) = sqr(arcsin(1+0.557*x)+exp(-2.24*x^789))-pi*log(cos(0.777*x), πως θα μου το σπάσουν ;

[nick]

Ριξε μια ματια στο Euler's Totient Theorem και την εφαρμογη στο RSA.
Τα εξηγει πολυ ομορφα στο λινκ.
https://www.muppetlabs.com/~breadbox/txt/rsa.html


Σχετικα με μια οποιαδήποτε συνάρτηση κρυπτογραφησης, Αν ειναι invertible τοτε δεν ειναι πολύ χρήσιμη π.χ.

F(X) = 7 * X + 43
G(X) = (X - 43) / 7.
G(64) is equal to 3, and in general, G(F(X)) is equal to X. Therefore, G is F's inverse.

[wooded glade]

Ριξε μια ματια στο Euler's Totient Theorem και την εφαρμογη στο RSA.
Τα εξηγει πολυ ομορφα στο λινκ.
https://www.muppetlabs.com/~breadbox/txt/rsa.html


Σχετικα με μια οποιαδήποτε συνάρτηση κρυπτογραφησης, Αν ειναι invertible τοτε δεν ειναι πολύ χρήσιμη π.χ.

F(X) = 7 * X + 43
G(X) = (X - 43) / 7.
G(64) is equal to 3, and in general, G(F(X)) is equal to X. Therefore, G is F's inverse.

Ναι, είχα διαβάσει και στο Scientific American, αλλά πως όμως θα αντιστρέψουν τη δικιά μου φόρμουλα.
Με τι προσόντα ;

[break]

Γιατί γίνεται με τυχαίους αριθμούς η κρυπτογράφηση ;

Γιατί το ζητούμενο είναι η κρυπτογράφηση χωρίς πρότερη συνεννόηση. Αν υπάρχει πρότερη συνεννόηση, δηλαδή αν η μία και η άλλη πλευρά έχουν προαποφασίσει πως θα ανταλλάξουν την πληροφορία, τότε υπάρχουν άπειροι τρόποι να σκεφτείς πως να το κάνεις με μυστικότητα.

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

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

[nick]

Ριξε μια ματια στο Euler's Totient Theorem και την εφαρμογη στο RSA.
Τα εξηγει πολυ ομορφα στο λινκ.
https://www.muppetlabs.com/~breadbox/txt/rsa.html


Σχετικα με μια οποιαδήποτε συνάρτηση κρυπτογραφησης, Αν ειναι invertible τοτε δεν ειναι πολύ χρήσιμη π.χ.

F(X) = 7 * X + 43
G(X) = (X - 43) / 7.
G(64) is equal to 3, and in general, G(F(X)) is equal to X. Therefore, G is F's inverse.

Ναι, είχα διαβάσει και στο Scientific American, αλλά πως όμως θα αντιστρέψουν τη δικιά μου φόρμουλα.
Με τι προσόντα ;

Αυτο που εγραψες f(x) = sqr(arcsin(1+0.557*x)+exp(-2.24*x^789))-pi*log(cos(0.777*x), (αν και πολύπλοκο) μπορει να λυθει δλδ να βρεις τη συναρτιση g οπου g(f(x))=x για καθε x.

[- Casper -]

Ο break τα εξηγεί άψογα

[break]

Και το να πετάς φόρμουλες στην τύχη ανακατεύοντας πράγματα δεν οδηγεί σε καλή κρυπτογραφία. Πρέπει να υπάρχει λογική πίσω από όλα αυτά για να εξασφαλίσεις ότι δεν αντιστρέφονται.

Θα σου πω μία ενδιαφέρουσα ιστορία. Οταν δημιουργήθηκε ο DES (αλγόριθμός κρυπτογράφησης) την δεκαετία του 70 η NSA πρότεινε να αλλαχτεί ο τρόπος κάποιου "ανακατέματος" στην φόρμουλα. Η αλλαγή δεν ήταν προφανές τι σκοπό εξυπηρετούσε και δημιούργησε αναπόφευκτα την υποψία ότι η NSA κάποιο παραθυράκι είχε βάλει για να μπορεί να τον αντιστρέφει. Όταν 20 χρόνια αργότερα ανακαλύφθηκε μία μέθοδος επίθεσης σε τέτοιους αλγόριθμους αποδείχθηκε ότι η εκδοχή της NSA ήταν ανθεχτική σε αυτή την επίθεση αλλά όχι η αυθεντική που είχε αλλάξει.

Συμπέρασμα ; Η NSA ήξερε αυτού του είδους την επίθεση 20 χρόνια πριν ανακαλυφθεί και δημοσιευθεί στην ακαδημαϊκή κοινότητα !!!

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

[Αρχέλαος]

Γιατί γίνεται με τυχαίους αριθμούς η κρυπτογράφηση ;

Γιατί το ζητούμενο είναι η κρυπτογράφηση χωρίς πρότερη συνεννόηση. Αν υπάρχει πρότερη συνεννόηση, δηλαδή αν η μία και η άλλη πλευρά έχουν προαποφασίσει πως θα ανταλλάξουν την πληροφορία, τότε υπάρχουν άπειροι τρόποι να σκεφτείς πως να το κάνεις με μυστικότητα.

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

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

[nick]

Στο RSA οπου βρίσκουν εφαρμογή οι πρωτοι αριθμοι υπαρχουν δυο κλειδια: private-public.
Εδω τα κλειδια δεν ειναι τυχαια, ειναι προαποφασισμένα.
Π.χ. η amazon φτιαχνει ενα ζευγάρι κλειδια (private-public) και δίνει σε ολους τους πελατες το (ιδιο) public.
Ο πελάτης έχοντας το public μπορεί να κρυπτογραφησει το μήνυμα του. Κάνεις από τους πελάτες που έχουν το public δεν μπορεί να το αποκρυπτογραφησει (ουτε ο ιδιος που το κρυπτογραφησε).
Μονο οποίος εχει το private (η amazon) μπορει να το αποκρυπτογραφησει.
Το πλεονέκτημα εδω ειναι οτι δεν υπαρχει ο φοβος να σου κλέψουν το κλειδι.
Ειναι πολυ δυσκολο να βρεις το private key ξέροντας το public.