הצפנת RSA

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

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

הרעיון דומה לסיפור הבא:
נניח כי ברצוני לשלוח ארגז המכיל מידע מסווג למישהו, ואני קושר את התיבה בשרשאות ומנעול כבד. אני לא מעוניין לשלוח לו את המפתח למנעול, שכן אם המפתח יפול לידיים לא נכונות, תכולת הארגז לא תהיה סודית יותר. אני שולח את הארגז הנעול לדרכו. בצד השני, האדם מקבל ממני את הארגז, ומוסיף מנעול משל עצמו. כעת על הארגז ישנם שני מנעולים. הארגז נשלח חזרה אלי, אל השולח. אני מקבל את הארגז, שעליו שני מנעולים. מן הסתם, אין באפשרותי לפתח את המנעול שהוסיף האדם שאליו שלחתי את הארגז, אולם אני מסוגל להסיר את המנעול שלי, כיוון שלי יש את המפתח. אני מסיר את המנעול, וכעת הארגז נעול במנעול אחד – המנעול של הצד המקבל. אני שולח את הארגז חזרה, ומקבל המשלוח יכול לפתוח את הארגז כיוון שלו יש את המפתח.

מה עשינו כאן? לא שלחנו את המפתחות למנעולים אחד לשני, ובשום שלב בדרך לא היה מצב בו הארגז לא היה נעול.

מאחורי המתמטיקה: האלגוריתם נשען על מספר משפטים מתמטיים, בין השאר על משפט אוילר ועל עקרון של פונקציות חד-כיווניות. משפט אוילר (שאין טען להתחבט בקרביים שלו) קובע פונקציה בין שני מספרים שהקשר היחיד ביניהם הוא ששניהם מתחלקים ב-1. כלומר, שני המספרים זרים זה לזה ואין להם מחלק משותף כלשהו (למשל, 5 ו-7). פונקציות חד כיווניות הן פונקציות שלא ניתן להסיק את המספרים הבסיסיים שהוכנסו לפונקציה, מתוך התשובה ומידע חלקי. למשל, עבור X+5=7 נוכל להסיק בוודאות כי X=2 ולכן זו לא פונקציה חד כיוונית כיוון שהסקנו על מספר שהוזן לפונקציית החיבור מהתשובה (המספר 7) וממידע חלקי (המספר 5). כדי להבטיח בחירה של שני מספרים שאין להם מחלקים משותפים, בוחרים שני מספרים ראשוניים גדולים מאוד.

איך זה עובד בפועל? בוחרים שני מספרים ראשוניים P ו- Q. מהמספרים האלו מייצרים שני מספרים, n ו- e שהם המפתחות הציבוריים. מייצרים נתון נוסף בעזרת e ומסמנים אותו באות d. עכשיו זה יהיה קצת מלוכלך, ונראה לכם איך זה מתבצע מתמטית: נניח ורוצים להצפין את m כלשהו. קודם כל, מקטינים אותו כך שיהיה קטן יותר מ-n בעזרת הנוסחא c = m^e mod n, כלומר נצמצם את m ע"י העלאה בחזקה של e (שחישבנו קודם לכן) ונבצע מודולו n. נקבל c, שהוא הקידוד המוצפן. הפיענוח נעשה ע"י הנוסחא m = c^d mod n. האופי המתמטי של הנוסחאות הוא כזה שלא ניתן לשחזר את m אפילו בהינתן e ו-n, אלא אך ורק באמצעות d. כמובן, ייעילות ההצפנה נעשית לפי גודל המפתחות, ולרוב משתמשים במפתחות בגודל 128 ביט לפחות.

ל-RSA קיימות מספר גרסאות שונות ששיפרו את ההצפנה במהלך 30 השנים האחרונות. כך למשל ניתן למצוא את RAS-CRT, Batch RSA, Multi-power RSA ועוד כמה גרסאות שונות. את RSA ניתן למצוא היום במרבית תחומי אבטחת המידע והוא משמש לחתימות דיגיטליות, הצפנות מייל ומידע כלליות, שרתי SSL וגם בהצפנות WPA תחת אימות המשתמש וההצפנה.