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

Salsa20 הוא [[קריפטוגרפיה|צופן]] [[צופן זרם|זרם]] שפותח ב-2005 על ידי [[דניאל ברנשטיין]] ב[[אוניברסיטת אילינוי בשיקגו]]{{הערה|שם=עמוד הבית של צופן סלסה|[http://cr.yp.to/snuffle.html Snuffle 2005: the Salsa20 encryption function]}} והוצע עבור פרויקט [[eSTREAM]]{{הערה|[http://www.ecrypt.eu.org/stream/index.html eSTREAM: the ECRYPT Stream Cipher Project]}} [[אירופה|האירופאי]]. ב-2008 נבחר על ידי eSTREAM בסיבוב השלישי (Phase 3), כאחד מארבעת [[אלגוריתם|האלגוריתמים]] המובילים במסגרת פרופיל 1 בקטגוריית צופן זרם ב[[תוכנה]]. הגרעין של Salsa20 הוא [[פונקציה פסבדו-אקראית קריפטוגרפית|פונקציה פסאודו-אקראית]] הפועלת על [[קלט]] ופלט בגודל 64 [[בית (מחשב)|בתים]] ומיושמת כצופן זרם [[מצב הפעלה של צופן בלוקים#מצב CTR|במצב מונה]]. הפונקציה מקבלת מפתח הצפנה סודי באורך 128 או 256 סיביות, ערך ייחודי חד-פעמי באורך 64 סיביות הנקרא Nonce ומשמש כ[[וקטור אתחול]], מונה המייצג את מספר הבלוק באורך 64 סיביות וקבועים נוספים. על ידי גיבוב הערכים הללו כשהם משולבים יחד, מייצרת [[פלט]] פסאודו-אקראי באורך 64 בתים, אותו מחברים ב[[או מוציא|חיבור בינארי]] עם בלוק טקסט קריא לקבלת טקסט מוצפן. אפשר להצפין עם מפתח אחד עד <math>2^{70}</math> בתים של מידע. המבנה הזה מעניק לצופן יתרון ביכולת לשחזר כל בלוק ספציפי מהטקסט המוצפן בזמן קבוע. מימוש ממוטב של צופן Salsa יכול להגיע ליעילות בסדר גודל של כמעט 14 [[אות שעון|מחזורי שעון]] לבית או כ-643 מגה לשנייה (לעומת [[RC4]] שמגיע לסדר גודל של 200 מגה לשנייה בקירוב). נכון לשנת 2014 נחשב Salsa לצופן בטוח ולא ידוע על התקפה יעילה נגדו.

==תיאור האלגוריתם==
Salsa20 הוא צופן זרם סינכרוני (שבו המפתח מופק ללא תלות בטקסט הקריא או המוצפן), הפועל על יחידת מידע בגודל 64 בתים. השלד העיקרי מורכב מ[[פונקציית גיבוב קריפטוגרפית|פונקציית גיבוב]] הכוללת שילוב של שלוש פעולות אריתמטיות פשוטות; חיבור [[חשבון מודולרי|מודולו]] <math>2^{32}</math> המבוצע [[מילה (מחשב)|במילים]] בגודל 32 סיביות, חיבור מודולו 2 (המסומן [[XOR]]) ו[[הזזה מעגלית]] (rotation) על מילים (הזזה של כל סיביות המילה שמאלה או ימינה במספר פוזיציות לפי פרמטר, כאשר הסיביות הקיצוניות שנפלטות מצד אחד מוחזרות מהצד השני). ומפיקה פלט בגודל 64 בתים פסאודו-אקראיים שמרכיבים את 'המצב הפנימי' של הצופן. פונקציית הגיבוב הופכת לפונקציית הצפנה ב[[צופן ורנם|שיטת ורנם]], שבה תוצאת הגיבוב הופכת למפתח הצפנה מורחב בגודל 16 מילים. בלוק הטקסט הקריא בגודל 16 מילים מוצפן מילה אחר מילה, בדרך זו: <math>c_i=m_i\oplus k_i</math>. הפענוח זהה, כיוון ש-XOR הופכי של עצמו. סדר הפעולות בתוך הליבה של Salsa20 הוא "או-מוציא של חיבור לאחר הזזה מעגלית" בקיצור ARX (ראשי תיבות של שלוש הפעולות לפי הסדר האמור). שילוב זה הוכח כבטוח כנגד [[קריפטואנליזה דיפרנציאלית|התקפה דיפרנציאלית]] (ראה להלן) וכן מבטיח עמידות כנגד התקפת תזמון (timing attack). 

===המצב הפנימי===
את המצב ההתחלתי (initial state) של פונקציית הגיבוב של Salsa מאתחלים בערכים הבאים:

#'''8 מילות מפתח'''. מפתח ההצפנה המסופק על ידי המשתמש בסך הכול 256 סיביות, מחולק לשמונה מילים של 32 סיביות. במקרה של מפתח 128 סיביות מכפילים פעמיים לקבלת 8 מילים.
# '''2 מילות מונה'''. קידוד של [[מספר שלם]] בגודל 64 סיביות המזהה את מספר הבלוק הנוכחי, מתחיל באפס ומקודם באחד לאחר כל הצפנה של בלוק, כך שבכל הצפנה מתקבל מפתח אחר. המונה מאפשר לשחזר את זרם המפתח ששימש להצפנת בלוק נתון ובכך לפענחו ללא תלות בבלוקים האחרים.
#'''2 מילות Nonce'''. ערך ייחודי בגודל 64 סיביות המשמש פעם אחת בלבד עבור מסר נתון (המכיל בלוק אחד או יותר) ואינו בהכרח סודי. בדרך כלל בוחרים מספר פסאודו-אקראי או מספר רץ. בתקן eSTREAM הוא מכונה [[וקטור אתחול]] (iv). ערך זה מבטיח שלא יהיו שני מסרים שונים שיוצפנו באותו מפתח. ייחודיותו של ערך זה באחריות המשתמש.
#'''4 מילים קבועות'''. שהם (16 בתים) של קידוד [[מחרוזת (מדעי המחשב)|המחרוזת]] '''"expand 32-byte k"''' (כולל רווחים) במקרה של מפתח 256 סיביות, או המחרוזת '''"expand 16-byte k"''' במקרה של מפתח 128 סיביות. 

את הערכים המתוארים פורסים לתוך מצב הראשוני ב-64 בתים לפי הסדר הבא. אם המפתח הוא בגודל 256 סיביות (לפי ההמלצה של המַפַתֵּח דניאל ברנשטיין), תחילה ממירים את מחרוזות הטקסט הקבועות לארבע מילים לפי סדר בתים קטן, סך הכול ארבע אותיות במילה. למשל קוד ה[[אסקי]] של "e" הוא <math>101</math> ובייצוג הקסדצימלי <math>\mbox{0x65}</math>, של "x" הוא <math>\mbox{0x78}</math> ושל "p" <math>\mbox{0x70}</math> וכן הלאה. אחרי המרה של המחרוזת למילים ב[[בסיס הקסדצימלי|ייצוג הקסדצימלי]] מתקבל: 
:<math>\sigma_0=(\text{65,78,70,61}), \sigma_1=(\text{6E,64,20,33}), \sigma_2=(\text{32,2D,62,79}), \sigma_3=(\text{74,65,20,6B})</math> 

וקטור האתחול מיוצג על ידי <math>v</math> ומונה הבלוקים מיוצג על ידי <math>i</math>. אם המפתח בגודל 256 סיביות מחלקים אותו לשני מקטעים בני 16 בתים כל אחד <math>k_0,k_1</math> ומשרשרים את כל החלקים יחד במבנה הבא:
{| class="wikitable"
|-
!  ||1||2||3||4||5||6||7||8
|-
! בתים||1-4||5-20||21-24||25-32||33-40||41-44||45-60||61-64
|-
! ערך||<math>\sigma_0</math>||<math>k_0</math>||<math>\sigma_1</math>||<math>v</math>||<math>i</math>||<math>\sigma_2</math>||<math>k_1</math>||<math>\sigma_3</math>
|}

עבור מפתח 128 סיביות קיים רק מפתח <math>k</math> אחד בגודל 16 בתים וערכי המחרוזת "expand 16-byte k" בחלוקה למילים הם: 
:<math>\tau_0=(\text{65,78,70,61}), \tau_1=(\text{6E,64,20,31}), \tau_2=(\text{36,2D,62,79}), \tau_3=(\text{74,65,20,6B})</math>

והמבנה המתקבל הוא:
{| class="wikitable"
|-
!  ||1||2||3||4||5||6||7||8
|-
! בתים||1-4||5-20||21-24||25-32||33-40||41-44||45-60||61-64
|-
! ערך||<math>\tau_0</math>||<math>k</math>||<math>\tau_1</math>||<math>v</math>||<math>i</math>||<math>\tau_2</math>||<math>k</math>||<math>\tau_3</math>
|}


[[קובץ:QuarterRound.png|שמאל|ממוזער|260px|תיאור הפונקציה הפנימית QuarterRound של צופן Salsa]]

===פונקציית QuarterRound===
הפונקציה השוכנת בליבו של צופן סלסה <math>z_0,...,z_3=\mbox{QuarterRound}(y_0,...,y_3)</math> (ראו תרשים), היא [[פונקציה הפיכה]] המקבלת 4 מילים ומפיקה פלט של 4 מילים כדלהלן:
:<math>z_1=y_1\oplus ((y_0\boxplus y_3)\lll 7)</math>

:<math>z_2=y_2\oplus ((z_1\boxplus y_0)\lll 9)</math>

:<math>z_3=y_3\oplus ((z_2\boxplus z_1)\lll {13})</math>

:<math>z_0=y_0\oplus ((z_3\boxplus z_2)\lll {18})</math>

הסימן <math>\boxplus</math> מייצג חיבור מודולו <math>2^{32}</math>, הסימן <math>\lll</math> מייצג הזזה מעגלית של משתנה באורך 32 סיביות שמאלה במספר פוזיציות לפי הערך שלימינו והסימן <math>\oplus</math> מייצג XOR. לדוגמה בייצוג הקסדצימלי בחישוב <math>\mbox{QuarterRound}(1,0,0,0)</math> מתקבל: 
<math>(z_0=\text{0x8008145},z_1=\mbox{0x80},z_2=\text{0x10200},z_3=\text{0x20500000})</math>

===פונקציית RowRound===
הפונקציה RowRound מפעילה את הפונקציה QuarterRound על 16 מילים <math>y_0,...,y_{15}</math> באופן הבא:

:<math>(z_0, z_1, z_2, z_3) = \mbox{QuarterRound}(y_0, y_1, y_2, y_3)</math>
:<math>(z_5, z_6, z_7, z_4) = \mbox{QuarterRound}(y_5, y_6, y_7, y_4)</math>
:<math>(z_{10}, z_{11}, z_8, z_9) = \mbox{QuarterRound}(y_{10}, y_{11}, y_8; y_9)</math>
:<math>(z_{15}, z_{12}, z_{13}, z_{14}) = \mbox{QuarterRound}(y_{15}, y_{12}, y_{13}, y_{14})</math>

===פונקציית ColumnRound===
<div style="clear: left; float: left;" border="1">
<math>\begin{pmatrix} x_0 & x_1 & x_2 & x_3 \\ x_4 & x_5 & x_6 & x_7 \\ x_8 & x_9 & x_{10} & x_{11} \\ x_{12} & x_{13} & x_{14} & x_{15}  \end{pmatrix}</math>
</div>

אם מדמיינים את 16 הבתים לעיל, כמטריצה ריבועית 4x4 מילים (ראו תרשים), הפונקציה ColumnRound דומה לקודמת מלבד זאת שהיא מפעילה את QurterRound על עמודות המטריצה במקום שורות, כדלהלן:

:<math>(y_0, y_4, y_8, y_{12}) = \mbox{QuarterRound}(x_0, x_4, x_8, x_{12})</math>

:<math>(y_5, y_9, y_{13}, y_1) = \mbox{QuarterRound}(x_5, x_9, x_{13}, x_1)</math>

:<math>(y_{10}, y_{14}, y_2, y_6) = \mbox{QuarterRound}(x_{10}, x_{14}, x_2, x_6)</math>

:<math>(y_{15}, y_3, y_7, y_{11}) = \mbox{QuarterRound}(x_{15}, x_3, x_7, x_{11})</math>

===פונקציית DoubleRound===
שתי הפונקציות המתוארות כשהן משולבות יחד נקראות DoubleRound דהיינו כל מילה מעובדת פעמיים, פעם אחת כחלק משורות במטריצה ופעם אחת כעמודות, בניסוח פורמלי: <math>\mbox{DoubleRound}(x_0,...,x_{15})=\mbox{RowRound}(\mbox{ColumnRound}(x_0,...,x_{15}))</math>. 

כמו כן, לצורך הפעולות האריתמטיות, המעבר ממערך של ארבעה בתים למילה אחת הוא לפי [[סדר בתים]] קטן שאומר שהבית הראשון מייצג את הספרות הפחות משמעותיות של המילה, לכן במחשב עם סדר בתים גדול, יש צורך בפונקציית המרה כדי להמיר מבתים למילים ובחזרה לפי הנוסחה: <math>b_0+2^8b_1+2^{16}b_2+2^{24}b_3</math>. לדוגמה אם נתון מערך הבתים: <math>\{ b_0=86,b_1=75,b_2=30,b_3=9 \} </math> בהמרה למילה בת 32 סיביות לפי סדר בתים קטן, יתקבל הערך <math>152,980,310</math> (לפי סדר בתים גדול מתקבל <math>1,447,763,456</math>).

אם מסכמים את כל הפעולות יחד, מימוש הפונקציה DoubleRound ייראה כך:
<center>
<div class="mw-content-ltr">
:{| class="wikitable"
|-
! ColumnRound !! RowRound
|-
| 
:<math>x_{4} = x_{4} \oplus \mbox{ROTL}_{7}(x_{0} \boxplus x_{12})</math>
:<math>x_{8} = x_{8} \oplus \mbox{ROTL}_{9}(x_{4} \boxplus x_{0})</math>
:<math>x_{12} = x_{12} \oplus \mbox{ROTL}_{13}(x_{8} \boxplus x_{4})</math>
:<math>x_{0} = x_{0} \oplus \mbox{ROTL}_{18}(x_{12} \boxplus x_{8})</math>
:<math>x_{9} = x_{9} \oplus \mbox{ROTL}_{7}(x_{5} \boxplus x_{1})</math>
:<math>x_{13} = x_{13} \oplus \mbox{ROTL}_{9}(x_{9} \boxplus x_{5})</math>
:<math>x_{1} = x_{1} \oplus \mbox{ROTL}_{13}(x_{13} \boxplus x_{9})</math>
:<math>x_{5} = x_{5} \oplus \mbox{ROTL}_{18}(x_{1} \boxplus x_{13})</math>
:<math>x_{14} = x_{14} \oplus \mbox{ROTL}_{7}(x_{10} \boxplus x_{6})</math>
:<math>x_{2} = x_{2} \oplus \mbox{ROTL}_{9}(x_{14} \boxplus x_{10})</math>
:<math>x_{6} = x_{6} \oplus \mbox{ROTL}_{13}(x_{2} \boxplus x_{14})</math>
:<math>x_{10} = x_{10} \oplus \mbox{ROTL}_{18}(x_{6} \boxplus x_{2})</math>
:<math>x_{3} = x_{3} \oplus \mbox{ROTL}_{7}(x_{15} \boxplus x_{11})</math>
:<math>x_{7} = x_{7} \oplus \mbox{ROTL}_{9}(x_{3} \boxplus x_{15})</math>
:<math>x_{11} = x_{11} \oplus \mbox{ROTL}_{13}(x_{7} \boxplus x_{3})</math>
:<math>x_{15} = x_{15} \oplus \mbox{ROTL}_{18}(x_{11} \boxplus x_{7})</math>
||
:<math>x_{1} = x_{1} \oplus \mbox{ROTL}_{7}(x_{0} \boxplus x_{3})</math>
:<math>x_{2} = x_{2} \oplus \mbox{ROTL}_{9}(x_{1} \boxplus x_{0})</math>
:<math>x_{3} = x_{3} \oplus \mbox{ROTL}_{13}(x_{2} \boxplus x_{1})</math>
:<math>x_{0} = x_{0} \oplus \mbox{ROTL}_{18}(x_{3} \boxplus x_{2})</math>
:<math>x_{6} = x_{6} \oplus \mbox{ROTL}_{7}(x_{5} \boxplus x_{4})</math>
:<math>x_{7} = x_{7} \oplus \mbox{ROTL}_{9}(x_{6} \boxplus x_{5})</math>
:<math>x_{4} = x_{4} \oplus \mbox{ROTL}_{13}(x_{7} \boxplus x_{6})</math>
:<math>x_{5} = x_{5} \oplus \mbox{ROTL}_{18}(x_{4} \boxplus x_{7})</math>
:<math>x_{11} = x_{11} \oplus \mbox{ROTL}_{7}(x_{10} \boxplus x_{9})</math>
:<math>x_{8} = x_{8} \oplus \mbox{ROTL}_{9}(x_{11} \boxplus x_{10})</math>
:<math>x_{9} = x_{9} \oplus \mbox{ROTL}_{13}(x_{8} \boxplus x_{11})</math>
:<math>x_{10} = x_{10} \oplus \mbox{ROTL}_{18}(x_{9} \boxplus x_{8})</math>
:<math>x_{12} = x_{12} \oplus \mbox{ROTL}_{7}(x_{15} \boxplus x_{14})</math>
:<math>x_{13} = x_{13} \oplus \mbox{ROTL}_{9}(x_{12} \boxplus x_{15})</math>
:<math>x_{14} = x_{14} \oplus \mbox{ROTL}_{13}(x_{13} \boxplus x_{12})</math>
:<math>x_{15} = x_{15} \oplus \mbox{ROTL}_{18}(x_{14} \boxplus x_{13})</math>
|}
</div>
</center>
הפונקציה <math>\mbox{ROTL}</math> היא פונקציית הזזה מעגלית לשמאל והמספר התחתי מציין את מספר הפוזיציות שיש להזיז. הזזה מעגלית ניתנת ליישום בתוכנה בקריאה לפונקציית ספרייה או באמצעות הזזות Shift ו-[[או (לוגיקה)|OR]] המובנות ברוב שפות התיכנות, למשל ב[[שפת C]] הביטוי: '''<tt>(value << count) | (value >> (32 - count))</tt>''' מבצע הזזה מעגלית של '''<tt>value</tt>''' במספר פוזיציות לפי '''<tt>count</tt>'''.

===פונקציית הגיבוב===
פונקציית הגיבוב של Salsa משלבת את הפונקציות האמורות על קלט בגודל 64 בתים, כדי להפיק פלט של 64 בתים פסאודו-אקראיים. בניסוח פורמלי אם נתון המצב הראשוני <math>x</math> המתואר לעיל, הנוסחה היא:
:<math>\mbox{Salsa20}(x_0,...,x_{15})=(x_0,...,x_{15})+\mbox{DoubleRound}^{10}(x_0,...,x_{15})</math>. 

כלומר מחלקים את הקלט <math>x</math> ל-16 מילים <math>x_0</math> עד <math>x_{15}</math>, אותם מחשבים באמצעות פונקציית DoubleRound עשר פעמים. ופלט הפונקציה הוא תוצאת החיבור מודולו <math>2^{32}</math> עם מילות המצב הראשוני <math>x_0</math> עד <math>x_{15}</math>. המציין מעל הפונקציה DoubleRound מייצג את מספר החזרות. כיוון שהפונקציה הפנימית מבוצעת פעמיים (בשורות ובעמודות) מסומן הצופן בקיצור Salsa20, כלומר ביצוע <math>\mbox{DoubleRound}^{10}</math>, נחשב כ-20 סבבים. כאשר מעוניינים בפונקציית הצפנה מהירה יותר על חשבון ביטחון אפשר להפחית במספר הסבבים. האופציות המומלצות הן 8 או 12 סבבים.

===הצפנה ופענוח===
עם פלט פונקציית הגיבוב Slasa20 המתוארת, אפשר להצפין מסר <math>m</math> באורך מקסימלי של <math>2^{70}</math> בתים כשהוא מחולק לבלוקים בגודל 64 בתים, עם וקטור האתחול <math>v</math>, המונה <math>i</math>  כאשר <math>0 \le i \le 2^{64}-1</math> והמפתח <math>k</math> באופן הבא:

:<math>c_i=\mbox{Salsa20}_k(v,i)\oplus m_i</math>. 

לאחר הצפנת <math>2^{70}</math> בתים יש לאתחל את הצופן עם וקטור אתחול חדש ולהתחיל את המונה מאפס או להחליף מפתח. כאמור <math>v</math> לא חייב להיות סודי אך חייב להיות ייחודי. מעשית יכול להיות מונה כלשהו. לפענוח פועלים באופן זהה לחלוטין:
:<math>m_i=\mbox{Salsa20}_k(v,i)\oplus c_i</math>.

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

==ביטחון ויעילות==
ב-2005 דווח על סוג של ההתקפה [[קריפטואנליזה דיפרנציאלית|דיפרנציאלית]] נגד גרסה מצומצמת של סלסה בחמשה סבבים, מסומן בקיצור Salsa20/5 ב[[סיבוכיות]] זמן של <math>2^{165}</math> בקירוב. מפתח ההתקפה זכה באלף דולר מאת דניאל ברנשטיין שהבטיח את הפרס לכל מי שיצליח להציג "[[קריפטואנליזה]] הכי מעניינת של סלסה"{{הערה|שם=Paul Crowley|[http://www.ciphergoth.org/crypto/salsa20/ Truncated differential cryptanalysis of five rounds of Salsa20]}}. ב-2006 הצליחו מספר חוקרים לפתח התקפה כנגד Salsa20/6 בסיבוכיות זמן של <math>2^{177}</math> וכן התקפת Related key על Salsa20/7 בזמן של <math>2^{217}</math>{{הערה|Simon Fischer, Willi Meier, Côme Berbain, Jean-Francois Biasse, Matt Robshaw, Non-Randomness in eSTREAM Candidates Salsa20 and TSC-4, Indocrypt 2006}}. ב-2007 פותחה התקפה על Salsa20/8 בזמן של <math>2^{255}</math> עם <math>2^{11.37}</math> מפתחות{{הערה|[http://www.ecrypt.eu.org/stream/papersdir/2007/010.pdf Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima (2007-01-02)]}}. ב-2008 פותחה התקפה נגד Salsa20/7 בזמן של <math>2^{153}</math> וכן התקפה על Salsa20/8 בזמן של <math>2^{251}</math>. ב-2012 התקפה של אמסון ושי כנגד Salsa20/8 הצליחה לשבור את הצופן בזמן של <math>2^{109}</math> או בזמן של <math>2^{250}</math> במקרה של מפתח 256 סיביות עם 8 סבבים{{הערה|Zhenqing Shi, Bin Zhang, Dengguo Feng, Wenling Wu (2012): „Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha“. Information Security and Cryptology – ICISC 2012. Springer Verlag, 2013, pp. 337-351}}. ב-2013 פורסמה הוכחה{{הערה|[http://eprint.iacr.org/2013/328.pdf Nicky Mouha, Bart Preneel (2013)]}} שצופן סלסה מעל 15 סבבים בטוח כנגד התקפה דיפרנציאלית, כלומר לא נמצאו מאפיינים דיפרנציאליים בהסתברות גבוהה מ-<math>2^{-130}</math> כך שהיא אינה יעילה מ[[כוח גס]].

Salsa20 מהיר יותר מ-[[AES]] ו[[בוחן ביצועים|במבחני ביצועים]] של eSTREAM{{הערה|[https://cr.yp.to/snuffle/salsafamily-20071225.pdf The Salsa20 family of stream ciphers]}} נמצא שבעשרים סבבים הצופן מסוגל להצפין בקצב של 3.93 מחזורי שעון לבית על [[Xeon]] בעל ליבה כפולה 3 גיגה-הרץ. כמו כן קיימות שתי גרסאות של הצופן פחותות סבבים הנקראות Salsa20/8 ו-Salsa20/12 עם שמונה סבבים או 12 סבבים בהתאמה, המיועדים למשתמשים הרואים צורך בצופן יעיל ומוכנים להקריב מעט בביטחונו.

==ChaCha==
ב-2008 הציע דניאל ברנשטיין את משפחת ChaCha{{הערה|[https://cr.yp.to/chacha.html The ChaCha family of stream ciphers]}} שהיא גרסה משופרת של צפני זרם החולקת אותם עקרונות תכנון עם Salsa20 אך בשינויים קלים שנועדו בעיקר להגברת רמת הפיזור (diffusion) של הצופן. הפיזור הנוסף אינו בא על חשבון ביצועים, כמו ב-Salsa20 בכל סבב מתבצעים 16 פעולות חיבור, XOR והזזה מעגלית בהיסטים קבועים וכן נשמרת אותה רמת מקביליות ואף יותר. ההערכה היא שגרסאות ChaCha מספקות עמידות גבוהה יותר נגד קריפטואנליזה ומשפרות במעט את הביצועים אם כי רק על פלטפורמות מסוימות. בגלל אחידות כמות העבודה בכל סבב, למספר הסבבים השפעה ישירה על ביצועי הצופן. מסיבה זו הוצעו גרסאות מופחתות סבבים לשיפור ביצועים על חשבון ביטחון. ChaCha8 מבוסס על Salsa20 עם שמונה סבבים, ChaCha12 על Salsa20 עם 12 סבבים בהתאמה. ההבדלים בין צופן Salsa וצופן ChaCha הם כדלהלן:

===פונקציית QuarterRound===
פונקציית הסבב הפנימית של ChaCha גם היא מבצעת 4 פעולות חיבור, 4 פעולות XOR ו-4 פעולות הזזה מעגלית על ארבעה משתני המצב הפנימי אך בסדר שונה. ב-Salsa20 כל משתנה מעודכן בפעולה אחת למשל <math>b=b\oplus ((a\boxplus d)\lll 7)</math>. לעומתו ב-ChaCha כל מילה מעודכנת פעמיים בנפרד, כך שכל מילת קלט משפיעה על מילות קלט אחרות בשני הכיוונים. אפשר לראות על ידי מעקב אחרי כל סיבית כי ב-ChaCha לפחות 12.5 סיביות בממוצע משתנות בכל סבב לעומת רק 8 ב-Salsa20.
<center>
<div class="mw-content-ltr">
{|
|-
| 
:<math>a = a + b,\ \ d = d\oplus a,\ \  d = d\lll 16</math>
:<math>c = c + d,\ \ b = b\oplus c,\ \ \  b = b\lll 12</math>
:<math>a = a + b,\ \ d = d\oplus a,\ \  d = d\lll 8</math>
:<math>c = c + d,\ \ b = b\oplus c,\ \ \ b = b\lll 7</math>
|}
</div>
</center>
בנוסף קיים הבדל פחות משמעותי בערכי ההיסטים הקבועים של ההזזה המעגלית 16,12,8,7 לעומת 7,9,13,18 ב-Salsa20. ההשפעה של הבדל זה על ביטחון הצופן זניחה. לעומת זאת קיים שיפור במהירות על פלטפורמות מסוימות.

===מטריצת הקלט===
בצופן Salsa20 הקלט המורכב מוקטור אתחול ומונה בלוקים וכן שמונה מילות מפתח וארבע מילים קבועות, נטענים לתוך טבלה או [[מטריצה]] ראשונית <math>4\times 4</math> במבנה זה:
<center>
{| class="wikitable"
|-
| קבוע || מפתח || מפתח || מפתח
|-
| מפתח || קבוע || קלט || קלט
|-
| קלט || קלט || קבוע || מפתח
|-
| מפתח || מפתח || מפתח || קבוע
|}
</center>
בכל הרצה של הצופן הפונקציה הפנימית מעבדת במקביל את עמודות המטריצה האמורה <math>r</math> פעמים ואז מחברת את התוצאה הסופית עם המטריצה הראשונית לקבלת 16 מילים של הפלט. במימושי תוכנה ממוטבים של Salsa20 נהוג היה לבצע תחילה תמורה פנימית של המטריצה הראשונית כך שהעמודה השנייה מוסטת שורה אחת כלפי מעלה, העמודה השלישית שתי שורות כלפי מעלה והרביעית שלוש ומתקבל:
<center>
{| class="wikitable"
|-
| קבוע || קבוע || קבוע || קבוע
|-
| מפתח || קלט || מפתח || מפתח
|-
| קלט || מפתח || מפתח || קלט
|-
| מפתח || מפתח || קלט || מפתח
|}
</center>
השפעת השינוי על ביטחון הצופן זניחה, לעומת זאת חל שיפור בביצועים כיוון שכעת ניתן לממש ארבעה רבעים של הפונקציה הפנימית בהוראת SIMD אחת על וקטורים (ראה [[עיבוד מקבילי]]). הרעיון הוא שהיות שהפונקציה הפנימית מופעלת על כניסות המטריצה באלכסונים, ההיסט גורם לכך שהאלכסון יהפוך לעמודה ואז ניתן להבצע את החישוב בפקודה אחת. שינוי דומה נעשה בסבב השני וכן הסבב השלישי כמו הראשון והרביעי כמו השני. רעיון דומה נעשה ב-ChaCha מאותה סיבה אך בשלושה שינויים. תחילה נעשה השינוי בסדר המילים בבלוק הפלט כדי להתאימו לשינוי המתואר לעיל. זאת על מנת לשפר ביצועים על פלטפורמות התומכות ב-SIMD. בנוסף המטריצה הראשונית מסודרת אחרת:
<center>
{| class="wikitable"
|-
| קבוע || קבוע || קבוע || קבוע
|-
| מפתח || מפתח || מפתח || מפתח
|-
| מפתח || מפתח || מפתח || מפתח
|-
| קלט || קלט || קלט || קלט
|}
</center>
הנתונים פשוט נטענים לפי סדר קליטתם כאשר הקלט שהוא בשליטת המשתמש (וכן התוקף במקרה של קריפטואנליזה) מוצב בשורה האחרונה. הסבב הראשון תחילה מחבר את הקבועים למפתחות ואז מבצע XOR של התוצאות עם הקלטים, מבצע הזזה מעגלית ושוב מחבר עם המפתחות וכן הלאה. השינוי השלישי הוא, עיבוד השורות מתבצע באותו סדר בכל הסבבים לפי המוצג בתרשים הבא:
<center>
<div class="mw-content-ltr">
{|
|-
| <math>\text{QuarterRound}(x_0\ ,x_4\ ,x_8\ ,x_{12})</math>
|-
| <math>\text{QuarterRound}(x_1\ ,x_5\ ,x_9\ ,x_{13})</math>
|-
| <math>\text{QuarterRound}(x_2\ ,x_6\ ,x_{10},x_{14})</math>
|-
| <math>\text{QuarterRound}(x_3\ ,x_7\ ,x_{11},x_{15})</math>
|-
| <math>\text{QuarterRound}(x_0\ ,x_5\ ,x_{10},x_{15})</math>
|-
| <math>\text{QuarterRound}(x_1\ ,x_6\ ,x_{11},x_{12})</math>
|-
| <math>\text{QuarterRound}(x_2\ ,x_7\ ,x_8\ ,x_{13})</math>
|-
| <math>\text{QuarterRound}(x_3\ ,x_4\ ,x_9\ ,x_{14})</math>
|}
</div>
</center>
ארבעת הרבעים של כל סבב תמיד מסודרים מלמעלה למטה מה שמוסיף מהיבט של מהירות. פונקציית הגיבוב [[BLAKE]] הנמנית עם רשימת הפינלסטים של תחרות הגיבוב של NIST וגרסת ההמשך שלה BLAKE2 מבוססים על ChaCha.

===שימושים===
ב-2014 אימצה [[גוגל (חברה)|גוגל]] את ChaCha יחד עם [[קוד אימות מסרים]] [[Poly1305]] כתחליף ל-[[RC4]] ב-[[OpenSSL]]{{הערה|[https://tools.ietf.org/html/draft-ietf-tls-chacha20-poly1305-04 ChaCha20-Poly1305 Cipher Suites for Transport Layer Security (TLS)  draft-ietf-tls-chacha20-poly1305-04]}}. כמו כן המימוש של גוגל עבור [[TLS (פרוטוקול)|TLS]]{{הערה|[http://www.infosecurity-magazine.com/news/google-swaps-out-crypto-ciphers-in-openssl/ Google Swaps Out Crypto Ciphers in OpenSSL]}} משמש להגנה על תעבורת הרשת (HTTPS) בין [[דפדפן]] כרום ל[[אנדרואיד (מערכת הפעלה)|אנדרואיד]] לבין אתרי גוגל. באופן דומה האלגוריתם שולב בפרוטוקול [[OpenSSH]]. הצופן ChaCha נכלל גם במערכות ההפעלה [[OpenBSD]] ו-[[NetBSD]]{{הערה|[http://bxr.su/OpenBSD/usr.bin/ssh/PROTOCOL.chacha20poly1305 Super User's BSD Cross Reference: PROTOCOL.chacha20poly1305]}}. וכן הוצע לפרוטוקול [[IPSec]] בטיוטה {{RFC|7539}} וטיוטה {{RFC|7634}}. פונקציית הגיבוב [[BLAKE]] מבוססת על ליבת צופן ChaCha בשינויים מינוריים.

==קוד לדוגמה==
להלן קוד [[C++]]{{D}} שלם של צופן ChaCha20 המלא (20 סבבים). למען הבהירות הקוד אינו ממוטב והוא תואם את ההמלצה המופיעה באתר המפתח{{הערה|[https://cr.yp.to/chacha.html The ChaCha family of stream ciphers]}}. ההנחה שה[[מהדר]] תומך ב[[סדר בתים]] קטן. הפונקציה {{D}}_lrotl{{D}}  היא  פונקציית [[הזזה מעגלית]] לשמאל הכלולה בספרייה הסטנדרטית של [[ויז'ואל סטודיו|VS]]. אפשר לשנות את מספר הסבבים בפונקציה ChaCha_encrypt בקריאה לפונקציה Salsa20_Rounds בהתאם לצורך, למשל לגרסת שמונה סבבים יש לציין 8 בפרמטר האחרון, ערכים מומלצים הם 8,12 או 20.
<syntaxhighlight lang="CPP">
typedef unsigned char byte;
typedef unsigned int uint;

#define BYTES_TO_INT(p) (((uint*)(p))[0])
#define INT_TO_BYTES(p, v) (((uint*)(p))[0] = (v))
#define ROTATE(v,c) (_lrotl(v, c))
#define XOR(v,w) ((v) ^ (w))
#define PLUS(v,w) ( (uint)(((v) + (w)) & 0xFFFFFFFF))
#define PLUSONE(v) (PLUS((v),1))

typedef struct
{
   uint input[16];
} ChaCha_Context;

#define QUARTERROUND(a,b,c,d) \
  x[a] = PLUS(x[a],x[b]); x[d] = ROTATE(XOR(x[d],x[a]),16); \
  x[c] = PLUS(x[c],x[d]); x[b] = ROTATE(XOR(x[b],x[c]),12); \
  x[a] = PLUS(x[a],x[b]); x[d] = ROTATE(XOR(x[d],x[a]), 8); \
  x[c] = PLUS(x[c],x[d]); x[b] = ROTATE(XOR(x[b],x[c]), 7);

static const char sigma[] = "expand 32-byte k";
static const char tau[] = "expand 16-byte k";

static void Salsa20_Rounds(byte output[64], const uint input[16], uint nrounds)
{
	uint x[16];

	for (uint i = 0; i < 16; ++i) 
		x[i] = input[i];

	for (uint i = nrounds; i > 0; i -= 2) {
		QUARTERROUND( 0, 4,  8, 12)
		QUARTERROUND( 1, 5,  9, 13)
		QUARTERROUND( 2, 6, 10, 14)
		QUARTERROUND( 3, 7, 11, 15)
		QUARTERROUND( 0, 5, 10, 15)
		QUARTERROUND( 1, 6, 11, 12)
		QUARTERROUND( 2, 7,  8, 13)
		QUARTERROUND( 3, 4,  9, 14)
	}
	for (uint i = 0; i < 16; ++i) 
		x[i] = PLUS(x[i], input[i]);

	for (uint i = 0; i < 16; ++i) 
		INT_TO_BYTES(output + 4 * i, x[i]);
}


void ChaCha_keysetup(ChaCha_Context *ctx, const byte *k, uint kbits, uint ivbits)
{
	const char *constants;

	ctx->input[4] = BYTES_TO_INT(k + 0);
	ctx->input[5] = BYTES_TO_INT(k + 4);
	ctx->input[6] = BYTES_TO_INT(k + 8);
	ctx->input[7] = BYTES_TO_INT(k + 12);

	if (kbits == 256) { // recommended
		k += 16;
		constants = sigma;
	}
	else { // kbits == 128
		constants = tau;
	}
	ctx->input[8] = BYTES_TO_INT(k + 0);
	ctx->input[9] = BYTES_TO_INT(k + 4);
	ctx->input[10] = BYTES_TO_INT(k + 8);
	ctx->input[11] = BYTES_TO_INT(k + 12);
	ctx->input[0] = BYTES_TO_INT(constants + 0);
	ctx->input[1] = BYTES_TO_INT(constants + 4);
	ctx->input[2] = BYTES_TO_INT(constants + 8);
	ctx->input[3] = BYTES_TO_INT(constants + 12);
}

void ChaCha_ivsetup(ChaCha_Context *ctx, const byte *iv)
{
	ctx->input[12] = 0;
	ctx->input[13] = 0;
	ctx->input[14] = BYTES_TO_INT(iv + 0);
	ctx->input[15] = BYTES_TO_INT(iv + 4);
}

void ChaCha_encrypt(ChaCha_Context *ctx, const byte *m, byte *c, uint bytes)
{
	byte output[64];

	if (!bytes) return;
	for (;;) {
		Salsa20_Rounds(output, ctx->input, 20);
		ctx->input[12] = PLUSONE(ctx->input[12]);
		if (!ctx->input[12]) {
			ctx->input[13] = PLUSONE(ctx->input[13]);
			// stopping at 2^70 bytes per nonce is user's responsibility
		}
		if (bytes <= 64) {
			for (uint i = 0; i < bytes; ++i) c[i] = m[i] ^ output[i];
			return;
		}
		for (uint i = 0; i < 64; ++i) c[i] = m[i] ^ output[i];
		bytes -= 64;
		c += 64;
		m += 64;
	}
}
</syntaxhighlight>

==וקטור בדיקה==
מפתח (32 בתים):
{|
|-
|
:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
|}

וקטור אתחול (8 בתים):
{|
|-
|
:00 00 00 00 00 00 00 00
|}

מספר סבבים: 20

64 בתים פסאודו אקראיים הראשונים של פלט הצופן ב[[בסיס הקסדצימלי]]:
{|
|-
|
:<div class="mw-content-ltr">76 b8 e0 ad a0 f1 3d 90 40 5d 6a e5 53 86 bd 28</div>
:<div class="mw-content-ltr">bd d2 19 b8 a0 8d ed 1a a8 36 ef cc 8b 77 0d c7</div>
:<div class="mw-content-ltr">da 41 59 7c 51 57 48 8d 77 24 e0 3f b8 d8 4a 37</div>
:<div class="mw-content-ltr">6a 43 b8 f4 15 18 a1 1c c3 87 b6 69 b2 ee 65 86</div>
|}

==ראו גם==
* [[צופן זרם]]
* [[RC4]]

==קישורים חיצוניים==
* {{אתר רשמי}}

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


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

[[קטגוריה:צפני זרם]]