רשת פייסטל

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

היסטוריה[עריכת קוד מקור | עריכה]

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

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

פרטי הבנייה[עריכת קוד מקור | עריכה]

Feistel cipher diagram.svg

תהי 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)

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ 1.0 1.1 Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 251.
  2. ^ K.V. Srinivasa Rao , M. Rama Krishna and D. Bujji Babu , 2009. Cryptanalysis of a Feistel Type Block Cipher by Feed Forword Neural Network Using Right Sigmoidal SignalsInternational Journal of Soft Computing, 4: 131-135.