לצורך המחשת הקריפטואנליזה הליניארית, נניח שנתון צופן בלוקים פשוט המורכב מרשת החלפה-תמורה. הוא מקבל בלוק קלט באורך 16 סיבות (שני בתים), מעבד את הבלוק על ידי חזרה ארבע פעמים על פונקציה פנימית הכוללת בדומה ל-AES, שלוש שכבות; החלפה, תמורה וערבוב מפתח, כמתואר בתרשים משמאל. למרות שהצופן פשוט והוא מובא כאן להמחשה בלבד, ההתקפה הליניארית על צופן זה מספקת תובנה די טובה לגבי פעולתה נגד צפנים מודרניים מורכבים יותר.
לצורך הדיון נניח ששלב ההחלפה בצופן הצעצוע האמור כולל ארבע תיבות החלפה המקבלות 4 סיביות ומחזירות 4 סיביות. כל תיבת החלפה אפשר ליישם באמצעות טבלה פשוטה המכילה 16 ערכים באורך 4 סיביות כל אחד. הערך המוחזר הוא בעצם תוכן הכניסה שהקלט מייצג את מספרה. ברוב הצפנים קיימות מספר טבלאות, לצורך הפשטות נניח שקיימת רק תיבה אחת כזו שבה משתמשים ארבע פעמים בכל סבב. להלן הטבלה הלקוחה מצופן DES בייצוג הקסדצימלי:
לצורך שלב הטרנספוזיציה (תמורה) נתונה הטבלה הבאה. פעולת הטרנספוזיציה ניתנת לתיאור באופן הבא: הפלט בפוזיציה ה-formula_4 של תיבת ההחלפה formula_8 מנותב לכניסה ה-formula_8 של תיבת ההחלפה ה-formula_4 (בסבב הבא). ראוי לציין שאין טעם בטרנספוזיציה בסבב האחרון של הצופן כי היא ניתנת להפיכה בקלות.
שכבת חיבור המפתח מבצעת חיבור XOR של כל סיביות הפלט עם חלק מהמפתח הסודי הנקרא תת-מפתח. חיבור המפתח בסיום הסבב האחרון מבטיח שלא יהיה אפשרי להתעלם מהסבב האחרון כשמנתחים את הצופן. לצורך הפשטות נניח שתת-המפתחות עבור ארבעת הסבבים הוכנו בנפרד זה מזה. פענוח הוא פשוט חזרה לאחור צעד אחרי צעד במבנה זהה להצפנה, רק יש צורך לוודא שתיבות ההחלפה הן פונקציה חד-חד-ערכית ועל ועל כן הן הפיכות וכן צריך להשתמש במפתחות בסדר הפוך.
עקרון הערמה.
מציאת משוואה ליניארית של הצופן מסתמכת על צירוף משוואות ליניאריות של חלקים שונים של הצופן למשוואה ליניארית אחת. החלק הקשה הוא למצוא ולצרף משוואות ליניאריות מתאימות. לצורך ההדגמה נתייחס לצופן הצעצוע המתואר לעיל. אם נתונים שני משתנים מקריים formula_25 ו-formula_26, אז formula_27 הוא ביטוי ליניארי השקול ל-formula_28. אם formula_29 זהו ביטוי אפיני השקול ל-formula_30. נניח שההתפלגות הסטטיסטית נתונה על ידי:
וכן
אם שני המשתנים המקריים בלתי תלויים אפשר לשלב את שניהם ביחד:
וכן אפשר להוכיח ש-
דרך אחרת להציג זאת, יהיו formula_34 וכן formula_35 כאשר formula_36 ו-formula_37 הן שיעור ההטיה ההסתברותיות מחצי כך שמתקיים formula_38 וכן formula_39. מזה נובע ש-formula_40. ההטיה של formula_27 היא formula_42. אפשר להרחיב את האמור ליותר משתנים מקריים formula_25 עד formula_44 עם ההסתברויות formula_34 עד formula_46. ההסתברות ש-formula_47 תתקיים ניתנת לחישוב באמצעות למת הערמה (Piling-Up Lemma) של מיצורו מצואי, בהנחה שכל המשתנים בלתי תלויים:
נתונים formula_6 משתנים מקריים בלתי תלויים: formula_49 מתקיים
או לחלופין
כאשר formula_52 מייצג את ההטיה של formula_47. יש לשים לב שאם formula_54 או formula_55 אז formula_56 או 1 בהתאם. אם רק formula_57 אחד שווה חצי אז formula_58.
כאשר מרכיבים משוואה ליניארית של הצופן המשתנים formula_3 הם בעצם קירוב ליניארי של תיבות ההחלפה. למשל, אם נתונים ארבעה משתנים מקריים formula_60 ו-formula_61 ויהיו formula_62 וכן formula_63, הסכום formula_64 המתקבל על ידי חיבור formula_65 עם formula_66 אז מתקיים:
בדרך זו אפשר לשלב משוואות ליניאריות כדי לקבל משוואה ליניארית חדשה, ואם מניחים שהמשתנים בלתי תלויים אז אפשר להשתמש בלמת הערמה באופן הזה:
כתוצאה מכך formula_69. אפשר לראות שהביטויים formula_27 וכן formula_71 מקבילים לקירובים הליניאריים של שתי תיבות ההחלפה בהתאמה ואילו formula_72 מקביל לקירוב הליניארי של שתיהן יחד. כמובן שבניתוח אמיתי של הצופן מעורבים יותר תיבות החלפה ויותר משתנים מקריים בהתאם.
תיבות ההחלפה.
במרבית הצפנים כמו DES ו-AES, כל הפעולות למעט תיבות ההחלפה הן פעולות ליניאריות ולכן מספיק לייצג את פעולות תיבות ההחלפה כמשוואה ליניארית כדי לפצח את הצופן. בהינתן תיבת החלפה כמו בדוגמה לעיל, המקבלת 4 סיביות formula_73 ומחזירה ארבע סיביות formula_74. קל יותר לגלות קירובים ליניאריים על ידי חישוב ההטיה של כל תיבה בנפרד. למשל אם לוקחים את הביטוי formula_75 או לחלופין formula_76, מנסים את כל 16 האפשרויות של formula_11 ובודקים את התוצאות formula_13 המתקבלות מתיבת ההחלפה, מגלים שב-12 מתוך 16 המקרים המשוואה האמורה מתקיימת, כלומר בהסתברות של formula_79. דוגמה אחרת, עם הביטוי formula_80 מתקבלת הטיה של אפס וכן עם המשוואה formula_81 ההסתברות היא formula_82 שזהו קירוב אפיני (בגלל סימן המינוס). היות שההתקפה הליניארית מסתמכת על שיעור ההטיה אין חשיבות לסימן וההתקפה תצליח במידה שווה במקרה של קירוב ליניארי או אפיני (מלמעלה או מלמטה). את כל 16 האפשרויות של הצירופים הליניאריים של כל המשוואות האפשריות, אפשר לסכם בטבלה. על בסיס טבלה הזו מגלים את כל הקירובים הליניאריים/אפיניים של תיבת ההחלפה ומסכמים אותם בטבלה אחרת הנקראת טבלת קירוב ליניארי, לדוגמה כך נראית הטבלה עבור תיבת ההחלפה שנבחרה לצורך הדוגמה:
כל כניסה בטבלה מייצגת בבסיס הקסדצימלי, את מספר הפעמים שנמצאה התאמה בין המשוואה הליניארית של קלט תיבת ההחלפה לבין סכום סיביות הפלט שלה פחות 8. לכן אם מחלקים את הערך בכניסה כלשהי ב-16 מתקבלת ההטיה ההסתברותית של הצירוף הליניארי המתאים. הערך של אינדקס כל כניסה מגדיר את המשתנים המקריים הנכללים במשוואה בצורה של צירוף ליניארי מהצורה formula_83 כאשר formula_84 והסימן formula_85 מייצגת פעולת AND. לכן הערך בבסיס הקסדצימלי הוא formula_86 כאשר formula_87 הוא הסיבית המשמעותית ביותר. מזה אפשר לראות שההטיה של המשוואה הליניארית formula_81 (בשורה הרביעית בעמודה העשירית) היא formula_89 וההסתברות שהמשוואה הליניארית תתקיים היא formula_90. מהתבוננות בטבלה אפשר לשים לב שההסתברות שכל סכום של סיביות פלט שווה לערך שאין בו סיביות מהקלט הוא בדיוק חצי, זאת בגלל שתיבת ההחלפה היא פונקציה חד ערכית ועל וכל צירוף ליניארי מחייב שיהיה מספר שווה של סיביות אפס ואחד. באותה מידה ההסתברות של כל צירוף ליניארי שאין בו סיביות פלט היא בדיוק formula_91(בטבלה היא formula_92), לכן השורה העליונה בטבלה כולה מאופסת למעט בכניסה השמאלית ביותר וכן לגבי העמודה הראשונה.
קירוב ליניארי של כל הצופן.
בהינתן הקירובים הלנאריים של כל תיבות ההחלפה של הצופן, קיים מספיק מידע כדי לחשב את הקירוב הליניארי של הצופן בשלמותו. את זה אפשר לבצע על ידי צירוף מספר קירובים מתאימים מתיבות ההחלפה. עם מידע זה אפשר לחלץ סיביות מהמפתח הסודי ששימש בסבב האחרון של הצופן. לדוגמה, בתרשים משמאל מתואר קירוב לנארי של צופן הצעצוע להמחשה בתיבות formula_93 ו-formula_94 כאשר הספרה הראשונה באינדקס התיבה מציינת את מספר הסבב ואילו השנייה את מספר התיבה (שזה התיבה השנייה בסבב הראשון, השנייה בסבב השני והתיבות השנייה והרביעית בסבב השלישי). יש לשים לב שהקירוב האמור אינו כולל את כל הצופן אלא רק שלושה סבבים ממנו, זה כל מה שדרוש להתקפה. לאחר בחינה של התרשים וטבלת הקירובים, מתקבלים הקירובים הבאים:
formula_104 בהסתברות formula_99 והטיה formula_100
יהיו formula_107 ו-formula_108 בלוק הקלט ובלוק הפלט בהתאמה של תיבות ההחלפה של הצופן בסבב ה-formula_4. וכן formula_110 ו-formula_111 הסיבית ה-formula_8 של בלוק הקלט או הפלט בהתאמה, בסבב ה-formula_4. באותו אופן formula_114 מייצג את המפתח המחובר ב-XOR עם בלוק הנתונים בסבב ה-formula_4 כאשר formula_116 הוא המפתח שמחובר לאחר הסבב הרביעי וכן formula_117 מתייחס לסיבית במיקום ה-formula_8 של המפתח ה-formula_4. לכן בשלב הראשון של הצופן מתקבל: formula_120. כאשר formula_121 הוא בלוק הקלט הגלוי או המסר המיועד להצפנה, באורך 16 סיביות. על בסיס הקירוב הליניארי של הסבב הראשון של הצופן, המשוואה הליניארית הבאה:
מתקיימת בהסתברות formula_122. וכן עבור הסבב השני, הצירוף הבא
מתקיים בהסתברות formula_124. היות שפלט הסבב הראשון הוא בעצם קלט הסבב השני המחובר עם המפתח המתאים, מתקבל formula_125 לכן אפשר לקבל קירוב ליניארי מהצורה:
בהסתברות 1/4. לפי "למת הערמה" של מצואי, אם משלבים יחד את הצירופים משני הסבבים הראשונים מתקבלת המשוואה:
שמתקיימת בהסתברות ש/ל formula_128 עם הטיה formula_129. למרות שהיא מתבססת על ההנחה שהקירובים הליניאריים של כל סבב בלתי תלויים שהיא הנחה לא מדויקת, בפועל היא עובדת היטב. עבור הסבב השלישי אפשר להבחין ש:
היות שמתקיים formula_134 וכן formula_135 מתקבלת המשוואה הבאה:
בהסתברות של formula_137 (עם הטיה formula_129). כעת אפשר לשלב את הצירופים מכל הסבבים (לפי עקרון הערמה) ולקבל את:
אפשר לפשט את המשוואה. היות שבעצם formula_140 וכן formula_141, אפשר לשכתב את המשוואה האמורה כך:
כאשר formula_143 כולל את כל סיביות המפתח המשתתפות (שמיקומן ידוע):
ההסתברות שהמשוואה האחרונה תתקיים היא formula_145 עם הטיה -formula_146 והיא הקירוב הליניארי של הצופן.
היות ש-formula_143 קבוע בהתאם למפתח הסודי המשוואה הבאה: