RSA

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

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

היסטוריה

עד 1976 האלגוריתמים הידועים להצפנה היו סימטריים במובן שמפתח ההצפנה שימש גם להצפנה וגם לפענוח. שיטות אלו סובלות בעיקר מהקושי שבהעברת מפתח ההצפנה הסודי לידי המקבל. ב-1976 פרסמו ויטפילד דיפי ומרטין הלמן מאמר מפורסם המתאר את התפיסה של המפתח הפומבי וכן דוגמה למימוש מעשי. כשנה לאחר מכן, רונלד ריבסט (Ronald Rivest), עדי שמיר (Adi Shamir) ולאונרד אדלמן (Leonard Adelman) ששהו במכון הטכנולוגי של מסצ'וסטס (MIT) פרסמו לראשונה את RSA ששמו נגזר מראשי תיבות שמותיהם. אלגוריתם RSA מבוסס על הרעיון של דיפי והלמן ויישם לראשונה את שיטת ההצפנה האסימטרית, שבה מקבל הצופן מפרסם מפתח הצפנה המכונה מפתח פומבי (שניתן לפרסמו ברבים ללא חשש) ובעזרתו מבוצעת ההצפנה עבורו ואילו הפענוח מתבצע אך ורק באמצעות המפתח הפרטי (הסודי) שנשאר בידיו, בכך אין צורך לסכן את מפתח הפענוח בחשיפה. אלגוריתם RSA זיכה את ממציאיו בפרס טיורינג לשנת 2002 על הישגם.

זכויות

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

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

בסיס מתמטי

שיטת RSA מבוססת על משפט אוילר הקובע: עבור כל $\ a$ ו-$\ n$ טבעיים הזרים זה לזה (שאין להם מחלק משותף מלבד 1) מתקיים: $\ a^{\phi(n)} \equiv 1 \ (\mbox{mod }n)$ (הפונקציה $\ \phi (n)$ נקראת פונקציית אוילר ומייצגת את מספר הטבעיים הזרים ל-$\ n$ וקטנים ממנו ו-$\ \mbox{mod }n$ מציין שהחישוב נעשה מדולו n). על כן מתקיים: $\ a^{\phi (n)+1}\equiv a^{\phi (n)} \cdot a\equiv a \ (\mbox{mod }n)$. ביטחון אלגוריתם RSA נשען על בעיה מתמטית הקרויה בעיית RSA המתוארת להלן.

הכנת מפתחות RSA

גרסת RSA הבסיסית:

1. בוחרים שני ראשוניים גדולים $\ p$ ו-$\ q$
2. מחשבים את $\ n = pq$
3. מחשבים את פונקציית אויילר: $\ \phi (n)=(p-1)(q-1)$ (מבוטא "פִי של $\ n$" ומסומן כאן בקיצור $\ \phi$)
4. בוחרים שלם $\ 1 < e < \phi$ שהוא זר ל- $\ \phi$
5. מחשבים $\ d$ המקיים את הקונגרואנציה: $\ de \equiv 1 \ (\mbox{mod }\phi)$

פירוט הפרמטרים

• $\ p$ ו-$\ q$ בשלב 1, צריכים להיות ראשוניים ואקראיים. על כן האסטרטגיה המומלצת היא בחירת מספר אקראי אי-זוגי בגודל הרצוי באמצעות מחולל מספרים אקראיים בטוח ובדיקת ראשוניותו באמצעות אלגוריתם בדיקת ראשוניות כלשהו. אפשר להסתפק באלגוריתם הסתברותי כגון אלגוריתם מילר-רבין לבדיקת ראשוניות במידה והפרמטרים נבחרים בקפידה באופן שיבטיח סיכוי קלוש לטעות. משפט המספרים הראשוניים מבטיח שתוך מספר קטן יחסית של הגרלות (בערך כמספר הספרות של המספר), נתקלים בראשוני.
• $\ n$ מכונה מודולוס ומהווה את קבוצת השלמים הטבעיים $\ \mathbb{Z}_n$ כאשר פעולות אריתמטיות סגורות תחת $\ n$, כלומר תוצאת פעולות חיבור וכפל היא השארית מחלוקה ב-$\ n$ (ראו חשבון מודולרי). $\ n$ משמש כמפתח פומבי ונדרש גם להצפנה וגם לפענוח, על כן צריך להיות נגיש לכל.
• הפרמטר $\ e$ (Encryption) נקרא מפתח פומבי המשמש להצפנה וצריך להיות נגיש לכל. $\ e$ יכול להיות כל שלם טבעי הנמוך מ-$\ n$ אולם חייב להיות זר ל- $\ \phi$ כלומר שאין לו מחלק משותף עם $\ \phi$ מלבד 1. מסמנים זאת: $\ \mbox{gcd}(\phi,e)=1$ (הפונקציה gcd מציינת מחלק משותף מרבי). זאת כדי להבטיח כי ההצפנה תהיה תמורה ייחודית (כלומר עבור כל $\ c$ יהיה $\ m$ יחיד המתאים לו). בדרך כלל רצוי לבחור $\ e$ קטן ככל האפשר כדי להקל על תהליך ההצפנה.
• הפרמטר $\ d$ (Decryption) נקרא מפתח פרטי המשמש לפענוח וצריך להישמר בסוד. $\ d$ נקרא הופכי כפלי מודולרי של $\ e$ (מודולו $\ n$) וניתן לסמנו: $\ e^{-1}$. להכנת $\ d$ נעזרים באלגוריתם אוקלידס המורחב (להלן), כדי לחשב את $\ de + k \phi = 1$ עבור שלם $\ k$ כלשהו.
• הראשוניים $\ p$ ו-$\ q$ בגרסת RSA הבסיסית לא נחוצים לתהליך ההצפנה והפענוח על כן רצוי להשמידם. כמו כן יש לרשום את המפתחות הציבוריים $\ n, e$ באופן שמבטיח את שלמותם ושייכותם לישות כלשהי כדלהלן.
• בתקן PKCS (גרסה 2), שונה מעט תהליך הכנת מפתחות ההצפנה. במקום לחשב את $\ \phi=(p-1)(q-1)$ מחשבים את $\ \lambda(n)=\mbox{LCM}(q-1, p-1)$, שהוא האקספוננט של חבורת אוילר $\ U_n$ (הפונקציה $\ \mbox{LCM}$ היא הכפולה המשותפת המינימלית). במקרה זה המפתח $\ d$ צריך לקיים את היחס $\ ed \equiv 1 \ (\mbox{mod } \lambda \left(n\right))$.

