הבדלים בין גרסאות בדף "בעיית RSA"

נוספו 16 בתים ,  לפני 7 חודשים
מ
הגהה
מ (יירפד->ייפרד - תיקון תקלדה בקליק)
מ (הגהה)
ב[[קריפטוגרפיה]], '''בעיית RSA''' היא הבסיס התאורטי להצפנת [[RSA]], שהומצאה על ידי [[עדי שמיר|שמיר]], [[רונלד ריבסט|ריבסט]] ו[[לאונרד אדלמן|אדלמן]] ב-1977, ונמצאת מאז בשימוש מאסיבי בכמעט כל מערכת הצפנה מודרנית. בעיית RSA היא בעיה ב[[תורת המספרים]] שאפשר לנסחה בקיצור: "מציאת שורש ממעלה <math>e</math> של <math>c</math> מודולו <math>n</math>".
 
==מודולוס RSA==
:'''בהינתן שלם חיובי <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,. חיפוש סדרתי של הפונקציה ההופכית <math>f^{-1}(C)\ \mbox{mod }n</math> מחייב בממוצע בדיקת כמעט כל המעריכים האפשריים. אם המעריך גדול המשימה תהיה בלתי מעשית.
 
==השערת RSA==
אקראיות <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 ללא קשר לפירוק לגורמים,. השיטה מתבססת רק על העובדה שלא נמצאה עד כה דרך כזו. גורלו של [[המשפט האחרון של פרמה]], שלאחר 350 שנה ללא פתרון נמצאה לו הוכחה, כגורלן של בעיות קשות אחרות שפוצחו בסופו של דבר, עלולים להעלות פקפוק קל ביחס לביטחון צופן זה.
 
אף על פי שקיימים אלגוריתמים טובים לפירוק לגורמים של מספרים שלמים, הם עדיין רחוקים מלהוות איום ממשי על מודולוס RSA שנבחר לפי התקן. האלגוריתם היעיל ביותר, "סטייט אוף דה ארט" הידוע כיום לפירוק לגורמים הוא [[נפת שדה מספרים]] הכללי עם זמן ריצה מסדר גודל של <math>\exp((c+o(1))n^{1/3}\text{log}^{2/3}n)</math> עבור קבוע <math>c<2</math>. שזהו בערך [[חסם (מתמטיקה)|החסם]] התחתון הידוע לשבירת RSA באמצעות פירוק לגורמים.