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

בקריפטוגרפיה, לוציפר (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 (בעל צליל דומה לשד או שטן באנגלית) ללוציפר.

פסאודו קוד

בקוד הבא למען הנוחות המסר בנוי כמערך תלת-ממדי 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}