קריפטאנליזה לינארית

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

היסטוריה[עריכת קוד מקור | עריכה]

פיתוח הקריפטואנליזה הלינארית מיוחס לקריפטוגרף היפני מיטסורו מאטסוי שתקף באמצעותה בשנת 1992 את צופן FEAL. בשנת 1993 פרסם מאטסוי התקפה על צופן DES שהייתה הבסיס להתקפה הפומבית הראשונה על הצופן. התקפה זו מסוג התקפת גלוי-ידוע דורשת אחסון של \ 2^{43} זוגות של טקסט גלוי וטקסט מוצפן מתאים ולכן אינה נחשבת מעשית. מאז פורסמה הפכה השיטה לפופולרית בקרב מנתחי צפנים ועברה שיפורים רבים. כיום השיטה נחשבת לאחת משתי השיטות הפופולריות לתקיפת צפנים יחד עם הקריפטאנליזה הדיפרנציאלית וצפנים מודרניים נדרשים להוכיח עמידות ביחס אליה כתנאי בסיסי לבטיחותם. חשוב להבין כי שיטה תאורטית ל"פיצוח" צופן הוא כל אלגוריתם שמגלה את המפתח בפחות מהזמן הדרוש לכח גס. מבחינה מעשית, ייתכן שגם ביצוע של התקפה זו, למרות יעילותה היחסית לעומת כח גס, ייקח מאות רבות של שנים והיא אינה נחשבת מעשית.

שיטה[עריכת קוד מקור | עריכה]

שימוש בקריפטאנליזה לינארית מורכב משני שלבים. בשלב הראשון מחפש התוקף קירוב לינארי בין הטקסט הגלוי, הטקסט המוצפן והמפתח בעל הטייה (Bias) גבוהה ככל האפשר‏[1]. לאחר שנמצא קירוב לינארי מספק, מציב התוקף במשוואה זוגות ידועים של (טקסט גלוי, טקסט מוצפן) כדי לחשב מתוכם חלקים מתוך המפתח. בהתאם לטיב הקירוב \ k יש להציב 2^k זוגות כאלה.

לצורך קריפטאנליזה לינארית, משוואה לינארית מוגדרת כשוויון בין ביטויים המורכבים ממשתנים בינאריים ופעולת XOR. למשל אם פעולת XOR בין הסיבית ראשונה והשלישית בטקסט הגלוי והסיבית הראשונה בצופן שווה לסיבית השנייה של המפתח הרי שמתקבל: \ P_1\oplus P_3\oplus C_1=K_2. בצופן אידאלי משוואה לינארית מסוג זה שתבטא קשר בין סיביות מסוימות של הטקסט הגלוי, הצופן והמפתח תהיה נכונה במחצית מן המקרים. ביטוי שכזה, המתקיים בהסתברות מסוימת מכונה קירוב לינארי, ומספר הפעמים שהביטוי נכון הוא ההסתברות שלו. ככל שהסטייה מהסתברות של חצי תהיה גדולה יותר, כלומר ההסתברות קרובה לאפס או אחד, כן יגדלו הסיכויים שהערכים שנבחרו נכונים. הרעיון הוא למצוא משוואות לינאריות שהסתברותן רחוקה מחצי ככל האפשר.

האופן בו מתאימים קירובים לינאריים משתנה בהתאם לסוג הצופן. קל לייצג בצורה לינארית פעולות כגון הזזה וXOR אך פעולות חישוב באמצעות S-Box וחשבון מודולרי לא ניתן לייצג באמצעות משוואה לינארית ולכן יש למצוא להן קירוב. השיטה המקובלת היא לחשב את כל הקירובים האפשריים לכל פעולה שאינה לינארית ואז לבחור את הקירוב בעל ההסתברות הטובה ביותר. בצופן בלוקים בדרך כלל מתמקדים בתיבות ההחלפה (S-box) כיוון שזו הפעולה היחידה שאינה לינארית (כלומר לא ניתן לייצגה על ידי ביטוי לינארי מצורה כלשהי). לאחר מציאת הקירובים הטובים ביותר עבור הפעולות הלא-לינאריות מחשבים את ההסתברות הכוללת של כולן ואת השפעת הפעולות הלינאריות על הקירוב כדי למצוא קירוב המייצג את הצופן כולו.

לאחר שנמצא קירוב לינארי מספק מהצורה: 
P_{i_1} \oplus P_{i_2} \oplus \cdots \oplus C_{j_1} \oplus C_{j_2} \oplus \cdots = K_{k_1} \oplus K_{k_2} \oplus \cdots

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

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


הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ מכיוון שבצופן אידאלי ההסתברות לערך כלשהו בסיבית הפלט הוא בדיוק \frac{1}{2}. הטיה גבוהה ככל האפשר משמעותה שההסתברות לנכונות הקירוב קרובה ככל האפשר ל-0 או ל-1.