עתיד הקריפטוגרפיה של המפתח הציבורי בעידן המחשוב הקוונטי

(של מריו ראסו)
27/07/20

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

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

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

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

בין אלגוריתמי המפתח הסימטריים, ה-תקן הצפנה מתקדם (AES), ה Blowfishשני דגים או נָחָשׁ, עם אורך מפתח גדול מ- 256 ביט או שווה לו ובתנאים מתאימים, הם יכולים להוכיח את עצמם בטוח קוונטית.

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

צופי המפתח הציבוריים הידועים והמשתמשים כיום כוללים:

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

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

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

הצ'יפים החדשים יאומצו על ידי ארצות הברית בהקבלה ליוזמות קודמות להקמת ה- הצפנת נתונים רגילה (DES) ו- AES.

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

מחזור שני, קריפטוגרפיה רב משתנה4, מבוסס על הקושי לפתור מערכות של משוואות אלגבריות ריבועיות במשתנים רבים (NP-קַשִׁיוּת).

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

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

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

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

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

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

1 גרובר, "אלגוריתם מכני קוונטי מהיר לחיפוש בסיסי נתונים", Proceedings, 28 ACM Symposium שנתי על תיאוריית המחשוב, עמ '. 212, 1996.

2 שור, "אלגוריתמים לחישוב קוונטי: יומן בדידים ופקטורציה", בהמשך לסימפוזיון השנתי ה -35 בנושא יסודות מדעי המחשב, סנטה פה, IEEE Computer Society Press, pp. 124-134, 1994.

3 McEliece, "מערכת מפתח ציבורי המבוססת על תורת קידוד אלגברי", דוח התקדמות DSN 44, עמ '. 114-116, 1978.

4 Matsumoto, Imai, "סוג של מערכות קריפטו-אסימטריות המבוססות על פולינומים על טבעות סופיות", סימפוזיון בינלאומי של IEEE על תיאוריית המידע, תקציר ניירות, עמ '131-132, 1983.

5 גולדרייך, גולדווסר, הלוי, "מערכת קריפטו-מפתח בציבור מבעיית הפחתת הסריג", בפרק. Crypto '97, כרך 1294 של LNCS עמ '. 112-131, IACR, שפרינגר-ורלאג, 1997.

6https://itbrief.com.au/story/apac-jumps-on-quantum-computing-bandwagon

7https://www.ilsole24ore.com/art/la-cina-l-occidente-e-sfida-globale-big-...

8https://fedmanager.com/news/congressman-quantum-computing-equivalent-to-...

צילום: יבמ