יש לזכור שכל הפעולות מבוצעות מודולו formula_56.
מכיוון שהפרמטרים ביישום מעשי בדרך כלל גדולים, חישוב חזקות בסדר גודל כזה נעשה בשיטות לחישובים מודולריים מרובי ספרות (ראו חשבון מודולרי).
השיטה הבסיסית המתוארת כאן אינה בטוחה לשימוש לפי מודל ביטחון מחמיר שנקרא עמידות נגד התקפת מוצפן-נבחר לכן במרבית המקרים אין להשתמש בה כך. תחת זאת, התקן מפרט שיטות להכנה בטוחה של המסר להצפנה באופן כזה שההצפנה תהיה בטוחה ולא תדליף מידע שלא במתכוון (ראו ריפוד). בנוסף, כדי למנוע התקפה אקטיבית על המערכת מצד גורם זדוני שיכול לשנות מסרים בדרכם, רצוי להבטיח את שלמות המפתחות ושייכותם לבעליהם. מקובל לרשום את המפתח הציבורי אצל צד שלישי מהימן כמו רשות אישורים (ראו מפתח פומבי).
בסיס מתמטי.
ביטחון שיטת RSA מתבסס על בעיית RSA כדלקמן; נתון שלם חיובי formula_104, מכפלת שני ראשוניים שונים שווים בגודלם בקירוב, נתון שלם חיובי formula_1 הנמוך מ־formula_104 המקיים formula_107 (פירושו ש־formula_1 זר ל־formula_109) ונתון שלם formula_76 כלשהו. מצא את formula_73 המקיים את המשוואה: formula_112. במילים אחרות הבעיה היא מציאת שורש ממעלה formula_1 של formula_76 (מודולו formula_104).
הרעיון מאחורי אלגוריתם הפענוח של RSA מבוסס על משפט אוילר הקובע: עבור כל formula_116 ו־formula_2 טבעיים הזרים זה לזה (שאין להם מחלק משותף מלבד 1) מתקיים:
formula_118. הפונקציה formula_119 נקראת פונקציית אוילר ומייצגת את מספר הטבעיים הזרים ל־formula_2 וקטנים ממנו. אם מכפילים את שני אגפי השקילות האמורה ב־formula_121 מתקבל: formula_122.
הוכחת נכונות.
לפי האלגוריתם מפתח הפענוח formula_20 מקיים את השקילות formula_124,
כלומר formula_125 הוא כפולה כלשהי של formula_17 שהוא בעצם formula_109, בניסוח אחר קיים שלם formula_128 המקיים formula_129 לכן formula_130 הוא פתרון של המשוואה formula_131 כי עבור כל שלם formula_76 הנמוך מ־formula_104 מתקיים:
והפתרון הוא יחיד כיוון שאם קיים פתרון אחר נניח formula_134 שגם הוא פתרון של formula_135 אז:
דוגמה במספרים קטנים.
נניח שאליס בוחרת את הראשוניים
formula_136 ומחשבת את: formula_137
ואת פונקציית אוילר: formula_138
וכן בוחרת את formula_139, שימו לב שמתקיים formula_140 כנדרש.
בעזרת אלגוריתם אוקלידס המורחב מתקבל
formula_141
לכן formula_142 יהיה מפתח הפענוח המתאים. אליס שולחת את
formula_143 ואת formula_144 לבוב ושומרת בסוד את formula_145.
אם בוב מעוניין להצפין את המסר formula_146 עבור אליס הוא מחשב את:
כשאליס מקבלת את formula_32 היא משחזרת את formula_33 בעזרת המפתח הסודי:
בגרסת CRT מחשבים תחילה את מפתחות הפענוח formula_152 כי מתקיים formula_153 באופן דומה מוצאים את formula_154.
ואז לפענוח מחשבים את formula_155 וכן formula_156
מחשבים את ההופכי הכפלי של formula_42 מודולו formula_41 שהוא formula_159 ואז formula_160. שימו לב שהיות ש־formula_161 הוא מספר שלילי לכן לפי הכלל בחשבון מודולרי (מודולו formula_41 במקרה זה) הוא שקול למעשה ל־formula_163.
מה שנותר הוא לחשב את formula_164.
הדוגמה היא להמחשה בלבד, בפועל חובה על הראשוניים formula_13 ו־formula_14 להיות הרבה יותר גדולים מהדוגמה המובאת כאן. זאת כדי למנוע ניסיון לתקוף את האלגוריתם על ידי פירוק formula_2 לגורמים באמצעות אלגוריתם פירוק לגורמים ידוע (ראו פירוק לגורמים) ואז לחשב את מפתח הפענוח formula_6 באותה דרך שבה מחשב אותו המקבל.
חתימה דיגיטלית.
אלגוריתם RSA יכול לשמש גם כחתימה דיגיטלית. כיוון שפונקציית ההצפנה היא התאמה על המפתחות יכולים להחליף תפקידים והחתימה מתבצעת על ידי היפוך סדר ההצפנה והפענוח לעיל. כדי לחתום על המסר אליס מצפינה אותו באמצעות המפתח הסודי שלה ושולחת את התוצאה לבוב, כדי לאמת את החתימה בוב מפענח את המסר באמצעות המפתח הפומבי (של אליס). אולם אין לחתום על מסמך בשיטת RSA בצורה ישירה אלא יש צורך תחילה לקודד את המסר באמצעות פונקציית יתירות כלשהי או פונקציית גיבוב לפני החתימה ואת החתימה לבצע על תוצאת הפונקציה במקום על המסר עצמו כדלהלן:
אם אליס מעוניינת לשלוח את המסר formula_73 כשהוא חתום על ידה לבוב, היא מבצעת:
כאשר formula_172 היא פונקציית היתירות האמורה והחתימה היא formula_173. שימו לב אף על פי שהמטרה בחתימה הדיגיטלית אינה סודיות, כיוון שאליס בעצם הצפינה את המסר היא לא צריכה לשלוח אותו כיוון שבוב מסוגל לשחזרו מתוך החתימה. על כן השיטה המתוארת אפשרית רק כשהמסר קצר (קטן מהמודולוס), כדי לחתום על מסר גדול יותר, נוקטים בשיטה אחרת, תחילה משתמשים בפונקציית גיבוב על המסר ואת החתימה מבצעים על תוצאת פונקציית הגיבוב במקום על המסר עצמו. במקרה זה אליס תצטרך לשלוח גם את המסר עצמו בנפרד.
לאימות החתימה, בוב מחשב את:
בוב משיג עותק אותנטי של מפתח האימות של אליס (המקביל למפתח ההצפנה formula_34) באמצעותו מפענח את formula_177 ובהפעלת הפונקציה ההופכית formula_178 משחזר את המסר המקורי. בוב יכול להיות משוכנע כי רק אליס שהיא בעלת המפתח הפרטי המתאים, יכולה הייתה להיות המקור למסר ובמיוחד שלא שונה על ידי גורם כלשהו במהלך המשלוח.
פונקציית היתירות הכרחית כיוון שללא השימוש בה יהיה קל למצוא מסר אחר שעבורו החתימה של אליס תהיה תקפה ללא ידיעת המפתח הפרטי שלה. זאת בשל הכיפליות של RSA. כדי לראות מדוע נניח כי formula_179 (פונקציית הזהות), אם אליס חתמה על שני מסמכים שונים formula_180 ו־formula_181 אזי כפולה של החתימות: formula_182 ו־formula_183 על המסרים הנ"ל תהיה חתימה תקפה עבור המסר formula_184. פונקציית היתירות מבטלת את האסוציאטיביות של החתימות ועל כן מונעת בעיה זו.
גרסאות מתקדמות.
החסרון העיקרי בגרסה הבסיסית הוא בגודל מפתח הפענוח שחייב להיות מטעמי ביטחון קרוב לגודלו של formula_2. היות שאלגוריתם RSA מערב העלאה בחזקה מודולרית, זמן ההצפנה והפענוח תלויים ישירות במספר סיביות המפתחות. מאז המצאת RSA נעשו מספר ניסיונות לצימצום גודל המפתחות ולשפר בכך את יעילות האלגוריתם. הדרך הפופולרית ביותר היא ניצול משפט השאריות הסיני (CRT). הרעיון הוא לפצל את מפתח הפענוח למספר מפתחות קטנים, חישוב העלאה בחזקה עם כל אחד מהם בנפרד ואז שילוב התוצאות בעזרת אלגוריתם CRT מתוך מערכת השקילויות שנוצרת. חישוב CRT זניח יחסית לפעולת העלאה בחזקה מודולרית, על כן שיטה זו משפרת משמעותית את תהליך הפענוח. משפט השאריות הסיני מאפשר פענוח מהיר יותר במיוחד בפלטפורמה מרובת מעבדים, בה ניתן לחשב העלאה בחזקה מודולרית באופן מקבילי.
סוגיית ביטחון גרסאות אילו היא שאלה פתוחה. לא ברור לגמרי האם טכניקות אילו מחלישות או מחזקות את ביטחון אלגוריתם RSA. אם כי לא ידוע על דרכים יעילות לשבירת האלגוריתם בשל שינויים אילו. ראו המאמר של דן בונה וחובב שחם Fast Variants of RSA שפורסם במגזין Cryptobytes של RSA, קיץ 2002.
ריפוד.
הצפנת RSA מכונה דטרמיניסטית משום שהאלגוריתם אינו מערב שימוש במספרים אקראיים בניגוד לשיטות הצפנה הסתברותיות (כמו אל־גמאל). משמעות הדבר היא שבהצפנת אותו מסר פעמים נוספות (עם מפתח הצפנה זהה) תתקבל תמיד תוצאה זהה. הצפנה דטרמיניסטית פגיעה מעצם טבעה להתקפת מוצפן־נבחר, בה מניחים שהתוקף מסוגל לבחור טקסטים אותם הוא מעוניין להצפין ולנתח את תוצאת הצפנתם, אך אין לו גישה למפתח הפענוח עצמו. כתוצאה מכך, ייתכן מצב שהתוקף יוכל לנחש או לחשוף מידע חלקי או מלא אודות הצופן. כמו כן ישנם מקרי קצה שבהם המסר המיועד להצפנה עלול להוות נקודת תורפה כגון אם הוא קטן מאוד או בעל מבנה ייחודי. במקרה כזה הטקסט נקרא "חלש" כי הוא מסכן את ביטחון ההצפנה. למשל:
כדי להימנע ממסר חלש וכדי לסכל התקפת טקסט מוצפן נבחר שמנצלת חולשה זו, מקובל לרפד את המסר באמצעות אלגוריתם ריפוד מוסכם לפני ההצפנה. שיטת הריפוד עצמה לא חייבת להיות סודית. אפשר לשרשר מחרוזת אקראית למסר לפני ההצפנה כך שמבנהו המקורי מיטשטש ובזמן הפענוח פשוט מסירים את המחרוזת האקראית. תקן PKCS #1 יישם שיטת ריפוד פשוטה כזו. לפני ההצפנה המסר רופד באפסים ובמספר אקראי באורך מוגדר כלשהו. ב־1998 הראה דניאל בלייכבכר ממעבדות בל ששיטת ריפוד כזו אינה בטוחה כלל ואפשר לפרוץ אותה בקלות. ב־1995 ניסחו מיהיר בלייר ופיליפ רוגווי את רעיון מודל אורקל אקראי והראו שבאמצעותו אפשר ליישם כל שיטת הצפנה אסימטרית (דטרמיניסטית) באופן שתהיה בעלת ביטחון סמנטי. על בסיס רעיון זה פותח אלגוריתם OAEP המשתמש במחולל מספרים אקראיים בטוח ופונקציית גיבוב קריפטוגרפית בשילוב עם RSA להצפנה בטוחה. ב־1998 תקן הצפנת מפתח־פומבי PKCS #1 תוקן ואלגוריתם OAEP שולב בתקן כשיטת הריפוד התקנית להצפנת מפתח פומבי הנקראת RSA-OAEP (ראו תרשים).
אלגוריתמים.