Θέμα: Η μέθοδος κρυπτογράφησης του Καίσαρα

[alkisg]

Disclaimer: η συνημμένη άσκηση είναι εκτός ύλης.Με αφορμή αυτήν τη συζήτηση, η παρούσα άσκηση προσπαθεί να δώσει μια οπτική του ερωτήματος «πώς θα ήταν αν η ΓΛΩΣΣΑ υποστήριζε χειρισμό αλφαριθμητικών».

Εκφώνηση:
Ο Ιούλιος Καίσαρας με τους στρατηγούς του χρησιμοποιούσε την παρακάτω μέθοδο κρυπτογράφησης για αποστολή μηνυμάτων:
Το μήνυμα «ΚΕΙΜΕΝΟ» γραφόταν ως «ΛΖΚΝΖΞΠ», δηλαδή:
το Κ αντικαθιστούνταν από το αμέσως επόμενο γράμμα της αλφαβήτου και γινόταν Λ,
το Ε αντικαθιστούνταν από το αμέσως επόμενο γράμμα της αλφαβήτου και γινόταν Ζ,
το Ι αντικαθιστούνταν από το αμέσως επόμενο γράμμα της αλφαβήτου και γινόταν Κ,
το Μ αντικαθιστούνταν από το αμέσως επόμενο γράμμα της αλφαβήτου και γινόταν Ν,
κτλ.
Φυσικά δε χρησιμοποιούνταν μόνο το επόμενο γράμμα, αλλά μια οποιαδήποτε μετατόπιση.
Περισσότερες πληροφορίες υπάρχουν στη διεύθυνση http://en.wikipedia.org/wiki/Caesar_cipher

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

[evry]

Η άσκηση δεν είναι εκτός ύλης. Αν δώσεις στους μαθητές έναν πίνακα χαρακτήρων με όλα τα γράμματα της αλφαβήτου (24 ή 26) τότε ουσιαστικά η συνάρτηση Ord και η chr υλοποιούνται μέσω του πίνακα.
    Επίσης είναι αρκετά καλή άσκηση για το μάθημα αυτή η μετατόπιση των γραμμάτων στον πίνακα, πως σου φαίνεται?

[gpapargi]

Είμαι σίγουρος Άλκη ότι περιμένεις την ερώτησή μου. Και αφού κανείς δεν ξέρει τη ΓΛΩΣΣΑ καλύτερα από κάποιον που την υλοποίησε (ούτε καν αυτός που την προδιάγραψε) είμαι βέβαιος ότι θα έχεις μια καλή απάντηση. Ας διατυπώσω το ερώτημα με όσο γίνεται μεγαλύτερη αφέλεια:

Επιτρέπεται να χρησιμοποιήσεις τον τελεστή + σε αλφαριθμητικά και αυτό να σημαίνει συνένωση; Δηλαδή το ερώτημα είναι πως μπορούμε να στηρίξουμε μέσα από το διδακτικό πακέτο το ότι ‘α’+’β’=’αβ’;
Το βιβλίο (αν δεν έχω χάσει κάτι) αναφέρει το + στους αριθμητικούς τελεστές μόνο. Εδώ το χρησιμοποιούμε σαν τελεστή αλφαριθμητικών.  Έχεις δει και κάτι άλλο;

Θυμάμαι πιο παλιά είχα ξαναγράψει ότι για να εκτυπώσω strings οριζόντια θέλω είτε μια συνάρτηση συνένωσης είτε μια εντολή εκτύπωσης που δεν αλλάζει γραμμή στο τέλος. Νομίζω πως κάποτε σε είχα ξαναδεί να γράφεις για τον τελεστή  + στα αλφαριθμητικά και είχα σκοπό να σε ρωτήσω αλλά μετά το ξέχασα.

[alkisg]

Γιώργο περίμενα την ερώτηση, αλλά σόρρυ, δεν έχω απάντηση από το σχολικό βοήθημα, πέρα από αυτά που είχαμε πει στις σχετικές συζητήσεις:
https://alkisg.mysch.gr/steki/index.php?topic=374.0
https://alkisg.mysch.gr/steki/index.php?topic=453.0

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

Έλεγχος δεδομένων
Σε πρώτο στάδιο αυτό που πρέπει να μην αγνοηθεί, είναι ο έλεγχος των δεδομένων εισόδου.

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

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

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

