כולם יכולים לצותת לקו
כשהטלפון שלכם מדבר עם הבנק, ההודעה עוברת דרך קישורי רדיו, כבלים ונתבים שבבעלות אנשים אחרים. כל אחד מהם יכול לשמור עותק. קריפטוגרפים מתארים את המצב כשני אנשים, אליס ובוב, בשני הקצוות של ערוץ פתוח, ומצותתת, איב, באמצע, שרואה כל מה שנשלח בו.
בסצנה הערוץ הוא צינור זכוכית. כל קפסולה שעוברת ליד שרוול הפליז שבאמצע מועתקת דרך צינור ההאזנה של איב אל המגש שלה. היא לא יכולה לעצור את הקפסולות או לשנות אותן; היא יכולה רק לקרוא מה שבתוכן.
מנעול ששני הקצוות חולקים
התשובה הוותיקה ביותר היא מפתח סודי משותף. אליס מערבלת בעזרתו את ההודעה שלה, ורק מי שמחזיק באותו מפתח יכול לפענח אותה. זו הצפנה סימטרית, וכך מוגנים היום כמעט כל הנתונים, בצפנים כמו AES.
מה שאיב מעתיקה הוא שורה של בתים שנראית כמו רעש. ההתקפה הכללית היחידה שלה היא לנסות כל מפתח אפשרי עד שההודעה נעשית הגיונית. למפתח של n סיביות יש 2ⁿ ערכים אפשריים, ולכן כל סיבית נוספת מכפילה את העבודה שלה. למפתח בן 8 סיביות יש 256 ערכים, ומכונה שמנסה טריליון מפתחות בשנייה עוברת על כולם ברבע ננו־שנייה. תקן הצפנת המידע (DES), שאומץ בארצות הברית ב־1977, השתמש ב־56 סיביות. ב־1998 מכונה שנבנתה במיוחד לשם כך מצאה מפתח DES בפחות משלושה ימים. למפתח בן 128 סיביות יש כ־3.4 × 10³⁸ ערכים: באותו קצב של טריליון בשנייה, ניסיון של כולם לוקח כ־10¹⁹ שנים, כמעט פי מיליארד מגיל היקום.
נסו: לחצו על צעצוע תחת אורך המפתח וקראו את החלק התחתון של הלוח של איב, ואז לחצו על DES, 1977 ועל היום. צפו בחלק הוורוד של קוביית הזכוכית שלה, החלק מכל המפתחות שהיא יכולה לנסות במשך חיים שלמים, מתכווץ עד שהוא נעלם.
בממוצע איב מוצאת את המפתח באמצע הדרך, וזה חוסך לה רק סיבית אחת. כרטיס הפליז המנוקב בכל קצה הוא המפתח עצמו: חור אחד לכל 1 בייצוג הבינארי שלו, כך שמפתח ארוך יותר פירושו יותר חורים.
ערבוב צבעים בפומבי
מפתח משותף מעורר שאלה קשה יותר. אליס ובוב צריכים להסכים עליו קודם, והדרך היחידה שלהם לדבר עוברת בצינור של איב. ב־1976 פרסמו ויטפילד דיפי ומרטין הלמן דרך לעשות את זה בפומבי. קריפטוגרפים במטה התקשורת הממשלתית של בריטניה (GCHQ) מצאו את אותו רעיון כמה שנים קודם, אבל הוא נשמר בסוד עד שנות ה־90.
את הרעיון מסבירים לעיתים קרובות בעזרת צבע. כולם, כולל איב, מכירים צבע ציבורי: צהוב. אליס בוחרת צבע סודי, אדום, ובוב צבע סודי כחול. כל אחד מהם מערבב את הצבע הציבורי עם הסוד שלו ושולח את התערובת: אליס שולחת כתום, ובוב ירוק. אחר כך כל אחד מוסיף את הסוד שלו לתערובת שקיבל. בצנצנת של אליס יש צהוב, כחול ואדום; בצנצנת של בוב יש צהוב, אדום וכחול. חלקים שווים מאותם שלושה צבעים יוצרים אותו גוון, ולכן שניהם מסיימים עם אותו חום בדיוק.
לאיב יש את הצהוב, את הכתום ואת הירוק. לשפוך את שתי התערובות יחד לא עוזר, כי בצנצנת כזאת יש שני חלקים של צהוב, והיא יוצאת צהובה מדי. כדי להגיע לצבע הסודי היא הייתה צריכה להוציא את האדום בחזרה מהכתום, וצבע שעורבב אי אפשר להפריד.
המתמטיקה שמתחת
הצבע הוא רק משל. בהחלפה האמיתית, במקום ערבוב יש חישוב שקל לעשות בכיוון אחד, ועד כמה שידוע, קשה מאוד להפוך. אליס ובוב מסכימים בפומבי על מספר ראשוני p ועל מספר g. אליס בוחרת מספר סודי a ושולחת A = gᵃ mod p; בוב בוחר מספר סודי b ושולח B = gᵇ mod p. “mod p” (מודולו p) פירושו לשמור רק את השארית אחרי חלוקה ב־p, כמו לקרוא שעון עם p מקומות: החוגה בסצנה מראה איפה כל מספר נוחת.
אחר כך אליס מחשבת Bᵃ mod p ובוב מחשב Aᵇ mod p. שניהם שווים ל־gᵃᵇ mod p, אותו מספר s, שהופך למפתח המשותף שלהם. איב רואה את g, p, A ו־B. כדי למצוא את s היא צריכה את a או את b, ופירוש הדבר לפתור את gˣ mod p = A ולמצוא את x: זו בעיית הלוגריתם הבדיד. העלאה בחזקה לוקחת למחשב חלק זעיר של שנייה, גם עבור מספרים בני מאות ספרות. להפוך אותה אין שום דרך מהירה ידועה, ולכן כשהראשוני גדול, לאיב לא נשאר אלא משהו כמו לנסות מעריכים אחד אחרי השני.
בגודל צעצוע הסצנה משתמשת ב־p = 227, מספר קטן מספיק כדי לבדוק אותו ביד. בכל גודל יש ראשוני בטוח קצת מתחת ל־2ⁿ (ראשוני שבו גם (p − 1)/2 ראשוני), ו־g שהחזקות שלו מגיעות לכל מקום על החוגה חוץ מאפס. המספרים על הלוחות ועל האריחים הם התוצאות האמיתיות; מספרים ארוכים מקוצרים לספרות הראשונות והאחרונות שלהם.
נסו: הזיזו את פתיחה צעד אחר צעד אל המתמטיקה, לחצו על צעצוע ובדקו שהמפתחות של אליס ובוב זהים. אחר כך לחצו על 256 סיביות וצפו במספרים גדלים עד 78 ספרות, בזמן שהחוגה מתמלאת במקומות צפופים מכדי לצייר אותם.
כמה גדול זה גדול מספיק
כוח גס הוא הרצפה של התקפה, לא התקרה שלה. בצופן סימטרי כמו AES לא ידועה שום התקפה טובה בהרבה מניסיון מפתחות, ולכן 128 סיביות מספיקות בהחלט. לוגריתמים בדידים הם סיפור אחר: אלגוריתמים מתוחכמים פותרים אותם מהר בהרבה מניסיון של כל מעריך, ולכן לראשוני בהחלפה אמיתית יש 2,048 סיביות או יותר, כדי לתת ביטחון דומה לזה של מפתח בן 128 סיביות. מערכות מודרניות משתמשות בעיקר באותו רעיון על עקום אליפטי, שבו לא ידוע קיצור דרך כזה, ומספרים של כ־256 סיביות מספיקים.
מחשב קוונטי גדול שמריץ את אלגוריתם שור יוכל לפתור לוגריתמים בדידים במהירות, ולכן שיטות חדשות לשיתוף מפתח, שנשענות על בעיות קשות אחרות, מוטמעות עכשיו לצד השיטות הישנות.
מה המודל הזה משאיר בחוץ
כאן איב רק מאזינה. מצותת שיכול גם לשנות קפסולות יכול לנהל החלפה אחת עם אליס ואחרת עם בוב, ולקרוא את כל מה שעובר ביניהם. פרוטוקולים אמיתיים כמו TLS עוצרים את התקפת אדם בתווך הזאת: כל צד חותם על החלק שלו בהחלפה, והחתימה נבדקת מול תעודות דיגיטליות.
הערבול בסצנה הוא צופן זרם צעצוע, לא AES, וקצב הניחוש של טריליון מפתחות בשנייה הוא הנחה; מכונה גדולה מאוד יכולה להיות מהירה פי מיליון, וזה משנה את הזמן למפתח בן 128 סיביות מכ־10¹⁹ שנים לכ־10¹³. אפילו הראשוני של 256 סיביות קטן בהרבה מהראשוניים בני 2,048 סיביות שמשמשים בהחלפות אמיתיות: החשבון בסצנה מדויק, אבל החלפה מעל הראשוני בן 128 הסיביות של היום הייתה נופלת בפני אלגוריתמים ללוגריתם הבדיד הרבה לפני שהספירה של איב בכוח גס הייתה מסתיימת. תוקפים אמיתיים גם מחפשים טעויות במקום לעשות את המתמטיקה: מפתחות גנובים, מספרים אקראיים גרועים ודליפות דרך זמני ריצה או צריכת חשמל שוברים יותר מערכות מאשר כוח גס.