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

הצפנה בעקום אליפטי (Elliptic Curve Cryptography, ובקיצור ECC), היא מערכת הצפנה אסימטרית, שבה מממשים אלגוריתם הצפנה מוכר כמו (פרוטוקול דיפי-הלמן), באמצעות מבנה אלגברי-גאומטרי ייחודי בשם "עקום אליפטי", המוגדר מעל שדה סופי גדול. יש הסבורים כי בבחירת פרמטרים מושכלת, בטיחות שיטה זו אינה נופלת מזו של השיטות הידועות המבוססות ברובן על אריתמטיקה מודולרית, למרות שימוש במפתח הצפנה קטן משמעותית.

היסטוריה ורקע

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

רעיון השימוש בעקום אליפטי ככלי קריפטוגרפי הועלה לראשונה ב-1985 על ידי ויקטור מילר ומעט מאוחר יותר על ידי ניל קובליץ. כאמור רעיון יישום הצפנת מפתח-פומבי (כדוגמת פרוטוקול דיפי-הלמן) בשדות סופיים הנוצרים מעקום אליפטי, מציע יתרון משמעותי על פני שיטות הצפנה אסימטריות אחרות, בשל השימוש במפתח הצפנה קטן יותר. תכונה זו מאפשרת יישום יעיל של ההצפנה בסביבה מוגבלת במשאבים, כדוגמת מעגלים משולבים במתקנים ניידים כמו טלפון סלולרי, כרטיס חכם וכדומה.

הצפנת מפתח-פומבי מבוססת כידוע על פונקציה חד כיוונית עם דלת מלכודת (Trapdoor) שהיא "מידע נסתר" המכונה מפתח פרטי, בעזרתו שחזור הפונקציה הופך לקל. "הדור הראשון" של מערכות מפתח-פומבי כמו RSA ודומיה מתבססות על מספר מצומצם של בעיות מתמטיות קשות כפירוק לגורמים ולוגריתם דיסקרטי בחבורות. השאיפה היא שללא המפתח הפרטי, שחזור הפונקציה יהיה קשה לפחות כפתרון הבעיה המתמטית עליה היא מבוססת; טענה שלא הוכחה מתמטית בכל מערכות ההצפנה האסימטריות (למעט הצפנת רבין).

חסרונן העיקרי של שיטות אילו הוא באורך מפתח ההצפנה. בשל ההתקדמות הטכנולוגית (בעיקר בפירוק לגורמים), מפתחות ההצפנה במערכות מפתח-פומבי מסוג זה חייבים להיות בסדר גודל של אלפי ספרות בינאריות, בשל פגיעותן לאלגוריתמים ידועים לפתרון הבעיות עליהן הן מסתמכות. עובדה המאפילה על יעילותם, כיוון שחישובים אריתמטיים בסדר גודל כזה איטיים מאוד. על כן ברור מדוע הצפנת עקום אליפטי זוכה להתעניינות רבה מצד מומחים. ה-NSA כינה אותה "הדור השני" של הצפנת מפתח-פומבי. זאת משום שהאלגוריתמים הטובים ביותר הידועים כיום לפתרון הבעיות המתמטיות הנפוצות, אינם ישימים באופן כללי בעקומים אליפטיים, בשל כך ניתן להקטין באופן משמעותי את אורכם של מפתחות ההצפנה, מבלי לסכן את בטיחות המערכת.

הגדרה כללית

עקום אליפטי הוא עקום אלגברי פרויקטיבי חלק (שאין לו "קצוות חדים"), המוגדר על ידי משוואה ממעלה שלישית. ניתן להגדיר עקום אליפטי מעל כל שדה. מעל שדה בעל מאפיין שאינו 2 או 3, אפשר להגדיר את העקום באמצעות הנוסחה:

$\ \boldsymbol{y^2 = x^3 + ax + b}$

כאשר $\ a$ ו- $\ b$ קבועים. העקום הנו קבוצת כל הנקודות המקיימות את המשוואה האמורה, בתוספת נקודה מיוחדת הנקראת "הנקודה באינסוף", אותה מקובל לסמן ב-$\ \mathcal{O}$. המשוואה מתארת עקום אליפטי אם ורק אם הדיסקרימיננטה $\ 4a^3+27b^2 \ne 0$.

מעל שדה בעל מאפיין 2, צורתו של העקום האליפטי (שאינו סופרסינגולרי) נתונה על ידי:

$\ \boldsymbol{y^2+xy=x^3+ax^2+b}$, כאשר $\ b \ne 0$

שמם של עקומים אלה מגיע מהאינטגרלים האליפטיים, הקשורים באורך קשת האליפסה. מעל שדה המספרים המרוכבים, העקום איזומורפי לטורוס. ניתן להגדיר עקום אליפטי גם מעל שדה המספרים הממשיים, למשל אם $\ a=-4$ ו-$\ b=0.67$ מתקבל עקום אליפטי עם המשוואה: $\ y^2=x^3-4x+0.67$.

על אוסף הנקודות בעקום (לרבות הנקודה באינסוף) אפשר להגדיר פעולה בינארית $\ +$, ההופכת אותו לחבורה אבלית, שבה הנקודה באינסוף היא הנקודה הנייטרלית. מבחינה מעשית, חישוב הנקודה $\ (x_1,y_1) + (x_2,y_2) = (x_3,y_3)$, כאשר $\ (x_1,y_1)$ ו- $\ (x_2,y_2)$ נקודות נתונות על העקום, אורך כשלושים פעולות יסודיות של חיבור, כפל וחילוק בשדה שמעליו העקום מוגדר.

בתורת ההצפנה משתמשים בעקומים אליפטיים מעל שדה סופי. בפועל, מקובל לבחור בשדות $\ \mathbb{F}_p$ מסדר ראשוני גדול, או בשדות בינאריים $\ \mathbb{F}_{2^m}$, כאשר $\ m$ גדול.

אריתמטיקה בעקומים אליפטיים

בייצוג גרפי פעולת החיבור היא השתקפות הנקודה השלישית המשיקה ליישר העובר דרך שתי נקודות $\ \mbox{P}$ ו-$\ \mbox{Q}$ (ראו תרשים). כאמור כיוון שהעקום אינו סינגולרי, ישר העובר דרך שתי נקודות יחתוך את העקום בדיוק בנקודה נוספת אחת ויחידה. $\ \lambda$ מייצג את שיפוע הישר החותך את הנקודות. במקרה של $\ \mbox{P + -P}$ (כאשר $\ \mbox{-P}$ היא נקודת ההשתקפות של $\ \mbox{P}$) הישר העובר דרכם אנכי ולכן התוצאה מוגדרת כנקודת האין סוף $\ \mathcal{O}$, לכן $\ \mbox{P+}\mathcal{O}\mbox{=P}$.

כללי האריתמטיקה לעקום מעל שדה בעל מאפיין שאינו 2 או 3

סכום שתי נקודות (ECADD): אם נתונות הנקודות $\ \mbox{P}=(x_P,y_P)$ ו- $\ \mbox{Q}=(x_Q,y_Q)$, ואם $\ x_P \ne x_Q$, אזי הסכום $\ \mbox{R = P + Q}$ מחושב כדלהלן:

חיבור הנקודות: $\ \mbox{R = P + Q}$ בעקום אליפטי מעל השדה $\ \mathbb{F}_{23}$ מסדר ראשוני $\ p=23$.

$\ x_R = \lambda^2 - x_P - x_Q$

$\ y_R = \lambda(x_P-x_R) - y_P$

$\ \lambda = \frac{y_Q-y_P}{x_Q-x_P}$

הכפלת נקודה יחידה (ECDBL): את $\ \mbox{P+P=2P}$ מחשבים כדלהלן:

$\ x_R = \lambda^2-2x_P$

$\ y_R = \lambda(x_P-x_R)-y_P$

$\ \lambda= \frac{3x^2_P+a}{2y_P}$

במקרה ש- $\ y_P=y_Q=0$ אזי $\ \mbox{P+P}=\mathcal{O}$.

הנקודה ההפכית של $\ \mbox{P}=(x,y)$ היא $\ -\mbox{P}=(x,-y)$.

כללי האריתמטיקה לעקום מעל שדה בעל מאפיין 2 (לעקום שאינו סופרסינגולרי)

סכום שתי נקודות (ECADD) $\ \mbox{R=P+Q}$:

$\ x_R = \lambda^2+\lambda+x_P+x_Q+a$

$\ y_R = \lambda(x_P+x_R)+x_R+y_P$

$\ \lambda \equiv \frac{y_P+y_Q}{x_P+x_Q}$

הכפלת נקודה יחידה (ECDBL) $\ \mbox{R=P+P=2P}$:

$\ x_R = \lambda^2+\lambda+a$

$\ y_R = x^2_P+(\lambda+1) \cdot x_R$

$\ \lambda = x_P+\frac{y_P}{x_P}$

הנקודה ההפכית של $\ \mbox{P}=(x,y)$ היא $\ -\mbox{P}=(x,x+y)$.

פעולת כפל סקלרי (Scalar Multiplication)

להבדיל מכפל רגיל מכנים פעולת כפל נקודות בעקום בשם כפל סקלרי. הכפלה של נקודה $\ \mbox{P}$ בשלם $\ k$ כלשהו הינה בעצם פעולת חיבור חוזר $\ P+\cdots+P=k\cdot P$. פעולה זו ניתן לבצע על ידי אלגוריתם המנצל את הייצוג הבינארי של $\ k$ כדי לבצע פעולות חוזרות של חיבור וכפל המתוארים לעיל. בשיטה זו זמן החישוב תלוי ב-$\ k$ ועל-כן בתנאים מסוימים עלול לחשוף את המערכת להתקפות "Side Channel". קיימות שיטות אחרות, איטיות אך בטוחות יותר לביצוע כפל סקלרי.

דוגמה לאלגוריתם הצפנה בסיסי

אלגוריתם ההצפנה המתואר להלן אנלוגי לצופן אל-גמאל, אלא שכאן הוא מבוסס על עקום אליפטי. עקום אליפטי מספק כלי כללי ליצירת פונקציה חד כיוונית עם דלת מלכודת (Trapdoor) ולפיכך עקרונית ניתן לישם כל מערכת הצפנה אסימטרית העושה שימוש בפונקציה שכזו.

הכנת מפתחות

1. אליס בוחרת עקום אליפטי (הפרמטרים לבחירת העקום מפורטים בתקנים שונים) מעל שדה סופי $\ E(\mathbb{F}_p)$. ובוחרת נקודה קבועה $\ \mbox{P}$ כלשהי על העקום. נניח שלנקודה זו סדר $\ m$. אזי תת-החבורה הציקלית של $\ E(\mathbb{F}_p)$ הנוצרת על ידי $\ \mbox{P}$ היא:

$\ \left\{ {0,{\rm{P,2P,3P}},...,(m - 1){\rm{P}}} \right\}$

1. אליס בוחרת שלם אקראי $\ a$ בטווח $\ [1, m-1]$ אשר ישמש כמפתח פרטי, אותו היא שומרת בסוד.
2. המפתח הפומבי של אליס הוא: $\ \mbox{Q}=a\mbox{P}$.
3. הפרמטרים של העקום האליפטי, דהיינו $\ a, b, p, \rm{P}$, פומביים גם כן ומכונים "Domain Parameters".

הצפנה

בוב משיג עותק אותנטי של המפתח הפומבי של אליס ומצפין את המסר $\ m$ כדלהלן:

1. בוב מייצג את המסר $\ m$ כנקודה $\ M$ על העקום האליפטי.
2. בוחר מספר אקראי $\ r$ ומחשב את $\ rQ$ ואת $\ rP$.
3. ושולח לאליס הודעה מוצפנת המכילה את $\ C_1$ ואת $\ C_2$, כאשר: $\ C_1=rP$ ואילו: $\ C_2=M+rQ$.

פענוח

1. בעזרת המפתח הפרטי אליס מחשבת תחילה את $\ d=aC_1$.
2. ומשחזרת את $\ m$ על ידי חישוב $\ M=C_2-d$ והמרת הייצוג חזרה ל-$\ m$.

מדוע זה עובד

למעשה אליס מחשבת את: $\ d=aC_1=a(rP)=r(aP)=rQ$
ויכולה לשחזר את $\ M$ מכיוון ש- $\ C_2-d=(M+rQ)-rQ=M$.

טכניקות להאצת תהליך ההצפנה וייעולו

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

עקום אליפטי בשדה בינארי

שדה בינארי הוא שדה סופי בעל מאפיין 2, כאשר מספר האברים בו הוא תמיד חזקה של 2. לכן ניתן ליצג כל אלמנט בשדה כמחרוזת של $\ m$ סיביות. מקובל לסמנו $\ \mathbb{F}_{2^m}$. קיים רק שדה אחד בגודל $\ 2^m$ עבור כל שלם $\ m$ נתון.

למטרות הצפנה, מקובל לבחור $\ m$ ראשוני גדול, משום שאז אין לשדה תת שדות. את גודלו של $\ m$ יש לבחור בהתאם לדרישות האבטחה מחד, ולביצועים הרצויים מאידך. לשדות בינאריים יתרון ברור כשמדובר בחומרה ותוכנה, משום שפעולת החיבור בשדה מבוצעת על ידי פעולת ה-XOR, שהיא פעולה יסודית ומהירה במחשב.

דוגמה. נתון השדה הבינארי $\ \mathbb{F}_{2^4}$ בן 16 אברים, הניתן להצגה כהרחבה של השדה בן שני האברים $\ \mathbb{F}_2=\{0,1\}$, כחוג המנה $\ \mathbb{F}_2[x]/<x^4+x+1>$. באופן הזה, כל איבר בשדה הוא מהצורה $\ s=a_0+a_1x+a_2x^2+a_3x^3$ כאשר $\ a_0,\dots,a_3\in \mathbb{F}_2$, ובאופן חסכוני אפשר להציג איבר כזה כמחרוזת סיביות, $\ s=(a_3a_2a_1a_0)$.

החבורה הכפלית של השדה היא חבורה ציקלית, הנוצרת (למשל) על ידי החזקות של היוצר $\ g=(0010)$ כדלהלן:

$\ g^0=(0001)$	$\ g^1=(0010)$	$\ g^2=(0100)$	$\ g^3=(1000)$	$\ g^4=(0011)$	$\ g^5=(0110)$
$\ g^6=(1100)$	$\ g^7=(1011)$	$\ g^8=(0101)$	$\ g^9=(1010)$	$\ g^{10}=(0111)$	$\ g^{11}=(1110)$
$\ g^{12}=(1111)$	$\ g^{13}=(1101)$	$\ g^{14}=(1001)$

אם נבחר העקום האליפטי הבא: $\ y^2+xy=x^3+(1000)x^2+(1001) \,\,\,\boldsymbol{=}\,\,\, y^2+xy=x^3+g^3x^2+g^{14}$

חישוב $\ \mbox{R = P=}(g^1,g^{12}) + \mbox{Q=}(g^6,g^6)$, מתבצע לפי כללי האריתמטיקה דלעיל:

$\ \lambda = (g^{12} + g^6) \cdot (g^1 + g^6)^{-1} = g^8$

$\ x_R = (g^8)^2 + g^8 + g^1 + g^6 + g^3 = g^0$

$\ y_R = g^8 \cdot (g^1+g^0) + g^0 + g^{12} = g^0$

ובייצוג בינארי: $\ (0010, 1111) + (1100, 1100) = (0001, 0001)$

קואורדינטות פרויקטיביות

אפשר לראות שחיבור נקודות בעקום אליפטי דורש בנוסף לכפל וחיבור רגילים פעולת היפוך (inverse) קרי, חישוב הופכי כפלי מודולרי: בהינתן $\ a$ לחשב את $\ x=a^{-1}$ המקיים: $\ a \cdot x \equiv 1 \ (\mbox{mod }p)$. בדרך כלל חישוב הופכי כפלי היא פעולה יקרה במונחי חישוב ומשתדלים להימנע ממנה כשאפשר. קיימת דרך יישום ל-ECC הנקראת מערכת פרויקטיבית (projective system), המאפשרת חיבור נקודות בלי השימוש בהיפוך. מערכת זו מכילה 3 קואורדינטות $\ \mbox{(X,Y,Z)}$ עבור כל נקודה, כאשר $\ x = \mbox{X/Z}$ ו-$\ y=\mbox{Y/Z}$.

צמצום מודולרי

ניתן ליעל באופן משמעותי את פעולת הצמצום המודולרי הדרושה בכפל וחיבור בעקום אליפטי אם הראשוני $\ p$ הוא מספר מרסן (מספר מהצורה $\ 2^s-1$) לדוגמה $\ 2^{251}-1$. עקומים עם מספר ראשוני מסוג זה מומלצים על ידי NIST בליווי הסברים כיצד לבצע צמצום מודולרי יעיל במספרים אלו.

בטיחות

כיון שקיימת הקבלה בין החבורה הנוצרת מעקום אליפטי בשדה סופי והחבורה הכפלית מודולו ראשוני $\ p$. אפשר למעשה להגדיר את בעיית לוגריתם דיסקרטי בעקום אליפטי כדלהלן: בהינתן עקום אליפטי $\ E$ מעל $\ \mathbb{Z}_p$ מסדר $\ n$, הנקודה $\ \mbox{P} \in \mbox{E}(\mathbb{Z}_P)$ והנקודה $\ \mbox{Q} \in \mbox{E}(\mathbb{Z}_P)$, מצא שלם $\ l$ בטווח $\ 0 \le l \le n-1$, המקיים $\ \mbox{Q} = l \mbox{P}$ בתנאי ששלם כזה אכן קיים. בעיית לוגריתם דיסקרטי בעקום אליפטי (ECDLP) נחשבת לבעיה קשה יותר מבעיית לוגריתם דיסקרטי בחבורות. האלגוריתם היעיל ביותר הידוע כיום לפתרון בעיית לוגריתם דיסקרטי בחבורות, תחשיב האינדקסים אינו ישים בעקומים אליפטיים כיוון שהוא מסתמך על "מספרים חלקים" ולא קיימת הגדרה מתמטית ברורה למספרים חלקים בעקום אליפטי. שיטת פולרד הנה השיטה היעילה ביותר הקיימת כיום לפתרון בעיית ECDLP וסיבוכיותה היא $\ \sqrt{(\pi n/2)}$ בקירוב. על כן אינה יעילה (גם בגרסה המקבילית שלה) כשמדובר בשדה מסדר גדול. עבור בטיחות של 128 סיביות מספיק שהסדר יהיה $\ q \approx 2^{256}$. לשם המחשה, מערכת מפתח פומבי (בחבורות) דורשת מפתח פומבי בסדר גודל של כ-2048 סיביות כדי שתקרא בטוחה. במערכת ECC מקבילה, מפתח בגודל 224 סיביות מספק בטיחות שקולה. מערכת ECC היחידה שנפרצה נכון להיום הייתה עם מפתח בגודל 109 סיביות. בפריצת ECC עם שדה ראשוני בגודל זה, נדרשו כעשרת אלפים יחידות מחשב שפעלו באופן מקבילי ללא הרף במשך תקופה של 540 יום.

Side channel attack

ההבדל המהותי בין חישוב פעולת חיבור לבין פעולת כפל של נקודות בעקום אליפטי, מהווה נקודת תורפה שיש להימנע ממנה, כיוון שמערכת המיישמת את ECC עלולה להדליף מידע פנימי כתוצאה מהפרשי הזמן במהלך ביצוע פעולות כפל וחיבור. התקפת Side channel attack בקיצור SCA מתחלקת לשני סוגים עקריים האחת נקראת Simple Power Analysis שבה מודדים את עצמת הצריכה של יחידת העיבוד (כגון motorola 6805, או Intel 8051) במהלך ביצוע ECADD ו-ECDBL המתוארות לעיל בפרוצדורת כפל סקלרי. בשל הבדלים אילו ניתן לחלץ מידע קריטי מהמערכת. השנייה נקראת Differential Power Analysis, התקפה המבוססת על ניתוח סטטיסטי של מספר פעולות חישוב כדי לחלץ מידע מהמערכת. כאמור לעיל לאור יתרונותיה, מערכת ECC מתאימה במיוחד ליישום במתקנים ניידים על כן נגישות התוקף למערכת ויכולתו למדוד את משך זמן ביצוע פעולות החישוב של יחידת העיבוד הנו בגדר אפשרי.

הפתרון להתקפת SPA (הראשונה) הוא שינוי פרוצדורת הכפל באופן שלא תדליף מידע קריטי. קיימות מספר שיטות יעילות לביצוע פעולה זו כגון: שיטת יעקובי (Jacobi) והסה (Hesse) המשתמשת באלגוריתם אחיד לחיבור וכפל סקלרי של נקודות. באופן כזה הזמן הדרוש לביצוע פעולות אילו זהה ועל כן לא דולף מידע קריטי. שיטה זו מתאימה לעקומים מיוחדים הנקראים "עקום קובליץ". או כפל סקלרי בשיטת קורון עם חיבור מדומה (double-and-always-add), כפל סקלרי בשיטת חלון, כפל סקלרי בשיטת סולם מונטגומרי וכן שיטת מולר (Möller) העושה שימוש ב-Addition chain. כנגד התקפת DPA, הוספת אקראיות כמו אקראיות פרויקטיבית $\ \mbox{P}=(r^2\mbox{X},r^3\mbox{Y},r\mbox{Z})$ עם $\ r$ שלם אקראי כלשהו מספקת.

גודל מפתח

מאחר ומפתח למעשה מייצג נקודה בעקום, גודלו הוא למעשה שתי הקואורדינטות x ו-y. אולם ניתן להפחית בגודל המפתח על ידי דחיסת הקואורדינטה y כך שנדרשת רק סיבית אחת ליצגה באופן שאפשר יהיה לשחזרה לאחר מכן. כך שאפקטיבית גודל המפתח הוא בערך כגודל הקואורדינטה x. היות שהקואורדינטות הם בערך כגודל הסדר של השדה (מספר האלמנטים) הרי שחוסן אלגוריתם ההצפנה תלוי למעשה בסדר. לצורך השוואה להשגת רמת בטיחות של 128 סיביות (למשל אותה רמת בטיחות המושגת עם אלגוריתם סימטרי כמו AES ומפתח בגודל 128 סיביות) הסדר של שדה במערכת ECC יכול להיות בסדר גודל של 256 סיביות, רק לשם השוואה במערכת מפתח-פומבי טיפוסית כמו RSA יש צורך במודולוס בגודל 3072 סיביות, להשגת רמת בטיחות זהה.

יישומים מעשיים

על בסיס הגדרת בעיית לוגריתם דיסקרטי בעקום אליפטי (ECDLP) המתוארת לעיל, ניתן ליישם את פרוטוקול דיפי-הלמן, אלגוריתם DSA מעל עקום אליפטי הנקרא ECDSA וכן אלגוריתמים אסימטריים ידועים אחרים. אך יש צורך להמיר את המסר או המפתח לנקודה בעקום. אין זה פשוט כל כך כיון שלא לכל $\ x$ יש $\ y$ מתאים בעקום. על כן לא כל מערכת אסימטרית ניתנת ליישום בעקום אליפטי. הסוכנות לביטחון לאומי של ארצות הברית (NSA) הכריזה על Suit B, המנצלת הצפנת עקום אליפטי (ECC) עבור חתימה דיגיטלית והעברת מפתח הצפנה. ערכה זו אמורה להחליף את הטכנולוגיה האסימטרית הקודמת כגון RSA ודומיה, להגנה על סודות לאומיים מסווגים ולא מסווגים של ממשלת ארצות הברית. כמו כן קיימת מערכת ECC המבוססת על תבנית בילינארית (הנקראת גם Weil pairing) המשמשת למערכת אימות זהויות מבוססת ID (שבה זהות המשתמש מהווה חלק מהמפתח הפומבי). וכן חברת Certicom הקנדית משווקת מגוון גדול של מערכות אבטחה המבוססות על עקום אליפטי.

