Πώς σπάει μια κρυπτογράφηση απλής αντικατάστασης

Η κρυπτογράφηση απλής αντικατάστασης είναι ένας σχεδόν παιδικός τρόπος να κρυπτογραφήσουμε ένα κείμενο. Ορίζουμε από μόνοι μας ότι κάθε γράμμα της αλφαβήτου αντικαθίσταται από κάποιο άλλο, δηλαδή όπου Α θα βάζουμε Κ, όπου Β θα βάζουμε Χ κ.ο.κ. Η αντικατάσταση μπορεί να είναι εντελώς τυχαία ή μπορεί να ακολουθεί κάποια λογική, όπως για παράδειγμα κάθε γράμμα να αντικαθίσταται με το αμέσως επόμενό του στην σειρά της αλφαβήτου. Φυσικά, δεν υπάρχει κάποια πρακτική αξία στο να μάθεις να σπας τέτοιες κρυπτογραφήσεις εκτός κι αν βρήκες ακαταλαβίστικα σημειώματα στην τσάντα του σχολείου του μικρού σου αδερφού (μην γελάς… εγώ το είχα κάνει στο σχολείο!). Το ενδιαφέρον όμως σε αυτή την κρυπτογράφηση είναι πως οι πιθανοί συνδυασμοί κλειδιών είναι της τάξης του \(26!\) (έχω βαρεθεί να σου λέω ότι το θαυμαστικό είναι το σύμβολο του παραγοντικού), αριθμός απαγορευτικά μεγάλος για κάποιον που θέλει να επιχειρήσει επίθεση με όλους τους πιθανούς συνδυασμούς. Εκεί έρχεται να μπει η θαυμαστή ανθρώπινη λογική που κάνει μια κρυπτογράφηση με τόσα πολλά κλειδιά, να σπάει για πλάκα.

Οπουδήποτε βλέπεις ισότητες γραμμάτων π.χ Α=Β, να ξέρεις ότι γράφω πάντα το πραγματικό γράμμα αριστερά (Α) και το κρυπτογραφημένο δεξιά (Β).

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

                                       
A = L N = U
B = Q O = D
C = V P = I
D = M Q = Y
E = F R = N
F = K S = X
G = B T = A
H = P U = H
I = R V = W
J = Z W = E
K = C X = T
L = G Y = J
M = O Z = S
 
Στην συνέχεια, με βάση αυτόν τον πίνακα, πήρε και κρυπτογράφησε το κείμενό του, το οποίο πλέον φαίνεται κάπως έτσι:

RXLJADJDHADMLJOJKNRFUMXXDFWFUAPDHBPEFKLVFAPFMRKKRVHGARFXDKADML
JLUMADODNNDERXARGGPLWFLMNFLORARXLMNFLOMFFIGJNDDAFMRUAPFLOFNRVL
UMNFLORPLWFLMNFLOAPLADUFMLJAPRXULARDUERGGNRXFHILUMGRWFDHAAPFAN
HFOFLURUBDKRAXVNFFMEFPDGMAPFXFANHAPXADQFXFGKFWRMFUAAPLALGGOFUL
NFVNFLAFMFYHLGRPLWFLMNFLOAPLADUFMLJDUAPFNFMPRGGXDKBFDNBRLAPFXD
UXDKKDNOFNXGLWFXLUMAPFXDUXDKKDNOFNXGLWFDEUFNXERGGQFLQGFADXRAMD
EUADBFAPFNLAAPFALQGFDKQNDAPFNPDDM

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

                                       
Γράμμα Συχνότητα  εμφάνισης (%)
A 8,2
B 1,4
C 2,8
D 3,8
E 12,7
F 2,9
G 2,0
H 5,3
I 6,3
J 0,1
K 0,4
L 3,4
M 2,3
N 7,1
O 8,0
P 2,0
Q 0,1
R 6,8
S 6,1
T 10,5
U 2,5
V 0,9
W 1,5
X 0,2
Y 2,0
Z 0,1
 
Βλέπουμε στον πίνακα πως τα πιο συχνά εμφανιζόμενα γράμματα είναι τα E, T, A και O. Κάνοντας την ίδια ανάλυση στο κρυπτογραφημένο μας κείμενο, προκύπτουν τα εξής:
                                       
Γράμμα Συχνότητα  εμφάνισης (%)
A 10,12
B 0,99
C 0
D 8,89
E 1,48
F 14,32
G 5,19
H 1,98
I 1,73
J 1,98
K 3,21
L 9,14
M 5,68
N 6,42
O 2,96
P 5,68
Q 1,23
R 4,94
S 0
T 0
U 4,94
V 1,23
W 2,22
X 5,43
Y 0,25
Z 0
 