[kLee]

Πολύ καλο θέμα Άλκη!

Αυτό ακριβώς εννοώ ρε παιδιά, να υπάρχει και για μας που διδάσκουμε το μάθημα μια πρόκληση να μάθουμε και να υλοποιήσουμε κ κάτι καινούργιο!
Γιατί να κρινόμαστε για την αγάπη μας για το αντικείμενο? Υπάρχει και αυτό! Δεν υποχρεώνουμε κανέναν να τα βάλει σα θέματα σε εξετάσεις, αλλά μακάρι στα εργαστήρια των σχολείων να γινότανε δουλειά με τέτοιο υλικό! Εργαστηριακό μάθημα υποτίθεται ότι είναι η εκμάθηση της ΓΛΩΣΣΑΣ..

[gpapargi]

Χμμμμμ σε αυτό το εύλογο ερώτημα όμως θα μας σώσει τη συνένωση των αλφαριθμητικών; Βασικά θέλεις να μπορείς να αναφερθείς με α[1] στον πρώτο χαρακτήρα του αλφαριθμητικού α (που μάλλον απαγορεύεται).
Αν διαβάζεις χαρακτήρα χαρακτήρα τα ψηφία ενός ακεραίου μπορείς να κάνεις τη  μετατροπή σε ακεραίους και στη συνέχεια τη συνένωση με τις δυνάμεις του 10 (πχ 345 = 3*10^2 +4*10^1+5*10^0). Αλλά αν εισάγει κάποιος ‘345’ με τη μια μπορούμε να μπούμε μέσα στους επιμέρους χαρακτήρες;

[alkisg]

Ψιλο-ισοδύναμα είναι από άποψη δυνατοτήτων (όχι όμως και από απόδοσης).
Αν υποστηρίζεται συνένωση, μπορείς κατασκευάζοντας ένα string και συγκρίνοντας να βρεις τα στοιχεία του μόνο με τους τελεστές >, <, =. Οπότε "αλγεβρικά" μιλώντας, είναι ισοδύναμα, μπορείς να υλοποιήσεις σε συναρτήσεις τις δυνατότητες που δεν έχεις.
Το θέμα είναι ότι αν δεν έχεις έστω και κάτι κόβεται όλο το string handling... Βέβαια π.χ. στην παραπάνω άσκηση μπορείς να βγάλεις το τελευταίο ερώτημα, "να εμφανίζονται σε μία γραμμή", και να γίνει εντός ύλης, αλλά έτσι χάνεται η μαγεία... Αν πεις στο μαθητή να δίνει - διαβάζει ένα γράμμα τη φορά, ξενέρωσε...

edit: μάλλον πρέπει να είμαι λίγο πιο αναλυτικός... Έστω μία μεταβλητή χαρακτήρας = 'asdfghjkl'. Αν υποστηρίζεται συνένωση, μπορώ με πεπερασμένες επαναλήψεις να το αναλύσω σε πίνακα χαρακτήρων = ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'].
Για να το κάνω αυτό, ξεκινώ με s = 'n' και κάνω κάτι σαν δυαδική αναζήτηση ανάμεσα στα 'a' και 'z', μεταβάλλοντας το s και συγκρίνοντάς το διαδοχικά με τη μεταβλητή χαρακτήρα, μέχρι να βρω το πρώτο γράμμα της. Έτσι χρησιμοποιώ μόνο τους τελεστές <, > και =. Αφού βρω ότι το πρώτο γράμμα είναι το 'a', προσθέτω στο s πάλι το 'n', γίνεται 'an' και κάνω πάλι δυαδική αναζήτηση της μεταβλητής χαρακτήρα κοκ. Έτσι μπορώ να κάνω μια συνάρτηση που επιστρέφει οποιονδήποτε από τους χαρακτήρες του s, και επειδή στο τέλος των δυαδικών αναζητήσεων θα έχω υπολογίζει το s, θα έχω και το μήκος του. Αλγεβρικά λοιπόν είναι ισοδύναμα, μπορώ να υλοποιήσω το indexing αν έχω τη συνένωση. Πληροφορικά... it sucks, θέλει O[N*logN] επί περίπου Ν ακόμα για το σταδιακό χτίσιμο του s επί περίπου maxof(char) ακόμα για τις ord και chr που θα χρειαστούν.

