המפצחים:
פרוטוקול שיתוף מפתח

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

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

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

התפתחות רשתות המחשבים, לימים האינטרנט, חייבה יצירת שיטות לאבטחת נתונים. אבטחת מידע ברשת מחשבים | מקור: tadamichi, Shutterstock

בעיית הפצת המפתחות

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

1. אליס רוצה להעביר מכתב חסוי לבוב. היא מניחה את המכתב בארגז, נועלת אותו במנעול ששייך לה ושולחת לבוב את הארגז הנעול.

2. אחרי שקיבל את הארגז, בוב נועל אותו במנעול משלו ושולח אותו בחזרה לאליס.

3. כשאליס מקבלת את הארגז, היא מסירה את המנעול שלה ושולחת לבוב את הארגז פעם נוספת.

4. כעת בוב יכול לפתוח את הארגז ולקרוא את המכתב ללא קושי, שכן רק המנעול שלו נשאר.

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

מומחי ההצפנה מצאו דרך להצפין מידע כך שניתן להעבירו בערוץ פתוח. ויטפילד דיפי, מרטין הלמן, רלף מרקל (מימין לשמאל) ב-1977 | מקור: Chuck Painter, Stanford News Service

פונקציות חד-כיווניות 

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

דיפי והלמן נברו בעוד ועוד פונקציות חד-כיווניות אפשריות, עד שמצאו מועמדת הולמת: פונקציה שמבצעת כמה פעולות שאחת מהן היא פעולת המודולו, המוגדרת כך: 

(a)mod(b)=c

המספר c הוא שארית החלוקה של a ב-b. למשל, נוכל לשאול מהי השארית של 5 בחלוקה ב-2. מתמטית השאלה ותשובתה מנוסחות כך:

5mod2=1

הלמן מצא שיטה שבה אליס ובוב יוכלו להסכים על מפתח בלי לחשוף אותו. השיטה של הלמן משתמשת בפונקציה f(x)=Y^xmodp ומסתמכת על בעיית דיפי-הלמן, שלא נתעמק בה כאן.

*בבחירת המספרים הראשוניים Y, p יש לעמוד בכמה תנאים שלא נפרט כאן.

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

אתגר :