לוציפר (צופן)

בקריפטוגרפיה, לוציפר (Lucifer) הוא שם כולל שניתן למשפחה של צפני בלוקים שפיתוחם החל בראשית 1966 במעבדות IBM "תומאס ג'י ווטסון" ביורקטאון ניו-יורק. לוציפר ידוע כצופן הבלוקים הראשון שפותח למטרות אזרחיות ואף נעשה ב-1970 שימוש מסחרי בגרסה אחת שלו במערכת בנקאות אלקטרונית בבריטניה. הצופן הוא אב קדמון של DES ולמעשה כמעט כל הרעיונות נשאבו ממנו לטובת תקן ההצפנה הפדרלי הישן שהוצע לממשלת ארצות הברית ב-1976. כיום הצופן אינו בטוח לשימוש, הוא פגיע להתקפה דיפרנציאלית ועיקר העניין בו הוא לצורך אקדמי. ידוע שה-NSA התערב במהלך פיתוח DES שהיה מבוסס על לוציפר ושינה אחדים מערכי תיבות ההחלפה כדי לחזקו כנגד התקפה דיפרנציאלית.

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

צופן לוציפר יועד בעיקר לחומרה והתבנית הבסיסית שלו הייתה, בהשראת קלוד שאנון אבי תורת האינפורמציה, "צופן מרוכב" המשלב כמה פונקציות חלשות כשלעצמן במבנה פייסטל. הרעיון היה בשעתו חידוש בפני עצמו ואבן דרך בתולדות ההצפנה המודרנית. ההבדלים העיקריים בין הגרסאות השונות שהוצעו על ידי פייסטל נבע בעיקר מגודל הבלוק בסיביות, גודל המפתח בסיביות, מספר התאמות בערכי תיבות ההחלפה וכיוצא בזה. ב-1971 רשם פייסטל פטנט על גרסה אחת שבה אורך הבלוק והמפתח היה 48 סיביות. John L. Smith פרסם גרסה אחרת המשתמשת בבלוק באורך 32 סיביות ומפתח 64 סיביות. ב-1973 פרסם פייסטל בסיינטיפיק אמריקן את הגרסה החזקה ביותר של הצופן הפועלת על בלוקים באורך 128 סיביות ועם מפתח באורך 128 סיביות. גרסה דומה תוארה על ידי ארתור סורקין (להלן) הפועלת עם 16 סבבים. כמו כן פורסם מימוש שלו לתוכנה בשפת APL. כאמור הצופן אינו בטוח לשימוש בסטנדרטים של ימינו והעניין בו אקדמי בלבד.

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

מבנה כללי

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

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

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

בסבב אחד קל לראות שהמבנה הוא פרמוטציה הפיכה כי מתקיים:

הסימן  הוא XOR. כלומר כיוון ש-XOR הופכי של עצמו לכן  היא אינוולוציה. מזה נובע שאפשר להפוך את ההצפנה פשוט על ידי חזרה על אותה פעולה.

לוציפר 2984
תיאור הצופן בגרסה של אלן קונהיים שהיה בצוות הפיתוח, שתוארה בספרו Computer Security and Cryptography. לטענתו זוהי הגרסה המסחרית היחידה של הצופן שהוטמעה במכונה IBM 2984 Cash Issuing Terminal שהייתה מהכספומטים הראשונים שיוצרו עבור בנקים באנגליה. לפי גרסה זו בלוק הקלט בגודל  סיביות (בסך הכול 8 ספרות הקסדצילמיות), המפתח בגודל  סיביות, הצופן מבוצע עם 16 סבבים והוא פועל ברמה של "ניבלים" שהם חצאי בתים בגודל 4 סיביות (כל ניבל מיוצג על ידי ספרה הקסדצימלית אחת).

בלוק המסר מחולק תחילה לשני חצאים  ו- כל אחד בגודל 16 סיביות (4 ניבלים) אותם טוענים לתוך אוגרי דטה מתאימים ומבצעים 16 פעמים:
 הפעלת , כלומר מחברים את תוצאת הטרנספורמציה של צד ימין ב-XOR עם צד שמאל, שים לב שצד ימין נותר ללא שינוי!
 הטרנספורמציה  כוללת את שלוש הפעולות הבאות:
 חיבור מודולו 16 של מקטע באורך 16 סיביות מהמפתח עם 16 הסיביות של  התוצאה מועתקת לאוגר זמני כאשר  נותר ללא שינוי.
 החלפת 16 הסיביות של התוצאה האחרונה ב-16 סיביות אחרות לפי תיבות ההחלפה S-box ובהתאם למפתח.
 הפעלת התמורה P-box לפי מפתח על 16 הסיביות של התוצאה האחרונה.
 שני החצאים  ו- מחליפים מקומות.
 חוזרים לשלב 1 עד להשלמת כל 16 הסבבים.
 פלט הצופן הוא התוצאה האחרונה.

הפונקציה  מתנהגת כטרנספורמציה אי-ליניארית על קלט של 16 סיביות. ובכל סבב משתמשים בסך הכול ב-36 סיביות מהמפתח. כך שכל סיבית מפתח מנוצלת 9 פעמים. 36 סיביות המפתח משולבות בכל סבב באופן הבא; 16 מהן לצורך פעולה 2.1, 4 מהן לצורך פעולה 2.2 ו-16 האחרונות לצורך פעולה 2.3. לאחר מכן "מסובבים" את המפתח.

