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

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

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

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

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

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

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

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

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

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

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

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

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

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

ביטחון

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

גודל מפתח

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