RSA – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
שורה 67:
== בסיס מתמטי ==
{{הפניה לערך מורחב|בעיית RSA}}
ביטחון שיטת RSA מתבסס על [[בעיית RSA]] כדלקמן; נתון שלם חיובי <math>pq</math>, מכפלת שני ראשוניים שונים שווים בגודלם בקירוב, נתון שלם חיובי <math>e</math> הנמוך מ־<math>pq</math> המקיים <math>\ \mbox{gcd}((p-1)(q-1),e)=1</math> (פירושו ש־<math>e</math> [[מספר זר|זר]] ל-ל־<math>(p-1)(q-1)</math>) ונתון שלם <math>c</math> כלשהו. מצא את <math>m</math> המקיים את המשוואה: <math>m^e \equiv c \ (\mbox{mod }pq)</math>. במילים אחרות הבעיה היא מציאת שורש ממעלה <math>e</math> של <math>c</math> (מודולו <math>pq</math>).
 
הרעיון מאחורי אלגוריתם הפענוח של RSA מבוסס על [[משפט אוילר]] הקובע: עבור כל <math>\ a</math> ו־<math>n</math> טבעיים ה[[מספרים זרים|זרים זה לזה]] (שאין להם מחלק משותף מלבד 1) מתקיים:
אוחזר מתוך "https://he.wikipedia.org/wiki/RSA"