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

הצפנה מבוססת עָקֹם אֶלִיפְּטִי או בקיצור הצפנת עקום אליפטי (באנגלית: Elliptic Curve Cryptography, בקיצור ECC), היא שיטת הצפנה אסימטרית העושה שימוש במבנה האלגברי-גאומטרי הנקרא עקום אליפטי מעל שדה סופי גדול, למימוש מערכת כגון פרוטוקול דיפי-הלמן או צופן אל-גמאל. הדעה הרווחת היא שבבחירת פרמטרים מושכלת, ניתן להשיג בדרך זו אלגוריתמים מהירים ויעילים באופן משמעותי מאלו המבוססים על אריתמטיקה מודולרית בשל העובדה שמפתח ההצפנה קצר יותר מאשר בהצפנה אסימטרית רגילה, ללא פגיעה בביטחון המידע. בשל עובדה זו הצפנה מבוססת עקומים אליפטיים אטרקטיבית במיוחד בחומרה מוגבלת במשאבים כמו סנסור אלחוטי, כרטיס חכם או מערכות משובצות.

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

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

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

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

הגדרה כללית

דוגמאות של עקום אליפטי מעל השדה הממשי.

ערך מורחב – עקום אליפטי

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

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

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

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

$\ {\boldsymbol {y^{2}+xy=x^{3}+ax^{2}+b}}$, כאשר $\ b\neq 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})$ נקודות נתונות על העקום, אורך כשלושים פעולות יסודיות של חיבור, כפל וחילוק בשדה שמעליו העקום מוגדר.

קיימים עקומים אחרים כמו עקום קובליץ, עקום מונטגומרי, עקום אדוארד ועקום הסה שלהם שימושים בתחום הקריפטוגרפיה. לכל אחד מהם יתרונות בשדות שונים בהם חיבור וכפל נקודות קל יותר מאשר באחרים. גרסה מפותלת של עקום אדוארד שולבה בעקום 25519 ובעקום 448 שניהם עקומים חדשים הידועים בביטחון וביעילות גבוהים ונוספו כמועמדים לפרוטוקול SSL וכן נכללו מספר תקנים בינלאומיים (ראו RFC 7748).

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

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

חוק החיבור בעקום האליפטי $E$ מקיים את הכללים הבאים:

• איבר יחידה. עבור כל נקודה $P\in E$ תמיד מתקיים: $P+{\mathcal {O}}={\mathcal {O}}+P=P$.
• איבר הופכי. עבור כל נקודה $P\in E$ תמיד מתקיים: $P+(-P)={\mathcal {O}}$.
• אסוציאטיביות. עבור נקודות כלשהן $P,Q,R\in E$ תמיד מתקיים: $(P+Q)+R=P+(Q+R)$.
• קומוטטיביות. עבור נקודות כלשהן $P,Q\in E$ תמיד מתקיים: $P+Q=Q+P$.

העקום האליפטי $y^{2}=x^{3}+2x+3$ מעל השדה $GF(71)$ עם 88 נקודות.

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

ניתן להגדיר עקומים אליפטיים מעל כל שדה, אך לצרכים קריפטוגרפים מתמקדים בשדות סופיים. במקרה זה, על אף שניתן להציג את הנקודות על העקום בצורה גרפית, הדבר איננו מקובל. התרשים משמאל ממחיש את העקום האליפטי $y^{2}=x^{3}+2x+3$ מעל השדה $GF(71)$ (המקדמים הם שלמים חיוביים מודולו 71) שנראה כמו תפזורת אקראית של נקודות.

כללי האריתמטיקה

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

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

${\begin{aligned}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}}}\end{aligned}}$

הכפלת נקודה יחידה (ECDBL) $\ {\mbox{R=P+P=2P}}$, החיבור זהה למעט:

$\lambda ={\frac {3x_{p}^{2}+a}{2y_{p}}}$

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

מעל שדה סופי פעולת החילוק מתבצעת על ידי הכפלה בהופכי הכפלי, לדוגמה הפעולה $\textstyle {\frac {y_{q}-y_{p}}{x_{q}-x_{p}}}$ שקולה לפעולה $(y_{q}-y_{p})\cdot (x_{q}-x_{p})^{-1}{\text{ (mod }}p)$. לשם כך צריך להשתמש באלגוריתם למציאת הופכי כפלי המבוסס על הרעיון של אוקלידס.

דוגמאות

לדוגמה יהיו $p=23,a=1,b=4$ ומשוואת העקום $E:y^{2}=x^{3}+x+4$ מעל השדה $\mathbb {F} _{23}$ המכיל את 29 הנקודות $(x_{i},y_{i})$ המובאות להלן יחד עם נקודת האין סוף ${\mathcal {O}}$, כאשר $x,y\in \mathbb {F} _{23}$:

$(0,2)$	$(0,21)$	$(1,11)$	$(1,12)$	$\color {Blue}(4,7)$	$(4,16)$	$(7,3)$
$(7,20)$	$(8,8)$	$(8,15)$	$(9,11)$	$(9,12)$	$(10,5)$	$\color {Purple}(10,18)$
$(11,9)$	$(11,14)$	$\color {Orange}(13,11)$	$(13,12)$	$(14,5)$	$(14,18)$	$\color {Green}(15,6)$
$(15,17)$	$(17,9)$	$(17,14)$	$(18,9)$	$(18,14)$	$(22,5)$	$(22,18)$
${\mathcal {O}}$

