IDEA

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

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

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

תיאור הצופן

תהליך ההצפנה מורכב משמונה סבבים של פעולות אריתמטיות וטרנספורמציה מסיימת (ראו שורה אחרונה בפסאודו קוד). האלגוריתם מקבל בלוק קלט בגודל 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) אלא תחת זאת שילוב פעולות אלגבריות בחבורות שונות. פעולות אילו נבחרו בשל היחס הסטטיסטי בין המשתנים$X,Y,Z$בפעולה$Y=X*Z$עם תכונתסודיות מושלמת,כלומר שאם אחד מהמשתנים נבחר באקראי במידה שווה מתוך כל איברי החבורה אזי שני המשתנים האחרים יהיובלתי תלויים סטטיסטית.מבנה הצופן נקרא מבנה כפל-חיבור בקיצור מבנה MA (כמתואר בתרשים).

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

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

$a\boxplus (b\odot c)\neq (a\boxplus b)\odot (a\boxplus c)$

$a\boxplus (b\oplus c)\neq (a\boxplus b)\oplus c$

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

ראו גם

• DES
• SAFER
• TEA
• צופן בלוקים