הצגת המקור של הדף "RC6"

{{צופן בלוקים
|תמונה=RC6Scheme.png
|כיתוב=תרשים צופן RC6. הסימן <math>\oplus</math> מייצג XOR הסימן <math>\boxplus</math> מייצג חיבור מודולו <math>2^w</math> הסימן <math>\lll</math> מייצג הזזה מעגלית לשמאל, ו-<math>f</math> מתייחס לפונקציה <math>f(x)=x\times (2x+1)</math>
|תכנון=[[רון ריבסט]], Matt Robshaw, Ray Sidney, Yiqun Lisa Yin
|פרסום=2000
|מבוסס על=[[RC5]]
|גרסאות מתקדמות=
|אורך מפתח=128/192/256 סיביות
|אורך בלוק=128 סיביות
|מבנה=[[רשת פייסטל]]
|מספר סבבים=20
|קריפטואנליזה=
}}
'''RC6''' הוא [[הצפנה|צופן]] [[צופן בלוקים|בלוקים]] [[צופן סימטרי|סימטרי]] שפותח ב-1998, על ידי [[רונלד ריבסט]] יחד עם [[Matt Robshaw]] ,[[Ray Sidney]] ו-[[Yiqun Lisa Yin]], מחברת [[RSA (חברה)|RSA]] ו-[[המכון הטכנולוגי של מסצ'וסטס|MIT]] עבור [[AES|תקן ההצפנה המתקדם]] שהחליף את [[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'''. גודל [[מילה (מחשב)|מילה]] הוא <math>w</math> סיביות, מספר הסבבים הוא <math>r</math> והמפתח בגודל <math>b</math> בתים, לצורך התקן נקבע <math>w=32, r=20 </math> והמפתח יכול להיות <math>b\in \{16,24,32\}</math> בתים. האלגוריתם פועל על ארבע מילים בגודל <math>w</math> תוך שימוש בפעולות הבאות:

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

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

===הצפנה===
<div class="mw-content-ltr">
:<math>B=B+S[0]</math>
:<math>D=D+S[1]</math>
:<math>\mbox{For }i=1\mbox{ to }r\mbox{ do:}</math>
::<math>t=(B \times (2B+1) \lll \mbox{lg }w</math>
::<math>u=(D \times (2D+1) \lll \mbox{lg }w</math>
::<math>A=((A \oplus t) \lll u)+S[2i]</math>
::<math>C=((C \oplus u) \lll t)+S[2i+1]</math>
::<math>(A,B,C,D)=(B,C,D,A)</math>
:<math>A=A+S[2r+2]</math>
:<math>C=C+S[2r+3]</math>
</div>

===פענוח===
<div class="mw-content-ltr">
:<math>C=C-S[2r+3]</math>
:<math>A=A-S[2r+2]</math>
:<math>\mbox{For }i=r\mbox{ downto }1\mbox{ do:}</math>
::<math>(A,B,C,D)=(D,A,B,C)</math>
::<math>u=(D \times (2D+1) \lll \mbox{lg }w</math>
::<math>t=(B \times (2B+1) \lll \mbox{lg }w</math>
::<math>C=((C - S[2i+1]) \ggg t) \oplus u</math>
::<math>A=((A - S[2i]) \ggg u) \oplus t</math>
:<math>D=D-S[1]</math>
:<math>B=B-S[0]</math>
</div>

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

<div class="mw-content-ltr">
:<math>S[0]=P_{32}</math>
:<math>\mbox{For }i=1\mbox{ to }2r+3\mbox{ do:}</math>
:<math>\{</math>
::<math>S[i]=S[i-1]+Q_{32}</math>
:<math>\}</math>
:<math>A=B=i=j=0</math>
:<math>v=3\times \mbox{max}\{c,2r+4\}</math>
:<math>\mbox{For }s=1\mbox{ to }v\mbox{ do:}</math>
:<math>\{</math>
::<math>A=S[i]=(S[i]+A+B) \lll 3</math>
::<math>B=L[j]=(L[j]+A+B) \lll (A+B)</math>
::<math>i=(i+1)\mbox{ modulo }(2r+4)</math>
::<math>j=(j+1)\mbox{ modulo }c</math>
:<math>\}</math>
</div>

==ביצועים וביטחון==
יישום צופן RC6 (על [[פנטיום]] 2) ב[[שפת c]] הגיע למהירות של כ-600 מחזורי שעון לבלוק או כ-5 מגה לשנייה. RC6 עולה בביצועיו על ריינדל במימוש בתוכנה{{הערה|[http://www.emc.com/emc-plus/rsa-labs/historical/rc6-block-cipher.htm RC6 and the AES]}} בעיקר על מחשב [[אינטל]] 32 סיביות. כמו יתר המועמדים (לפי דרישות התקן) מתאים ליישום גם בחומרה או במעבד [[כרטיס חכם]], אם כי לריינדל ביצועים טובים יותר בשטח זה. היות ש-RC6 אינו משתמש בתיבות החלפה מימוש האלגוריתם מאוד קומפקטי ויכול לאכלס פחות מ-256 בתים. הערכת המפתחים היא שההתקפה הטובה ביותר האפשרית כנגד הצופן, היא בסיבוכיות בין <math>2^{704}</math> ל-<math>2^{256}</math>.

==קוד לדוגמה==
להלן קוד [[C++]]{{D}} לא אופטימלי להמחשה. לפי פרמטרים: <math>w=32, r=20, lgw=5</math>. המפתח באורך b יכול להיות 16, 24 או 32 בתים. הקלט והפלט הם מערכי 4 מילים בגודל 32 סיביות. S הוא מערך עזר בגודל 44 מילים.
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

==ראו גם==
* [[AES]]
* [[RC4]]

==קישורים חיצוניים==
* R.L. Pavan, M.J.B. Robshaw, R.Sidney, and Y.L. Yin, [http://people.csail.mit.edu/rivest/pubs/RRSY98.pdf The RC6 Block Cipher], v1.1, August 1998

==הערות שוליים==
{{הערות שוליים|יישור=ימין}}

{{קריפטוגרפיה}}

[[קטגוריה:קריפטוגרפיה]]