הצפנה ופענוח

הצפנה 

אליס משדרת לבוב את מפתחות ההצפנה ($\ e, n$) ושומרת בסוד את המפתח $\ d$. אם בוב מעוניין לשלוח את המסר $\ m$ לאליס תחילה עליו להפוך את המסר $\ m$ לערך מספרי הנמוך מ-$\ n$ בדרך מוסכמת כלשהי ואז מחשב את:

$\ \boldsymbol{c = m^e \mbox{ mod }n}$.

בוב מעלה את $\ m$ בחזקת $\ e$ ומצמצם מודולו $\ n$ ואת הטקסט המוצפן $\ c$ יוכל לשדר לאליס אפילו בערוץ פתוח (שאינו מאובטח).

פענוח 

אליס משחזרת את המסר $\ m$ מתוך הטקסט המוצפן $\ c$ בעזרת המפתח הסודי $\ d$ בדרך זו:

$\ \boldsymbol{m = c^d \mbox{ mod }n}$

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

הוכחה לנכונות האלגוריתם

לפי האלגוריתם מפתח הפענוח $\ d$ מקיים את השקילות $\ ed \equiv 1 \ (\mbox{mod } \phi)$, כלומר קיים שלם $\ k$ המקיים $\ ed=1+k \phi$. לפי משפט פרמה: $\ m^{p-1} \equiv 1 \ (\mbox{mod }p)$, אם נעלה את שני אגפי שקילות זו בחזקת $\ k(q-1)$ ונכפיל ב-$\ m$ נקבל: $\ m^{1+k(p-1)(q-1)} \equiv m \ (\mbox{mod }p)$ במקרה ש-$\ m$ זר ל-$\ p$ (במקרה ש-$\ m$ אינו זר ל-$\ p$ כגון אם $\ m$ הוא כפולה של $\ p$, השקילות האחרונה נכונה גם כן, כיוון שאז שני האגפים שקולים ל-0). בכל מקרה מזה נובע כי:

$\ m^{ed} \equiv m \ (\mbox{mod }p)$ ומאותה הטענה,

$\ m^{ed} \equiv m \ (\mbox{mod }q)$

היות ש-$\ p$ ו-$\ q$ הם ראשוניים שונים, לכן לפי משפט השאריות הסיני (CRT), חישוב מערכת שקילויות זו מניב $\ m^{ed} \equiv m \ (\mbox{mod }n)$. לכן:

$\ c^d \equiv (m^e)^d \equiv m^{ed} \equiv m \ (\mbox{mod }n)$.

דוגמה במספרים קטנים

נניח שאליס בוחרת את הראשוניים $\ p=97, q=127$ ומחשבת את: $\ n=97 \cdot 127=12319$ ואת פונקציית אוילר: $\ \phi=96 \cdot 126=12096$ וכן בוחרת את $\ e=11$ כמפתח פומבי, שים לב שמתקיים $\ \mbox{gcd}(12096,11)=1$. בעזרת אלגוריתם אוקלידס המורחב מתקבל $\ (3299 \cdot 11) \equiv 1 \ (\mbox{mod } \phi)$ כיוון ש-$\ 3299\cdot 11 \mbox{ mod }12096 = 1$, הרי ש-$\ d=3299$ הינו מפתח הפענוח המתאים. אליס שולחת את $\ 12319$ ואת $\ 11$ לבוב ושומרת בסוד את $\ 3299$.

