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

[[קובץ:MD5_f.png|שמאל|ממוזער|250px|מבנה פונקציית התמצות הפנימית של אלגוריתם MD5. הקלט מחולק לארבעה חלקים שווים <math>A,B,C,D</math> והפונקציה <math>F</math> היא אחת מארבע טרנספורמציות לוגיות על החלקים <math>B,C,D</math> כשהתוצאה מחוברת עם <math>A</math> יחד עם חלק מבלוק הקלט <math>X</math> וקבועים כלשהם. פירוט הפונקציות וקוד לדוגמה מובאים בהמשך.]]

ב[[קריפטוגרפיה]], '''MD5''' ([[ראשי תיבות]] ב[[אנגלית]]: '''M'''essage '''D'''igest algorithm '''5''', ב[[תרגום חופשי]]: "[[אלגוריתם]] תמצות מסרים גרסה 5") היא [[פונקציית גיבוב קריפטוגרפית]] שהייתה פונקציה קריפטוגרפית פופולרית בכל העולם ועדיין נמצאת בשימוש<ref>{{קישור כללי|כתובת=https://www.zdnet.com/article/a-quarter-of-major-cmss-use-outdated-md5-as-the-default-password-hashing-scheme/|הכותב=Catalin Cimpanu|כותרת=A quarter of major CMSs use outdated MD5 as the default password hashing scheme|אתר=ZDNet|שפה=en|תאריך_וידוא=2020-06-04}}</ref> למרות שהתגלתה כ[[התקפת התנגשויות|פונקציה פגיעה]] ולא נחשבת בטוחה יותר<ref>{{קישור כללי|כתובת=https://www.kb.cert.org/vuls/id/836068|הכותב=|כותרת=MD5 vulnerable to collision attacks|אתר=Carnegie Mellon University|תאריך=31/12/2008}}</ref>.  MD5 מקבלת קלט באורך כלשהו ו[[פלט|מפיקה]] ממנו "תמצית" באורך 128 [[סיבית|סיביות]] שהיא [[מחרוזת (מדעי המחשב)|מחרוזת]] סיביות חסרת משמעות המשמשת מעין [[טביעת אצבע]] דיגיטלית. עיקר מטרתה היה לספק אמצעי קריפטוגרפי להגנה על [[אימות מסרים|שלמות ואימות מסרים]] ברשת האינטרנט וכחלק ממנגנון [[חתימה דיגיטלית]]. ההתאמה בין התמצית לבין הקלט היא חד כיוונית באופן שקשה מאוד למצוא קלט אחר שממנו אפשר להפיק תמצית זהה לכן התמצית מהווה הוכחה לאותנטיות הקלט. נהוג לייצג את תמצית MD5 כ[[מחרוזת (מדעי המחשב)|מחרוזת טקסט]] [[הקסדצימלי|הקסדצימלית]].

== היסטוריה ==
פונקציית הגיבוב MD5 פותחה על ידי [[רונלד ריבסט]] ב-1991 והחליפה את קודמתה [[MD4]]. מקור שמה הוא ראשי התיבות של "Message Digest" (ב[[תרגום חופשי]]: "תמצית מסרים"). האלגוריתם היה בעבר [[תקן]]{{הערה|[http://www.ietf.org/rfc/rfc1321.txt Internet Standard: "The MD5 Message-Digest Algorithm"]}}, כלומר, הוא הוגדר וסווג על ידי ה-[[IETF]], ולכן הוא כלול ב[[תוכנת אבטחה|תוכנות אבטחה]] רבות. תיאורו וקוד המקור שלו נמצאים בטיוטה {{RFC|1321}}. ב-1996 נמצא פגם באלגוריתם MD5 ואף על פי שלא פגע בביטחונו באופן מהותי, מספר מומחי [[אבטחה]] ייעצו לעבור לאלגוריתם בטוח יותר. כיום מרבית התקנים ומומחי ה[[הצפנה]] ממליצים שלא להשתמש בו כלל לצורך קריפטוגרפי אלא לעבור לאלגוריתם תיקני מסדרת [[SHA]]. במרוצת השנים מאז המצאתו התגלו ב-MD5 בעיות וחולשות רבות שנוצלו לצורך התקפות נגד מערכות שעשו בו שימוש, כשהמפורסמת שבהן הייתה ה[[נוזקה]] [[להבה (נוזקה)|להבה]] שניצלה את חולשתו כדי לזייף חתימה דיגיטלית של [[מיקרוסופט]]. הוכח שהוא אינו מספק את המטרה לשמה נועד ואינו מקיים את התכונות החיוניות הנדרשות מפונקציית גיבוב קריפטוגרפית, בעיקר התכונה החזקה יותר שלה - עמידות מפני [[התנגשות (מדעי המחשב)|התנגשויות]]. הוא עדיין נמצא בשימוש מוגבל בעיקר בגלל [[תאימות לאחור]] ושיקולי יעילות. הוא הוצא כליל מפרוטוקולי [[חתימה דיגיטלית]] כמו [[Digital Signature Algorithm|DSA]] ופרוטוקולי תקשורת כמו [[SSL]], אך נמצא עדיין בשימוש כ[[קוד תיקון שגיאות|אלגוריתם תיקון שגיאות]] או [[סכום ביקורת]], להבטחת שלמות מידע כל עוד השגיאות נגרמות עקב תקלות תקשורת שאינן זדוניות.

== תיאור האלגוריתם ==
אלגוריתם MD5 הוא פונקציית גיבוב [[איטרציה|איטרטיבית]] הבנויה בסגנון [[שיטת מרקל-דמגרד|מרקל-דמגרד]]. בהינתן הקלט <math>m</math> באורך <math>\ell</math> סיביות שעבורו מעוניינים לייצר תמצית. תחילה מחלקים אותו למקטעים באורך 512 סיביות אותם מעבדים בזה אחר זה, כל מקטע נקרא '''בלוק'''. הקלט לא תמיד מתחלק באורך הבלוק. אם למשל [[מחרוזת (מדעי המחשב)|מחרוזת]] הקלט מכילה 75 אותיות, לפי קידוד [[ASCII]] שבו כל אות תופסת שמונה סיביות, אורכה הכולל הוא 600 סיביות ולכן היא מתחלקת לשני בלוקים, בלוק אחד מלא באורך 512 סיביות ובלוק שני חלקי המכיל רק 88 סיביות משמעותיות והיתר מאופסות. הבלוקים מסומנים כאן על ידי:
<center>
:<math>m_0,m_1,m_2,...,m_{b-1}</math>.
</center>
הקלט חייב להיות לפחות באורך בלוק אחד, אך יכול להיות ריק (מכיל רק אפסים). מספר הבלוקים מיוצג על ידי <math>b</math>. להלן פירוט חמשת הצעדים של האלגוריתם לחישוב תמצית הקלט.

====1. ריפוד====
תחילה הקלט "מרופד" כך שאורכו בסיביות יהיה שקול ל-448 [[מודולו]] 512. כלומר הקלט מורחב כך שיהיה רק 64 סיביות פחות מכפולה של 512. וב-64 הסיביות הנותרות בבלוק האחרון מעתיקים את קידוד אורך הקלט (להלן). הריפוד מתבצע כך, תחילה מוסיפים את הסיבית '1' לסוף מחרוזת הקלט ולאחר מכן מוסיפים אפסים כנדרש. במקרה הטוב תידרש תוספת של סיבית אחת בלבד ובמקרה הגרוע 512 סיביות. הריפוד חייב להתבצע בכל מקרה גם אם המסר כבר באורך בלוק שלם (במקרה כזה מוסיפים בלוק ריק). הרעיון של תוספת ה-'1' הוא שניתן יהיה תמיד לדעת היכן סוף הקלט מבלי לדעת כמה אפסים נוספו. פשוט מוחקים את כל האפסים המסיימים מסוף הקלט (אם ישנם) עד שנתקלים ב-'1' ואז מסירים גם אותו ומתקבל הקלט באורכו המקורי.

לדוגמה אם [[מחרוזת (מדעי המחשב)|מחרוזת]] הקלט היא המשפט: 
<center>
<div class="mw-content-ltr">"Hello World!"</div>
</center>
בבסיס הקסדצימלי המחרוזת נראית כך:
<center>
{| dir="ltr"
|-
| 48 || 65 || 6c || 6c || 6f || 20 || 57 || 6f || 72 || 6c || 64 || 21
|} 
</center>

כל ספרה הקסדצימלית היא באורך 4 סיביות. כולל הרווח (קוד אסקי 20) וסימן הקריאה (קוד אסקי 21) המחרוזת מכילה 12 תווים שתופסים לפי קידוד [[ASCII]] בדיוק 12 בתים בזיכרון (96 סיביות). היות שהמחרוזת נכנסת בבלוק אחד, מוסיפים <math>448-96=352</math> סיביות כשהראשונה היא הסיבית '1' ולאחריה 351 אפסים (בסך הכול 44 בתים) ומתקבלת המחרוזת הבאה:
<center>
{| dir="ltr"
|-
| 48 || 65 || 6c || 6c || 6f || 20 || 57 || 6f || 72 || 6c || 64 || 21 || {{צבע גופן|כחול|80}} || {{צבע גופן|כחול|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}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}}
|-
| {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}}
|}
</center>

ב-64 הסיביות הנותרות של הבלוק מקודדים את אורך המחרוזת המקורית שהוא 96 סיביות או בבסיס הקסדצימלי <math>\text{0x60}</math> ומתקבל:
<center>
{| dir="ltr"
|-
| 48 || 65 || 6c || 6c || 6f || 20 || 57 || 6f || 72 || 6c || 64 || 21 || {{צבע גופן|כחול|80}} || {{צבע גופן|כחול|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}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}}
|-
| {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|כחול|00}} || {{צבע גופן|ירוק|60}} || {{צבע גופן|ירוק|00}} || {{צבע גופן|ירוק|00}} || {{צבע גופן|ירוק|00}} || {{צבע גופן|ירוק|00}} || {{צבע גופן|ירוק|00}} || {{צבע גופן|ירוק|00}} || {{צבע גופן|ירוק|00}}
|}
</center>
כעת מתקבל בלוק שלם (אחד או יותר) באורך 512 סיביות כך שהקלט מוכן לעיבוד.

====2. קידוד האורך====
אורך הקלט בסיביות <math>\ell</math> (לפני הריפוד) מקודד במשתנה באורך 64 סיביות לפי [[סדר בתים]] קטן. משתנה זה מוצב ב-64 הסיביות האחרונות של הבלוק האחרון. בשל כך אורכו הכולל של הקלט לא יעלה על <math>2^{64}</math> סיביות כי אז לא ניתן לייצג את אורכו במשתנה באורך 64 סיביות. אם במקרה אורך הקלט עולה על מספר זה יש לקחת רק את 64 הסיביות האחרונות (הפחות משמעותיות) של <math>\ell</math>. הקידוד לפי סדר בתים קטן פירושו שהבית בכתובת הנמוכה ביותר מייצג את הספרות הפחות משמעותיות של המספר. דהיינו [[מילה (מחשב)|המילה]] <math>W</math> באורך 32 סיביות מורכבת מארבעה בתים <math>B_1,B_2,B_3,B_4</math> כאשר <math>B_1</math> הוא הבית הראשון (בכתובת הראשונה בזיכרון). אזי לפי סדר בתים קטן <math>W=2^{24}B_4+2^{16}B_3+2^{8}B_2+B_1</math>. במקרה שהמספר מתפרס על פני שתי מילים אזי המילה הראשונה מכילה את החלק הפחות משמעותי של המספר.

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

====3. אתחול זיכרון====
מכינים [[חוצץ]] באורך 4 מילים המסומנות <math>A,B,C,D</math> כל מילה מאוחסנת באוגר באורך 32 סיביות. בסך הכול נפח הזיכרון הפנימי הוא 128 סיביות. אתחול האוגרים מתבצע על ידי [[וקטור אתחול|וקטור האתחול]] המכיל 4 מילים קבועות <math>(H_1,H_2,H_3,H_4)</math>. המכילות את מחרוזת הספרות של [[בסיס הקסדצימלי|הבסיס ההקסדצימלי]]: "0123456789abcdef" ישר והפוך. לאחר חלוקה למילים לפי [[סדר בתים]] קטן מתקבל:
<center>
:<math>H_1 =\text{67452301}, H_2 = \text{efcdab89}, H_3 = \text{98badcfe}, H_4 = \text{10325476}</math>
</center>

====4. עיבוד הקלט====
תחילה מכינים ארבע פונקציות עזר פנימיות המקבלות כקלט שלוש מילים באורך 32 סיביות ומחזירות פלט באורך מילה אחת. הפונקציות הן:
{| align="center"
|-
| 
<div class="mw-content-ltr">
:<math>\boldsymbol{F}(x, y, z) = (x \land y) \lor (\lnot x \land z)</math>.
:<math>\boldsymbol{G}(x, y, z) = (x \land z) \lor (y \land \lnot z)</math>.
:<math>\boldsymbol{H}(x, y, z) = x \oplus y \oplus z</math>.
:<math>\boldsymbol{I}(x, y, z) = y \oplus (x \lor (\lnot z))</math>.
</div>
|}

הסימן <math>\land</math> מייצג [[וגם (לוגיקה)|וגם]], הסימן <math>\lnot</math> מייצג את [[לא (לוגיקה)|אופרטור השלילה]], הסימן <math>\lor</math> מייצג [[או (לוגיקה)|או לוגי]] והסימן <math>\oplus</math> מייצג [[XOR]]. בכל פוזיציה של הקלט הפונקציה <math>F</math> מתנהגת כ[[פסוק (לוגיקה)|פסוק לוגי]]: "אם <math>x</math> אז <math>y</math> אחרת <math>z</math>". אפשר היה להחליף את האופרטור <math>\lor</math> בחיבור (+) בגלל שסיביות <math>(x \land y) \lor (\lnot x \land z)</math> לעולם לא יהיו '1' באותן פוזיציות ולכן לא תהיה בעיה עם הנשא. אפשר לראות שאם סיביות הקלט <math>x</math>, <math>y</math> ו-<math>z</math> בלתי מוטות ובלתי תלויות זו בזו, תוצאת הפונקציה תהיה בלתי תלויה גם היא. יתר הפונקציות דומות לפונקציה <math>F</math> בכך שהן מייצרות במקביל פלט [[תלות (הסתברות)|בלתי תלוי הדדית]]. הפונקציה <math>H</math> היא [[פונקציית זוגיות|פונקציית הזוגיות]] (XOR) של הקלט.

בנוסף לפונקציות יש להכין טבלת קבועים <math>T</math> המכילה 64 אלמנטים. עבור כל אינדקס <math>i</math> כאשר <math>0\le i \le 63</math> האלמנט <math>T[i]</math> מכיל את החלק השלם של ה[[שבר (מתמטיקה)|שבר]] <math>4294967296 \cdot |\sin(i+1)|</math> (הפונקציה sin היא ה[[סינוס (טריגונומטריה)|סינוס]] של <math>i+1</math> ב[[רדיאן|רדיאנים]]). אין צורך לחשב את הטבלה בכל פעם שצריכים לחשב תמצית, נהוג לחשבה מראש. להלן ערכי הקבועים בבסיס [[בסיס הקסדצימלי|הקסדצימלי]]:
{| align="center"
|-
| 
<div class="mw-content-ltr">
:<math>\begin{matrix} \text{d76aa478} & \text{e8c7b756} & \text{242070db} & \text{c1bdceee} & \text{f57c0faf} & \text{4787c62a} & \text{a8304613} & \text{fd469501} \\ \text{698098d8} & \text{8b44f7af} & \text{ffff5bb1} & \text{895cd7be} & \text{6b901122} & \text{fd987193} & \text{a679438e} & \text{49b40821} \\ \text{f61e2562} & \text{c040b340} & \text{265e5a51} & \text{e9b6c7aa} & \text{d62f105d} & \text{02441453} & \text{d8a1e681} & \text{e7d3fbc8} \\ \text{21e1cde6} & \text{c33707d6} & \text{f4d50d87} & \text{455a14ed} & \text{a9e3e905} & \text{fcefa3f8} & \text{676f02d9} & \text{8d2a4c8a} \\ \text{fffa3942} & \text{8771f681} & \text{6d9d6122} & \text{fde5380c} & \text{a4beea44} & \text{4bdecfa9} & \text{f6bb4b60} & \text{bebfbc70} \\ \text{289b7ec6} & \text{eaa127fa} & \text{d4ef3085} & \text{04881d05} & \text{d9d4d039} & \text{e6db99e5} & \text{1fa27cf8} & \text{c4ac5665} \\ \text{f4292244} & \text{432aff97} & \text{ab9423a7} & \text{fc93a039} & \text{655b59c3} & \text{8f0ccc92} & \text{ffeff47d} & \text{85845dd1} \\ \text{6fa87e4f} & \text{fe2ce6e0} & \text{a3014314} & \text{4e0811a1} & \text{f7537e82} & \text{bd3af235} & \text{2ad7d2bb} & \text{eb86d391} \end{matrix}</math>
</div>
|}

במהלך חישוב התמצית, כל בלוק קלט <math>m_i</math> מועתק למשתנה מקומי <math>X</math> לצורך עיבוד. <math>X</math> מכיל 16 מילים באורך 32 סיביות שהם 512 סיביות. כל חישובי הפונקציות מבוצעים עם מילים מתוך <math>X</math> לפי סדר מסוים. סדר עיבוד המילים נקבע לפי הטבלה הבאה בהתאם למספר הסבב:
{| align="center"
|-
| 
<div class="mw-content-ltr">
:<math>z[0..15] = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\},</math> 
:<math>z[16..31] = \{1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12\},</math>
:<math>z[32..47] = \{5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2\},</math>
:<math>z[48..63] = \{0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9\}.</math>
</div>
|}
ב-16 הסבבים הראשונים מעבדים את מילות הבלוק לפי הסדר מהמילה הראשונה עד המילה ה-16. בסבב ה-17 לפי הטבלה מתחילים מהמילה השנייה <math>X[z[16]] = X[1]</math> במקום הראשונה לאחר מכן מדלגים למילה השביעית וכן הלאה (יש לזכור שהספירה מתחילה תמיד מאפס).

