התקפה אחרת של פרנקלין וריטר על RSA עם מעריך formula_1 קטן, מנצלת קשר או יחס בין מסרים. כלומר אם לדוגמה השולח מצפין שני מסרים formula_218 כאשר formula_219 הוא פונקציה ידועה כלשהי מהצורה formula_220 של formula_221. וכן formula_222. ידוע ש-formula_221 הוא שורש של הפולינום formula_224 וכן formula_219 הוא שורש של formula_226. הגורם הליניארי formula_227 מחלק של שני הפולינומים. לאור זאת אפשר להשתמש באלגוריתם אוקלידס כדי לחשב את formula_228. ההשלכה של התקפה זו הפכת חמורה יותר אם סכימת הריפוד אינה בטוחה. אם השולח מרפד את המסר formula_203 לפני המשלוח על ידי הוספת מספר אקראי קצר formula_126 לסוף המסר הרי שאם יעלה בידי התוקף להשיג מסר formula_4 כלשהו שנשלח פעמיים (עם ריפוד שונה, דהיינו formula_232 וכן formula_233 כאשר formula_234 הוא אורך הריפוד בסיביות), הוא יכול לבצע את ההתקפה האמורה ולחלץ את formula_4. כיוון שאם מגדירים את הפולינומים formula_236 וכן formula_237, ידוע שאם formula_238 הרי ש-formula_221 יהיה שורש משותף של שניהם שאותו אפשר למצוא בעזרת אלגוריתם קופרשמידט אם הוא קטן.
ראוי לציין שאם המעריך גדול ההתקפות האמורות אינן יעילות. דרך אחרת לסכל התקפות אילו היא לרפד את המסר בסכימת ריפוד אקראית בטוחה. למרות זאת בגלל ההתקפות המתוארות התקנים הידועים נמנעים באופן כללי משימוש במפתחות הצפנה או פענוח קטנים.
חשיפה חלקית של d כאשר e קטן.
בונה ואחרים הוכיחו שאם עלה בידי התוקף לגלות חלק (למשל רבע) מסיביות המפתח הסודי formula_19 הרי שהוא יכול באמצעותם לגלות את המפתח הסודי כולו בתנאי שמפתח ההצפנה מקיים formula_241. עובדה זו נובעת ממשפט קופרשמידט שהוכיח שאם יעלה בידי התוקף לנחש נכונה כרבע מסיביות אחד הגורמים הראשוניים של המודולוס, ביכולתו לפרק את המודולוס כולו לגורמים בזמן של formula_242 ניסיונות.
בנוסף אפשר לראות שאם המעריך formula_1 קטן מערכת RSA מדליפה כמחצית מהסיביות המשמעותיות של המפתח הפרטי formula_19. הסיבה היא בשל המשוואה formula_245 עבור formula_246. בהינתן formula_85 כאמור התוקף יכול לחשב את formula_248 ואז את
לכן formula_250 הוא קירוב טוב של formula_19. דהיינו ברוב המקרים מחצית הסיביות המשמעותיות של formula_250 זהות לסיביות של formula_19. היות שקיימים רק formula_1 ערכים אפשריים של formula_85 אפשר לבנות טבלה קטנה של formula_1 כניסות כך שאחד מהאלמנטים בה שווה למחצית השמשעותית של סיביות formula_19.
כפליות (Multiplicative).
אם formula_258 הם מסרים כלשהם שהטקסטים המוצפנים המקבילים להם הם formula_259 בהתאמה. אזי מתקיימת הזהות הבאה:
תכונה זו נקראת גם הומומורפיזם והיא מאפשרת במצב מסוים התקפה שבה לתוקף גישה חלקית למערכת ההצפנה (אין לו גישה למפתח ההצפנה) אם formula_261 וברצונו לחשוף את formula_23 ביכולתו להסתירו על ידי הכפלת הטקסט המוצפן ב-formula_263 כלשהו כך: formula_264, אם המערכת תפענח עבורו את formula_265 בלא ידיעת הקשר שבינו לבין formula_23 הוא יקבל את: formula_267. תוצאה זו מאפשרת חילוץ formula_23 בשל הזהות הבאה:
ולכן formula_270. כלומר מסירים את formula_48 על ידי הכפלה בהופכי שלו כדי לקבל את הטקסט מקורי. תכונה זו שימושית גם לטכניקת הסינוור להלן כנגד התקפת ערוץ צדדי. הדרך הטובה ביותר למנוע חולשות עקב תכונת הכיפליות היא לרפד את המסר באמצעות סכימת ריפוד בטוחה.
פריקות עצמית.
לאור תכונת הכפליות, לפונקציית RSA תכונת "פריקות עצמית" (Self-reducibility) או רדוקציה עצמית, כלומר תמיד מתקיים:
כך שאפשר למעשה להמיר טקסט מוצפן נתון formula_273 לטקסט מוצפן אחר formula_274 כאשרformula_275 אקראי. כעת היות שיש סיכוי שהתוצאה תהיה "חלשה" במובן שייתכן שתהיה דרך קלה לפענחה, הרי שהתוקף יכול לנצל עובדה זו כדי לפענח כל טקסט מוצפן. הוכח שאם קיים אלגוריתם formula_276 שיכול לפענח חלקיק קטן formula_277 מסך כל ההצפנות האפשריות, הרי שקיים אלגוריתם אקראי אחר formula_278 שיכול לפענח את כל המסרים המוצפנים באותה סיבוכיות זמן בערך.
מצד אחד תכונת הפריקות העצמית מלמדת שאפשר לצפות מכך שהרוב המכריע של הטקסטים המוצפנים יהיה קשה לפענוח באופן כמעט שווה, תכונה שהועילה בהוכחת ביטחון מספר מערכות הצפנה אסימטרית המבוססות על RSA. אולם מאידך היא נותנת כלים טובים בידי התוקף, היא מאפשרת לגלות טקסט מוצפן אחד מתוך טקסט מוצפן אחר. זו אחת הסיבות מדוע חשוב שמערכת ההצפנה תהיה עמידה כנגד התקפת מוצפן נבחר.
השערת RSA החזקה.
באריץ' ופיצמן ואחרים המציאו ב-1997 את השערת RSA החזקה (Strong RSA Assumption) שמאז מהווה בסיס למספר מערכות הצפנה וחתימה דיגיטלית בין היתר חתימה דיגיטלית של קריימר ושופ. השערה זו שונה מההשערה הרגילה בכך שהתוקף יכול לבחור גם את המפתח הציבורי, כדלהלן:
כלומר היריב מקבל מודולוס וטקסט מוצפן ועליו למצוא כל מעריך ובסיס כך שהמשוואה האמורה תתקיים. ייתכן שמשימה זו תהיה קלה יותר מפתרון בעיית RSA הרגילה ולכן ההשערה נקראת חזקה במובן הזה, שאם היא קשה, הרי שהיא משיגה ביטחון גבוה יותר מ-RSA הרגיל.
סיבית קשה ב-RSA.
אף על פי ש-RSA בטוח בהנחה שהשערת RSA נכונה ובהנחה שפירוק לגורמים היא משימה קשה. בכל זאת בתנאים מסוימים RSA מדליף מעט מידע על הטקסט המקורי, כלומר קל לנחש סיביות מסוימות של המסר המקורי מתוך הטקסט המוצפן. גולדווסר ומיקאלי הראו שאם היריב יכול לנחש את הסיבית הכי פחות משמעותית של הטקסט המקורי, הוא יכול עם מידע זה לבצע התקפה שבה יצליח יחלץ את כל סיביות המקור בזמן פולינומי. ואזירני וכן שור, גולדרייך, אלקסי פישלין, שנור ואחרים הוכיחו ש-formula_284 הסיביות הפחות משמעותיות של הטקסט המוצפן של הצפנת RSA בטוחות, דהיינו ההסתברות לניחוש מוצלח שלהן הוא לא יותר מאשר formula_285 כאשר formula_286.
הוסטד ונוסלנד הוכיחו שכל סיביות הטקסט המקורי "מוסתרות היטב" בהצפנת RSA במובן שאם יהיה בידי תוקף יתרון כלשהו לגלות חלק מהן הרי שהוא יצליח לחשוף את כולן באותה מידה. ההוכחות מתבססות על רדוקציה המוכיחה שאם קיים אלגוריתם יעיל לניחוש סיבית אחת או יותר אפשר לבנות ממנו אלגוריתם לניחוש כל הסיביות ומכאן להיפוך פונקציית RSA.
תכונה זו היא חרב פיפיות, מצד אחד מבטיחה כי כל הסיביות מוגנות במידה שווה, אולם מצד שני מעניקה לתוקף כלי רב עוצמה, אם יעלה בידו לנחש סיבית אחת הוא יכול לגלות את כולן. מסיבה זו יישום RSA דורש תשומת לב רבה וזהירות שלא ייוצר מצב שחלק מהמערכת ידליף שלא במודע רסיס כלשהו שיאפשר לתוקף לשבור את המערכת כולה.
התקפת מוצפן נבחר.
התקפת מוצפן נבחר על RSA מוגדרת כדלהלן: לתוקף גישה לאורקל אשר מבצע עבורו עם מפתח הצפנה זהה, formula_85 פענוחים של formula_85 טקסטים מוצפנים formula_289 (לא בהכרח קשורים זה בזה) ומתוך מידע זה עליו לגלות formula_23 אחר שאינו נמנה כמובן עליהם. ההתקפה מתחלקת לשני סוגים CCA1 ו-CCA2 כאשר השנייה מאפשרת שיהיה קשר בין formula_23 שאותו התוקף מעוניין לגלות לבין הפענוחים שקיבל, במילים אחרות הוא יכול לבחור את הפענוחים שברצונו לקבל לפי formula_23 בהתאם לתוצאות קודמות כלשהן.
היות שפונקציית RSA דטרמיניסטית באופיה לא ניתן לסכל התקפה זו. הדרך היחידה לסכלה היא לעשות שימוש בסכימת ריפוד אקראית על המסר לפני ההצפנה כמו OAEP. בצורה זו מבטלים את דטרמיניסטיות ההצפנה וההתקפה נעשית חסרת תועלת.
התקפת תיזמון.
RSA הבסיסי פגיע להתקפת ערוץ צדדי המודדת במדויק את הזמן הדרוש לביצוע פענוח. למשל בהינתן כרטיס חכם שבו מוטמע מפתח הצפנה סודי שכמובן לא ניתן לראות באמצעים רגילים. בגלל שהמספרים העצומים לא מאפשרים חישוב ישיר של העלאה בחזקה פעולת הפענוח מנצלת את "אלגוריתם ריבוע וכפל" כדי לחשב את formula_23 בחזקת formula_19 ברקורסיה של העלאות בריבוע. העיקרון הוא להקצות משתנה זמני שמתחיל ב-1, סורקים את הייצוג הבינארי של המעריך מימין לשמאל (מהסיבית הכי פחות משמעותית לסיבית העליונה). אם הסיבית היא "1" מכפילים את המשתנה הזמני ב-formula_23 ומעלים בריבוע ואילו אם הסיבית היא "0" מבצעים רק העלאה בריבוע, מצמצמים את התוצאה במודולוס וממשיכים כאשר התוצאה האחרונה היא במשתנה הזמני. היות ש-formula_19 אי זוגי, אנחנו יודעים שבסבב הראשון מתבצעת העלאה בריבוע וכפל מלא ב-formula_23 אם מודדים את הזמן הדרוש לפעולה זו ומשווים עם הפעולה של האלגוריתם בסבב הבא ונמצא הבדל אפילו כלשהו אפשר להעריך שהסיבית השנייה היא "0". בדרך זו ניתן לעלות על כל הסיביות. באותה מידה אפשר לבצע את ההתקפה על ידי מדידת הפרשי צריכת החשמל בזמן ביצוע פעולות ההעלאה בריבוע וכפל.
דרך אחת לסכל התקפה זו היא באמצעות טכניקת "סינוור" (blinding) המנצלת את תכונת ההומומורפיות של RSA. לפני הפענוח מכפילים את המסר במספר אקראי כלשהו ולאחר הפענוח מחלקים בו שוב. בדרך זו מדידת התזמון אינה מועילה לתוקף כי המסר אקראי.
מחשב קוונטי ובעיית RSA.
היות שביטחון הצפנת RSA מבוסס בעיקר על פירוק לגורמים - בידיעת הגורמים הראשוניים של המודולוס השיטה הופכת ללא בטוחה כלל, יש חשיבות בהקשר זה להתקדמות הטכנולוגית בכל המישורים בתחום פירוק לגורמים. מסיבה זו עם המצאת אלגוריתם שור והדיון על מחשבים קוונטיים, הנושא נעשה רגיש. כאשר מחשב קוונטי פונקציונלי יהפוך למעשי רוב האלגוריתמים האסימטריים ביניהם RSA יצאו מכלל שימוש.