Το πιο συχνά εμφανιζόμενο γράμμα στο κρυπτογραφημένο κείμενο όπως φαίνεται από τον πίνακα, είναι το γράμμα F με ποσοστό 14,32%. Είναι ορθό λοιπόν να υποθέσουμε ότι το F αντικαθιστά το E. Κάνουμε την αντικατάσταση:

RXLJADJDHADMLJOJKNReUMXXDeWeUAPDHBPEeKLVeAPeMRKKRVHGAReXDKADML
JLUMADODNNDERXARGGPLWeLMNeLORARXLMNeLOMeeIGJNDDAeMRUAPeLOeNRVL
UMNeLORPLWeLMNeLOAPLADUeMLJAPRXULARDUERGGNRXeHILUMGRWeDHAAPeAN
HeOeLURUBDKRAXVNeeMEePDGMAPeXeANHAPXADQeXeGKeWRMeUAAPLALGGOeUL
NeVNeLAeMeYHLGRPLWeLMNeLOAPLADUeMLJDUAPeNeMPRGGXDKBeDNBRLAPeXD
UXDKKDNOeNXGLWeXLUMAPeXDUXDKKDNOeNXGLWeDEUeNXERGGQeLQGeADXRAMD
EUADBeAPeNLAAPeALQGeDKQNDAPeNPDDM

Με την ίδια λογική μπορούμε να υποθέσουμε ότι το δεύτερο πιο συχνά εμφανιζόμενο γράμμα του κρυπτογραφημένου κειμένου, δηλαδή το A, αντικαθιστά το T. Μπορούμε να το κάνουμε αυτό για τα 4 πρώτα γράμματα μιας κι από ‘κει και κάτω τα ποσοστά συγκλίνουν αρκετά για να έχουμε σαφές στατιστικό συμπέρασμα. Άρα θεωρούμε ότι E=F, T=A, A=L και O=D οπότε και τα αντικαθιστούμε στο κρυπτογραφημένο κείμενο:

RXaJtoJoHtoMaJOJKNReUMXXoeWeUtPoHBPEeKaVetPeMRKKRVHGtReXoKtoMa
JaUMtoOoNNoERXtRGGPaWeaMNeaORtRXaMNeaOMeeIGJNooteMRUtPeaOeNRVa
UMNeaORPaWeaMNeaOtPatoUeMaJtPRXUatRoUERGGNRXeHIaUMGRWeoHttPetN
HeOeaURUBoKRtXVNeeMEePoGMtPeXetNHtPXtoQeXeGKeWRMeUttPataGGOeUa
NeVNeateMeYHaGRPaWeaMNeaOtPatoUeMaJoUtPeNeMPRGGXoKBeoNBRatPeXo
UXoKKoNOeNXGaWeXaUMtPeXoUXoKKoNOeNXGaWeoEUeNXERGGQeaQGetoXRtMo
EUtoBetPeNattPetaQGeoKQNotPeNPooM

Όπως αξιοποιήσαμε τα πιο συχνά εμφανιζόμενα γράμματα, θα μπορούσαμε να αξιοποιήσουμε και τα πιο σπάνια όπως το Z, το Q και το X αλλά όπως βλέπουμε στην ανάλυση του κρυπτογραφημένου κειμένου, υπάρχουν 4 γράμματα που δεν εμφανίζονται ποτέ οπότε δεν μπορούμε να κάνουμε κάποια αντιστοιχία. Δεν πτοούμαστε όμως!

Πάμε τώρα να δούμε τα ζεύγη γραμμάτων (διγραμματική ανάλυση, bigram analysis). Ο παρακάτω πίνακας μας δίνει τα 12 πιο συχνά εμφανιζόμενα ζεύγη γραμμάτων:

                                       
Δίγραμμα Συχνότητα  εμφάνισης
th 1,52
he 1,28
in 0,94
er 0,94
an 0,82
re 0,68
nd 0,63
at 0,59
on 0,57
nt 0,56
ha 0,56
es 0,56
 
Ας κάνουμε την ίδια ανάλυση και για το κρυπτογραφημένο κείμενο κι ύστερα συζητάμε τα συμπεράσματα που προκύπτουν:
                                       
Δίγραμμα Συχνότητα  εμφάνισης
ap 16
fl 11
pf 10
ad 9
nf 9
wf 8
xd 7
fa 7
fm 7
fn 7
la 7
fx 6
 
