• בלוג
  • איך לזהות הודעה באנגלית תקנית

איך לזהות הודעה באנגלית תקנית

08/09/2023

שאלה 59 בפרויקט אוילר מציגה את האתגר הבא - נתונה הודעה מוצפנת במפתח הצפנה המורכב מ-3 אותיות קטנות בלבד, והמשימה שלנו היא למצוא את הטקסט המקורי.

ברור שבמספרים כל כך קטנים אפשר להריץ בקלות חיפוש Brute Force על כל האפשרויות למפתח ולמצוא את התשובה. האתגר היותר גדול הוא לזהות איזה אפשרות היא נכונה כלומר לזהות מתי ההודעה המפוצחת היא אכן ההודעה המקורית.

הניסיון הראשון שלי (שנכשל) היה לחפש הודעות שמורכבות רק מאותיות. זה נכשל כי ההודעה המקורית כללה גם מספרים ותווים מיוחדים.

בסופו של דבר נזכרתי שיש לי רשימה של כל המילים באנגלית ממש אצלי על המחשב, וגם אצלכם, בקובץ /usr/share/dict/words. משם הדרך היתה קצרה לחיפוש הודעות בהן לפחות 40% מהמילים הן מילים חוקיות באנגלית מה שהוביל להודעה הנכונה. הפיתרון המלא בפייתון היה:

from pathlib import Path
import string
import sys
from itertools import cycle

english_words = set([c.removesuffix('\n').lower() for c in Path('/usr/share/dict/words').open().readlines()])
message = [int(i) for i in Path('./0059_cipher.txt').open().read().split(',')]
key = [97, 98, 99]

def decrypt(message, key):
   return ''.join([chr(i) for i in [p[0] ^ p[1] for p in zip(message, cycle(key))]])

for i in range(ord('a'), ord('z') + 1):
    for j in range(ord('a'), ord('z') + 1):
        for k in range(ord('a'), ord('z') + 1):
            key = [i, j, k]
            plaintext = decrypt(message, key)
            words = plaintext.split()
            valid_words = [w for w in plaintext.split() if w in english_words]
            if len(valid_words) / len(words) > 0.4:
                print(plaintext)
                print(sum(ord(ch) for ch in plaintext))