Digital Signature Algorithm

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

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

DSA sign.jpg

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

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

DSA verify.jpg

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

אלגוריתם חתימה דיגיטאלית 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 כך ש-\ 1 < h < (p-1) ומחשבים את \ 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. יהיה \ z שווה \ \mbox{min}(N, outlen) הסיביות הנמוכות של \ \mbox{H}(M) כאשר \ outlen מייצג את האורך בסיביות של תוצאת פונקציית הגיבוב.
  3. \ s = (k^ {-1} (z + xr)) \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. יהיה \ z שווה \ \mbox{min}(N, outlen) הסיביות הנמוכות של \ \mbox{H}(M)
  3. \ u_1 = (zw) \mbox{ mod } q
  4. \ u_2 = (rw) \mbox{ mod } q
  5. \ v = ((g^{u_1} y^{u_2}) \mbox{ mod } p) \mbox{ mod } q

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

הוכחה לנכונות האלגוריתם[עריכת קוד מקור | עריכה]

אם \ r ו-\ s הופקו על ידי בעל החתימה הלגיטימי מהמסר \ m, אזי חייב להתקיים:

\ \mbox{H}(m) \equiv -ar+ks \ (\mbox{mod }q).

אם מכפילים את שני אגפי השקילות הזו ב-\ w, אחרי העברת אגפים מתקבל:

\ w \cdot \mbox{H}(m)+arw=k \ (\mbox{mod }q).

תוצאה זו למעשה שקולה ל:

\ u_1+au_2 \equiv k \ (\mbox{mod }q).

אם מעלים את \ g בחזקת שני אגפי השקילות האחרונה מתקבל:

\ (g^{u_1} \cdot y^{u_2} \mbox{ mod }p)\mbox{ mod }q = (g^k \mbox{ mod }p) \mbox{ mod }q.

על כן \ v=r.

דוגמה[עריכת קוד מקור | עריכה]

הכנת מפתח חתימה: בוחרים את הראשוני \ q=787 וכן \ p=6 \cdot q+1=4723, היוצר \ g=3045. ובוחרים מפתח פרטי למשל \ x=211 ומחשבים את \ y=3045^{211} \mbox{ mod }4723=4583. המפתחות הפומביים יהיו: \ \{4723,787,3045,4583\} ואילו המפתח הפרטי יהיה: \ 211.

תהליך החתימה: בוחרים אלמנט אקראי, נניח \ k=293, מחשבים את \ r=(3045^{293} \mbox{ mod }4723) \mbox{ mod }787=519 וכן מחשבים את ההופכי \ k^{-1}=231 \ (\mbox{mod }787). אם המסר המיועד לחתימה הוא \ m=344865, אזי: \ s=231 \cdot (344865+211 \cdot 519)\mbox{ mod }787 = 565. החתימה על המסר היא אם כן \ s=565, \ r=519.

תהליך אימות החתימה: כדי לוודא כי החתימה על המסר \ m=344865 נכונה, המקבל משתמש במפתחות הפומביים תחילה כדי לחשב את: \ w=565^{-1} = 748 \ (\mbox{mod }787) ואז מחשב את: \ u_1=748 \cdot 344865 \mbox{ mod }787=95 וכן \ u_2=519 \cdot 748 \mbox{ mod }787=221 ולבסוף: \ v=(3045^{95} \cdot 4583^{221})\mbox{ mod }4723) \mbox{ mod }787 = 519 וכיוון ש- \ r=v החתימה מתקבלת.

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

ECDSA[עריכת קוד מקור | עריכה]

תקן ANS X9.62 (הצפנת מפתח ציבורי למגזר העסקי) שפותח על ידי Accredited Standards Committee X9 עבור ANSI, כולל גם תקן חתימה דיגיטלית מבוססת עקום אליפטי הנקראת ECDSA (קיצור של Elliptic Curve Digital Signature Algorithm) שהיא אנלוגית לחתימת DSA המתוארת. התקן מפרט פרמטרים בטוחים שיטות ותהליכים של חתימה ואימות לצורך חתימה דיגיטלית המשתמשת בעקום אליפטי וכן מנחה כיצד לבחור מפתחות (מפתח פרטי/מפתח ציבורי) בהתאם לסט פרמטרים מסויים שנקרא פרמטרי תחום של העקום האליפטי, שהם בדרך כלל אוסף של ערכים קבועים המשותפים למספר גדול של משתמשים ומגובלים לתקופה מסויימת, בדרך כלל מספר שנים.

פרמטרי התחום עבור ECDSA כוללים את: (q,\text{FR},a,b,\text{seed},G,n,h) כאשר q הוא סדר השדה האריתמטי, FR מציין בסיס לצורך החישובים האריתמטיים של אלגוריתם החתימה, a ו-b הם אלמנטים בשדה GF(q) שהם חלק ממשוואת העקום, \text{seed} הוא מחרוזת סיביות אופציונלית הנקראת גרעין התחלתי והיא שימושית כאשר העקום נוצר באופן אקראי בדרך שניתנת לבדיקה, G הוא נקודת בסיס בעקום מסדר n המכילה קואורדינטות (x_G,y_G)\in GF(q), כאשר n הוא מספר ראשוני המשמש כפרמטר בטחון ו-h נקרא פקטור משלים (שהוא סדר העקום לחלק ל-n). התקן כולל חמשה אורכים שונים עבור n החל מ-160 סיביות ועד 512 סיביות או יותר. השדה יכול להיות שדה ראשוני GF(q) כאשר q ראשוני או שדה בינארי מורחב GF(2^m) כאשר m הוא שלם חיובי גדול והוא מתחלק לשלושה סוגים:

  • עקום אליפטי מעל שדה ראשוני המיוצג על ידי \text{P-xxx}.
  • עקום אליפטי מעל שדה בינארי מורחב המיוצג על ידי \text{B-xxx}.
  • עקום אליפטי מסוג קובליץ המיוצג על ידי \text{K-xxx}.

