RC6

RC6

תרשים צופן RC6. הסימן $\oplus$ מייצג XOR הסימן $\boxplus$ מייצג חיבור מודולו $2^{w}$ הסימן $\lll$ מייצג הזזה מעגלית לשמאל, ו-$f$ מתייחס לפונקציה $f(x)=x\times (2x+1)$
מידע כללי
תכנון	רון ריבסט, Matt Robshaw, Ray Sidney, Yiqun Lisa Yin
פרסום	2000
מבוסס על	RC5
מבנה הצופן
אורך מפתח	128/192/256 סיביות
אורך בלוק	128 סיביות
מבנה	רשת פייסטל
מספר סבבים	20

RC6 הוא צופן בלוקים סימטרי שפותח ב-1998, על ידי רונלד ריבסט יחד עם Matt Robshaw ,Ray Sidney ו-Yiqun Lisa Yin, מחברת RSA ו-MIT עבור תקן ההצפנה המתקדם שהחליף את DES. זהו דור ההמשך של צופן RC5 שפותח במיוחד כדי להתאים לדרישות התקן והיה מבין חמשת המועמדים המובילים (מקום רביעי אחרי Twofish). כקודמו RC6 עושה שימוש נרחב בהזזה מעגלית בסיביות (bitwise rotation) תלויית מידע. אולם נוספו בו מאפיינים חדשים; הוא מנצל ארבעה אוגרים במקום שניים וכולל כפל מודולרי בשלמים שמגביר באופן ניכר את רמת הפיזור (diffusion) לסבב. מה שמניב ביטחון טוב יותר בפחות סבבים ובתפוקה גבוהה יותר. כיתר המועמדים שעלו לגמר במהלך התחרות הוכרז כי לא נמצאו התקפות יעילות נגדו. RC6 רשום כפטנט, שמו הוא סימן רשום והזכויות עליו שייכות לחברת RSA. ייתכן שהשימוש בו מצריך רישיון (החברה הצהירה כי אם ייבחר על ידי התקן יהיה השימוש בו חופשי אולם לא ניתנה כל הצהרה נוספת לאחר סגירת התחרות).

שיקולי פיתוח

RC6 נולד בעקבות הרצון להתאים את צופן RC5 שיצא ב-1995 לתקן המתקדם ובעקרון הם דומים בפשטותם הרבה. את השם RC ניתן לפרש כקיצור של Rivest Cipher או Ron's Code. אף על פי שלא התגלו התקפות מעשיות מוצלחות כנגד RC5, מחקרים גילו אפשרות להתקפה תאורטית שנובעת מהעובדה שמידת ההזזה המעגלית אינה מושפעת מכל סיביות האוגרים. הפתרון היה הוספת כפל שלמים מודולרי. בנוסף, כדי לעמוד בדרישות התקן על הבלוק להיות 128 סיביות לפחות. למרות היותו מהיר RC5 מכיל רק שני אוגרי 32 סיביות לכן לא ניתן היה להרחבה ביעילות כדי להגיע ל-128 סיביות ללא שימוש באוגרים גדולים יותר שהתקן אינו תומך בהם, במקום זאת הוחלט להגדיל את מספר האוגרים. והתוצאה היא RC6 – בטוח ומהיר יותר וכמו קודמו שומר על פשטות וביצועים גבוהים בתוכנה.

תיאור האלגוריתם

RC6 הוא אלגוריתם פרמטרי המוגדר על ידי הסימון RC6-w/r/b. גודל מילה הוא $w$ סיביות, מספר הסבבים הוא $r$ והמפתח בגודל $b$ בתים, לצורך התקן נקבע $w=32,r=20$ והמפתח יכול להיות $b\in \{16,24,32\}$ בתים. האלגוריתם פועל על ארבע מילים בגודל $w$ תוך שימוש בפעולות הבאות:

