Data Encryption Standard

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

Data Encryption Standard (בראשי תיבות: DES) הוא תקן הצפנת נתונים.

זהו צופן בלוקים שפותח ב־1975 על־ידי IBM בשיתוף ה־NSA. התקבל בשנת 1976 כתקן האמריקאי להצפנת נתונים בעולם האזרחי, ושימש כתקן עד נובמבר 2001, אז הוחלף בתקן החדש Advanced Encryption Standard או AES, שהינו בטוח ומהיר מקודמו. למרות זאת, צופן DES עדיין נמצא בשימוש נרחב, בעיקר בתחום הבנקאות.

צופן DES הוא צופן סימטרי, להבדיל מצופן מפתח ציבורי וככזה ההנחה היא שבידי השולח והמקבל מפתח ההצפנה, שאותו העבירו אחד לשני באופן מאובטח בשלב מוקדם יותר. DES משתייך לתת-המחלקה של צופנים סימטריים הקרויה צופן גושים (Block Ciphers). צופן גושים מצפין גושי מידע גדולים (במקרה של DES באורך 64 סיביות), בעזרת מפתח סודי K באורך 64 סיביות. המפתח יכול להיות תוצר של קוד סודי או סיסמה קצרה יותר, בדרך ידועה ומקובלת.

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

ההתקפה הבולטת הראשונה כנגד צופן זה הייתה של אלי ביהם, כיום פרופסור בטכניון, והמנחה שלו לדוקטורט עדי שמיר, כיום פרופסור במכון ויצמן למדע. הם פרסמו ב-1990 את עבודת הדוקטורט שלו שעסקה בקריפטואנליזה דיפרנציאלית כנגד DES - טכניקה רבת עוצמה היעילה כנגד אלגוריתמים סימטריים נוספים. ההתקפה הטובה ביותר המוכרת כיום כנגד DES היא הקריפטואנליזה הלינארית. שתי ההתקפות דורשות כמות גדולה ביותר של טקסטים מוצפנים ומקורותיהם על מנת למצוא את מפתח ההצפנה, ולכן אינן שימושיות בפועל, להבדיל מהתקפות כוח גס על DES שמנצלות את המפתח הקטן יחסית שלו.

[עריכה] היסטוריה

DES קשור בשני רעיונות כלליים: צופן מורכב וצופן פייסטל על שמו של הורסט פייסטל מתמטיקאי וקריפטוגרף (ממוצא גרמני) שעבד בצוות המחקר של יבמ והיה אחראי להמצאות נוספות כמו צופן לוציפר. הרעיונות ששילב פייסטל בצופן שלו היוו מקור השראה לאלגוריתם DES. הרעיון של צופן מורכב הוא הרכבת פונקציות הצפנה חלשות, אשר כשלעצמן אינן מספקות רמה בטיחות ראויה, אולם שילובן יחד יוצר פונקציה חדשה בעלת חוסן רב יותר. פונקציות פשוטות אילו יכולות להיות למשל "שיכול" (סידור מחדש), תמורה, טרנספורמציה לינארית, פעולות אריתמטיות על סיביות כמו XOR והחלפה (טרנספוזיציה).

הרעיון של צופן פייסטל הוא מיפוי של $\ 2t$ סיביות של גושי טקסט קריא $\ (L_i, R_i)$ , ל- $\ 2t$ סיביות גושי צופן באופן כזה: מחלקים כל גוש לשני חלקים, צד ימין $\ R$ וצד שמאל $\ L$ . בכל סבב מצפינים את חלקי הגוש בנפרד ושוזרים, כלומר $\ R$ ו- $\ L$ מחליפים מקומות. במילים אחרות פעולת פונקציית ההצפנה מבוצעת על שני חלקי הגוש צד ימין וצד שמאל לסירוגין, כך שבכל סבב הפלט של צד ימין הופך לקלט של צד שמאל וחוזר חלילה. סחרור הצופן באופן זה מחזק אותו ומקשה באופן משמעותי על פריצתו. הפענוח מתבצע באותו סדר שזירה אך עם פונקציית מפתח הפוכה.

[עריכה] פירוט האלגוריתם