xxx מציין את מספר הסיביות של גודל השדה.

אפשר להכין פרמטרי תחום לבד או להשתמש בסטים מומלצים של תקן X9.62 שהוכנו ונבדקו על ידי מומחים. אם מכינים את הפרמטרים באופן עצמאי רצוי להכין את הנקודה G באופן בטוח. ההמלצה היא להשתמש בפונקציית גיבוב קריפטוגרפית בטוחה לפי תקן SP 800-57 כך שניתן יהיה לוודא שאינה מכילה דלת אחורית. יש לשים לב שביטחון פונקציית הגיבוב לא יהיה נמוך מביטחון פרמטרי התחום הנקבע על ידי n.

המפתח הפרטי של החותם הוא שלם אקראי סודי d ואילו המפתח הציבורי הוא נקודה בעקום Q. להכנת המפתחות מוצעות שתי שיטות:

  • תחילה מכינים מספר אקראי c באורך המומלץ על ידי התקן באמצעות מחולל פסאודו אקראי קריפטוגרפי ואז מחשבים את d=(c\text{ mod }(n-1))+1 והמפתח הציבורי הוא Q=d\times G. כלומר מכפלה סקלרית של הנקודה G ב-d.
  • לחילופין, בוחרים באותה דרך מספר אקראי c עד שמתקיים c\le n-2 אם התנאי אינו מתקיים בוחרים מספר אחר. ואז המפתח הפרטי הוא d=c+1 והמפתח הציבורי הוא Q=d\times G.

לפני חתימה על מסר יש לוודא שהערכים הבאים הוכנו לפי המלצות התקן, נבדקו ואומתו:

  1. פרמטרי תחום (q,\text{FR},a,b,\text{seed},G,n,h).
  2. מפתח פרטי d ומפתח ציבורי Q.
  3. מספר אקראי חד-פעמי k המתאים למסר אחד.
  4. ההופכי הכפלי של k מודולו n המסומן k^{-1}.
  5. וכן מכינים פונקציית גיבוב ומחולל פסאודו אקראי בטוחים לשימוש קריפטוגרפי.

החתימה דומה לחתימת DSA, בהינתן המסמך m החותם מבצע כדלהלן:

  1. מחשבים את ערך הגיבוב של המסמך m למשל h=H(m) כאשר H היא פונקציית גיבוב כמו SHA-2.
  2. אם N=\text{len}(n) הוא אורך הפרמטר n בסיביות אזי z יהיה מספר שלם המתקבל מ-N הסיביות המשמעותיות (העליונות) של h.
  3. מחשבים את הנקודה בעקום (x_1,y_1)=k\times G.
  4. מחשבים את r=x_1\text{ mod }n (אם r=0 יש לבחור k אחר ולחזור לצעד 3).
  5. מחשבים את s=k^{-1}(z+rd)\text{ mod }n (אם s=0 יש לבחור k אחר ולחזור לצעד 3).
  6. החתימה היא (r,s).

לאימות החתימה תחילה המאמת צריך לבדוק שפרמטרי התחום וכן המפתח הציבורי של החותם תקינים ושייכים לו. לשם כך יתכן שיצטרך להעזר בצד שלישי. לאימות החתימה המאמת פועל כדלהלן:

  1. בודק שהערכים (r,s) הם שלמים חיוביים הנמוכים מ-n, אם לא הוא דוחה את החתימה.
  2. מחשב את פונקציית הגיבוב של המסמך h=H(m).
  3. נוטל את N הסיביות המשמעותיות של h וממיר אותן למספר שלם z.
  4. מחשב את w=s^{-1}\text{ mod }n. (כך ש-w הוא ההופכי הכפלי של s מודולו n).
  5. מחשב את u_1=zw\text{ mod }n וכן u_2=rw\text{ mod }n.
  6. מחשב את הנקודה בעקום (x_1,y_1)=u_1\times G+u_2\times Q.
  7. החתימה תתקבל אך ורק אם r\equiv x_1\text{ (mod }n) אחרת החתימה או המסמך השתבשו, ייתכן במזיד.

תנאי הכרחי כדי שהחתימה תהיה בטוחה הוא להשתמש ב-k אך ורק פעם אחת. כדי לראות למה, נניח שהחותם השתמש ב-k כלשהו לחתימה על שני מסמכים שתמציות הגיבוב שלהם הן z_1, z_2 כך שלאחר החתימה התקבלו (r,s_1) ו-(r,s_2) בהתאמה. היות שמתקיים s_1-s_2=k^{-1}(z_1-z_2) (מודולו n) המתקיף יכול לחשב את \textstyle k=\frac{z_1-z_2}{s_1-s_2} וכן s_1=k^{-1}(z_1+rd) ועם זה הוא יכול לגלות את המפתח הפרטי כי \textstyle d=\frac{s_1k-z_1}{r}.

הטעות הזו למעשה ארעה במציאות בתהליך החתימה הדיגיטלית של קונסולת המשחקים פלייסטיישן 3. בנוסף יש להיזהר ממחולל פסאודו אקראי לא בטוח. ב-2013 התגלתה פרצה חמורה בביטקוין שנבעה משימוש במחולל גרוע לצורך חתימת ECDSA.

אלגוריתם גיבוב[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]