בקריפטוגרפיה, עקום 25519 (באנגלית: Curve25519) הוא כינוי לעקום אליפטי מסוים המיועד לשימוש ביחד עם פונקציית דיפי-הלמן בעקום אליפטי (בקיצור ECDH), כחלק מפרוטוקול שיתוף מפתח המבוסס על דיפי-הלמן. העקום מספק ביטחון ברמה של 128 סיביות (גודל מפתח של 256 סיביות) ומהירות ביצוע גבוהה במיוחד. זהו אחד מהעקומים המהירים ביותר הקיימים כיום, הוא אינו מוגן בפטנט וקוד הייחוס שלו הוא נחלת הכלל.
העקום פופולרי מאוד כיום ונמצא בשימוש מעשי נרחב ביישומי אבטחה רבים, במיוחד באבטחת מסרים מיידיים. עקום 25519 פותח ב-2005 על ידי דניאל ברנשטיין שקרא לו בתחילה פונקציית DH. מאוחר יותר הציע לקרוא לעקום בשם זה בשל מבנהו המסתמך על המספר הראשוני formula_1 ופונקציית דיפי הלמן נקראה X25519 בהתאם.
יתרונות עקום 25519 הם:
מבנה מתמטי.
העקום Curve25519 הוא עקום מונטגומרי מעל ההרחבה הריבועית של השדה הראשוני המוגדר על ידי המספר הראשוני formula_1 יחד עם נקודת בסיס קבועה formula_3 ונוסחתו היא:
פרוטוקול דיפי הלמן בעקום זה משתמש בגרסה "דחוסה", שבה מתייחסים רק לקואורדינטה formula_5 של הנקודה, מה שמאפשר להשתמש באלגוריתם סולם מונטגומרי (המתואר להלן) כדי לבצע כפל נקודות בעקום תוך שימוש במה שקרוי קוארודינטות פרויקטיביות. עקום זה הוא גרסה מפותלת של עקום אליפטי ממשפחת עקומי אדוארד שהם עקומים אליפטיים מיוחדים הנקראים על שם המתמטיקאי הרולד אדוארד שחקר אותם ב-2007. עקום אדוארד מפותל מעל השדה formula_6 שהמציין שלו אינו 2 הוא מישור אפיני המוגדר על ידי המשוואה:
כאשר formula_8 ו-formula_9 הם אלמנטים שונים של formula_6. אם formula_11 מתקבל עקום אדוארד. עקום זה שקול בירציונלית לעקום מונטגומרי שהוא סוג אחר של עקום אליפטי שהיתרון שלו הוא ביכולת לבצע חישובי כפל וחיבור נקודות ביעילות בייצוג פרויקטיבי. בשיטה זו הנקודה formula_12 מיוצגת על ידי formula_13 כאשר formula_14 (לדוגמה יכול להיות formula_15). בשיטת ייצוג זו הנקודה מאבדת מידע בשל העובדה שהקואורדינטה formula_16 אינה משתתפת בחישובים לכן לא יהיה הבדל בין formula_17 ל-formula_18, אך יתרונה הוא בכך שכפל נקודות הופך להיות קל ולצורך חישובי דיפי-הלמן צריך רק את הקואורדינטה formula_5.
נוסחת חיבור וכפל של מונטגומרי.
לפי נוסחת מונטגומרי נדרשים בדיוק 4 ריבועים, כפל אחד ב-formula_20, בנוסף ל-5 פעולות כפל נוספות ו-8 פעולות חיבור/חיסור. האלגוריתם פועל כדלהלן. בהינתן מספר ראשוני formula_21 ושלם formula_22 כך ש-formula_23 אינו מספר ריבועי מודולו formula_24. ויהי formula_25 עקום אליפטי מעל השדה formula_26. יהי formula_27 כדלהלן: formula_28 (הסמל formula_29 מייצג את הנקודה באינסוף). בהינתן formula_30 כאשר formula_31 השוויון הבא מתקיים:
אז formula_32 עבור כל formula_33 כך שמתקיים formula_34.
כאן הביטוי formula_35 פירושו המנה של formula_5 ו-formula_37 בשדה formula_26 אם formula_39. אם formula_40 התוצאה היא formula_29 וכן אם formula_42 התוצאה אינה מוגדרת.
פונקציית דיפי-הלמן.
בעקום 25519 לכל משתמש מפתח סודי באורך 32 בתים ומפתח ציבורי באורך 32 בתים. כל זוג משתמשים משתפים "סוד" באורך 32 בתים שממנו הם יכולים לייצר מפתחות לאימות והצפנה של חילופי המסרים ביניהם. העקום 25519 ונקודת הבסיס 9 הם פרמטרים ציבוריים וידועים לכל, כולל למתקיפה פוטנציאלית. המפתח הפרטי של אליס הוא השלם formula_8 שיכול להיות כל מחרוזת אקראית של 32 בתים והמפתח הפרטי של בוב הוא formula_44. אליס שולחת לבוב את המפתח הציבורי שלה formula_45. הפונקציה formula_46 מקבלת שלם כלשהו formula_47 ונקודה formula_48 בעקום 25519 ומחזירה את formula_49. בוב שולח לאליס את המפתח הציבורי שלו formula_50. הסוד המשותף הוא:
במילים, הסוד המשותף מתקבל מהכפלת הסוד הפרטי של כל משתמש במפתח הציבורי של המשתמש השני. הרעיון כאן הוא שהמשתמשים אינם חושפים את הסודות שלהם, תחת זאת הם מכפילים את הסודות בנקודה הקבועה ושולחים את התוצאה ברשת האינטרנט. ניסיון לנחש את השלם שאיתו בוצע כפל סקלרי של נקודה קבועה כלשהי בעקום קשה מאוד והוא נחשב לבעיה מתמטית קשה הנקראת "בעיית הלוגריתם הבדיד בעקום אליפטי". ניסיון לנחש את הסוד המשותף מתוך שני המפתחות הציבוריים נקרא בעיית דיפי-הלמן בעקום אליפטי וגם היא נחשבת כבעיה קשה, אם כי אין הוכחה שהיא קשה לפחות כבעיית הלוגריתם הבדיד. בדרך כלל מהסוד המשותף גוזרים מפתחות הצפנה ואימות באמצעות פונקציית גיבוב קריפטוגרפית.
עקום 25519 נבנה כך שיהיה עמיד נגד מספר מלכודות הנובעות מאופן היישום שלו בפועל. העקום עמיד נגד התקפת תיזמון, הוא יכול לקבל כל מחרוזת באורך 32 בתים כמפתח ציבורי תקף ואינו דורש אימות.
היסטוריה ושימושים.
עקום 25519 זכה לפופולריות רבה מאז פורסם, אולם ההתעניינות הגוברת בו החלה אחרי 2013 כשנודע שה-NSA שתלו דלת אחורית בעקום האליפטי DUAL EC DRBG שהיה חלק מתקן ההצפנה בעקום אליפטי של NIST. אף על פי שאין קשר ישיר ביניהם, החשיפה הגבירה את החשש בקרב המשתמשים מפני דלתות נוספות שייתכן נשתלו במרכיבים אחרים של התקן כמו העקומים הקבועים P-xxx. ברוס שנייר מגדולי הקריפטוגרפים בני זמננו התבטא פעם: "איני סומך יותר על העקומים הקבועים שלהם. אני מאמין שה-NSA ביצעו מניפולציות בעזרת הקשרים שלהם עם התעשייה". הוא גם ציין שה-NSA מסוגלים לפצח כל הצפנה באינטרנט (נכון ל-2013).
עקום 25519 הפך לתקן בפועל שהחליף את P-256 והוא בשימוש במגוון רחב של יישומים. החל מ-2014 פרוטוקול OpenSSH הטמיע את העקום כברירת מחדל בישומים מבוססי ECDH. ספריות קריפטוגרפיות רבות תומכות בעקום זה ביניהן: OpenSSL וכן Libgcrypt, Crypto++ ועוד רבים. בין הפרוטוקולים, האפלקציות ומערכות ההפעלה המשתמשים בעקום זה נמנים:
ביטחון ויעילות.
הביטחון של העקום הזה נחשב גבוה, כלומר לא קיימת דרך לחשיפת הסוד המשותף מתוך שני המפתחות הציבוריים שהיא טובה יותר מכוח גס בסיבוכיות של formula_52. הבעיה הכללית עליה הוא מבוסס, בעיית דיפי הלמן בעקום אליפטי נחקרה באופן אינטנסיבי מזה כשני עשורים והותקפה רבות על ידי מתמטיקאים, אנליסטים והאקרים ללא הצלחה. עקום 25519 מכיל מספר תכונות שמעניקות לו יתרון, הסדר שלו הוא מעל formula_53, הוא אינו מכיל מאפיינים אלגבריים ייחודיים שניתנים לניצול לקיצור ההתקפה נגדו. האלגוריתמים הידועים כמו אלגוריתם רו או אלגוריתם קנגורו של פולרד ואלגוריתם פוליג-הלמן יעילים רק נגד עקומים מסדר ראשוני נמוך יותר ולכן אינם פרקטיים נגד עקום 25519.
היתרון של עקום 25519 הוא באופן המימוש שלו. אפשר לנצל את יחידת הנקודה הצפה בקיצור FPU של המעבד כדי להאיץ ביצועים של פעולות כפל וחיבור בסיסיות באופן משמעותי. הסיבה לבחירה של הראשוני formula_1 נובעת בגלל היכולת לייצג אלמנטים של השדה בצורה פולינומית ולבצע חיבור וכפל במהירות. הפולינומים נבחרו כך שיענו על שני מאפיינים חשובים, שהמעלה שלהם תהיה נמוכה (לכל היותר 9) כך שיהיו פחות מקדמים שצריך לכפול כחלק מהכפל בפולינומים וכן, כל מקדם הוא כפולה קטנה של formula_55. ביתר פירוט הפולינומים עם מספר מופחת של מקדמים קטנים הם מהצורה:
כאן הפולינום formula_60 מייצג את השלם formula_61 שהוא בעצם פיצול של שלם באורך 256 סיביות לעשרה שלמים באורך 26 סיביות כל אחד בקירוב, כדי שיתאימו באורכם לאוגרי הנקודה הצפה המצויים בכל מעבד. כל שלם באורך 256 סיביות ניתן לטעינה בתשעה אוגרים. בדרך כלל במעבדים מודרניים אוגרים אילו מצויים בשפע. השימוש בבסיס 25.5 ולא בבסיס 25 או 26 נובע מסיבות של יעילות כדי להימנע מחילוק ארוך במקדמים formula_62 ו-formula_63 וכן להימנע מכפל המקדמים ב-formula_64 במקום ב-19.
חיבור/חיסור שני פולינומים של עקום 25519 מודולו formula_1 מצריך 10 פעולות חיבור/חיסור של מספרי נקודה צפה (fp). כל פעולת חיבור/חיסור צורכת 10 פקודות fp בסיסיות, בלולאה הראשית של הפונקציה Curve25519 מתבצעים בסך הכול 20,400 פקודות fp. פעולת כפל צורכת 100 פקודות fp עבור כפל ו-81 פקודות fp עבור חיבור. המקדמים הגבוהים formula_66 לאחר תוצאת הכפל מצומצמים מודולו formula_67. למשל המקדם formula_68 מוכפל ב-formula_69 ומחובר למקדם formula_70. כל צמצום דורש פקודת fp אחת לכפל ופקודת fp אחת לחיבור. החלק הגבוה (הכפולה הקרובה ביותר לחזקה של 2) של כל מקדם מחוסר ומחובר למקדם שלפניו. כל העברה כזו צורכת בסך הכול 4 פקודות fp. כך שלצורך הצמצום המודולרי נדרשים עוד כ-60 פקודות fp. כתיבת הקוד עדיפה באסמבלי כדי להימנע מתקורה מיותרת שעלולה לקרות ביישום בשפת C.
ראוי לציין שכאשר מחשב קוונטי לשימוש כללי בקנה מידה גדול יהיה מעשי, ניתן יהיה לפתור את בעיית דיפי הלמן בעקום 25519 ובעקומים אליפטיים אחרים בקלות רבה ולכן הפרוטוקול לא יהיה בטוח לשימוש במקרה כזה.
הפונקציה Curve25519.
הפונקציה Curve25519 היא בעצם כפל סקלרי של הקואורדינטה formula_71 מעל העקום formula_72, כאשר formula_24 הוא המספר הראשוני formula_1 ו-formula_75 הוא העקום האליפטי formula_4.
ביתר פירוט, השדה formula_77 מוגדר כקבוצת כל האלמנטים formula_78. תהי הפונקציה formula_79 מוגדרת כדלהלן: formula_80. במילים אחרות formula_81 היא פונקציה שממירה נקודה בעקום לאלמנט בשדה (פשוט על ידי נטילת הקואורדינטה formula_5 והתעלמות מהקואורדינטה formula_16). תהי הפונקציה formula_84 המוגדרת כדלהלן: formula_85.