אם בוב מעוניין להצפין את המסר $\ m=128$ עבור אליס הוא מחשב את:

$\ 128^{11} \mbox{ mod }12319 = 3557$

ושולח את $\ c=3557$ לאליס.

כשאליס מקבלת את $\ c$ היא מחלצת את $\ m$ בעזרת המפתח הסודי $\ 3299$:

$\ 3557^{3299} \mbox{ mod }12319=128=m$.

כמובן שדוגמה זו הנה להמחשה בלבד, חובה על הראשוניים $\ p$ ו-$\ q$ להיות גדולים מספיק כדי למנוע ניסיון לתקוף את האלגוריתם על ידי פירוק $\ n$ לגורמיו באמצעות אלגוריתם פירוק לגורמים ידוע (ראו פירוק לגורמים).

חתימה דיגיטלית

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

אם אליס מעוניינת לשלוח את המסר $\ m$ כשהוא חתום על ידה לבוב, היא מבצעת:

$\ \bar{m} = R(m)$

$\ s = \bar{m}^d \mbox{ mod }n$ (בדיוק כמו בתהליך הפענוח לעיל).

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

לאימות החתימה, בוב מחשב את:

$\ \bar{m} = s^e \mbox{ mod }n$ (בדיוק כמו תהליך ההצפנה לעיל)

$m = R^{-1}(\bar{m})$

בוב משיג עותק אותנטי של מפתח האימות $\ e$ בעזרתו הוא מחלץ את $\ \bar{m}$ ובהפעלת הפונקציה ההופכית $\ R^{-1}$ משחזר את המסר המקורי. בוב יכול להיות משוכנע כי רק אליס שהיא בעלת המפתח הפרטי המתאים, יכולה להיות המקור למסר זה ובמיוחד שהמסר לא שונה על ידי גורם כלשהו במהלך המשלוח.

פונקציית היתירות הכרחית כיוון שללא השימוש בה, יהיה קל למצוא מסר אחר שעבורו החתימה של אליס תהיה תקפה מבלי לדעת את המפתח הפרטי שלה. זאת בשל הכיפליות של RSA. כדי לראות מדוע נניח כי $\ R(m)= m$, אם אליס חתמה על שני מסמכים שונים $\ m_1$ ו-$\ m_2$ אזי כפולה של החתימות: $\ s_1 = m^d_1 \mbox{ mod }n$ ו-$\ s_2 = m^d_2 \mbox{ mod }n$ על המסרים הנ"ל תהיה חתימה תקפה עבור המסר $\ m = m_1m_2$. פונקציית היתירות מבטלת את האסוציאטיביות של החתימות ועל כן מונעת בעיה זו.

גרסאות RSA מתקדמות

החסרון העיקרי בגרסה הבסיסית המתוארת לעיל הוא בגודל המפתחות. בעוד שמפתח ההצפנה יכול להיות קטן מאוד (כגון: $\ e=3$), בשל שיקולי ביטחון (ראו להלן) מפתח הפענוח חייב להיות גדול - קרוב לגודלו של $\ n$. היות שאלגוריתם RSA מערב העלאה בחזקה מודולרית, זמן ההצפנה והפענוח תלויים ישירות במספר סיביות המפתח. מאז המצאת RSA נעשו מספר נסיונות לצמצם את גודל המפתחות ולשפר בכך את יעילות האלגוריתם. הדרך הפופולרית ביותר היא ניצול משפט השאריות הסיני (CRT). הרעיון הוא שאפשר לייעל את תהליך הפענוח על ידי פיצולו לתהליכים קטנים יותר, למשל על ידי פיצול מפתח הפענוח למספר מפתחות קטנים וחישוב העלאה בחזקה עם כל אחד מהם בנפרד ואז בעזרת אלגוריתם CRT כלשהו לחשב את התוצאה הסופית מתוך מערכת השקילויות שנוצרת. חישוב CRT הנו זניח יחסית לפעולת העלאה בחזקה מודולרית, על כן שיטה זו משפרת משמעותית את תהליך הפענוח. משפט השאריות הסיני מאפשר פענוח מהיר יותר במיוחד בפלטפורמה מרובת מעבדים, בה ניתן לחשב העלאה בחזקה מודולרית באופן מקבילי.

RSA-CRT ‎ 

