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

ב[[קריפטוגרפיה]], '''EAX'''{{הערה|[http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/eax/eax-spec.pdf A Conventional Authenticated-Encryption Mode]}} הוא [[מצב הפעלה של צופן בלוקים]] עם [[הצפנה מאומתת]], שפותח ב-2004 על ידי [[מיהיר בלייר]], [[פיליפ רוגווי]] ו[[דייוויד וגנר]] [[אוניברסיטת קליפורניה בברקלי]] והוצע כאלטרנטיבה ל-[[CCM]] לצורך [[תקן]] הצפנה מאומתת. האלגוריתם שייך לקטגוריה AEAD - הצפנה מאומתת עם מידע נלווה ופועל בשתי ריצות. בהינתן מסר <math>M</math>, [[וקטור אתחול]] <math>N</math> שנקרא גם Nonce וכותר <math>H</math> באורך שרירותי כלשהו, האלגוריתם מצפין תחילה את <math>M</math> תוך שימוש בצופן בלוקים בטוח לפי העדפת המשתמש ומייצר טקסט מוצפן <math>C</math> ולאחר מכן מייצר תג אימות <math>T</math> להבטחת שלמות <math>C</math> והמידע הנלווה <math>H</math>, תוך ביצוע <math>2\left \lceil |M|/n\right \rceil + \left \lceil |H|/n \right\rceil + \left \lceil |N|/n\right\rceil</math> ריצות של [[צופן בלוקים|צופן הבלוקים]] כאשר <math>n</math> הוא אורך הבלוק בסיביות (128 סיביות במקרה של [[AES]]).{{כ}} EAX הוא און ליין, אפשר להתחיל הצפנה או פענוח לפני שמתקבל כל המסר ואורכו לא חייב להיות ידוע מראש וכן ניתן לחשב חלקים קבועים מראש כדי להפחית את כמות העבודה פר מסר. EAX מוכח כבטוח תחת הנחות סטנדרטיות ויעיל ופשוט יותר מ-CCM וכן כמו המתחרה, למיטב ידיעת המפתחים נקי מ[[זכויות יוצרים]] וחופשי לשימוש לכל מטרה.

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

קיימות מספר סכמות תיקניות להצפנה מאומתת ביניהן כאלו שנקראות 'גנריות' המשלבות הצפנה עם אימות בשני שלבים נפרדים ובלתי חופפים, כך שאפשר להחליף [[אלגוריתם]] הצפנה או אימות לפי הצורך, וכאלו שמשלבים הצפנה עם אימות יחד. וכן כאלו שפועלים בריצה אחת או בשתי ריצות. בשל [[פטנט]]ים וזכויות יוצרים שמקשים על תיקנון אלגוריתמים יעילים כמו [[OCB]], פותחו CCM ו-EAX שאמנם פחות יעילים אך חופשיים לשימוש. לעיתים עולה הצורך באימות ללא סודיות של חלק מהמידע. לדוגמה קובץ כותר המכיל הוראות והגדרות כמו כתובות שאמור להיות גלוי לעיני השרת המקבל, לכן התפתחה קטגוריה של מצבי הפעלה שנקראת AEAD שמנסה לענות על צורך זה.

