בעיית RSA

בקריפטוגרפיה, בעיית RSA היא הבסיס התאורטי להצפנת RSA, שהומצאה על ידי שמיר, ריבסט ואדלמן ב-1977, ונמצאת מאז בשימוש מאסיבי בכמעט כל מערכת הצפנה מודרנית. בעיית RSA היא בעיה בתורת המספרים שאפשר לנסחה בקיצור: "מציאת שורש ממעלה $e$ של $c$ מודולו $n$".

מודולוס RSA

ערך מורחב – RSA

בהצפנת RSA אליס מצפינה את המסר הגלוי $M$ עבור בוב באמצעות המפתח הציבורי של בוב $(n,e)$ על ידי חישוב:

$C\equiv M^{e}{\text{ mod }}n$

$n$ נקרא מודולוס RSA והוא בדרך כלל כפולה של שני ראשוניים $p$ ו-$q$ אקראיים, גדולים ושווים בגודלם בקירוב. $e$ נקרא מעריך ציבורי והוא שלם אי-זוגי $e\geq 3$, שצריך להיות זר ביחס ל-$\phi (n)$ שהוא פונקציית אוילר המייצגת את הסדר של החבורה הכפלית $\mathbb {Z} _{n}^{*}$. היות שהסדר של $p$ הוא $p-1$ וכן לגבי $q$ הרי ש-$\phi (n)=(p-1)(q-1)$. פונקציית RSA היא מהצורה $f(x)=x^{e}{\text{ (mod }}n)$. השלם $d$ הוא הופכי כפלי של $e$ ביחס לסדר $\phi$ ונקרא גם דלת המלכודת. המפתח הפרטי הוא אם כן הצמד $(n,d)$.

בוב שברשותו המפתח הפרטי יכול לפענח את $C$ כיוון ש-$de\equiv 1{\text{ (mod }}\phi (n))$ ומזה נובע ש-$C^{d}\equiv M^{ed}\equiv M{\text{ (mod }}n)$.

יריב פוטנציאלי יכול לנסות לגלות מהו $C$ על ידי ציתות לרשת וייתכן אף שהמפתח הציבורי של בוב ידוע לו. ההנחה היא שלמרות האמור יהיה קשה לו לחשוף את $M$ או את $d$.

ניסוח פורמלי של הבעיה

בהינתן שלם חיובי $\ n=pq$, כאשר $p$ ו-$q$ ראשוניים שווים בגודלם בקירוב ושלם אי-זוגי חיובי $e$ הנמוך מ-$n$ שמקיים ${\mbox{gcd}}((p-1)(q-1),e)=1$ ונתון שלם $C$. מצא שלם $M$ המקיים: $M^{e}\equiv C\ ({\mbox{mod }}n)$.

המגבלות שהוטלו על הפרמטרים מבטיחים שלכל $C$ קיים אך ורק $M$ יחיד המתאים לו, כלומר $\ f(x)=x^{e}\ {\mbox{mod }}n$ היא תמורה ב-$\mathbb {Z} _{n}$. הפונקציה gcd היא מחלק משותף מקסימלי. היריב, שהמפתח הפרטי אינו ידוע לו, חייב להפוך את פונקציית RSA. חיפוש סדרתי של הפונקציה ההופכית $f^{-1}(C)\ {\mbox{mod }}n$ מחייב בממוצע בדיקת כמעט כל המעריכים האפשריים. אם המעריך גדול המשימה תהיה בלתי מעשית.

השערת RSA

השערת RSA מניחה שבעיית RSA המתוארת קשה לפתרון במידה והתנאים הבאים מתקיימים: הגורמים הראשוניים של המודולוס אינם ידועים לתוקף, המודולוס גדול מאוד, המודולוס נוצר באקראי (הגורמים נבחרו באקראי) וכן המסר $M$ (ומזה נובע גם הצופן $C$) ממופה לאלמנט אקראי ב-$\mathbb {Z} _{n}^{*}$, דהיינו בטווח $[0,n-1]$.

השערה זו זהה לטענה שפונקציית RSA היא חד-כיוונית עם דלת מלכודת כשהמפתח הפרטי הוא דלת המלכודת. דהיינו בעוד שקל לחשב חזקה ממעלה $e$ של $x$ (מודולו $n$), הרי שקשה לבצע את הפעולה ההפוכה, לחשב את השורש ממעלה $e$ של $C$ מודולו $n$. אלא אם כן יינתן רמז סודי שהוא במקרה זה $\phi (n)$.

אקראיות $M$ חשובה כיוון שאם ידוע ש-$M$ נבחר מתוך טווח קצר, היריב יכול לנסות לפענח את $C$ פשוט על ידי ניסוי כל האפשרויות (מבלי צורך להפוך את פונקציית RSA כלל).

גם אם $M$ נבחר באקראי היריב יכול למפות את כל האלמנטים ב-$\mathbb {Z} _{n}^{*}$ עד שהוא נתקל ב-$M$ הנכון. אולם התקפת כוח גס מסוג זה היא מעריכית, עם זמן ריצה בסדר גודל של ${\text{log}}_{2}\ n$. בטכנולוגיה הנוכחית ועם מספרים גדולים (כמה אלפי ספרות) אלגוריתם כזה אינו יעיל.

הקשר לפירוק לגורמים