ב-1982 פותחה גרסה חדשה של אלגוריתם RSA הנקראת RSA-CRT בשיטה זו תהליך ההצפנה אינו שונה, אולם תהליך הכנת המפתחות וכן תהליך הפענוח דורשים מספר התאמות: מפצלים את מפתח הפענוח לשני מפתחות (קטנים יותר) $\ d_p$ ו-$\ d_q$ באופן שמתקיים $\ e \cdot d_p \equiv 1 \ (\mbox{mod }(p-1))$ וכן $\ e \cdot d_q \equiv 1 \ (\mbox{mod }(q-1))$. הפענוח מתבצע כך: תחילה מחשבים את $\ m_1=c^{d_p} \mbox{ mod }p$ ואת $\ m_2=c^{d_q} \mbox{ mod }q$. נעזרים באלגוריתם גרנר (Garner) לחישוב CRT, כדי לחלץ את $\ m$ מתוך מערכת השקילויות כך: $\ h=(m_1-m_2) \cdot q^{-1} \mbox{ mod }p$ (כאשר $\ q^{-1}$ הוא הופכי כפלי של $\ q$ מודולו $\ p$). המסר $\ m$ יהיה $\ m_2+q \cdot h$. כיוון שהמפתחות $\ d_p$ ו-$\ d_q$ קטנים יותר זמן הפענוח מתקצר משמעותית, זאת מבלי לאבד מביטחון האלגוריתם. גרסת RSA-CRT מהירה יותר מהגרסה הבסיסית בפקטור של 2 בקירוב.

Batch RSA ‎ 

גרסת RSA של עמוס פיאט שבה, אם המפתח הפומבי קטן מאוד, ניתן לפענח מספר מסרים שהוצפנו תחת אותו מודולוס בבת אחת. רעיון זה שימושי במערכות דוגמת שרת SSL המבצע פעולות Handshake בתדירות גבוהה. במקרה כזה ניתן לשנות את ארכיטקטורת השרת כך שימתין לקבלת מספר בקשות פענוח ואז יפענח את כל המסרים במחיר של פעולת פענוח אחת, בתנאי כמובן שהמודולוס זהה ומפתחות ההצפנה קטנים (ושונים). שיטה זו משפרת את יעילות אלגוריתם RSA בפקטור של כמעט 3.5 אם מבצעים שמונה פענוחים בבת אחת. כדי להסביר כיצד זה פועל, ידוע שבעיית RSA היא מציאת שורש ממעלה כלשהי מודולו שלם פריק $\ N$. כלומר:

$\ M^d \ (\mbox{mod }N) = M^{1/e} \ (\mbox{mod }N)$.

כלומר בתהליך הפענוח וכן בתהליך הכנת החתימה המתוארים לעיל, יש צורך להעלות את $\ M$ בחזקת $\ d$ כלומר לחשב את $\ M^{1/e}$. אם למשל $\ e_1=3, e_2=5$, ונתונים $\ M_1, M_2$ שעבורם צריך לחשב את $\ m^{1/3}_1$ ואת $\ M^{1/5}_2$, אפשר לחשב תחילה את:

$\ M = M^5_1 \cdot M^3_2 \ (\mbox{mod }N)$ ואת,

$\ I=M^{1/15} \ (\mbox{mod }N)$.

ואז לפתור את המשוואות הנ"ל כדלהלן:

$\ \frac{I^6}{M^2_1 \cdot M_2}=M^{1/5}_2 \ (\mbox{mod }N)$,

$\ \frac{I}{M^{1/5}_2}=M^{1/3}_1 \ (\mbox{mod }N)$.

יוצא שרק בחישוב $\ I=M^{1/15}$ נדרשת העלאה בחזקה מודולרית מלאה, בנוסף למספר קבוע קטן של פעולות כפל וחילוק מודולריים. החסכון הוא ששני העלאות בחזקה מודולו $\ N$ בוצעו כמעט במחיר של העלאה בחזקה מודולרית אחת. הטריק המתואר מסתמך על העובדה שהמעריכים זרים זה לזה. אפשר להוסיף שיפורים לשיטה זו כמו CRT האמור. החסרון העיקרי הוא בצורך במפתחות הצפנה קטנים מאוד כגון: $\ 3,5,7,11$). הבעיה היא שבדרך כלל מפתח הצפנה טיפוסי של RSA גדול יותר (כגון: $\ e=65537$ ומעלה) במקרה כזה Batch RSA לא תהיה יעילה בשל התקורה הרבה הנוספת.

Multi-prime RSA 

גרסה זו מבוססת על שינוי מבנה המודולוס. בשיטה זו במקום להשתמש במודולוס במבנה $\ n=pq$, מיישמים את RSA עם מודולוס במבנה $\ n=pqr$, כמובן תוך ניצול משפט השאריות הסיני כדי לחשב את מערכת המשוואות לאחר פענוח עם כל אחד מהגורמים הראשוניים לחוד. אם למשל המודולוס הוא בגודל 1024 סיביות אזי כל גורם ראשוני יהיה בגודל 341 סיביות. חישוב חזקה מודולרית בסדר גודל כזה מהיר במידה ניכרת מאשר בשיטה הרגילה. מפתח ההצפנה יכול להיות קטן (כגון $\ e=65537$). אפשר להרחיב את הרעיון בעצם לכל מספר של גורמים ראשוניים. משיקולי ביטחון במקרה שהמודולוס בגודל 1024 סיביות מספר הגורמים המקסימלי יכול להיות 3. RSA multi-prime מהירה יותר מהגרסה הבסיסית בפקטור של 2 בקירוב. תקן PKCS #1 למעשה תומך בגרסה זו של RSA ומפרט דרכים ליישומה.

