Digital Signature Algorithm
אלגוריתם חתימה דיגיטאלית DSA, הנו תקן פדרלי של ממשלת ארה"ב או תקן FIPS לחתימה דיגיטאלית. אלגוריתם זה הוצע על ידי המכון הלאומי לסטנדרט וטכנולוגיה של ארה"ב (NIST) באוגוסט 1991 כחלק מסטנדרט חתימה דיגיטאלית DSS המפורט ב-FIPS 186. ואומץ על ידי הממשל בראשית 1993. ב-1996 פורסם עדכון קל של האלגוריתם תחת התקן FIPS 186-1 והורחב אף יותר בשנת 2000 כתקן FIPS 186-2. בקרוב אמור להתפרסם עדכון נוסף כ-FIPS 186-3. DSA רשום כפטנט בארה"ב משנת 1991, על שמו של דויד קרביץ עובד לשעבר של ה-NSA. הזכויות על הפטנט הועברו לממשלת ארה"ב והופץ על ידי NIST ברחבי העולם לשימוש חופשי.
אלגוריתם DSA הוא וריאציה של אל-גמאל ומבוסס על בעיית לוגריתם דיסקרטי המפורסמת. למעשה האלגוריתם מסתמך על שני בעיות קשורות של לוגריתם דיסקרטי. האחת לוגריתם דיסקרטי בחבורה כיפלית Z*p עבור p ראשוני. והשנייה לוגריתמים בתת-חבורה ציקלית מסדר ראשוני q כלשהו. וכולל שימוש באלגוריתם ערבול (Hash) בטוח.
הכנת מפתח
1. בוחרים ראשוני q בגודל 160 סיביות.
2. בוחרים שלם t בטווח [0, 8], ובוחרים ראשוני p המקיים:
2511+64t < p < 2512+64t. כאשר q מחלק של (p-1).
הערה: FIPS 186-2 מגדיר את t = 8 (הטווח המירבי) כך שגודלו של p הוא 1024 סיביות.
3. בוחרים יוצר z של חבורה ציקלית ייחודית מסדר q ב-Z*p.
בוחרים אלמנט g ב-Z*p, ומחשבים את z = g(p-1)/q mod p. אם z = 1 חוזרים אל התהליך עם אלמנט g אחר.
4. בוחרים שלם אקראי a בטווח [1, q-1].
5. מחשבים את za mod p.
המפתח הציבורי הוא (p, q, z, y) ואילו המפתח הפרטי הוא: a. ניתן לשתף את המפתח הציבורי בין מספר משתמשים.
תהליך החתימה
החתימה על המסר m מתבצעת בעצם עם (H(m שהוא ערך ההאש של m:
1. יוצרים מספר אקראי סודי k הנמוך מ-q.
2. מחשבים את r = (zk mod p) mod q.
3. מחשבים את k-1 mod q (ההופכי של k תחת q).
4. מחשבים את s = k-1(H(m)+ar) mod q.
החתימה היא הצמד (r, s).
תהליך אישור החתימה
1. תחילה בודקים כי הערכים r ו-s נמוכים מ-q (במקרה שלא החתימה אינה מתקבלת).
2. מחשבים את w = s-1 mod q.
3. מחשבים את u1 = w * H(m) mod q וכן את u2 = rw mod q.
4. מחשבים את v = (zu1*yu2 mod p) mod q.
החתימה מתקבלת כאותנטית אך ורק אם v = r.
הוכחה לנכונות תהליך האישור: אם הערכים (r, s) הנם החתימה הלגיטימית של החותם על המסר m אזי H(m)=-ar+ks (mod q). אם מכפילים את שני צידי המשוואה ב-w אחרי סידור מחדש מקבלים w*H(m)+arw=k (mod q). למעשה הדבר שקול ל-(u1+au2=k (mod q. אם מעלים את z בחזקת שני צידי המשוואה מקבלים (zu1*yu2 mod p) mod q = (zk mod p) mod q, על כן v = r.
אלגוריתם העירבול (H(m המשמש את DSA הוגדר בתקן FIPS 186-1 כפונקציית ערבול בטוחה SHA-1. אולם מאחר ולאחרונה התגלו טכניקות חדשות המטילות בספק את בטיחותו, תקן FIPS 186 העדכני מגדיר דרישה לפונקציית ערבול בטוחה יותר כגון SHA-224 ומעלה.