בכל סבב מתבצעת [[פעולה על סיביות#סיבוב ללא סחיבה|הזזה מעגלית]] במספר הפוזיציות שונה בהתאם למספר הסבב. הטבלה הבאה מכילה את מספרי ההזזות עבור כל הסבבים:
{| align="center"
|-
| 
<div class="mw-content-ltr">
:<math>s[0..15] = \{7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22\},</math>
:<math>s[16..31] = \{5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20\},</math>
:<math>s[32..47] = \{4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23\},</math>
:<math>s[48..63] = \{6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21\}.</math>
</div>
|}
הטבלה <math>s</math> מכילה 64 ערכים כשכל ערך מייצג את מספר הפוזיציות שיש להזיז את המשתנה המקומי <math>t</math> המכיל את פלט הפונקציות האמורות ומהווה חלק מערך הביניים של האלגוריתם. למשל בסבב הראשון <math>t\lll s[0]=t\lll 7</math> הזזה של שבע סיביות, לדוגמה <math>\text{10F24B1F} \lll 7 = \text{19258FC3}</math>.

פונקציית התמצות הפנימית של אלגוריתם MD5 מבצעת על כל בלוק קלט 64 פעולות כאשר בסופן היא מעדכנת את המצב הפנימי שהופך לקלט עבור הבלוק הבא. פלט פונקציית הגיבוב יהיה המצב הפנימי האחרון לאחר סיום כל הבלוקים. להלן [[פסאודו קוד]] המתאר את המתרחש בלב האלגוריתם:
{| align="center"
|-
| 
<div class="mw-content-ltr">
:<math>\text{For each }i\text{ from }0\text{ to }b-1\text{ do }</math>
:<math>\{</math>
::<math>\text{For }j = 0\text{ to }15\text{ do:}</math>
:::<math>X[j] \leftarrow m[16 \cdot i + j].</math>
:{{D}}
::<math>(A, B, C, D) \leftarrow (H_1, H_2, H_3, H_4).</math>
:{{D}}
::<math>\text{For }j = 0\text{ to }15\text{ do:}</math>
:::<math>t \leftarrow (A + F(B, C, D) + X[z[j]] + y[j]),</math>
:::<math>(A, B, C, D) \leftarrow (D, B + (t \lll s[j]),B, C).</math> 
:{{D}}
::<math>\text{For }j = 16\text{ to }31\text{ do:}</math>
:::<math>t \leftarrow (A + G(B, C, D) + X[z[j]] + y[j]),</math>
:::<math>(A, B, C, D) \leftarrow (D, B + (t \lll s[j]),B, C).</math>
:{{D}}
::<math>\text{For }j = 32\text{ to }47\text{ do:}</math>
:::<math>t \leftarrow (A + H(B, C, D) + X[z[j]] + y[j]),</math>
:::<math>(A, B, C, D) \leftarrow (D, B + (t \lll s[j]),B, C).</math>
:{{D}}
::<math>\text{For }j = 48\text{ to }63\text{ do:}</math>
:::<math>t \leftarrow (A + I(B, C, D) + X[z[j]] + y[j]),</math>
:::<math>(A, B, C, D) \leftarrow (D, B + (t \lll s[j]),B, C).</math>
:{{D}}
::<math>(H_1, H_2, H_3, H_4) \leftarrow (H_1 + A, H_2 + B, H_3 + C, H_4 + D).</math>
:<math>\}</math>
</div>
|}

הביטוי <math>(A, B, C, D) \leftarrow (H_1, H_2, H_3, H_4)</math> פירושו העתקת הערכים מהאגף הימני לאגף השמאלי לפי סדר זה <math>A=H_1</math>, <math>B=H_2</math> וכן הלאה. הסימן <math>\lll</math> מייצג [[הזזה מעגלית]] לשמאל לפי מספר הפוזיציות המופיע לימין הסימן בגבולות מילה באורך 32 סיביות. הזזה מעגלית ניתנת למימוש בתוכנה או בחומרה. למשל ב[[שפת C]] ממשים הזזה מעגלית כך: '''<tt>(value << count) | (value >> (32 - count))</tt>''' כאשר האופרטורים "<<" ו-">>" הם אופרטורי ההזזה המובנים בכל [[שפת תכנות|שפות התכנות]]. הפעולה העיקרית באלגוריתם היא המשפט <math>t \leftarrow (A + F(B, C, D) + X[z[j]] + y[j])</math>, המשתנה המקומי <math>t</math> מכיל את תוצאת הפונקציה על המצב הפנימי יחד עם חלק מבלוק הקלט והקבועים, כאשר <math>F</math> מוחלפת בפונקציות האחרות לפי הסדר. הפעולה מומחשת בתרשים למעלה.

====5. פלט====
הפלט הוא [[שרשור (מחרוזות)|שרשור]] ערכי הביניים מהסבב האחרון: <math>H_1\ \| \ H_2\ \| \ H_3 \ \| \ H_4</math>

===וקטור בדיקה===
{| align="center"
|-
! פלט !! קלט
|-
| <div class="mw-content-ltr">
::<math>\text{d41d8cd9 8f00b204 e9800998 ecf8427e}</math>
::<math>\text{0cc175b9 c0f1b6a8 31c399e2 69772661}</math>
::<math>\text{90015098 3cd24fb0 d6963f7d 28e17f72}</math>
::<math>\text{c3fcd3d7 6192e400 7dfb496c ca67e13b}</math>
</div>
|| 
<div class="mw-content-ltr">
::<math>\text{MD5(“”)}</math>
::<math>\text{MD5(“a”)}</math>
::<math>\text{MD5(“abc”)}</math>
::<math>\text{MD5(“abcdefghijklmnopqrstuvwxyz”)}</math>
</div>
|}

===קוד לדוגמה===
להלן קוד שלם בשפת [[C++]]{{D}} הממחיש את האלגוריתם. הקוד ממוטב חלקית ומיישם מספר אופטימיזציות כדי להשיג ביצועים טובים, ביניהם אפשר למנות; שימוש באופרטורים כמו XOR ו-AND במקום כפל וחיבור, פקודות מאקרו, פתיחת [[לולאה (תכנות)|לולאות]] (loop unrolling) ומיעוט [[שגרה (תכנות)|קריאות לפונקציות]].
<syntaxhighlight lang="CPP">
typedef unsigned int uint;
typedef unsigned char byte;

typedef struct {
	uint state[4];
	uint count[2];
	byte buffer[64];
} MD5_CTX;

class MD5
{
	#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
	#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
	#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
	#define H(x, y, z) ((x) ^ (y) ^ (z))
	#define I(x, y, z) ((y) ^ ((x) | (~z)))

	byte PADDING[64] = {
		0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	};

	#define FF(a, b, c, d, x, s, ac) { \
		 (a) += F ((b), (c), (d)) + (x) + (uint)(ac); \
		 (a) = ROTATE_LEFT ((a), (s)); \
		 (a) += (b); \
		}
	#define GG(a, b, c, d, x, s, ac) { \
		 (a) += G ((b), (c), (d)) + (x) + (uint)(ac); \
		 (a) = ROTATE_LEFT ((a), (s)); \
		 (a) += (b); \
		 }
	#define HH(a, b, c, d, x, s, ac) { \
		 (a) += H ((b), (c), (d)) + (x) + (uint)(ac); \
		 (a) = ROTATE_LEFT ((a), (s)); \
		 (a) += (b); \
		 }
	#define II(a, b, c, d, x, s, ac) { \
		 (a) += I ((b), (c), (d)) + (x) + (uint)(ac); \
		 (a) = ROTATE_LEFT ((a), (s)); \
		 (a) += (b); \
		 }
	static void MD5Transform(uint state[4], byte block[64])
	{
		uint a = state[0], b = state[1], c = state[2], d = state[3], x[16];
		Decode(x, block, 64);
		/* Round 1 */
		FF(a, b, c, d, x[0], 7, 0xd76aa478); 
		FF(d, a, b, c, x[1], 12, 0xe8c7b756); 
		FF(c, d, a, b, x[2], 17, 0x242070db); 
		FF(b, c, d, a, x[3], 22, 0xc1bdceee); 
		FF(a, b, c, d, x[4], 7, 0xf57c0faf); 
		FF(d, a, b, c, x[5], 12, 0x4787c62a);
		FF(c, d, a, b, x[6], 17, 0xa8304613);
		FF(b, c, d, a, x[7], 22, 0xfd469501); 
		FF(a, b, c, d, x[8], 7, 0x698098d8); 
		FF(d, a, b, c, x[9], 12, 0x8b44f7af);
		FF(c, d, a, b, x[10], 17, 0xffff5bb1); 
		FF(b, c, d, a, x[11], 22, 0x895cd7be);
		FF(a, b, c, d, x[12], 7, 0x6b901122);
		FF(d, a, b, c, x[13], 12, 0xfd987193);
		FF(c, d, a, b, x[14], 17, 0xa679438e);
		FF(b, c, d, a, x[15], 22, 0x49b40821);

	/* Round 2 */
		GG(a, b, c, d, x[1], 5, 0xf61e2562); 
		GG(d, a, b, c, x[6], 9, 0xc040b340); 
		GG(c, d, a, b, x[11], 14, 0x265e5a51);
		GG(b, c, d, a, x[0], 20, 0xe9b6c7aa);
		GG(a, b, c, d, x[5], 5, 0xd62f105d); 
		GG(d, a, b, c, x[10], 9, 0x2441453); 
		GG(c, d, a, b, x[15], 14, 0xd8a1e681); 
		GG(b, c, d, a, x[4], 20, 0xe7d3fbc8);
		GG(a, b, c, d, x[9], 5, 0x21e1cde6); 
		GG(d, a, b, c, x[14], 9, 0xc33707d6); 
		GG(c, d, a, b, x[3], 14, 0xf4d50d87); 
		GG(b, c, d, a, x[8], 20, 0x455a14ed); 
		GG(a, b, c, d, x[13], 5, 0xa9e3e905); 
		GG(d, a, b, c, x[2], 9, 0xfcefa3f8); 
		GG(c, d, a, b, x[7], 14, 0x676f02d9); 
		GG(b, c, d, a, x[12], 20, 0x8d2a4c8a);

	/* Round 3 */
		HH(a, b, c, d, x[5], 4, 0xfffa3942);
		HH(d, a, b, c, x[8], 11, 0x8771f681); 
		HH(c, d, a, b, x[11], 16, 0x6d9d6122); 
		HH(b, c, d, a, x[14], 23, 0xfde5380c);
		HH(a, b, c, d, x[1], 4, 0xa4beea44); 
		HH(d, a, b, c, x[4], 11, 0x4bdecfa9); 
		HH(c, d, a, b, x[7], 16, 0xf6bb4b60); 
		HH(b, c, d, a, x[10], 23, 0xbebfbc70); 
		HH(a, b, c, d, x[13], 4, 0x289b7ec6); 
		HH(d, a, b, c, x[0], 11, 0xeaa127fa); 
		HH(c, d, a, b, x[3], 16, 0xd4ef3085);
		HH(b, c, d, a, x[6], 23, 0x4881d05); 
		HH(a, b, c, d, x[9], 4, 0xd9d4d039); 
		HH(d, a, b, c, x[12], 11, 0xe6db99e5); 
		HH(c, d, a, b, x[15], 16, 0x1fa27cf8); 
		HH(b, c, d, a, x[2], 23, 0xc4ac5665);

	/* Round 4 */
		II(a, b, c, d, x[0], 6, 0xf4292244); 
		II(d, a, b, c, x[7], 10, 0x432aff97); 
		II(c, d, a, b, x[14], 15, 0xab9423a7); 
		II(b, c, d, a, x[5], 21, 0xfc93a039); 
		II(a, b, c, d, x[12], 6, 0x655b59c3); 
		II(d, a, b, c, x[3], 10, 0x8f0ccc92); 
		II(c, d, a, b, x[10], 15, 0xffeff47d);
		II(b, c, d, a, x[1], 21, 0x85845dd1); 
		II(a, b, c, d, x[8], 6, 0x6fa87e4f); 
		II(d, a, b, c, x[15], 10, 0xfe2ce6e0); 
		II(c, d, a, b, x[6], 15, 0xa3014314);
		II(b, c, d, a, x[13], 21, 0x4e0811a1); 
		II(a, b, c, d, x[4], 6, 0xf7537e82);
		II(d, a, b, c, x[11], 10, 0xbd3af235);
		II(c, d, a, b, x[2], 15, 0x2ad7d2bb); 
		II(b, c, d, a, x[9], 21, 0xeb86d391);
		state[0] += a;
		state[1] += b;
		state[2] += c;
		state[3] += d;
		memset((byte *)x, 0, sizeof(x));
	}

	static void Decode(uint *output, byte *input, uint len)
	{
		uint i, j;
		for (i = 0, j = 0; j < len; i++, j += 4)
			output[i] = ((uint)input[j]) | (((uint)input[j + 1]) << 8) |
			(((uint)input[j + 2]) << 16) | (((uint)input[j + 3]) << 24);
	}

	static void Encode(byte *output, uint *input, uint len)
	{
		for (uint i = 0, j = 0; j < len; i++, j += 4) {
			output[j] = (byte)(input[i] & 0xff);
			output[j + 1] = (byte)((input[i] >> 8) & 0xff);
			output[j + 2] = (byte)((input[i] >> 16) & 0xff);
			output[j + 3] = (byte)((input[i] >> 24) & 0xff);
		}
	}