Στα ζεύγη γραμμάτων του κρυπτογραφημένου κειμένου, βλέπουμε πρώτο-πρώτο το ζεύγος AP. Ξέρουμε ότι το πιο συχνό ζεύγος στην αγγλική γλώσσα είναι το TH από τον προηγούμενο πίνακα και είδαμε ήδη νωρίτερα ότι T=A άρα είναι ασφαλές να υποθέσουμε ότι H=P.

RXaJtoJoHtoMaJOJKNReUMXXoeWeUthoHBhEeKaVetheMRKKRVHGtReXoKtoMa
JaUMtoOoNNoERXtRGGhaWeaMNeaORtRXaMNeaOMeeIGJNooteMRUtheaOeNRVa
UMNeaORhaWeaMNeaOthatoUeMaJthRXUatRoUERGGNRXeHIaUMGRWeoHtthetN
HeOeaURUBoKRtXVNeeMEehoGMtheXetNHthXtoQeXeGKeWRMeUtthataGGOeUa
NeVNeateMeYHaGRhaWeaMNeaOthatoUeMaJoUtheNeMhRGGXoKBeoNBRatheXo
UXoKKoNOeNXGaWeXaUMtheXoUXoKKoNOeNXGaWeoEUeNXERGGQeaQGetoXRtMo
EUtoBetheNatthetaQGeoKQNotheNhooM

Μπορούμε να υποθέσουμε ότι είμαστε στον σωστό δρόμο διότι έχουν αρχίσει ήδη να σχηματίζονται λέξεις όπως το “the” και “that”. Αν κοιτάξουμε προσεκτικά το κείμενο, μπορούμε να βρούμε ημιτελείς λέξεις και να συμπληρώσουμε τα γράμματα που λείπουν. Για παράδειγμα, έχουμε το “thoHBh” το οποίο δεν μπορεί να είναι τίποτε άλλο από την λέξη “though”. Άρα υποθέτουμε ότι U=H και G=B:

RXaJtoJoutoMaJOJKNReUMXXoeWeUthoughEeKaVetheMRKKRVuGtReXoKtoMa
JaUMtoOoNNoERXtRGGhaWeaMNeaORtRXaMNeaOMeeIGJNooteMRUtheaOeNRVa
UMNeaORhaWeaMNeaOthatoUeMaJthRXUatRoUERGGNRXeuIaUMGRWeoutthetN
ueOeaURUgoKRtXVNeeMEehoGMtheXetNuthXtoQeXeGKeWRMeUtthataGGOeUa
NeVNeateMeYuaGRhaWeaMNeaOthatoUeMaJoUtheNeMhRGGXoKgeoNgRatheXo
UXoKKoNOeNXGaWeXaUMtheXoUXoKKoNOeNXGaWeoEUeNXERGGQeaQGetoXRtMo
EUtogetheNatthetaQGeoKQNotheNhooM

Ακριβώς πριν την λέξη “though” που συμπληρώσαμε, έχουμε τα γράμματα “eWeU” οπότε υποθέτουμε πως πρόκειται για την γνωστή έκφραση “even though”, άρα V=W και N=U:

RXaJtoJoutoMaJOJKNRenMXXoeventhoughEeKaVetheMRKKRVuGtReXoKtoMa
JanMtoOoNNoERXtRGGhaveaMNeaORtRXaMNeaOMeeIGJNooteMRntheaOeNRVa
nMNeaORhaveaMNeaOthatoneMaJthRXnatRonERGGNRXeuIanMGRveoutthetN
ueOeanRngoKRtXVNeeMEehoGMtheXetNuthXtoQeXeGKevRMentthataGGOena
NeVNeateMeYuaGRhaveaMNeaOthatoneMaJontheNeMhRGGXoKgeoNgRatheXo
nXoKKoNOeNXGaveXanMtheXonXoKKoNOeNXGaveoEneNXERGGQeaQGetoXRtMo
EntogetheNatthetaQGeoKQNotheNhooM

