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

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

מי שמעוניין לראות סקירה רחבה של התחום כולו, יוכל לרפרף על הספרים

M. Gonzalez-Vasco, R. Steinwandt, Group Theoretic Cryptography, Cryptography and Network Security Series, Chapman and Hall/CRC Press, 2015.
A. Myasnikov, V. Shpilrain, A. Ushakov, Non-commutative Cryptography and Complexity of Group-theoretic Problems, American Mathematical Society Surveys and Monographs 177, 2011.

שני הספרים נמצאים בספריה, ומן הסתם גם אפשר להורידם מ library genesis.

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

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

פונקציית תימצות מבוססת גרפי קיילי

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

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

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

להלן כמה דוגמאות קונקרטיות לתחילת התנסות ומחקר (חלקן כבר פתרנו במפגש). כולן של מטריצות משולשיות עליונות ב $\operatorname{SL}_2(\mathbb{F})$, כאשר $\mathbb{F}$ שדה סופי שגודלו חזקה של 2. המטריצות הן מהצורה \[ .A_0 := \begin{pmatrix} a & b\\ 0 & a^{-1} \end{pmatrix}, A_1 := \begin{pmatrix} c & d\\ 0 & c^{-1} \end{pmatrix} \] מוצע לבחון מקרים מיוחדים, בהם חלק מהפרמטרים מוגבלים למשהו פשוט, והאחרים אקראיים. להלן כמה דוגמאות. אתם מוזמנים להמציא ולבחון עוד דוגמאות.

$ a=c=1 $: $ \begin{pmatrix} 1 & b\\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & d\\ 0 & 1 \end{pmatrix} $.
$ a=c $: $ \begin{pmatrix} a & b\\ 0 & a^{-1} \end{pmatrix}, \begin{pmatrix} a & d\\ 0 & a^{-1} \end{pmatrix} $.
$ a=1, b=d $: $ \begin{pmatrix} 1 & b\\ 0 & 1 \end{pmatrix}, \begin{pmatrix} c & b\\ 0 & c^{-1} \end{pmatrix} $.
$ b=d=1, c=a^{-1} $: $ \begin{pmatrix} a & 1\\ 0 & a^{-1} \end{pmatrix}, \begin{pmatrix} a^{-1} & 1\\ 0 & a \end{pmatrix} $.
$ b=d=1 $: $ \begin{pmatrix} a & 1\\ 0 & a^{-1} \end{pmatrix}, \begin{pmatrix} c & 1\\ 0 & c^{-1} \end{pmatrix} $.
$ b=d, c=a^{-1} $: $ \begin{pmatrix} a & b\\ 0 & a^{-1} \end{pmatrix}, \begin{pmatrix} a^{-1} & b\\ 0 & a \end{pmatrix} $.
$ b=d $: $ \begin{pmatrix} a & b\\ 0 & a^{-1} \end{pmatrix}, \begin{pmatrix} c & b\\ 0 & c^{-1} \end{pmatrix} $.

רעיון חדש לפונקציית תימצות: TS-Hash

להלן רעיון לפונקציית תימצות, שלא דורש כל ידע קודם. היש דרך למצוא התנגשויות קצרות?

נקבע וקטור שורה אקראי $v_0\in(\mathbb{Z}_2)^n$. נקבע עוד שני וקטורי שורה אקראיים $v_1,v_2\in(\mathbb{Z}_2)^n$, מבין כל הוקטורים שהרכיב האחרון שלהם הוא 1.

לכל $ i=1,2 $ נגדיר טרנספורמציה לינארית $ T_i\colon (\mathbb{Z}_2)^n \to (\mathbb{Z}_2)^n $ בצורה הבאה: \[ T_i(x_1,\dots,x_n) := (x_2,\dots,x_n,0)+x_1v_i \] עבור וקטור שונה מאפס $ (x_1,\dots,x_n)\in (\mathbb{Z}_2)^n $ נגדיר את ההזזה שלו כך: \[ \text{Shift}(x_1,\dots,x_n) := (x_k,x_{k+1},\dots, x_n,0,\dots,0), \] כאשר $ k=\min\{\, i : x_i\neq 0\} $. פונקציית התימצות מוגדרות כך: \[ h(b_1,b_2,\dots,b_N) := T_{b_N}\circ \text{Shift}\circ T_{b_{N-1}}\circ \text{Shift}\circ \cdots \circ T_{b_1}\circ \text{Shift}(v_0). \] בעיית המחקר הזאת מעניינת במיוחד מפני שהיא משתמשת ברכיב הנדסי סטנדרטי, בעל מימושים יעילים בארכיטקטורות רבות. במידה שהשאלה תתברר קלה מדיי, אפשר לנסות להציע ולנתח וריאציות שלה.

למי שמעוניין, להלן פסאודו-קוד של הפונקציה בשפה דמויית C, כאשר ההנחה היא שהוקטור כולו מוחזק במילת מחשב אחת. כדי לקבל חוזק קריפטוגרפי, נדרש $n\ge 128$ ואז יש לממש זאת בעזרת שירשור מילות מחשב. אפשר גם לבחור בזהירות פרמטרים שאינם אקראיים לגמרי ויותר יעילים למימוש כאשר לא הכל נכנס במילה אחת. גם זה מתאים למחקר בנושא (איתור מחלקות של מקרים שאינם בטוחים מבין היישומים היעילים ביותר).



word Shift(word v) { //assumes v!=0
  if ( v == 0 )
    exit(-1); //error!
  while ( (v&1) == 0 )
    v >>= 1;
  return v;
}

word Hash(bit s[N]) {
  word T[2] = [v1, v2];
  word v = v0;
  for (i = 0; i < N; i++)
    v = (Shift(v)>>1)^T[b];
  return v;
}

בעיית הצמידות המרובה ב Right-angled Artin groups

בעיה זו דורשת היכרות בסיסית של The conjugacy problem in subgroups of right-angled Artin groups תמצאו את פתרון בעיית הצמידות הרגילה. המטרה כאן היא להכליל את הפתרון לבעיית הצמידות המרובה, שהיא הבעיה הבאה: נתונים איברים $ g_1,\dots,g_k,h_1,\dots,h_k\in G $. יש לקבוע האם קיים איבר $ x\in G $ שעבורו \[ (x^{-1}g_1x,\dots,x^{-1}g_kx)=(h_1,\dots,h_k). \] על מקורה של בעיית הצמידות המרובה בהצפנה, וחשיבותה לתחום, תוכלו ללמוד מפרקים 1 ו 2 במאמר הזה.

תקיפת הרחבה של מערכת RSA

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

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

Recycled Carpentry