הצפנה פוסט-קוונטית

From האנציקלופדיה היהודית
Jump to: navigation, search

הצפנה פוסט-קוונטית (Post-quantum cryptography) מתייחסת לאלגוריתמים קריפטוגרפיים (בדרך כלל של מפתח ציבורי) הנחשבים בטוחים נגד קריפטואנליזה המבוצעת עם מחשב קוונטי. הנחה שאינה נכונה כלל לגבי מרבית האלגוריתמים האסימטריים הפופולריים כמו אילו המבוססים על RSA ודיפי-הלמן, אותם ניתן לפרוץ בקלות עם מחשב קוונטי מעשי בקנה מידה גדול[1].

רקע[edit | edit source]

האלגוריתמים האסימטריים הנפוצים בשימוש מעשי כיום, מבוססים ברובם בעיקר על שתי בעיות מתורת המספרים הנחשבות "קשות" ונגזרותיהן; בעיית פירוק לגורמים ובעיית הלוגריתם הבדיד. כשהאחרונה מתחלקת לשני תחומים מתמטיים, שדה סופי ועקום אליפטי. ב-1994 הראה פיטר שור[2] שאפשר לפרק לגורמים מספר גדול באמצעות אלגוריתם קוונטי הנקרא על שמו אלגוריתם שור בסיבוכיות זמן של , היעילה באופן דרמטי לעומת השיטות הידועות במחשב קלאסי. ב-1996 המציא לוב גרובר[3] אלגוריתם קוונטי שנקרא אלגוריתם גרובר לחיפוש במבנה נתונים לא ממויין בזמן של . ההשלכה שלו מרחיקה לכת ויש לה השפעה עצומה על תורת ההצפנה, במיוחד על הצפנה א-סימטרית אך גם על הצפנה סימטרית. עם האלגוריתמים המנויים כאשר מחשב קוונטי גדול יהפוך למציאות, שבירת המערכות הללו יכולה להתרחש בזמן פולינומי, שזה נמוך בהרבה מהאלגוריתם הטוב ביותר הידוע כיום הנקרא נפת שדה מספרים שהוא תת-מעריכי. משמעות הדבר שפרוטוקול דיפי-הלמן, RSA וכן כל נגזרותיהם המסתמכים על בעיות דומות יצאו מכלל שימוש כליל.

בשנים האחרונות חלה התדקמות בפיתוח מחשבים קוונטיים. באוגוסט 2015 הכריזה חברת D-Wave הקנדית על מחשב קוונטי "אנלוגי" מעשי הנקרא D-Wave 2X בקנה מידה של +1000 קיוביטים. באותה עת פורסם שהמחשב הותקן בהצלחה במעבדת הבינה המלאכותית הקוונטית השייכת למיזם משותף של נאס"א וגוגל. יש לציין שמחשב קוונטי מסוג זה אינו לשימוש כללי ואינו רלוונטי לקריפטואנליזה, הוא מתאים בעיקר לפתרון בעיות מיוחדות בתחום אופטימיזציה, ביואינפורמטיקה וכדומה. למרות שהמחשבים הקוונטיים הדיגיטליים המיוצרים נכון לשנת 2016 עדיין קטנים מדי מכדי לבצע עליהם התקפה מלאה נגד האלגוריתמים האסימטריים עם מפתחות באורכים המומלצים על ידי התקנים הבינלאומיים, ישנן הערכות שמחשבים קוונטיים בהיקף מלא עומדים להיות זמינים בתוך כעשור, זאת בניגוד להערכות קודמות. מסיבה זו הקהילה הקריפטוגרפית נערכת בתקופה זו למעבר לעידן קוונטי והעניין בנושא גובר מצד האקדמיה והתעשייה בעיקר דרך כנסים של PQCrypto[4] המתקיימים אחת לשנה מאז 2006 וכן קבוצות מחקר של ארגונים כמו ETSI וIEEE[5].

הצפנה פוסט-קוונטית לעומת הצפנה קוונטית[edit | edit source]

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

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

הצפנה סימטרית[edit | edit source]

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