public:
	void Init(MD5_CTX *context)
	{
		context->count[0] = context->count[1] = 0;
		context->state[0] = 0x67452301;
		context->state[1] = 0xefcdab89;
		context->state[2] = 0x98badcfe;
		context->state[3] = 0x10325476;
	}

	void Update(MD5_CTX *context, byte *input, uint inputLen)
	{
		uint i, index = (uint)((context->count[0] >> 3) & 0x3F);
		if ((context->count[0] += ((uint)inputLen << 3)) < ((uint)inputLen << 3))
			context->count[1]++;
		context->count[1] += ((uint)inputLen >> 29);
		uint partLen = 64 - index;
		if (inputLen >= partLen) {
			memcpy((byte *)&context->buffer[index], (byte *)input, partLen);
			MD5Transform(context->state, context->buffer);
			for (i = partLen; i + 63 < inputLen; i += 64)
				MD5Transform(context->state, &input[i]);
			index = 0;
		}
		else i = 0;
		memcpy((byte *)&context->buffer[index], (byte *)&input[i], inputLen - i);
	}

	void Final(byte digest[16], MD5_CTX *context)
	{
		byte bits[8];
		uint index, padLen;
		Encode(bits, context->count, 8);
		index = (uint)((context->count[0] >> 3) & 0x3f);
		padLen = (index < 56) ? (56 - index) : (120 - index);
		Update(context, PADDING, padLen);
		Update(context, bits, 8);
		Encode(digest, context->state, 16);
		memset((byte *)context, 0, sizeof(*context));
	}
};
</syntaxhighlight>

