העתיד של קריפטוגרפיה יהיה בטוח קוונטי. הנה איך זה יעבוד.

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

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

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

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

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

הנה דרך אחת לתאר קריפטוגרפיה של סריג: תאר לעצמך שלחבר שלך יש סריג, שהוא רק חבורה של נקודות בדפוס קבוע שחוזר על עצמו בכל המישור. חבר שלך רוצה שתציין 10 מהנקודות האלה. אבל הוא מתקשה, והוא לא ישרטט את כל הסריג. במקום זאת, הוא מפרט רק שתי נקודות - הראשונה עם א x-ערך של 101 ו-a y-ערך של 19, השני עם קואורדינטות [235, 44].

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

אבל החבר שלך עדיין לא מרוצה. הוא נותן לך את אותן שתי נקודות התחלה, ואז שואל אותך אם הנקודה [2, 1] נמצאת על אותו סריג. כדי לענות נכון על שאלה זו, עליך למצוא את השילוב של [101, 19] ו- [235, 44] שמייצר [2, 1]. בעיה זו היא הרבה יותר קשה מהראשונה, וסביר להניח שבסופו של דבר רק תנחש ותבדוק כדי לקבל את התשובה.* אסימטריה זו היא שעומדת בבסיס ההצפנה של הסריג.

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

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

הדביקו את העמודה החדשה על קצה הרשת. הרשת החדשה הזו בת שלוש עמודות היא המפתח הציבורי שלך. שתפו אותו בחופשיות!

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

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

כעת היא מצמידה את השורה החדשה לתחתית הרשת ושולחת אותה בחזרה אליך. (שוב, במערכת אמיתית, היא תצטרך להוסיף קצת רעש לשורה שלה.)

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

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

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

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

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

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

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

*: התשובה, אם אתה סקרן, היא 7 × [101, 19] - 3 × [235, 44] = [2, 1]. [בחזרה למאמר]