بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 19: فرکانس حروف Letter Frequency

در هر زبان بعضی حرف‌ها بیشتر از بقیه می‌آیند. با Counter حرف‌ها را می‌شماریم و از ترتیب فرکانس انگلیسی (etaoinshrdlu) برای شکستن رمز سزار و حتی رمز جانشینی استفاده می‌کنیم.

در این جلسه یاد می‌گیری

درس

⚠️ شکستن رمز را فقط روی پیام‌های خودت یا نمونه‌هایی که معلم داده تمرین کن. خواندن پیام رمزی دیگران بدون اجازه، حتی اگر بتوانی، جرم است. اینجا با متن‌های تمرینی کار می‌کنیم تا ببینیم چرا رمزهای ساده شکستنی‌اند.

در متن انگلیسی حرف e از همه بیشتر می‌آید، بعد t, a, o و... . این یک «اثر انگشت» برای زبان است. اگر یک متن رمزی داشته باشیم، پرتکرارترین حرفش احتمالاً همان e رمزشده است.

Counter از ماژول collections هر چیز را می‌شمارد. most_common(1) پرتکرارترین را می‌دهد. برای شمردن فقط حرف‌ها، بقیه را رد می‌کنیم.

from collections import Counter

text = "hello world"
counts = Counter(c for c in text if c.isalpha())
print(counts.most_common(1))   # [('l', 3)]
print(counts["o"])             # 2

ترتیب تقریبی فرکانس انگلیسی را به خاطر بسپار: etaoinshrdlu. این رشته از پرتکرار به کم‌تکرار مرتب است و برای حدس زدن خیلی کمک می‌کند.

ORDER = "etaoinshrdlu"
print(ORDER[0])   # e  (most common)
print(ORDER[1])   # t

رمز سزار هر حرف را به اندازه‌ی یک «شیفت» جلو می‌برد. برای باز کردن با شیفت معلوم، همان اندازه عقب می‌رویم. از ord و chr و % 26 استفاده می‌کنیم تا در دایره‌ی الفبا بمانیم.

def shift(text, n):
    out = ""
    for c in text:
        out += chr((ord(c) - 97 + n) % 26 + 97)
    return out


print(shift("khoor", -3))   # hello

برای شکستن سزار وقتی شیفت را نمی‌دانیم: پرتکرارترین حرف متن را پیدا می‌کنیم، فرض می‌کنیم آن e است، و اختلافش با e همان شیفت است. بعد با آن شیفت کل متن را باز می‌کنیم.

from collections import Counter

ct = "khoor zruog"
top = Counter(c for c in ct if c.isalpha()).most_common(1)[0][0]
shift_amount = (ord(top) - ord("e")) % 26
print(shift_amount)   # the guessed shift

رمز جانشینی سخت‌تر است: هر حرف به یک حرف دلخواه نگاشت می‌شود. با فرکانس می‌توانیم چند حرف پرتکرار را حدس بزنیم و بقیه را از روی کلمات بسازیم. این «باز کردن ناقص» است، اما شروع خوبی است.

mapping = {"x": "h", "q": "e", "z": "l", "p": "o"}
ct = "xqzzp"
plain = "".join(mapping.get(c, "?") for c in ct)
print(plain)   # hello

اشتباه‌های رایج: (۱) شمردن فاصله و علامت‌ها همراه حرف‌ها — فقط c.isalpha() را بشمار. (۲) فراموش کردن % 26 در سزار و بیرون زدن از الفبا. (۳) اعتماد صددرصد به فرکانس در متن‌های کوتاه؛ در متن کوتاه ممکن است پرتکرارترین حرف e نباشد.

مثال‌های این جلسه

چالش‌ها

  1. Most Common Letter (آسان)
  2. Count One Letter (آسان)
  3. Frequency Order (متوسط)
  4. Caesar Decrypt (متوسط)
  5. Break the Caesar (سخت)
  6. Partial Substitution (سخت)
  7. Most Common Letter (متوسط)
  8. Top Three Letters (سخت)

بیشتر بخوان

← جلسه‌ی 18: رمزنگاری متقارن با پایتون جلسه‌ی 20: پروژه: رمزشکن خودکار →