היות ש-$p$ ראשוני, השדה $\mathbb {F} _{23}$ הוא ציקלי (מחזורי) ולכן מכיל יוצרים. למשל הנקודה $P=(0,2)$ היא יוצר. אפשר לראות שאם מחברים את הנקודה $P$ בעצמה 29 פעמים מתקבלות כל נקודות העקום לא בהכרח לפי הסדר, עד שמגיעים לנקודת האין סוף, כלומר $1P=(0,2),2P=(13,12),3P=(11,9),...,29P={\mathcal {O}}$.

דוגמה לחיבור שתי נקודות. אם נבחר את הנקודות $P=(4,7)$ ו-$Q=(13,11)$ החיבור $P+Q=(x_{3},y_{3})$ מבוצע כך:

תחילה $x_{3}=\left({\frac {11-7}{13-4}}\right)^{2}-4-13=3^{2}-4-13=-8\equiv 15{\text{ (mod }}23)$,

ואז $y_{3}=3(4-15)-7=-40\equiv 6{\text{ (mod }}23)$.

לכן התוצאה היא $P+Q=(15,6)$.

כדי להכפיל את הנקודה $P=(4,7)$ בשתים, $2P=P+P=(x_{3},y_{3})$ מחשבים כדלהלן:

תחילה $x_{3}=\left({\frac {3(4^{2})+1}{14}}\right)^{2}-8=15^{2}-8=217\equiv 10{\text{ (mod }}23)$,

ואז $y_{3}=15(4-10)-7=-97\equiv 18{\text{ (mod }}23)$.

ולכן $2P=(10,18)$.

כפל סקלרי

להבדיל מכפל רגיל מכנים פעולת כפל נקודות בעקום בשם כפל סקלרי (Scalar Multiplication). הכפלה של נקודה $\ {\mbox{P}}$ בשלם $\ k$ כלשהו היא בעצם פעולת חיבור חוזר $\ P+P+\cdots +P$ בסך הכול $k$ פעמים. פעולה זו ניתן לבצע על ידי אלגוריתם רקורסיבי המנצל את הייצוג הבינארי של $\ k$ כדי לבצע פעולות חוזרות של חיבור וכפל המתוארים לעיל. קיימות שיטות רבות לביצוע כפל נקודה בעקום אליפטי. דוגמה אחת נקראת "שיטה בינארית מימין לשמאל" והיא מתבצעת כדלהלן:

קלט: שלם $k$ באורך $t$ סיביות (בייצוג בינארי $k_{t},...,k_{2},k_{1}$), הנקודה $P$.

פלט: הנקודה $Q=kP$.

1. $Q={\mathcal {O}}$

2. מ-$1$ עד $t$ בצע:

אם $k_{i}=1$ בצע $Q\leftarrow Q+P$

$P\leftarrow 2P$

3. החזר את $Q$

בשיטה זו זמן החישוב תלוי ב-$\ k$ ועל-כן בתנאים מסוימים עלול לחשוף את המערכת להתקפות ערוץ צדדי. קיימות שיטות מתקדמות ויעילות יותר לביצוע כפל סקלרי כמו שיטת חלון (sliding window) או שיטת מונטגומרי. ההתמודדות עם התקפות ערוץ צדדי תלויות מאוד באופן היישום ובסביבה בה האלגוריתם מיושם.

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

חשיבות עקום אליפטי בתורת ההצפנה היא בעובדה שהוא מועמד טוב לפונקציה חד-כיוונית שהכרחית בכל הצפנה א-סימטרית. לדוגמה אם נתונה הנקודה $P$ ושלם כלשהו $k$, מצד אחד חישוב $kP$ (באמצעות אלגוריתם רקורסיבי כמו זה המתואר לעיל) קל לביצוע במחשב, לעומת זאת, בהינתן הנקודה $Q=kP$ מאוד קשה לגלות את $k$. זוהי בעיה מתמטית קשה הנקראת בעיית הלוגריתם הבדיד בעקום אליפטי. לסדר העקום (מספר הנקודות בעקום) חשיבות רבה, בפרט על העקום להכיל תת-חבורה מסדר ראשוני גדול.

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

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

בעיית הלוגריתם הבדיד בעקום אליפטי בקיצור ECDLP

בהינתן עקום אליפטי $E$ המוגדר מעל שדה סופי $\mathbb {F} _{q}$,

הנקודה $P\in E(\mathbb {F} _{q})$ מסדר $n$, הנקודה $Q\in \left\langle P\right\rangle$,

מצא שלם $k\in [0,n-1]$ כך שמתקיים $Q=kP$.

השלם $k$ נקרא הלוגריתם הבדיד (דיסקרטי) של $Q$ בבסיס $P$ ואפשר לסמנו בקיצור $k={\text{log}}_{P}Q$. הסימן $\left\langle P\right\rangle$ מייצג את החבורה הציקלית $\{{\mathcal {O}},P,2P,3P,...,(n-1)P\}$ שהיא אוסף הנקודות שהן כפולות של $P$ יחד עם הנקודה באין סוף. שים לב שתמיד מתקיים $nP={\mathcal {O}}$.

בעיית דיפי-הלמן בעקום אליפטי בקיצור ECDHP

בעיית דיפי-הלמן בעקום אליפטי המקבילה לבעיית דיפי-הלמן המפורסמת היא בעיה חישובית המוגדרת כך:

בהינתן עקום אליפטי $E$ המוגדר מעל שדה סופי $\mathbb {F} _{q}$,

הנקודה $P\in E(\mathbb {F} _{q})$ מסדר $n$ והנקודות $A=aP,B=bP\in \left\langle P\right\rangle$,

מצא את הנקודה $C=abP$.

כמובן שאם ניתן לפתור ביעילות את בעיית ECDLP יהיה קל לפתור את ECDHP, ההפך לא הוכח למעט מקרים פרטיים אחדים. באופן כללי לא ידוע אם הבעיות שקולות.