Multi-power RSA 

בגרסה זו המודולוס הוא מהצורה: $\ N=p^{b-1}q$ כאשר $\ p$ ו-$\ q$ הם בגודל $\ n/b$ סיביות (n הוא מספר סיביות המודולוס). במקרה של 1024 סיביות משיקולי ביטחון, לכל היותר $\ b=3$. בפענוח משתמשים בשיטת Hensel lifting שהיא יעילה יותר מהעלאה בחזקה מודולית רגילה. בשיפורים קלים multi-power יעילה יותר מהשיטה הבסיסית בפקטור של 2.3 לפחות.

Rebalanced RSA 

הרעיון של שיטה זו נועד להתמודד עם חוסר האיזון הבולט הקיים ביישומים מעשיים של הגרסה הבסיסית של RSA, בין גודל מפתח ההצפנה לבין גודל מפתח הפענוח. עובדה זו נובעת משיקולי יעילות אך לא תמיד רצויה. במערכות רבות (דוגמת SSL) נוצר לעתים עומס יתר על הצד המפענח לעומת הצד המצפין. במיוחד הדבר חשוב כאשר מדובר בטלפון נייד שאמור לייצר חתימת RSA שתאומת לאחר מכן על ידי שרת מרכזי מהיר. כאן דווקא תהליך יצירת החתימה (המקביל לפענוח) צריך להיות קל יותר כיוון שהוא נעשה בסביבה מוגבלת הן בכמות זיכרון והן ביכולת החישוב. גרסת Rebalanced RSA דומה ל-RSA-CRT המתוארת לעיל, מלבד זאת שבגרסה זו מקזזים מגודל מפתח הפענוח על חשבון מפתח ההצפנה. השוני הוא בעיקר באלגוריתם הכנת המפתחות. אם השיטה מיושמת נכון ניתן להגיע למפתחות פענוח בסדר גודל של 160 סיביות כל אחד (במקרה של מודולוס בגודל 1024 סיביות). התקורה הנוספת מתהליך הכנת המפתחות וכן חישוב CRT בשלב הסופי של הפענוח נמוכה ביותר. חסרונה של השיטה הוא בעיקר בעובדה שהמפתח הפומבי גדול מאוד (קרוב לגודלו של n), עקב כך לא בכל המערכות ניתן לישמה. יש מערכות המגבילות את גודל מפתח ההצפנה משיקולי יעילות. שיטה זו יעילה יותר מהגרסה הבסיסית של RSA בפקטור של 3 לפחות.

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

ביטחון

שיטת RSA מתבססת על בעיית RSA (נקראת גם RSAP) כדלקמן: נתון שלם חיובי $\ n=pq$, מכפלת שני ראשוניים שונים שווים בגודלם בקירוב, נתון שלם חיובי $\ e$ הנמוך מ-$\ n$ המקיים $\ \mbox{gcd}((p-1)(q-1),e)=1$ (פירושו ש-$\ e$ זר ל-$\ (p-1)(q-1)$) ונתון שלם $\ c$ כלשהו. מצא את $\ m$ המקיים את המשוואה: $\ m^e \equiv c \ (\mbox{mod }n)$ (פירושו $\ m^e$ שקול ל-$\ c$ מודולו $\ n$). במילים אחרות הבעיה היא מציאת שורש ממעלה $\ e$ של $\ c$ (מודולו $\ n$). המגבלות שהוטלו על הפרמטרים מבטיחים כי לכל $\ c$ קיים אך ורק $\ m$ יחיד המקיים שקילות זו, מאחר שהפונקציה החד-כיוונית $\ f(m)=m^e \mbox{ mod }n$ היא תמורה ב-$\ \mathbb{Z}_n$. הקושי נעוץ בעובדה שתוצאת הפונקציה האמורה אינה לינארית ולמעשה מתנהגת כפונקציה אקראית. חיפוש סדרתי של ערך כזה מחייב במקרה הגרוע בדיקת כל המעריכים האפשריים ועל כן אינו מעשי.

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

מקובל להניח, כי בעיית RSAP שקולה לבעיית פירוק מספר שלם לגורמים שהיא כידוע בעיה קשה, שנכון להיום לא ידוע על דרך יעילה לפתרונה. לפי סברה זו כל דרך לפתרון בעיית RSAP תאפשר גם פתרון בעיית פירוק לגורמים באופן יעיל, אם כי איש לא הוכיח זאת מעולם מבחינה מתמטית. לעומת זאת קיימת הוכחה בכיוון ההפוך, כלומר אם תמצא דרך קלה לפירוק $\ n$ לגורמים, אזי קל לראות שבעיית RSAP ניתנת לפתרון יעיל. כיוון שחישוב הפונקציה החד-כיוונית $\ c=m^e \mbox{ mod }n$ בכיוון ההפוך יהיה קל אם הגורמים הראשונים של $\ n$ ידועים שאז פשוט מחשבים את $\ \phi$ ואת $\ d$ באותה הדרך בה ביצעה זאת אליס.

