ΠΡΩΤΟΙ ΑΡΙ8ΜΟΟΙ

disegono_tou_Riemann · #1

ΓΕΙΑ ΣΑΣ. ΜΠΟΡΕΙΤΕ ΜΗΠΩΣ ΝΑ ΜΟΥ ΕΞΗΓΗΣΕΙ ΚΑΝΕΙΣ ΜΕ ΑΠΛΑ ΛΟΓΙΑ ΤΗΝ ΣΗΜΑΣΙΑ ΤΩΝ ΠΡΩΤΩΝ ΑΡΙΘΜΩΝ ΣΤΙΣ ΤΡΑΠΕΖΙΚΕΣ ΣΥΝΑΛΛΑΓΕΣ?? ΔΗΛΑΔΗ ΠΩΣ ΛΕΙΤΟΥΡΓΕΙ ΤΟ ΟΛΟ ΣΥΣΤΗΜΑ ΚΑΙ ΣΕ ΤΙ 8Α ΧΡΗΣΙΜΕΥΕ ΑΝ ΒΡΟΥΜΕ ΤΟΥΣ ΠΡΩΤΟΥΣ ΑΡΙΘΜΟΥΣ ΠΟΥ ΣΥΝΘΕΤΟΥΝ ΕΝΑΝ ΑΛΛΟ ΑΡΙΘΜΟ.
ΣΑΣ ΕΥΧΑΡΙΣΤΩ

#2

Φαντάζομαι αναφέρεσαι στην κρυπτογραφία και τον αλγόριθμο RSA. Τα μαθηματικά υπάρχουν εδώ.

Θα προσπαθήσω με λίγα λόγια να παραθέσω την ιδέα πίσω από τον αλγόριθμο χωρίς τα μαθηματικά.

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

Α-->Δ
Β-->Ε
Γ-->Ζ

κτλ. (Μεταθέτει δηλαδή όλα τα γράμματα τρεις θέσεις δεξιά)

Έτσι αντι να λέει στους στρατηγούς του "επιθεση τα μεσανυκτα" θα έλεγε "θτμλθφκ χε οθφδπψνχδ".

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

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

Α --> Ε
Β --> Α
Γ --> Ρ

κτλ

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

Θέλουμε λοιπόν ένα σύστημα που να είναι πιο ασφαλές. Ιδανικά θέλουμε ένα σύστημα που όποιοσδήποτε να μπορεί να κωδικοποιεί αλλά μόνο εμείς να μπορούμε να αποκωδικοποιούμε. Αυτό φαίνεται αρχικά αδύνατο επειδή "όπως κωδικοποιήσαμε, κάνουμε τις αντίστροφες πράξεις και αποκωδικοποιούμε". Η βασική ιδέα του αλγορίθμου RSA είναι ότι δεν μπορούμε να κάνουμε τις αντίστροφες πράξεις. Βασίζεται στο γεγονός ότι εύκολα μπορούμε να πολλαπλασιάσουμε δυο αριθμούς p,q αλλά δύσκολα μπορούμε αν μας δώσουν μόνο το γινόμενο pq να βρούμε τους p,q. (Αν οι p,q έχουν ο καθένας 100 ψηφία, ο pq έχει περίπου 200 ψηφία και αν προσπαθούμε να βρούμε τους πρώτους παράγοντές του δοκιμάζοντας κατα σειρά τα 2,3,5,7 κτλ θα θέλαμε κάποια δισεκατομμύρια χρόνια για να τελειώσουμε (και λίγα βάζω). [Αυτό δυστυχώς δεν σημαίνει πως είναι απαραίτητα δύσκολο να βρούμε τους pq. Αυτή την στιγμή όμως κανείς δεν γνωρίζει πως να τους βρει γρήγορα.]

Ο αλγόριθμος βασίζεται λοιπόν στο εξής:
1) Όποιος ξέρει το γινόμενο pq μπορεί εύκολα να κρυπτογραφήσει.
2) Όποιος ξέρει τους p,q μπορεί εύκολα να αποκρυπτογραφήσει.
3) Όποιος ξέρει το γινόμενο pq (πιστεύουμε αλλά δεν έχουμε απόδειξη πως) δεν μπορεί να αποκρυπτογραφήσει.

-------------------------------------------------------

Ελπίζω να σε κάλυψα. Υπάρχουν συστήματα κρυπτογράφησης που θεωρούνται πιο ασφαλή από αυτόν τον αλγόριθμο. Η βασική ιδέα όμως παραμένει η ίδια. Χρησιμοποιούν κάποια διαδικασία που δύσκολα αντιστρέφεται. Δεν ξέρω τι ακριβώς σύστημα χρησιμοποιούν οι τράπεζες ή άλλοι οργανισμοί για την ασφάλεια των μηνυμάτων τους.

disegono_tou_Riemann · #3

Kαθε μηνυμα δεν μετατρεπεται στο δυαδικο ή οποιοδηποτε αλλο συστημα??? Μετα τι γινεται δηλαδη??Πολλαπλασιαζονται αυτοι οι αρι8μοι ή γινεται κατι τετοιο??Και γιατι πρεπει να αναλη8ει σε πρωτους αρι8μους ωστε να αποκωδικοποιηθει,ποια ειναι η σημασια τους??/