$a+b$ או $a-b$	חיבור וחיסור שלמים מודולו $2^{w}$
$a\oplus b$	חיבור XOR במילים בגודל 32 סיביות
$a\times b$	כפל שלמים מודולו $2^{w}$
$a\lll b$ או $a\ggg b$	הזזה מעגלית של $a$ שמאלה או ימינה לפי כיוון החצים במספר פוזיציות לפי ${\mbox{lg }}w$ הסיביות הראשונות של $b$ (כאשר ${\mbox{lg}}$ מייצג לוגריתם בבסיס 2, במקרה של $w=32$ לפי התקן, 5 סיביות).

הקלט הוא 128 סיביות טקסט גלוי המחולקות לארבע מילים בגודל 32 סיביות $A,B,C,D$ לפי סדר בתים קטן (הסיביות הראשונות של הקלט מוצבות בבית הראשון של $A$). וכן מפתח מורחב (ראה להלן) שהוא מערך של 43 מפתחות-סבב בגודל 32 סיביות כל אחד, המסומן $S[0,...,2r+3]$. בתיאור הצופן, סבב מתייחס לתהליך דמוי רשת פייסטל, דהיינו בכל סבב מחצית סיביות הקלט עוברות טרנספורמציה בהתאם למחצית השנייה ולאחר מכן מחליפים מקומות לפי סדר $(A,B,C,D)=(B,C,D,A)$. להלן פסאודו קוד.

הצפנה

$B=B+S[0]$

$D=D+S[1]$

${\mbox{For }}i=1{\mbox{ to }}r{\mbox{ do:}}$

