RSA

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

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

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

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

היסטוריה

עדי שמיר בכנס בנושא המאגר הביומטרי, אפריל 2012

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

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

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