#4

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

Θα εξηγήσω την διαδικασία της κρυπτογράφησης/αποκρυπτογράφησης με ένα παράδειγμα:

1) Επιλέγουμε μεγάλους πρώτους αριθμούς p,q

με $p\neq q$ και θέτουμε n=pq

Για ευκολία στις πράξεις θα πάρουμε p=5

και

. (Η μέθοδος εξακολουθεί να δουλεύει αλλά δεν είναι ασφαλής.)

2) Βρίσκουμε ένα αριθμο

ο οποίος να είναι σχετικά πρώτος με τον αριθμό (p-1)(q-1)

Έχουμε

. Μπορούμε να πάρουμε π.χ. d=11

.

3) Βρίσκουμε ένα αριθμό

που να ικανοποιεί $1 \leqslant e \leqslant (p-1)(q-1)$ και $ed \equiv 1 \bmod (p-1)(q-1)$ .

Στην περίπτωσή μας έχουμε $11^2 = 5 \cdot 24 + 1$ άρα μπορούμε να πάρουμε e=11

. (Ο αριθμός

είναι μοναδικός και μπορεί να βρεθεί γρήγορα χρησιμοποιώντας τον Ευκλείδιο αλγόριθμο.)

4) Δημοσιεύουμε το κλειδί (e,n)

. (Και κρατάμε τα p,q,d

μυστικά.)

5) Κωδικοποίηση: Ο αριθμός

κωδικοποιήται ως

όπου

ο μοναδικός αριθμός που ικανοποιεί $1 \leqslant C \leqslant n$ και $C \equiv M^e \bmod n$ .

Για παράδειγμα, για να κωδικοποιήσουμε τον αριθμό 18 (ο οποίος μπορεί π.χ. να συμβολίζει το Σ που είναι το 18ο γράμμα του αλφαβήτου) κάνουμε τις εξής πράξεις
$18^2 = 324 \equiv 9 \bmod 35$
$18^4 \equiv 9^2 \equiv 11 \bmod 35$
$18^8 \equiv 121 \equiv 16 \bmod 35$
Άρα $18^{11} = 18 \cdot 18^2 \cdot 18^8 \equiv 18 \cdot 16 \cdot 9 \equiv 288 \cdot 9 \equiv 8 \cdot 9 \equiv 2 \bmod 35.$

Θα κωδικοποιήσουμε λοιπόν τον αριθμό 18 με τον αριθμό 2.

6) Αποκωδικοποίηση: Ο αριθμός

αποκωδικοποιήται ως ο αριθμός

, όπου $1 \leqslant D \leqslant n$ και $D \equiv C^d \bmod n$

Για παράδειγμα, για να αποκωδικοποιήσουμε τον αριθμό 2 κάνουμε τις πράξεις
$2^{11} \equiv 2 \cdot 2^2 \cdot 2^8 \equiv 8 \cdot 256 \equiv 8 \cdot 11 \equiv 88 \equiv 18 \bmod 35$ .

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

είναι γνωστά σε όλους. Για την αποκωδικοποίηση χρειάζεται γνώση του

. Για να βρει κάποιος το

χρειάζεται γνώση του (p-1)(q-1)

. Για να βρει κάποιος το (p-1)(q-1)

χρειάζεται γνώση των p,q

. Για να βρεθούν τα p,q

χρειάζεται να μπορεί να αναλυθεί ο

σε γινόμενο πρώτων παραγόντων. Αυτό όμως δεν μπορεί να γίνει γρήγορα αν οι p,q

είναι τεράστιοι. (Στην περίπτωσή μας, αν σου δώσω n=35

βλέπεις αμέσως ότι τα p,q

ισούνται με 5 και 7.)

Όπου έγραφα "χρειάζεται" στην πιο πάνω παράγραφο, θα ήταν πιο όρθό να έγραφα "πιστεύουμε πως χρειάζεται". Μέχρι στιγμής όμως κανέις δεν γνωρίζει γρήγορο αλγόριθμο αποκρυπτογράφησης που να χρησιμοποιεί μόνο γνώση των e,n

.

disegono_tou_Riemann · #5

Εδω παιζει συμαντικο ρολο το 8εωρημα του Riemann??Μπορειτε καταρχας να μου πειτε με απλα λογια τι λεει??Εχω διαβασει αρκετα γι αυτο αλλα δεν εχω καταλαβει ακριβως την σημασια του.

ΠΡΩΤΟΙ ΑΡΙ8ΜΟΟΙ

ΠΡΩΤΟΙ ΑΡΙ8ΜΟΟΙ

Re: ΠΡΩΤΟΙ ΑΡΙ8ΜΟΟΙ

Re: ΠΡΩΤΟΙ ΑΡΙ8ΜΟΟΙ

Re: ΠΡΩΤΟΙ ΑΡΙ8ΜΟΟΙ

Re: ΠΡΩΤΟΙ ΑΡΙ8ΜΟΟΙ

Μέλη σε σύνδεση