$t=(B\times (2B+1)\lll {\mbox{lg }}w$

$u=(D\times (2D+1)\lll {\mbox{lg }}w$

$A=((A\oplus t)\lll u)+S[2i]$

$C=((C\oplus u)\lll t)+S[2i+1]$

$(A,B,C,D)=(B,C,D,A)$

$A=A+S[2r+2]$

$C=C+S[2r+3]$

פענוח

$C=C-S[2r+3]$

$A=A-S[2r+2]$

${\mbox{For }}i=r{\mbox{ downto }}1{\mbox{ do:}}$

$(A,B,C,D)=(D,A,B,C)$

$u=(D\times (2D+1)\lll {\mbox{lg }}w$

$t=(B\times (2B+1)\lll {\mbox{lg }}w$

$C=((C-S[2i+1])\ggg t)\oplus u$

$A=((A-S[2i])\ggg u)\oplus t$

$D=D-S[1]$

$B=B-S[0]$

הרחבת מפתח

תהליך הרחבת המפתח תואם את תהליך הרחבת המפתח של RC5, עם יותר מילות מפתח. המפתח מורחב ממפתח הצופן $b$ המסופק על ידי המשתמש כשהוא מרופד באפסים לפי הצורך ומיוצג על ידי מערך $L$ המכיל $c$ מילים בגודל $w$ סיביות. אם המפתח $b=0$ אזי $c=1$ ו-$L[0]=0$. מספר המילים הדרוש למפתח המורחב $S$ הוא $2r+4$. מכינים מערך $S[0,...,2r+3]$ תוך שימוש בקבוע $P_{32}={\mbox{B7E15163}}$ שהוא ייצוג הקסדצימלי של $e-2$ (כאשר $e$ הוא בסיס הלוגריתם הטבעי) ובקבוע $Q_{32}={\mbox{9E3779B9}}$ שהוא ייצוג הקסדצימלי של $\phi -1$ כאשר $\phi$ מייצג את יחס הזהב (אילו ערכים שרירותיים שאפשר להחליפם באחרים להתאמה אישית) מבצעים כדלהלן:

$S[0]=P_{32}$

${\mbox{For }}i=1{\mbox{ to }}2r+3{\mbox{ do:}}$

$\{$

$S[i]=S[i-1]+Q_{32}$

$\}$

$A=B=i=j=0$

$v=3\times {\mbox{max}}\{c,2r+4\}$

${\mbox{For }}s=1{\mbox{ to }}v{\mbox{ do:}}$

$\{$

$A=S[i]=(S[i]+A+B)\lll 3$

$B=L[j]=(L[j]+A+B)\lll (A+B)$

$i=(i+1){\mbox{ modulo }}(2r+4)$

$j=(j+1){\mbox{ modulo }}c$

$\}$

ביצועים וביטחון

יישום צופן RC6 (על פנטיום 2) בשפת c הגיע למהירות של כ-600 מחזורי שעון לבלוק או כ-5 מגה לשנייה. RC6 עולה בביצועיו על ריינדל במימוש בתוכנה בעיקר על מחשב אינטל 32 סיביות. כמו יתר המועמדים (לפי דרישות התקן) מתאים ליישום גם בחומרה או במעבד כרטיס חכם, אם כי לריינדל ביצועים טובים יותר בשטח זה. היות ש-RC6 אינו משתמש בתיבות החלפה מימוש האלגוריתם מאוד קומפקטי ויכול לאכלס פחות מ-256 בתים. הערכת המפתחים היא שההתקפה הטובה ביותר האפשרית כנגד הצופן, היא בסיבוכיות בין $2^{704}$ ל-$2^{256}$.

קוד לדוגמה

להלן קוד C++‎ לא אופטימלי להמחשה. לפי פרמטרים: $w=32,r=20,lgw=5$. המפתח באורך b יכול להיות 16, 24 או 32 בתים. הקלט והפלט הם מערכי 4 מילים בגודל 32 סיביות. S הוא מערך עזר בגודל 44 מילים.

#define ROTL(x,y) (((x)<<(y&(w-1))) | ((x)>>(w-(y&(w-1)))))
#define ROTR(x,y) (((x)>>(y&(w-1))) | ((x)<<(w-(y&(w-1)))))

void Setup(byte *key, int b, unsigned int *S)
{
   int i, j, s, v;
   unsigned int L[8], A, B;

   L[((b + 4 - 1) / 4) - 1] = 0;
   for (i = b - 1; i >= 0; i--)
      L[i / 4] = (L[i / 4] << 8) + key[i];

   S[0] = 0xB7E15163;
   for (i = 1; i <= 43; i++)
      S[i] = S[i - 1] + 0x9E3779B9;

   A = B = 0;
   i = j = 0;
   v = 44;
   if (((b + 4 - 1) / 4) > v) v = ((b + 4 - 1) / 4);
   v *= 3;

   for (s = 1; s <= v; s++)
   {
      A = S[i] = ROTL(S[i] + A + B, 3);
      B = L[j] = ROTL(L[j] + A + B, A + B);
      i = (i + 1) % 44;
      j = (j + 1) % ((b + 4 - 1) / 4);
   }
}

void Encrypt(unsigned int *pt, unsigned int *ct, unsigned int *S)
{
   unsigned int A = pt[0], B = pt[1], C = pt[2], D = pt[3];
   B += S[0], D += S[1];
   for (int i = 2; i <= 40; i += 2)
   {
      t = ROTL(B * (2 * B + 1), lgw);
      u = ROTL(D * (2 * D + 1), lgw);
      A = ROTL(A ^ t, u) + S[i];
      C = ROTL(C ^ u, t) + S[i + 1];
      x = A, A = B, B = C, C = D, D = x;
   }
   A += S[42], C += S[43];
   ct[0] = A, ct[1] = B, ct[2] = C, ct[3] = D;
}

void Decrypt(unsigned int *pt, unsigned int *ct, unsigned int *S)
{
   unsigned int A = ct[0], B = ct[1], C = ct[2], D = ct[3];
   C -= S[43], A -= S[42];
   for (int i = 40; i >= 2; i -= 2)
   {
      x = D, D = C, C = B, B = A, A = x;
      u = ROTL(D * (2 * D + 1), lgw);
      t = ROTL(B * (2 * B + 1), lgw);
      C = ROTR(C - S[i + 1], t) ^ u;
      A = ROTR(A - S[i], u) ^ t;
   }
   D -= S[1], B -= S[0];
   pt[0] = A, pt[1] = B, pt[2] = C, pt[3] = D;
}

ראו גם

• AES
• RC4

קישורים חיצוניים

• R.L. Pavan, M.J.B. Robshaw, R.Sidney, and Y.L. Yin, The RC6 Block Cipher, v1.1, August 1998