בעיית הלוגריתם הבדיד

באלגברה חישובית ובקריפטוגרפיה, בעיית הלוגריתם הבָּדִיד (דיסקרטי) המסומנת בקיצור DLP (באנגלית: Discrete Logarithm Problem), היא מציאת המעריך $x$ בהינתן הבסיס $g$ והתוצאה $h$ כך שמתקיים $h=g^x$. בקיצור $x={\log }_{g}h$. בניגוד ללוגריתם רגיל מעל המספרים הממשיים שאותו קל לחשב בשיטות המסתמכות על קירוב, קשה לחשב לוגריתם בדיד בקבוצה סופית של מספרים שלמים, מודולו שלם כלשהו הנקרא מודולוס. בעיית הלוגריתם הבדיד בחבורה ציקלית נחשבת כשני עשורים לבעיה מתמטית קשה והיא הבסיס למספר אלגוריתמים חשובים בהצפנת מפתח ציבורי כמו פרוטוקול דיפי-הלמן ואלגוריתם חתימה דיגיטלית DSA.

חבורה ציקלית

ערך מורחב – חבורה ציקלית

תהי $\mathbb{𝔾}$ חבורה סופית מסדר $m$. עבור כל אלמנט $g\in \mathbb{𝔾}$ הקבוצה הבאה:

$⟨g⟩=\{g^0,g^1,g^2,...\}$

היא תת-חבורה ציקלית של $\mathbb{𝔾}$ שהסדר שלה הוא השלם הקטן ביותר $i$ המקיים $g^i=1$. קל לראות שהרצף חוזר על עצמו כי $g^i=g^0$ וכן $g^{i+1}=g^1$ וכן הלאה. אם $m$ ראשוני אז $\mathbb{𝔾}$ היא צקלית וכל האלמנטים שלה הם יוצרים של החבורה. לעומת זאת סדר החבורה הכפלית ${\mathbb{\mathbb{Z}}}_p^{*}$ כאשר $p$ ראשוני אינו ראשוני. לדוגמה ${\mathbb{\mathbb{Z}}}_{15}^{*}$ לפי אוילר היא מסדר $(5-1)(3-1)=8$. רואים ש-2 אינו יוצר של החבורה כי $⟨2⟩=\{1,2,4,8\}$ לכן הסדר שלו הוא 4. כן רואים שלפי חוקי החבורות סדר תת-חבורה תמיד מחלק של סדר החבורה. אם $\mathbb{𝔾}$ היא חבורה ציקלית מסדר ראשוני $q$, קיים יוצר של החבורה $g\in \mathbb{𝔾}$ כך שמתקיים $\{g^0,g^1.g^2,...,g^{q-1}\}=G$ (למעשה יכולים להיות יוצרים רבים). במילים אחרות, עבור כל שלם $h\in \mathbb{𝔾}$ קיים שלם ייחודי $x\in \mathbb{𝔾}$ המקיים $g^x=h$. אם החבורה $\mathbb{𝔾}$ מובנת מההקשר קוראים ל-$x$ "הלוגריתם הבדיד" של $h$ בבסיס $g$ ואפשר לכתוב זאת בקיצור ${\log }_{g}h$. כמו כן אם $g^{x^{\prime }}=h$ עבור שלם כלשהו $x^{\prime }$ אז ${\log }_{g}h=x^{\prime }\text{ (mod }q)$. הסיבה שהלוגריתם נקרא כאן "בדיד" נובעת מהעובדה שהוא נלקח מעל חבורה סופית, זאת בניגוד ללוגריתם רגיל שטווח הערכים שלו הוא מעל קבוצה אין סופית.

חוקי הלוגריתמים

לוגריתם בדיד מציית לחוקי הלוגריתמים הרגילים. למשל, ${\log }_{g}1=0$ (כאשר '1' הוא איבר יחידה של $\mathbb{𝔾}$) וכן:

• ${\log }_g(h_1\cdot h_2)=({\log }_g{h}_1+{\log }_g{h}_2)\text{ mod }p$.
• ${\log }_g(h^y)=(y{\log }_{g}h)\text{ mod }p$ עבור שלם $y$ כלשהו.

הגדרה פורמלית

הגדרה פורמלית של בעיית הלוגריתם הבדיד היא:

נתונה חבורה ציקלית סופית מסדר $p$ המסומנת $G$ ונתון יוצר $g$ של החבורה ויהי $h\in G$ אלמנט כלשהו. מצא את הלוגריתם הבדיד של $h$ בבסיס $g$ בקיצור ${\log }_{g}h$ שהוא אלמנט יחידי $x$ בטווח $0\le x\le p-1$ המקיים: $h=g^x$.

ביתר פירוט, נתון אלגוריתם פולינומי יעיל ${𝒢}$ שמקבל את $1^n$ ומחזיר את החבורה $\mathbb{𝔾}$, הסדר שלה $q$ ויוצר $g\in \mathbb{𝔾}$. ונתון הניסוי הבא:

ניסוי לוגריתם בדיד ${\mathbf{𝐃}\mathbf{𝐋}\mathbf{𝐨}\mathbf{𝐠}}_{{𝒜},{𝒢}}\mathit{(}\mathit{n}\mathit{)}$:

1. מריצים את ${𝒢}(1^n)$ כדי לקבל את $(\mathbb{𝔾},q,g)$ כאשר $\mathbb{𝔾}$ היא חבורה ציקלית מסדר $q$ ו-$g$ הוא יוצר של $\mathbb{𝔾}$.
2. בוחרים אלמנט $h\leftarrow \mathbb{𝔾}$ (אפשר לעשות זאת על ידי בחירת אלמנט אקראי $x^{\prime }$ וחישוב $h=g^{x^{\prime }}$).
3. האלגוריתם ${𝒜}$ מקבל את $(\mathbb{𝔾},q,g,h)$ ומחשב את $x\in {\mathbb{\mathbb{Z}}}_q$.
4. הניסוי יוכתר בהצלחה אם $g^x=h$ אחרת היא נחשבת לכישלון.

בהגדרה פורמלית, אומרים שבעיית הלוגריתם הבדיד (המסומנת בקיצור DLP) קשה לפתרון ביחס ל-${𝒢}$ אם עבור כל אלגוריתם פולינומי הסתברותי ${𝒜}$ קיימת פונקצית זניחות $\text{negl}$ כך שמתקיים:

$\mathrm{Pr}[{\text{DLog}}_{{𝒜},{𝒢}}(n)=1]\le \text{ negl}(n)$

במילים, ההשערה היא שקיימת חבורה $\mathbb{𝔾}$ שבה בעיית DLP קשה לפתרון מבחינה חישובית למעט בהסתברות זניחה.

דוגמה במספרים קטנים

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

בעיית דיפי-הלמן

ויטפילד דיפי ומרטין הלמן פרסמו ב-1976 מאמר פורץ דרך שהעלה לראשונה את רעיון ההצפנה האסימטרית והציעו לבססה על בעיה מתמטית קשה בתורת המספרים הקשורה לבעיית הלוגריתם הבדיד שנקראת כיום בעיית דיפי-הלמן והיא מתחלקת לשתים, בעיית דיפי הלמן חישובית, המסומנת בקיצור CDH ובעיית הכרעת דיפי-הלמן המסומנת בקיצור DDH. שתיהן בעיות שלהן חשיבות רבה בתחום הקריפטוגרפיה. נתונה חבורה ציקלית $\mathbb{𝔾}$ ויוצר $g\in \mathbb{𝔾}$ ונתונים שני אלמנטים מהחבורה $h_1$ ו-$h_2$. פונקציית דיפי-הלמן מוגדרת כדלהלן:

${\text{DH}}_g(h_1,h_2)\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}{g}^{{\log }_g{h}_1\cdot {\log }_g{h}_2}$.

