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 מבוסס על בעיית הלוגריתם הבדיד והוא וריאציה של אל-גמאל. הוא מנצל את הקושי שבפתרון בעיית חישוב לוגריתמים בחבורות, שהיא כידוע בעיה קשה מבחינה חישובית. למעשה האלגוריתם מסתמך על שתי בעיות קשורות של לוגריתם בדיד. האחת לוגריתם בדיד בחבורה כיפלית $\ Z_{p}^{*}$ מודולו $\ p$ (ראשוני) גדול. והשנייה מציאת לוגריתמים בתת-חבורה ציקלית מסדר ראשוני $\ q$ כלשהו ($\ q<p$). כמו כן מנגנון החתימה כולל, שימוש בפונקציית גיבוב.

חתימה ואימות

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

$\ p$ מודולוס ראשוני גדול, המקיים $\ 2^{L-1}<p<2^{L}$

($\ L$ מייצג את גודל $\ p$ בסיביות, ראו להלן).

$\ q$ מחלק ראשוני של ($\ p-1$), המקיים $\ 2^{N-1}<q<2^{N}$

($\ N$ מייצג את גודל $\ q$ בסיביות, ראו להלן).

$\ g$ יוצר של תת-חבורה מסדר $\ q$ מודולו $\ p$, כאשר $1<g<p$.

להכנת $\ 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$ בהתאמה לפי הטבלה הבאה:

N = 160	L = 1024
N = 224	L = 2048
N = 256	L = 2048
N = 256	L = 3072

חתימת 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$ הופקו על ידי בעל החתימה הלגיטימי מהערך $\ z$, אזי חייב להתקיים:

$\ z\equiv -xr+ks\ ({\mbox{mod }}q)$.

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

$\ w\cdot z+xrw\equiv k\ ({\mbox{mod }}q)$.

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

