הצפנה מבוססת עקום אליפטי (Elliptic Curve Cryptography, ECC) היא שיטת הצפנה אסימטרית שמשתמשת במבנה מתמטי שנקרא עקום אליפטי מעל שדה סופי. שדה סופי הוא קבוצה סופית של מספרים שבה ניתן לבצע חיבור וכפל כמו רגיל, אבל תוצאתן נשארת בתוך הקבוצה. היתרון המרכזי של ECC הוא שמפתחות ההצפנה יכולים להיות קצרים יותר מאשר במערכות כמו RSA, ובכך לחסוך בזמן חישוב ובמשאבים חומרתיים בלי לפגוע ברמת הביטחון כשהפרמטרים נבחרים נכון. הרעיון הוצע על ידי ויקטור מילר וניל קובליץ בשנות ה-80.
עקומים אליפטיים נחקרו במתמטיקה שנים רבות. הם שימשו בעבר בבעיות בתורת המספרים ובגאומטריה אלגברית. בשנים האחרונות נמצאו להם שימושים קריפטוגרפיים רבים. קיימים תקנים בינלאומיים ליישום ECC, והמחקר בתחום נמשך.
עקום אליפטי מוגדר על ידי משוואה פולינומית ממעלה שלישית. במקרים פשוטים העבודה נעשית עם המשוואה y^2 = x^3 + ax + b כש-a ו-b הם מספרים בשדה. אוסף הנקודות שעונות על המשוואה יחד עם "הנקודה באינסוף"
מהווים קבוצה שבה אפשר להגדיר חיבור של נקודות. התנאי 4a^3 + 27b^2 ≠ 0 מוודא שהעקום חלקי ולא מכיל נקודות מיוחדות מדי.
על קבוצת הנקודות של העקום ניתן להגדיר חיבור נקודות כך שהקבוצה הופכת לחבורה אבלית. חיבור גרפי נעשה על ידי קו החותך את העקום בשלוש נקודות: אם הקו חותך ב-P ו-Q, אז הנקודה השלישית משתקפת סביב ציר ה-x ומתקבלת P+Q. חיבור נקודה בעצמה נקרא point doubling. בפועל משתמשים בנוסחאות אלגבריות לחישוב חיבור וכפל נקודות בשדה נתון.
נוסחאות לחיבור שתי נקודות ולכפל נקודה בעצמה תלויות בסוג השדה. מעל שדות בעלי מאפיין שונה מ-2 או 3 משתמשים בנוסחאות ויירשטראס: למשל x_r = λ^2 - x_p - x_q, y_r = λ(x_p - x_r) - y_p עם λ=(y_q-y_p)/(x_q-x_p). בכפלה עצמית λ שונה ומכיל את המקדמים של העקום. מעל שדה סופי, חילוק מתבצע באמצעות הכפלה בהופכי כפלים מודולו p, שנמצא בעזרת אלגוריתם אוקלידס.
ניתן להציג דוגמאות פשוטות בעבודה מעל שדות קטנים. למשל בעקום מסוים מעל השדה של מוכפלים מודולו 23 נקודות יכולות להתחבר ולתת תוצאות כמו P+Q=(15,6) ובעזרת נוסחאות אפשר לחשב 2P=(10,18). דוגמאות כאלו ממחישות את החיבור והכפל בעקומים בסביבה סופית.
כפל סקלרי (Scalar Multiplication) הוא חיבור חוזר של נקודה P בעצמה k פעמים לקבלת kP. זו פעולה מרכזית ב-ECC. מבצעים אותה באמצעות אלגוריתמים שמנצלים את הייצוג הבינארי של k כדי להקטין חישובים, כמו שיטת ה"כפל בינארי". שיטות מתקדמות נוספות הן חלון ואלגוריתמים מיוחדים לשיפור מהירות ובטיחות מפני התקפות ערוץ צדדי.
העיקרון הוא פונקציה חד-כיוונית: קל לחשב kP, אבל קשה למצוא k בהינתן Q=kP. קושי זה נקרא בעיית הלוגריתם הבדיד בעקום אליפטי (ECDLP). מבנים קריפטוגרפיים מרכזיים מבוססים על הבעיה הזאת, בין השאר חתימה דיגיטלית, שיתוף מפתח והצפנה אסימטרית. חשוב לזכור שקיים אלגוריתם קוונטי שיכול לפרק בעיות כאלו במהירות, ולכן ECC אינה בטוחה מפני מחשב קוונטי עתידי.
בגרסה פשוטה: בהינתן נקודה P ועוד נקודה Q ששייכת לקבוצה שנוצרת על ידי P, למצוא k כך ש-Q=kP. k נקרא הלוגריתם הבדיד של Q בבסיס P. זו הבעיה שעליה מבוססים ביטוח ובטיחות של פרוטוקולים.
בהינתן P, A=aP ו-B=bP, למצוא C=abP. אם יודעים לפתור ECDLP, פותרים גם ECDHP, אך ההפך לא הוכח כללית.
הבעיה היא להכריע אם נקודה C שווה ל-abP או לא, בהינתן P, A=aP, B=bP ו-C=cP. יש לה חשיבות בהוכחות ביטחון של פרוטוקולים.
יש עקומים קטנים שבהם אפשר לחשב לוגריתם בדיד ישירות. לדוגמה בעקום מעל
F_73 נמצא כי Q=11P ולכן log_P(Q)=11. דוגמאות אלו משמשות להבנה יותר מאשר ליישום מעשי.
לבחירת עקום לצורכי קריפטוגרפיה דרושות בחינות קפדניות. יש לוודא שמספר נקודות העקום (#E) מכיל גורם ראשוני גדול n, שהנקודה הבסיס P היא מסדר n, ושאין חולשות מיוחדות כמו עקומים סופר-סינגולריים או "עקום אנומלי". יש להשתמש בפרמטרים שבדקו תקנים ידועים, ולשמור גרעין (seed) כשאפשר להראות שהעקום נוצר באופן אקראי.
חשיבות נוספת היא מניעת דלתות אחוריות (backdoors) בפרמטרים ציבוריים. חשיפות כמו הדלפות סנודן הראו חששות לגבי בחירת פרמטרים על ידי ארגונים מסוימים, והדבר הוביל לביקוש לעקומים אחרים כגון Curve25519 של דניאל ברנשטיין.
פרמטרי תחום כוללים את השדה
q, מקדמי העקום a,b, נקודת בסיס G ונוספים כמו סדר n ו-cofactor h. יש לוודא תקינות פרמטרים לפני שימוש, כולל שאינם גורמים להחלשות הביטחון.
מספר הנקודות בעקום משפיע על ביטחון המערכת. קיימים אלגוריתמים כמוהו של שוף (Schoof) ושיפוריהם לספירת נקודות בזמן פולינומי. ספירה זו חשובה כדי לבחור עקומים בטוחים.
אחת הדרכים היא לייצר פרמטרים מתוך גרעין seed בעזרת פונקציית גיבוב כמו SHA-2. שמירת הגרעין מאפשרת אימות שהפרמטרים לא נבחרו במכוון להכיל חולשה.
המפתח הפרטי הוא שלם d אקראי בטווח [1,n-1]. המפתח הציבורי הוא Q=dP. על המפתח הציבורי להיות נקודה תקפה בעקום ולא הנקודה באינסוף. מפתחות צריכים להיות מאומתים באמצעות תעודות דיגיטליות או חתימות.
ניתן להמיר מסר לנקודה M ולהצפין אותו באמצעות שיטה דמוית אל-ג׳מאל על העקום: אליס בוחרת k אקראי ושולחת C1=kP ו-C2=M+kQ. בוב מפענח בעזרת המפתח הפרטי d מקבל M=C2-dC1. פרוטוקול עשיר ומקובל יותר הוא ECIES, שמשלב חישוב דיפי-הילמן, פונקציית KDF להצפנה סימטרית ואימות MAC.
שדות בינאריים הם שדות בגודל 2^m, וניתן לייצג אלמנטים כמחרוזות סיביות. בעבודה בשדה זה המשוואה היא y^2+xy=x^3+ax^2+b. שדות בינאריים מקלים על יישום חומרתי כי חיבור שווה ל-XOR.
כדי להימנע מחישוב הופכי כפלי יקרים, משתמשים בייצוגים פרויקטיביים ובשיטות כמו סולם מונטגומרי. כך אפשר לבצע כפל נקודות מבלי לחשב הופכיים מודולרים בכל שלב.
צמצום מודולרי יכול להיות מהיר כאשר הראשוני p הוא מספר מיוחד, כמו ראשוני מרסן. תקנים מסבירים שיטות לצמצום מהיר במספרים כאלו.
האלגוריתם הטוב ביותר הידוע לפתרון ECDLP בקבוצה כללית הוא אלגוריתם פולרד רו, עם סיבוכיות בסדר
O(√n). לפיכך צריך לבחור סדר גדול כדי להשיג ביטחון מספק. מומלץ להשתמש באורכי מפתחות לפי הנחיות תקינה, ולזכור כי מחשב קוונטי ישנה את התמונה.
יישום לא זהיר יכול לדלוף מידע באמצעות מדידת זמן או צריכת אנרגיה. התקפות אלה נקראות SPA ו-DPA. קיימות שיטות הגנה, למשל שימוש באלגוריתמים אחידים תמידיים כמו סולם מונטגומרי, הוספת אקראיות ונוסחאות שמאזנות את זמן הריצה.
מפתח ציבורי מיוצג על ידי שתי קואורדינטות, אך ניתן לדחוס את y לסיבית אחת. לכן גודל מפתח פרקטי תלוי בגודל השדה. בדרך כלל מפתח ECC של כ-224, 256 סיביות מספק ביטחון שקול ל-RSA גדול בהרבה.
יש תקנים רבים ל-ECC ולפרוטוקולים קשורים כמו ECDH ו-ECDSA. בעבר היו ויכוחים על פטנטים וחשדות לניסיון לשתול דלתות אחוריות בתקן. לאחר חשיפות נוצר ביקוש לעקומים אלטרנטיביים שאינם מעוררי חשד.
מאז 2007 הופיעו משפחות חדשות של עקומים, כמו עקומי אדוארד וגרסאותיהם. הם מציעים נוסחאות חיבור פשוטות ובטוחות יותר, ולכן זוכים לפופולריות. דוגמאות מודרניות הן Curve25519 ועקומים נוספים שאינם מוגנים בפטנטים.
הצפנה בעקום אליפטי היא דרך להצפין מידע. עקום אליפטי הוא צורה מתמטית שנראית כמו עקומה מיוחדת. השיטה משתמשת בנקודות על העקום.
הרעיון הופיע בשנות ה-80. מאז חוקרים משתמשים בו כדי לשמור סודות במחשבים וטלפונים.
עקום אליפטי מוגדר על ידי משוואה. הנקודות שעונות עליה יוצרות קבוצה שאפשר לחבר ביניהן. יש נקודה מיוחדת שנקראת "הנקודה באינסוף". החיבור שם עובד לפי כללים ברורים.
כשמחברים שתי נקודות על העקום, יש דרך גרפית וקיימות נוסחאות לחישוב. כשמכפילים נקודה בעצמה זה נקרא כפל סקלרי. פעולה זו חשובה בהצפנה.
קל לחשב k פעמים את הנקודה P ולקבל kP. קשה למצוא את k כשנותנים רק את kP. הקושי הזה שומר על הסוד. הבעיה הקשה נקראת ECDLP, והיא הבסיס לאבטחה.
מפתחות פרטיים הם מספרים קטנים שמסתירים. מפתחות ציבוריים הם נקודות על העקום. אם רוצים לשלוח הודעה מוצפנת, שותלים נקודה אקראית ועושים חישוב שגורם שרק בעל המפתח הפרטי יוכל לפתור.
כדי שלא יהיו חולשות בוחרים עקומים בזהירות. יש רשימות עקומים בטוחות שנבדקו על ידי מומחים. דוגמה מפורסמת היא Curve25519.
אם מיישמים את הצופן בצורה לא נכונה הוא עלול לדלוף מידע דרך מדידות זמן או צריכת חשמל. לכן מפתחים משתמשים בשיטות מיוחדות כדי להסתיר את הפעולות.
בעוד ש-RSA צריך מפתחות מאוד ארוכים, ב-ECC המפתחות קצרים יותר. זה חוסך מקום ומהירות במכשירים קטנים.
ECC היא שיטה מודרנית וחזקה להצפנה. היא מתאימה במיוחד למכשירים קטנים. חוקרים עובדים כדי לשפר אותה ולהגן מפני טכנולוגיות עתידיות.
תגובות גולשים