כלומר, אם $h_1=g^x$ ו-$h_2=g^y$ אז ${\text{DH}}_g(h_1,h_2)=g^{x\cdot y}=h_1^y=h_2^x$. הבעיה הראשונה, בעיית CDH היא לחשב את פונקציית דיפי-הלמן ${\text{DH}}_g(h_1,h_2)$ עבור שני אלמנטים אקראיים $h_1,h_2$ (כאשר $x$ ו-$y$ אינם ידועים אחרת הבעיה טריוויאלית). הבעיה השנייה DDH היא בעיית הכרעה, להבחין בין פלט הפונקציה ${\text{DH}}_g(h_1,h_2)$ לבין אלמנט אקראי כלשהו מהחבורה. במילים אחרות עבור אלמנטים $h_1,h_2$ שנבחרו באקראי ופתרון אפשרי $h^{\prime }$ הבעיה היא להכריע האם $h^{\prime }={\text{DH}}_g(h_1,h_2)$ או $h^{\prime }$ הוא אלמנט אקראי חסר משמעות.

אם בעיית הלוגריתם הבדיד קלה לפתרון אז אפשר לפתור גם את בעיית דיפי-הלמן, תחילה מחשבים את $x={\log }_g{h}_1$ ואז מחזירים את $h_2^x$. מאידך לא ברור האם קושייה המשוער של בעיית דיפי-הלמן שקול לבעיית הלוגריתם הדיסקרטי.

בעיית DDH נחשבת לבעיה קשה ביחס ל-${𝒢}$ אם עבור כל אלגוריתם הסתברותי פולינומי ${𝒜}$ קיימת פונקציית זניחות $\text{negl}$ כך שהמתקיים:

$|\mathrm{Pr}[{𝒜}(\mathbb{𝔾},q,g,g^x,g^y,g^z)=1-\mathrm{Pr}[{𝒜}(\mathbb{𝔾},q,g,g^x,g^y,g^{xy})=1]|\le \text{ negl}(n)$

כאשר $x,y,z$ הם אלמנטים אקראיים. אם $z$ נבחר באקראי מתוך ${\mathbb{\mathbb{Z}}}_q$ באופן בלתי תלוי בערכים אחרים אז האלמנט $g^z$ הוא בעל התפלגות אחידה ב-$\mathbb{𝔾}$.

ישנן מספר חבורות בהן בעיית הלוגריתם הבדיד ותאומה בעיית דיפי-הלמן קשות לפתרון. העדיפות היא לחבורה ציקלית מסדר ראשוני והסיבות הן ראשית משום שידוע שאם סדר החבורה אינו ראשוני אפשר לצמצם את בעיית הלוגריתם הבדיד לבעיה בתת-חבורות שלה שהן יותר קטנות ולכן הפתרון קל יותר. שנית, קל למצוא יוצר בחבורה מסדר ראשוני כי כל האלמנטים של החבורה הם יוצרים. בנוסף, קל יותר למצוא הופכי כפלי של מעריך כלשהו דבר שרצוי במבנים קריפטוגרפיים מסוימים ובעיקר הסיבה היא שזה הגיוני להשתמש בחבורה מסדר ראשוני כי אם הסדר ראשוני אפשר להוכיח שפלט הפונקציה ${\text{DH}}_g(h_1,h_2)$ הוא כמעט אקראי בהשוואה להתפלגות אחידה מעל $\mathbb{𝔾}$.

למרות זאת, החבורה הכפלית ${\mathbb{\mathbb{Z}}}_p^{*}$ עם ראשוני $p$ נפוצה בישומים מעשיים למרות שסדר החבורה הזו אינו ראשוני. ההשערה היא שבעיית הלוגריתם הבדיד בחבורה זו קשה גם היא בתנאי שמשתמשים בתת-חבורה מתאימה של ${\mathbb{\mathbb{Z}}}_p^{*}$. האלמנט $y\in {\mathbb{\mathbb{Z}}}_p^{*}$ הוא שארית ריבועית מודולו $p$ אם קיים אלמנט $x\in {\mathbb{\mathbb{Z}}}_p^{*}$ המקיים $x^2\equiv y\text{ (mod }p)$. כך שקבוצת כל השאריות הריבועיות היא תת-חבורה של ${\mathbb{\mathbb{Z}}}_p^{*}$. מחצית מהאלמנטים של החבורה ${\mathbb{\mathbb{Z}}}_p^{*}$ הם שאריות ריבועיות מודולו $p$. אם $p$ הוא מספר ראשוני "חזק", כלומר $p=2q+1$ כאשר $q$ ראשוני אז מספר האלמנטים בתת החבורה המכילה את כל השאריות הריבועיות מודולו $p$ הוא $(p-1)/2=q$ והיות ש-$q$ ראשוני תת-חבורה זו ציקלית. יתרה מזו כל האלמנטים בתת-חבורה זו הם יוצרים שלה. כדי למצוא יוצר, פשוט בוחרים אלמנט אקראי כלשהו $x$ שהתנאי הוא שלא יהיה שקול ל-$\pm 1$ (מודולו $p$) ואז מציבים $g=x^2$ מודולו $p$.

דוגמה במספרים קטנים

נתון הראשוני $p=97$ החבורה הציקלית ${\mathbb{\mathbb{Z}}}_{97}^{*}$ מסדר $n=96$ והיוצר $g=5$. אם נבחר $x=32$ וכן $y=17$. אם נתונים האלמנטים $5^{32}\equiv 35$ ו-$5^{17}\equiv 83$ (מודולו 97), בעיית דיפי-הלמן היא לגלות את $5^{32\cdot 17}\equiv 61\text{ (mod }97)$ (כאשר $x$ ו-$y$ לא ידועים).

עקום אליפטי

ערך מורחב – הצפנה מבוססת עקום אליפטי

חבורה אחרת שבה ההשערה היא שבעיית הלוגריתם הבדיד קשה היא אוסף הנקודות על עקום אליפטי. היתרון שלו הוא שבניגוד לחבורה כפלית לא ידוע על אלגוריתם שמסוגל לפתור את בעיית הלוגריתם הבדיד בזמן ריצה תת-מעריכי בחבורת העקום האליפטי. בקצרה, יהי $p\ge 5$ מספר ראשוני ונתונה משוואה מעוקבת $E$ בשני נעלמים $x$ ו-$y$ מהצורה:

$y^2=x^3+Ax+B\text{ mod }p$.

כאשר $A,B\in {\mathbb{\mathbb{Z}}}_p$ הם קבועים המקיימים את התנאי $4A^3+27B^2\equiv ̸0\text{ (mod }p)$ (תנאי זה הכרחי כדי להבטיח שלא יהיו בעקום קצוות חדים) נניח ש-$\hat{E}({\mathbb{\mathbb{Z}}}_p)$ מייצג את כל הזוגות $(x,y)\in {\mathbb{\mathbb{Z}}}_p\times {\mathbb{\mathbb{Z}}}_p$ המקיימים את המשוואה האמורה, אז העקום האליפטי הוא $E({\mathbb{\mathbb{Z}}}_p)=\hat{E}({\mathbb{\mathbb{Z}}}_p)\cup \{{𝒪}\}$. במילים, אוסף כל הנקודות המקיימות את המשוואה האמורה עם נקודה מיוחדת הנקראת "הנקודה באין סוף" המסומנת ב-${𝒪}$. קיים כלל חיבור מסובך שמאפשר לחבר שתי נקודות בעקום כדי לקבל נקודה שלישית שגם היא בעקום; $R=P+Q$ או חיבור נקודה בעצמה $Q=P+P=2P$. למרבה ההפתעה אפשר להוכיח שקבוצת הנקודות בעקום $E$ יחד עם כלל החיבור יוצרים חבורה אבלית. שהיא חבורה סגורה תחת כלל החיבור כשהנקודה באין סוף משמשת כאיבר יחידה. לכל נקודה יש נקודה הופכית וכן חוקי האסוציאטיביות והקומוטטיביות מתקיימים בה.

בעיית הלוגריתם הבדיד בעקום אליפטי היא כדלקמן. נתון עקום אליפטי $E({\mathbb{\mathbb{Z}}}_p)$ ונתונה נקודה כלשהי $P\in E({\mathbb{\mathbb{Z}}}_p)$ וכן הנקודה $Q\in ⟨P⟩$ מצא שלם $l$ המקיים $Q=lP$. השלם $l$ נקרא הלוגריתם הבדיד של הנקודה $Q$ בבסיס הנקודה $P$ או בקיצור $l={\log }_{P}Q$. הקבוצה $⟨P⟩$ היא תת-חבורה ציקלית המכילה את אוסף כל הנקודות שהן כפולות של $P$ כלומר $\{P,2P,3P,4P,...\}$ והשלם $l$ מייצג בעצם את מספר הפעמים שהנקודה $P$ חוברה לעצמה כדי לקבל את $Q$.

אלגוריתמים

באופן כללי נתונה חבורה הציקלית $\mathbb{𝔾}$ עם היוצר $g$ והאלמנט $y\in ⟨g⟩$ הבעיה היא מציאת השלם $x$ המקיים $g^x=y$ (בתת-החבורה הנוצרת על ידי $g$ או בחבורה $\mathbb{𝔾}$ אם $g$ הוא יוצר שלה), המסומנת בקיצור ${\log }_{g}y$ מודולו הסדר של $g$ שנקרא לעיתים הבסיס. אותה אפשר לפתור בכמה דרכים. הפתרון הנאיבי ביותר הוא שיטת כוח גס, כלומר אפשר לחשב את כל החזקות של $g$ לפי סדר $g^1,g^2,g^3,...$ עד שמתקבל $y$. סיבוכיות הפתרון היא מסדר גודל $O(q)$. קיימים מספר אלגוריתמים שלהם סיבוכיות טובה יותר והם המתחלקים לשתי קטגוריות. אלגוריתם גנרי שפועל על כל החבורה ואלגוריתם שפועל רק על חבורה ספציפית. לצורך הדיון אפשר להתעלם מהחבורה $\mathbb{𝔾}$ ולהתייחס ישירות לתת-החבורה $⟨g⟩$ שהיא מסדר $q$ שההנחה היא שהוא מספר ראשוני ידוע. להלן רשימת האלגוריתמים הידועים לפתרון בעיית הלוגריתם הבדיד וכן בעיית דיפי-הלמן.

• אלגוריתם צעד-קטן צעד-גדול של דויד שנקס שמסוגל למצוא לוגריתם בדיד בזמן ריצה של $O(\sqrt{q}\times \text{polylog}(q))$ ובסיבוכיות מקום בסדר גודל $O(\sqrt{q})$.
• אלגוריתם פוליג-הלמן הוא אלגוריתם ספציפי המתאים במקרה שהגורמים הראשוניים של סדר החבורה $q$ ידועים. במיוחד, אם לסדר החבורה יש גורמים קטנים, אלגוריתם זה מאפשר לצמצם את הבעייה לשתי בעיות לוגריתם בדיד מסדר קטן יותר (לפי גודלם של הגורמים הראשוניים) והפתרונות שלהם ניתנים לשילוב כדי לקבל פתרון לבעיה המקורית בסיבוכיות זמן זהה לבעיות הקטנות.
• אלגוריתם רו של פולרד ללוגריתמים שזמן ריצתו הוא $O(\sqrt{q})$ אך ללא סיבוכיות מקום.
• אלגוריתם תחשיב אינדקסים שרץ בזמן ריצה תת-מעריכי ונחשב בין היעילים ביותר לפתרון הבעיה.

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

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

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

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

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

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0