הצגת המקור של הדף "SHA-3"

'''SHA-3''', השלישית במשפחת [[אלגוריתם|האלגוריתמים]] [[SHA|Secure Hash Algorithm]] (בשמו המקורי '''Keccak'''{{הערה|שם=תחרות |[http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html NIST בחרה את הזוכה בתחרות אלגוריתם הגיבוב (SHA-3)] - הודעה לעיתונות באתר [[NIST]]}}), היא [[פונקציית גיבוב קריפטוגרפית]] שפותחה ב-2008 על ידי [[גוידו ברטוני]], [[יוהאן דאמן]] (ממפתחי [[AES]]), [[מיכאל פיטרס]] ו[[ג'יל ואן אשה]], ונבחרה על ידי [[NIST]] כתקן גיבוב פדרלי של ממשלת [[ארצות הברית]].

פונקציית גיבוב היא מרכיב חיוני בכל מערכת [[קריפטוגרפיה|קריפטוגרפית]] מודרנית. הפונקציה מפיקה ממסר בכל אורך רצוי, ערך ייחודי בגודל קבוע שנקרא "ערך גיבוב" או "תמצית המסר" ומטרתו להוות '''ייצוג קומפקטי''' או טביעת אצבע דיגיטלית של המסר.

==תחרות תקן הגיבוב==
המניע מאחורי פיתוח תקן SHA-3 הוא התפתחותן של טכניקות קרפיטואנליטיות חדשות וחשיפת חולשות תאורטיות ומעשיות באלגוריתמים הקודמים במשפחה [[MD5]] וכן SHA-0 והתקפה תאורטית על SHA-1. ב-NIST ראו צורך לפתח פונקציית גיבוב חדשה שונה במבנה ובקונספט מקודמותיה, על מנת להרחיב את היצע הפונקציות במשפחה, וסימונה יהיה SHA-3. לאור זאת הוחלט בנובמבר 2007 על תחרות פתוחה לציבור לפיתוח פונקציית גיבוב קריפטוגרפית שתשמש כתקן גיבוב ממשלתי (בדומה לתחרות לבחירת תקן [[AES]] שבסופה נבחר [[צופן בלוקים|צופן הבלוקים]] Rijndael). באוקטובר 2008 הצטברו 64 הצעות של מומחי [[הצפנה]] מכל העולם, מתוכם נבחרו 51 מועמדים לסבב הראשון לאחר שכמה מהם נפסלו כי לא עמדו בתנאי הסף{{הערה|[http://csrc.nist.gov/groups/ST/hash/sha-3/index.html תחרות פונקציית הגיבוב הקריפטוגרפית] - תיאור כללי באתר [[NIST]]}}. ביולי 2009 הצטמקה הרשימה הנבחרת לסבב השני ל-14 מועמדים, ההכרזה בוצעה באמצעות [[אימייל]] שנשלח ל[[רשימת תפוצה|רשימת התפוצה]] של התחרות.

הקריטריונים בהם נעזר חבר השופטים היו: בטיחות האלגוריתם, [[סיבוכיות זמן|עלות החישוב]] ומדידת ביצועים ומאפיינים הקשורים במימוש. חבר השופטים ציין במפורש שאף אחד מהאלגוריתמים שנבחרו לשלב השני לא נשבר במלואו. NIST אפשרה למועמדים שעברו לשלב זה לבצע שינויים קלים (Tweaks) באלגוריתמים שהגישו אך לא כאלה שיהפכו התקפות קיימות לבטלות{{הערה|[http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/index.html תחרות SHA-3 - שלב 2], באתר [[NIST]]}}.

בדצמבר 2010 הגיעו לגמר חמישה מועמדים מובילים:
*'''Keccak'''
*[[Skein]]
*[[JH]]
*[[Grøstl]]
*[[BLAKE]]

הקהילה הקריפטוגרפית הייתה מעורה בשיקולים וההתלבטות במהלך התחרות. הערות והצעות רבות נשלחו ל-NIST או לפורום הגיבוב שהוקם למטרה זו וכן פורסמו מאמרים אקדמיים של [[קריפטואנליזה]] של המועמדים על ידי מומחים בעלי שם מסביב לעולם. באוקטובר 2012 נסגרה התחרות עם ההכרזה על האלגוריתם הזוכה{{הערה|שם=תחרות }}.

משפחת האלגוריתמים SHA-3 הוכנסה לתקן FIPS PUB 202{{הערה|[http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions]}} של [[NIST]] והיא כוללת שישה אלגוריתמים בגדלים שונים בהתאם, SHA3-224,{{כ}} SHA3-256,{{כ}} SHA3-384 ו-SHA3-512 וכן שתי פונקציות הרחבה הנקראות XOF והן SHAKE128 ו-SHAKE256. תקן FIPS 202 אושר על ידי מנהל [[מחלקת המסחר של ארצות הברית]] באוגוסט 2015.

כל החישובים בפונקציית הגיבוב, מוגבלים לפעולות [[AND]],{{כ}} [[NOT]],{{כ}} [[XOR]] ו[[הזזה מעגלית]] (Rotate), ללא פעולות [[אריתמטיקה|אריתמטיות]] או פונקציות המבוססות על מידע חיצוני. וכן אין צורך ליישם טבלאות חיפוש לצורך האצת החישובים. לפי הצהרת המפתחים נדרשים 12.5 [[אות שעון|מחזורי שעון]] ל[[בית (מחשב)|בית]] ב[[מעבד]] [[אינטל]] ליבה כפולה. בגרסת החומרה שלו האלגוריתם הפגין ביצועים טובים יותר מכל המועמדים האחרים.

SHA-3 אמור להצטרף למשפחת אלגוריתמי [[SHA]] כדי להרחיב את ההיצע של משפחה זו. בדומה ל-[[AES]], התקן מפותח בשיטה של תחרות בינלאומית פתוחה בה מנסים חוקרי [[קריפטוגרפיה]] למצוא חולשות באלגוריתמים שהוגשו לתחרות. האלגוריתם אינו אמור להחליף את קודמו [[SHA-2]], אלא מיועד להגדיל את היצע הפונקציות.

==Keccak==
[[קובץ:Keccak State.png|200px|ממוזער|שמאל|תיאור המצב הפנימי של Keccak. נתיב (lane) הוא שורה אחת לאורך ציר ה-z]]
אלגוריתם Keccak (מבוטא קֵצַ'אק, על שם ריקוד [[באלי]]נזי עתיק) פותח ב-2008 על ידי Guido Bertoni, Joan Daemen, Michaël Peeters ו-Gils Van Assche{{הערה|[http://keccak.noekeon.org/ The Keccak sponge function family]}}. זוהי משפחה של פונקציות גיבוב המבוססת על [[פונקציית ספוג]] שהיא מבנה גנרי שהומצא במהלך פיתוח אלגוריתם [[RadioGatun]]. ב-Keccak הפונקציה הפנימית <math>f</math> היא [[תמורה (מתמטיקה)|פרמוטציה]] אחת מתוך אוסף של שבע פרמוטציות אפשריות המסומנות <math>\text{KECCAK-f}[b]</math>, כאשר <math>b\in\{25,50,100,200,400,800,1600\}</math> נקרא "רוחב" המצב הפנימי. המצב הפנימי בנוי כמערך תלת-ממדי בעל אורך ורוחב קבועים <math>5\times 5</math> נתיבים (lanes) בעומק משתנה <math>w\in\{1,2,4,8,16,32,64\}</math> כאשר <math>b=25w</math> כמתואר בתרשים. על מעבד 64 ביט נתיב (Lane) ב-<math>\text{KECCAK-f}[1600]</math> ניתן לייצוג במילה אחת בגודל 64 סיביות. פונקציית הספוג <math>\text{KECCAK-f}[r+c]</math> מקבלת את הפרמטרים "קצב" (Bitrate) המסומן <math>r</math> וכן "קיבולת" (Capacity) המסומנת <math>c</math>. מפונקציה זו מתקבל מבנה ספוג יחד עם כלל ריפוד מתאים. כלל הריפוד הוא <math>\text{pad}10^*1</math>. כלומר תחילה מוסיפים סיבית "1" בסוף המסר, מרפדים באפסים ולבסוף מסיימים עם סיבית "1" נוספת, מספר האפסים הוא פונקציה של גודל הבלוק, כך שלבסוף יתקבל לפחות בלוק שלם באורך <math>b</math> סיביות.

===פונקציית הסבב - <math>\text{Round}[b](A, \text{RC})</math>===
להלן פסאודו-קוד המתאר את פונקציית הסבב המקבלת מערך <math>A</math> המכיל את המצב הפנימי. מספר הסבבים הוא <math>n_r</math> בהתאם לאורך הבלוק והוא נתון על ידי <math>n_r=12+2l</math> כאשר <math>2^l=w</math>. למשל עבור <math>\text{KECCAK-f}[1600]</math> מתקבלים 24 סבבים. כל הפעולות על האינדקסים בקוד הבא הם מודולו 5. הביטוי <math>A[x,y]</math> מתייחס לנתיב אחד במצב (ראו תרשים). <math>B[x,y]</math>, <math>X[x]</math>, <math>D[x]</math> הם משתנים זמניים. הקבועים <math>r[x,y]</math> הם היסטים של ההזזה המעגלית לפי הטבלה להלן. <math>\text{RC}[i]</math> הם קבועי סבב הנתונים בטבלה להלן. <math>\text{ROT}(W,r)</math> הוא פעולת הזזה מעגלית רגילה (Cyclic shift) בסיביות כשההיסט הוא מודולו אורך הנתיב. הביטוי <math>\text{NOT}</math> פירושו [[לא (לוגיקה)|אופרטור השלילה]], הסימן <math>\oplus</math> הוא [[XOR]] והסימן <math>\land</math> מייצג [[AND]].

<div class="mw-content-ltr">
<math>\mathbf{Round[b](A, \text{RC})}</math>

<math>\color{Blue}\boldsymbol{\theta}\text{ Step}</math>
:<math>\text{For }x = 0\text{ to }4\text{ do}</math>
::<math>C[x]=A[x,0]\oplus A[x,1]\oplus A[x,2]\oplus A[x,3]\oplus A[x,4]</math>
:<math>\text{For }x = 0\text{ to }4\text{ do}</math>
::<math>D[x]=C[x-1]\oplus \text{ROT}(C[x+1],1)</math>
:<math>\text{For }x = 0\text{ to }4\text{ do}</math>
::<math>\text{For }y = 0\text{ to }4\text{ do}</math>
:::<math>A[x,y]=A[x,y]\oplus D[x]</math>
:{{D}}
<math>\color{Blue}\boldsymbol{\rho}\text{ and }\boldsymbol{\pi}\text{ Steps}</math>
:<math>\text{For }x = 0\text{ to }4\text{ do}</math>
::<math>\text{For }y = 0\text{ to }4\text{ do}</math>
:::<math>B[y,2\cdot x+3\cdot y]=\text{ROT}(A[x,y],r[x,y])</math>
:{{D}}
<math>\color{Blue}\boldsymbol{\chi}\text{ Step}</math>
:<math>\text{For }x = 0\text{ to }4\text{ do}</math>
::<math>\text{For }y = 0\text{ to }4\text{ do}</math>
:::<math>A[x,y]=B[x,y]\oplus((\text{NOT }B[x+1,y])\land B[x+2,y]</math>
:{{D}}
<math>\color{Blue}\boldsymbol{\iota}\text{ Step}</math>
:<math>A[0,0]=A[0,0]\oplus \text{RC}</math>

<math>\text{Return }A</math>
</div>

===פונקציית הספוג - <math>\text{KECCAK-f}[b](A)</math>===
פונקציית הסבב המתוארת מבוצעת <math>n_r</math> פעמים על הקלט:
<div class="mw-content-ltr">
<math>\mathbf{KECCAK}\text{-}\mathbf{f[b](A)}</math>
:<math>\text{For }i = 0\text{ to }n_r-1\text{ do}</math>
::<math>A=\text{Round}[b](A,\text{RC}[i])</math>
:<math>\text{Return }A</math>
</div>

===אלגוריתם הגיבוב קצ'אק - <math>\mathbf{KECCAK[r,c](M)}</math>===
להלן פסאודו-קוד המתאר את אלגוריתם הגיבוב <math>\text{KECCAK}[r,c]</math>, עם הפרמטרים <math>c</math> ו-<math>r</math> (קצב וקיבולת) והמסר <math>M</math>, כאשר ההנחה לפי התקן היא ש-<math>r</math> הוא כפולה של אורך נתיב. הקוד מתייחס אל המידע ברמה של בתים, ברמה של סיביות יש צורך בהתאמות נוספות. <math>S</math> מייצג את המצב כמערך של נתיבים. המסר המרופד <math>P</math> מאורגן כמערך דו־ממדי של נתיבים. הסימן <math>\|</math> מייצג שרשור מחרוזות. באלגוריתם שלושה שלבים, שלב הריפוד שמקבל את המסר ומפיק מחרוזת מרופדת לפי התקן, שלב הספיגה שמפעיל את הפונקציה הפנימית על הקלט ושלב הסחיטה שמפיק את ערך הגיבוב באורך הנדרש:

<div class="mw-content-ltr">
<math>\mathbf{KECCAK[r,c](M)}</math>

<math>\color{Blue}\text{*Initialization and padding*}</math>
:<math>\text{For }x = 0\text{ to }4\text{ do}</math>
::<math>\text{For }y = 0\text{ to }4\text{ do}</math>
:::<math>S[x,y]=0</math>
:<math>P=M \ \| \ \text{0x01} \ \| \ \text{0x00} \ \| \ ... \ \| \ \text{0x00}</math>
:<math>P = P\oplus (\text{0x00} \ \| \ ... \ \| \ \text{0x00} \ \| \ \text{0x80})</math>
:{{D}}
<math>\color{Blue}\text{*Absorbing phase*}</math>
:<math>\text{For all blocks }P_i\text{ in }P\text{ do}</math>
::<math>\text{For all }(x,y)\text{ such that }x+5\cdot y<r/w\text{ do}</math>
:::<math>S[x,y]=S[x,y]\oplus P_i[x+5\cdot y]</math>
:::<math>S=\text{KECCAK-f}[r+c](S)</math>
:{{D}}
<math>\color{Blue}\text{*Squeezing phase*}</math>
:<math>\text{Loop:}</math>
::<math>\text{For all }(x,y)\text{ such that }x+5\cdot y<r/w\text{ do}</math>
:::<math>Z=Z\ \| \ S[x,y]</math>
:::<math>S=\text{KECCAK-f}[r+c](S)</math>
::<math>\text{Return }Z</math>
</div>

===עזרים===
קבועי הסבב <math>\text{RC}[i]</math> נתונים בטבלה הבאה עבור אורך מקסימלי של נתיב. עבור אורכים קצרים יותר פשוט חותכים את הערכים בהתאם.
<div class="mw-content-ltr">
{| class="wikitable"
|-
| RC[ 0] || 0x0000000000000001 || RC[12] || 0x000000008000808B
|-
| RC[ 1] || 0x0000000000008082 || RC[13] || 0x800000000000008B
|-
| RC[ 2] || 0x800000000000808A || RC[14] || 0x8000000000008089
|-
| RC[ 3] || 0x8000000080008000 || RC[15] || 0x8000000000008003
|-
| RC[ 4] || 0x000000000000808B || RC[16] || 0x8000000000008002
|-
| RC[ 5] || 0x0000000080000001 || RC[17] || 0x8000000000000080
|-
| RC[ 6] || 0x8000000080008081 || RC[18] || 0x000000000000800A
|-
| RC[ 7] || 0x8000000000008009 || RC[19] || 0x800000008000000A
|-
| RC[ 8] || 0x000000000000008A || RC[20] || 0x8000000080008081
|-
| RC[ 9] || 0x0000000000000088 || RC[21] || 0x8000000000008080
|-
| RC[10] || 0x0000000080008009 || RC[22] || 0x0000000080000001
|-
| RC[11] || 0x000000008000000A || RC[23] || 0x8000000080008008

|}
</div>

ההיסטים עבור ההזזה המעגלית נתונים בטבלה הבאה.
<div class="mw-content-ltr">
{| class="wikitable"
|-
! {{D}} !! x = 3 !! x = 4 !! x = 0 !! x = 1 !! x = 2
|-
| y = 2 || 25 || 39 || 3 || 10 || 43
|-
| y = 1 || 55 || 20 || 36 || 44 || 6
|-
| y = 0 || 28 || 27 || 0 || 1 || 62
|-
| y = 4 ||56 || 14 || 18 || 2 || 61
|-
| y = 3 || 21 || 8 || 41 || 45 || 15
|}
</div>

==קישורים חיצוניים==
* [http://csrc.nist.gov/groups/ST/hash/sha-3/index.html cryptographic hash Algorithm Competition], באתר NIST
* [http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo SHA-3 Zoo] – אתר המרכז את המידע שנצבר לגבי כל אחד מהמועמדים בתחרות
* [[אור דונקלמן]], [http://www.cs.technion.ac.il/~biham/Workshops/Cryptoday/2012/Slides/4-Orr-Dunkelman.pdf The Hitchhiker’s Guide to the SHA-3 Competition], מצגת מיום עיון בקריפטולוגיה שנערך בטכניון ב-4 ביולי 2012

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

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

[[קטגוריה:פונקציות גיבוב קריפטוגרפיות]]