בעקבות פרשת סנאודון, ישנם מומחי אבטחה המעריכים כי נכון לשנת 2013 ארגונים בינלאומיים בעלי אמצעים כמו NSA מסוגלים לפצח מפתח כזה בעלות של כמיליארד דולר בזמן קצר בהרבה (כמספר שעות).
לפי חוק מור כל שנתיים בערך היכולת הטכנולוגית מכפילה עצמה. אולם קצב המיזעור הולך ודועך. בשנת 2007 צוטט מור כי בתוך עשר שנים לא יתאפשר מיזעור נוסף בהתאם לחוק שהגה. בהערכה זהירה מודולוס בגודל 2048 סיביות (או 4096 סיביות לאלו שחוששים במיוחד), מספק רמת ביטחון ראויה לכל צורך מעשי בזמן הקרוב.
תכונת המעגליות.
בשל העובדה שהצפנת RSA הנה תמורה ב-formula_83, אם formula_84 קיים שלם formula_85 המקיים formula_86. מאותה סיבה formula_87. אם formula_88 קטן חיפוש סדרתי של formula_85 כזה אפשרי. אפשר להתחיל בערך נמוך ולקדם את formula_85 עד שהמשוואה האמורה מתקיימת. יתרה מזו, ניתן לייעל את ההתקפה על ידי מציאת השלם formula_91 העונה על הדרישה formula_92. יש סיכוי טוב למצוא את formula_91 בפחות מהזמן הדרוש למצוא את formula_94. אם formula_95 מודולו אחד מהגורמים הראשוניים של formula_88, אזי formula_97 הוא גורם ראשוני של formula_3 וכאמור ידיעת הגורמים הראשוניים מספקת לחילוץ מפתח הפענוח. במקרה ש-formula_99 אזי מתקיים בהכרח formula_100 וכאמור formula_101, במקרה כזה מתקבל formula_102 בלא צורך במפתח הפענוח כלל. למעשה אפשר לראות בשיטה זו כדרך שונה לפירוק formula_3 לגורמים. כאמור, פירוק לגורמים היא בעיה קשה כך שתכונה זו אינה מהווה איום משמעותי על אלגוריתם RSA.
מספרים ראשוניים.
כאמור חשוב שהמספרים הראשוניים ייבחרו באקראי. לא מומלץ למשל להשתמש ברשימת מספרים ראשוניים מפורסמת, כיוון שבדרך זו מועבר מידע ליריב פוטנציאלי. בבחירת מספרים ראשוניים רצוי שיהיו לא רק אקראיים אלא גם קשים לניחוש. אילו הגדרות שונות, כיוון שאקראיות לבדה אינה מבטיחה קושי בניחוש. על כן השיטה המקובלת היא הפעלת מחולל אקראי בטוח ליצירת מספר אי-זוגי אקראי באורך הרצוי ובדיקת ראשוניותו, מכיוון שבדיקת ראשוניות קלה יותר מפירוק לגורמים, אם המספר מתגלה כפריק מנסים שוב עם מספר אחר. הסיכויים הם שתוך מספר ניסיונות קצר בערך כמספר הספרות, יימצא ראשוני. כמו כן רצוי ש-formula_8 ו-formula_9 יהיו בגודל זהה בקירוב, כלומר שלמודולוס formula_3 לא יהיו גורמים קטנים כלשהם. זאת כדי לסכל אפשרות שימוש באלגוריתם פירוק שמנצל את קיומם של גורמים קטנים. מצד שני רצוי שההפרש ביניהם לא יהיה קטן מדי. כי אם formula_107, אזי גם formula_108 ואז ניתן למצוא אותם בחיפוש קל, קרוב לשורש.
יש הממליצים להשתמש במספרים ראשוניים חזקים. formula_109 הוא מספר ראשוני חזק אם הוא מקיים את ההגדרות הבאות:
הוכח מעשית שאין צורך במספרים ראשוניים חזקים, משום שמספרים ראשוניים גדולים מאוד שנבחרו אקראית בדרך בטוחה, כמעט תמיד נוטים לענות על דרישות אלו.
חשיפת המפתח הפרטי לעומת פירוק לגורמים.
ההוכחה פשוטה. אם formula_19 ידוע אפשר לחשב את formula_120. ידוע ש-formula_85 צריך להיות כפולה של הסדר formula_21. היות ש-formula_21 זוגי, אם כותבים את formula_85 כ-formula_125 כאשר formula_126 אי-זוגי ו-formula_127, מתקיים formula_128 עבור כל formula_129 ולכן formula_130 הוא שורש ריבועי של formula_131 מודולו formula_3. לפי משפט השאריות הסיני ל-formula_131 ארבעה שורשים ריבועיים מודולו formula_68. שניים הם formula_135 האחרים הם formula_136 כאשר formula_48 מקיים formula_138 וכן formula_139. בעזרת אחד משני השורשים האחרונים אפשר לגלות את הגורמים של formula_3 על ידי חישוב formula_141 (gcd היא מחלק משותף מקסימלי). אפשר לראות שאם formula_142 נבחר באקראי, אחד מהאלמנטים ברצף formula_143 מודולו formula_3 הוא שורש ריבועי של formula_131 בהסתברות של לפחות חצי. כל האלמנטים ברצף האמור ניתנים לחישוב בזמן של formula_60.
הטענה ההפוכה נובעת ישירות מהעובדה שבהינתן הגורמים הראשוניים אפשר לחשב את formula_21 ואת formula_19. מזה נובע שבעיית פירוק לגורמים שקולה לחשיפת המפתח הפרטי, כך שאין טעם להסתיר את המפתח הפרטי ממי שהגורמים ידועים לו וכן להפך. מסיבה זו לא יהיה חכם לשתף מודולוס אחד לכמה משתמשים (כך שרק המפתחות הפרטיים והציבוריים שלהם שונים). כי בידי כל אחד מהם מספיק מידע כדי לפרק את formula_3 לגורמים ואז הוא יכול לחלץ את המפתחות הפרטיים של כל האחרים מתוך המפתחות הציבוריים שלהם.
מעריך d קטן.
בפענוח סיבוכיות פעולת ההעלאה בחזקה המודולרית, ליניארית ביחס לאורכו של formula_19 בסיביות, מסיבה זו אם המפתח הפרטי קטן משיגים שיפור ביעילות הפענוח בפקטור משמעותי. התקפה מתוחכמת של מייקל ויינר מראה שעם מפתח פענוח קטן אפשר לשבור את המערכת כולה בקלות. הטענה היא:
ההתקפה של ויינר מבוססת על קירוב שברים משולבים. היות ש-formula_156 שקול ל-formula_131 מודולו formula_21 קיים formula_85 המקיים formula_160. מתקיים יחס הקירוב:
השברים formula_162 נותנים קירוב טוב של formula_163 על ידי התכנסות השבר המשולב. התוקף יכול לחשב את ההתכנסויות עבור formula_163. אחד מהם יהיה שווה ל-formula_162 ולאור האמור צריך להיות formula_166 ולכן formula_162 הוא שבר מצומצם. האלגוריתם של ויינר מאפשר חילוץ formula_19 בזמן ליניארי. אם formula_3 באורך 1024 סיביות formula_19 חייב להיות לפחות 256 סיביות כדי לסכל התקפה זו. לחלופין אפשר להגדיל את formula_1 על חשבון formula_19. ויינר הראה שאם formula_173 ההתקפה שלו לא תצלח. על כל פנים הגדלת formula_1 אינה פותרת את בעיית היעילות אלא מעבירה אותה להצפנה. ייתכן ושיטה זו תהיה יעילה במקרים בהם המחיר שווה את התועלת, אם אין חשיבות לגודל מפתח ההצפנה לעומת מפתח הפענוח.
ייעול ההצפנה והפענוח מבלי להסתכן בהתקפה של ויינר, אפשרי באמצעות משפט השאריות הסיני כפי שמובא בתקן PKCS. אם מחלקים את formula_19 לשני מפתחות פענוח כך שמתקיים formula_176 וכן formula_177 ואורך כל אחד מהם מחצית מאורך המודולוס. אזי הפענוח מתייעל בפקטור של שניים בקירוב. בפענוח משתמשים במשפט השאריות הסיני כדי לפתור את מערכת השקילויות formula_178 וכן formula_179 כדי לחשב את formula_4. והרעיון הוא שהמפתחות formula_181 ו-formula_182 קטנים לכן העלאה בחזקה עם מפתחות אילו יעילה יותר. לא ברור האם השיטה הזו מחזקת או מחלישה את RSA.
החסם שהציע ויינר אינו מדויק. בונה ואחרים הוכיחו שכל עוד formula_183 אפשר לשחזר את formula_19 מתוך formula_5. בכל אופן החסם המדויק הוא שאלה פתוחה.
מעריך e קטן.
משיקולי יעילות מקובל שהמעריך הציבורי יהיה קטן, זאת מבלי לפגוע בביטחון המערכת. הדבר חשוב במיוחד כאשר מיישמים את RSA בחומרה כמו כרטיס חכם. formula_186 נפוץ ביישומים מעשיים, יתרונו במשקלו הבינארי הנמוך. יש לשים לב שאם המסר עצמו קטן גם הוא, ייתכן שיהיה אפשר פשוט לחשב את השורש ממעלה formula_1 של המסר ללא המודולוס (אם formula_188). משפט קופרשמידט אומר:
כלומר אפשר לחשב כל השורשים של formula_196 מודולו formula_3 הנמוכים מ-formula_198. ככל ש-formula_199 קטן זמן הריצה קטן בהתאם. הרעיון של קופרשמידט מבוסס על LLL (אלגוריתם לצמצום סריגים) וזמן הריצה שלו נשלט בידי הזמן שלוקח ל-LLL לרוץ על סריג בעל מימד formula_200 כאשר formula_201. הוא טוב במקרה שמנסים למצוא שורשים קטנים מודולו מספר פריק ויש לו השלכות גם בתחומים אחרים (במקרה של מספר ראשוני אין צורך בכך כי קיימות שיטות יותר טובות). על כל פנים ההשלכה של משפט זה שניתן לפתח התקפה על RSA כאשר המעריך הציבורי formula_1 קטן, כדלהלן.
אם השולח מצפין מסר formula_203 מספר פעמים עבור formula_204 משתמשים, כל אחד עם המפתחות המתאימים formula_205 שלהם, אם כל formula_206 שווים ל-formula_1 שלם קטן (נניח formula_208), הרי שיריב שמסוגל ליירט את המסרים המוצפנים יכול לחלץ את המסר המקורי על ידי משפט השאריות הסיני ברגע שיצליח להניח ידו על לפחות formula_1 מהם. משום שעבור המסרים formula_210 קיים שלם formula_211 כך ש-formula_212. לפי משפט קופרשימדט formula_4 יהיה השורש ממעלה formula_1 (מעל השלמים) של formula_215. גם אם השולח ייפרד את formula_4 על ידי סכימת ריפוד ידועה כלשהי (אם הריפוד הוא ערך קבוע עבור כל משתמש) ההתקפה עדיין ישימה. לכן הריפוד חייב להיות אקראי כדי לסכל את ההתקפה האמורה.