קל לראות שבעיית RSA אינה קשה יותר מפירוק לגורמים. כלומר, אם קיים אלגוריתם יעיל לפירוק לגורמים אזי RSA אינו בטוח כלל. היות שאם היריב יכול לפרק את המודולוס לגורמים קל לו לחשב את סדר החבורה $\phi$, למצוא את המפתח הפרטי $(n,d)$ מתוך המפתח הציבורי $(n,e)$ כך שמתקיים $d\equiv e^{-1}{\text{ mod }}\phi (n)$ ואז לפענח את $C$.

שבירת RSA על ידי פירוק לגורמים נקראת שיטת כוח גס, דהיינו ניסוי כל המספרים האפשריים עד שיימצא גורם. אם המספר גדול מספיק גם המהיר במחשבים יזדקק למאות שנים לצורך כך. חרף המאמצים טרם נמצאה שיטה יעילה לפירוק לגורמים המהירה במידה משמעותית מכוח גס. אין הוכחה שלא תימצא כזו, ואף לא מובטח שלא ניתן לשבור את RSA ללא קשר לפירוק לגורמים. השיטה מתבססת רק על העובדה שלא נמצאה עד כה דרך כזו. גורלו של המשפט האחרון של פרמה, שלאחר 350 שנה ללא פתרון נמצאה לו הוכחה, כגורלן של בעיות קשות אחרות שפוצחו בסופו של דבר, עלולים להעלות פקפוק קל ביחס לביטחון צופן זה.

אף על פי שקיימים אלגוריתמים טובים לפירוק לגורמים של מספרים שלמים, הם עדיין רחוקים מלהוות איום ממשי על מודולוס RSA שנבחר לפי התקן. האלגוריתם היעיל ביותר, "סטייט אוף דה ארט" הידוע כיום לפירוק לגורמים הוא נפת שדה מספרים הכללי עם זמן ריצה מסדר גודל של $\exp((c+o(1))n^{1/3}{\text{log}}^{2/3}n)$ עבור קבוע $c<2$. שזהו בערך החסם התחתון הידוע לשבירת RSA באמצעות פירוק לגורמים.

מודולוס RSA שלא נבחר באקראי עלול להכיל חולשות שמאפשרות שבירתו בקלות. לדוגמה אם $n=pq$ נבחר כך ש-$p-1$ הוא כפולה של ראשוניים קטנים שאינם עולים על חסם כלשהו $B$ אזי ניתן לפרקו לגורמים בזמן של $B^{3}$ בערך.

על כל פנים ההפך אינו מוכח. דהיינו השאלה אם יימצא אלגוריתם יעיל לשבירת RSA, האם אפשר לבנות באמצעותו אלגוריתם יעיל לפירוק לגורמים, היא שאלה פתוחה. או בניסוח אחר:

בהינתן מודלוס $n$ ומעריך $e$ שלם אי זגי, המקיימים ${\text{gcd}}(e,\phi (n))=1$ והתמורה $f_{e,n}(x)=x^{1/e}{\text{ mod }}n$ מהחבורה $\mathbb {Z} _{n}^{*}$ על עצמה, האם קיים אלגוריתם שיכול חשב בזמן פולינומי את הגורמים הראשוניים של $n$ בהינתן גישה לאורקל $f_{e,n}(x)$, כאשר האורקל יכול לחשב את $f(x)$ בזמן קבוע.

בונה ו-Venkatesan ואחרים הוכיחו שאם $e$ קטן כגון $e\leq 17$, התשובה לשאלה האמורה היא "לא". במילים אחרות ייתכן שלא קיימת רדוקציה מבעיית RSA לפירוק לגורמים במקרה הפרטי של $e$ קטן. אך אין בזה די כדי להוכיח באופן כללי שבעיית RSA קלה מפירוק לגורמים.

לאחר המצאת RSA חודשו המאמצים למציאת אלגוריתמים יעילים לפירוק לגורמים. ב-1981 פיתח קארל פומרנץ את אלגוריתם הנפה הריבועית אשר נחשב עד ל-1993 לאלגוריתם היעיל ביותר (באופן אסימפטוטי) לפירוק לגורמים. ב-1993 הומצאה נפת שדה מספרים הידועה כיום כאלגוריתם הטוב ביותר בכל הזמנים לפירוק לגורמים של מספרים גדולים מאוד (בשל מורכבותה נפת שדה המספרים יעילה בעיקר מעל מאה ספרות עשרוניות).

בנובמבר 2005 הצליח צוות מתמטיקאים לפרק לגורמים בעזרת אלגוריתם נפת שדה המספרים את המודולוס RSA-200 (200 ספרות עשרוניות) מתוך מספרי האתגר של מעבדות RSA. המאמץ נמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל. בדצמבר 2009 פרסם צוות מחקר ממוסדות אקדמאיים שונים, בראשות תורסטן קליינג'ונג כי הצליחו לפרק לגורמים את המספר RSA-768 (ממספרי האתגר של מעבדות RSA) בתהליך שנמשך כמעט שלוש שנים ונרתמו לצורכו אלפי מעבדים (אותו תהליך על מחשב בודד בעל עוצמת חישוב טובה, היה אורך כ-1500 שנה). האתגר הבא RSA-1024 (כ-300 ספרות עשרוניות) קשה פי כמה אלפים. בעבר הוצע פרס של כ-100,000 דולר למי שיצליח לפרקו.