Συμπέρασμα; Αφού ο Διερμηνευτής (αλλά και η Γλωσσομάθεια) υποστηρίζει + στα αλφαριθμητικά, είναι δυνατόν να υλοποιηθεί σε αυτόν μια διαδικασία που να μετατρέπει ένα οποιοδήποτε αλφαριθμητικό σε πίνακα μονών χαρακτήρων!!!
Γιώργο αν θες να το δεις για πλάκα, μπορώ να το υλοποιήσω και το αρχικό μήνυμα της κρυπτογράφησης να δίνεται σε μία γραμμή!

[gpapargi]

Βιάστικα να ρωτήσω. Ξέχασα ότι είχα κάνει το ίδιο και εγώ πιο παλιά αυτό με αφορμή την άσκηση της αναζήτησης κατακερματισμού (σχολικό βιβλίο σελίδα 56 αφήνεται σαν άσκηση στο μαθητή). Αυτή η άσκηση σε συνδυασμό με ένα ερώτημα που δέχτηκα από την τάξη για το ποια είναι η πιο γρήγορη μέθοδος αναζήτησης με ώθησε στο να θέσω στον εαυτό μου το ερώτημα: «Ποια είναι η ταχύτερη μέθοδος αναζήτησης που μπορώ να φτιάξω χωρίς να βγω από την ύλη;»

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

Η υπόθεση δεν περπάτησε γιατί δεν είχα στη διάθεσή μου τη συνένωση των strings. Προσπάθησα να κάνω κάτι αλχημίες του στυλ να χρησιμοποιήσω τους ακεραίους για να κάνω το κόλλημα (επειδή οι ακέραιοι κολλάνε με πρόσθεση και δυνάμεις του 10). Πήγα να μπλέξω με το 24δικό σύστημα αρίθμησης για να έχω ένα χαρακτήρα με μαθηματικές ιδιότητες ανά γράμμα της αλφαβήτου (εδώ βαράνε) και τελικά είδα ότι η φάση ξέφευγε. Ακόμα κι αν έβγαζα τη λύση (μου μάλλον δε βγαίνει) δεν άξιζε τον κόπο. Έτσι απέτυχα ενδόξως 

Ανακεφαλαιώνοντας αν παίξεις με όλα τα όπλα (και τα εκτός ύλης) μπορείς με δυαδική αναζήτηση να βρεις ένα ζεύγος διαδοχικών χαρακτήρων που αν  κολλήσεις τον καθένα στο χτιζόμενο string καταλήγεις σε 2 strings που φράσουν πάνω και κάτω αυτό που πας να φτιάξεις. Αν οι χαρακτήρες που υποστηρίζεις είναι μέχρι 32 με 5 βήματα είσαι ΟΚ. Κι αν το string που πας να φτιάξεις έχει ν χαρακτήρες πάμε σε 5ν βήματα. Όχι κι άσχημα (αν δε μου ξέφυγε κάτι) αν σκεφτείς ότι και δεχόμαστε το αυτόματο σπάσιμο string σε πίνακα χαρακτήρων θα φτάσεις μέχρι τη θέση ν. 

Αυτά όσο αφορά τα περίεργα.

Τώρα το θέμα είναι άλλο.

Κοιτώντας το σχολικό βιβλίο στις παραγράφους 7.5, 7.7, 8.1 μου δίνεται η εντύπωση ότι αναφέρονται όλα όσα επιτρέπονται από τελεστές και πράξεις σε τύπους δεδομένων. Με βάση αυτά θα έλεγε κανείς με αρκετή ασφάλεια ότι δεν επιτρέπεται η συνένωση αλφαριθμητικών.
 
Αλλά στο βιβλίο καθηγητή αναφέρεται η φράση:
«Γενικεύοντας το πρόβλημα και θεωρώντας ότι ο χρήστης του προγράμματος μπορεί να πληκτρολογήσει οτιδήποτε, θα έπρεπε η μεταβλητή εισόδου να είναι αλφαριθμητική, να γίνουν οι σχετικοί έλεγχοι και μετά η μετατροπή, εφ' όσον είναι όλα καλά.»

Αυτό έρχεται να ταράξει τα νερά.

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

 Μπορούμε όμως να βρούμε τρόπο να κάνουμε αληθή την παραπάνω πρόταση.

