המפצחים:
כוחם של הראשוניים

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

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

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

הפרוטוקול שפיתחו, שנקרא RSA על בסיס ראשי התיבות של שמות המשפחה שלהם, נמצא בשימוש עד היום, אם כי יש כיום פרוטוקולים מהירים יותר שמתאימים טוב יותר להעברת כמויות גדולות של נתונים. בשנת 2002 זכו השלושה בפרס טיורינג, שנחשב לפרס החשוב ביותר בתחום מדעי המחשב, על פיתוח הפרוטוקול. בדיעבד יש מי שטוענים שקדם להם בפיתוח שיטת ההצפנה הזאת המהנדס והקריפטוגרף הבריטי ג'ורג' אליס (Ellis), בעת שעבד בשירות הממשלתי של הממלכה המאוחדת.

שלושה מומחי הצפנה ומדעי המחשב שכללו את עקרונות השיטה. מימין: לאונרד אדלמן, עדי שמיר ורון ריבסט | ויקיפדיה, Ronald L. Rivest, Duncan.Hull, len adlmen

קצת מתמטיקה

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

מושג מתמטי נוסף שעלינו להכיר הוא "זרות": שני מספרים ייחשבו זרים אם אין להם מחלק משותף. כלומר אין שום מספר פרט ל-1 שמחלק את שניהם ללא שארית. למשל המספרים הזרים ל-5 וקטנים ממנו הם 1, 2, 3, ו-4. על בסיס המושג הזה, פונקציית אוילר, המסומנת כ-ϕ(n), היא הפונקציה שמספקת את גודל קבוצת המספרים שקטנים מ-n וזרים לו. למשל ערכה של פונקציית אוילר עבור המספר 5 הוא 4, כי יש ארבעה מספרים טבעיים שזרים לו וקטנים ממנו.

לפונקציית אוילר יש שתי תכונות שימושיות שרלוונטיות עבורנו. הראשונה היא שהערך של פונקציית אוילר עבור מספר ראשוני הוא המספר עצמו פחות 1. למשל ערכה של הפונקציה עבור 19 הוא 18. זה נובע מכך שמספר ראשוני הוא מספר שהמחלקים היחידים שלו הם 1 והוא עצמו. התכונה השנייה היא שהערך של פונקציית אוילר עבור מכפלה של שני מספרים זרים ושונים הוא המכפלה של ערכי הפונקציה עבור שני המספרים בנפרד ובניסוח מתמטי, ϕ(n⋅m)=ϕ(n)⋅ϕ(m). למשל במקום לחשב את ערכה של הפונקציה עבור המספר 15 (3 כפול 5), ניתן לחשב את ערכה עבור 3 ולהכפיל בערכה של הפונקציה עבור 5. מאחר ששניהם מספרים ראשוניים, נשאר להפחית 1 משניהם ולקבל שהערך של פונקציית אוילר עבור 15 הוא 2X4, כלומר 8. 

פונקציית אויילר מספקת את גודל קבוצת המספרים שקטנים מ-n וזרים לו. לאונרד אויילר, מתמטיקאי שוויצרי בין המאה ה-18 | New York Public Library, Science Photo Library

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

הפרוטוקול

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

הפרוטוקול בנוי כך:

דוגמה

חתימה דיגיטלית

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

כשאליס תרצה לשלוח הודעה מוצפנת לבוב היא תשלח פעם אחת את ההודעה תחת המפתח הציבורי של בוב ופעם אחת תחת המפתח הפרטי שלה. כשבוב יקבל את ההודעות הוא יפענח את הראשונה עם המפתח הפרטי שלו ואת השנייה עם המפתח הציבורי של אליס. אם תתקבל אותה הודעה אז הוא ידע שההודעה נשלחה על ידי אליס.

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

חולשות

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