כמו כן אפשר לראות שאם מפתח הפענוח $\ d$ ידוע אזי ניתן בעזרתו לפרק לגורמים את המודולוס כדלהלן: היות ש-$\ ed \equiv 1 \ (\mbox{mod }n)$ כלומר $\ ed-1 = k \phi$. ולפי משפט אוילר $\ a^{\phi} \equiv 1 \ (\mbox{mod }n)$ לכל $\ a$ ב-$\ \mathbb{Z}^*_n$, לכן גם $\ a^{ed-1} \equiv 1 \ (\mbox{mod }n)$. אם נייצג את $\ ed-1$ כ-$\ 2^st$ עם $\ t$ אי-זוגי כלשהו, נוכל למצוא $\ i < s$ וכן שלם $\ a$ המקיימים $\ a^{2^{i-1}t} \not\equiv \pm 1 \ (\mbox{mod }n)$ ולעומת זאת $\ a^{2^i t} \equiv 1 \ (\mbox{mod }n)$. לפחות מחצית האלמנטים ב-$\ \mathbb{Z}^*_n$ עונים על דרישה זו, כך שהסיכוי למצוא זוג ערכים $\ (a, i)$ כאלו גבוה. ומכאן הדרך קלה כיוון שבהכרח $\ \mbox{gcd}(a^{2^{i-1}t} - 1,n)$ הנו גורם לא טריויאלי של $\ n$.

למשל, בדוגמה לעיל $\ ed-1 = 2^6 \cdot 567$ חשבון פשוט מראה שאם $\ a=2, i=4$ מתקבל $\ 2^{2^4 \cdot 567}$ שקול ל-$\ 1$ וכן $\ 2^{2^3 \cdot 567}$ שקול ל-$\ 10669$ (מודולו $\ 12319$), אם נחשב את המחלק המשותף המרבי של $\ 10668$ ו-$\ 12319$ נקבל $\ 127$ שזה אחד מהגורמים הראשוניים של $\ n$.

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

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

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

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

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

יעילות

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

קיימות ספריות תמיכה מתמטיות לחישובים אריתמטיים מרובי ספרות לשפות התכנות הנפוצות כגון: Long Integer Package (או FreeLIP), ספריית תמיכה למספרים ארוכים בשפת C של ארג'ן לנסטרה, שסייעה באתגר הראשון כנגד RSA, פירוק לגורמים של המודולוס RSA-129 (בגודל 426 סיביות) ב-1994. או המחלקה BigInteger של Java ועוד רבים.

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

פרמטרים

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

כמו כן חשוב שהמפתח הפרטי $\ d$ (מפתח החתימה במקרה של חתימה דיגיטלית) יהיה גדול ככל האפשר. באוגוסט 1989 פרסם מיכאל ויינר התקפה כנגד RSA עם מפתח פרטי קטן. הוא הראה שאם $\ d < n^{1/4} / 3$ ניתן לחשב את המפתח הפרטי מתוך $\ n$ ו-$\ e$ באופן יעיל למדי, באמצעות מה שמכונה קירוב שברים משולבים או קירוב רציונלי. התקפה זו אינה ישימה כאשר המפתח הפרטי גדול.

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

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

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

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

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

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

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

ריפוד

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

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

• במקרה ש- m = 0, m = 1 תוצאת ההצפנה תהיה תמיד m עצמו.
• במקרה ש- m = n - 1 תוצאת ההצפנה תהיה m עצמו.
• כאשר מצפינים עם מעריך e קטן כגון e = 3 ערכים קטנים של m עלולים להניב תוצאות קטנות הנמוכות מהמודולוס מה שמאפשר חישוב שורש ממעלה שלישית ללא תלות במודולוס.
• במקרה שהמסר קטן ניתן לתקוף את ההצפנה במתקפת טקסט מוצפן נבחר, שבה התוקף מצפין מראש את כל האפשרויות של m כדי לבדוק את תוצאתם, בסבירות גבוהה הוא יעלה על c מתאים ובכך יפענח את הטקסט המוצפן מבלי לתקוף את השיטה עצמה.

