FEAL

בקריפטוגרפיה, FEAL (ראשי תיבות של Fast data Encipherment ALgorithm, בעברית: אלגוריתם הצפנת נתונים מהיר) כולל משפחה של צפני בלוקים במבנה פייסטל שהראשון שבהם הוצע כאלטרנטיבה לצופן DES והוא מהיר ממנו בתוכנה. הגרסה הראשונה פותחה ב-1987 על ידי אקירו שימיזו ושוי מיאגוטשי מתאגיד הטלגרף והטלפון של יפן (NTT)^[1]. ב-1994 התקבל הצופן לתקן בינלאומי ISO/IEC9979 וב-1999 נבחר לתקן ATM וכן נכלל בתקן יפני לכרטיסים חכמים ב-1998. בשל קריפטואנליזה שמעידה על חולשות הצופן אינו בשימוש כיום. NTT ממליצים להשתמש בצופן מדור חדש כמו קמליה.

קיימות מספר גרסאות של FEAL כולן במבנה פייסטל עם אותה פונקציית סבב פנימית אך עם מספר סבבים שונה או עם מפתח גדול יותר. הצופן מקבל בלוק קלט באורך 64 סיביות ומחזיר בלוק מוצפן באורך 64 סיביות. הגרסה הראשונה שכיום נקראת FEAL-4 משתמשת במפתח הצפנה באורך 64 סיביות וכוללת ארבעה סבבים של הפונקציה הפנימית. FEAL-8 מכיל שמונה סבבים עם אותו מפתח ואילו FEAL-NX מכילה מספר דינאמי של סבבים בהתאם לצורך כך ש- $N\geq 8$ . (המספר המומלץ הוא $N=32$ ) ואילו "X" מתייחס לאופציה של מפתח באורך 128 סיביות שנוספה בגרסה המאוחרת יותר.

בטחון

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

בתחילה התגלו בעיות בגרסה הראשונה של הצופן על ידי דן בואר ושון מרפי שגילו התקפות קריפוטאנליטיות הדורשות כמות מועטה של טקסטים גלויים נבחרים כדי לפצח את הצופן בקלות^[2]^[3]. ההתקפות שלהם מכילות אלמנטים דומים להתקפה הדיפרנציאלית שהתגלתה מאוחר יותר. ב-1998 ניסו מפתחי הצופן לפתור את הבעיה על ידי העלאת מספר הסבבים וכך נוצר FEAL-8 הכולל שמונה סבבים במקום ארבעה.

ב-1991 פרסמו אלי ביהם ועדי שמיר את ההתקפה הדיפרנציאלית שלהם על FEAL-8^[4]. אחריהם פורסמו עוד כמה התקפות מסוג זה שמצליחות לפצח את הצופן עם כמות יחסית קטנה של טקסטים גלויים נבחרים. בתגובה פותח FEAL-NX אך הסתבר שההתקפה הדיפרנציאלית של שמיר וביהם הייתה ישימה גם נגד הגרסה הזו שהיא החזקה ביותר שפותחה, ההתקפה שלהם יעילה מכוח גס כל עוד $N\leq 31$ .

ב-1991 גילו טארדי וגילברט התקפה חדשה נגד גרסאות צופן FEAL שמסוגלת לפצח אותו בסיבוכיות טובה מכוח גס^[5]. למשל FEAL-8 ניתן בשיטה זו לשבירה עם $2^{15}$ טקסטים גלויים נבחרים. מאוחר יותר פרסם מיצורו מצואי את ההתקפה הליניארית שמבוססת על רעיון זה המסוגלת לשבור את צופן FEAL-4 בתוך כחמש דקות עם ששה טקסטים גלויים ידועים. ב-1994 פורסמה התקפה ליניארית נגד FEAL-8 עם $2^{12}$ טקסטים גלויים נבחרים^[6]. למעשה בעקבות התקפות אילו נסתם הגולל על FEAL והוא אינו בשימוש כיום כלל. NTT ממליצים להשתמש בקמליה במקומו.

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

פירוט מהלכי הצופן

תיאור סכמתי של צופן FEAL

להלן תיאור צופן FEAL-NX כאשר $N\geq 32$ . הוא מקבל מפתח באורך 64 או 128 סיביות לפי בחירת המשתמש ופועל על בלוק גלוי באורך 8 בתים. באופן כללי האלגוריתם מבצע שלושה מהלכים:

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

בשלב ההכנה הנקרא קדם-עיבוד, בלוק הטקסט הגלוי $P$ מחולק לשני חצאים $(R_{0},L_{0})$ באורך 32 סיביות כל אחד. תחילה מבצעים:

(L_{0},R_{0})\leftarrow (L_{0},R_{0})\oplus (K_{N},K_{N+1},K_{N+2},K_{N+3})

כלומר מחברים ב-XOR עם ארבעה תת-מפתחות מתאימים. כל תת-מפתח באורך 16 סיביות לכן כל מחצית מהבלוק מחוברת עם שני תת-מפתחות ואז

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_0,R_0)\leftarrow(L_0,R_0)\oplus(\phi,L_0)}

כאשר הסימן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} מייצג בלוק המכיל 32 אפסים, הסימן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \oplus} הוא XOR ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_i} מייצג את תת-המפתחות מתהליך ההכנה המתואר להלן. המשמעות של המהלך הוא שהמחצית הימנית היא תוצאה של XOR עם המחצית השמאלית. לפעולת XOR עם אפסים אין השפעה לכן המחצית השמאלית נותרת ללא שינוי.

בשלב האיטרציה, הקלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_0,R_0)} משלב ההכנה עובר עיבוד עם הפונקציה $f$ בסך הכול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} פעמים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_r\leftarrow L_{r-1}\oplus f(R_{r-1},K_{r-1})}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_r=R_{r-1}}

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \le r\le N} . הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} מתוארת להלן והפלט הוא התוצאה מהסבב האחרון $(L_{N},R_{N})$ .

בשלב הסיום, מחליפים בין החצאים של הפלט האחרון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (R_N,L_N)\leftarrow(L_N,R_N)} ואז מחשבים את:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (R_N,L_N)\leftarrow (R_N,L_N)\oplus(\phi,R_N)}

ולסיום מחברים עם חלקים מתאימים מהמפתח:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (R_N,L_N)\leftarrow (R_N,L_N)\oplus(K_{N+4},K_{N+5},K_{N+6},K_{N+7})}

הטקסט המוצפן הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C=(R_N,L_N)} .

אלגוריתם הפענוח

תהליך הפענוח דומה, הקלט $(R_{N},L_{N})$ מעובד תחילה על ידי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (R_N,L_N)\leftarrow (R_N,L_N)\oplus(K_{N+4},K_{N+5},K_{N+6},K_{N+7})}

ואז

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (R_N,L_N)\leftarrow (R_N,L_N)\oplus(\phi,R_N)}

לאחר מכן מבצעים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} פעמים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{r-1}\leftarrow R_r\oplus f(L_r,K_{r-1})}

R_{r-1}\leftarrow L_{r}

כדי לקבל את הטקסט המקורי תחילה מבצעים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_0,R_0)\leftarrow (L_0,R_0)\oplus(\phi,L_0)}

לסיום מחשבים את:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_0,R_0)\leftarrow (L_0,R_0)\oplus(K_{N},K_{N+1},K_{N+2},K_{N+3})}

שימו לב שמחברים ארבעה תת-מפתחות כי תת-מפתח הוא באורך 16 סיביות ולכן נדרשים ארבעה כדי לחבר עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_0,R_0)} שהוא באורך 64 סיביות (8 בתים).

תהליך הכנת המפתח

#define ROTL(x, n)  (byte)(((byte)(x) << (n))  |  ((byte)(x) >> (8-(n))))
#define S0(x, y)   (byte)(ROTL(((byte)((x) + (y)    )), 2))
#define S1(x, y)   (byte)(ROTL(((byte)((x) + (y) + 1)), 2))

void FEAL_Fk(byte *a, byte *b)
{
	a[1] ^= a[0], a[2] ^= a[3];
	byte t;
	t = a[2] ^ b[0], a[1] = S1(a[1], t);
	t = a[1] ^ b[1], a[2] = S0(a[2], t);

	t = a[1] ^ b[2], a[0] = S0(a[0], t);
	t = a[2] ^ b[3], a[3] = S1(a[3], t);
}
void FEAL_F(byte *a, byte *b, byte *e)
{
	a[1] = (b[0] ^ b[1] ^ e[0]);
	a[2] = (b[2] ^ b[3] ^ e[1]);

	a[1] = S1(a[1], a[2]);
	a[2] = S0(a[1], a[2]);

	a[0] = S0(b[0], a[1]);
	a[3] = S1(b[3], a[2]);
}

קוד C++‎ של הפונקציות הפנימיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_k}

מהמפתח הסודי המסופק על ידי המשתמש מכינים $N+8$ תת-מפתחות מסומנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_0,K_1,K_2,...,K_{N+7}} כל אחד באורך 16 סיביות (שני בתים), כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} מהם משמשים לצורך הפונקציה הפנימית, מפתח אחד לכל סבב ואילו 8 הנוספים משמשים לפעולת ההלבנה (חיבור ב-XOR), ארבעה מהם לפני האיטרציה של הפונקציה הפנימית וארבעה לאחריה. תחילה המפתח מחולק לשני חצאים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (K_L,K_R)} באורך 64 סיביות כל אחד.

את החצי הימני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_R} מחלקים לשני חצאים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (K_{R1},K_{R2})} ומכינים סדרה של משתנים מקומיים בהתאם למספר הסבבים $Q_{r}$ בהם מציבים עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=0,1,2,...} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_r\leftarrow K_{R1}\oplus K_{R2}} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r=3i+1} ,

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_r\leftarrow K_{R1}} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r=3i+2} ,

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_r\leftarrow K_{R2}} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r=3i+3}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} נמוך מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (N/2)+4} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N\ge 32} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} זוגי.

את החצי השמאלי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_L} מחלקים לשני חצאים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A_0,B_0)} ומכינים משתנה מקומי ריק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_0} . את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_i} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=0} עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N+7} מכינים עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r=1} עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (N/2)+4 } כדלהלן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_r=A_{r-1},A_r=B_{r-1}} ,

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_r=f_K(\alpha,\beta)=f_K(A_{r-1}(B_{r-1}\oplus D_{r-1})\oplus Q-r))} ,

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{2(r-1)}=(B_{r0},B_{r1})} ,

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{2(r-1)+1}=(B_{r2},B_{r3})}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_r} הוא משתנה מקומי המחולק לארבעה בתים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_{r0},B_{r1},B_{r2},B_{r3}} .

פונקציות עזר

תיאור הפונקציה הפנימית

הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} מגיעה בשתי גרסאות אחת עבור פונקציית הסבב הפנימית והשנייה עבור הכנת המפתח. הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(\alpha,\beta)} המשמשת לצורך פונקציית הסבב מקבלת שני פרמטרים הראשון באורך 32 סיביות והשני באורך 16 סיביות, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} מחולק לארבעה בתים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha=(\alpha_0,\alpha_1,\alpha_2,\alpha_3)} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} מחולק לשני בתים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta=(\beta_0,\beta_1)} . פלט הפונקציה כמתואר בתרשים משמאל, הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f=(f_0,f_1,f_2,f_3)} כדלהלן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1 =\alpha_1 \oplus \beta_0, f_2 =\alpha_2 \oplus \beta_1}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1 = f_1 \oplus \alpha_0, f_2 = f_2 \oplus \alpha_3}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1 = S_1 (f_1, f_2), f_2 = S_0 (f_2, f_1)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_0 = S_0 (\alpha_0, f_1), f_3 = S_1 (\alpha_3, f_2)} .

הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_K(\alpha,\beta)} מקבלת שני פרמטרים באורך 32 סיביות כל אחד וכן תת-מפתח באורך 16 סיביות. הפרמטרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha,\beta} מחולקים לבתים כך: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha=(\alpha_0,\alpha_1,\alpha_2,\alpha_3)} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta=(\beta_0,\beta_1,\beta_2,\beta_3)} ואז הפונקציה מחשבת ומחזירה את ארבעת הערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (f_{K0},f_{K1},f_{K2},f_{K3})} , כדלהלן:

תיאור הפונקציה f בתהליך הכנת המפתח

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{K1} = \alpha_1 \oplus \alpha_0}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{K2} = \alpha_2 \oplus \alpha_3}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{K1} = S_1 (f_{K1}, (f_{K2} \oplus \beta_0))}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{K2} = S_0 (f_{K2}, (f_{K1} \oplus \beta_1))}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{K0} = S_0 (\alpha_0, (f_{K1} \oplus \beta_2))}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{K3} = S_1 (\alpha_3, (f_{K2} \oplus \beta_3))}

הפונקציות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_1} מוגדרות כדלהלן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_0(X_1, X_2)=\text{ROT2}((X_1 + X_2)\text{ mod }256)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_1(X_1, X_2)=\text{ROT2}((X_1 + X_2 + 1)\text{ mod }256)}

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_2} הם בתים והפונקציה ROT2 היא הזזה מעגלית לשמאל שתי סיביות, לדוגמה בהינתן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1=00010011} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_2=11110010} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle T=(X_1+X_2+1)\text{ mod }256=0000110} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_1(X_1,X_2)=00011000} בבסיס בינארי.

קוד לדוגמה

void FEAL_keygen(byte *k, byte *e, uint r)
{
	byte a[4], b[4], d[4], kr1[4], kr2[4], t, s[4];

	for (uint i = 0; i < 4; i++) {
		a[i] = k[i], b[i] = k[i + 4];
		kr1[i] = k[i + 8], kr2[i] = k[i + 12];
		d[i] = 0;
	}

	for (uint i = 0; i < r + 8; i += 2) {
		for (uint j = 0; j < 4; j++) {
			s[j] = b[j];
			if ((i / 2) % 3 == 0) {
				s[j] ^= (kr1[j] ^ kr2[j]);
			}
			else if ((i / 2) % 3 == 1) {
				s[j] ^= kr1[j];
			}
			else {
				s[j] ^= kr2[j];
			}
			s[j] ^= d[j];
			d[j] = a[j];  /*  for next steps  */
		}
		FEAL_Fk(a, s);

		for (uint j = 0; j < 4; j++) {
			e[2 * i + j] = a[j];
		}

		for (uint j = 0; j < 4; j++) {
			t = a[j];
			a[j] = b[j], b[j] = t;
		}
	}
}

void FEAL_encrypt(byte *p, uint r, byte *e, byte *c)
{
	byte a[4], b[4], t, s[4];

	for (uint j = 0; j < 4; j++) {
		a[j] = p[j] ^ e[2 * r + j];
		b[j] = p[j + 4] ^ e[2 * r + j + 4] ^ a[j];
	}

	for (uint i = 0; i < r; i++) {
		FEAL_F(s, b, e + 2 * i);

		for (uint j = 0; j < 4; j++) {
			a[j] ^= s[j];
		}

		for (uint j = 0; j < 4; j++) {
			t = a[j];
			a[j] = b[j], b[j] = t;
		}
	}

	for (uint j = 0; j < 4; j++) {
		a[j] ^= b[j];
	}

	for (uint j = 0; j < 4; j++) {
		c[j] = (b[j] ^ e[2 * r + j + 8]);
		c[j + 4] = (a[j] ^ e[2 * r + j + 12]);
	}
}


void FEAL_decrypt(byte *c, uint r, byte *e, byte *p)
{
	byte a[4], b[4], t, s[4];

	for (uint j = 0; j < 4; j++) {
		a[j] = c[j] ^ e[2 * r + j + 8];
		b[j] = c[j + 4] ^ e[2 * r + j + 12] ^ a[j];
	}

	for (uint i = 0; i < r; i++) {
		FEAL_F(s, b, e + 2 * (r - 1 - i));

		for (uint j = 0; j < 4; j++) {
			a[j] ^= s[j];
		}

		for (uint j = 0; j < 4; j++) {
			t = a[j];
			a[j] = b[j], b[j] = t;
		}
	}

	for (uint j = 0; j < 4; j++) {
		a[j] ^= b[j];
	}

	for (uint j = 0; j < 4; j++) {
		p[j] = (b[j] ^ e[2 * r + j]);
		p[j + 4] = (a[j] ^ e[2 * r + j + 4]);
	}
}

קריפטואנליזה דיפרנציאלית של FEAL-4

קריפטואנליזה דיפרנציאלית פועלת לפי מודל התקפת גלוי-נבחר^[7], כלומר המתקיף רשאי לבחור זוגות של טקסטים גלויים וטקסטים מוצפנים המתאימים להם שהוצפנו עם מפתח שאינו ידוע לו ותפקידו הוא לגלות את המפתח הסודי ששימש להצפנתם. המתקיף בוחר את הטקסטים באופן כזה שהדיפרנציאל (ההפרש) שלהם עונה על "מאפיין" מסוים המתאים לצורך ההתקפה. כאן הדיפרנציאל הוא מעל פעולת XOR ולכן הדברים נעשים פשוטים יותר כי בגלל התכונה הידועה שאם מבצעים XOR בין שני טקסטים מוצפנים שהוצפנו עם אותו קטע מהמפתח למעשה מבטלים את השפעת המפתח כאילו לא היה קיים (ראו פנקס חד-פעמי). במקרה של FEAL-4 התגלתה עובדה מעניינת: נתונה הפונקציה הפנימית של הצופן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} , עבור כל זוג טקסטים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_0\oplus A_1=\text{0x808000000}} (בבסיס הקסדצימלי) אז מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(A_0)\oplus F(A_1)=\text{0x02000000}} . למרבה ההפתעה זהו דיפרנציאל בעל הסתברות של 1 שלא קשה לחשב והוא משמש לשבירת הצופן.

FEAL-4 זהה לתיאור FEAL-XN למעט העובדה שהפונקציה הפנימית מבוצעת רק 4 פעמים ותהליך הכנת מפתח שונה. אפשר להציג את הצופן בכמה דרכים, אולם לצורך הקריפטואנליזה הדיפרנציאלית שלו הוא מוצג כאן בדרך קצת שונה מהקודמת (קל להוכיח ששתיהן למעשה שקולות). המפתח מחולק לשישה תת-מפתחות באורך 32 סיביות כל אחד (במקום 12 תת-מפתחות באורך 16 סיביות בתיאור המקורי). אפשר להתעלם מתהליך הכנת המפתח כולו כי ההתקפה מתמקדת בשחזור תת-המפתחות ואם מצליחים לנחש אותם אז אפשר לשחזר את המפתח הסודי בקלות. פונקציית הסבב הפנימית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} מקבלת ארבעה בתים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_0,x_1,x_2,x_3)} ומחזירה ארבעה בתים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (y_0,y_1,y_2,y_3)} , היא עושה שימוש בפונקציות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_1} המתוארות לעיל והיא נראית כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_1=S_1(x_0\oplus x_1, x_2\oplus x_3)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_0=S_0(x_0,y_1)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_2=S_0(y_1,x_2\oplus x_3)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_3=S_1(y_2,x_3)}

תיאור ההתקפה הדיפרנציאלית על צופן FEAL-4