==סימנים מוסכמים==
[[קובץ:eax_scheme.png|300px|ממוזער|שמאל|תרשים לדוגמה של הצפנה מאומתת בשיטת EAX]]
בבסיס האלגוריתם קיים צופן בלוקים שההנחה היא שהוא [[תמורה פסאודו-אקראית]] (PRP), למשל ההנחה היא ש-[[AES]] מתאים להגדרה זו. סימונו הכללי הוא <math>E:K\times \{0,1\}^n \rightarrow \{0,1\}^n</math> כאשר <math>n</math> הוא גודל הבלוק בסיביות. בסימון מקוצר <math>C=E_K(M)</math> - פירושו <math>C</math> הוא התוצאה של הפעלת האלגוריתם <math>E</math> עם המפתח <math>K</math> על המסר <math>M</math>. הביטוי <math>0^n</math> פירושו הסיבית אפס כשהיא משוכפלת <math>n</math> פעמים (לדוגמה <math>0^5=00000</math>). הביטוי <math>L\ll 1</math> פירושו הזזה לשמאל של כל סיביות האופרנד <math>L</math> פוזיציה אחת, כאשר הסיבית הפחות משמעותית תהיה אפס והסיבית המשמעותית ביותר נפלטת. הסימון <math>|M|</math> פירושו אורכה של ה[[מחרוזת (מדעי המחשב)|מחרוזת]] <math>M</math> בסיביות. האופרטור [[XOR]] מסומן בקיצור <math>\oplus</math> והסימון "<math>\stackrel{}\oplus{\rightarrow}</math>" פירושו כאשר המחרוזות אינן באותו אורך, המחרוזת הקצרה יותר מיושרת לסוף המחרוזת הארוכה ואז מבוצע XOR. בנוסף האלגוריתם עושה שימוש בכמה פרימיטיבים ידועים; CBC, CTR, OMAC*{{D}} ו-pad. לפירוט האלגוריתמים תחילה CBC (קיצור של CBC MAC) הוא [[קוד אימות מסרים]] בסיסי ופשוט המשתמש במצב ההעפלה [[מצב הפעלה של צופן בלוקים#מצב CBC|Cipher block chaining]]. האלגוריתם CTR הוא סגנון הפעלה ב[[מצב הפעלה של צופן בלוקים#מצב CTR|מצב מונה]] של צופן בלוקים. pad משמש כשיטת עזר לריפוד המסר עבור OMAC*{{D}}. האחרון הוא קיצור של One key MAC שהוא [[פונקציה פסבדו-אקראית קריפטוגרפית|פונקציה פסאודו-אקראית]] (PRF), פרי פיתוח של בלאק ורוגווי בשנת 2000 כחלק מקוד אימות מסרים [[XCBC]]. הכוכבית מסמנת שגרסה זו שונה מהמקורית בכך שהיא מקבלת [[פרמטר]] נוסף <math>t</math> הנקרא "tweak" שהוא סוג של וקטור אתחול או Nonce. זהו בעצם אלגוריתם [[קוד אימות מסרים#OMAC|OMAC]] הרגיל שבו מחרוזת הקלט משורשרת עם מחרוזת נוספת המייצגת את וקטור האתחול ואז מחשבים את תג האימות על המחרוזת החדשה.

הכוונה בביטוי <math>2L</math> באלגוריתם OMAC להלן היא שמתייחסים למחרוזת הסיביות <math>L</math> כאל [[פולינום]] מעל השדה <math>GF(2^n)</math> תוך שימוש בפולינום 'קנוני' המייצג את השדה. זהו [[פולינום פרימיטיבי]] [[פולינום אי פריק|אי-פריק]] בעל משקל בינארי נמוך, למשל במקרה של בלוקים בגודל 128 סיביות ההמלצה היא <math>x^{128}+x^7+x^2+x+1</math>. אפשר לראות באלמנטים של שדה בינארי מורחב <math>GF(2^n)</math> כפולינומים עם מקדמים בינאריים ממעלה הנמוכה מ-<math>n</math> ואז פעולת החיבור בשדה היא חיבור המקדמים מודולו 2 שמקבילה בעצם לאופרטור XOR וכפל ב-2 הוא בעצם הזזה (Shift) של כל המקדמים (סיביות) של הפולינום שמאלה פוזיציה אחת. במקרה של כפל ב-2 אם הסיבית המשמעותית היא 1 התוצאה תהיה פולינום ממעלה הגבוהה או שווה ל-128 תוצאה שחורגת מהשדה לכן יש צורך לצמצם את המספר, כלומר לחלק אותו בפולינום האי-פריק ולקחת את השארית (ראו [[חשבון מודולרי]]). כל מה שנדרש הוא פעולת [[חיסור]] אחת שבשדה זה זהה לחיבור כי XOR הופכי של עצמו לכן הפעולה מסתכמת ב-<math>2L=(L\ll 1)\oplus 0^{120}10000111</math> במקרה שהסיבית המשמעותית היא 1, או פשוט <math>L \ll 1</math> במקרה שהסיבית המשמעותית היא אפס. בדרך זו, אפשר לחשב את <math>4L=2(2L)</math>. כדי למנוע [[התקפת תזמון]] צריך לשים לב שפעולת הכפל תתבצע בזמן קבוע (בין אם הסיבית המשמעותית היא 1 או 0).

להלן פירוט האלגוריתמים הבסיסיים ש-EAX משתמש בהם:

<div class="mw-content-ltr">
<math>\textbf{CBC}_{\textit{\textbf{K}}}(\textit{\textbf{M}})</math>
:<math>M=M_1,M_2,...,M_m, \text{ where }|M_i|=n</math>
:<math>C=0^n</math>
:<math>\text{For }i=1\text{ to }m\text{ do: }C=E_K(M_i\oplus C)</math>
:<math>\text{Return }C</math>
</div>

<div class="mw-content-ltr">
<math>\textbf{CTR}_{\textit{\textbf{K}},\textit{\textbf{N}}}(\textit{\textbf{M}})</math>
:<math>m=\left\lceil |M|/n\right\rceil</math>
:<math>S=E_K(N) \ \| \ E_K(N+1) \ \| \ \cdots \ \| \ E_K(N+m-1)</math>
:<math>\text{Return }M\oplus S[\text{first }|M|\text{ bits}]</math>
</div>

<div class="mw-content-ltr">
<math>\textbf{pad}(\textit{\textbf{M}}, \textit{\textbf{B}}, \textit{\textbf{P}})</math>
:<math>\text{If }|M| \in \{n, 2n, 3n,...\}\text{ then return }M \ \stackrel{}\oplus{\rightarrow} \ B</math>
:<math>\text{else return }\left(M \ \| \ 10^{n-1-(|M| \text{ mod }n)}\right) \ \stackrel{}\oplus{\rightarrow} \ P</math>
</div>
הסבר: אם אורך המסר מתחלק ללא שארית בגודל הבלוק, אזי מבצעים XOR עם הפרמטר <math>B</math> כשהוא מיושר לסוף <math>M</math> ומחזירים את התוצאה. אחרת מרפדים את הבלוק האחרון בסיבית '1' ובאפסים כמידת הצורך כדי להשלימו לגודל בלוק שלם ומחזירים את התוצאה לאחר XOR עם הפרמטר <math>P</math> כשהוא מיושר לסוף <math>M</math>.
<div class="mw-content-ltr">
<math>\textbf{OMAC}_{\textit{\textbf{K}}}^t(\textit{\textbf{M}})</math>
:<math>L=E_K(0^n)</math>
:<math>\text{Return }\text{CBC}_K(\text{pad}([t]_n \ \| \ M, 2L, 4L))</math>
</div>
הסבר: תחילה משרשרים את <math>n</math> הסיביות הראשונות של <math>t</math> למסר <math>M</math>, מחשבים את שני הפרמטרים <math>(P,B)</math> לצורך הריפוד ומחזירים את תג האימות שהוא תוצאה של CBC של המסר לאחר הריפוד.

==תיאור האלגוריתם==
====אלגוריתם הצפנה עם אימות====
'''קלט:''' אורך התג הרצוי <math>\tau</math>, מפתח <math>K</math>, מסר <math>M</math>, כותר <math>H</math>, וקטור אתחול <math>N</math>. 

'''פלט:''' טקסט מוצפן <math>C</math> ותג אימות <math>T</math>.

<div class="mw-content-ltr">
<math>\textbf{EAX-ENCRYPT}_{\textit{\textbf{K}},\textit{\textbf{N}},\textit{\textbf{H}}}(\textit{\textbf{M}},\tau)</math>
:<math>\mathcal{N}=\text{OMAC}_K^0(N)</math>
:<math>\mathcal{H}=\text{OMAC}_K^1(H)</math>
:<math>C=\text{CTR}_{K,N}(M)</math>
:<math>\mathcal{C}=\text{OMAC}_K^2(C)</math>
:<math>\text{Tag}=\mathcal{N}\oplus\mathcal{C}\oplus\mathcal{H}</math> 
:<math>T=\text{Tag}[\text{first } \tau \text{ bits}]</math>
:<math>\text{Return }C \ \| \ T</math>
</div>

הסבר: תחילה מייצרים תג אימות עבור קובץ הכותר <math>H</math> וכן עבור וקטור האתחול <math>N</math> באמצעות OMAC. לאחר מכן מצפינים את המסר במצב מונה ומייצרים תג אימות מהטקסט המוצפן <math>C</math>. מחברים ב-XOR את שלושת התגים שנוצרו ולוקחים חלק מהתוצאה האחרונה כתג אימות <math>T</math> שנשלח יחד עם <math>C</math>.

====אלגוריתם פענוח עם אימות====
'''קלט:''' אורך התג הרצוי <math>\tau</math>, מפתח <math>K</math>, טקסט מוצפן <math>C</math>, כותר <math>H</math>, וקטור אתחול <math>N</math>, תג אימות <math>T</math>. 

'''פלט:''' מסר מקורי <math>M</math> או סמל מיוחד '''INVALID''' שפירושו שהאלגוריתם נכשל בפענוח, עקב שינוי באחד הערכים.

<div class="mw-content-ltr">
<math>\textbf{EAX-DECRYPT}_{\textit{\textbf{K}},\textit{\textbf{N}},\textit{\textbf{H}}}(\textit{\textbf{C}} \ \| \ \textit{\textbf{T}},\tau)</math>
:<math>\text{If }|(C \ \| \ T)| < \tau\text{ then return INVALID}</math> 
:<math>\mathcal{N}=\text{OMAC}_K^0(N)</math>
:<math>\mathcal{H}=\text{OMAC}_K^1(H)</math>
:<math>\mathcal{C}=\text{OMAC}_K^2(C)</math>
:<math>\text{Tag}'=\mathcal{N}\oplus\mathcal{C}\oplus\mathcal{H}</math>
:<math>\text{If }T \ne \text{Tag}'[\text{first }\tau\text{ bits}] \text{ then return INVALID}</math>
:<math>M=\text{CTR}_{K,N}(C)</math>
:<math>\text{Return }M</math>
</div>

==תכונות==
EAX{{הערה|[http://web.cs.ucdavis.edu/~rogaway/papers/eax.pdf The EAX Mode of Operation (A Two-Pass Authenticated-Encryption Scheme Optimized for Simplicity and Efficiency)]}} הוא סכמת הצפנה מאומתת בשתי ריצות, בתור שכזה יעילותו נמוכה מאלגוריתמים הפועלים בריצה אחת. ל-EAX מספר יתרונות:
*ביטחון מוכח, בהנחה שצופן הבלוקים שבבסיסו בטוח. למשל ההנחה היא ש-AES הוא PRP בטוח. כמו כן ביטחונו נשען על OMAC שגם לגביו קיימת הוכחה שהוא PRP בטוח.
*התנפחות הצופן מינימלית, כגודל תג האימות.
*שימוש במצב מונה מאפשר מקביליות וכן חישובים מוקדמים.
*האלגוריתם הוא "און ליין" ומתאים למשל ל[[הזרמת מדיה]].
*כאשר המידע הנלווה קבוע, כמו כותר קבוע למספר גדול של הודעות, ניתן לחשבו רק פעם אחת ולחסוך בזמן.

==ראו גם==
* [[CCM]]
* [[CWC mode|CWC]]

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




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

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