Ένας τρόπος είναι να εννοούν ότι εισάγουμε τα ψηφία ενός αριθμού  ένα ένα για να γίνονται οι έλεγχοι. Στη συνέχεια μετατρέπουμε σε αριθμούς και μετά κολλάμε (με δυνάμεις του 10 και πρόσθεση). Αλλά αυτό είναι εξαιρετικά άβολο για το χρήστη. Είναι ανώμαλη σκέψη.

Άλλος τρόπος να κάνουμε την πρόταση αληθή είναι να δεχτούμε ότι υπάρχει τελεστής συνένωσης χαρακτήρων. Αν και δεν αναφέρεται ρητά κάτι τέτοιο υποθέτουμε τον +. Τι άλλο θα μπορούσε να είναι; Δε θα μπορούσε να είναι κάτι περίεργο αφού θα έπρεπε να αναφέρεται ρητά. Πχ αν υπήρχε συνάρτηση συνένωσης θα έπρεπε να αναφέρεται ο ορισμός της Συνένωση(string1, string2) που επιστρέφει το ενωμένο αλφαριθμητικό. Ωστόσο νομίζω ότι υπάρχει μια αυθαιρεσία. Έχουμε τόσο δυνατό εργαλείο και δε μας το λένε ρητά;
Αν φτάσουμε στο σημείο να κάνουμε αυτή την παραδοχή για να κάνουμε αληθή την πρόταση, γιατί να μη δεχτούμε ότι γίνεται αυτόματη αποθήκευση του αλφαριθμητικού σε πίνακα; Θα βόλευε ακόμα πιο πολύ στο χειρισμό χωρίς να μας αναγκάζει να καταφύγουμε σε ακρότητες όπως το να κατασκευάζουμε σταδιακά το αλφαριθμητικό με αναζητήσεις και συνενώσεις.
Θα μου πεις ότι με αυτή την παραδοχή πάλι δεν μπορούμε να εκτυπώσουμε string οριζόντια αν αυτό προκύψει από συνένωση 2 άλλων γιατί δεν μπορείς να εκτυπώσεις πίνακα οριζόντια. Τη συνένωση τη θέλεις. Η παραδοχή της συνένωσης είναι η ελάχιστη δυνατή απαίτηση για να μπορείς να κάνεις τα πάντα. Και είναι λογικό να προχωρούμε με τον ελάχιστο αριθμό παραδοχών.
Αλλά αν το δούμε έτσι είναι σα να ψιλοπαραδεχόμαστε ότι η παραδοχή του + είναι κάπως αυθαίρετη και για αυτό δε θέλουμε να αυξήσουμε σε 2 τις παραδοχές (μια για το + κα μια για την αυτόματη αποθήκευση σε πίνακα) γιατί θα έχουμε 2 τις αυθαιρεσίες.

Δεν ξέρω… είναι δυνατόν να περίμεναν από εμάς οι συγγραφείς όλες αυτές τις σκέψεις; Δηλαδή να επέτρεπαν συνειδητά το χειρισμό strings μέσω της συνένωσης και να απαγόρευαν την αυτόματη αποθήκευση του αλφαριθμητικού σε πίνακα; Πιο φυσιολογικό μου φαίνεται να τους ξέφυγε η πρόταση στηριζόμενη στην πρότερη εμπειρία τους από γλώσσες προγραμματισμού. Δηλαδή πιστεύω πως αν ρωτήσουμε κάποιο συγγραφέα αν υπάρχει το + σαν τελεστής συνένωσης αλφαριθμητικών δε νομίζω να μας πει ναι. Θα πρέπει να του παραθέσουμε και αρκετούς συλλογισμούς.

Βέβαια για αν είμαι ειλικρινής δεν έχω άποψη. Εσύ  αισθάνεσαι ασφαλής για το + και ανασφαλής για τη αυτόματη αποθήκευση; Δε μου φαίνεται να διαφέρουν τόσο πολύ ως προς το αν είναι αυθαίρετα ή προκύπτουν από το διδακτικό πακέτο.

 

[alkisg]

> Εσύ  αισθάνεσαι ασφαλής για το +;

Όχι βρε! Ίσα ίσα, στο https://alkisg.mysch.gr/steki/index.php?topic=918.0 προτείνω να αλλάξουν τα λογισμικά που υποστηρίζουν το μάθημα και να βαράνε syntax error όταν βλέπουν 'α' + 'β'!

