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

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

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

חבורה ציקלית

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

תהי ${\displaystyle \mathbb {G} }$ חבורה סופית מסדר ${\displaystyle m}$. עבור כל איבר ${\displaystyle g\in \mathbb {G} }$ קבוצת החזקות של ${\displaystyle g}$:

${\displaystyle \langle g\rangle =\{g^{0},g^{1},g^{2},...\}}$

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

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

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

• ${\displaystyle \log _{g}(h_{1}\cdot h_{2})=(\log _{g}h_{1}+\log _{g}h_{2}){\text{ mod }}p}$.
• ${\displaystyle \log _{g}(h^{y})=(y\log _{g}h){\mbox{ mod }}p}$ עבור שלם ${\displaystyle y}$ כלשהו.

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

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

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

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

ניסוי לוגריתם בדיד ${\displaystyle {\boldsymbol {\mathbf {DLog} _{{\mathcal {A}},{\mathcal {G}}}(n)}}}$:

1. מריצים את ${\displaystyle {\mathcal {G}}(1^{n})}$ כדי לקבל את ${\displaystyle (\mathbb {G} ,q,g)}$ כאשר ${\displaystyle \mathbb {G} }$ היא חבורה ציקלית מסדר ${\displaystyle q}$ ו-${\displaystyle g}$ הוא יוצר של ${\displaystyle \mathbb {G} }$.
2. בוחרים איבר ${\displaystyle h\leftarrow \mathbb {G} }$ (אפשר לעשות זאת על ידי בחירת איבר אקראי ${\displaystyle x'}$ וחישוב ${\displaystyle h=g^{x'}}$).
3. האלגוריתם ${\displaystyle {\mathcal {A}}}$ מקבל את ${\displaystyle (\mathbb {G} ,q,g,h)}$ ומחשב את ${\displaystyle x\in \mathbb {Z} _{q}}$.
4. הניסוי יוכתר בהצלחה אם ${\displaystyle g^{x}=h}$ אחרת הוא מסתיים בכישלון.

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

${\displaystyle \Pr[{\text{DLog}}_{{\mathcal {A}},{\mathcal {G}}}(n)=1]\leq {\text{ negl}}(n)}$

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

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

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

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

נתונה חבורה ציקלית מסדר ראשוני ${\displaystyle q}$, המסומנת ב-${\displaystyle \mathbb {G} }$, ונתונים ${\displaystyle n}$ יוצרים ${\displaystyle g_{1},\dots ,g_{n}\in \mathbb {G} }$. בהינתן ${\displaystyle h\in \mathbb {G} }$ איבר כלשהו, בעיית ייצוג הלוגריתם הבדיד (discrete logarithm representation problem) בקיצור DLREP, היא למצוא n-יה ${\displaystyle (x_{1},\dots ,x_{n})}$ כך ש-${\displaystyle h=g_{1}^{x_{1}}\cdots g_{n}^{x_{n}}}$. n-יה כזו נקראת הייצוג של ${\displaystyle \textstyle h=\Pi _{i=1}^{n}g_{i}^{x_{i}}}$ ביחס ל-${\displaystyle (g_{1},...,g_{n})}$.

לדוגמה, ה-n-יה ${\displaystyle (0,...,0)}$ היא הייצוג של 1 ביחס לכל בסיס ${\displaystyle (g_{1},...,g_{n})}$, והיא נקראת ייצוג טריוויאלי. בעיית ייצוג הלוגריתם הבדיד נחשבת לבעיה קשה, ובפרט היא קשה יותר מבעיית הלוגריתם הבדיד (אם ניתן לפתור את בעיית ייצוג הלוגריתם הבדיד, אזי ניתן לפתור את בעיית הלוגריתם הבדיד). בעיית DLREP אטרקטיבית כי אפשר להשתמש בה לצורך חתימה עיוורת.

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

ויטפילד דיפי ומרטין הלמן פרסמו ב-1976 מאמר פורץ דרך שהעלה לראשונה את רעיון ההצפנה האסימטרית והציעו לבססה על בעיה מתמטית קשה בתורת המספרים הקשורה לבעיית הלוגריתם הבדיד שנקראת כיום בעיית דיפי-הלמן והיא מתחלקת לשתים, בעיית דיפי הלמן חישובית, המסומנת בקיצור CDH ובעיית הכרעת דיפי-הלמן המסומנת בקיצור DDH. שתיהן בעיות בעלות חשיבות רבה בתחום הקריפטוגרפיה. נתונה חבורה ציקלית ${\displaystyle \mathbb {G} }$ ויוצר ${\displaystyle g\in \mathbb {G} }$ ונתונים שני איברים מהחבורה ${\displaystyle h_{1}}$ ו-${\displaystyle h_{2}}$ כאשר ${\displaystyle h_{1}=g^{x}}$ ו-${\displaystyle h_{2}=g^{y}}$ עבור שני שלמים ${\displaystyle x}$ ו-${\displaystyle y}$ לא ידועים. פונקציית דיפי-הלמן מוגדרת כדלהלן:

${\displaystyle {\text{DH}}_{g}(h_{1},h_{2})=g^{x\cdot y}=h_{1}^{y}=h_{2}^{x}}$.

הבעיה הראשונה, בעיית CDH, היא לחשב את פונקציית דיפי-הלמן ${\displaystyle {\text{DH}}_{g}(h_{1},h_{2})}$ עבור שני איברים אקראיים ${\displaystyle h_{1},h_{2}}$ (כאשר ${\displaystyle x}$ ו-${\displaystyle y}$ אינם ידועים אחרת הבעיה טריוויאלית). הבעיה השנייה DDH היא בעיית הכרעה, להבחין בין פלט הפונקציה ${\displaystyle {\text{DH}}_{g}(h_{1},h_{2})}$ לבין איבר אקראי כלשהו מהחבורה. במילים אחרות עבור איברים ${\displaystyle h_{1},h_{2}}$ שנבחרו באקראי ופתרון אפשרי ${\displaystyle h'}$ הבעיה היא להכריע האם ${\displaystyle h'={\text{DH}}_{g}(h_{1},h_{2})}$ או ${\displaystyle h'}$ הוא איבר אקראי חסר משמעות.

אם בעיית הלוגריתם הבדיד קלה לפתרון אז אפשר לפתור גם את בעיית דיפי-הלמן, תחילה מחשבים את ${\displaystyle x=\log _{g}h_{1}}$ ואז מחזירים את ${\displaystyle h_{2}^{x}}$. מאידך לא ברור האם קושיה המשוער של בעיית דיפי-הלמן שקול לבעיית הלוגריתם הבדיד.

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

${\displaystyle |\Pr[{\mathcal {A}}(\mathbb {G} ,q,g,g^{x},g^{y},g^{z})=1-\Pr[{\mathcal {A}}(\mathbb {G} ,q,g,g^{x},g^{y},g^{xy})=1]|\leq {\text{ negl}}(n)}$

כאשר ${\displaystyle x,y,z}$ הם איברים אקראיים. במילים פירושו שהבעיה האמורה קשה אם לא קיים אלגוריתם ${\displaystyle {\mathcal {A}}}$ שמצליח להכריע האם ${\displaystyle z=xy}$ בהסתברות משמעותית ביחס לסדר החבורה. אם ${\displaystyle z}$ נבחר באקראי מתוך ${\displaystyle \mathbb {Z} _{q}}$ באופן בלתי תלוי בערכים אחרים אז האיבר ${\displaystyle g^{z}}$ הוא בעל התפלגות אחידה בדידה ב-${\displaystyle \mathbb {G} }$.

ישנן מספר חבורות בהן בעיית הלוגריתם הבדיד ותאומה בעיית דיפי-הלמן קשות לפתרון. העדיפות היא לחבורה ציקלית מסדר ראשוני והסיבות הן ראשית משום שידוע שאם סדר החבורה אינו ראשוני אפשר לצמצם את בעיית הלוגריתם הבדיד לבעיה בתת-חבורות שלה שהן יותר קטנות ולכן הפתרון קל יותר. שנית, קל למצוא יוצר בחבורה מסדר ראשוני כי כל איברי החבורה הם יוצרים. בנוסף, קל יותר למצוא הופכי כפלי של מעריך כלשהו דבר שרצוי במבנים קריפטוגרפיים מסוימים ובעיקר הסיבה היא שזה הגיוני להשתמש בחבורה מסדר ראשוני כי אם הסדר ראשוני אפשר להוכיח שפלט הפונקציה ${\displaystyle {\text{DH}}_{g}(h_{1},h_{2})}$ הוא כמעט אקראי בהשוואה להתפלגות אחידה מעל ${\displaystyle \mathbb {G} }$.

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

דוגמה לבעיית דיפי-הלמן במספרים קטנים

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

עקום אליפטי

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

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

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

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

בעיית הלוגריתם הבדיד בעקום אליפטי היא כדלקמן. נתון עקום אליפטי ${\displaystyle E(\mathbb {Z} _{p})}$ ונתונה נקודה כלשהי ${\displaystyle P\in E(\mathbb {Z} _{p})}$ הנקראת נקודת הבסיס וכן הנקודה ${\displaystyle Q\in \langle P\rangle }$ מצא שלם ${\displaystyle l}$ המקיים ${\displaystyle Q=lP}$. השלם ${\displaystyle l}$ נקרא הלוגריתם הבדיד של הנקודה ${\displaystyle Q}$ בבסיס הנקודה ${\displaystyle P}$ או בקיצור ${\displaystyle l=\log _{P}Q}$. הקבוצה ${\displaystyle \langle P\rangle }$ היא תת-חבורה ציקלית המכילה את אוסף כל הנקודות שהן כפולות של ${\displaystyle P}$ כלומר ${\displaystyle \{P,2P,3P,4P,...\}}$ עד שמגיעים לנקודה באין סוף (נניח שנמצא שלם ${\displaystyle t}$ כך שמתקיים ${\displaystyle tP={\mathcal {O}}}$) הנקודה ${\displaystyle Q}$ נמצאת אי שם בחבורה זו כאשר השלם ${\displaystyle l<t}$ מייצג את מספר הפעמים שהיה צריך לחבר את הנקודה ${\displaystyle P}$ כדי להגיע ל-${\displaystyle Q}$:

${\displaystyle Q=\underbrace {P+P+\cdots +P} _{l{\text{ times}}}}$

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

אלגוריתמים

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

• אלגוריתם צעד-קטן צעד-גדול של דויד שנקס שמסוגל למצוא לוגריתם בדיד בזמן ריצה של ${\displaystyle O({\sqrt {q}}\times {\text{polylog}}(q))}$ ובסיבוכיות מקום בסדר גודל ${\displaystyle O({\sqrt {q}})}$.
• אלגוריתם פוליג-הלמן הוא אלגוריתם ספציפי המתאים במקרה שהגורמים הראשוניים של סדר החבורה ${\displaystyle q}$ ידועים. במיוחד, אם לסדר החבורה יש גורמים קטנים, אלגוריתם זה מאפשר לצמצם את הבעיה לשתי בעיות לוגריתם בדיד מסדר קטן יותר (לפי גודלם של הגורמים הראשוניים) והפתרונות שלהם ניתנים לשילוב כדי לקבל פתרון לבעיה המקורית בסיבוכיות זמן זהה לבעיות הקטנות.
• אלגוריתם רו של פולרד ללוגריתמים שזמן ריצתו הוא ${\displaystyle O({\sqrt {q}})}$ בדומה לאלגוריתם צעד-קטן צעד-גדול אך ללא סיבוכיות מקום.
• אלגוריתם תחשיב אינדקסים שרץ בזמן ריצה תת-מעריכי ונחשב לאלגוריתם החזק ביותר הידוע כיום לפתרון בעיית הלוגריתם הבדיד בחבורות מסדר גדול מאוד כמו ${\displaystyle \mathbb {Z} _{n}^{*}}$ עבור ${\displaystyle n\geq 500}$ פריק. גרסה אחת שלו הנקראת אלגוריתם Coppersmith מסוגלת להגיע לזמן ריצה של ${\displaystyle \textstyle L_{2^{m}}\left[{\frac {1}{3}},c\right]}$ עבור קבוע כלשהו ${\displaystyle c<1.587}$.
• כאשר מחשבים קוונטיים יהיו מעשיים אפשר יהיה לפתור את בעיית הלוגריתם הבדיד בזמן פולינומי עם אלגוריתם שור^[2].

אלגוריתם צעד-קטן צעד-גדול

המחשה של אלגוריתם צעד-קטן צעד-גדול

אלגוריתם צעד-קטן/צעד-גדול של דויד שנקס הוא אלגוריתם כוח גס רקורסיבי שעושה שימוש בזיכרון כדי לפתור את בעיית הלוגריתם הבדיד בחבורה ציקלית מסדר ${\displaystyle q}$ בזמן ריצה של ${\displaystyle O({\sqrt {q}}\cdot {\text{polylog}}(q))}$. הרעיון הוא פשוט. בהינתן תת-חבורה ציקלית ${\displaystyle \langle g\rangle }$ ואיבר ${\displaystyle y\in \langle g\rangle }$, אפשר לדמיין את החבורה כמעגל של האיברים ${\displaystyle 1=g^{0},g^{1},g^{2},...,g^{q-2},g^{q-1},g^{q}=1}$.

ידוע ש-${\displaystyle y=g^{x}}$ חייב להיות היכן שהוא בתוך המעגל, במקום לחשב ולאחסן בזיכרון את כל האיברים של המעגל עד שנמצא ${\displaystyle x}$ שזה אינו מעשי, "מסמנים" נקודות במעגל במרווחים קבועים (או מדלגים במרחק קבוע) לפי ${\displaystyle t=\lfloor {\sqrt {q}}\rfloor }$. במילים אחרות מחשבים ומאחסנים בטבלה ממוינת בזיכרון את האיברים:

${\displaystyle g^{0},g^{t},g^{2t},...,g^{\lfloor q/t\rfloor \cdot t}}$.

שלב זה נקרא "צעד-גדול". כעת היות ש-${\displaystyle y=g^{x}}$ נמצא באחד מהמרווחים, מובטח שאחד מ-${\displaystyle t}$ האיברים

${\displaystyle y\cdot g^{0}=g^{x},y\cdot g^{1}=g^{x+1},...,y\cdot g^{t}=g^{x+t}}$

יהיה שווה לאחת מהנקודות שאוחסנו בטבלה בזיכרון, שלב זה נקרא "צעד-קטן". נניח ש-${\displaystyle y\cdot g^{i}=g^{k\cdot t}}$ עבור ${\displaystyle i}$ ו-${\displaystyle k}$ כלשהם, אפשר בקלות לפתור את הלוגריתם על ידי ${\displaystyle y=g^{kt-i}}$ או ${\displaystyle \log _{g}y=(kt-i){\text{ mod }}q}$.

האלגוריתם דורש ${\displaystyle O({\sqrt {q}})}$ העלאות בחזקה בחבורה ${\displaystyle \mathbb {G} }$, כל פעולה כזו מתבצעת בזמן של ${\displaystyle O({\text{polylog}}(q))}$ פעולות בסיסיות, אם משתמשים באלגוריתם יעיל לחישוב חזקות בחבורה. אך יש צורך לאחסן בזיכרון ${\displaystyle {\sqrt {q}}}$ איברים בערך. למעשה ברקורסיה, למעט האיבר הראשון לחישוב כל איבר נדרשת פעולת כפל אחת: ${\displaystyle g_{i}=g_{i-1}\cdot g_{1}}$ באופן דומה כל ${\displaystyle y_{i}}$ ניתן לחישוב כ-${\displaystyle y_{i}=y_{i-1}\cdot g}$. מיון ניתן לביצוע בזמן של ${\displaystyle O({\sqrt {q}}\log q)}$ וחיפוש בינארי מתבצע בזמן של ${\displaystyle O(\log q)}$.

פירוט מהלכי האלגוריתם

קלט: תת-חבורה ${\displaystyle g\in \mathbb {G} }$, האיבר ${\displaystyle y\in \langle g\rangle }$ וסדר החבורה ${\displaystyle q}$.

פלט: ${\displaystyle \log _{g}y}$.

1. מחשבים את ${\displaystyle t=\lfloor {\sqrt {q}}\rfloor }$.
2. עבור ${\displaystyle i=0}$ עד ${\displaystyle \lfloor q/t\rfloor }$ מבצעים כדלהלן:
   1. מחשבים את ${\displaystyle g_{i}=g^{i\cdot t}}$.
3. ממיינים את כל הזוגות (${\displaystyle i,g_{i}}$) לפי הערך השני.
4. עבור ${\displaystyle i=0}$ עד ${\displaystyle t}$ מבצעים:
   1. מחשבים את ${\displaystyle y_{i}=y\cdot g^{i}}$ ובודקים
   2. אם ${\displaystyle y_{i}=g_{k}}$ עבור ${\displaystyle k}$ כלשהו מחזירים את ${\displaystyle (kt-i)}$ מודולו ${\displaystyle q}$.

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

בחבורה ${\displaystyle \mathbb {Z} _{29}^{*}}$ מסדר ${\displaystyle q=28}$, אם ${\displaystyle g=2}$ ו-${\displaystyle y=17}$ כדי לחשב את הלוגריתם הבדיד של 17 בבסיס 2 תחילה מחשבים את ${\displaystyle t=5}$ ואז מכינים טבלה עם זוגות הערכים הבאים (מודולו 29) ממוינת לפי הערך השני:

1	2	3	4	5	6
${\displaystyle 0,2^{0}=1}$	${\displaystyle 5,2^{5}=3}$	${\displaystyle 10,2^{10}=9}$	${\displaystyle 25,2^{25}=11}$	${\displaystyle 20,2^{20}=23}$	${\displaystyle 15,2^{15}=27}$

ואז מחשבים את הערכים הבאים עם המונה ${\displaystyle i=0,1,2,...}$:

${\displaystyle 17\cdot 2^{0}=17,17\cdot 2^{1}=5,17\cdot 2^{2}=10,17\cdot 2^{3}=20,17\cdot 2^{4}=11}$

בחיפוש מהיר מסתבר שהערך האחרון שהתקבל זהה למעשה לכניסה הרביעית בטבלה לכן ${\displaystyle \log _{2}17=25-4=21}$ מודולו 29.

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

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

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

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

ראו גם

• בעיית RSA
• אלגוריתם רו של פולרד ללוגריתם הבדיד

קישורים חיצוניים

• בעיית הלוגריתם הבדיד, באתר MathWorld (באנגלית)

הערות שוליים

1. Introduction to Modern Cryptography (2nd edition), Jonathan Katz and Yehuda Lindell
2. Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing