בעיית RSA
הקשר לפירוק לגורמים

קל לראות שבעיית 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, האם אפשר לבנות באמצעותו אלגוריתם יעיל לפירוק לגורמים, היא שאלה פתוחה. או בניסוח אחר:
בונה ו-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 סיביות לאלו שחוששים במיוחד), מספק רמת ביטחון ראויה לכל צורך מעשי בזמן הקרוב.