לדוגמה יהיו formula_51 ומשוואת העקום formula_52 מעל השדה formula_53 המכיל את 29 הנקודות formula_54 המובאות להלן יחד עם נקודת האין סוף formula_36, כאשר formula_56:
היות ש-formula_57 ראשוני, השדה formula_58 הוא ציקלי (מחזורי) ולכן מכיל יוצרים. למשל הנקודה formula_59 היא יוצר. אפשר לראות שאם מחברים את הנקודה formula_17 בעצמה 29 פעמים מתקבלות כל נקודות העקום לא בהכרח לפי הסדר, עד שמגיעים לנקודת האין סוף, כלומר formula_61.
דוגמה לחיבור שתי נקודות. אם נבחר את הנקודות formula_62 ו-formula_63 החיבור formula_64 מבוצע כך:
תחילה formula_65,
ואז formula_66.
לכן התוצאה היא formula_67.
כדי להכפיל את הנקודה formula_62 בשתים, formula_69 מחשבים כדלהלן:
תחילה formula_70,
ואז formula_71.
ולכן formula_72.
כפל סקלרי.
להבדיל מכפל רגיל מכנים פעולת כפל נקודות בעקום בשם כפל סקלרי (Scalar Multiplication). הכפלה של נקודה formula_24 בשלם formula_74 כלשהו היא בעצם פעולת חיבור חוזר formula_75 בסך הכול formula_76 פעמים. פעולה זו ניתן לבצע על ידי אלגוריתם רקורסיבי המנצל את הייצוג הבינארי של formula_74 כדי לבצע פעולות חוזרות של חיבור וכפל המתוארים לעיל. קיימות שיטות רבות לביצוע כפל נקודה בעקום אליפטי. דוגמה אחת נקראת "שיטה בינארית מימין לשמאל" והיא מתבצעת כדלהלן:
בשיטה זו זמן החישוב תלוי ב-formula_74 ועל-כן בתנאים מסוימים עלול לחשוף את המערכת להתקפות ערוץ צדדי. קיימות שיטות מתקדמות ויעילות יותר לביצוע כפל סקלרי כמו שיטת חלון (sliding window) או שיטת מונטגומרי. ההתמודדות עם התקפות ערוץ צדדי תלויות מאוד באופן היישום ובסביבה בה האלגוריתם מיושם.
עקום אליפטי בקריפטוגרפיה.
חשיבות עקום אליפטי בתורת ההצפנה היא בעובדה שהוא מועמד טוב לפונקציה חד-כיוונית שהכרחית בכל הצפנה א-סימטרית. לדוגמה אם נתונה הנקודה formula_17 ושלם כלשהו formula_76, מצד אחד חישוב formula_93 (באמצעות אלגוריתם רקורסיבי כמו זה המתואר לעיל) קל לביצוע במחשב, לעומת זאת, בהינתן הנקודה formula_82 מאוד קשה לגלות את formula_76. זוהי בעיה מתמטית קשה הנקראת בעיית הלוגריתם הבדיד בעקום אליפטי. לסדר העקום (מספר הנקודות בעקום) חשיבות רבה, בפרט על העקום להכיל תת-חבורה מסדר ראשוני גדול.
קיימים בעיקר שלושה פרימיטיבים קריפטוגרפיים מבוססי עקום אליפטי; הצפנה אסימטרית, חתימה דיגיטלית ופרוטוקול שיתוף מפתח, שלושתם מבוססים על גרסת העקום האליפטי של בעיית הלוגריתם הבדיד, בעיית דיפי-הלמן ובעיית הכרעת דיפי-הלמן, הנגזרות ממנה. בעיות המוגדרות קשות חישובית, אם כי לא ידועה הוכחה מתמטית לכך. בחבורת אוילר של שדה סופי קיימים אלגוריתמים תת-מעריכיים לפתרון הבעיות המנויות, אך האלגוריתם היעיל ביותר (הידוע) לפתרון בעיות (במחשב קלאסי) אלו עבור עקומים אליפטיים הוא בעל זמן ריצה מעריכי. עקב כך, מפתחות ההצפנה בעקום אליפטי קטנים משמעותית ביחס למפתחות הצפנה בצפנים המבוססים על שדות סופיים, כמו צופן אל-גמאל או צופן RSA. יש לציין שקיים אלגוריתם קוונטי לפתרון הבעיות הללו בעזרת מחשב קוונטי ביעילות, הן עבור חבורת אוילר והן עבור עקום אליפטי. לכן כאשר מחשב קוונטי לשימוש כללי בקנה מידה גדול יהיה מעשי הצפנה המבוססת על עקום אליפטי לא תהיה בטוחה יותר לשימוש.
ישנו פרימיטיב נוסף שקשור לעקומים אליפטיים הנקרא הצפנה מבוססת איזוגניה. זהו תחום מחקר חדש יחסית בקריפטוגרפיה, המבוסס על איזוגניות בין עקומים אליפטיים. לא ידוע על אלגוריתם קוונטי יעיל לפתרון הבעיה ולכן היא מועמדת טובה להצפנה פוסט-קוונטית.
בעיית הלוגריתם הבדיד בעקום אליפטי בקיצור ECDLP.
השלם formula_76 נקרא הלוגריתם הבדיד (דיסקרטי) של formula_18 בבסיס formula_17 ואפשר לסמנו בקיצור formula_106. הסימן formula_107 מייצג את החבורה הציקלית formula_108 שהיא אוסף הנקודות שהן כפולות של formula_17 יחד עם הנקודה באין סוף. שים לב שתמיד מתקיים formula_110.
בעיית דיפי-הלמן בעקום אליפטי בקיצור ECDHP.
בעיית דיפי-הלמן בעקום אליפטי המקבילה לבעיית דיפי-הלמן המפורסמת היא בעיה חישובית המוגדרת כך:
כמובן שאם ניתן לפתור ביעילות את בעיית ECDLP יהיה קל לפתור את ECDHP, ההפך לא הוכח למעט מקרים פרטיים אחדים. באופן כללי לא ידוע אם הבעיות שקולות.
בעיית הכרעת דיפי-הלמן בקיצור ECDDHP.
שתי השאלות הללו שקולות. כמובן שאם ניתן לפתור את ECDHP יהיה קל לפתור את ECDDHP. שופ הוכיח שקיים חסם תחתון שהוא formula_125 עבור בעיית ההכרעת דיפי-הלמן בעקום אליפטי, formula_99 הוא הסדר (מספר הנקודות).
הבעיות המתוארות מהוות בסיס לפונקציה חד כיוונית המתאימה לצורך קריפטוגרפי. עליהן אפשר לבנות פרוטוקולים קריפטוגרפיים בטוחים בהנחה שהבעיות אכן קשות לפתרון.
דוגמה ללוגריתם בדיד בעקום אליפטי.
אם נתון העקום: formula_127 מעל formula_128, הנקודות formula_129 ו-formula_130 הן בעקום formula_131 ומפני שהעקום מכיל רק 41 נקודות קל לגלות באופן ישיר שהלוגריתם הבדיד הוא:
באופן דומה formula_134 וכן formula_135. אחרי חישוב קל אפשר לראות שהם מקיימים formula_136 וכן formula_137 לכן:
אף על פי שלפי הנוסחה לעיל formula_140 היות ש-formula_141 למעשה סדר העקום הוא formula_142. כך שרק 41 מהנקודות בעקום זה הן כפולות של formula_17.
בחירת פרמטרים.
כדי להשתמש בעקום אליפטי לצורך פרוטוקול קריפטוגרפי יש לשים לב לכמה היבטים חשובים כדי למנוע חולשות שעלולות להוביל לנקודות תורפה ולשבירת המערכת. הפרמטרים הציבוריים של העקום נקראים "פרמטרי תחום" (Domain Parameters) שכאמור פומביים ומשותפים לכל המשתמשים במערכת אך יש לוודא את תקינותם. תחילה בוחרים "עקום מתאים" formula_27 המוגדר מעל שדה סופי formula_97 עם מציין formula_57 וכן בוחרים נקודת בסיס formula_98. כאשר ההגדרה "עקום מתאים" מתייחסת לכמה פרמטרים חיוניים כדלהלן; כדי למנוע התקפות המסתמכות על פתרון בעיית הלוגריתם הבדיד בעקום אליפטי (ECDLP) עם אלגוריתם רו של פולרד או פוליג-הלמן, חובה שלסדר העקום או מספר נקודות העקום המסומן ב-formula_148 יהיה גורם ראשוני formula_99 גדול דיו (למשל formula_150), ש-formula_151 כך שמספר הנקודות בעקום יהיה "כמעט ראשוני" וכן ש-formula_152. לפי משפט הסה בעקום אליפטי, מספר הנקודות של עקום אליפטי חסום על ידי
מזה נובע ש-formula_154 אינו מחלק של formula_148 ולכן לעקום זה קיימת תת-חבורה מסדר formula_99. ממשפט זה נובע גם שקיים שלם יחיד formula_157 הנקרא cofactor המקיים
במילים אחרות formula_159 ולכן מספר הנקודות של העקום הוא formula_160. וכדי למנוע התקפת תת-חבורה מסדר קטן המנצלת את סדר החבורה יש צורך שהנקודה formula_17 תהיה מסדר formula_99. וכדי למנוע התקפות המנצלות רדוקציה מעקום אליפטי לשדה סופי (מורחב) יש צורך שהעקום לא יהיה סופר-סינגולרי, כלומר לוודא ש-formula_99 אינו מחלק של formula_164 עבור כל formula_165 כאשר formula_166 גדול מספיק כך שמציאת לוגריתם דיסרקטי בשדה formula_167 יהיה קשה (למשל formula_168) וכן רצוי למנוע התקפה אחרת נגד "עקום אנומלי" שהוא עקום אליפטי שבו מספר הנקודות הוא בדיוק formula_169 (שהוא מספר ראשוני), לכן רצוי שסדר העקום לא יהיה formula_169. באופן כללי כדי למנוע התקפות אילו ואחרות (שמנצלות חולשות הנובעות מתכונות מיוחדות של העקום) האסטרטגיה המומלצת היא לבחור את העקום באופן אקראי בתנאי כמובן של-formula_148 יש גורם ראשוני גדול. הסבירות שעקום שנבחר כך יהיה פגיע לאחת ההתקפות הללו אינה גדולה. וכן חשוב לבחור את העקום באופן כזה שיהיה קל לוודא שהוא אכן עומד בתנאים המצוינים. אחת הדרכים היא אסטרטגיה דומה לזו שננקטה על ידי NIST בבחירת הפרמטרים עבור DSA בתקן FIPS 186 - קרי לעשות שימוש בפונקציית גיבוב כמו SHA-2 כגרעין התחלתי ממנו מפיקים את הפרמטרים האמורים, כמתואר בתקן ANSI X9.62. ואז יש כמובן לשמור גם את הגרעין ההתחלתי כחלק בלתי נפרד מסט הפרמטרים, כך שהמקבל יוכל לוודא באמצעותו שהפרמטרים תקינים ולא נבחרו באופן מעורר חשד.
יש לציין שהכנת עקום אליפטי בטוח לצורך קריפטוגרפי שעומד בכל התנאים הדרושים היא מלאכה קשה, מסיבה זו בפועל מעדיפים להשתמש ברשימות העקומים האליפטיים ונקודות בסיס הנלוות להם, שמסופקות על ידי ארגוני התקינה ומלוות בדרך כלל באמצעים המאפשרים לוודא שהם אכן עומדים בסטנדרטים המחמירים ביותר ובעיקר שאינם מכילים דלת אחורית (backdoor) - שהיא תכונה נסתרת באחד הפרמטרים שמאפשרת למי שמחזיק במידע סודי לשבור את המערכת בקלות.
ב-2013 התגלה כחלק מההדלפות של סנודן שה-NSA שתלו דלת אחורית באלגוריתם Dual_EC_DRBG שהיה חלק מתקן של NIST למחולל פסאודו אקראי קריפטוגרפי המבוסס על עקום אליפטי. מלבד זאת מומחים הביעו חשש בנוגע לאחדים מן הקבועים של NIST ש-NSA התערב בבחירתם. בשל כך נוצרה דרישה לעקומים אליפטיים תיקניים שאינם נמנים עם הרשימה של NIST. ב-2005 פרסם דניאל ברנשטיין את העקום Curve25519 המציע ביטחון ברמה של 128 סיביות והוא נמצא בשימוש נרחב כיום בין היתר על ידי OpenSSL וכן וואטסאפ.
פרמטרי התחום.