הצפנת מקאליס

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

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

הגדרות כלליות

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

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

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

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

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

דוגמה במספרים קטנים

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

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

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

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

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}}

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

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}}

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}}

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

mG^{*}=(1,1,1,1,0,1,0,0,0,1,1,1)

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

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

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

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

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

mSG=(1,1,0,1,1,1,1,0,1,1,0,0)

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

[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}}

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

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)

.

קוד גופא בינארי

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

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

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

פענוח אלגברי של קוד גופה

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

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

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

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

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

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

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

גודל מפתחות

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

ביטחון

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

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

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

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

קישורים חיצוניים

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

הערות שוליים

^ A Public-Key Cryptosystem Based On Algebraic Coding Theory
^ Niederreiter, H. (1986). “Knapsack-type cryptosystems and algebraic coding theory.” Prob. Contr. Inform. Theory, 15 (2), 157–166.
^ Sidel’nikov, V.M. (1994). “A public-key cryptosystem based on Reed-Muller codes.” Discrete Mathematics and Applications, 4 (3), 191–207.
^ Courtois. N., M. Finiasz, and N. Sendrier (2001). “How to achieve a McEliece-based digital signature scheme.” Advances in Cryptology—ASIACRYPT 2001, Lecture Notes in Computer Science, vol. 2248, ed. C. Boyd. Springer-Verlag, Berlin, 157–174.
^ Sendrier, N. (2002). “On the security of the McEliece public-key cryptosystem.” Information, Coding and Mathematics, eds. M. Blaum, P.G. Farrell, and H. van Tilborg. Kluwer, 141–163. Proceedings of Workshop honoring Prof. Bob McEliece on his 60th birthday.
^ Berlekamp, E.R., R.J. McEliece, and H.C. van Tilborg (1978). “On the inherent intractability of certain coding problems.” IEEETransactions on Information Theory, 24 (3), 384–386.
^ The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks

[1] A Public-Key Cryptosystem Based On Algebraic Coding Theory

[2] Niederreiter, H. (1986). “Knapsack-type cryptosystems and algebraic coding theory.” Prob. Contr. Inform. Theory, 15 (2), 157–166.

[3] Sidel’nikov, V.M. (1994). “A public-key cryptosystem based on Reed-Muller codes.” Discrete Mathematics and Applications, 4 (3), 191–207.

[4] Courtois. N., M. Finiasz, and N. Sendrier (2001). “How to achieve a McEliece-based digital signature scheme.” Advances in Cryptology—ASIACRYPT 2001, Lecture Notes in Computer Science, vol. 2248, ed. C. Boyd. Springer-Verlag, Berlin, 157–174.

[5] Sendrier, N. (2002). “On the security of the McEliece public-key cryptosystem.” Information, Coding and Mathematics, eds. M. Blaum, P.G. Farrell, and H. van Tilborg. Kluwer, 141–163. Proceedings of Workshop honoring Prof. Bob McEliece on his 60th birthday.

[6] Berlekamp, E.R., R.J. McEliece, and H.C. van Tilborg (1978). “On the inherent intractability of certain coding problems.” IEEETransactions on Information Theory, 24 (3), 384–386.

[7] The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks

[1]

[2]

[3]

[4]

[5]

[6]

[7]