חתימה דיגיטלית של שנור

בקריפטוגרפיה, חתימה דיגיטלית של שנור היא שיטת חתימה דיגיטלית שפותחה ב-1989 על ידי קלאוס שנור^[1] המבוססת על הצפנת אל-גמאל והיא יעילה יותר מ-DSA. חתימת שנור ידועה בפשוטתה והביטחון שלה מבוסס על הקושי המשוער של בעיית הלוגריתם הבדיד. היא מייצרת חתימה קצרה והחישובים שהצדדים צריכים לעשות יעילים ביחס לחתימת DSA. החתימה נרשמה בארצות הברית כפטנט שתוקפו פג ב-2008.

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

תיאור כללי

החתימה משתמשת במספר ראשוני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} כך של-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} יש גורם ראשוני גדול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} (לפחות 140 סיביות) וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} שהוא בסיס הלוגריתם הדיסקרטי (מודולו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} ) כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha^q\equiv 1\text{ (mod }p)} . אורך החתימה קצר בהרבה מחתימת RSA או DSA (במאמר המקורי זה היה בערך 212 סיביות, אך מן הסתם לאור ההתקדמות הטכנולוגית נדרשים מספרים יותר גדולים). ביטחון החתימה מסתמך על החד-כיווניות של ההעלאה בחזקה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y=\alpha^x\text{ (mod }p)} . בהנחה שלוגריתם בדיד בסדר גודל כזה קשה מאד לחישוב. החתימה על המסר נוצרת באופן כזה שכדי לזייפה יש צורך לחשב את הלוגריתם הבדיד.

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

פירוט מהלכי האלגוריתם

תחילה לצורך אתחול, מכינים את הראשוניים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p|(q-1)} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p\ge2^{512}} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q\ge 2^{140}} . במקרה זה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} נקרא ראשוני חזק. חשוב לזכור שהמספרים הללו נכונים רק לעת כתיבת המאמר המקורי של שנור. יש צורך לעדכן אותם בהתאם. בוחרים יוצר $\alpha \in \mathbb {Z} _{p}$ מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha^q\equiv 1\text{ (mod }p)} בתנאי ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha\ne 1} . כמו כן בוחרים פונקציית גיבוב מתאימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle h:\mathbb{Z}_q\times\mathbb{Z}\rightarrow\{0,...,2^t-1\}} (פונקציית גיבוב שמפיקה פלט באורך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} סיביות) כאשר $t$ הוא פרמטר ביטחון (נניח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t=80} ). הפרמטרים הציבוריים המשותפים לכל המשתמשים במערכת יהיו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p,q,\alpha,h)} . אותם אפשר להכין על ידי צד שלישי נאמן. אותו צד שלישי יצטרך כנראה גם הוא לחתום בחתימה נפרדת על הערכים הללו כדי להבטיח את שלמותם.

כל משתמש צריך להכין מפתח פרטי ומפתח ציבורי כאשר המפתח הפרטי משמש לחתימה והמפתח הציבורי לאימות. הוא מגריל שלם אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} ומחשב את המפתח הציבורי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\equiv \alpha^{-s}\text{ (mod }p)} (כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s=-\log_{\alpha}v} ). את $s$ הוא שומר בסוד ואת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} הוא מפרסם בדרך כלשהי. הפרוטוקול הבא מתאר את תהליך החתימה של אליס על מסמך כלשהו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} ותהליך האימות של בוב.

לצורך החתימה אליס מחשבת את הערכים הבאים:

מגרילה שלם אקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} ומחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\equiv \alpha^r\text{ (mod }p)} .
מחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e=h(x,m)} (ערך הגיבוב באורך $t$ סיביות של המסר יחד עם המפתח הארעי).
מחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y=r+se\text{ (mod }q)} .
החתימה על המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} היא זוג הערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (e,y)} .

לצורך אימות החתימה בוב משתמש במפתח האימות הציבורי של אליס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} כדי לבדוק את הערכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (e,y)} שקיבל כך:

מחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x'=\alpha^yv^e\text{ (mod }p)}
בודק שמתקיים $e=h(x',m)$ ורק אם השוויון מתקיים הוא מקבל את החתימה.

אם החתימה נוצרה לפי הפרוטוקול אז זה נכון ש-

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{x\equiv\alpha^r\equiv\alpha^{r+se}v^e\equiv\alpha^yv^e\text{ (mod }p)}} .

לצורך החתימה צריך להעלות בחזקה אחת ולבצע כפל מודולרי אחד וחיבור אחד, חלק מהם ניתנים לחישוב מראש. לצורך האימות נדרשות שתי העלאות בחזקה מודולרית. את שתיהן אפשר לבצע בסיבוכיות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1.5\ell+0.25 t} פעולות כפל מודולרי כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell=\lceil\log_2q\rceil} (האורך של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} בסיביות). הטריק הוא לחשב את ההעלאה בחזקה כדלהלן:

תחילה מחשבים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha v} ואז מקבלים את $x'$ על ידי הפעולות הבאות.
מצביבים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=\ell,z=1}
כל עוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i\ge 0} מבצעים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=i-1,z=z^2\alpha^{y_i}v^{e_i}\text{ (mod }p)} .

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_i} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} הן הסיבית ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} החל מימין לשמאל לפי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle y=\sum_{i=0}^{\ell-1}y_i2^i} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle e=\sum_{i=0}^{\ell-1} e_i2^i} .

