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

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

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

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

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

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

המימוש הפשוט ביותר לבעיה הזו הוא כאשר החבורה G היא תת-חבורה של חבורת אוילר . אם n שווה לחזקה של מספר ראשוני אי-זוגי, או לפעמיים חזקה כזו, או ל-2 או 4, אז חבורת אוילר עצמה היא ציקלית, ויש לה איבר פרימיטיבי. אבל הבעיה בעינה עומדת גם אם יוצר תת-חבורה אמיתית של חבורת אוילר.

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

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

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

אם הוא יוצר של חבורה ציקלית מסדר ו- . אז

וכן
עבור שלם כלשהו.

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

אזי
.
על כן:
וכן,
.

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

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

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

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

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

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

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

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

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

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