קלט האלגוריתם הוא גוש טקסט קריא בגודל 64 סיביות ומפתח הצפנה סודי $\ K$ בגודל 64 סיביות (כאשר רק 56 סיביות מתוכם בשימוש) . DES הנו צופן איטרטיבי, ההצפנה מתבצעת בשש-עשרה סבבים. באמצעות פרוצדורת הרחבת מפתח מרחיבים ומחלקים את המפתח ל-16 גושים בני 48 סיביות, כל אחד מהם משמש עבור סבב אחד. מכינים 8 תיבות החלפה (S-box) סטטיות $\ S_1,S_2,...,S_8$ המייצגות פונקציות שמחזירות פלט של 4 סיביות עבור קלט של 6 סיביות. תיבות ההחלפה הן לב לבו של DES. הפונקציות שהן מייצגות הן הפעולות הלא-לינאריות היחידות שמופעלות על הקלט, ואלמלא הן, הצופן היה ניתן לפריצה בקלות. בדיעבד התברר כי התיבות תוכננו בצורה כזו שתהפוך את הצופן עמיד יחסית להתקפות דוגמת הקריפטואנליזה הדיפרנציאלית.

מכינים תיבות הרחבה ותמורה נוספות $\ E$ ו- $\ P$ (ראה תרשימים), המייצגות פונקציות מיפוי לפי ערכים קבועים. בשלב הראשון מבצעים תמורה על כל סיביות הקלט באמצעות תיבת תמורה סטטית הנקראת $\ IP$ (ראה תרשים) ובסיום כל 16 הסבבים מעבירים את הפלט בתיבת התמורה ההופכית $\ IP^{-1}$ . לפעולה זו אין השפעה משמעותית על בטיחות הצופן ומקובל להתעלם ממנה כשמנתחים את הצופן. סדר הפעולות בכל הסבבים זהה. תחילה מחלקים את קלט האלגוריתם לשני חצאים $\ L_0, R_0$ בהתאמה. ובכל סבב מבצעים כדלהלן:

$\ L_i=R_{i-1}$ ,

$\ R_i = L_{i-1} \oplus f(R_{i-1}, K_i)$

כאשר $\ f(R_{i-1},K_i)=P(S(E(R_{i-1}) \oplus K_i))$ .

הפונקציה $\ E$ מייצגת פונקציית הרחבה/תמורה סטטית הממפה קלט של 32 סיביות לפלט של 48 סיביות, הפונקציה למעשה "מגדילה" את הקלט (כל סיבית קלט משפיעה על פלט הפונקציה לפחות פעם אחת). הפונקציה $\ P$ מייצגת טבלת שיכול סטטית אחרת בגודל 32 סיביות, שלמעשה מכווצת את הקלט ל-32 סיביות (ראה תרשימים).

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

[עריכה] פרוצדורת הרחבת מפתח

להרחבת המפתח, צופן DES משתמש בשתי טבלאות סטטיות $\ PC1$ ו- $\ PC2$ (ראה תרשימים). המפתח מורחב כאמור ל-16 גושים בני 48 סיביות כל אחד. מתעלמים מהסיביות $\ (k_8,k_{16},...,k_{64})$ ובאמצעות טבלה $\ PC1$ מחלקים את 56 הסיביות האפקטיביות לשני משתנים $\ C$ ו- $\ D$ בני 28 סיביות כל אחד.

עבור כל סבב מבצעים הזזה מחזורית לשמאל (Rotate left) של סיביות המשתנים $\ C$ ו- $\ D$ בסיבית אחת או שתים (בהתאם לערך התלוי במיקום הסיביות, עבור הסיביות 1,2,9,16 מזיזים ב-2 עבור היתר מזיזים ב-1) משתמשים בטבלה $\ PC2$ כדי לשרשר את סיביות המשתנים לגוש מפתח בגודל 48 סיביות.

[עריכה] מצבי הפעלה

הצפנה סימטרית כמו DES מכילה מטבעה בעיה מהותית והיא: הצפנה חוזרת של גושים זהים עם מפתח זהה תניב גוש מוצפן זהה. ניתן להעזר במספר מועט של גושי צופן (שחלקם זהים) על מנת לבצע ניתוח סטטיסטי של הצופן (אם ידועה השפה) ולחלץ בדרך זו מידע אודות טקסט המקור. הפתרון לכך הוא יישום האלגוריתם באחד ממצבי ההפעלה כדי לבטל את יתירות (Redundancy) הצופן. ראה צופן בלוקים.

מקור: http://he.wikipedia.org../../../d/a/t/Data_Encryption_Standard_9913.html

קטגוריות: תקנים בתחום המחשוב | הצפנה