הכנת המפתח
תהליך הכנת המפתח פשוט בתכלית. תחילה טוענים את 64 סיביות המפתח הסודי המסופק על ידי המשתמש לאוגר בזיכרון. בחלוקה לניבלים מתקבלים בסך הכול 16 ניבלים הממוספרים מ-0 עד 15. מבצעים פעולת הזזה מעגלית בסיביות שמאלה 28 פעמים (או 7 ניבלים), בכל פעימה הסיבית הנפלטת מצד שמאל מוחזרת מצד ימין. מתוך 16 הניבלים משתמשים בכל סבב רק בתשעה מהם המסומנים באותיות  עד . למשל בסבב 2 משתמשים בניבלים 6,5,4,3,2,1,0,15,14 לפי סדר זה (מסמנים ב- את הערך המצוי בניבל מס' 14 וכן הלאה עד ). סיביות המשתנים  משולבות בפעולה 2.1. סיביות המשתנה  משמשות לצורך תיבות ההחלפה בפעולה 2.2. סיביות המשתנים  משולבות בפעולה 2.3. ובכל סבב כל סיביות המפתח מוזזות שוב בהזזה מעגלית לשמאל 28 פוזיציות. כל התהליך מסתכם בטבלה הבאה:

תיבות החלפה S
תיבות ההחלפה הן שתי פונקציות אי-ליניאריות המסומנות  בהתאמה. לצורך פונקציות אילו מכינים שתי טבלאות החלפה לכל 16 הניבלים האפשריים, בסך הכול 64 סיביות. סיביות המשתנה  קובעות האם להשתמש בתיבה 0 (שורה שלישית בטבלה) או בתיבה 1 (שורה רביעית) עבור כל אחד מארבעת הניבלים של הקלט בהתאם. למשל אם הסיבית הראשונה של  היא אפס וערכו של הניבל הראשון הוא 'C' (בעשרוני 12) אז הפלט הוא .

עבור קלט  באורך 4 ניבלים הפלט הוא:

<center class="mw-content-ltr">

פסאודו קוד
בקוד הבא למען הנוחות המסר בנוי כמערך תלת-ממדי 8x8x2 בתים כשכל בית מייצג סיבית אחת בלבד (אפס או אחד). באופן דומה המפתח בנוי כמערך דו-ממדי 8x16 בתים. למעט ההחלפה האחרונה כל ההחלפות בין החצאים מתבצעות על ידי החלפת מצביעים במקום החלפה פיזית. וכן לצורך יעילות מספר פעולות שולבו יחד, בשלב הראשון תיבות ההחלפה משולבות יחדיו עם בית הבקרה וכן בשלב השני הוספת המפתח משולבת עם התמורה הקבועה וכן מתבצעת המרה ממערך סיביות למספר שלם וההפך. ברור הקוד אינו ממוטב וניתן לבצע שיפורים רבים (במיוחד בעיית אחסון סיביות במערך בתים), אלה לא בוצעו למען הפשטות וכדי להתאימו לתיאור ולתרשים לעיל.
Lucifer( m, k, d ) // m = m[0 to 7][0 to 7][0 to 1], k = k[0 to 7][0 to 15], d=1 indicates decipher
{
 O = { 7, 6, 2, 1, 5, 0, 3, 4 } // convolution registers
 R = { 2, 5, 4, 0, 3, 1, 7, 6 } // permutaion table

 s_0 = { 12, 15, 7, 10, 14, 13, 11, 0, 2, 6, 3, 1, 9, 4, 5, 8 } // s-box 0
 s_1 = { 7, 2, 14, 9, 3, 11, 0, 4, 12, 13, 1, 10, 6, 15, 8, 5 } // s-box 1

 h0 = 0, h1 = 1 // pointers to the message halfs
 kc = 0
 if( d == 1 ) kc = 8

 For i = 1 to 16 do
 {
 if( d == 1 ) kc = (kc + 1) mod 16
 ks = kc // ks is the control byte

 For j = 0 to 7 do
 {
 l = 0, h = 0
 // construct integers of two nibbles of current message byte
 For k=0 to 3 do
 l = l * 2 + m[7 - k, j, h1]
 For k=4 to 7 do
 h = h * 2 + m[7 - k, j, h1]

 // controlled interchange and s-box permutation
 v = (s_0[l] + 16 * s_1[h]) * (1 - k[j, ks]) + (s_0[h] + 16 * s_1[l]) * k[j, ks]

 // convert back to bit array
 For k=0 to 7 do
 {
 tr[k] = v mod 2
 v = v / 2
 }
 // combined key interruption and permutaion
 For k=0 to 7 do
 m[k, (O[k] + j) mod 8, h0] =
 ((k[R[k], kc] + tr[R[k]] + m[k, (O[k] + j) mod 8, h0]) mod 2

 If ( j < 7 or d == 1 ) kc = (kc + 1) mod 16
 }
 swap( h0, h1 ) // swap pointers only
 }
 swap( m[*, *, 0], m[*, *, 1] ) // phisically swap upper with lower halfs of the message
}

ראו גם
 DES

הערות שוליים

ערכים שבהם תבנית בריטניקה אינה מתאימה
קריפטוגרפיה