עדי שמיר וערן טרומר פיתחו חומרה היפותטית (TWINKLE ו-TWIRL) להאצת תהליך הניפוי של אלגוריתם NFS. באמצעותה פירוק לגורמים של מודולוס RSA בגודל 1024 סיביות בר ביצוע בזמן סביר. במאמרם נטען שניתן לבנות מערכת ייעודית מעשית לשבירת RSA בסדר גודל של 1024 סיביות בתוך כשנה ובעלות של כעשרה מיליון דולר. לא ידוע על מימוש מעשי של החומרה שהציעו.

בעקבות פרשת סנאודון, ישנם מומחי אבטחה המעריכים כי נכון לשנת 2013 ארגונים בינלאומיים בעלי אמצעים כמו NSA מסוגלים לפצח מפתח כזה בעלות של כמיליארד דולר בזמן קצר בהרבה (כמספר שעות).

לפי חוק מור כל שנתיים בערך היכולת הטכנולוגית מכפילה עצמה. אולם קצב המיזעור הולך ודועך. בשנת 2007 צוטט מור כי בתוך עשר שנים לא יתאפשר מיזעור נוסף בהתאם לחוק שהגה. בהערכה זהירה מודולוס בגודל 2048 סיביות (או 4096 סיביות לאלו שחוששים במיוחד), מספק רמת ביטחון ראויה לכל צורך מעשי בזמן הקרוב.

תכונת המעגליות

בשל העובדה שהצפנת RSA הנה תמורה ב-$\ \mathbb {Z} _{n}$, אם $C=M^{e}{\mbox{ mod }}n$ קיים שלם $k$ המקיים $C^{e^{k}}\equiv C\ ({\mbox{mod }}n)$. מאותה סיבה $C^{e^{k-1}}\equiv M\ ({\mbox{mod }}n)$. אם $\ n$ קטן חיפוש סדרתי של $k$ כזה אפשרי. אפשר להתחיל בערך נמוך ולקדם את $k$ עד שהמשוואה האמורה מתקיימת. יתרה מזו, ניתן לייעל את ההתקפה על ידי מציאת השלם $\ u$ העונה על הדרישה ${\mbox{gcd}}(C^{e^{u}}-C,n)>1$. יש סיכוי טוב למצוא את $\ u$ בפחות מהזמן הדרוש למצוא את $\ k$. אם $C^{e^{u}}\equiv C$ מודולו אחד מהגורמים הראשוניים של $\ n$, אזי ${\mbox{gcd}}(C^{e^{u}}-C,n)$ הוא גורם ראשוני של $n$ וכאמור ידיעת הגורמים הראשוניים מספקת לחילוץ מפתח הפענוח. במקרה ש-${\mbox{gcd}}(C^{e^{u}}-C,n)=n$ אזי מתקיים בהכרח $u=k$ וכאמור $C^{e^{u-1}}\equiv M$, במקרה כזה מתקבל $\ m$ בלא צורך במפתח הפענוח כלל. למעשה אפשר לראות בשיטה זו כדרך שונה לפירוק $n$ לגורמים. כאמור, פירוק לגורמים היא בעיה קשה כך שתכונה זו אינה מהווה איום משמעותי על אלגוריתם RSA.

מספרים ראשוניים

כאמור חשוב שהמספרים הראשוניים ייבחרו באקראי. לא מומלץ למשל להשתמש ברשימת מספרים ראשוניים מפורסמת, כיוון שבדרך זו מועבר מידע ליריב פוטנציאלי. בבחירת מספרים ראשוניים רצוי שיהיו לא רק אקראיים אלא גם קשים לניחוש. אילו הגדרות שונות, כיוון שאקראיות לבדה אינה מבטיחה קושי בניחוש. על כן השיטה המקובלת היא הפעלת מחולל אקראי בטוח ליצירת מספר אי-זוגי אקראי באורך הרצוי ובדיקת ראשוניותו, מכיוון שבדיקת ראשוניות קלה יותר מפירוק לגורמים, אם המספר מתגלה כפריק מנסים שוב עם מספר אחר. הסיכויים הם שתוך מספר ניסיונות קצר בערך כמספר הספרות, יימצא ראשוני. כמו כן רצוי ש-$p$ ו-$q$ יהיו בגודל זהה בקירוב, כלומר שלמודולוס $n$ לא יהיו גורמים קטנים כלשהם. זאת כדי לסכל אפשרות שימוש באלגוריתם פירוק שמנצל את קיומם של גורמים קטנים. מצד שני רצוי שההפרש ביניהם לא יהיה קטן מדי. כי אם $p\approx q$, אזי גם $p\approx {\sqrt {n}}$ ואז ניתן למצוא אותם בחיפוש קל, קרוב לשורש.

יש הממליצים להשתמש במספרים ראשוניים חזקים. $\ p$ הוא מספר ראשוני חזק אם הוא מקיים את ההגדרות הבאות:

• $\ p-1$ מכיל גורם ראשוני גדול $\ r$.
• $\ p+1$ מכיל גורם ראשוני גדול כלשהו.
• $\ r$ האמור גם הוא, מכיל גורם ראשוני גדול כלשהו.

