קריפטואנליזה ליניארית
תיאור כללי > תיבות ההחלפה

במרבית הצפנים כמו DES ו-AES, כל הפעולות למעט תיבות ההחלפה הן פעולות ליניאריות ולכן מספיק לייצג את פעולות תיבות ההחלפה כמשוואה ליניארית כדי לפצח את הצופן. בהינתן תיבת החלפה כמו בדוגמה לעיל, המקבלת 4 סיביות  X=[X_{1}X_{2}X_{3}X_{4}] ומחזירה ארבע סיביות  Y=[Y_{1}Y_{2}Y_{3}Y_{4}]. קל יותר לגלות קירובים ליניאריים על ידי חישוב ההטיה של כל תיבה בנפרד. למשל אם לוקחים את הביטוי  X_{2}\oplus X_{3}\oplus Y_{1}\oplus Y_{3}\oplus Y_{4}=0 או לחלופין  X_{2}\oplus X_{3}=Y_{1}\oplus Y_{3}\oplus Y_{4}, מנסים את כל 16 האפשרויות של  X ובודקים את התוצאות  Y המתקבלות מתיבת ההחלפה, מגלים שב-12 מתוך 16 המקרים המשוואה האמורה מתקיימת, כלומר בהסתברות של  12/16-1/2=1/4. דוגמה אחרת, עם הביטוי  X_{1}\oplus X_{4}=Y_{2} מתקבלת הטיה של אפס וכן עם המשוואה  X_{3}\oplus X_{4}=Y_{1}\oplus Y_{4} ההסתברות היא  2/16-1/2=-3/8 שזהו קירוב אפיני (בגלל סימן המינוס). היות שההתקפה הליניארית מסתמכת על שיעור ההטיה אין חשיבות לסימן וההתקפה תצליח במידה שווה במקרה של קירוב ליניארי או אפיני (מלמעלה או מלמטה). את כל 16 האפשרויות של הצירופים הליניאריים של כל המשוואות האפשריות, אפשר לסכם בטבלה. על בסיס טבלה הזו מגלים את כל הקירובים הליניאריים/אפיניים של תיבת ההחלפה ומסכמים אותם בטבלה אחרת הנקראת טבלת קירוב ליניארי, לדוגמה כך נראית הטבלה עבור תיבת ההחלפה שנבחרה לצורך הדוגמה:
|  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | +8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | -2 | -2 | 0 | 0 | -2 | +6 | +2 | +2 | 0 | 0 | +2 | +2 | 0 | 0 |
| 2 | 0 | 0 | -2 | -2 | 0 | 0 | -2 | -2 | 0 | 0 | +2 | +2 | 0 | 0 | -6 | +2 |
| 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | +2 | -6 | -2 | -2 | +2 | +2 | -2 | -2 |
| 4 | 0 | +2 | 0 | -2 | -2 | -4 | -2 | 0 | 0 | -2 | 0 | +2 | +2 | -4 | +2 | 0 |
| 5 | 0 | -2 | -2 | 0 | -2 | 0 | +4 | +2 | -2 | 0 | -4 | +2 | 0 | -2 | -2 | 0 |
| 6 | 0 | +2 | -2 | +4 | +2 | 0 | 0 | +2 | 0 | -2 | +2 | +4 | -2 | 0 | 0 | -2 |
| 7 | 0 | -2 | 0 | +2 | +2 | -4 | +2 | 0 | -2 | 0 | +2 | 0 | +4 | +2 | 0 | +2 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -2 | +2 | +2 | -2 | +2 | -2 | -2 | -6 |
| 9 | 0 | 0 | -2 | -2 | 0 | 0 | -2 | -2 | -4 | 0 | -2 | +2 | 0 | +4 | +2 | -2 |
| A | 0 | +4 | -2 | +2 | -4 | 0 | +2 | -2 | +2 | +2 | 0 | 0 | +2 | +2 | 0 | 0 |
| B | 0 | +4 | 0 | -4 | +4 | 0 | +4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | -2 | +4 | -2 | -2 | 0 | +2 | 0 | +2 | 0 | +2 | +4 | 0 | +2 | 0 | -2 |
| D | 0 | +2 | +2 | 0 | -2 | +4 | 0 | +2 | -4 | -2 | +2 | 0 | +2 | 0 | 0 | +2 |
| E | 0 | +2 | +2 | 0 | -2 | -4 | 0 | +2 | -2 | 0 | 0 | -2 | -4 | +2 | -2 | 0 |
| F | 0 | -2 | -4 | -2 | -2 | 0 | +2 | 0 | 0 | -2 | +4 | -2 | -2 | 0 | +2 | 0 |
כל כניסה בטבלה מייצגת בבסיס הקסדצימלי, את מספר הפעמים שנמצאה התאמה בין המשוואה הליניארית של קלט תיבת ההחלפה לבין סכום סיביות הפלט שלה פחות 8. לכן אם מחלקים את הערך בכניסה כלשהי ב-16 מתקבלת ההטיה ההסתברותית של הצירוף הליניארי המתאים. הערך של אינדקס כל כניסה מגדיר את המשתנים המקריים הנכללים במשוואה בצורה של צירוף ליניארי מהצורה  a_{1}\cdot X_{1}\oplus a_{2}\cdot X_{2}\oplus a_{3}\cdot X_{3}\oplus a_{4}\cdot X_{4} כאשר  a_{i}\in \{0,1\} והסימן  \cdot  מייצגת פעולת AND. לכן הערך בבסיס הקסדצימלי הוא  a_{1}a_{2}a_{3}a_{4} כאשר  a_{1} הוא הסיבית המשמעותית ביותר. מזה אפשר לראות שההטיה של המשוואה הליניארית  X_{3}\oplus X_{4}=Y_{1}\oplus Y_{4} (בשורה הרביעית בעמודה העשירית) היא  -6/16=-3/8 וההסתברות שהמשוואה הליניארית תתקיים היא  1/2-3/8=1/8. מהתבוננות בטבלה אפשר לשים לב שההסתברות שכל סכום של סיביות פלט שווה לערך שאין בו סיביות מהקלט הוא בדיוק חצי, זאת בגלל שתיבת ההחלפה היא פונקציה חד ערכית ועל וכל צירוף ליניארי מחייב שיהיה מספר שווה של סיביות אפס ואחד. באותה מידה ההסתברות של כל צירוף ליניארי שאין בו סיביות פלט היא בדיוק  +1/2(בטבלה היא  +8), לכן השורה העליונה בטבלה כולה מאופסת למעט בכניסה השמאלית ביותר וכן לגבי העמודה הראשונה.