Κρυπτογραφία

[digimyth]

Χαιρετώ,

 

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

Θέλω να μάθω πως γίνεται η αποκρυπτογράφηση του "Ομοπαραλληλικού συστήματος" ή αλλιώς "Γραμμικού αλγορίθμου" ή "Affine cipher".

Έχω σημειώσεις αλλά δε μπορώ να καταλάβω την αποκρυπτογράφηση γιατί δεν λέει πουθενά αναλυτικά. Θα επισυνάψω και τις σημειώσεις.

Η κρυπτογράφηση πάντως είναι απλή. Θα παραθέσω ένα παράδειγμα και την άσκησή μου που δε μπορώ να αποκρυπτογραφήσω (*παράδειγμα 2).

 

Παράδειγμα 1

Να κρυπτογραφηθεί και να αποκρυπτογραφηθεί το κείμενο “ΘΑ

ΕΡΘΕΙΣ;” με το oμοπαραλληλικό κρυπτοσύστημα χρησιμοποιώντας το

κλειδί e = (7,4)

 

Απάντηση

Αντιστοιχία γραμμάτων με θέση στο αλφάβητο:

“ΘΑ ΕΡΘΕΙΣ;” ↔ {7, 0, 24, 4, 16, 7, 4, 8, 17, 25}.

Χρησιμοποιώντας τη συνάρτηση κρυπτογράφησης 7 x + 4

παίρνουμε:

{1, 4, 16, 6, 12, 1, 6, 8, 19, 23} ↔ ”ΒΕΡΗΝΒΕΙΥΩ”

Για να υπολογίσουμε τη συνάρτηση αποκρυπτογράφησης πρέπει να

υπολογίσουμε το 7 στην −1 . Έχουμε λοιπόν από τον αλγόριθμο του Ευκλείδη:

26 = 3⋅ 7 + 5

7 = 5 + 2

5 = 2⋅2 + 1, άρα:

 

1 = 5 – 2⋅2

= 5 – 2 (7-5) = -2⋅7 + 3⋅5=

-2 * 7 + 3 * ( 26 - 3 * 7 )=

3⋅26-11⋅7,

 

συνεπώς:

7 στην −1 = −11≡15mod 26, δηλαδή 7 στην −1 =15, οπότε 15χ - 8

Παράδειγμα 2

Έχουμε το κείμενο " ΧΤΥΠΑ_ΤΩΡΑ" και e = {9, 3}, τότε χρησιμοποιώντας τη συνάρτηση κρυπτογράφησης: 9 x + 3 modN.

Αντιστοιχία γραμμάτων με θέση στο αλφάβητο:

«ΧΤΥΠΑ_ΤΩΡΑ» ↔ {21, 18, 19, 15, 0, 24, 18, 23, 16, 0}

 

Κρυπτογράφηση του Χ:

ƒe(21) = 9 x 21 = 189 + 3 mod 25 = 17

 

Κρυπτογράφηση του Τ:

ƒe(18) = 9 x 18 = 162 + 3 mod 25 = 15, κ.ο.κ.

 

Άρα: {17, 15, 24, 13, 3, 19, 15, 10, 22, 3} ↔ «ΣΠ_ΞΔΥΠΛΨΔ»

 

Η αποκρυπτογράφηση πως γίνεται;

 

 

Ευχαριστώ πολύ

crypto.zip

[bnvdarklord]

Μα την έχεις βρεί την συνάρτηση αποκρυπτογράφησης:

 

Για να υπολογίσουμε τη συνάρτηση αποκρυπτογράφησης πρέπει να

υπολογίσουμε το 7 στην −1 . Έχουμε λοιπόν από τον αλγόριθμο του Ευκλείδη:

26 = 3⋅ 7 + 5

7 = 5 + 2

5 = 2⋅2 + 1, άρα:

 

1 = 5 – 2⋅2

= 5 – 2 (7-5)[/i] = -2⋅7 + 3⋅5=

-2 * 7 + 3 * ( 26 - 3 * 7 )=

3⋅26-11⋅7,

 

συνεπώς:

7 στην −1 = −11≡15mod 26, δηλαδή 7 στην −1 =15, οπότε 15χ - 8

 

Αν κανεις στο κωδικοποιημένο (15χ - 8) mod 26 βρήσκεις το αρχικό μήνυμα...

[digimyth]

Δεν έχω καταλάβει όμως όλους αυτούς τους αριθμούς από που τους βγάζουμε. Ξέρω ότι το 15χ-8 είναι η συνάρτηση αποκωδικοποίησης αλλά το θέμα είναι πως βγαίνει;

[bnvdarklord]

Δεν έχω καταλάβει όμως όλους αυτούς τους αριθμούς από που τους βγάζουμε. Ξέρω ότι το 15χ-8 είναι η συνάρτηση αποκωδικοποίησης αλλά το θέμα είναι πως βγαίνει;

 

Δεν καταλαβες πως βρησκεις το 15χ-8 ή πως το χρησιμοποιείς για την αποκωδικοποίηση?

[digimyth]

Δεν καταλαβες πως βρησκεις το 15χ-8 ή πως το χρησιμοποιείς για την αποκωδικοποίηση?

