Digital Signature Algorithm

מתוך ויקיפדיה, האנציקלופדיה החופשית

Digital Signature Algorithmראשי תיבות: DSA; בתרגום חופשי: אלגוריתם חתימה דיגיטאלית) הוא מנגנון חתימה דיגיטלית שהתקבל על ידי ממשלת ארצות הברית כתקן פדרלי (FIPS) בראשית 1993. אלגוריתם DSA הוצע לראשונה על ידי המכון הלאומי לסטנדרט וטכנולוגיה של ארצות הברית (NIST) באוגוסט 1991, כחלק מסטנדרט חתימה דיגיטלית DSS הקרוי תקן FIPS 186. ב-1996 פורסם עדכון של האלגוריתם תחת התקן FIPS 186-1 והורחב אף יותר בשנת 2000 בתקן FIPS 186-2. מפעם לפעם מתפרסמים עדכונים (כמו טיוטה FIPS 186-3), בהתאם להתפתחויות בתחום הקריפטוגרפיה. DSA רשום כפטנט בארצות הברית מאז 1991 על שמו של דויד קרביץ, עובד לשעבר של ה-NSA. הזכויות על הפטנט הוענקו לממשלת ארצות הברית. לאחר מכן פורסם האלגוריתם והופץ על ידי NIST באופן רשמי לשימוש חופשי. DSA אינו נחשב להצפנה במובן שלחתימה אין השפעה על המסר עצמו.

הגדל

תוכן עניינים

[עריכה] בעיית לוגריתם דיסקרטי

כמעט כל אלגוריתם מפתח-פומבי יכול לשמש כבסיס למנגנון חתימה דיגיטאלית. הרעיון של מנגנון החתימה של DSA מבוסס על בעיית לוגריתם דיסקרטי (בדידי). DSA הוא וריאציה של אל-גמאל ומשתמש בקושי שבפתרון בעיית חישוב לוגריתמים בחבורות, שהיא כידוע בעייה קשה מבחינה חישובית. למעשה האלגוריתם מסתמך על שתי בעיות קשורות של לוגריתם דיסקרטי. האחת לוגריתם דיסקרטי בחבורה כיפלית \ Z^{*}_ {p} מודולו \ p (ראשוני) גדול. והשנייה מציאת לוגריתמים בתת-חבורה ציקלית מסדר ראשוני \ q כלשהו (\ q < p). כמו כן מנגנון החתימה כולל, שימוש באלגוריתם ערבול (Hash) בטוח (ראה להלן).

הגדל

[עריכה] חתימה ואימות

אלגוריתם חתימה דיגיטאלית DSA כולל מספר פרמטרים בסיסיים: מפתח פרטי x, מספר סודי חד-פעמי k (מתאים למסר יחיד) ופונקציית ערבול H בטוחה. אימות החתימה נעשה בעזרת אותם פרמטרים יחד עם מפתח ציבורי y המשוייך באופן מתמטי למפתח הפרטי שאיתו בוצעה החתימה ואלגוריתם הערבול האמור. הפרמטרים מתוארים להלן:

\ p - מודולוס ראשוני גדול, המקיים \ 2^ {L-1} < p < 2^ {L}
(\ L מייצג את גודל \ p בסיביות, ראה להלן).
\ q - מחלק ראשוני של (\ p - 1), המקיים \ 2^ {N-1} < q < 2^ {N}
(\ N מייצג את גודל \ q בסיביות, ראה להלן).
\ g - יוצר של תת-חבורה מסדר \ q מודולו \ p, כאשר \ g < q.
להכנת \ g בוחרים שלם \ h הנמוך מ-\ q ומחשבים את \ g = h^ {(p-1)/q} \mbox{ mod } p, אם \ g = 1 חוזרים על התהליך עם \ h אחר.
\ x - מפתח פרטי וסודי. \ x צריך להיבחר באופן אקראי בטווח \left[1 ,q-1 \right].
\ y - מפתח ציבורי, אותו מחשבים כך: \ y = g^ {x} \mbox{ mod } p.
\ k - מספר ייחודי חד-פעמי עבור כל מסר. ייבחר באופן אקראי בטווח \left[1 ,q-1 \right].

