מחשבים קוונטיים: סוף הקריפטוגרפיה?

פרסומת

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

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

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

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

אז למה כל העניין? למה אכפת לך? מחשבים נעשים מהירים יותר כל הזמן מה החוק של מור, ומה זה קשור אליך? [MakeUseOf מסביר]מזל רע לא קשור לחוק של מור. אם זו העמותה שהייתה לך, אתה מבלבל אותה עם החוק של מרפי. עם זאת, לא היית רחוק מכיוון שחוק מור וחוק מרפי ...

קרא עוד - מה כל כך מיוחד במחשבים קוונטיים?

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

מהי מורכבות זמן פעולה?

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

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

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

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

מורכבות זמן וקריפטוגרפיה

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

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

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

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

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

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

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

מחשבים קוונטיים: שינוי משחק הקריפטו

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

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

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

לדוגמה קונקרטית, האלגוריתם של שור, שניתן לבצע רק במחשב קוונטי, יכול לחשב מספרים גדולים ב יומן (n) ^ 3 הזמן, שהוא טוב באופן דרסטי מההתקפה הקלאסית הטובה ביותר. שימוש במסננת המספר הכללי בכדי לפקטור מספר עם 2048 ביטים לוקח בערך 10 ^ 41 יחידות זמן, מה שמסתדר ליותר מטריליון טריליון טריליון. באמצעות האלגוריתם של שור, אותה בעיה אורכת רק 1000 יחידות זמן.

האפקט בולט יותר ככל שהמפתחות ארוכים יותר. זה הכוח של מחשבים קוונטיים.

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

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

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

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

קריפטוגרפיה שלאחר הקוונטים

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

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

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

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

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

האם אתה מודאג מחוסר הביטחון של הקריפטוגרפיה למחשבים קוונטיים? מה הצורך שלך? שתף את מחשבותיך בתגובות למטה!

זיכויים לתמונה: כדור בינארי דרך Shutterstock