רשת פייסטל

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

המבנה הסימטרי של הבנייה מאפשר שימוש נוח בצופן כך שפונקציות ההצפנה והפענוח הן מבוצעות באופן זהה בהחלפת סדר הזנת המפתחות. מבנה זה מקטין את גודל היישום של הצופן היות שאין צורך ליישם את פונקציות ההצפנה והפענוח בנפרד. רשת פייסטל היא מבנה הבסיס לצפני ידועים רבים, בהם: DES, Blowfish, KASUMI, Twofish, 3DES, Tiny ו-RC5.

בניסוח פורמלי, רשת פייסטל היא פונקציה הממפה טקסט גלוי באורך $2\cdot t$ סיביות $(L_0,R_0)$ לטקסט מוצפן $(R_n,L_n)$ באמצעות מפתח הצפנה $k$ בתהליך $n$ שלבי‏.

היסטוריה

רשת פייסטל הופיעה לראשונה בצופן לוציפר שפותח במשותף על ידי הורסט פייסטל ודון קופרשמידט במסגרת עבודתם ב-IBM. השימוש בבנייה הפך נפוץ לאחר ש-NSA אימץ את תקן ההצפנה DES שהתבסס על לוציפר^{[דרוש מקור]}.

כאמור, צפנים רבים הם בעלי מבנה פייסטל. עובדה זו הובילה לכך שהקהילה המדעית השקיעה מאמץ אקדמי רב בניתוח תכונות המבנה. בעבודתם משנת 1988 הוכיחו מיכאל לובי וצ'ארלס רקופף שאם פונקציית השלב מתנהגת בצורה פסבדו-אקראית תחת מפתח ההצפנה אזי שילובה בתוך רשת פייסטל יניב פונקציה פסאודו-אקראית לאחר 3 איטרציות ופונקציה פסאודו-אקראית חזקה לאחר 4 איטרציות. אחד היתרונות של רשת פייסטל על-פני רשת החלפה הוא שפונקציית השלב אינה חייבת להיות הפיכה.

פרטי הבנייה

תהי $F$ פונקציית שלב ויהי $K$ המפתח לפונקציה כך שהמפתחות $K_0,K_1,\ldots,K_{n}$ הם התת-מפתחות לאיטרציות $0,1,\ldots,n$ בהתאמה. הבנייה עובדת באופן הבא:

1. הבנייה מחלקת את הטקסט הגלוי לשני חלקים שווים $L_0$, $R_0$.
2. עבור כל שלב $i=0,1,\ldots,n$ מבצעים:

$L_{i+1} = R_i\,$

$R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$.

• הטקסט המוצפן הוא:

$\ (R_{n}, L_{n})$

פענוח הצופן נעשה באופן דומה בסדר איטרציות הפוך $i=n,n-1,\ldots,0$

$R_{i} = L_{i+1}\,$

$L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$.

• כך שבסוף התהליך מתקבל שוב הטקסט הגלוי:

$\ (R_0, L_0)$