הצפנת מקאליס

הצפנת מקאליס (באנגלית: McEliece Cryptosystem) היא מערכת הצפנה אסימטרית המבוססת על קוד תיקון שגיאות, שפותחה ב-1978 על ידי רוברט מקאליס (R.J. McEliece)^[1].

הרעיון הכללי הוא; בהינתן מחרוזת של ${\displaystyle k}$ סיביות המקודדת למילת קוד בגודל ${\displaystyle n>k}$ סיביות על ידי מקודד ידוע לכול של קוד ליניארי בינארי באורך ${\displaystyle n}$ וממד ${\displaystyle k}$, אזי הטקסט המוצפן מיוצר על ידי החדרת ${\displaystyle t}$ שגיאות אקראיות, כלומר הפיכת ${\displaystyle t}$ סיביות (Bit flipping) במיקומים אקראיים במילת הקוד. אם ${\displaystyle t}$ קטן בחצי לפחות ממרחק המינג של הקוד הליניארי של טקסט מוצפן נתון קיים רק טקסט גלוי יחיד המתאים לו שניתן לשחזור באמצעות קוד תיקון השגיאות. אך אם הפרמטרים ${\displaystyle n,k,t}$ גדולים חילוץ הטקסט הגלוי מהטקסט המוצפן באמצעות תיקון שגיאות אינו מעשי אלא אם כן נתון מידע נוסף לגבי מבנה הקוד. ההבדל בפקטור העבודה בין קידוד מילת הקוד לבין תיקון השגיאות הוא הבסיס להצפנה האסימטרית שהציע מקאליס, המפתח הציבורי יהיה הקוד הליניארי והמפתח הפרטי יהיה המידע המאפשר את תיקון השגיאות בזמן פולינומי. מקאליס המליץ על שימוש בקוד תיקון שגיאות שנקרא "קוד גוֹפַּא בינארי" על שם ממציאו וולרי גופא (Valerii Goppa) מפני כמה סיבות, לקוד זה קיים אלגוריתם פענוח פולינומי יעיל וכן העובדה שקוד גופא מהווה מועמד טוב לפונקציה חד-כיוונית - קל לייצר קוד כזה אך קשה מאוד לזהות אותו.

כדי להקים מערכת הצפנת מקאליס, אפשר לפעול כדלהלן: בוחרים קוד גוֹפַּא שהוא פולינום שרירותי אי-פריק ${\displaystyle g(z)}$ ממעלה ${\displaystyle t}$ מעל השדה ${\displaystyle GF(2^{m})}$ ותת-קבוצה ${\displaystyle L}$ של ${\displaystyle GF(2^{m})}$ עם הפרמטרים ${\displaystyle [n,\geq n-mt,\geq 2t+1]}$. כדי לקבל מרחק מינימלי גדול ככל האפשר רצוי שמספר השורשים של ${\displaystyle g(z)}$ יהיה שווה למעלה שלו (נקרא separable). מכינים מטריצה יוצרת ${\displaystyle G}$ של קוד גופא מסדר ${\displaystyle k\times n}$. לאחר מכן בוחרים מטריצה הפיכה (לא סינגולרית) ${\displaystyle S}$ אקראית מסדר ${\displaystyle k\times k}$, ומטריצת תמורה ${\displaystyle P}$ (מטריצה בינארית ריבועית המכילה בדיוק כניסה אחת שהיא '1' בכל שורה ואו בכל עמודה וכל היתר אפסים) מסדר ${\displaystyle n\times n}$ ומחשבים א�� ${\displaystyle G^{*}=SGP}$. מפיצים את ${\displaystyle G^{*}}$ ואת ${\displaystyle t}$ כפרמטרים ציבוריים ושומרים בסוד את כל היתר. אם מישהו רוצה להצפין מסר כלשהו ${\displaystyle m}$ באורך ${\displaystyle k}$ סיביות, הוא בוחר וקטור שגיאות ${\displaystyle e}$ באורך ${\displaystyle n}$ במשקל ${\displaystyle t}$ (שבו לכל היותר ${\displaystyle t}$ קואורדינטות שונות מאפס), וההצפנה של ${\displaystyle m}$ היא ${\displaystyle y=mG^{*}+e}$ אותה הוא שולח למקבל. המקבל יכול לחשב עם הפרמוטציה הסודית ${\displaystyle P}$ את:

${\displaystyle y'=yP^{-1}=mG^{*}P^{-1}+eP^{-1}=mSGPP^{-1}+e'=(mS)G+e'}$

כאשר ${\displaystyle e'}$ במשקל נמוך מ-${\displaystyle t}$. עם אלגוריתם הפענוח של קוד גופא המקבל יכול לתקן את ${\displaystyle y'}$ למילה ${\displaystyle m'=mS}$ על ידי חישוב ${\displaystyle e'}$. כיוון שהמטריצה ${\displaystyle S}$ הפיכה אפשר לחלץ את המסר על ידי ${\displaystyle m=m'S^{-1}}$.

כדי שהמערכת האמורה תהיה בטוחה ההמלצה של מקאליס הייתה לפני 25 שנה שהפרמטרים יהיו ${\displaystyle m=10}$ והפולינום ${\displaystyle g(z)}$ הוא פולינום אי פריק מסדר ${\displaystyle t=50}$ ובמקרה זה ${\displaystyle n=2^{10}=1024}$ ו-${\displaystyle k\geq 1024-10\cdot 50=525}$. אולם כדי לעמוד בהתקדמות הטכנולוגית שחלה ב-25 השנים האחרונות מומלץ כיום להשתמש בפרמטרים קצת יותר גדולים כמו ${\displaystyle n=2048,m=11}$ ומספר השגיאות בין 30 ל-120 והממד במקרה זה נע בין 1,718 ל-728. לסיכום המערכת היא:

מפתח ציבורי	מטריצה מותאמת ${\displaystyle G^{*}}$ מסדר ${\displaystyle k\times n}$ עם יכולת תיקון עד ${\displaystyle t}$ שגיאות
מפתח סודי	הפולינום ${\displaystyle g(z)}$, המטריצה היוצרת המקורית ${\displaystyle G}$ מסדר ${\displaystyle k\times n}$, המטריצה ${\displaystyle P}$ מסדר ${\displaystyle k\times k}$, המטריצה ${\displaystyle S}$ מסדר ${\displaystyle n\times n}$ כך שמתקיים ${\displaystyle G^{*}=SGP}$
המסר לקידוד	${\displaystyle m\in \{0,1\}^{k}}$
הצפנה	${\displaystyle y=mG^{*}+e}$ כאשר ${\displaystyle wt(e)\leq t}$
פענוח	תחילה ${\displaystyle y'=yP^{-1}}$, מתקנים את ${\displaystyle y'}$ ל-${\displaystyle m'=mS}$ מחשבים את ${\displaystyle m=m'S^{-1}}$

לשם המחשה: אם נבחר השדה ${\displaystyle GF(2^{4})}$, הפולינום ${\displaystyle k(X)=X^{4}+X+1}$ אי פריק ואז ${\displaystyle \alpha }$ הוא אלמנט פרימיטיבי רק אם הוא מסדר 15. האלמנטים של תת-הקבוצה ${\displaystyle GF(2^{4})^{*}}$ הם החזקות של ${\displaystyle \alpha }$ כאשר ${\displaystyle \alpha ^{4}=\alpha +1}$ הקבוצה המתקבלת היא ${\displaystyle \{\alpha ,\alpha ^{2},...,\alpha ^{14}\}}$. קוד גופה מעל שדה זה יכול להיות

${\displaystyle g(z)=(z+\alpha )(z+\alpha ^{14})=z^{2}+\alpha ^{7}z+1}$

${\displaystyle L=\{\alpha ^{i}|2\leq i\leq 13\}}$

עבור קוד זה ${\displaystyle n=12,t=2}$ ו-${\displaystyle k}$ צריך להיות ${\displaystyle 12-4\cdot 2=4}$. המרחק המינימלי הוא ${\displaystyle d\geq 2\cdot 2+1=5}$. בקיצור זהו קוד גופא בינארי ${\displaystyle \Gamma (L,g(z))}$ עם הפרמטרים ${\displaystyle [12,\geq 4,\geq 5]}$ ואפשר לתקן איתו עד שתי שגיאות. אם נבחר לדוגמה את המטריצות הבאות

${\displaystyle G={\begin{pmatrix}1\ \ 1\ \ 1\ \ 1\ \ 0\ \ 1\ \ 0\ \ 1\ \ 0\ \ 1\ \ 0\ \ 0\\0\ \ 1\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 1\ \ 0\\0\ \ 0\ \ 1\ \ 0\ \ 1\ \ 0\ \ 1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\\0\ \ 1\ \ 0\ \ 1\ \ 0\ \ 0\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 1\end{pmatrix}}}$

${\displaystyle S={\begin{pmatrix}1&0&1&1\\0&1&0&1\\1&1&0&1\\1&1&1&1\end{pmatrix}}}$

${\displaystyle P={\begin{pmatrix}0\ \ 0\ \ 0\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\\0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 1\ \ 0\\0\ \ 0\ \ 0\ \ 0\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\\0\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\\1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\\0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\end{pmatrix}}}$

${\displaystyle G^{*}=SGP={\begin{pmatrix}1\ \ 0\ \ 1\ \ 1\ \ 0\ \ 1\ \ 1\ \ 1\ \ 0\ \ 1\ \ 0\ \ 0\\1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 0\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\\1\ \ 0\ \ 1\ \ 1\ \ 1\ \ 0\ \ 1\ \ 1\ \ 1\ \ 0\ \ 1\ \ 0\\0\ \ 0\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1\end{pmatrix}}}$

והמסר להצפנה הוא ${\displaystyle m=(0,1,0,1)}$ תחילה מחשבים את

${\displaystyle mG^{*}=(1,1,1,1,0,1,0,0,0,1,1,1)}$

מוסיפים את וקטור השגיאה (שהוא וקטור המכיל אפסים למעט הפוזיציות השנייה והשלישית) ואז ההצפנה של ${\displaystyle m}$ היא

${\displaystyle y=mG^{*}+e=(1,\color {Red}0\color {Black},\color {Red}0\color {Black},1,0,1,0,0,0,1,1,1)}$

המקבל שרוצה לפענח את ${\displaystyle m}$ מתוך ${\displaystyle y}$ מחשב תחילה את ${\displaystyle yP^{-1}}$ מהמטריצה ${\displaystyle P}$

${\displaystyle yP^{-1}=mSG+e'=(1,1,0,\color {Red}0\color {Black},1,1,1,0,1,\color {Red}0\color {Black},0,0)}$

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

${\displaystyle mSG=(1,1,0,1,1,1,1,0,1,1,0,0)}$

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

${\displaystyle [G^{T}|(mS)^{T}]={\begin{pmatrix}1&0&0&0&1\\1&1&0&1&1\\1&0&1&0&0\\1&0&0&1&1\\0&1&1&0&1\\1&1&0&0&1\\0&1&1&1&1\\1&1&1&1&0\\0&0&1&0&1\\1&0&0&0&1\\0&1&0&0&0\\0&0&0&1&0\end{pmatrix}}\sim {\begin{pmatrix}1&0&0&0&\color {Green}1\\0&1&0&0&\color {Green}0\\0&0&1&0&\color {Green}1\\0&0&0&1&\color {Green}0\\1&1&0&1&1\\1&0&1&0&0\\1&0&0&1&1\\0&1&1&0&1\\1&1&0&0&1\\0&1&1&1&1\\1&1&1&1&0\\1&0&0&0&1\end{pmatrix}}}$

לכן ${\displaystyle mS=(1,0,1,0)}$ והצעד האחרון הוא חישוב ${\displaystyle S^{-1}}$

${\displaystyle m=(1,0,1,0)\cdot {\begin{pmatrix}0&1&1&0\\1&0&0&1\\0&0&1&1\\1&1&0&1\\\end{pmatrix}}=(0,1,0,1)}$.

יהי ${\displaystyle m}$ שלם חיובי ויהיו ${\displaystyle n}$ ו-${\displaystyle t}$ שני פרמטרים כך שמתקיים ${\displaystyle n\leq 2^{m}}$ וכן ${\displaystyle t<n/m}$. קוד גופה בינארי המסומן ${\displaystyle \Gamma (L,g)}$ מוגדר על ידי תת-קבוצה סדורה ${\displaystyle L=(\alpha _{1},...,\alpha _{n})}$ של השדה ${\displaystyle F_{2^{m}}}$ מסדר ${\displaystyle n}$ שנקראת תמיכה (support) ועל ידי פולינום מתוקן אי פריק ${\displaystyle g(z)\in F_{2^{m}}[z]}$ ממעלה ${\displaystyle t}$ ללא שורשים ב-${\displaystyle L}$ הנקרא יוצר (generator). הווקטור ${\displaystyle a=(a_{0},...,a_{n-1})\in F_{2}^{n}}$ ייקרא קוד גופא אם מתקיים

${\displaystyle R_{a}(z)\triangleq \sum _{j=0}^{n-1}\alpha _{j}(z-\alpha _{j})^{-1}\equiv 0{\text{ mod }}g(z)}$

הביטוי ${\displaystyle (z-\alpha _{j})^{-1}}$ קיים מאחר ש-${\displaystyle F_{2^{m}}/g(z)}$ הוא שדה. והמעלה ${\displaystyle t}$ של הפולינום מהווה גבול תחתון ליכולת תיקון השגיאות של הקוד. הקוד המתואר ליניארי ולו ממד ${\displaystyle k\geq n-tm}$ וכן מרחק מינימלי של ${\displaystyle 2t+1}$ לפחות לכן ניתן לשחזר עד ${\displaystyle t}$ שגיאות.

אם ${\displaystyle a}$ הוא מילת קוד של ${\displaystyle \Gamma (L,g)}$ ואם ${\displaystyle b=a+e}$ עם ${\displaystyle e\in F_{2}^{n}}$ בעל מרחק המינג ${\displaystyle t}$ או פחות, המילים ${\displaystyle a}$ ו-${\displaystyle e}$ ייחודיים בגלל ${\displaystyle b}$. קיים פולינום מתוקן יחיד ${\displaystyle \sigma (z)}$ ב-${\displaystyle F_{2^{m}}}$ ממעלה לכל היותר ${\displaystyle t}$ המקיים

${\displaystyle \sigma (z)R_{b}(z)\equiv \omega (z){\text{ mod }}g(z)}$

כאשר ${\displaystyle \omega (z)}$ הוא פולינום ב-${\displaystyle F_{2^{m}}}$ ממעלה לכל היותר ${\displaystyle t-1}$. לפולינום ${\displaystyle \sigma (z)}$ יש בדיוק ${\displaystyle t}$ שורשים ב-${\displaystyle L}$ המתאימים לפוזיציות המכילות אחד בווקטור השגיאה ${\displaystyle e}$. תהליך הפענוח כולל את הפעולות הבאות:

• חישוב קוד גופה ${\displaystyle R_{b}(z){\text{ mod }}g(z)}$,
• פתרון נוסחת המפתח ${\displaystyle \sigma (z)R_{b}(z)\equiv \omega (z){\text{ mod }}g(z)}$,
• חישוב השורשים של ${\displaystyle \sigma (z)}$.

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

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

גודל המפתח הציבורי הוא כנראה חסרונה הגדול של המערכת והוא ${\displaystyle kn}$ כאשר ${\displaystyle k}$ הוא אורך המידע המיועד להצפנה ו-${\displaystyle n}$ הוא אורך הבלוק המוצפן. למשל לפי הפרמטרים המקוריים שהוצעו על ידי מקאליס גודל המפתח הציבורי הוא 536,576 סיביות. סנדריר הציע^[5] להפחית מגודל המפתח הציבורי בשיטה סיסטמטית. כלומר ${\displaystyle G=(I|U)}$ כאשר ${\displaystyle I}$ הוא מטריצת היחידה ${\displaystyle k\times k}$ ו-${\displaystyle U}$ הוא מסדר ${\displaystyle k\times (n-k)}$. כך גודל המפתח מצטמצם ל-${\displaystyle k(n-k)}$ סיביות כי יש צורך לאחסן רק את הצד הימני (${\displaystyle U}$), אך עדיין המפתח יהיה די גדול (בערך 262,000 סיביות).

הצפנת מקאליס מבוססת על שתי בעיות קשות בתורת הקודים האחת היא מקרה פרטי של בעיית "פענוח סינדרומי" שהוכח שהיא NP-שלמה; בהינתן מטריצה בינארית מסדר ${\displaystyle r\times n}$ ו-${\displaystyle a}$ מילות קוד כלשהן ב-${\displaystyle F_{2}^{r}}$ הבעיה היא למצוא מילה ${\displaystyle e}$ ב-${\displaystyle F_{2}^{n}}$ במשקל נמוך או שווה ל-${\displaystyle r/{\text{log}}_{2}n}$ כך שמתקיים ${\displaystyle He^{T}=s}$ כאשר ${\displaystyle s}$ הוא הסינדרום. הוכח על ידי ברלקמפ, מקאליס וטילבורג שהבעיה NP-קשה^[6].

והבעיה שנייה היא בעיית זיהוי 'קוד גופא', כלומר בהינתן מטריצה בינארית מסדר ${\displaystyle r\times n}$ לענות על השאלה האם היא מטריצת גופה. אפשר לתקוף את סכימת מקאליס בשתי דרכים. אחת היא 'התקפה מבנית' בה מנסים לשחזר את המפענח של הקוד הנוצר על ידי המפתח הציבורי ${\displaystyle G^{*}}$ ומשם לשחזר את המפתח הפרטי ${\displaystyle G}$, אם היא מצליחה המערכת נפרצת לחלוטין. אפשר לסווג קודי שגיאות למחלקות שקילות, שני קודים באורך זהה ייקראו שקולים (שההפרש ביניהם הוא מילת קוד) אם קיימת בדיוק תמורה אחת באורך ${\displaystyle n}$ המשנה קוד אחד לשני לכן הקוד ${\displaystyle C'}$ שנוצר על ידי ${\displaystyle G^{*}}$ והקוד הנוצר על ידי ${\displaystyle G}$ נקראים שקולים. בהתקפה זו התוקף מנסה להשוות בין קודים כדי למצוא שקילות. אם נמצאה שקילות אפשר לשחזר את התמורה ביניהם על ידי אלגוריתם פולינומי שנקרא Support Splitting Algorithm (של ניקולס סנדריר 1999). תהליך זה הוא מעבר ליכולת הטכנולוגית הנוכחית עם הפרמטרים המקוריים של מקאליס כי התקפה מבנית מסוג זה דורשת בערך ${\displaystyle 2^{466}}$ קודים כדי שתצליח. בהתקפה השנייה שנקראת התקפת פענוח התוקף מנסה לנחש את פענוח הקוד מבלי לפרוץ את המערכת עצמה. ההתקפה תלויה בפרמטרים של קוד תיקון השגיאות ${\displaystyle C'}$, אורכו, הממד שלו ויכולת תיקון השגיאות (${\displaystyle t}$). לפי הפרמטרים המקוריים של מקאליס התקפה כזו תתבצע עם ${\displaystyle 2^{64}}$ פעולות בינאריות. מספר זה נמוך בהשוואה ליכולת הטכנולוגית הנוכחית אך הבעיה היא שכדי להעלות מספר זה יש צורך להגדיל את הפרמטרים וכיוון שהמפתח הציבורי מאוד גדול גם ככה זו בעיה.

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

• אתר האינטרנט הרשמי של הצפנת מקאליס
• אנציקלופדיה לקריפטוגרפיה ואבטחה, הוצאת שפרינגר, 2005