הערך האקראי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} נקרא מפתח ארעי. כלומר זהו מספר חד-פעמי שהוגרל לטובת חתימה על מסר אחד. בגלל התכונות של הלוגריתם הבדיד, כמו בהצפנת אל-גמאל, אסור לחתום על יותר ממסמך אחד עם אותו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} כי אז אפשר לגלות את מפתח החתימה. כי אם נניח שבידי המתקיף שתי חתימות (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e,y} ) וכן (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e',y'} ) אז תמיד מתקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y'-y=(r'-r)-s(e'-e)}

לכן אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r'=r } אבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e'\ne e} המתקיף יכול לבודד את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} על ידי חילוק ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (e'-e)} .

דוגמה במספרים קטנים

נניח שהפרמטרים של המערכת הם (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p=467,q=233,\alpha=153} )

מפתח החתימה הפרטי של אליס הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s=202}
מפתח האימות הציבורי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v=153^{-202}\equiv 198\text{ (mod }467)} .

כעת לצורך החתימה על המסר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m } היא בוחרת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r=94} ומחשבת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=153^{94}\equiv 38\text{ (mod }467)} .

נניח שערך הגיבוב על המסר עם המפתח הארעי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle e=h(m,38)=120} החתימה על המסר היא אם כן הזוג (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 120,102} ) כי מתקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 38\equiv 153^{94}\equiv 153^{94+202\cdot 120}\cdot 198^{120}\equiv 153^{102}\cdot 198^{120}\text{ (mod }467)}

אם אליס תשתמש באותו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r=94} כדי לחתום על מסר אחר, נניח שהחתימה השנייה שהתקבלה היא (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 50,175} ) תוצאה זו התקבלה אם כל הערכים למעט המסר זהים. אז מתוך שתי החתימות אפשר לחשב את:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (y'-y)=(175-102)=73\text{ (mod }233)} , ואת

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (e'-e)=(50-120)\equiv 163\text{ (mod }233)}

להכפיל בהופכי הכפלי של 163 (מודולו 233) שהוא 223 ומתקבל

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (73\cdot 223)\text{ mod }233=202}

וזהו מפתח החתימה.

חתימה עיוורת

ערך מורחב – חתימה עיוורת

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

ביטחון

חתימת שנור היא שילוב של פרוטוקול אימות של שנור יחד עם רעיון רב ההשפעה של עמוס פיאט ועדי שמיר^[2]. פונקציית הגיבוב לצורך חתימת שנור לא חייבת להיות חסינת התנגשויות, מחקרים^[3] מראים שבניגוד ל-DSA אפשר להסתפק בחתימת שנור בפונקציית גיבוב חלשה כמו SHA-1 וכן אפשר להסתפק בערך גיבוב קצר יותר בכעשרים וחמש אחוז.

הביטחון של חתימת שנור ניתן להוכחה במסגרת מודל אורקל אקראי תחת ההשערה שבעיית הלוגריתם הבדיד קשה. ב-2012 בוצע מחקר^[4] באשר לביטחון המדוייק של חתימת שנור והטענה היא שלפי למת הפיצול (Forking Lemma) קיים איבוד זמן בפקטור של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(q_h)} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_h} הוא מספר השאילתות לאורקל האקראי. במילים אחרות אם קיים זייפן שיכול לזייף חתימת שנור בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon_F} אז אפשר יהיה לחשב את הלוגריתם הבדיד בהסתברות קבועה על ידי חזרה לאחור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(q_h/\epsilon_F)} פעמים, תחת הנחות נוספות אפשר להגיע לרדוקציה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_h^{2/3}} לכל היותר בשיעור ההצלחה/זמן.

ראו גם

הערות שוליים

^ C. P. Schnorr, “Efficient Identification and Signatures for Smart Cards,” In: G. Brassard, Ed., Advances in Cryptology—Crypto’89, Lecture Notes in Computer Science No 435, Springer-Verlag, 1990. pp. 239-252.
^ Fiat; Shamir (1986). "How To Prove Yourself: Practical Solutions to Identification and Signature Problems" (PDF). Proceedings of CRYPTO '86.
^ Hash function requirements for Schnorr signatures
^ Seurin, Yannick (2012-01-12). "On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model" (PDF). Cryptology ePrint Archive. International Association for Cryptologic Research. Retrieved 2014-08-11.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

24744623

[1] C. P. Schnorr, “Efficient Identification and Signatures for Smart Cards,” In: G. Brassard, Ed., Advances in Cryptology—Crypto’89, Lecture Notes in Computer Science No 435, Springer-Verlag, 1990. pp. 239-252.

[2] Fiat; Shamir (1986). "How To Prove Yourself: Practical Solutions to Identification and Signature Problems" (PDF). Proceedings of CRYPTO '86.

[3] Hash function requirements for Schnorr signatures

[4] Seurin, Yannick (2012-01-12). "On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model" (PDF). Cryptology ePrint Archive. International Association for Cryptologic Research. Retrieved 2014-08-11.

[1]

[2]

[3]

[4]