$\ u_{1}+xu_{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$.

תהליך אימות החתימה: כדי לוודא כי החתימה על הערך $\ z=159$ נכונה, המקבל משתמש במפתחות הפומביים תחילה כדי לחשב את: $\ w=565^{-1}=748\ ({\mbox{mod }}787)$ ואז מחשב את: $\ u_{1}=748\cdot 159{\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 המתוארת. התקן מפרט פרמטרים בטוחים שיטות ותהליכים של חתימה ואימות לצורך חתימה דיגיטלית המשתמשת בעקום אליפטי וכן מנחה כיצד לבחור מפתחות (מפתח פרטי/מפתח ציבורי) בהתאם לסט פרמטרים מסוים שנקרא פרמטרי תחום של העקום האליפטי, שהם בדרך כלל אוסף של ערכים קבועים שיכולים להיות משותפים למספר גדול של משתמשים ומגובלים לתקופה מסוימת, בדרך כלל מספר שנים.

הכנת פרמטרים

לצורך החתימה הדיגיטלית, החותמת אליס צריכה להכין תחילה מספר פרמטרים קבועים של המערכת וכן מפתחות אימות וחתימה. תחילה אליס בוחרת שדה מסדר $q$, מתוכו היא בוחרת באופן אקראי שני מקדמים $a$ ו-$b$ המייצגים את העקום האליפטי $E:y^{2}=x^{3}+ax+b$ במקרה שסדר השדה הוא $p=q$ ראשוני, או $E:y^{2}+xy=x^{3}+ax^{2}+b$ במקרה של שדה בינארי מורחב כאשר $q=2^{m}$. היא מחשבת את $N=\#E(\mathbb {F} _{q})$ מספר הנקודות בעקום האליפטי $E$ ומוודא שהוא מתחלק במספר ראשוני $n$ גדול $(n>2^{160})$. היא בוחרת את הקואורדינטות $(x_{G},y_{G})$ ומגדירה את נקודת הבסיס $G$ שהיא מסדר $n$ ראשוני גדול ב-$E(\mathbb {F} _{q})$. ולבסוף מחשבת את הגורם המשלים $h$ כך שמתקיים $h=\#E(\mathbb {F} _{q})/n$. לסיכום פרמטרי התחום הבסיסיים של ECDSA הם: $(q,a,b,G,n,h)$.

בנוסף אליס קובעת את הבסיס האריתמטי לצורך חישוב הפעולות בשדה. אם השדה מסדר ראשוני כאשר $q=p$ הקואורדינטות הן שני שלמים חיוביים $(x,y)$ וכל פעולות החיבור והכפל מבוצעות מודולו $n$. אם השדה הוא בינארי מורחב כאשר $q=2^{m}$ הקואורדינטות הן פולינומים ממעלה $m$ עם מקדמים בינאריים. התקן כולל שדה אופציונלי הנקרא ${\text{seed}}$ שהוא מחרוזת סיביות אקראית הנקראת גרעין התחלתי והיא שימושית כאשר העקום נוצר באופן אקראי באמצעות מחולל פסאודו אקראי קריפטוגרפי, שאיתה ניתן יהיה לאמת לאחר מכן בבדיקה פשוטה שלא הוחדרה לפרמטרים של העקום האליפטי דלת אחורית במכוון.

אפשר להכין פרמטרי תחום לבד או להשתמש בסטים מומלצים של תקן X9.62 שהוכנו ונבדקו על ידי מומחים. אם מכינים את הפרמטרים באופן עצמאי רצוי להכין את הנקודה $G$ באופן בטוח. ההמלצה היא להשתמש בפונקציית גיבוב קריפטוגרפית בטוחה לפי תקן SP 800-57 כך שניתן יהיה לוודא שאינה מכילה דלת אחורית. יש לשים לב שביטחון פונקציית הגיבוב לא יהיה נמוך מביטחון פרמטרי התחום הנקבע על ידי $n$. התקן כולל חמישה סטים מוכנים של עקומים אליפטיים לצורך חתימה דיגיטלית באורכים שונים של $n$ החל מ-160 סיביות ועד 512 סיביות או יותר. השדה יכול להיות שדה ראשוני $F_{q}$ כאשר $q$ ראשוני או שדה בינארי מורחב $F_{2^{m}}$ כאשר $m$ הוא שלם חיובי גדול והוא מתחלק לשלושה סוגים:

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

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

הכנת מפתחות

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

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

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

חתימה ואימות

כדי לחתום על המסר $m$ החותמת אליס משתמשת בפרמטרי התחום $(q,a,b,G,n,h)$ השייכים למפתח הפרטי והציבורי המתאימים שלה $(d,Q)$ ומבצעת כדלהלן:

1. בוחרת שלם אקראי $k$ הנמוך מ-$n$.
2. מחשבת את הנקודה $kG$ ונוטלת את הקואורדינטה ה-$x$ שלה וממירה אותה למספר שלם $x_{1}$.
3. מחשבת את $r=x_{1}{\text{ mod }}n$. אם $r=0$ חוזרת להתחלה.
4. מחשבת את $k^{-1}{\text{ mod }}n$.
5. מחשבת את ערך הגיבוב של המסר $e={\text{SHA-2}}(m)$ ומתייחסת ל-$e$ כאל מספר שלם.
6. מחשבת את $s=k^{-1}(e+dr){\text{ mod }}n$. אם $s=0$ חוזרת להתחלה.
7. החתימה של אליס על $m$ היא $(r,s)$.

כדי לאמת את החתימה $(r,s)$ על המסמך $m$ המוודא בוב משיג תחילה עותק אותנטי של המפתח הציבורי של אליס $Q$ יחד עם פרמטרי התחום של העקום האליפטי ששימש לחתימה $(q,a,b,G,n,h)$ ופועל כדלהלן:

1. מוודא ש-$r$ ו-$s$ הם שלמים חיוביים בטווח $[1,n-1]$ אם לא הוא דוחה את החתימה.
2. מחשב את ערך הגיבוב של המסר $e={\text{SHA-2}}(m)$.
3. מחשב את $w=s^{-1}{\text{ mod }}n$.
4. מחשב את $u_{1}=ew{\text{ mod }}n$ וכן $u_{2}=rw{\text{ mod }}n$.
5. מחשב את הנקודה $X=u_{1}G+u_{2}Q$. אם $X={\mathcal {O}}$ דוחה את החתימה.
6. ממיר את הקואורדינטה $x$ של הנקודה $X$ למספר שלם $x_{1}$.
7. מחשב את $v=x_{1}{\text{ mod }}n$.
8. החתימה מתקבלת כאוטנתית רק אם $v=r$.

הוכחת נכונות: אם החתימה $(r,s)$ על המסר $m$ נוצרה על ידי אליס אז $s=k^{-1}(e+dr){\text{ mod }}n$, לאחר סידור מחדש מתקבל:

$k\equiv s^{-1}(e+dr)\equiv s^{-1}e+s^{-1}rd\equiv we+wrd\equiv u_{1}+u_{2}d{\text{ (mod }}n)$,

לכן $u_{1}G+u_{2}Q=(u_{1}+u_{2}d)G=kG$ ומזה נובע $v=r$ כנדרש.

ערך חד פעמי

יש לייצר מספר חד-פעמי $k$ שונה עבור כל מסמך שאליס מעוניינת לחתום עליו אחרת ניתן יהיה לחשוף את מפתח החתימה הפרטי שלה בגלל העובדה ש-

$d=r^{-1}(ks-e){\text{ mod }}n$

וכל הערכים באגף הימני של המשוואה ידועים למעט $k$. לכן יש צורך ש-$k$ יהיה חד פעמי ובלתי צפוי. אם אליס תחתום על שני מסמכים שונים עם אותו $k$ אפשר יהיה לבצע התקפה נגד החתימה ולחשוף את המפתח הפרטי של אליס כדלהלן: נניח שהחתימות של אליס הן $(r,s_{1})$ ו-$(r,s_{2})$ עבור המסרים $m_{1}$ ו-$m_{2}$ בהתאמה. אז

$s_{1}\equiv k^{-1}(e_{1}+dr)$ וכן

$s_{2}\equiv k^{-1}(e_{2}+dr)$

כאשר $e_{1}$ ו-$e_{2}$ הם תמציות הגיבוב של המסמכים $m_{1}$ ו-$m_{2}$ בהתאמה. מזה נובע

$ks_{1}\equiv e_{1}+dr$ וכן

$ks_{2}\equiv e_{2}+dr$

אם מחסרים $k(s_{1}-s_{2})\equiv e_{1}-e_{2}$ ואם $s_{1}\neq s_{2}$ מה שאמור לקרות בהסתברות גבוהה אז מתקבל

$k\equiv (s_{1}-s_{2})^{-1}(e_{1}-e_{2})$.

בכך היריב הצליח לחלץ את $k$ ואיתו הוא יכול לחשב את המפתח הפרטי של אליס. (כל החישובים כאמור הם מודולו $n$).

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

אלגוריתם גיבוב

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

ראו גם

• חתימה דיגיטלית
• אל-גמאל (חתימה דיגיטלית)

קישורים חיצוניים

• אתר NIST, תקן FIPS 186-4
• פוסט על התקלה במחולל המספרים האקראיים באנדרואיד