ניתן להכין מספרים כאלו בעזרת אלגוריתם גורדון (Gordon) למשל. הסיבות לתנאים אלו הם: הראשון והשני נועדו לסכל שימוש באלגוריתם פירוק לגורמים על המודולוס כמו אלגוריתם rho של פולרד או אלגוריתמים אחרים (של פולרד) המנצלים את $p\pm 1$. השלישי נועד לסכל את מתקפת מחזוריות (ראו להלן).

הוכח מעשית שאין צורך במספרים ראשוניים חזקים, משום שמספרים ראשוניים גדולים מאוד שנבחרו אקראית בדרך בטוחה, כמעט תמיד נוטים לענות על דרישות אלו.

חשיפת המפתח הפרטי לעומת פירוק לגורמים

בהינתן המפתח הפרטי $(n,d)$ אפשר לבנות אלגוריתם יעיל לפירוק לגורמים של $n=pq$.

וכן להפך; בהינתן הגורמים הראשוניים של $n$, אפשר לחלץ את $d$ בקלות.

ההוכחה פשוטה. אם $d$ ידוע אפשר לחשב את $k=de-1$. ידוע ש-$k$ צריך להיות כפולה של הסדר $\phi$. היות ש-$\phi$ זוגי, אם כותבים את $k$ כ-$2^{t}r$ כאשר $r$ אי-זוגי ו-$t\geq 1$, מתקיים $g^{k}\equiv 1$ עבור כל $g\in \mathbb {Z} _{n}^{*}$ ולכן $g^{k/2}$ הוא שורש ריבועי של $1$ מודולו $n$. לפי משפט השאריות הסיני ל-$1$ ארבעה שורשים ריבועיים מודולו $n=pq$. שניים הם $\pm 1$ האחרים הם $\pm x$ כאשר $x$ מקיים $x\equiv 1{\text{ mod }}p$ וכן $x\equiv -1{\text{ mod }}q$. בעזרת אחד משני השורשים האחרונים אפשר לגלות את הגורמים של $n$ על ידי חישוב ${\text{gcd}}(x-1,n)$ (gcd היא מחלק משותף מקסימלי). אפשר לראות שאם $g$ נבחר באקראי, אחד מהאלמנטים ברצף $g^{k/2},g^{k/4},...,g^{k/2^{t}}$ מודולו $n$ הוא שורש ריבועי של $1$ בהסתברות של לפחות חצי. כל האלמנטים ברצף האמור ניתנים לחישוב בזמן של ${\text{log}}_{2}\ n$.

הטענה ההפוכה נובעת ישירות מהעובדה שבהינתן הגורמים הראשוניים אפשר לחשב את $\phi$ ואת $d$. מזה נובע שבעיית פירוק לגורמים שקולה לחשיפת המפתח הפרטי, כך שאין טעם להסתיר את המפתח הפרטי ממי שהגורמים ידועים לו וכן להפך. מסיבה זו לא יהיה חכם לשתף מודולוס אחד לכמה משתמשים (כך שרק המפתחות הפרטיים והציבוריים שלהם שונים). כי בידי כל אחד מהם מספיק מידע כדי לפרק את $n$ לגורמים ואז הוא יכול לחלץ את המפתחות הפרטיים של כל האחרים מתוך המפתחות הציבוריים שלהם.

מעריך d קטן

בפענוח סיבוכיות פעולת ההעלאה בחזקה המודולרית, ליניארית ביחס לאורכו של $d$ בסיביות, מסיבה זו אם המפתח הפרטי קטן משיגים שיפור ביעילות הפענוח בפקטור משמעותי. התקפה מתוחכמת של מייקל ויינר מראה שעם מפתח פענוח קטן אפשר לשבור את המערכת כולה בקלות. הטענה היא:

בהינתן $n=pq$, כאשר $q<p<2q$ וכן השלמים $e,d$ כך שמתקיים $ed\equiv 1{\text{ mod }}\phi (n)$, אם $d<n^{1/4}/3$ אפשר לחלץ את $d$ ביעילות.

ההתקפה של ויינר מבוססת על קירוב שברים משולבים. היות ש-$ed$ שקול ל-$1$ מודולו $\phi$ קיים $k$ המקיים $ed-k\phi =1$. מתקיים יחס הקירוב:

$\left|{\frac {e}{n}}-{\frac {k}{d}}\right|\leq {\frac {1}{dn^{1/4}}}<{\frac {1}{2d^{2}}}$

השברים $k/d$ נותנים קירוב טוב של $e/n$ על ידי התכנסות השבר המשולב. התוקף יכול לחשב את ההתכנסויות עבור $e/n$. אחד מהם יהיה שווה ל-$k/d$ ולאור האמור צריך להיות ${\text{gcd}}(k,d)=1$ ולכן $k/d$ הוא שבר מצומצם. האלגוריתם של ויינר מאפשר חילוץ $d$ בזמן ליניארי. אם $n$ באורך 1024 סיביות $d$ חייב להיות לפחות 256 סיביות כדי לסכל התקפה זו. לחלופין אפשר להגדיל את $e$ על חשבון $d$. ויינר הראה שאם $e>n^{1.5}$ ההתקפה שלו לא תצלח. על כל פנים הגדלת $e$ אינה פותרת את בעיית היעילות אלא מעבירה אותה להצפנה. ייתכן ושיטה זו תהיה יעילה במקרים בהם המחיר שווה את התועלת, אם אין חשיבות לגודל מפתח ההצפנה לעומת מפתח הפענוח.