== שימושים נפוצים ==
בשל העובדה שהפלט רגיש מאוד לשינויים בקלט (ה[[הודעה (מחשבים)|הודעה]]), MD5 מאפשר יצירת "[[חתימה דיגיטלית|חתימה]]" לכל פלט נתון.
עובדה זו מאפשרת להשתמש בו ביישומים כגון:
* [[אימות זהות]] ופרטי [[משתמש (מחשוב)|משתמש]] תוך הגנה על [[פרטיות]]ו. האימות מתבצע על ידי הפעלת אלגוריתם MD5 על [[קלט]] מהמשתמש ([[סיסמה#סיסמת גישה למשאבי מחשב|שם משתמש וסיסמה]]), והשוואת הפלט המתקבל ל"חתימה" השמורה בזיכרון ה[[שרת (מחשבים)|שרת]]. באופן זה, לא נשמרים בפועל פרטים רגישים אלא רק חתימתם הייחודית. השימוש באלגוריתם MD5 נפוץ, למשל, ב[[פורום (אינטרנט)|פורומים]] מבוססי [[IB]] או [[PHP]].
* בדיקת שלמות או תקינות של [[קובץ|קבצים]]. המשתמש יכול להשוות את חתימת ה-MD5 שפורסמה, מול החתימה של הקובץ ש[[הורדה|הוריד]]. יש לציין, שבדיקת תקינות זו יכולה לגלות רק אם הקובץ פגום (או לא שלם), אך לא לגלות את השגיאה עצמה.

== ביטחון ==
MD5 לא בטוח כיום לשימוש קריפטוגרפי והוא הוצא ממרבית התקנים וכן מ-[[SSL]] לאחר שהתגלו בו בעיות ופגמים רבים. למרות זאת הוא עדיין קיים בשימוש מוגבל. ב-1996 התגלה פגם בתכנון MD5 שבזמנו לא נחשב לבעיה חמורה, אולם לאור הממצאים מומחי הצפנה המליצו כבר אז לעבור לאלגוריתמים טובים יותר כמו פונקציות הגיבוב ממשפחת [[SHA]] שבחלקם התגלו גם הם כבעייתיים. ב-2004 הוכח ש-MD5 אינו מספק את המטרה העיקרית לשמה הוא פותח; עמידות מפני [[התנגשות (מדעי המחשב)|התנגשויות]], כלומר אמור להיות קשה מאוד מבחינה חישובית למצוא שני קלטים שונים שאם מזינים אותם לפונקציית הגיבוב מקבלים פלט זהה. מסיבה זו MD5 אינו מתאים ל[[תעודת מפתח ציבורי]] או [[חתימה דיגיטלית]] שהם מסתמכים על ההנחה שהתנגשויות בלתי אפשריות (חישובית). באותה שנה קבוצת חוקרים גילו פגמים חמורים נוספים. הם הראו איך אפשר להכין שני מסמכים שונים כך שיפיקו תמצית MD5 זהה. בשנים שלאחר מכן חלה התקדמות נוספת בשבירת האלגוריתם. בדצמבר 2008 קבוצת חוקרים השתמשה בטכניקות שהתגלו כדי לזייף תעודת [[מפתח ציבורי]] בתוך מספר שעות. נכון לשנת 2010 הוכרז על ידי ארגון [[SEI]] כי אלגוריתם MD5 נפרץ לחלוטין ואינו מתאים יותר לכל שימוש קריפטוגרפי. יישומים ממשלתיים נדרשים כיום להשתמש ב-[[SHA-2]]. ב-2012 [[להבה (נוזקה)|נוזקת להבה]] ניצלה את חולשות MD5 כדי לזייף חתימה דיגיטלית של [[מיקרוסופט]]. כיום קיימות התקפות התנגשויות נגד MD5 שמסוגלות למצוא התנגשות בתוך שניות על מחשב ביתי. יתרה מזו, קיימת התקפה שנקראת chosen-prefix (תחילית-נבחרת) שמאפשרת ליצור התנגשות עבור שני קלטים עם תחילית קבועה בתוך מספר שעות עם [[חומרה]] סטנדרטית.

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

== ראו גם ==
* [[פונקציית גיבוב קריפטוגרפית]]
* [[פונקציה חד-כיוונית]]
* [[שיטת מרקל-דמגרד]]

== לקריאה נוספת ==
* [[סיימון סינג]], '''[[סודות ההצפנה]]''', "ידיעות אחרונות".
* Internet Security: Cryptographic Principles, Algorithms and Protocols.

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

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

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