RSA

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

היסטוריה

החיסרון העיקרי בצפנים סימטריים הוא שהמפתח הסודי נדרש הן להצפנה והן לפענוח ולכן יש צורך להעבירו לידי השולח בדרך כלשהי ובכך לסכנו בחשיפה. ב־1976 פרסמו ויטפילד דיפי ומרטין הלמן מאמר המתאר את התפיסה של ההצפנה האסימטרית, שבה הנמען מפרסם מפתח הצפנה פומבי בעזרתו מבוצעת הצפנת מסרים הנשלחים אליו, ואילו הפענוח מתבצע אך ורק באמצעות המפתח הפרטי שברשותו, שמעולם לא נחשף. כשנה לאחר מכן ב־1977, רונלד ריבסט, עדי שמיר ולאונרד אדלמן מ־MIT פרסמו לראשונה במגזין סיינטיפיק אמריקן את RSA (שמו נגזר מראשי תיבות שמותיהם), שיישם לראשונה את המודל של דיפי והלמן באופן מעשי. אלגוריתם RSA זיכה את ממציאיו בפרס טיורינג לשנת 2002.

זכויות יוצרים

RSA נרשם כפטנט בארצות הברית בשנת 1983 ותוקפו פג בספטמבר 2000. בדצמבר 1997 פרסם מטה התקשורת של המודיעין הבריטי GCHQ מסמך בו נטען כי רעיון המפתח הפומבי היה ידוע להם כעשור לפני שהתפרסם. הם גילו לטענתם גם את RSA וגם את דיפי־הלמן, אך שמרו את הדבר בסוד. גם ה־NSA טען שגילה את RSA הרבה לפני שנודע לציבור, אולם התגלית סווגה כסוד לאומי. המתמטיקאי הבריטי קליפורד קוקס שעבד בסוכנות הביון הבריטית, פרסם מסמך בו נטען כי ב־1973 המציא אלגוריתם הצפנה דומה ל־RSA. ייתכן שבקהיליית המודיעין המצאות אלו היו ידועות שנים רבות לפני שהציבור התוודע להן. בכל מקרה ספק אם לממצאים אלו הייתה תועלת מעשית כלשהי באותה עת.

הצפנה ופענוח

אליס משדרת לבוב את מפתחות ההצפנה () ושומרת בסוד את המפתח . אם בוב מעוניין לשלוח את המסר  לאליס תחילה עליו להפוך את  לערך מספרי הנמוך מ־ בדרך מוסכמת כלשהי.