ייעול ההצפנה והפענוח מבלי להסתכן בהתקפה של ויינר, אפשרי באמצעות משפט השאריות הסיני כפי שמובא בתקן PKCS. אם מחלקים את $d$ לשני מפתחות פענוח כך שמתקיים $d_{p}\equiv d{\text{ mod }}(p-1)$ וכן $d_{q}\equiv d{\text{ mod }}(q-1)$ ואורך כל אחד מהם מחצית מאורך המודולוס. אזי הפענוח מתייעל בפקטור של שניים בקירוב. בפענוח משתמשים במשפט השאריות הסיני כדי לפתור את מערכת השקילויות $M_{p}\equiv c^{d_{p}}{\text{ mod }}p$ וכן $M_{q}\equiv c^{d_{q}}{\text{ mod }}q$ כדי לחשב את $M$. והרעיון הוא שהמפתחות $d_{p}$ ו-$d_{q}$ קטנים לכן העלאה בחזקה עם מפתחות אילו יעילה יותר. לא ברור האם השיטה הזו מחזקת או מחלישה את RSA.

החסם שהציע ויינר אינו מדויק. בונה ואחרים הוכיחו שכל עוד $d<n^{0.292}$ אפשר לשחזר את $d$ מתוך $(n,e)$. בכל אופן החסם המדויק הוא שאלה פתוחה.

מעריך e קטן

משיקולי יעילות מקובל שהמעריך הציבורי יהיה קטן, זאת מבלי לפגוע בביטחון המערכת. הדבר חשוב במיוחד כאשר מיישמים את RSA בחומרה כמו כרטיס חכם. $e=2^{16}+1$ נפוץ ביישומים מעשיים, יתרונו במשקלו הבינארי הנמוך. יש לשים לב שאם המסר עצמו קטן גם הוא, ייתכן שיהיה אפשר פשוט לחשב את השורש ממעלה $e$ של המסר ללא המודולוס (אם $M<{\sqrt[{e}]{n}}$). משפט קופרשמידט אומר:

בהינתן מודולוס $n$ ופולינום $f\in \mathbb {Z} [x]$ ממעלה $d$. יהי $X=n^{1/d-\epsilon }$ עבור $\epsilon \geq 0$, קיים אלגוריתם לחישוב כל השלמים $|x_{0}|<X$ המקיימים $f(x_{0})=0{\text{ mod }}n$.

כלומר אפשר לחשב כל השורשים של $f$ מודולו $n$ הנמוכים מ-$X=n^{1/d}$. ככל ש-$X$ קטן זמן הריצה קטן בהתאם. הרעיון של קופרשמידט מבוסס על LLL (אלגוריתם לצמצום סריגים) וזמן הריצה שלו נשלט בידי הזמן שלוקח ל-LLL לרוץ על סריג בעל מימד $O(w)$ כאשר $w={\text{min}}(1/\epsilon ,{\text{log}}_{2}\ n)$. הוא טוב במקרה שמנסים למצוא שורשים קטנים מודולו מספר פריק ויש לו השלכות גם בתחומים אחרים (במקרה של מספר ראשוני אין צורך בכך כי קיימות שיטות יותר טובות). על כל פנים ההשלכה של משפט זה שניתן לפתח התקפה על RSA כאשר המעריך הציבורי $e$ קטן, כדלהלן.

אם השולח מצפין מסר $m$ מספר פעמים עבור $i$ משתמשים, כל אחד עם המפתחות המתאימים $(n_{i},e_{i})$ שלהם, אם כל $e_{i}$ שווים ל-$e$ שלם קטן (נניח $e=3$), הרי שיריב שמסוגל ליירט את המסרים המוצפנים יכול לחלץ את המסר המקורי על ידי משפט השאריות הסיני ברגע שיצליח להניח ידו על לפחות $e$ מהם. משום שעבור המסרים $C_{1},C_{2},C_{3},...$ קיים שלם $C'\in \mathbb {Z} _{n_{1}\cdot n_{2}\cdot n_{3}\cdots }$ כך ש-$C'\equiv M^{e}{\text{ mod }}n_{1}n_{2}n_{3}\cdots$. לפי משפט קופרשימדט $M$ יהיה השורש ממעלה $e$ (מעל השלמים) של $C'$. גם אם השולח ייפרד את $M$ על ידי סכימת ריפוד ידועה כלשהי (אם הריפוד הוא ערך קבוע עבור כל משתמש) ההתקפה עדיין ישימה. לכן הריפוד חייב להיות אקראי כדי לסכל את ההתקפה האמורה.