אלגוריתמים פוסט קוונטיים[edit | edit source]

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

  • הצפנה מבוססת גיבוב: הדוגמה הקלאסית למערכת כזו היא חתימה דיגיטלית מבוססת עץ גיבוב משנת 1979 של רלף מרקל מחלוצי הצפנת מפתח ציבורי, המבוססת על חתימת למפורט.
  • הצפנה מבוססת קודים: הדוגמה הטובה ביותר היא הצפנת מקאליס משנת 1978 של רוברט מקאליס המבוססת על תורת הקודים.
  • הצפנה מבוססת סריג: סריגים נחקרו במשך שנים לטובת הצפנה, הדוגמה הידועה והמעשית ביותר היא אלגוריתם NTRU משנת 1996 של Jeffrey Hoffstein, Jill Pipher ו-Joseph Silverman[6].
  • הצפנה מבוססת משוואות רבועיות מרובות משתנים: הדוגמה המבטיחה ביותר היא גרסאות של אלגוריתם חתימה דיגיטלית HFE של Jacques Patarin משנת 1996[7].
  • הצפנה סימטרית או הצפנת מפתח סודי: הדוגמה הטובה ביותר היא תקן AES אך קיים מאגר עשיר של אלגוריתמים יעילים ובדוקים כמו Salsa20 או SNOW 3G ועוד רבים שנבחנו במשך שנים ולא נמצאו בהם חולשות משמעותיות. חלקם בטוחים יותר וחלקם פחות, כל אחד מהם מתאים לשימוש בהתאם לסיטואציה, חשיבות היעילות, פוטנציאל האיום, קונפיגורציה וכדומה. נכון להיום מרבית האלגוריתמים הבטוחים יעמדו במבחן האיום הקוונטי עם מפתחות באורך כפול מהאורך הנוכחי בלבד. עובדה זו מאפשרת מציאת חלופות להצפנה אסימטרית כמו העברת מפתח מבוססת הצפנה סימטרית של קרברוס.

הצפנה מבוססת גיבוב[edit | edit source]

Postscript-viewer-shaded.png ערך מורחב – חתימה דיגיטלית מבוססת פונקציית גיבוב

חתימה דיגיטלית מבוססת פונקציית גיבוב מסתמכת על התכונה של פונקציית הגיבוב שהיא חסינת התנגשויות. הוכח שתכונה זו לבדה מספקת כדי להכין ממנה חתימה דיגיטלית. האלגוריתם הראשון המבוסס על פונקציית גיבוב הוא חתימת למפורט הפועלת כך: אליס משתמשת במחולל פסאודו-אקראי כדי לייצר טבלה של 256 זוגות מספרים אקראיים באורך 256 סיביות כל אחד, סך הכול 16 קילובייט של מידע פרטי. את כל הערכים בטבלה היא מגבבת ושולחת לבוב את התוצאות כמפתח ציבורי. כדי לחתום על מסר תחילה מגבבת את המסר ומקבלת 256 סיביות של תוצאת הגיבוב, אותם היא מחליפה סיבית אחר סיבית בערכים מהטבלה בהתאם לערכה של כל סיבית כלומר אם הסיבית הנוכחית היא "0" מוחלפת בערך הראשון בזוג המתאים בטבלה ואם היא "1" מוחלפת בשני וכן הלאה. כך נוצרים 256 ערכים של חתימה שאורכה הכולל הוא 8 קילובייט. כדי לאמת את החתימה בוב מבצע פעולה דומה, מגבב את המסר, את התוצאה מחליף סיבית אחר סיבית בהתאם לערכה בערכים מהמפתח של אליס, הוא מבצע גיבוב של 256 הערכים של החתימה שקיבל ומשווה ביניהם. אליס אינה משתמשת שוב במפתח הפרטי שלה לחתימה על מסרים אחרים (מכאן השם). כדי לחתום על מסרים נוספים עם אותו מפתח פרטי ניתן לבצע "שרשור". כלומר כל מסר יכיל בנוסף לחתימה שלו מפתח ציבורי חדש שישמש לחתימה על המסר הבא וכן הלאה. כך החתימה על המסר האחרון תכיל עותק של כל המסרים שנחתמו קודם עם אותו מפתח.

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

הצפנה מבוססת קודים[edit | edit source]

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

הצפנה מבוססת משוואות רבועיות מרובות משתנים[edit | edit source]

אלגוריתם HFE (קיצור של Hidden Fields Equations) הוא מערכת הצפנה מרובת משתנים (multivariate cryptography) המבוססת על מערכת משוואות ריבועיות מרובות נעלמים, שהדיעה הרווחת שהיא תהיה עמידה נגד התקפת מחשב קוונטי. הרעיון הבסיסי העומד מאחורי הצפנה כזו הוא הקושי שבפתרון מערכת משוואות פולינומיות מרובת משתנים ממעלה שנייה או יותר, מעל שדה סופי שהיא בעיה NP-קשה או בעיית NP-שלמה. נכון להיום הניסיונות לפתח מערכת הצפנה מבוססת משוואות ריבועיות מרובות משתנים לא צלחו. ז'ק פטרין המציא ב-1997 חתימה דיגיטלית אסימטרית מעשית בשיטת Oil and Vinegar (הסתרת משוואות ריבועיות ב- נעלמים הנקראים "שמן" ו- נעלמים הנקראים "חומץ" מעל שדה סופי עם פונקציות ליניאריות סודיות, כאשר ). שמיר וקיפניס הוכיחו[8] שהיא אינה בטוחה. וריאציה אחרת שלה הנקראת Unbalanced Oil and Vinegar[9] שבה טובה יותר וביטחונה הוא שאלה פתוחה[10].

אלגוריתמים נוספים[edit | edit source]

הצפנה מבוססת עקום אליפטי סופר-סינגולרי איזוגני, היא נושא חדש שנמצא במחקר ועוסק במועמדים טובים להצפנת מפתח ציבורי פוסט-קוונטית המבוססת על עקום אליפטי. קושייה המשוער נובע מהבעיה של מציאת איזוגניות בין עקומים אליפטיים סופר-סינגולריים. המחקר נובע מהתפתחות חדשה בתחום אלגוריתמים קוונטיים תת-מעריכיים למציאת איזוגניות בין עקומים רגילים, אך הבעיה נותרת מעריכית בעקומים סופר-סינגולריים. ההבדל הזה הוא הבסיס למערכת הצפנה אסימטרית. ב-2011 פותח אלגוריתם Supersingular isogeny key exchange[11] (בקיצור SIDH) המבוסס על פרוטוקול העברת מפתח דיפי-הלמן הנפוץ כיום בשימוש במערכות אבטחה רבות בשתי גרסאות DHE ו-ECDHE (בעקום אליפטי). האלגוריתם פותח לאור האיום הקוונטי מתוך מטרה שיהיה מועמד ראוי להחלפת הפרוטוקולים הקודמים ובעל תכונות טובות כמו מפתח קצר וביטחון לפנים (forward secrecy).

למידה חישובית ובעיות סריג[edit | edit source]

הצפנה חדשה אחרת שגם היא נחשבת לפוסט-קוונטית היא פרוטוקול שיתוף מפתח RLWE קיצור של Ring learning with errors המבוסס על למידה חישובית שהוכחה על ידי עודד רגב ב-2005 שקושייה שקול לבעיות סריג קשות. הרעיון הכללי הוא לבסס מערכת הצפנת מפתח ציבורי על הקושי בהבחנה בין פונקציות ליניאריות אקראיות המוסתרות על ידי כמות מועטה של "רעש" מפונקציות אקראיות אמיתיות.

חתימה דיגיטלית BLISS[12] שפותחה ב-2015 אף היא מבוססת על הצפנת סריגים ונחשבת אך לא מוכחת כבטוחה בהנחה שבעיית CVP (בעיית הווקטור הקרוב ביותר בתורת הסריגים) קשה והיא מועמדת טובה להצפנה פוסט קוונטית.

אורך מפתחות[edit | edit source]

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

אלגוריתם אורך מפתח ציבורי בסיביות אורך מפתח פרטי בסיביות
Ring-LWE[13] 6,595 14,000
NTRU[14] 6,130 6,743
Rainbow[15][16] 991,000 740,000
הצפנה מבוססת גיבוב[17] 36,000 36,000
McEliece[18] 8,373,911 92,027
MDPC McEliece[18][19] 65,542 4,384
SIDH[11] 6,144 6,144


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

אתגרים[edit | edit source]

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

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

ראו גם[edit | edit source]

הערות שוליים[edit | edit source]

  1. ^ Daniel J. Bernstein (2009). "Introduction to post-quantum cryptography". (Introductory chapter to book "Post-quantum cryptography").
  2. ^ Peter W. Shor (1995-08-30). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer"
  3. ^ Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
  4. ^ Cryptographers Take On Quantum Computers
  5. ^ ETSI 2nd Quantum-Safe Crypto Workshop in partnership with the IQC
  6. ^ NTRU: A Ring-Based Public Key Cryptosystem
  7. ^ Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms
  8. ^ A. Kipnis, A. Shamir, Cryptanalysis of the Oil and Vinegar Signature Scheme, Proceedings of CRYPTO’98, Springer, LNCS no1462, pp. 257-266
  9. ^ Unbalanced Oil and Vinegar Signature Schemes
  10. ^ Bulygin, Stanislav; Petzoldt; Buchmann (2010). "Towards Provable Security of the Unbalanced Oil and Vinegar Signature Scheme under Direct Attacks". Progress in Cryptology – INDOCRYPT 2010. Lecture Notes in Computer Science (Springer) 6498: 17–32.
  11. ^ 11.0 11.1 TOWARDS QUANTUM-RESISTANT CRYPTOSYSTEMS FROM SUPERSINGULAR ELLIPTIC CURVE ISOGENIES
  12. ^ Lattice Signatures and Bimodal Gaussians, Leo Ducas and Alain Durmus and Tancrede Lepoint and Vadim Lyubashevsky
  13. ^ A Practical Key Exchange for the Internet using Lattice Cryptography
  14. ^ Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: A Ring Based Public Key Cryptosystem. In Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288.
  15. ^ Ding J., Schmidt D.: Rainbow, a new multivariate polynomial signature scheme. In Ioannidis, J.,Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS vol. 3531, pp. 164–175 Springer, Heidelberg (2005)
  16. ^ Selecting Parameters for the Rainbow Signature Scheme
  17. ^ One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal
  18. ^ 18.0 18.1 Post-Quantum Cryptography for Long-Term Security
  19. ^ MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes


ערך זה מוגש באדיבות ויקיפדיה העברית. (הדף המקורי, רשימת התורמים)
הערך בוויקיפדיה גדול מערך זה ב +2685 תווים

לעדכון מוויקיפדיה, לחץ כאן.

NivdakVeushar.png