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

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

בעיית הלוגריתם הדיסקרטי היא בעיה באלגברה חישובית, שמהותה מציאת המעריך \ x של הערך \ \alpha^x, כאשר \ \alpha איבר בחבורה; זאת בדומה לפונקציית הלוגריתם הרגילה, המחשבת את \ x כאשר \ \alpha מספר ממשי.

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

הגדרה כללית[עריכת קוד מקור | עריכה]

בעיית לוגריתם דיסקרטי הכללית היא כדלהלן: תהי \ 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 בחזקת \ x ומצמצמים מודולו \ n, מתקבל \ \beta. בגלל הצמצום המודולרי ב-\ n, ישנם למעשה אינסוף אפשרויות לפתרון המשוואה. המטרה היא למצוא את השלם החיובי, הקטן ביותר המקיים את המשוואה \ \beta=\alpha^{x}.

יוצר בחבורה הוא איבר בחבורה שהחזקות שלו מרכיבות את החבורה כולה. אם \ \alpha \in \mathbb{Z}^{*}_n והסדר של \ \alpha דהיינו השלם \ t המקיים \ a^t \equiv 1\ (\mbox{mod }n) שווה \ \phi(n) (פונקציית אוילר), אזי \ \alpha נקרא יוצר או איבר פרימיטיבי של \ \mathbb{Z}^{*}_n ומסמנים זאת \ \mathbb{Z}^*_n=\{\alpha^i \mbox{ mod }n \ | \ 0 \le i \le \phi(n)-1 \}. במקרה זה החבורה \ \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 בחזקת מספרים שונים בסדר עולה, עד שימצא המספר העונה על התנאי האמור, דרך זו מכונה כוח גס וזמן הריצה שלה מעריכי ביחס לאורך הייצוג של סדר החבורה (\ \log(n)). בין האלגוריתמים הטובים ביותר הידועים לפתרון בעיה זו נמנים:

  • Baby-step giant step.
  • אלגוריתם Pollard's rho.
  • אלגוריתם פוליג-הלמן (Pohlig-Hellman).
  • אלגוריתם תחשיב האינדקסים.

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

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

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

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

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