התקפה אחרת של פרנקלין וריטר על RSA עם מעריך $e$ קטן, מנצלת קשר או יחס בין מסרים. כלומר אם לדוגמה השולח מצפין שני מסרים $m_{1},m_{2}$ כאשר $m_{2}$ הוא פונקציה ידועה כלשהי מהצורה $f=ax+b$ של $m_{1}$. וכן $c_{1}=m_{1}^{e}{\text{ mod }}n$. ידוע ש-$m_{1}$ הוא שורש של הפולינום $g_{1}(x)=f(x)^{e}-c_{1}$ וכן $m_{2}$ הוא שורש של $g_{2}(x)=x^{e}-c_{2}$. הגורם הליניארי $x-m_{2}$ מחלק של שני הפולינומים. לאור זאת אפשר להשתמש באלגוריתם אוקלידס כדי לחשב את $m_{2}={\text{gcd}}(g_{1},g_{2})$. ההשלכה של התקפה זו הפכת חמורה יותר אם סכימת הריפוד אינה בטוחה. אם השולח מרפד את המסר $m$ לפני המשלוח על ידי הוספת מספר אקראי קצר $r$ לסוף המסר הרי שאם יעלה בידי התוקף להשיג מסר $M$ כלשהו שנשלח פעמיים (עם ריפוד שונה, דהיינו $m_{1}=2^{z}M+r_{1}$ וכן $m_{2}=2^{z}M+r_{2}$ כאשר $z$ הוא אורך הריפוד בסיביות), הוא יכול לבצע את ההתקפה האמורה ולחלץ את $M$. כיוון שאם מגדירים את הפולינומים $g_{1}(x,y)=x^{e}-c_{1}$ וכן $g_{2}(x,y)=(x+y)^{e}-c_{2}$, ידוע שאם $y=r_{1}-r_{2}$ הרי ש-$m_{1}$ יהיה שורש משותף של שניהם שאותו אפשר למצוא בעזרת אלגוריתם קופרשמידט אם הוא קטן.

ראוי לציין שאם המעריך גדול ההתקפות האמורות אינן יעילות. דרך אחרת לסכל התקפות אילו היא לרפד את המסר בסכימת ריפוד אקראית בטוחה. למרות זאת בגלל ההתקפות המתוארות התקנים הידועים נמנעים באופן כללי משימוש במפתחות הצפנה או פענוח קטנים.

חשיפה חלקית של d כאשר e קטן

בונה ואחרים הוכיחו שאם עלה בידי התוקף לגלות חלק (למשל רבע) מסיביות המפתח הסודי $d$ הרי שהוא יכול באמצעותם לגלות את המפתח הסודי כולו בתנאי שמפתח ההצפנה מקיים $e<{\sqrt {n}}$. עובדה זו נובעת ממשפט קופרשמידט שהוכיח שאם יעלה בידי התוקף לנחש נכונה כרבע מסיביות אחד הגורמים הראשוניים של המודולוס, ביכולתו לפרק את המודולוס כולו לגורמים בזמן של $e{\text{ log}}_{2}\ e$ ניסיונות.

בנוסף אפשר לראות שאם המעריך $e$ קטן מערכת RSA מדליפה כמחצית מהסיביות המשמעותיות של המפתח הפרטי $d$. הסיבה היא בשל המשוואה $ed-k(n-p-q+1)=1$ עבור $0<k\leq e$. בהינתן $k$ כאמור התוקף יכול לחשב את ${\hat {d}}=\lfloor (kn+1)/e\rfloor$ ואז את

$|{\hat {d}}-d|\leq k(p+q)/e\leq 3k{\sqrt {n}}/e<3{\sqrt {n}}$

לכן ${\hat {d}}$ הוא קירוב טוב של $d$. דהיינו ברוב המקרים מחצית הסיביות המשמעותיות של ${\hat {d}}$ זהות לסיביות של $d$. היות שקיימים רק $e$ ערכים אפשריים של $k$ אפשר לבנות טבלה קטנה של $e$ כניסות כך שאחד מהאלמנטים בה שווה למחצית השמשעותית של סיביות $d$.

כפליות (Multiplicative)

אם $m_{1},m_{2}$ הם מסרים כלשהם שהטקסטים המוצפנים המקבילים להם הם $c_{1},c_{2}$ בהתאמה. אזי מתקיימת הזהות הבאה:

$(m_{1}\cdot m_{2})^{e}\equiv m_{1}^{e}\cdot m_{2}^{e}\equiv c_{1}\cdot c_{2}({\mbox{mod }}n)$

תכונה זו נקראת גם הומומורפיזם והיא מאפשרת במצב מסוים התקפה שבה לתוקף גישה חלקית למערכת ההצפנה (אין לו גישה למפתח ההצפנה) אם $c=M^{e}{\mbox{ mod }}n$ וברצונו לחשוף את $C$ ביכולתו להסתירו על ידי הכפלת הטקסט המוצפן ב-$x^{e}$ כלשהו כך: $s=Cx^{e}{\mbox{ mod }}n$, אם המערכת תפענח עבורו את $s$ בלא ידיעת הקשר שבינו לבין $C$ הוא יקבל את: $t=s^{d}{\mbox{ mod }}n$. תוצאה זו מאפשרת חילוץ $C$ בשל הזהות הבאה:

$t\equiv s^{d}\equiv C^{d}(x^{e})^{d}\equiv Mx\ ({\mbox{mod }}n)$

ולכן $M=tx^{-1}{\mbox{ mod }}n$. כלומר מסירים את $x$ על ידי הכפלה בהופכי שלו כדי לקבל את הטקסט מקורי. תכונה זו שימושית גם לטכניקת הסינוור להלן כנגד התקפת ערוץ צדדי. הדרך הטובה ביותר למנוע חולשות עקב תכונת הכיפליות היא לרפד את המסר באמצעות סכימת ריפוד בטוחה.

פריקות עצמית

לאור תכונת הכפליות, לפונקציית RSA תכונת "פריקות עצמית" (Self-reducibility) או רדוקציה עצמית, כלומר תמיד מתקיים:

$(MR)^{e}\equiv M^{e}R^{e}{\text{ (mod }}n)$.

כך שאפשר למעשה להמיר טקסט מוצפן נתון $M^{e}$ לטקסט מוצפן אחר $(MR)^{e}$ כאשר$R$ אקראי. כעת היות שיש סיכוי שהתוצאה תהיה "חלשה" במובן שייתכן שתהיה דרך קלה לפענחה, הרי שהתוקף יכול לנצל עובדה זו כדי לפענח כל טקסט מוצפן. הוכח שאם קיים אלגוריתם ${\text{A}}$ שיכול לפענח חלקיק קטן $\epsilon$ מסך כל ההצפנות האפשריות, הרי שקיים אלגוריתם אקראי אחר ${\text{A}}'$ שיכול לפענח את כל המסרים המוצפנים באותה סיבוכיות זמן בערך.

מצד אחד תכונת הפריקות העצמית מלמדת שאפשר לצפות מכך שהרוב המכריע של הטקסטים המוצפנים יהיה קשה לפענוח באופן כמעט שווה, תכונה שהועילה בהוכחת ביטחון מספר מערכות הצפנה אסימטרית המבוססות על RSA. אולם מאידך היא נותנת כלים טובים בידי התוקף, היא מאפשרת לגלות טקסט מוצפן אחד מתוך טקסט מוצפן אחר. זו אחת הסיבות מדוע חשוב שמערכת ההצפנה תהיה עמידה כנגד התקפת מוצפן נבחר.

השערת RSA החזקה

באריץ' ופיצמן ואחרים המציאו ב-1997 את השערת RSA החזקה (Strong RSA Assumption) שמאז מהווה בסיס למספר מערכות הצפנה וחתימה דיגיטלית בין היתר חתימה דיגיטלית של קריימר ושופ. השערה זו שונה מההשערה הרגילה בכך שהתוקף יכול לבחור גם את המפתח הציבורי, כדלהלן:

בהינתן מודולוס אקראי $n$ ושלם אקראי $C\in \mathbb {Z} _{n}^{*}$, מצא $e>1$ ו-$M\in \mathbb {Z} _{n}^{*}$ המקיימים $C=M^{e}$.

כלומר היריב מקבל מודולוס וטקסט מוצפן ועליו למצוא כל מעריך ובסיס כך שהמשוואה האמורה תתקיים. ייתכן שמשימה זו תהיה קלה יותר מפתרון בעיית RSA הרגילה ולכן ההשערה נקראת חזקה במובן הזה, שאם היא קשה, הרי שהיא משיגה ביטחון גבוה יותר מ-RSA הרגיל.

סיבית קשה ב-RSA

ערך מורחב – סיבית קשה

אף על פי ש-RSA בטוח בהנחה שהשערת RSA נכונה ובהנחה שפירוק לגורמים היא משימה קשה. בכל זאת בתנאים מסוימים RSA מדליף מעט מידע על הטקסט המקורי, כלומר קל לנחש סיביות מסוימות של המסר המקורי מתוך הטקסט המוצפן. גולדווסר ומיקאלי הראו שאם היריב יכול לנחש את הסיבית הכי פחות משמעותית של הטקסט המקורי, הוא יכול עם מידע זה לבצע התקפה שבה יצליח יחלץ את כל סיביות המקור בזמן פולינומי. ואזירני וכן שור, גולדרייך, אלקסי פישלין, שנור ואחרים הוכיחו ש-${\text{log}}({\text{log}}(n))$ הסיביות הפחות משמעותיות של הטקסט המוצפן של הצפנת RSA בטוחות, דהיינו ההסתברות לניחוש מוצלח שלהן הוא לא יותר מאשר $1/2+\epsilon$ כאשר $\epsilon =1/{\text{poly}}({\text{log}}(n))$.

הוסטד ונוסלנד הוכיחו שכל סיביות הטקסט המקורי "מוסתרות היטב" בהצפנת RSA במובן שאם יהיה בידי תוקף יתרון כלשהו לגלות חלק מהן הרי שהוא יצליח לחשוף את כולן באותה מידה. ההוכחות מתבססות על רדוקציה המוכיחה שאם קיים אלגוריתם יעיל לניחוש סיבית אחת או יותר אפשר לבנות ממנו אלגוריתם לניחוש כל הסיביות ומכאן להיפוך פונקציית RSA.

תכונה זו היא חרב פיפיות, מצד אחד מבטיחה כי כל הסיביות מוגנות במידה שווה, אולם מצד שני מעניקה לתוקף כלי רב עוצמה, אם יעלה בידו לנחש סיבית אחת הוא יכול לגלות את כולן. מסיבה זו יישום RSA דורש תשומת לב רבה וזהירות שלא ייוצר מצב שחלק מהמערכת ידליף שלא במודע רסיס כלשהו שיאפשר לתוקף לשבור את המערכת כולה.

התקפת מוצפן נבחר

ערך מורחב – התקפת מוצפן-נבחר