ביישומים מעשיים בדרך כלל מיישמים את ECC מעל שדה עם נקודה קבועה $\ G$ שהסדר $\ n$ שלה (השלם הקטן ביותר המקיים $\ nG=O$) הוא כפולה של ראשוני גדול $\ p$ ושלם קטן מאוד $\ h$ הנקרא co-factor. בשל שיקולי יעילות נהוג להימנע מ-$\ h$ גדול מדי. המקובל הוא ש-$\ h \le 4$ לעתים $\ h=1$. מציאת הסדר של עקום אליפטי (קרי, מספר הנקודות) אינו דבר קל, קיימים אמנם אלגוריתמים לשם כך (כמו אלגוריתם שוף - Schoof). על כל פנים, כיוון שהסדר נחוץ בפרוטוקולים קריפטוגרפיים מסוימים, נהוג לבנות עקום אליפטי באופן כזה שהסדר קל לחישוב. למעשה התקנים למערכות ECC מגדירים פרוצדורות שונות להכנת עקום אליפטי בטוח העונה על הדרישות הרצויות וכן מכילים אוסף עקומים אליפטיים מומלצים לצורך ECC.

תקנים וזכויות

הצפנת ECC כבר שולבה בתקנים בינלאומיים שונים כמו תקן FPIS 186-2 של NIST, תקן X9.62-1998 של ANSI, תקן SEC 1 של חברת Certicom וכן IEEE 1363-2000.

תקן FIPS 186-2 מפרט עקומים אליפטיים בעלי תכונות המקלות על הפעולות האריתמטיות. תקן זה ותקנים אחרים ממליצים על שימוש בפונקציית גיבוב בטוחה להכנת העקום. דוגמה לעקום אליפטי כזה היא P-192 (ראשוני בגודל 192 סיביות):

מספר ראשוני:

$\ p = 6277101735386680763835789423207666416083908700390324961279$

הסדר:

$\ r = 6277101735386680763835789423176059013767194773182842284081$

גרעין התחלתי לפונקציית הגיבוב (SHA-1):

$\ s = \mbox{3045AE6F C8422F64 ED579528 D38120EA E12196D5}$

פלט פונקציית הגיבוב:

$\ c = \mbox{3099D2BB BFCB2538 542DCD5F B078B6EF 5F3D6FE2 C745DE65}$

המקדם $\ b$ המקיים $\ b^2c \equiv -27 \ (\mbox{mod }p)$:

$\ b = \mbox{64210519 E59C80E7 0fA7E9AB 72243049 FEB8DEEC C146B9B1}$

הקואורדינטה x של הנקודה G:

$\ G_x = \mbox{188DA80E B03090F6 7CBF20EB 43A18800 F4FF0AFD 82FF1012}$

הקואורדינטה y של הנקודה G:

$\ G_y = \mbox{07192B95 FFC8DA78 631011ED 6B24CDD5 73F977A1 1E794811}$

חלק ממערכות ECC מוגנות בפטנטים וזו אחת הסיבות מדוע מערכות ECC אינן נפוצות כל כך. חברת Certicom מחזיקה בכמאה וחמישים פטנטים הקשורים בהיבטים שונים של ECC כגון אלגוריתם ECQMV. חברת אפל מחזיקה בפטנט על יישום יעיל של ECC מעל השדה $\ GF(p)$ כאשר $\ p$ קרוב לחזקה של 2. ה-NSA רכשו זכויות שימוש מוגדרות במערכות ECC של חברת Certocim לצורך שימוש להצפנת מידע עבור הממשל. והם מוסמכים לתת רישיון לכל גוף המעוניין לשלב ECC באפליקציות אבטחה בהן נעשה שימוש עבור ממשלת ארצות הברית.

ראו גם

• פרוטוקול דיפי-הלמן
• Advanced Encryption Standard

קישורים חיצוניים

• NSA, "הדור החדש של ההצפנה האסימטרית", The Case for Elliptic Curve Cryptography
• המכון הלאומי לסטנדרט וטכנולוגיה של ממשלת ארצות הברית נספח לתקן הצפנה בעקומים אליפטיים: Recommended Elliptic Curves For Federal Government Use
• חברת Certicom הקנדית, תקן עקומים אליפטיים בהצפנה SEC 1: Elliptic Curve Cryptography, כולל סקירה תמציתית של ארתימטיקה בעקום אליפטי, אלגוריתמים ופרוטוקולים ודיון בסוגיית הבטיחות.
• קורס בהצפנה בעקומים אליפטיים למתחילים, באתר חברת Certicom.