הצפנת מקאליס

הצפנת מקאליס (באנגלית: McEliece Cryptosystem) היא מערכת הצפנה אסימטרית המבוססת על קוד תיקון שגיאות, שפותחה ב-1978 על ידי רוברט מקאליס (R.J. McEliece).
הרעיון הכללי הוא; בהינתן מחרוזת של  סיביות המקודדת למילת קוד בגודל  סיביות על ידי מקודד ידוע לכול של קוד ליניארי בינארי באורך  וממד , אזי הטקסט המוצפן מיוצר על ידי החדרת  שגיאות אקראיות, כלומר הפיכת  סיביות (Bit flipping) במיקומים אקראיים במילת הקוד. אם  קטן בחצי לפחות ממרחק המינג של הקוד הליניארי של טקסט מוצפן נתון קיים רק טקסט גלוי יחיד המתאים לו שניתן לשחזור באמצעות קוד תיקון השגיאות. אך אם הפרמטרים  גדולים חילוץ הטקסט הגלוי מהטקסט המוצפן באמצעות תיקון שגיאות אינו מעשי אלא אם כן נתון מידע נוסף לגבי מבנה הקוד. ההבדל בפקטור העבודה בין קידוד מילת הקוד לבין תיקון השגיאות הוא הבסיס להצפנה האסימטרית שהציע מקאליס, המפתח הציבורי יהיה הקוד הליניארי והמפתח הפרטי יהיה המידע המאפשר את תיקון השגיאות בזמן פולינומי. מקאליס המליץ על שימוש בקוד תיקון שגיאות שנקרא "קוד גוֹפַּא בינארי" על שם ממציאו וולרי גופא (Valerii Goppa) מפני כמה סיבות, לקוד זה קיים אלגוריתם פענוח פולינומי יעיל וכן העובדה שקוד גופא מהווה מועמד טוב לפונקציה חד-כיוונית - קל לייצר קוד כזה אך קשה מאוד לזהות אותו.

גרסאות נוספות

ב-1986 הציע נידריטר (Niederreiter) מערכת דומה בביטחונה שנקראת גרסה דואלית. גרסה נוספת שהוצעה מבוססת על קוד ריד-מולר. מקאליס ציין שהמערכת שלו אינה מתאימה לחתימה דיגיטלית ב-2001 הומצאה חתימה דיגיטלית מבוססת מקאליס.

גודל מפתחות

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

ביטחון

הצפנת מקאליס מבוססת על שתי בעיות קשות בתורת הקודים האחת היא מקרה פרטי של בעיית "פענוח סינדרומי" שהוכח שהיא NP-שלמה; בהינתן מטריצה בינארית מסדר  ו- מילות קוד כלשהן ב- הבעיה היא למצוא מילה  ב- במשקל נמוך או שווה ל- כך שמתקיים  כאשר  הוא הסינדרום. הוכח על ידי ברלקמפ, מקאליס וטילבורג שהבעיה NP-קשה.
והבעיה שנייה היא בעיית זיהוי 'קוד גופא', כלומר בהינתן מטריצה בינארית מסדר  לענות על השאלה האם היא מטריצת גופה. אפשר לתקוף את סכימת מקאליס בשתי דרכים. אחת היא 'התקפה מבנית' בה מנסים לשחזר את המפענח של הקוד הנוצר על ידי המפתח הציבורי  ומשם לשחזר את המפתח הפרטי , אם היא מצליחה המערכת נפרצת לחלוטין. אפשר לסווג קודי שגיאות למחלקות  שקילות, שני קודים באורך זהה ייקראו שקולים (שההפרש ביניהם הוא מילת קוד) אם קיימת בדיוק תמורה אחת באורך  המשנה קוד אחד לשני לכן הקוד  שנוצר על ידי  והקוד הנוצר על ידי  נקראים שקולים. בהתקפה זו התוקף מנסה להשוות בין קודים כדי למצוא שקילות. אם נמצאה שקילות אפשר לשחזר את התמורה ביניהם על ידי אלגוריתם פולינומי שנקרא Support Splitting Algorithm (של ניקולס סנדריר 1999). תהליך זה הוא מעבר ליכולת הטכנולוגית הנוכחית עם הפרמטרים המקוריים של מקאליס כי התקפה מבנית מסוג זה דורשת בערך  קודים כדי שתצליח. בהתקפה השנייה שנקראת התקפת פענוח התוקף מנסה לנחש את פענוח הקוד מבלי לפרוץ את המערכת עצמה. ההתקפה תלויה בפרמטרים של קוד תיקון השגיאות , אורכו, הממד שלו ויכולת תיקון השגיאות (). לפי הפרמטרים המקוריים של מקאליס התקפה כזו תתבצע עם  פעולות בינאריות. מספר זה נמוך בהשוואה ליכולת הטכנולוגית הנוכחית אך הבעיה היא שכדי להעלות מספר זה יש צורך להגדיל את הפרמטרים וכיוון שהמפתח הציבורי מאוד גדול גם ככה זו בעיה.

יתרונות וחסרונות

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