בעיית RSA – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ יירפד->ייפרד - תיקון תקלדה בקליק |
עמק שושנים (שיחה | תרומות) מ הגהה |
||
שורה 1:
ב[[קריפטוגרפיה]], '''בעיית RSA''' היא הבסיס התאורטי להצפנת [[RSA]], שהומצאה על ידי [[עדי שמיר|שמיר]], [[רונלד ריבסט|ריבסט]] ו[[לאונרד אדלמן|אדלמן]] ב-1977, ונמצאת מאז בשימוש מאסיבי בכמעט כל מערכת הצפנה מודרנית. בעיית RSA היא בעיה ב[[תורת המספרים]] שאפשר לנסחה בקיצור: "מציאת שורש ממעלה <math>e</math> של <math>c</math> מודולו <math>n</math>".
==מודולוס RSA==
שורה 15:
:'''בהינתן שלם חיובי <math>\ n=pq</math>, כאשר <math>p</math> ו-<math>q</math> ראשוניים שווים בגודלם בקירוב ושלם אי-זוגי חיובי <math>e</math> הנמוך מ-<math>n</math> שמקיים <math>\mbox{gcd}((p-1)(q-1),e)=1</math> ונתון שלם <math>C</math>. מצא שלם <math>M</math> המקיים: <math>M^e \equiv C \ (\mbox{mod }n)</math>'''.
המגבלות שהוטלו על הפרמטרים מבטיחים שלכל <math>C</math> קיים אך ורק <math>M</math> יחיד המתאים לו, כלומר <math>\ f(x)=x^e \ \mbox{mod }n</math> היא [[תמורה (מתמטיקה)|תמורה]] ב-<math>\mathbb{Z}_n</math>. הפונקציה gcd היא [[מחלק משותף מקסימלי]]. היריב, שהמפתח הפרטי אינו ידוע לו, חייב להפוך את פונקציית RSA
==השערת RSA==
שורה 24:
אקראיות <math>M</math> חשובה כיוון שאם ידוע ש-<math>M</math> נבחר מתוך טווח קצר, היריב יכול לנסות לפענח את <math>C</math> פשוט על ידי ניסוי כל האפשרויות (מבלי צורך להפוך את פונקציית RSA כלל).
גם אם <math>M</math> נבחר באקראי היריב יכול למפות את כל האלמנטים ב-<math>\mathbb{Z}_n^*</math> עד שהוא נתקל ב-<math>M</math> הנכון. אולם התקפת כוח גס מסוג זה היא מעריכית, עם זמן ריצה בסדר גודל של <math>\text{log}_2\ n</math>. בטכנולוגיה הנוכחית ועם מספרים גדולים (כמה אלפי ספרות) אלגוריתם כזה אינו יעיל.
==הקשר לפירוק לגורמים==
קל לראות שבעיית RSA אינה קשה יותר מפירוק לגורמים. כלומר, אם קיים אלגוריתם יעיל לפירוק לגורמים אזי RSA אינו בטוח כלל. היות שאם היריב יכול לפרק את המודולוס לגורמים קל לו לחשב את סדר החבורה <math>\phi</math>, למצוא את המפתח הפרטי <math>(n,d)</math> מתוך המפתח הציבורי <math>(n,e)</math> כך שמתקיים <math>d\equiv e^{-1}\text{ mod }\phi(n)</math> ואז לפענח את <math>C</math>.
שבירת RSA על ידי פירוק לגורמים נקראת שיטת [[כוח גס]], דהיינו ניסוי כל המספרים האפשריים עד שיימצא גורם. אם המספר גדול מספיק גם המהיר [[מחשב|במחשבים]] יזדקק למאות שנים לצורך כך. חרף המאמצים טרם נמצאה שיטה [[סיבוכיות זמן|יעילה]] לפירוק לגורמים המהירה במידה משמעותית מכוח גס. אין הוכחה שלא
אף על פי שקיימים אלגוריתמים טובים לפירוק לגורמים של מספרים שלמים, הם עדיין רחוקים מלהוות איום ממשי על מודולוס RSA שנבחר לפי התקן. האלגוריתם היעיל ביותר, "סטייט אוף דה ארט" הידוע כיום לפירוק לגורמים הוא [[נפת שדה מספרים]] הכללי עם זמן ריצה מסדר גודל של <math>\exp((c+o(1))n^{1/3}\text{log}^{2/3}n)</math> עבור קבוע <math>c<2</math>. שזהו בערך [[חסם (מתמטיקה)|החסם]] התחתון הידוע לשבירת RSA באמצעות פירוק לגורמים.
| |||