[Sergio]

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

Καλή ασκησούλα

[Sergio]

Κώδικας: ΓΛΩΣΣΑ

1. ΠΡΟΓΡΑΜΜΑ ΚρυπροΓράφηση_Ακέραιου_αλα_Καίσαρα
2. ΜΕΤΑΒΛΗΤΕΣ
3.   ΑΚΕΡΑΙΕΣ: Αρχικός, Τελικός, ψηφίο, Υπόλοιπο, εκθέτης, μετατόπιση
4. ΑΡΧΗ
5.   ΓΡΑΨΕ "Ποιόν αριθμό θέλεις να κωδικοποιήσεις;"
6.   ΔΙΑΒΑΣΕ Αρχικός
7.   ΓΡΑΨΕ "Ποιά είναι μετατόπιση;"
8.   ΔΙΑΒΑΣΕ μετατόπιση
9.  
10.   Υπόλοιπο <- Α_Τ(Αρχικός)
11.   Τελικός <- 0
12.   εκθέτης <- 0
13.   ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
14.     ψηφίο <- Υπόλοιπο MOD 10
15.     Υπόλοιπο <- Υπόλοιπο DIV 10
16.     ΚΑΛΕΣΕ κρυπτογράφηση(ψηφίο, μετατόπιση)
17. ! ή
18. !    ψηφίο <- κρυπτογραφημένο(ψηφίο, μετατόπιση)
19.     Τελικός <- Τελικός + Α_Μ(ψηφίο * 10 ^ εκθέτης)
20.     εκθέτης <- εκθέτης + 1
21.   ΜΕΧΡΙΣ_ΟΤΟΥ Υπόλοιπο = 0
22.  
23.   ΑΝ Αρχικός < 0 ΤΟΤΕ
24.     Τελικός <- -Τελικός
25.   ΤΕΛΟΣ_ΑΝ
26.   ΓΡΑΨΕ "Η κρυπτογράφηση του ", Αρχικός, " δίνει ", Τελικός
27. ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
28.  
29. ΔΙΑΔΙΚΑΣΙΑ κρυπτογράφηση(χ, ψ)
30. ΜΕΤΑΒΛΗΤΕΣ
31.   ΑΚΕΡΑΙΕΣ: χ, ψ
32. ΑΡΧΗ
33.   χ <- (χ + ψ) MOD 10
34. ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
35.  
36. ΣΥΝΑΡΤΗΣΗ κρυπτογραφημένο(χ, ψ): ΑΚΕΡΑΙΑ
37. ΜΕΤΑΒΛΗΤΕΣ
38.   ΑΚΕΡΑΙΕΣ: χ, ψ
39. ΑΡΧΗ
40.   κρυπτογραφημένο <- (χ + ψ) MOD 10
41. ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

[Sergio]

Άλκη,

ο τελεστής ^ δίνει πραγματικό αποτέλεσμα;

Στην παραπάνω άσκηση έπρεπε να χρησιμοποιήσω Α_Μ(10^χ), έστω και αν το χ είναι ακέραιο, διαφορετικά υπήρχε πρόβλημα.

Σωστά;

[alkisg]

Από τη βοήθεια του Διερμηνευτή, https://alkisg.mysch.gr/help/?p=Telestes:

^ (δύναμη): ισχύει για τους ακέραιους και τους πραγματικούς. Το αποτέλεσμα είναι συνήθως πραγματικός αριθμός, εκτός αν ο εκθέτης είναι θετικός ακέραιος σταθερής αποτίμησης. Για παράδειγμα το 2^2 είναι ακέραιος, ενώ το 2^-2 πραγματικός (= 0.25). Έτσι στην γενική περίπτωση το 2^ι εκλαμβάνεται σαν πραγματικός αριθμός.

Δηλαδή το πρόβλημα δεν είναι αν το χ είναι ή όχι ακέραιος, το πρόβλημα είναι αν το χ είναι ή όχι αρνητικός ακέραιος. Αν είναι αρνητικός, το 10^χ είναι πραγματικός.
Και φυσικά η συντακτική ανάλυση δεν μπορεί να γνωρίζει αν το χ θα πάρει ή όχι αρνητικές τιμές, οπότε το θεωρεί γενικά πραγματικό αριθμό.