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

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

בעיית הלוגריתם הדיסקרטי היא בעיה באלגברה חישובית, שמהותה מציאת החזקה 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$ ומצמצמים מודולו $\ 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$ בחזקת מספרים שונים בסדר עולה, עד שימצא המספר העונה על התנאי האמור, דרך זו מכונה כוח גס וזמן הריצה שלה מעריכי ביחס לסדר החבורה $\ 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$ שלם פריק, קבוצת הנקודות בעקומה אליפטית המוגדרת מעל שדה סופי ועקומה היפר-אליפטית המוגדרת מעל שדה סופי.