הבעיה אינה ההצפנה. היא המפתח

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

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

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

השאלה הזו נראתה חסרת פתרון עד 1976. איך שני זרים מסכימים על סוד, כשכל מילה שהם אומרים נשמעת.

הפתרון, בצבעים

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

הם מתחילים מצבע אחד שכולם רואים, נניח צהוב. לאליס יש צבע סודי שהיא לא מגלה לאיש, ולבוב יש אחר. כל אחד מהם מערבב את הצהוב הציבורי עם הצבע הסודי שלו, ושולח את התערובת לצד השני, בגלוי. כולם רואים את שתי התערובות.

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

המאזין ראה את הצהוב ואת שתי התערובות שעברו. כדי להרכיב את התערובת הסופית הוא היה צריך צבע סודי אחד לפחות, ואת זה אף אחד לא שלח.

למה דווקא ערבוב

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

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

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

החשבון עצמו: שעון עם 23 שעות

הפעולה שמשחקת את תפקיד הערבוב היא חזקה על שעון. כלומר: מעלים מספר בחזקה, מחלקים במספר ראשוני, ולוקחים רק את השארית. בדיוק כמו שעון, שאחרי 12 חוזר ל-1.

נניח שהשעון שלנו הוא בגודל 23, והמספר הציבורי שממנו מתחילים הוא 5. שניהם ידועים לכולם. אליס בוחרת לעצמה סוד, 6. בוב בוחר לעצמו סוד, 15.

אליס מחשבת 5 בחזקת 6, שזה 15,625, ולוקחת את השארית בחלוקה ב-23. השארית היא 8. את המספר 8 היא שולחת בגלוי. בוב מחשב 5 בחזקת 15 ולוקח את השארית, ומקבל 19. גם הוא שולח בגלוי.

עכשיו אליס לוקחת את ה-19 שקיבלה ומעלה אותו בחזקת הסוד שלה, 6, שוב מודולו 23. התוצאה היא 2. בוב לוקח את ה-8 שקיבל ומעלה אותו בחזקת הסוד שלו, 15, מודולו 23. גם הוא מקבל 2.

זה לא צירוף מקרים. אליס חישבה בפועל את 5 בחזקת 15 ואז בחזקת 6, ובוב חישב את 5 בחזקת 6 ואז בחזקת 15. שניהם חישבו את 5 בחזקת 90, רק בסדר הפוך. סדר החזקות אינו משנה, וזו כל התחבולה.

והמאזין. הוא יודע 23, יודע 5, ראה את 8 ואת 19. כדי להגיע ל-2 הוא צריך למצוא איזו חזקה של 5 נותנת 8. על שעון בגודל 23 הוא ימצא תוך שניות. על שעון בגודל של מספר בן 2048 ביט אין היום דרך לעשות את זה.

להסכים על סוד, או לשלוח סוד

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

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

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

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

חתימה דיגיטלית: אותו זוג, בכיוון ההפוך

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

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

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

מה זה לא פותר

כאן נמצאת אי ההבנה הנפוצה ביותר בנושא. הצפנה מגינה על התוכן. היא אינה מגינה על הזהות.

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

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

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

מה מאיים על זה

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

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

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

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