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

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

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

תיאור כללי

החתימה משתמשת במספר ראשוני ${\displaystyle p}$ כך של-${\displaystyle p-1}$ יש גורם ראשוני גדול ${\displaystyle q}$ (לפחות 140 סיביות) וכן ${\displaystyle \alpha }$ שהוא בסיס הלוגריתם הדיסקרטי (מודולו ${\displaystyle q}$) כך שמתקיים ${\displaystyle \alpha ^{q}\equiv 1{\text{ (mod }}p)}$. אורך החתימה קצר בהרבה מחתימת RSA או DSA (במאמר המקורי זה היה בערך 212 סיביות, אך מן הסתם לאור ההתקדמות הטכנולוגית נדרשים מספרים יותר גדולים). ביטחון החתימה מסתמך על החד-כיווניות של ההעלאה בחזקה ${\displaystyle y=\alpha ^{x}{\text{ (mod }}p)}$. בהנחה שלוגריתם בדיד בסדר גודל כזה קשה מאוד לחישוב. החתימה על המסר נוצרת באופן כזה שכדי לזייפה יש צורך לחשב את הלוגריתם הבדיד.

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

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

תחילה לצורך אתחול, מכינים את הראשוניים ${\displaystyle p}$ ו-${\displaystyle q}$ כך שמתקיים ${\displaystyle p|(q-1)}$, כאשר ${\displaystyle p\geq 2^{512}}$ וכן ${\displaystyle q\geq 2^{140}}$. במקרה זה ${\displaystyle p}$ נקרא ראשוני חזק. חשוב לזכור שהמספרים הללו נכונים רק לעת כתיבת המאמר המקורי של שנור. יש צורך לעדכן אותם בהתאם. בוחרים יוצר ${\displaystyle \alpha \in \mathbb {Z} _{p}}$ מסדר ${\displaystyle q}$ כך שמתקיים ${\displaystyle \alpha ^{q}\equiv 1{\text{ (mod }}p)}$ בתנאי ש-${\displaystyle \alpha \neq 1}$. כמו כן בוחרים פונקציית גיבוב מתאימה ${\displaystyle h:\mathbb {Z} _{q}\times \mathbb {Z} \rightarrow \{0,...,2^{t}-1\}}$ (פונקציית גיבוב שמפיקה פלט באורך ${\displaystyle t}$ סיביות) כאשר ${\displaystyle t}$ הוא פרמטר ביטחון (נניח ${\displaystyle t=80}$). הפרמטרים הציבוריים המשותפים לכל המשתמשים במערכת יהיו ${\displaystyle (p,q,\alpha ,h)}$. אותם אפשר להכין על ידי צד שלישי נאמן. אותו צד שלישי יצטרך כנראה גם הוא לחתום בחתימה נפרדת על הערכים הללו כדי להבטיח את שלמותם.

כל משתמש צריך להכין מפתח פרטי ומפתח ציבורי כאשר המפתח הפרטי משמש לחתימה והמפתח הציבורי לאימות. הוא מגריל שלם אקראי ${\displaystyle s}$ ומחשב את המפתח הציבורי ${\displaystyle v\equiv \alpha ^{-s}{\text{ (mod }}p)}$ (כלומר ${\displaystyle s=-\log _{\alpha }v}$). את ${\displaystyle s}$ הוא שומר בסוד ואת ${\displaystyle v}$ הוא מפרסם בדרך כלשהי. הפרוטוקול הבא מתאר את תהליך החתימה של אליס על מסמך כלשהו ${\displaystyle m}$ ותהליך האימות של בוב.

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

1. מגרילה שלם אקראי ${\displaystyle r}$ ומחשבת את ${\displaystyle x\equiv \alpha ^{r}{\text{ (mod }}p)}$.
2. מחשבת את ${\displaystyle e=h(x,m)}$ (ערך הגיבוב באורך ${\displaystyle t}$ סיביות של המסר יחד עם המפתח הארעי).
3. מחשבת את ${\displaystyle y=r+se{\text{ (mod }}q)}$.
4. החתימה על המסר ${\displaystyle m}$ היא זוג הערכים ${\displaystyle (e,y)}$.

לצורך אימות החתימה בוב משתמש במפתח האימות הציבורי של אליס ${\displaystyle v}$ כדי לבדוק את הערכים ${\displaystyle (e,y)}$ שקיבל כך:

