בעיית לוגריתם דיסקרטי

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

בעיית לוגריתם דיסקרטי - Discrete Logarithm Problem. היא בעיה באלגברה מופשטת, במתמטיקה. לוגריתם דיסקרטי (בדיד) מקביל ללוגריתם רגיל, אך בחבורות. הבעיה הכללית, היא מציאת לוגריתמים בחבורה כפלית סופית $\ G$ מסדר $\ p$ (המכילה $\ p - 1$ שלמים) עם יוצר $\ \alpha$ , כאשר פעולות כפל נעשות מודולו $\ p$ . בעיה זו דומה לבעיית פירוק לגורמים, במובן ששתיהן קשות (לא ידוע על אלגוריתם יעיל לפתרון בעיות אלו).

[עריכה] הגדרה כללית

בעיית לוגריתם דיסקרטי הכללית היא כדלהלן: תהי $\ G$ חבורה סופית ציקלית מסדר $\ n$ . יהי $\ \alpha$ יוצר של $\ G$ ויהי $\ \beta\in G$ . בעיית לוגריתם דיסקרטי של $\ \beta$ בבסיס $\ \alpha$ המיוצגת: $\ \mbox{log}_{\alpha}\beta$ , היא שלם ייחודי $\ x$ , כאשר $\ 0\le x\le n-1$ , המקיים $\ \beta = \alpha^{x}$ (מודולו $\ n$ ). במילים, מציאת החזקה $\ x$ שאם מעלים בה את $\ \alpha$ ומצמצמים מודולו $\ n$ , מתקבל $\ \beta$ . בגלל הצמצום המודולרי ב- $\ n$ , ישנם למעשה אינסוף אפשרויות לפתרון המשוואה. המטרה היא למצוא את השלם החיובי, הקטן ביותר המקיים את המשוואה $\ \beta=\alpha^{x}$ .

ההגדרה של יוצר בחבורות היא: אם $\ \alpha \in \mathbb{Z}^{*}_n$ והסדר של $\ \alpha$ (מספר האלמנטים) הוא $\ \phi(n)$ , אזי $\ \alpha$ נקרא יוצר או אלמנט פרימיטיבי של $\ \mathbb{Z}^{*}_n$ . במקרה זה $\ \mathbb{Z}^{*}_n$ מכונה חבורה ציקלית. ל- $\ \mathbb{Z}^{*}_n$ יש יוצר אך ורק אם $\ n$ הוא ראשוני או חזקה של מספר ראשוני.

[עריכה] דוגמה

אם $\ p = 97$ . אזי $\ \mathbb{Z}^*_{97}$ היא חבורה ציקלית מסדר $\ n = 96$ . אם ניקח יוצר של $\ \mathbb{Z}^*_{97}$ למשל $\ \alpha=5$ . בהינתן השלם $\ 35$ , הבעיה היא למצוא $\ x$ המקיים $5^x \equiv 35 (\mbox{ mod } 97)$ , היות ש- $\ 5^{32} \equiv 35 (\mbox{mod } 97)$ , אזי $\ \mbox{log}_{5}35 = 32$ ב- $\ \mathbb{Z}^*_{97}$ .

[עריכה] תכונות

אם $\ \alpha$ הוא יוצר של חבורה ציקלית $\ G$ מסדר $\ n$ ו- $\ \beta,\gamma \in G$ . אז

$\ \mbox{log}_{\alpha}(\beta\gamma) = \mbox{log}_{\alpha}\beta + \mbox{log}_{\alpha}\gamma \mbox{ mod } n$

וכן

$\ \mbox{log}_{\alpha}(\beta^{\,s}) = s\, \mbox{log}_{\alpha}\beta \mbox{ mod } n$ עבור שלם $\ s$ כלשהו.

הקושי שבבעיית לוגריתם דיסקרטי הכללית, אינו תלוי ביוצר. הווה אומר, אם $\ \alpha$ ו- $\ \gamma$ הם יוצרים של $\ G_n$ . ואם $\ x = \mbox{log}_{\alpha}\beta$ וכן $\ y = \mbox{log}_{\gamma}\beta$ ו- $\ z = \mbox{log}_{\alpha}\gamma$ .

אזי

$\ \alpha^x = \beta = \gamma^y = (\alpha^z)^y$ .

על כן:

$\ x = zy \mbox{ mod } n$

וכן,

$\ \mbox{log}_\gamma\beta = (\mbox{log}_{\alpha}\beta)(\mbox{log}_{\alpha}\gamma)^{-1} \mbox{ mod } n$ .

משמעות הדבר היא, שכל אלגוריתם המסוגל לחשב לוגריתמים בבסיס $\ \alpha$ ניתן לשימוש כדי לחשב את הלוגריתמים בכל בסיס אחר שגם הוא יוצר של $\ G$ .

הגדרה קשה יותר של הבעיה האמורה, היא כאשר $\ G$ אינה חבורה ציקלית וכן הבסיס $\ \alpha$ אינו יוצר בהכרח של $\ G$ . בעיה זו קשה אף יותר לפתרון.

[עריכה] אלגוריתמים

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

Baby-step giant step.
אלגוריתם Pollard's rho.
אלגוריתם פוליג-הלמן (Pohlig-Hellman).
אלגוריתם Index calculus.

האחרון הנו האלגוריתם החזק ביותר הידוע כיום לפתרון בעיית לוגריתם דיסקרטי בחבורות מסוימות כמו $\ \mathbb{Z}^*_n$ עבור $\ n$ פריק כלשהו. גרסה מסוימת שלו הנקראת אלגוריתם Coppersmith מסוגלת להגיע לזמן ריצה של $\ L_ {2^m}\left[ \frac{1}{3}, c \right]$ עבור קבוע כלשהו $\ c < 1.587$ .

[עריכה] לוגריתם דיסקרטי בקריפטוגרפיה

החבורות שיש בהן עניין מבחינה קריפטוגרפית הן, החבורה הכפלית $\ \mathbb{F}^*_q$ מעל שדה הסופי $\ \mathbb{F}_q$ . במיוחד החבורה הכפלית $\ \mathbb{Z}^*_p$ של השלמים מודולו ראשוני $\ p$ גדול וכן החבורה הכפלית $\ \mathbb{F}^*_{2^m}$ מעל השדה המורחב $\ \mathbb{F}_{2^m}$ עם מציין 2. כן יש עניין מיוחד בחבורה $\ \mathbb{Z}^*_n$ כאשר $\ n$ שלם פריק, קבוצת הנקודות בעקומה אליפטית המוגדרת מעל שדה סופי ועקומה היפר-אליפטית המוגדרת מעל שדה סופי.

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

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

מקור: http://he.wikipedia.org../../../%D7%91/%D7%A2/%D7%99/%D7%91%D7%A2%D7%99%D7%99%D7%AA_%D7%9C%D7%95%D7%92%D7%A8%D7%99%D7%AA%D7%9D_%D7%93%D7%99%D7%A1%D7%A7%D7%A8%D7%98%D7%99.html

קטגוריות: מתמטיקה | תורת החבורות