באופן כללי כדי להימנע ממצבים בהם טקסט המיועד להצפנה יפגע בביטחון ההצפנה, מקובל "לרפד" את המסר באמצעות אלגוריתם ריפוד מתאים לפני ההצפנה, כדי לבטל את מבנהו המקורי ולהימנע ממבנה "חלש". הדרך הנאיבית היא לשרשר מספר אקראי כלשהו למסר עצמו לפני ההצפנה. המספר האקראי מטשטש את מבנה המסר המקורי ומבטל את האופי הדטרמיניסטי של אלגוריתם ההצפנה ובכך מסכל את התקפת טקסט מוצפן נבחר האמורה. למעשה תקן PKCS #1 (הגרסה הראשונה) יישם שיטת ריפוד פשוטה כזו. לפני ההצפנה המסר רופד באפסים ובמספר אקראי באורך מוגדר כלשהו. אולם ב-1998 הראה דניאל בלייכבכר ממעבדות בל כיצד ניתן לפצח את הצפנת RSA בשיטת ריפוד כזו בקלות רבה. עקב כך פרוטוקולי SSL שיישמו את תקן PKCS #1 הראשון באלפי שרתים מסביב לעולם היו פרוצים לחלוטין.

ב-1993 ניסחו מיהיר בלייר ופיליפ רוגווי (Bellare-Rogaway) מתמטיקאים מאוניברסיטת קליפורניה בסן דייגו, רעיון מודל אורקל אקראי (Random oracle model) שהושאל מתורת הסיבוכיות לצורך הצפנה. רעיון זה מאפשר ליישם שיטות הצפנה אסימטרית (דטרמיניסטית) בעלת "ביטחון מוכח" ו"ביטחון סמנטי". הם פתחו אלגוריתם הנקרא OAEP (קיצור של Optimal asymmetric encryption padding) המשתמש במחולל מספרים אקראיים ופונקציית גיבוב לבניית המסר באופן בטוח לפני ההצפנה. ב-1998 תקן הצפנת מפתח-פומבי PKCS #1 תוקן ואלגוריתם OAEP שולב בתקן כשיטת הריפוד התקנית להצפנת מפתח פומבי הנקראת RSA-OAEP. קיימים אלגוריתמים נוספים לריפוד מסרים בטוח כמו AEOP+, SAEP+, REACT בהתבסס על עבודתו של ויקטור שאופ.

אלגוריתמים

כאמור מפתח הפענוח $\ d$ נקרא הופכי כפלי של $\ e$ (מודולו $\ n$). מציאת הופכי כפלי נעשית באמצעות אלגוריתם אוקלידס המורחב. הגרסה הבסיסית מתוארת להלן:

  Input:   a, b (a >= b).
  Output:  d = ax + by. (d is Gcd(a, b))
  1. if b = 0 then
        d = a, x = 1, y = 0.
        Goto: 5.
  2. x1 = 0, x2 = 1, y1 = 1, y2 = 0
  3. While b > 0 do:
     3.1 q = a / b, r = a mod b,
         x = x2 - q * x1,
         y = y2 - q * y1.
     3.2 a = b, b = r,
         x2 = x1, x1 = x,
         y2 = y1, y1 = y
  4. d = a, x = x2, y = y2
  5. return d, x, y

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

  Input: a, k, n (a < n, k is represented by array of t binary digits).
  Output: a^k mod n (the sign ^ stands for exponentiation)
  1. b=1
  2. if k = 0 then return b.
  3. if k[0] = 1 then b = a.
  4. For i from 1 to t do:
     4.1 a = a^2 mod n.
     4.2 if k[i] = 1 then b = a * b mod n.
  5. return b.

עוברים על k המייצג את סיביות המעריך החל מהסיבית הנמוכה ביותר כלפי מעלה. בכל שלב מעלים את a בריבוע ובנוסף אם הסיבית הנוכחית היא 1 מכפילים את a ב-b, כאשר התוצאה הסופית היא b.

הקטע הבעייתי באלגוריתם הוא הצמצום המודולרי. בשיטה הנאיבית מבצעים צמצום מודולרי על ידי חלוקה ב-n אך השימוש בחילוק אינו מומלץ אם רוצים להגיע לביצועים אופטימליים. קיימות שיטות יעילות יותר לצמצום מודולרי כמו שיטת Barrett או שיטת מונטגומרי. האחרונה נחשבת ליעילה יותר ונפוצה במימושים מעשיים בהם נדרש צמצום מודולרי כמו ב-RSA.

התקפות

מתקפת תזמון

ב-1995 פותחה התקפה כנגד RSA הנקראת Timing Attack. התקפה זו עושה שימוש בעובדה שמהירות הצפנת RSA תלויה בקלט. אם לתוקף יש גישה למערכת שבה מתבצעת ההצפנה, גם אם אין לו גישה לפרמטרים של ההצפנה ביכולתו לחלץ את מפתח הפענוח באמצעות מדידת הפרשי הזמן בעת פענוח מספר מסוים של טקסטים מוצפנים. יתרה מזו במערכות מסוימות מיישמים גרסאות ממוטבות של RSA המנצלות את הגורמים הראשוניים של n כדי לשפר ביצועים. אולם נתון זה מהווה פרצת אבטחה כיוון שאם לתוקף יש גישה למערכת (כמו כרטיס חכם או מעגל משולב במכשיר כלשהו) הוא מסוגל לחלץ את הגורמים הראשוניים של n בהסתמך על מידע שדולף מהמערכת בשל ניצול משפט השאריות הסיני כדי לחשב מערכת קונגרואנציות המערבות שימוש בגורמים הראשוניים p ו-q.

