Digital Signature Algorithm (אלגוריתם חתימה דיגיטלית) הוא מנגנון קריפטוגרפי לחתימה דיגיטלית.
הוא אומץ כתקן פדרלי בארצות הברית (FIPS) בתחילת 1993. NIST הציע את DSA ב-1991 כחלק מ-FIPS 186. האלגוריתם היה רשום כפטנט על שם דויד קרביץ אך שוחרר לשימוש חופשי על ידי הממשלה. חתימת DSA היא תווית נפרדת מהמסר ולא הצפנה: היא מאשרת מקור ושלמות המידע, בעוד שהמסר יכול להישאר קריא.
הרעיון של DSA נשען על בעיית הלוגריתם הבדיד. זוהי בעיה חישובית קשה: קשה למצוא ח' כאשר יודעים g^h במודול מספר ראשוני p. DSA היא וריאציה של אלגורתם אל-גמאל ומנצלת את הקושי הזה בחבורות ומחלקות ראשוניות. בנוסף משתמשים בפונקציית גיבוב (hash) כדי לקצר ולייצג את המסר.
פרמטרים בסיסיים: p (ראשוני גדול), q (מחלק ראשוני של p-1), g (יוצר תת-חבורה), מפתח פרטי x ומפתח ציבורי y=g^x mod p. בעת החתימה נבחר מספר אקראי חד-פעמי k וכן פונקציית גיבוב H (למשל SHA-2).
כיצד חותמים בקצרה: מחשבים r=(g^k mod p) mod q. מחשבים z מהביטים הנמוכים של H(m). ואז s = k^{-1}(z + x r) mod q. החתימה היא הזוג (r,s). יש לוודא ש-r ו-s לא שווים 0.
כיצד מאמתים בקצרה: הבודק מחשב w=s^{-1} mod q, z מהגיבוב, u1=zw mod q ו-u2=rw mod q. לאחר מכן מחשבים v = ((g^{u1} y^{u2} mod p) mod q). החתימה תקפה אם v = r. אם לא, ייתכן שהמסר או החתימה שונו.
אם החותם ייצר את r ו-s כראוי, מתקיימות שקילויות שמובילות לכך ש-(g^{u1} y^{u2} mod p) mod q = (g^k mod p) mod q, כלומר v=r. זו הצורה המקוצרת של ההוכחה המתמטית.
יש דוגמה מספרית עם p=4723, q=787, g=3045 ומפתח פרטי x=211. המפתח הציבורי הוא y=4583. בחירה של k=293 הניבה חתימה r=519 ו-s=565. בתהליך האימות מחושבים ערכים שונים ומקבלים v=519, ולכן החתימה מתקבלת.
ECDSA היא גרסה של חתימת DSA שעובדת על עקומות אליפטיות. התקן X9.62 מפרט פרמטרים בטוחים ושיטות בחירה של מפתחות לפרמטרי תחום של העקום (q,a,b,G,n,h).
ב-ECDSA בוחרים שדה (פלטפורמת חישוב), מקדמים a ו-b של העקום, נקודת בסיס G וסדר n. מחשבים את מספר הנקודות על העקום ומוודאים שחולק ב-n. יש אפשרות להשתמש ב-seed כדי לבדוק שהעקום נוצר ללא דלת אחורית.
המפתח הפרטי הוא מספר סודי d. המפתח הציבורי הוא נקודה Q = dG על העקום. יש לוודא תקינות ושייכות של הפרמטרים לפני שימוש.
החותם בוחר k אקראי < n, מחשב את הנקודה kG, מוציא ממנה את x ומחשב r = x mod n. מחשב s = k^{-1}(e + d r) mod n כאשר e הוא הגיבוב של המסר. החתימה היא (r,s).
לאימות המוודא בודק תחילה טווח תקינות של r ו-s, מחשב e ו-w=s^{-1} mod n, מחשב u1=ew mod n ו-u2=rw mod n, ואז X=u1G+u2Q. אם X הוא נקודה תקינה וה-x שלה מביא v = r, החתימה מוגדרת תקינה.
חשיבות בחירת k שונה לכל חתימה: אם משתמשים באותו k לשני מסמכים, אפשר לחשוף את k ואז לחשוף את המפתח הפרטי. טעויות כאלה אכן קרו בעבר (למשל ב-PS3 ובמקרים של מחוללים לא בטוחים באנדרואיד ששפיעו על ארנקים בביטקוין).
חתימה דיגיטלית מבוססת על גיבוב של המסר קודם לחתימה. בעבר השתמשו ב-SHA-1, אך כיום ממליצים על SHA-2 כיוון ש-SHA-1 נחלש.
Digital Signature Algorithm (DSA) הוא שיטה לחתימה דיגיטלית.
החתימה מאמתת מי שלח את המסר ושומרת על שלמותו. היא לא מצפינה את המסר.
הביטחון ב-DSA מבוסס על בעיה מתמטית קשה שנקראת לוגריתם בדיד. קשה לפתור את הבעיה הזו, ולכן קשה לזייף חתימות.
יש שני מפתחות: פרטי וסודי, וציבורי שכולם יכולים לראות.
כדי לחתום בוחרים מספר אקראי k שמשתמשים בו רק פעם אחת. מחשבים שני מספרים r ו-s מהמסר ומהמפתחות. החתימה היא (r,s).
כדי לבדוק חתימה, משתמשים במפתח הציבורי. מחשבים כמה ערכים ובודקים אם v שווה ל-r. אם כן, החתימה אמיתית.
ECDSA היא גרסה של DSA שמשתמשת בעקומות אליפטיות. עם עקומות אפשר לקבל אבטחה דומה עם מספרים קטנים יותר.
חשוב שכל חתימה תקבל k שונה. אם משתמשים באותו k פעמיים, אפשר לגלות את המפתח הפרטי ולגנוב חתימות. זה קרה בעבר במשחקים ובארנקים של ביטקוין.
לפני החתימה מחשבים גיבוב של המסר. גיבוב הוא מספר קבוע שמייצג את המסר. כיום משתמשים ב-SHA-2 כדי שהגיבוב יהיה בטוח.
תגובות גולשים