הצגת המקור של הדף "הצפנה לא-קומוטטיבית"

'''הצפנה לא-קומוטטיבית''' (ב[[אנגלית]]: Noncommutative Cryptography) היא תת-תחום של [[הצפנה]] המשתמש בכלים מ[[תורת החבורות]] ה'''לא'''-[[פעולה קומוטטיבית|קומוטטיבית]] כדי להציג [[פרוטוקול קריפטוגרפי|פרוטוקולי הצפנה]]. זהו תחום המשלב שלושה תחומים מ[[מתמטיקה]] ו[[מדעי המחשב]] - [[תורת החבורות הקומבינטורית]], [[קריפטוגרפיה]] ו[[סיבוכיות]]. המחקר בתחום גם תורם לתורת החבורות כתחום בפני עצמו.

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

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

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

===פרוטוקול Ko-Lee===
מידע ציבורי: חבורה <math>G</math> ושתי תתי-חבורות <math>A,B \le G</math> שאיבריהם מתחלפים (היינו <math>\forall a \in A , b \in B : ab = ba</math>).
# אליס בוחרת באקראי איבר <math>a \in A</math> ושולחת אל בוב את <math>a^{-1} g a</math>.
# בוב בוחר באקראי איבר <math>b \in B</math> ושולח אל אליס את <math>b^{-1} g b</math>.
# המפתח המשותף שלהם הוא <math>(ab)^{-1} g (ab) = (ba)^{-1} g (ba)</math>.

===פרוטוקול Anshel-Anshel-Goldfeld===
מידע ציבורי: איברים <math>a_1, \dots , a_n, b_1, \dots, b_m \in G</math>.
# אליס בוחרת מילה <math>x</math> באיברים <math>a_1, \dots , a_n</math>, ושולחת אל בוב את האיברים <math>x^{-1} b_1 x, \dots x^{-1} b_m x</math>.
# בוב בוחר מילה <math>y</math> באיברים <math>b_1, \dots , b_m</math>, ושולח אל אליס את האיברים <math>y^{-1} a_1 y, \dots y^{-1} a_n y</math>.
# המפתח המשותף הוא ה[[קומוטטור]] <math>[x,y] = x^{-1} y^{-1} x y</math>.

בוב ואליס אכן יכולים לחשב את הקומוטטור - למשל אליס יודעת את המבנה של המילה <math>x</math> שבחרה, ולכן יכולה לחשב את <math>y^{-1} x y</math> (כי היא יודעת את ההצמדה של כל היוצרים), ואז להכפיל ב-<math>x^{-1}</math> משמאל ולקבל את הקומוטטור.

===פרוטוקול Shpilrain-Ushakov===
מידע ציבורי: חבורה <math>G</math>, איבר <math>g \in G</math>. ושתי תתי-חבורות <math>A,B \le G</math> שאיבריהם מתחלפים.
# אליס בוחרת איברים <math>a_1 \in A , b_1 \in B</math> ושולחת <math>a_1 g b_1</math>.
# בוב בוחר איברים <math>a_2 \in A , b_2 \in B</math> ושולח <math>b_2 g a_2</math>.
# המפתח המשותף הוא <math>a_1 b_2 g b_1 a_2</math>.

חבורה ספציפית שהוצעה על ידי המחברים היא [[חבורת תומפסון]], ראו בהמשך לפרטים.

===פרוטוקול שלושת המעברים של Shamir===
פרוטוקול זה הוא פרוטוקול שליחת מפתח (Key transport protocol), כלומר פרוטוקול בו אחד הצדדים מעביר מפתח אל האחר (הם לא מחליפים מפתח ביניהם). הפרוטוקול נקרא על שמו של [[עדי שמיר]].

מידע ציבורי: חבורה <math>G</math> ושתי תתי-חבורות <math>A,B \le G</math> שאיבריהם מתחלפים. כדי לשלוח מילה <math>W</math> אל אליס, בוב ואליס יפעלו כך:
# בוב בוחר שני איברים <math>X_1, X_2 \in A</math> ושולח אל אליס את האיבר <math>X_1 W X_2</math>.
# אליס בוחרת שני איברים <math>Y_1, Y_2 \in B</math> ושולחת אל בוב את האיבר <math>Y_1 X_1 W X_2 Y_2</math>.
# בוב מכפיל בהפכיים של האיברים שלו ושולח אל אליס: <math>X_1^{-1}(Y_1 X_1 W X_2 Y_2)X_2^{-1}=Y_1 W Y_2</math> (בגלל החילופיות).
# אליס מכפילה בהפכיים של האיברים שלה, ומקבלת את המפתח: <math>Y_1^{-1}(Y_1W Y_2)Y_2^{-1} = W</math>.

