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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

היסטוריה ורקע[עריכת קוד מקור | עריכה]

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

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

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

הגדרה כללית[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – עקום אליפטי

עקום אליפטי הוא עקום אלגברי פרויקטיבי חלק (שאין לו "קצוות חדים"), המוגדר על ידי משוואה ממעלה שלישית. ניתן להגדיר עקום אליפטי מעל כל שדה. מעל שדה בעל מאפיין שאינו 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 גדול.

אריתמטיקה בעקומים אליפטיים[עריכת קוד מקור | עריכה]

ECADD2.jpg

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

כללי האריתמטיקה[עריכת קוד מקור | עריכה]

כללי האריתמטיקה לעקום אליפטי משתנות בהתאם לשדה עליו הוא מבוסס. בשדה בעל מאפיין 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 כדי לבצע פעולות חוזרות של חיבור וכפל המתוארים לעיל. לדוגמה כפל נקודה מימין לשמאל מתבצע כדלהלן:

קלט: שלם k באורך t סיביות (בייצוג בינארי k_{t-1},...,k_1,k_0), הנקודה P.
פלט: הנקודה Q=kP.
1. Q=\mathcal{O}
2. מ-1 עד t-1 בצע:
אם k_i=1 בצע Q\leftarrow Q+P
P\leftarrow 2P
3. החזר את Q

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

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

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

בעיית הלוגריתם הדיסקרטי בעקום אליפטי בקיצור ECDLP[עריכת קוד מקור | עריכה]

בהינתן עקום אליפטי E המוגדר מעל שדה סופי \mathbb{F}_q,
הנקודה P\in E(\mathbb{F}_q) מסדר n, הנקודה Q\in\left \langle P\right \rangle,
מצא שלם l\in [0,n-1] כך שמתקיים Q=lP.

השלם l נקרא הלוגריתם הדיסקרטי (בדידי) של Q בבסיס P ואפשר לסמנו בקיצור l=\text{log}_PQ. הסימן \left \langle P\right \rangle מייצג את הכפולות של P, אוסף הנקודות \{\mathcal{O},P,2P,3P,...,(n-1)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 הוא הסדר (מספר הנקודות).

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

בחירת פרמטרים[עריכת קוד מקור | עריכה]

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

(\sqrt{q}-1)^2 \ \le \ \#E(\mathbb{F}_q) \ \le \ (\sqrt{q}+1)^2

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

q+1-2\sqrt{q} \ \le \ nh \ \le \ q+1+2\sqrt{q}

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

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

פרמטרי התחום[עריכת קוד מקור | עריכה]

פרמטרי התחום (domain parameters) של עקום אליפטי לצורך קריפטוגרפי הם:

  • q הסדר של השדה \mathbb{F}, חשוב שיהיה ראשוני או חזקה של ראשוני (דהיינו q=p ראשוני או q=2^m) וכן רצוי ש-m יהיה ראשוני גם הוא[דרוש מקור].
  • שני אלמנטים 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.
  • h שנקרא גורם משני (cofactor) כך שמתקיים h=\#E(\mathbb{F}_q)/n.

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

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

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

מפתח פרטי ומפתח ציבורי[עריכת קוד מקור | עריכה]

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

הצפנה עם עקום אליפטי[עריכת קוד מקור | עריכה]

ניתן ליישם את צופן אל-גמאל בעקום אליפטי כדלהלן; אם אליס מעוניינת לשלוח את המסר m לבוב עליה תחילה להמירו לנקודה M בדרך מוסכמת ואותה להצפין על ידי חיבור עם kQ, כאשר k שלם אקראי "טרי", שנבחר על ידה על מנת להצפין את המסר M ואילו Q הוא המפתח הציבורי של בוב. ואז היא יכולה לשדר לבוב בערוץ הפתוח את הערכים C_1=kP, וכן C_2=M+kQ. זה עובד היות שמתקיים

dC_1=d(kP)=k(dP)=kQ

היות ש-M=C_2-kQ בוב יכול להחליפו בביטוי M=C_2-dC_1. המאזינה איב שמעוניינת לגלות את 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\ne \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'\ne \tau מחזירים INVALID.
  4. מחשבים את m=E_{k_1}^{-1}(C).

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

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

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

טכניקות להאצת תהליך ההצפנה וייעולו[עריכת קוד מקור | עריכה]

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

עקום אליפטי בשדה בינארי[עריכת קוד מקור | עריכה]

שדה בינארי הוא שדה סופי בעל מאפיין 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 + 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)

קואורדינטות פרויקטיביות[עריכת קוד מקור | עריכה]

אפשר לראות שחיבור נקודות בעקום אליפטי דורש בנוסף לכפל וחיבור רגילים פעולת היפוך (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 בליווי הסברים כיצד לבצע צמצום מודולרי יעיל במספרים אלו.

בטיחות[עריכת קוד מקור | עריכה]

האלגוריתם היעיל ביותר הידוע כיום לפתרון בעיית לוגריתם דיסקרטי בחבורות, תחשיב האינדקסים אינו ישים בעקומים אליפטיים כיוון שהוא מסתמך על "מספרים חלקים" ולא קיימת הגדרה מתמטית ברורה למספרים חלקים בעקום אליפטי. שיטת פולרד הנה השיטה היעילה ביותר הקיימת כיום לפתרון בעיית ECDLP וסיבוכיותה היא \ \sqrt{(\pi n/2)} בקירוב. על כן אינה יעילה (גם בגרסה המקבילית שלה) כשמדובר בשדה מסדר גדול. עבור בטיחות של 128 סיביות מספיק שהסדר יהיה \ q \approx 2^{256}. לשם המחשה, מערכת מפתח פומבי (בחבורות) דורשת מפתח פומבי בסדר גודל של כ-2048 סיביות כדי שתקרא בטוחה. במערכת ECC מקבילה, מפתח בגודל 224 סיביות מספק בטיחות שקולה. מערכת ECC היחידה שנפרצה נכון להיום הייתה עם מפתח בגודל 109 סיביות. בפריצת ECC עם שדה ראשוני בגודל זה, נדרשו כעשרת אלפים יחידות מחשב שפעלו באופן מקבילי ללא הרף במשך תקופה של 540 יום‏[8].

התקפת ערוץ צדדי[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – התקפת ערוץ צדדי

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

ביבליוגרפיה[עריכת קוד מקור | עריכה]

  1. ^ Victor S. Miller: Use of Elliptic Curves in Cryptography. CRYPTO 1985: 417-426
  2. ^ Neal Koblitz, Elliptic curve cryptosystems, Math. Computation, Vol. 48 (1987) pp. 203-209.
  3. ^ J. Pollard, "Monte Carlo methods for index computation mod p", Mathematics of computation, 32 (1978), 918-924
  4. ^ S. Pohlig and M. Hellman, "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance", IEEE Transactions on Information Theory, 24 (1978), 106-110
  5. ^ A. Menezes, M. Qu and S. Vanstone, "Key agreement and the need for authentication", presentation at PKS '95, Toronto, Canada, November 1995
  6. ^ A. Menezes, T. Okamoto and S. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field", IEEE Transactions on Information Theory, 39 (1993), 1639-1646
  7. ^ T. Satoh and K. Arkai, "Fermat quotients and the polynomial time discrete log algorithm to anomalous elliptic curves", Commentarii Mathematici Universitatis Sancti Pauli, 47 (1998), 81-92
  8. ^ http://www.certicom.com/index.php/2002-press-releases/340-notre-dame-mathematician-solves-eccp-109-encryption-key-problem-issued-in-1997

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]