אליס ובוב: ידועים בציבור

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

מה עושים?

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

מה הבעיה? שבמשך זמן מה, לא הייתה ידועה שום שיטה למימוש של “מנעול” שכזה.

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

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

הרעיון הבסיסי ב-RSA אינו מסובך כל כך. לב העניין הוא חשבון מודולורי, שמבוצע מודולו מספר גדול n (“גדול” פירושו בן מאות ספרות) שהוא מכפלה של שני ראשוניים גדולים (ולכן קשה לפרק אותו לגורמים - רק שני גורמים זה המינימום ההכרחי). העניין הוא בכך שלא קשה להעלות מספר בחזקה טבעית כלשהי e מודולו n הזה, אבל קשה מאוד להוציא שורש מסדר כלשהו מודולו ה-n הזה אם לא ידוע מידע נוסף עליו. המידע הנוסף הזה יכול להיות, למשל, הפירוק שלו - אבל מה שבאמת מעניין הוא מהי פונקצית אוילר שלו (שאותה קל לחשב בהינתן הפירוק, וקל לפרק אם יודעים אותה). אם המידע הזה ידוע, בעיית הוצאת השורש הופכת לטריוויאלית: מתברר שכדי להוציא שורש e-י של מספר מודולו n, לפעמים מספיק להעלות את המספר בחזקה אחרת, d, וההעלאה בחזקה הזו זהה להוצאת שורש. זה לא תמיד אפשרי - בוחרים את e מראש כך שעבורה זה יהיה אפשרי. דוגמה: עבור n=35, זוג אפשרי אחד הוא e=5, d=17 - נסו ותהנו. אם כן, ה”מנעול” הוא פשוט העלאה של ההודעה הסודית שרוצים להצפין (וחושבים עליה כמספר) בחזקת e, והמפתח למנעול הזה הוא ההעלאה של המספר המוצפן בחזקת d.

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

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

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

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

התשובה לכך כפולה. ראשית, הצפנת מפתח פומבי היא איטית הרבה יותר מהצפנה סימטרית. זה לא הופך אותה לבלתי מעשית, כמובן; אבל זה הופך אותה להרבה פחות רצויה. לכן, הפתרון הוא אלגנטי ופשוט: כדי להתחיל תקשורת בין שני צדדים, הם משתמשים בהצפנה פומבית כדי להעביר בצורה בטוחה מפתח מצד אחד לשני. אחרי כן, שני הצדדים משתמשים במפתח המשותף הזה להצפנה סימטרית (מהירה פי כמה). זה גם מה שמשיגות שיטות לשיתוף מפתח, כמו דיפי-הלמן. זה גם מסביר מדוע עוסקים כל הזמן בפיתוח צפנים סימטריים חדשים דוגמת AES, ולא משתמשים פשוט בפנקס חד פעמי (שהוא, כזכור, הצפנה מושלמת) - בפנקס חד פעמי, אורך המפתח הוא כאורך ההודעה שמעבירים, ולכן אין טעם להעביר את המפתח בעזרת ההצפנה הציבורית - אפשר פשוט להעביר את ההודעה (טוב, זה לא נכון לגמרי - אפשר לשדר מפתח ארוך לפנקס חד פעמי בזמן שישנים בלילה ואין הודעות להעביר, למשל, אבל הבעיה העקרונית ברורה). חשוב להבהיר שמפתחות של הצפנות פומביות ולא פומביות הם קטנים. קטנים מאוד. אפשר לראות איך מפתח שכזה נראה אם בודקים את ה-Certificates של הדפדפן שלכם (בפיירפוקס: Edit/Preferences/Advanced/Encryption/View Certificates ואז לבחור אחד אקראי ולחפש בו Subject’s Public Key). זכרו שזה מפתח ציבורי, כלומר של הצפנה שאינה סימטרית; מפתחות של הצפנה סימטרית קטנים בהרבה. עם מפתחות קטנים כאלו קל לעבוד, בניגוד לפנקס חד פעמי.

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

זו אחת מהדוגמאות המעצבנות שבהן “העולם האמיתי” מתעקש לקחת רעיון קריפטוגרפי יפה ולזהם אותו. מה לעשות, שבעולם האינטרנט שבו כל בקשת תקשורת עוברת דרך המוני גורמים שונים ומשונים, התקפות כאלו (שמכונות “Man-in-the-middle-attack”) הן פשוטות למדי לביצוע וחייבים להתייחס אליהן.

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

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