ישנן שתי דרכים להתמודדות עם התקפה זו. האחת, היא להבטיח כי תהליך הפענוח יתרחש בזמן קבוע עבור כל מסר אפשרי, ניתן לעשות זאת באמצעות השהיה מכוונת בצד המערכת. אולם שיטה זו מפחיתה מיעילות המערכת באופן משמעותי. הגישה השנייה נקראת Blinding (לעוור) והיא הגישה המקובלת. בשיטה זו מנצלים את תכונת הכפליות של RSA (להלן). במקום לפענח את הטקסט המוצפן ישירות, בוחרים $\ r$ אקראי כלשהו ואז מחשבים את: $\ (cr^e)^d \mbox{ mod }n$ והתוצאה תהיה $\ mr \mbox{ mod }n$. ניתן להסיר את הערך האקראי מהמסר על ידי הכפלה ב-$\ r^{-1}$ (ההופכי של $\ r$ מודולו $\ n$). בצורה זו הפענוח אינו תלוי בטקסט המוצפן המתקבל ועל כן התקפת תזמון תכשל במקרה כזה.

הפצת מפתחות

נדמה כאילו הצפנת RSA היא הפתרון המושלם, למעשה אין זה כך. הצפנת RSA לבדה אינה פותרת את בעיית האימות והבטחת השלמות. במילים אחרות, תוקף אקטיבי המסוגל להשתלט על ערוץ התקשורת שבין אליס ובוב, ליירט מסרים לשנותם ולשולחם ליעדם, מסוגל להונות את המשתתפים ולקרוא את כל התשדורות המוצפנות. בהתקפה זו הנקראת Man in the middle, התוקף מיירט את מפתח ההצפנה שאליס שולחת לבוב ומחליפו באחר, כך שבוב יצפין את המסר עבור אליס במפתח הלא נכון בלא ידיעתו. כמו כן התוקף יירט את המסר המוצפן שבוב שולח לאליס, יפענחו יקרא את תוכנו ואז יצפינו במפתח הנכון וישלח אותו ליעדו, כאשר בוב ואליס אינם מודעים למתרחש. במילים אחרות, בוב חייב להיות בטוח שהמפתח הפומבי אכן שייך לאליס. כמו כן אליס אינה יכולה לדעת מיהו המקור למסר שקיבלה ללא אמצעים נוספים כדי להבטיח זאת. על כן יש צורך להבטיח את שלמות ואותנטיות מפתח ההצפנה והמסר המוצפן. זאת עושים באמצעות שיטות אימות ידועות, ביניהן העזרות בצד-שלישי נאמן (כמו רשות אישורים CA) וחתימה דיגיטלית.

תכונת הכפליות (Multiplicative)

אם $\ m_1, m_2$ הנם מסרים כלשהם כאשר הטקסטים המוצפנים המקבילים להם הם $\ c_1, c_2$ בהתאמה. אזי מתקיימת הזהות הבאה:

$\ (m_1 \cdot m_2)^e \equiv m^e_1 \cdot m^e_2 \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$ על ידי הכפלה בהופכי שלו כדי לקבל את הטקסט מקורי. למשל בדוגמה שניתנה לעיל, אם $\ r=1804$ אזי $\ 1804^{11}\cdot 3557=1312 \ (\mbox{mod }12319)$. אם נחשב את $r^{-1}=2711 \ (\mbox{mod }12319)$ אזי ניתן לחלץ את m על ידי $\ (1312^{3299} \cdot 2711) \mbox{ mod }12319 = 128 = m$.

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

התקפת המעגליות (Cycling attack)

בשל העובדה שהצפנת 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.

ראו גם

• פונקציה חד כיוונית

קישורים חיצוניים

• המאמר המקורי של ריבסט, שמיר ואדלמן A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, המכון הטכנולוגי של מסצ'וסטס, קיימברידג' מסצ'וסטס, אפריל 1977.
• תקן PKCS #1 להצפנת RSA, אתר מעבדות RSA.
• נימוקי הוועדה, להענקת פרס טיורינג ל-RSA
• תמי לפידות וד"ר דלית לוי, הסבר תמציתי ובהיר (עברית) על שיטת RSA, הצפנה בכלל, ומקבלי פרס טיורינג
• סדרת מאמרים של מעבדות RSA, המסבירים את עקרונות אלגוריתם RSA, הבסיס המתמטי, היתרונות והתועלת שבשיטה.
• התקפות על צופן הRSA במיזם UnderWarrior
• גרסאות מהירות של RSA, מגזין CryptoBytes (כרך 5) ינואר 2002.