בעיית הכרעת דיפי-הלמן בקיצור ECDDHP

בהינתן עקום אליפטי $E$ מעל $\mathbb {F} _{q}$,

הנקודה $P\in E(\mathbb {F} _{q})$ מסדר $n$, הנקודות $A=aP,B=bP\in \left\langle P\right\rangle$ וכן $C=cP\in \left\langle P\right\rangle$

הבעיה היא להכריע האם $C=abP$ או האם $c\equiv ab\ ({\text{mod }}n)$.

שתי השאלות הללו שקולות. כמובן שאם ניתן לפתור את ECDHP יהיה קל לפתור את ECDDHP. שופ הוכיח שקיים חסם תחתון שהוא ${\sqrt {n}}$ עבור בעיית ההכרעת דיפי-הלמן בעקום אליפטי, $n$ הוא הסדר (מספר הנקודות).

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

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

אם נתון העקום: $E:Y^{2}=X^{3}+8X+7$ מעל $\mathbb {F} _{73}$, הנקודות $P=(32,53)$ ו-$Q=(39,17)$ הן בעקום $E(\mathbb {F} _{73})$ ומפני שהעקום מכיל רק 41 נקודות קל לגלות באופן ישיר שהלוגריתם הבדיד הוא:

$Q=11\cdot P$ לכן $\log _{P}(Q)=11$.

באופן דומה $R=(35,47)\in E(\mathbb {F} _{73})$ וכן $S=(58,4)\in E(\mathbb {F} _{73})$. אחרי חישוב קל אפשר לראות שהם מקיימים $R=37P$ וכן $S=28P$ לכן:

$\log _{P}(R)=37$ וכן $\log _{P}(S)=28$.

אף על פי שלפי הנוסחה לעיל $\#E(\mathbb {F} _{73})=82$ היות ש-$41P={\mathcal {O}}$ למעשה סדר העקום הוא $82/2$. כך שרק 41 מהנקודות בעקום זה הן כפולות של $P$.

בחירת פרמטרים

כדי להשתמש בעקום אליפטי לצורך פרוטוקול קריפטוגרפי יש לשים לב לכמה היבטים חשובים כדי למנוע חולשות שעלולות להוביל לנקודות תורפה ולשבירת המערכת. הפרמטרים הציבוריים של העקום נקראים "פרמטרי תחום" (Domain Parameters) שכאמור פומביים ומשותפים לכל המשתמשים במערכת אך יש לוודא את תקינותם. תחילה בוחרים "עקום מתאים" $E$ המוגדר מעל שדה סופי $\mathbb {F} _{q}$ עם מציין $p$ וכן בוחרים נקודת בסיס $P\in E(\mathbb {F} _{q})$. כאשר ההגדרה "עקום מתאים" מתייחסת לכמה פרמטרים חיוניים כדלהלן; כדי למנוע התקפות המסתמכות על פתרון בעיית הלוגריתם הבדיד בעקום אליפטי (ECDLP) עם אלגוריתם רו של פולרד או פוליג-הלמן, חובה שלסדר העקום או מספר נקודות העקום המסומן ב-$\#E(\mathbb {F} _{q})$ יהיה גורם ראשוני $n$ גדול דיו (למשל $n>2^{160}$), ש-$n\approx q$ כך שמספר הנקודות בעקום יהיה "כמעט ראשוני" וכן ש-$n>4{\sqrt {q}}$. לפי משפט הסה בעקום אליפטי, מספר הנקודות של עקום אליפטי חסום על ידי

$({\sqrt {q}}-1)^{2}\ \leq \ \#E(\mathbb {F} _{q})\ \leq \ ({\sqrt {q}}+1)^{2}$

מזה נובע ש-$n^{2}$ אינו מחלק של $\#E(\mathbb {F} _{q})$ ולכן לעקום זה קיימת תת-חבורה מסדר $n$. ממשפט זה נובע גם שקיים שלם יחיד $h$ הנקרא cofactor המקיים

$q+1-2{\sqrt {q}}\ \leq \ nh\ \leq \ q+1+2{\sqrt {q}}$

במילים אחרות $\textstyle h=\left\lfloor ({\sqrt {q}}+1)^{2}/n\right\rfloor$ ולכן מספר הנקודות של העקום הוא $hn$. וכדי למנוע התקפת תת-חבורה מסדר קטן המנצלת את סדר החבורה יש צורך שהנקודה $P$ תהיה מסדר $n$. וכדי למנוע התקפות המנצלות רדוקציה מעקום אליפטי לשדה סופי (מורחב) יש צורך שהעקום לא יהיה סופר-סינגולרי, כלומר לוודא ש-$n$ אינו מחלק של $q^{k}-1$ עבור כל $1\leq k\leq C$ כאשר $C$ גדול מספיק כך שמציאת לוגריתם דיסרקטי בשדה $\mathbb {F} _{q^{C}}$ יהיה קשה (למשל $C=20$) וכן רצוי למנוע התקפה אחרת נגד "עקום אנומלי" שהוא עקום אליפטי שבו מספר הנקודות הוא בדיוק $q$ (שהוא מספר ראשוני), לכן רצוי שסדר העקום לא יהיה $q$. באופן כללי כדי למנוע התקפות אילו ואחרות (שמנצלות חולשות הנובעות מתכונות מיוחדות של העקום) האסטרטגיה המומלצת היא לבחור את העקום באופן אקראי בתנאי כמובן של-$\#E(\mathbb {F} _{q})$ יש גורם ראשוני גדול. הסבירות שעקום שנבחר כך יהיה פגיע לאחת ההתקפות הללו אינה גדולה. וכן חשוב לבחור את העקום באופן כזה שיהיה קל לוודא שהוא אכן עומד בתנאים המצוינים. אחת הדרכים היא אסטרטגיה דומה לזו שננקטה על ידי NIST בבחירת הפרמטרים עבור DSA בתקן FIPS 186 - קרי לעשות שימוש בפונקציית גיבוב כמו SHA-2 כגרעין התחלתי ממנו מפיקים את הפרמטרים האמורים, כמתואר בתקן ANSI X9.62. ואז יש כמובן לשמור גם את הגרעין ההתחלתי כחלק בלתי נפרד מסט הפרמטרים, כך שהמקבל יוכל לוודא באמצעותו שהפרמטרים תקינים ולא נבחרו באופן מעורר חשד.

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

