# Από: https://jfking50.github.io/decipher/
import numpy as np
import math
import pandas as pd
def get_trans_counts(plaintext):
'''takes .txt file and creates a dictionary with two-letter combinations as keys
and their counts as values.
returns a dictionary of the counts in the form {AB:343, AC:112, etc}'''
trans_counts = {}
chars = ['A','B','C','D','E','F','G','H','I','J','K','L','M',
'N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
f = open(plaintext)
wp = []
for line in f:
wp.append(line)
f.close()
for line in wp:
#convert to upper case
line = str.upper(line)
#remove the \n newline characters at the end of the line
line = line[0:len(line)-1]
#count the number of two letter pairs
for i in range(len(line)-1):
twoletter_key = line[i] + line[i+1]
#two consecutive letters
if (line[i] in chars) & (line[i+1] in chars):
if twoletter_key not in trans_counts: trans_counts[twoletter_key] = 1
else: trans_counts[twoletter_key] += 1
#non-letter followed by a letter
elif (line[i] not in chars) & (line[i+1] in chars):
twoletter_key = " " + line[i+1]
if twoletter_key not in trans_counts: trans_counts[twoletter_key] = 1
else: trans_counts[twoletter_key] += 1
#letter followed by a non-letter
elif (line[i] in chars) & (line[i+1] not in chars):
twoletter_key = line[i] + " "
if twoletter_key not in trans_counts: trans_counts[twoletter_key] = 1
else: trans_counts[twoletter_key] += 1
#two non-letters
elif (line[i] not in chars) & (line[i+1] not in chars):
twoletter_key = " " + " "
if twoletter_key not in trans_counts: trans_counts[twoletter_key] = 1
else: trans_counts[twoletter_key] += 1
return trans_counts
def map_key(key):
'''given a encryption or decryption key, returns a dictionary where the dictionary key
is the letter from the key and the value is the letter of the alphabet it maps to
in the form {A:R, B:W, C:O, etc}'''
alphabet = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
mapping = {}
for i in range(len(key)): mapping[alphabet[i]] = key[i]
return mapping
def apply_key(key, text):
'''encodes/decodes text given a de/encryption key (a sequence of 26 letters) and a string of text
returns a new text (string)'''
mapped_text = ""
#convert the text to a list
text = list(text)
#get the mapping from map_key
mapping = map_key(key)
#apply the mapping based on the key
for letter in text:
#convert to upper case
letter = str.upper(letter)
if letter in mapping: mapped_text += mapping[letter]
else: mapped_text += " "
return mapped_text
def score(key, text, trans_counts):
'''calculates the score of a decryption key based on it's log-likliness
to the referece text transition counts.
Returns a score value (float)'''
#get the current mapping
mapping = map_key(key)
#decode the text based on the mapping
decoded = apply_key(key, text)
key_score = 0
target_counts = {}
chars = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
#strip the text
stripped_text = decoded.strip()
#convert the target text into a list of characters
text_list = list(stripped_text)
#count the number of two letter pairs in the target text
for i in range(len(text_list)-1):
twoletter_key = text_list[i] + text_list[i+1]
#two consecutive letters
if (text_list[i] in chars) & (text_list[i+1] in chars):
if twoletter_key not in target_counts: target_counts[twoletter_key] = 1
else: target_counts[twoletter_key] += 1
#non-letter followed by a letter
elif (text_list[i] not in chars) & (text_list[i+1] in chars):
twoletter_key = " " + text_list[i+1]
if twoletter_key not in target_counts: target_counts[twoletter_key] = 1
else: target_counts[twoletter_key] += 1
#letter followed by a non-letter
elif (text_list[i] in chars) & (text_list[i+1] not in chars):
twoletter_key = text_list[i] + " "
if twoletter_key not in target_counts: target_counts[twoletter_key] = 1
else: target_counts[twoletter_key] += 1
#two non-letters
elif (text_list[i] not in chars) & (text_list[i+1] not in chars):
twoletter_key = " " + " "
if twoletter_key not in target_counts: target_counts[twoletter_key] = 1
else: target_counts[twoletter_key] += 1
for k,v in target_counts.items():
if k in trans_counts:
key_score += v*math.log(trans_counts[k])
return key_score
def get_proposed_key(key):
'''Takes a decryption key, randomly selects two letters, and swaps they keys for those letters.
So if A mapped to X and B mapped to Q, then A maps to Q and B to X.
Returns a new decryption key (string)'''
proposed_key = ""
chars = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
#randomly select two letters to swap
char1, char2 = np.random.choice(chars, size=2, replace=False)
#create a new key, swapping letters in the old key
new_key = list(key)
for i in range(len(new_key)):
if new_key[i] == char1: index1 = i
if new_key[i] == char2: index2 = i
new_key[index1] = char2
new_key[index2] = char1
for letter in new_key:
proposed_key += letter
return proposed_key
### MAIN PROGRAM
#get letter transition counts for reference text
trans_counts = get_trans_counts('wp_full.txt') # war and peace
#trans_counts = get_trans_counts('alice.txt') # alice in wonderland
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#generate a random encryption key
chars = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
encrypt_list = list(np.random.choice(chars, size=26, replace=False))
encrypt_key = ""
for i in encrypt_list:
encrypt_key = encrypt_key + i
encrypt_test ="abcdefghijklmnopqrstuvwxyz"
test_key = apply_key(encrypt_key, encrypt_test)
target_text =" to bat—rb. con todo mi respeto. i was sitting down playing chess with danny de emf and boxer de el centro was sitting next to us. boxer was making loud and loud voices so i tell him por favor can you kick back homie cause im playing chess. a minute later the vato starts back up again so this time i tell him con respecto homie can you kick back. the vato stop for a minute and he starts up again so i tell him check this out shut the fuck up cause im tired of your voice and if you got a problem with it we can go to celda and handle it. i really felt disrespected thats why i told him. anyways after i tell him that the next thing I know that vato slashes me and leaves. by the time i figure im hit i try to get away but the c.o. is walking in my direction and he gets me right by a celda. so i go to the hole. when im in the hole my home boys hit boxer so now b is also in the hole. while im in the hole im getting schoold wrong."
target_text = """Yes, and a noble reputation it was, worthy of a son of Zeus. As
you and Megillus have been trained in these institutions, I dare say
that you will not be unwilling to give an account of your government
and laws; on our way we can pass the time pleasantly in about them,
for I am told that the distance from Cnosus to the cave and temple
of Zeus is considerable; and doubtless there are shady places under
the lofty trees, which will protect us from this scorching sun.
Being no longer young, we may often stop to rest beneath them, and get
over the whole journey without difficulty, beguiling the time by
conversation."""
#encrypt the target text
encoded_text = apply_key(encrypt_key, target_text)
#generate a random decryption key
decrypt_list = list(np.random.choice(chars, size=26, replace=False))
current_decrypt_key = ""
for i in decrypt_list:
current_decrypt_key = current_decrypt_key + i
#Results!
print('Unencrypted text:\n', target_text)
print('\nEncrypted text:\n', encoded_text)
print('\n')
for iters in range(20001):
proposed_decrypt_key = get_proposed_key(current_decrypt_key)
current_score = score(current_decrypt_key, encoded_text, trans_counts)
proposed_score = score(proposed_decrypt_key, encoded_text, trans_counts)
#calculate the acceptance probability based on the ratio of the proposed and current scores
ap = min(1, math.exp(proposed_score - current_score))
#generate a random number between 0 and 1
runif = np.random.uniform()
#accept the proposed key only if the random number is less than the probability of acceptance
if runif >= ap: accept_proposed_key = False
else: accept_proposed_key = True
if accept_proposed_key: current_decrypt_key = proposed_decrypt_key
#print every 1000th iteration
if iters%500 == 0:
print('Iter:', iters, apply_key(current_decrypt_key, encoded_text)[0:99])
test = apply_key(encrypt_key, alphabet)
check = apply_key(current_decrypt_key, test)
correct = 0
for i in range(len(alphabet)):
if alphabet[i] == check[i]: correct += 1
#print('Number of correctly decoded letters:', correct)
print('\nDecrypted text:')
print(apply_key(current_decrypt_key, encoded_text))
#get number of correct letters
test = apply_key(encrypt_key, alphabet)
check = apply_key(current_decrypt_key, test)
correct = 0
for i in range(len(alphabet)):
if alphabet[i] == check[i]: correct += 1
print('\n')
#print(alphabet)
#print(check)
print('Number of correctly decoded letters:', correct)
Δείτε εδώ (μέχρι και παρ. 1.4) και εδώ για πιο λεπτομερή παρουσίαση και περισσότερη ορολογία. Και η αντίστοιχη σελίδα της Wikipedia μπορεί να σας φανεί χρήσιμη.
Ας υποθέσουμε ότι έχουμε τη μετοχή μιας εταιρείας που σήμερα έχει τιμή $S_0$ και αύριο την τιμή $S_1$. Υποθέτουμε επίσης ότι η μετοχή είτε αυξάνει κατά ένα παράγοντα $u>1$ είτε μειώνεται κατά ένα παράγοντα $d<1$. Δηλ. ισχύει $S_1 = uS_0$ ή $S_1 = dS_0$. Οι ποσότητες $u, d$ είναι γνωστές.
Παράλληλα με τη μετοχή αυτή υποθέτουμε την ύπαρξη ενός option αναφορικά με τη μετοχή αυτή. Αυτό είναι ένα συμβόλαιο που δίνει στον κάτοχό του (αγοραστή του συμβολαίου) ένα ποσό $f_u$ αν η μετοχή ανέβει και ένα ποσό $f_v$ αν η μετοχή πέσει. Τα ποσά αυτά τα δίνει ο πωλητής της option στον αγοραστή, ανάλογα με το τι θα κάνει η μετοχή τη χρονική στιγμή 1. Το ζητούμενο είναι η τιμολόγηση αυτής της option. Πόσο δηλ. πρέπει να δώσει ο αγοραστής στον πωλητή (τη χρονική στιγμή 0, οπότε γίνεται και η σύναψη του συμβολαίου);
Η αξία του συμβολαίου τη χρονική στιγμή 1 είναι ξεκάθαρη. Αξίζει $f_u$ αν ανέβηκε η μετοχή και $f_v$ αν έπεσε η μετοχή. Πόσο είναι η αξία της τη χρονική στιγμή 0; Για να το βρούμε αυτό κατασκευάζουμε κατ' αρχήν (ιδεατά) ένα μεικτό χαρτοφυλάκιο (portfolio) που απαρτίζεται από $\Delta$ πλήθος μετοχών και από πώληση μιας option. Ο ιδιοκτήτης του χαρτοφυλακίου δηλ. τη χρονική στιγμή 0 αγοράζει $\Delta$ στο πλήθος μετοχές και πουλάει μια option. Αν συμβολίσουμε με $f_0$ την αξία της option (για τον αγοραστή) τότε η αξία του χαρτοφυλακίου τη χρονική στιγμή 0 είναι $$ \Delta S_0 - f_0. $$ (Οι μετοχές συνεισφέρουν θετικά στην αξία του χαρτοφυλακίου ενώ η option αρνητικά μια και ως πωλητές του option έχουμε υποχρέωση λόγου αυτής.)
Τη χρονική στιγμή 1 η αξία του χαρτοφυλακίου είναι $\Delta u S_0 - f_u$ αν η μετοχή ανέβηκε και $\Delta d S_0 - f_d$ αν η μετοχή έπεσε. Μπορούμε τώρα να επιλέξουμε την ποσότητα $\Delta$ με τέτοιο τρόπο ώστε οι δύο αυτές εναλλακτικές αξίες τη χρονική στιγμή 1 να είναι ίδιες, λύνοντας την εξίσωση $$ \Delta u S_0 - f_u = \Delta d S_0 - f_d. $$ Με αυτή την επιλογή το χαρτοφυλάκιο είναι risk-free αφού δεν υπάρχει καμία αμφιβολία για το ποια είναι η αξία του τη χρονική στιγμή 1. Υπό την καθιερωμένη υπόθεση έλλειψης arbitrage αυτό σημαίνει ότι η αξία του χαρτοφυλακίου τις δύο χρονικές στιγμές 0 και 1 είναι η ίδια. Δεν πρέπει να ξεχνάμε και την ύπαρξη του λεγόμενου risk-free interest rate, που είναι π.χ. το εγγυημένο επιτόκιο $r$ που δίνει μια τράπεζα (ή ένα κράτος με τα ομόλογά του) και που μας δίνει ένα τρόπο να αναγάγουμε μια αξία από μια χρονική στιγμή σε μια άλλη πολλαπλασιάζοντας με $e^{r \tau}$ όπου το χρονικό διάστημα $\tau$ ανάμεσα στις δύο χρονικές στιγμές είναι θετικό ή αρνητικό. (Δείτε αυτό το video για το πώς προκύπτει το $e^{r \tau}$.)
Βρίσκουμε έτσι λοιπόν $\Delta = \frac{f_u-f_d}{(u-d) S_0}$ που μας οδηγεί, ακολουθώντας τον προηγούμενο συλλογισμό, στον τύπο $$ f_0 = e^{-r\tau} (p f_u + (1-p) f_d), \text{ όπου } p = \frac{e^{r\tau}-d}{u-d}. $$ Στον τύπο αυτό $r$ είναι το ετήσιο επιτόκιο που δίνει η τράπεζα (π.χ. $r=0.1$ αν η τράπεζα έχει ετήσιο επιτόκιο 10% με συνεχή ανατοκισμό) και $\tau$ είναι το χρονικό διάστημα (σε έτη) ανάμεσα στις στιγμές 0 και 1.
Εδώ η υπόθεση $e^{r\tau} \le u$ είναι απολύτως φυσιολογική, αλλιώς θα είχαμε να κάνουμε με μια μετοχή που και στην καλή της περίπτωση θα είχε άνοδο μικρότερη από το αν βάζαμε το αντίστοιχο ποσό στην τράπεζα, μια μετοχή δηλ. με εγγυημένη χασούρα. Yπό αυτή την υπόθεση ο αριθμός $p$ είναι στο διάστημα $[0, 1]$ και μπορούμε να τον ερμηνεύσουμε ως μια πιθανότητα (χωρίς όμως να είναι πραγματικά κάτι τέτοιο) για ευκολία μας. Υπό αυτή την πιθανότητα τότε μπορεί ο παραπάνω τύπος να γραφτεί ως $$ f_0 = e^{-r \tau} \mathbb{E}_p(f_1) $$ όπου $f_1$ είναι η αξία της option τη χρονική στιγμή 1 (δηλ. $f_1 = f_u$ ή $f_1 = f_d$). Υπό αυτή λοιπόν την φανταστική πιθανότητα $p$ η αξία της option τη χρονική στιγμή 0 είναι η μέση αξία της την επόμενη χρονική στιγμή (μεταφερμένη στο παρόν με τον παράγοντα $e^{-r\tau}$)
Αν μας ενδιαφέρει να τιμολογήσουμε ένα option που γνωρίζουμε την αξία του μετά από $k$ χρονικές στιγμές η διαδικασία είναι η ακόλουθη. (Για να δουλέψουν τα παρακάτω θα πρέπει η μορφή του συμβολαίου να εξαρτάται μόνο από την αξία της μετοχής, και όχι από το ολόκληρη την ιστορία εξέλιξης της μετοχής μέχρι τη χρονική στιγμή $k$.)
Η μετοχή ξεκινάει από την τιμή $S_0$ (τη χρονική στιγμή 0) και σε κάθε χρονική στιγμή $t+1$ η τιμή της μετοχής είναι είτε $u S_t$ είτε $d S_t$. Βλέπουμε ότι οι δυνατές τιμές της μετοχής τη χρονική στιγμή $k$ είναι οι $$ u^j d^{k-j} S_0, \text{ για } j=0, 1, 2, \ldots, k. $$ Υποθέτουμε ότι ξέρουμε την αξία του συμβολαίου για κάθε μια από τις παραπάνω περιπτώσεις. Για παράδειγμα, το συμβόλαιο θα μπορούσε να είναι της μορφής
σου επιτρέπω να αγοράσεις μια μετοχή στη τιμή $K$ τη χρονική στιγμή $k$
στην οποία περίπτωση η αξία του συμβολαίου τη χρονική στιγμή $k$ είναι 0 αν $u^j d^{k-j} S_0 < Κ$ και είναι $u^j d^{k-j} S_0 - Κ$ αν η ποσότητα αυτή είναι θετική.
Ας κοιτάξουμε τώρα τη χρονική στιγμή $k-1$. Σε αυτή τη χρονική στιγμή η μετοχή μας μπορεί να έχει μια από τις παρακάτω αξίες $$ u^j d^{k-1-j} S_0, \text{ για } j=0, 1, 2, \ldots, k-1. $$ Θα πρέπει να βρούμε την αξία του συμβολαίου μας σε κάθε μια από αυτές τις περιπτώσεις. Εδώ είναι που θα χρησιμοποιήσουμε τη θεμελιώδη εξίσωση $$ f_0 = e^{-r \tau} \mathbb{E}_p(f_1) $$ που συνάγαμε προηγουμένως, η οποία μας λέει ότι για να βρούμε την αξία του συμβολαίου στην περίπτωση που η αξία της μετοχής μας είναι η $$ u^j d^{k-1-j} S_0 $$ αρκεί να πάρουμε τη μέση τιμή (πάντα με $p=\frac{e^{r\tau}-d}{u-d}$) των δύο διαδοχικών καταστάσεων δηλ. των αξιών $$ u^j d^{k-j} S_0 \text{ και } u^{j+1}d^{k-1-j}S_0 $$ κατά τη χρονική στιγμή $k$ (τις οποίες αξίες ήδη ξέρουμε). Έτσι λοιπόν μεταφέρουμε τις αξίες του συμβολαίου από τη χρονική στιγμή $k$ στη χρονική στιγμή $k-1$, σε κάθε μια από τις δυνατές περιπτώσεις τιμής της μετοχής. Συνεχίζονται κατ' αυτόν τον τρόπο καταλήγουμε να βρούμε την τιμή του συμβολαίου μας στη χρονική στιγμή 0 που είναι και το ζητούμενο.