הצפנה מבוססת עקום אליפטי
תקנים וזכויות יוצרים

על בסיס בעיית לוגריתם בדיד בעקום אליפטי (ECDLP) המתוארת לעיל, ניתן ליישם את פרוטוקול דיפי-הלמן (ECDH), חתימה דיגיטלית DSA מעל עקום אליפטי (ECDSA), אל-גמאל וכן פרימיטיבים קריפטוגרפיים אסימטריים אחרים כמו מחולל פסאודו אקראי. NSA הכריזה על חבילה קריפטוגרפית Suit B המנצלת הצפנת עקום אליפטי (ECC) כדור חדש של הצפנה. היא אמורה להחליף את הטכנולוגיה האסימטרית כ-RSA ודומיה להגנה על סודות לאומיים מסווגים ולא מסווגים של ממשלת ארצות הברית. כמו כן קיימת מערכת ECC המבוססת על תבנית ביליניארית (הנקראת גם Weil pairing) המשמשת למערכת אימות זהויות מבוססת ID (שבה זהות המשתמש מהווה חלק מהמפתח הפומבי) כמו כן חברת Certicom הקנדית משווקת מגוון גדול של מערכות אבטחה המבוססות על עקום אליפטי.
מסיבות של יעילות ביישומים מעשיים בדרך כלל מיישמים את ECC מעל שדה עם נקודה קבועה בעלת תכונות מסוימות שמאפשרות חישוב כפל סקלארי במהירות וביעילות. מציאת הסדר של עקום אליפטי (קרי, מספר הנקודות) אינו דבר קל, קיימים אלגוריתמים לשם כך (כמו אלגוריתם שוף). כיוון שסדר החבורה חיוני בפרוטוקולים קריפטוגרפיים נהוג לבנות עקום אליפטי באופן כזה שהסדר קל לחישוב. למעשה התקנים למערכות ECC מגדירים פרוצדורות שונות להכנת עקום אליפטי בטוח העונה על הדרישות הרצויות וכן מכילים אוסף עקומים אליפטיים מומלצים לצורך ECC. היות שמלאכת הכנת עקום אליפטי לצורך קריפטוגרפי קשה ומסובכת, קיימים מספר תקנים בינלאומיים ראויים לציון, המכסים עקומים אליפטיים קבועים שהוכנו במיוחד על ידי מומחים לשימוש כללי כחלק ממערכת הצפנת ECC תוך התחשבות ברמת הביטחון הנדרשת ויעילותה. החשובים שבהם:
| שם התקן | שנת הוצאה |
| --- | --- |
ANSI X9.62: 1999
IEEE P1363: 2000
SEC 2: 2000
NIST FIPS 186-2: 2000
ANSI X9.63: 2001
Brainpool: 2005
NSA Suite B: 2005
ANSSI FRP256V1: 2011
דוגמה לעקום אליפטי שאינו מומלץ כיום לשימוש הוא P-192 שנכלל בתקן FIPS 186-2 וכן ב-SEC v2 ומובא כאן להמחשה בלבד:
משוואת העקום היא  y^{2}=x^{3}+3 מעל השדה  \mathbb {F} _{p} כאשר  p הוא ראשוני באורך 192 סיביות. סדר העקום הוא  n והפרמטרים  p,a,b,G,n,h הם לפי הסדר:
| שם פרמטר | ערך | תיאור |
| --- | --- | --- |
|  p |  2^{192}-2^{32}-2^{12}-2^{8}-2^{7}-2^{6}-2^{3}-1 |  \mathbb {F} _{p} המספר הראשוני של השדה |
|  a |  000000000000000000000000000000000000000000000000 | מקדם ראשון של משוואת העקום |
|  b |  000000000000000000000000000000000000000000000003 | מקדם שני של משוואת העקום |
|  G |  {\text{03 DB4FF10E C057E9AE 26B07D02 80B7F434 1DA5D1B1 EAE06C7D}} | נקודת הבסיס בפורמט דחוס |
|  G_{x} |  {\text{04 DB4FF10E C057E9AE 26B07D02 80B7F434 1DA5D1B1 EAE06C7D}} | קואורדינטה  x של נקודת הבסיס |
|  G_{y} |  {\text{9B2F2F6D 9C5628A7 844163D0 15BE8634 4082AA88 D95E2F9D}} | קואורדינטה  y של נקודת הבסיס |
|  n |  {\text{FFFFFFFF FFFFFFFF FFFFFFFE 26F2FC17 0F69466A 74DEFD8D}} | הסדר של העקום |
|  h |  01 | פקטור משלים |
בשל העובדה שחלק ממערכות ECC מוגנות בפטנטים הפצתן והטמעתן התעכבה. חברת Certicom מחזיקה בכמאה וחמישים פטנטים הקשורים בהיבטים שונים של ECC. חברת אפל מחזיקה בפטנטים על יישום יעיל של ECC מעל השדה  \ GF(p) כאשר  \ p קרוב לחזקה של 2. ה-NSA רכשו זכויות שימוש במערכות ECC של חברת Certicom הקנדית והוסמכו לתת רישיון לכל גוף המעוניין לשלב ECC באפליקציות אבטחה בהן נעשה שימוש עבור ממשלת ארצות הברית. בעקבות החשיפות בפרשת סנודן, עלה חשש בציבור שחלק מתקני עקום אליפטי במיוחד אילו של NIST מכילים דלתות סתר שמאפשרות למי שיודע אותם לפרוץ את המערכת בקלות אם כי לא קיימות הוכחות ברורות לכך מלבד מקרה אחד. בעקבות הדלפות סנודן, פורסם בספטמבר 2013 בניו יורק טיימס שכחלק מפרויקט סודי של ה-NSA הנקרא "Bullrun" שמטרתו החדרת נקודות תורפה נסתרות בתקני הצפנה החדיר ה-NSA "דלת אחורית" במחולל הפסאודו אקראי Dual_EC_DRBG שהפך לתקן ובעקבות הפרסומים החליט NIST להפסיק לתמוך באלגוריתם והסיר אותו מהתקן. כיום NIST מנהל מדיניות פתוחה ומשתף פעולה באופן נרחב עם הקהילה האקדמית ועם גורמי תקינה בינלאומיים.
כל אחד מהתקנים המתוארים מנסה להבטיח שבעיית הלוגריתם הבדיד בעקום אליפטי תהיה קשה ככל האפשר בעקום שהוא תומך בו. הבעיה היא שקיים פער בין קושיה המשוער של בעיית דיפי הלמן בעקום אליפטי לבין הביטחון של מערכת ה-ECC בפועל. כלומר, במציאות קורה לא אחת שקל לפצח את המערכת מבלי לפתור את בעיית דיפי הלמן או בעיית הלוגריתם הבדיד. הסיבה העיקרית היא שיש סיכויים טובים שמי שמימש את העקום בתוך מערכת ההצפנה עשה זאת בצורה שגויה. בגלל שיישומו בפועל עלול להדליף שלא במודע מידע קריטי, אם בשל יישום לקוי, טיפול לא נכון במקרי קצה ומצבי שגיאה או בגלל מידע תזמון שדולף מהמעבד או זיכרון המטמון בזמן ביצוע החישובים האריתמטיים. מימוש בטוח של הצפנת עקום אליפטי אפילו אם הוא תואם את התקן, מתגלה כמשימה קשה מאוד. יתרה מזו, כל התקנים שואפים להבטיח יעילות גבוהה ככל האפשר בנוסף לביטחון. עובדה זו מטילה מגבלות נוספות על אופן המימוש שלו. מחקרים מראים שבמקרים אחדים לא רק שהעקום לא היה יעיל, אלא שכל המגבלות והאופטימיזציות שנוספו רק השפיעו לרעה על יעילות העקום ובעיקר על ביטחונו.