1. מחשב את ${\displaystyle x'=\alpha ^{y}v^{e}{\text{ (mod }}p)}$
2. בודק שמתקיים ${\displaystyle e=h(x',m)}$ ורק אם השוויון מתקיים הוא מקבל את החתימה.

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

${\displaystyle {\boldsymbol {x\equiv \alpha ^{r}\equiv \alpha ^{r+se}v^{e}\equiv \alpha ^{y}v^{e}{\text{ (mod }}p)}}}$.

לצורך החתימה צריך להעלות בחזקה אחת ולבצע כפל מודולרי אחד וחיבור אחד, חלק מהם ניתנים לחישוב מראש. לצורך האימות נדרשות שתי העלאות בחזקה מודולרית. את שתיהן אפשר לבצע בסיבוכיות של ${\displaystyle 1.5\ell +0.25t}$ פעולות כפל מודולרי כאשר ${\displaystyle \ell =\lceil \log _{2}q\rceil }$ (האורך של ${\displaystyle q}$ בסיביות). הטריק הוא לחשב את ההעלאה בחזקה כדלהלן:

• תחילה מחשבים את ${\displaystyle \alpha v}$ ואז מקבלים את ${\displaystyle x'}$ על ידי הפעולות הבאות.
• מציבים ${\displaystyle i=\ell ,z=1}$
• כל עוד ${\displaystyle i\geq 0}$ מבצעים ${\displaystyle i=i-1,z=z^{2}\alpha ^{y_{i}}v^{e_{i}}{\text{ (mod }}p)}$.

כאשר ${\displaystyle y_{i}}$ ו-${\displaystyle v_{i}}$ הן הסיבית ה-${\displaystyle i}$ החל מימין לשמאל לפי ${\displaystyle \textstyle y=\sum _{i=0}^{\ell -1}y_{i}2^{i}}$ וכן ${\displaystyle \textstyle e=\sum _{i=0}^{\ell -1}e_{i}2^{i}}$.

הערך האקראי ${\displaystyle r}$ נקרא מפתח ארעי. כלומר זהו מספר חד-פעמי שהוגרל לטובת חתימה על מסר אחד. בגלל התכונות של הלוגריתם הבדיד, כמו בהצפנת אל-גמאל, אסור לחתום על יותר ממסמך אחד עם אותו ${\displaystyle r}$ כי אז אפשר לגלות את מפתח החתימה. כי אם נניח שבידי המתקיף שתי חתימות (${\displaystyle e,y}$) וכן (${\displaystyle e',y'}$) אז תמיד מתקיים:

${\displaystyle y'-y=(r'-r)-s(e'-e)}$

לכן אם ${\displaystyle r'=r}$ אבל ${\displaystyle e'\neq e}$ המתקיף יכול לבודד את ${\displaystyle s}$ על ידי חילוק ב-${\displaystyle (e'-e)}$.

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

נניח שהפרמטרים של המערכת הם (${\displaystyle p=467,q=233,\alpha =153}$)

• מפתח החתימה הפרטי של אליס הוא ${\displaystyle s=202}$
• מפתח האימות הציבורי הוא ${\displaystyle v=153^{-202}\equiv 198{\text{ (mod }}467)}$.

כעת לצורך החתימה על המסר ${\displaystyle m}$ היא בוחרת את ${\displaystyle r=94}$ ומחשבת את ${\displaystyle x=153^{94}\equiv 38{\text{ (mod }}467)}$.

נניח שערך הגיבוב על המסר עם המפתח הארעי הוא ${\displaystyle e=h(m,38)=120}$ החתימה על המסר היא אם כן הזוג (${\displaystyle 120,102}$) כי מתקיים:

${\displaystyle 38\equiv 153^{94}\equiv 153^{94+202\cdot 120}\cdot 198^{120}\equiv 153^{102}\cdot 198^{120}{\text{ (mod }}467)}$

אם אליס תשתמש באותו ${\displaystyle r=94}$ כדי לחתום על מסר אחר, נניח שהחתימה השנייה שהתקבלה היא (${\displaystyle 50,175}$) תוצאה זו התקבלה אם כל הערכים למעט המסר זהים. אז מתוך שתי החתימות אפשר לחשב את:

${\displaystyle (y'-y)=(175-102)=73{\text{ (mod }}233)}$, ואת

${\displaystyle (e'-e)=(50-120)\equiv 163{\text{ (mod }}233)}$

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

${\displaystyle (73\cdot 223){\text{ mod }}233=202}$

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

חתימה עיוורת

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

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

ביטחון

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

הביטחון של חתימת שנור ניתן להוכחה במסגרת מודל אורקל אקראי תחת ההשערה שבעיית הלוגריתם הבדיד קשה. ב-2012 בוצע מחקר^[4] באשר לביטחון המדויק של חתימת שנור והטענה היא שלפי למת הפיצול (Forking Lemma) קיים איבוד זמן בפקטור של ${\displaystyle O(q_{h})}$ כאשר ${\displaystyle q_{h}}$ הוא מספר השאילתות לאורקל האקראי. במילים אחרות אם קיים זייפן שיכול לזייף חתימת שנור בהסתברות ${\displaystyle \epsilon _{F}}$ אז אפשר יהיה לחשב את הלוגריתם הבדיד בהסתברות קבועה על ידי חזרה לאחור ${\displaystyle O(q_{h}/\epsilon _{F})}$ פעמים, תחת הנחות נוספות אפשר להגיע לרדוקציה של ${\displaystyle q_{h}^{2/3}}$ לכל היותר בשיעור ההצלחה/זמן.

ראו גם

• חתימה דיגיטלית
• צופן אל-גמאל

הערות שוליים

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.