==סיבות בטיחות==
בטיחות הפרוטוקולים השונים לעיל תלויה בקיומם את הבעיות הבאות:
* [[בעיית חיפוש המצמיד]] (Conjugator Search Problem)- בבעיה זו, שואלים האם בהינתן שני האיברים: <math>h=x^{-1} g x , g</math>, ניתן למצוא איבר <math>y</math> ש[[הצמדה (תורת החבורות)|יצמיד]] את <math>g</math> אל <math>h</math>, כלומר כך ש-<math>y^{-1} g y = h</math>. לעיתים דורשים תנאים נוספים על המצמיד, למשל שהוא יבוא מתת-חבורה נתונה כלשהי, כמו בפרוטוקולים לעיל. סיבת הבטיחות בפרוטוקולים רבים היא בדיוק בעיית חיפוש המצמיד, ועל כן יש לבחור חבורות בהן '''הבעיה קשה'''.

גרסה נוספת של הבעיה היא ''בעיית חיפוש המצמיד הסימולטני''' - בהינתן ההצמדות <math>x^{-1} g_1 x , \dots , x^{-1} g_n x</math> והאיברים <math>g_1, \dots, g_n</math>, למצוא את המצמיד <math>x</math>. בבעיה זו ניתן יותר מידע, ויש בה שימוש למשל בפרוטוקול AAG' אך גם היא מתגלה כקשה מספיק בפלטפורמות הנכונות.

* בעיית הפירוק (Decomposition Problem)- בעיה זו ניתן לנסח גם בתורה הקומוטטיבית. ניסוח הבעיה הוא: בהינתן שני האיברים <math>h= x g y , g</math>, למצוא איברים <math>a_1 , a_2 </math> מתוך חבורה נתונה מראש <math>A</math>, כך ש-<math>a_1 g a_2 = h</math>. בעיה זו היא הסיבה לבטיחות של פרוטוקול Shpilrain-Ushakov.

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

===תכונות שהחבורות צריכות לקיים===
פרט לדרישה שבחבורות לא יהיו פתרונות פשוטים לבעיות לעיל, יש לדרוש כי לחבורה תהיה בעיית מילה פשוטה.

[[בעיית המילה (תורת החבורות)|בעיית מילה]] - '''בעיית המילה''' היא בעיית ההכרעה, בה יש להכריע האם שתי מילים בחבורה <math>w,w'</math> הנתונות בהצגות שונות הן זהות. לכל חבורה התממש פרוטוקול כלעיל, '''חייבת להיות בעיית מילה פתירה ביעילות''' - שכן על שני הצדדים להחליף איברים בעלי הצגות שונות, אך בסופו של דבר להחזיק באותו האיבר.

====צורה נורמלית====
אחת הדרכים הנפוצות לפתור את בעיית המילה והעברת איברי חבורות אבסטרקטיות בצורה יעילה היא הצגת '''[[צורה נורמלית (תורת החבורות)|צורה נורמלית]]''' (Normal Form) עבור החבורה. זוהי תבנית בה ניתן להציג את כל איברי החבורה באופן יחיד. בהינתן צורה נורמלית יעילה, בעיית המילה פתירה בקלות - בהינתן שתי מילים, מחשבים את הצורה הנורמלית של כל אחת מהן ובודקים האם מתקבלת אותה צורה. מציאת צורה נורמלית תלויה במידה רבה במבנה החבורה ואיברים מיוחדים.

כעת, כשאמרנו לעיל 'יש לשלוח את האיבר...', מה שבאמת שולחים הוא '''צורה נורמלית של האיבר'''. אם בוחרים חבורה טובה אפשר לחשב אותה ביעילות, לעיתים קל להכפיל איברים בעזרתה, וקל לזהות שתי מילים בעזרתה.

עם זאת, לעיתים צורות נורמליות נותנות יותר מדי מידע ומהוות פרצה להתקפות, כדוגמת [[התקפה מבוססת אורך|התקפות מבוססות אורך]] או התקפות על בעיית הפירוק.

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

===דוגמאות===
כעת יוצגו מספר דוגמאות קלאסיות וספציפיות, ויוסבר בקצרה מדוע הן מתאימות לפרוטוקולים לעיל.

====חבורת הצמות====
{{ערך מורחב|חבורת הצמות#חבורת הצמות והצפנה}}
אחת החברות שעלו כמומעד טבעי לפרוטוקולים לעיל היא [[חבורת הצמות]]. לחבורה זו [[חבורת הצמות#צורה נורמלית|שתי צורות נורמליות]] יעילות, מבניות ונוחות במיוחד, וכן בעיית חיפוש המצמיד בה נחשבת לקשה. יש בה גם חבורות גדולות המתחלפות איבר איבר. לחבורה זו יש גם [[הצגה ליניארית]], ולכן יש דרך נוספת לפתור את בעיית המילה ולהכפיל ולשלוח את איבריה.

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

====חבורות ארטין====
{{ערך מורחב|חבורת ארטין#שימושים בהצפנה}}
[[חבורת ארטין|חבורות ארטין]] מהוות הכללה של חבורת הצמות: בהן יש יחסים בסגנון דומה לאלו של חבורת הצמות, אך חבורות ארטין יכולות להיות מסובכות יותר. הן הוצעו באופן טבעי לאחר שמספר התקפות נמצאו על חבורת הצמות.

[[חבורת ארטין#חבורת ארטין ישרת-זווית|משפחות מסוימות]] של חבורת ארטין הן [[חבורה ליניארית|ליניאריות]].

====חבורת תומפסון====
[[חבורת תומפסון]] גם היא חבורה בעלת שימושים במספר תחומים במתמטיקה, כמו [[טופולוגיה]] ו[[גאומטריה]]. יש לה את ה[[הצגה על ידי יוצרים ויחסים|הצגה]] האינסופית הבאה:
<center>
<math>\langle x_1, x_2, \dots \mid x_i^{-1} x_k x_i=x_{k+1}, k>i \rangle</math>
</center>
לחבורה זו יש גם הצגות סופיות, אך דווקא בעזרת ההצגה האינסופית הזו ניתן להציג צורה נורמלית שלה - כל איבר ניתן לרשום ביחידות בצורה <math>x_{i_1}\dots x_{i_t}x_{j_s}^{-1} \dots x_{j_1}^{-1}</math>, כאשר האינדקסים מסודרים בסדר עולה, ואם <math>x_,x_i^{-1}</math> שניהם מופיעים, אז גם <math>x_{i+1}</math> או <math>x_{i+1}^{-1}</math>. צורה זו ניתן לחשב בסיבוכיות זמן ריצה <math>O(|W| log |W|)</math>, כאשר <math>|W|</math> הוא אורך המילה הנתונה.

שתי תתי-חבורות מתחלפות של חבורת תומפסון שהוצעו על ידי המחברים הן: <math>A= \langle x_0 x_1^{-1}, \dots , x_0,x_s^{-1} \rangle , B = \langle x_{s+1},x_{s+2},\dots \rangle</math>.

====חבורות מטריצות====
חבורות [[מטריצה|מטריצות]] מעל [[חוג (מבנה אלגברי)|חוג]] חילופי סופי אף הן חבורות לא-קומוטטיביות שהוצעו במספר פרוטוקולים. הדרישה להיותו של חוג הבסיס קומוטטיבי וסופי היא כדי שיהיה אפשר להשתמש בבעיית הפירוק.

דוגמאות מפורשות הן [[חוג מטריצות]] מעל <math>\mathbb{n}</math> - אך צריך לבחור <math>n</math> גבוה במיוחד. הצעה נוספת היא להשתמש ב[[שדה סופי|שדות סופיים]], להן מימוש יעיל בהינתן [[פולינום אי פריק]] מהמעלה הרצויה. ניתן גם להשתמש בחוגים עם [[איבר נילפוטנטי|נילפוטנטים]], כדוגמת <math>F_p[x]/\langle x^n \rangle</math>.

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

==לקריאה נוספת==
<div class="mw-content-ltr">
*{{cite book|last1=Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov|title=Group-based Cryptography|date=2008|publisher=Birkhäuser Verlag|location=Berlin}}
*{{cite web|last1=Benjamin Fine|title=Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems|url=http://arxiv.org/pdf/1103.4093|year=2011}}
*{{cite web|last1=David Garber|title=Braid Group Cryptography|url=http://arxiv.org/pdf/0711.3941|year=2008}}
*{{cite web|last1=S.R. Blbackburn, C. Cid, C. Mullan|title=Group Theory In Cryptography|url=http://arxiv.org/pdf/0906.5545v2|year=2010}}
</div>

[[קטגוריה:תורת החבורות הקומבינטורית]]
[[קטגוריה:קריפטוגרפיה]]
[[קטגוריה:מפתח ציבורי]]