לצורך ההתקפה המתקיף בוחר טקסט גלוי אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_0} ומחשב את הטקסט הגלוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1} המקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1=P_0\oplus \text{0x8080000080800000}} וכן מניחים (לפי הגדרת מודל ההתקפה) שהמתקיף השיג את הטקסטים המוצפנים המתאימים להם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1} בהתאמה ואז הוא מחשב את הדיפרנציאלים שלהם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P'=P_0\oplus P_1} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C'=C_0\oplus C_1} וכן מחשב את הדיפרנציאלים של כל ערכי הביניים של הצופן המתקבלים משני הטקסטים שהוצפנו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1} ומה שמתקבל מופיע בתרשים משמאל. העובדה שהמפתח לא מופיע בתרשים אינה טעות, כיוון שמדובר על דיפרנציאל של שני טקסטים שהוצפנו עם אותו מפתח לכן אפשר להתעלם ממנו כרגע. הדיפרנציאל האמור יחד עם הטקסטים הידועים עוזר לגלות את המפתח בשלב הבא של ההתקפה. אם מנסים לנוע בכיוון ההפוך בשיטת היפגשות באמצע, כלומר מנסים לחשב את ערכי הביניים מהטקסט המוצפן כלפי מעלה, רואים שיש אפשרות להשיג את הקלט והפלט לפונקציה הפנימית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} במהלך האחרון של הצופן. כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1} ידועים וכן אפשר לחשב את הדפירנציאלים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C', L', R'} כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L'=\text{0x2000000}\oplus Z'} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R'=L'\oplus Y'} מה שמאפשר לחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y'=\text{0x80800000}\oplus X'} . היות שהטקסט המוצפן ידוע מתקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y=L\oplus R} .

עם כל המידע הזה אפשר לפצח את הצופן תחילה על ידי ניחוש תת-המפתח השלישי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_3} . מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z'} ואז מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_1} (המתאימים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_1} ) אותם אפשר להשיג על ידי חישוב מהסוף להתחלה. היות ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_3} הוא באורך 32 סיביות ישנם למעשה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{32}} ערכים אפשריים. אם נסמן ניחוש אחד ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde K_3} , אז בידיעת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_0} אפשר לחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde Z_0} ובידיעת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_1} אפשר לחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde Z_1} כך שיתקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z'=\tilde Z_0\oplus\tilde Z_1} . אם המשוואה הזו מתקיימת אז הניחוש הצליח ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde K_3} הוא "מועמד" מתאים ושומרים אותו. היות שיכולים להיות מועמדים רבים שמקיימים את התנאי האמור, יש צורך לבדוק נכונות מול זוגות טקסטים נוספים. אם בודקים לפחות עם ארבעה זוגות כאלה הסיכויים הם מאוד גבוהים שאפשר להגיע לניחוש מוצלח והוא יהיה יחיד. אם התנאי האמור לא מתקיים נפטרים מערך זה ומחפשים ערכים אחרים. פקטור העבודה לגילוי תת-מפתח אחד הוא ברמה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{32}} שזה לא מהיר במיוחד, אבל כאן נעזרים במבנה הפנימי של הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} כדי להאיץ את החיפוש לכדי פקטור של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{17}} . לצורך כך מגדירים תחילה פונקציה המקבלת ארבעה בתים ומחשבת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(A)=M(a_0,a_1,a_2,a_3)=(0,a_0\oplus a_1, a_2\oplus a_3, 0)} . ההתקפה המשופרת לניחוש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_3} פועלת בשני שלבים. תחילה עבור כל ערך אפשרי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=(0,a_0,a_1,0)} מחשבים את:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q_0=F(M(Y_0)\oplus A), Q_1=F(M(Y_1)\oplus A)} .

אם מתבוננים בהגדרה של $F$ רואים שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=M(K_3) } אז מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle Q_0\oplus Q_1\rangle _{8...23}=\langle Z'\rangle_{8...23}} כאשר המספרים מייצגים את 16 הסיביות האמצעיות החל מהסיבית השמינית (כאשר הספירה מתחילה מאפס) ועד הסיבית ה-23. אפשר להשתמש בעובדה זו כדי למצוא מועמדים עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M(K_3)} ובכך למעשה מגלים 16 סיביות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_3} . בשלב השני כל מועמד ששרד את שלב אחד נבדק שוב כך שבהינתן מועמד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=(0,a_0,a_1,0)} , מגרילים תחילה שני בתים $B=b_{0},b_{1}$ ומחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde K_3=(b_0,a_0\oplus b_0,a_1\oplus b_1, b_1)} ואז מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde Z_0} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde Z_1} כמו בשלב אחד ובודקים אם מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z'=\tilde Z_0\oplus \tilde Z_1} . בדרך זו לאחר בדיקה מקיפה עם מספר זוגות טקסטים ידועים אפשר לשחזר את תת-המפתח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_3} או לפחות לנחש מספר קטן של מועמדים אפשריים ואז אפשר לעבור לשלב הבא של שחזור תת-המפתח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_2} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_1, K_4, K_5} עד שמנחשים את כל המפתח. בכל שלב נעזרים בניחוש תת-המפתח מהשלב הקודם כדי לנחש את הקלט והפלט של הפונקציה הפנימית.

ההתקפה המתוארת מצליחה בפקטור של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{17}} בקירוב עם ארבעה טקסטים גלויים ידועים בלבד ואינה אורכת יותר ממספר שניות על מחשב פשוט כך שגרסת FEAL-4 אינה ראויה לשימוש כלל. ההתקפה הדיפרנציאלית הורחבה ויושמה נגד כל גרסאות FEAL ונמצא שבכולן היא מצליחה בפקטור עבודה שהוא נמוך מכוח גס, למעט גרסת FEAL-NX כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N>32} , אולם בשל העובדה שפגיעות הצופן להתקפה זו מעידה על פגם מהותי בתכנונו, השימוש בכל הגרסאות שלו נזנח עקב כך.

ראו גם

הערות שוליים

^ Introduction to FEAL, NTT 1990
^ Cryptanalysis of F.E.A.L. Bert den Boer, Spnnger-Verlag Berlin Heidelberg 1988
^ THE CRYPTANALYSIS OF FEAL WITH TWENTY CHOSEN PLAINTEXTS, Sean Murphy, January 1990
^ Differential Cryptanalysis of Feal and N-Hash, Eli Biham, Adi Shamir, Spnnger-Verlag Berlin Heidelberg 1991
^ A Known Plaintext Attack of FEAL-4 and FEAL-6, Anne Tardy-Corfdir, Henri Gilbert, May 2001
^ A New Method for Known Plaintext Attack of FEAL Cipher, Mitsuru Matsui, Atsuhiro Yamagishi, May 2001
^ Applied Cryptanalysis: Breaking Ciphers in the Real World, Mark Stamp, Richard M. Low, Apr 2007, Wiley-IEEE Press

[1] Introduction to FEAL, NTT 1990

[2] Cryptanalysis of F.E.A.L. Bert den Boer, Spnnger-Verlag Berlin Heidelberg 1988

[3] THE CRYPTANALYSIS OF FEAL WITH TWENTY CHOSEN PLAINTEXTS, Sean Murphy, January 1990

[4] Differential Cryptanalysis of Feal and N-Hash, Eli Biham, Adi Shamir, Spnnger-Verlag Berlin Heidelberg 1991

[5] A Known Plaintext Attack of FEAL-4 and FEAL-6, Anne Tardy-Corfdir, Henri Gilbert, May 2001

[6] A New Method for Known Plaintext Attack of FEAL Cipher, Mitsuru Matsui, Atsuhiro Yamagishi, May 2001

[7] Applied Cryptanalysis: Breaking Ciphers in the Real World, Mark Stamp, Richard M. Low, Apr 2007, Wiley-IEEE Press

[1]

[2]

[3]

[4]

[5]

[6]

[7]