Δεν ξέρω πως βγαίνει η συνάρτηση αποκρυπτογράφησης όχι πως χρησιμοποιείται, δηλαδή όλους τους αριθμούς και πράξεις που πρέπει να κάνεις πριν καταλήξεις στο 15χ-8. Άλλωστε στο 2ο παράδειγμα ρωτάω πως αποκωδικοποιείται;

[Technology fan]

Θα μπορούσα να σου περιγράψω πως αλλα καλύτερα να το δεις απο μόνος σου, δες εδώ σελ 2,3 (του pdf), απο τον καθηγητή που μας τα 'κανε...

[MitsakosGR]

Ο αλγόριθμος κρυπτογράφησης είναι "(ax+ mod m", όπου a,b τα κλειδιά της κρυπτογράφησης και m το μέγεθος του αλφαβήτου που χρησιμοποιείς (πχ Αγγλικά κεφαλαία = 26 και 24 για ελληνικά κεφαλαία)

Ο αλγόριθμος που χρησιμοποιείς εδώ έχει κλειδιά (7,4) και μέγεθος αλφαβήτου 26. Έτσι ο αλγόριθμος κρυπτογράφησης είναι (7 x + 4)mod26.

 

Ο αλγόριθμος αποκρυπτογράφησης είναι "(a στην -1)(x- mod m".

Για να υπολογίσεις το (a στην -1) εφαρμόζεις τον αλγόριθμο του Ευκλείδη για τον μέγιστο κοινό διαιρέτη μεταξύ m και a. Για το παράδειγμά σου:

26 mod 7 = 5 ==> 26 = 7*3 + 5 (1)

7 mod 5 = 2 ==> 7 = 5*1 + 2 (2)

5 mod 2 = 1 ==> 5 = 2*2 + 1 (3)

2 mod 1 = 0 (ολοκλήρωση αλγόριθμου με Μ.Κ.Δ. το 2)

 

Λύνεις τις (1), (2), (3) ως προς το υπόλοιπο:

5 = 26 - 7*3 (4)

2 = 7 - 5*1 (5)

1 = 5 - 2*2 (6)

 

Αντικαθιστάς στην (6) τις (5), (4) ώστε να έχεις ένα αποτέλεσμα τύπου (mγ + aδ).

Έτσι έχουμε:

1 = 5 - 2 * 2 = (με αντικατάσταση της 5)

. = 5 - 2(7-5) = (με αντικατάσταση της 4)

. = 26 - 7*3 - 2( 7 - 26 + 7*3)=

. = 26 - 7*3 - 2*7 + 26*2 - 7*6 =

. = 26(1+2) - 7(3+2+6) =

. = 26*3 - 7*11

 

Τέλος υπολογίζουμε το (a στην -1) = m - δ = 26 - 11 = 15

 

Έτσι ο τελικός αλγόριθμος αποκωδικοποίησης είναι:

(a στην -1)(x- mod m = 15(χ - 4) mod 26

.= (15x - 15*4) mod 26 = (15x mod 26) - 8 (αυτό δεν ξέρω αν ισχύει γιατί στο παράδειγμα 2 βγαίνει εντελώς λάθος αν το κάνεις.

 

 

Για το παράδειγμα 2:

Έχεις m = 25, a = 9, b = 3

Ο αλγόριθμος αποκρυπτογράφησης είναι:

(9 στην -1) (x - 3) mod 25

 

Υπολογίζουμε το (9 στην -1) = 14

Άρα ο αλγόριθμος αποκρυπτογράφησης είναι: 14(χ - 3) mod 25

[digimyth]

Θα μπορούσα να σου περιγράψω πως αλλα καλύτερα να το δεις απο μόνος σου, δες εδώ σελ 2,3 (του pdf), απο τον καθηγητή που μας τα 'κανε...

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

[Technology fan]

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

 

Λοιπόν, πες οτι έχεις έναν αριθμό Χ αυτόν κρυπτογραφώντας τον, τον αντιστοιχείς με κάποιον τρόπο σε έναν άλλον αριθμό Υ, για να πας τώρα απο τον Υ στον Χ πρέπει να πάς με τον αντίστροφο τρόπο. (πχ απλοικό αν είχες 5 και τον πολλαπλασιάζεις με 4 για να βγάλεις το 20 , για να πας απο το 20 στο 5 πρέπει να διαιρέσεις με 4, δηλαδή πολλαπλασιασμός/διαίρεση αντίστροφες πράξεις) το πρόβλημα τώρα είναι ότι η αντιστροφή σε ένα σύστημα αρίθμησης 26 ή πεπερασμένων αριθμών δεν ορίζεται απλά ως πολλαπλασιασμός/διαίρεση αλλα ορίζεται διαφορετικά και βρίσκεται μέσω του αλγόριθμου του ευκλείδη! ελπίζω να μη σε μπέρδεψα παραπάνω! και οχι ούτε εγώ είμαι μαθηματικός.

 

Επίσης θα σου συνιστούσα να δείς λίγο αυτό κυρίως τις ασκήσεις