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

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

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

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

בשל העובדה שפונקציית התמצות הפנימית f חייבת לקבל קלט באורך קבוע, כאשר המסר המיועד לגיבוב גדול ובאורך שרירותי, שזה המצב בדרך כלל, מחלקים אותו לבלוקים בגודל קבוע (512 או 1024 סיביות) אותם מעבדים בזה אחר זה באופן איטרטיבי. מתחילים עם וקטור אתחול קבוע כלשהו ובכל שלב פונקציית התמצות הפנימית מקבלת כקלט את הבלוק הבא ואת תמצית הבלוק הקודם ומפיקה תמצית חדשה, כך פלט סבב אחד הופך קלט לסבב הבא וכן הלאה עד לעיבוד כל הבלוקים. אם המסר אינו מתחלק בגודל הבלוק, מרפדים את הבלוק האחרון בשיטת הריפוד של תמצית המסרים (בקיצור MD) של רונלד ריבסט.

הרעיון של מרקל ודמגר הוא שכדי לחזק את השיטה המתוארת יש להוסיף בלוק המייצג את גודל המסר, אותו מעבדים בסוף.

בניסוח פורמלי: נתונה פונקציה f שממפה קלט באורך r+n סיביות לפלט באורך n סיביות. ממנה אפשר לבנות פונקציית גיבוב כדלהלן:

  1. מחלקים את הקלט x באורך b סיביות ל-t בלוקים x_1,x_2,...,x_t בני r סיביות כל אחד.
  2. אם הבלוק האחרון קטן מ-r סיביות, מוסיפים '1' ומרפדים באפסים עד שמתקבל בלוק בגודל r סיביות.
  3. מוסיפים בלוק x_{t+1} שבו מקודדים את אורך המסר בסיביות ומרפדים באפסים.
  4. מגדירים וקטור איתחול (initialization vector) בקיצור IV קבוע שערכו תלוי ביישום ספציפי. מציבים H_0=IV.
  5. עבור כל i כאשר 1\le i\le t+1 מחשבים H_i=f(H_{i-1} \ \| \ x_i) כאשר ל-H_i קוראים ערך-ביניים (chaining value).
  6. הפלט הוא h(x)=H_{t+1}.

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

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

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