Παρατηρούμε σε κάποιο σημείο τα γράμματα “haveaMNeaOthatone” και υποθέτοντας τα κενά, έχουμε “have a MNeaO that one”. Οι πρώτες λέξεις που μου έρχονται στο μυαλό είναι steam, gleam και dream. Ήδη θυμίζει κάτι η πρόταση (γκουχ γκουχ I have a dream that one day… γκουχ γκουχ) αλλά δεν θέλουμε να βασιστούμε στις ιστορικές μας γνώσεις οπότε θα εξετάσουμε κάθε μια από τις υποθέσεις μας ξεχωριστά:

  1. steam: θα πρέπει να αποκλείσουμε αυτή την λέξη για τον απλό λόγο ότι γνωρίζουμε ήδη πως ο αντικαταστάτης του γράμματος T είναι το A στο κρυπτογραφημένο κείμενο και όχι το N.
  2. gleam: κι αυτή η λέξη πρέπει να αποκλειστεί γιατί γνωρίζουμε ήδη πως ο αντικαταστάτης του G είναι το B και όχι το Μ όπως θα απαιτούσε η περίπτωση.
  3. dream: εδώ έχουμε μια πιθανή λύση μιας και δεν γνωρίζουμε τίποτα για τους αντικαταστάτες των D, R και M γι’ αυτό και δοκιμάζουμε να δούμε αν ισχύει ότι D=M, R=N και M=O:

    RXaJtoJoutodaJmJKrRendXXoeventhoughEeKaVethedRKKRVuGtReXoKtoda
    JandtomorroERXtRGGhaveadreamRtRXadreamdeeIGJrootedRntheamerRVa
    ndreamRhaveadreamthatonedaJthRXnatRonERGGrRXeuIandGRveoutthetr
    uemeanRngoKRtXVreedEehoGdtheXetruthXtoQeXeGKevRdentthataGGmena
    reVreatedeYuaGRhaveadreamthatonedaJontheredhRGGXoKgeorgRatheXo
    nXoKKormerXGaveXandtheXonXoKKormerXGaveoEnerXERGGQeaQGetoXRtdo
    EntogetheratthetaQGeoKQrotherhood

    Ελέγχουμε προσεκτικά το κείμενο να δούμε αν υπάρχουν «περίεργα» ζευγάρια γραμμάτων που δεν θα μπορούσαν να βγάζουν νόημα. Όλα φαίνονται σωστά όμως οπότε θεωρούμε ότι η υπόθεσή μας ήταν σωστή.

Είναι ώρα να δοκιμάσουμε να βρούμε τα κενά, όπου αυτό είναι δυνατόν:

RXaJtoJoutodaJmJKrRendXXo_even_though_EeKaVethedRKKRVuGtReXoK_
todaJ_and_tomorroE_RXtRGG_have_a_dream_RtRXa_dream_deeIGJ_rooted_
RntheamerRVandreamR_have_a_dream_that_one_daJthRXnatRonERGGrRX
euIandGRveout_the_true_meanRng_oKRtXVreedEehoGdtheXetruthXtoQe
XeGKevRdentthataGGmen_are_Vreated_eYuaGR_have_a_dream_that_one
_daJ_on_the_redhRGGXoKgeorgRatheXonXoKKormerXGaveXand_theXonXo
KKormerXGaveoEnerXERGGQeaQGetoXRtdoEntogetheratthetaQGeoK_Qrot
herhood

Από την λέξη “tomorroE” μπορούμε να συμπεράνουμε ότι W=E, από το “have_a_dream_that_one_daJ_on_the” ότι Y=J και από το “meanRng” ότι I=R:

i_Xay_to_you_today_my_KriendXXo_even_though_weKaVethediKKiVuGt
ieXoK_today_and_tomorrow_iXtiGG_have_a_dream_it_iX_a_dream_deeIGy
_rooted_in_the_ameriVan_dream_i_have_a_dream_that_one_day_thiX_
nation_wiGGriXeuIandGiveout_the_true_meaning_oKitXVreedwehoGd
theXetruthXtoQeXeGKevidentthataGGmenareVreatedeYuaG_i_have_a_
dream_that_one_day_on_the_redhiGGXoK_georgia_theXonXoKKormerX
GaveX_and_the_XonXoKKormerXGaveownerXwiGGQeaQGetoXitdown_together
_at_the_taQGeoK_Qrotherhood

Αρχίζει σιγά-σιγά και αποκαλύπτεται το κείμενο. Βλέποντας την πρόταση “have_a_dream_it_iX_a_dream_deeIGy_rooted_in_the_ameriVan_dream” μπορούμε εύκολα να συμπεράνουμε ότι S=X, P=I, L=G και C=V:

i_say_to_you_today_my_Kriends_so_even_though_we_Kace_the_
diKKiculties_oK_today_and_tomorrow_i_still_have_a_dream_it_is_
a_dream_deeply_rooted_in_the_american_dream_i_have_a_dream_that
_one_day_this_nation_will_rise_up_and_live_out_the_true_meaning
_oK_its_creed_we_hold_these_truths_toQeselK_evident_that_all_men
_are_created_eYual_i_have_a_dream_that_one_day_on_the_red_hills
_oK_georgia_the_sons_oK_Kormer_slaves_and_the_sons_oK_Kormer_
slave_owners_will_QeaQleto_sit_down_together_at_the_taQle_oK_
Qrotherhood

