פרמטרי התחום (domain parameters) של מערכת הצפנה בעקום אליפטי כוללים עקום אליפטי מתאים formula_27 המוגדר מעל שדה סופי formula_97 עם מציין formula_57 ונקודת בסיס formula_175 בנוסף למספר ערכים חשובים המהווים חלק בלתי נפרד מהמערכת. פרמטרי התחום יכולים להיות משותפים לקבוצת משתמשים או ספציפיים למשתמש יחיד. בחירת פרמטרים נכונה היא חלק קריטי בביטחון מערכת הצפנה כזו ולכן התקן מפרט צעדים מומלצים כיצד לייצר באופן אקראי או לבחור בעקום אליפטי יחד עם אוסף הפרמטרים באופן בטוח לשימוש קריפטוגרפי וכיצד לוודא שאכן עקום אליפטי אכן נוצר באופן שעונה על כל הדרישות האמורות. פרמטרי התחום של עקום אליפטי לצורך קריפטוגרפי הם:
חשוב לוודא תקפות הפרמטרים לפני שמשתמשים בהם, כדי לוודא תקינותם יש לפעול כדלהלן:
בתקן SEC-1 של GSEC (חברת Certicom הקנדית) ובתקן של NIST, נקבע הבסיס האריתמטי או ייצוג האלמנטים לפי סוג השדה, בשדה ראשוני formula_97 האלמנטים הם השלמים מודולו formula_169 ונקודה בעקום מיוצגת על ידי קואורדינטות שלמות formula_218. בשדה עם מציין 2 האלמנטים מיוצגים בבסיס פולינומי כאשר השדה הוא formula_182 וקואורדינטות הנקודה הן פולינומים ממעלה formula_220.
סדר העקום האליפטי.
מספר הנקודות בעקום האליפטי חשוב מאוד לביטחון מערכת ECC כאמור, כדי למנוע התקפות קריפטוגרפיות מסוימות שמנצלות סדר חבורה שמכיל גורמים קטנים. ספירת נקודות העקום אפשרית בזמן פולינומי עם מספר אלגוריתמים ידועים ביניהם אלגוריתם של שוף (schoof) שהורחב ושופר לאחר מכן על ידי קובליץ אלקיס ואטקין ונקרא אלגוריתם SEA. עם אלגוריתם SEA אפשר לספור את נקודות עקום אליפטי מעל שדה סופי מסדר 200 בתוך מספר שעות. אלגוריתם SATOH פותח במיוחד לספירת נקודות עקום אליפטי מעל שדה בינארי מורחב, למשל אם formula_221 אפשר לספור את נקודות העקום עם אלגוריתם SATOH בתוך מספר שניות.
הכנת עקום אליפטי באופן אקראי.
הכנת עקום אליפטי באופן אקראי נעשית לפי התקן עם פונקציית גיבוב קריפטוגרפית כמו SHA-2 כאשר הגרעין ההתחלתי משמש כהוכחה שהעקום אכן נוצר באופן אקראי ולא נוצר במכוון כך שיכיל חולשות או דלתות סתר. הרעיון הכללי הוא שמכינים עם פונקציית הגיבוב מתוך גרעין התחלתי seed מחרוזת סיביות אקראית באורך הרצוי formula_222. מייצגים את המחרוזת formula_223 כמספר בינארי שלם formula_224 ומוודים שלא מתקיים formula_225 וכן בוחרים שני שלמים אקראיים formula_226 כך שמתקיים formula_227. הגרעין ההתחלתי צריך להישמר יחד עם העקום והוא משמש כהוכחה. הוא מייצר באותה דרך מחרוזת סיביות formula_228 ומוודא שמתקבל formula_229 אם התנאי לא מתקיים זו הוכחה שהעקום לא נבחר באקראי.
מפתח פרטי ומפתח ציבורי.
בהינתן הפרמטרים הציבוריים formula_230 המפתח הפרטי הוא שלם formula_231 אקראי בטווח formula_232 הנשמר בסוד והמפתח הציבורי המתאים הוא formula_233 שהוא כפל סקלרי של הנקודה formula_17 עם המפתח הפרטי formula_231. בדרך כלל המפתחות של כל משתמש צריכים להיות מאומתים ומשויכים אליו בדרך כלשהי. בדרך קריפטוגרפית מאמתים מפתח באמצעות חתימה דיגיטלית או תעודה (certificate) שמונפקת על ידי רשות מאשרת (CA). וכן בדרך כלל קיימת הפרדה בין המפתחות הקבועים המיועדים לטווח ארוך לבין מפתחות ארעיים (ephemeral keys) הנוצרים לצורך התקשרות ספציפית. יש צורך תמיד לאמת תקפות המפתח הציבורי, לוודא שמקיים את התנאים המפורטים לעיל; ש-formula_18 הוא נקודה בעקום שאינה formula_36 וכן שהקואורדינטות formula_238 שלה הם אלמנטים בשדה formula_97 בטווח המתאים וכן שמתקיים formula_240. בפועל משתדלים להימנע מהבדיקה האחרונה כיוון שהיא פעולה מכבידה במונחי מחשוב, אפשר לחסוך בדיקה זו על ידי שימוש בפרוטוקול שיתוף מפתח עם אימות כמו MQV שבו הבדיקה עקיפה ונעשית כחלק ממהלכי הפרוטוקול.
הצפנה עם עקום אליפטי.
ניתן ליישם את צופן אל-גמאל בעקום אליפטי כדלהלן; בהינתן המפתח הציבורי של בוב הנקודה formula_18, אם אליס מעוניינת להצפין את המסר formula_181 עליה תחילה להמירו לנקודה formula_243 בעקום ואותה להצפין על ידי חיבור עם formula_244, כאשר formula_76 שלם אקראי "טרי" חד-פעמי שנבחר על ידה כדי להצפין את formula_243 ובנוסף היא צריכה להצפין ולשלוח את המפתח formula_76. ביתר פירוט, אליס משדרת לבוב בערוץ הפתוח שני ערכים: formula_248 שמכיל את המפתח המוצפן וכן formula_249 שמכיל את המסר המוצפן. כאשר בוב מקבל את הערכים הללו מאליס הוא מבצע את הפעולות בסדר הפוך, הוא מפענח את המפתח המוצפן ואז מחסיר את התוצאה מהטקסט המוצפן כדי לקבל את הנקודה formula_243 וממנה לחלץ את המסר formula_181. זה עובד היות שמתקיים
כאשר formula_231 הוא המפתח הפרטי של בוב המקיים formula_233. לכן היות ש-formula_255 בוב יכול להחליפו בביטוי formula_256 ולקבל את formula_243. המאזינה איב שמעוניינת לגלות את formula_243 צריכה לחשב תחילה את formula_244, חילוץ formula_244 מתוך formula_18 ומתוך formula_262 היא בדיוק בעיית דיפי-הלמן. למען הפשטות הגרסה המתוארת חסרה מספר מרכיבים חשובים כמו אימות ובדיקת תקפות. להלן תיאור פרוטוקול הצפנה היברידי שנקרא ECIES (קיצור של Elliptic Curve Integrated Encryption Scheme) שהוצע על ידי בלייר ורוגווי, המשלב הצפנה אסימטרית המבוססת על צופן אל-גמאל והצפנה סימטרית עם אימות. הוכנס לתקן ANSI X9.63 וכן ISO/IEC 15946-3 וכן IEEE P1363. בפרוטוקול זה מנצלים את פרוטוקול שיתוף הסוד הבסיסי של דיפי והלמן כדי לשתף שני מפתחות סודיים formula_263 כאשר formula_264 משמש להצפנת המסר ו-formula_265 לאימות התוצאה להגנה מפני התקפת מוצפן-נבחר. לצורך הפרוטוקול מוגדרות שלוש פונקציות בסיסיות; KDF - פונקציית הכנת מפתח שהיא תוצאת פונקציית גיבוב של גרעין כלשהו formula_266 ומונה כלשהו שמשתנה בכל קריאה, המשורשרים יחד. E - פונקציית הצפנה סימטרית כמו AES וכן MAC - פונקציית אימות כמו HMAC.
הצפנה.
נתונים פרמטרי התחום formula_267, המפתח הציבורי formula_18 והמסר formula_181.
התוצאה היא השלישייה: הטקסט המוצפן formula_166, תג האימות formula_283 והאלמנט formula_284.
פענוח.
נתונים פרמטרי התחום formula_267, המפתח הפרטי formula_231, האלמנט formula_284 יחד עם הטקסט המוצפן formula_166 ותג האימות formula_283 (כמובן שיש לוודא את תקפות כל הפרמטרים לפי התקן).
הטקסט המקורי הוא formula_181. אפשר לראות שאם הטקסט המוצפן formula_297 נוצר על ידי המשתמש הלגיטימי כאשר הצפין את formula_181 הרי שמתקיים
בהצפנה שורות 1 ו-2 הן דיפי-הלמן, הכפל ב-formula_157 נועד להבטיח באופן עקיף שהתוצאה בטווח המותר. פעולה 3 באלגוריתם ההצפנה ופעולה 2 באלגוריתם הפענוח מניבות תוצאה זהה, מכאן המקבל יכול לייצר את זוג המפתחות formula_301 שחישב השולח באמצעות אותה פונקציית KDF ולשחזר את הטקסט המוצפן. אך יש להישמר מהתקפת ערוץ צדדי כך שלתוקף לא תהיה דרך לדעת באיזה שלב של האלגוריתם הוחזרה הודעת שגיאה אם ארעה.
עקום אליפטי מעל שדה בינארי.
בשל החישובים המורכבים יישום מערכת הצפנה בעקום אליפטי בצורה נאיבית איטי ומסורבל. השאיפה היא שהמערכת תהיה אופטימלית (במונחי זמן עיבוד וצריכת זיכרון) ככל שניתן והדבר חשוב במיוחד במערכות ניידות שמטבען מוגבלות יותר ממקבילותיהן הנייחות. תכונות השדה הבינארי מאפשרות שיפור ביצועים בפעולות אריתמטיות בסיסיות, לכן תקני עקומים אליפטיים כוללים מפרטים למימוש הצפנה בעקום אליפטי מעל שדה בינארי מורחב.
שדה בינארי הוא שדה סופי בעל מאפיין 2, כאשר מספר האיברים בו הוא תמיד חזקה של 2. לכן ניתן ליצג כל אלמנט בשדה כמחרוזת של formula_302 סיביות. מקובל לסמנו formula_303. קיים רק שדה אחד בגודל formula_304 עבור כל שלם formula_302 נתון.
משוואת העקום האליפטי מעל שדה זה היא: formula_187 כאשר formula_307 וכן formula_202. הקבוצה formula_309 כוללת את כל הנקודות שהקואורדינטות שלהן formula_277 ו-formula_311 הן אלמנטים בשדה הבינארי המורחב אשר מקיימות את משוואת העקום, יחד עם הנקודה באין סוף formula_36. יחד עם פעולות החיבור והכפל מתקבלת חבורה ציקלית סופית מסדר formula_313 בקירוב.
כללי החיבור והכפל בעקום אליפטי מעל שדה בינארי מורחב שונות במעט: לחיבור הנקודות formula_314 ו-formula_315 כאשר formula_316 מבצעים:
כפל נקודה formula_319 כאשר formula_320 מתבצע על ידי:
למטרות הצפנה, מקובל לבחור formula_302 ראשוני גדול, משום שאז אין לשדה תת שדות. את גודלו של formula_302 יש לבחור בהתאם לדרישות האבטחה מחד, ולביצועים הרצויים מאידך. לשדות בינאריים יתרון ברור כשמדובר בחומרה ותוכנה, משום שפעולת החיבור בשדה מבוצעת על ידי פעולת ה-XOR, שהיא פעולה יסודית ומהירה במחשב.
דוגמה. נתון השדה הבינארי formula_324 בן 16 איברים, הניתן להצגה כהרחבה של השדה בן שני האיברים formula_325, כחוג המנה formula_326. באופן הזה, כל איבר בשדה הוא מהצורה formula_327 כאשר formula_328, ובאופן חסכוני אפשר להציג איבר כזה כמחרוזת סיביות, formula_329.
החבורה הכפלית של השדה היא חבורה ציקלית, הנוצרת (למשל) על ידי החזקות של היוצר formula_330 כדלהלן:
אם נבחר העקום האליפטי הבא:
formula_331
חישוב formula_332, מתבצע לפי כללי האריתמטיקה דלעיל:
ובייצוג בינארי:
formula_336
קואורדינטות פרויקטיביות.