הערה: במקום לחשב תחילה את \ p ולאחר מכן למצוא מחלק ראשוני \ q של \ (p - 1), אפשר קודם למצוא את \ q לאחר מכן לבדוק אם \ q \cdot i+1 = p הוא ראשוני, עבור \ i שלם כלשהו הגדול מ-1. למעשה התיעוד הרשמי של NIST מפרט אלגוריתם מומלץ למציאת \ p,q.

לצורך קביעת גודל הפרמטרים, התקן מפרט מבחר זוגות של N ו-L המבטאים גודל בסיביות של p ו-q בהתאמה. לדוגמה (L = 1024, N = 160) היא בחירה נמוכה ביותר, להשגת בטיחות מינימאלית. התקן המכסימלי הוא (L = 3072, N = 256).

[עריכה] חתימת DSA

החתימה על המסר \ m מורכבת מזוג המספרים \ s ו-\ r המחושבים כדלהלן:

  1. \ r = (g^ {k} \mbox{ mod } p) \mbox{ mod } q
  2. \ s = (k^ {-1} (\mbox{H}(m) + x \cdot r)) \mbox{ mod } q

\ \mbox{H}(m) הנו ערך האש שנוצר באמצעות פונקציית ערבול האמורה. \ k^{-1} הוא ההופכי של \ k מודולו \ q. יש לוודא כי \ s או \ r לא שווים 0, למרות שמקרה כזה נדיר אם תהליך החתימה בוצע נכון. כמו כן כחלק משלב הכנה מוקדם אפשר לחשב את \ r ללא תלות ב-\ m.

[עריכה] אימות ואישור החתימה

אישור החתימה נעשה על ידי כל גורם, בעזרת המפתח הפומבי של החותם. תחילה, על המידע הפומבי הנחוץ להיות נגיש לבודק החתימה באופן מזוהה ומוכח. למשל באמצעות סרטיפיקט חתום על ידי רשות אישרור (CA) מקובלת או במפגש אישי בין הצדדים. כמובן על הבודק לוודא כי הערכים \ r ו-\ s אינם שווים 0 או גדולים מ-\ q. תחילה מחשבים את הערכים הבאים:

  1. \ w = s^ {-1} \mbox{ mod } q (ההופכי של \ s מודולו \ q)
  2. \ u_1 = (\mbox{H}(m) \cdot w) \mbox{ mod } q
  3. \ u_2 = r \cdot w \mbox{ mod } q
  4. \ v = (g^ {u_1} \cdot y^ {u_2} \mbox{ mod } p) \mbox{ mod } q

אם ורק אם \ v = r, החתימה מתקבלת כאותנטית, אחרת מניחים כי המסר או החתימה שונו בידי גורם שלישי לא ידוע, אולי בניסיון לזייף את החתימה. או שחלה טעות במהלך החתימה או האימות.

[עריכה] אלגוריתם ערבול

כחלק ממנגנון חתימה דיגיטאלית יש צורך באלגוריתם ערבול או פונקציית גיבוב בטוחה על המסר לפני תהליך החתימה ואת החתימה לבצע על תוצאת הפונקציה ולא על המסר ישירות. הפונקציה מקבלת את המסר m המיועד לחתימה ומפיקה עבורו ערך ייחודי (H(m בגודל קבוע כאשר H(m) < m. הסיבות לכך הן, האחת עניין של יעילות, חתימה על מסר גדול באורך לא מוגדר, מסורבלת וקשה יותר מחתימה על ערך בגודל קבוע (קטן). שנית, עניין של בטיחות, חתימה על המסר עצמו ישירות, יוצרת פרצה בטיחותית מסוימת. בחתימה דיגיטאלית, לא די בכך שהערך יהיה ייחודי אלא שאלגוריתם הערבול יהיה בטוח, כדי להקטין כמעט לאפס את הסיכויים לכך שיימצא מסר אחר שעבורו הפונקציה מפיקה אותו ערך. לפי תקן DSA המקורי FIPS 186-1, אלגוריתם ערבול בטוח SHA-1 מספק. לאחרונה התגלו טכניקות חדשות המטילות בספק את בטיחותו של SHA-1. למעשה תקן FIPS 186 העדכני מגדיר דרישה לפונקציית ערבול בטוחה לפי תקן SHS, לפונקציית ערבול המכונה FIPS 180-2.

[עריכה] מקורות

אתר NIST, תקן FIPS 186-2.

אתר NIST, טיוטה 186-3.