Από το “Kriends” συμπεραίνουμε ότι F=K και από το “Qrotherhood” ότι B=Q κι έτσι έχουμε αποκρυπτογραφήσει πλέον όλο το κείμενο. Βάζοντας τα σημεία στίξης, έχουμε το πασίγνωστο απόσπασμα από την ομιλία του Martin Luther King jr. κατά των φυλετικών διακρίσεων στις 28 Αυγούστου 1963:

I say to you today, my friends, so even though we face the difficulties of today and tomorrow, I still have a dream. It is a dream deeply rooted in the American dream. I have a dream that one day this nation will rise up and live out the true meaning of its creed: “We hold these truths to be self-evident: that all men are created equal.” I have a dream that one day on the red hills of Georgia the sons of former slaves and the sons of former slave owners will be able to sit down together at the table of brotherhood.

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

Οι λέξεις συνήθως:

  • ξεκινάνε με: T, O, A, W, B, C, D, S, F, M, R, H, I, Y, E, G, L, N, U, J, K
  • έχουν δεύτερο γράμμα το: H, O, E, I, A, U, N, R, T
  • έχουν τρίτο γράμμα το: E, S, A, R, N, I
  • έχουν τελευταίο γράμμα το: E, S, T, D, N, R, Y, F, L, O, G, H, A, K, M, P, U, W
  • έχουν διπλά γράμματα τα: SS, EE, TT, FF, LL, MM, OO

Τριγραμματική ανάλυση (trigram analysis): είδαμε στο παράδειγμά μας νωρίτερα τον τρόπο που εκτελέσαμε και εφαρμόσαμε την διγραμματική ανάλυση. Στην τριγραμματική ανάλυση κάνουμε ακριβώς το ίδιο μόνο που αυτή τη φορά ψάχνουμε την συχνότητα επανάληψης συνδυασμών τριών γραμμάτων. Συνήθως αυτή η ανάλυση δεν πάει μακριά και μένει μόνο στο ότι ο πιο συχνά εμφανιζόμενος συνδυασμός τριών γραμμάτων είναι κατά πάσα πιθανότητα η λέξη “THE”. Επειδή όμως τα γράμματα E και T είναι από τα πρώτα που βρίσκουμε, το μόνο μας κέρδος είναι να βρούμε το γράμμα H καθώς και να σιγουρευτούμε ότι η αποκρυπτογράφησή μας για τα E και T είναι σωστή.

Διακριτή στατιστική ανάλυση Μαρκόφ: μια λίγο πιο περίπλοκη ανάλυση, είναι αυτή που μελετά την εξάρτηση κάποιου γράμματος από τα γύρω του. Για παράδειγμα, πόσο συχνά το γράμμα B ακολουθεί το γράμμα A; Για να το παραστήσουμε και μαθηματικά, θα γράφαμε:

\(P(Xj=B,Xj-1=A)\)
 
Υπολογίζοντας αυτή την πιθανότητα για όλους τους συνδυασμούς γραμμάτων, παίρνουμε έναν πίνακα διαστάσεων 26×26. Μόλις λοιπόν κάνουμε την αρχική αντικατάσταση με τα πιο συχνά γράμματα (E, T, A, O), μπορούμε στην συνέχεια να ανατρέξουμε σε αυτόν τον πίνακα και να δούμε ποιο γράμμα είναι πιθανότερο να ακολουθεί το E, το T κ.ο.κ.

Είδαμε λοιπόν πόσο εύκολο είναι να σπάσει μια κρυπτογράφηση απλής αντικατάστασης ακόμα κι αν οι πιθανές λύσεις φαντάζουν άπειρες. Αν δεν βάζαμε το μυαλό να δουλέψει και απλά δίναμε το πρόβλημα σε έναν υπολογιστή, θα κάναμε καιρό να πάρουμε απάντηση μιας και θα έπρεπε να υπολογίσει όλες τις \(26!\) πιθανές λύσεις και να εξετάσει την ορθότητα κάθε μιας απ’ αυτές ξεχωριστά. Βέβαια, αν είσαι στόκος, άσε τον υπολογιστή να το κάνει. Αφού δεν έχεις μυαλό, σίγουρα θα ‘χεις χρόνο.

 

1 comment on Πώς σπάει μια κρυπτογράφηση απλής αντικατάστασης

Leave a Reply

Your email address will not be published. Required fields are marked *