ב-2013 התגלה כחלק מההדלפות של סנודן שה-NSA שתלו דלת אחורית באלגוריתם Dual_EC_DRBG שהיה חלק מתקן של NIST למחולל פסאודו אקראי קריפטוגרפי המבוסס על עקום אליפטי. מלבד זאת מומחים הביעו חשש בנוגע לאחדים מן הקבועים של NIST ש-NSA התערב בבחירתם. בשל כך נוצרה דרישה לעקומים אליפטיים תיקניים שאינם נמנים עם הרשימה של NIST. ב-2005 פרסם דניאל ברנשטיין את העקום Curve25519 המציע ביטחון ברמה של 128 סיביות והוא נמצא בשימוש נרחב כיום בין היתר על ידי OpenSSL וכן וואטסאפ.

פרמטרי התחום

פרמטרי התחום (domain parameters) של מערכת הצפנה בעקום אליפטי כוללים עקום אליפטי מתאים $E$ המוגדר מעל שדה סופי $\mathbb {F} _{q}$ עם מציין $p$ ונקודת בסיס $G\in E(\mathbb {F} _{q})$ בנוסף למספר ערכים חשובים המהווים חלק בלתי נפרד מהמערכת. פרמטרי התחום יכולים להיות משותפים לקבוצת משתמשים או ספציפיים למשתמש יחיד. בחירת פרמטרים נכונה היא חלק קריטי בביטחון מערכת הצפנה כזו ולכן התקן מפרט צעדים מומלצים כיצד לייצר באופן אקראי או לבחור בעקום אליפטי יחד עם אוסף הפרמטרים באופן בטוח לשימוש קריפטוגרפי וכיצד לוודא שאכן עקום אליפטי אכן נוצר באופן שעונה על כל הדרישות האמורות. פרמטרי התחום של עקום אליפטי לצורך קריפטוגרפי הם:

• $q$ הסדר של השדה $\mathbb {F}$, צריך להיות ראשוני או חזקה של 2 (דהיינו $q=p$ ראשוני או $q=2^{m}$). במקרה הראשון קואורדינטות הנקודות הן שלמים חיוביים המהווים אלמנטים בשדה $\mathbb {F} _{p}$ ואילו במקרה השני הן פולינומים ממעלה $m$ מעל השדה המורחב $\mathbb {F} _{2^{m}}$ כאשר המקדמים בינאריים.
• גרעין התחלתי (seed) אופציונלי במקרה שהעקום האליפטי נוצר באופן אקראי ולא נבחר מתוך התקן. הגרעין ההתחלתי משמש לבדיקה ואימות העקום.
• שני אלמנטים $a$ ו-$b$ מהשדה $\mathbb {F} _{q}$ המגדירים את נוסחת העקום האליפטי (כגון $y^{2}=x^{3}+ax+b$ או $y^{2}+xy=x^{3}+ax^{2}+b$ במקרה של מציין $p=2$). את האלמנטים הללו בוחרים על ידי פונקציית גיבוב יחד עם גרעין התחלתי (seed) אקראי כלשהו (אותו שומרים לצורך אימות עתידי).
• שני אלמנטים (קואורדינטות) $x_{P},y_{P}$ המייצגים את הנקודה $P$ מסדר ראשוני גבוה.
• הסדר $n$ של הנקודה $P$ צריך להתחלק במספר ראשוני גדול. כאשר $n>2^{160}$ וכן $n>4{\sqrt {q}}$.
• $h$ שנקרא גורם משלים (cofactor) כך שמתקיים $h=\#E(\mathbb {F} _{q})/n$.

חשוב לוודא תקפות הפרמטרים לפני שמשתמשים בהם, כדי לוודא תקינותם יש לפעול כדלהלן:

• לוודא ש-$q$ ראשוני או חזקה של ראשוני.
• לוודא שהאלמנטים $a,b,x_{P},y_{P}$ כולם אלמנטים בשדה $\mathbb {F} _{q}$ ובפורמט הנכון (אפשר להיעזר בגרעין ההתחלתי שמסופק על ידי מי שייצר את העקום כדי לוודא שהוא אכן נוצר באקראי באמצעות פונקציית גיבוב).
• לוודא שהאלמנטים $a,b$ מגדירים עקום אליפטי לא סינגולרי, כלומר שמתקיים $4a^{3}+27b^{2}\neq 0$ (וכן ש-$b\neq 0$ במקרה של עקום עם מציין $p=2$).
• לוודא שהנקודה $P$ היא בעקום לפי הנוסחה האמורה.
• לוודא ש-$n>4{\sqrt {q}}$, ש-$n$ ראשוני וכן גדול מספיק (למשל $n>2^{160}$).
• לוודא שמתקיים $nP={\mathcal {O}}$.
• לוודא שהסדר $N=\#E(\mathbb {F} _{q})$ (מספר נקודות העקום) מתחלק במספר ראשוני $n>2^{160}$.
• לוודא ש-$h=\left\lfloor ({\sqrt {q}}+1)^{2}/n\right\rfloor$.
• לוודא ש-$n$ אינו מחלק של $q^{k}-1$ עבור כל $1\leq k\leq 20$ וכן $n\neq q$.

בתקן SEC-1 של GSEC (חברת Certicom הקנדית) ובתקן של NIST, נקבע הבסיס האריתמטי או ייצוג האלמנטים לפי סוג השדה, בשדה ראשוני $\mathbb {F} _{q}$ האלמנטים הם השלמים מודולו $q$ ונקודה בעקום מיוצגת על ידי קואורדינטות שלמות $x,y\in \mathbb {F} _{q}$. בשדה עם מציין 2 האלמנטים מיוצגים בבסיס פולינומי כאשר השדה הוא $\mathbb {F} _{2^{m}}$ וקואורדינטות הנקודה הן פולינומים ממעלה $m-1$.

סדר העקום האליפטי

מספר הנקודות בעקום האליפטי חשוב מאוד לביטחון מערכת ECC כאמור, כדי למנוע התקפות קריפטוגרפיות מסוימות שמנצלות סדר חבורה שמכיל גורמים קטנים. ספירת נקודות העקום אפשרית בזמן פולינומי עם מספר אלגוריתמים ידועים ביניהם אלגוריתם של שוף (schoof) שהורחב ושופר לאחר מכן על ידי קובליץ אלקיס ואטקין ונקרא אלגוריתם SEA. עם אלגוריתם SEA אפשר לספור את נקודות עקום אליפטי מעל שדה סופי מסדר 200 בתוך מספר שעות. אלגוריתם SATOH פותח במיוחד לספירת נקודות עקום אליפטי מעל שדה בינארי מורחב, למשל אם $m=200$ אפשר לספור את נקודות העקום עם אלגוריתם SATOH בתוך מספר שניות.

הכנת עקום אליפטי באופן אקראי

הכנת עקום אליפטי באופן אקראי נעשית לפי התקן עם פונקציית גיבוב קריפטוגרפית כמו SHA-2 כאשר הגרעין ההתחלתי משמש כהוכחה שהעקום אכן נוצר באופן אקראי ולא נוצר במכוון כך שיכיל חולשות או דלתות סתר. הרעיון הכללי הוא שמכינים עם פונקציית הגיבוב מתוך גרעין התחלתי seed מחרוזת סיביות אקראית באורך הרצוי $H={\text{SHA2}}(seed)$. מייצגים את המחרוזת $H$ כמספר בינארי שלם $r$ ומוודים שלא מתקיים $4r+27\equiv 0{\text{ (mod }}p)$ וכן בוחרים שני שלמים אקראיים $a,b\in \mathbb {F} _{p}$ כך שמתקיים $r\cdot b^{2}\equiv a^{3}{\text{ mod }}p$. הגרעין ההתחלתי צריך להישמר יחד עם העקום והוא משמש כהוכחה. הוא מייצר באותה דרך מחרוזת סיביות $r'$ ומוודא שמתקבל $r'\cdot b^{2}\equiv a^{3}$ אם התנאי לא מתקיים זו הוכחה שהעקום לא נבחר באקראי.

מפתח פרטי ומפתח ציבורי

בהינתן הפרמטרים הציבוריים $(q,a,b,P,n,h)$ המפתח הפרטי הוא שלם $d$ אקראי בטווח $[1,n-1]$ הנשמר בסוד והמפתח הציבורי המתאים הוא $Q=dP$ שהוא כפל סקלרי של הנקודה $P$ עם המפתח הפרטי $d$. בדרך כלל המפתחות של כל משתמש צריכים להיות מאומתים ומשויכים אליו בדרך כלשהי. בדרך קריפטוגרפית מאמתים מפתח באמצעות חתימה דיגיטלית או תעודה (certificate) שמונפקת על ידי רשות מאשרת (CA). וכן בדרך כלל קיימת הפרדה בין המפתחות הקבועים המיועדים לטווח ארוך לבין מפתחות ארעיים (ephemeral keys) הנוצרים לצורך התקשרות ספציפית. יש צורך תמיד לאמת תקפות המפתח הציבורי, לוודא שמקיים את התנאים המפורטים לעיל; ש-$Q$ הוא נקודה בעקום שאינה ${\mathcal {O}}$ וכן שהקואורדינטות $x,y$ שלה הם אלמנטים בשדה $\mathbb {F} _{q}$ בטווח המתאים וכן שמתקיים $nQ={\mathcal {O}}$. בפועל משתדלים להימנע מהבדיקה האחרונה כיוון שהיא פעולה מכבידה במונחי מחשוב, אפשר לחסוך בדיקה זו על ידי שימוש בפרוטוקול שיתוף מפתח עם אימות כמו MQV שבו הבדיקה עקיפה ונעשית כחלק ממהלכי הפרוטוקול.

הצפנה עם עקום אליפטי

