tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
בשדה בעל מאפיין גדול מ-2 (לעקום שאינו סופרסינגולרי) תרגום הפעולות הגרפיות לנוסחאות אלגבריות הוא כדלהלן:
סכום שתי נקודות (ECADD) :
הכפלת נקודה יחידה (ECDBL) , החיבור זהה למעט:
הנקודה ההפכית של היא .
מעל שדה סופי פעולת החילוק מתבצעת על ידי הכפלה בהופכי הכפלי, לדוגמה הפעולה שקולה לפעולה .
לשם כך צריך להשתמש באלגוריתם למציאת הופכי כפלי המבוסס על הרעיון של אוקלידס.
לדוגמה יהיו ומשוואת העקום מעל השדה המכיל את 29 הנקודות המובאות להלן יחד עם נקודת האין סוף , כאשר :
היות ש- ראשוני, השדה הוא ציקלי (מחזורי) ולכן מכיל יוצרים.
אפשר לראות שאם מחברים את הנקודה בעצמה 29 פעמים מתקבלות כל נקודות העקום לא בהכרח לפי הסדר, עד שמגיעים לנקודת האין סוף, כלומר .
אם נבחר את הנקודות ו- החיבור מבוצע כך:
כדי להכפיל את הנקודה בשתים, מחשבים כדלהלן:
להבדיל מכפל רגיל מכנים פעולת כפל נקודות בעקום בשם כפל סקלרי (Scalar Multiplication).
הכפלה של נקודה בשלם כלשהו היא בעצם פעולת חיבור חוזר בסך הכול פעמים.
פעולה זו ניתן לבצע על ידי אלגוריתם רקורסיבי המנצל את הייצוג הבינארי של כדי לבצע פעולות חוזרות של חיבור וכפל המתוארים לעיל.
קיימות שיטות רבות לביצוע כפל נקודה בעקום אליפטי.
דוגמה אחת נקראת "שיטה בינארית מימין לשמאל" והיא מתבצעת כדלהלן:
קלט: שלם באורך סיביות (בייצוג בינארי ), הנקודה .
בשיטה זו זמן החישוב תלוי ב- ועל-כן בתנאים מסוימים עלול לחשוף את המערכת להתקפות ערוץ צדדי.
קיימות שיטות מתקדמות ויעילות יותר לביצוע כפל סקלרי כמו שיטת חלון (sliding window) או שיטת מונטגומרי.
ההתמודדות עם התקפות ערוץ צדדי תלויות מאוד באופן היישום ובסביבה בה האלגוריתם מיושם.
חשיבות עקום אליפטי בתורת ההצפנה היא בעובדה שהוא מועמד טוב לפונקציה חד-כיוונית שהכרחית בכל הצפנה א-סימטרית.
לדוגמה אם נתונה הנקודה ושלם כלשהו , מצד אחד חישוב (באמצעות אלגוריתם רקורסיבי כמו זה המתואר לעיל) קל לביצוע במחשב, לעומת זאת, בהינתן הנקודה מאוד קשה לגלות את .
זוהי בעיה מתמטית קשה הנקראת בעיית הלוגריתם הבדיד בעקום אליפטי.
לסדר העקום (מספר הנקודות בעקום) חשיבות רבה, בפרט על העקום להכיל תת-חבורה מסדר ראשוני גדול.
קיימים בעיקר שלושה פרימיטיבים קריפטוגרפיים מבוססי עקום אליפטי; הצפנה אסימטרית, חתימה דיגיטלית ופרוטוקול שיתוף מפתח, שלושתם מבוססים על גרסת העקום האליפטי של בעיית הלוגריתם הבדיד, בעיית דיפי-הלמן ובעיית הכרעת דיפי-הלמן, הנגזרות ממנה.
בעיות המוגדרות קשות חישובית, אם כי לא ידועה הוכחה מתמטית לכך.
בחבורת אוילר של שדה סופי קיימים אלגוריתמים תת-מעריכיים לפתרון הבעיות המנויות, אך האלגוריתם היעיל ביותר (הידוע) לפתרון בעיות (במחשב קלאסי) אלו עבור עקומים אליפטיים הוא בעל זמן ריצה מעריכי.
עקב כך, מפתחות ההצפנה בעקום אליפטי קטנים משמעותית ביחס למפתחות הצפנה בצפנים המבוססים על שדות סופיים, כמו צופן אל-גמאל או צופן RSA.
יש לציין שקיים אלגוריתם קוונטי לפתרון הבעיות הללו בעזרת מחשב קוונטי ביעילות, הן עבור חבורת אוילר והן עבור עקום אליפטי.
לכן כאשר מחשב קוונטי לשימוש כללי בקנה מידה גדול יהיה מעשי הצפנה המבוססת על עקום אליפטי לא תהיה בטוחה יותר לשימוש.
ישנו פרימיטיב נוסף שקשור לעקומים אליפטיים הנקרא הצפנה מבוססת איזוגניה.
זהו תחום מחקר חדש יחסית בקריפטוגרפיה, המבוסס על איזוגניות בין עקומים אליפטיים.
לא ידוע על אלגוריתם קוונטי יעיל לפתרון הבעיה ולכן היא מועמדת טובה להצפנה פוסט-קוונטית.
בעיית הלוגריתם הבדיד בעקום אליפטי בקיצור ECDLP
בהינתן עקום אליפטי המוגדר מעל שדה סופי ,
הנקודה מסדר , הנקודה ,
מצא שלם כך שמתקיים .
השלם נקרא הלוגריתם הבדיד (דיסקרטי) של בבסיס ואפשר לסמנו בקיצור .
הסימן מייצג את החבורה הציקלית שהיא אוסף הנקודות שהן כפולות של יחד עם הנקודה באין סוף.
שים לב שתמיד מתקיים .
בעיית דיפי-הלמן בעקום אליפטי בקיצור ECDHP
בעיית דיפי-הלמן בעקום אליפטי המקבילה לבעיית דיפי-הלמן המפורסמת היא בעיה חישובית המוגדרת כך:
כמובן שאם ניתן לפתור ביעילות את בעיית ECDLP יהיה קל לפתור את ECDHP, ההפך לא הוכח למעט מקרים פרטיים אחדים.
באופן כללי לא ידוע אם הבעיות שקולות.
בעיית הכרעת דיפי-הלמן בקיצור ECDDHP
בהינתן עקום אליפטי מעל ,
הנקודה מסדר , הנקודות וכן
הבעיה היא להכריע האם או האם .
כמובן שאם ניתן לפתור את ECDHP יהיה קל לפתור את ECDDHP.
שופ הוכיח שקיים חסם תחתון שהוא עבור בעיית ההכרעת דיפי-הלמן בעקום אליפטי, הוא הסדר (מספר הנקודות).
הבעיות המתוארות מהוות בסיס לפונקציה חד כיוונית המתאימה לצורך קריפטוגרפי.
עליהן אפשר לבנות פרוטוקולים קריפטוגרפיים בטוחים בהנחה שהבעיות אכן קשות לפתרון.
דוגמה ללוגריתם בדיד בעקום אליפטי
אם נתון העקום: מעל , הנקודות ו- הן בעקום ומפני שהעקום מכיל רק 41 נקודות קל לגלות באופן ישיר שהלוגריתם הבדיד הוא:
אחרי חישוב קל אפשר לראות שהם מקיימים וכן לכן:
אף על פי שלפי הנוסחה לעיל היות ש- למעשה סדר העקום הוא .
כך שרק 41 מהנקודות בעקום זה הן כפולות של .
כדי להשתמש בעקום אליפטי לצורך פרוטוקול קריפטוגרפי יש לשים לב לכמה היבטים חשובים כדי למנוע חולשות שעלולות להוביל לנקודות תורפה ולשבירת המערכת.
הפרמטרים הציבוריים של העקום נקראים "פרמטרי תחום" (Domain Parameters) שכאמור פומביים ומשותפים לכל המשתמשים במערכת אך יש לוודא את תקינותם.
תחילה בוחרים "עקום מתאים" המוגדר מעל שדה סופי עם מציין וכן בוחרים נקודת בסיס .
לפי משפט הסה בעקום אליפטי, מספר הנקודות של עקום אליפטי חסום על ידי
מזה נובע ש- אינו מחלק של ולכן לעקום זה קיימת תת-חבורה מסדר .
ממשפט זה נובע גם שקיים שלם יחיד הנקרא cofactor המקיים
במילים אחרות ולכן מספר הנקודות של העקום הוא .
וכדי למנוע התקפת תת-חבורה מסדר קטן המנצלת את סדר החבורה יש צורך שהנקודה תהיה מסדר .
באופן כללי כדי למנוע התקפות אילו ואחרות (שמנצלות חולשות הנובעות מתכונות מיוחדות של העקום) האסטרטגיה המומלצת היא לבחור את העקום באופן אקראי בתנאי כמובן של- יש גורם ראשוני גדול.
הסבירות שעקום שנבחר כך יהיה פגיע לאחת ההתקפות הללו אינה גדולה.
וכן חשוב לבחור את העקום באופן כזה שיהיה קל לוודא שהוא אכן עומד בתנאים המצוינים.
ב-2013 התגלה כחלק מההדלפות של סנודן שה-NSA שתלו דלת אחורית באלגוריתם Dual_EC_DRBG שהיה חלק מתקן של NIST למחולל פסאודו אקראי קריפטוגרפי המבוסס על עקום אליפטי.
מלבד זאת מומחים הביעו חשש בנוגע לאחדים מן הקבועים של NIST ש-NSA התערב בבחירתם.
בשל כך נוצרה דרישה לעקומים אליפטיים תיקניים שאינם נמנים עם הרשימה של NIST.
ב-2005 פרסם דניאל ברנשטיין את העקום Curve25519 המציע ביטחון ברמה של 128 סיביות והוא נמצא בשימוש נרחב כיום בין היתר על ידי OpenSSL וכן וואטסאפ.
פרמטרי התחום (domain parameters) של מערכת הצפנה בעקום אליפטי כוללים עקום אליפטי מתאים המוגדר מעל שדה סופי עם מציין ונקודת בסיס בנוסף למספר ערכים חשובים המהווים חלק בלתי נפרד מהמערכת.
פרמטרי התחום יכולים להיות משותפים לקבוצת משתמשים או ספציפיים למשתמש יחיד.
בחירת פרמטרים נכונה היא חלק קריטי בביטחון מערכת הצפנה כזו ולכן התקן מפרט צעדים מומלצים כיצד לייצר באופן אקראי או לבחור בעקום אליפטי יחד עם אוסף הפרמטרים באופן בטוח לשימוש קריפטוגרפי וכיצד לוודא שאכן עקום אליפטי אכן נוצר באופן שעונה על כל הדרישות האמורות.
פרמטרי התחום של עקום אליפטי לצורך קריפטוגרפי הם:
הסדר של השדה , צריך להיות ראשוני או חזקה של 2 (דהיינו ראשוני או ).
במקרה הראשון קואורדינטות הנקודות הן שלמים חיוביים המהווים אלמנטים בשדה ואילו במקרה השני הן פולינומים ממעלה מעל השדה המורחב כאשר המקדמים בינאריים.
גרעין התחלתי (seed) אופציונלי במקרה שהעקום האליפטי נוצר באופן אקראי ולא נבחר מתוך התקן.
הגרעין ההתחלתי משמש לבדיקה ואימות העקום.
שני אלמנטים ו- מהשדה המגדירים את נוסחת העקום האליפטי (כגון או במקרה של מציין ).
את האלמנטים הללו בוחרים על ידי פונקציית גיבוב יחד עם גרעין התחלתי (seed) אקראי כלשהו (אותו שומרים לצורך אימות עתידי).
שני אלמנטים (קואורדינטות) המייצגים את הנקודה מסדר ראשוני גבוה.
הסדר של הנקודה צריך להתחלק במספר ראשוני גדול.
שנקרא גורם משלים (cofactor) כך שמתקיים .
חשוב לוודא תקפות הפרמטרים לפני שמשתמשים בהם, כדי לוודא תקינותם יש לפעול כדלהלן:
לוודא ש- ראשוני או חזקה של ראשוני.
לוודא שהאלמנטים כולם אלמנטים בשדה ובפורמט הנכון (אפשר להיעזר בגרעין ההתחלתי שמסופק על ידי מי שייצר את העקום כדי לוודא שהוא אכן נוצר באקראי באמצעות פונקציית גיבוב).
לוודא שהאלמנטים מגדירים עקום אליפטי לא סינגולרי, כלומר שמתקיים (וכן ש- במקרה של עקום עם מציין ).
לוודא שהנקודה היא בעקום לפי הנוסחה האמורה.
לוודא ש-, ש- ראשוני וכן גדול מספיק (למשל ).
לוודא שהסדר (מספר נקודות העקום) מתחלק במספר ראשוני .
לוודא ש- אינו מחלק של עבור כל וכן .
בתקן SEC-1 של GSEC (חברת Certicom הקנדית) ובתקן של NIST, נקבע הבסיס האריתמטי או ייצוג האלמנטים לפי סוג השדה, בשדה ראשוני האלמנטים הם השלמים מודולו ונקודה בעקום מיוצגת על ידי קואורדינטות שלמות .
בשדה עם מציין 2 האלמנטים מיוצגים בבסיס פולינומי כאשר השדה הוא וקואורדינטות הנקודה הן פולינומים ממעלה .
מספר הנקודות בעקום האליפטי חשוב מאוד לביטחון מערכת ECC כאמור, כדי למנוע התקפות קריפטוגרפיות מסוימות שמנצלות סדר חבורה שמכיל גורמים קטנים.
ספירת נקודות העקום אפשרית בזמן פולינומי עם מספר אלגוריתמים ידועים ביניהם אלגוריתם של שוף (schoof) שהורחב ושופר לאחר מכן על ידי קובליץ אלקיס ואטקין ונקרא אלגוריתם SEA.
עם אלגוריתם SEA אפשר לספור את נקודות עקום אליפטי מעל שדה סופי מסדר 200 בתוך מספר שעות.
אלגוריתם SATOH פותח במיוחד לספירת נקודות עקום אליפטי מעל שדה בינארי מורחב, למשל אם אפשר לספור את נקודות העקום עם אלגוריתם SATOH בתוך מספר שניות.
הכנת עקום אליפטי באופן אקראי
הכנת עקום אליפטי באופן אקראי נעשית לפי התקן עם פונקציית גיבוב קריפטוגרפית כמו SHA-2 כאשר הגרעין ההתחלתי משמש כהוכחה שהעקום אכן נוצר באופן אקראי ולא נוצר במכוון כך שיכיל חולשות או דלתות סתר.
הרעיון הכללי הוא שמכינים עם פונקציית הגיבוב מתוך גרעין התחלתי seed מחרוזת סיביות אקראית באורך הרצוי .
מייצגים את המחרוזת כמספר בינארי שלם ומוודים שלא מתקיים וכן בוחרים שני שלמים אקראיים כך שמתקיים .
הגרעין ההתחלתי צריך להישמר יחד עם העקום והוא משמש כהוכחה.
הוא מייצר באותה דרך מחרוזת סיביות ומוודא שמתקבל אם התנאי לא מתקיים זו הוכחה שהעקום לא נבחר באקראי.
בהינתן הפרמטרים הציבוריים המפתח הפרטי הוא שלם אקראי בטווח הנשמר בסוד והמפתח הציבורי המתאים הוא שהוא כפל סקלרי של הנקודה עם המפתח הפרטי .
בדרך כלל המפתחות של כל משתמש צריכים להיות מאומתים ומשויכים אליו בדרך כלשהי.
בדרך קריפטוגרפית מאמתים מפתח באמצעות חתימה דיגיטלית או תעודה (certificate) שמונפקת על ידי רשות מאשרת (CA).
וכן בדרך כלל קיימת הפרדה בין המפתחות הקבועים המיועדים לטווח ארוך לבין מפתחות ארעיים (ephemeral keys) הנוצרים לצורך התקשרות ספציפית.
יש צורך תמיד לאמת תקפות המפתח הציבורי, לוודא שמקיים את התנאים המפורטים לעיל; ש- הוא נקודה בעקום שאינה וכן שהקואורדינטות שלה הם אלמנטים בשדה בטווח המתאים וכן שמתקיים .
בפועל משתדלים להימנע מהבדיקה האחרונה כיוון שהיא פעולה מכבידה במונחי מחשוב, אפשר לחסוך בדיקה זו על ידי שימוש בפרוטוקול שיתוף מפתח עם אימות כמו MQV שבו הבדיקה עקיפה ונעשית כחלק ממהלכי הפרוטוקול.
ביתר פירוט, אליס משדרת לבוב בערוץ הפתוח שני ערכים: שמכיל את המפתח המוצפן וכן שמכיל את המסר המוצפן.
כאשר בוב מקבל את הערכים הללו מאליס הוא מבצע את הפעולות בסדר הפוך, הוא מפענח את המפתח המוצפן ואז מחסיר את התוצאה מהטקסט המוצפן כדי לקבל את הנקודה וממנה לחלץ את המסר .
כאשר הוא המפתח הפרטי של בוב המקיים .
לכן היות ש- בוב יכול להחליפו בביטוי ולקבל את .
המאזינה איב שמעוניינת לגלות את צריכה לחשב תחילה את , חילוץ מתוך ומתוך היא בדיוק בעיית דיפי-הלמן.
למען הפשטות הגרסה המתוארת חסרה מספר מרכיבים חשובים כמו אימות ובדיקת תקפות.
להלן תיאור פרוטוקול הצפנה היברידי שנקרא ECIES (קיצור של Elliptic Curve Integrated Encryption Scheme) שהוצע על ידי בלייר ורוגווי, המשלב הצפנה אסימטרית המבוססת על צופן אל-גמאל והצפנה סימטרית עם אימות.
הוכנס לתקן ANSI X9.63 וכן ISO/IEC 15946-3 וכן IEEE P1363. בפרוטוקול זה מנצלים את פרוטוקול שיתוף הסוד הבסיסי של דיפי והלמן כדי לשתף שני מפתחות סודיים כאשר משמש להצפנת המסר ו- לאימות התוצאה להגנה מפני התקפת מוצפן-נבחר.
לצורך הפרוטוקול מוגדרות שלוש פונקציות בסיסיות; KDF - פונקציית הכנת מפתח שהיא תוצאת פונקציית גיבוב של גרעין כלשהו ומונה כלשהו שמשתנה בכל קריאה, המשורשרים יחד.
E - פונקציית הצפנה סימטרית כמו AES וכן MAC - פונקציית אימות כמו HMAC.
נתונים פרמטרי התחום , המפתח הציבורי והמסר .
בוחרים שלם אקראי בטווח .
מחשבים את וכן (יש לוודא ש-).
מציבים כאשר הוא הקואורדינטה של הנקודה והסימן מייצג שרשור (concatenation).
התוצאה היא השלישייה: הטקסט המוצפן , תג האימות והאלמנט .
נתונים פרמטרי התחום , המפתח הפרטי , האלמנט יחד עם הטקסט המוצפן ותג האימות (כמובן שיש לוודא את תקפות כל הפרמטרים לפי התקן).
מחשבים את אם מתקבל מחזירים INVALID.
מחשבים את אם מחזירים INVALID.
אפשר לראות שאם הטקסט המוצפן נוצר על ידי המשתמש הלגיטימי כאשר הצפין את הרי שמתקיים
בהצפנה שורות 1 ו-2 הן דיפי-הלמן, הכפל ב- נועד להבטיח באופן עקיף שהתוצאה בטווח המותר.
פעולה 3 באלגוריתם ההצפנה ופעולה 2 באלגוריתם הפענוח מניבות תוצאה זהה, מכאן המקבל יכול לייצר את זוג המפתחות שחישב השולח באמצעות אותה פונקציית KDF ולשחזר את הטקסט המוצפן.
אך יש להישמר מהתקפת ערוץ צדדי כך שלתוקף לא תהיה דרך לדעת באיזה שלב של האלגוריתם הוחזרה הודעת שגיאה אם ארעה.
עקום אליפטי מעל שדה בינארי
בשל החישובים המורכבים יישום מערכת הצפנה בעקום אליפטי בצורה נאיבית איטי ומסורבל.
השאיפה היא שהמערכת תהיה אופטימלית (במונחי זמן עיבוד וצריכת זיכרון) ככל שניתן והדבר חשוב במיוחד במערכות ניידות שמטבען מוגבלות יותר ממקבילותיהן הנייחות.
תכונות השדה הבינארי מאפשרות שיפור ביצועים בפעולות אריתמטיות בסיסיות, לכן תקני עקומים אליפטיים כוללים מפרטים למימוש הצפנה בעקום אליפטי מעל שדה בינארי מורחב.
שדה בינארי הוא שדה סופי בעל מאפיין 2, כאשר מספר האיברים בו הוא תמיד חזקה של 2. לכן ניתן ליצג כל אלמנט בשדה כמחרוזת של סיביות.
קיים רק שדה אחד בגודל עבור כל שלם נתון.
משוואת העקום האליפטי מעל שדה זה היא: כאשר וכן .
הקבוצה כוללת את כל הנקודות שהקואורדינטות שלהן ו- הן אלמנטים בשדה הבינארי המורחב אשר מקיימות את משוואת העקום, יחד עם הנקודה באין סוף .
יחד עם פעולות החיבור והכפל מתקבלת חבורה ציקלית סופית מסדר בקירוב.
כללי החיבור והכפל בעקום אליפטי מעל שדה בינארי מורחב שונות במעט: לחיבור הנקודות ו- כאשר מבצעים:
כפל נקודה כאשר מתבצע על ידי:
למטרות הצפנה, מקובל לבחור ראשוני גדול, משום שאז אין לשדה תת שדות.
את גודלו של יש לבחור בהתאם לדרישות האבטחה מחד, ולביצועים הרצויים מאידך.
לשדות בינאריים יתרון ברור כשמדובר בחומרה ותוכנה, משום שפעולת החיבור בשדה מבוצעת על ידי פעולת ה-XOR, שהיא פעולה יסודית ומהירה במחשב.
נתון השדה הבינארי בן 16 איברים, הניתן להצגה כהרחבה של השדה בן שני האיברים , כחוג המנה .
באופן הזה, כל איבר בשדה הוא מהצורה כאשר , ובאופן חסכוני אפשר להציג איבר כזה כמחרוזת סיביות, .
החבורה הכפלית של השדה היא חבורה ציקלית, הנוצרת (למשל) על ידי החזקות של היוצר כדלהלן:
אם נבחר העקום האליפטי הבא:
חישוב , מתבצע לפי כללי האריתמטיקה דלעיל:
אפשר לראות שחיבור נקודות בעקום אליפטי דורש בנוסף לכפל וחיבור פעולת חישוב הופכי כפלי מודולרי: בהינתן לחשב את המקיים: .
בדרך כלל חישוב הופכי כפלי היא פעולה יקרה במונחי חישוב ומשתדלים להימנע ממנה כשאפשר.
קיימת דרך יישום ל-ECC הנקראת מערכת פרויקטיבית בשיטת מונטגומרי המאפשרת חיבור נקודות בלי השימוש בהיפוך.
בעקום מסוג מונטגומרי מהצורה הנקודה מיוצגת על ידי ללא הקואורדינטה שלצורך קריפטוגרפי אינה נחוצה.
כפל נקודות בשיטה זו שנקראת גם סולם מונטגומרי יכול להתבצע על ידי הנוסחאות הבאות:
יוצא שהכפל התבצע תוך 11 פעולות כפל באלמנטים מסדר ללא חילוק או חישוב הופכי כפלי כלל.
ניתן לייעל באופן משמעותי את פעולת הצמצום המודולרי הדרושה בכפל וחיבור בעקום אליפטי אם הראשוני הוא מספר מרסן (מספר מהצורה ) לדוגמה .
עקומים עם מספר ראשוני מסוג זה מומלצים על ידי NIST בליווי הסברים כיצד לבצע צמצום מודולרי יעיל במספרים אלו.
האלגוריתם היעיל ביותר הידוע כיום לפתרון בעיית לוגריתם בדיד בחבורות, תחשיב האינדקסים אינו ישים בעקומים אליפטיים כיוון שהוא מסתמך על מספרים חלקים ולא קיימת הגדרה מתמטית ברורה למספרים חלקים בעקום אליפטי.
אלגוריתם רו של פולרד ללוגריתמים נחשב לשיטה היעילה ביותר הקיימת כיום לפתרון בעיית ECDLP וסיבוכיותה היא בקירוב.
על כן אינה יעילה (גם בגרסה המקבילית שלה) כשמדובר בשדה מסדר גדול.
עבור ביטחון בסדר גודל של 128 סיביות מספיק שסדר העקום יהיה .
לשם המחשה, מערכת מפתח ציבורי דורשת מפתח בסדר גודל של כ-2048 סיביות כדי שתקרא בטוחה ברמה המקבילה ל-AES עם מפתח באורך 112 סיביות.
במערכת ECC מקבילה, מפתח בגודל 224 סיביות מספק בטיחות שקולה.
לפי המלצות NIST בתקן 800-131A (תחת הכותרת שינוי אלגוריתמים קריפטוגרפיים ואורך מפתחות) שפורסם ביולי 2018, עד דצמבר 2023 ההמלצה היא להשתמש עבור RSA במפתחות באורך 2048 לפחות, עבור DSA מפתחות באורך (2048,224), (2048,256) או (3072,256) ועבור ECC מפתח באורך 224 סיביות ומעלה.
לשם כך נדרשו 2600 יחידות מחשב שפעלו באופן מקבילי במשך 17 חודשים.
בנובמבר 2009 החלו קבוצת חוקרים בפרויקט לשבירת העקום ECC2K-130 מתוך רשימת האתגרים של חברת סרטיקום (שהפרס עליו היה 20,000$).
זהו עקום קובליץ מעל השדה הבינארי בגודל 130 סיביות והוא העקום הקטן ביותר שטרם פוצח מתוך רשימת האתגרים של סרטיקום.
ההערכה המקורית של חברת סרטיקום בשנת 1997 הייתה שייקח לפחות ימים לשבירתו ולכן בהגדרה נאמר שהוא בלתי שביר.
אולם המחקר האחרון מראה שבעקבות ההתקדמות הטכנולוגית הן ברמה חומרה והן ברמת תוכנה ההערכה הזו לא נכונה.
כיום ההערכה היא שהעקום ניתן לשבירה וזה רק עניין של זמן (מספר שנים) עד שהוא יפוצח.
ההבדל המהותי בין חישוב פעולת חיבור לבין פעולת כפל של נקודות בעקום אליפטי, מהווה נקודת תורפה שיש להימנע ממנה, כיוון שמערכת המיישמת את ECC עלולה להדליף מידע פנימי כתוצאה מהפרשי הזמן במהלך ביצוע פעולות כפל וחיבור.
התקפת ערוץ צדדי מנצלת מידע כזה.
אפשר לחלק התקפה זו לשני סוגים עיקריים, האחת נקראת Simple Power Analysis שבה מודדים את עצמת הצריכה של המעבד (CPU) במהלך ביצוע ECADD ו-ECDBL המתוארות לעיל בפרוצדורת כפל סקלרי.
בשל הבדלים אילו ניתן לחלץ מידע קריטי מהמערכת.
השנייה נקראת Differential Power Analysis, התקפה המבוססת על ניתוח סטטיסטי של מספר פעולות חישוב שבוצעו, כדי לחלץ מידע מהמערכת.
כאמור לעיל לאור יתרונותיה, מערכת ECC מתאימה במיוחד ליישום במתקנים ניידים על כן נגישות התוקף למערכת ויכולתו למדוד את משך זמן ביצוע פעולות החישוב של יחידת העיבוד הוא בגדר אפשרי.
הפתרון להתקפת SPA (הראשונה) הוא שינוי פרוצדורת הכפל באופן שלא תדליף מידע קריטי.
קיימות מספר שיטות יעילות לביצוע פעולה זו כגון: שיטת יעקובי (Jacobi) והסה (Hesse) המשתמשת באלגוריתם אחיד לחיבור וכפל סקלרי של נקודות.
באופן כזה הזמן הדרוש לביצוע פעולות אילו זהה ועל כן לא דולף מידע קריטי.
שיטה זו מתאימה לעקומים מיוחדים הנקראים "עקום קובליץ".
או כפל סקלרי בשיטת קורון עם חיבור מדומה (double-and-always-add), כפל סקלרי בשיטת חלון, כפל סקלרי בשיטת סולם מונטגומרי וכן שיטת מולר (Möller) העושה שימוש ב-Addition chain.
כנגד התקפת DPA, הוספת אקראיות כמו אקראיות פרויקטיבית עם שלם אקראי כלשהו מספקת.
מאחר שמפתח למעשה מייצג נקודה בעקום, גודלו הוא למעשה שתי הקואורדינטות ו-.
אולם ניתן להפחית בגודל המפתח על ידי דחיסת הקואורדינטה כך שנדרשת רק סיבית אחת (המייצגת האם המספר חיובי או שלילי) לייצגה באופן שאפשר יהיה לשחזרה לאחר מכן.
כך שאפקטיבית גודל המפתח הוא בערך כגודל הקואורדינטה .
היות שהקואורדינטות הם בערך כגודל הסדר של השדה (מספר האלמנטים) הרי שחוסן אלגוריתם ההצפנה תלוי למעשה בסדר.
על בסיס בעיית לוגריתם בדיד בעקום אליפטי (ECDLP) המתוארת לעיל, ניתן ליישם את פרוטוקול דיפי-הלמן (ECDH), חתימה דיגיטלית DSA מעל עקום אליפטי (ECDSA), אל-גמאל וכן פרימיטיבים קריפטוגרפיים אסימטריים אחרים כמו מחולל פסאודו אקראי.
NSA הכריזה על חבילה קריפטוגרפית Suit B המנצלת הצפנת עקום אליפטי (ECC) כדור חדש של הצפנה.
היא אמורה להחליף את הטכנולוגיה האסימטרית כ-RSA ודומיה להגנה על סודות לאומיים מסווגים ולא מסווגים של ממשלת ארצות הברית.
כמו כן קיימת מערכת ECC המבוססת על תבנית ביליניארית (הנקראת גם Weil pairing) המשמשת למערכת אימות זהויות מבוססת ID (שבה זהות המשתמש מהווה חלק מהמפתח הפומבי) כמו כן חברת Certicom הקנדית משווקת מגוון גדול של מערכות אבטחה המבוססות על עקום אליפטי.
מסיבות של יעילות ביישומים מעשיים בדרך כלל מיישמים את ECC מעל שדה עם נקודה קבועה בעלת תכונות מסוימות שמאפשרות חישוב כפל סקלארי במהירות וביעילות.
מציאת הסדר של עקום אליפטי (קרי, מספר הנקודות) אינו דבר קל, קיימים אלגוריתמים לשם כך (כמו אלגוריתם שוף).
כיוון שסדר החבורה חיוני בפרוטוקולים קריפטוגרפיים נהוג לבנות עקום אליפטי באופן כזה שהסדר קל לחישוב.
למעשה התקנים למערכות ECC מגדירים פרוצדורות שונות להכנת עקום אליפטי בטוח העונה על הדרישות הרצויות וכן מכילים אוסף עקומים אליפטיים מומלצים לצורך ECC.
היות שמלאכת הכנת עקום אליפטי לצורך קריפטוגרפי קשה ומסובכת, קיימים מספר תקנים בינלאומיים ראויים לציון, המכסים עקומים אליפטיים קבועים שהוכנו במיוחד על ידי מומחים לשימוש כללי כחלק ממערכת הצפנת ECC תוך התחשבות ברמת הביטחון הנדרשת ויעילותה.
דוגמה לעקום אליפטי שאינו מומלץ כיום לשימוש הוא P-192 שנכלל בתקן FIPS 186-2 וכן ב-SEC v2 ומובא כאן להמחשה בלבד:
משוואת העקום היא מעל השדה כאשר הוא ראשוני באורך 192 סיביות.
סדר העקום הוא והפרמטרים הם לפי הסדר:
שם פרמטר ערך תיאור המספר הראשוני של השדה מקדם ראשון של משוואת העקום מקדם שני של משוואת העקום נקודת הבסיס בפורמט דחוס קואורדינטה של נקודת הבסיס קואורדינטה של נקודת הבסיס הסדר של העקום פקטור משלים
בשל העובדה שחלק ממערכות ECC מוגנות בפטנטים הפצתן והטמעתן התעכבה.
חברת Certicom מחזיקה בכמאה וחמישים פטנטים הקשורים בהיבטים שונים של ECC.
חברת אפל מחזיקה בפטנטים על יישום יעיל של ECC מעל השדה כאשר קרוב לחזקה של 2. ה-NSA רכשו זכויות שימוש במערכות ECC של חברת Certicom הקנדית והוסמכו לתת רישיון לכל גוף המעוניין לשלב ECC באפליקציות אבטחה בהן נעשה שימוש עבור ממשלת ארצות הברית.
בעקבות החשיפות בפרשת סנודן, עלה חשש בציבור שחלק מתקני עקום אליפטי במיוחד אילו של NIST מכילים דלתות סתר שמאפשרות למי שיודע אותם לפרוץ את המערכת בקלות אם כי לא קיימות הוכחות ברורות לכך מלבד מקרה אחד.
בעקבות הדלפות סנודן, פורסם בספטמבר 2013 בניו יורק טיימס שכחלק מפרויקט סודי של ה-NSA הנקרא "Bullrun" שמטרתו החדרת נקודות תורפה נסתרות בתקני הצפנה החדיר ה-NSA "דלת אחורית" במחולל הפסאודו אקראי Dual_EC_DRBG שהפך לתקן ובעקבות הפרסומים החליט NIST להפסיק לתמוך באלגוריתם והסיר אותו מהתקן.
כיום NIST מנהל מדיניות פתוחה ומשתף פעולה באופן נרחב עם הקהילה האקדמית ועם גורמי תקינה בינלאומיים.
כל אחד מהתקנים המתוארים מנסה להבטיח שבעיית הלוגריתם הבדיד בעקום אליפטי תהיה קשה ככל האפשר בעקום שהוא תומך בו.
הבעיה היא שקיים פער בין קושיה המשוער של בעיית דיפי הלמן בעקום אליפטי לבין הביטחון של מערכת ה-ECC בפועל.
כלומר, במציאות קורה לא אחת שקל לפצח את המערכת מבלי לפתור את בעיית דיפי הלמן או בעיית הלוגריתם הבדיד.
הסיבה העיקרית היא שיש סיכויים טובים שמי שמימש את העקום בתוך מערכת ההצפנה עשה זאת בצורה שגויה.
בגלל שיישומו בפועל עלול להדליף שלא במודע מידע קריטי, אם בשל יישום לקוי, טיפול לא נכון במקרי קצה ומצבי שגיאה או בגלל מידע תזמון שדולף מהמעבד או זיכרון המטמון בזמן ביצוע החישובים האריתמטיים.
מימוש בטוח של הצפנת עקום אליפטי אפילו אם הוא תואם את התקן, מתגלה כמשימה קשה מאוד.
יתרה מזו, כל התקנים שואפים להבטיח יעילות גבוהה ככל האפשר בנוסף לביטחון.
עובדה זו מטילה מגבלות נוספות על אופן המימוש שלו.
מחקרים מראים שבמקרים אחדים לא רק שהעקום לא היה יעיל, אלא שכל המגבלות והאופטימיזציות שנוספו רק השפיעו לרעה על יעילות העקום ובעיקר על ביטחונו.
ב-2007 גילה המתמטיקאי הרולד אדוארד משפחה חדשה של עקומים אליפטיים מהצורה .
מאוחר יותר פרסמו דניאל ברנשטיין וטניה לאנג שאפשר לנצל את עקומי אדוארד ווריאציות מפותלות שלהם לצורך קריפטוגרפי.
האטרקטיביות של עקומים אילו היא בעובדה שחיבור נקודות בהם קל יותר.
עקומי אדוארד נוטים להיות קלים יותר למימוש באופן בטוח בגלל שהם תומכים בנוסחאות חיבור שלמות שאינן כוללות מקרים חריגים שעלולים להוביל לחילוק באפס.
מה שמאפשר מימוש בטוח באופן כזה שאינו מדליף מידע צדדי.
כמו כן עקומים אילו מהירים ופשוטים יחסית.
לכל עקומי אדוארד והגרסאות המפותלות שלהם יש פקטור משלים המתחלק בארבע, מסיבה זו עקומי NIST מסדר ראשוני אינם ניתנים לייצוג בצורה זו.
מאז נוספו מספר עקומים חדשים המבוססים על עקומי אדוארד וכן עקומי מונטגומרי שהמכנה המשותף שלהם הוא ביטחון ויעילות גבוהים לפי סטנדרטים מחמירים ביותר.
בטבלה הבאה נכללו מספר עקומים אליפטיים חדשים שאינם מוגנים בפטנטים ושעוצבו לאחר 2007 כאשר רמת הביטחון שלהם נמדדת לפי המודולוס הראשוני , ליתר דיוק בפקטור שהוא מחצית מאורכו בסיביות.
למשל אם סיביות ביטחון העקום הוא בקירוב, שזה מקביל לביטחון של צופן AES עם מפתח באורך 128 סיביות.
סכימת בלום-גולדווסר (Blum-Goldwasser) היא סכימת הצפנה אסימטרית הסתברותית שהוצעה על ידי מנואל בלום ושפי גולדווסר ב-1984. היא יעילה מבין סכימות ההצפנה ההסתברויות הידועות ויעילה יותר בהשוואה ל-RSA מהיבט של מהירות והתנפחות הצופן וכן נחשבת לבטוחה סמנטית בהנחה שבעיית פירוק לגורמים קשה.
סכימת בלום גולדווסר מנצלת את רעיון המחולל הפסאודו אקראי Blum-Blum-Shub (בקיצור BBS), כדי ליצור רצף סיביות פסאודו אקראי, המשמש לאחר מכן לחיבור ב-XOR עם המסר בדומה לפנקס חד פעמי.
התוצאה ביחד עם הגרעין ההתחלתי כשהוא מוצפן מועברים למקבל שמשתמש במידע הסודי המצוי ברשותו הנקרא דלת צונחת (Trapdoor), כדי לחלץ את הגרעין ההתחלתי שהוזן למחולל ומשם הדרך לשחזור המסר קלה.
אפשר לראות בשיטה זו מעין שילוב של צופן זרם עם מפתח פומבי.
בדומה להצפנת רבין, הצפנת בלום-גולדווסר פגיעה להתקפת טקסט מוצפן נבחר.
אלגוריתם הכנת מפתח עבור הצפנת בלום-גולדווסר
בוחרים שני שלמים ראשוניים גדולים ו- השקולים ל- מודולו .
בעזרת אלגוריתם אוקלידס המורחב מוצאים שלמים ו- המקיימים את .
המפתח הפומבי הוא והמפתח הפרטי הוא .
להצפנת המסר המצפין משיג לידיו עותק של המפתח הפומבי ופועל כדלהלן:
מחלק את המסר ל- לבלוקים, כל אחד בגודל סיביות, כאשר (הלוגריתם בבסיס 2 של מספר סיביות המודולוס בקירוב).
בוחר גרעין אקראי סודי , שהוא שארית ריבועית מודולו (אפשר להשיג זאת על ידי בחירת שלם אקראי וחישוב ).
ההצפנה מבוצעת באופן רקורסיבי ב- סבבים כאשר בכל סבב: א.
הוא מחשב את , ב.
מצפין את בלוק המסר כדלהלן: , כאשר ערכו של הוא הסיביות הנמוכות של .
המקבל משתמש במפתח הפרטי שבידיו כדי לחשב את
ואז מחלץ את הגרעין ההתחלתי .
הוא מפענח את המסר באותה הדרך בה הוצפן, עבור כל בלוק מוצפן מחשב את ואז משתמש ב- הסיביות הנמוכות כדי לחבר ב-XOR עם בלוק הטקסט המוצפן: כדי לקבל את .
ראשית ממשפט השאריות הסיני נובע, היות ש- הוא שארית ריבועית מודולו , הוא שארית ריבועית מודולו הגורמים הראשוניים של .
ולפי תכונות סימן לז'נדר .
לכן אם מחשבים את מתקבל הגרעין ההתחלתי .
אם הגרעין ההתחלתי ידוע הפענוח טריוויאלי, כיוון שכל מה שנדרש הוא פעולת XOR חוזרת על הטקסט המוצפן בדיוק כפי שנעשה עם המקור.
לצורך הכנת מפתחות המקבל בוחר ראשוניים מתאימים נניח ו- ומחשב את ואז מחשב את משוואת אוקלידס כך ש-.
המפתח הפומבי הוא אם כן והמפתח הפרטי הוא .
כעת אם השולח מעוניין להצפין את המסר (בייצוג הקסדצימלי, בסה"כ 24 סיביות).
הוא מחשב תחילה את ואז ואז מחלק את סיביות המסר לשישה בלוקים בני ארבע סיביות כל אחד ומתקבל:
כעת בוחר גרעין התחלתי אקראי, נניח (שהוא ).
הצפנת המסר מוצגת בטבלה הבאה, כאשר מייצג את ארבע הסיביות הנמוכות של , בכל שלב לאחר העלאת בריבוע מחשבים את :
לסיום מחשב גם את ואת הטקסט המוצפן הוא שולח למקבל.
כדי לפענח את הטקסט המוצפן המקבל מחשב תחילה את הערכים:
ואז משחזר את הגרעין ההתחלתי כך: .
בעזרת הגרעין ההתחלתי הוא משחזר את הרצף הפסאודו אקראי, בדיוק כפי שעשה זאת המצפין ומכאן שחזור המסר קל כיוון ש-
הצפנת בלום-גולדווסר ידועה כהצפנה אסימטרית בטוחה סמנטית בניגוד לשיטות אחרות כמו RSA ורבין.
ההגדרה של ביטחון סמנטי היא שכל מה שניתן ללמוד בזמן ריצה פולינומי מהתבוננות בטקסט המוצפן בהינתן טקסט המקור, ניתן ללמוד גם ללא הטקסט המוצפן.
במילים אחרות הסכימה תקרא בטוחה סמנטית אם אינה חושפת כל מידע ולו הקל ביותר אודות טקסט המקור שניתן לגלות בזמן פולינומי.
למעשה זוהי גרסה חלשה של סודיות מושלמת, לפי שאנון שיטת הצפנה תקרא מושלמת אם יריב פסיבי אפילו בעל עצמת חישוב בלתי מוגבלת, לא יוכל ללמוד מאומה אודות טקסט המקור בהינתן טקסט-מוצפן בלבד, כיוון שכל טקסט יכול להיות המקור במידה שווה.
אפשר להפוך כל שיטה דטרמיניסית לבטוחה סמנטית על ידי הוספת אקראיות למסר לפני תהליך ההצפנה.
מספר בלום; המודולוס ייקרא מספר בלום אם הוא שלם פריק שהוא כפולה של שני ראשוניים שונים השקולים ל-3 מודולו 4. כלומר אם קיים שלם כלשהו המקיים .
אלגוריתם בלום גולדווסר מיישם גרסה מובנית של המחולל הפסאודו האקראי BBS כאשר הסיביות הנמוכות של השארית הריבועית בכל סבב, משלימות את הרצף הפסאודו אקראי לצורך הצפנת המסר.
השארית הריבועית האחרונה נשלחת באופן גלוי כאמור אל המקבל לצורך שחזור הגרעין ההתחלתי.
בהנחה שפירוק לגורמים היא בעיה קשה, ניתן להוכיח כי הסיביות הנמוכות של בטוחות סימולטנית, כלומר אין דרך יעילה לחשב אותם מלבד ניחוש, מה שאומר שהמחולל נחשב לבטוח (כל עוד פירוק לגורמים היא בעיה קשה).
כמובן הגדרה זו מוגבלת לביטחון חישובי בלבד.
בדומה לשיטת רבין, הצפנת בלום גולדווסר פגיעה להתקפת מוצפן-נבחר שבה תוקף מנסה לגלות את הגורמים הראשוניים של המודולוס ועל כן לגלות את המפתח הפרטי מתוך המפתח הפומבי.
במודל זה ההנחה היא שלתוקף גישה למערכת המבצעת הצפנה ופענוח כקופסה שחורה, אין לו גישה למפתח הסודי עצמו אך באפשרותו לבחור מסרים אותם הוא מעוניין שהמערכת תפענח עבורו ולנתח את התוצאה.
סיטואציה כזו אינה בלתי אפשרית במערכות מסוימות ולכן מהווה איום בלתי מבוטל.
הצפנת בלום גולדווסר יעילה מבחינה חישובית כיוון שהטקסט המוצפן המתקבל אינו גדול משמעותית מטקסט המקור, אלא במספר קבוע של סיביות (כגודל השלם בסיביות).
תהליך ההצפנה יעיל ודורש רק הכפלה מודולרית (מודולו ) אחת כדי להצפין סיביות, כלומר עבור מודולוס בגודל סיביות ומסר בגודל סיביות תהליך ההצפנה לוקח פעולות בסיסיות.
לעומת RSA למשל שדורשת העלאה בחזקה מודולרית מלאה במידה והמעריך נבחר אקראית.
ללא אופטימיזציה העלאה בחזקה מודולרית מלאה דורשת בממוצע פעולות כפל מודולריות כאשר שווה ללוגריתם בבסיס 2 של המודולוס.
כמו כן תהליך הפענוח של אלגוריתם בלום גולדווסר דורש (בנוסף בשלב ההכנה) רק שלוש העלאות בחזקה מודולריות ללא תלות באורך המסר, יתר הפעולות דומות להצפנה, כלומר בסה"כ .
מה שאומר שעבור מסרים גדולים, שיטת בלום גולדווסר יעילה יותר מ-RSA.
בתקשורת נתונים, הצפת SYN היא סוג של התקפת מניעת שירות המנצלת פרצת אבטחה במנגנון הקמת הקשר של ה-TCP.
במסגרת ההתקפה התוקף שולח רצף של חבילות SYN למחשב המותקף ובכך מאלץ אותו לפתוח במקביל חיבורים רבים עד שלא נותרים לו משאבים לקבלת חיבורים חדשים.
בכך התוקף מונע מהמחשב המותקף להעניק שירות למשתמשים אחרים ומשיג את מבוקשו.
הצפת SYN היא התקפה מוכרת ביותר, ולרוב אינה אפקטיבית נגד שרתים ורכיבי רשת מודרניים, שכן אמצעי התמודדות רבים כבר שולבו באלו על מנת שיוכלו להתמודד איתה.
על פי מנגנון הקמת הקשר של ה-TCP, כל לקוח הפונה לשרת מתחיל בחבילה המכילה את הדגל SYN דלוק.
השרת עונה ללקוח בחבילה המכילה את הדגלים SYN ו-ACK, וממתין לאישור של הלקוח באמצעות חבילת ACK נוספת.
טרם השלמת השליחה והקבלה של שלוש החבילות האלו לא ניתן להתחיל להעביר מידע על גבי הקשר.
הצפת SYN מנצלת למעשה את ההמתנה שהשרת מחויב לה עד לקבלת האישור מהלקוח.
באמצעות שליחת חבילות SYN רבות, התוקף מאלץ את השרת להשאיר קשרים רבים פתוחים (קשר חצי-פתוח, ליתר דיוק), אף על פי שאף אחד מהם לא שמיש להעברת מידע.
בשל מגבלת משאבים על השרת, לאחר פתיחת קשרים רבים בו-זמנית, השרת מאבד מיכולתו להעניק שירות למשתמשים הלגיטימיים.
בכך התוקף משיג את מבוקשו.
כדי שכתובת ה-IP של התוקף לא תיחשף וכדי שלא ניתן יהיה לחסום את כתובת ה-IP הספציפית שלו ובכך לחסום את ההתקפה, התוקפים משתמשים על פי רוב בהונאת IP ובכך לא מאפשרים הבחנה בין החבילות התמימות לבין החבילות התוקפות.
בשל המראה התמים של חבילות ה-SYN, פעמים רבות הן אינן נחסמות בדרך לשרת.
עובדה זו מאפשרת לתוקפים להשתמש בהצפת SYN כאמצעי פשוט ליצירת עומס תעבורה על השרת ובכך לחסום את רוחב הפס העומד לרשות שאר המשתמשים, גם במידה והשרת לא קורס תחת עומס הקשרים החצי פתוחים.
ניתן לחשב חסמים תאורטיים לקצב שבו תוקף יכול לשלוח חבילות SYN לפי סוג החיבור של המחשב התוקף:
סוג החיבור קצב מקסימלי (חבילות SYN לשנייה) מודם אנלוגי 87 ISDN, DSL 200 T1 2,343
כאשר התוקף משתמש במחשבי זומבי לצורך התקיפה, כלומר מבצע הצפת SYN מבוזרת, יש לסכום את הערך הנ"ל עבור כל אחד מהמחשבים התוקפים.
ב-5 בפברואר 2000 החלה הצפת SYN רחבת היקף על אתרי אינטרנט רבים שכללו בין היתר את CNN, eBay, יאהו ואמזון התקיפה נמשכה עד 11 בפברואר.
שנה לאחר מכן, בין 4 במאי ל-20 במאי 2001, חברת Gibson Research הותקפה מ-474 מחשבים שונים ברשת באמצעות הצפת SYN.
ההתקפה הרוותה לחלוטין שני חיבורי T1 שהיו באחזקת החברה.
ילד בן 13 לקח אחריות על ההתקפה.
קיימות דרכי התמודדות רבות עם התקפות אלו.
חלק מהדרכים מאפשרות התמודדות עצמאית על ידי השרת: דרך אחת היא פשוט להגדיל את הקיבולת של הקשרים החצי פתוחים שבה השרת יכול לתמוך, ובכך להקשות על תוקף פוטנציאלי בכך שהוא צריך לשלוח יותר חבילות.
דרך אחרת היא לקצר את משך ההמתנה לחבילת האישור מהלקוח, ובכך להקשות על התוקף הפוטנציאלי שכן קצב שליחת החבילות שלו צריך לגדול.
פתרון נוסף הוא להגביל את מספר הקשרים החצי פתוחים ובכל פעם שהתור מגיע לשיא הקיבולת שלו - למחוק את הקשרים הישנים ביותר.
באופן דומה ניתן לבצע את כל הפתרונות הנ"ל על ידי הוספת שרתים נוספים ומעבר לעבודה באשכול מחשבים.
יחד עם זאת, ברוחב הפס שרוב השרתים והתוקפים יכולים היום להשיג, מגבלות אלו אינן מהוות מגבלה מהותית ולרוב יפגעו במשתמשים בעלי חיבור איטי יותר בין כה וכה בשל חוסר היכולת להבחין בזמנים קצרים בין לקוח איטי לבין קשר חצי פתוח.
לפיכך נדרשים פתרונות לוגיים מוצלחים יותר.
ניתן להשתמש גם בפתרונות חיצוניים לשרת, באמצעות מנגנון הנקרא SYN-פרוקסי (SYN Proxy).
בפתרון זה מציבים חומת אש לפני השרת, כזו בעלת קיבולת קשרים חצי פתוחים גדולה יותר, שתשמש כחוצץ בינו לבין התוקף.
חומת האש תענה על חבילות ה-SYN הנשלחות לשרת בהודעת SYN-ACK שהוא מרכיב בעצמו, ורק עם קבלת ה-ACK הסופי מהלקוח, כשחומת האש משתכנעת שמדובר בלקוח אמיתי, היא שולחת את החבילות לשרת ומאפשרת לו ליצור את החיבור עם הלקוח.
פתרון לוגי אחר הוא שימוש בעוגיית-SYN .
טכנולוגיה זו מאפשרת לשרת להימנע לחלוטין מהקצאת משאבים לקשרים חצי פתוחים על ידי הוספת נתונים לחבילת ה-SYN-ACK הנשלחת חזרה ללקוח באופן שמאפשר לשרת לחשב את המספר הסידורי שהוגרל לאחר קבלת ACK ובכך ליצור את הקשר באופן שקוף.
בקריפטוגרפיה, הצפנה הומומורפית (Homomorphic encryption) היא שיטת הצפנה המאפשרת לבצע חישוב על מסרים מוצפנים, כך שתוצאת החישוב על המסר המוצפן שקולה לתוצאה שהייתה מתקבלת מהצפנת הפלט של פעולת החישוב האמורה על המסר המקורי.
למשל הצפנה הומומורפית ביחס לפעולת החיבור היא הצפנה הומומורפית חלקית המאפשרת להצפין שני מספרים ואז לבצע על הצפנים חישוב שתוצאתו היא הצפנת סכומם של שני המספרים.
הצפנה הומומורפית מלאה היא הומומורפית ביחס לחיבור וכפל כאחד.
הצפנה הומומרפית מאפשרת לבצע חישוב באופן פומבי מבלי לחשוף את מרכיביו ואת תוצאתו.
מדובר בכלי חזק מאוד שאף כונה "הגביע הקדוש של הקריפטוגרפיה".
שימוש חשוב הוא כפתרון בעיות של ביטחון מידע במחשוב ענן, מפני שניתן לבצע פעולות חישוב בענן על מידע המוצפן הומומורפית בלי פיענוח שלו, תוך שמירה על סודיותו גם במקרה של פריצה למערכות הענן.
חברות ענק טכנולוגיות עוסקות בפיתוח הצפנה כזו לשימושים שונים, כגון פייסבוק שמפתחת מערכת לניתוח נתונים מוצפנים שתשמש להתאמת מודעות מדויקת יותר למשתמשים בוואטסאפ.
בהינתן סכמת הצפנה עם פונקציית הצפנה שמצפינה את המסר עם המפתח הפומבי ופונקציית פענוח המפענחת את המסר המוצפן עם המפתח הפרטי .
נסמן ב־ את מרחב ההודעות וב־ את מרחב ההודעות־המוצפנות של הסכמה.
סכמת הצפנה תיקרא הומומומורפית ביחס לפונקציה ב־ משתנים אם לסכמה קיימת פונקציית הערכה כך שלכל הצפנות של הודעות מתקיים כי מוציאה כפלט צופן c שהוא הצפנה של באמצעות .
ופירושו שניתן לבצע חישוב על המסר המוצפן ותוצאתו תהיה הצפנה של תוצאת החישוב על המסר טרם ההצפנה.
ברוב המקרים יש דרישה כחלק מההגדרה שהסכמה תהיה בטוחה סמנטית.
בשנת 1978, מעט לאחר פרסום הצופן RSA רון ריבסט, לאונרד אדלמן ודרטוזוס הגדירו את המושג לראשונה ודנו בחשיבות של הומומורפיזם בהצפנה.
ההומומורפיזם שדובר עליו במאמר הוא הומומורפיזם חלקי, הוא אפשרי אך ורק לפעולת הכפל.
אחת השאלות שעלו במאמר היא האם קיימת סכמת הצפנה שתהיה הומומורפית לכל פונקציה חשיבה.
צופן קיסר הוא הומומורפי (כצופן סימטרי) ביחס לפעולת השרשור: אפשר קודם לשרשר שתי מחרוזות ואז להסיט אותן או שאפשר להסיט כל אחת בנפרד ואז לשרשר.
המסר מוצפן עם המפתח כ- ולכן:
לצופן אל-גמאל תכונת הומומורפיות זהה.
הצפנת גולדווסר מיקאלי הומומורפית ביחס לחיבור.
הצפנה הומומורפית מלאה היא שיטת הצפנה שהומומרפית ביחס לכל פונקציה שניתנת לחישוב יעיל, זאת בניגוד להצפנה הומומורפית חלקית שהומומורפית רק עבור משפחה מצומצמת של פונקציות.
הצפנה כזו תהיה הומומורפית גם לחיבור וגם לכפל, וכך תהיה הומומורפית בהתאם למודל של מעגל אריתמטי, ובעצם תשמר מבנה של חוג (מבנה אלגברי).
במשך כשלושים שנה לאחר פרסום המאמר של ריבסט, אדלמן ודרטוזוס השאלה האם קיימת הצפנה הומומורפית מלאה הייתה פתוחה.
ההצפנה עם היכולת הקרובה ביותר שנמצאה הייתה סכמת הצפנה מ־2005 המסוגלת להעריך הומומורפית כל ביטוי מסוג 2-DNF, שהתפרסמה על ידי דן בונה, גו וניסים.
בשנת 2009 הוכיח קרייג ג'נטרי, דוקטורנט באוניברסיטת סטנפורד וחוקר בקבוצת ווטסון בחברת IBM, בעבודת הדוקטורט שלו שהצפנה כזו קיימת.
הסכמה היא הצפנה מבוססת סריגים ומתבססת על הנחות בנוגע לסריגים אידיאליים.
הבנייה התחלקה לשני שלבים עיקריים:
ראשית בנה ג'נטרי הצפנה הומומורפית מלאה לעומק קבוע (Levelled FHE), הצפנה שהומומורפית לכל פונקציה שניתנת לחישוב על ידי מעגל בעומק נתון מראש, במקרה הנוכחי - יכולת להעריך כל פולינום עד למעלה מסוימת.
ההגבלה על העומק נוצרה מכך שסכמת ההצפנה כללה החדרת רעש למסר המוצפן, כך שיכולת השחזור אפשרית רק לבעלי סוד מסוים שהוא המפתח הפרטי.
בסכמות כאלה הרעש גדל בסדר גודל מסוים בכל שלב במעגל ולכן פלט של מעגל בעומק גבוה מדי יהיה עם יותר מדי רעש ולא יהיה ניתן לשחזור.
לאחר בניית הסכמה הזו, הגדיר ג'נטרי והוכיח את תהליך ה־Bootstrapping.
פריצת הדרך של ג'נטרי נבעה מהתייחסותו אל תהליך הפענוח כאל עוד פונקציה שניתנת להערכה באופן הומומורפי על המסר המוצפן.
מכאן, מרגע שהמסר המוצפן מכיל כמות גבוהה של רעש, כל שיש לעשות הוא להריץ הומומורפית את סכמת הפענוח, בעזרת פרסום הצפנה של המפתח הפרטי, וכך לקבל הצפנה של המסר המוצפן המפוענח - נניח שלאחר מספר פעולות הומומורפיות התקבל המסר המוצפן שמכיל רעש רב.
אנחנו נרצה לקבל הצפנה חדשה של עם רעש חדש וקטן יחסית, את זאת נוכל לקבל על ידי הפעלת פונקציית הפענוח - .
בצורה פורמלית - סכמת הצפנה תיקרא ניתנת ל־Bootstrapping אם היא הומומורפית לכל מעגל בעומק לכל היותר D+1, כאשר D הוא עומק המעגל של פונקציית הפענוח של הסכמה.
כעת לאחר כל מספר פעולות הומומורפיות וכאשר הרעש גדל, מפעילים הומומורפית את פוקנציית הפענוח וממשיכים.
הבנייה של ג'נטרי ורעיון ה־Bootstrapping הביאו לפריחה בתחום.
בשנים שעברו מאז פרסום עבודתו פורסמו סכמות הצפנה רבות (כמו TFHE, CKKS, BGV, ואחרים) המבוססות על רעיונות דומים שמנסות להתגבר על חלק מהחסרונות בבנייתו.
כיום רוב הסכמות מתבססות על הנחת הקושי הנובעת מ־Learning With Errors של עודד רגב, שהיא הנחת קושי מקובלת יותר בניגוד להתבססות על סריגים אידיאליים.
בנוסף, הסכמות היום יעילות יותר, אך עדיין לא יעילות מספיק לשימוש המוני.
סיפור הצפרדע המתבשלת הוא משל המתאר צפרדע שמתבשלת לאט במים המחוממים באופן הדרגתי.
המשל מספר שכאשר צפרדע תוכנס למים רותחים, היא תנסה לקפוץ החוצה ולהימלט.
אבל אם תוכנס הצפרדע למים קרירים שיחוממו באופן הדרגתי, היא לא תבחין בסכנה, היא תתרגל לעלייה האיטית בטמפרטורה ולא תנסה להימלט, ובסופו של דבר תתבשל ותמות.
הסיפור משמש בדרך כלל כמטפורה לחוסר הרצון או היכולת של בני אדם להגיב לשינויים משמעותיים אשר קורים באופן הדרגתי.
אף על פי שסיפור הצפרדע הוא סיפור מפורסם, הוא חסר ביסוס מדעי ומהווה אגדה אורבנית.
בתרבות המודרנית משתמשים בסיפור הצפרדע המתבשלת בעיקר כמטפורה לתיאור חוסר תשומת לבם של אנשים לשינויים משמעותיים הקורים באופן הדרגתי, אשר בסופו של דבר עלולים להשפיע על חייהם בצורה לא רצויה.
המטפורה ניתנת בדרך כלל במקביל לטיעון המדרון החלקלק.
כמו כן נעשה בה שימוש בעולם העסקים, על מנת להדגיש כי על שינוי להיעשות באופן הדרגתי כדי שיקבלו אותו.
הסיפור סופר פעמים רבות כדי לתאר מצבים שונים.
ב-1960 נעשה בו שימוש בהקשר לסימפתיה כלפי ברית המועצות במהלך המלחמה הקרה.
ב-1980 שרדנים השתמשו בו בהקשר לנפילת הציוויליזציה בעתיד, ובמהלך שנות ה-90 בקשר לחוסר הפעולה בנוגע לשינוי אקלים ואלימות במשפחה.
בנוסף השתמשו בו ליברטריאנים כדי להזהיר אחרים מפני היעלמותן ההדרגתית של זכויות האזרח.
בנוסף, מהווה הסיפור כמטפורה לאירועים שהובילו לשואת היהודים במהלך מלחמת העולם השנייה, כאשר הגרמנים (ואף היהודים) הורגלו ואימצו אט אט טיעונים קלים ומאוחר יותר טיעונים חמורים יותר נגד היהודים.
באופן זה, מאוחר יותר, כל טיעון נגד היהודים, אף המופרך ביותר, נשמע היה כאמת.
כך, נקודת הרתיחה, שלב רציחת היהודים, הגיעה בעת בה האנשים כבר לא יכולו להבחין בה, והם קיבלו את המצב כמצב טבעי.
הצפנה ככלי לקידוד והסתרת מידע הייתה קיימת משחר ההיסטוריה.
בראשית דרכה הייתה ההצפנה בעיקר אמנות לקסיקוגרפית שנעשתה בשיטות פרימיטיביות ידניות.
שיטות ההצפנה בהן עסקו בעת העתיקה, עד תחילת המאה העשרים, נקראות הצפנה קלאסית במובן זה שהן נעשו בשיטת 'נייר ועט' או באמצעים מכניים בסיסיים כמו גליל הצפנה או בשיטות סטגנוגרפיות.
זאת בניגוד לקריפטוגרפיה מודרנית שנעשית באמצעות מחשב.
ממצאים המעידים כי המצרים הקדמונים השתמשו בהצפנה בכתב חרטומים, לערך 3000 שנה לפנה"ס.
בתנ"ך ובמקורות יהודיים נוספים קיימות עדויות נוספות להצפנה.
לדוגמה, בספר ירמיהו (נכתב בשלהי תקופת בית ראשון, לפני שנת 586 לפנה"ס) נכתב , .
"ששך" היא "בבל" ו"לב קמי" היא "כשדים" בצופן אתב"ש.
השימוש בהצפנה התרחב בתקופת יוון העתיקה.
צבא ספרטה השתמש צופן הזזה פשוט.
בצופן זה, כל אות משנה את מיקומה לפי חוק מסוים.
צפנים אלו מומשו בין היתר בעזרת גליל הצפנה.
יוליוס קיסר (102 עד 40 לפנה"ס) נהג להשתמש בשיטת הצפנה שנקראת צופן החלפה, בה כל אות נשארת במקומה אך מוחלפת באות שונה לפי חוקיות מסוימת.
הצופן בו השתמש יוליוס קיסר נודע לימים כצופן קיסר.
כמו כן נעשה בתקופה זו שימוש רב בשיטות סטגנוגרפיות, כגון קעקוע המסר על ראשו המגולח של חייל ושליחתו ליעד לאחר שצמחו שערותיו, או כתיבת המסר על לוחות עץ וציפויים בשעווה לאחר מכן.
בימי הביניים ובעת החדשה נעשה שימוש רב בהצפנה מסוגים שונים.
צופן הזזה ב"שיטת הרשת" שימש את האפיפיור.
אנגרמות שימשו מדענים כגון גלילאו גלילי (המאה ה-16) להחבאת סודות או על מנת להוכיח זכות ראשונים על גילויים מדעיים.
מרי, מלכת הסקוטים (המאה ה-16) התכתבה עם קבוצת אצילים קתוליים שרצו להדיח את המלכה אליזבת הראשונה מהכתר, באמצעות צופן החלפה.
שבירת צופן זה על ידי שרות הריגול של המלכה אליזבת עלתה למלכה מרי בחייה.
במהלך המאה ה-9 פותחה על ידי איש האשכולות העיראקי אל-כנדי (801 - 873) שיטת פיצוח צפנים המבוססת על ניתוח תדירויות.
ככל הנראה, ניתוח התדירויות החל בעקבות בחינה של כתבי הקוראן וניסיון לנתח אותם.
שיטה זו הייתה שימושית לפיצוח צפנים עד שלהי המאה ה-20 ופיתוח ההצפנה המודרנית.
אל-כנדי פרט את ממצאיו בספר שהכיל, בין היתר, מספר שיטות לפיצוח צפנים (חלקן עבור צפנים פוליאלפביתיים), סיווג צפנים שונים, וניתוח תדירויות אותיות בשפה הערבית.
הסופר והמתמטיקאי המצרי אל-קאלקשנדי (1355 - 1418) כתב אנציקלופדיה שהכילה פרק בנושא קריפטוגרפיה.
כתבים אלו הכילו צפני הזזה והחלפה פשוטים, וכן צפני החלפה בהם כל אות מוחלפת באות אחרת מתוך מבחר של מספר אותיות שונות.
כמו כן מתוארים שיטות קריפטואנליטיות מבוססות ניתוח תדירויות של אותיות, וצירופי אותיות שלא יופיעו זו אחר זו בטקסט.
ייתכן שכתבים אלו מקורם בעבודתו של טאג' א-דין עלי (1312 - 1361).
מחוץ לאירופה ולעולם המוסלמי, תחום הקריפטוגרפיה לא התפתח רבות.
לדוגמה, קריפטוגרפיה ביפן החלה להתפתח ככל הנראה רק בשנת 1510.
קריפטוגרפיה עד אמצע המאה ה-20
בשנת 1854 המציא המדען הבריטי צ'ארלס ויטסטון שיטת הצפנה חדשה אשר נודעה לימים כצופן פלייפייר.
בשיטה זו התבצעה ההצפנה לראשונה על קבוצת אותיות ולא על כל אות בנפרד.
בצופן פלייפייר ההצפנה מבוצעת על זוגות של אותיות (דיגרפים).
עובדה זו מקשה את שבירת הצופן בטכניקה של ניתוח תדירויות, כיוון שכעת יש לנתח תדירויות של כ-600 דיגרפים (צירופי אותיות) שונים, לעומת כמות של כ-26 אותיות.
הרחבה של רעיון זה הובילה למושג צופן בלוקים הנפוץ בקריפטולוגיה המודרנית.
עם התפתחות הטכנולוגיה גבר גם השימוש בהצפנה ובפרט הצפנה ממוכנת .
הקריפטוגרפיה הפכה כלי בסיסי להצפנת ידיעות צבאיות טרם שליחתן בטלגרף או ברדיו.
במקביל גורמי מודיעין רבים עסקו בניסיונות פיצוח צפנים של צבאות אויב.
בשנת 1917 הגה המהנדס גילברט סטנפורד ורנם (1890 - 1960) שיטה ממוכנת לביצוע הצפנה בטלגרף, בה המידע מוצפן תו אחר תו בעת שידורו, בניגוד לביצוע ההצפנה מראש ולאחר מכן שידור הטקסט המוצפן.
בשיטה זו המפתח מוכן מראש על גבי סרט מנוקב ומחובר על ידי ממסר חשמלי אל מכונת הטלגרף.
שיטת הצפנה זו ידועה בשם צופן ורנם, על שם ממציאה, והיוותה את הבסיס להצפנת פנקס חד-פעמי הבלתי-שבירה.
בתקופה זו הקריפטוגרפיה עדיין לא הייתה מפותחת דיה, והייתה קלה יחסית לשבירה.
במקביל, התפתחות הטכנולוגיה הובילה להעברת מסרים רבים בקשר רדיו, שהוצפנו בצורה חלשה יחסית והיו מועדים לשבירה על ידי גורמי המודיעין של מדינות מפותחות כגון הממלכה המאוחדת, יפן וארצות הברית.
פער זה הוביל למספר אירועים ידועים שגרמו לשינויים מהותיים בקבלת ההחלטות במדינות העולם:
מברק צימרמן: מברק מוצפן שנשלח במהלך מלחמת העולם הראשונה (16 בינואר 1917) על ידי שר החוץ של גרמניה, ארתור צימרמן, לשגריר גרמניה בארצות הברית, ומטרתו ליזום ברית בין גרמניה למקסיקו כנגד מדינות ההסכמה.
המברק הוצפן באמצעות ספר צופן שנפל בידי המודיעין הבריטי.
פענוח המברק היה בין הגורמים להצטרפות ארצות הברית ללחימה לצד מדינות ההסכמה.
פרויקט ונונה (מסמכי וינונה): פרויקט ביון משותף לארצות הברית ולאנגליה, לפענוח מסמכים מוצפנים של ברית המועצות שיורטו במהלך מלחמת העולם השנייה, ופוענחו במשך 40 השנים הבאות.
מסמכים אלו היוו מקור מידע חשוב עבור הביון של הגוש המערבי במהלך המלחמה הקרה.
פיצוח הצופן נבע מטעות שימוש בצד הסובייטי: הצופן בו נעשה שימוש היה מסוג פנקס חד-פעמי, בו כל מפתח משמש פעם יחידה בלבד.
ככל הנראה, עקב רצון לחסוך בכמות המפתחות, או עקב הזמן הארוך הנדרש לייצור מפתחות, נעשה שימוש חוזר בחלק מהפנקס החד-פעמי, דבר שהוביל לפענוח חלקי של המסמכים.
כ-3,000 מסמכים שיורטו בין השנים 1942 - 1945 פוענחו באופן חלקי או מלא על ידי כוחות הברית, והחל מ-1948 כלל התשדורות שיורטו הפכו בלתי פציחות.
שפת הנאוואחו: השפה המדוברת על ידי אינדיאנים בני שבט הנאוואחו.
ניתן לראות בה צופן פשוט הידוע רק לדוברי השפה וזאת מכמה סיבות:
בשל מיעוטם היחסי של דוברי השפה והעובדה כי איש מדובריה לא גר בתקופה ההיא בארץ אויב.
עקב השונות הגבוהה (יחסית) של שפה זו משפות מודרניות אחרות ושפות נחקרות אחרות, העובדה ששום מוסד לא לימד שפה זו, העובדה שהקלטות של השפה היו נדירות ביותר והעובדה שהיא שפה מדוברת בלבד ולא כתובה, קיים קושי רב ב"פיצוח" השפה על ידי בלשנים.
במהלך מלחמת העולם השנייה עשתה ארצות הברית שימוש באלחוטנים בני שבט הנאוואחו להעברת מסרים ברשתות הרדיו, שימוש שהחל עוד בשלהי מלחמת העולם הראשונה לאחר ההבנה שגרמניה בעלת יכולת יירוט של כלל התקשורת הצבאית של ארצות הברית.
צופן זה אינו נחשב חזק במיוחד, שכן על מנת לפענחו המודיעין הנגדי צריך להשיג מרגל בן שבט הנאוואחו.
אניגמה: מכונת הצפנה מבוססת רוטור, ששימשה את גרמניה במהלך מלחמת העולם השנייה.
על מנת שלא לחשוף את העובדה שהמערכת נפרצה על ידי בעלות הברית, נעשה שימוש זהיר ביותר במודיעין שהופק מיירוט מסרים שהוצפנו באניגמה.
כמות המידע שהופק מהודעות אלו ואיכותו הובילו את צ'רצ'יל לומר "הודות לאולטרה (המודיעין שהופק מהאניגמה) ניצחנו במלחמה".
בעת העתיקה נעשה שימוש בשני צפנים קלאסיים עיקריים: צופן שחלוף (הזזה או העתקה) וצופן החלפה.
צופן הזזה (טרנספוזיציה או העתקה) הוא צופן בו כל אות משנה את מיקומה לפי חוקיות מסוימת.
צופן הזזה היה נפוץ בעת העתיקה כאנגרמה (שיכול אותיות).
אנגרמות מופיעות ביוון העתיקה וברומא העתיקה, וכן בתלמוד ובמדרשים.
כיום אנגרמות אינן נחשבות ככלי קריפטוגרפי, בשל העובדה שקל לפצחן, והן נחשבות כשעשוע-מוחי, ומופיעות בתשבצי היגיון.
צופן החלפה הוא שם כללי לצופן בו כל אות מוחלפת על ידי אות אחרת לפי חוקיות ידועה הנקראת מפתח.
צופני החלפה מתחלקים לשני סוגים עיקריים; צופן החלפה חד-אלפביתי שבו מוחלפת כל אות באות אחרת לפי היסט קבוע או צופן החלפה רב-אלפביתי שבו ההיסט משתנה מאות לאות בהתאם לקבוצת מפתחות או היסטים.
דוגמה ידועה לצופן החלפה חד-אלפביתי היא צופן קיסר בו השתמש יוליוס קיסר.
בצופן זה כל אות מוחלפת באות הבאה אחריה באלפבית בהיסט מסוים וקבוע (באופן מעגלי).
לדוגמה, אם ההיסט הוא שלוש אותיות (גודל ההיסט בו השתמש יוליוס קיסר), המילה "קיסר" תוחלף במילה "תמצא".
בצופן זה, גודל ההיסט הוא המפתח לפענוח המסר.
צופן החלפה חד-אלפביתי קל לזיהוי ולשבירה כיוון שהוא משמר את תדירות האותיות שבמסר המקורי וקל לפצחו מכיוון שמספר ההיסטים האפשריים מוגבל מאוד.
צופן החלפה רב-אלפביתי מסתיר את תדירויות האותיות על ידי החלפה דינאמית בהתאם לסדרה של היסטים שונים, בהם משתמשים באופן מחזורי כדי להגדיר את ההמרה בין כל אות (או קבוצת אותיות) בטקסט הגלוי, לאות (או קבוצת אותיות) בטקסט המוצפן.
צופן ויז'נר וצופן ורנם הם דוגמאות טובות לצופן החלפה רב-אלפביתי וכן במידה מסוימת מכונת האנימה.
ישנן פעמים שקבוצת ההיסטים היא בעצם אוסף אותיות הנגזר מספר כלשהו לפי סדר הופעתן ואז יקרא הצופן ספר צופן, ויתרונו הוא שהוא מכיל כמות גדולה של מפתחות לשימוש, למשל דף מפתח ייעודי עבור כל יום בו עושים שימוש בצופן.
בדרך זו מטשטשים יותר את הזיקה בין הצופן לטקסט הגלוי, בהתאם לרמת אקראיותו של הטקסט המשמש כמפתח.
הצפנה קלאסית במאה ה-20: מכונות הצפנה מבוססות רוטור
בראשית המאה ה-20, עם התפתחות הטכנולוגיה, בעיקר המצאת הרדיו והטלפון, גבר הצורך באמצעי אבטחה קריפטוגרפיים ממוכנים, עקב קלות היירוט של שדר אלחוטי.
אז החלו להופיע לראשונה מכונות הצפנה מבוססות רוטור.
מקור הרעיון החל בגליל ג'פרסון על שם ממציאו תומאס ג'פרסון, לימים נשיאה השלישי של ארצות הברית.
זהו צופן החלפה רב-אלפביתי הבנוי מציר מרכזי עליו מורכבים מספר גלילים שהיקפם מחולק ל-26 מקטעים, בהם מוטבעות האותיות A עד Z לא בסדר אלפביתי אלא בסדר אקראי כלשהו, כל גליל בסדר אלפביתי אחר.
הגלילים המסוגלים לנוע בחופשיות ללא תלות זה בזה והמנגנון כולו יכול לשמש כחלק ממכונת כתיבה שמדפיסה את הצופן על פי סדר האותיות שהוטבע בגלילים.
לאחר מכן החלו להופיע מכונות הצפנה מורכבות יותר בהן הורכבו גלילים בהיקפים שונים ובסדר שונה ונוספו מנגנונים אלקטרוניים שונים, כדי להתאימם לתקשורת אלחוטית.
הדוגמה הקלאסית היא מכונת אניגמה הגרמנית ששימשה את הנאצים במלחמת העולם השנייה.
למכונות ההצפנה מבוססות הרוטור היה משקל מכריע במלחמת העולם השנייה.
המכונות שימשו בעיקר לתקשורת מאובטחת בין כוחות הצבא לבין המפקדות ובחילות הים.
רוב מכונות ההצפנה פוצחו על ידי מנתחי הצפנים של כוחות המודיעין.
יחידת המודיעין הסודית של הבריטים בבלצ'לי פארק, הצליחה בזמן מלחמת העולם השנייה ליירט ולפענח שדרים מוצפנים של הצבא הגרמני ששודרו באמצעות מכונות הצפנה מסוג זה.
אלן טיורינג, שהניח את היסודות להמצאת המחשב המודרני, עמד בראש צוות מנתחי הצפנים הבריטיים שפיצח את האניגמה.
הודות לכך, השיגו בעלות הברית יתרון משמעותי במלחמה.
גם בעלות הברית עשו שימוש במכונות הצפנה שונות כמו TypeX הבריטית ו-SIGABA האמריקאית (שככל הידוע לא פוצחה בעודה בשירות פעיל).
בספרו של וינטרבותאם The Ultra Secretes צוטט גנרל דווייט אייזנהאואר לאחר המלחמה שלמודיעין האולטרה הייתה השפעה "נחרצת", כלשונו, על ניצחון בעלות הברית במלחמת העולם השנייה.
כמו כן טוען וינטרבותאם בספרו שהמלחמה הייתה עשויה להיגמר במפלה מוחלטת אילו לא הייתה קיימת אולטרה.
ניתוח סטטיסטי של צפנים קלאסיים
כמעט לכל הצפנים הקלאסיים המנויים חשיבות היסטורית בלבד והם אינם בטוחים כיום לשימוש כלל.
זאת בשל העובדה שהם סובלים מבעיה יסודית הנקראת יתירות.
בכל שפה ישנן אותיות ששכיחותן גבוהה מזו של האחרות.
בשפה העברית למשל, האות יו"ד מופיעה בשכיחות של 11.5 אחוז בערך מסך כל האותיות בטקסט נפוץ לעומת האות טי"ת ששכיחותה היא 1.2 אחוז בקירוב.
מידע סטטיסטי על התפלגות האותיות בשפה ספציפית, עשוי לסייע בידי מנתחי הצופן בחשיפת המסר ללא צורך במפתח, או אף בחשיפת המפתח עצמו מתוך טקסט מוצפן קצר יחסית.
קיימות מספר שיטות לפענוח צופן רב-אלפביתי עם מפתח קצר, בהן שיטת קסיסקי או מבחן קסיסקי, בה מנסים לאתר את גודל המפתח מתוך מקטעים החוזרים על עצמם בטקסט המוצפן.
משנמצא אורך המפתח, מחלקים את הטקסט המוצפן לגושים באורך המפתח ומפעילים ניתוח סטטיסטי על כל גוש בנפרד בהתבסס על שכיחות האותיות.
עד מלחמת העולם השנייה עסקו בקריפטוגרפיה בעיקר גורמים צבאיים, גופי מודיעין, דיפלומטים ומרגלים.
עם המצאת המחשב והתרחבות היקף השימוש בו, גבר הצורך באמצעי קריפטוגרפיים גם במגזר הפרטי והעסקי.
המחקר המדעי המואץ החל בעיקר באמצע שנות השבעים של המאה העשרים, כאשר הבסיס התאורטי מסתמך בעיקר על עבודתו של קלוד שאנון, אבי תורת האינפורמציה, שביסס ב-1949 את התאוריה המתמטית של ההצפנה.
שנון הגדיר לראשונה, באופן מתמטי, עד כמה צופן מסוים בטוח לשימוש וכן הוכיח כי צופן פנקס חד-פעמי מספק סודיות מושלמת.
תקן ההצפנה הראשון, DES, שהתקבל ב-1975, פיתוח של צוות מתמטיקאים מיבמ בשיתוף פעולה עם NSA, היה נקודת ציון חשובה שהגבירה את ההתעניינות הציבורית בתחום.
אולם פריצת הדרך אולי החשובה ביותר, אירעה באותה שנה, המצאת ענף חשוב בתורת ההצפנה הקרוי מפתח-פומבי, על ידי ויטפילד דיפי ומרטין הלמן
במרוצת השנים הפכה אמנות הקריפטוגרפיה שאופיה היה בעיקר לקסיקוגרפי, לתורה מדעית המבוססת על היבטים תאורטיים שונים בתחום המתמטיקה כתורת הסיבוכיות, תורת המספרים וסטטיסטיקה.
הקריפטוגרפיה המודרנית היא חלק בלתי נפרד מחיינו ומיושמת באופן מעשי בעיקר באבטחת תקשורת, אינטרנט ורשתות מחשבים.
כמעט כל אדם שברשותו מחשב עושה שימוש יומיומי בקריפטוגרפיה לביצוע פעולות בסיסיות ככניסה לחשבון דואר אלקטרוני, חשבון בנק, גישה לרשת מקומית או המסחר האלקטרוני.
כל אדם שברשותו מכשיר טלפון סלולרי או כרטיס אשראי עושה שימוש בקריפטוגרפיה אם באופן עקיף או ישיר.
הצפנת קריימר-שׁוּפּ היא מערכת הצפנה א-סימטרית פרקטית, מוכחת כבטוחה סמנטית נגד התקפת מוצפן-נבחר שהומצאה ב-1998 על ידי רונלד קריימר מהמכון הטכנולוגי של ציריך וויקטור שופ ממעבדות IBM והוצגה בוועידת CRYPTO '98 בקליפורניה.
ביטחונה מסתמך על קושיה המשוער של בעיית הכרעה דיפי-הלמן והיא הרחבה של צופן אל-גמאל.
שבניגוד לאחרון שנקרא חשיל ואינו מוגן כלל כנגד התקפת מוצפן-נבחר (בקיצור CCA), לגרסת קריימר-שופ נוספו כמה אלמנטים כדי להבטיח אי-חשילות (Non-malleability) ועמידות כנגד התקפת CCA בשילוב של פונקציית גיבוב חד-כיוונית אוניברסלית ומחולל מספרים אקראיים בטוח.
הגדרת ביטחון סמנטי כפי שהוגדרה לראשונה על ידי גולדווסר ומיקלי מייצגת את האינטואיציה המובנת שמתקיף פסיבי לא יוכל ללמוד מאומה על הטקסט המקורי מתוך התבוננות בטקסט המוצפן בלבד.