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

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

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

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

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

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

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

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

ECADD2.jpg

בייצוג גרפי פעולת החיבור היא השתקפות הנקודה השלישית החותכת את היישר העובר דרך שתי נקודות \ \mbox{P} ו-\ \mbox{Q} (ראו תרשים). כאמור כיוון שהעקום אינו סינגולרי, ישר העובר דרך שתי נקודות יחתוך את העקום בדיוק בנקודה נוספת אחת ויחידה. \ \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 ועל-כן בתנאים מסוימים עלול לחשוף את המערכת להתקפות "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\}
2. אליס בוחרת שלם אקראי \ n בטווח \ [1, m-1] אשר ישמש כמפתח פרטי, אותו היא שומרת בסוד.
3. המפתח הפומבי של אליס הוא: \ \mbox{Q}=n\mbox{P}.
4. הפרמטרים של העקום האליפטי, דהיינו \ a, b, p, \rm{P}, פומביים גם כן ומכונים "Domain Parameters".

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

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

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

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

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

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

למעשה אליס מחשבת את: \ d=nC_1=n(rP)=r(nP)=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 + 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 בליווי הסברים כיצד לבצע צמצום מודולרי יעיל במספרים אלו.

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

כיון שקיימת הקבלה בין החבורה הנוצרת מעקום אליפטי בשדה סופי והחבורה הכפלית מודולו ראשוני \ p. אפשר למעשה להגדיר את בעיית לוגריתם דיסקרטי בעקום אליפטי כדלהלן: בהינתן עקום אליפטי \ E מעל \ \mathbb{F}_p מסדר \ n, הנקודה \ \mbox{P} \in \mbox{E}(\mathbb{F}_P) והנקודה \ \mbox{Q} \in \mbox{E}(\mathbb{F}_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 יום‏[3].

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

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

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

  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. ^ http://www.certicom.com/index.php/2002-press-releases/340-notre-dame-mathematician-solves-eccp-109-encryption-key-problem-issued-in-1997

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

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