התקפת מוצפן נבחר על RSA מוגדרת כדלהלן: לתוקף גישה לאורקל אשר מבצע עבורו עם מפתח הצפנה זהה, $k$ פענוחים של $k$ טקסטים מוצפנים $c_{1},c_{2},...,c_{k}$ (לא בהכרח קשורים זה בזה) ומתוך מידע זה עליו לגלות $C$ אחר שאינו נמנה כמובן עליהם. ההתקפה מתחלקת לשני סוגים CCA1 ו-CCA2 כאשר השנייה מאפשרת שיהיה קשר בין $C$ שאותו התוקף מעוניין לגלות לבין הפענוחים שקיבל, במילים אחרות הוא יכול לבחור את הפענוחים שברצונו לקבל לפי $C$ בהתאם לתוצאות קודמות כלשהן.

היות שפונקציית RSA דטרמיניסטית באופיה לא ניתן לסכל התקפה זו. הדרך היחידה לסכלה היא לעשות שימוש בסכימת ריפוד אקראית על המסר לפני ההצפנה כמו OAEP. בצורה זו מבטלים את דטרמיניסטיות ההצפנה וההתקפה נעשית חסרת תועלת.

התקפת תיזמון

ערך מורחב – התקפת ערוץ צדדי

RSA הבסיסי פגיע להתקפת ערוץ צדדי המודדת במדויק את הזמן הדרוש לביצוע פענוח. למשל בהינתן כרטיס חכם שבו מוטמע מפתח הצפנה סודי שכמובן לא ניתן לראות באמצעים רגילים. בגלל שהמספרים העצומים לא מאפשרים חישוב ישיר של העלאה בחזקה פעולת הפענוח מנצלת את "אלגוריתם ריבוע וכפל" כדי לחשב את $C$ בחזקת $d$ ברקורסיה של העלאות בריבוע. העיקרון הוא להקצות משתנה זמני שמתחיל ב-1, סורקים את הייצוג הבינארי של המעריך מימין לשמאל (מהסיבית הכי פחות משמעותית לסיבית העליונה). אם הסיבית היא "1" מכפילים את המשתנה הזמני ב-$C$ ומעלים בריבוע ואילו אם הסיבית היא "0" מבצעים רק העלאה בריבוע, מצמצמים את התוצאה במודולוס וממשיכים כאשר התוצאה האחרונה היא במשתנה הזמני. היות ש-$d$ אי זוגי, אנחנו יודעים שבסבב הראשון מתבצעת העלאה בריבוע וכפל מלא ב-$C$ אם מודדים את הזמן הדרוש לפעולה זו ומשווים עם הפעולה של האלגוריתם בסבב הבא ונמצא הבדל אפילו כלשהו אפשר להעריך שהסיבית השנייה היא "0". בדרך זו ניתן לעלות על כל הסיביות. באותה מידה אפשר לבצע את ההתקפה על ידי מדידת הפרשי צריכת החשמל בזמן ביצוע פעולות ההעלאה בריבוע וכפל.

דרך אחת לסכל התקפה זו היא באמצעות טכניקת "סינוור" (blinding) המנצלת את תכונת ההומומורפיות של RSA. לפני הפענוח מכפילים את המסר במספר אקראי כלשהו ולאחר הפענוח מחלקים בו שוב. בדרך זו מדידת התזמון אינה מועילה לתוקף כי המסר אקראי.

מחשב קוונטי ובעיית RSA

היות שביטחון הצפנת RSA מבוסס בעיקר על פירוק לגורמים - בידיעת הגורמים הראשוניים של המודולוס השיטה הופכת ללא בטוחה כלל, יש חשיבות בהקשר זה להתקדמות הטכנולוגית בכל המישורים בתחום פירוק לגורמים. מסיבה זו עם המצאת אלגוריתם שור והדיון על מחשבים קוונטיים, הנושא נעשה רגיש. כאשר מחשב קוונטי פונקציונלי יהפוך למעשי רוב האלגוריתמים האסימטריים ביניהם RSA יצאו מכלל שימוש.

ב-2011 פרסמה חברת D-Wave הקנדית שהצליחה לייצר מעבד קוונטי המכיל 128 קיוביטים שנועד בעיקר לפתרון בעיות כמו אופטימיזציה, מדגמים, ביואינפורמטיקה וכדומה. מומחי החברה הדגישו שהמעבד אינו מסוג מעבד לשימוש כללי ולכן לא מתאים לכל מטרה ועוד הם מצפים לכל היותר לשיפור ריבועי ביכולת החישובית לעומת מחשב קונבנציונלי בפתרון בעיות מסוימות בתורת המספרים. במאי 2013 הכריזה החברה על מחשב קוונטי מדור שני בעל 512 קיוביטים. המעבד של D-Wave כפי שהוצג אינו מתאים לפירוק לגורמים משום שלא ניתן להריץ עליו את אלגוריתם שור. המחשבים הקוונטיים הדיגיטליים שפותחו נכון להיות אינם מסוגלים לפרק לגורמים מספרים גדולים לפי התקן העולמי הנוכחי. בנוסף כל מספר שניתן לטעון ב-512 קיוביטים אפשר לפרק לגורמים על מחשב קונבנציונלי.

ראו גם

• RSA
• הצפנת פאיי
• הצפנת קריימר-שופ
• הצפנת רבין
• התקפת שיבוש (קריפטוגרפיה)