שיטת מרקל-דמגרד

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Merkle-Damgard hash big-HE.svg

שיטת מרקל-דמגרד (Merkle-Damgård Construction) היא שיטה לבניית פונקציות גיבוב קריפטגרפיות המחלקת סדרת סיביות באורך שרירותי למקטעים באורך קבוע כדי שניתן יהיה להפעיל עליהם פונקציית תמצות. בכל שלב, מופעלת פונקציית התמצות על פלט השלב הקודם והמקטע הבא לעיבוד. ראלף מרקל ואיוון דמגרד הוכיחו בנפרד כי במידה ופונקציית התמצות חסינה מהתנגשויות כך גם פונקציית הגיבוב שנבנתה באמצעותה בשיטה זו.

עקרונות השיטה[עריכת קוד מקור | עריכה]

בהינתן פונקציית תמצות h המקבלת קלט באורך k+t כאשר k הוא גודל ה-Chaining value והודעה M באורך m, פונקציית מרקל-דמגרד תחלק את ההודעה ל-c מקטעים באורך t. במידה ואורך ההודעה אינו כפולה של t מוסיפים את הספרה 1 בסוף ההודעה האחרונה ומרפדים את ההודעה באפסים עד לאורך המתאים. לאחר מכן, בכל שלב מועבר לפונקציית התמצות מקטע חדש יחד עם פלט השלב הקודם (Chaining value).

בטיחות הבנייה[עריכת קוד מקור | עריכה]

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