IDEA

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

International Data Encryption Algorithm הוא צופן בלוקים סימטרי שהוצע ב-1991 על ידי ג'יימס מסי מהמכון הטכנולוגי של ציריך ו-Xuejia Lai מאוניברסיטת ג'יאו טונג שאנגחאי[1] כדי להוות מחליף ראוי ל-DES הוותיק. הצופן פועל על בלוק נתונים בגודל 64 סיביות עם מפתח 128 סיביות והוא מבוסס על קונספט "שילוב פעולות מחבורות אלגבריות שונות". הצופן הומלץ על ידי מומחים וההתקפה היעילה ביותר כנגדו היא בסיבוכיות של  2^{126} בערך - קצת פחות מכוח גס. חסרונותיו העיקריים, בלוק המידע הוא רק 64 סיביות (כלומר סיבוכיות מקום נמוכה ביחס לדרישת התקן המתקדם - 128 סיביות לפחות) וכן קצת איטי ביישום הן בתוכנה והן בחומרה. זמינותם של אלגוריתמים חדשים, מהירים ובטוחים יותר הותירה את IDEA מאחור, אם כי עדיין נתמך בפועל במערכות אבטחה רבות כולל PGP ו-OpenSSL. השם IDEA הינו סימן רשום ונרשם כפטנט שתוקפו פג ב-2012 וכעת חופשי לשימוש.

IDEA מיישם רשת החלפה-תמורה דומה לרשת פייסטל ומנצל פעולות אריתמטיות בשלוש חבורות אלגבריות שונות על תת-בלוקים בגודל 16 סיביות, להשגת פיזור (diffusion) מהיר ועירבוב (confusion) גבוה. פיזור נחוץ להבטיח שכל סיבית טקסט גלוי וכל סיבית מפתח, ישפיעו על כל סיביות הטקסט המוצפן במידה שווה. ערבוב מבטיח שהקשר בין הטקסט המוצפן לטקסט הגלוי והמפתח יהיה מסובך ורחוק ככל האפשר. רשת ההחלפה-תמורה בנויה כך שהצפנה ופענוח ייעשו באמצעות אותה פונקציה עם מפתח שונה (ראה להלן). ידוע על מפתחות הצפנה "חלשים" שלא מומלץ להשתמש בהם (כגון אם הייצוג הבינארי מכיל רצף ארוך של אפסים), בפועל אם המפתח נבחר באקראי הסיכוי נמוך ביותר שיבחר מפתח חלש. מלבד זאת קיימות טכניקות למנוע זאת.

תיאור הצופן[עריכת קוד מקור | עריכה]

תרשים אלגוריתם IDEA. הסימן \oplus מייצג XOR, הסימן \boxplus מייצג חיבור מודולו 2^{16} והסימן \odot מייצג כפל מודולו 2^{16}+1

תהליך ההצפנה מורכב משמונה סבבים של פעולות אריתמטיות וטרנספורמציה מסיימת (ראה שורה אחרונה בפסאודו קוד). האלגוריתם מקבל בלוק קלט בגודל 64 סיביות, מחולק לארבעה מטקעים בני 16 סיביות כל אחד X_1,...,X_4 ומפיק ארבעה בלוקים Y_1,...,Y_4 בסיוע 52 תת-מפתחות Z_1,...,Z_{52} המחולקים כדלהלן: ששה תת-מפתחות עבור כל סבב כפול שמונה סבבים המסומנים Z_1^{(r)},...,Z_6^{(r)} כאשר r=1,..,8 מייצג את מספר הסבב. וארבעה נוספים עבור הפעולה המסיימת המסומנים Z_1^{(9)},Z_2^{(9)},Z_3^{(9)},Z_4^{(9)}. בכל סבב מתבצע צירוף של סדרת פעולות אריתמטיות:

  1. מיפוי סיביות בשדה בינארי מורחב F_{2^n} מעל F_2 עם פעולת XOR המסומן בסמל \oplus.
  2. חיבור שלמים מודולו 2^{16} (חבורה חיבורית Z_{2^{16}}), המסומן ב-\boxplus.
  3. כפל שלמים מודולו 2^{16}+1 (חבורה כפלית Z_{2^{16}+1}) ומסומן בקיצור \odot. זהו כפל מודולרי רגיל למעט הכלל שמחרוזת 16 אפסים מייצגת את הערך 2^{16} (כזכור לא ניתן לייצג את 2^{16} ב-16 סיביות, על כן סיבית 1 הגבוהה מרומזת) לדוגמה \mbox{00...00} \cdot \mbox{10...00} = \mbox{10...01} בגלל ש-2^{16}\cdot 2^{15}\mbox{ mod }(2^{16}+1)=2^{15}+1.

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

מבצעים בלולאה שמונה סבבים (שים לב שהאינדקס מתחיל באחד ולא באפס. Z_i^{(r)} מייצג את ערך המפתח בכניסה i במפתח-סבב r במערך הדו-ממדי):

  1. \text{For }r = 1\text{ to }8\text{ do }
    1. X_1 = X_1 \odot Z_1^{(r)}, \quad \quad X_2 = X_2 \odot Z_2^{(r)}.
    2. X_3 = X_3 \boxplus Z_3^{(r)}, \quad \quad X_4 = X_4 \boxplus Z_4^{(r)}.
    3. k = Z_5^{(r)} \odot (X_1 \oplus X_3)
    4. t_1 = Z_6^{(r)} \odot k \boxplus (X_2 \oplus X_4)
    5. t_2 = k \boxplus t_1
    6. a = X_1 \oplus t_1, \quad \quad x_1 = X_3 \oplus t_1, \quad \quad X_3 = a
    7. a = X_2 \oplus t_2, \quad \quad x_2 = X_4 \oplus t_2, \quad \quad X_4 = a
  2. Y_1 = X_1 \cdot Z_1^{(9)}, \quad \quad Y_2 = X_2 \cdot Z_2^{(9)}, \quad Y_3 = X_3 \boxplus Z_3^{(9)}, \quad \quad Y_4 = X_4 \boxplus Z_4^{(9)}

תהליך הכנת מפתחות[עריכת קוד מקור | עריכה]

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

  1. תחילה מכינים מערך נלווה S_0,...,S_{54}, בשמונה הכניסות הראשונות מציבים את המפתח המסופק על ידי המשתמש ואז עבור היתר, מבצעים לולאה i=8,...,54 כדלהלן:
  2. אם (i+2) מתחלק ב-8 מציבים: S_i =(S_{i - 7} \mbox{ ROL}_9) \oplus (S_{i - 14} \mbox{ ROR}_7).
  3. אחרת, אם (i+1) מתחלק ב-8 מציבים: S_i = (S_{i - 15} \mbox{ ROL}_9) \oplus (S_{i - 14} \mbox{ ROR}_7).
  4. ביתר המקרים מציבים: S_i = (S_{i - 7} \mbox{ ROL}_9) \oplus (S_{i - 6} \mbox{ ROR}_7).
  5. מבצעים לולאה אחרונה שבה מעבירים את הערכים ל-Z כאשר האינדקסים הם r=1,...,9 ו-j=1,...,6:
Z_{j, r} = S_{6 \cdot (r - 1)+j - 1}

הפעולות ROR ו-ROL הן הזזה מעגלית בסיביות ימינה או שמאלה בהתאמה במספר פוזיציות לפי המציין התחתי.

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

לפענוח תחילה מחשבים את 52 מפתחות הפענוח מתוך מפתחות ההצפנה באמצעות חישוב המספרים ההופכיים שלהם. כלומר Z^{-1} מייצג הופכי כפלי של Z מודולו  2^{16}+1 כך שמתקיים Z\cdot Z^{-1}\equiv 1\mbox{ (mod }2^{16}+1) וכן -Z הוא הופכי חיבורי או המשלים של Z מודולו 2^{16} (במקרה זה המשלים יהיה 2^{16}-Z). ההופכי של XOR נותר זהה. לצורך המחשה אם מפתחות הסבב הם Z_1^{(r)},Z_2^{(r)},Z_3^{(r)},Z_4^{(r)},Z_5^{(r)},Z_6^{(1)} מפתחות הפענוח המקבילים להם יהיו {Z_1^{(r)}}^{-1},{Z_2^{(r)}}^{-1},-Z_3^{(r)},-Z_4^{(r)},Z_5^{(r)},Z_6^{(r)} (שני האחרונים מייצגים XOR לכן הם הופכיים של עצמם) - בסדר הפוך, דהיינו תחילה ארבעת המפתחות המקבילים לטרנספורמציה האחרונה המסומנים 9 ולאחר מכן 48 המפתחות הנותרים בסדר הפוך, ששה עבור כל סבב. ואז הפענוח מתבצע באופן זהה להצפנה (בפסאודו-קוד לעיל). הכנת מפתח הפענוח בניסוח פורמלי מתוארת להלן, כאשר DK מייצג את מפתח הפענוח (decryption key). מבצעים תשעה סבבים כדלהלן:

  1. \text{For }j=1\text{ to }9\text{ do }
    1. DK_1^{(10-j)} = {Z_1^{(j)}}^{-1}
    2. DK_2^{(10-j)} = {Z_2^{(j)}}^{-1}
    3. DK_3^{(10-j)} = 2^{16} - Z_3^j
    4. DK_4^{(10-j)} = 2^{16} - Z_4^j
    5. DK_5^{(9 - j)} = Z_5^{(j)}
    6. DK_6^{(9 - j)} = Z_6^{(j)}

ביטחון האלגוריתם[עריכת קוד מקור | עריכה]

הצופן אינו עושה שימוש בתיבות החלפה (S-box) אלא תחת זאת משיג פיזור (diffusion) באמצעות שילוב בין פעולות אלגבריות בחבורות. פעולות אילו נבחרו בשל היחס הסטיסטי בין המשתנים X,Y,Z בפעולה Y=X*Z עם תכונת "סודיות מושלמת", כלומר שאם אחד מהמשתנים נבחר באקראי במידה שווה מתוך כל איברי החבורה אזי שני המשתנים האחרים יהיו בלתי תלויים סטטיסטית. מבנה הצופן נקרא מבנה כפל-חיבור בקיצור מבנה MA (כמתואר בתרשים).

מבנה כפל-חיבור של IDEA

האינטראקציה בין סוגים שונים של פעולות בחבורות מניבה את הערבוב (confusion) הדרוש. השילוב נעשה באופן שבכל קבוצה של שלוש פעולות אלגבריות לא תתקיים דיסטריבוטיביות או אסוציאטיביות. למשל אפשר לראות שאם מציבים a=b=c=1 בשתי המשוואות הבאות החוקים האמורים אינם מתקיימים:

a\boxplus (b \odot c)\ne (a\boxplus b)\odot (a\boxplus c)
a\boxplus (b \oplus c) \ne (a\boxplus b)\oplus c

לפי טענת המפתחים האלגוריתם מעוצב כדי להתמודד מול איום קריפטואנליזה דיפרנציאלית. נכון ל-2007 ההתקפה הטובה ביותר כנגד האלגוריתם הייתה בסיבוכיות של 2^{126.8} עם 2^{64} טקסטים גלויים. למרות היותו איטי מספק האלגוריתם ביטחון טוב יותר בהשוואה ל-DES אולם חלש יחסית לאלגוריתמים חדשים דוגמת AES או Twofish. העובדה שגודל הבלוק הוא רק 64 סיביות מעיבה מעט על ביטחונו.

ראו גם[עריכת קוד מקור | עריכה]


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