RSA

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

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

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

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