קריפטואנליזה ליניארית – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שורה 203:
לאחר שהתגלה הקירוב הלינארי הכולל של <math>R-1</math> מתוך <math>R</math> הסבבים של הצופן, עם הטייה הסתברותית משמעותית, עוברים לשלב ניחוש סיביות תת-המפתח האחרון על ידי חישוב לאחור. ביתר פירוט, תחילה מנסים את כל האפשרויות של המפתח האחרון (<math>K_5</math> במקרה זה) ומחברים אותם ב-XOR עם הבלוק המוצפן, ואז מבצעים פענוח חלקי (העברה בתיבות ההחלפה של הסבב האחרון) של הבלוק שהתקבל. פעולה זו מתבצעת עבור כל זוגות הבלוקים גלויים/מוצפנים שנמצאים בידי המתקיף. שומרים מונה שמקודם בכל פעם שהתקבל ערך המקיים את הצירוף הלינארי של התיבות מהסבב האחרון (יש לזכור שהבלוק הגלוי ידוע). כל ניחוש סיביות מפתח שהמונה שלו גבוה או נמוך ממחצית מזוגות הקלט/פלט שבידי המתקיף בשיעור משמעותי הדבר נחשב לניחוש מוצלח. ניחוש לא נכון אמור לתת תוצאה אקראית ולכן המשוואה האמורה תתקיים בהסבתרות קרובה לחצי.
 
בצופן הצעצוע המובא להמחשה, הצירוף הלינארי האחרון משפיע על הפלט לתיבות <math>S_{42}</math> ו-<math>S_{44}</math> של הסבב האחרון. כיוון שכל תיבה מכילה 4 סיביות בסך הכול 8 זה אומר שעבור כל זוג קלט/פלט מנסים את כל 256 צירופי סיביות של קטעי המפתח <math>[K_{5,5}...K_{5,8},K_{5,13}...K_{5,16}]</math> (יתר סיביות המפתח אינן משפיעות כי שתי תיבות אילו היות התיבות הפעילות היחידות בסבב זה). עבור כל ניחוש מפתח חלקי כזה, מקדמים מונה כלשהו אם המשוואה האחרונה התקיימה. הזוגות שלהם המונה הגבוה ביותר (שלילי או חיובי) מרמזות על ניחוש מוצלח בהסתברות גבוהה. המשוואה האחרונה (הצירוף הלינארי של הצופן) משפיעה על התוצאה בהתאם למפתח. אם ערכן של סיביות המפתח בפוזיציות הללו הוא <math>\textstyle\sum_K=0</math> אז המשואה תתקיים בהסתברות גבוהה מחצי ואילו אם <math>\textstyle\sum_K=1</math> המשוואה תתקיים בהסתברות נמוכה מחצי. את צופן הצעצוע המתואר אפשר לתקוף עם 10,000 זוגות קלט/פלט ידועים, ולפי תיאור ההתקפה עד כה, התגלה ניחוש מוצלח של סיביות תת-המפתח <math>[K_{5,5}...K_{5,8}]=[0010]</math> וכן <math>[K_{5,13}...K_{5,16}]=[0100]</math>. ואכן המונה עבור סיביות אילו <math>[2,4]</math> בבסיס הקסדצימלי כצפוי היה גבוה משמעותית מ-5,000. הטבלה הבאה מכילה להמחשה, אוסף חלקי מתוך 256 האפשרויות. ערכים אילו מייצגים את שיעור ההטייה לפי החשבון האמור, "הטייה = מונה פחות חצי חלקי מספר כל הזוגות". כאשר המונה מתייחס לניחוש מסויים של 8 סיביות מהמפתח. אפשר לראות שההטייה הגבוהה ביותר מופיעה כאשר הניחוש הוא 2,4.
 
{| class="wikitable"