ניתן ליישם את צופן אל-גמאל בעקום אליפטי כדלהלן; בהינתן המפתח הציבורי של בוב הנקודה $Q$, אם אליס מעוניינת להצפין את המסר $m$ עליה תחילה להמירו לנקודה $M$ בעקום ואותה להצפין על ידי חיבור עם $kQ$, כאשר $k$ שלם אקראי "טרי" חד-פעמי שנבחר על ידה כדי להצפין את $M$ ובנוסף היא צריכה להצפין ולשלוח את המפתח $k$. ביתר פירוט, אליס משדרת לבוב בערוץ הפתוח שני ערכים: $C_{1}=kP$ שמכיל את המפתח המוצפן וכן $C_{2}=M+kQ$ שמכיל את המסר המוצפן. כאשר בוב מקבל את הערכים הללו מאליס הוא מבצע את הפעולות בסדר הפוך, הוא מפענח את המפתח המוצפן ואז מחסיר את התוצאה מהטקסט המוצפן כדי לקבל את הנקודה $M$ וממנה לחלץ את המסר $m$. זה עובד היות שמתקיים

$dC_{1}=d(kP)=k(dP)=kQ$

כאשר $d$ הוא המפתח הפרטי של בוב המקיים $Q=dP$. לכן היות ש-$M=C_{2}-kQ$ בוב יכול להחליפו בביטוי $M=C_{2}-dC_{1}$ ולקבל את $M$. המאזינה איב שמעוניינת לגלות את $M$ צריכה לחשב תחילה את $kQ$, חילוץ $kQ$ מתוך $Q$ ומתוך $C_{1}$ היא בדיוק בעיית דיפי-הלמן. למען הפשטות הגרסה המתוארת חסרה מספר מרכיבים חשובים כמו אימות ובדיקת תקפות. להלן תיאור פרוטוקול הצפנה היברידי שנקרא ECIES (קיצור של Elliptic Curve Integrated Encryption Scheme) שהוצע על ידי בלייר ורוגווי, המשלב הצפנה אסימטרית המבוססת על צופן אל-גמאל והצפנה סימטרית עם אימות. הוכנס לתקן ANSI X9.63 וכן ISO/IEC 15946-3 וכן IEEE P1363. בפרוטוקול זה מנצלים את פרוטוקול שיתוף הסוד הבסיסי של דיפי והלמן כדי לשתף שני מפתחות סודיים $k_{1},k_{2}$ כאשר $k_{1}$ משמש להצפנת המסר ו-$k_{2}$ לאימות התוצאה להגנה מפני התקפת מוצפן-נבחר. לצורך הפרוטוקול מוגדרות שלוש פונקציות בסיסיות; KDF - פונקציית הכנת מפתח שהיא תוצאת פונקציית גיבוב של גרעין כלשהו $S$ ומונה כלשהו שמשתנה בכל קריאה, המשורשרים יחד. E - פונקציית הצפנה סימטרית כמו AES וכן MAC - פונקציית אימות כמו HMAC.

הצפנה

נתונים פרמטרי התחום $(q,S,a,b,P,n,h)$, המפתח הציבורי $Q$ והמסר $m$.

1. בוחרים שלם אקראי $k$ בטווח $[1,n-1]$.
2. מחשבים את $R=kP$ וכן $Z=hkQ$ (יש לוודא ש-$Z\neq \infty$).
3. מציבים $(k_{1},k_{2})\leftarrow {\text{KDF}}(x_{Z}\ \|\ R)$ כאשר $x_{Z}$ הוא הקואורדינטה $x$ של הנקודה $Z$ והסימן $\|$ מייצג שרשור (concatenation).
4. מחשבים את $C=E_{k_{1}}(m)$ וכן $\tau ={\text{MAC}}_{k_{2}}(C)$.

התוצאה היא השלישייה: הטקסט המוצפן $C$, תג האימות $\tau$ והאלמנט $R$.

פענוח

נתונים פרמטרי התחום $(q,S,a,b,P,n,h)$, המפתח הפרטי $d$, האלמנט $R$ יחד עם הטקסט המוצפן $C$ ותג האימות $\tau$ (כמובן שיש לוודא את תקפות כל הפרמטרים לפי התקן).

1. מחשבים את $Z=hdR$ אם מתקבל $\infty$ מחזירים INVALID.
2. מציבים $(k_{1},k_{2})\leftarrow {\text{KDF}}(x_{Z}\ \|\ R)$.
3. מחשבים את $\tau '={\text{MAC}}_{k_{2}}(C)$ אם $\tau '\neq \tau$ מחזירים INVALID.
4. מחשבים את $m=E_{k_{1}}^{-1}(C)$.

הטקסט המקורי הוא $m$. אפשר לראות שאם הטקסט המוצפן $(R,C,\tau )$ נוצר על ידי המשתמש הלגיטימי כאשר הצפין את $m$ הרי שמתקיים

$hdR=hd(kP)=hk(dP)=hkQ$

בהצפנה שורות 1 ו-2 הן דיפי-הלמן, הכפל ב-$h$ נועד להבטיח באופן עקיף שהתוצאה בטווח המותר. פעולה 3 באלגוריתם ההצפנה ופעולה 2 באלגוריתם הפענוח מניבות תוצאה זהה, מכאן המקבל יכול לייצר את זוג המפתחות $(k_{1},k_{2})$ שחישב השולח באמצעות אותה פונקציית KDF ולשחזר את הטקסט המוצפן. אך יש להישמר מהתקפת ערוץ צדדי כך שלתוקף לא תהיה דרך לדעת באיזה שלב של האלגוריתם הוחזרה הודעת שגיאה אם ארעה.

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

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

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

משוואת העקום האליפטי מעל שדה זה היא: $y^{2}+xy=x^{3}+ax^{2}+b$ כאשר $a,b\in \mathbb {F} _{2^{m}}$ וכן $b\neq 0$. הקבוצה $E(\mathbb {F} _{2^{m}})$ כוללת את כל הנקודות שהקואורדינטות שלהן $x$ ו-$y$ הן אלמנטים בשדה הבינארי המורחב אשר מקיימות את משוואת העקום, יחד עם הנקודה באין סוף ${\mathcal {O}}$. יחד עם פעולות החיבור והכפל מתקבלת חבורה ציקלית סופית מסדר $2^{m}$ בקירוב.

כללי החיבור והכפל בעקום אליפטי מעל שדה בינארי מורחב שונות במעט: לחיבור הנקודות $P=(x_{1},y_{1})$ ו-$Q=(x_{2},y_{2})$ כאשר $P\neq Q$ מבצעים:

$x_{3}=\left({\frac {y_{1}+y_{2}}{x_{1}+x_{2}}}\right)^{2}+{\frac {y_{1}+y_{2}}{x_{1}+x_{2}}}+x_{1}+x_{2}+a$

$y_{3}=\left({\frac {y_{1}+y_{2}}{x_{1}+x_{2}}}\right)+(x_{1}+x_{3})+x_{3}+y_{1}$

כפל נקודה $2P=(x_{3},y_{3})$ כאשר $P\neq -P$ מתבצע על ידי:

$x_{3}=x_{1}^{2}+{\frac {b}{x_{1}^{2}}},\ \ y_{3}=x_{1}^{2}+\left(x_{1}+{\frac {y_{1}}{x_{1}}}\right)x_{3}+x_{3}$

למטרות הצפנה, מקובל לבחור $\ 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_{1}x+a_{2}x^{2}+a_{3}x^{3}$ כאשר $\ a_{0},\dots ,a_{3}\in \mathbb {F} _{2}$, ובאופן חסכוני אפשר להציג איבר כזה כמחרוזת סיביות, $\ s=(a_{3}a_{2}a_{1}a_{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^{3}x^{2}+g^{14}$

חישוב $\ {\mbox{R = P + Q =}}(g^{1},g^{12})+(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)$

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

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

$X_{2n}=(X_{n}-Z_{n})^{2}(X_{n}+Z_{n})^{2}$, $Z_{2n}=((X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2})\left((X_{n}+Z_{n})^{2}+{\frac {A-2}{4}}((X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2})\right)$ $X_{2n+1}=((X_{n}-Z_{n})(X_{n+1}+Z_{n+1})+(X_{n}+Z_{n})(X_{n+1}-Z_{n+1}))2Z_{1},$ $Z_{2n+1}=((X_{n}-Z_{n})(X_{n+1}+Z_{n+1})-(X_{n}+Z_{n})(X_{n+1}-Z_{n+1}))2X_{1}$

יוצא שהכפל $nX$ התבצע תוך 11 פעולות כפל באלמנטים מסדר $n$ ללא חילוק או חישוב הופכי כפלי כלל.

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

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

ביטחון

האלגוריתם היעיל ביותר הידוע כיום לפתרון בעיית לוגריתם בדיד בחבורות, תחשיב האינדקסים אינו ישים בעקומים אליפטיים כיוון שהוא מסתמך על מספרים חלקים ולא קיימת הגדרה מתמטית ברורה למספרים חלקים בעקום אליפטי. אלגוריתם רו של פולרד ללוגריתמים נחשב לשיטה היעילה ביותר הקיימת כיום לפתרון בעיית ECDLP וסיבוכיותה היא $\textstyle O({\sqrt {n}})$ בקירוב. על כן אינה יעילה (גם בגרסה המקבילית שלה) כשמדובר בשדה מסדר גדול. עבור ביטחון בסדר גודל של 128 סיביות מספיק שסדר העקום יהיה $\textstyle q\approx 2^{256}$. לשם המחשה, מערכת מפתח ציבורי דורשת מפתח בסדר גודל של כ-2048 סיביות כדי שתקרא בטוחה ברמה המקבילה ל-AES עם מפתח באורך 128 סיביות. במערכת ECC מקבילה, מפתח בגודל 224 סיביות מספק בטיחות שקולה. לפי המלצות NIST בתקן 800-131A (תחת הכותרת שינוי אלגוריתמים קריפטוגרפיים ואורך מפתחות) שפורסם ביולי 2018, עד דצמבר 2023 ההמלצה היא להשתמש עבור RSA במפתחות באורך 2048 לפחות, עבור DSA מפתחות באורך (2048,224), (2048,256) או (3072,256) ועבור ECC מפתח באורך 224 סיביות ומעלה. ב-2004 פוצח עקום ECC109 עם מפתח בגודל 109 סיביות. לשם כך נדרשו 2600 יחידות מחשב שפעלו באופן מקבילי במשך 17 חודשים. בנובמבר 2009 החלו קבוצת חוקרים בפרויקט לשבירת העקום ECC2K-130 מתוך רשימת האתגרים של חברת סרטיקום (שהפרס עליו היה 20,000$). זהו עקום קובליץ מעל השדה הבינארי בגודל 130 סיביות והוא העקום הקטן ביותר שטרם פוצח מתוך רשימת האתגרים של סרטיקום. ההערכה המקורית של חברת סרטיקום בשנת 1997 הייתה שיקח לפחות $2.7\times 10^{9}$ ימים לשבירתו ולכן בהגדרה נאמר שהוא בלתי שביר. אולם המחקר האחרון מראה שבעקבות ההתקדמות הטכנולוגית הן ברמה חומרה והן ברמת תוכנה ההערכה הזו לא נכונה. כיום ההערכה היא שהעקום ניתן לשבירה וזה רק עניין של זמן (מספר שנים) עד שהוא יפוצח.

התקפת ערוץ צדדי

ערך מורחב – התקפת ערוץ צדדי

ההבדל המהותי בין חישוב פעולת חיבור לבין פעולת כפל של נקודות בעקום אליפטי, מהווה נקודת תורפה שיש להימנע ממנה, כיוון שמערכת המיישמת את ECC עלולה להדליף מידע פנימי כתוצאה מהפרשי הזמן במהלך ביצוע פעולות כפל וחיבור. התקפת ערוץ צדדי מנצלת מידע כזה. אפשר לחלק התקפה זו לשני סוגים עיקריים, האחת נקראת Simple Power Analysis שבה מודדים את עצמת הצריכה של המעבד (CPU) במהלך ביצוע 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) המתוארת לעיל, ניתן ליישם את פרוטוקול דיפי-הלמן (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 בפועל. כלומר, במציאות קורה לא אחת שקל לפצח את המערכת מבלי לפתור את בעיית דיפי הלמן או בעיית הלוגריתם הבדיד. הסיבה העיקרית היא שיש סיכויים טובים שמי שמימש את העקום בתוך מערכת ההצפנה עשה זאת בצורה שגויה. בגלל שיישומו בפועל עלול להדליף שלא במודע מידע קריטי, אם בשל יישום לקוי, טיפול לא נכון במקרי קצה ומצבי שגיאה או בגלל מידע תזמון שדולף מהמעבד או זיכרון המטמון בזמן ביצוע החישובים האריתמטיים. מימוש בטוח של הצפנת עקום אליפטי אפילו אם הוא תואם את התקן, מתגלה כמשימה קשה מאוד. יתרה מזו, כל התקנים שואפים להבטיח יעילות גבוהה ככל האפשר בנוסף לביטחון. עובדה זו מטילה מגבלות נוספות על אופן המימוש שלו. מחקרים מראים שבמקרים אחדים לא רק שהעקום לא היה יעיל, אלא שכל המגבלות והאופטימיזציות שנוספו רק השפיעו לרעה על יעילות העקום ובעיקר על ביטחונו.

תקנים חדשים

ב-2007 גילה המתמטיקאי הרולד אדוארד משפחה חדשה של עקומים אליפטיים מהצורה $x^{2}+y^{2}=1+dx^{2}y^{2}$. מאוחר יותר פרסמו דניאל ברנשטיין וטניה לאנג שאפשר לנצל את עקומי אדוארד ווריאציות מפותלות שלהם לצורך קריפטוגרפי. האטרקטיביות של עקומים אילו היא בעובדה שחיבור נקודות בהם קל יותר. עקומי אדוארד נוטים להיות קלים יותר למימוש באופן בטוח בגלל שהם תומכים בנוסחאות חיבור שלמות שאינן כוללות מקרים חריגים שעלולים להוביל לחילוק באפס. מה שמאפשר מימוש בטוח באופן כזה שאינו מדליף מידע צדדי. כמו כן עקומים אילו מהירים ופשוטים יחסית. לכל עקומי אדוארד והגרסאות המפותלות שלהם יש פקטור משלים המתחלק בארבע, מסיבה זו עקומי NIST מסדר ראשוני אינם ניתנים לייצוג בצורה זו. מאז נוספו מספר עקומים חדשים המבוססים על עקומי אדוארד וכן עקומי מונטגומרי שהמכנה המשותף שלהם הוא ביטחון ויעילות גבוהים לפי סטנדרטים מחמירים ביותר. בטבלה הבאה נכללו מספר עקומים אליפטיים חדשים שאינם מוגנים בפטנטים ושעוצבו לאחר 2007 כאשר רמת הביטחון שלהם נמדדת לפי המודולוס הראשוני $p$, ליתר דיוק בפקטור שהוא מחצית מאורכו בסיביות. למשל אם $|p|\approx 256$ סיביות ביטחון העקום הוא $2^{128}$ בקירוב, שזה מקביל לביטחון של צופן AES עם מפתח באורך 128 סיביות.

שם העקום	משוואת העקום	המודולוס הראשוני $p$	מפתחים
M-221	$y^{2}=x^{3}+117050x^{2}+x$	$2^{221}-3$	Aranha, Barreto, Pereira, Ricardini, 2013
E-222	$x^{2}+y^{2}=1+160102x^{2}y^{2}$	$2^{222}-117$	Aranha, Barreto, Pereira, Ricardini 2013
Curve1174	$x^{2}+y^{2}=1-1174x^{2}y^{2}$	$2^{251}-9$	Bernstein, Hamburg, Krasnova, Lange 2013
Curve25519	$y^{2}=x^{3}+486662x^{2}+x$	$2^{255}-9$	Bernstein 2007
E-382	$x^{2}+y^{2}=1-67254x^{2}y^{2}$	$2^{382}-105$	Aranha, Barreto, Pereira, Ricardini, 2013
M-383	$y^{2}=x^{3}+2065150x^{2}+x$	$2^{383}-187$	Aranha, Barreto, Pereira, Ricardini, 2013
Curve383187	$y^{2}=x^{3}+229969x^{2}+x$	$2^{383}-187$	Aranha, Barreto, Pereira, Ricardini, 2013
Curve41417	$x^{2}+y^{2}=1+3617x^{2}y^{2}$	$2^{414}-17$	Bernstein, Lange 2013
Ed448	$x^{2}+y^{2}=1-39081x^{2}y^{2}$	$2^{448}-2^{224}-1$	Hamburg 2014
M-511	$y^{2}=x^{3}+530438x^{2}+x$	$2^{511}-187$	Aranha, Barreto, Pereira, Ricardini, 2013
E-521	$x^{2}+y^{2}=1-376014x^{2}y^{2}$	$2^{521}-1$	Aranha, Barreto, Pereira, Ricardini, 2013

ראו גם

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

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

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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