חתימה דיגיטלית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 51:
:<math>\Pr[\text{Forge}_{\mathcal{A},\Pi}(n)=1]\le\text{negl}(n)</math>.
במילים הכוונה היא שסיכוייו של הזייפן להצליח בזיוף החתימה נמוכים מערך זניח שניתן להתעלם ממנו.
==אלגוריתם חתימה דיגיטלית מבוסס RSA==
{{ערך מורחב|RSA}}
הצפנת RSA הייתה מערכת ההצפנה האסימטרית הראשונה שיישמה גם חתימה דיגיטלית מעשית. RSA מבוסס על העובדה שמצד אחד קל לחשב [[העלאה בחזקה]] ומצד שני קשה [[פירוק לגורמים של מספר שלם|לפרק לגורמים מספר שלם]]. החותם בוחר שני [[מספר ראשוני|מספרים ראשוניים]] גדולים <math>p</math> ו-<math>q</math> ומחשב את <math>n=pq</math>. כמו כן בוחר מספר שלם <math>d</math> ומספר שלם <math>e</math> כך שמתקיים <math>ed\equiv 1\text{ (mod }\phi(n))</math>. כאשר <math>\phi(n)</math> הוא [[פונקציית אוילר]] של <math>n</math> שהיא במקרה זה <math>(p-1)(q-1)</math>. את <math>e</math> ואת <math>n</math> הוא מפרסם לכל דורש ואילו את <math>d</math> הוא שומר בסוד. כדי לחתום על המסר <math>m</math> הוא מחשב את <math>s=m^d\text{ (mod }n)</math> ושולח את <math>(m,s)</math>. כדי לאמת את החתימה המקבל מחשב את <math>m'=s^e\text{ (mod }n)</math> ורק אם מתקיים <math>m=m'</math> הוא מקבל את החתימה. זה נכון בגלל הזהות הבאה:
<center>
:<math>s^d=(m^e)^d=m^{ed}=m^{1+\phi(n)k}\equiv m\text{ (mod }n)</math>
</center>
כי לפי אויילר <math>m^{\phi(n)}\equiv 1\text{ (mod }n)</math> עבור כל <math>m</math> ולכן גם <math>m^{1+\phi(n)}\equiv m\text{ (mod }n)</math>. היות שאף אחד חוץ מהחותם אינו יודע מהם <math>d</math> או <math>\phi(n)</math> כיוון שהם מעולם לא פורסמו ולא ניתן לחשב אותם מתוך <math>e</math> ו-<math>n</math> מבלי לדעת מהם הגורמים הראשוניים, המקבל יכול להשתכנע שההחתימה אותנטית.
==מניעת התכחשות (Non-repudiation) וחותם-זמן (Timestamping)==
| |||