כתיבת קוד — שיעור 47

תרגול CTF טקטי

כל 4 משימות הקוד שנשמרו מהשיעור מופיעות כאן, עם דרישות, דוגמאות וקוד פתיחה. אפשר לכתוב פתרון בעורך המקומי וללחוץ על „בדיקת AI” לקבלת ציון, רמזים והערות.

T5 · שיא800 נק'~15 דק'algorithmic⏱ בונוס-זמן

Crypto — פיצוח RSA (מודולוס קטן)

אתגר קריפטו קלאסי של CTF. נתונים n (מכפלת שני ראשוניים קטנים), e, ו-ciphertext c. שחזר את ה-plaintext m: פרק את n, חשב phi=(p-1)(q-1), מצא d=e⁻¹ mod phi, והחזר m=c^d mod n.

דוגמאות

rsa_decrypt(3233, 17, pow(42,17,3233)) → 42

פתרון-ייחוס Crypto — פיצוח RSA (מודולוס קטן) ›

def rsa_decrypt(n: int, e: int, c: int) -> int:
    f = 2; p = None                       # פירוק n (מודולוס קטן)
    while f * f <= n:
        if n % f == 0: p = f; break
        f += 1
    q = n // p
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)                    # d = e^-1 mod phi
    return pow(c, d, n)                    # m = c^d mod n

הפתרון שלךהפתרון נשמר מקומית אוטומטית.

T5 · שיא800 נק'~15 דק'algorithmic⏱ בונוס-זמן

Forensics — ציד flag ב-XOR

blob של בתים (רשימת ints) מכיל flag שהוצפן ב-XOR עם מפתח בית-יחיד ומוסתר ברעש. ממש find_flag(data) שמנסה את כל 256 המפתחות, מפענח, ומחזיר את המחרוזת בפורמט flag{...} שמופיעה. אם אין — None.

דוגמאות

find_flag(blob) # blob = flag{...} ^ key ברעש → 'flag{f0r3ns1cs}'

פתרון-ייחוס Forensics — ציד flag ב-XOR ›

import re
def find_flag(data: list) -> str:
    for k in range(256):                          # brute כל 256 המפתחות
        dec = bytes(b ^ k for b in data)
        m = re.search(rb'flag\{[ -~]*?\}', dec)  # flag{...} מודפס
        if m: return m.group().decode()
    return None

הפתרון שלךהפתרון נשמר מקומית אוטומטית.

T5 · שיא800 נק'~15 דק'algorithmic⏱ בונוס-זמן

Reverse — היפוך בדיקת Serial

פונקציית check ששוחזרה מ-disassembly בודקת: (ord(s[i]) ^ 0x2a) + i == target[i] לכל i. נתון target — ממש solve(target) שמחזיר את ה-serial (המחרוזת s) שעובר את הבדיקה.

דוגמאות

solve(target) # target שנגזר מ-'c7f2' → 'c7f2'

פתרון-ייחוס Reverse — היפוך בדיקת Serial ›

def solve(target: list) -> str:
    # ה-check: (ord(s[i]) ^ 0x2a) + i == target[i]
    # היפוך:  ord(s[i]) = (target[i] - i) ^ 0x2a
    return ''.join(chr((target[i] - i) ^ 0x2a) for i in range(len(target)))

הפתרון שלךהפתרון נשמר מקומית אוטומטית.

T5 · שיא800 נק'~20 דק'algorithmic⏱ בונוס-זמן

Algo — תת-סדרה עולה ארוכה ביותר

מצא את אורך תת-הסדרה העולה-ממש הארוכה ביותר (LIS) ברשימת מספרים. חובה O(n log n) (patience sorting עם חיפוש בינארי): קלט של 200,000 איברים חייב לרוץ בזמן. פתרון DP של O(n²) ייפסל ב-timeout.

דוגמאות

lis_length([10,9,2,5,3,7,101,18]) → 4

lis_length([3,3,3]) → 1

פתרון-ייחוס Algo — תת-סדרה עולה ארוכה ביותר ›

import bisect
def lis_length(nums: list) -> int:
    tails = []                            # patience sorting — O(n log n)
    for x in nums:
        i = bisect.bisect_left(tails, x)  # מיקום להחלפה (עולה ממש)
        if i == len(tails): tails.append(x)
        else: tails[i] = x
    return len(tails)

הפתרון שלךהפתרון נשמר מקומית אוטומטית.