מבוא לקריפטוגרפיה ב-CTF, RSA כשער כניסה

בכל אתגרי CTF יש קטגוריית Crypto, ובכל קטגוריית Crypto, RSA הוא כמעט תמיד האלגוריתם הראשון שפוגשים. הסיבה פשוטה - RSA הוא בו זמנית אחד השיטות הכי חשובות בעולם ההצפנה האמיתי, ואחד הכי קל ללמד דרכו איך מתקפות קריפטוגרפיות בכלל עובדות, כי הבסיס המתמטי שלו נגיש יחסית.

הרעיון הבסיסי מאחורי RSA

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

המפתח הציבורי מורכב משני ערכים - n (המכפלה של שני הראשוניים) ו-e (מעריך קבוע, לרוב 65537). המפתח הפרטי הוא d, שמחושב באמצעות ידיעת שני הראשוניים המקוריים, p ו-q. מי שיודע לפרק את n בחזרה ל-p ו-q יכול לחשב את d בעצמו, ולפענח כל הודעה שהוצפנה עם המפתח הציבורי.

למה אתגרי CTF ב-RSA בכלל פתירים

RSA "האמיתי", עם מפתחות בגודל תקני (2048 סיביות ומעלה) ומימוש נכון, בלתי אפשרי לשבור עם הידע והחומרה הזמינים היום. אתגרי CTF לא מנסים לשבור RSA תקני - הם בונים תרחיש שבו יש טעות מימוש ספציפית, וזו המשימה שלכם, לזהות את הטעות ולנצל אותה. כמה טעויות קלאסיות שכדאי להכיר:

• n קטן מדי או ניתן לפירוק בקלות. אם המימוש בחר ראשוניים קטנים מדי, אפשר פשוט לפרק את n בכלים סטנדרטיים (למשל FactorDB או Pollard's rho) ולחשב את d ישירות.
• מעריך e קטן מדי בשילוב הודעה קצרה. אם e שווה 3 וההודעה עצמה קצרה מספיק כך שהחזקה שלה בחזקת e לא "עוטפת" את n, אפשר לפעמים לחשב שורש שלישי רגיל ולקבל את ההודעה המקורית בלי לגעת בהצפנה בכלל.
• שימוש חוזר במודולוס משותף. אם שני הודעות שונות מוצפנות עם אותו n אבל מעריכים e שונים, יש התקפה מתמטית ידועה (Common Modulus Attack) שמאפשרת לשחזר את ההודעה המקורית בלי לפרק את n בכלל.
• ראשוניים קרובים מדי זה לזה. אם p ו-q נבחרו בקירוב מדי, יש שיטה (Fermat's factorization) שמפרקת את n הרבה יותר מהר מפירוק רגיל.
• מפתחות פרטיים חלשים - Wiener's Attack. אם d נבחר קטן מדי במכוון או בטעות, קיימת שיטה מתמטית שמאפשרת לשחזר אותו במהירות, גם בלי לפרק את n.

כל אחת מהטעויות האלה היא לא פגם באלגוריתם RSA עצמו, אלא בבחירת פרמטרים לא זהירה בזמן המימוש.

איך בפועל ניגשים לאתגר RSA

הצעד הראשון תמיד הוא לזהות בדיוק אילו ערכים קיבלתם - n, e, ולפעמים גם הצפנה של הודעה. אחר כך בודקים אם n קטן מספיק לפירוק ישיר, מנסים לזהות אם יש שימוש חוזר במודולוס, ובודקים את גודל e. ספריות פייתון כמו pycryptodome, יחד עם כלים ייעודיים לפתרון אתגרי RSA כמו RsaCtfTool, מייעלים מאוד את התהליך של ניסוי כמה טכניקות מוכרות במהירות על אותו סט נתונים.

למה זה שווה ללמוד

RSA הוא מבוא מצוין לחשיבה קריפטוגרפית - במקום לחפש חולשה בקוד או בזיכרון, מחפשים חולשה מתמטית בבחירת פרמטרים. זו זווית ראייה שונה לגמרי מעולם הניצול הבינארי, אבל היא חלק חשוב לא פחות מעולם מחקר החולשות הרחב.

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

תקועים על אתגר RSA ולא בטוחים איזו טעות מימוש מסתתרת שם? בדיסקורד שלנו יש אנשים שאוהבים בדיוק את החידות האלה.

הצטרפו לקהילה בדיסקורד

לסיכום

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