הצגת המקור של הדף "עקום 25519"

ב[[קריפטוגרפיה]], '''עקום 25519''' (באנגלית: Curve25519) הוא כינוי ל[[עקום אליפטי]] מסוים המיועד לשימוש ביחד עם '''פונקציית דיפי-הלמן בעקום אליפטי''' (בקיצור ECDH), כחלק מ[[פרוטוקול שיתוף מפתח]] המבוסס על [[פרוטוקול דיפי-הלמן|דיפי-הלמן]]. העקום מספק ביטחון ברמה של 128 סיביות (גודל מפתח של 256 סיביות) ומהירות ביצוע גבוהה במיוחד. זהו אחד מהעקומים המהירים ביותר הקיימים כיום, הוא אינו מוגן ב[[פטנט]] וקוד הייחוס שלו הוא [[רשות הציבור|נחלת הכלל]]. 

העקום פופולרי מאוד כיום ונמצא בשימוש מעשי נרחב ביישומי אבטחה רבים, במיוחד באבטחת [[מסרים מיידיים]]. עקום 25519 פותח ב-2005 על ידי [[דניאל ברנשטיין]] שקרא לו בתחילה פונקציית DH{{הערה|[https://cr.yp.to/ecdh.html A state-of-the-art Diffie-Hellman function]}}. מאוחר יותר הציע לקרוא לעקום בשם זה בשל מבנהו המסתמך על [[מספר ראשוני|המספר הראשוני]] <math>2^{255}-19</math> ופונקציית דיפי הלמן נקראה X25519 בהתאם{{הערה|[https://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html 25519 naming]}}.

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

==מבנה מתמטי==
העקום Curve25519 הוא [[עקום מונטגומרי]] מעל [[הרחבת שדות|ההרחבה הריבועית]] של [[שדה (מבנה אלגברי)|השדה]] הראשוני המוגדר על ידי [[מספר ראשוני|המספר הראשוני]] <math>2^{255}-19</math> יחד עם '''נקודת בסיס''' קבועה <math>x=9</math> ונוסחתו היא: 
<center>
:<math>y^2=x^3+486662x^2+x</math>.
</center>
פרוטוקול דיפי הלמן בעקום זה משתמש בגרסה "דחוסה", שבה מתייחסים רק לקואורדינטה <math>x</math> של הנקודה, מה שמאפשר להשתמש באלגוריתם [[סולם מונטגומרי]] (המתואר להלן) כדי לבצע כפל נקודות בעקום תוך שימוש במה שקרוי [[מרחב פרויקטיבי|קוארודינטות פרויקטיביות]]. עקום זה הוא גרסה מפותלת של עקום אליפטי ממשפחת [[עקומי אדוארד]] שהם עקומים אליפטיים מיוחדים הנקראים על שם המתמטיקאי הרולד אדוארד שחקר אותם ב-2007. עקום אדוארד מפותל מעל השדה <math>\mathbb{K}</math> שה[[מציין של שדה|מציין]] שלו אינו 2 הוא [[מישור אפיני]] המוגדר על ידי המשוואה:
<center>
:<math>E_{E_{a,d}}:ax^2+y^2=1+dx^2y^2</math>
</center>
כאשר <math>a</math> ו-<math>d</math> הם אלמנטים שונים של <math>\mathbb{K}</math>. אם <math>a=1</math> מתקבל עקום אדוארד. עקום זה שקול בירציונלית לעקום מונטגומרי שהוא סוג אחר של עקום אליפטי שהיתרון שלו הוא ביכולת לבצע חישובי כפל וחיבור נקודות ביעילות בייצוג פרויקטיבי. בשיטה זו הנקודה <math>P=(x,y)</math> מיוצגת על ידי <math>(X:Z)</math> כאשר <math>x=X/Z</math> (לדוגמה יכול להיות <math>Z=1</math>). בשיטת ייצוג זו הנקודה מאבדת מידע בשל העובדה שהקואורדינטה <math>y</math> אינה משתתפת בחישובים לכן לא יהיה הבדל בין <math>P</math> ל-<math>-P</math>, אך יתרונה הוא בכך שכפל נקודות הופך להיות קל ולצורך חישובי דיפי-הלמן צריך רק את הקואורדינטה <math>x</math>.

===נוסחת חיבור וכפל של מונטגומרי===
לפי נוסחת מונטגומרי נדרשים בדיוק 4 [[העלאה בריבוע|ריבועים]], כפל אחד ב-<math>(A-2)/4</math>, בנוסף ל-5 פעולות כפל נוספות ו-8 פעולות חיבור/חיסור. האלגוריתם פועל כדלהלן. בהינתן מספר ראשוני <math>p\ge 5</math> ושלם <math>A</math> כך ש-<math>A^2-4</math> אינו [[מספר ריבועי]] מודולו <math>p</math>. ויהי <math>E:y^2=x^3+Ax^2+x</math> עקום אליפטי מעל השדה <math>F_p</math>. יהי <math>X:E(F_{p^2})\rightarrow\{\mathcal{O}\}\cup F_{p^2}</math> כדלהלן: <math>X(\mathcal{O})=\mathcal{O}, X(x,y)=x</math> (הסמל <math>\mathcal{O}</math> מייצג את הנקודה באינסוף). בהינתן <math>x,z\in F_p</math> כאשר <math>(x,z)\ne(0,0)</math> השוויון הבא מתקיים:
{| dir="ltr"
|-
|
:<math>x_2 = (x_2 - z_2)^2 = (x - z)^2(x + z)^2</math>,
:<math>z_2 = 4xz(x^2 + Axz + z^2)</math>
:<math>\ \ \ \ = ((x + z)^2 - (x - z)^2)\left((x + z)^2 +\frac{A - 2}{4}((x + z)^2 - (x - z)^2)\right)</math>
|}
אז <math>X(2Q)=x_2/z_2</math> עבור כל <math>Q\in E(F_{p^2})</math> כך שמתקיים <math>X(Q)=x/z</math>.
כאן הביטוי <math>x/z</math> פירושו המנה של <math>x</math> ו-<math>z</math> בשדה <math>F_p</math> אם <math>z\ne 0</math>. אם <math>x=0</math> התוצאה היא <math>\mathcal{O}</math> וכן אם <math>x=z=0</math> התוצאה אינה מוגדרת.

==פונקציית דיפי-הלמן==
בעקום 25519 לכל משתמש מפתח סודי באורך 32 בתים ומפתח ציבורי באורך 32 בתים. כל זוג משתמשים משתפים "סוד" באורך 32 בתים שממנו הם יכולים לייצר מפתחות ל[[אימות מסרים|אימות]] והצפנה של חילופי המסרים ביניהם. העקום 25519 ונקודת הבסיס 9 הם פרמטרים ציבוריים וידועים לכל, כולל למתקיפה פוטנציאלית. המפתח הפרטי של אליס הוא השלם <math>a</math> שיכול להיות כל מחרוזת אקראית של 32 בתים והמפתח הפרטי של בוב הוא <math>b</math>. אליס שולחת לבוב את המפתח הציבורי שלה <math>\text{Curve}25519(a,9)</math>. הפונקציה <math>\text{Curve}25519</math> מקבלת שלם כלשהו <math>n</math> ונקודה <math>Q</math> בעקום 25519 ומחזירה את <math>nQ</math>. בוב שולח לאליס את המפתח הציבורי שלו <math>\text{Curve}25519(b,9)</math>. הסוד המשותף הוא:
<center>
:<math>\text{Curve}25519(a, \text{Curve}25519(b,9))=\text{Curve}25519(b, \text{Curve}25519(a,9))</math>
</center>
במילים, הסוד המשותף מתקבל מהכפלת הסוד הפרטי של כל משתמש במפתח הציבורי של המשתמש השני. הרעיון כאן הוא שהמשתמשים אינם חושפים את הסודות שלהם, תחת זאת הם מכפילים את הסודות בנקודה הקבועה ושולחים את התוצאה ברשת האינטרנט. ניסיון לנחש את השלם שאיתו בוצע כפל סקלרי של נקודה קבועה כלשהי בעקום קשה מאוד והוא נחשב לבעיה מתמטית קשה הנקראת "בעיית הלוגריתם הבדיד בעקום אליפטי". ניסיון לנחש את הסוד המשותף מתוך שני המפתחות הציבוריים נקרא בעיית דיפי-הלמן בעקום אליפטי וגם היא נחשבת כבעיה קשה, אם כי אין הוכחה שהיא קשה לפחות כ[[בעיית הלוגריתם הבדיד]]. בדרך כלל מהסוד המשותף גוזרים מפתחות הצפנה ואימות באמצעות [[פונקציית גיבוב קריפטוגרפית]].

עקום 25519 נבנה כך שיהיה עמיד נגד מספר מלכודות הנובעות מאופן היישום שלו בפועל. העקום עמיד נגד [[התקפת ערוץ צדדי|התקפת תיזמון]], הוא יכול לקבל כל מחרוזת באורך 32 בתים כמפתח ציבורי תקף ואינו דורש אימות.

==היסטוריה ושימושים==
עקום 25519 זכה לפופולריות רבה מאז פורסם, אולם ההתעניינות הגוברת בו החלה אחרי 2013 כשנודע שה-[[NSA]] שתלו [[דלת אחורית]] בעקום האליפטי [[DUAL EC DRBG]] שהיה חלק מתקן ההצפנה בעקום אליפטי של [[NIST]]. אף על פי שאין קשר ישיר ביניהם, החשיפה הגבירה את החשש בקרב המשתמשים מפני דלתות נוספות שייתכן נשתלו במרכיבים אחרים של התקן כמו העקומים הקבועים P-xxx. [[ברוס שנייר]] מגדולי הקריפטוגרפים בני זמננו התבטא פעם: "איני סומך יותר על העקומים הקבועים שלהם. אני מאמין שה-NSA ביצעו מניפולציות בעזרת הקשרים שלהם עם התעשייה". הוא גם ציין שה-NSA מסוגלים לפצח כל הצפנה באינטרנט (נכון ל-2013).

עקום 25519 הפך לתקן בפועל שהחליף את P-256 והוא בשימוש במגוון רחב של יישומים. החל מ-2014 פרוטוקול [[OpenSSH]] הטמיע את העקום כברירת מחדל בישומים מבוססי ECDH. ספריות קריפטוגרפיות רבות תומכות בעקום זה ביניהן: [[OpenSSL]] וכן [[Libgcrypt]], [[Crypto++]]{{D}} ועוד רבים. בין הפרוטוקולים, האפלקציות ומערכות ההפעלה המשתמשים בעקום זה נמנים:
{{טורים
|רוחב=26em
|תוכן=* [[Viber]]
* [[וואטסאפ]]
* [[iOS]]
* [[מדמה מסוף]] [[PuTTY]].
* [[OpenBSD]]
* [[Google Allo]]
* [[פרוטוקול סיגנל]]
* [[Tor]]
* [[OpenSSH]]
* Messenger של [[פייסבוק]]
* [[Threema]] (תוכנת [[מסרים מיידיים]])
* [[Cryptocat]] (תוכנת [[צ'אט]])
* [[GNU Privacy Guard]] תחליף ל-[[PGP|OpenPGP]]
* [[DNSCrypt]]
}}

==ביטחון ויעילות==
הביטחון של העקום הזה נחשב גבוה, כלומר לא קיימת דרך לחשיפת הסוד המשותף מתוך שני המפתחות הציבוריים שהיא טובה יותר מ[[כוח גס]] ב[[סיבוכיות]] של <math>2^{128}</math>. הבעיה הכללית עליה הוא מבוסס, בעיית דיפי הלמן בעקום אליפטי נחקרה באופן אינטנסיבי מזה כשני עשורים והותקפה רבות על ידי מתמטיקאים, אנליסטים והאקרים ללא הצלחה. עקום 25519 מכיל מספר תכונות שמעניקות לו יתרון, הסדר שלו הוא מעל <math>2^{255}</math>, הוא אינו מכיל מאפיינים אלגבריים ייחודיים שניתנים לניצול לקיצור ההתקפה נגדו. האלגוריתמים הידועים כמו [[אלגוריתם רו של פולרד ללוגריתמים|אלגוריתם רו]] או [[אלגוריתם קנגורו של פולרד]] ו[[אלגוריתם פוליג-הלמן]] יעילים רק נגד עקומים מסדר ראשוני נמוך יותר ולכן אינם פרקטיים נגד עקום 25519.

היתרון של עקום 25519 הוא באופן המימוש שלו. אפשר לנצל את [[FPU|יחידת הנקודה הצפה]] בקיצור FPU של ה[[מעבד]] כדי להאיץ ביצועים של פעולות כפל וחיבור בסיסיות באופן משמעותי. הסיבה לבחירה של הראשוני <math>2^{255}-19</math> נובעת בגלל היכולת לייצג אלמנטים של השדה בצורה פולינומית ולבצע חיבור וכפל במהירות. הפולינומים נבחרו כך שיענו על שני מאפיינים חשובים, שהמעלה שלהם תהיה נמוכה (לכל היותר 9) כך שיהיו פחות מקדמים שצריך לכפול כחלק מהכפל בפולינומים וכן, כל מקדם הוא כפולה קטנה של <math>2^{\lceil 25.5i\rceil}</math>. ביתר פירוט הפולינומים עם מספר מופחת של מקדמים קטנים הם מהצורה:
:<math>u_0+u_1x+u_2x^2+\cdots +u_9x^9</math> כאשר <math>u_i</math> הוא כפולה שלמה של <math>2^{\lceil 25.5i\rceil}</math>.
:<math>u_i/2^{\lceil 25.5i\rceil}\in\{-2^{25},-2^{25} + 1,...,-1,0,1,...,2^{25}-1, 2^{25}\}</math>	
כאן הפולינום <math>\textstyle \sum_i u_ix^i</math> מייצג את השלם <math>u_0+u_1+\cdots+u_9</math> שהוא בעצם פיצול של שלם באורך 256 סיביות לעשרה שלמים באורך 26 סיביות כל אחד בקירוב, כדי שיתאימו באורכם ל[[אוגר (מחשבים)|אוגרי]] הנקודה הצפה המצויים בכל מעבד. כל שלם באורך 256 סיביות  ניתן לטעינה בתשעה אוגרים. בדרך כלל במעבדים מודרניים אוגרים אילו מצויים בשפע. השימוש בבסיס 25.5 ולא בבסיס 25 או 26 נובע מסיבות של יעילות כדי להימנע מחילוק ארוך במקדמים <math>x^{10}</math> ו-<math>x^{11}</math> וכן להימנע מכפל המקדמים ב-<math>2^5\cdot 19</math> במקום ב-19.

חיבור/חיסור שני פולינומים של עקום 25519 [[מודולו]] <math>2^{255}-19</math> מצריך 10 פעולות חיבור/חיסור של מספרי נקודה צפה (fp). כל פעולת חיבור/חיסור צורכת 10 פקודות fp בסיסיות, בלולאה הראשית של הפונקציה Curve25519 מתבצעים בסך הכול 20,400 פקודות fp. פעולת כפל צורכת 100 פקודות fp עבור כפל ו-81 פקודות fp עבור חיבור. המקדמים הגבוהים <math>x^{10}, x^{11},...,x^{18}</math> לאחר תוצאת הכפל מצומצמים מודולו <math>2^{255}x^{10}-19</math>. למשל המקדם <math>x^{18}</math> מוכפל ב-<math>19\cdot 2^{255}</math> ומחובר למקדם <math>x^8</math>. כל צמצום דורש פקודת fp אחת לכפל ופקודת fp אחת לחיבור. החלק הגבוה (הכפולה הקרובה ביותר לחזקה של 2) של כל מקדם מחוסר ומחובר למקדם שלפניו. כל העברה כזו צורכת בסך הכול 4 פקודות fp. כך שלצורך הצמצום המודולרי נדרשים עוד כ-60 פקודות fp. כתיבת הקוד עדיפה ב[[אסמבלי]] כדי להימנע מתקורה מיותרת שעלולה לקרות ביישום ב[[שפת C]].

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

==הפונקציה Curve25519==
הפונקציה Curve25519 היא בעצם כפל סקלרי של הקואורדינטה <math>x\in F_p</math> מעל העקום <math>E(F_{p^2})</math>, כאשר <math>p</math> הוא המספר הראשוני <math>2^{255}-19</math> ו-<math>E</math> הוא העקום האליפטי <math>y^2=x^3+486662x^2+x</math>.

ביתר פירוט, השדה <math>\mathbb{F}_{p^2}</math> מוגדר כקבוצת כל האלמנטים <math>(Z/(2^{255}-19))[\sqrt{2}]</math>. תהי הפונקציה <math>X_0:E(\mathbb{F}_{p^2})\rightarrow\mathbb{F}_{p^2}</math> מוגדרת כדלהלן: <math>X_0(\mathcal{O})=0,X_0(x,y)=x</math>. במילים אחרות <math>X_0</math> היא פונקציה שממירה נקודה בעקום לאלמנט בשדה (פשוט על ידי נטילת הקואורדינטה <math>x</math> והתעלמות מהקואורדינטה <math>y</math>).  תהי הפונקציה <math>X:E(\mathbb{F}_{p^2})\rightarrow\{\mathcal{O}\}\cup\mathbb{F}_{p_2}</math> המוגדרת כדלהלן: <math>X(\mathcal{O})=\mathcal{O},X(x,y)=x</math>.

המפתח הציבורי והמפתח הפרטי מומרים ממחרוזות בתים לאלמנטים של השדה לפי [[סדר בתים]] קטן. במילים אחרות כל שלם <math>s\in\{0,1,...,2^{256}-1\}</math> מיוצג כך:
:<math>s=(s\text{ mod }256,\lfloor s/256\rfloor\text{ mod }256,...,\left\lfloor s/256^{31}\right\rfloor\text{ mod }256)</math>.
קבוצת כל המפתחות הציבוריים האפשריים היא <math>\{q:q\in\{0,1,...,2^{256}-1\}\}</math>. קבוצת כל מפתחות הפרטיים היא <math>\{n:n\in 2^{254}+8\{0,1,2,3,...,2^{251}-1\}\}</math>. הפונקציה Curve25519 מוגדרת כך:
<center>
:<math>\text{Curve}25519:\{\text{Curve25519 }\text{secret key}\}\times\{\text{Curve25519 }\text{public key}\}\rightarrow\{\text{Curve25519 }\text{public key}\}</math>. 
</center>
בהינתן <math>n</math> ו-<math>q</math> קיים שלם ייחודי <math>s\in\{0,1,2,...,2^{255}-20\}</math> כך שמתקיים <math>s=X_0(nQ)</math> עבור כל <math>Q\in E(\mathbb{F}_{p^2})</math> כאשר <math>X_0(Q)=q\text{ mod }2^{255}-19</math>. לסיום הפונקציה <math>\text{Curve}25519(n,q)</math> מחזירה את <math>s</math> האמור.

===פסאודו קוד===
הפונקציה <math>\text{Curve25519 }</math> בפסאודו קוד הבא מבוססת על סולם מונטגומרי. היא מקבלת את השלם <math>k</math> (שהוא הסוד הפרטי של המשתמש) ואת הקואורדינטה <math>u</math> (מקבילה ל-<math>x</math> בעקום מונטגומרי) של הנקודה הקבועה <math>P</math> בעקום 25519 ומחזירה את <math>x_2</math> שהוא הקואורדינטה <math>x</math> של הכפל הסלקרי <math>kP</math>. 
<center>
{| dir="ltr"
|-
| 
:<math>\boldsymbol{\mathbf{Curve25519}(k,u)}</math>
:<math>x_1=x_3=u</math>
:<math>x_2=z_3=1</math>
:<math>z_2=0</math>
:<math>s=0 \text{ // boolean} </math>
:{{D}}
:<math>\text{For } t=254\text{ Down to }0\text{ do:}</math>
:<math>\{</math>
:<math>\ \ \ \ \ \ k_t=(k \gg t) \text{ AND } 1</math>
:<math>\ \ \ \ \ \ s = s \oplus k_t</math>
:<math>\ \ \ \ \ \ (x_2,x_3)=\text{ConditionalSwap}(s,x_2,x_3)</math>
:<math>\ \ \ \ \ \ (z_2,z_3)=\text{ConditionalSwap}(s,z_2,z_3)</math>
:<math>\ \ \ \ \ \ A=x_2+z_2</math>
:<math>\ \ \ \ \ \ B=x_2-z_2</math>
:<math>\ \ \ \ \ \ E=A^2-B^2</math>
:<math>\ \ \ \ \ \ C=x_3+z_3</math>
:<math>\ \ \ \ \ \ D=x_3-z_3</math>
:<math>\ \ \ \ \ \ x_3=(DA + CB)^2</math>
:<math>\ \ \ \ \ \ z_3=x_1\cdot(DA-CB)^2</math>
:<math>\ \ \ \ \ \ x_2=A^2\cdot B^2</math>
:<math>\ \ \ \ \ \ z_2=E\cdot (A^2+121665\cdot E)</math>
:<math>\}</math>
:<math>(x_2,x_3)=\text{ConditionalSwap}(s, x_2,x_3)</math>
:<math>(z_2,z_3)=\text{ConditionalSwap}(s, z_2,z_3)</math>
:<math>\text{Return }x_2\cdot\left(z_2^{(p-2)}\right)</math>
|}
</center>
הסמל <math>\gg</math> כאן מייצג הזזה ימינה (shift right) ברמת סיביות, <math>\text{ AND}</math> הוא [[וגם (לוגיקה)|וגם]] והסמל <math>\oplus</math> הוא XOR. הפונקציה <math>\text{ConditionalSwap}(s,a,b)</math> היא פונקציית החלפה שמקבלת פרמטר בוליאני <math>s</math> ומחליפה בין ערכי <math>a</math> ו-<math>b</math> בתנאי ש-<math>s</math> שווה אמת. הפונקציה חייבת להיות מיושמת באופן כזה שההחלפה תהיה קבועה תמיד כדי לסכל התקפת ערוץ צדדי. אפשר ליישם זאת על ידי הוספת מסכת אחדים לפי <math>s</math>, למשל <math>\text{mask}(s)=0-s</math>, אם <math>s=0</math> התוצאה תהיה כאילו לא בוצעה החלפה. אם <math>\text{dummy}</math> הוא משתנה מקומי, אז ההחלפה מתבצעת בשלושה מהלכים ללא [[אם-אז|תנאי]] כך: 
:<math>\text{dummy}=\text{mask}(\text{s})\text{ AND } (a\oplus b)</math>
:<math>a=a\oplus\text{dummy}</math>
:<math>b=b\oplus\text{dummy}</math>

==קישורים חיצוניים==
* {{אתר רשמי}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:הצפנה]]