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

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

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

הגדרה כללית

בעיית לוגריתם דיסקרטי הכללית היא כדלהלן: תהי $\ G$ חבורה סופית ציקלית מסדר $\ n$. יהי $\ \alpha$ יוצר של $\ G$ ויהי $\ \beta \in G$. בעיית לוגריתם דיסקרטי של $\ \beta$ בבסיס $\ \alpha$ המיוצגת: $\ {\mbox{log}}_{\alpha }\beta$, היא מציאת שלם ייחודי $\ x$, כאשר $\ 0\leq x\leq 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\leq i\leq \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\geq 1$ וכן החבורה הכפלית $\ \mathbb {F} _{2^{m}}^{*}$ מעל שדה בינארי $\ \mathbb {F} _{2^{m}}$ עם מציין 2. כן יש עניין מיוחד בחבורה $\ \mathbb {Z} _{n}^{*}$ כאשר $\ n$ שלם פריק, קבוצת הנקודות בעקומה אליפטית המוגדרת מעל שדה סופי ועקומה היפר-אליפטית המוגדרת מעל שדה סופי.