בעיית RSA – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ מהקורי->המקורי - תיקון תקלדה בקליק |
מ יירפד->ייפרד - תיקון תקלדה בקליק |
||
שורה 97:
כלומר אפשר לחשב כל השורשים של <math>f</math> מודולו <math>n</math> הנמוכים מ-<math>X=n^{1/d}</math>. ככל ש-<math>X</math> קטן זמן הריצה קטן בהתאם. הרעיון של קופרשמידט מבוסס על [[LLL]] (אלגוריתם לצמצום [[סריג (גאומטריה)|סריגים]]) וזמן הריצה שלו נשלט בידי הזמן שלוקח ל-LLL לרוץ על סריג בעל מימד <math>O(w)</math> כאשר <math>w=\text{min}(1/\epsilon,\text{log}_2\ n)</math>. הוא טוב במקרה שמנסים למצוא שורשים קטנים מודולו מספר פריק ויש לו השלכות גם בתחומים אחרים (במקרה של מספר ראשוני אין צורך בכך כי קיימות שיטות יותר טובות). על כל פנים ההשלכה של משפט זה שניתן לפתח התקפה{{הערה|J. Hastad. Solving simultaneous modular equations of low degree. SIAM J. of Computing,}} על RSA כאשר המעריך הציבורי <math>e</math> קטן, כדלהלן.
אם השולח מצפין מסר <math>m</math> מספר פעמים עבור <math>i</math> משתמשים, כל אחד עם המפתחות המתאימים <math>(n_i,e_i)</math> שלהם, אם כל <math>e_i</math> שווים ל-<math>e</math> שלם קטן (נניח <math>e=3</math>), הרי שיריב שמסוגל ליירט את המסרים המוצפנים יכול לחלץ את המסר המקורי על ידי משפט השאריות הסיני ברגע שיצליח להניח ידו על לפחות <math>e</math> מהם. משום שעבור המסרים <math>C_1,C_2,C_3,...</math> קיים שלם <math>C'\in \mathbb{Z}_{n_1\cdot n_2\cdot n_3\cdots}</math> כך ש-<math>C'\equiv M^e\text{ mod }n_1n_2n_3\cdots</math>. לפי משפט קופרשימדט <math>M</math> יהיה השורש ממעלה <math>e</math> (מעל השלמים) של <math>C'</math>. גם אם השולח
התקפה אחרת{{הערה|D. Coppersmith, M. Franklin, J. Patarin, and M. Reiter. Low-exponent RSA with related messages. In EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 1-9. Springer-Verlag, 1996.}} של פרנקלין וריטר על RSA עם מעריך <math>e</math> קטן, מנצלת קשר או יחס בין מסרים. כלומר אם לדוגמה השולח מצפין שני מסרים <math>m_1,m_2</math> כאשר <math>m_2</math> הוא פונקציה ידועה כלשהי מהצורה <math>f=ax+b</math> של <math>m_1</math>. וכן <math>c_1=m_1^e\text{ mod }n</math>. ידוע ש-<math>m_1</math> הוא שורש של הפולינום <math>g_1(x)=f(x)^e-c_1</math> וכן <math>m_2</math> הוא שורש של <math>g_2(x)=x^e-c_2</math>. הגורם הליניארי <math>x-m_2</math> מחלק של שני הפולינומים. לאור זאת אפשר להשתמש ב[[אלגוריתם אוקלידס]] כדי לחשב את <math>m_2=\text{gcd}(g_1,g_2)</math>. ההשלכה של התקפה זו הפכת חמורה יותר אם סכימת הריפוד אינה בטוחה. אם השולח מרפד את המסר <math>m</math> לפני המשלוח על ידי הוספת מספר אקראי קצר <math>r</math> לסוף המסר הרי שאם יעלה בידי התוקף להשיג מסר <math>M</math> כלשהו שנשלח פעמיים (עם ריפוד שונה, דהיינו <math>m_1=2^zM+r_1</math> וכן <math>m_2=2^zM+r_2</math> כאשר <math>z</math> הוא אורך הריפוד בסיביות), הוא יכול לבצע את ההתקפה האמורה ולחלץ את <math>M</math>. כיוון שאם מגדירים את הפולינומים <math>g_1(x,y)=x^e-c_1</math> וכן <math>g_2(x,y)=(x+y)^e-c_2</math>, ידוע שאם <math>y=r_1-r_2</math> הרי ש-<math>m_1</math> יהיה שורש משותף של שניהם שאותו אפשר למצוא בעזרת אלגוריתם קופרשמידט אם הוא קטן.
| |||