הרעיון הכללי הוא; בהינתן מחרוזת של formula_1 סיביות המקודדת למילת קוד בגודל formula_2 סיביות על ידי מקודד ידוע לכול של קוד ליניארי בינארי באורך formula_3 וממד formula_1, אזי הטקסט המוצפן מיוצר על ידי החדרת formula_5 שגיאות אקראיות, כלומר הפיכת formula_5 סיביות (Bit flipping) במיקומים אקראיים במילת הקוד. אם formula_5 קטן בחצי לפחות ממרחק המינג של הקוד הליניארי של טקסט מוצפן נתון קיים רק טקסט גלוי יחיד המתאים לו שניתן לשחזור באמצעות קוד תיקון השגיאות. אך אם הפרמטרים formula_8 גדולים חילוץ הטקסט הגלוי מהטקסט המוצפן באמצעות תיקון שגיאות אינו מעשי אלא אם כן נתון מידע נוסף לגבי מבנה הקוד. ההבדל בפקטור העבודה בין קידוד מילת הקוד לבין תיקון השגיאות הוא הבסיס להצפנה האסימטרית שהציע מקאליס, המפתח הציבורי יהיה הקוד הליניארי והמפתח הפרטי יהיה המידע המאפשר את תיקון השגיאות בזמן פולינומי. מקאליס המליץ על שימוש בקוד תיקון שגיאות שנקרא "קוד גוֹפַּא בינארי" על שם ממציאו וולרי גופא (Valerii Goppa) מפני כמה סיבות, לקוד זה קיים אלגוריתם פענוח פולינומי יעיל וכן העובדה שקוד גופא מהווה מועמד טוב לפונקציה חד-כיוונית - קל לייצר קוד כזה אך קשה מאוד לזהות אותו.
הגדרות כלליות.
כדי להקים מערכת הצפנת מקאליס, אפשר לפעול כדלהלן:
בוחרים קוד גוֹפַּא שהוא פולינום שרירותי אי-פריק formula_9 ממעלה formula_5 מעל השדה formula_11 ותת-קבוצה formula_12 של formula_11 עם הפרמטרים formula_14. כדי לקבל מרחק מינימלי גדול ככל האפשר רצוי שמספר השורשים של formula_9 יהיה שווה למעלה שלו (נקרא separable).
מכינים מטריצה יוצרת formula_16 של קוד גופא מסדר formula_17.
לאחר מכן בוחרים מטריצה הפיכה (לא סינגולרית) formula_18 אקראית מסדר formula_19, ומטריצת תמורה formula_20 (מטריצה בינארית ריבועית המכילה בדיוק כניסה אחת שהיא '1' בכל שורה ואו בכל עמודה וכל היתר אפסים) מסדר formula_21 ומחשבים את formula_22.
מפיצים את formula_23 ואת formula_5 כפרמטרים ציבוריים ושומרים בסוד את כל היתר.
אם מישהו רוצה להצפין מסר כלשהו formula_25 באורך formula_1 סיביות, הוא בוחר וקטור שגיאות formula_27 באורך formula_3 במשקל formula_5 (שבו לכל היותר formula_5 קואורדינטות שונות מאפס), וההצפנה של formula_25 היא formula_32 אותה הוא שולח למקבל. המקבל יכול לחשב עם הפרמוטציה הסודית formula_20 את:
כאשר formula_35 במשקל נמוך מ-formula_5. עם אלגוריתם הפענוח של קוד גופא המקבל יכול לתקן את formula_37 למילה formula_38 על ידי חישוב formula_35. כיוון שהמטריצה formula_18 הפיכה אפשר לחלץ את המסר על ידי formula_41.
כדי שהמערכת האמורה תהיה בטוחה ההמלצה של מקאליס הייתה לפני 25 שנה שהפרמטרים יהיו formula_42 והפולינום formula_9 הוא פולינום אי פריק מסדר formula_44 ובמקרה זה formula_45 ו-formula_46. אולם כדי לעמוד בהתקדמות הטכנולוגית שחלה ב-25 השנים האחרונות מומלץ כיום להשתמש בפרמטרים קצת יותר גדולים כמו formula_47 ומספר השגיאות בין 30 ל-120 והממד במקרה זה נע בין 1,718 ל-728. לסיכום המערכת היא:
דוגמה במספרים קטנים.
לשם המחשה: אם נבחר השדה formula_48, הפולינום formula_49 אי פריק ואז formula_50 הוא אלמנט פרימיטיבי רק אם הוא מסדר 15. האלמנטים של תת-הקבוצה formula_51 הם החזקות של formula_50 כאשר formula_53 הקבוצה המתקבלת היא formula_54. קוד גופה מעל שדה זה יכול להיות
עבור קוד זה formula_57 ו-formula_1 צריך להיות formula_59. המרחק המינימלי הוא formula_60. בקיצור זהו קוד גופא בינארי formula_61 עם הפרמטרים formula_62 ואפשר לתקן איתו עד שתי שגיאות. אם נבחר לדוגמה את המטריצות הבאות
והמסר להצפנה הוא formula_67 תחילה מחשבים את
מוסיפים את וקטור השגיאה (שהוא וקטור המכיל אפסים למעט הפוזיציות השנייה והשלישית) ואז ההצפנה של formula_25 היא
המקבל שרוצה לפענח את formula_25 מתוך formula_72 מחשב תחילה את formula_73 מהמטריצה formula_20
כתוצאה מהפעולה האחרונה השגיאות עברו לפוזיציות הרביעית והעשירית אחרי תיקון מתקבל
ואז אפשר לפענח את הקוד על ידי כפל המטריצות הבא:
לכן formula_78 והצעד האחרון הוא חישוב formula_79
קוד גופא בינארי.
יהי formula_25 שלם חיובי ויהיו formula_3 ו-formula_5 שני פרמטרים כך שמתקיים formula_84 וכן formula_85. קוד גופה בינארי המסומן formula_86 מוגדר על ידי תת-קבוצה סדורה formula_87 של השדה formula_88 מסדר formula_3 שנקראת תמיכה (support) ועל ידי פולינום מתוקן אי פריק formula_90 ממעלה formula_5 ללא שורשים ב-formula_12 הנקרא יוצר (generator). הווקטור formula_93 ייקרא קוד גופא אם מתקיים
הביטוי formula_95 קיים מאחר ש-formula_96 הוא שדה. והמעלה formula_5 של הפולינום מהווה גבול תחתון ליכולת תיקון השגיאות של הקוד. הקוד המתואר ליניארי ולו ממד formula_98 וכן מרחק מינימלי של formula_99 לפחות לכן ניתן לשחזר עד formula_5 שגיאות.
פענוח אלגברי של קוד גופה.
אם formula_101 הוא מילת קוד של formula_86 ואם formula_103 עם formula_104 בעל מרחק המינג formula_5 או פחות, המילים formula_101 ו-formula_27 ייחודיים בגלל formula_108. קיים פולינום מתוקן יחיד formula_109 ב-formula_88 ממעלה לכל היותר formula_5 המקיים
כאשר formula_113 הוא פולינום ב-formula_88 ממעלה לכל היותר formula_115. לפולינום formula_109 יש בדיוק formula_5 שורשים ב-formula_12 המתאימים לפוזיציות המכילות אחד בווקטור השגיאה formula_27. תהליך הפענוח כולל את הפעולות הבאות:
ישנן כמה וריאציות לפתרון נוסחת המפתח האמורה ביניהן אלגוריתם אוקלידס.
גרסאות נוספות.
ב-1986 הציע נידריטר (Niederreiter) מערכת דומה בביטחונה שנקראת גרסה דואלית. גרסה נוספת שהוצעה מבוססת על קוד ריד-מולר. מקאליס ציין שהמערכת שלו אינה מתאימה לחתימה דיגיטלית ב-2001 הומצאה חתימה דיגיטלית מבוססת מקאליס.
גודל מפתחות.
גודל המפתח הציבורי הוא כנראה חסרונה הגדול של המערכת והוא formula_123 כאשר formula_1 הוא אורך המידע המיועד להצפנה ו-formula_3 הוא אורך הבלוק המוצפן. למשל לפי הפרמטרים המקוריים שהוצעו על ידי מקאליס גודל המפתח הציבורי הוא 536,576 סיביות. סנדריר הציע להפחית מגודל המפתח הציבורי בשיטה סיסטמטית. כלומר formula_126 כאשר formula_127 הוא מטריצת היחידה formula_19 ו-formula_129 הוא מסדר formula_130. כך גודל המפתח מצטמצם ל-formula_131 סיביות כי יש צורך לאחסן רק את הצד הימני (formula_129), אך עדיין המפתח יהיה די גדול (בערך 262,000 סיביות).
ביטחון.
הצפנת מקאליס מבוססת על שתי בעיות קשות בתורת הקודים האחת היא מקרה פרטי של בעיית "פענוח סינדרומי" שהוכח שהיא NP-שלמה; בהינתן מטריצה בינארית מסדר formula_133 ו-formula_101 מילות קוד כלשהן ב-formula_135 הבעיה היא למצוא מילה formula_27 ב-formula_137 במשקל נמוך או שווה ל-formula_138 כך שמתקיים formula_139 כאשר formula_140 הוא הסינדרום. הוכח על ידי ברלקמפ, מקאליס וטילבורג שהבעיה NP-קשה.
והבעיה שנייה היא בעיית זיהוי 'קוד גופא', כלומר בהינתן מטריצה בינארית מסדר formula_133 לענות על השאלה האם היא מטריצת גופה. אפשר לתקוף את סכימת מקאליס בשתי דרכים. אחת היא 'התקפה מבנית' בה מנסים לשחזר את המפענח של הקוד הנוצר על ידי המפתח הציבורי formula_23 ומשם לשחזר את המפתח הפרטי formula_16, אם היא מצליחה המערכת נפרצת לחלוטין. אפשר לסווג קודי שגיאות למחלקות שקילות, שני קודים באורך זהה ייקראו שקולים (שההפרש ביניהם הוא מילת קוד) אם קיימת בדיוק תמורה אחת באורך formula_3 המשנה קוד אחד לשני לכן הקוד formula_145 שנוצר על ידי formula_23 והקוד הנוצר על ידי formula_16 נקראים שקולים. בהתקפה זו התוקף מנסה להשוות בין קודים כדי למצוא שקילות. אם נמצאה שקילות אפשר לשחזר את התמורה ביניהם על ידי אלגוריתם פולינומי שנקרא Support Splitting Algorithm (של ניקולס סנדריר 1999). תהליך זה הוא מעבר ליכולת הטכנולוגית הנוכחית עם הפרמטרים המקוריים של מקאליס כי התקפה מבנית מסוג זה דורשת בערך formula_148 קודים כדי שתצליח. בהתקפה השנייה שנקראת התקפת פענוח התוקף מנסה לנחש את פענוח הקוד מבלי לפרוץ את המערכת עצמה. ההתקפה תלויה בפרמטרים של קוד תיקון השגיאות formula_145, אורכו, הממד שלו ויכולת תיקון השגיאות (formula_5). לפי הפרמטרים המקוריים של מקאליס התקפה כזו תתבצע עם formula_151 פעולות בינאריות. מספר זה נמוך בהשוואה ליכולת הטכנולוגית הנוכחית אך הבעיה היא שכדי להעלות מספר זה יש צורך להגדיל את הפרמטרים וכיוון שהמפתח הציבורי מאוד גדול גם ככה זו בעיה.
יתרונות וחסרונות.